基于分簇和覆蓋優(yōu)化的改進LEACH協(xié)議

陳 樹,徐 圓

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

基于分簇和覆蓋優(yōu)化的改進LEACH協(xié)議

陳 樹,徐 圓

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

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

LEACH協(xié)議;能量消耗;最優(yōu)簇半徑;簇頭

1 概述

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

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

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

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

2 LEACH協(xié)議的改進

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

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

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

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

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

2.1 簇頭選擇

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

圖1 改進的成簇算法

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

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

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

2.2 數據傳輸

穩(wěn)定數據傳輸時,定義單次數據傳輸過程中發(fā)送節(jié)點到接受節(jié)點之間的距離為d。

每個節(jié)點發(fā)送一個數據包消耗的能量為[12]:

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

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

d0臨界值由下式決定:

3 算法描述

基于分簇和覆蓋優(yōu)化的策略對LEACH協(xié)議改進的詳細算法描述如下:

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

圖2 簇頭選舉

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

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

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

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

程序流程如下:

4 仿真與結果對比

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

表1 仿真參數設置

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

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

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

圖3 節(jié)點分布

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

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

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

圖5 剩余節(jié)點數

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

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

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

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

圖6 網絡剩余能量

5 結束語

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

[1] 王仁興,易靈芝,王根平,等.基于LEACH協(xié)議的無線傳感器網絡路由算法[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協(xié)議的能耗均衡路由算法［J］.計算機工程,2013,39(7):133-141.

［4］ 王偉超,代增全,徐啟建.LEACH協(xié)議簇頭選擇算法的改進［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］ 王志剛,李臘元,李春林.一種新的無線傳感器網絡均勻分簇路由協(xié)議［J］.計算機工程與應用,2009, 45(31):81-84.

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

［11］ 劉 明,曹建農,陳貴海,等.EADEEG:能量感知的無線傳感器網絡數據收集協(xié)議［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協(xié)議的改進研究［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-),男,副教授,主研方向:無線傳感器網絡及通信,過程控制與優(yōu)化,現場總線及控制技術;徐 圓,碩士研究生。

2013-11-27

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

中文引用格式:陳 樹,徐 圓.基于分簇和覆蓋優(yōu)化的改進LEACH協(xié)議[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.