謝琳

（四川大學計算機學院，成都　610065)

基于雙Sink非均勻成簇的無線傳感器網(wǎng)絡能量空洞避免策略

謝琳

（四川大學計算機學院，成都610065)

無線傳感器網(wǎng)絡；能量空洞；雙Sink；非均勻成簇

0　引言

近年來，無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）由于其良好的擴展性以及較強的抗毀性，已經(jīng)被廣泛應用[1]，如環(huán)境監(jiān)測、健康醫(yī)療、搶險救災、戰(zhàn)場監(jiān)視等領域[2]。WSN在眾多領域的廣泛應用給人們生活以及工業(yè)生產(chǎn)都帶來了極大的便利，然而傳感器節(jié)點的能量受限問題制約了WSN的發(fā)展。在網(wǎng)絡中，各個區(qū)域的傳感器節(jié)點通信負載不同，通信負載較大的區(qū)域的傳感器節(jié)點能量消耗更快，進而會過早的耗盡能量，成為死亡節(jié)點，導致網(wǎng)絡數(shù)據(jù)傳輸中斷，出現(xiàn)“能量空洞”現(xiàn)象[3]。研究表明，當網(wǎng)絡出現(xiàn)能量空洞時，網(wǎng)絡剩余能量為70%以上，大多數(shù)網(wǎng)絡甚至高達90%[4]。然而，當傳感器節(jié)點自身攜帶的電池能量耗盡時，以人工方式為其更換電池是不現(xiàn)實的。鑒于此，如何在有限能量的情況下提高能量利用率、避免能量空洞、延長網(wǎng)絡生命周期具有重要的研究價值和現(xiàn)實意義[5]。

本文針對無線傳感器網(wǎng)絡的能量空洞問題，提出一種雙Sink部署的節(jié)點非均勻成簇算法DS-EEUC。在無線傳感器網(wǎng)絡中部署兩個Sink，可以有效縮短傳感器節(jié)點與Sink之間的距離，有效降低節(jié)點在通信過程中的能量消耗，又能提高網(wǎng)絡可靠性。在成簇階段，采用非均勻成簇策略。其原理是根據(jù)簇頭與Sink距離的不同，調(diào)節(jié)簇的競爭半徑，以達到減緩簇頭能耗速率、延長網(wǎng)絡壽命的目的。算法的實現(xiàn)包括以下幾個方面：確定網(wǎng)絡中兩個Sink的最優(yōu)位置；在成簇階段，網(wǎng)絡內(nèi)每個節(jié)點根據(jù)剩余能量和與Sink相對距離決定是否成為簇頭或者成為某個簇中的成員；在數(shù)據(jù)傳輸階段，根據(jù)該簇頭與Sink的距離，簇頭作出判斷將融合后的數(shù)據(jù)通過最短路徑多跳傳輸?shù)骄嚯x較短的Sink。

1　網(wǎng)絡與能耗模型

1.1雙 Sink 無線傳感器網(wǎng)絡模型

在本文中，對網(wǎng)絡模型做出以下假設：

（1）網(wǎng)絡位于一個A×A的方形區(qū)域內(nèi)，A默認值為300m；

（2）網(wǎng)絡中存在兩個Sink，它們具有極強的計算和存儲能力、并且有充足的能量。Sink分別位于方形網(wǎng)絡中以對角線劃分的三角形的重心處，位置固定不變；

（3）N個傳感器節(jié)點在網(wǎng)絡范圍內(nèi)隨機分布，并且，傳感器節(jié)點在部署后不再移動；

（4）網(wǎng)絡內(nèi)各個傳感器節(jié)點具有相同的初始能量Einit，傳感器節(jié)點的無線發(fā)射功率可調(diào)，即節(jié)點可以根據(jù)接收者的距離來調(diào)整其發(fā)射功率；

（5）網(wǎng)絡內(nèi)節(jié)點非均勻成簇，簇頭在數(shù)據(jù)融合處理后，負責傳輸?shù)絊ink；

（6）鏈接是對稱的.如果傳輸功率已知，則節(jié)點可以根據(jù)接收到的信號的強度來計算距離。

網(wǎng)絡模型結構如圖1 所示。

圖1　網(wǎng)絡模型

1.2雙Sink的 最優(yōu)位置計算

方形網(wǎng)絡均分為兩個等腰直角三角形，雙Sink的最優(yōu)位置分別為兩個三角形的重心處。

