基于分簇和覆蓋優化的改進LEACH協議

陳 樹,徐 圓

(江南大學物聯網工程學院,江蘇無錫214122)

基于分簇和覆蓋優化的改進LEACH協議

陳 樹,徐 圓

(江南大學物聯網工程學院,江蘇無錫214122)

針對傳統LEACH協議中簇頭數量自由度高以及分布不均所導致能量消耗過多的缺陷,提出一種基于優化分簇的、能耗均勻的改進LEACH協議。改進簇頭選擇機制,在常規能量閾值選取簇頭節點的過程中,引入最優簇半徑控制策略,改善簇頭節點的物理分布位置,達到網絡能量的均衡,同時引入網絡覆蓋率控制簇頭數目,避免產生多余的簇頭節點。該算法還在傳統LEACH協議的基礎上,使用CH-VCH交替輪尋策略簡化計算量。仿真結果表明,該改進LEACH協議能解決傳統LEACH協議存在的能量問題,使網絡的能量消耗更加均勻,并在一定程度上延長網絡的生存期限。

LEACH協議;能量消耗;最優簇半徑;簇頭

1 概述

LEACH協議是一個適用于傳感網絡的協議架構。它應用于典型傳感網絡[1]中的路由選擇[2]。

傳統LEACH協議使用輪次作為參數的閾值T(n),作為判斷簇頭選擇的依據,各個節點隨機成為簇頭[3]。如果不考慮能量消耗,選取了剩余能量較少的節點成為簇頭節點,就很容易出現節點過早死亡、能量消耗不均勻的情況[4]。LEACH協議的能量均勻消耗是人們研究的熱點。

文獻[5]提出的LEACH改進以及文獻[6]提出的LEACH-N協議將節點的剩余能量和初始能量作為參數加入閾值的計算,使得節點的剩余能量越少時,節點能夠被選為簇頭節點的概率越小,優化簇頭選擇。文獻[7]提出E-LEACH協議,在閾值中加入能量參數后,引入最小生成樹的概念,選擇剩余能量最多的簇頭節點作為根節點,首輪閾值選擇加入能量參數后,從第2輪開始,通過考慮最佳的成簇大小計算每輪閾值,控制簇頭數量,為確保整個網絡的能量均衡消耗。文獻[8]依舊從閾值的角度加入能量參數對LEACH協議的閾值進行改進,同時還考慮節點當選簇頭節點的次數,改變節點被選為簇頭節點的概率,并均衡節點消耗的能量。該算法通過使用CH(簇頭節點)-VCH(副簇頭節點)交替的循環策略,簡化計算量,同時節省了多余能量的消耗。

通過研究發現,在改進的LEACH協議中,把節點的剩余能量、簇頭節點數等作為參數加入閾值,通過參數影響閾值控制選取節點的數量,能夠更加有效延長網絡的使用壽命。但上述研究都沒有考慮簇頭節點分布的問題,簇頭節點的隨機分布會使得網絡的負載不平衡,加快節點死亡[9]。本文以均衡衡量消耗為目的,針對簇頭節點分布問題對簇頭選擇進行改進。

2 LEACH協議的改進

本文在簇頭選擇時,使用文獻[8]中提出的閾值T(n):

其中,p是簇頭節點占總節點的百分比;r是輪數;G是1/p輪中沒有做過簇頭節點的節點數;En_current是該節點的剩余能量;En_init是該節點的初始能量。初始定義節點的總能量為2 J;CH_times表示該節點當選過簇頭CH的次數;VCH_times表示該節點當選過簇頭VCH的次數,閾值T(n)是針對每個節點的不同剩余能量分別計算的,參數CH_times,VCH_times加入閾值計算中,已當選過簇頭CH或者副簇頭VCH的節點,之后成為簇頭的概率就相對減少。

在LEACH協議中,隨機分布的簇頭節點位置很大概率上可能造成某塊通信區域內,當簇頭位置相對集中時,簇頭的覆蓋區域出現大量重疊,能量重復消耗,或者在某一塊區域內,簇頭節點太過分散分布,簇頭節點數量很少。普通節點加入很遠距離的簇頭,使得節點的載荷也變大,節點很快出現死亡,加速了網絡的死亡[10]。

(2)目前關于再生細骨料種類、取代率對再生砂漿抗壓強度和和易性的研究較多。而對于力學性能中的抗折強度、彈性模量等指標，耐久性中的抗凍性、抗滲性、抗碳化性能等指標，再生砂漿的強度形成機理、水泥漿與再生細骨料的界面分析等的研究還比較缺乏，有待于不斷補充和完善。

本文針對LEACH協議在簇頭建立階段選擇簇頭時簇頭分布的隨機性,以及簇頭個數沒有一個合理的限制進行改進。

2.1 簇頭選擇

在初選簇頭的時候,加入簇頭選擇規則:首輪選出一個隨機值小于閾值的簇頭節點,第一個簇頭選出后,逐一對接下來產生的簇頭進行篩選,計算已選簇頭的通信半徑,如果新產生的備選簇頭在已選簇頭的通信范圍之內,對節點進行標記,之后的簇頭將從未被標記過的節點中選取,被標記過的節點放棄競爭簇頭,未被標記過且滿足閾值條件的節點才有可能作為簇頭。如圖1所示。由此選擇機制產生的簇頭之間的距離必然大于等于一個簇頭的成簇半徑R。

圖1 改進的成簇算法

其中,A為傳感器分布區域的面積;N為區域中單個節點的能量;EDA為感知每比特數據所需要的能量;εfs為功率放大所需的能量。由此,最優簇半徑R能夠確保在網絡內部用于感知數據傳輸的能量消耗相對合理。

該簇頭選擇策略在簇頭產生的過程中控制簇頭之間距離,防止簇頭間距過小,減少生成過多冗余簇頭所造成的能量浪費。

當普通節點基本上都在簇頭的最優簇半徑內時,已能夠保證網絡的基本通信要求得到滿足,此時的數據傳輸最節省能量,再產生新的簇頭僅會消耗過多的能量,并不能對網絡通信做出有效的貢獻。因此,當普通節點的90%被簇頭節點的成簇半徑覆蓋時,就需要控制簇頭節點的數量,停止產生冗余的簇頭,以此來再一次避免能量的浪費。

2.2 數據傳輸

穩定數據傳輸時,定義單次數據傳輸過程中發送節點到接受節點之間的距離為d。

每個節點發送一個數據包消耗的能量為[12]:

單個節點接收一個數據包消耗的能量為:

其中,l為傳輸數據包的長度;Eelec表示無線收發電路所消耗的能量;εfs和εamp分別為自由空間模型和多路徑衰減模型2種情況下信號放大器能量消耗的比例系數;εfsd2和εmpd4定義為每放大1 bit數據放大器需要消耗的能量;d0為常數,取決于傳感器網絡應用的環境。

d0臨界值由下式決定:

3 算法描述

基于分簇和覆蓋優化的策略對LEACH協議改進的詳細算法描述如下:

(1)CH簇頭選擇。計算簇頭節點的能量閾值,以及最優簇半徑等參數,運用本文改進的簇頭選擇規則選舉簇頭,并根據簇頭覆蓋率控制簇頭數量。如圖2所示。

圖2 簇頭選舉

(2)建立簇的通信。簇頭節點廣播自己的ID、位置等信息。普通節點選擇最近的簇頭節點加入簇。完成簇的建立,與簇頭之間進行數據傳輸,一輪傳感信息傳輸之后,記錄每個節點的剩余能量E,并對網絡的剩余能量進行計算并記錄。

(3)VCH副簇頭節點選擇。在下一輪的VCH簇頭選擇過程中,以簇為單位,標記一個簇內剩余能量最多的節點,作為下一輪的VCH簇頭。

(4)數據傳輸階段。該VCH簇頭節點廣播簇頭節點信息,普通節點遍歷所有的簇頭,選擇最近的簇加入,網絡重新形成分簇。并依照相同的能量損耗模型在簇內進行數據傳輸,計算網絡內傳感節點的能量損耗。

