上海交通大学学报(自然版) ›› 2014, Vol. 48 ›› Issue (03): 351-356.

• 无线电电子学、电信技术 • 上一篇    下一篇

基于Gossip算法的无线传感器网络时间同步

师超1,仇洪冰1,2,王俊义2,李晓艳1
  

  1. (1. 西安电子科技大学 通信工程学院,  西安 710071; 2. 桂林电子科技大学 信息与通信学院, 广西 桂林 541004)
     
  • 收稿日期:2013-04-07 出版日期:2014-03-28 发布日期:2014-03-28
  • 基金资助:

    国家自然科学基金资助项目(61071088,61231008,61261017)

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

摘要:

将Gossip算法用于实现无线传感网络的分布式时间同步,提出单Gossip同步算法和多Gossip同步算法,解决传统无线传感器网络时间同步算法中存在的计算复杂度高和同步收敛速度慢等问题.单Gossip同步算法首先利用构造生成树算法得到一个生成树,然后,依次对生成树每条边的两节点时钟信息进行Gossip运算,反复循环,最终可使网络各节点的时钟信息收敛于它们初始时钟信息的平均值.多Gossip同步算法对生成树进行边染色,相同染色的边可以同时进行Gossip运算.这2种同步算法减小了消息交换数,降低了计算复杂度,提高了同步的收敛速度.用随机矩阵理论和图论进行了理论证明,通过计算机仿真对理论分析进行了数据验证.
 

关键词: 时间同步, Gossip算法, 无线传感器网络

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

中图分类号: