Distributed clock synchronization for wireless sensor networks

Abstract

Clock synchronization for Wireless Sensor Networks (WSNs) has attracted lots of attention due to its importance for operations in WSNs. In traditional centralized clock synchronization algorithms, all the local information should be transmitted to a fusion center for processing, and the results need to be forwarded back to each individual sensor, thus resulting in a heavy burden on communication and computation in the network. In addition, it also lacks of adaptability to link failures and dynamic changes in the network topology, which greatly prevents their use in WSNs. Hence, in this thesis, we focus on developing energy-efficient distributed clock synchronization algorithms for WSNs.

Firstly, global clock synchronization problem is investigated with time-varying clock parameters (skew and offset) owing to imperfect oscillator circuits. A distributed Kalman filter is developed for clock parameters tracking. The proposed algorithm only requires each node to exchange limited information with its direct neighbors, thus is energy efficient, scalable with network size, and is robust against changes in network connectivity. A low-complexity distributed algorithm based on Coordinate-Descent with Bootstrap (CD-BS) is also proposed to provide rapid initialization of the tracking algorithm. Simulation results show that the proposed distributed tracking algorithm achieves the long-term accuracy for the clock parameters close to the Bayesian Cramer-Rao Lower Bound.

Secondly, the problem of global clock synchronization for WSNs in the presence of unknown exponential delays is studied. The joint maximum likelihood estimator of clock offsets, clock skews and fixed delays of the network is first formulated as a global linear programming (LP) problem. Based on the Alternating Direction Method of Multipliers (ADMM), we propose a fully-distributed synchronization algorithm that has low communication overhead and computation cost. Simulation results show that the proposed algorithm achieves better accuracy than consensus algorithm and the distributed least squares algorithm, and can always converge to the centralized optimal solution.

Finally, global clock synchronization for WSNs under the exponentially distributed delays is re-visited with the fast convergence min-sum algorithm. The synchronization problem is cast into an optimization problem represented by factor graph, and a closed-form expression of the messages passed between nodes are derived. Simulation results show that this distributed algorithm can approach the centralized LP solution with faster convergence speed compared to ADMM-based algorithm.