嚴斌亨， 陳任秋， 劉 軍

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

能量優(yōu)化的無線傳感器網(wǎng)絡(luò)LEACH算法

嚴斌亨， 陳任秋， 劉 軍

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

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

無線傳感器網(wǎng)絡(luò)； LEACH算法； 簇頭閾值； 簇頭選擇

0 引 言

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

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

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

1 無線傳感器網(wǎng)絡(luò)傳輸能耗模型

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

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

2 LEACH算法分析

2.1 經(jīng)典的LEACH算法

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

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

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

(1)

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

2.2 LEACH算法存在的問題

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

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

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

3 改進的LEACH-EC算法

3.1 LEACH-EC算法設(shè)計思路

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

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

Ei≥Eaverage

(2)

(3)

式中Ei為節(jié)點i當前的剩余能量，Eaverage為當前所有節(jié)點的平均能量，Einitial為節(jié)點i初始時刻的能量，Ci為節(jié)點i的連通度，kopt為網(wǎng)絡(luò)中的最優(yōu)簇頭數(shù)，N為傳感器節(jié)點總數(shù)。

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

(4)

式中M為節(jié)點分布區(qū)域的邊長，dtoSINK為節(jié)點到匯聚節(jié)點Sink的距離。

3.2 LEACH-EC算法流程

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

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

4 仿真結(jié)果與分析

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

為了驗證理論結(jié)果，通過仿真實驗，分析了網(wǎng)絡(luò)能耗情況、節(jié)點存活數(shù)量以及匯聚節(jié)點接收的數(shù)據(jù)量在LEACH和LEACH-EC兩個不同算法之下的對比關(guān)系。仿真結(jié)果如下：

表1 仿真參數(shù)Tab 1 Simulation parameters

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

圖3 網(wǎng)絡(luò)中剩余存活節(jié)點數(shù)目比較情況Fig 3 Remained alive node number comparison in network

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

圖4 網(wǎng)絡(luò)節(jié)點總能耗比較情況Fig 4 Comparison of network nodes total energy consumption

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

[1] 趙菊敏,張子辰,李燈熬.一種無線傳感器網(wǎng)絡(luò)鏈式傳輸分簇路由協(xié)議[J].傳感器與微系統(tǒng),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] 李建中,李金寶,石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進展[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節(jié)能路由協(xié)議[J].傳感器與微系統(tǒng),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在戰(zhàn)場態(tài)勢感知應(yīng)用中的關(guān)鍵技術(shù)研究[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

綜上可得，經(jīng)改進后的LEACH-EC算法相比于LEACH算法，網(wǎng)絡(luò)的生命周期延長了約30 %，提高了數(shù)據(jù)的采集量，優(yōu)化了網(wǎng)絡(luò)的能量利用率。

5 結(jié)束語

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

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