無線傳感網中最大化生命的延遲優化算法

陳　燕　李勝嵐　梁俊斌

(廣西大學計算機與電子信息學院　廣西 南寧 530004)

?

無線傳感網中最大化生命的延遲優化算法

陳燕李勝嵐梁俊斌

(廣西大學計算機與電子信息學院廣西 南寧 530004)

針對一些實時性要求比較高的應用場景，如地震監測、火警探測等，提出一種限定延遲的最大化網絡生命周期算法DCLB(Delay-ConstrainedandLoad-Balancedataaggregationalgorithm)。DCLB以一棵具有最小跳生成樹為基礎，在滿足限制樹高的前提下，迭代的轉移樹上負載最大節點的子孫到負載小的節點上去。實驗表明，與目前已有算法相比，DCLB算法具有更低的時間復雜度，能有效地減少延遲并延長樹的生命周期。

無線傳感器網絡數據收集最大化生命周期限定延遲

0　引　言

無線傳感器網絡WSN(WirelessSensorNetwork)是由大量微型傳感器節點自組織而成的網絡。傳感器節點隨機分布在某一監測區域，周期性地感知一定量的數據并以多跳的方式發送給Sink[1]。每個傳感器節點在通信時會消耗掉大量的能量，由于它們利用電池供電，能量有限并且通常是無法補充的[2]，因此WSN的壽命問題尤為突出。同時，在一些實時性要求比較高的應用中，要求延遲越小越好。因此，如何有效地延長網絡的生命周期和減少延遲是WSN兩個難點問題。

根據數據傳輸過程中節點對數據的不同處理，可將數據收集分為匯聚數據收集和非匯聚數據收集。在匯聚數據收集中節點將接收到的數據和自己感知的數據進行聚合[3]，其目的是去除數據冗余、減少節點的能耗。然而，在某些應用中存在一些非數值型數據(如視頻、圖像等)，這些數據很難進行聚合。當節點接受到這些數據時，需要將這些數據連同自己感知的數據全部發送出去，這也就是非匯聚數據收集。在非匯聚數據收集中，Sink周圍的節點需要轉發大量的數據，導致能量消耗很快，容易造成“熱區”[3]。因此，在非匯聚數據收集模式下，如何在滿足延遲的同時延長網絡生命周期是個難點，同時也是本文研究的重點。

本文針對非匯聚數據收集，提出一個有效的算法DCLB。DCLB通過對樹高的限定來滿足延遲要求，然后不斷減少負載最大節點的子孫數，均衡節點的能量。仿真實驗和理論分析表明，DCLB算法能有效地減少網絡的延遲同時延長網絡的生命周期。

1　相關工作

對基于樹的數據收集協議的研究，目前已出現大量的工作。根據WSN需要滿足的兩個不同的應用需求，可將這些工作分為以下兩類：

1) 最大化網絡生命周期的數據收集協議

在一棵樹中，節點的孩子數越多，節點在收集其孩子節點發送的數據時，就會消耗越多的能量。因此，現有很多工作都通過減少節點孩子數量來最大化網絡生命周期。

文獻[4]針對數據收集過程中數據能夠完全匯聚的情形，在初始階段構造一棵樹后，把樹上所有的節點劃分為瓶頸節點、次瓶頸節點以及富裕節點三個類型，然后對樹進行優化操作。它首先選擇一條任意邊加入樹中，產生一個包含瓶頸節點在內的圈。接著刪除該瓶頸節點在圈中的另一條邊，從而降低瓶頸節點的度，有效地延長了網絡生命周期。然而算法在設計上沒有考慮樹的高度，會產生數據收集延遲。文獻[5]是針對完全匯聚的數據收集模式，提出一個分布式k負載均衡樹算法。每個節點選擇當前孩子數和鄰居樹最少的節點作為父節點，從到達樹上每兩個非葉子節點孩子數的差值小于K。該算法能很好地延長樹的生命周期，到達樹上負載均衡。文獻[6]也是針對完全匯聚的數據收集模式，當一個失效的節點靠近Sink時，造成以該失效節點為根的子樹上的所有子孫傳來的數據丟失。針對這種情況提出一個基于聚合樹的分布式算法DEST。DEST選取具有較高的剩余能量的節點，安排它們位于Sink節點附近，達到減小剩余能量低的節點的負載來最大化網絡生命周期的目的。

