作者：黄培煌; 朱文兴扫描覆盖线性规划贪心算法移动传感器
摘要：扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点(Points of Interest,POI)进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大.首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案.该算法可在O(mn3.5L)时间内求解,并具有可证明的近似比1-1/e.其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O(m2n2)的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器.为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O(m log m+mn2).最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
