Journal of Shanghai Jiaotong University ›› 2014, Vol. 48 ›› Issue (03): 351-356.

• Radiao Electronics, Telecommunication Technology • Previous Articles     Next Articles

Time Synchronization for Wireless Sensor Networks Based on Gossip Algorithm

SHI Chao1,QIU Hongbing1,2,WANG Junyi2,LI Xiaoyan1
  

  1. (1. School of Telecommunication Engineering, Xidian University, Xi’an 710071, China; 2. Information and Communication College, Guilin University of Electronic Technology, Guilin 541004, Guangxi, China)
  • Received:2013-04-07 Online:2014-03-28 Published:2014-03-28

Abstract:

The single gossip synchronization algorithm and multigossip synchronization algorithm were proposed in this paper using gossip algorithm to implement distributed time synchronization for wireless sensor networks. The two algorithms aimed to solve the problems of high computational complexity and slow convergence rate of traditional time synchronization scheme. A spanning tree was formed by using the tectonic spanning tree algorithm in the single gossip algorithm and then the gossiping was executed between the pairwise nodes of each edge in the spanning tree. The aforementioned process was repeated and the clock information of all nodes ultimately converged to the average of their original values. While in the multigossip algorithm, the edge coloring algorithm was executed to the spanning tree and the same color edge gossiped at the same time. These two algorithms decreased the number of exchange information and computational complexity and boosted the convergence rate. The proposed algorithms were verified by using the random matrix theory and graph theory. Computer simulations were also conducted to show the validity of the theoretical results.
 

Key words: time synchronization, gossip algorithm, wireless sensor networks

CLC Number: