能量優化的無線傳感器網絡LEACH算法

嚴斌亨， 陳任秋， 劉 軍

(武警工程大學 信息工程系，陜西 西安 710086)

能量優化的無線傳感器網絡LEACH算法

嚴斌亨， 陳任秋， 劉 軍

(武警工程大學 信息工程系，陜西 西安 710086)

針對無線傳感器網絡(WSNs)的經典路由算法LEACH中存在簇頭節點選舉不合理，導致節點加速死亡、網絡壽命縮短的問題，提出了基于能量和連通度的LEACH(LEACH-EC)算法。該算法主要在簇頭選舉時，同時引入節點的剩余能量和連通度兩個因子，采用修改閾值的方法，優化簇頭選舉，從而避免低能量和低連通度節點擔任簇頭的可能性。仿真實驗結果表明：該算法均衡了整個網絡能量消耗的比例，延長了節點和網絡的壽命。

無線傳感器網絡； LEACH算法； 簇頭閾值； 簇頭選擇

0 引 言

隨著計算機網絡技術、傳感器技術、分布式處理技術和無線通信技術的迅速發展，無線傳感器網絡[1](wireless sensor networks，WSNs)應運而生。無線傳感器網絡是在一定空間范圍內密集分布的，由大量廉價的、體積小、電池供電的傳感器節點構成的自組織系統[2,3]，這些網絡節點部署在某個監控區域內，協作進行數據的采集、存儲、處理和傳輸，完成對整個區域的監控。

無線傳感器網絡中的經典算法LEACH[4](low energy adaptive clustering hierarchy)是最早被提出的分簇路由算法，具有擴展性好，節點管理方便的優點，算法中各個節點以隨機等概率的方式競選簇頭，一定程度上延長網絡壽命[5]。

本文在分析了經典LEACH算法后，針對算法在簇頭選舉時未考慮節點自身能量和連通度導致簇頭選舉不合理的問題，提出了基于能量和連通度的LEACH(LEACH-energy and connectivity,LEACH-EC)路由算法，同時引入節點剩余能量及連通度兩個因子對閾值信息進行合理控制，優化簇頭選舉，有效地提高了網絡的能量均衡和生存時間。

1 無線傳感器網絡傳輸能耗模型

通常傳感器節點采用的是無線電能耗模型[6]，如圖1所示。

圖1 無線電能耗模型Fig 1 Energy consumption model for radio

2 LEACH算法分析

2.1 經典的LEACH算法

LEACH算法采用分簇拓撲控制的管理機制，一組節點

形成一個簇，簇成員與簇頭進行通信，簇頭融合處理接收到的數據并轉發至匯聚節點，簇頭選舉采用隨機循環選擇機制，各個節點產生一個介于0～1間的隨機數，并與閾值T(n)相比較，判定是否擔任簇頭，選舉完成后，簇頭節點廣播身份消息，非簇節點根據接收到的信號強度選擇要加入的簇，之后進入穩定數據傳輸階段。

LEACH算法的簇頭選擇閾值T(n)計算公式見式(1)

(1)

式中p為節點中簇頭的百分數，r為當前選舉的輪數，rmod(1/p)為當前這一輪中已當選過簇頭的節點個數，G為之前 輪中未當選過簇頭的節點集合。

2.2 LEACH算法存在的問題

盡管相比于平面路由算法，分簇的LEACH算法使得不同的節點在不同的時間內隨機當選為簇頭，分擔中繼通信任務，可以有效均衡網絡能量的消耗，延長網絡壽命，并且LEACH算法的分簇組織形式具有良好的網絡擴展性[7]。但該算法在簇頭選舉階段仍存在兩個主要問題：

1)LEACH算法中節點競選簇頭時沒有考慮候選簇頭節點連通度對當選為簇頭概率的影響。

2)LEACH算法的簇頭選舉機制雖然保證了各節點等概率競選簇頭，但是選舉過程中并沒有考慮節點的能量狀態，在每一輪循環選舉中，如果某一節點的剩余能量較少卻仍然當選為簇頭，則會進一步加速該節點耗盡能量死亡，不能有效提高網絡整體性能和壽命，降低網絡負載平衡程度。

3 改進的LEACH-EC算法

3.1 LEACH-EC算法設計思路

當節點剩余能量相同時，連通度更大的節點成為簇頭后會為更多的簇內節點傳輸數據，更有利于數據的采集傳輸和能量的優化，從而達到提高能量利用率的目的，因此針對上述(1)中存在的問題，本文引入連通度因子，以此增加連通度大的節點成為簇頭的概率。針對上述(2)中LEACH 算法在選擇簇頭時沒有考慮能量因素，可能導致該節點所處的部分網絡'斷層'，使得整個無線傳感器網絡運行不暢的問題，改進的算法在簇頭選舉的閾值公式中引入能量因子，提高剩余能量多的節點當選簇頭的概率。同時，為了防止剩余能量低的節點在某一個特定的選舉輪中選舉成功，引入了節點當前剩余能量Ei和當前網絡平均能量Eaverage兩個參數進行比較限制。

基于以上分析，本文提出了LEACH-EC算法。該算法以LEACH算法為基礎，在簇頭選舉前，首先設定參與選舉的限定條件公式(2)，判定節點是否參與選舉；在設定選舉閾值T′(n)時，同時引進節點剩余能量及節點的連通度兩個因子，以提高選舉簇頭節點的合理性，改進后的閾值公式為式(3),即

Ei≥Eaverage

(2)

(3)

式中Ei為節點i當前的剩余能量，Eaverage為當前所有節點的平均能量，Einitial為節點i初始時刻的能量，Ci為節點i的連通度，kopt為網絡中的最優簇頭數，N為傳感器節點總數。

公式(5)中，最優簇頭數kopt采用文獻[8]中的方案確定，如下式(4)

(4)

式中M為節點分布區域的邊長，dtoSINK為節點到匯聚節點Sink的距離。

3.2 LEACH-EC算法流程

圖2為LEACH-EC算法的流程。

圖2 LEACH-EC算法的流程Fig 2 Flow chart of LEACH-EC algorithm

4 仿真結果與分析

為了驗證LEACH-EC算法的性能，采用Matlab工具進行仿真。LEACH-EC算法采用的能量模型與LEACH算法相同，仿真中將初始能量為2 J的 100個節點隨機分布于100 m×100 m的覆蓋區域，信道的帶寬是2 Mb/s，當節點能量低于0.001 J時，就認為節點已經死亡不再發送或接收數據，每一輪的時間定為20 s，時間片大小為0.025 s，每個數據包長度為4 000 bit，控制消息長度為200 bit。實驗仿真的其它參數見表1。

為了驗證理論結果，通過仿真實驗，分析了網絡能耗情況、節點存活數量以及匯聚節點接收的數據量在LEACH和LEACH-EC兩個不同算法之下的對比關系。仿真結果如下：

表1 仿真參數Tab 1 Simulation parameters

由圖3可看出LEACH-EC算法在350 s左右才開始出現死亡節點，而LEACH算法在145 s左右就開始出現死亡節點；LEACH-EC算法最后一個節點死亡是在590 s左右，而LEACH算法在工作450 s后節點全部死亡；由此可見LEACH-EC算法的生存曲線明顯優于LEACH算法，將網絡的生存周期延長了30 % 左右。

圖3 網絡中剩余存活節點數目比較情況Fig 3 Remained alive node number comparison in network

圖4說明無線網絡中節點的能耗隨網絡的運行在不斷遞增，在整個周期里，改進算法LEACH-EC的能耗一直低于LEACH算法，尤其在后期更為明顯，表網絡能量消耗情況得到有效控制，延長了網絡的生存周期。

圖4 網絡節點總能耗比較情況Fig 4 Comparison of network nodes total energy consumption

由圖5中可看出： LEACH-EC算法中匯聚節點接收到的數據量是LEACH算法中節點接收到的數據量的兩倍。在450 s左右，LEACH算法中匯聚節點就不能接收到數據，網絡中節點己經全部死亡；而LEACH-EC算法中匯聚節點一直到590 s左右仍在接收數據。由此可見，消耗相同的能量下，LEACH-EC算法中節點接收到的數據量比LEACH算法要更多，能量利用率更高。

[1] 趙菊敏,張子辰,李燈熬.一種無線傳感器網絡鏈式傳輸分簇路由協議[J].傳感器與微系統,2014,33(3):135-138.

[2] Akyldiz F,Su W,Sankarasubramanian Y,et al.A survey of sensor networks[J].IEEE Communications Magazine,2002,40(8):102-114.

[3] 李建中,李金寶,石勝飛.傳感器網絡及其數據管理的概念、問題與進展[J].軟件學報,2003,14(10):1717-1727.

[4] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro sensor network-s[C]∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,Maui:IEEE,2000:3005-3014．

[5] 鄧仲芬,石為人,黃 河,等.一種基于樹均勻分簇的WSNs節能路由協議[J].傳感器與微系統,2011,30(5):47-50.

[6] Wendi B Heinzelman,Anantha P Chandrakasan,Hari Balakrishnan.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications,2002,4(1):660-670.

[7] 劉 軍,朱維杰,陳嵐嵐.WSNs在戰場態勢感知應用中的關鍵技術研究[M].北京:人民武警出版社,2014.

[8] Zhang Wenya,Liang Zize,Hou Zengguang,et al.A power efficient routing protocol for wireless sensor networks[C]∥IEEE International Conference on Networking,Sensing and Control,London,UK,2007:20-25.

LEACH algorithm for wireless sensor networks based on energy optimization

YAN Bin-heng, CHEN Ren-qiu, LIU Jun

(Department of Information Engineering,Engineering College of CAPF,Xi’an 710086,China)

Aiming at problems that cluster head node election is unreasonable,which leads to nodes consume their power quickly and network lifetime decreasing in classical routing algorithm LEACH for WSNs,propose an improved LEACH-EC algorithm.The algorithm gives full consideration of other factors of surplus energy and connectivity of node,use the method to modify threshold and optimize cluster head election,so as to avoid the possibility of low energy and low connectivity nodes act as cluster heads.Simulation results show that the algorithm balances ratio of energy consumption of the overall network effectively and prolong the lifetime of node and network．

wireless sensor networks(WSNs); LEACH algorithm; cluster head threshold; cluster head selection

by Sink node

10.13873/J.1000—9787(2016)07—0120—03

2015—10—28

TP 393

A

1000—9787(2016)07—0120—03

綜上可得，經改進后的LEACH-EC算法相比于LEACH算法，網絡的生命周期延長了約30 %，提高了數據的采集量，優化了網絡的能量利用率。

5 結束語

分簇路由協議在無線傳感器網絡中起著關鍵性的作用，它的性能不僅直接影響整個網絡的運行效率，也關系到無線傳感器網絡的壽命。本文重點對LEACH路由算法進行了研究，提出了基于節點剩余能量和連通度的LEACH-EC算法，通過改變閾值信息的方式，使簇頭選舉更加合理。仿真結果顯示，LEACH-EC算法有效均衡了整個網絡能量消耗的比例，延長了網絡生命周期。

嚴斌亨(1993-)，男，福建莆田人，碩士研究生，主要研究方向為無線傳感器網絡。