A robust gradient clock synchronization algorithm for wireless sensor networks

A variation of the classical clock synchronization problem is to synchronize clocks with an error that is proportinal to their distance in the network. Among several applications, gradient clock synchronization in wireless sensor networks can yield precise time coordination of packet transmissions, allowing for time-based collision free transmission scheduling. In this paper, we propose a simple and robust gradient clock synchronization (RGCS) algorithm designed for wireless sensor networks. The algorithm is fully distributed and operates independently of network topology, network routing and has no parameters to tune. It also does not require strict timing or reliability in clock synchronization messages or any global time reference. In particular, RGCS is based on a running average of logical clock rates and addresses specific aspects of gradient synchronization, such as estimating the logical clock of neighbors. We evaluate the algorithm through realistic simulations in various scenarios to illustrate the benefits of our approach. We also compare our results with GTSP a prominent gradient clock synchronization algorithm. Our results indicates that RCGS can operate adequately under high loss rates (50%) and high variability in the period of synchronization messages.