一種能耗平衡和密度感知的無線傳感器網(wǎng)絡分簇算法

余建迪，朱 翔，陳培基，徐超超，唐震洲

（溫州大學 物理與電子信息工程學院，浙江 溫州 325035）

一種能耗平衡和密度感知的無線傳感器網(wǎng)絡分簇算法

余建迪，朱 翔，陳培基，徐超超，唐震洲

（溫州大學 物理與電子信息工程學院，浙江 溫州 325035）

WSN在實際應用中其能量是有限的，因其所處環(huán)境等，后期對能源的補充不易。為了延長其生命周期，此對LEACH算法進行了一些改進，根據(jù)節(jié)點自身能量情況以及節(jié)點密度情況來改進對簇頭的選取方式，并提出了一種EDS-LEACH算法。通過用MATLAB對LEACH算法，EDS-LEACH算法以及2種其他文獻的分簇算法進行仿真比較，驗證了EDS-LEACH算法在網(wǎng)絡的存活時間上較之LEACH算法以及另外兩種分簇算法有顯著提高。

WSN；EDS-LEACHL；能量；簇頭；算法

無線傳感器網(wǎng)絡（WSN：Wireless Sensor Networks）近年來迅速發(fā)展，因其個體小巧、價格低廉、部署方便且擁有強大的監(jiān)測、感知功能，能將采集到的數(shù)據(jù)準確傳輸給用戶進行分析，被廣泛應用于國防、工業(yè)、農(nóng)業(yè)、商業(yè)等[1]。但無線傳感器網(wǎng)絡的每個傳感器節(jié)點的電池容量有限，網(wǎng)絡中的傳感器個數(shù)多且分布不均，節(jié)點所處環(huán)境不定，對于給傳感器充電或者更換電池來說可能更不易。這就導致了當網(wǎng)絡中大部分節(jié)點耗盡能量，整個網(wǎng)絡就將瀕臨癱瘓。因此，如何延長無線傳感器網(wǎng)絡的平均壽命成為了研究無線傳感器網(wǎng)絡的重點問題之一。

考慮到各節(jié)點能量不平衡，無線傳感器網(wǎng)絡通常采用分簇的方式，通過選擇簇頭來轉(zhuǎn)發(fā)信息給基站的方式，延長網(wǎng)絡平均壽命。LEACH算法就是一種基于多簇結構的自適應聚類路由協(xié)議[2]。其通過簇頭節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)給基站，減少了每個節(jié)點向基站發(fā)送數(shù)據(jù)的次數(shù)以及所產(chǎn)生的信號沖突問題，提高數(shù)據(jù)發(fā)送的效率，并且實現(xiàn)了網(wǎng)絡能量負載均衡。然而，LEACH算法也有其自身的不足之處：1）其簇頭選擇未對節(jié)點剩余能量進行判斷。2）其簇頭選擇并沒有考慮到待選擇的節(jié)點的周圍節(jié)點密度。3）其數(shù)據(jù)傳輸僅采用單跳，不利于簇頭節(jié)點降低能耗。

圍繞如何選擇簇頭，如何形成簇群，如何傳輸數(shù)據(jù)，有許多文獻在LEACH的基礎上進行優(yōu)化研究，提出了很多優(yōu)秀的算法和協(xié)議。文獻[3]考慮到節(jié)點初始能量以及節(jié)點密度對閾值算法進行了改進。文獻[4]考慮節(jié)點初始能量和節(jié)點平均能量，提出了LEACH-EA、LEACH-EI兩種新的算法用于不同規(guī)模的無線傳感器網(wǎng)絡。文獻[5]采用中繼節(jié)點承擔數(shù)據(jù)轉(zhuǎn)發(fā)，提出了EB-LEACH分簇多跳路由協(xié)議。文獻[6]結合貪婪算法選擇中繼節(jié)點，提出了一種基于時間的簇頭競爭算法。文獻[7]采用粒子群算法和蟻群算法提出了多跳算法。

文中以無線傳感器網(wǎng)絡的簇頭選擇方式作為切入點，針對上述不足點1與不足點2，提出EDS-LEACH算法，并與文獻[3]文獻[4]所涉及的部分算法以及LEACH算法一同用MATLAB仿真，比較各算法對WSN網(wǎng)絡生命周期的延長情況。

1　LEACH算法介紹

1.1LEACH算法概述

LEACH[2]（Low Energy Adaptive Clustering Hierarchy）是Heinzelman等提出的一種經(jīng)典的自適應型的集群算法。該算法提出了“輪”的概念，每一輪由兩個階段構成：一為初始分簇[8-9]，二為穩(wěn)定狀態(tài)。

