感知受限的移动传感器节点扫描覆盖优化算法

神显豪，李 军，奈 何

(广西高校嵌入式技术与智能信息处理重点实验室(桂林理工大学)，广西 桂林 541004)

(*通信作者电子邮箱leejun19901113@163.com)

感知受限的移动传感器节点扫描覆盖优化算法

神显豪，李 军*，奈 何

(广西高校嵌入式技术与智能信息处理重点实验室(桂林理工大学)，广西 桂林 541004)

(*通信作者电子邮箱leejun19901113@163.com)

移动无线传感器网络(WSN)的应用中，因为传感器节点的感知范围受限，其覆盖分析就是一个针对目标区域的扫描覆盖问题。提出了一种基于多目标优化的扫描覆盖算法。在目标区域中，采用双目标优化策略对单个移动传感器节点进行路径规划，一方面使节点的覆盖面最大化，另一方面使扫描覆盖的路径最短。仿真实验在含有障碍物和不含障碍物的情况下进行，与多节点的编队覆盖算法相比，所提算法在适度降低覆盖率的情况下，可大幅降低移动能耗。

移动传感器节点；扫描覆盖；双目标优化；覆盖率；能耗

GuilinGuangxi541004,China)

0 引言

在无线传感器网络(Wireless Sensor Network, WSN)研究中，覆盖问题是基本问题之一，它直接影响到WSN的工作效率和质量。在移动无线传感器网络的应用中，因为移动传感器节点的感知范围受限，其覆盖分析就是一个针对目标区域的扫描覆盖问题。近年来国内外对移动传感器节点的扫描覆盖目标区域的算法也有一些研究。王伟等[1]提出了一种模拟退火算法的扫描覆盖机制，比传统的扫描覆盖表现出更好的性能；雍毅等[2]提出了一种动态兴趣点的扫描覆盖，更能适应动态的目标区域；李小康等[3]提出了一种关于路径增量与覆盖间隔差异的插入启发式算法；刘晨光等[4]设计了一种使用聚类方法的扫描覆盖方法；舒莉等[5]设计了一种关于兴趣点问题的扫描覆盖；林锋等[6]设计了一种扫描覆盖方法，它使用具有移动性的传感器节点当作辅助来修复覆盖洞。上述几种算法都是通过多个移动传感器节点之间的编队对覆盖洞进行扫描覆盖，没有考虑到节点的能耗和生命周期，也没有考虑在含有障碍物的情况下的路径规划等问题[7]。

在上述研究的理论基础上，本文提出了一种优化的扫描覆盖算法。在目标区域中，采用双目标优化策略对单个移动传感器节点进行路径规划，一方面使得节点的覆盖面最大化，另一方面使扫描覆盖的路径最短。通过优化扫描覆盖算法，既降低了节点在扫描覆盖的过程中的能耗，又延长了节点的生命周期。

1 网络模型

本文将计算域定义为D，紧子集定义为R2,障碍物的集合定义为Ω，一个封闭的集合包含了有限数量的连接部件和多个特定的障碍物。传感器节点的半径为r，水平集函数ψ(x)表明的环境包含了两种情况：如果定义域的覆盖部分是在障碍里面，那就表示为负的；如果定义域的覆盖部分是在障碍外面，那就表示为正的。本文定义ψ(x)是障碍物Ω边界的典型符号距离函数。一个传感器节点x位于存在障碍物Ω的计算域D中，x为起始点，以直线的形式向前移动并且在点y的位置停下。如果x和y的绝对值之差小于等于r，那么就表示点y在障碍物的边界或者之内。部分公式概念如表1所示。

下面定义半径为r的传感器节点移动到点y位置的检测面积的水平集函数φ：

(1)

其中L(x，y)表示x到y的连线部分。z的位置在障碍物的边界时ψ(z)=0，在障碍物内的时候ψ(z)<0,在障碍物外界的时候ψ(z)>0。

表1 公式概念

2 移动传感器节点的路径规划

2.1 节点单位置的路径规划

考虑了移动传感器节点单位置的最大覆盖，更确切地说就是将移动传感器节点移动到最大覆盖范围V的最佳位置。本文使用梯度上升的方法来实现这个目标，即本文按照梯度流来移动节点x的位置，公式[8]如下：

(2)

