detecting cuts in sensor networks
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 . We show that the base station can detect whenever an ?-cut occurs by monitoring the status of just O (1/?) nodes in the network. Our scheme is deterministic and it is free of false positives: no reported cut has size smaller than 1/2 ? n . 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 sampling.
network failure distributed algorithms computational geometry