Study on Path Sweep Coverage Problem in Mobile Sensor Networks

doi:10.19678/j.issn.1000-3428.0062218

Abstract

Abstract: As an important application of wireless sensor networks, compared to traditional covering methods, a sweep coverage provides a more cost-efficient method for monitoring the Points of Interest (POIs) by placing the sensors regularly within the monitored region.This study studies the Minimum Sensor Number and Punishment Sweep Coverage on Path (MNPSCP) problem, in which mobile sensors are scheduled to scan the POI sets on a given path to minimize the total sensor consumption and punishment time costs of the POIs.First, the problem is described as a type of integer programming.Second, because integer programming can only efficiently solve small and medium-sized instances, greedy and genetic algorithms are designed to solve large-scale instances based on the problem structure.To increase the solution quality and improve the local optimization ability of the algorithm, a genetic simulated annealing algorithm is designed by introducing a simulated annealing operation based on the genetic algorithm.The experimental results show that the greedy algorithm, genetic algorithm, and proposed genetic simulated annealing algorithm all achieve a good convergence.In addition, although the quality of the greedy algorithm solution is relatively poor, the speed is fast.Moreover, the quality of the solution of the genetic algorithm is better but unstable.The local optimization ability and solution stability of the genetic simulated annealing algorithm are significantly enhanced, and the quality of the solution is higher than that of the other algorithms.

Key words: wireless sensor, sweep coverage, integer programming, greedy algorithm, genetic algorithm, simulated annealing

摘要： 扫描覆盖作为无线传感器网络中的重要应用之一，通过规划移动传感器对区域内兴趣点（POI）进行定期覆盖，因此相较于传统覆盖方法能以更低廉的成本监测POI。研究最少传感器数量-最小罚时路径扫描覆盖问题，即通过调度移动传感器扫描给定路径上的POI集合，使传感器使用数量及产生的POI总罚时成本之和最小。将该问题转换为整数规划，并基于该问题的特殊结构设计贪心算法和遗传算法，以求解大规模实例。在遗传算法基础上引入模拟退火操作，以设计一种遗传模拟退火算法，从而提高求解质量和算法局部寻优能力。实验结果表明，所提贪心算法、遗传算法及遗传模拟退火算法均有较好的收敛性，贪心算法求解质量相对较差，但求解速度快；遗传算法解的质量更好，但存在不稳定的问题，局部寻优能力较弱；遗传模拟退火算法的局部寻优能力和求解稳定性明显增强，解的质量优于其他两种算法。

关键词: 无线传感器, 扫描覆盖, 整数规划, 贪心算法, 遗传算法, 模拟退火

CLC Number:

TP393

MIAO Xin, CHEN Xuan, BAO Hongying, ZHANG Jingxuan, YU Wei. Study on Path Sweep Coverage Problem in Mobile Sensor Networks[J]. Computer Engineering, 2022, 48(12): 150-155,164.

缪欣, 陈璇, 鲍红莹, 张静轩, 余炜. 移动传感器网络中路径扫描覆盖问题研究[J]. 计算机工程, 2022, 48(12): 150-155,164.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0062218

http://www.ecice06.com/EN/Y2022/V48/I12/150

Figures/Tables 2

References

