能量均衡的無線傳感器網(wǎng)絡(luò)分簇方法

摘要：在對節(jié)點通信模式和簇群劃分過程分析的基礎(chǔ)上，提出一種在節(jié)點分布不均勻的條件下，構(gòu)建能量均衡簇群的方法。該算法兼顧了簇群成員節(jié)點與簇頭通信的能量消耗和簇群能耗負載，實現(xiàn)各簇群間能耗的平衡。仿真表明，該方法在網(wǎng)絡(luò)生命期、節(jié)點平均生命期和網(wǎng)絡(luò)擴展性方面比基于最短距離的分簇算法具有更好的性能。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò); 簇群劃分; 能量均衡

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)03－0878－03

0引言

近年來，結(jié)合無線通信技術(shù)、微電機系統(tǒng)(microelectromechanism system，MEMS)和傳感器技術(shù)的無線傳感器網(wǎng)絡(luò)越來越受到學(xué)術(shù)界和工程技術(shù)人員的關(guān)注。一方面，它提高了軍事和民用領(lǐng)域諸多應(yīng)用的性能，如戰(zhàn)場事態(tài)監(jiān)視、災(zāi)害數(shù)據(jù)收集和環(huán)境監(jiān)測等，而采用傳統(tǒng)技術(shù)則需要極高的成本并具有較大的風(fēng)險；另一方面，無線傳感器網(wǎng)絡(luò)技術(shù)利用飛機或人工在監(jiān)測區(qū)域拋撒傳感器節(jié)點部署網(wǎng)絡(luò)，節(jié)點以Ad hoc方式自組織、自配置運行，在時間和空間上持續(xù)感知監(jiān)測對象的溫度、聲波、壓力等參數(shù)。但這種特殊運行的方式也給網(wǎng)絡(luò)維護、管理帶來諸多挑戰(zhàn)[1]。WSNs的基本組成單位是配備有感知、計算和通信能力的節(jié)點，配備十分有限的硬件資源，包括CPU、內(nèi)存和電池。網(wǎng)絡(luò)部署后對電池的充電和更換幾乎不可能，節(jié)點一直工作到電能耗盡為止。所以電能是WSNs節(jié)點的一個非常重要的資源，應(yīng)在網(wǎng)絡(luò)設(shè)計和實施過程中加以仔細考慮，盡可能延長節(jié)點的使用期，以滿足應(yīng)用需求。

節(jié)點電能的消耗主要用于無線傳輸/接收數(shù)據(jù)、處理查詢請求、數(shù)據(jù)融合處理和感知環(huán)境參數(shù)等。其中無線通信消耗的能量占絕大部分。采用分簇技術(shù)[2~6]可以有效地降低節(jié)點能耗，延長網(wǎng)絡(luò)使用期，此外采用分簇技術(shù)組織的網(wǎng)絡(luò)在可擴展性、魯棒性和安全性等方面具有較好的優(yōu)勢。分簇技術(shù)是將傳感器節(jié)點劃分成多個簇群，如圖1所示，網(wǎng)絡(luò)中每個節(jié)點必歸屬一個簇群；每個簇群中由一個節(jié)點充當(dāng)簇頭節(jié)點(cluster head， CH)，負責(zé)簇群成員節(jié)點數(shù)據(jù)的收集，經(jīng)過數(shù)據(jù)融合處理后再通過直接或間接的方式傳送給匯聚節(jié)點(sink)，避免每個節(jié)點直接長距離與sink節(jié)點通信，減少節(jié)點發(fā)送數(shù)據(jù)的能耗。此外，數(shù)據(jù)的融合處理減少發(fā)送數(shù)據(jù)的長度，也降低了每個節(jié)點處理和通信時的能耗。

WSNs通常采用密集部署方式，單位面積內(nèi)節(jié)點數(shù)目眾多，并且監(jiān)測區(qū)域較大。如果節(jié)點部署不均勻，簇群在覆蓋面積相同的情況下，CH節(jié)點能耗將隨節(jié)點部署密度、監(jiān)測目標數(shù)和感知事件數(shù)量的增大而增大，必將造成以下結(jié)果：成員節(jié)點越多的簇群，其CH節(jié)點能耗速率越快，進而提前結(jié)束生命期; CH失效后，造成網(wǎng)絡(luò)重新發(fā)起成簇過程，將導(dǎo)致更多的通信量。為避免這種情況，在簇群劃分過程中，除了考慮成員節(jié)點與CH通信的能耗外，還必須對每個簇群的能耗負載進行評估，以建立能耗分布均勻的簇群。

為此需要解決以下最優(yōu)化問題：

minimize max{Ecluster(1)-E(c)，Ecluster(2)-E(c)，…，

Ecluster(m)-E(c)} (1)

其中：Ecluster(i)表示每個簇群的能耗代價總和；E(c)表示所有簇群的能耗平均值；m表示簇群數(shù)目。

本文提出的方法可以同時滿足數(shù)據(jù)收集類型WSNs和事件監(jiān)測類型WSNs。前者節(jié)點周期性地采集數(shù)據(jù)傳送給CH節(jié)點；后者節(jié)點一直處于睡眠狀態(tài)， 當(dāng)某種事件發(fā)生時，變?yōu)榛顒訝顟B(tài)開始采集數(shù)據(jù)。

1系統(tǒng)模型

網(wǎng)絡(luò)以圖1所示的分簇方式組織節(jié)點，節(jié)點分為CH節(jié)點和普通節(jié)點。CH節(jié)點與普通節(jié)點在性能、配置上相同。惟一不同之處在于CH節(jié)點的電能使用限制小，可以實現(xiàn)長距離的無線通信，即CH和CH以及CH和sink之間。不對節(jié)點部署密度作任何假設(shè)，但保證網(wǎng)絡(luò)是連通的，不存在孤立的節(jié)點。節(jié)點在部署后不具備移動能力。節(jié)點間建立雙向鏈路的條件是當(dāng)且僅當(dāng)彼此都處于對方的通信半徑之內(nèi)。假設(shè)在簇群內(nèi)，CH節(jié)點與成員節(jié)點之間的鏈路均為雙向鏈路。CH可以逐級控制發(fā)射功率，以實現(xiàn)通信半徑的變化。本文假設(shè)任何一個CH節(jié)點至少與其他一個CH相連。簇群內(nèi)通信采用共享信道方式，如無碰撞的MAC協(xié)議TDMA。另外，不考慮因碰撞和重發(fā)所產(chǎn)生的能量消耗，所有數(shù)據(jù)包具有相同的長度。

網(wǎng)絡(luò)部署之前，事先為每個節(jié)點分配一個惟一ID號，或節(jié)點在網(wǎng)絡(luò)部署后采用文獻[8]提出的方法獲得一個惟一的ID號。節(jié)點可以配備GPS設(shè)備從而獲得自身的物理位置數(shù)據(jù)，或利用文獻[7]提出的方法在沒有GPS支持環(huán)境下獲知物理位置數(shù)據(jù)。

此外，網(wǎng)絡(luò)生存期定義為從網(wǎng)絡(luò)部署開始到出現(xiàn)第一個因電能耗盡而失效的節(jié)點所需要的時間[2]。

2網(wǎng)絡(luò)通信模型

無線通信消耗節(jié)點絕大部分能量。本文節(jié)點采用文獻[3]的通信模型。建立通信鏈路的兩個節(jié)點距離為d，當(dāng)d≤dcrossover時，能量消耗與d2成正比；當(dāng)d>dcrossover，能量消耗與d4成正比。其中：dcrossover為距離閾值。當(dāng)節(jié)點傳送l bit長度的數(shù)據(jù)到距離為d的另一個節(jié)點時，發(fā)送節(jié)點的能耗表示為

ETx(l，d)=lEelec+lεfsd2 d

lEelec+lεmpd4d≥dcrossover(2)

其中：lEelec表示用于數(shù)據(jù)編碼、調(diào)制解調(diào)等的電量消耗；表達式中第二項則是根據(jù)傳輸距離不同而選擇不同發(fā)射方式的電量消耗。節(jié)點接收l bit數(shù)據(jù)所消耗的能量為

ERx(l)=l×Eelec(3)

僅用于信號接收、解碼等過程，與距離d無關(guān)。本文中，CH通信半徑rcluster

3能量均衡的分簇算法

網(wǎng)絡(luò)部署后，CH和普通節(jié)點物理位置分布不均勻。如果不考慮節(jié)點密度而只根據(jù)CH通信范圍大小、簇群成員節(jié)點數(shù)目進行分簇，必然導(dǎo)致因節(jié)點在物理位置上的分布不均勻而產(chǎn)生的各個簇群能耗的不均勻，節(jié)點密度大的簇群能耗高，反之則低，極大地影響了網(wǎng)絡(luò)生存期。本文的目標是建立一個能量消耗均衡的網(wǎng)絡(luò)簇群拓撲結(jié)構(gòu)，從而實現(xiàn)整個網(wǎng)絡(luò)中能耗的均勻分布。為此，簇群劃分過程中，每個CH在選擇哪些普通節(jié)點可以成為簇群成員節(jié)點時，必須根據(jù)自己所在簇群的能耗代價以及當(dāng)前剩余的電能多少來控制簇群規(guī)模的大小。能耗代價包括CH與成員節(jié)點通信的能耗、簇群數(shù)據(jù)處理能耗、簇群總的節(jié)點數(shù)目以及CH的當(dāng)前剩余電能水平。網(wǎng)絡(luò)節(jié)點簇群劃分過程分為初始化和成簇兩個階段。

