基于全局时延最小化的移动Sink数据收集算法*

常　捷，张　灵，曾　碧

（广东工业大学计算机学院，广州510006）



基于全局时延最小化的移动Sink数据收集算法*

常捷，张灵*，曾碧

（广东工业大学计算机学院，广州510006）

摘要：针对Sink节点移动所带来的时延问题，提出了一种基于最优路径的移动Sink数据收集方案OPDG（Data Gathering Based on Optimal-Path）。首先由MWHA（Minimum Weighted Heuristic Algorithm）算法得到汇聚节点RP（Rendezvous Point）的集合，然后根据这些RP节点求出移动Sink的最佳驻留点集合，最后求出经过驻留点的最短路径。Sink沿着这条路径周期性采集数据。通过NS-2中大量的仿真实验结果表明，与已有算法相比，OPDG算法能最大限度的减小时延，延长网络的生命周期。

关键词：无线传感器网络；时延；移动Sink；汇聚节点

无线传感器网络WSN（Wireless Sensor Net⁃work）由大量微型的且能量受限的传感器节点组成。其中数据收集是WSN的主要应用之一，传感器节点通过逐跳通信的方式将感知的数据传送给Sink或基站。早期的研究工作侧重于静态网络［1］，容易使Sink周围的节点因过多的转发数据而很快死亡，从而造成“网络分割”，产生能量空洞［2］，使网络寿命大大降低。

因此很多研究者引入移动Sink来解决上述问题，相比静态网络，用移动Sink充当数据收集器［3-4］可以有效的解决能量空洞问题，缓解节点负载不均问题，而且，Sink的移动性还能减少节点将数据传输给Sink所需要的跳数，从而减少节点的能耗，延长网络寿命［5-6］。然而移动Sink的路径选择直接影响数据的收集效率以及网络的整体性能。Zhangc⁃hun［7］等采用一种自组织分簇算法选取合适的簇头作为数据收集点，可有效降低网络能耗。文献［8-9］提出时延受限时移动Sink的数据收集算法。文献［10］提出一种优化网络生存时间的Sink节点移动路径选择算法MPSA，通过将监测区域分成大小一致的网格来收集单跳范围内的传感器数据。文献［11］以满足时延要求和最小化网络能耗为目标，提出了一种基于虚拟点优先级的移动Sink路径优化方法，在算法中由网格方法划分虚拟点用TSP算法求解最短路径后由Sink沿着此路径收集传感器节点的数据。文献［12］提出一种基于可移动Sink的数据采集方案DCSR，通过确定采集点，再由量子遗传算法求解最短回路的方法来收集数据。文献［13］采用分布式思想与网络的局部信息选择最优路径，实现了网络能耗与传输时延之间的折中。文献［14］提出一种基于旅行商问题的汇聚节点选择算法。文献［15］提出一种Sink移动速度控制算法，在节点稀疏的区域增大移动速度在节点稠密的区域减小移动速度，提高了数据采集效率。

本文针对时延受限的无线传感器网络，提出了基于最优路径的数据收集方案OPDG（Data Gather⁃ing Based Optimal-Path）。主要包含两个阶段：第一阶段，由网络中节点的部署情况选出一系列RP节点。第二个阶段，在RP节点的基础上进一步找到Sink的最佳驻留点集合，再找到经过这些点的最短路径，使移动Sink沿着该路径收集数据。

1　网络模型

假设传感器节点以随机的方式部署到一个L×L的矩形监测区域内，形成一个多跳自组织网络，其中①网络是全连通的，且其中所有的节点有唯一的ID（0，…，n-1）号标识，且部署后就不再移动。②每一个节点具有相同的通信半径R。③每一个节点具有相同的初始能量E，但Sink的能量不受限制。④每一个节点可以获得自己的地理位置信息（例如采用GPS或节点定位算法获得）。⑤Sink RP节点具有移动性，且移动方式可控，以恒定的速度V移动。

本文用简单的能耗模型，假设网络中每个节点采用固定的发射功率和接收功率。当Sink移动到终点并返回到起点时，称其完成一“轮”移动。et表示发送单位数据的能耗，er表示接收单位数据的能耗。则在每一轮中的能耗表示如下式：

其中，hi表示节点i将数据发送到所属RP节点的最小跳数，且如果当前节点i即为RP节点，则hi=0。则将网络的单轮总能耗用最小跳数的形式表示如下：

从式（3）可知整个网络的能耗最小化问题相当于所有节点到其所属的RP节点的跳数之和的最小化，因此RP节点的选择至关重要。

2　汇聚节点

访问每个传感器节点会增加移动Sink的路径长度，这样将导致数据收集时延的增加。因此提出建立汇聚点的模型，静态传感器节点将数据发送到RP节点，移动Sink只需访问一系列的汇聚点即可。为了减轻下个阶段最短路径的计算量，RP节点集的建立应尽可能少量且能覆盖整个网络。

2.1问题描述

给定一个全连通网络G=（L，A），每条边aij∈A有一个非负代价eij，且eij相当于节点si与sj之间距离的代价，则最短路径数据收集问题可以定义为一个混合的线性规划问题：

目标函数

最小值

约束条件

该模型中定义的决策变量如下：

上面的公式中，目标函数（4）是指数据收集路径上的最小值。xij是用来表示边aij（从si到sj）是否在最优路径上的一个变量，变量Ii表明RP节点ci是否在最优路径上。限制条件（5）和（6）确保路径上的每个节点必须有一条指向它的边和另一条远离它的边。公式（7）强调了每个传感器节点必须在至少一个属于收集路径上的RP节点的邻居集合内，这样移动Sink可以收集到全网范围内的传感器节点的信息。由此可看出与TSP（Traveling Sales⁃man Problem）相似是一个NP-hard问题。因此提出一个启发式算法来解决这个问题。

2.2算法实现

由上节中的模型可知，选取RP节点时应尽量减少普通节点到RP节点的传输跳数。传感器节点的邻居集合应该包含在该节点一跳范围内的所有节点。这样我们可以得到全网范围内所有传感器节点的位置信息，以及每个节点的一跳邻居节点，且每个节点会定时发消息来维护自己的邻居表，每个传感器节点也可以通过广播来发现一跳范围内的邻居节点。因此，每个节点都可能是候选的RP节点。

我们举例说明邻居集合，RP节点的定义，在图1（a）中，其中s1，s2，s3，s44个节点，它们都可能成为RP节点，si∈{s1，s2，s3，s4}，候选的RP节点集C={s1，s2，s3，s4}。s1的邻居集合为{s1，s2，s3，s4}，s4的邻居集合为{s4，s1}，s2和s3的邻居集合为{s1，s2，s3}。

图2基于最小权值的启发算法MWHA（Mini⁃mum Weighted Heuristic Algorithm）由迭代执行来选出RP节点，从而选取最短路径，简称MWHA算法。在该算法中，当某个节点被选作RP节点时它的邻居节点也会被覆盖。该算法尽量用最小的代价覆盖每一个未被覆盖的节点的邻居集合。其中权值α定义为覆盖S中每个未被覆盖的节点的平均代价。计算每个候选RP节点的权重值，首先，定义一个空集C，C将包含所有的RP节点，U包含所有的传感器节点。F是所有节点的邻居集合的总集。两个邻居集合之间的距离被定义为两个相关的RP节点的距离。cost{S}是未被覆盖的邻居集合S的代价相当于S和任一覆盖的邻居集合之间的最短距离。

图1　MWHA执行示例

Create an empty set C

Create a set U containing all remaining sensors

Create the family set F of all neighbor sets

while U=Φ

Cover sensors in S

Add the corresponding polling point of S into C Remove sensors in S from U

end while

Find an approximate shortest tour on polling points in C

图2 MWHA——基于最小权值的RP选择算法

3　OPDG算法

交付时延即为移动Sink节点在整个路径上消耗的时间。因而Sink的访问路径越长，相应的时延也就越大。受Sink移动速率的限制，移动Sink由求出的TSP路径依次遍历网络区域内所有的汇聚节点，移动的距离较长，需要的时间也较长，且Sink移动得越频繁，网络的稳定性就越差。为进一步缩短Sink的移动路径，降低数据交付时延。提出了基于最优路径的数据收集算法。

3.1问题模型

