無線傳感器網絡能量均衡分簇路由協議

趙成林,毛 松,譚 虎

(北京郵電大學無線網絡實驗室,北京100876)

0 引言

無線傳感器網絡是近年來綜合了傳感器技術、嵌入式計算技術、分布式信息處理技術和無線通信技術等多學科的研究成果迅速發展的一門技術,在工業、農業、軍事、環境、醫療、家用、保健和交通等領域具有廣闊的應用前景。

無線傳感器網絡節點能量的有限性使高能效路由協議的研究成為無線傳感器網絡研究熱點之一。無線傳感器網絡的路由協議按照拓撲結構可分為平面型和層次型2類。平面型路由需要維護動態變化的路由表,維護相對困難且擴展性差。而層次型路由控制信息較少,可擴展性好,適合大規模的無線傳感器網絡。LEACH協議[1]是一種典型的基于簇結構的層次路由協議,得到了非常廣泛的應用,其成簇思想也在很多后期發展的協議中得到應用,如TEEN協議[2]、PEGASIS協議[3]和HEED協議[4]等。

1 LEACH協議及性能分析

LEACH協議將WSN中的節點分為簇首節點和普通節點,普通節點采集數據后發送到簇首節點,簇首節點進行數據的融合后再發送到匯聚節點(基站)。一般來講,簇首節點的能量消耗要大于普通節點的能量消耗。在LEACH算法中定義了“輪”的概念,每一輪包括簇的建立和穩定的數據傳輸2個階段,每個節點通過周期性輪轉都有可能成為簇首,因此均衡了網絡節點的能量負載。

在簇的建立階段,每個節點自動生成一個0～1間的隨機數RandomNumber,若RandomNumber小于某門限值T(n),則此節點在本輪中被選為簇首。

式中,p為網絡中簇首節點占總節點數的百分比;r為已完成的輪數;G為在最后rmod(1/p)輪中還沒有當選簇首的節點集合。

節點當選為簇首后向周圍節點廣播自己是簇首的消息ADV,非簇首節點收到該消息后,根據接收到的信號強度選擇信號最強,即距離最近的簇首發送加入簇請求消息,此后簇首節點設定一個TDMA時間表為其簇成員節點分配發送時隙,同時產生一個本簇內使用的CDMA編碼,連同TDMA時間表一起發送給本簇的成員節點,至此,簇建立階段結束。

在穩定運行階段,簇成員節點采集數據并在TDMA時間表確定的時隙內向簇首節點發送數據,然后進入睡眠狀態以節省能量,直到下一個傳輸時刻的到來。簇首節點接收到本簇所有成員節點的數據形成一幀數據,然后經過數據融合后發送到基站。每隔一定時間后,整個網絡重新進入簇形成階段開始新一輪的簇首選舉過程。

LEACH協議采用層次結構,與平面路由相比簡化了路徑的選擇及路由信息的存儲,同時自適應隨機選取簇首節點,利于實現全網負載的均衡。但是LEACH協議存在的下列3個方面的問題制約著網絡能量的均衡消耗:

①節點擔任簇首是嚴格的等概率選擇,能量較低的節點一旦成為簇首很容易耗盡能量而死亡;

②簇的形成過程中只考慮了節點與被選簇首之間的距離,而沒有考慮能量因素,因此可能導致能量較低的簇首節點過快的消耗能量而死亡;

③簇首節點以單跳形式向基站傳送數據,不僅會導致距離基站較遠節點的能量消耗過大,也不利于網絡的大規模擴展。

2 改進的能量均衡分簇路由協議

針對LEACH協議中存在的上述問題,提出了一種改進的高能效分簇路由協議,協議在簇首選擇、簇的形成和簇間路由3個方面均引入傳感器節點的能量因子,均衡了網絡的能量消耗,全面提高了網絡的生命周期。

2.1 能量模型

傳感器節點的能量損耗采用文獻[2]中的自由空間模型和多徑衰減模型進行計算。由文獻[2]得知,當通信距離小于閾值d0時,發送數據的能量消耗與距離的平方成正比,否則與距離的4次方成正比。

