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

謝琳

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

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

謝琳

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

無線傳感器網絡；能量空洞；雙Sink；非均勻成簇

0　引言

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

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

1　網絡與能耗模型

1.1雙 Sink 無線傳感器網絡模型

在本文中，對網絡模型做出以下假設：

（1）網絡位于一個A×A的方形區域內，A默認值為300m；

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

（3）N個傳感器節點在網絡范圍內隨機分布，并且，傳感器節點在部署后不再移動；

（4）網絡內各個傳感器節點具有相同的初始能量Einit，傳感器節點的無線發射功率可調，即節點可以根據接收者的距離來調整其發射功率；

（5）網絡內節點非均勻成簇，簇頭在數據融合處理后，負責傳輸到Sink；

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

網絡模型結構如圖1 所示。

圖1　網絡模型

1.2雙Sink的 最優位置計算

方形網絡均分為兩個等腰直角三角形，雙Sink的最優位置分別為兩個三角形的重心處。

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

圖2　Sink位置布局

該重心滿足以下三個性質：

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

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

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

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

1.3能量模型

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

其中， Eelec表示發送或接收1bit數據時的能量消耗，是發送1bit數據放大器的能量消耗。

2　成簇算法

2.1簇競爭半徑的計算

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

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

2.2 構建簇

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

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

圖3　簇頭生成過程

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

2.4數據轉發路由

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

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

3　實驗與仿真

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

表1　實驗參數

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

圖4　簇頭能耗總和

圖5　網絡生命周期

圖6　網絡剩余能量

4　結語

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

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

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

[3]劉安豐，任炬，徐娟，等.異構傳感器網絡能量空洞分析與避免研究[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]曾志文，陳志剛，劉安豐.無線傳感器網絡中基于可調發射功率的能量空洞避免[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]蔣暢江，石為人，唐賢倫.能量均衡的無線傳感器網絡非均勻分簇路由協議 [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-），女，黑龍江密山人，碩士研究生，研究方向為無線傳感器網絡

2015-11-19

2016-01-15

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

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.