一種非均勻部署傳感網的能量空洞緩解方法

陳 歡,沙 超,2,黃海平,王汝傳

(1.南京郵電大學 計算機學院，江蘇 南京 210003; 2.蘇州大學 江蘇省計算機信息處理技術重點實驗室,江蘇 蘇州 215006)

一種非均勻部署傳感網的能量空洞緩解方法

陳 歡1,沙 超1,2,黃海平1,王汝傳1

(1.南京郵電大學 計算機學院，江蘇 南京 210003; 2.蘇州大學 江蘇省計算機信息處理技術重點實驗室,江蘇 蘇州 215006)

在無線傳感網中，網絡中心附近的節點由于要負責全網數據的接收和轉發，將會消耗更多能量，從而造成節點間能耗不均，產生“能量空洞問題”。為延長簇樹狀無線傳感網的網絡生命期并均衡網內各節點能耗，提出了一種面向圓形傳感器網絡的能量空洞緩解方法。該方法將網絡劃分為虛擬的環狀結構以滿足多跳數據傳輸的要求，感知節點非均勻地分布在該圓形網絡中，內環中的節點數總是多于外環，以確保數據上傳過程中的能耗均衡性，各節點根據其鄰近節點的剩余能量和通信距離，選擇相鄰環內的最優節點作為父節點上傳數據。仿真實驗結果表明，與其他典型的能量空洞避免方法相比，所提出的方法有效延長了網絡生命期，在多跳傳感網中較好地實現了能耗均衡，有效地緩解了能量空洞的產生。

無線傳感網;能量空洞;能耗均衡;非均勻部署

0 引 言

近年來，無線傳感器網絡(Wireless Sensor Networks,WSNs)成為研究熱點[1-3]。并且許多配備了無線傳感器網絡的消費產品已被部署在家庭網絡之中[4-5]。使用環形拓撲均勻分布節點的無線傳感器網絡通常是由一組傳感器節點和一個sink節點組成的，采用多對一的數據收集模式[6]。

然而，越靠近sink的節點攜帶越多的流量負載，導致更多的能量消耗。由于節點能量的有限供應，因此靠近sink布置的節點將比遠離sink布置的節點更快地耗盡自身能量。節點能量的不平衡消耗將會在sink周圍引起能量空洞(Energy Hole)現象[7-8]。能量空洞現象是指網絡中由于部分節點過早耗盡自身能量導致網絡原有覆蓋區域缺失或者數據無法送達sink的現象[9]。在能量空洞問題產生后，將會不再有數據發送給sink，從而使得網絡的生命周期過早結束。然而當分布在sink第一半徑范圍內的節點耗盡了自身能量時，那些遠離sink的節點大部分初始能量還沒有被使用。Lian等[10]指出，無線傳感器網絡的生命周期在提前結束時，大約有90%的初始能量還沒有被使用。因此上述的能量空洞問題在無線傳感器網絡中已經成為最顯著的問題之一[11-12]。

文獻[13]認為，在負載量大的節點周圍布置更多數量的節點可以減輕節點的負載量，從而緩解能量空洞的出現。與這個思路相同的是，吳小兵等[14]證明了無線傳感器網絡的能量均衡耗盡的不可能性，并提出了“次優網絡能耗均衡”(Sub-balanced Energy Depletion)的概念，提出了一種非均勻的節點分布策略，用于實現網絡中的次平衡能量消耗，即從外環CR-1到內環C1中的節點數量按照比率為q>1的幾何級增長，并且在最外環CR中有NR-1/(q-1)個節點，從而實現了網絡的次平衡能量消耗。其中，R為總環數，Ni為環Ci中的節點數。然而在此策略中，節點在相鄰環中選擇數據傳輸方式時，未定義明確的標準，且環間節點選擇具有隨機性，使得節點消耗不平衡，仍會造成能量空洞的出現。

在文獻[14]的基礎上，利用功率自適應機制，對節點的傳輸半徑進行動態調節，以降低其多跳通信的能耗開銷。同時，設計實現了環間節點協同數據上傳方案，降低了簇樹狀傳感網“多對一”數據上傳過程中出現“近中心負載過高”現象的可能性，有效緩解了能量空洞問題。實驗結果表明，網絡運行結束后，各節點剩余能量均小于自身初始能量的8%，體現出了較好的能耗均衡性，且節點剩余能量的下降速度小于所對比的網絡模型，網絡生命期得到了有效延長。

1 網絡模型描述

1.1 節點能耗模型

不失一般性，采用同文獻[15]相同的節點能耗模型。節點發送數據時，其功率損耗如式(1)所示：