如圖2 所示，△ABC中，做三條中線，相交于一點，該點叫做三角形的重心。

圖2　Sink位置布局

該重心滿足以下三個性質(zhì)：

（1）通過三條中線劃分得到的六個三角形面積相等；

（2）重心和三角形3個頂點組成的3個三角形面積相等；

（3）重心到三角形3個頂點距離的平方和最小。

綜上可得，若Sink放置在重心位置，一方面可以使Sink在網(wǎng)絡各方向均勻覆蓋；另一方面可以使網(wǎng)絡內(nèi)簇頭節(jié)點與其的數(shù)據(jù)傳輸距離整體上保持較短，提高網(wǎng)絡總的能量利用率。至此，確定兩個Sink在網(wǎng)絡中的位置。

1.3能量模型

本文使用能量消耗模型與文獻[3]相同，不考慮節(jié)點計算、存儲等過程的能耗，僅考慮節(jié)點數(shù)據(jù)通信的能耗。經(jīng)過距離d傳輸lbit信息，發(fā)送端能量消耗為：

其中， Eelec表示發(fā)送或接收1bit數(shù)據(jù)時的能量消耗，是發(fā)送1bit數(shù)據(jù)放大器的能量消耗。

2　成簇算法

2.1簇競爭半徑的計算

由于網(wǎng)絡采用節(jié)點隨機分布，節(jié)點密度近似均勻。所以在計算每個簇競爭半徑時，僅考慮簇頭與Sink距離即可，無需考慮節(jié)點密度因素。

公式3中，α為常數(shù)因子，dmax和dmin分別代表網(wǎng)絡中節(jié)點到Sink的最大距離和最小距離為最大競爭半徑，d（i，Sink1）為節(jié)點到Sink1的距離值，min[d（i，Sink1），d（i，Sink2）]是取節(jié)點i到Sink1和Sink2距離的最小值。根據(jù)公式可得，節(jié)點i在網(wǎng)絡中會選擇離自己較近的Sink發(fā)送數(shù)據(jù)，并且節(jié)點i的競爭半徑與其到Sink的距離呈線性正相關，即，節(jié)點i與Sink距離越近，其競爭半徑越小。則靠近Sink的簇頭，其在簇內(nèi)數(shù)據(jù)通信方面所消耗的能量會大幅降低，在有限的初始能量下，可以有更多的能量用于簇間的數(shù)據(jù)轉(zhuǎn)發(fā)，所以，網(wǎng)絡中不同區(qū)域簇頭的能耗得到平衡，可以有效延長網(wǎng)絡生命周期。

2.2 構建簇

本文根據(jù)剩余能量比率RRE（i）和競爭半徑比率RD（i）共同選舉簇頭，節(jié)點成為簇頭的概率計算既要考慮簇頭節(jié)點要擁有更多的剩余能量，也要考慮盡量減少簇內(nèi)的通信能耗。簇頭選擇過程如圖3 所示，簇頭選擇概率公式計算如下：

P為節(jié)點成為簇頭的概率值。RRE（i）表明節(jié)點i的鄰居節(jié)點的平均剩余能量與節(jié)點i的剩余能量之比。即表示節(jié)點i的所有鄰居節(jié)點的剩余能量的均值代表節(jié)點i自身的剩余能量。若RRE（i）＜1，則說明節(jié)點i的剩余能量大于其通信半徑內(nèi)節(jié)點的平均剩余能量，可加入候選簇頭集合；RD（i）表明候選簇頭i和其競爭半徑范圍內(nèi)所有節(jié)點距離的平均值與候選簇頭i競爭半徑的比重。即，

圖3　簇頭生成過程

確定簇頭后，普通節(jié)點j根據(jù)簇頭節(jié)點的剩余能量，以及j和各個簇頭之間的距離選擇簇加入。

2.4數(shù)據(jù)轉(zhuǎn)發(fā)路由

簇頭首先判斷其與兩個Sink的距離，選擇將數(shù)據(jù)傳輸給距離較短的Sink，公式如下：