其中，Δx表示关于x的梯度算子。梯度算子可以近似地看作有限差分方程。如本文使用中心差分方程可以得到：

(3)

其中h表示空间步长。

为了能够清晰地表示出移动传感器节点达到最大化覆盖的移动路径，本文在目标区域中设置了三个障碍物，并且通过梯度流的方法移动传感器节点，得到最大化覆盖面积。如图1所示，表示传感器节点的初始位置；如图2所示，表示移动传感器节点x位移到与障碍物相切的位置，达到最大化覆盖面积的位置[9]。移动传感器节点在目标区域中移动，当碰撞到计算域D的边界时，停止计算。其中阴影部分表明三个障碍物，虚线圆圈表示传感器节点的感知面积。

图1 传感器节点初始位置

图2 传感器节点最大化覆盖面积

2.2 节点多位置的路径规划

由移动传感器节点单位置发散到移动传感器节点的多位置，本文设{x1，x2，…，xm}表明m个传感器节点，{r1，r2，…，rm}表明m个传感器节点的半径，每个传感器节点的覆盖范围不同[10]。总的检测范围是多个传感器节点的联合覆盖，多个传感器节点的水平集函数如下所示：

(4)

另外，多个传感器节点检测面积V如下所示：

(5)

其中H表示一维的赫维赛德函数。

在目标区域中，两个移动传感器节点的情况下，需要寻找两个新的位置达到彼此的覆盖范围不相交，这样就使得覆盖面积达到最大化[11]。如图3所示两个移动传感器节点的初始状态，如图4所示两个移动传感器节点通过移动达到与障碍物相切，最终达到最大化覆盖面积，其中阴影部分表明三个障碍物，虚线圆圈表明传感器节点的检测面积[12]。

图3 两个移动传感器节点初始状态

图4 两个节点的最大化覆盖面积

当有三个移动传感器节点时，本文也考虑了多个节点的局部优化。图5为三个传感器节点的初始状态；图6为三个传感器节点达到的局部最大化覆盖。其中阴影部分表示三个障碍物，虚线圈表示传感器节点的覆盖范围[13]。

图5 三个传感器节点的初始状态

图6 三个传感器节点的局部最大化覆盖

2.3 解锁方法

在移动传感器节点的扫描过程中，面对障碍物的阻拦时需要改变位移的路径[14]。扫描过程中有可能会出现路径交叉的情况，这样会延长完成覆盖的时间[15]。为了解决交叉路径问题，完成最短时间的优化，本文在交叉点的位置补充了两个移动的位置。这样就可以达到解锁的目的，完成最短时间的最大覆盖优化。如图7所示，移动传感节点的四个位置出现交叉，此时本文在交叉点位置加上了两个移动位置完成解锁，如图8所示。

图7 初始位置 图8 解锁

Fig.7InitialpositionFig.8Nodepositionafterunlock

为了能够清晰地表示出该方法如何解锁，本文给出了一般情况下的解锁方法。

步骤1 假设移动传感器节点的路径为x1,x2,…,xm，其中路径线段xixi+1和xjxj+1存在交叉点。

步骤2 假设路径线段的交叉点为xinter，那么将xinter分别加入到xixi+1和xjxj+1两个路径线段之间。

步骤3 将交叉点加入到路径线段之后，对移动传感器节点的路径重新排序如下所示：xi,xinter,xj,xj-1,xj-2,…,xi+2,xi+1,xinter,xj+1。

步骤4 重复步骤1到步骤3，直至路径中不存在交叉点。

一般解锁方法如图9所示。

图9 一般解锁方法

3 扫描覆盖算法设计

扫描覆盖问题的目标是以最少数量的移动传感器达到最大的覆盖面积。在扫描覆盖问题的相关场合中，决策者在目标区域布置少许的移动传感器节点进行周期性的覆盖，代替了大规模固定式传感器节点覆盖的间隔需要。由于目标区域覆盖所需的节点数量减少，目标区域覆盖所需的工作成本也随之降低。

在传感器节点覆盖功能的水平集框架中，目标区域被描述的正值表示在覆盖区域的障碍外，负值表示在障碍物内，零值表示在障碍物的边界。传感器节点直线前进遇到障碍物时，会导致覆盖范围丢失，如果目标区域中的点和传感器节点的线段不相交于任何障碍物，那么该目标区域的点就会被传感器节点所覆盖。本文考虑了传感器节点的有限覆盖范围，使用单个移动传感器节点代替多个固定传感器节点对目标区域进行扫描覆盖。对于存在障碍物的目标区域，本文通过移动传感器节点的路径规划方法实现最大化覆盖。扫描算法设计如下：

