Coverage in sensor networks via persistent homology

We introduce a topological approach to a problem of covering a region in Euclidean space by balls of fixed radius at unknown locations (this problem being motivated by sensor networks with minimal sensing capabilities). In particular, we give a homological criterion to rigorously guarantee that a collection of balls covers a bounded domain based on the homology of a certain simplicial pair. This pair of (Vietoris–Rips) complexes is derived from graphs representing a coarse form of distance estimation between nodes and a proximity sensor for the boundary of the domain. The methods we introduce come from persistent homology theory and are applicable to nonlocalized sensor networks with ad hoc wireless communications.

PDF Access Denied

Warning: We have not been able to recognize your IP address 47.88.87.18 as that of a subscriber to this journal. Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form.

Or, visit our subscription page for instructions on purchasing a subscription. You may also contact us at contact@msp.org or by using our contact form.

Or, you may purchase this single article for USD 29.95:

Keywords

Rips complex, Cech complex, persistent homology, sensor network, coverage

Mathematical Subject Classification 2000

Primary: 55M25, 93A15

Secondary: 55N35

References

Publication

Received: 25 November 2005

Revised: 29 January 2006

Accepted: 8 October 2006

Published: 25 April 2007

Authors

Vin de Silva
Department of Mathematics and Computer Science Pomona College Claremont CA 91711 USA

Robert Ghrist
Department of Mathematics and Coordinated Sciences Laboratory University of Illinois Urbana, IL 61801 USA

Volume 7, issue 1 (2007)

Vin de Silva and Robert Ghrist

Abstract