一种受时延约束的最大化生命周期数据收集算法

刘文彬（湖南财政经济学院信息管理系，湖南长沙410205）

一种受时延约束的最大化生命周期数据收集算法

刘文彬
（湖南财政经济学院信息管理系，湖南长沙410205）

在无线传感器网络中，构造一棵网络生命周期最大化、满足用户时延需求的数据收集树，是一个NP完全问题.提出一种新的启发式算法，该算法起始于Sink节点，然后每次将生命周期估计值最大、且其对应的节点满足用户延时需求的边加入到树中，直到所有的节点加入到树中为止.仿真实验表明：与现有算法相比，该算法在满足用户时延的需求下，能有效地延长树的生命周期.

无线传感器网络；生命周期；时延需求；数据收集

LiuWB.ADelay-Constrained Maximum-Lifetime Data Gathering Algorithm[J].Journal of Yibin University,2015,15 （6）：86-88.

无线传感器网络（WSNs）具有十分广阔的应用前景，包括在军事监视、森林火警监视、野外考察、地形探测或建筑监控等方面[1].这些应用的基本任务是收集从各个监控点采集到的信息，并最终传输给基站.但由于无线传感器节点体积微小、能量非常有限，通常运行在人无法接近的恶劣、甚至危险的远程环境中，通过更换电池的方式补充节点的能量是不现实的.此外，在一些诸如森林火警监视、战场监控等持续性的监视应用中，除了要求网络能保存能量长期地工作，还要求网络在收集到数据后能尽快地将数据传送给用户进行处理.因此，在WSNs中，如何在满足用户时延需求的情况下，提高能量的使用效率，从而延长网络寿命，已成为目前研究的热点之一.

目前，学界已提出了大量基于树结构的数据收集方法.有些算法以最小生成树算法为基础，开始时建立一棵只包括Sink节点的数据收集树，然后依次选择一条权值最小的边（边的一个节点在树上，另一个节点不在树）加入到树中，直到所有的传感器节点加入到树为止，如PEDAP算法[2]、PEDAP-PA算法[2]、MNL算法[3]、MLT算法[4]、ECRT算法[5]、MLDGA算法[6]等.还有一些算法初始于一棵任意的树，然后采取不同的方法或手段，不断地改进或改善树的生命周期，直到不能改进为止，如LOCAL_OPT算法[5]、MDST算法[5]、IAA算法[7-8]与文献［9］提出的算法等.

上述这些算法能做到生成树上节点负载均衡，树的生命周期达到近似最优.但是，树的高度无法控制，难以应用于对实时要求很高的环境中.为了满足用户的时延需求，DB-MDST算法[10]改进了MDST算法，其主要思想是在限制树的高度的情况下，反复利用“加入－删除”边的操作减少节点的度，从而达到优化树的生命周期.DCML算法[11]和MILD算法[12]在IAA算法的基础上考虑时延约束，它开始于最小跳数树，然后在保证时延约束的条件下，反复将非树上的一条边去替代树中的一条边，以降低某一瓶颈结点或次瓶颈结点的度.

尽管DB-MDST算法、DCML算法和MILD算法能保证在时延受限的情况下构造负载均衡的最大生命周期数据收集树，但它们只将节点的跳数作为时延约束条件，而没有考虑节点发送、接收、处理数据等方面所产生的时延，如子节点数多的节点产生的时延比子节点数少的节点产生的时延大.另外，反复优化的过程需要大量的运行时间，从而造成算法具有较高的时间复杂性.因此，本文提出一种新的受时延约束的最大化生命周期数据收集树算法（a Delay-Constrained Maximum-Lifetime data Gathering Tree algorithm，简记为DCMLGT算法），旨在满足用户时延需求的情况下，提高能量的使用效率从而延长网络寿命.

1　系统模型和问题的陈述

1.1网络模型

假设用一个连通的无向图G=（V,E）表示一个由n个无线传感器和1个Sink节点组成的网络，其中V={v0,v1,v2,…,vn},||V=n+1,v0表示Sink节点，v1, v2,…,vn表示n个无线传感器且随机分布在一个正方形区域A内，边（u,v）∈E是指传感器u和传感器v相互处于对方的通信范围内， ||E=m为边的数量.

此外，无线传感器网络具有如下的性质：

①网络是连通的静态网络，节点部署后不再移动，即节点是固定的.②每个传感器节点的初始能量有限，并且不能补充；Sink节点的能量是无限的.③除Sink节点外，所有节点具有相似的能力（处理/通信），并且地位平等.④采用数据聚合的方式进行通信，即每个传感器节点接收其邻居节点发来的m个大小为k bits的数据包，与自己产生的k bits数据进行聚合后，发送一个大小也为k bits的数据包给与自己的相邻节点或Sink.

1.2能量消耗模型

本文采用与文献[13]相同的无线通信能量消耗模型.节点发射k bit的数据到距离为d的位置，消耗的能量由发射电路损耗和功率放大损耗两部分组成，即：

其中Eelec表示发射电路损耗的能量，Eamp表示功率放大所需的能量.节点接收k bit的数据消耗的能量为：

1.3相关定义

为了方便描述在WSNs中如何构造受时延约束最大化生命周期的数据收集树，先将一些常用的术语和概念作定义.

定义1轮（Round）：是从所有传感器节点收集一次数据，并传送到Sink节点的过程.

定义2在一轮中，一个节点在树上的能量消耗定义为：

其中m是节点v在树上的孩子数.

定义3节点的生命周期（Node lifetime）：是节点v在一棵树中能存活的轮数.存活指节点v的能量Eo（v）＞0，节点v在一棵树中的生命周期可定义为：

定义4树的生命周期（Tree lifetime）：是树T中第一个节点死亡时，该节点存活的轮数，定义为：

定义5数据时延：如果节点u和节点v之间存在一条连通的路径（用P（u,v）表示），那么，数据时延是指数据从节点u传送到节点v的累计时延，即数据在路径P（u,v）上所有节点的数据处理时延与数据在链路上的传送时延之和，即：

1.4问题描述

无线传感器网络的重要目标就是在满足应用需求的前提下，尽可能长时间地对周围环境进行监测.这样本文要解决的问题可描述为：①数据收集树的生命周期最大化；②满足数据收集的最大时延小于上限.

对于上述问题，可用公式（7）表示：

其中T是网络G中任意一棵生成树，Ts（G）是无向图G中所有生成树的集合，Δ为应用需求的时延上限（或时延约束）.

2 DCMLGT算法

2.1DCMLGT算法描述

DCMLGT算法起始于只包含Sink节点的生成树T，然后每次将生命周期估计值最大、且其对应的节点满足端对端时延约束的边加入到生成树，直到所有的节点加入到生成树为止.DCMLGT算法的伪代码如下：

输入：图G，时延约束△

输出：满足时延约束△的最大生命周期树T

VT={sink}；

Q=V-{sink}；

Repeat

Maxlife=0

for each v∈Q{

If（u,v）∈E and u∈VT{

if delay（u,sink）+delay（u,v）≤△ {

计算w（u,v）

if maxlife≤w（u,v）{

maxlife=w（u,v）

add_edge=（u,v）

add_node=v

}

}

}

}

If maxlife＞0{

VT=VT∪{add_node}；

T=T∪{add_edge}；

Q=Q-{add_node}；

计算delay（add_node,sink）

}

else return false

until Q=0

在DCMLGT算法中，每次将一个节点加入生成树的主要步骤为：对于每条边（u,v）∈E，且u为生成树T上的节点，v为非生成树的节点，首先计算节点v经节点 u到 Sink的时延 delay（v,Sink）.如果delay（v,Sink）≤Δ，则计算边（u,v）的权值.边（u,v）的权值设为该边两端节点的生命周期估计值中的最小值，即：w（u,v）=min（LE（u）,LE（v）），其中 LE（u）=E0（u）/（（m+1）×Erx（k）+Etx（k,d））表示节点u的生命周期的估计值（m为节点u在当前生成树上孩子节点的个数）；LE（v）=E0（v）/（Etx（k,d））表示节点v的生命周期的估计值.最后，在所有连接生成树T上的节点和非生成树上的节点的边中，取权值最大、且其对应的节点满足端对端时延约束的边加入到生成树上.

2.2仿真实验

假设网络中所有节点随机地分布在一个200× 200平方米的正方形区域.每个节点的初始能量在［1J,1.5J］之间随机分布，节点的数据产生率为1 000 bits/round，Erx=50 nJ/bit.所有节点的最大通信半径为50m.在每一个随机网络中，Sink节点的位置位于区域的中心.为了测试DCMLGT算法的性能，本文选择DB－MDST和MILD算法进行对比，且网络结点数在50～400之间变化，时延约束条件Δ在［10，40］ms之间变化.一般来说，数据在链路上的传送时延与结点之间的距离成正比，节点处理数据的时延与该节点及其子节点的个数相关.但本文为了便于与DB－MDST和MILD算法进行比较，在仿真实验中，将数据在链路上的传送时延设置为1ms，节点处理节点本身或每个子节点的数据时延为0.1ms.实验结果均是执行50次后的平均结果.

图1是网络的生命周期随网络节点员数目变化时的曲线图，图2是网络大小变化时各种算法的计算时间曲线图.从图中可以看出，DCMLGT算法在网络的生命周期上优于DB－MDST算法而劣于MILD算法，在计算时间上优于DB－MDST和MILD算法.

