移动传感器网络中最少数量-罚时路径扫描覆盖问题研究

作者：缪欣; 陈璇; 鲍红莹; 张静轩; 余炜

来源：计算机工程, 2022, 1-10.

DOI：10.19678/j.issn.1000-3428.0062218

• 无线传感器
• 扫描覆盖
• 整数规划
• 贪心算法
• 遗传算法
• 模拟退火

作为无线传感器网络中的一个重要应用，扫描覆盖通过规划移动传感器对区域内兴趣点（Point of Interest，POI）进行定期覆盖，从而相对传统覆盖方法以更低廉的成本实现对POI的监测。研究最少数量-罚时路径扫描覆盖问题，即调度移动传感器扫描给定路径上的POI集合，使其耗用成本以及产生的POI总罚时成本之和最小。首先将问题刻画为整数规划，其次，由于整数规划只能高效求解中小规模实例，故基于该问题的特殊结构设计了复杂度为O(m~(2)n~(2))的贪心算法和O(MAXGEN×Nnlogn)的遗传算法求解大规模实例。为增加求解质量，提高算法局部寻优能力，在遗传算法基础上引入模拟退火操作设计了遗传模拟退火算法，其复杂度为O(MAXGEN×Nnlogn×logT_(s)/T_(e))。最后，通过仿真实验分析以上算法的实际性能。实验结果表明，三种算法均有较好的收敛性，贪心算法求解质量相对较差，但求解速度快；遗传算法解的质量更好，但存在不稳定的问题，局部寻优能力较弱；遗传模拟退火算法，局部寻优能力和求解稳定性明显增强，解的质量优于以上算法。

• 单位
  华东理工大学; 数学学院