基于二次栅格划分的移动sink最小路径构建算法

王薇, 史浩山, 黄鹏宇, 高宝建, 牛进平, 王举

1.西北工业大学 电子信息学院, 陕西 西安 710072; 2.西北大学 信息科学与技术学院, 陕西 西安 710069 3.西安电子科技大学 通信工程学院, 陕西 西安 710071

基于二次栅格划分的移动sink最小路径构建算法

王薇1,2, 史浩山1, 黄鹏宇3, 高宝建2, 牛进平2, 王举2

1.西北工业大学 电子信息学院, 陕西 西安 710072; 2.西北大学 信息科学与技术学院, 陕西 西安 710069 3.西安电子科技大学 通信工程学院, 陕西 西安 710071

在无线传感器网络中引入移动sink能够有效解决能量空洞问题,从而提高无线传感器网络的生存时间。但是移动sink的移动速度限制通常会影响数据收集的时延特性,文章的研究重点即如何为移动sink构建最佳巡航路径,从而减小信息收集时延。充分利用传感器节点的通信范围,将构建最佳路径问题转化为求解带邻域的旅行商问题TSPN(traveling salesman problem with neighborhoods),并提出了一种基于二次栅格划分的可变长编码单亲遗传算法的最佳路径构建方法。该算法首先在网络区域中使用粗粒度栅格进行划分,并利用可变长度编码的单亲遗传算法获得最佳途经栅格,从而构造出初始最佳路径。然后对于每一个途经栅格再次使用细粒度栅格进行划分以优化收集路径。仿真结果表明,新算法能够获得更短的数据收集路径,大幅度减低了网络信息收集时延,有效地拓展了网络的生存时间。

无线传感器网络;移动sink;TSPN;栅格;最短路径

近年来无线传感器网络WSN(wireless sensor network)在环境监测、火情监测、战场探察等方面得到了广泛的应用[1]。在这些网络中,大量的感知节点被部署到被测区域中,每当有敏感事件发生时,传感器节点将收集到的数据经由多跳路径传输给静止的汇聚节点(sink节点)。由于全网收集的信息都要逐渐中转、汇聚,因此必然会导致靠近sink节点的普通节点需要承载更多传输负荷,从而消耗更多的能量,最终加速其死亡,并缩短了整个网络的生存时间,这就是所谓的“能量空洞”问题[2]。

在本项目组所承担的野生金丝猴相关研究课题中,我们也发现了“能量空洞”问题的存在。我们将大量的无线传感器节点部署在金丝猴经常出现的区域,由于野外地形所限,sink节点的数量有限,因此其余节点的数据都需要经过多次中转后到达sink节点。运行一段时间之后,我们发现靠近sink节点的普通节点总是最先耗尽电池。但是由于地处野外,节点电池难以更换,因此非常需要相应的方法来解决能量空洞问题。

近年来,移动sink的概念应运而生,利用移动sink可以优化数据的采集过程,并延长整个网络的生存时间[3-5],也可利用移动sink来辅助节点定位,由此显著提高定位精度[6-7]。在以上的研究中,我们可以看到由于移动节点收集信息时更贴近传感器节点,因此更利于提高信息收集的数量与质量,很好地解决sink固定时节点间耗能均衡的问题。

但是在实际的应用环境中,WSN布设范围通常较大,而受数据传输和承载平台的限制，移动sink的移动速度大多不高,因此与静止sink节点相比较,移动sink常常需要更多的时间才能完成全网数据的收集工作。而信息收集时延的大小在实际应用中是一个非常重要的性能衡量指标,因此有必要深入研究移动sink的移动路径规划问题,从而尽可能减少数据包的延迟。本文研究的重点即如何为移动sink设计最短的行进路由,从而获得最小的数据采集时延。

1 相关工作

在收集WSN中的数据时,移动sink通常需要在网络中按照某种路径往复运行。在移动过程中,为了节省能量移动sink通常仅会在某些信息汇聚点RP(rendezvous points)上才会开机采集数据,而在运动过程中关闭传输电路以节省能量。当移动sink移动到信息收集点时,如果传感器节点位于移动sink的通信范围之内,则上传其相关信息。