图1　网络生命周期对比图

图2　算法的计算时间曲线图

3　结语

在无线传感器网络中，构造一棵网络生命周期最大化、满足用户延时需求的数据收集树，是一个NP完全问题.针对目前一些算法没有考虑节点发送、接收、处理数据等方面所产生的时延，提出一种新的启发式算法，该算法起始于Sink节点，然后每次将生命周期估计值最大、且其对应的节点满足用户延时需求的边加入到树中，直到所有的节点加入到树中为止.仿真实验表明：与现有算法相比，该算法在时延受限的情况下，能有效地延长树的生命周期.

[1]Akyildiz IF,Su W,Sankarasubramaniam Y,et al.Wireless sensor networks：a survey［J］.Computer Networks,2002,38（4）：393-422.

[2]Korpeoglu I,Tan H O.Power efficient data gathering and aggrega⁃tion in wireless sensor networks［J］.SIGMOD Record,2003,32（4）：66-71.

[3]LiangW F,Liu Y Z.Online data gathering formaximizing network lifetime in sensor networks［J］.IEEE Transactions on Mobile Com⁃puting,2007,6（1）：1-10.

[4]Badrinath G S,Gupta P,Das SK.Maximum lifetime tree construc⁃tion for wireless sensor networks［J］.Lecture Notes in Computer Science,2007：158-165.

[5]Buragohain C,Agrawal D,Suri S.Power aware routing for sensor databases［C］.Proc of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies（INFOCOM 2005）, Miami,2005：1747-1757.

[6]Zhang Q,Xie ZP,Ling B,etal.Amaximum lifetime data gathering algorithm for wireless sensor networks［J］.Journal of Software, 2005,16（11）：1946-1957.

[7]Yan W,Sonia F,Shroff N B.On the construction of a maximumlifetime data gathering tree in sensor networks：NP-completeness and approximation algorithm［C］.Proc of the 27th IEEE Confer⁃ ence on Computer Communications（INFOCOM2008）,Phoenix, 2008：356-360.

[8]YanW,Mao Z J,Sonia F,etal.Constructingmaximum-lifetime da⁃ta-gathering forests in sensor networks［J］.IEEE/ACM Transac⁃tionson Networking,2010,18（5）：1571-1584.

[9]Lin H C,Li F J,Wang K Y.Constructingmaximum-lifetime data gathering trees in sensor networkswith data aggregation［C］.Proc of IEEE International Conference on Communications（ICC）,Cape Town,2010：1-6.

[10]Kwon S,Kim JG,Kim C.An efficient tree structure for delay sensi⁃tive data gathering in wireless sensor networks［C］.Proc of the 22nd IEEE International Conference on Advanced Information Net⁃workingand Applications,Okinawa,2008：738-743.

[11]Liang JB,Wang JX,Chen JN.A delay-constrained andmaximum lifetime data gathering algorithm for wireless sensor networks［C］.Proc of the 5th International Conference on Mobile Ad-hoc and Sensor Networks（MSN'09）,WuyiMountain,2009：148-155.

[12]梁俊斌,王建新,陈建二.在传感器网络中构造延迟限定的最大化生命周期树［J］.电子学报,2010,38（2）：345-351.

[13]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-effi⁃cient communication strategies for wireless sensor networks［C］.Proceedingsof the 33rd Hawail International Conference on System Science,Hawaii,2000.

（编校：王露）

A Delay-Constrained Maximum-Lifetime Data Gathering Algorithm

LIUWenbin
（Departmentof Information and Management,Hunan University ofFinanceand Economics,Changsha,Hunan 410205,China）

The problem of constructing a data gathering treewhichmaximizes the network lifetime and satisfies the user's delay requirements inWSNs（Wireless Sensor Networks）is NP-complete.A new heuristics is proposed to solve this prob⁃lem.Starting from the Sink,this heuristics selects an edgewithmaximum estimation of lifetime and ability to satisfy the user's delay requirements to join the tree iteratively.It repeats this procedure untilallnodesare added to the tree.Simula⁃tion results show that the heuristics can constructa tree thathas longer lifetime than previous algorithms under the need ofuser'sdelay.

wirelesssensornetworks；lifetime；delay requirements；data gathering

TP393

A

1671-5365（2015）06-0086-03

2015-01-29修回：2015-03-18

刘文彬（1975-），男，讲师，硕士，研究方向为无线网络通信、算法优化、交通组织与交通控制

网络出版时间：2015-03-23 16：48网络出版地址：http：//www.cnki.net/kcms/detail/51.1630.Z.20150323.1648.001.html

引用格式：刘文彬.一种受时延约束的最大化生命周期数据收集算法[J].宜宾学院学报,2015,15（6）：86-88.