其次，選擇中繼簇頭進行數(shù)據(jù)轉(zhuǎn)發(fā)。轉(zhuǎn)發(fā)概率的計算同時考慮節(jié)點剩余能量和與選定Sink的距離。轉(zhuǎn)發(fā)概率Q的計算如公式（6）所示為節(jié)點當前的剩為網(wǎng)絡中各個簇頭剩余能量的均值，maxd（i，Sink）為網(wǎng)絡中簇頭與Sink的最大距離，d（k，Sink）為該簇頭與Sink的距離。根據(jù)公式（7）可得，若該簇頭的剩余能量越高，與Sink距離越近，則其成為中繼簇頭的概率Q越高。

3　實驗與仿真

本文用C語言對DS-EEUC算法進行仿真實驗，將DS-EEUC、LEACH[6]、EEUC[7]算法做相關性能的對比，表1為實驗采用的多種參數(shù)。余能量

表1　實驗參數(shù)

在LEACH、EEUC、DS-EEUC算法中，隨機選取10輪，取每輪簇頭消耗能量之和，如圖4所示。圖中LEACH算法的簇頭能耗最大，由于它采用單跳傳輸方式，導致簇頭能耗過大；EEUC和DS-EEUC由于采用多跳通信方式，所以簇頭能耗較小，而DS-EEUC采用雙Sink，可以有效縮短簇頭到Sink的轉(zhuǎn)發(fā)路徑長度，使得本算法的簇頭能耗最低。圖5 為三種算法下的網(wǎng)絡生命周期對比，DS-EEUC算法有效地延長了網(wǎng)絡生命周期。圖6為三種算法下網(wǎng)絡剩余能量的比較，從圖中可以看出，DS-EEUC算法的網(wǎng)絡剩余能量曲線的斜率p均低于LEACH、EEUC算法。即本算法有效降低了每輪網(wǎng)絡的能量消耗。

圖4　簇頭能耗總和

圖5　網(wǎng)絡生命周期

圖6　網(wǎng)絡剩余能量

4　結語

本文通過建立雙Sink、非均勻成簇的網(wǎng)絡模型，提出DS-EEUC算法。通過實驗仿真情況可以得到，與LEACH、EEUC算法相比，DS-EEUC可以有效提高網(wǎng)絡能量利用率、延緩能量空洞的形成、延長了網(wǎng)絡生命周期。

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

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

[3]劉安豐，任炬，徐娟，等.異構傳感器網(wǎng)絡能量空洞分析與避免研究[J].軟件學報，2012，23（9）:2438-2448.

[4]Song C，Liu M，Cao J，et al.Maximizing Network Lifetime Based on Transmission Range Adjustment in Wireless Sensor Networks[J]. Computer Communications，2009，32（11）:1316-1325.

[5]曾志文，陳志剛，劉安豐.無線傳感器網(wǎng)絡中基于可調(diào)發(fā)射功率的能量空洞避免[J].計算機學報，2010，33（1）:12-22.

[6]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].Wireless Communications，IEEE Transactions on，2002，1（4）:660-670.

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

Wireless Sensor Networks;Energy Hole;Double Sink;Non-Uniform Clustering

Energy Hole Avoidance Strategy Based on Double Sink and Non-Uniform Clustering for Wireless Sensor Networks

XIE Lin
（College of Computer Science，Sichuan University，Chengdu 610065）

謝琳（1992-），女，黑龍江密山人，碩士研究生，研究方向為無線傳感器網(wǎng)絡

2015-11-19

2016-01-15

為了解決無線傳感器網(wǎng)絡的能量空洞問題，延長網(wǎng)絡生命周期，對能量空洞現(xiàn)象進行研究，建立雙Sink、節(jié)點隨機分布的方形網(wǎng)絡模型；通過分析確定Sink位置，優(yōu)化簇構建過程，提出層次路由算法。給出基于雙Sink非均勻成簇的無線傳感器網(wǎng)絡能量空洞避免算法DS-EEUC。仿真結果表明，該算法和LEACH、EEUC相比，在網(wǎng)絡壽命和能量利用率方面有顯著提高。

In order to solve the problem of energy hole in the wireless sensor networks,prolong the lifetime of network,studies the phenomenon of the energy hole,constructs the network model with double Sink,and nodes are randomly distributed.Determines the position of Sink by analysis,optimizes the process of cluster construction and proposes hierarchical routing algorithm.Proposes Energy Hole Avoidance Strategy Based on Double Sink and Non-uniform Clustering for Wireless Sensor Networks(DS-EEUC).The simulation results show that,compared with LEACH and EEUC,DS-EEUC improves the network lifetime and network energy efficiency.