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 epsilon-cut, for any 0 epsilon , is a linear separation of epsilon n nodes in S from a distinguished node, the base station. Our main result is that, by monitoring the status of just O(1/epsilon) nodes in the network, the base station can detect whenever an epsilon-cut occurs. Furthermore, this detection comes with a deterministic guarantee that every reported cut has size at least epsilon n/2. Besides this combinatorial result, we also propose efficient algorithms for finding the O(1/epsilon) nodes that should act as sentinels, and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on random sampling.