Model-based clock synchronization protocol

In a network of communicating motes, each one equipped with a distinct clock, a given node is taken as reference and is associated with the time evolution t. We introduce and analyze a stochastic model for clocks in which the relative speedup of a clock with respect to the reference node, called the skew, is characterized by some parametrized stochastic process. We study the problem of synchronizing clocks in a network which amounts to estimating the instantaneous relative skews and relative offsets, i.e., the differences in the clock readouts, by asynchronously communicating time-stamped packets between neighboring nodes. For a given communication link, we develop an algorithm for filtering the time-stamps exchanged between the two nodes in order to obtain Maximum-Likelihood (ML) estimates of the logarithm of the relative skew of one clock with respect to the other. We highlight implementation issues of the optimal filter and further present a scheme for pairwise offset estimation based on the obtained relative skew estimates. We study the properties of the proposed algorithms and provide theoretical guarantees on their performance. We extend the analysis to the problem of network-wide synchronization where the goal is to obtain