陳　燕　李勝嵐　梁俊斌

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

?

無線傳感網(wǎng)中最大化生命的延遲優(yōu)化算法

陳燕李勝嵐梁俊斌

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

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

無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集最大化生命周期限定延遲

0　引　言

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

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

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

1　相關(guān)工作

對基于樹的數(shù)據(jù)收集協(xié)議的研究，目前已出現(xiàn)大量的工作。根據(jù)WSN需要滿足的兩個不同的應(yīng)用需求，可將這些工作分為以下兩類：

1) 最大化網(wǎng)絡(luò)生命周期的數(shù)據(jù)收集協(xié)議

在一棵樹中，節(jié)點的孩子數(shù)越多，節(jié)點在收集其孩子節(jié)點發(fā)送的數(shù)據(jù)時，就會消耗越多的能量。因此，現(xiàn)有很多工作都通過減少節(jié)點孩子數(shù)量來最大化網(wǎng)絡(luò)生命周期。

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

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

2) 低能耗低延遲的數(shù)據(jù)收集協(xié)議

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

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

2　網(wǎng)絡(luò)模型和問題描述

2.1網(wǎng)絡(luò)模型

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

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

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

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

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

2.2相關(guān)定義

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

定義1輪：Sink從所有節(jié)點收集完一次數(shù)據(jù)的過程。

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

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

(1)

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

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

(2)

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

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

(3)

定義5節(jié)點vi的負載Zi為：

(4)

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

(5)

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

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

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

2.3問題描述

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

3　算法DCLB的設(shè)計

3.1DCLB的基本思想

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

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

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

圖1　樹的不同轉(zhuǎn)換方式

3.2算法DCLB的描述

FunctionTransit(T,x)

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

2.if(a.visited==0)

3.a.visited=1;

4.for(a在圖G中的每一個鄰居節(jié)點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

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

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

1.if(P不為空)

2.AP中節(jié)點所在層次最小值;

3.BP中負載最小值;

4.end

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

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

7.ya新的父節(jié)點;

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新的父節(jié)點;

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

1. 采用dijkstra算法從Sink出發(fā)構(gòu)造一棵最小跳生成樹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. 計算每個節(jié)點的負載;

10.x最大負載節(jié)點；

11.Transit(T,x);

12.hasv=1;

13.end

14.end

3.3算法DCLB的時間復(fù)雜度

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

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

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

4　模擬實驗

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

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

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

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

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

圖2　兩個場景中的對比

5　結(jié)　語

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

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

[2] 蔚趙春,周水庚,關(guān)佶紅.無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)存儲與訪問研究進展[J].電子學(xué)報,2008,36(10):2001-2010.

[3] 梁俊斌,王建新,李陶深,等.傳感器網(wǎng)絡(luò)中基于樹的最大生命精確數(shù)據(jù)收集[J].軟件學(xué)報,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] 李碩,樊建席,王成,等.一種新型無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集生成樹[J].小型微型計算機系統(tǒng),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] 梁俊斌,王建新,陳建二.在傳感器網(wǎng)絡(luò)中構(gòu)造延遲限定的最大化生命周期樹[J].電子學(xué)報,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。國家自然科學(xué)基金項目(61103245)；廣西自然科學(xué)基金項目(2012GXNSFBA053163)。陳燕，教授，主研領(lǐng)域：網(wǎng)絡(luò)優(yōu)化算法。李勝嵐，碩士生。梁俊斌，副教授。

TP301

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