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

Time Synchronization for Wireless Sensor Networks Based on Gossip Algorithm

作　　者：师超[1] 仇洪冰[1,2] 王俊义[2] 李晓艳[1] 

机构地区：[1]西安电子科技大学通信工程学院,西安710071 [2]桂林电子科技大学信息与通信学院,广西桂林541004

出　　处：《上海交通大学学报》2014年第3期351-356,362,共7页Journal of Shanghai Jiaotong University

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

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

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

分 类 号：TN929.5[电子电信—通信与信息系统]