Etx(k,d)=kEelec+kεampd2

(1)

在接收數據時，節點功率損耗如式(2)所示：

Erx(k)=kEelec

(2)

其中，Etx、Erx分別為發送、接收數據損耗的功率；k為數據比特數；d為接收端和發射端之間的通信距離；Eelec為發送或接收單位比特數據電路損耗的功耗系數；εamp為功率放大電路的放大系數。

由式(1)和式(2)可知，一個節點發送單位比特的數據量所耗費的能量要大于接收單位比特的數據量。這主要是由于發射數據損耗功率是與發射端和接收端的距離有直接關系的。而且在通信距離較大時，Etx隨d的變化會產生巨增。若此時采用單跳直接傳輸數據的策略，反而會增加節點的能量消耗，而采用多跳數據上傳方案則可將負載均衡到網絡中其他節點，有利于均衡能耗，推遲能量空洞現象的產生。因此，重點針對多跳傳輸下的簇樹狀無線傳感網的能量效率問題進行研究。

1.2 網絡模型

假設網絡中所有的節點分布在一個半徑為R的圓形區域中。網絡中只有唯一的sink節點，且置于圓心處。令網絡中有n個感知節點，定義其標號為Aj(j=1,2,…,n)。該圓形區域使用以sink為原點的直角坐標系，故以A0(0,0)表示sink的位置。為便于選擇最優父節點，進一步將網絡劃分為N(N>1)個寬度均為dw的虛擬環狀區域，從內環向外環依次使用Ci(i=1,2,…,N)表示第i個圓環。節點在各環中均勻部署[14]。

由文獻[14]可知，圓環CN-1到圓環C1內的節點數目以等比系數q(q>1)遞增。而圓環CN和CN-1中的節點數目之比為1/(q-1)，即:

(3)

令所有節點一經部署后便不能移動，其初始能量均為E0且無法進行后續補充。

1.3 相關定義

定義1：最大通信傳輸距離dx。

