Multi-hop consensus time synchronization algorithm for sparse wireless sensor network: A distributed constraint-based dynamic programming approach

The recent consensus time synchronization algorithms designed for Wireless Sensor Networks (WSNs) are mostly one-hop in nature, i.e., every node communicates with its one-hop neighbors and performs clock parameters averaging to reach to the consensus or synchronized state. As per consensus theory, apart from the averaging scheme employed by the consensus algorithm, another factor that affects the consensus-based algorithms' performance is the topological connectivity of the networks. In topologies of lower degree of connectivity like sparse network, these one-hop consensus synchronization algorithms have exhibited poor performance in terms of convergence speed and synchronization accuracy. This motivates the design of multi-hop consensus time synchronization algorithm for sparse WSNs. In this paper, we have proposed a multi-hop consensus time synchronization algorithm, multi-hop Selective Average Time Synchronization (SATS), for sparse and multi-hop WSNs. A distributed, constraint-based dynamic programming approach is suggested for multi-hop clock parameters estimation. Simulation results show that the proposed algorithm outperforms some recent, state-of-the-art one-hop consensus time synchronization algorithms within a restricted hop count.