传感器节点随机部署在网络中，RP节点存在集合C中，由图3可知，移动Sink s0的路径由一系列连接的线段组成。要使移动Sink的移动路径最短，即让所有的线段之和达到最小值。即

其中l（ci，cj）代表RP节点ci和cj之间的距离。

交付时延即为Sink节点在整个路径上消耗的时间与在每个驻留点的停留时间之和。可以线性表示为：

其中V是移动Sink节点s0的移动速度，tk代表移动节点在驻留点k处所停留的时间，A表示Sink所有的停留位置集合。要使交付时延Tmin取得最小值，一方面要使移动节点的移动路径Lmin最短，另一方面应尽量减少移动节点的访问停留点。

3.2路径优化算法实现

步骤①：求出TSP路径

由上节中得到的RP节点集合C求出移动Sink的一条TSP路径ρ=（s0，c1，…，ck，s0）如图3所示的TSP路径为ρTSP=（s0，c1，c2，c3，c4，c5，c6，c7，s0）。

图3　TSP路径

步骤②：选择驻留点AP（Access Point）

若要使节点s0的移动路径更短，AP个数更少，移动Sink的访问停留点应该在传感器节点通信范围的相交点。

首先由求出的TSP路径结合C中的汇聚节点找到在汇聚节点通信范围边界上的合适的驻留点AP（Access Point）并将其加入到集合A中。如图4所示，假设路径ρ=（s0，t1，b0，a0，t2，t3，a6，a7，s0）为当前最短路径。其中a0在节点的通信范围之外，b0在节点的通信范围之内，其他访问停留点均在节点通信范围的边界上。l（t1，b0′）＜I（t1，b0）+I（b0，b0′），访问点b0使移动路径变长，同理，l（t2，a0）＜I（t2，a0′）+I（a0，a0′），a0也使移动路径变长。我们可以通过让线段t0b0′代替t1，b0和b0，b0′，t2，a0′代替a0，a0′和t2，a0来使Sink的移动路径变得更短。因此，每个驻留点必须在节点通信范围的边界上。否则我们总能找到能使路径变短的更适合的点来代替它们。

其次，为了通过减少驻留点的个数来降低时延，判断如果汇聚节点ci和cj相交，则相交点成为新的AP。如图3中c1和c2相交，交点为t1，t1同时在RP节点c1和c2通信范围的边界上。因此s0停留在t1处能够同时接收到c1和c2的数据，这样减少了移动Sink的驻留点个数，从而减小了系统的交付时延。当前的AP集合为S={t1，t2，t3，a6，a7}，即得到最佳驻留点集合后的路径ρAP=（s0，t1，t2，t3，a6，a7，s0）。

图4　步骤2得到的路径

步骤③：线段组合优化

这种线段组合方法必须满足两个条件，一个就是两条相邻边的长度之和必须大于它们的欧氏距离，另一个就是要保证线段组合后所有的汇聚点仍然可以被访问。

如图5所示，t1是RP节点c1和c2的交叉点，由三角形定理可知d（t3，a6）+d（a6，a7）＞d（t3，a7），d0代表访问停留点t3与a7之间的距离，d1代表RP节点c6到线段t3a7之间的距离，R是节点的通信半径。假设t3的坐标为（x1，y1），a7的坐标为（x2，y2），c6的坐标为（x3，y3），则该线段的斜率是k=（y2-y1）/（x2-x1），方程为y-k（x-x1）-y1=0。由此可知

图5　最优路径

如果d1＜R，即Sink节点的移动路径经过c6的通信范围。故移动节点s0到此节点通信范围时仍可以直接接收c6节点的数据（即移动路径变短，收集的数据没变），也就保证了线段组合后所有的RP节点仍可以被访问。很显然，通过沿ρbest=（s0，t1，t2，t3，a7）这条最短路径移动，可以在最短的时间内获得时延最小的数据。

OPDG算法如下：

Create an empty set A

diis the distance between ciand line ai-1ai+1

While C≠ΦChoose a point aion the communication bound of ciAdd the access point aiinto AIf（ciand cjhave intersection point ti）{Add tiinto A instead of aiand aj

}

End while