按照移动sink是否采用传感器节点的自身位置作为信息收集点,我们可以将移动sink信息收集方式分为2种类型:①使用传感器节点位置作为信息收集点坐标的方法,在这类方法中将移动sink的路径规划归结为TSP(travelling salesman problem)问题,见文献[8-12];②不使用传感器节点位置作为信息收集点坐标的算法,此时可以将问题归结为TSP的一种变形——TSPN问题,见文献[13]。

基于第一种思路,文献[8]研究了在WSN节点随机分布的情况下,移动sink的移动速度与信息收集效率之间的关系,并提出了一种MASP(maximum amount shortest path)算法。该算法将时延受限的信息收集问题转化为一个整数线性规划问题,并使用遗传算法以及一种分布式近似算法确定路径最优解。文献[9]将数据收集路径长度最小化问题归结为一个单跳数据收集问题SHDGP(single-hop data gathering problem)。并将SHDGP问题转化为一个混合的整数规划问题进行求解。文献[10]以满足时延要求和最小化网络整体能耗为优化目标,提出了一种基于虚拟点优先级的移动sink路径优化选择方法。该方法在牺牲少量能耗的前提下能显著降低算法时间复杂度。文献[11-12]则提出了一种基于信息汇聚点RP的移动sink数据收集机制。在该机制中传感器节点将采集的信息以多跳方式发送给距离最近的RP节点,移动sink依次访问各PR节点以收集数据。根据第二种思路,文献[13]将移动sink最短信息收集路径问题看作是一种带邻近区域的旅行商问题TSPN,提出了一种启发式算法构建信息收集路径,利用TSP路径为不自交环路的特征构建赛道,通过内圈启发式、弯道启发式以及捷径搜索寻找赛道内的近似最短路径。

对于以TSP问题为核心的算法,由于移动sink直接遍历各个传感器节点,因此不必考虑节点的通信范围,从而简化信息收集问题。但是由于这种方法需要遍历所有的节点,因此即使感知区域不变,当传感器节点数量增多时移动sink的信息收集路径长度也会相应增多,从而导致网络信息收集时延也随之增大,所以这一方法在扩展性和实用性方面都存在问题。

相较于基于TSP的方法,采用以TSPN为核心的方法是一个较好的思路。在这类算法中,移动sink并不直接遍历传感器节点的位置坐标,而是首先确定一些信息收集点IGP(information gathering position)。这些信息收集点并不仅限于节点的位置,而有可能是部署区域中的任意位置点。移动sink在工作的过程中并不连续收集信息,而是移动到信息收集点的时候才激活以该点为中心的通信范围内的传感器节点完成信息收集任务。同时,由于不需要限制IGP的选择范围,构建信息收集路径的将会更加灵活,因此可以在很大程度上缩短信息收集路径的长度。并且由于不需要簇头中转、汇聚信息,所以有更好的能耗表现。但是基于TSPN方法的难点在于如何构建最佳的信息收集路径。

根据以上分析,本文中我们提出了一种新颖的算法来解决移动sink路径规划问题。该算法采用二级栅格划分的方法对收集点位置进行逐层筛选以减少路径搜索的空间复杂度,并采用可变长编码的退火单亲遗传算法计算收集点的最佳遍历路径。仿真结果显示本文算法能够获得更短的信息收集路径长度,可显著减小移动sink信息收集时延。

2 基于二级栅格划分的可变长编码单亲遗传算法

由于基于TSPN的移动sink的最佳信息收集路径问题的关键在于如何选取信息收集点以及如何构建一条最短信息收集路径。所以,本文所研究的问题可以归纳为:在给定传感器网络节点分布的条件下,选择合适的信息收集点,并确定一条最短的信息收集路径,依次遍历所有信息收集点收集信息,最终使信息收集过程的时延最小。

2.1 算法设计

本文算法可以分为2个步骤:

步骤1 为了获得最佳信息收集路径,我们首先使用一个较大间隔的栅格将仿真区域划分为若干栅格单元,并以每个栅格的中心点作为备选的信息收集点,然后在这些备选的收集点集合中使用可变长编码单亲遗传算法构建一条能够覆盖所有节点的最短的信息收集路径。

