Message efficient termination detection in wireless sensor networks

Execution of wireless sensor network (WSN) applications typically consists of a number of successive phases such as network reprogramming, localization, power management, health monitoring, and parameter updates. Termination detection of a phase is therefore a critical operation for a network manager to safely execute a new phase on some or all of the network nodes. In this paper, we reformulate the well-known problem of termination detection for WSNs, and present an automated, low-cost solution to the problem. Our algorithm, Reporter, exploits the reactive nature of WSN protocols as well as the broadcast communication model of WSNs. It detects termination accurately and (message) efficiently, using reports from only a small fraction of nodes in the network. It exploits existing network traffic to construct a routing tree to collect these reports at a base station, and thus reduces the control overhead of structure formation. Moreover, it has low computation and memory overhead. We have developed a TinyOS implementation of Reporter, which is easily composed with a number of existing WSN protocols. We provide detailed experimental performance results obtained on an indoor mote testbed which show that Reporter selects as few as 5 % of the total number of nodes in the network for collecting termination reports while preserving accuracy.