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

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

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

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

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

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

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

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

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

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

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

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

1　LEACH算法介紹

1.1LEACH算法概述

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

1.2初始分簇階段

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

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

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

2　LEACH算法改進(jìn)

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

2.1改進(jìn)公式

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

2.2改進(jìn)分析

2.2.1節(jié)點(diǎn)能量分析

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

2.2.2節(jié)點(diǎn)密度分析

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

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

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

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

表1　仿真參數(shù)

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

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

4　結(jié)束語(yǔ)

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

[1]李建中，高宏.無(wú)線傳感器網(wǎng)絡(luò)的研究進(jìn)展[J].計(jì)算機(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]秦相林，王瑋琦.基于延長(zhǎng)WSN生命周期的LEACH算法的改進(jìn)[J]．黑龍江科技信息，2015，15（1）:111-112.

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

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

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

[7]鄭波.基于改進(jìn)粒子群算法的無(wú)線傳感器能量?jī)?yōu)化[D].無(wú)錫：江南大學(xué)，2014.

[8]孫利民，葉馳，廖勇.傳感器網(wǎng)絡(luò)的路由機(jī)制[J].計(jì)算機(jī)科學(xué)，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ú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，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].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（17）:4158-4160.

[14]劉鐵流，巫詠群.基于能量?jī)?yōu)化的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法研究[J].傳感技術(shù)學(xué)報(bào)，2011，24（5）:764-770.

[15]王國(guó)芳，李臘元，李春林，等.無(wú)線傳感器網(wǎng)絡(luò)中基于能量約束的簇首多跳算法[J].傳感器技術(shù)學(xué)報(bào)，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稿件編號(hào)：201511114

國(guó)家自然科學(xué)基金資助項(xiàng)目(6130320)；浙江省新苗計(jì)劃項(xiàng)目(2013R424016)

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