Introduction

As wireless technology has improved and miniaturized, there has been increasing interest in large-scale, widely-deployed sensor networks. Fault-tolerant algorithms are of key importance in sensor networks that suffer from hardware malfunction, physical damage, battery depletion, or enforced hibernation. Examples are numerous: choosing a TDMA schedule, remote management and re-programming of sensor deployments, maintaining consistent replicated state, simultaneous temperature control, and coordinating stages of a factory assembly line, among others.

Unfortunately, communication in wireless networks is unreliable: collisions and other wireless interference might cause significant message disruption. In addition, the deployment of devices cannot be carefully controlled, so the number of deployed devices (and, perhaps, the density of the deployment) is a priori unknown. Moreover, the devices may be "anonymous", meaning that they have no unique identifiers. As a result of collisions, an arbitrary number of messages that have been broadcast in a round can be lost. Furthermore, without an a priori knowledge of the number of participants, the message loss cannot be reliably detected.

To circumvent the problem of unrestricted message loss, we assume that, eventually, if the broadcast contention is low, then the MAC layer is able to ensure that there are no collisions. In the worst case, the contention can be as low as 1. Under this assumption, we focus on developing algorithms where the number of broadcasting participants is dynamically adjusted to the desired contention level, without actually knowing it. The two main advantages of this approach are (1) improved fault-tolerance for MAC layers that can sustain higher contention levels, and (2) the ability to use fixed length rounds, which is important in practice.

To cope with undetectable message loss, we augment the nodes with a collision detection capability. Collision detectors monitor the broadcast medium and deliver notifications whenever a possible message loss is detected. They do not provide any information with respect to the number of lost messages or the identities of their senders. Moreover, there is no guarantee that a node performing a transmission can detect collisions (unlike, for example, Ethernet networks). We classify collision detectors according to their completeness, the ability to detect actual collisions, and accuracy, the ability not to report non-existent collisions.

Progress

In recent work, we consider the fault-tolerant consensus problem in wireless ad hoc networks with crash-prone nodes. We develop consensus algorithms for single-hop wireless networks, where the nodes are located within broadcast range of each other. Our algorithms tolerate a highly unpredictable network model, in which messages may be lost due to collisions, electromagnetic interference, or other anomalies. Accordingly, each node may receive a different set of messages in the same round. In order to minimize collisions, we design adaptive consensus algorithms that attempt to minimize the broadcast contention. Our algorithms depend on collision detectors with varying levels of completeness and accuracy. We show in which cases consensus can be solved, and thus determine the requirements for a useful collision detector.

Our algorithms, and the underlying wireless model, are validated with simulations based on a realistic 802.11 MAC layer implementation and a detailed radio propagation model. We analyze the performance of our algorithms under varying sized deployments, varying densities of deployment, and varying MAC layer parameters. We use our single-hop consensus protocol as the basis for solving consensus in a multi-hop network, demonstrating the resilience of our protocol to a challenging and noisy environment.

Research Support

This project is supported by DARPA Air Force contract number FA9550-04-C-0084, DARPA Award number F33615-01-C-1896, NSF Award numbers CCR-0326277 and CCR-0121277, NSF-Texas Engineering Experiment Station grant 64961-CS, DARPA/AFOSR MURI Award F49620-02-1-0325 and MURI AFOSR Award Number SA2796PO 1-0000243658.

References

[1] G. Chockler, M. Demirbas, S. Gilbert, C. Newport, and T. Nolte. Consensus and collision detectors in wireless ad hoc networks. Technical Report 980, MIT CSAIL, 2005.

[2] G. Chockler, M. Demirbas, S. Gilbert, N. Lynch, C. Newport, and T. Nolte. Reconciling the theory and practice of (un)reliable wireless broadcast. To appear in International Workshop on Assurance in Distributed Systems and Networks (ADSN), June, 2005.