(5)新的一輪循環開始。按照相同的選擇機制,重新選擇CH主簇頭節點,如果本輪沒有選擇出簇頭節點,考慮到所有節點與BS基站通信,會浪費很多能量,則本輪不進行通信,直接進入下一輪選擇CH簇頭節點。

程序流程如下:

4 仿真與結果對比

仿真實驗采用Matlab作為仿真平臺。對傳統LEACH協議[12]、參考文獻中Liang Ying改進的協議LEACH1、Fuzhe Zhao的改進LEACH2,以及本文對LEACH協議的能量均衡改進進行仿真和性能對比。并且為了減少偶然性,對每種情況在同一個節點分布下獨立運行100次,統計結果的平均值。在這里提供的相同的100 m×100 m的網絡環境進行節點布局,其他相關參數的設置見表1。

表1 仿真參數設置

在仿真實驗中,還設置了一些其他參數:

分析網絡性能的參數有許多[13],本文在這里以輪數為單位選用具有代表性的剩余節點、網絡剩余能量,以及簇頭節點個數這3個性能參數對其進行對比。

圖3表示該網絡中節點的分布。節點均勻的分布在100 m×100 m的網絡仿真區域中,對所有的節點都定義同樣的初始能量0.5 J。本文排除了節點具有相同坐標的可能,使節點相對地均勻分布,通過圖表觀察,這些節點分布很均勻,沒有區域太擁擠或者空白,這和期望是一致的。

圖3 節點分布

圖4為簇頭節點基于最優簇頭半徑R覆蓋網絡后,以輪為單位,記錄每輪被選為簇頭節點的節點數。

從圖4中可以看出,在仿真開始階段,前幾種改進中的簇頭節點個數都明顯過多,LEACH1協議中簇頭數量最多時超過了13個簇頭,這其中有很多多余簇頭,資源的重復利用浪費了大量能量。本文改進的簇頭節點個數在整個仿真中能夠相對均勻的分布,通過最優選擇策略,合理地選擇不超過9個節點作為簇頭,簇頭數量最多時平均不超過8個簇頭。

圖5表示網絡中還未死亡的節點數量,不考慮其他外在的因素,如果某個節點的能量小于或等于0,就認為這個節點已經死亡。

圖5 剩余節點數

當網絡內節點基本上都已經死亡,無法進行正常的數據傳輸,視為網絡已死亡。網絡中剩余節點的數量就是反應這個網絡能量是否均勻消耗的標志。

通過對比可以明顯看出,在100次實驗結果平均后,本文改進的LEACH協議存活節點數量在相同輪數均能高于其他改進協議,LEACH協議在接近400輪的時候,出現第一次節點死亡,而本文改進的選擇策略最遲出現節點死亡,在運行到500輪以后才會第一次出現節點死亡,大大減緩了節點死亡的速度。

仿真結果表明:在相同時間下,本文相對于其他的改進能保持更多的活躍節點,以傳輸更多的數據信息給基站。本文的LEACH協議改進在仿真過程中是均優于其他2種改進的。

圖6在仿真初始階段,每個節點的能量都是相同的,為0.5 J,網絡初始能量為節點能量的總和,即50 J,仿真中網絡能量均從50 J開始,經過數據傳輸的消耗,能量趨于0。可見,本文改進后的剩余能量曲線的斜率最小,反映出節點的負載均衡性最好。本文改進網絡的成簇規則,使得節點在數據傳輸中,對能量進行了合理的分配,避免消耗多余的能量,從而網絡死亡的速率小于其他改進,網絡的壽命得以延長。

圖6 網絡剩余能量

5 結束語

本文針對傳統LEACH協議能量過多損耗的問題,對其簇頭選舉策略進行優化,以均衡節點能量的損耗。仿真實驗結果表明,本文算法在簇頭數量優化和分布均勻2個方面都有改進,很大程度上改善了網絡能量消耗,有效地延長網絡的使用壽命。

[1] 王仁興,易靈芝,王根平,等.基于LEACH協議的無線傳感器網絡路由算法[J].計算機測量與控制,2012, 20(11):3129-3135.