步骤1 将多个固定传感器节点，依次地加入到目标区域中，按照几何方式布置达到全覆盖。

步骤2 存在障碍物的情况下，利用单个移动传感器节点代替多个固定传感器节点，按原路径进行扫描覆盖。

步骤3 根据路径规划，使得移动传感器节点达到最大覆盖，通过位移多个节点所扫描的位置，达到节点的最大化覆盖面积，并且删除冗余的节点。

步骤4 按照最短路径算法Dijkstra，利用移动传感器节点求出全覆盖下的最优路径。

步骤5 如果初始化路径中存在交叉路径，那么使用解锁方法来达到收敛。

步骤6 计算原有路径长度和扫描覆盖之后的路径长度，进行比较。如果优化之后的路径长度较短，那就说明本文扫描覆盖方法的有效性；反之，则效果不佳。

4 仿真实验及性能评估

4.1 实验参数设置

本文采用Matlab2012b仿真平台来进行仿真。平台是基于IntelCorei5-2300的CPU，4GB的运行内存的PC。为了表示传感器节点的覆盖性能，本文分别在没有障碍物的情况和存在障碍物的情况下进行分析。

1)无障碍物场景下的参数设置。

假定在20m×20m的目标区域内，依次布置的固定式传感器节点数N=16，节点的理想探测半径为r=6。无障碍物的仿真参数如表2所示。

表2 无障碍物场景下的仿真参数

2)有障碍物场景下的参数设置。

表3 有障碍物场景下的仿真参数

4.2 实验结果对比

1)无障碍物场景。

本文使用16个固定式传感器节点依次部署在20 m×20 m的目标区域中，达到全覆盖的效果，如图10所示。

接下来本文利用单个移动传感器节点按照原来的路径进行扫描，扫描过程按照几何的方法进行。如图11所示，移动传感器节点移动了16次位置，并且存在冗余覆盖面积。接下来本文会使用优化的扫描覆盖算法来对移动次数优化，防止移动传感器节点的能量耗尽。

由图11可知，移动传感器节点代替固定传感器节点进行扫描覆盖完成后，明显存在冗余节点位置，冗余覆盖。使用本文提出的扫描覆盖算法，进行路径规划，并且将冗余节点位置去除。这样可以达到移动传感器节点以最少时间、最短路径，达到最大化覆盖面积的效果。如图12可知，移动传感器节点移动了10次位置，达到了全覆盖的效果。

图10 16个固定节点的全覆盖

图11 移动传感器节点路径覆盖16个固定传感器节点

图12 优化扫描覆盖的路径

2)有障碍物场景。

在含有障碍物的情况下，该算法先假设障碍物不存在，使用36个固定传感器节点依次部署在30 m×30 m的目标区域中，达到全覆盖的效果，如图13所示。

接下来利用单个移动传感器节点按照原来的路径进行扫描，扫描过程按照几何的方法进行。如图14所示，移动传感器节点移动了36次位置，并且存在冗余覆盖面积。接下来本文会使用优化的扫描覆盖算法来对移动次数优化，防止移动传感器节点的能量耗尽，来延长网络寿命。

此时加入障碍物，也就相当于在复杂地形下，移动传感器节点的路径位置，如图15所示障碍物阻挡了多个传感器节点位置的感知面积。

图13 36个固定节点的全覆盖

图14 移动传感器节点路径覆盖36个固定传感器节点

图15 存在障碍物的移动路径

经过扫描覆盖优化方法之后，去除冗余的移动传感器节点位置，减小了移动路径的长度，缩短了移动到全覆盖的时间，移动传感器节点位移了33次，如图16所示。

4.3 计算开销性能和路径长度

图16 优化的移动路径

表4 有无障碍情况下的参数对比

Tab.4 Parameter comparison with/without obstacles

场景路径网络区域范围/(m×m)固定传感器节点数感知半径/m通信半径/m节点的移动次数移动路径长度/m无障碍物有障碍物原始路径20×20166121660．00优化路径20×20166121036．27原始路径30×303652/25236175．00优化路径30×303652/25233164．48