在这个过程中,由于节点分布的不均匀性,因此构建的路径不一定包含所有的备选收集点。我们仅需要在备选收集点集合中找出一个子集,在该子集上收集信息就可以覆盖网络中所有节点。这个问题是一个典型的集合覆盖问题SCP(set cover problem),SCP问题同样是一个NP-hard问题。而且由于这种覆盖集所涵盖的备选信息收集点数目是可变的,所以如果使用遗传算法构建最佳路径,则无法使用经典的固定长度编码方式来表示遍历路径的位置序列,所以在这里我们无法使用常规的遗传算法进行求解。本文中我们使用可变长度编码的方法来解决这个问题,并对常规的单亲遗传算法进行修改以适应可变长度编码的问题。

步骤2 通过步骤1我们获得了第一级最佳路径。但由于其中所使用的栅格的划分间隔比较大,所以第一级最佳路径只是最佳路径的一个初步结果。为了进一步获得更精确的遍历路径,我们再次针对步骤1中所获最佳路径对应的一级栅格再做一次细粒度的栅格划分。在更细的栅格划分的基础上进一步确定收集点的精确位置坐标。在步骤2中由于在每一个一级栅格中还是选取一个收集点位置,所以在该过程中收集点的数量是固定不变的,且与一级最佳路径中涉及的栅格数相同。因此,为了提高运算速度,在这里我们使用固定长度编码的单亲遗传算法进行计算。最终就可以获得更加精确的二级最佳信息收集路径,并将其作为我们算法的最终结果。

图1 二级栅格划分方法

通过这种二级栅格筛选方法可以有效简化信息收集点的选择,降低算法的计算量,为之后最佳路径计算创造了有利条件。

2.2 算法流程

i∈I,j∈J,l∈N}

式中,nodel表示第l个传感器节点的位置坐标,I、J分别表示横、纵轴划分的栅格数,N表示场景中的节点数,“‖‖”表示进行欧氏距离计算。

算法流程描述如下:

Step1 产生初始种群

Step2 计算适应值

适应值是遗传算法的进化依据,在本文算法中,选择个体对应路径长度作为个体的适应值,适应值越小代表个体越优秀。

Step3 运行可变长度编码单亲遗传算法

为了保持进化过程中个体长度的可变特性,本文设计了2个算子:倒序算子和置换算子。

倒序算子:对于一个个体,根据个体长度随机选择倒序的起始、终结位置t1,t2,不失一般性设t1≤t2,然后将t1→t2的路径倒置为t2→t1的路径。

Step4 最优保持策略

在算法的运行过程中,将每一代中的最优个体保存下来;在倒序、置换操作完成后,比较上一代的最优个体值与当代最优个体值;若当代最优个体较差,则使用上代最优个体替换当代最差个体。

Step5 退出条件判断。

Step6 二次栅格划分及求解

在通过粗粒度栅格划分大致确定最佳信息收集路径之后,为了获得更加精确的信息收集路径,从而进一步减少信息收集时延,我们对所获得的一级最佳路径所涉及的一级栅格再次使用更小粒度的栅格进行划分,并且在每一个粗粒度栅格中只选择一个细粒度栅格中心作为路径的信息收集点备选位置。通过这一过程,整个路径的进一步构建就转化为对每个粗粒度栅格中细粒度栅格中心的选择过程,由于此时粗粒度栅格的数目已经固定,所以这里的搜索问题就变成一个固定IGP数量的路径优化问题,即信息收集路径上的信息收集点的数目是固定的。因此,我们在这里就可以采用定长编码的单亲遗传算法来加以解决,最终可以获得一条更好、更短的信息收集路径。

3 仿真结果分析

我们对文中所提出的算法进行了仿真,并将仿真结果与基于TSP的方法以及一种基于TSPN思路的算法——COM算法[14]进行对比分析,为方便起见,我们将本文所提出的算法简称为TGDA。

为了对比方便,本文采用和文献[14]相同的仿真设置。仿真中传感器节点均匀分布在在500 m×500 m的矩形区域里;节点数50～100个节点;传感器节点与移动sink节点具有相同的通信半径,半径设置为20～100 m;每次生成50个拓扑,每一个拓扑仿真50次。

