research-article

Approximation Algorithms for Sweep Coverage Problem With Multiple Mobile Sensors

Authors:

Fan WuAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 26, Issue 2

Pages 990 - 1003

https://doi.org/10.1109/TNET.2018.2815630

Published: 01 April 2018 Publication History

Abstract

Sweep coverage plays an important role in many applications like data gathering, sensing coverage, and devices control. In this paper, we deal with the sweep coverage problem with multiple mobile sensors to periodically cover $n$ targets in the surveillance region. We propose three constant-factor approximations, namely, CycleSplit, HeteroCycleSplit, and PathSplit, to minimize the longest sweep period of mobile sensors under different scenarios, respectively. CycleSplit deals with the min-period sweep coverage problem MPSC, in which each mobile sensor works independently along a predetermined trajectory cycle. It has an approximation ratio of $5-{2}/{n-m+1}$, which improves the best known approximation ratio of 5. HeteroCycleSplit is a $5\alpha $ -approximation. It computes the sensor routes for heterogeneous velocity min-period sweep coverage problem HVMPSC, where each mobile sensor has a different velocity. PathSplit is a 2-approximation for connected path min-period sweep coverage problem CPMPSC. It solves a variant problem of sweep coverage where we need to cover all the given edges. Besides, we also propose an optimal algorithm DP-MPSC for min-period sweep coverage problem in 1-D case. Finally, we provide various numerical experiments and comparisons with several previous work to validate the efficiency of our design.

References

[1]

M. Cardei, M. T. Thai, Y. Li, and W. Wu, "Energy-efficient target coverage in wireless sensor networks," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Mar. 2005, pp. 1976-1984.

[2]

S. Kumar, T. H. Lai, and A. Arora, "Barrier coverage with wireless sensors," in Proc. ACM Int. Conf. Mobile Comput. Netw. (MOBICOM), 2005, pp. 284-298.

Digital Library

[3]

B. Liu, O. Dousse, J. Wang, and A. Saipulla, "Strong barrier coverage of wireless sensor networks," in Proc. ACM Int. Symp. Mobile Ad Hoc Netw. Comput. (MOBIHOC), 2008, pp. 411-420.

Digital Library

[4]

A. Chen, S. Kumar, and T. H. Lai, "Designing localized algorithms for barrier coverage," in Proc. ACM Int. Conf. Mobile Comput. Netw. (MOBICOM), 2007, pp. 63-74.

Digital Library

[5]

M. Amac Guvensan and A. Gokhan Yavuz, "On coverage issues in directional sensor networks: A survey," Ad Hoc Netw., vol. 9, no. 7, pp. 1238-1255, 2011.

Digital Library

[6]

Y. Wang and G. Cao, "On full-view coverage in camera sensor networks," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Apr. 2011, pp. 1781-1789.

[7]

S. He, J. Chen, X. Li, X. Shen, and Y. Sun, "Cost-effective barrier coverage by mobile sensor networks," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Mar. 2012, pp. 819-827.

[8]

B. Liu, O. Dousse, P. Nain, and D. Towsley, "Dynamic coverage of mobile sensor networks," IEEE Trans. Parallel Distrib. Syst., vol. 24, no. 2, pp. 301-311, Feb. 2013.

Digital Library

[9]

B. Gorain and P. S. Mandal, "Approximation algorithms for sweep coverage in wireless sensor networks," J. Parallel Distrib. Comput., vol. 74, no. 8, pp. 2699-2707, 2014.

[10]

M. Li, W. Cheng, K. Liu, Y. He, X. Li, and X. Liao, "Sweep coverage with mobile sensors," IEEE Trans. Mobile Comput., vol. 10, no. 11, pp. 1534-1545, Nov. 2011.

Digital Library

[11]

N. Bisnik, A. Abouzeid, and V. Isler, "Stochastic event capture using mobile sensors subject to a quality metric," in Proc. ACM Int. Conf. Mobile Comput. Netw. (MOBICOM), 2006, pp. 98-109.

Digital Library

