陈　燕　李胜岚　梁俊斌

(广西大学计算机与电子信息学院　广西 南宁 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