﻿ 感知受限的移动传感器节点扫描覆盖优化算法
 计算机应用   2017, Vol. 37 Issue (1): 60-64  DOI: 10.11772/j.issn.1001-9081.2017.01.0060 0

### 引用本文

SHEN Xianhao, LI Jun, NAI He. Sweep coverage optimization algorithm for mobile sensor node with limited sensing[J]. JOURNAL OF COMPUTER APPLICATIONS, 2017, 37(1): 60-64. DOI: 10.11772/j.issn.1001-9081.2017.01.0060.

### 文章历史

Sweep coverage optimization algorithm for mobile sensor node with limited sensing
SHEN Xianhao, LI Jun, NAI He
Guangxi Universities Key Laboratory of Embedded Technology and Intelligent Information Processing(Guilin University of Technology), Guilin Guangxi 541004, China
Abstract: 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.
Key words: mobile sensor node    sweep coverage    double objective optimization    coverage rate    energy consumption
0 引言

1 网络模型

 $\varphi (x,r;y)=\underset{z\in L(x,y)}{\mathop{\min }}\,\{\psi (z),r-|z-x|\}$ (1)

2 移动传感器节点的路径规划 2.1 节点单位置的路径规划

 ${{\partial }_{t}}^{x}=\Delta xV(x)$ (2)

 ${{\partial }_{t}}^{x}={{D}_{0}}^{h}V(x)$ (3)

 图 1 传感器节点初始位置 Figure 1 Initial position of a sensor node
 图 2 传感器节点最大化覆盖面积 Figure 2 Maximum coverage area of a sensor node
2.2 节点多位置的路径规划

 $\varphi ({{x}_{1}},...{{x}_{m}},{{r}_{1}},...{{r}_{m}};y)=\underset{i=1,2,...,m}{\mathop{\max }}\,\varphi ({{x}_{i}},{{r}_{i}};y)$ (4)

 $V({{x}_{1}},{{x}_{2}},...{{x}_{m}})=\int_{\Omega }{\left( H\varphi ({{x}_{1}},...{{x}_{m}},{{r}_{1}},...{{r}_{m}};y) \right)dy}$ (5)

 图 3 两个移动传感器节点初始状态 Figure 3 Initial position of two sensor nodes
 图 4 两个节点的最大化覆盖面积 Figure 4 Maximum coverage area of two sensor nodes

 图 5 三个传感器节点的初始状态 Figure 5 Initial position of three sensor nodes
 图 6 三个传感器节点的局部最大化覆盖 Figure 6 Local maximum coverage area of three sensor nodes
2.3 解锁方法

 图 7 初始位置 Figure 7 Initial position
 图 8 解锁 Figure 8 Node position after unlock

 图 9 一般解锁方法 Figure 9 General unlock method
3 扫描覆盖算法设计

4 仿真实验及性能评估 4.1 实验参数设置

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

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

4.2 实验结果对比

1) 无障碍物场景。

 图 10 16个固定节点的全覆盖 Figure 10 Full coverage with 16 fixed sensor nodes

 图 11 移动传感器节点路径覆盖16个固定传感器节点 Figure 11 Path of mobile sensor nodes to cover 16 fixed sensor nodes

 图 12 优化扫描覆盖的路径 Figure 12 Optimized path after sweep coverage (without obstacles)

2) 有障碍物场景。

 图 13 36个固定节点的全覆盖 Figure 13 Full coverage with 36 fixed sensor nodes

 图 14 移动传感器节点路径覆盖36个固定传感器节点 Figure 14 Path of mobile sensor nodes to cover 36 fixed sensor nodes

 图 15 存在障碍物的移动路径 Figure 15 Moving path with obstacles

 图 16 优化的移动路径 Figure 16 Moving path after sweep coverage (with obstacles)
4.3 计算开销性能和路径长度

4.4 仿真对比

 图 17 能耗仿真对比 Figure 17 Energy consumption comparison
 图 18 覆盖率仿真对比 Figure 18 Coverage rate comparison

5 结语

 [1] 王伟, 林锋, 周激流. Sweep Coverage中的节点移动控制[J]. 四川大学学报(自然科学版), 2010, 47 (5) : 1105-1109. ( 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. doi: 10.1016/j.comnet.2013.04.008 [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. doi: 10.1016/j.jnca.2011.06.007 [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. doi: 10.1016/j.jcp.2015.07.037 [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. doi: 10.1016/j.jpdc.2014.02.009