作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2022, Vol. 48 ›› Issue (12): 150-155,164. doi: 10.19678/j.issn.1000-3428.0062218

• 移动互联与通信技术 • 上一篇    下一篇

移动传感器网络中路径扫描覆盖问题研究

缪欣1, 陈璇2, 鲍红莹2, 张静轩2, 余炜1   

  1. 1. 华东理工大学 数学学院, 上海 200237;
    2. 华东理工大学 商学院, 上海 200237
  • 收稿日期:2021-07-30 修回日期:2022-01-16 发布日期:2022-12-07
  • 作者简介:缪欣(2000—),男,本科生,主研方向为无线传感器网络;陈璇、鲍红莹、张静轩,本科生;余炜(通信作者),副教授、博士。
  • 基金资助:
    国家级大学生创新创业训练计划(202010251060);上海市自然科学基金(19ZR1411800)。

Study on Path Sweep Coverage Problem in Mobile Sensor Networks

MIAO Xin1, CHEN Xuan2, BAO Hongying2, ZHANG Jingxuan2, YU Wei1   

  1. 1. School of Science, East China University of Science and Technology, Shanghai 200237, China;
    2. School of Business, East China University of Science and Technology, Shanghai 200237, China
  • Received:2021-07-30 Revised:2022-01-16 Published:2022-12-07

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

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

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

中图分类号: