無線傳感器網絡能量均衡分簇路由算法的改進

韓紅芳 孫守昌 鄒凌

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

0 引言

無線傳感器網絡通常由大量隨機分布的、用電池供電的傳感器節點組成。這些節點在無人監管的模式下工作。由于節點在布灑之后不方便進行電池更換，因此，網絡的工作能力受到電池電量的嚴重限制。如何節省能量并延長網絡生命周期是設計更優算法的目標和準則［1］。

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

1 經典LEACH協議分析

1.1 算法描述

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

式中:P為網絡中簇首節點占總節點數目的百分比;r為當前的輪數;G為在前1/P輪中沒有擔當過簇首節點的節點集合;mod為求模運算符號。

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

1.2 LEACH算法的局限性

在LEACH算法中，簇首選擇機制中沒有考慮節點的剩余能量和節點已經做過簇首的次數。一旦所剩能量較少的節點成為簇首，其能量將會很快耗盡從而過早死亡，其簇內成員也將因收不到簇首的信息而不斷地發送請求信號，耗費大量的能量而導致加速死亡，最終縮短了整個網絡的生存時間［6］。

簇首的數量對整個網絡的壽命也有影響。若簇首過少，則成員節點要經過很長的路徑與簇首進行通信，簇首也將接收大量節點的信息并向基站進行轉發，這對每一個節點來說負擔都過重;若產生過多簇首，則會有過多的節點與基站進行通信，降低了網絡能量的利用率。LEACH協議簇首選擇機制沒有控制簇首的數量。

2 LEACH算法的優化

上述LEACH算法存在的不足導致了無線傳感器網絡負載能量的不均衡。本文主要通過改進簇首節點選舉算法對LEACH協議進行優化。其主要目標是避免能量低的節點成為簇首，同時控制簇首數量達到最優，從而達到降低系統能量消耗、最終實現延長網絡生命周期的目的。

2.1 簇首選舉機制的算法改進

對于簇首選舉的改進，文獻［6］對其閾值作了以下改進:

式中:En_current為節點n當前的剩余能量;En_max為節點n的初始能量。

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

針對這一現象，本文綜合考慮了節點當前剩余能量En_current和當前網絡平均能量Eaverage這兩個參數，改進后的閾值為:

式中:Eaverage為當前網絡平均能量;En_current為節點當前的剩余能量。這樣既保證了節點被選為簇首節點的可能性與其剩余能量相關，又保證了新一輪中選舉出來的簇首節點數與期望數相同。

網絡中簇首的個數也是影響網絡壽命的重要因素，因此，本文將簇首個數的優化方案融入了改進的協議。簇首最優個數確定公式如下所示:

式中:M2為無線傳感器網絡覆蓋區域面積;N為區域內節點數量;εamp為信號放大器的放大倍數;Eatart為每發送或接收1 B數據電路自身消耗的能量;dadv為簇首節點的最大覆蓋距離。

2.2 改進算法的具體實現

改進算法的具體實現步驟詳細描述如下。

①根據式(4)計算出最佳簇首個數。

②根據節點的剩余能量是否大于網絡的當前平均能量，判斷其是否成為候選簇首。

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

④簇首節點以一定的功率發送簇首告知信息ADV后等待簇成員的加入。該消息只包括簇首節點的ID和消息標志符。

⑤非簇首節點根據接收到的ADV信號強度來決定從屬的簇類。當簇首收到反饋消息后，便為簇內節點分配時隙(基于TDMA方式)，以確保成員節點與簇首節點通信時不會產生沖突。簇首將TDMA時隙以最小功率發送給簇內成員，這樣，網絡中某一輪的簇就已建立。

改進后的簇建立階段算法流程如圖1所示。

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

⑥在穩定階段，簇內節點在自己時隙到來的時刻向簇首發送采集數據，簇首節點則將接收到的數據進行必要的融合后傳送到基站或匯聚節點。同時根據信息中包含的簇首和節點的ID及其發送信息時的功率強度，估計下一輪發送消息時網絡中節點的平均能量，并將此信息廣播到網絡，為下一輪循環做準備。至此，本輪結束。

3 算法仿真與性能分析

3.1 NS2 仿真過程

網絡模擬器第2版(network simulator，version 2，NS2)可構建并仿真分析整個協議棧的運行情況，進行有線或無線網絡上多種協議的模擬［7－8］。

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

參數設置完成后，執行以下步驟進行協議分析。

① $ns genscen，生成一個100nodes.txt文件，這個txt文件就是隨機生成的100個節點的位置信息。

② $./leach_test，進行協議模擬，生成 leach.out、leach.data、leach.alive、leach.energy 等文件。其中leach.out文件記錄了節點能量等信息。

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

④ $startxwin.bat，進入繪圖模式。

⑤ $gnuplot，采用gnuplot畫圖。

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

3.2 仿真結果與性能分析

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

圖2 簇首節點個數比較圖Fig.2 The comparison of the number of the head clustering nodes

在不考慮處理器、傳感器耗能的情況下，網絡的能量消耗與數據通信密切相關。LEACH協議在改進前后網絡生命期的能量消耗情況如圖3所示。

圖3 節點平均消耗能量比較圖Fig.3 The comparison of the node average energy consumption

從圖3可以看出，改進后能量消耗是增加的，即說明改進前大量節點的過早死亡，導致整個網絡的癱瘓，剩余能量沒有被利用;協議改進后，網絡消耗比改進前以略多的能量維持更長的生存期并采集更多的數據，能量被充分利用。

網絡節點壽命比較如圖4所示。

圖4 網絡節點壽命比較圖Fig.4 The comparison of network node lifecycle

從圖4可以看出，改進后算法的第一個節點的死亡時間比改進前算法第一個節點死亡時間延遲了25%左右，全部節點的死亡時間比改進前延遲了大約20%，即改進后的算法網絡生存時間比改進前算法網絡生存時間延長了20%。試驗表明，改進后的算法可以降低傳感器節點的通信能耗，從而有效地延長網絡的生存時間［9－14］。

4 結束語

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

［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］靳偉，廖延彪，張志鵬.導波光學傳感器原理與技術［M］.北京:科學出版社，1998:254－255.

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

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

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