[12]

W. Yu and Z. Liu, "Improved approximation algorithms for min-max and minimum vehicle routing problems," in Proc. Int. Comput. Combinat. Conf. (COCOON), 2015, pp. 147-158.

[13]

G. N. Frederickson, M. S. Hecht, and C. E. Kim, "Approximation algorithms for some routing problems," SIAM J. Comput., vol. 7, no. 2, pp. 178-193, 1978.

Digital Library

[14]

L. Xue et al., "Multiple heterogeneous data ferry trajectory planning in wireless sensor networks," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Apr./May 2014, pp. 2274-2282.

[15]

J. Du, Y. Li, H. Liu, and K. Sha, "On sweep coverage with minimum mobile sensors," in Proc. IEEE Int. Conf. Parallel Distrib. Syst. (ICPADS), Dec. 2010, pp. 283-290.

Digital Library

[16]

B. H. Liu, N. T. Nguyen, and V. T. Pham, "An efficient method for sweep coverage with minimum mobile sensor," in Proc. IEEE Int. Conf. Intell. Inf. Hiding Multimedia Signal Process. (IIH-MSP), Aug. 2014, pp. 289-292.

Digital Library

[17]

B. Gorain and P. S. Mandal, "Approximation algorithm for sweep coverage on graph," Inf. Process. Lett., vol. 115, no. 9, pp. 712-718, 2015.

Digital Library

[18]

Y. Feng, X. Gao, F. Wu, and G. Chen, "Shorten the trajectory of mobile sensors in sweep coverage problem," in Proc. IEEE Global Commun. Conf. (GLOBECOM), Dec. 2015, pp. 1-6.

[19]

S. Li, L. Z. Wang Wei, L. Feng, and Z. Jiliu, "A sweep coverage scheme based on vehicle routing problem," Indonesian J. Elect. Eng., vol. 11, no. 4, pp. 2029-2036, 2013.

[20]

R. Moazzez-Estanjini and I. C. Paschalidis, "On delay-minimized data harvesting with mobile elements in wireless sensor networks," Ad Hoc Netw., vol. 10, no. 7, pp. 1191-1203, 2012.

Digital Library

[21]

D. Zhao, H. Ma, and L. Liu, "Mobile sensor scheduling for timely sweep coverage," in Proc. IEEE Wireless Commun. Netw. Conf. (WCNC), Apr. 2012, pp. 1771-1776.

[22]

Z. Chen et al., "Efficient scheduling strategies for mobile sensors in sweep coverage problem," in Proc. IEEE Int. Conf. Sens., Commun., Netw. (SECON), Jun. 2016, pp. 1-4.

[23]

B. Gorain and P. S. Mandal, "Line sweep coverage in wireless sensor networks," in Proc. Commun. Syst. Netw. (COMSNETS), Jan. 2014, pp. 1-6.

[24]

B. Gorain and P. S. Mandal, "Point and area sweep coverage in wireless sensor networks," in Proc. IEEE Int. Symp. Modeling, Optim. Mobile, Ad Hoc Wireless Netw. (WiOpt), May 2013, pp. 140-145.

[25]

C. Liu, H. Du, and Q. Ye, "Sweep coverage with return time constraint," in Proc. IEEE Global Commun. Conf. (GLOBECOM), Dec. 2016, pp. 1-6.

[26]

P. Huang, F. Lin, C. Liu, J. Gao, and J. Zhou, "ACO-based sweep coverage scheme in wireless sensor networks," J. Sensors, vol. 2015, 2015, Art. no. 484902. [Online]. Available: https://www.hindawi.com/journals/js/2015/484902/

[27]

N. Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem," Graduate School Ind. Admin., Carnegie-Mellon Univ., Pittsburgh, PA, USA, Tech. Rep. 388, 1976.

[28]

M. Karpinski, M. Lampis, and R. Schmied, "New inapproximability bounds for TSP," J. Comput. Syst. Sci., vol. 81, no. 8, pp. 1665-1677, 2015.

Digital Library

[29]

