{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T15:06:51Z","timestamp":1721401611671},"reference-count":15,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,1,11]],"date-time":"2019-01-11T00:00:00Z","timestamp":1547164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772005"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"Given a set of sensors distributed on the plane and a set of Point of Interests (POIs) on a line segment, a primary task of the mobile wireless sensor network is to schedule covering the POIs by the sensors, such that each POI is monitored by at least one sensor. For balancing the energy consumption, we study the min-max line barrier target coverage (LBTC) problem which aims to minimize the maximum movement of the sensors from their original positions to their final positions at which the coverage is composed. We first proved that when the radius of the sensors are non-uniform integers, even 1-dimensional LBTC (1D-LBTC), a special case of LBTC in which the sensors are distributed on the line segment instead of the plane, is NP -hard. The hardness result is interesting, since the continuous version of LBTC to cover a given line segment instead of the POIs is known polynomial solvable. Then we present an exact algorithm for LBTC with uniform radius and sensors distributed on the plane, via solving the decision version of LBTC. We argue that our algorithm runs in time O ( n 2 log n ) and produces an optimal solution to LBTC. The time complexity compares favorably to the state-of-art runtime O ( n 3 log n ) of the continuous version which aims to cover a line barrier instead of the targets. Last but not the least, we carry out numerical experiments to evaluate the practical performance of the algorithms, which demonstrates a practical runtime gain comparing with an optimal algorithm based on integer linear programming.<\/jats:p>","DOI":"10.3390\/s19020273","type":"journal-article","created":{"date-parts":[[2019,1,11]],"date-time":"2019-01-11T16:36:42Z","timestamp":1547224602000},"page":"273","source":"Crossref","is-referenced-by-count":5,"title":["Optimizing Movement for Maximizing Lifetime of Mobile Sensors for Covering Targets on a Line"],"prefix":"10.3390","volume":"19","author":[{"given":"Peihuang","family":"Huang","sequence":"first","affiliation":[{"name":"College of Physics and Information Engineering, Fuzhou University, Fuzhou 350116, China"}]},{"given":"Wenxing","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China"}]},{"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[{"name":"College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China"}]}],"member":"1968","published-online":{"date-parts":[[2019,1,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/1394555.1394565","article-title":"Localized sensor self-deployment with coverage guarantee","volume":"Volume 12","author":"Li","year":"2008","journal-title":"ACM SIGMOBILE Mobile Computing and Communications Review"},{"key":"ref_2","unstructured":"Kumar, S., Lai, T.H., and Arora, A. (September, January 28). Barrier coverage with wireless sensors. Proceedings of the 11th Annual International Conference on Mobile Computing and Networking, Cologne, Germany."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gage, D.W. (1992). Command Control for Many-Robot Systems, The Research, Development, Test & Evaluation (RDT&E) Infrastructure Division of Naval Command Control and Ocean Surveillance Center. Technical Report.","DOI":"10.21236\/ADA422540"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., and Yazdani, M. (2009, January 22\u201325). On minimizing the maximum sensor movement for barrier coverage of a line segment. Proceedings of the International Conference on Ad-Hoc Networks and Wireless, Murcia, Spain.","DOI":"10.1007\/978-3-642-04383-3_15"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/s00454-013-9525-x","article-title":"Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain","volume":"50","author":"Chen","year":"2013","journal-title":"Discret. Comput. Geom."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"5515","DOI":"10.1016\/j.tcs.2009.07.007","article-title":"Optimal movement of mobile sensors for barrier coverage of a planar region","volume":"410","author":"Bhattacharya","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tan, X., and Wu, G. (2010, January 11\u201313). New algorithms for barrier coverage with mobile sensors. Proceedings of the International Workshop on Frontiers in Algorithmics, Wuhan, China.","DOI":"10.1007\/978-3-642-14553-7_31"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.tcs.2015.02.006","article-title":"Complexity of barrier coverage with relocatable sensors in the plane","volume":"579","author":"Dobrev","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","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), Kowloon, Hong Kong, China.","DOI":"10.1109\/INFOCOM.2015.7218388"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., and Yazdani, M. (2010, January 20\u201322). On minimizing the sum of sensor movements for barrier coverage of a line segment. Proceedings of the International Conference on Ad-Hoc Networks and Wireless, Edmonton, AB, Canada.","DOI":"10.1007\/978-3-642-14785-2_3"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Mehrandish, M., Narayanan, L., and Opatrny, J. (2011, January 28\u201331). Minimizing the number of sensors moved on line barriers. Proceedings of the 2011 IEEE Wireless Communications and Networking Conference (WCNC), Cancun, Quintana Roo, Mexico.","DOI":"10.1109\/WCNC.2011.5779210"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Cherry, A., Gudmundsson, J., and Mestre, J. (2017, January 4\u20138). Barrier Coverage with Uniform Radii in 2D. Proceedings of the International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Vienna, Austria.","DOI":"10.1007\/978-3-319-72751-6_5"},{"key":"ref_13","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_14","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to NP-Completeness, W. H. Freeman and Company."},{"key":"ref_15","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/2\/273\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T11:42:28Z","timestamp":1718451748000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/2\/273"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,11]]},"references-count":15,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,1]]}},"alternative-id":["s19020273"],"URL":"https:\/\/doi.org\/10.3390\/s19020273","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,11]]}}}