为了更加清晰地体现算法性能,首先我们固定节点的通信半径为50 m和100 m,节点数由50逐级增加到100,并在这一过程中对3个算法的性能进行仿真,结果如图2所示。然后我们将节点数固定为50和100,节点的通信半径从20 m逐渐增加到100 m,再次对3个算法进行仿真,获得的结果显示如图3所示。

图2 节点通信半径固定时TGDA算法的性能 图3 节点数固定时TGDA算法的性能

从图2的仿真结果可以看出,在通信半径固定的情况下,无论网络中的节点数为50还是100,3种算法所获得的最佳路径长度都在逐渐增加。这是因为随着节点数的增多,移动sink需要经历的节点数也会同步增长,所以路径长度会随之增加。在节点数的不同设置下,显而易见TSP算法的性能都是最差的。这是由于在TSP算法中,每个传感器节点的位置就是IGP的位置,因此移动sink需要遍历所有节点位置才能完成信息收集任务,因此该算法所获得的路径长度必然是其中最长的。相较于TSP算法,COM算法的性能有了不小的提高。由于COM算法会根据相邻IGP覆盖范围的重叠程度选择合并相邻的IGP,这样COM算法生成的路径中包含的IGP更少,所以生成的路径长度相对更好。相较于对比算法本文提出的TGDA算法具有最好的算法性能,在通信半径50m、节点数50的情况下TGDA算法生成的路径长度比COM算法缩短了33.37%。若节点数增加为100,TGDA算法的优势更是扩大到了35.19%。

在固定节点数为50和100,节点通信半径由20 m增加到100 m时,仿真结果同样相似。在固定节点数时可以看到由于TSP算法遍历所有的节点位置,因此在节点数不变的情况下TSP算法的性能基本没有变化。随着节点通信半径的增加,由于COM和TGDA算法都考虑到节点的通信范围能力,因此这2种算法的性能都有了相应提高。并且节点通信半径越大意味着移动sink节点可以在更大的范围内收集到节点上传信息。所以随着通信半径的增长,COM以及TGDA算法的性能提高程度都随之扩大,但本文算法提高程度更高。从图3中看到,在节点数为50、通信半径为100 m时,相较于COM算法TGDA算法的路径长度减少了43.51%,若节点数增加到100,TGA算法的优势扩大到48.16%。

以上仿真结果可见在不同的仿真配置下,本文提出的TGDA算法都取得了优异的结果。TGDA算法能有效减少了移动sink的信息收集路径长度,从而降低了移动sink系统的信息收集时延,进而提高了整个系统的执行效率。

4 结 论

信息收集是WSN的一个关键应用领域,是WSN实际应用的基础。移动sink的引入使sink节点只需要通过传感器节点通信范围即可完成节点信息的收集,减少了信息传输的环节,简化了网络协议的复杂度。本文在充分考虑节点的无线通信特性的条件下,研究了移动sink在WSN中的最佳信息收集路径规划问题。在移动sink最佳信息收集路径的搜索过程中,本文算法通过二次栅格划分的方法来筛选信息收集点的搜索范围,简化算法的计算复杂度,在路径构建过程中的提出了一种新颖的基于可变长编码的单亲遗传算法来进行路径搜索。仿真结果表明本文算法与传统的基于TSP的算法相比,能够获得更好(短)的信息收集路径,减少了传感器节点的传输能耗、延长了网络的生存时间。与基于TSPN的算法相比本文算法原理简单,扩展性好,能够获得更好的信息收集路径。因此本文算法非常适用于大规模WSN网络信息收集路径的构建应用。

[1] Ou C H. A Localization Scheme for Wireless Sensor Networks Using Mobile Anchors With Directional Antennas[J]. IEEE Sensors Journal, 2011, 11(7):1607-1616

[2] Olariu S, Stojmenovi I. Design Guidelines for Maximizing Lifetimeand Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting[C]∥IEEE Infocom, 2006: 1-12

[3] Zhao M, Yang Y. Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks[J]. IEEE Trans on Computers, 2012, 61(2): 265-277

[4] Lin K, Chen M, Zeadally S, et al. Balancing Energy Consumption with Mobile Agents in Wireless Sensor Networks[J]. Future Generation Computer Systems, 2012, 28(2): 446-456