4.4 仿真对比

与传统扫描覆盖[5]相比，本文采用的是单个移动传感器节点扫描覆盖，通过路径规划使得节点达到最大覆盖面积，而不是用多个移动传感器节点实行编队扫描覆盖，后者大幅增加了成本，也增加了能耗。下面对本文提出的单个移动传感器节点扫描覆盖方法和双节点编队的扫描覆盖方法进行仿真对比。如图17所示，本文采用单个移动传感器节点和两个节点作对比，评估它们每个节点的时间和能耗。如图18所示，在有限的时间内本文提出的单移动传感器节点和双移动传感器节点编队的覆盖率作出了对比。

图17 能耗仿真对比

根据图17的仿真结果，在相同时间内本文提出的单个移动传感器节点，没有节点之间的编队和通信，减少了能量消耗，延长了节点的生命周期。这样可以确保移动传感器节点在维持覆盖的时间上能够延长。根据图18的仿真结果可知，随着时间的增加，单移动传感器节点和双移动传感器节点的覆盖率都在增加，其中双移动节点的覆盖率较高些。

图18 覆盖率仿真对比

相比之下，虽然双移动传感器节点的覆盖率较高些，但是它的两个节点之间需要进行编队和通信消耗了部分能量，每个节点能耗是单移动传感器节点的近乎两倍。为了延长节点的生命周期，在满足覆盖维持的前提下，可以选择单移动传感器节点对目标区域进行扫描覆盖。

5 结语

本文提出了一种优化的扫描覆盖。在目标区域中，使用单个移动传感器节点来代替固定传感器节点，对目标区域进行扫描修复。通过节点的路径规划，使得节点的覆盖面最大化，同时扫描覆盖的路径最短。实验结果表明，本文提出的算法在适度降低覆盖率的情况下，可大幅降低移动能耗。

References)

[1] 王伟，林锋，周激流.Sweep Coverage中的节点移动控制[J].四川大学学报(自然科学版),2010,47(5):1015-1019.(WANG W, LIN F, ZHOU J L.Controlling the mobility of sensors in sweep coverage [J].Journal of Sichuan University (Natural Science Edition), 2010, 47(5): 1105-1109.)

[2] 雍毅，林锋，周激流.基于Dynamic POIs的Sweep Coverage节点移动算法[J].四川大学学报(自然科学版),2012,49(4):795-799.(YONG Y, LIN F, ZHOU J L.Controlling the mobility of sensors in sweep coverage based on dynamic POIS [J].Journal of Sichuan University (Natural Science Edition), 2012, 49(4): 795-799.)

[3] 李小康，林锋，周激流.一种Sweep coverage问题的插入启发式算法[J].四川大学学报(自然科学版),2015,52(1):74-78.(LI X K, LIN F, ZHOU J L.A novel insert heuristic algorithm for sweep coverage problem [J].Journal of Sichuan University (Natural Science Edition), 2015, 52(1): 74-78.)

[4] 刘晨光，林锋，周激流.一种基于A-means聚类算法的Sweep coverage机制[J].计算机应用研究,2012,29(3):1051-1053.(LIU C G, LIN F, ZHOU J L.Sweep coverage approach with A-means clustering algorithm [J].Application Research of Computers, 2012, 29(3): 1051-1053.)

[5] 舒莉，林锋，刘中豪,等.基于兴趣点分类的无线传感器网络扫描覆盖机制[J].西南交通大学学报,2014,49(1):165-172.(SHU L, LIN F, LIU Z H.POI classfication based sweep coverage scheme in wireless sensor networks [J].Journal of Southwest Jiaotong University, 2014, 49(1): 165-172.)

[6] 林锋，王伟，周激流.MASC:一种基于移动辅助节点的Sweep Coverage机制[J].四川大学学报(工程科学版),2010,42(6):119-125.(LIN F, WANG W, ZHOU J L.MASC: a sweep coverage approach with mobile-assisted carriers [J].Journal of Sichuan University (Engineering Science Edition), 2010, 42(6): 119-125.)[7] 张洪德,石为人,杨磊,等.基于粒子均衡的移动传感器网络覆盖控制研究[J].仪器仪表学报,2016,37(5):1049-1057.(ZHANG H D, SHI W R, YANG L, et al.Study on equilibrium of particle based coverage control for mobile sensor network [J].Chinese Journal of Scientific Instrument, 2016, 37(5): 1049-1057.)

