计算机工程

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

单位：1. 华东理工大学 数学学院, 上海 200237;2. 华东理工大学 商学院, 上海 200237

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

基金：国家级大学生创新创业训练计划（202010251060）；上海市自然科学基金（19ZR1411800）。

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

来源：2022年第12期

《计算机工程》期刊编辑部

查看计算机工程杂志2022年第12期