Abstract

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 entire barrier. Our first algorithm is oblivious and terminates in n^2 time, whereas our second one uses two bits of memory at each sensor, and takes n steps, which is asymptotically optimal. However, if the sensors are semi-synchronous, and do not share the same orientation, we show that no algorithm exists that always terminates within finite time. Finally, for sensors that share the same orientation we give an algorithm that terminates within finite time, even if all sensors are fully asynchronous.

Finally, we study barrier coverage with multi-round random deployment using stationary sensors. We analyze the probability of barrier coverage with uniformly dispersed sensors as a function of parameters such as length of the barrier, the width of the intruder, the sensing range of sensors, as well as the density of deployed sensors. We propose two specific deployment strategies and analyze the expected number of deployment rounds and deployed sensors for each strategy. We present a cost model for multi-round sensor deployments, and for each deployment strategy we find the optimal density of sensors to be deployed in each round that minimizes the total expected cost. Our results are validated by extensive simulations.