扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点(Points　of　Interest,POI)进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大.首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案.该算法可在O(mn~(3.5)L)时间内求解,并具有可证明的近似比1-1/e.其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O(...