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

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

Study on Path Sweep Coverage Problem in Mobile Sensor Networks

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.