網(wǎng)絡(luò)部署后進入初始化階段。每個節(jié)點通過配備的GPS系統(tǒng)或定位算法計算出自己的物理位置，并將此信息和節(jié)點當(dāng)前電量值以及ID號向外廣播。于是，每個CH節(jié)點獲得通信半徑內(nèi)所有相鄰節(jié)點的位置、ID和電量信息。CH的鄰節(jié)點集合表示為

NSeti={Sj|（Ri>dCHi-j)∧(Rj>dCHi-j)}

其中：Ri是CH的通信半徑；dCHi-j是CH與節(jié)點Sj之間的距離。根據(jù)式(2)計算得到CH與鄰節(jié)點通信的能耗總和：

ECH_Total=∑i∈NSetiECH_i

其中：ECH_i為CH節(jié)點與鄰節(jié)點集合NSet中每個節(jié)點通信的能耗

ECH_i=ETx+ERx=(Eelec+εfsd2CHi-j)l+l×Eelec

CH與整個NSet通信的能量消耗代價可以表示為節(jié)點通信能耗ECH_Total和簇頭處理數(shù)據(jù)能耗Eprocess之和：

CHenergy_load=ECH_Total+Eprocess(4)

其中：Eprocess與集合NSet中節(jié)點數(shù)目n成正比。本文用性能參數(shù)PCH來評估CH節(jié)點的成簇能力，并向網(wǎng)絡(luò)中其他CH廣播該參數(shù)。

PCH=CHenergy_load/Ecurrent(5)

其中：Ecurrent為節(jié)點當(dāng)前剩余電量。

成簇階段中，每個CH節(jié)點根據(jù)收到的其他CH節(jié)點的PCH值，計算下面的目標函數(shù)：

D=1/NCH∑NCHi=1|PCH-E(PCH)|(6)

其中：NCH為網(wǎng)絡(luò)中CH數(shù)量；E(PCH)表示網(wǎng)絡(luò)中所有簇群能量代價的期望值。為實現(xiàn)能耗均勻分布，將式(6)的計算值最小化，作為CH控制簇群規(guī)模大小的依據(jù)，與本文開始提出的能量優(yōu)化表達式(1)相對應(yīng)。首先，每個CH將鄰節(jié)點集合NSet中的節(jié)點分為兩類集合（第一類是只被一個CH通信范圍覆蓋的節(jié)點集；剩下的能被多個CH通信范圍覆蓋的節(jié)點為第二類）。用參數(shù)c表示節(jié)點可到達的CH數(shù)量。前者用節(jié)點集合DSet表示：

DSeti={Sj|(Sj∈NSeti)∧(m≠i，SjNSetm)}

為保證網(wǎng)絡(luò)的連通性，這類節(jié)點必須首先劃歸到能惟一與之通信的CH所構(gòu)成的簇群中，同時CH利用式(5)求得簇群的性能參數(shù)PCH。由于節(jié)點分布的不均勻性，各簇群的PCH不相同，在對第二類節(jié)點進行劃分時，按照最小化目標函數(shù)式(6)的方式進行。每個CH節(jié)點通過調(diào)節(jié)發(fā)射功率，逐級增大通信半徑，并對每個新加入簇群覆蓋范圍的節(jié)點進行考查。例如該節(jié)點當(dāng)前尚未加入任何簇群，則CH計算包含此節(jié)點后，簇群的性能參數(shù)PCH。經(jīng)過信息交換后，式(6)計算結(jié)果最小的CH獲此次考查的節(jié)點。如此下去，直到所有節(jié)點都被劃分到簇群中。最后，每個CH向外廣播屬于自己成員節(jié)點的ID號，于是收到廣播的節(jié)點可以確定自己所歸屬的簇群。

4性能評估

為評估本文提出方法的性能，筆者將該算法與基于最短距離原理的LEACH算法[3]和能量感知分簇算法HEED[2]進行了比較。為此，構(gòu)建以下網(wǎng)絡(luò)仿真環(huán)境：500個節(jié)點在1 000×1 000 m2的二維平面隨機分布，其中含10個CH節(jié)點。普通節(jié)點配備了2 J電能，最大的通信半徑為200 m；CH節(jié)點可以覆蓋整個網(wǎng)絡(luò)。數(shù)據(jù)包長度為10K bit，分簇信息數(shù)據(jù)包長度為2K bit，節(jié)點以1 packet/s的恒定速率發(fā)送數(shù)據(jù)。每個節(jié)點預(yù)分配惟一的ID號。簇群內(nèi)通信采用無沖突協(xié)議，不考慮數(shù)據(jù)傳輸錯誤和重傳等情況。為節(jié)省能量，節(jié)點在沒有采集數(shù)據(jù)和通信時處于睡眠狀態(tài)，當(dāng)有事件發(fā)生或定時器超時則轉(zhuǎn)為活動狀態(tài)。仿真過程中，本文以隨機方式切換節(jié)點的狀態(tài)來模擬現(xiàn)實中節(jié)點工作的情形。其余的有關(guān)通信模型參數(shù)的設(shè)置參見文獻[2]。

