Self-Organizing Synchronization

Time synchronization algorithms that operate in a decentralized manner in large wireless networks are being developed and evaluated. It is demonstrated that the stochastic nature of interactions between devices is a key ingredient for convergence to synchrony. This convergence has been mathematically proven for arbitrary connected network topologies and variably changing interaction delays. Implementation and experiments on programmable radios show synchronization precisions below one microsecond when applying automatic phase rate correction. The developed solutions were patented, implemented in the robot operating system (ROS), and tested in a swarm of resource-limited robots.

There is a broad spectrum of work on pulse-coupled oscillators to model synchronization phenomena in biology, physics, and other basic sciences. A prominent example is swarms of fireflies that synchronize their blinking behavior. The beauty of these synchronization phenomena lies in the fact that system-wide synchrony emerges among the participating entities in a completely nonhierarchical manner without need for central entities. Such synchronization is scalable with the number of entities and robust against complete failure of entities or appearance of new entities. It is considered as a prime example of self-organization in nature—similar to the flocking of birds or shoaling of fish—where simple rules in each entity and localized interactions between neighboring entities lead to pattern formation of the entire system.

«We advance this field of science and transfer it to wireless networks,» Christian Bettstetter argues. Synchronization is an important building block in large networks of embedded systems, where synchrony should emerge in a distributed manner without having to rely on central entities. A one-to-one transfer of synchronization known from biology and physics to wireless networks is, however, infeasible due to the differences between biological and wireless communication systems. Several significant and nontrivial extensions and modifications are required to cope with delays, noise, multihop communications, and synchronization words, to mention a few.

Johannes Klinglmayr with synchronizing pendula

Johannes Klinglmayr with synchronizing pendula

Bettstetter and his team have developed such a synchronization solution for wireless networks. It exploits a combination of positive and negative coupling between devices and takes into account unreliable channels. «Together with Marc Timme from the Max Planck Institute for Dynamics and Self-Organization we have mathematically proven that our algorithm always converges,» PhD student Johannes Klinglmayr concludes. An important aspect in this convergence proof is that unreliable links between nodes or intentionally stochastic transmission of synchronization messages actually helps the network to converge to synchrony. This leads to an unprecedented degree of freedom for the design of synchronization schemes tat may have great impact on synchronization performance.

The algorithm has been implemented in the physical layer of a programmable radio for field tests. Bettstetter’s PhD student Günther Brandner is excited: «This is the first ever evaluation of convergence and precision of pulse-coupled oscillator-based synchronization on programmable radios.» It became obvious from these experiments that automatic phase rate adaptation is needed in a real-word setup. If we apply such rate adaptation, the synchronization precision below one microsecond in a testbed with six radio boards can be achieved.

A conceptual difference of the self-organizing synchronization algorithm developed in Klagenfurt compared to synchronization found in cellular networks is that it always synchronizes the entire network as a whole (all devices), while cellular systems apply point-to-point or point-to-multipoint synchronization to synchronize mobile devices to a base station. Bettstetter concludes: «In summary, we can state that time-discrete coupling can be used for network synchronization over wireless channels. Such self-organizing synchronization is a viable option if centralized control should be avoided, yet scalable and computationally simple solutions are needed. Key ingredients for the design of such algorithms are excitatory and inhibitory coupling, stochastic coupling, and phase rate correction.»

Selected Publications

Additional Publications

Videos


Firefly synchronization implemented in the Robot Operating System (ROS) and demonstrated with a swarm of Balboa robots. Work by Agata Gniewek and Michał Barciś  under supervision of Christian Bettstetter at the Karl Popper school of the University of Klagenfurt.


Johannes Klinglmayr explains our coupling scheme proposed and patented for self-organizing synchronization. It won the runner-up award at the 2013 video abstract competition of the IOP New Journal of Physics.

Selected Talks

Patents

. . .

Related Research

A. Self-Organizing Consensus

The problem of finding a consensus in a group of people occurs in many social contexts. In a similar way, distributed algorithms for consensus play an important role in networked computing and communication systems if centralized decision making is difficult or impossible. Bettstetter’s PhD student Alexander Gogolev studied binary consensus in networks with disturbances. It was shown that additive noise, topology randomness, and message loss can increase the convergence rate of simple binary consensus algorithms, while presence of faulty nodes always inhibits convergence. A new consensus rule was proposed, which embeds randomization directly into the consensus algorithm, thus yielding a better convergence rate and robustness toward faulty entities.

Major Publication
Distributed binary consensus in networks with disturbances
ACM Transactions on Autonomous and Adaptive Systems, Oct. 2015

B. Centralized Synchronization

A time synchronization technique for networked devices with low-precision oscillators and low computational power is proposed and evaluated. Bettstetter’s PhD student Wasif Masood applies a dynamic stochastic model inserted into a Kalman filter formulation to track the clock evolution of oscillators and achieve synchrony to a central time reference. Indoor and outdoor experiments performed with commercially available wireless sensor platforms over several days serve as a proof of concept and show the synchronization accuracy under stable and varying temperature conditions.

Major Publication
DISTY: Dynamic stochastic time synchronization for wireless sensor networks
IEEE Transactions on Industrial Informatics, May 2017