Algorithms on minimizing the maximum sensor movement for barrier coverage of a linear domain. (English) Zbl 1298.68276
Summary: In this paper, we study the problem of moving \(n\) sensors on a line to form a barrier coverage of a specified segment of the line such that the maximum moving distance of the sensors is minimized. Previously, it was an open question whether this problem on sensors with arbitrary sensing ranges is solvable in polynomial time. We settle this open question positively by giving an \(O(n^2 \log n)\) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes \(O(n^2)\) time. We present an \(O(n \log n)\) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes \(O(n)\) time. Also, we extend our techniques to the cycle version of the problem where the barrier coverage is for a simple cycle and the sensors are allowed to move only along the cycle. For sensors with the same-size sensing range, we solve the cycle version in \(O(n)\) time, improving the previously best \(O(n^2)\) time solution.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52B55 | Computational aspects related to convexity |
| 52C17 | Packing and covering in \(n\) dimensions (aspects of discrete geometry) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 94A05 | Communication theory |
References:
| [1] | Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Comput. Netw. 38(4), 393-422 (2002) · doi:10.1016/S1389-1286(01)00302-4 |
| [2] | Bhattacharya, B., Burmester, B., 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) · Zbl 1192.68816 · doi:10.1016/j.tcs.2009.07.007 |
| [3] | Chen, A., Kumar, S., Lai T.: Designing localized algorithms for barrier coverage. In: Proceedings of the 13th Annual ACM International Conference on Mobile Computing and Networking, pp. 63-73 (2007) |
| [4] | Chen, D.Z., Wang, C., Wang, H.: Representing a functional curve by curves with fewer peaks. Discrete Comput. Geom. 46(2), 334-360 (2011) · Zbl 1219.68157 · doi:10.1007/s00454-011-9338-8 |
| [5] | Chen, D.Z., Tan, X., Wang, H., Wu, G.: Optimal point movement for covering circular regions. In: Proceedings of the 23rd International Symposium on Algorithms and Computation, pp. 332-341 (2012) · Zbl 1260.68408 |
| [6] | Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. J. ACM 34(1), 200-208 (1987) · Zbl 1378.68037 · doi:10.1145/7531.7537 |
| [7] | Cole, R., Salowe, J., Steiger, W., Szemerédi, E.: An optimal-time algorithm for slope selection. SIAM J. Comput. 18(4), 792-810 (1989) · Zbl 0678.68033 · doi:10.1137/0218055 |
| [8] | 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 the 8th International Conference on Ad-Hoc, Mobile and Wireless Networks. Lecture Notes in Computer Science, vol. 5793, pp. 194-212. Springer, Heidelberg (2009) |
| [9] | 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 the 9th International Conference on Ad-Hoc, Mobile and Wireless Networks. Lecture Notes in Computer Science, vol. 6288, pp. 29-42. Springer, Heidelberg (2010) |
| [10] | Hu, S.: ‘Virtual Fence’ along border to be delayed. Washington Post, February 28, (2008) |
| [11] | Kumar, S., Lai, T., Arora, A.: Barrier coverage with wireless sensors. Wirel. Netw. 13(6), 817-834 (2007) · doi:10.1007/s11276-006-9856-0 |
| [12] | Li, X., Frey, H., Santoro, N., Stojmenovic, I.: Localized sensor self-deployment with coverage guarantee. ACM SIGMOBILE Mobile Comput. Commun. Rev. 12(2), 50-52 (2008) · doi:10.1145/1394555.1394565 |
| [13] | Li, M., Sun, X., Zhao, Y.: Minimum-cost linear coverage by sensors with adjustable ranges. In Proceedings of the 6th International Conference on Wireless Algorithms, Systems, and Applications, pp. 25-35 (2011) |
| [14] | Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852-865 (1983) · Zbl 0627.68034 · doi:10.1145/2157.322410 |
| [15] | Mehrandish, M.: On routing, backbone formation and barrier coverage in wireless ad doc and sensor networks. PhD thesis, Concordia University, Montreal, QC, Canada. http://spectrum.library.concordia.ca/7326/1/Mehrandish_PhD_S2011.pdf (2011) |
| [16] | Mehrandish, M., Narayanan, L., Opatrny, J.: Minimizing the number of sensors moved on line barriers. In: Proceedings of IEEE, Wireless Communications and Networking Conference, pp. 653-658 (2011) |
| [17] | Tan, X., Wu, G.: New algorithms for barrier coverage with mobile sensors. In: Proceedings of the 4th International Workshop on Frontiers in Algorithmics. Lecture Notes in Computer Science, vol. 6213, pp. 327-338. Springer, Heidelberg (2010) · Zbl 1288.68234 |
| [18] | Yang, S., Li, M., Wu, J.: Scan-based movement-assisted sensor deployment methods in wireless sensor networks. IEEE Trans. Parallel Distrib. Syst. 18(8), 1108-1121 (2007) · doi:10.1109/TPDS.2007.1048 |
| [19] | Zou, Y., Chakrabarty, K.: A distributed coverage and connectivity-centric technique for selecting active nodes in wireless sensor networks. IEEE Trans. Comput. 54(8), 978-991 (2005) · doi:10.1109/TC.2005.123 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
