Efficient Synchronization Method for Wireless Networks.

摘要

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.