[5] Guo S, Wang C, Yang Y. Joint Mobile Data Gathering and Energy Provisioning in Wireless Rechargeable Sensor Networks[J]. IEEE Trans on Mobile Computing, 2014, 13(12): 2836-2852

[6] Liao W H, Lee Y C, Kedia S P. Mobile Anchor Positioning for Wireless Sensor Networks[J]. IET Communications, 2011, 5(7):914-921

[7] Chen H, Shi Q, Tan R, et al. Mobile Element Assisted Cooperative Localization for Wireless Sensor Networks with Obstacles[J]. IEEE Trans on Wireless Communications, 2010, 9(3): 956-963

[8] Gao S, Zhang H, Das S K. Efficient Data Collection in Wireless Sensor Networks with Path-Constrained Mobile Sinks[J]. IEEE Trans on Mobile Computing, 2010, 10(4): 592-608

[9] Ma M, Yang Y, Zhao M. Tour Planning for Mobile Data-Gathering Mechanisms in Wireless Sensor Networks[J]. IEEE Trans on Vehicular Technology, 2013, 62(4):1472-1483

[10] 郜帅, 张宏科. 时延受限传感器网络移动Sink路径选择方法研究[J]. 电子学报, 2011, 39(4):742-747 Gao Shuai, Zhang Hongke. Optimal Path Selection for Mobile Sink in Delay-guaranteed[J]. Acta Electronica Sinica, 2011, 39(4):742-747 (in Chinese)

[11] Xing G, Wang T, Jia W, et al. Rendezvous Design Algorithms for Wireless Sensor Networks with a Mobile Base Station[C]∥ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2008: 231-240

[12] Xing G, Wang T, Xie Z, et al. Rendezvous Planning in Wireless Sensor Networks with Mobile Elements[J]. IEEE Trans on Mobile Computing, 2008, 7(12):1430-1443

[13] 袁远, 彭宇行, 李姗姗,等. 高效的移动sink路由问题的启发式算法[J]. 通信学报, 2011, 32(10):107-117 Yuan Yuan, Peng Yuxing, Li Shanshan, et al. Efficient Heuristic Algorithm for the Mobile Sink Routing Problem[J]. Journal on Communications, 2011, 32(10):107-117 (in Chinese)

[14] He L, Pan J, Xu J. A Progressive Approach to Reducing Data Collection Latency in Wireless Sensor Networks with Mobile Elements[J]. IEEE Trans on Mobile Computing, 2013, 12(7):1308-1320

A Routing Planning Algorithm base on Twice Grid Division for Mobile Sink

Wang Wei1,2, Shi Haoshan1, Huang Pengyu3,Gao Baojian2, Niu Jinping2, Wang Ju2

1.School of Electronics and Information, Northwestern Polytechnical University, Xi′an 710072, China 2. School of Information and Technology, Northwest University, Xi′an 710069, China 3. School of Telecommunications Engineering, Xidian University, Xi′an 710071, China

Introduce mobile sinks into wireless sensor networks can balance the energy level of the sensor nodes, resolve the hotspot problem and prolong the lifetime of the whole network. However, the mobility of the sink may also introduce additional delays. Therefore, it is important to design an efficient routing protocol for the mobile sink. In this paper, we deduce this routing planning problem into a Traveling Salesman Problem with Neighborhoods (TSPN). In addition, we propose a routing design algorithm base on twice grid division and variable-length Partheno-genetic Algorithm. In this algorithm, we divide the network area with the grids coarse-grained, and obtain the grids on the best path with variable-length Partheno-genetic Algorithm. We then divide every grid on the path with the grids fine-grained in order to optimize the path. Finally, we implement this algorithm in Matlab and the simulation results show that the proposed algorithm can significantly improves the efficiency and effectiveness of the routing planning for the mobile sink.

wireless sensor network; mobile sink; TSPN; routing planning; grid division

2016-04-12 基金项目：国家自然科学基金(61170218、61602379)与陕西省教育厅自然科学基金(15JK1742、12JK0937)资助

王薇(1977—)，女，西北工业大学博士研究生，西北大学讲师，主要从事信息网络理论、无线传感器网络研究。

TP393

A

1000-2758(2016)06-1016-06