無(wú)線傳感器網(wǎng)絡(luò)能量均衡分簇路由協(xié)議

趙成林,毛 松,譚 虎

(北京郵電大學(xué)無(wú)線網(wǎng)絡(luò)實(shí)驗(yàn)室,北京100876)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)是近年來(lái)綜合了傳感器技術(shù)、嵌入式計(jì)算技術(shù)、分布式信息處理技術(shù)和無(wú)線通信技術(shù)等多學(xué)科的研究成果迅速發(fā)展的一門技術(shù),在工業(yè)、農(nóng)業(yè)、軍事、環(huán)境、醫(yī)療、家用、保健和交通等領(lǐng)域具有廣闊的應(yīng)用前景。

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量的有限性使高能效路由協(xié)議的研究成為無(wú)線傳感器網(wǎng)絡(luò)研究熱點(diǎn)之一。無(wú)線傳感器網(wǎng)絡(luò)的路由協(xié)議按照拓?fù)浣Y(jié)構(gòu)可分為平面型和層次型2類。平面型路由需要維護(hù)動(dòng)態(tài)變化的路由表,維護(hù)相對(duì)困難且擴(kuò)展性差。而層次型路由控制信息較少,可擴(kuò)展性好,適合大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)。LEACH協(xié)議[1]是一種典型的基于簇結(jié)構(gòu)的層次路由協(xié)議,得到了非常廣泛的應(yīng)用,其成簇思想也在很多后期發(fā)展的協(xié)議中得到應(yīng)用,如TEEN協(xié)議[2]、PEGASIS協(xié)議[3]和HEED協(xié)議[4]等。

1 LEACH協(xié)議及性能分析

LEACH協(xié)議將WSN中的節(jié)點(diǎn)分為簇首節(jié)點(diǎn)和普通節(jié)點(diǎn),普通節(jié)點(diǎn)采集數(shù)據(jù)后發(fā)送到簇首節(jié)點(diǎn),簇首節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的融合后再發(fā)送到匯聚節(jié)點(diǎn)(基站)。一般來(lái)講,簇首節(jié)點(diǎn)的能量消耗要大于普通節(jié)點(diǎn)的能量消耗。在LEACH算法中定義了“輪”的概念,每一輪包括簇的建立和穩(wěn)定的數(shù)據(jù)傳輸2個(gè)階段,每個(gè)節(jié)點(diǎn)通過(guò)周期性輪轉(zhuǎn)都有可能成為簇首,因此均衡了網(wǎng)絡(luò)節(jié)點(diǎn)的能量負(fù)載。

在簇的建立階段,每個(gè)節(jié)點(diǎn)自動(dòng)生成一個(gè)0～1間的隨機(jī)數(shù)RandomNumber,若RandomNumber小于某門限值T(n),則此節(jié)點(diǎn)在本輪中被選為簇首。

式中,p為網(wǎng)絡(luò)中簇首節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的百分比;r為已完成的輪數(shù);G為在最后rmod(1/p)輪中還沒(méi)有當(dāng)選簇首的節(jié)點(diǎn)集合。

節(jié)點(diǎn)當(dāng)選為簇首后向周圍節(jié)點(diǎn)廣播自己是簇首的消息ADV,非簇首節(jié)點(diǎn)收到該消息后,根據(jù)接收到的信號(hào)強(qiáng)度選擇信號(hào)最強(qiáng),即距離最近的簇首發(fā)送加入簇請(qǐng)求消息,此后簇首節(jié)點(diǎn)設(shè)定一個(gè)TDMA時(shí)間表為其簇成員節(jié)點(diǎn)分配發(fā)送時(shí)隙,同時(shí)產(chǎn)生一個(gè)本簇內(nèi)使用的CDMA編碼,連同TDMA時(shí)間表一起發(fā)送給本簇的成員節(jié)點(diǎn),至此,簇建立階段結(jié)束。

在穩(wěn)定運(yùn)行階段,簇成員節(jié)點(diǎn)采集數(shù)據(jù)并在TDMA時(shí)間表確定的時(shí)隙內(nèi)向簇首節(jié)點(diǎn)發(fā)送數(shù)據(jù),然后進(jìn)入睡眠狀態(tài)以節(jié)省能量,直到下一個(gè)傳輸時(shí)刻的到來(lái)。簇首節(jié)點(diǎn)接收到本簇所有成員節(jié)點(diǎn)的數(shù)據(jù)形成一幀數(shù)據(jù),然后經(jīng)過(guò)數(shù)據(jù)融合后發(fā)送到基站。每隔一定時(shí)間后,整個(gè)網(wǎng)絡(luò)重新進(jìn)入簇形成階段開(kāi)始新一輪的簇首選舉過(guò)程。

LEACH協(xié)議采用層次結(jié)構(gòu),與平面路由相比簡(jiǎn)化了路徑的選擇及路由信息的存儲(chǔ),同時(shí)自適應(yīng)隨機(jī)選取簇首節(jié)點(diǎn),利于實(shí)現(xiàn)全網(wǎng)負(fù)載的均衡。但是LEACH協(xié)議存在的下列3個(gè)方面的問(wèn)題制約著網(wǎng)絡(luò)能量的均衡消耗:

①節(jié)點(diǎn)擔(dān)任簇首是嚴(yán)格的等概率選擇,能量較低的節(jié)點(diǎn)一旦成為簇首很容易耗盡能量而死亡;

②簇的形成過(guò)程中只考慮了節(jié)點(diǎn)與被選簇首之間的距離,而沒(méi)有考慮能量因素,因此可能導(dǎo)致能量較低的簇首節(jié)點(diǎn)過(guò)快的消耗能量而死亡;

③簇首節(jié)點(diǎn)以單跳形式向基站傳送數(shù)據(jù),不僅會(huì)導(dǎo)致距離基站較遠(yuǎn)節(jié)點(diǎn)的能量消耗過(guò)大,也不利于網(wǎng)絡(luò)的大規(guī)模擴(kuò)展。

2 改進(jìn)的能量均衡分簇路由協(xié)議

針對(duì)LEACH協(xié)議中存在的上述問(wèn)題,提出了一種改進(jìn)的高能效分簇路由協(xié)議,協(xié)議在簇首選擇、簇的形成和簇間路由3個(gè)方面均引入傳感器節(jié)點(diǎn)的能量因子,均衡了網(wǎng)絡(luò)的能量消耗,全面提高了網(wǎng)絡(luò)的生命周期。

2.1 能量模型

傳感器節(jié)點(diǎn)的能量損耗采用文獻(xiàn)[2]中的自由空間模型和多徑衰減模型進(jìn)行計(jì)算。由文獻(xiàn)[2]得知,當(dāng)通信距離小于閾值d0時(shí),發(fā)送數(shù)據(jù)的能量消耗與距離的平方成正比,否則與距離的4次方成正比。

當(dāng)發(fā)送方發(fā)送l比特信息到距離為d的接收方時(shí),發(fā)送方消耗的能量由發(fā)射電路損耗和功率放大損耗2個(gè)部分構(gòu)成,可表示為:

同時(shí),接收方消耗的能量為:

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

2.2 簇首的選擇

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

式中,Eresidual為備選簇首節(jié)點(diǎn)的當(dāng)前能量;Etotal為網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)當(dāng)前的總能量;Er-1_average為 上一輪簇首形成過(guò)程中傳感器節(jié)點(diǎn)的平均能量;Er-1_dissipate為上一輪簇首形成過(guò)程中節(jié)點(diǎn)消耗的能量。

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

式中,N為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目;Ei(r-1)為第r-1輪中節(jié)點(diǎn)i的剩余能量;E0為傳感器網(wǎng)絡(luò)建立時(shí)各節(jié)點(diǎn)的總能量。