處于圓環Ci(2

(a)最大通信傳輸距離dx (b)節點的最大考察區域

由定義1及圖1(a)易知：

(4)

而處于圓環Ci(i<2)內的節點的最大通信傳輸距離dx，即為其與sink的最短距離。

(5)

定義2：節點最大考察區域B。

以處于圓環Ci(1

定義3：P代價。

P代價是處于圓環Ci(1

(6)

其中，djk表示節點Aj與考察區域B內的節點Ak的距離；Ck表示節點Ak被選擇為后繼節點的次數；α和β是常量，滿足α+β=1。

令節點工作一輪的時間單位為一個時間片T，節點在每個時間片內分為三個階段：數據采集階段、數據發送階段和數據接收階段，其持續時間分別為t1、t2和t3。網絡中每個處于工作狀態的節點以相同的數據采集率采集數據，并在這個時間片內進行發送或者接收其他節點數據的工作。處于圓環Ci(i

2 環間數據上傳模式

2.1 最優父節點選擇方法

節點分布策略采用文獻[14]的非均勻分布方案，其基本思想是在靠近sink的圓環布置較多的節點。因此對于某一圓環在其相鄰內環選擇一個節點傳輸數據顯得尤為重要。這里，給出節點選擇其最優下一跳父節點的方法。

(1)網絡中的各節點，根據1.3節的定義，構建其各自的最大考察區域。由于已令各環的寬度均相等，故該最大考察區域B的面積將主要取決于節點在環中的位置及環的寬度值dw。在節點部署密度ρ一定的情況下，該面積大小將直接決定可供選擇的下一跳父節點個數。

(2)位于最外環中的節點，對于其所構建的B區域中的各節點，分別根據式(6)計算其P值，并從中選取P值最大的一個節點作為其下一跳父節點，向其發送一個包含自身ID和位置信息的消息包。

(3)若當前節點的B區域中無可供選擇的父節點，則其選擇距離其最近的一個同層節點，作為其父節點。

(4)當最外層節點均完成父節點的選擇后，位于次外環的各節點按照上述方式，從第N-2環中(或從與其位于同一環的兄弟節點中)選擇P值最大的節點，作為其父節點，并以此類推，最終構建一個以網絡中心sink為根，以虛擬圓環和B區域為約束條件的簇樹狀數據收集結構。

2.2 緩解能量空洞的環間數據上傳策略

如前所述，在簇樹狀無線傳感網中，若對于數據上傳時機不加限制，則很容易造成信道沖突、加重“近網絡中心”的負載，降低數據收集效率且產生能量空洞。為此，在2.1節所選取的最優父節點基礎上，進一步給出提升能耗均衡性的環間數據上傳策略。

在時間片開始后，各虛擬圓環內的節點首先都以相同的數據采集率在t1時間內采集數據。數據采集結束后，位于圓環Ci(i=N,N-2,N-4…)內的各節點首先向其父節點發送數據，持續時間為t2，如圖2(a)所示。此時，位于第Ci-1環內的節點將存在兩種可能：

(1)若該節點存在子節點，則其將進入接收模式，等待來自于其Ci環中子節點的數據。

(2)若該節點無子節點，則其將處于休眠狀態，以節約能量。

在t2時間片結束后，由位于圓環Ci-1內的節點向其父節點發送數據，此時，位于圓環Ci-2內的父節點將處于接收狀態。若該父節點無子節點，則處于休眠狀態以節約能量，如圖2(b)所示。

(a)Ci環節點向父節點發數據 (b)Ci-1環節點向父節點發數據

3 實驗及結果分析

為驗證算法性能，在Matlab2013中進行實驗，參數如表1所示。

表1 仿真參數值

不失一般性，這里認為，當網絡中出現第一個死亡節點時，網絡便停止運行。在網絡生命期、各節點剩余能量方差、網內節點剩余能量綜合等三方面，同文獻[14]中提出的環狀網絡節點非均勻分布下的能量空洞避免方法進行比較。能耗分析采用文獻[15]中所提出的傳感網能量消耗模型。

當網絡生命期結束時，網內各節點剩余能量如圖3所示。所采用的圓形網絡中非均勻部署了50個節點。

圖3 網絡中節點剩余能量

由圖3可知，在網絡停止運行時，各節點的剩余能量都未超過1.5 J，即各節點剩余能量均小于自身初始能量的8%，體現了較好的能耗均衡性。

表2為在環內部署不同數量節點后的節點剩余能量標準差、網絡生命期和數據吞吐量。

表2 不同部署情況下節點的能量效率比較

由表2可知，采用的方法對于不同部署模式下的適應性較強，其能耗均衡性和網絡生命期的實驗效果均較好。而在NumN=10，q=1.3這個方案部署下，網絡的能效性能最好，可最大限度地緩解能量空洞現象的產生。

圖4為所提出的非均勻部署網絡下的能量空洞緩解方法(Energy Hole Mitigation Strategy for non-uniform deployed sensor networks，EHMS)同節點非均勻分布的能量空洞避免方法(Avoiding Energy Holes in sensor networks with non-uniform node distribution，AEH)[14]在節點剩余能量之和方面的實驗結果。

圖4 節點剩余能量之和的變化比較

由圖4可知，在網絡運行時間內，由于EHMS方法中的各節點均在t1、t2和t3時間段內均衡地消耗能量，故其剩余能量總和隨著網絡的運行，基本呈線性下降的趨勢。AEH方法也采用環狀的非均勻部署方式，以均衡網絡能耗，故在網絡運行前期，其網內節點剩余能量的下降趨勢和EHMS方法基本一致。但其僅考慮到了相鄰圓環間的節點分布情況，未能夠進一步對父節點的選擇做出必要約束。節點每次僅選擇剩余能量最多的節點作為其下一跳父節點，未考慮跳距和環數的影響。故在網路運行后期，其網內節點剩余能量之和略低于EHMS方法。而在1 600～1 800 s之間，AEH方法的節點剩余能量總和未發生變化，說明此時該網絡已經停止工作。即EHMS方法的網絡生命期相對較長。

圖5是節點剩余能量方差隨網絡運行時間變化的比較曲線。

圖5 節點剩余能量方差的變化比較

由圖5可知，在網絡運行初期，兩種方法的節點剩余能量方差均較小，體現出了較好的能耗均衡性。然而，隨著網絡的運行，盡管兩種方法下的方差均可有效地控制在0.35 J2以內，但EHMS方法的能耗均衡性相對更好一些。這是由于該方法采用了環間數據交替上傳的策略，在避免傳輸沖突的同時，有效保存了環內各節點的能量，可進一步推遲能量空洞的產生。

4 結束語

以緩解能量空洞出現為目標，在非均勻部署的無線傳感網中，提出了一種選擇最優父節點開展層間數據上傳的方案。同時考慮到了后繼父節點的剩余能量、相鄰層間節點的通信距離及環內節點密度等因素。與典型的非均勻無線傳感網數據收集方式相比，該方案在實現能耗均衡性的同時，較為有效地緩解了能量空洞的產生，延長了網絡生命期。

[1] 劉 唐,彭 艦,陳 果,等.基于密度控制的傳感器網絡能量空洞避免策略[J].計算機學報,2016,39(5):993-1006.

[2] 張 樂,李 棟,崔 莉.一種針對移動全覆蓋問題的節點移動策略[J].計算機研究與發展,2013,50(5):901-911.

[3] 田賢忠,陽 勝.基于網絡編碼的無線傳感器網絡瓶頸區域生存時間優化策略[J].計算機學報,2016,39(5):1039-1050.

[4] Wang J,Yin Y,Zhang J,et al.Mobility based energy efficient and multi-sink algorithms for consumer home networks[J].IEEE Transactions on Consumer Electronics,2013,59(1):77-84.

[5] Bellido-Outeirino F J,Flores-Arias J M,Linan-Reyes M,et al.Wireless sensor network and stochastic models for household power management[J].IEEE Transactions on Consumer Electronics,2013,59(3):483-491.

[6] 夏先進,李士寧,張 羽,等.一維傳感網中混合數據傳輸的能量均衡[J].軟件學報,2015,26(8):1983-2006.

[7] 唐冰清,張玲華.GEAR協議中貪婪算法及查詢消息傳播優化方法[J].計算機技術與發展,2013,23(1):135-138.

[8] 曾志文,陳志剛,劉安豐.無線傳感器網絡中基于可調發射功率的能量空洞避免[J].計算機學報,2010,33(1):12-22.

[9] 李繼樓,柯家龍.基于壓縮感知的WSN數據壓縮與重構[J].計算機技術與發展,2015,25(9):111-114.

[10] Lian J,Naik K,Agnew G B.Data capacity improvement of wireless sensor networks using non-uniform sensor distribution[J].International Journal of Distributed Sensor Networks,2006,2(2):121-145.

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

[12] 張 琪,管有慶.基于網絡編碼的無線傳感網絡自適應數據聚集[J].計算機技術與發展,2015,25(10):123-126.

[13] Ferng H W,Hadiputro M S,Kurniawan A.Design of novel node distribution strategies in corona-based wireless sensor networks[J].IEEE Transactions on Mobile Computing,2011,10(9):1297-1311.

[14] Wu X,Chen G,Das S K.Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(5):710-720.

[15] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C]//Proceedings of the 33rd annual Hawaii international conference on system sciences.[s.l.]:IEEE,2000:1-10.

A Type of Energy Hole Mitigation Strategy for Non-uniform Deployed Sensor Networks

CHEN Huan1,SHA Chao1,2,HUANG Hai-ping1,WANG Ru-chuan1

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.Key Laboratory for Computer Information Processing Technology of Jiangsu Province, Soochow University,Suzhou 215006,China)

In Wireless Sensor Networks (WSN),nodes near the center tend to consume more energy as they are responsible for receiving and forwarding data from the whole network,which leads to a non-uniform energy consumption among nodes,that is so called the “energy hole problem”.To prolong network lifetime and balance energy consumption in the cluster-tree based sensor network,a type of energy hole mitigation strategy in a circular network has been proposed.Network has been divided into several virtual annuluses for multi-hop transmission and nodes have been non-uniformly deployed in it.Moreover,for balancing energy consumption on data uploading,the number of nodes in the inner annulus is more than that in the outer one.According to the residual energy and the communication distance of its neighbor,each node has chosen an optimal parent in the adjacent annulus for data uploading.Simulation results have shown that this method could effectively prolong network lifetime by comparing with other energy hole avoidance algorithms and has also performed well on balancing energy consumption in the multi-hop transmission network and could effectively mitigate the energy hole problem.

wireless sensor networks;energy hole;balance of energy consumption;non-uniform deployment

2016-07-05

2016-10-13 網絡出版時間：2017-04-28

國家自然科學基金資助項目(61572260)；江蘇省自然科學優秀青年基金(BK20160089)；江蘇省普通高校研究生培養創新工程(SJLX15_0382,SJLX15_0383,KYLX15_0842)；江蘇省計算機信息處理技術重點實驗室開放課題(KJS1327)

陳 歡(1991-)，男，碩士研究生，研究方向為無線傳感網能量空洞緩解技術；沙 超，副教授，碩士生導師，通信作者，研究方向為無線傳感網能耗均衡技術；黃海平，教授，碩士生導師，研究方向為物聯網隱私保護技術；王汝傳，教授，博士生導師，研究方向為物聯網信息處理技術。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.042.html

TP393

A

1673-629X(2017)06-022-05

10.3969/j.issn.1673-629X.2017.06.05