[8] XIAO Y L, KAI L W, YANMIN Z, et al.Mobility increases the surface coverage of distributed sensor networks [J].Computer Networks, 2013, 57(11): 2348-2361.

[9] 方如举,王建平,孙伟.无线传感器网络通信的拥塞控制策略[J].电子测量与仪器学报,2016,30(4):558-567.(FANG R J, WANG J P, SUN W.The congestion control strategy for WSNs communication [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(4): 558-567.)

[10] 徐雪松,杨胜杰,陈荣元.复杂环境移动群机器人最优路径规划方法[J].电子测量与仪器学报,2016,30(2):274-282.(XU X S, YAN S J, CHEN R Y.Dynamic differential evolution algorithm for swarm robots search path planning [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 274-282.)

[11] MA H-C, SAHOO P K, CHEN Y-W.Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks [J].Journal of Network and Computer Applications, 2011, 34(5): 1743-1756.

[12] 张建军,陈晓,赵意.一种无线传感器节点动态采样策略[J].电子测量与仪器学报,2016,30(2):249-255.(ZHANG J J, CHEN X, ZHAO Y.Dynamic sampling control strategy for wireless sensor nodes [J].Journal of Electronic Measurement and Instrumentation, 2016, 30(2): 249-255.)

[13] SUNG H K, SEONG J K, HAOMIN Z.Path optimization with limited sensing ability [J].Journal of Computational Physics, 2015, 299: 887-901.

[14] 邓亚平，吴川平.基于移动节点的无线传感器网络中的瓶颈节点[J].计算机应用,2011,31(7):1939-1943.(DENG Y P, WU C P.Bottleneck nodes in wireless sensor networks based on mobile sensors [J].Journal of Computer Applications, 2011, 31(7): 1939-1943.)

[15] GORAIN B, MANDAL P S.Approximation algorithms for sweep coverage in wireless sensor networks [J].Journal of Parallel and Distributed Computing, 2014, 74(8): 2699-2707.

This work is partially supported by National Natural Science Foundation of China (E050603), Scientific Research Project of Guangxi Higher Education Institutions (YB2014157), Natural Science Foundation of Guangxi (2015GXNSFBA139254).

SHEN Xianhao, born in 1980, Ph.D., associate professor.His research interests include intelligent fault diagnosis, wireless sensor network.

LI Jun, born in 1990, M.S.candidate.His research interests include wireless sensor network.

NAI He, born in 1992, M.S.candidate.His research interests include wireless sensor network.

Sweep coverage optimization algorithm for mobile sensor node with limited sensing

SHEN Xianhao, LI Jun*, NAI He

(GuangxiUniversitiesKeyLaboratoryofEmbeddedTechnologyandIntelligentInformationProcessing(GuilinUniversityofTechnology),

In the applications of mobile Wireless Sensor Network (WSN), since the sensing range of the sensor nodes is limited, the coverage analysis is a scan coverage problem for the target area.In this paper, a new scan coverage algorithm based on multi-objective optimization was proposed.In the target area, the double objective optimization strategy was used on path planning for a single mobile sensor node, which could maximize the coverage of the node and make scan coverage path to the shortest.Simulation experiments were carried out under the conditions with obstacles and without obstacles.Compared with the formation coverage algorithm for multiple nodes, the proposed algorithm can significantly reduce the mobile energy consumption while moderately reducing coverage rate.

mobile sensor node; sweep coverage; double objective optimization; coverage rate; energy consumption

2016-07-26;

2016-08-06。 基金项目:国家自然科学基金资助项目(E050603)；广西高等学校科研项目(YB2014157)；广西自然科学基金资助项目(2015GXNSFBA139254)。

神显豪(1980—)，男，广西横县人，副教授，博士，主要研究方向：智能故障诊断、无线传感器网络； 李军(1990—)，男，安徽滁州人，硕士研究生，主要研究方向：无线传感器网络； 奈何(1992—)，男，湖北襄阳人，硕士研究生，主要研究方向：无线传感器网络。

1001-9081(2017)01-0060-05DOI:10.11772/j.issn.1001-9081.2017.01.0060

TP

A