基于能量和距離的WSN自適應(yīng)分簇算法

孫增友，周　池

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

?

基于能量和距離的WSN自適應(yīng)分簇算法

孫增友，周池

(東北電力大學(xué) 信息工程學(xué)院，吉林 吉林 132012)

摘要：無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的能量有限且難以補(bǔ)充，為了提高網(wǎng)絡(luò)節(jié)點(diǎn)的能量利用率，延長(zhǎng)網(wǎng)絡(luò)生命周期。在LEACH算法分簇結(jié)構(gòu)的不足的基礎(chǔ)上，提出一種自適應(yīng)的最優(yōu)簇首數(shù)計(jì)算方式，綜合考慮傳感器節(jié)點(diǎn)的能量及距離，對(duì)閾值公式T(n)進(jìn)行改進(jìn)。經(jīng)仿真實(shí)驗(yàn)分析，本文提出的算法較LEACH算法節(jié)點(diǎn)存活率更高，網(wǎng)絡(luò)生命周期顯著延長(zhǎng)。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；LEACH；分簇

為了最大化的延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Network ，WSN)的生命周期，學(xué)者們?cè)O(shè)計(jì)了多種層次路由協(xié)議以充分利用網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量[1-2]。

經(jīng)典LEACH 算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為多個(gè)簇，簇內(nèi)節(jié)點(diǎn)以相同的概率隨機(jī)地被選為簇首，在一定程度上，這種算法能防止某個(gè)節(jié)點(diǎn)損耗過(guò)高，均衡了網(wǎng)絡(luò)整體能耗。但該算法不能保證每輪的分簇?cái)?shù)量達(dá)到最佳。同時(shí)，由于簇首的選擇未考慮節(jié)點(diǎn)的能量和地理位置信息，簇首可能會(huì)集中分布于監(jiān)測(cè)區(qū)域的某一處，造成個(gè)別簇首覆蓋的監(jiān)測(cè)區(qū)域面積較大，負(fù)擔(dān)的成員節(jié)點(diǎn)數(shù)量較多，能量消耗較大而過(guò)早死亡。文獻(xiàn)[3]提出了一種新型的自適應(yīng)最佳分簇算法，選取能量較大的節(jié)點(diǎn)作為簇首，從而保護(hù)剩余能量少的節(jié)點(diǎn)，該算法在一定程度上提升了網(wǎng)絡(luò)性能，但是算法未考慮節(jié)點(diǎn)位置，小范圍區(qū)域內(nèi)可能當(dāng)選大量簇首，使簇首分布不均勻，易形成網(wǎng)絡(luò)空洞。因此，本文在考慮網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量和位置的基礎(chǔ)上，通過(guò)閾值T(n)的重新定義對(duì)LEACH協(xié)議的簇首選擇過(guò)程進(jìn)行優(yōu)化，實(shí)現(xiàn)網(wǎng)絡(luò)整體功耗的降低，從而提高網(wǎng)絡(luò)生命周期[3]。

1WSN系統(tǒng)模型和能量模型

1.1WSN系統(tǒng)模型

本文考慮簇首節(jié)點(diǎn)通過(guò)單跳轉(zhuǎn)發(fā)的方式與基站直接通信，采用文獻(xiàn)[3]的系統(tǒng)模型，用一個(gè)無(wú)向加權(quán)圖G表示其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)G={V，E}，V為傳感器網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合V={v1v2…vi…vn}。

1.2能耗模型

本文采用文獻(xiàn)[4]的能耗模型，當(dāng)發(fā)送和接收l(shuí)bit數(shù)據(jù)時(shí)，能耗公式如下：

(1)

(2)

Etotal=Etx+Erx，

(3)

其中，d為源節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離；n為信道衰減指數(shù)，取值范圍為[2,5]；εfs為單位放大功率；εmp為多徑衰落模型的單位放大功率；Eelec為發(fā)送或接收單位bit數(shù)據(jù)的能耗[4]。

2分簇路由算法

2.1確定最佳簇首數(shù)

(4)

(5)

因此，可計(jì)算一個(gè)簇的總能耗為：

(6)

推出整個(gè)網(wǎng)絡(luò)能耗為：

(7)

為了使網(wǎng)絡(luò)總能耗最小，則

(8)

(9)

dto-CH節(jié)點(diǎn)與簇頭的距離，為

(10)

則式(8)即：

(11)

得

(12)

