Synchronization algorithms based on the theory of pulse-coupled oscillators are evaluated on programmable radios. It is experimentally demonstrated that the stochastic nature of coupling is a key ingredient for convergence to synchrony. We propose a distributed algorithm for automatic phase rate equalization and show that synchronization precisions below one microsecond are possible.
There is a broad spectrum of work on pulse-coupled oscillators (PCO) to model synchronization phenomena in biology, physics, and other 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 distributed, self-organizing manner without any need for central entities. Furthermore, PCO synchronization—sometimes called firefly synchronization—is scalable with respect to the number of entities and robust against full failure of individual entities or appearance of new entities.
Many communication protocols and scheduling techniques, as well as novel approaches such as interference alignment in wireless networks, require synchronization. Thus, the telecommunications engineering community has been interested to transfer the concepts behind these natural synchronization phenomena to design algorithms for the synchronization of nodes in wireless networks. A one-to-one transfer is, however, infeasible due to the differences between biological and wireless communication systems. Several extensions and modifications are required with respect to delays, noise, and multihop communications, to mention a few.
Despite the conceptual and theoretical advances in the design of PCO synchronization for wireless systems, real-world performance studies and proofs of concepts are largely missing. There only exist a few implementations on low-cost sensor platforms, whose results are of interest, but whose synchronization precision is limited by restricted hardware capabilities.
As part of his doctoral research, Günther Brandner investigated this topic together with his professor Christian Bettstetter and Postdoc Udo Schilcher. “We did a comprehensive performance analysis of PCO synchronization on programmable radio boards,” Brandner says. To be more precise, they analyzed three recently proposed PCO synchronization algorithms by implementing them using field programmable gate-array (FPGA)-based radios and study their performance with respect to the achieved synchronization precision. Besides this experimental contribution, the main conceptual contribution comes from the lessons learned during our measurements: they proposed an automatic phase rate equalization algorithm, integrated it into PCO synchronization, and showed by experiments that this new feature significantly improves the synchronization precision compared to existing PCO algorithms.
Bettstetter concludes: “We can now state that the at least three building blocks are essential for PCO synchronization in wireless networks and should be considered by protocol designers: a combination of positive (excitatory) and negative (inhibitory) coupling, unreliable or intentionally stochastic communication of synchronization words, and automatic phase rate equalization.”
The work has been published in the March 2016 issue of Computer Networks and is available for free download.
G. Brandner, U. Schilcher, C. Bettstetter:
Firefly Synchronization with Phase Rate Equalization and its Experimental Analysis in Wireless Systems. Computer Networks, March 2016.
This blog entry is closely based on the introduction of the mentioned journal publication, jointly written by the three authors.