當發送方發送l比特信息到距離為d的接收方時,發送方消耗的能量由發射電路損耗和功率放大損耗2個部分構成,可表示為:

同時,接收方消耗的能量為:

式中,Eelec為無線收發單位信息電路所消耗的能量;εfriss-amp、εtwo-ray-amp分別為2種信道模型下功率放大所需要的能量。其中d0的表達式為:

2.2 簇首的選擇

為了均衡傳感器節點的能量,改進的算法在簇首選擇時考慮了節點的當前能量與歷史能量消耗2種信息,以增大當前具有較高能量的節點成為簇首的概率。具體的方法是對LEACH協議中選擇簇首的門限值T(n)進行如下修正:

式中,Eresidual為備選簇首節點的當前能量;Etotal為網絡中所有傳感器節點當前的總能量;Er-1_average為 上一輪簇首形成過程中傳感器節點的平均能量;Er-1_dissipate為上一輪簇首形成過程中節點消耗的能量。

為了方便,采用下面的方法對Er-1_average的值進行估計[5]。

式中,N為網絡中節點的數目;Ei(r-1)為第r-1輪中節點i的剩余能量;E0為傳感器網絡建立時各節點的總能量。

假設理想情況下網絡中所有節點的生命周期相同,設R為網絡運行的總輪數,則有

式中,Eround為網絡運行每一輪中消耗的能量,

式中,l為一個數據包含的比特數;k為網絡中簇首的個數;EDA為簇首節點融合單位數據消耗的能量;dtoBS為簇首到基站的平均距離;dtoCH為成員節點到簇首的平均距離。假設節點在M×M區域均勻部撒,則有[6]

將式(9)和式(10)代入式(8)求得Eround值,進而代入式(7)中求得R值,最后將R值代入式(6)中即可求得Er-1_ average值。

2.3 簇的形成

式中,Einitial為每個節點已知的初始能量;w為權重因子。普通節點選擇有最大權值的簇首節點加入,然后當選為簇首的節點創建TDMA時間表,向簇成員節點分配時隙和簇內CDMA編碼。式(11)的意義在于成簇階段普通節點選擇簇首加入其中時綜合權衡了備選簇首節點的當前能量信息以及普通節點距離備選簇首節點的距離因素,這樣做主要基于以下2點:

①考慮備選簇首節點的當前能量信息可以有效避免當前能量較低的簇首節點加入過多的簇成員節點,使簇首節點的負載過重造成能量消耗過速;

②根據上述能量模型,簇內通信的消耗和距離的平方成正比(假設簇首節點和簇成員節點的距離小于閾值d0),考慮普通節點距離備選簇首節點的距離因素可以有效降低簇內通信代價,節省簇內通信能量消耗。

權重因子w用于平衡能量和距離2個因素在weight中所占比例,以使實驗效果得到最優。實驗中從0到1變化w的取值,觀察網絡中第1個節點死亡的時間(定義為網絡的生命周期)隨之變化的趨勢,結果如圖1所示,圖中當w等于0.8時,網絡的生命周期達到最大值,因此將w的值確定為0.8。

為了均衡簇內節點的能量消耗,在簇首節點廣播的ADV消息中增加自身的能量信息Eresidual,非簇首節點在收到ADV消息后首先根據信號強度計算本節點與該備選簇首節點的距離Dch。通過上述計算可以得出非簇首節點與所有備選簇首節點的距離,選擇上述最小值Dmin和所有備選簇首節點能量的最小值Emin,計算所有備選簇首節點的權重為:

圖1 第1節點死亡時間隨w值變化關系

2.4 簇間路由的建立

假設簇首節點A向基站BS傳輸數據,做如下定義:

①定義當前輪中簇首節點的集合為I;

②定義D(X)=+,X∈I其中dA-X表示節點A到節點X的距離,dX-BS表示節點X到基站的距離。

分別計算集合I中除節點A以外節點的函數值D(X),找出其中的最小值D(X)min,當滿足以下2個條件時,將節點X作為節點A的下一跳節點,否則,節點A直接向基站傳送數據。

