移动传感器网络中的最大价值路径扫描覆盖算法

doi:10.15960/j.cnki.issn.1007-6093.2019.04.014

摘要/Abstract

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

关键词: 扫描覆盖, 线性规划, 贪心算法, 移动传感器

Abstract: Sweep coverage is an important covering technique in nowaday wireless sensor networks, which deploys mobile sensors to periodically monitor a set of points of interest (POIs), providing a more cost-efficient method to monitor POIs comparing to the traditional covering methods. This paper investigates the Max-Value Sweep Coverage problem on Path (MVSCP), which is to cover a set of POIs over a path using mobile sensors, such that the value sum of the covered POIs attains maximum. This paper first presents an approximation algorithm based on linear programming (LP) randomized rounding technique, in which the problem is first relaxed as a linear program whose fractional optimum solution is then rounded to a solution to MVSCP. The approximation algorithm is with a runtime O(mn^3.5L) and an approximation ratio1-1/e. Then, extending the greedy algorithm for Set Covering, the paper presents an algorithm with a runtime O(m²n²), based on the main idea of repeatly picking the sensor with maximum covered value per unit patrolling range. To reduce the runtime, this paper further improves the runtime of the algorithm to O(m log m+mn²)based on the problem structure of MVSCP. At last, the paper evaluates the practical performance of the proposed algorithms by simulation experiments. The results show that the LP-randomized rounding algorithm is with a much better runtime that is one percent of the exact algorithm based on integral linear programs, but only compromising with slightly lower practical performance. Although without a provably approximation ratio, the improved greedy algorithm has a practical performance as good as the LP-randomized algorithm, while it is with least runtime among all the three algorithms.

Key words: sweep coverage, linear programming, greedy algorithm, mobile sensor

中图分类号:

O221.7

黄培煌, 朱文兴. 移动传感器网络中的最大价值路径扫描覆盖算法[J]. 运筹学学报, 2019, 23(4): 155-164.

HUANG Peihuang, ZHU Wenxing. Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks[J]. Operations Research Transactions, 2019, 23(4): 155-164.

参考文献

[1] Qi X, Wei P, Liu L, et al. Wireless sensor networks energy effectively distributed target detection[J]. International Journal of Distributed Sensor Networks, 2014, 10(7):763918.
[2] Xiao Y, Chen H, Li F. Handbook on Sensor Networks[M]. Singapore:World Scientific, 2010.
[3] Gorain B, Mandal P. Point and area sweep coverage in wireless sensor networks[C].//The 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt). Tsukuba Science City:IEEE, 2013, 140-145.
[4] Kong L, Zhao M, Liu X, et al. Surface coverage in sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(1):234-243.
[5] Li S, Shen H. Minimizing the maximum sensor movement for barrier coverage in the plane[C].//IEEE Conference on Computer Communications (INFOCOM). HongKong:IEEE, 2015, 244-252.
[6] Sengupta S, Das S, Nasir MD, et al. Multi-objective node deployment in wsns:In search of an optimal trade-off among coverage, lifetime, energy consumption, and connectivity[J]. Engineering Applications of Artificial Intelligence, 2013, 26(1):405-416.
[7] Pasqualetti F, Franchi A, Bullo F. On cooperative patrolling:Optimal trajectories, complexity analysis, and approximation algorithms[J]. IEEE Transactions on Robotics, 2012, 28(3):592-606.
[8] Cheng W, Li M, Liu K, et al. Sweep coverage with mobile sensors[C].//IEEE International Symposium on Parallel and Distributed Processing (IPDPS). Florida:IEEE, 2008:1-9.
[9] Choset H. Coverage for robotics-A survey of recent results[J]. Annals of Mathematics and Artificial Intelligence, 2001, 31(1-4):113-126.
[10] Xi M, Wu K, Qi Y, et al. Run to Potential:Sweep Coverage in Wireless Sensor Networks[C].//Proceeding of International Conference on Parallel Processing (ICPP). Vienna:IEEE, 2009:50-57.
[11] Du J, Li Y, Liu H, et al. On sweep coverage with minimum mobile sensors[C]//IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS). Shanghai:IEEE, 2010:283-290.
[12] Huang P, Lin F, Liu C, et al. ACO-Based Sweep Coverage Scheme in Wireless Sensor Networks[J]. Journal of Sensors, 2015:1-6.
[13] Gorain B, Mandal P. Point and area sweep coverage in wireless sensor networks[C].//Proceedings of the 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt). Tsukuba Science City:IEEE, 2013:140-145.
[14] Yang M, Kim D, Li D, et al. Sweep-coverage with energy-restricted mobile wireless sensor nodes[C].//Proceedings of the 8th International Conference on Wireless Algorithms, Systems, and Applications. Zhangjiajie:Springer, 2013:486-497.
[15] Gorain B, Mandal P. Line sweep coverage in wireless sensor networks[C].//Proceedings of Sixth International Conference on Communication Systems and Networks (COMSNETS). Bangalore:IEEE, 2014:1-6.
[16] Shu L, Cheng K, Zhang X, et al. Periodic sweep coverage scheme based on periodic vehicle routing problem[J]. Journal of Networks, 2014, 9(3):726-732.
[17] Collins A, Czyzowicz J, Gasieniec L, et al. Optimal patrolling of fragmented boundaries[C].//Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures. Montréal:ACM, 2013, 241-250.
[18] Dumitrescu A, Ghosh A, Tóth C. On fence patrolling by mobile agents[J]. arXiv 2014:1401.6070.
[19] Kawamura A, Kobayashi Y. Fence patrolling by mobile agents with distinct speeds[J]. Distributed Computing, 2015, 28(2):147-154.