Detecting cuts in sensor networks
Authors:
Open Access
- 1 March 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Sensor Networks
- Vol. 4 (2) , 1-25
Abstract
We propose a low-overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An ε- cut , for any 0 < ε < 1, is a linear separation of ε n nodes in S from a distinguished node, the base station . Our main result is that, by monitoring the status of just O (1/ε) nodes in the network, the base station can detect whenever an ε- cut occurs. Furthermore, this detection comes with a deterministic guarantee that every reported cut has size at least ε n /2. Besides this combinatorial result, we also propose efficient algorithms for finding the O (1/ε) nodes that should act as sentinels , and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on random sampling.Keywords
Funding Information
- University of California, Santa Barbara (DAAD19-03-D-0004)
- Division of Information and Intelligent Systems (IIS-0121562)
This publication has 27 references indexed in Scilit:
- ASCENT: adaptive self-configuring sensor networks topologiesIEEE Transactions on Mobile Computing, 2004
- Sensor and actuator networks - Query processing in sensor networksIEEE Pervasive Computing, 2004
- Collaborative signal and information processing: An information-directed approachProceedings of the IEEE, 2003
- Point Sets with Many k-SetsDiscrete & Computational Geometry, 2001
- Wireless integrated network sensorsCommunications of the ACM, 2000
- Taking a Walk in a Planar ArrangementSIAM Journal on Computing, 2000
- Product Range Spaces, Sensitive Sampling, and DerandomizationSIAM Journal on Computing, 1999
- Constructing Arrangements of Lines and Hyperplanes with ApplicationsSIAM Journal on Computing, 1986
- The number of small semispaces of a finite set of points in the planeJournal of Combinatorial Theory, Series A, 1986
- On the Uniform Convergence of Relative Frequencies of Events to Their ProbabilitiesTheory of Probability & Its Applications, 1971