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.
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.»
- Convergence of self-organizing … synchronization in dynamic networks
IEEE Transactions on Automatic Control, April 2017
- Firefly synchronization with phase rate equalization and its experimental analysis …
Computer Networks, March 2016
- Guaranteeing global synchronization in networks with stochastic interactions
New Journal of Physics, July 2012
- Self-organizing synchronization with inhibitory-coupled oscillators …
ACM Transactions on Autonomous and Adaptive Systems, Sept. 2012
- Emergent slot synchronization in wireless networks
IEEE Transactions on Mobile Computing, May 2010
- Self-organization in communication networks: principles & design paradigms
IEEE Communications Magazine, July 2005
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.
- Self-organizing synchronization: From metronomes to robot swarms
Invited talk at Trinity College Dublin, December 2018
- Self-organizing synchronization in networked systems
Invited talk at Intern. ITG Conf. on Systems, Communications and Coding, Hamburg, February 2017
- Self-configuration and self-organized synchronization in communication networks
Invited lecture at TU Ilmenau, January 2010
- Self-organizing synchronization and probabilistic flooding in communication networks
Invited talk at TU München, Munich, Nov. 2009
- Robots that sync and swarm: A proof of concept in ROS 2
- Precision of pulse-coupled oscillator synchronization on FPGA-based radios
- Experimental evaluation of PCO synchronization in 802.15.4 networks
- Robustness of self-organizing consensus algorithms …
- Synchronization of inhibitory pulse-coupled oscillators in delayed … networks
- Fault-tolerant averaging for self-organizing synchronization …
- How does a faulty node disturb … synchronization over wireless networks?
- A survey of models and design methods for self-organizing networked systems
- Globally stable synchronization by inhibitory pulse coupling
- Biologically inspired synchronization for wireless networks
- On autonomy and emergence in self-organizing systems
- A synchronization metric for meshed networks of pulse-coupled oscillators
- On the accuracy of firefly synchronization with delays
- Fireflies as role models for synchronization in ad hoc networks
- Synchronization inspired from nature for wireless meshed networks
- Communication node and method for self-organizing synchronization of a communication network
- Apparatus and method for synchronizing transmitter and receiver
- Apparatus and method for synchronizing first transmitting or receiving device to second transmission or reception device
. . .
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.
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.
DISTY: Dynamic stochastic time synchronization for wireless sensor networks
IEEE Transactions on Industrial Informatics, May 2017