基于節點位置與剩余能量的LEACH協議優化*

余成波，鄧順華，方　軍，余玉潔

(重慶理工大學 遠程測試與控制研究所，重慶 400054)

基于節點位置與剩余能量的LEACH協議優化*

余成波，鄧順華，方軍，余玉潔

(重慶理工大學 遠程測試與控制研究所，重慶 400054)

摘要:LEACH協議在簇頭選舉產生、能耗控制還存在許多問題，為此，對其產生方式提出改進。在原LEACH協議中加入網絡中節點的具體位置信息和網絡節點當前的剩余能量信息，在簇頭選定階段引入了備選簇頭節點間距和模擬退火算法。在NS2上的仿真結果表明:改進的LEACH協議使簇頭節點的選擇更為合理，整個網絡的壽命延長了50 %，網絡基站的接收數據量提高了175 %。

關鍵詞：無線傳感器網絡；LEACH協議；位置信息；剩余能量；模擬退火算法；NS2

0引言

LEACH[1,2]協議與其它平面路由協議相比，在整個網絡的生存時間上有了很大的提升。但LEACH協議本身還存在很多不足，比如:LEACH協議在簇頭產生的時候采用的是隨機數原則，沒有結合節點本身的位置和剩余能量，這會導致部分節點過早死亡，對延長網絡的生存時間有不利影響。

針對LEACH協議的不足,文獻[3,4]中在協議中考慮了能量因素，在簇頭選擇的時候選擇能量較多的節點成為簇頭。文獻[5]中提出先將網絡區域進行分區，保證網絡中各節點的數量一致，然后再選擇能量最高的作為簇頭節點。文獻[6]中采用分級的方式實現數據逐級短距離傳輸實現節能。文獻[7]中提出的A-LEACH算法是根據節點的能量和當前幾點的疏密程度選出簇頭節點。文獻[8]中提出讓冗余節點進行休眠的方式實現節能。其他還有許多相應的改進算法如LEACH-LC[9]，BPSO-LEACH[10]等。

本文在協議中加入了節點的剩余能量和位置信息，在選擇備選簇頭時考慮了備選簇頭的距離因素，最后簇頭節點的選擇時引入模擬退火算法，使協議在簇頭節點的選擇和延長網絡壽命上都有很大提高。

1LEACH 協議簇頭選舉存在的問題分析

1.1LEACH 協議的工作流程

LEACH協議的執行過程大體可以分成以下三個階段：

1)簇頭的選取與簇的形成

各節點隨機產生一個[0,1]的隨機數，再將隨機數與設定閾值T(n)進行比較，若產生的隨機數小于閾值T(n)，則該節點為本輪的一個簇頭;否則,為普通節點。T(n)的值由式(1)確定

(1)

式中p為需要產生簇頭數量的百分比；n為傳感器節點的總個數；r為當前已經完成的輪數；G為最近輪不是簇頭的節點集合。

節點被選為簇頭后，利用廣播消息通知周圍的節點。非簇頭節點在收到廣播消息后都將簇頭消息存在備選簇頭消息列表中，最后比較各廣播消息的信號強度，選擇信號最強的簇頭節點發送加入簇請求消息。簇頭節點根據請求消息將節點加入并記錄相應的ID信息。

2)時隙表建立

當網絡完成簇的建立后，各簇頭節點根據加入簇的成員節點個數建立TDMA時隙表，并通過廣播發送給簇內各成員節點。這樣簇內成員只有在自己時隙時才給簇頭節點發送消息，其他節點則關閉天線等待自己的時隙到來。

3)穩定運行

完成了時隙的分配后網絡就處于一個穩定的狀態。各網絡節點根據自己的時隙對簇頭節點進行數據傳輸，簇頭節點將接收的數據進行簡單的融合后傳輸給基站。如此反復運行，達到一段時間后，又從新回到簇頭的選取和簇形成階段。

1.2LEACH 協議簇頭產生存在的問題

LEACH協議中簇頭的產生依靠隨機數的方式，這樣使得所有節點都有相同的機會成為簇頭，這就導致了以下的幾個問題：

1)被選為簇頭的節點可能是能量比較少的節點。若能量比較少的節點當選簇頭節點這會加劇節點的能量消耗，使得節點過早死亡；同時在能量比較少的節點在與基站進行通信時候也會影響通信的質量，導致數據的傳輸有誤。

2)因為簇頭選擇是隨機的，當選的簇頭節點有可能出現不均勻或者相對集中的情況。簇頭節點不均勻會使得簇頭節點所分配的節點數不均勻，導致部分簇頭能量消耗很快。這樣也就失去了分層路由協議本來的意義。如果簇頭節點相對集中了，也會導致其他節點要完成數據傳輸都必須進行遠距離傳輸，這樣不但加大了簇頭節點的能量消耗，同時使得整個網絡的能量消耗也大大增加了，縮短了整個網絡的生存時間。

