An Efficient Synchronization Method for Wireless Networks
Abstract
When a group of independent actors wish to coordinate their actions with one another, each actor uses internal state information combined with information known about all other actors' states to decide what to do. This generally requires some form of communication to synchronize state information between all actors. Since communication is often costly and not all parts of an actor's state change between synchronization attempts using a method such as rsync can reduce the number of bits transmitted, and thus, the communications cost. However, rsync is designed for pair-wise interactions. In wireless communications, group-wise synchronization which is more e cient than rsync, is possible. This paper describes Dandelion, an algorithm that builds on the ideas of the rsync algorithm to e ciently distribute information to all actors in a group over a shared broadcast medium. The algorithm is described in detail, as well as some experimental results using the algorithm on robots. Finally, theoretical comparisons to rsync and generic multicast trees are provided, as well as experimental comparisons between an implementation and a current version of the rsync program, showing that the costs of transmission are as low as a multicast tree, without the associated cost of building or maintaining a tree.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2013
- Accession Number
- ADA584458
Entities
People
- Cem Karan
Organizations
- United States Army Research Laboratory