[2] Meenakshi S,Kalpana S.An Energy Efficient Extended LEACH[C]//Proceedings of 2012 International Conference on Communication Systems and Network Technologies.[S.l.]:IEEE Computer Society,2012:377-382.

［3］ 唐甲東,蔡 明.基于LEACH協議的能耗均衡路由算法［J］.計算機工程,2013,39(7):133-141.

［4］ 王偉超,代增全,徐啟建.LEACH協議簇頭選擇算法的改進［J］.無線電工程,2010,40(3):1-3.

［5］ Liang Ying,Yu Haibin.Energy Adaptive Cluster-head Selection for Wireless Sensor Networks［C］// Proceedings of the 6th International Conference on Parallel and Distributed Computing,Applicationsand Technologies.Dalian,China:［s.n.］,2005:634-638.

［6］ Xu Jia,Jin Ning,Lou Xizhong,et al.Improvement of LEACH Protocol for WSN［C］//Proceedings of 2012 International Conference on Fuzzy Systems and Knowledge Discovery.Chongqing,China:［s.n.］,2012:2174-2177.

［7］ Li Yuling,Ding Luwei,Liu Feng.The Improvement of LEACH Protocol in WSN［C］//Proceedings of 2011 International Conference on Computer Science and Network Technology.［S.l.］:IEEE Press,2011:1345-1348.

［8］ Zhao Fuzhe,Xu You,Li Ru,et al.Improved Leach Communication Protocol for WSN［C］//Proceedings of 2012 International Conference on Control Engineering and Communication Technology.Jilin,China:［s.n.］, 2012:700-702.

［9］ 王志剛,李臘元,李春林.一種新的無線傳感器網絡均勻分簇路由協議［J］.計算機工程與應用,2009, 45(31):81-84.

［10］ 王振飛,紀越峰.基于能量均衡策略的無線傳感器網絡LEACH協議改進［J］.東南大學學報,2008,38(S1): 262-270.

［11］ 劉 明,曹建農,陳貴海,等.EADEEG:能量感知的無線傳感器網絡數據收集協議［J］.軟件學報,2007, 18(5):1092-1109.

［12］ Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Network［J］.IEEE Transactions on Wireless Communications,2002,4(1):660-670.

［13］ 萬青苗,張浩平,王 強,等.無線傳感器網絡LEACH協議的改進研究［J］.電腦知識與技術,2012,32(8): 7679-7701.

編輯 任吉慧

Improved LEACH Protocol Based on Clustering and Coverage Optimization

CHEN Shu,XU Yuan
(School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

As high free degree of amount and uneven distribution of the cluster-head nodes cause high energy consumption,this paper presents a novel improved LEACH protocol algorithm based on cluster optimization and energy balance.In the process of selecting cluster-heads according to the conventional energy threshold,the improved selection mechanism selects cluster-head with the optimal cluster-radius control strategy and optimizes the distribution of cluster-head nodes.In the meantime,the coverage rate is put forward to avoid extra cluster-heads and keep the amount of cluster-head nodes.It uses CH-VCH alternate circulated strategy to simplify the calculation.The simulation reveals that the improved LEACH protocol can solve the problem that the traditional one can not do.It can average the energy consumption and prolong the survival period of the wireless sensor networks.

LEACH protocol;energy consumption;optimal cluster-radius;cluster-head

1000-3428(2014)11-0097-04

A

TP393.02

10.3969/j.issn.1000-3428.2014.11.019

國家自然科學基金資助項目(21206053);江蘇省六大人才高峰基金資助項目(2012-WLW-006)。

陳 樹(1969-),男,副教授,主研方向:無線傳感器網絡及通信,過程控制與優化,現場總線及控制技術;徐 圓,碩士研究生。

2013-11-27

2014-01-20E-mail:95442600@qq.com

中文引用格式:陳 樹,徐 圓.基于分簇和覆蓋優化的改進LEACH協議[J].計算機工程,2014,40(11):97-100.

英文引用格式:Chen Shu,Xu Yuan.Improved LEACH Protocol Based on Clustering and Coverage Optimization[J].Computer Engineering,2014,40(11):97-100.