Volume 25 Issue 12 - Publication Date: 1 December 2006
Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology
V. de Silva Department of Mathematics, Pomona College, Claremont CA 91711, USA and R. Ghrist Department of Mathematics and Coordinated Science Laboratory, University of Illinois, Urbana IL, 61801, USA
Tools from computational homology are introduced to verify coverage in an idealized sensor network. These methods are unique in that, while they are coordinate-free and assume no localization or orientation capabilities for the nodes, there are also no probabilistic assumptions. The key ingredient is the theory of homology from algebraic topology. The robustness of these tools is demonstrated by adapting them to a variety of settings, including static planar coverage, 3-D barrier coverage, and time-dependent sweeping coverage. Results are also given on hole repair, error tolerance, optimal coverage, and variable radii. An overview of implementation is given.
Return to Contents