假設(shè)理想情況下網(wǎng)絡(luò)中所有節(jié)點(diǎn)的生命周期相同,設(shè)R為網(wǎng)絡(luò)運(yùn)行的總輪數(shù),則有

式中,Eround為網(wǎng)絡(luò)運(yùn)行每一輪中消耗的能量,

式中,l為一個(gè)數(shù)據(jù)包含的比特?cái)?shù);k為網(wǎng)絡(luò)中簇首的個(gè)數(shù);EDA為簇首節(jié)點(diǎn)融合單位數(shù)據(jù)消耗的能量;dtoBS為簇首到基站的平均距離;dtoCH為成員節(jié)點(diǎn)到簇首的平均距離。假設(shè)節(jié)點(diǎn)在M×M區(qū)域均勻部撒,則有[6]

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

2.3 簇的形成

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

①考慮備選簇首節(jié)點(diǎn)的當(dāng)前能量信息可以有效避免當(dāng)前能量較低的簇首節(jié)點(diǎn)加入過(guò)多的簇成員節(jié)點(diǎn),使簇首節(jié)點(diǎn)的負(fù)載過(guò)重造成能量消耗過(guò)速;

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

權(quán)重因子w用于平衡能量和距離2個(gè)因素在weight中所占比例,以使實(shí)驗(yàn)效果得到最優(yōu)。實(shí)驗(yàn)中從0到1變化w的取值,觀察網(wǎng)絡(luò)中第1個(gè)節(jié)點(diǎn)死亡的時(shí)間(定義為網(wǎng)絡(luò)的生命周期)隨之變化的趨勢(shì),結(jié)果如圖1所示,圖中當(dāng)w等于0.8時(shí),網(wǎng)絡(luò)的生命周期達(dá)到最大值,因此將w的值確定為0.8。

為了均衡簇內(nèi)節(jié)點(diǎn)的能量消耗,在簇首節(jié)點(diǎn)廣播的ADV消息中增加自身的能量信息Eresidual,非簇首節(jié)點(diǎn)在收到ADV消息后首先根據(jù)信號(hào)強(qiáng)度計(jì)算本節(jié)點(diǎn)與該備選簇首節(jié)點(diǎn)的距離Dch。通過(guò)上述計(jì)算可以得出非簇首節(jié)點(diǎn)與所有備選簇首節(jié)點(diǎn)的距離,選擇上述最小值Dmin和所有備選簇首節(jié)點(diǎn)能量的最小值Emin,計(jì)算所有備選簇首節(jié)點(diǎn)的權(quán)重為:

圖1 第1節(jié)點(diǎn)死亡時(shí)間隨w值變化關(guān)系

2.4 簇間路由的建立

假設(shè)簇首節(jié)點(diǎn)A向基站BS傳輸數(shù)據(jù),做如下定義:

①定義當(dāng)前輪中簇首節(jié)點(diǎn)的集合為I;

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

分別計(jì)算集合I中除節(jié)點(diǎn)A以外節(jié)點(diǎn)的函數(shù)值D(X),找出其中的最小值D(X)min,當(dāng)滿足以下2個(gè)條件時(shí),將節(jié)點(diǎn)X作為節(jié)點(diǎn)A的下一跳節(jié)點(diǎn),否則,節(jié)點(diǎn)A直接向基站傳送數(shù)據(jù)。

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

②EX＞EA,EX、EA分別為節(jié)點(diǎn)X和A的當(dāng)前能量。

上述2個(gè)條件既可以保證通過(guò)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)的能量消耗小于節(jié)點(diǎn)直接向基站發(fā)送數(shù)據(jù)的能量消耗,又可以避免低能量節(jié)點(diǎn)頻繁轉(zhuǎn)發(fā)數(shù)據(jù)造成的過(guò)早死亡。

