無線傳感器網(wǎng)絡(luò)能量均衡分簇路由算法的改進(jìn)

韓紅芳 孫守昌 鄒凌

(常州大學(xué)信息科學(xué)與工程學(xué)院，江蘇 常州 213016)

0 引言

無線傳感器網(wǎng)絡(luò)通常由大量隨機(jī)分布的、用電池供電的傳感器節(jié)點(diǎn)組成。這些節(jié)點(diǎn)在無人監(jiān)管的模式下工作。由于節(jié)點(diǎn)在布灑之后不方便進(jìn)行電池更換，因此，網(wǎng)絡(luò)的工作能力受到電池電量的嚴(yán)重限制。如何節(jié)省能量并延長網(wǎng)絡(luò)生命周期是設(shè)計(jì)更優(yōu)算法的目標(biāo)和準(zhǔn)則［1］。

低能量自適應(yīng)分簇路由協(xié)議(low energy adaptive clustering hierarchy，LEACH)［2］是較早提出的、較成熟且常用的一種基于簇結(jié)構(gòu)的層次型的傳感器網(wǎng)絡(luò)路由協(xié)議。LEACH算法簇首位置的輪換算法將遠(yuǎn)距離通信的負(fù)載輪流分配給網(wǎng)絡(luò)節(jié)點(diǎn)，以延長整個(gè)系統(tǒng)的生存時(shí)間。節(jié)點(diǎn)輪流擔(dān)任簇首，均衡了網(wǎng)絡(luò)的能耗。由于簇首在當(dāng)選時(shí)沒有考慮節(jié)點(diǎn)的能量高低，若節(jié)點(diǎn)在能量很低的情況下仍要擔(dān)當(dāng)簇首，就會加速其死亡。本文通過對LEACH協(xié)議的研究，采用修改門限值和優(yōu)化簇首個(gè)數(shù)的方法，對其負(fù)載能量不均衡的問題作出改進(jìn)。

1 經(jīng)典LEACH協(xié)議分析

1.1 算法描述

LEACH協(xié)議定義了“輪”的概念，每一輪由簇的建立和穩(wěn)定狀態(tài)階段組成。在簇建立的階段，首批簇的選取是隨機(jī)的。對于一個(gè)節(jié)點(diǎn)，其在0～1之間選取一個(gè)隨機(jī)數(shù)，若該數(shù)字小于一個(gè)門限值T(n)，則節(jié)點(diǎn)n就成為本輪的簇首節(jié)點(diǎn)。門限T(n)定義如下:

式中:P為網(wǎng)絡(luò)中簇首節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)目的百分比;r為當(dāng)前的輪數(shù);G為在前1/P輪中沒有擔(dān)當(dāng)過簇首節(jié)點(diǎn)的節(jié)點(diǎn)集合;mod為求模運(yùn)算符號。

在選定簇首節(jié)點(diǎn)后，向周圍廣播自己成為簇首的信息(advertisement，ADV)，非簇首節(jié)點(diǎn)根據(jù)接收到的信號強(qiáng)度來決定從屬的簇類。當(dāng)簇首收到反饋消息后，就基于TDMA方式為簇內(nèi)節(jié)點(diǎn)分配時(shí)隙。在穩(wěn)定階段，簇內(nèi)節(jié)點(diǎn)在自己時(shí)隙到來時(shí)刻向簇首發(fā)送采集數(shù)據(jù);簇首節(jié)點(diǎn)則將接收到的數(shù)據(jù)進(jìn)行必要的融合后傳送到基站或匯聚節(jié)點(diǎn)。經(jīng)過一段時(shí)間的數(shù)據(jù)傳送后，網(wǎng)絡(luò)將重新進(jìn)入簇的建立階段，進(jìn)行下一輪的簇重建循環(huán)［3－5］。

1.2 LEACH算法的局限性

在LEACH算法中，簇首選擇機(jī)制中沒有考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)已經(jīng)做過簇首的次數(shù)。一旦所剩能量較少的節(jié)點(diǎn)成為簇首，其能量將會很快耗盡從而過早死亡，其簇內(nèi)成員也將因收不到簇首的信息而不斷地發(fā)送請求信號，耗費(fèi)大量的能量而導(dǎo)致加速死亡，最終縮短了整個(gè)網(wǎng)絡(luò)的生存時(shí)間［6］。

