孫增友，周　池

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

?

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

孫增友，周池

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

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

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

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

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

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

1.1WSN系統(tǒng)模型

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

1.2能耗模型

本文采用文獻[4]的能耗模型，當發(fā)送和接收lbit數(shù)據(jù)時，能耗公式如下：

(1)

(2)

Etotal=Etx+Erx，

(3)

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

2分簇路由算法

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

(4)

(5)

因此，可計算一個簇的總能耗為：

(6)

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

(7)

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

(8)

(9)

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

(10)

則式(8)即：

(11)

得

(12)

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

(13)

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

2.2簇首選取

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

(14)

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

f=f1×f2，

(15)

(16)

(17)

(18)

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

(19)

3實驗與性能分析

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

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

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

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

3.2結(jié)果分析

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

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

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

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

4結(jié)論

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

參考文獻

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

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

[3]過文亮，施惠昌，周一飛.一種新型的自適應(yīng)最佳簇首分簇算法[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ǎng)絡(luò)分簇算法[J].華中科技大學學報(自然科學版)，2012，6(40):29-33.

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

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

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

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

[10] 胡君，王雷，林亞平.傳感器網(wǎng)絡(luò)中一種基于節(jié)點平均能耗的分布式簇頭選取算法[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

中圖分類號：TP212.9

文獻標識碼：A

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

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

收稿日期：2015-06-05