Barrier Coverage

Project Goal

The goal of this project is to develop theories and algorithms that can be used for the deployment and maintenance of wireless sensor networks that are deployed in thin strips.

Project Description

In several real–life scenarios,wireless sensors may be deployed in thin strip regions, such as when deploying sensors along international borders to detect illegal intrusion, around forests to detect the spread of forest fire, around a chemical factory to detect the spread of lethal chemicals, or on both sides of a long gas pipeline to detect potential sabotage. Most existing work on coverage and connectivity are not applicable to these strip deployment regions since they often ignore the boundaries of the deployment region. Further, most existing work on coverage and connectivity for random deployments provide only asymptotic results, and do not give reliable numerical conditions for determining the density required for adequate coverage in finite regions.

This project is aimed at establishing a strong foundation for coverage and connectivity when wireless sensors are deployed in thin strip regions. To achieve this goal, this project is investigating the coverage and connectivity properties for three kinds of sensors – omnidirectional sensors, directional sensors (such as lasers and cameras), and mobile sensors. The project uses rigorous mathematical analysis to derive precise numerical estimates for achieving coverage and connectivity for random deployments. It is also investigating optimal algorithms (both centralized and distributed versions) for critical network activities such as coverage/connectivity verification, coverage restoration upon sensor failures, and sleep–wakeup schedule determination for network lifetime maximization.


We observed that if the objective is only to detect a moving object, it is not necessary to cover every point in the deployment region. Several orders of magnitude saving in the number of sensors needed can be achieved if the movement of the object is exploited. Consequently, we defined a new model of coverage called k-barrier Coverage in a MobiCom 2005 paper. A given belt region is said to be k-barrier covered with a sensor network if all crossing paths through the region are k-covered, where a crossing path is any path that crosses the width of the region completely. We proposed efficient algorithms using which one can quickly determine, after deploying the sensors, whether a region is k-barrier covered. Next, we established the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically.  Finally, we considered barrier coverage with high probability when sensors are deployed randomly. We introduced two notions of probabilistic barrier coverage in a belt region - weak and strong barrier coverage. While weak barrier-coverage with high probability guarantees the detection of intruders as they cross a barrier of stealthy sensors, a sensor network providing strong barrier coverage with high probability (at the expense of more sensors) guarantees the detection of all intruders crossing a barrier of sensors, even when the sensors are not stealthy.

In an IEEE BROADNETS 2007 paper, whose extended version was published in IEEE Transactions on Mobile Computing, we developed optimal algorithms to determine the sleeping schedules of wireless sensor deployed for achieving barrier coverage that maximizes the network lifetime. We solved the sleep–wakeup problem for both the homogeneous lifetime case and for the more difficult heterogeneous lifetime case. This is the first time that the sleep–wakeup problem has been solved optimally for any model of coverage in a sensor network.

In a landmark work, published in ACM MobiCom 2007, we showed that strong barrier coverage can indeed be achieved in thin long belt regions. The fact that percolation does not occur in thin strip does not prevent one to derive an estimate of density of sensors needed to achieve strong barrier coverage. We developed a new technique for deriving precise density estimates in random deployments for achieving coverage and connectivity that do not insist on asymptotics and hence yield reliable estimates. These estimates can readily be used in real–life for practical–sized networks, thus bridging the gap between theory and practice. This technique can be applied to other models of coverage, connectivity, and capacity.

In another ACM MobiCom 2007 paper, we introduced a localized model of barrier coverage since the original definition does not permit the checking of the existence of barrier coverage locally by individual or groups of sensors. We showed that this local model of barrier coverage approximates the original model quite well for the sleep–wakeup problem.

More recently, in a paper under review at IEEE INFOCOM 2011, we showed that the sensing range needed to achieve barrier coverage using an orientable directional sensor (including lasers) is asymptotically equivalent to the sensing range needed by omnidirectional sensors. We further showed that if the directional sensors are not orientable, then the sensing range needed is approximately PI times that needed by omnidrectional sensors. Finally, we developed a 2–factor approximation algorithm to deterimne the appropriate orientation for orientable directional sensors to achieve barrier coverage.