1.2初始分簇階段

在LEACH算法的分簇階段，隨機選擇網(wǎng)絡中的節(jié)點作為簇頭節(jié)點，負責接收簇群范圍內(nèi)的節(jié)點發(fā)送的信息，統(tǒng)一轉(zhuǎn)發(fā)給基站節(jié)點，從而使整個網(wǎng)絡的能量負載能夠均衡分配在各個節(jié)點上，延長了首個死亡節(jié)點的生存時間以及總網(wǎng)絡的壽命[10]。

簇頭選擇方式為：網(wǎng)絡中的節(jié)點產(chǎn)生0～1之間的隨機數(shù)，如果這個數(shù)小于閾值T（n）[11]，則該節(jié)點當選簇頭，T（n）的計算方法如圖（1）所示：

其中，p為期望簇頭在節(jié)點總數(shù)的百分比，r為當前輪數(shù)，G為在過去輪中為當選簇頭的節(jié)點集合。由上式可知，當r=0時，T=p，即在初始階段每個節(jié)點都以p的概率成為簇頭。若在此過程中某一節(jié)點成為了簇頭，則其在接下來的輪中都不能再成為簇頭，而若在此過程中每一節(jié)點沒有成為簇頭，則其下一輪中成為簇頭的概率為，比前一輪的概率增加了，因而其成為簇頭的概率得到提升。輪數(shù)r增加，概率T也隨之增加，到時，T=1。所以該網(wǎng)絡中所有的節(jié)點都會在輪中僅成為一次簇頭。

2　LEACH算法改進

LEACH算法通過產(chǎn)生一個閾值，讓節(jié)點自主選擇是否當選簇頭。文中考慮了節(jié)點剩余能量大小以及其覆蓋范圍內(nèi)存活的節(jié)點總數(shù)，但仍保留LEACH算法的基本“輪”機制，在其閾值公式上進行了改進，提出了EDS-LEACH算法。

2.1改進公式

其中，Ecurrent為節(jié)點當前剩余能量，Emax為當前所有節(jié)點里最大的剩余能量，m為節(jié)點監(jiān)聽范圍內(nèi)的節(jié)點數(shù)，M為當前各節(jié)點監(jiān)聽范圍內(nèi)的節(jié)點數(shù)中的最大值。

2.2改進分析

2.2.1節(jié)點能量分析

在原LEACH算法中，任何一個節(jié)點均有機會成為簇頭，然而該算法卻沒有考慮到節(jié)點自身剩余能量情況，當節(jié)點自身剩余能量較少時，若繼續(xù)成為簇頭節(jié)點，該節(jié)點將會加速死亡，從而影響到整個網(wǎng)絡的生命周期。我們可以采取降低其閾值的方案，從而降低該節(jié)點當選為簇頭的概率。

2.2.2節(jié)點密度分析

在公式（2）中，節(jié)點剩余能量率和節(jié)點密度都通過乘法因子的方式引入，其目的是為了讓綜合節(jié)點剩余能量以及節(jié)點密度后的閾值能夠保證其取值范圍不變。若采用將節(jié)點剩余能量率和節(jié)點密度相加后引入，將可能出現(xiàn)簇頭選舉失誤的情況例如，某一節(jié)點，其ρ接近1，而EP接近0時，其總和接近1，相應的T值較大，則該節(jié)點當選簇頭節(jié)點的概率大，一旦該節(jié)點當選簇頭，將很快就死亡，影響整個網(wǎng)絡的生命周期。

3　仿真參數(shù)及結果

文中在Windows平臺下利用MATLAB進行仿真。假設在一個長100 m，寬100 m的區(qū)域內(nèi)隨機分配100個無線傳感器節(jié)點，每個節(jié)點的能量隨機分配，取值范圍是0.3 J到0.5 J之間，基站位于坐標（50 m，50 m），具體參數(shù)[12-14]如表1所示。

網(wǎng)絡存活節(jié)點百分比與工作時長變化關系通過100次的仿真求平均后得出結果如圖1所示，圖中可看出原來的LEACH算法在 550輪時出現(xiàn)了首個死亡節(jié)點，而 EDSLEACH算法在740輪才出現(xiàn)首個死亡節(jié)點，兩者相差200輪。假定當系統(tǒng)內(nèi)的節(jié)點存活數(shù)低于20%后，便認為該系統(tǒng)已癱瘓。由圖知，當改變了閥值的系數(shù)后，網(wǎng)絡生命周期比原來的LEANCH算法要更長，整個網(wǎng)絡的能量利用率得到提高。

