Trap Coverage

Project Goal

The goal of this project is to build an appropriate model of coverage in a wireless sensor network that can be used for large scale tracking of assets such as lost or stolen objects or of other moving object or phenomena that is to be tracked.

Project Description

The full coverage model, where every point in the deployment region must be covered by at least one sensor, is pervasive in the wireless sensor network community. For applications that involve tracking movements at large scale such as tracking of thieves and robbers fleeing with stolen objects, tracking of animals in forests, and tracking the spread of forest fire, using the full coverage model makes sensor deployment prohibitively expensive. No sound model currently exists that can be used for systematic deployment of such large scale applications.

This project proposes a novel model of coverage called Trap Coverage that can be used for systematic deployment of sparse sensor networks, while ensuring frequent tracking of movements of interest. Most existing theoretical and systems work are not applicable to this new model because of the inherent sparsity of the network implied by the trap coverage model. The overall goal of this project is to establish a strong foundation for all large scale movement tracking applications and address the key systems issues faced in such applications. The project applies rigorous mathematical analysis, experimentation on a large scale sensor network testbed, and real-life deployment of a campus-wide object tracking system called AutoWitness to design, develop, and evaluate the algorithms and protocols developed in this project. In addition to providing hands-on research experience to undergraduate and graduate students in building a real wireless sensor network, the AutoWitness system is expected to help reduce property thefts in a university campus.

Results

In an INFOCOM 2009 paper, we propose a new model of coverage, called Trap Coverage, that scales well with large deployment regions. A sensor network providing Trap Coverage guarantees that any moving object or phenomena can move at most a (known) displacement before it is guaranteed to be detected by the network, for any trajectory and speed. Applications aside, trap coverage generalizes the de-facto model of full coverage by allowing holes of a given maximum diameter. From a probabilistic analysis perspective, the trap coverage model explains the continuum between percolation (when coverage holes become finite) and full coverage (when coverage holes cease to exist).

We take first steps toward establishing a strong foundation for this new model of coverage. We derive reliable, explicit estimates for the density needed to achieve trap coverage with a given diameter when sensors are deployed randomly. Our density estimates are more accurate than those obtained using asymptotic critical conditions. We show by simulation that our analytical predictions of density are quite accurate even for small networks. We then propose polynomial-time algorithms to determine the level of trap coverage achieved once sensors are deployed on the ground. Finally, we point out several new research problems that arise by the introduction of the trap coverage model.

Team Members at the WiSe MANet Lab:

• Lead Faculty Member: Dr. Santosh Kumar
• Amin Ahsan Ali (2008-) - aaali(dot)(at)memphis(dot)edu

Collaborators

• Prof. Paul Balister, Mathematical Sciences, University of Memphis
• Prof. Bela Bollobas,  Mathematical Sciences, University of Memphis
• Prof. Prasun Sinha, Computer Science and Engineering, Ohio State University

Sponsor

• National Science Foundation (CCF, TF, COMM)

Updates

• NSF grant awarded on 9/17/2007.