Time-synchronization in mobile sensor networks from difference measurements

We examine distributed time-synchronization in mobile ad-hoc and sensor networks. The problem is to estimate the skews and offsets of clocks of all the nodes with respect to an arbitrary reference clock. Pairs of nodes that can communicate with each other can obtain noisy measurements of the relative skews and offsets between them. We propose a distributed algorithm with which each node can estimate its offset/skew from these noisy relative measurements by communicating only with its neighbors. The algorithm is simple and easy to implement. We model the change in the communication network due to the moving nodes as a Markov chain whose state space is the set of graphs that can occur. Using tools from Markov Jump Linear Systems, we provide a sufficient condition for the mean square convergence of the estimation error. A conjecture on mean square convergence under weaker conditions is discussed. Monte Carlo simulations are provided that corroborate the predictions and justify the conjecture.