Research Abstracts - 2006

Limited Receiver-Side Collision Detection for Sensor Networks

Gregory Chockler, Murat Demirbas, Seth Gilbert & Calvin Newport

Introduction

Collisions are a key feature of wireless communication that has not been adequately addressed so far in theoretical work on wireless network algorithms: many theoretical papers ignore collisions, assuming that they can be handled adequately by a lower layer (if they cannot, then in the worst case, even basic problems such as distributed consensus become impossible to solve). In this project, we aim to develop communication models that include more realistic communication assumptions (including the possibility of message collisions), yet also allow efficient solutions to basic agreement problems such as consensus.

To this end, following our approach in previous work [1], we consider a limited receiver-side collision detection (RCD) capability in our communication models, with a range of possible assumptions about the completeness and accuracy of RCD. Here, completeness refers to the percentage of actual collisions that are detected, whereas accuracy refers to the percentage of false collision identifications. In [1], we have shown that, using even fairly incomplete and inaccurate RCDs, consensus can be achieved over unreliable, collision-prone channels.

Current MAC layer designs, unfortunately, do not export explicit collision-detection information. We believe, however, that it is possible to produce such information, and that this information will be useful for implementing efficient reliable-broadcast protocols, consensus protocols, and contention management services--a claim we explore in [2]. As a proof of concept, we have implemented RCD on a Mica2 node platform, and investigated its performance using MIT's MistLab testbed. Our RCD works by utilizing the carrier-sensing mechanism widely employed in wireless networks with CSMA (Carrier Sense Multiple Access) MAC layers, including IEEE 802.11, IEEE 802.15.4, and wireless sensor network MAC layers.

Traditionally, carrier sensing has been used primarily at the transmitter side: before beginning to transmit, a transmitter senses the medium for current transmissions, and only begins transmitting if the medium appears to be idle. Instead, we use carrier sensing at the receiver side for detecting collisions. Our nodes perform carrier sensing while they are in the idle state---when they are not transmitting or receiving a message, nor engaged in synchronizing in preparation for receiving a message. A node detects a collision when its carrier-sensing mechanism detects, in the idle state, that there is intense activity on the medium. Due to noise, there is a lot of activity in the transceiver even in the idle state. However, it is easy to differentiate between noise and genuine activity, such as a message or collision. The random noise has significant variance in channel energy (occasional pits below the noise floor) whereas genuine activity has fairly constant channel energy (always stays above the noise floor). Our carrier sensing at the idle state searches for these pits: if for a long period no pit is found, this is a good indication of genuine activity in the radio.

In our preliminary experiments with the Mica2 mote platform, we find that our carrier-sensing-based receiver-side collision detection performs well, detecting more than 90% of the collisions with only about 10-15% false positives for most of the runs. We expect that using closely synchronized tiny rounds (say of one message length) can improve the completeness and accuracy of our RCD greatly. More study is needed to derive good models for collisions and collision detection in real wireless networks.

References:

[1] 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.

[2] Gregory Chockler, Murat Demirbas, Seth Gilbert, and Calvin Newport. A Middleware Framework for Robust Applications in Wireless Ad Hoc Networks. In Proceeding of the 43rd Allerton Conference on Communication, Control, and Computing, September, 2005 (Invited).