G. Even, N. Garg, J. Könemann, R. Ravi, and A. Sinha, "Min-max tree covers of graphs," Oper. Res. Lett., vol. 32, no. 4, pp. 309-315, 2004.

Digital Library

[30]

M. R. Khani and M. R. Salavatipour, "Improved approximation algorithms for the min-max tree cover and bounded tree cover problems," Algorithmica, vol. 69, no. 2, pp. 443-460, 2014.

[31]

Z. Xu and Q. Wen, "Approximation hardness of min-max tree covers," Oper. Res. Lett., vol. 38, no. 3, pp. 169-173, 2010.

Digital Library

[32]

R. Sugihara and R. K. Gupta, "Optimal speed control of mobile node for data collection in sensor networks," IEEE Trans. Mobile Comput., vol. 9, no. 1, pp. 127-139, Jan. 2010.

Digital Library

[33]

L. Shu, K.-W. Cheng, X.-W. Zhang, and J.-L. Zhou, "Periodic sweep coverage scheme based on periodic vehicle routing problem," J. Netw., vol. 9, no. 3, pp. 726-732, 2014.

[34]

S. O. Tiwari and S. K. Yadav, "Data harvesting with mobile elements in wireless sensor networks," J. Electron. Commun. Eng., vol. 9, no. 1, pp. 104-114, 2014.

[35]

W. Cheng et al., "Sweep coverage with mobile sensors," in Proc. IEEE Int. Symp. Parallel Distrib. Process. (IPDPS), Apr. 2008, pp. 1-9.

[36]

N. Bisnik, A. A. Abouzeid, and V. Isler, "Stochastic event capture using mobile sensors subject to a quality metric," IEEE Trans. Robot., vol. 23, no. 4, pp. 676-692, Aug. 2007.

[37]

Z. Chen et al., "A route scheduling algorithm for the sweep coverage problem," in Proc. IEEE Int. Conf. Distrib. Comput. Syst. (ICDCS), Jun./Jul. 2015, pp. 750-751.

[38]

T. M. Cheng, A. V. Savkin, and F. Javed, "Decentralized control of a group of mobile robots for deployment in sweep coverage," Robot. Autom. Syst., vol. 59, nos. 7-8, pp. 497-507, 2011.

Digital Library

[39]

X. Gao, X. Zhu, Y. Feng, F. Wu, and G. Chen, "Data ferry trajectory planning for sweep coverage problem with multiple mobile sensors," in Proc. IEEE Int. Conf. Sens., Commun., Netw. (SECON), Jun. 2016, pp. 1-9.

[40]

P. Huang, L. Xu, Z. Kang, C. Liu, and F. Lin, "Ga-based sweep coverage scheme in WSN," in Proc. Int. Conf. Cloud Comput. Big Data (CCBD), Nov. 2016, pp. 254-259.

[41]

C. Liu, H. Du, and Q. Ye, "Utilizing communication range to shorten the route of sweep coverage," in Proc. IEEE Int. Conf. Commun. (ICC), May 2017, pp. 1-6.

[42]

B. Gorain and P. S. Mandal, "Solving energy issues for sweep coverage in wireless sensor networks," Discrete Appl. Math., vol. 228, pp. 130-139, Sep. 2017.

Digital Library

[43]

R. E. Burkard and U. Derigs, "The chinese postman problem," in Assignment and Matching Problems: Solution Methods With FORTRAN-Programs. Berlin, Germany: Springer-Verlag, 1980, pp. 72-98. [Online]. Available: https://link.springer.com/chapter/10.1007/978-3-642-51576-7_6.

Cited By

Özdağ R(2025)A novel hybrid path planning method for sweep coverage of multiple UAVsThe Journal of Supercomputing10.1007/s11227-024-06574-z81:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06574-z
Sen RKhatua SDas R(2024)Cost Efficient Mobile Trajectory Planning in Barrier Sweep CoverageProceedings of the 2024 Sixteenth International Conference on Contemporary Computing10.1145/3675888.3676121(618-627)Online publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1145/3675888.3676121
Huang LYu WLiu Z(2024)Approximation Algorithms for the Min–Max Mixed Rural Postmen Cover Problem and Its VariantsAlgorithmica10.1007/s00453-023-01187-z86:4(1135-1162)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-023-01187-z
Show More Cited By