文獻[7]針對非匯聚數據收集，提出一個基于樹的分布式數據收集算法MLT。MLT在初始化時分布式地使用Dijkstra算法構造一棵生成樹。然后計算樹中生命周期最小的節點，并與Sink中存儲的閾值比較，若低于閾值則優化該生命周期最小的節點，轉移其孩子節點到剩余能量高的節點上。MLT能夠有效地均衡網絡能耗。文獻[8]綜合考慮了數據發送成本和網絡生命周期，提出了一個高效的HEE算法。HEE首先計算每個節點到Sink距離，然后根據距離將每個節點劃分到不同的集合，距離值最大的是葉子節點。HEE從葉子節點開始自下而上的構造數據收集樹，并采用壓縮傳感的方式進行數據收集，從而減少發送成本。然后調整樹的結構，不斷地轉移孩子數最多的節點到孩子數少的節點上來延長網絡生命周期。MITT[9]也是針對非匯聚數據收集模式，把樹上的節點劃分為三個類型。算法首先構造一棵最小最大權生成樹。然后，根據各個不同類型節點的能量，賦予不同的子孫數。最后，迭代的轉移權值最大的節點子孫，使樹達到平衡。然而由于頻繁地更換樹結構，使得MITT的時間復雜度較高。RaSMaLai[10]采用與文獻[9]相似的轉換思想，即不斷地將樹上負載最大的節點的子孫轉移到負載小的節點上去。區別在于：RaSMaLai沒有劃分節點類型，而是先計算所有節點的負載，以及各個節點到達Sink的路徑負載。然后根據葉子節點的路徑負載之間的差值來判定是否是平衡樹。RaSMaLai算法的時間復雜度較其他算法更低。但是RaSMaLai沒有考慮延遲問題，不適用于延遲敏感的網絡。

2) 低能耗低延遲的數據收集協議

低能耗低延遲的數據收集協議主要研究如何在延遲限定下延長網絡生命周期的問題。文獻[11]首先構造一棵胖樹，然后通過半匹配的思想，得到一棵最短路徑的最大化生命周期樹。由于最短路徑樹具有較小的延遲，所以該方案在減小延遲下達到最大化生命周期。文獻[12]提出一個基于樹的延遲和能量意識方案TEDAS。該方案根據鏈路上預期的數據傳輸數(ETX)，先構造一棵ETX最小的生成樹。然后，在限定的延遲下不斷地調整樹的結構，減少負載最大節點的度，達到樹上節點的能量均衡。MILD[13]針對文獻[4]的延遲問題進行改進，首先在限定樹高的條件下構造一顆最小跳生成樹，然后對樹中瓶頸節點的邊進行優化。即每次在滿足樹高限定的前提下選擇一條能產生更低樹高的邊刪除。MILD不僅能夠滿足延遲需求還能做到節點負載均衡，但是MILD針對匯聚數據收集的。

DCBL是對RaSMaLai[10]進行改進。DCBL在限定的樹高下，不斷優化樹中負載最大的節點，從而達到負載均衡。

2　網絡模型和問題描述

2.1網絡模型

我們采用與文獻[10]類似的網絡模型：整個網絡被抽象為一個連通無向圖G=(V,E),V={v0,v1,…,vn}表示n傳感器節點的集合，v0代表Sink節點；E是G中邊的集合，若兩個節點vi、vj在數據路徑上直接進行通信則有邊(vi,vj)∈E。網絡具有如下性質：

a) 每個節點隨機部署后不再移動；

b) 每個節點有不同的初始能量且能量都是無法補充；

c)Sink部署后不再移動且能量充足。

為了簡化問題和便于討論，假設節點采用固定發射和接收功率，發射1bit數據需要的能量是eT，接收1bit數據需要的能量是eR[6]。我們假設能量消耗僅包含兩部分：發送數據和接受數據。

