Consensus-based Time Synchronization Algorithms for Wireless Sensor Networks with Topological Optimization Strategies for Performance Improvement

Abstract

Wireless Sensor Networks(WSNs)have received considerable attention in recent years because of its broad area of applications.In the same breadth,it also faces many challenges.Time synchronization is one of those fundamental challenges faced by WSN being a distributed system.It is a service by which all nodes in the network will share a common notion of time.It is a prerequisite for correctness of other protocols and services like security,localization and tracking protocols.Several approaches have been proposed in the last decade for time synchronization in WSNs.The well-known methods are based on synchronizing to a reference(root)node's time by considering a hierarchical backbone for the network.However,this approach seems to be not purely distributed,higher accumulated synchronization error for the farthest node from the root and subjected to the root node failure problem.Recently,consensus based approaches are gaining popularity due its computational lightness,robustness, and distributed nature.In this thesis,average consensus-based time synchronization algorithms are proposed,aiming to improve the performance metrics like number of iterations for convergence,total synchronization error,local synchronization error,message complexity,and scalability.Further,to cope up with energy constraint environment, Genetic algorithm based topological optimization strategies are proposed to minimize energy consumption and to accelerate the consensus convergence of the existing consensus-based time synchronization algorithms.All algorithms are analyzed mathematically and validated through simulation in MATLAB based PROWLER simulator.Firstly,a distributed Selective Average Time Synchronization (SATS) algorithm is proposed based on average consensus theory.The algorithm is purely distributed(runs at each node),and each node exploits a selective averaging with the neighboring node having maximum clock difference. To identify the neighboring node with maximum clock difference,every node broadcasts a synchronization initiation message to the neighboring nodes at its local oscillation period and waits for a random interval to get the synchronization acknowledgment messages.After receiving acknowledgment messages,a node estimates relative clock value and sends an averaging message to the selected node.The iteration continues until all nodes reach an acceptable synchronization error bound. The optimal convergence of the proposed SATS algorithm is analyzed and validated through simulation and compared with some state-of-the-art,average consensus based time synchronization algorithms.
Furthermore, it is observed that most of the consensus-based time synchronization algorithms are one-hop in nature, i.e., the algorithms iterate by averaging with one-hop neighbors' clock value. In a sparse network with a lower average degree of connectivity, these algorithms show poor performance. In order to have better convergence on the sparse network, a multi-hop SATS algorithm is proposed. The basic principle of multi-hop SATS algorithm remains same as that of SATS algorithm, i.e., performing selective averaging with the neighboring node, having maximum clock difference. But, in this case, the search for neighboring node goes beyond one hop. The major challenge lies in multi-hop search is the end-to-end delay which increases with the increase in hop count. So, to search a multi-hop neighboring node with maximum clock difference and with minimum and bounded end-to-end delay, a distributed, constraint-based dynamic programming approach is proposed for multi-hop SATS algorithm. The performance of the proposed multi-hop SATS algorithm is compared with some one-hop consensus time synchronization algorithms. Simulation results show notable improvement in terms of convergence speed, total synchronization error within a restricted hop count. The trade-off with the increase in number of hops is also studied. The well-known consensus-based time synchronization algorithms are ``all node based'', i.e., every node iterates the algorithm to reach the synchronized state. This increases the overall message complexity and consumption of energy. Further, congestion in the network increases due to extensive synchronization message exchanges and induces the delay in the network. The delay induced in the message exchange is the main source of synchronization error and slows down the convergence speed to the synchronized (consensus) state. Hence, it is desirable that a subset of sensors along with a reasonable number of neighboring sensors should be selected in such a way that the resultant logical topology will accelerate the consensus algorithm with optimal message complexity and minimizes energy consumption. This problem is formulated as topological optimization problem which is claimed to be NP-complete in nature. Therefore, Genetic Algorithm (GA) based approaches are used to tackle this problem. Considering dense network topology, a single objective GA-based approach is proposed and considering sparse topology, a multi-objective Random Weighted GA based approach is proposed. Using the proposed topological optimization strategy, significant improvements are observed for consensus-based time synchronization algorithms in terms of average number of messages exchanged, energy consumption, and average mean square synchronization error.