Algorithms on Minimizing the Maximum Sensor Movement for Barrier Coverage of a Linear Domain |
| |
Authors: | Danny Z Chen Yan Gu Jian Li Haitao Wang |
| |
Institution: | 1. Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN, 46556, USA 2. Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, China 3. Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University, Beijing, 100084, China 4. Department of Computer Science, Utah State University, Logan, UT, 84322, USA
|
| |
Abstract: | In this paper, we study the problem of moving $n$ 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)$ 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)$ O ( n 2 ) time. We present an $O(n\log n)$ 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)$ 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)$ O ( n ) time, improving the previously best $O(n^2)$ O ( n 2 ) time solution. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|