謝琳

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065)

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

謝琳

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065)

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

0　引言

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

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

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

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

在本文中，對(duì)網(wǎng)絡(luò)模型做出以下假設(shè)：

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

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

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

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

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

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

網(wǎng)絡(luò)模型結(jié)構(gòu)如圖1 所示。

圖1　網(wǎng)絡(luò)模型

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

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

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

圖2　Sink位置布局

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

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

（2）重心和三角形3個(gè)頂點(diǎn)組成的3個(gè)三角形面積相等；

（3）重心到三角形3個(gè)頂點(diǎn)距離的平方和最小。

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

1.3能量模型

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

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

2　成簇算法

2.1簇競(jìng)爭(zhēng)半徑的計(jì)算

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

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

2.2 構(gòu)建簇

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

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

圖3　簇頭生成過程

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

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

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

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

3　實(shí)驗(yàn)與仿真

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

表1　實(shí)驗(yàn)參數(shù)

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

圖4　簇頭能耗總和

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

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

4　結(jié)語

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

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

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

[3]劉安豐，任炬，徐娟，等.異構(gòu)傳感器網(wǎng)絡(luò)能量空洞分析與避免研究[J].軟件學(xué)報(bào)，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)絡(luò)中基于可調(diào)發(fā)射功率的能量空洞避免[J].計(jì)算機(jī)學(xué)報(bào)，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)絡(luò)非均勻分簇路由協(xié)議 [J].軟件學(xué)報(bào)，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-），女，黑龍江密山人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)

2015-11-19

2016-01-15

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

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.