Approximation Algorithms for Sweep Coverage Problem With Multiple Mobile Sensors
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis

Recommendations

Cooperative Sweep Coverage Problem With Mobile Sensors
Sweep coverage plays an important role in many applications such as data gathering, sensing coverage and devices control. In this paper, we deal with the cooperative sweep coverage problem with multiple mobile sensors to periodically cover all positions ...
On Sweep Coverage with Minimum Mobile Sensors
ICPADS '10: Proceedings of the 2010 IEEE 16th International Conference on Parallel and Distributed Systems

For some sensor network applications, the problem of sweep coverage, which periodically covers POIs (Points of Interest) to sense events, is of importance. How to schedule minimum number of mobile sensors to achieve the sweep coverage within specified ...
Data Ferry Trajectory Planning for Sweep Coverage Problem with Multiple Mobile Sensors
2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON)
Sweep coverage plays an important role in many applications like data gathering, sensing coverage, and devices control, etc. In this paper, we deal with sweep coverage problem with multiple mobile sensors to periodically cover n targets in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 26, Issue 2

April 2018

377 pages

ISSN:1063-6692

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 01 April 2018

Published in TON Volume 26, Issue 2

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
129
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Özdağ R(2025)A novel hybrid path planning method for sweep coverage of multiple UAVsThe Journal of Supercomputing10.1007/s11227-024-06574-z81:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06574-z
Sen RKhatua SDas R(2024)Cost Efficient Mobile Trajectory Planning in Barrier Sweep CoverageProceedings of the 2024 Sixteenth International Conference on Contemporary Computing10.1145/3675888.3676121(618-627)Online publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1145/3675888.3676121
Huang LYu WLiu Z(2024)Approximation Algorithms for the Min–Max Mixed Rural Postmen Cover Problem and Its VariantsAlgorithmica10.1007/s00453-023-01187-z86:4(1135-1162)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-023-01187-z
Sun YYu WLiu Z(2023)Approximation algorithms for some min–max and minimum stacker crane cover problemsJournal of Combinatorial Optimization10.1007/s10878-022-00955-x45:1Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1007/s10878-022-00955-x
Gao XFan JWu FChen G(2022)Cooperative Sweep Coverage Problem With Mobile SensorsIEEE Transactions on Mobile Computing10.1109/TMC.2020.300834821:2(480-494)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1109/TMC.2020.3008348
He SShi KLiu CGuo BChen JShi Z(2022)Collaborative Sensing in Internet of Things: A Comprehensive SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2022.318713824:3(1435-1474)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1109/COMST.2022.3187138
Huang LYu WLiu Z(2022)Approximation Algorithms for the Min-Max Mixed Rural Postmen Cover Problem and Its VariantsComputing and Combinatorics10.1007/978-3-031-22105-7_4(36-48)Online publication date: 22-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-22105-7_4
Das SKapelko R(2021)On the Range Assignment in Wireless Sensor Networks for Minimizing the Coverage-Connectivity CostACM Transactions on Sensor Networks10.1145/345740817:4(1-48)Online publication date: 10-Aug-2021
https://dl.acm.org/doi/10.1145/3457408
Sun YYu WLiu Z(2021)Approximation Algorithms for Some Min-Max and Minimum Stacker Crane Cover ProblemsCombinatorial Optimization and Applications10.1007/978-3-030-92681-6_32(400-415)Online publication date: 17-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-030-92681-6_32
Kapelko R(2020)On the Energy in Displacement of Random Sensors for Connectivity and InterferenceProceedings of the 21st International Conference on Distributed Computing and Networking10.1145/3369740.3369768(1-10)Online publication date: 4-Jan-2020
https://dl.acm.org/doi/10.1145/3369740.3369768
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents