Consensus-based Clock Synchronization Algorithm In Wireless Sensor Networks

With rapid advancement in sensors, computing, communications and MEMS technologies, wireless sensor networks (WSNs) are widely applied in a large range of fields such as environment surveillance, E-health care, architecture and smart grid, etc. WSNs are penetrating into our daily lives, changing the way we work and live. Attracted by their tremendous potential and bright blueprint, many researchers from the academic and industry communities devote huge effort and money to in-depth investigation of WSNs.As one of the fundamental problems in WSNs, time synchronization has been a hot and chal-lenging research topic as well as the basis of many applications of WSNs. Recently, consensus-based time synchronization protocols have attracted widespread concern and have been one of the hottest issues. Such protocols can not only overcome the lack of robustness and less scalability of traditional time synchronization protocols, but also can operate with distributed manner and high synchronization accuracy and compensate both clock skew and offset, which makes the al-gorithm more practical. Unfortunately, there are two problems in the existing research works in terms with consensus-based time synchronization protocols. One aspect is the slow convergence speed as well as the high energy consumption of achieving time synchronization; the other is the lack of security guarantee for time synchronization, which makes the time synchronization under attack uncertain. In order to solve these problems, in this article, we consider the consensus-based time synchronization with finite time convergence and the security problem for time synchroniza-tion based on the state-of-the-art research findings, propose corresponding protocols and provide theoretical analysis. The main work and contributions are summarized as follows.1. A brief literature review on the development of WSNs, time synchronization and secure time synchronization problem related works is provided.2. For the time synchronization problem in static WSNs, a maximum time synchronization (MTS) protocol is proposed based on maximum consensus. We prove the finite convergence of MTS based on the satiability theory of Lyapunov, and give an upper bound of the finite time convergence. To overcome the random communication delay, a weighted maximum time synchronization (WMTS) protocol is provided, which is proved with finite time conver-gence in expected.3. For the time synchronization problem in random mobile sensor networks, by combining maximum consensus and neighbor discover protocol, we propose a revised maximum time synchronization (RMTS) protocol, and prove that the protocol will converge with probabil-ity1. Based on the modeling of random mobile network with relation graph, we give the lower bound of the probability of the finite time convergence for RMTS, and also design the related computing protocol. Furthermore, we prove that strengthening the connectivity of network can improve the convergence speed of algorithm, and provide a necessary and sufficient condition to improve the convergence speed of algorithm when new nodes join in the network.4. For the security problem of consensus-based time synchronization under message manipu-lation attack in WSNs, we design hardware clock and logical clock safeguard mechanisms for MTS to obtain a secure maximum time synchronization (SMTS) protocol, and prove the finite time convergence of SMTS. SMTS is able to limit the attack manners and the number of attacks of attack nodes, and achieve synchronization again after being attacked, which guarantees the time synchronization security.5. For the security problem of average time synchronization under message manipulation attack in WSNs, we design hardware clock and logical clock checking process for ATS to obtain a secure average time synchronization (SATS) protocol. Based on the satiability theory of Lyapunov, we prove that SATS has exponentially convergence rate, which is the same as traditional ATS. Moveover, compared with other algorithms, attack nodes are not necessary to be isolated in SATS and such algorithm can utilize the attack information to accelerate its convergence speed.6. A real sensor network testbed consisted of Micaz nodes has been established, on which various experiments and evaluations for both of the Maximum consensus-based time syn-chronization algorithm (MTS) and Average consensus-based time synchronization algorithm (ATS) have been conducted. Based on substantial results of large amounts of experiments and previously-done simulations, we give the analysis and comparison of MTS and ATS re-garding convergence rate, synchronization accuracy and robustness. The results show that MTS has faster convergence rate and better synchronization accuracy than ATS, which also illustrates the practical feasibility of such consensus algorithm.In the end, the thesis is concluded and some future research works are discussed.