While A≠ΦIf（（d（ai-1，ai+1）＜d（ai-1，ai，）+d（ai，ai+1））&&（di＜R））{Remove aifrom A

}

End while

Find a shortest tour ρbeston access points in A

3.3停留时间分配

在一个采集周期中，每个汇聚节点发送的最大数据量是固定的，因此，在一定的网络生存时间内，可以根据在驻留点处Sink通信范围内各个汇聚节点的缓存数据量之和来改变停留时间。令Sink的最大移动速率为v，每个节点的数据发送速率为vg，则每一轮移动的总时间为Lmin/v，各访问点的停顿时间以及总停顿时间在如式（11）、式（12）所示：

其中，ak表示第k个访问点与Sink通信的汇聚节点的个数，qkj表示第k个访问点的第j个汇聚节点当前缓存的数据量，A表示Sink停留位置的集合，|C|表示集合C中汇聚节点的总数量。

4　仿真结果与性能分析

本文采用NS2仿真平台，对所提的时延受限的传感器网络移动Sink数据收集算法进行性能分析。实验中，我们假设节点随机分布在1 000 m× 1 000 m的网络区域中，且移动Sink的移动速度设为50 m/s，平台中节点的默认通信半径为200 m，而算法中驻留点的选取与节点的通信范围有关，因此，为了验证OPDG算法的良好性能，将本文中的OPDG算法与DCSR［12］算法进行比较，它也是一种利用移动Sink节点进行收集数据的方法。对两种算法所形成的路径长度，网络的时延以及生命周期加以统计比较。其中20个节点的拓扑结构如图6所示。

图6　拓扑结构

当在比较稀疏的网络中，且节点通信范围较小时，可能会造成整个网络不连通，这样，无论哪种算法，移动Sink都需要访问每个传感器节点。我们计算了在节点的通信半径分别为100 m和200 m，节点个数由20依次增加到60时，DCSR算法和OPDG算法各自的相对路径长度，由图7可知，一，当节点个数相同时，节点的通信范围越大，Sink节点移动的路径长度就越短。二，任意的通信范围，随着节点个数的增加，移动Sink的路径长度增长都趋于平缓。三，OPDG算法无论在何种情况下所求得的路径长度均明显少于DCSR算法。

图7　路径长度

交付时延指的是移动Sink完成一轮数据采集所消耗的时间。只有交付时延达到最小，每个数据包被上交给基站的时延才会最小。由图8可知，节点个数越多，时延越大，但当节点个数足够多时趋于平稳状态。节点通信范围越小，系统的整体时延也会相对增加。

图9中，可以看出，随着节点数目的增加，两种算法中网络的生命周期（轮数）都随之减小，且逐渐趋于平缓，然而OPDG算法的网络生命周期明显要长于DCSR算法。由图（a）图（b）比较可知，在相同拓扑结构的网络中，节点的通信范围越大，网络的生命周期越长。因此，在同一网络中，本文中的OPDG算法相比DCSR算法能更好的延长网络的生命周期。

以上结果表明OPDG算法能很好的适用于节点通信范围大的网络中。在网络中节点分布情况相同时，节点通信范围越大，它能覆盖的邻居节点数越多，我们得到的驻留点数越少，相对来说，优化所得的路径将会更短，故而时延越小。综上所述，OPDG算法能够极好的减小移动Sink的路径长度，从而最大限度的减小了系统的交付时延。

图9　网络生命周期

5　总结

本文为减小系统的交付时延，提出了一种基于最优路径的数据收集算法。先由MWHA算法求出汇聚节点集，在TSP算法的基础上经过优化求出一系列最佳驻留点，通过线段优化算法得到一条最短路径，使移动Sink能够尽快完成一个数据采集周期，从而减小时延。通过模拟平台的实验验证了本文的OPDG算法能够在最短路径的条件下减小系统的交付时延，延长网络的生命周期。下一步我们将考虑多个Sink移动的数据收集以及它们之间的协作通信问题。

参考文献：

［1］Lung C H，Zhou C J.Using Hierarchical Agglomerative Clustering in Wireless Sensor Networks：An Energy-Efficient and Flexible Approach［J］.Ad Hoc Networks，2010，8（3）：328-344.

