Abstracts - 2006
Fault-Tolerant, Collision-Aware Applications for Sensor Networks
Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport & Tina Nolte
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.
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.
An extended abstract describing our model, algorithms, and related lower bounds was published in the 24th Annual Symposium on the Principles of Distributed Computing (PODC 2005) .
This work is supported in part by NSF grant CCR-0098305 and NSF ITR Grant 0121277, AFOSR Contract #F49620-00-1-0097, DARPA Contract #F33615-01-C-1896, NSF Grant 64961-CS, and NTT Grant MIT9904-12.
 Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport, and Tina Nolte. Consensus and Collision Detectors in Wireless Ad Hoc Networks. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), July, 2005.