Abstract
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. Each sensor can monitor a circular area of specific diameter around its position, called the sensor diameter. Sensors are required to move to final locations so that they can there detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak barrier coverage of the region. We study three optimization problems related to the movement of sensors to achieve weak barrier coverage: minimizing the number of sensors moved (MinNum), minimizing the average distance moved by the sensors (MinSum), and minimizing the maximum distance moved by any sensor (MinMax). We give an \(O(n^{3/2})\) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast the problem is shown to be NP-complete even for sensors of diameter 2 that are initially placed at integer positions. We show that the MinSum problem is solvable in \(O(n \log n)\) time for the Manhattan metric and sensors of identical diameter (homogeneous sensors) in arbitrary initial positions, while it is NP-complete for heterogeneous sensors. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-complete.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andrews, A.M., Wang, H.: Minimizing the aggregate movements for interval coverage. Algorithmica 78(1), 48–85 (2017)
Balister, P., Bollobas, B., Sarkar, A., Kumar, S.: Reliable density estimates for coverage and connectivity in thin strips of finite length. In: ACM International Conference on Mobile Computing and Networking, pp. 75–86 (2007)
Ban, D., Jiang, J., Yang, W., Dou, W., Yi, H.: Strong k-barrier coverage with mobile sensors. In: Proceedings of International Wireless Communications and Mobile Computing Conference, pp. 68–72 (2010)
Berman, P., Karpinski, M.: On some tighter inapproximability results. In: Proceedings of ICALP 1999, LNCS, vol. 1644, pp. 200–209 (1999)
Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. Technical Report TR03-049, ECCC (2003)
Bhattacharya, B., Burmester, M., Hu, Y., Kranakis, E., Shi, Q., Wiese, A.: Optimal movement of mobile sensors for barrier coverage of a planar region. Theor. Comput. Sci. 410(52), 5515–5528 (2009)
Chen, D., Gu, Y., Li, J., Wang, H.: Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. Discrete Comput. Geom. 50, 374–408 (2013)
Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the maximum sensor movement for barrier coverage of a line segment. In: Proceedings of ADHOCNOW, LNCS, vol. 5793, pp. 194–212. Springer (2009)
Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Proceedings of ADHOCNOW, LNCS, vol. 6288, pp. 29–42. Springer (2010)
Dobrev, S., Durocher, S., Eftekhari, M., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S., Urrutia, J.: Complexity of barrier coverage with relocatable sensors in the plane. Theor. Comput. Sci. 579, 64–73 (2015)
Dobrev, S., Kranakis, E., Krizanc, D., Lafond, M., Maňuch, J., Narayanan, L., Opatrny, J., Stacho, L.: Weak coverage of a rectangular barrier. In: Proceedings of CIAC 2017 Conference, LNCS, vol. 10236, pp. 196–208 (2017)
Eftekhari, M., Flocchini, P., Narayanan, L., Opatrny, J., Santoro, N.: Distributed barrier coverage with relocatable sensors. In: Proceedings of Sirocco 2014 Conference, LNCS, vol. 8576, pp. 235–249 (2014)
Eftekhari, M., Kranakis, E., Krizanc, D., Morales-Ponce, O., Narayanan, L., Opatrny, J., Shende, S.: Distributed algorithms for barrier coverage using relocatable sensors. Distrib. Comput. 29(5), 361–376 (2016)
Eftekhari, M., Narayanan, L., Opatrny, J.: On multi-round sensor deployment for barrier coverage. In: Proceedings of 10th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (IEEE MASS), pp. 310–318 (2013)
Habib, M.: Stochastic barrier coverage in wireless sensor networks based on distributed learning automata. Comput. Commun. 55, 51–61 (2015)
Kranakis, E., Krizanc, D., Luccio, F.L., Smith, B.: Maintaining intruder detection capability in a rectangular domain with sensors. In: Proceedings of ALGOSENSORS 2015, LNCS, vol. 9536, pp. 27–40 (2015)
Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of the 11th ACM International Conference on Mobile Computing and Networking, pp. 284–298 (2005)
Li, L., Zhang, B., Shen, X., Zheng, J., Yao, Z.: A study on the weak barrier coverage problem in wireless sensor networks. Comput. Netw. 55, 711–721 (2011)
Li, X., Frey, H., Santoro, N., Stojmenovic, I.: Strictly localized sensor self-deployment for optimal focused coverage. IEEE Trans. Mob. Comput. 10(11), 1520–1533 (2011)
Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proceedings of IEEE WCNC, pp. 653–658 (2011)
Yan, G., Qiao, D.: Multi-round sensor deployment for guaranteed barrier coverage. In: Proceedings of IEEE INFOCOM’10, pp. 2462–2470 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
An extended abstract of this paper appeared in CIAC 2017 [11]. Research supported in part by NSERC grants, Canada, and a VEGA grant, Slovakia.
Rights and permissions
About this article
Cite this article
Dobrev, S., Kranakis, E., Krizanc, D. et al. Weak Coverage of a Rectangular Barrier. Algorithmica 82, 721–746 (2020). https://doi.org/10.1007/s00453-019-00611-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-019-00611-7