{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,26]],"date-time":"2026-06-26T12:06:13Z","timestamp":1782475573038,"version":"3.54.5"},"reference-count":39,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T00:00:00Z","timestamp":1609200000000},"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>We formulate and analyze a generic coverage optimization problem arising in wireless sensor networks with sensors of limited mobility. Given a set of targets to be covered and a set of mobile sensors, we seek a sensor dispatch algorithm maximizing the covered targets under the constraint that the maximal moving distance for each sensor is upper-bounded by a given threshold. We prove that the problem is NP-hard. Given its hardness, we devise four algorithms to solve it heuristically or approximately. Among the approximate algorithms, we first develop randomized (1\u22121\/e)-optimal algorithm. We then employ a derandomization technique to devise a deterministic (1\u22121\/e)-approximation algorithm. We also design a deterministic approximation algorithm with nearly \u25b5\u22121 approximation ratio by using a colouring technique, where \u25b5 denotes the maximal number of subsets covering the same target. Experiments are also conducted to validate the effectiveness of the algorithms in a variety of parameter settings.<\/jats:p>","DOI":"10.3390\/s21010184","type":"journal-article","created":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T19:55:25Z","timestamp":1609271725000},"page":"184","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":36,"title":["Maximum Target Coverage Problem in Mobile Wireless Sensor Networks"],"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 510006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hong","family":"Shen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lin","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1109\/TPDS.2013.30","article-title":"Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks","volume":"25","author":"Hackmann","year":"2013","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_2","first-page":"115","article-title":"A wheelchair control system using human-machine interaction: Singlemodal and multimodal approaches","volume":"28","author":"Shahin","year":"2019","journal-title":"J. Intell. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s11276-015-1133-7","article-title":"A review of industrial wireless networks in the context of industry 4.0","volume":"23","author":"Li","year":"2017","journal-title":"Wirel. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1214","DOI":"10.1109\/TIM.2017.2771979","article-title":"Wireless sensor network for distributed environmental monitoring","volume":"67","author":"Lombardo","year":"2017","journal-title":"IEEE Trans. Instrum. Meas."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Roy, A., and Sarma, N. (2020). A synchronous duty-cycled reservation based MAC protocol for underwater wireless sensor networks. Digit. Commun. Netw.","DOI":"10.1016\/j.dcan.2020.09.002"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Pawgasame, W. (2016, January 21\u201323). A survey in adaptive hybrid wireless sensor network for military operations. Proceedings of the 2016 Second Asian Conference on Defence Technology (ACDT), Chiang Mai, Thailand.","DOI":"10.1109\/ACDT.2016.7437647"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Shakila, R., and Paramasivan, B. (2020). Performance Analysis of Submarine Detection in Underwater Wireless Sensor Networks for Naval Application. Microprocess. Microsyst.","DOI":"10.1016\/j.micpro.2020.103293"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2056","DOI":"10.1109\/TIM.2017.2677619","article-title":"Analysis of three IoT-based wireless sensors for environmental monitoring","volume":"66","author":"Mois","year":"2017","journal-title":"IEEE Trans. Instrum. Meas."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.jclepro.2014.04.036","article-title":"Environmental parameters monitoring in precision agriculture using wireless sensor networks","volume":"88","author":"Srbinovska","year":"2015","journal-title":"J. Clean. Prod."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"7126","DOI":"10.1109\/JSEN.2015.2471837","article-title":"Regular Node Deployment for k-Coverage in m-Connected Wireless Networks","volume":"15","author":"Gupta","year":"2015","journal-title":"IEEE Sens. J."},{"key":"ref_11","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_12","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/CC.2016.7489970","article-title":"Efficient algorithm for k-barrier coverage based on integer linear programming","volume":"13","author":"Zhang","year":"2016","journal-title":"China Commun."},{"key":"ref_13","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_14","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_15","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_16","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_17","doi-asserted-by":"crossref","unstructured":"Liao, Z., Zhang, S., Cao, J., Wang, W., and Wang, J. (2012, January 18\u201321). Minimizing movement for target coverage in mobile sensor networks. Proceedings of the 2012 32nd International Conference on Distributed Computing Systems Workshops, Macau, China.","DOI":"10.1109\/ICDCSW.2012.38"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.comcom.2017.06.010","article-title":"Coverage in mobile wireless sensor networks (M-WSN)","volume":"110","author":"Mohamed","year":"2017","journal-title":"Comput. Commun."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.comnet.2017.05.008","article-title":"Coverage problem with uncertain properties in wireless sensor networks: A survey","volume":"123","author":"Wang","year":"2017","journal-title":"Comput. Netw."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1109\/JCN.2019.000005","article-title":"Coverage protocols for wireless sensor networks: Review and future directions","volume":"21","author":"Elhabyan","year":"2019","journal-title":"J. Commun. Netw."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1504\/IJAACS.2017.088774","article-title":"Survey of deployment algorithms in wireless sensor networks: Coverage and connectivity issues and challenges","volume":"10","author":"Khoufi","year":"2017","journal-title":"Int. J. Auton. Adapt. Commun. Syst."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"834","DOI":"10.1109\/SURV.2013.091213.00018","article-title":"Classification of wireless sensor networks deployment techniques","volume":"16","author":"Deif","year":"2013","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Shi, T., Li, J.Z., Gao, H., and Cai, Z.P. (2018, January 16\u201319). Coverage in Battery-Free Wireless Sensor Networks. Proceedings of the IEEE Conference on Computer Communications (IEEE Infocom 2018), Honolulu, HI, USA.","DOI":"10.1109\/INFOCOM.2018.8485808"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Lin, C., Zhou, Y., Ma, F., Deng, J., Wang, L., and Wu, G. (May, January 29). Minimizing charging delay for directional charging in wireless rechargeable sensor networks. Proceedings of the IEEE INFOCOM 2019-IEEE Conference on Computer Communications, Paris, France.","DOI":"10.1109\/INFOCOM.2019.8737589"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Shi, T., Cheng, S., Li, J., and Cai, Z. (2017, January 1\u20134). Constructing connected dominating sets in battery-free networks. Proceedings of the IEEE INFOCOM 2017-IEEE Conference on Computer Communications, Atlanta, GA, USA.","DOI":"10.1109\/INFOCOM.2017.8057073"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Wang, C., Li, J., Yang, Y., and Ye, F. (2016, January 10\u201314). A hybrid framework combining solar energy harvesting and wireless charging for wireless sensor networks. Proceedings of the IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524337"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Wu, T., Yang, P., Dai, H., Xu, W., and Xu, M. (May, January 29). Charging oriented sensor placement and flexible scheduling in rechargeable WSNs. Proceedings of the IEEE INFOCOM 2019-IEEE Conference on Computer Communications, Paris, France.","DOI":"10.1109\/INFOCOM.2019.8737502"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Shi, T., Cheng, S., Cai, Z., and Li, J. (2016, January 10\u201314). Adaptive connected dominating set discovering algorithm in energy-harvest sensor networks. Proceedings of the IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524504"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1016\/j.compeleceng.2015.11.009","article-title":"Genetic algorithm approach for k -coverage and m -connected node placement in target based wireless sensor networks","volume":"56","author":"Gupta","year":"2016","journal-title":"Comput. Electr. Eng."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.aeue.2018.03.031","article-title":"Optimized mobile sink based grid coverage-aware sensor deployment and link quality based routing in wireless sensor networks","volume":"89","author":"Dahiya","year":"2018","journal-title":"AEU-Int. J. Electron. Commun."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.adhoc.2017.04.001","article-title":"Maximizing the wireless sensor networks lifetime through energy efficient connected coverage","volume":"62","author":"Roselin","year":"2017","journal-title":"Ad Hoc Netw."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1002\/dac.3040","article-title":"Static wireless sensor networks deployment using an improved binary PSO","volume":"29","author":"Senouci","year":"2016","journal-title":"Int. J. Commun. Syst."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1971","DOI":"10.1109\/TPDS.2014.2333011","article-title":"Minimizing movement for target coverage and network connectivity in mobile sensor networks","volume":"26","author":"Liao","year":"2015","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Chen, Z., Gao, X., Wu, F., and Chen, G. (2016, January 10\u201314). A PTAS to minimize mobile sensor movement for target coverage problem. Proceedings of the INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, San Francisco, CA, USA.","DOI":"10.1109\/INFOCOM.2016.7524334"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"10803","DOI":"10.1109\/ACCESS.2018.2801941","article-title":"Coverage of targets in mobile sensor networks with restricted mobility","volume":"6","author":"Choudhuri","year":"2018","journal-title":"IEEE Access"},{"key":"ref_36","unstructured":"Nguyen, N., Liu, B., and Wang, S. (2018). On New Approaches of Maximum Weighted Target Coverage and Sensor Connectivity: Hardness and Approximation. arXiv."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1109\/JSYST.2018.2828879","article-title":"The Mobile Sensor Deployment Problem and the Target Coverage Problem in Mobile Wireless Sensor Networks are NP-Hard","volume":"13","author":"Nguyen","year":"2019","journal-title":"IEEE Syst. J."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","article-title":"Approximation schemes for covering and packing problems in image processing and VLSI","volume":"32","author":"Hochbaum","year":"1985","journal-title":"J. ACM"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539799354138","article-title":"Approximating the Throughput of Multiple Machines in Real-Time Scheduling","volume":"31","author":"Barnoy","year":"2002","journal-title":"SIAM J. Comput."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/1\/184\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:47:37Z","timestamp":1760179657000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/1\/184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,29]]},"references-count":39,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,1]]}},"alternative-id":["s21010184"],"URL":"https:\/\/doi.org\/10.3390\/s21010184","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,29]]}}}