Weak coverage of a rectangular barrier
Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a direction parallel to the sides of the rectangle, and thus provide weak bar-rier 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 the sensors (MinMax). We give an O(n3 /2) time algorithm for the MinNum problem for sensors of diameter 1 that are initially placed at integer positions; in contrast we show that the problem is NP-hard even for sensors of diameter 2 that are initially placed at integer posi-tions. We show that the MinSum problem is solvable in O(n log n) time for homogeneous range sensors in arbitrary initial positions for the Man-hattan metric, while it is NP-hard for heterogeneous sensor ranges for both Manhattan and Euclidean metrics. Finally, we prove that even very restricted homogeneous versions of the MinMax problem are NP-hard.
|Series||Lecture Notes in Computer Science|
Dobrev, S. (Stefan), Kranakis, E, Krizanc, D. (Danny), Lafond, M. (Manuel), Maňnuch, J. (Jan), Narayanan, L. (Lata), … Stacho, L. (Ladislav). (2017). Weak coverage of a rectangular barrier. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-57586-5_17