3)LEACH協議在設計時，其理想運用狀態為所有節點的初始能量和平均消耗均量都相同。但在實際運用中，各節點因為距離的原因和選擇的儲備電源均不可能完全一樣，而且因為各節點的數據量的差異也會導致節點能量消耗的不一樣。所以，LEACH協議要直接運用在實際傳感器網絡中還是比較困難的。

2LEACH協議的改進

2.1改變簇頭產生方式

1)當前剩余能量高于平均能量節點才能夠參加簇頭的競選。考慮到網絡節點的能量不一致和簇頭的能量消耗更多，將節點的當前剩余能量作為簇頭節點產生的一個重要標準，這樣能保證整個網絡能耗的平均，可有效提高全網節點的生存時間。

2)節點與備選簇頭之間必須大于閾值M才能當選備選簇頭。考慮到簇頭的分布必須平均才有利于全網絡的節能，文中引入了備選簇頭節點距離閾值M，這樣保證了在備選簇頭節點周邊M的范圍內不會再出現其他的備選簇頭，這樣既可以保證簇頭不會相對集中也可以使后面的退火算法的迭代次數大大減少，加快最優解搜索的速度。

3)在備選簇頭產生最后簇頭時引入模擬退火算法，選出最優的備選簇頭作為最后網絡的簇頭。

2.2改進協議的具體實現

改進LEACH協議執行每一輪流程圖如圖1所示，在協議開始時，首先要進行的是簇頭的產生，簇頭產生程序流程如圖2所示。協議開始時各節點首先將自己的位置信息和當前剩余能量信息發送給基站，節奏在接收到各節點的能量信息后計算出全網的平均能量并告知各節點。各節點根據自己的情況若大于全網平均能量并且周邊距離M范圍內沒有備選簇頭節點,則在[0,1]之間產生一個隨機數;若小于設定閾值T(n),則節點為備選簇頭節點。節點在被選為被選簇頭后將信息發送給基站和周邊節點。周邊節點在得知自己周邊距離M范圍內存在備選簇頭節點時,不在參數隨機數去競爭備選簇頭節點。M的設定不能太小或太大，太小會導致最后產生的備選簇頭較多不利于退火算法最后求最優解，太大則會使得部分被選簇頭分布不合理導致最后簇頭的分布不合理。多次實驗表明,M的選取為傳感器區域的1/15～1/20的時候得到的效果最佳。

圖1　改進LEACH協議每輪執行流程圖Fig 1　Each round execution flow chart of improved LEACH protocol

圖2　改進LEACH協議簇頭產生程序流程圖Fig 2　Flow chart of cluster head generation program of improved LEACH protocol

在確定備選簇頭后，基站利用模擬退火算法計算選出最優簇頭節點。基站在備選簇頭中選出一組備選簇頭作為最初解，然后對解中每個節點坐標產生一個新的坐標。設原來最初解的坐標為(Xi，Yi)，則新解的坐標如式(2)所示

(2)

式中rand(-10,10)為在-10～10之間產生一個隨機數，然后在解周邊的隨機數范圍內尋找新的解，即尋找備選簇頭節點。如果新產生的備選簇頭坐標與之前的均不同，則新產生的備選簇頭坐標成為新解。同時算法會產生一個隨機數，如果小于指定接收新解概率，則接收新解。新解中的備選簇頭成為最終簇頭。

選定簇頭后，簇頭向外廣播，周邊節點在收到廣播后根據自己接收到的不同簇頭發來廣播的信號強加入信號最強的簇頭。簇頭接收到節點的申請后對簇內的成員進行TDMA時隙分配發送給簇內各成員節點。完成時隙分配后網絡將進入穩定階段，各成員節點根據自己的時隙分配進行數據傳輸。簇頭節點在對收集的信息進行數據融合之后發送給基站。穩定時間完成后又從復之前的操作進入新一輪簇頭節點的選擇。

3仿真結果與分析

3.1仿真試驗場景與參數設定

為了驗證文中改進協議的合理性和有效性，文中采用NS2仿真軟件作為仿真平臺，對改后的LEACH協議和原LEACH協議作了相應的對比。實驗中對協議的能量消耗、網絡的生存時間以及網絡數據的吞吐量進行了比較。表1為實驗的仿真參數。

表1　仿真參數

3.2對比實驗結果與分析

圖3為協議改進后某一輪的分簇圖，圖中同一顏色代表為一個分簇。由圖中可以看出實驗中分簇數量為5，標示有CH字樣的為當前簇頭或是已經當選過簇頭，左下角有用字母BS標注的節點為基站。