［2］Tang L，Jian P，Xiao F W et al.Research on the Energy Hole Prob⁃lem Based on Non-Uniform Node Distribution for Wireless Sensor Network［J］.Transactions on Internet and Information Systems，2012，6（9）：2017-2036.

［3］Yang Y，Fonoage M I，Cardei M.Improving Network Lifetime with Mobile Wireless Sensor Networks［J］.Computer Communications，2010，33（4）：409-419.

［4］Zhang X W，Chen G H.Design of Mobile Sink Node for SDMA Applications in WSN［J］.Journal of Computer Research and De⁃velopment，2012，49（3）：541-549.

［5］惠晓威，刘彦每.WSN数据收集中移动Sink的路径规划和簇头节点选取问题的综合研究［J］.传感技术学报，2014，27（1）：118-122.

［6］张蕾，张堃.无线传感器网络中一种基于移动Sink的数据收集算法［J］.传感技术学报，2012，25（5）：673-677.

［7］Zhang Chun，Fei Shumin，Zhou Xingpeng.Energy Efficient Data Collection in Hierarchical Wireless Sensor Networks［J］.China Communications，2012，9（9）：79-88.

［8］Gao S，Zhang H，Das S K.Efficient Data Collection in Wireless Sensor Networks with Path-Constrained Mobile Sinks［J］.IEEE Transactions on Mobile Computing，2011，10（4）：592-608

［9］郜帅，张宏科.时延受限传感器网络移动Sink路径选择方法研究［J］.电子学报，2011，39（4）：742-747.

［10］王章权，陈友荣，尉理哲，等.优化网络生存时间的Sink节点移动路径选择算法［J］.传感技术学报，2014，27（3）：409-415.

［11］张希伟，沈琳，蒋益峰，等.移动协助传感器网络中Sink的路径优化策略［J］.通信学报，2013，34（2）：85-93.［12］郭剑，孙力娟，许文君，等.基于移动Sink的无线传感器网络数据采集方案［J］.通信学报，2012，33（9）：176-184.

［13］Somasundara A A，Kansal A，Jea D.Controllably Mobile Infra⁃structure for Low Energy Embedded Networks［J］.IEEE Transac⁃tions on Mobile Computing，2006，5（8）：958-973.

［14］Xing G L，Wang T，Jia W J，et al.Rendezvous Design Algorithms for Wireless Sensor Networks with a Mobile Base Station［C］//Proc of the ACM MobiHoc.Hongkong，China，2008，5317（6）：231-240.

［15］Bhadauria D，Tekdas O，Isler V.Robotic Data Mules for Collect⁃ing Data over Sparse Sensor Fields［J］.Journal of Field Robotics，2011，28（3）：388-404.

常　捷（1991-），女，河南人，广东工业大学在读硕士，主要研究方向为智能优化算法研究与应用，无线传感网络传输技术；

张　灵（1968-），女，广西人，博士，广东工业大学计算机学院教授。主要研究方向为智能优化算法研究与应用，无线传感网络传输技术，1252875930@qq.com。

Data Gathering Algorithm for Mobile Sink Based on the Global Delivery Latency Minimization*

CHANG Jie，ZHANG Ling*，ZENG Bi
（Faculty of Computer，Guangdong University of Technology，Guangzhou 510006，China）

Abstract：For the latency problem brought by the movement of Sink node，this paper presents a mobile Sink data gathering program based on optimal path（OPDG）.Firstly，a set of rendezvous points（RP）are obtained by MWHA （Minimum Weighted Heuristic Algorithm）algorithm.Then a best set of access points are selected according to the RP set.Finally，the shortest path is found across the access points.The mobile Sink will travel along this path peri⁃odically and collect data at each access point.Lots of simulation results show that compared with existing algorithm，OPDG algorithm can shorten the delivery latency and prolong the network lifetime.

Key words：wireless sensor networks；delivery latency；mobile Sink；rendezvous point

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.02.019

收稿日期：2015-08-13修改日期：2015-11-18

中图分类号：TP393.01

文献标识码：A

文章编号：1004-1699（2016）02-0264-07

项目来源：广东省产学研合作专项项目(2014B090904080)；广州市科技计划项目(2014J4100228)