此外,為了有效接收上一跳簇首節(jié)點(diǎn)發(fā)送的數(shù)據(jù),在簇形成階段備選簇首節(jié)點(diǎn)創(chuàng)建TDMA時(shí)間表時(shí)增加一個(gè)時(shí)隙,用于接收簇間數(shù)據(jù),同時(shí),當(dāng)前簇首節(jié)點(diǎn)在向下一跳簇首節(jié)點(diǎn)傳送數(shù)據(jù)時(shí)采用目的節(jié)點(diǎn)的簇內(nèi)CDMA編碼,這樣可以有效地改善簇間數(shù)據(jù)傳輸帶來(lái)的沖突和干擾。

3 仿真與分析

在Linux下用NS2仿真軟件對(duì)改進(jìn)后的路由協(xié)議進(jìn)行仿真,仿真場(chǎng)景為100個(gè)傳感器節(jié)點(diǎn)均勻部撒在100 m×100 m范圍內(nèi),基站位于(50 m,175 m)位置,每個(gè)節(jié)點(diǎn)的初始能量為2 J,每個(gè)數(shù)據(jù)包的分組長(zhǎng)度為500 byte,p=5%,其他能量模型相關(guān)的參數(shù)取自文獻(xiàn)[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)表示改進(jìn)的協(xié)議。

圖2為應(yīng)用LEACH協(xié)議和改進(jìn)協(xié)議的存活節(jié)點(diǎn)數(shù)隨時(shí)間的變化規(guī)律。可以看出,LEACH協(xié)議中第1個(gè)節(jié)點(diǎn)死亡時(shí)間為400 s,節(jié)點(diǎn)全部死亡的時(shí)間為500 s左右,而改進(jìn)的協(xié)議第1個(gè)節(jié)點(diǎn)死亡時(shí)間為680 s左右,節(jié)點(diǎn)全部死亡的時(shí)間為1 000 s左右,很明顯后者較好地延長(zhǎng)了網(wǎng)絡(luò)的生存壽命。

圖2 2種協(xié)議節(jié)點(diǎn)存活數(shù)比較

圖3為分別應(yīng)用LEACH協(xié)議和改進(jìn)協(xié)議的網(wǎng)絡(luò)能量消耗隨時(shí)間的變化過(guò)程,可以看出應(yīng)用改進(jìn)協(xié)議的網(wǎng)絡(luò)能量消耗速度明顯小于應(yīng)用LEACH協(xié)議的網(wǎng)絡(luò)能量消耗。

圖3 2種協(xié)議中網(wǎng)絡(luò)總耗能比較

圖4為分別應(yīng)用LEACH協(xié)議和改進(jìn)協(xié)議的網(wǎng)絡(luò)基站接收到的數(shù)據(jù)量和能量消耗關(guān)系圖,由圖可知相同能量消耗情況下應(yīng)用改進(jìn)后協(xié)議的網(wǎng)絡(luò)基站所接收到的數(shù)據(jù)明顯比應(yīng)用LEACH協(xié)議的網(wǎng)絡(luò)基站接收到的數(shù)據(jù)量大。

圖4 2種協(xié)議中消耗能量與接收數(shù)據(jù)比較

4 結(jié)束語(yǔ)

上述深入研究了無(wú)線傳感器網(wǎng)絡(luò)經(jīng)典的層次路由協(xié)議LEACH,并在此基礎(chǔ)上針對(duì)LEACH協(xié)議存在的缺陷進(jìn)行了改進(jìn)。改進(jìn)后的協(xié)議在簇首的選擇和簇的形成環(huán)節(jié)引入了傳感器節(jié)點(diǎn)的能量因子,有效避免了低能量節(jié)點(diǎn)過(guò)早死亡的現(xiàn)象。同時(shí)采用基于能量比較的簇間多跳路由,改善了LEACH協(xié)議中簇首節(jié)點(diǎn)向基站直接傳輸數(shù)據(jù)造成的能量消耗過(guò)大的缺陷,從而從整體上均衡了傳感器節(jié)點(diǎn)的能量消耗,大幅度地延長(zhǎng)了網(wǎng)絡(luò)的使用壽命。

[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.