簇首的數(shù)量對整個(gè)網(wǎng)絡(luò)的壽命也有影響。若簇首過少，則成員節(jié)點(diǎn)要經(jīng)過很長的路徑與簇首進(jìn)行通信，簇首也將接收大量節(jié)點(diǎn)的信息并向基站進(jìn)行轉(zhuǎn)發(fā)，這對每一個(gè)節(jié)點(diǎn)來說負(fù)擔(dān)都過重;若產(chǎn)生過多簇首，則會有過多的節(jié)點(diǎn)與基站進(jìn)行通信，降低了網(wǎng)絡(luò)能量的利用率。LEACH協(xié)議簇首選擇機(jī)制沒有控制簇首的數(shù)量。

2 LEACH算法的優(yōu)化

上述LEACH算法存在的不足導(dǎo)致了無線傳感器網(wǎng)絡(luò)負(fù)載能量的不均衡。本文主要通過改進(jìn)簇首節(jié)點(diǎn)選舉算法對LEACH協(xié)議進(jìn)行優(yōu)化。其主要目標(biāo)是避免能量低的節(jié)點(diǎn)成為簇首，同時(shí)控制簇首數(shù)量達(dá)到最優(yōu)，從而達(dá)到降低系統(tǒng)能量消耗、最終實(shí)現(xiàn)延長網(wǎng)絡(luò)生命周期的目的。

2.1 簇首選舉機(jī)制的算法改進(jìn)

對于簇首選舉的改進(jìn)，文獻(xiàn)［6］對其閾值作了以下改進(jìn):

式中:En_current為節(jié)點(diǎn)n當(dāng)前的剩余能量;En_max為節(jié)點(diǎn)n的初始能量。

從式(2)可以看出，由于節(jié)點(diǎn)的剩余能量總是小于其初始能量，所以改進(jìn)后的T(n)值一定比原值要小。本算法雖然降低了剩余能量少的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)的可能性，但同時(shí)也減少了其在整個(gè)網(wǎng)絡(luò)中能夠擔(dān)當(dāng)簇首節(jié)點(diǎn)的機(jī)會。

針對這一現(xiàn)象，本文綜合考慮了節(jié)點(diǎn)當(dāng)前剩余能量En_current和當(dāng)前網(wǎng)絡(luò)平均能量Eaverage這兩個(gè)參數(shù)，改進(jìn)后的閾值為:

式中:Eaverage為當(dāng)前網(wǎng)絡(luò)平均能量;En_current為節(jié)點(diǎn)當(dāng)前的剩余能量。這樣既保證了節(jié)點(diǎn)被選為簇首節(jié)點(diǎn)的可能性與其剩余能量相關(guān)，又保證了新一輪中選舉出來的簇首節(jié)點(diǎn)數(shù)與期望數(shù)相同。

網(wǎng)絡(luò)中簇首的個(gè)數(shù)也是影響網(wǎng)絡(luò)壽命的重要因素，因此，本文將簇首個(gè)數(shù)的優(yōu)化方案融入了改進(jìn)的協(xié)議。簇首最優(yōu)個(gè)數(shù)確定公式如下所示:

式中:M2為無線傳感器網(wǎng)絡(luò)覆蓋區(qū)域面積;N為區(qū)域內(nèi)節(jié)點(diǎn)數(shù)量;εamp為信號放大器的放大倍數(shù);Eatart為每發(fā)送或接收1 B數(shù)據(jù)電路自身消耗的能量;dadv為簇首節(jié)點(diǎn)的最大覆蓋距離。

2.2 改進(jìn)算法的具體實(shí)現(xiàn)

改進(jìn)算法的具體實(shí)現(xiàn)步驟詳細(xì)描述如下。

①根據(jù)式(4)計(jì)算出最佳簇首個(gè)數(shù)。

②根據(jù)節(jié)點(diǎn)的剩余能量是否大于網(wǎng)絡(luò)的當(dāng)前平均能量，判斷其是否成為候選簇首。

③候選簇首將自己產(chǎn)生的隨機(jī)數(shù)與T(n)值比較，若隨機(jī)數(shù)小于T(n)，則成為簇首節(jié)點(diǎn);反之，則為成員節(jié)點(diǎn)，等待簇首發(fā)送告知信息。至此，簇首的選舉完成。

④簇首節(jié)點(diǎn)以一定的功率發(fā)送簇首告知信息ADV后等待簇成員的加入。該消息只包括簇首節(jié)點(diǎn)的ID和消息標(biāo)志符。

⑤非簇首節(jié)點(diǎn)根據(jù)接收到的ADV信號強(qiáng)度來決定從屬的簇類。當(dāng)簇首收到反饋消息后，便為簇內(nèi)節(jié)點(diǎn)分配時(shí)隙(基于TDMA方式)，以確保成員節(jié)點(diǎn)與簇首節(jié)點(diǎn)通信時(shí)不會產(chǎn)生沖突。簇首將TDMA時(shí)隙以最小功率發(fā)送給簇內(nèi)成員，這樣，網(wǎng)絡(luò)中某一輪的簇就已建立。

