Font Size: a A A

Research On Distributed Time Synchronization Algorithm For Wireless Sensor Networks

Posted on:2015-04-27Degree:DoctorType:Dissertation
Country:ChinaCandidate:C ShiFull Text:PDF
GTID:1108330464468892Subject:Communication and Information System
Abstract/Summary:PDF Full Text Request
With the rapid growth of social demand of Internet of Things, wireless sensor networks(WSNs), as the core part of Internet of Things, have drawn more and more attention from the academia to the industry in recent years. Time synchronization is one of key technologies of WSNs. It is the prerequisite for the implementation of data fusion, cooperative transmission, network security and object tracking. With the progresses of the theoretical research and engineering practice, it was found that time synchronization is the main bottlenecks to the realization of engineering. According to these facts, this paper discusses the distributed time synchronization algorithm for WSNs in detail. The results and innovations are as follows: 1 WSNs are featured by lack of infrastructure, distributed system, restricted resources, storage and computing power. Accordingly, when we design the time synchronization schemes for WSNs, intensive computation and complex route selecting are undesirable. In order to accelerating the time synchronization and lowering energy consumption of WSNs, this paper presents a network time synchronized broadcasting synchronization algorithm for WSNs. In this scheme, each node broadcasts its present clock information, and its neighbors receive the information. After simple averaging, the neighbor nodes take the averaged clock information as its next clock tick and the broadcasting continues. The process is carried out repeatedly until all the nodes meet a same clock tick, which means the whole network achieves distributed synchronization. As each node in the network only receives its neighbors’ information, this scheme does not need specific routing or complex processing, and has rapid convergence and low energy consumption. 2 Large-scale WSNs requires a faster synchronization algorithm. Thus, a large-scale WSNs’ time synchronization scheme based on multicast Gossip synchronization algorithm is presented. It allows multiple nodes to broadcast their time information simultaneously. Other nodes in the broadcast domain of the nodes receive and update time clock information according to the broadcasted algorithm. In order to avoid collisions and the receiving confusion, the scheme requires the distance between broadcasting nodes to be three according to the graph theory. The algorithm can accelerate the convergence and improve the synchronization precision of WSNs time synchronization, as well as reduce the power consumption. 3 Single gossip synchronization algorithm and multiGossip synchronization algorithm are proposed to implement distributed time synchronization for WSNs. The two algorithms aim to solve the problems of high computational complexity and slow convergence rate of traditional WSNs time synchronization scheme. First, a spanning tree is formed by tectonic spanning tree algorithm in single Gossip algorithm. Then, gossiping is executed between the pairwise nodes of each edge on the spanning tree. The above process is repeated, and the clock information of all nodes will ultimately converge to the average of their original values. While in multiGossip algorithm, the edge coloring algorithm is executed to the spanning tree, and the edges with same color can be gossiped at the same time. These two algorithms decrease the amount of exchanged information and computational complexity, while increase the convergence rate. 4 In WSNs, traditional gossip time synchronization algorithms have certain disadvantages, such as the slow convergence rate, low precision and high energy consumption. An enhanced gossip synchronization algorithm is proposed to surmount these disadvantages. The proposed algorithm can greatly improve the performance of synchronization by integrating the broadcasting characteristics of wireless channel. In the clock information exchanging process between a pair of nodes, one node sends its clock information to the other, and this information is also accessible to other nodes in the broadcasting domain. All these nodes obtain their updated clock information by averaging the clock information received and the local clock information. By repeating this process for all the pairs of nodes, the system is eventually stabilized in a state where the time information of all the nodes converges to a fixed value, and thus realizes its relative time synchronization in the network. The channel fading effects and the random delay of time message are also considered. 5 There are considerable average time synchronization schemes for WSN, whose clock update rules are linear so far. However, under many practical conditions the algorithms of network nodes may be nonlinear; hence a nonlinear average time synchronization scheme for WSNs is proposed. The adjacent pairwise nodes exchange their clock information, and they update their clock information by a nonlinear rule. In order to ensure that all the network nodes converge to the average of their initial clock information, the rule must obey some conditions. By using graph theory, Lyapunov theory and Lagrange mean value theorem, the sufficient conditions that the proposed algorithms converge to the average of the initial values asymptotically are found.
Keywords/Search Tags:Synchronization, Time synchronization, Consensus, Distributed time synchronization, Wireless sensor networks
PDF Full Text Request
Related items