由式(12)可知，最優(yōu)簇首數(shù)由網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)決定。然而，在實(shí)際的網(wǎng)絡(luò)運(yùn)行過(guò)程中，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)能量的耗盡，存活節(jié)點(diǎn)數(shù)在不斷減少，節(jié)點(diǎn)數(shù)目也在不斷變化，因此本文用當(dāng)前節(jié)點(diǎn)數(shù)代替網(wǎng)絡(luò)初始節(jié)點(diǎn)數(shù)，提出自適應(yīng)最優(yōu)簇首數(shù)計(jì)算公式，即：

(13)

通過(guò)能量消耗與節(jié)點(diǎn)位置求得的最優(yōu)簇頭數(shù)目，結(jié)合了網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的動(dòng)態(tài)變化過(guò)程，與leach原有的隨機(jī)簇首數(shù)相比，更有助于降低無(wú)線傳感器網(wǎng)絡(luò)的整體能耗。

2.2簇首選取

LEACH算法進(jìn)行簇首選取時(shí)，每輪開(kāi)始時(shí)節(jié)點(diǎn)產(chǎn)生一個(gè)[0，1]的隨機(jī)數(shù)，如果這個(gè)數(shù)小于閾值T(n)，節(jié)點(diǎn)當(dāng)選簇首[6]

(14)

但是，LEACH算法在選取簇首時(shí)未考慮節(jié)點(diǎn)能量及節(jié)點(diǎn)間距離等因素，一些能量較低的節(jié)點(diǎn)也有可能被選為簇首，容易導(dǎo)致該類節(jié)點(diǎn)負(fù)載過(guò)重而過(guò)早死亡[7-8]。文獻(xiàn)[2]提出的AOCH算法，把剩余能量最多的節(jié)點(diǎn)選為簇首，卻沒(méi)有考慮其到基站的距離。因此，本文在進(jìn)行簇首選擇時(shí)，綜合考慮節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)與基站的距離關(guān)系，構(gòu)造了一個(gè)調(diào)節(jié)函數(shù)f，使剩余能量較多且距離基站較近的節(jié)點(diǎn)優(yōu)先競(jìng)爭(zhēng)簇頭。

f=f1×f2，

(15)

(16)

(17)

(18)

改進(jìn)后的T(n)除了考慮當(dāng)前節(jié)點(diǎn)的剩余能量外，還考慮了節(jié)點(diǎn)與基站之間的距離，盡可能的選擇與基站距離較近的節(jié)點(diǎn)作為簇首。在單跳路由網(wǎng)絡(luò)中，即降低了傳輸延遲，也減少了簇首的發(fā)送能耗，不至于使其能耗開(kāi)銷過(guò)大。為了更進(jìn)一步約束被選節(jié)點(diǎn)的能量，我們定義簇首還需滿足下式[9-10]：

(19)

3實(shí)驗(yàn)與性能分析

3.1實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定

本實(shí)驗(yàn)是在Matlab環(huán)境下進(jìn)行仿真，100個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)均勻分布在100×100的方形監(jiān)測(cè)區(qū)域內(nèi)，基站位于監(jiān)測(cè)區(qū)域外，坐標(biāo)為(50，150)，如圖1。仿真參數(shù)設(shè)定如表1。

圖1　網(wǎng)絡(luò)節(jié)點(diǎn)分布

圖2　LEACH與本文算法簇首數(shù)量圖

3.2結(jié)果分析

我們首先選取了50輪內(nèi)LEACH和本文算法的簇首數(shù)量進(jìn)行比較，如圖2所示，本文算法簇首數(shù)波動(dòng)范圍較小，與LEACH算法相比，簇首數(shù)量更穩(wěn)定。因此，保證了網(wǎng)絡(luò)成簇?cái)?shù)量的均衡性，避免分簇?cái)?shù)量過(guò)多或過(guò)少而引起的能量波動(dòng)及能量分布不均勻現(xiàn)象。

圖3a為網(wǎng)絡(luò)節(jié)點(diǎn)存活數(shù)比較圖。隨著網(wǎng)絡(luò)運(yùn)行，節(jié)點(diǎn)能量不斷消耗，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)不斷減少。由圖可知，LEACH算法在運(yùn)行至500輪左右時(shí)最先開(kāi)始出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，文獻(xiàn)[2]提出的AOCH算法推遲了第一個(gè)節(jié)點(diǎn)死亡時(shí)間，而本文提出的算法在運(yùn)行至650輪左右時(shí)才出現(xiàn)，節(jié)點(diǎn)死亡時(shí)間明顯延遲。當(dāng)運(yùn)行到800輪時(shí)，LEACH算法的網(wǎng)絡(luò)節(jié)點(diǎn)幾乎全部死亡，而本文所采用的算法仍有12%左右的節(jié)點(diǎn)存活，節(jié)點(diǎn)存活時(shí)間明顯增加，有效的延長(zhǎng)了網(wǎng)絡(luò)生命周期。

為了進(jìn)一步對(duì)本文算法的效果進(jìn)行驗(yàn)證，圖3b對(duì)網(wǎng)絡(luò)總能耗進(jìn)行了仿真分析，如圖可知，隨著輪數(shù)的增長(zhǎng)，網(wǎng)絡(luò)能耗逐漸增加，從0-1200輪的時(shí)間中，任意輪的LEACH能耗最快，在800輪左右時(shí)，由于節(jié)點(diǎn)數(shù)量幾乎全部死亡，能量耗盡。AOCH算法考慮了節(jié)點(diǎn)剩余能耗，在一定程度上減少了網(wǎng)絡(luò)總體能耗，但是由于未考慮節(jié)點(diǎn)位置，因此較本文提出的算法耗能快。

圖3　a節(jié)點(diǎn)存活數(shù)，b總能量消耗

4結(jié)論

本文改進(jìn)了LEACH算法分簇時(shí)未考慮能量和節(jié)點(diǎn)位置信息的缺點(diǎn)，綜合考慮網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域的面積和節(jié)點(diǎn)數(shù)等因素，通過(guò)自適應(yīng)調(diào)整的方式確定最優(yōu)簇首數(shù)。在選舉簇首時(shí)，考慮存活節(jié)點(diǎn)的剩余能量和位置信息，通過(guò)函數(shù)f對(duì)簇首選擇閾值T(n)進(jìn)行調(diào)整。經(jīng)仿真驗(yàn)證，本文提出的新算法能有效提高節(jié)點(diǎn)存活率，延長(zhǎng)網(wǎng)絡(luò)生命周期。

參考文獻(xiàn)

[1]李建坡，鐘鑫鑫，徐純.無(wú)線傳感器網(wǎng)絡(luò)動(dòng)態(tài)節(jié)點(diǎn)定位算法綜述[J].東北電力大學(xué)學(xué)報(bào)，2015，35(1)：52-58.

[2]李建坡，鐘鑫鑫，徐純.無(wú)線傳感器網(wǎng)絡(luò)靜態(tài)節(jié)點(diǎn)定位算法綜述[J].東北電力大學(xué)學(xué)報(bào)，2015，35(2)：73-82.

[3]過(guò)文亮，施惠昌，周一飛.一種新型的自適應(yīng)最佳簇首分簇算法[J].微計(jì)算機(jī)信息，2009，25(2):183-184+201.

[4]Pratyay Kuila ，Prasanta KJana，Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence，2014 (33):127-140.

[5]廖鷹，齊歡，王曉紅等.基于距離和分布的無(wú)線傳感器網(wǎng)絡(luò)分簇算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，6(40):29-33.

[6]趙小敏，毛科技，王正莉等.基于能量和距離的分簇式WSN路由協(xié)議設(shè)計(jì)[J].解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，8(13):394-397.

[7]王林，趙紹英.無(wú)線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議的研究與改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(2):80-82.

[8]潘霞，于宏毅，張霞.一種基于LEACH的能耗均衡分君算法[J].電路與系統(tǒng)學(xué)報(bào)，2012，17(1)：75-80.

[9]張磊，陳曙.一個(gè)新的基于能量和距離的傳感器網(wǎng)絡(luò)協(xié)議[J].計(jì)算機(jī)應(yīng)用，2008，5(28):1117-1119.

[10] 胡君，王雷，林亞平.傳感器網(wǎng)絡(luò)中一種基于節(jié)點(diǎn)平均能耗的分布式簇頭選取算法[J].計(jì)算機(jī)應(yīng)用，2007，27(12)：2979-2981.

Adaptive Clustering Algorithm in WSN Based on Energy and Distance

SUN Zeng-you，ZHOU Chi

(School of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：The energy of nodes in wireless sensor networks is limited and it is difficult to add.In order to improve the energy utilization of the nodes，and prolonging the lifetime of the network..This paper for the shorts of cluster structure in LEACH algorithm，proposed a calculation of an adaptive optimal number of cluster heads，considering the sensor node energy and the distance for clustering.The threshold formula T(n) was improved.Through simulation experiments，the proposed algorithm is more than the LEACH algorithm in node survival rate，the lifetime of the network is significantly prolonged.

Key words：Wireless Sensor Network；LEACH；Cluster

中圖分類號(hào)：TP212.9

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1005-2992(2016)01-0082-05

作者簡(jiǎn)介：孫增友(1963-)，男，吉林省吉林市人，東北電力大學(xué)信息工程學(xué)院高級(jí)工程師，碩士生導(dǎo)師，主要研究方向：無(wú)線通信、電力系統(tǒng)通信.

收稿日期：2015-06-05