[1] 徐文浩.移动传感器网络中信息捕获的在线问题与移动节点充电问题的研究[D].杭州:杭州电子科技大学, 2021. XU W H.Study on the online problem of information catching in the mobile sensor network and the charging problem of mobile nodes[D].Hangzhou:Hangzhou University of Electronic Science and Technology, 2011.(in Chinese)
[2] VERMA S, SOOD N, SHARMA A K.Genetic algorithm-based optimized cluster head selection for single and multiple data sinks in heterogeneous wireless sensor network[J].Applied Soft Computing, 2019, 85:1-21.
[3] MAZUMDAR N, ROY S, NAYAK S.A survey on clustering approaches for wireless sensor networks[C]//Proceedings of the 2nd International Conference on Data Science and Business Analytics.Washington D.C, USA:IEEE Press, 2018:52-58.
[4] YAGOUTA A B, JABBERI M, GOUISSEM B B.Impact of sink mobility on quality of service performance and energy consumption in wireless sensor network with cluster based routing protocols[C]//Proceedings of the 14th International Conference on Computer Systems and Applications.Washington D.C, USA:IEEE Press, 2017:32-37.
[5] 张大踪, 杨涛, 魏东梅.无线传感器网络低功耗设计综述[J].传感器与微系统, 2006, 25(5):10-14. ZHANG D Z, YANG T, WEI D M.Overview of low-power design in wireless sensor networks[J].Transducer and Microsystem Technologies, 2006, 25(5):10-14.(in Chinese)
[6] 王宏志, 武莎莎, 鲁晓帆, 等.基于最优簇头数的环形无线传感器网络分簇算法[J].吉林大学学报(理学版), 2020, 58(5):1215-1222. WANG H Z, WU S S, LU X F, et al.Clustering algorithm for ring wireless sensor networks based on optimal cluster head number[J].Journal of Jilin University Science Edition, 2020, 58(5):1215-1222.(in Chinese)
[7] MOHAMED S M, HAMZA H S, SAROIT I A.Coverage in mobile wireless sensor networks (M-WSN):a survey[J]. Computer Communications, 2017, 110:133-150.
[8] LI M, CHENG W F, LIU K B, et al.Sweep coverage with mobile sensors[J].IEEE Transactions on Mobile Computing, 2011, 10(11):1534-1545.
[9] DU J Z, LI Y W, LIU H, et al.On sweep coverage with minimum mobile sensors[C]//Proceedings of the 16th International Conference on Parallel and Distributed Systems.Washington D.C, USA:IEEE Press, 2010:283-290.
[10] CHEN Q Q, HUANG X H, RAN Y L.Approximation algorithm for distance constraint sweep coverage without predetermined base stations[J].Discrete Mathematics, Algorithms and Applications, 2018, 10(5):18-23.
[11] CHEN Z Y, GAO X F, WU F, et al.A PTAS to minimize mobile sensor movement for target coverage problem[C]//Proceedings of the 35th Annual IEEE International Conference on Computer Communications.Washington D.C, USA:IEEE Press, 2016:1-9.
[12] GORAIN B, MANDAL P S.Solving energy issues for sweep coverage in wireless sensor networks[J].Discrete Applied Mathematics, 2017, 228:130-139.
[13] LIANG J, HUANG X H, ZHANG Z.Approximation algorithms for distance constraint sweep coverage with base stations[J].Journal of Combinatorial Optimization, 2019, 37(4):1111-1125.
[14] NIE Z X, DU H W.An approximation algorithm for general energy restricted sweep coverage problem[J].Theoretical Computer Science, 2021, 864:70-79.
[15] 张景昱, 刘京菊, 叶春明.基于目标分层和路径分割策略的扫描覆盖算法[J].计算机工程, 2020, 46(11):231-237, 245. ZHANG J Y, LIU J J, YE C M.Sweep coverage algorithm based on target layering and path segmentation strategy[J].Computer Engineering, 2020, 46(11):231-237, 245.(in Chinese)
[16] GAO X F, FAN J H, WU F, et al.Approximation algorithms for sweep coverage problem with multiple mobile sensors[J].ACM Transactions on Networking, 2018, 26(2):990-1003.
[17] 黄培煌, 朱文兴.移动传感器网络中的最大价值路径扫描覆盖算法[J].运筹学学报, 2019, 23(4):155-164. HUANG P H, ZHU W X.Algorithms for max-value path sweep coverage in mobile sensor networks[J].Operations Research Transactions, 2019, 23(4):155-164.(in Chinese)
[18] 神显豪, 李军, 奈何.感知受限的移动传感器节点扫描覆盖优化算法[J].计算机应用, 2017, 37(1):60-64, 102. SHEN X H, LI J, NAI H.Sweep coverage optimization algorithm for mobile sensor node with limited sensing[J].Journal of Computer Applications, 2017, 37(1):60-64, 102.(in Chinese)
[19] 刘闯.无线传感器网络中扫描覆盖问题研究[D].哈尔滨:哈尔滨工业大学, 2016. LIU C.Research on the problems of sweep coverage in wireless sensor networks[D].Harbin:Harbin Institute of Technology, 2016.(in Chinese)
[20] 孟祥根.水面无人艇路径规划[D].哈尔滨:哈尔滨工业大学, 2020. MENG X G.Path planning of unmanned surface vehicle[D].Harbin:Harbin Institute of Technology, 2020.(in Chinese)
[21] 田钢, 汪晋, 董扬, 等.一种基于贪心算法的雷达网通信资源调度策略[J].现代雷达, 2021, 43(4):46-51. TIAN G, WANG J, DONG Y, et al.A communication resource scheduling strategy for radar network based on greedy algorithm[J].Modern Radar, 2021, 43(4):46-51.(in Chinese)
[22] 解扬, 苗付友, 白建峰.基于整数规划的一般访问结构秘密共享方案[J].计算机工程, 2019, 45(6):165-170. XIE Y, MIAO F Y, BAI J F.Secret sharing scheme with general access structure based on integer programming[J].Computer Engineering, 2019, 45(6):165-170.(in Chinese)
[23] 佘智勇, 庄健敏, 翟旭平.基于改进的TSP模型和模拟退火算法路径规划研究[J].工业控制计算机, 2018, 31(2):56-57. SHE Z Y, ZHUANG J M, ZHAI X P.Path planning research based on improved TSP model and simulated annealing algorithm[J].Industrial Control Computer, 2018, 31(2):56-57.(in Chinese)
[24] 张雅舰, 刘勇, 谢松江.一种求解装箱问题的改进遗传算法[J].控制工程, 2016, 23(3):327-331. ZHANG Y J, LIU Y, XIE S J.An improved genetic algorithm for bin-packing problem[J].Control Engineering of China, 2016, 23(3):327-331.(in Chinese)
[25] GUERRERO M, MONTOYA F G, BAÑOS R, et al.Adaptive community detection in complex networks using genetic algorithms[J].Neurocomputing, 2017, 266:101-113.
[26] 陈柏鸿.带能量约束的移动传感器扫描覆盖问题[D].哈尔滨:哈尔滨工业大学, 2018. CHEN B H.Mobile sensor sweep coverage problem with energy limitations[D].Harbin:Harbin Institute of Technology, 2018.(in Chinese)

Please choose a citation manager

Content to export