基于HEB無線傳感器網絡分簇路由算法的研究

何學文， 曹清梅， 鄭樂平

(江西理工大學機電工程學院，江西 贛州341000)

基于HEB無線傳感器網絡分簇路由算法的研究

何學文， 曹清梅， 鄭樂平

(江西理工大學機電工程學院，江西 贛州341000)

針對低功耗自適應集簇分層型協議(LEACH)存在網絡節點能耗不均、簇頭節點數據傳輸不合理等問題，在基于對LEACH算法優化的思想上，提出了一種異構能量均衡路由算法(HEB).該算法通過引入閾值因子、剩余能量因子、節點密度因子和最短數據傳輸模型，優化了簇頭選舉機制和簇頭節點之間的數據傳輸，使簇頭的選擇與建立、數據傳輸穩定更合理.仿真結果表明:與LEACH、DEEC以及SEP路由算法相比，HEB路由算法使整個網絡能耗更加均衡，數據傳輸穩定、擴大了有效數據的傳輸量，延長了整個網絡的壽命.

無線傳感器網絡;低功耗自適應集簇分層型協議;HEB路由算法;網絡能耗;

0 引 言

無線傳感器網絡 (Wireless Sensor Networks，WSN)綜合了傳感器技術、信號處理技術、片上系統SOC以及無線通信等技術，它具有網絡規模大、自組網、動態性拓撲、可靠性高等優點;但存在有限的存儲、運行空間和計算能力等缺點.如何降低網絡能耗是一個關于WSN路由協議熱門研究中亟待解決的問題.

LEACH (Low EnergyAdaptiveClustering Hierarchy)是一種典型的分簇路由協議，具有較強的數據融合能力，存在簇頭選擇不合理、網絡能耗不均以及簇頭節點數據傳輸不合理等不足.不少國內外研究者針對LEACH協議進行了改進，取得了一定的研究成果及學術價值.主要包括:文獻[1-2]優化了簇頭的選擇機制，使網絡能耗更加均衡，但簇頭的數據傳輸采用單跳的方式，增大了網絡的能耗.文獻[3]設想出用簇成員數門限和合并極小簇的方法解決極大簇和極小簇沖突的問題，但簇頭的數據傳輸不合理，增大了數據通信半徑.文獻[4]提出了一種基于節點信任的LEACH協議，該協議優化了簇頭選擇模型，但能量過低的節點也能參與簇頭的選擇，加速了部分節點失效.文獻[5]對于簇頭的選擇，同時在基于存在剩余能量大小和網絡的平均能量差別的因素的前提下，提出有效控制簇頭的個數的方法，但網絡存在“熱區”問題.文獻[6]提出了一種改進型LEACH協議，優化了簇頭的選擇機制和簇頭的數據傳輸采用多跳方式，延長了網絡的生存周期，但網絡的整個能耗不均衡.

文中提出的HEB路由算法綜合考慮了能量閾值、剩余能量和平均能量、節點密度等參數，結合了單跳和多跳通信方式，從而避免了網絡能耗不均問題.同時，文中提出的HEB路由算法對于異構網絡也適用.

1 HEB協議網絡結構

在無線網絡路由協議的結構中，與平面路由協議相比，層次路由協議具有時間同步高、可拓展性好和傳輸延遲小等特性.本文HEB路由算法應用于層次性無線網絡，具體結構如圖1所示.采集的數據在網絡簇內各個節點以單跳方式傳輸發送給網絡中轉的簇頭節點，簇頭節點之間通過多跳中繼的方式進行通信，最終將傳感采集的數據發送給基站.

圖1 HEB協議的網絡結構

2 算法模型的相關定義

2.1 能量閾值因子

以往大多數分簇路由算法中，能量低的節點也能參與簇頭的選擇，加速了部分節點失效.基于這種思想，引入能量閾值因子a，當節點剩余能量值不小于a時，該節點此時有資格參與競選簇頭，反之，則不能參與簇頭節點的選擇.能量閾值因子a的表達式為[7]:

其中，q表示調節系數大小，Ecurrent-i表示節點當前能量值大小.可以通過不斷調整q系數的大小來改變剩余能量閾值因子a，使網絡處于最佳性能.其中，a的取值范圍為0～1.

2.2 剩余能量因子

當節點剩余能量較少時，此時被選為簇頭節點，節點將馬上失效，引起網絡拓撲結構發生變化.如果網絡只考慮節點的剩余能量，作為簇頭選擇的依據，會造成整個網絡的能量負載失衡，導致局部網絡過早消亡，影響網絡的性能.考慮到網絡的能量負載平衡這一因素，文中提出了一種剩余能量因子b，b的表達式為[8]:

其中，g表示調節系數大小，Ecurrent-i表示節點i當前能量值大小.b的取值范圍為0～1.

2.3 節點密度因子

當網絡中節點通信區域內節點的數量越多，即密度越大，在自組織組網過程中，被選為簇頭節點的概率就越大，反之，節點被選擇為簇頭節點的概率越小.節點密度參數c的表達式為:

其中，Ns(i)表示節點i的有效通信區域范圍內的網絡節點總數，N表示網絡中所以存活的網絡節點的數值.c的取值范圍為0～1.

3 HEB路由算法描述

HEB協議的基本思想與LEACH協議差不多，主要包括閾值的判定、簇頭的確立、簇頭范圍內節點的加入和數據傳輸.

1)閾值判定:在進行簇頭選擇之前，節點根據能量閾值因子a判定是否有資格參與簇頭的選擇，當節點能量大于能量閾值因子a時，成為參與簇頭的選擇的節點，反之，節點不能參與簇頭的選擇.

2)簇頭選擇:Sink節點將簇頭節點的選擇信息進行廣播后，節點能否作為簇頭由式(4)確定[9-12].當節點被選擇為簇頭節點后，向周圍廣播簇頭節點信息，以便鄰近節點的加入.

其中p表示首次網絡運行時簇頭節點的比例數目大小，k1，k2為可調參數.當T(Snrm)值越大時，節點被選為簇頭節點的概率也越大.

3)簇頭范圍內節點的加入:簇頭選擇完成后，其余節點收到來自多個簇頭節點的信息，節點根據信號的強弱自行判斷申請加入簇，并記錄簇頭信息.簇頭節點收到申請消息時，記錄相關節點信息并安排時隙.

4)數據傳輸:在節點自組織組網結束后，簇內各個節點主動感知、采集被監測區域的信息，接著無線傳輸發送給簇頭節點.當簇頭節點的狀態時正處于工作時，節點進入休眠轉態，等待下一個時鐘喚醒.簇頭節點按照預先設置好的時隙表有效的接收傳輸的數據.簇頭節點之間通過多跳方式進行信息傳輸，簇頭的在網絡通信中下一跳網絡地址由最短通信模型決定.最短通信模型如下:

設Pi為i個簇頭，dpipj為簇頭i與j的通信距離的大小，dpjs為第j個簇頭與匯聚節點的通信距離大小，最短路徑d的表達式(5)[13]，

閾值因子a通過判斷節點的剩余能量大小來判斷節點是否參與簇頭節點的選擇，剩余能量過小，則不參與簇頭節點的選擇，避免因某個節點的失效影響網絡的壽命;剩余能量因子b和節點密度因子c直接影響公式(4)中T(Snrm)的大小，也就是簇頭節點的選擇.其中，b和c越大，T(Snrm)越大，節點被選為簇頭節點的概率越大，其中T(Snrm)的取值范圍為0～1.

4 仿真結果與分析

文中采用MATLAB軟件對HEB路由算法進行仿真，并與異構網絡分簇算法(Distribute Energyefficient clustering Alogorithm，簡稱DEEC[14];Stable Election Protocol，簡稱SEP[15])進行比較.實驗節點隨機部署于面積為100 m×100 m區域內，在區域內部，隨機均勻部署100個傳感器網絡節點;網絡基站設置在坐標為(50，50)的地方;網絡實驗節點的初始能量值大小參數為0.5 J;高能量節點與普通節點能量之比參數值為2;高能量節點數占總節點的比例為0.3;數據包的參數值是4000 bits，能量閾值因子為0.5，剩余能量因子b取0.2，節點密度密度因子c取0.5，T(Snrm)取0.6.通信模型采用文獻[7]的無線通信模型.

圖2表示不同算法下的整個網絡周期的對比.從圖中可以看出，與其它3種算法相比，使用HEB路由算法，網絡的首個節點失效到整個網絡節點失效的時間間隔最長，且首個節點失效時間最長，從而可以有效的增大了網絡利用的有效生命周期.

圖2 網絡周期對比圖

表1表示不同算法下的首個節點死亡的時間，從圖可得，改進HEB算法首個節點失效需要時間最多，網絡穩定周期延長，說明文中改進HEB算法提高了能量利用率.

表1 不同算法下的首個節點失效狀況

表2表示不同算法下的死亡節點總數，與其他3種算法比較，改進HEB算法剩余節點最多，能夠進一步延長網絡的壽命.

表2 不同算法下的死亡節點總數

圖3表示4種算法對網絡的能耗影響.從圖3可以看出，在0～1500輪之間，使用HEB路由算法，網絡的能耗最小，且網絡能耗曲線較緩.其中LEACH、DEEC在網絡運行了第1800輪左右，兩種算法下的整個網絡能量耗盡，SEP在3800輪左右網絡能量耗盡，但HEB路由算法一直到仿真結束后，整個的網絡能量才耗盡.從而有效的說明了文中提出的HEB算法降低了整個網絡節點的工作能耗開銷，使整個網絡能耗更加均衡.

圖3 網絡能耗在不同算法下消耗量大小對比

圖4 不同算法下的數據量對比