①D(X)min＜,dA-BS為節點A到基站的距離;

②EX＞EA,EX、EA分別為節點X和A的當前能量。

上述2個條件既可以保證通過中繼節點轉發的能量消耗小于節點直接向基站發送數據的能量消耗,又可以避免低能量節點頻繁轉發數據造成的過早死亡。

此外,為了有效接收上一跳簇首節點發送的數據,在簇形成階段備選簇首節點創建TDMA時間表時增加一個時隙,用于接收簇間數據,同時,當前簇首節點在向下一跳簇首節點傳送數據時采用目的節點的簇內CDMA編碼,這樣可以有效地改善簇間數據傳輸帶來的沖突和干擾。

3 仿真與分析

在Linux下用NS2仿真軟件對改進后的路由協議進行仿真,仿真場景為100個傳感器節點均勻部撒在100 m×100 m范圍內,基站位于(50 m,175 m)位置,每個節點的初始能量為2 J,每個數據包的分組長度為500 byte,p=5%,其他能量模型相關的參數取自文獻[2],即EDA=5 nJ,Eelec=50 nJ/bit/m,εfriss-amp=10 pJ/bit/m2,εtwo-ray-amp=0.0013 pJ/bit/m4。仿真中用CEBRP(Cluster based Energy Balance Routing Protocol)表示改進的協議。

圖2為應用LEACH協議和改進協議的存活節點數隨時間的變化規律。可以看出,LEACH協議中第1個節點死亡時間為400 s,節點全部死亡的時間為500 s左右,而改進的協議第1個節點死亡時間為680 s左右,節點全部死亡的時間為1 000 s左右,很明顯后者較好地延長了網絡的生存壽命。

圖2 2種協議節點存活數比較

圖3為分別應用LEACH協議和改進協議的網絡能量消耗隨時間的變化過程,可以看出應用改進協議的網絡能量消耗速度明顯小于應用LEACH協議的網絡能量消耗。

圖3 2種協議中網絡總耗能比較

圖4為分別應用LEACH協議和改進協議的網絡基站接收到的數據量和能量消耗關系圖,由圖可知相同能量消耗情況下應用改進后協議的網絡基站所接收到的數據明顯比應用LEACH協議的網絡基站接收到的數據量大。

圖4 2種協議中消耗能量與接收數據比較

4 結束語

上述深入研究了無線傳感器網絡經典的層次路由協議LEACH,并在此基礎上針對LEACH協議存在的缺陷進行了改進。改進后的協議在簇首的選擇和簇的形成環節引入了傳感器節點的能量因子,有效避免了低能量節點過早死亡的現象。同時采用基于能量比較的簇間多跳路由,改善了LEACH協議中簇首節點向基站直接傳輸數據造成的能量消耗過大的缺陷,從而從整體上均衡了傳感器節點的能量消耗,大幅度地延長了網絡的使用壽命。

[1]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHMAN H.Energy-efficientCommunication ProtocolforWireless MicrosensorNetworks[C]//ProceedingsoftheHawaii International Conference on System Sciences.Piscataway,USA,2000:175-187.

[2]MANJESHWAR A,GRAWAL D P.TEEN:A Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proceedings of the 15th Parallel and Distributed Processing Symp.San Francisco,2001:2009-2015.

[3]LINDSEYS,RAGHA VENDR A C.PEGSIS:Power-Efficient Gathering in Sensor Information Systems[C]//Proceedings of the IEEEAerospace Conference'02.Montana,2002:1125-1130.

[4]YOUNIS O,FAHMY S.HEED:A Hybrid,Energy-efficent,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing 2004,3(4):366-379.

[5]SUN Yanjing,CHEN Wei,ZHANG Bei,et al.Energy-efficient Clustering Routing ProtocolBased on Weight[C]//International Conference on Wireless Communications and Siganl Processing.Nanjing,China,2009:1-5.

[6]HEINZELMAN W,CHANDRAKASAN A,BALAKRISHNAN H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans on Wireless Comm.,2002,1(4):660-670.