Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Low-Power Asynchronous Wireless Protocols

View Current Project Information

Prabal Dutta, Razvan Musaloiu-E.1, David E. Culler, Scott Shenker, Ion Stoica and Andreas Terzis2

National Science Foundation, Microsoft, Intel, Hewlett-Packard and Sharp

Disco: An asynchronous neighbor discovery and rendezvous protocol that allows two or more nodes to operate their radios at low-duty cycles (e.g., 1%) and yet still discover and communicate with one another during infrequent, opportunistic encounters without requiring any prior synchronization information. The key challenge is to operate the radio at a low duty cycle but still ensure that discovery is fast, reliable, and predictable over a range of operating conditions. Disco nodes pick a pair of prime numbers such that the sum of their reciprocals is equal to the desired radio duty cycle. Each node increments a local counter with a globally fixed period. If a node’s local counter value is divisible by either of its primes, then the node turns on its radio for one period. This protocol ensures that two nodes will have some overlapping radio on-time within a bounded number of periods, even if nodes independently set their own duty cycle. Once a neighbor is discovered, and its wakeup schedule known, rendezvous is just a matter of being awake during the neighbor’s next wakeup period, for synchronous rendezvous, or during an overlapping wake period, for asynchronous rendezvous.

Backcast: An acknowledged anycast primitive that allows a node to wirelessly transmit a packet and efficiently determine that at least one neighbor successfully received it. The initiator transmits a single packet to a unicast, multicast, or broadcast address and all nodes that match the destination respond with identical acknowledgment packets automatically generated by the hardware. Although these acknowledgments interfere, they usually do so non-destructively, so the initiator can decode their superposition. We call such an exchange a Backcast and show that this operation is feasible using a commodity radio, general because it enables multiple network services, efficient because it is independent of the neighborhood size and runs in constant time, and scalable because it works with no fewer than a dozen interfering acknowledgments.

P. Dutta and D. Culler, "Practical Asynchronous Neighbor Discovery and Rendezvous for Mobile Sensing Applications," Proceedings of the Sixth ACM Conference on Embedded Networked Sensor Systems, November 2008.
P. Dutta, R. Musaloiu-E., I. Stoica, and A. Terzis, "Wireless ACK Collisions Not Considered Harmful," Proceedings of the Seventh Workshop on Hot Topics in Networks, Calgary, Alberta, Canada, October 2008.
P. Dutta, D. Culler, and S. Shenker, "Procrastination Might Lead to a Longer and More Useful Life," Proceedings of the Sixth Workshop on Hot Topics in Networks, Atlanta, GA, November 2007.

1Johns Hopkins University
2Johns Hopkins University