圖4顯示了HEB路由算法與LEACH、DEEC以及SEP路由算法下的網絡數據傳輸總量對比.仿真結束后Sink節點收到的數據量的對比如表3所示，可以看出，前兩種算法在網絡運行1800輪后，由于大部分節點失效，不再產生網絡傳輸數據.與其它算法比較，HEB算法所產生的數據傳輸總量最多，且仿真結束后還存在存活節點.因此，與其它3種路由算法比較，HEB路由算法獲取的信息量最大.

表3 不同算法下的網絡數據傳輸量大小

結合以上仿真結果，綜合考慮首個節點失效時間、網絡的運行周期、網絡的能耗以及整個網絡的數據傳輸量，文中提出的HEB路由算法要優于其它3種算法.在初始能耗一定時，基于文中算法下網絡的各項性能都比較好，例如穩定性、壽命以及能量使用效率等.從而對文中提出的改進型LEACH算法的HEB路由算法的有效性得到了驗證.

5 結束語

文中主要研究了WSN分簇路由算法，在以分析和改進典型分簇路由算法LEACH存在的缺點的思想上，提出了一種新的基于能量閾值因子、剩余能量因子、節點密度因子和最短數據傳輸模型的HEB路由算法，解決了節點能耗失衡、擴大網絡容量以及WSN低能耗問題.仿真結果表明，文中提出的HEB路由算法可以減少整個網絡的通信半徑，從而降低節點工作能耗，有效的延長了整個網絡的生存壽命，但并未具體應用到實際工作環境中，有待進一步實際應用的完善和改進.

[1]Bajaber F，Awan I.Centralized dynamic clustering for wireless sensor network[C]//International conference on advanced information networking and applications workshops，2009:193-198.

[2]游曉黔，李明隆，楊佳.無線傳感器網絡LEACH協議的研究與改進[J].重慶郵電大學學報(自然科學版)，2011，6(3):746-751，764.

[3]呂濤，朱清新，張路橋.一種基于LEACH協議的改進算法[J].電子學報，2011，39(6):1405-1409.

[4]白林林，嚴斌宇，羅敬文，等.基于節點信任的LEACH協議簇頭選舉改進算法[J].四川大學學報(工程科學版)，2012，45(8):218-223.

[5]王振飛，紀越峰.基于能量均衡策略的無線傳感器網絡LEACH協議改進[J].東南大學學報(自然科學版)，2008，30(7):262-270.

[6]楊永健，賈冰，王杰.無線傳感器網絡中LEACH協議的改進[J].北京郵電大學學報，2013，36(1):105-109.

[7]Heinzelman WR，Chandrakasan A P，Blakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless，2002，1(4):660-670.

[8]Akyild I F，Su W，Sankarasubramaniam Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[9]李玉凱.無線傳感器網絡高能效可靠數據傳輸理論及應用研究[D].北京:華北電力大學，2011.

[10]藍勻云.基于信息交互的無線傳感器網絡改進LEACH協議研究[D].上海:華東理工大學，2012.

[11]劉加杰，孫子文.基于代理和熵權的無線傳感器網絡數據融合[J].計算機應用研究，2012，29(10):879-882.

[12] Bajaber F，Awan I.Centralized dynamic clustering for wireless sensor network[C]//International conference on advanced information networking and applications workshops，2009:193-198.

[13]高德民，錢煥延，嚴筱永，等.無線傳感器網絡最大生命期數據融合算法[J].南京理工大學學報，2012，36(1):55-60.

[14]陳偉琦，胡斌杰.基于高斯隸屬度的融合算法在改進LEACH中的應用[J].傳感器與微系統，2011，30(2):35-138.

[15]李悅，孫力娟，王汝傳，等.一種改進的無線傳感器網絡LEACH算法[J].計算機研究與發展，2011，48(增刊2):131-134.

Research on clustering routing algorithm in wireless sensor networks based on HEB

HE Xuewen，CAO Qingmei，ZHENG Leping
(School of Mechanical and Electrical Engineering，Jiangxi University of Science and Technology，Ganzhou 341000，China)

Since the low energy adaptive clustering hierarchy protocol(LEACH)has the disadvantages that energy consumption of nodes is inequality and the data transmission of cluster head node is not reasonable，this paper proposed a Heterogeneous Energy Balanced Routing Algorithm (HEB)to optimize it.The selection of cluster head and the data transmission of HEB algorithm are more reasonable by introducing the threshold factor，energy factor，node density factor and the short data transmission model.The simulation results show that:compared with LEACH，DEEC and SEP routing algorithm，HEB routing algorithm makes the energy consumption of the whole network more balanced，transmission rate of data more stable.Besides，it increases the transmission capacity of the effective data and prolongs the life span of the networks.

Wireless Sensor Network (WSN);Low Energy Adaptive Clustering Hierarchy (LEACH);HEB routing algorithm;network energy

2095-3046(2015)01-0099-05

10.13265/j.cnki.jxlgdxxb.2015.01.017

TP398

A

2014-07-22

國家自然科學基金項目(61163063，50764005);江西省教育廳科技項目(GJJ12329，GJJ12353)

何學文(1971- )，男，博士，教授，主要從事無線傳感器網絡相關工作的研究，E-mail:hxw993@vip.163.com.