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(mn3.5L) and an approximation ratio1-1/e. Then, extending the greedy algorithm for Set Covering, the paper presents an algorithm with a runtime O(m2n2), 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+mn2)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.
HUANG Peihuang, ZHU Wenxing
. Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks[J]. Operations Research Transactions, 2019
, 23(4)
: 155
-164
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.014
[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.