圖3　改進后某一輪分簇圖Fig 3　A round of clustering picture after improvement

圖4為網絡存活節點數隨時間的變化圖，由圖中看到LEACH協議中節點在230～280 s之間節點的死亡速度非常快，并在280 s附近節點全部死亡。而改進后的協議50～100 s時死亡速度比LEACH協議快，這是由于網絡前期的計算量大于LEACH協議，相對應的能量消耗也大于LEACH協議，所以前期的死亡速度要快于LEACH協議。在100 s附近節點開始緩慢死亡，而且全網的生存時間由之前的280 s延長到420 s，提升了50 %的時間。

圖4　網絡節點存活數目Fig 4　Number of alive node of network

圖5為協議改進前后全網能量消耗的對比圖，圖中看到240 s附近兩種協議能量消耗線相交，前期改進的協議能量消耗大于原LEACH協議。但改進后的協議讓整個網絡的生存時間由之前的280 s延長到了420 s，大大的延長了網絡的壽命。

圖6為基站接收數據包對比圖，由圖中可以看出，改進后協議接收的數據包比原協議接收的數據包多接收了700 000個，效率提升了175 %。

圖5　全網能量消耗Fig 5　Energy consumption of the whole network

圖6　基站接收數據包的數量Fig 6　Amount of data packets received by base station

4結束語

本文首先分析了LEACH協議，針對LEACH協議的不足，在簇頭的選取時加入了節點的位置信息和當前剩余能量信息。同時在備選簇頭的產生時引入距離因素M，并在備選簇頭產生簇頭時引入退火算法提出新的改進LEACH協議。NS2的仿真結果表明:新的改進LEACH協議使協議的分簇更為合理，同時有效延長網絡壽命并能夠提高網絡的接收數據量。

參考文獻:

[1]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-effi-cient communication protocol for wireless microsensor network-s[C]∥Proc of the 33rd Annual Hawaii Int'l Conf on System Sciences,Maui:IEEE Computer Society,2000:3005-3014.

[2]Lindsey S,Raghavendra C,Sivalingam K.Data gathering in sensor networks using the energy delay metric[C]∥Proc of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing，2001.

[3]Heinzelman W B.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，10:660-670.

[4]Yang Yang，Bai Enjian，Hu Jia，et al.MRBCH:A multi-path routing protocol based on credible cluster heads for wireless sensor networks[J].J Communications，Network and System Sciences，2010，3:689-696.

[5]Gou Haosong，Yoo Younghwan.An energy balancing LEACH algorithm for wireless sensor networks[C]∥2010 The Seventh International Conference on Information Technology，2010：822-827.

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

[7]劉永超，張月霞，繆旻.基于能量和距離的分區域選擇簇首WSNs 路由算法[J].傳感器與微系統，2015，34(1)：124-127.

[8]魏玉宏，田杰，孔韋韋.一種基于LEACH 協議高效節能的數據融合算法[J]．傳感器與微系統，2015，34(6):148-151．

[9]馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術學報，2013,26(8):1147-1158.

[10] 曹欲曉，徐金寶，徐夢溪,等.無線傳感器網絡LEACH協議的二進制粒子群改進算法[J].電子技術應用，2015，41(4):91-93.

Optimization of LEACH protocol based on node position and residual energy*

YU Cheng-bo,DENG Shun-hua,FANG Jun,YU Yu-jie

(Institute of Remote Test and Control,Chongqing University of Technology,Chongqing 400054,China)

Abstract:LEACH has many problems in election of cluster head and energy consumption control,aiming at these problems,propose improvement for generation mode of LEACH protocol cluster head.The improved LEACH protocol is to add specific location information of network nodes and current remaining energy information of network node in original LEACH protocol,alternative cluster head node spacing and simulated annealing algorithm are introduced in cluster head selection stage.The simulation results on NS2 show that the improved LEACH protocol makes selection of cluster head more reasonable,and the whole network lifetime is extended 50 %,and amount of receiving data of base station is increased by 175 %.

Key words:wireless sensor networks(WSNs);LEACH protocol;location information;residual energy;simulated annealing algorithm;NS2

DOI:10.13873/J.1000—9787(2016)05—0139—03

收稿日期：2015—10—19

*基金項目：重慶市高校優秀成果轉化資助項目(KJZH14213)；重慶市科技人才培養計劃(新產品研發團隊)資助項目(CSJC2013KJRC—TDJS40012)

中圖分類號：TP 393

文獻標識碼：A

文章編號：1000—9787(2016)05—0139—03

作者簡介:

余成波(1965-)，男，江西鄱陽人，博士，教授，博士生導師，主要從事信號與信息處理、遠程測試與控制技術的研究。