We consider an interval coverage problem. Given @math intervals of the same length on a line @math and a line segment @math on @math , we want to move the intervals along @math such that every point of @math is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in @math time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an @math time algorithm. We also show an @math time lower bound for this problem, which implies the optimality of our algorithm.
Bhattacharya @cite_8 studied a two-dimensional barrier coverage in which the barrier is a circle and the sensors, initially located inside the circle, are moved to the circle to minimize the sensor movements; the ranges of the sensors are not explicitly specified but the destinations of the sensors are required to form a regular @math -gon on the circle. Algorithms for both min-sum and min-max versions were given in @cite_8 and subsequent improvements were made in @cite_5 @cite_6 .
@cite_5 @cite_6 @cite_8
1988777116 2217656054 1603500658 2125242971
In this paper, we study the problem of moving @math 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 @math O(n2logn) time algorithm. For the special case when all sensors have the same-size sensing range, the previously best solution takes @math O(n2) time. We present an @math O(nlogn) time algorithm for this case; further, if all sensors are initially located on the coverage segment, our algorithm takes @math 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 @math O(n) time, improving the previously best @math O(n2) time solution. We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in the plane and they can relocate to the barriers. We assume that each sensor can detect any intruder in a circular area centered at the sensor. Given a set of barriers and a set of sensors located in the plane, we study three problems: the feasibility of barrier coverage, the problem of minimizing the largest relocation distance of a sensor (MinMax), and the problem of minimizing the sum of relocation distances of sensors (MinSum). When sensors are permitted to move to arbitrary positions on the barrier, the problems are shown to be NP-complete. We also study the case when sensors use perpendicular movement to one of the barriers. We show that when the barriers are parallel, both the MinMax and MinSum problems can be solved in polynomial time. In contrast, we show that even the feasibility problem is NP-complete if two perpendicular barriers are to be covered, even if the sensors are located at integer positions, and have only two possible sensing ranges. On the other hand, we give an O(n 3 2) algorithm for a natural special case of this last problem. Monitoring and surveillance are important aspects in modern wireless sensor networks. In applications of wireless sensor networks, it often asks for the sensors to quickly move from the interior of a specified region to the region's perimeter, so as to form a barrier coverage of the region. The region is usually given as a simple polygon or even a circle. In comparison with the traditional concept of full area coverage, barrier coverage requires fewer sensors for detecting intruders, and can thus be considered as a good approximation of full area coverage. In this paper, we present an O(n2.5 log n) time algorithm for moving n sensors to the perimeter of the given circle such that the new positions of sensors form a regular n-gon and the maximum of the distances travelled by mobile sensors is minimized. This greatly improves upon the previous time bound O(n3.5 log n). Also, we describe an O(n4) time algorithm for moving n sensors, whose initial positions are on the perimeter of the circle, to form a regular n-gon such that the sum of the travelled distances is minimized. This solves an open problem posed in [2]. Moreover, our algorithms are simpler and have more explicit geometric flavor. We study the problem of achieving maximum barrier coverage by sensors on a barrier modeled by a line segment, by moving the minimum possible number of sensors, initially placed at arbitrary positions on the line containing the barrier. We consider several cases based on whether or not complete coverage is possible, and whether non-contiguous coverage is allowed in the case when complete coverage is impossible. When the sensors have unequal transmission ranges, we show that the problem of finding a minimum-sized subset of sensors to move in order to achieve maximum contiguous or non-contiguous coverage on a finite line segment barrier is NP-complete. In contrast, if the sensors all have the same range, we give efficient algorithms to achieve maximum contiguous as well as non-contiguous coverage. For some cases, we reduce the problem to finding a maximum-hop path of a certain minimum (maximum) weight on a related graph, and solve it using dynamic programming.