Time Synchronization
Coordination among a group of modules often relies on the existence of a common notion of time. Every module has its own notion of time provided by its own hardware clock. Since common hardware clocks are imperfect, local clocks tend to run at slightly different and variable frequencies, drifting apart from each other over time. Consequently, a distributed time synchronization is necessary to keep the local clock of each module synchronized. Our goal is to achieve network-wide time synchronization. In most of the existing protocols, devices exchange timestamped messages in order to estimate the current global time. Since time keeps going during communications, modules have to correctly compensate for network delays in order to evaluate the current global time upon reception of synchronization messages. Although it is non-trivial to accurately estimate communication delays, especially in the presence of unpredictable delays (due for example, to queueing or retransmissions), it is crucial in order to achieve high-precision performance. In this work, we assume that every module is equipped with a local clock, which can be low-precision and low-resolution.
The Modular Robot Time Synchronization Protocol
We propose the Modular Robot Time Synchronization Protocol (MRTP), a network-wide time synchronization protocol for modular robots. Our protocol achieves its performance by combining several mechanisms: central time master election, fast and recursive propagation of synchronization waves along the edges of a breadth-first spanning tree, low-level timestamping with per-hop compensation for communication delays using the most-appropriate method for the target platform, and clock skew compensation using linear regression. We evaluate our protocol on the Blinky Blocks system both on hardware and through simulations. Experimental results show that MRTP can potentially manage real systems composed of up to 27,775 Blinky Blocks. Furthermore, we show that our protocol is able to keep a Blinky Blocks system synchronized to a few milliseconds, using few network resources at runtime, even though the Blinky Blocks use low-bitrate communications (38.4 kbit/s) and are equipped with very low-accuracy (10,000 parts per million (ppm)) and poor-resolution (1 millisecond) clocks. We compared MRTP to existing synchronization protocols ported to fit our system model. Simulation results show that MRTP can achieve better synchronization precision than the most precise protocols compared, while sending more than half less messages in compact systems.
Videos
Publications
Naz, A. (2017). Distributed Algorithms for Large-scale Robotic Ensembles: Centrality, Synchronization and Self-Reconfiguration. FEMTO-ST Institute, Univ. Bourgogne Franche-Comté, CNRS.
Naz, A., Piranda, B., Bourgeois, J., & Goldstein, S. C. (2018). A time synchronization protocol for large-scale distributed embedded systems with low-precision clocks and neighbor-to-neighbor communications. Journal of Network and Computer Applications.
Naz, A., Piranda, B., Goldstein, S. C., & Bourgeois, J. (2016, February). A time synchronization protocol for modular robots. In Parallel, Distributed, and Network-Based Processing (PDP), 2016 24th Euromicro International Conference on (pp. 109-118). IEEE.