2.2相關定義

本文研究的是在非匯聚模式下的數據收集。樹上的每個節點將自身感知的數據和接收到的數據，全部發送給父節點。為了描述方便，我們首先給出以下定義：

定義1輪：Sink從所有節點收集完一次數據的過程。

定義2假設樹上每個節點周期性的產生kbit數據[6]，則一輪里節點vi的能量消耗C(vi)為：

C(vi)=f(vi)keR+(f(vi)+1)eT

(1)

其中，f(vi)是節點vi在樹上的孩子數量。

定義3節點的生命周期：節點vi在樹T中能存活的輪數。存活指節點vi的能量ei>0。節點vi在一棵樹中的生命周期可定義為:

(2)

定義4樹的生命周期:樹T中第一個節點死亡時,該節點存活的輪數。定義為:

L(T)=mini=0,…,n{T(vi)}

(3)

定義5節點vi的負載Zi為：

(4)

定義6節點的路徑負載：是在樹T中，沿著當前節點到v0的路徑上所有節點的最大負載。節點vi的路徑負載定義如下：

(5)

其中，當vi在樹T的第一層(Sink在第0層)時Wi=Zi。否則Wi=max{Zj|vj∈Ri}。Ri指在樹T中vi到v0的路徑。

定義8最優負載均衡樹T：所有均衡樹中負載最小的生成樹。若樹T是棵α-負載均衡樹，對于任何一顆β-負載均衡樹T’,滿足不等式α≤β恒成立。

定理1如果T0是一棵最優負載均衡樹，則對于任意Ti∈P，均有L(T0)≥L(Ti)成立。其中，P表示圖G中所構造的數據收集樹的集合。

2.3問題描述

在利用樹結構進行數據收集時，子孫多的節點會消耗更多的能量在接受和發送數據上，成為負載重的節點?？梢酝ㄟ^減少負載重節點的子孫數來延長它們的壽命，但是這會造成樹的高度增加，使得Sink需要花費很長的時間來收集全網的數據，最終導致網絡延遲的增大。在一些對延遲敏感的應用場景中，如何構造一棵最優樹，使得在減少延遲下同時最大化網絡生命周期是個難點。本文針對這一問題提出了一種在非匯聚模式下延遲限定的最大化網絡生命周期的方案。

3　算法DCLB的設計

3.1DCLB的基本思想

使一棵數據收集樹達到負載均衡，我們的做法是對這棵樹進行轉移操作，即轉移負載最大節點的子孫到負載小的節點上去，且每次轉移，都會為待轉移節點選擇能使節點轉移后樹的高度不變或者增加不超過限定的高度的新父節點。這一策略能夠有效地延長樹的生命周期且減少延遲。

DCLB首先構造一棵最小跳生成樹T，然后通過判斷樹上最大路徑負載的葉子節點和最小路徑負載的葉子節點之間負載的差值，來判定樹T是否是棵負載均衡樹。若滿足負載均衡，則直接返回樹T；否則對樹T進行優化操作：若T中負載最高的節點是vi、va是vi的孩子，從圖G中選擇一些合適的節點成為va可能的新父節點。然后對這些節點進一步優化，即選擇層次低的且負載小的節點成為va的新父節點，刪除va與舊父節點相連的邊，從而使得vi的孩子數減1，同時要求產生新的樹高不變或是增長不得超過樹高限定h。當無法繼續優化負載高的節點時算法結束并得到一棵滿足設定高度h的負載均衡樹。

為了便于理解，我們舉例來說明DCLB的思想。如圖1所示，其中(a)表示一棵未經任何處理的生成樹T’，圖中實線代表在樹T’中的邊，虛線代表樹T’在圖G中存在的邊，節點v0用0代替，各個節點旁邊的數字代表該節點的負載。這里，我們假設每個節點形成數據率為1，節點發送和接受數據所消耗的能量均為1。在(a)中，節點v2是最大負載節點，于是對v2的孩子v5進行轉移操作，v5在圖G中的鄰居有三個v4、v1和v3。若將v5轉移到v4上得到樹T1，此時v2的負載減小，但樹的高度有所增加；若將v5轉移到v1上得到樹T2，v2的負載減小，樹高不變。因此樹T2優于樹T1，但是此時樹T2并未達到負載均衡。我們的做法如(d)所示，在對v5進行轉移時，選擇v5的鄰居節點中負載小的且層次低的節點成為v5新的父節點，因此節點v3最適合，轉移后得到樹T3。樹T3在沒有增加樹高的情況下達到負載均衡。