改進(jìn)后的簇建立階段算法流程如圖1所示。

圖1 簇建立階段算法流程圖Fig.1 Flowchart of cluster building phase

⑥在穩(wěn)定階段，簇內(nèi)節(jié)點(diǎn)在自己時(shí)隙到來的時(shí)刻向簇首發(fā)送采集數(shù)據(jù)，簇首節(jié)點(diǎn)則將接收到的數(shù)據(jù)進(jìn)行必要的融合后傳送到基站或匯聚節(jié)點(diǎn)。同時(shí)根據(jù)信息中包含的簇首和節(jié)點(diǎn)的ID及其發(fā)送信息時(shí)的功率強(qiáng)度，估計(jì)下一輪發(fā)送消息時(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的平均能量，并將此信息廣播到網(wǎng)絡(luò)，為下一輪循環(huán)做準(zhǔn)備。至此，本輪結(jié)束。

3 算法仿真與性能分析

3.1 NS2 仿真過程

網(wǎng)絡(luò)模擬器第2版(network simulator，version 2，NS2)可構(gòu)建并仿真分析整個(gè)協(xié)議棧的運(yùn)行情況，進(jìn)行有線或無線網(wǎng)絡(luò)上多種協(xié)議的模擬［7－8］。

仿真平臺采用WinXP+Cygwin+NS2，仿真環(huán)境及模型如下。模擬開始時(shí)，將100個(gè)節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的空間內(nèi)，基站設(shè)在X=150 m，Y=150 m的位置，站內(nèi)所有節(jié)點(diǎn)都是靜止的。無線信道帶寬設(shè)置為1×106bit/s，消息長度設(shè)置為500 B，發(fā)送與接收的時(shí)延均為25 μs，每個(gè)節(jié)點(diǎn)的初始能量均為2 J。一輪的持續(xù)時(shí)間為10s、簇頭數(shù)期望值k=5。發(fā)射機(jī)與接收機(jī)處理數(shù)據(jù)的能耗為5×10－8J/bit。自由空間模型傳輸放大因子為1×10－11J/(bit·m2)。多路衰減模型傳輸放大因子為1.3×10－15J/(bit·m4)。數(shù)據(jù)融合能耗為5×10－9J/(bit·signal)、無線信道帶寬為1×106bit/s。

參數(shù)設(shè)置完成后，執(zhí)行以下步驟進(jìn)行協(xié)議分析。

① $ns genscen，生成一個(gè)100nodes.txt文件，這個(gè)txt文件就是隨機(jī)生成的100個(gè)節(jié)點(diǎn)的位置信息。

② $./leach_test，進(jìn)行協(xié)議模擬，生成 leach.out、leach.data、leach.alive、leach.energy 等文件。其中l(wèi)each.out文件記錄了節(jié)點(diǎn)能量等信息。

③ $awk-f leach.awk leach.alive ＞ live.txt，用 awk處理trace數(shù)據(jù)。采用awk編寫腳本，提取自己需要的信息，awk腳本文件為leach.awk，將需要的信息放到live.txt文件中。

④ $startxwin.bat，進(jìn)入繪圖模式。

⑤ $gnuplot，采用gnuplot畫圖。

⑥ gnuplot＞ plot'live.txt'with linespoints。在gnuplot下畫圖的命令是 plot，要畫的文件是 live.txt，指定繪圖的樣式為采用線性插值法連接各點(diǎn)。

3.2 仿真結(jié)果與性能分析

LEACH協(xié)議改進(jìn)前后簇首節(jié)點(diǎn)個(gè)數(shù)情況的對比如圖2所示。改進(jìn)前，協(xié)議每輪產(chǎn)生的簇首數(shù)很不均衡;與之相比，改進(jìn)后協(xié)議每輪產(chǎn)生的簇首數(shù)浮動較小且都在最佳值(仿真中為5個(gè))左右。

圖2 簇首節(jié)點(diǎn)個(gè)數(shù)比較圖Fig.2 The comparison of the number of the head clustering nodes

在不考慮處理器、傳感器耗能的情況下，網(wǎng)絡(luò)的能量消耗與數(shù)據(jù)通信密切相關(guān)。LEACH協(xié)議在改進(jìn)前后網(wǎng)絡(luò)生命期的能量消耗情況如圖3所示。

圖3 節(jié)點(diǎn)平均消耗能量比較圖Fig.3 The comparison of the node average energy consumption

從圖3可以看出，改進(jìn)后能量消耗是增加的，即說明改進(jìn)前大量節(jié)點(diǎn)的過早死亡，導(dǎo)致整個(gè)網(wǎng)絡(luò)的癱瘓，剩余能量沒有被利用;協(xié)議改進(jìn)后，網(wǎng)絡(luò)消耗比改進(jìn)前以略多的能量維持更長的生存期并采集更多的數(shù)據(jù)，能量被充分利用。

網(wǎng)絡(luò)節(jié)點(diǎn)壽命比較如圖4所示。

圖4 網(wǎng)絡(luò)節(jié)點(diǎn)壽命比較圖Fig.4 The comparison of network node lifecycle

從圖4可以看出，改進(jìn)后算法的第一個(gè)節(jié)點(diǎn)的死亡時(shí)間比改進(jìn)前算法第一個(gè)節(jié)點(diǎn)死亡時(shí)間延遲了25%左右，全部節(jié)點(diǎn)的死亡時(shí)間比改進(jìn)前延遲了大約20%，即改進(jìn)后的算法網(wǎng)絡(luò)生存時(shí)間比改進(jìn)前算法網(wǎng)絡(luò)生存時(shí)間延長了20%。試驗(yàn)表明，改進(jìn)后的算法可以降低傳感器節(jié)點(diǎn)的通信能耗，從而有效地延長網(wǎng)絡(luò)的生存時(shí)間［9－14］。

4 結(jié)束語

針對LEACH協(xié)議存在的問題，提出了新的優(yōu)化方案。新算法將當(dāng)前剩余能量和當(dāng)前網(wǎng)絡(luò)平均能量作為參數(shù)引入到簇首選舉機(jī)制中，并融入簇首最優(yōu)個(gè)數(shù)解決方案。利用NS2對改進(jìn)前后的算法進(jìn)行了仿真。給出了改進(jìn)前后的網(wǎng)絡(luò)生存時(shí)間、簇首個(gè)數(shù)和能量消耗仿真結(jié)果。仿真結(jié)果證明，本優(yōu)化方案能使節(jié)點(diǎn)分布更加合理，能較好地均衡網(wǎng)絡(luò)中的能量消耗，這在一定程度上延長了整個(gè)網(wǎng)絡(luò)的生命周期。

［1］Pottie G J，Kaiser W J.Wireless integrated network sensors［J］.Communications of the ACM，1999，43(5):279 －286.

［2］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002(1):660 －670.

［3］Liang Ying，Yu Haibin.Energy adaptive ouster-head selection for wireless sensor networks［C］//Proceedings of the Sixth International Conference on Parallel and Distributed Computing，Applications and Technology，2005:634 －638.

［4］Zhang Jiali，Huang Benxiong，Lai Tu，et al.A cluster-based energyefficient scheme for sensor networks［C］//Proceedings of the Sixth International Conference on Parallel and Distributed Computing，Applications and Technologies，2005:191 －195.

［5］Bianchi G.Performance analysis of the IEEE 802.11 distributed>coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18(3):535 －547.

［6］Mhatre V，Rosenberg C.Homogeneous vs.heterogeneous clustered sensor networks:a comparative study［C］//Proceedings of 2004 IEEE International Conference on Communications，2004:3646 －3651.

［7］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks:communication，clustering and aggregation［J］.Adhoc Networks Journal，Elsevier Science，2004，2(1):45 －63.

［8］Akkaya K，Younis M.A survey of routing protocols for wireless sensor networks［J］.Elsevier，Ad Hoc Networks，2005(3):325 －349.

［9］Jiang Q F，Manivannan D.Routing protocols for sensor networks［C］//Consumer Communications and Networking Conference，2004:93 －98.

［10］Dai S，Jing S，Li L.Research and analysis on routing protocols for wirelesssensornet works［C］//Communications Circuits and Systems，2005 International Conference，2005:407 －411.

［11］靳偉，廖延彪，張志鵬.導(dǎo)波光學(xué)傳感器原理與技術(shù)［M］.北京:科學(xué)出版社，1998:254－255.

［12］王艷菊，王玉田，劉靜.CH檢測系統(tǒng)微弱信號處理電路研究［J］.儀表技術(shù)與傳感器，2006(8):41－43.

［13］李政穎.煤礦瓦斯多通道光纖傳感檢測儀的研究與開發(fā)［D］.武漢:武漢理工大學(xué)，2007.

［14］林凌，洪權(quán)，李剛，等.模擬乘法器MLT04在高精度微弱光信號鎖相檢測電路中的應(yīng)用［J］.光電子技術(shù)，2005，25(4):263－266.