表1　仿真參數(shù)

仿真結果運行以1 500輪后節(jié)點存活數(shù)目作為算法節(jié)能的評價指標同時EDS-LEACH算法還與其他文獻所提出的算法進行比較，從圖中看出EDS-LEACH算法優(yōu)于文獻[3]的算法，其曲線與文獻[4]的算法曲線走勢類似，但依舊優(yōu)于文獻[4]所提出的算法。

圖1　剩余節(jié)點曲線

4　結束語

文中針對LEACH算法加以改進，結合節(jié)點自身當前剩余能量以及節(jié)點密度，對LEACH算法的簇頭選舉公式進行修改，提出EDS-LEACH算法，提升了WSN網(wǎng)絡的負載均衡能力，增加了WSN網(wǎng)絡的生命周期。但本文并未考慮到節(jié)點通信方式的改進，如何讓節(jié)點采用復合式單跳多跳[15]結合方式發(fā)送數(shù)據(jù)，我們將進一步深入研究。

[1]李建中，高宏.無線傳感器網(wǎng)絡的研究進展[J].計算機研究與發(fā)展，2008，42（1）：1-15.

[2]LI Hui-yun.An optimized LEATH algorithm in wireless sensor network[C].ISDEA，2014，F(xiàn)ifth International Conference on.IEEE，2014，191-194.

[3]秦相林，王瑋琦.基于延長WSN生命周期的LEACH算法的改進[J]．黑龍江科技信息，2015，15（1）:111-112.

[4]白鳳娥，王莉莉，馬艷艷，等.無線傳感器網(wǎng)絡路由協(xié)議LEACH的算法分析[J].太原理工大學學報，2009，40（4）: 347-351.

[5]周方，李臘元，戴佳佳，等.多跳路由協(xié)議EB-LEACH[J].中北大學學報：自然科學版，2013，34（4）:413-418.

[6]蔣昌江，石為人，唐賢倫，等.能量均衡的無線傳感器網(wǎng)絡非均勻分簇路由協(xié)議[J].軟件學報，2012，23（5）:1222-1232.

[7]鄭波.基于改進粒子群算法的無線傳感器能量優(yōu)化[D].無錫：江南大學，2014.

[8]孫利民，葉馳，廖勇.傳感器網(wǎng)絡的路由機制[J].計算機科學，2004，31（1）:54-57.

[9]LIU Re，WANG Xiu-ping.An improvement to LEACH-based routing algorithm[C].ICIME，2011，133-136.

[10]任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡[J].軟件學報，2003，14（7）:1282-1291.

[11]XU Long-long，ZHANG Jian-jun.Improved LEACH cluster head multi-hops algorithm in wireless sensor networks[C]. DCABES，2010，263-267.

[12]Ameer A A，Younis M.A survey on clustering algorithm for wireless sensor networks[J].Computer Communication，2008，30:2826-2841.

[13]李巖，張曦煌，李彥中.基于LEACH協(xié)議的簇頭多跳（LEACHM）算法[J].計算機工程與設計，2007，28（17）:4158-4160.

[14]劉鐵流，巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡分簇路由算法研究[J].傳感技術學報，2011，24（5）:764-770.

[15]王國芳，李臘元，李春林，等.無線傳感器網(wǎng)絡中基于能量約束的簇首多跳算法[J].傳感器技術學報，2009，22（7）: 997-1001.

An energy consumption balanced and density aware clustering algorithm for wireless sensor networks

YU Jian-di，ZHU Xiang，CHEN Pei-ji，XU Chao-chao，TANG Zhen-zhou
（Whenzhou University，Physics and Electronic Information Engineering College，Wenzhou 325035，China）

The energy of a wireless sensor network is limited.In order to prolong its life cycle，an energy consumption balanced and density aware clustering algorithm based on LEACH protocol is proposed for wireless sensor networks，which is called EDS-LEACH.EDS-LEACH takes full consideration on the residual energy of each node and the density of the network during the process of cluster header selecting.The performance of EDS-LEACH is compared with original LEACH and two other clustering algorithms.The results show that the survival time of the EDS-LEACH algorithm in network is distinctly much longer than the LEACH algorithm and two other clustering algorithms.

WSN；EDS-LEACHL；energy；cluster heads；protocol

TN929.5

A

1674－6236（2016）21-0115-03

2015-11-11稿件編號：201511114

國家自然科學基金資助項目(6130320)；浙江省新苗計劃項目(2013R424016)

余建迪（1995—），男，浙江寧波人。研究方向：無線傳感器網(wǎng)絡及其應用。