{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T15:43:06Z","timestamp":1767973386948,"version":"3.49.0"},"reference-count":32,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T00:00:00Z","timestamp":1613692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>As an important application of wireless sensor networks (WSNs), deployment of mobile sensors to periodically monitor (sweep cover) a set of points of interest (PoIs) arises in various applications, such as environmental monitoring and data collection. For a set of PoIs in an Eulerian graph, the point sweep coverage problem of deploying the fewest sensors to periodically cover a set of PoIs is known to be Non-deterministic Polynomial Hard (NP-hard), even if all sensors have the same velocity. In this paper, we consider the problem of finding the set of PoIs on a line periodically covered by a given set of mobile sensors that has the maximum sum of weight. The problem is first proven NP-hard when sensors are with different velocities in this paper. Optimal and approximate solutions are also presented for sensors with the same and different velocities, respectively. For M sensors and N PoIs, the optimal algorithm for the case when sensors are with the same velocity runs in O(MN) time; our polynomial-time approximation algorithm for the case when sensors have a constant number of velocities achieves approximation ratio 12; for the general case of arbitrary velocities, 12\u03b1 and 12(1\u22121\/e) approximation algorithms are presented, respectively, where integer \u03b1\u22652 is the tradeoff factor between time complexity and approximation ratio.<\/jats:p>","DOI":"10.3390\/s21041457","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T20:54:08Z","timestamp":1613768048000},"page":"1457","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Algorithms for Max-Weighted Point Sweep Coverage on Lines"],"prefix":"10.3390","volume":"21","author":[{"given":"Dieyan","family":"Liang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510275, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Shen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510275, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1736","DOI":"10.1109\/TNSE.2019.2952369","article-title":"On new approaches of maximum weighted target coverage and sensor connectivity: Hardness and approximation","volume":"7","author":"Nguyen","year":"2019","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Liang, D., Shen, H., and Chen, L. (2021). Maximum Target Coverage Problem in Mobile Wireless Sensor Networks. Sensors, 21.","DOI":"10.3390\/s21010184"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.engappai.2016.03.004","article-title":"Wireless sensors deployment optimization using a constrained Pareto-based multi-objective evolutionary approach","volume":"53","author":"Khalesian","year":"2016","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1109\/TPDS.2013.35","article-title":"Surface coverage in sensor networks","volume":"25","author":"Kong","year":"2014","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Li, S., and Shen, H. (May, January 26). Minimizing the maximum sensor movement for barrier coverage in the plane. Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China.","DOI":"10.1109\/INFOCOM.2015.7218388"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1109\/TMC.2016.2606403","article-title":"Maximum lifetime combined barrier-coverage of weak static sensors and strong mobile sensors","volume":"16","author":"Kim","year":"2016","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"3469","DOI":"10.1109\/TWC.2019.2914199","article-title":"Movement-Efficient Sensor Deployment in Wireless Sensor Networks With Limited Communication Range","volume":"18","author":"Guo","year":"2019","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3616","DOI":"10.1109\/TNET.2017.2756925","article-title":"Energy Efficient Algorithms for k -Sink Minimum Movement Target Coverage Problem in Mobile Sensor Network","volume":"25","author":"Gao","year":"2017","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.eswa.2017.09.008","article-title":"Optimizing K-coverage of mobile WSNs","volume":"92","author":"Elhoseny","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Cinque, M., Cotroneo, D., Di Martino, C., Russo, S., and Testa, A. (2009, January 23\u201329). Avr-inject: A tool for injecting faults in wireless sensor nodes. Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing, Rome, Italy.","DOI":"10.1109\/IPDPS.2009.5160907"},{"key":"ref_11","unstructured":"Cheng, W., Li, M., Liu, K., Liu, Y., Li, X., and Liao, X. (2008, January 14\u201318). Sweep coverage with mobile sensors. Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing, Miami, FL, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1007\/s11280-017-0481-x","article-title":"Participant selection for t-sweep k-coverage crowd sensing tasks","volume":"21","author":"Yu","year":"2017","journal-title":"World Wide Web"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"484902","DOI":"10.1155\/2015\/484902","article-title":"ACO-Based Sweep Coverage Scheme in Wireless Sensor Networks","volume":"2015","author":"Huang","year":"2015","journal-title":"J. Sens."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"8967","DOI":"10.1109\/JIOT.2020.2999083","article-title":"A Path Planning Method for Sweep Coverage With Multiple UAVs","volume":"7","author":"Li","year":"2020","journal-title":"IEEE Internet Things J."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"10686","DOI":"10.1109\/JIOT.2019.2940717","article-title":"A Task Assignment Method for Sweep Coverage Optimization Based on Crowdsensing","volume":"6","author":"Wu","year":"2019","journal-title":"IEEE Internet Things J."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"712","DOI":"10.1016\/j.ipl.2015.03.011","article-title":"Approximation algorithm for sweep coverage on graph","volume":"115","author":"Gorain","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Du, J., Li, Y., Liu, H., and Sha, K. (2010, January 8\u201310). On sweep coverage with minimum mobile sensors. Proceedings of the 2010 IEEE 16th International Conference on Parallel and Distributed Systems, Shanghai, China.","DOI":"10.1109\/ICPADS.2010.109"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2699","DOI":"10.1016\/j.jpdc.2014.02.009","article-title":"Approximation algorithms for sweep coverage in wireless sensor networks","volume":"74","author":"Gorain","year":"2014","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Gorain, B., and Mandal, P.S. (2014, January 6\u201310). Line sweep coverage in wireless sensor networks. Proceedings of the 2014 Sixth International Conference on Communication Systems and Networks (COMSNETS), Bangalore, India.","DOI":"10.1109\/COMSNETS.2014.6734885"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Chen, Z., Zhu, X., Gao, X., Wu, F., Gu, J., and Chen, G. (2016, January 27\u201330). Efficient Scheduling Strategies for Mobile Sensors in Sweep Coverage Problem. Proceedings of the 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), London, UK.","DOI":"10.1109\/SAHCN.2016.7732985"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/j.dam.2016.09.028","article-title":"Solving energy issues for sweep coverage in wireless sensor networks","volume":"228","author":"Gorain","year":"2017","journal-title":"Discret. Appl. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1142\/S0129054119500138","article-title":"Approximation Algorithms for Barrier Sweep Coverage","volume":"30","author":"Gorain","year":"2019","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Ga\u0327sieniec, L., Kosowski, A., and Kranakis, E. (2011). Boundary patrolling by mobile agents with distinct maximal speeds. European Symposium on Algorithms, Springer.","DOI":"10.1007\/978-3-642-23719-5_59"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Ghosh, A., and T\u00f3th, C.D. (2014). On fence patrolling by mobile agents. arXiv.","DOI":"10.37236\/4063"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00446-014-0226-3","article-title":"Fence patrolling by mobile agents with distinct speeds","volume":"28","author":"Kawamura","year":"2015","journal-title":"Distrib. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Kawamura, A., and Soejima, M. (2015). Simple strategies versus optimal schedules in multi-agent patrolling. International Conference on Algorithms and Complexity, Springer.","DOI":"10.1007\/978-3-319-18173-8_19"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"592","DOI":"10.1109\/TRO.2011.2179580","article-title":"On cooperative patrolling: Optimal trajectories, complexity analysis, and approximation algorithms","volume":"28","author":"Pasqualetti","year":"2012","journal-title":"IEEE Trans. Robot."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Collins, A., Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Martin, R., and Morales Ponce, O. (2013, January 23\u201325). Optimal patrolling of fragmented boundaries. Proceedings of the Twenty-Fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures, Montreal, QC, Canada.","DOI":"10.1145\/2486159.2486176"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1109\/TNET.2018.2815630","article-title":"Approximation Algorithms for Sweep Coverage Problem With Multiple Mobile Sensors","volume":"26","author":"Gao","year":"2018","journal-title":"IEEE-Acm Trans. Netw."},{"key":"ref_30","unstructured":"Gao, X., Fan, J., Wu, F., and Chen, G. (2020). Cooperative Sweep Coverage Problem with Mobile Sensors. IEEE Trans. Mob. Comput."},{"key":"ref_31","unstructured":"Gary, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Williamson, D.P., and Shmoys, D.B. (2011). The Design of Approximation Algorithms, Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1457\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:26:20Z","timestamp":1760160380000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,19]]},"references-count":32,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["s21041457"],"URL":"https:\/\/doi.org\/10.3390\/s21041457","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,19]]}}}