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

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

Abstract

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

CLC Number:

O221.7

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

References

[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.

Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics

Comments

[1]	SHEN Yindong, QIAN Zhuang, LI Yuanyuan. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[2]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[3]	HUANG Yakui, LI Bo, KANG Yang, DAI Yuhong, LIU Jianjun. A mixed integer model and an algorithm for steady-state gas network optimization [J]. Operations Research Transactions, 2017, 21(2): 13-23.
[4]	LIAN Shujun, DU Aihua, TANG Jiahui. A new class of simple smooth exact penalty functions for equality constrained optimization problems [J]. Operations Research Transactions, 2017, 21(1): 33-43.
[5]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[6]	TANG Guochun, LIU Xiaohui. Applications of operations research in automotive parts inbound logistics [J]. Operations Research Transactions, 2015, 19(3): 123-130.
[7]	PAN Pingqi. On “An efficient implementation of the face algorithm for linear programming” [J]. Operations Research Transactions, 2015, 19(3): 78-84.
[8]	HE Shengxue. Determining optimal routes for transit vehicles in no-notice emergency evacuation [J]. Operations Research Transactions, 2014, 18(3): 47-59.
[9]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[10]	Shu-jun Lian. On the Smoothing of the Lower Order Exact Penalty Function for Inequality Constrained Optimization [J]. Operations Research Transactions, 2012, 16(2): 51-64.
[11]	ZHOU Kang, CHEN Jin, QIU Jiang, JIE Zhi. Matrix Algorithm for LP Problem Based on Partial Basic Variables [J]. Operations Research Transactions, 2012, 16(2): 121-126.
[12]	Shang-You-Lin, LIU Mu-Hua, LI Pu. A New Penalty Function Based on Non-coercive Penalty Functions [J]. Operations Research Transactions, 2012, 16(1): 56-66.
[13]	SONG Wei, ZHAO Mao-Xian, WANG Xiang-Rong. Fuzzy programming approach for Multilevel linear programming [J]. Operations Research Transactions, 2011, 15(4): 85-92.
[14]	WANG Sheng-Gang, ZHANG Ying, XU Ying-Tao. The BP Neural Network Hydrological Forecasting Algorithm Based on Tunneling Function Method [J]. Operations Research Transactions, 2011, 15(4): 45-54.