查看文章

We study the problem of barrier coverage with a wireless sensor network. Each sensor is modelled by a point in the plane and a sensing disk or coverage area centered at the sensor's position. The barriers are usually modelled as a set of line segments on the plane. The barrier coverage problem is to add new sensors or move existing sensors on the barriers such that every point on every barrier is within the coverage area of some sensors. Barrier coverage using sensors has important applications, including intruder detection or monitoring the perimeter of a region. Given a set of barriers and a set of sensors initially located at general positions in the plane, we study three problems for relocatable sensors in the centralized setting: the feasibility problem, and the problems of minimizing the maximum or the average relocation distances of sensors (MinMax and MinSum respectively) for barrier coverage. We show that the MinMax problem is strongly NP-complete when sensors have arbitrary ranges and can move to arbitrary positions on the barrier. We also study the case when sensors are restricted to 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 strongly NP-complete if two perpendicular barriers are to be covered. For the barrier coverage problem in distributed settings, we give the first distributed local algorithms for fully synchronous unoriented sensors. Our algorithms achieve barrier coverage for a line segment barrier when there are enough sensors to cover the …