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. I. I NTRODUCTION Wireless sensor networks (WSN) have emerged as an important new technology for instrumenting and observing the physical world. The basic building block of these networks is a tiny microprocessor integrated with one or more MEMS (micro-electromechanical sys- tem) sensors, actuators, and a wireless transceiver. These devices can be embedded or scattered in large quantities in a physical space, where they self-organize into an ad hoc multi-hop wireless network, allowing us to observe and monitor the world at an unprecedented spatial and temporal resolution. A rich variety of scientific, commer- cial, and military applications (7), (11), (25), (32) has been proposed for sensor networks, and many experimental prototypes are under development in academia and industry. Realizing the full potential of the sensor networks, however, requires solving several challenging research problems. Many of these challenges stem from two major limitations of the sensor nodes: low power and low bandwidth. Consequently, a number of proposals have been made for improving the data collection and information processing in sensor networks, including power-aware routing and scheduling (16), (24), (27), in- network aggregation (15), (23), (28), query processing (13), data storage management (12), etc. In this paper, we address a different kind of challenge for sensor networks, which does not seem to have received adequate attention. How to monitor the sensor network itself, and how to detect when the network has suffered a significant "cut"?After all, if sensor networks are to act as our remote "eyes and ears," then we need to ensure that any significant failure (natural or adversarial) suffered by the network is promptly and efficiently detected. Tracking the operational health of the infrastructure is important in any communication network, but it is especially important in sensor networks due to their unique characteristics, and the need to perform this duty with very little overhead.