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

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

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

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

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

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

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

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

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

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

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

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

1　LEACH算法介紹

1.1LEACH算法概述

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

1.2初始分簇階段

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

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

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

2　LEACH算法改進

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

2.1改進公式

其中，Ecurrent為節點當前剩余能量，Emax為當前所有節點里最大的剩余能量，m為節點監聽范圍內的節點數，M為當前各節點監聽范圍內的節點數中的最大值。

2.2改進分析

2.2.1節點能量分析

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

2.2.2節點密度分析

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

3　仿真參數及結果

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

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

表1　仿真參數

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

圖1　剩余節點曲線

4　結束語

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

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

[2]LI Hui-yun.An optimized LEATH algorithm in wireless sensor network[C].ISDEA，2014，Fifth International Conference on.IEEE，2014，191-194.

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

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

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

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

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

[8]孫利民，葉馳，廖勇.傳感器網絡的路由機制[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]任豐原，黃海寧，林闖.無線傳感器網絡[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協議的簇頭多跳（LEACHM）算法[J].計算機工程與設計，2007，28（17）:4158-4160.

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

[15]王國芳，李臘元，李春林，等.無線傳感器網絡中基于能量約束的簇首多跳算法[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—），男，浙江寧波人。研究方向：無線傳感器網絡及其應用。