在最短距離路由算法[2，3]中，節(jié)點根據(jù)自己到達不同CH的距離遠近，選擇距離最近的CH加入。當(dāng)節(jié)點在物理位置分布不均勻時，密度大的區(qū)域CH的成員節(jié)點過多，簇群的能耗較大，而密度小的區(qū)域，CH距離各節(jié)點較遠，加入的節(jié)點較少，簇群的能耗較低。文獻[2，3]的仿真結(jié)果均建立在節(jié)點分布均勻的假設(shè)基礎(chǔ)上。在節(jié)點分布不均勻的情況下，與本文提出的方法在網(wǎng)絡(luò)節(jié)點平均生命期和網(wǎng)絡(luò)生命期的比較結(jié)果如圖2和3所示。從中得知，由于在簇群的產(chǎn)生過程中，本文方法除了考慮成員節(jié)點與CH通信的能耗外，同時還對整個簇群的能量代價進行評估，從而在整個網(wǎng)絡(luò)中建立了能量均衡的簇群分布。所以節(jié)點和網(wǎng)絡(luò)的生命期獲得了較好的性能。

圖2節(jié)點平均生命期圖3網(wǎng)絡(luò)生命期

圖4顯示了兩種算法在網(wǎng)絡(luò)擴展性與簇群平均能耗的標準差之間關(guān)系的對比。從圖中可以看出，伴隨網(wǎng)絡(luò)規(guī)模的擴大，最短路徑算法的簇群平均負載標準差呈上升趨勢，說明節(jié)點分布不均勻時，簇群之間的能耗差距隨著網(wǎng)絡(luò)規(guī)模的擴大而增大。采用能量均衡分簇算法的網(wǎng)絡(luò)，由于考慮了網(wǎng)絡(luò)中所有簇群的能耗情況，簇群間能耗差距基本保持不變。

5結(jié)束語

本文對無線傳感器網(wǎng)絡(luò)的節(jié)點簇群劃分問題進行了探討，提出一種在節(jié)點分布不均勻的條件下，實現(xiàn)能量消耗均衡的分簇方法，更好地延長了網(wǎng)絡(luò)生命周期。該方法兼顧了簇群成員節(jié)點與簇頭節(jié)點通信的能量消耗，以及整個簇群能耗負載狀況，實現(xiàn)了各簇群間能耗的平衡。仿真表明，該算法在節(jié)點平均生命期、網(wǎng)絡(luò)生命期和網(wǎng)絡(luò)擴展性方面，與最短路徑的成簇算法相比，具有更好的性能。

參考文獻：

[1]AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks: a survey [J]. Computer Networks， 2002，38(4):393－422.

[2]YOUNIS S， FAHMY S. Distributed clustering in Ad hoc sensor networks: a hybrid， energyefficient approach [C]//Proc of IEEE INFOCOM. Hong Kong:[s.n.]， 2004.

[3]HEINZELMAN W， CHANDRAKASAN A， BALAKRISHNAN H. An applicationspecific protocol architecture for wireless microsensor networks [J]. IEEE Trans Wireless Comm，2002， 1(4) :660－670.

[4]BLOUGH D M， SANTI P. Investigating upper bounds on network lifetime extension for cellbased energy conservation techniques in stationary Ad hoc networks[C]//Proc of ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM). 2002.

[5]AMIS D， PRAKASH R， VUONG T H P， et al. Maxmin dcluster formation in wireless Ad hoc networks[C]//Proc of IEEE INFOCOM. 2000.

[6]BHARDWAJ M， GARNETT T， CHANDRAKASAN A P. Upper bounds on lifetime of sensor networks[C]//Proc of IEEE Internatio￣nal Conference on Communications (ICC’01). Helsinki:[s.n.]， 2001.

[7]NICULESCU D， NATH B. Ad hoc positioning system (APS) using AoA[C]//Proc of IEEE INFOCOM. San Francisco:[s.n.]， 2003.

[8]湯波，周明天.無線傳感器網(wǎng)絡(luò)節(jié)點命名算法的研究[J].華中科技大學(xué)學(xué)報:自然科學(xué)版，2005，33(Z1): 54－56.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”