圖1　樹的不同轉換方式

3.2算法DCLB的描述

FunctionTransit(T,x)

1.for(x在樹T上的每一個孩子節點a)

2.if(a.visited==0)

3.a.visited=1;

4.for(a在圖G中的每一個鄰居節點b)

5.if((Wa-Wb)>σ)

6. 將b記錄在集合P中;

7.end

8.end

9.if(P為空)

10.Transit(T,a);

11.else

12.Optimal(P,T);

13.end

14.else

15.Transit(T,a);

16.end

17.end

其中，設置變量visited是為了避免出現死循環，初始化時每個節點的visited值均為0。不等式(Wa-Wb)>σ是用來判斷b是否是a可能的新父節點。若b滿足條件，則表明b的負載較小，將b加到集合P中。當遍歷完a的所有鄰居節點后，P中記錄的是所有滿足條件的節點。接著定義函數Optimal(P,T)對P中的節點進行優化。具體描述如下所示：

函數Transit(T，x)運行時，對于x的每一個孩子節點a，得到a可能的新父節點集合P

1.if(P不為空)

2.AP中節點所在層次最小值;

3.BP中負載最小值;

4.end

5.for(P中每一個節點y)

6.if((y.h==A)&(Zy==B)

7.ya新的父節點;

8.h1樹的高度;

9.if(h1>h)

10.returnfalse;

11.end

12.temp=1;

13.break;

14.end

15.if((y.h==A)&(y.rt～=B))

16.ya新的父節點;

17.h1樹的高度;

18.if(h1>h)

19.returnfalse;

20.end

21.temp=1;

22.break;

23.end

24.end

25.if(temp==1)

26.break;

27.returntrue;

對P中節點進行優化就是為被轉移節點選擇合適的父節點，轉移時選擇層次低的且負載小的節點作為新父節點。這樣做的好處是節點轉移后產生較小的樹高，可以有效減小延遲；同時轉移到負載小的節點上去，可以均衡負載大的節點的能耗，延長樹的生命周期。故函數Optimal(P,T)首先計算出P中節點的最小層次和最小負載。第6行表示優先選擇層次低的負載小的節點成為a的新父節點，接著計算a轉移之后得到新樹的高度，若不滿足限定樹高，算法結束。其中，y.h指節點y在樹T上的層次，Zy指節點y的負載。定義變量temp是為了避免節點一直處在循環轉移中，temp的初始值為0；第15行表示若P中沒有同時滿足層次低和負載小的節點，此時，選擇層次低的節點作為a的新父節點。當優化成功，函數返回true。算法DCLB的詳細描述如下所示：

1. 采用dijkstra算法從Sink出發構造一棵最小跳生成樹T;

2.if(樹T的高度>h)returnfalse;end

3.hasv=1;

4.while(hasv==1)

5.hasv=0;

6.if(max{Wis}-min{Wis}???)returntrue;

7.end

8.fori=1:n

9. 計算每個節點的負載;

10.x最大負載節點；

11.Transit(T,x);

12.hasv=1;

13.end

14.end

3.3算法DCLB的時間復雜度

算法DCLB第1步是Dijkstra算法構造一棵最小跳生成樹T，需要O(n2)的時間。算法第4步-第12步是一個迭代的優化過程。其中算法第6步計算每個葉子節點的路徑負載，然后求出葉子節點最大負載和最小負載的差值，需要花費O(S)的時間。其中，S是樹T中葉子節點的個數。在算法第8步-第9步中要得出樹T中負載最大的節點，需要遍歷樹T中的每個節點，因此需要O(n)的時間。得出負載最大的節點后，就嘗試對這個節點執行轉移操作。在算法中，先對負載最大的節點的孩子進行轉移，若滿足轉移條件，則執行Optimal(P,T)函數，得到集合P需要O(q)的時間，其中，q是任意節點在圖G中最大鄰居數。選擇最合適的節點成為轉移節點的新父節點，轉移成功后，迭代結束，重新計算樹T上節點的負載。若轉移失敗，則嘗試執行對最大負載節點的子孫節點進行轉移操作。如果迭代無法對負載最大節點進行優化，算法結束。故算法第4步-第12步的時間復雜度為O(n2qc)，其中，c是任意節點的最大孩子數。

定理2算法DCLB的時間復雜度為O(n2qc)。

證明：通過以上分析，算法第1步的時間復雜度為O(n2)；算法第4步-第12步的時間復雜度為O(n2qc)。因此，整個算法的時間復雜度為O(n2qc)。

4　模擬實驗

本文采用MATLAB仿真工具對提出的算法進行了評估與分析，為了便于比較，我們的實驗場景與文獻[10]相似。假定在100×100平方米的正方形監測區域內，隨機部署100至400個傳感器節點。每個節點的初始能量在[0.5J,1J]之間隨機分布，節點的通信半徑為25米。eR=50nJ,eT=100nJ。節點的數據產生率為128bits/round。

我們主要是在2個場景下分別進行2組實驗。其中，場景1 是Sink節點位于區域的中心,坐標(50 ,50)。第1組實驗主要驗證DCLB算法的生命周期；第2組實驗主要驗證DCLB算法的延遲，通過對樹的高度進行驗證。場景2是Sink節點位于區域的邊緣,坐標(100,50)。場景2的2組實驗與場景1相同。

由于文獻[10]已經分析了樹的生命周期受到葉子節點路徑負載之間允許最大差值σ的影響，因此我們設置σ的值同文獻[4]相同，即場景1中σ為5，場景2中σ為12。

如圖2(a)描述了網絡節點數對樹的生命周期的影響。隨著節點個數的增加，兩種算法樹的生命周期都有明顯下降。然而無論節點數如何，DCLB的樹生命周期均高于RaSMaLai，這是因為RaSMaLai在為負載大節點的子孫選取新的父節點時，沒有考慮可選新父節點的當前能量。當轉移操作成功后，這些新父節點的子孫數增多，過早的消耗完自身能量，降低了樹的生命周期。圖2(b)表示網絡節點數對樹的高度的影響。當網絡密度大時，兩種算法樹的高度都有所降低。這是因為當網絡中節點數增多時，可選路徑也相應增多，導致樹高降低。在網絡中節點數相同時，DCLB算法得到的樹高低于RaSMaLai。這是因為DCLB在轉移負載最大節點的子孫時，每次為待轉移節點選取所在層次低的節點為新父節點。這樣，節點在轉移后，不會產生比原來更高的樹高，故DCLB的延遲比RaSMaLai小。

在圖2(c)中，當網絡節點數為100時，DCLB的樹生命周期為1773輪，比(a)下降了48%；RaSMaLai為1242輪，比(a)下降了40%。造成這種現象的原因是當Sink位于網絡邊緣時，Sink的一跳鄰居數減少，致使這些少量的節點需承受更多子孫節點發送來的數據而過早耗盡能量。但是總體上，DCLB的樹生命周期仍然高于RaSMaLai。從圖2(d)可以看出，兩個算法樹的高度均比(b)高。但是在所有網絡密度下，DCLB的樹高均低于RaSMaLai，即DCLB能取得比RaSMaLai更小的延遲。

圖2　兩個場景中的對比

5　結　語

針對實時性要求高的場景，本文同時考慮了負載均衡和延遲兩個因素，提出了一種新的算法DCLB。DCLB算法在調整樹的結構同時，不斷為待轉移節點選擇合適的新父節點，從而得到一棵具有較小延遲的負載均衡樹。實驗結果表明，該算法與現有研究相比，在樹的生命周期和樹的收集延遲兩方面都更有優勢。

[1] 馬祖長,孫怡寧,梅濤.無線傳感器網絡綜述[J].通信學報,2004,25(4):114-124.

[2] 蔚趙春,周水庚,關佶紅.無線傳感器網絡中數據存儲與訪問研究進展[J].電子學報,2008,36(10):2001-2010.

[3] 梁俊斌,王建新,李陶深,等.傳感器網絡中基于樹的最大生命精確數據收集[J].軟件學報,2010,21(9):2289-2303.

[4]WuYan,SoniaFahmy,NessBshroff.OntheConstructionofaMaximum-LifetimeDataGatheringTreeinSensorNetworks:NP-CompletenessandApproximationAlgorithm[C]//IEEEINFOCOM,2008:356-360.

[5]HuangChungkuo,ChangGueyyun,SheuJangping.Load-BalancedTreesforDataCollectioninWirelessSensorNetworks[C]//41stInternationalConferenceonParallelProcessingWorkshops,2012:474-479.

[6]ChenJenyeu,JuanDawei,HuangChengsen.DEST:DistributedEndurantSpanningTreeforDataAggregationonWirelessSensorNetworks[C]//WirelessCommunicationsandApplications(ICWCA),2012:1-6.

[7] 李碩,樊建席,王成,等.一種新型無線傳感器網絡數據收集生成樹[J].小型微型計算機系統,2012,33(6):1238-1241.

[8]ChenXi,HeChen,JiangLingge.TheTradeoffbetweenTransmissionCostandNetworkLifetimeofDataGatheringTreeinWirelessSensorNetworks[C]//Communications(ICC)IEEEInternationalConferenceon,2013:1790-1794.

[9]LiangJunbin,WangJianxin,CaoJiannong,etal.AnEfficientAlgorithmforConstructingMaximumlifetimeTreeforDataGatheringWithoutAggregationinWirelessSensorNetworks[C]//IEEEINFOCOM,2010:1-5.

[10]ImonSKA,KhanA,DiFrancescoM,etal.RaSMaLai:ARandomizedSwitchingAlgorithmforMaximizingLifetimeinTree-basedWirelessSensorNetworks[C]//IEEEINFOCOM,2013:2913-2921.

[11]LuoDijun,ZhuXiaojun,WuXiaobing,etal.MaximizingLifetimefortheShortestPathAggregationTreeinWirelessSensorNetworks[C]//IEEEINFOCOM,2011:1566-1574.

[12]ShenYueyun,LiYanjun,ZhuYihua.ConstructingDataGatheringTreetoMaximizetheLifetimeofUnreliableWirelessSensorNetworkunderDelayConstraint[C]//WirelessCommunicationsandMobileComputingConference(IWCMC),2012:100-105.

[13] 梁俊斌,王建新,陳建二.在傳感器網絡中構造延遲限定的最大化生命周期樹[J].電子學報,2010,38(2):345-351.

DELAYOPTIMISATIONALGORITHMOFMAXIMISEDLIFETIMEINWIRELESSSENSORNETWORKS

ChenYanLiShenglanLiangJunbin

(School of Computer and Electronic Information,Guangxi University,Nanning 530004,Guangxi,China)

Thispaperproposesamaximisednetworklifecyclealgorithmwithconstraineddelay,namedDCLB,forsomeoftheappliedscenarioswithhigherreal-timedemand,suchasseismicmonitoring,firedetection,etc.DCLBisbasedonaminimumjumpspanningtree,andonthepremiseofmeetingthelimitedtreeheight,DCLBcontinuestotransferdescendantsofhigh-loadnodestolow-loadnodes.Experimentalresultsshowthatcomparedwithexistingalgorithms,DCLBhasalowertimecomplexity,whichcaneffectivelyreducethedelayandextendthelifecycleofthetree.

WirelesssensornetworksDatagatheringMaximisedlifecycleDelayconstrained

2014-09-12。國家自然科學基金項目(61103245)；廣西自然科學基金項目(2012GXNSFBA053163)。陳燕，教授，主研領域：網絡優化算法。李勝嵐，碩士生。梁俊斌，副教授。

TP301

ADOI:10.3969/j.issn.1000-386x.2016.03.030