A time synchronization protocol for large-scale distributed embedded systems with low-precision clocks and neighbor-to-neighbor communications. (1st March 2018)

• Record Type: Journal Article
• Authors: Naz, André; Piranda, Benoît; Bourgeois, Julien; Goldstein, Seth Copen
• Is Part Of: Journal of network and computer applications. Volume 105(2018)
• Page Start: 123
• Page End: 142
• Publication Date: 2018-03-01
• Subjects: Time synchronization -- Distributed embedded systems -- Modular robotics; Microcomputers -- Periodicals; Computer networks -- Periodicals; Application software -- Periodicals; Micro-ordinateurs -- Périodiques; Réseaux d'ordinateurs -- Périodiques; Logiciels d'application -- Périodiques; Application software; Computer networks; Microcomputers; Periodicals; 004.05; 004
• DOI: 10.1016/j.jnca.2017.12.018
• Languages: English
• ISSNs: 1084-8045

Abstract

Abstract: In this paper, we propose the Modular Robot Time Protocol (MRTP), a network-wide time synchronization protocol for modular robots (a class of distributed embedded systems) with neighbor-to-neighbor communications and potentially low-precision clocks. 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 and per-hop compensation for communication delays using the most-appropriate method, 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. We observe that the synchronization precision depends on the hop distance to the time master, the synchronization periods and the number of synchronization points used for the linear regressions. 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 hardware clocks exhibit very poor accuracy and resolution. We compare 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 compared protocols while sending more than half less messages in compact systems. Highlights: We propose MRTP: a network-wide time synchronization protocol for modular robots. Our protocol combines synchronization techniques proposed in various domains. We evaluate MRTP using both Blinky Blocks hardware and simulations. Experiments show MRTP can synchronize large-scale systems to a few milliseconds. Results also show MRTP outperforms existing synchronization protocols.