摘要： 传统时间同步算法RBS、TPSN、FTSP、DMTS等建立拓扑结构来实现时间同步，这种算法中一旦根节点或重要路由节点失效，其他节点将不能进行时间同步。为了更好的解决这个问题，文章提出了一种基于Markov链的分布式时间同步算法，通过将时间同步过程映射到markov链的状态转移过程，最终通过markov链收敛来实现全网节点的时间同步。应用结果表明：随着时间的推移，模型的全网节点时间能迅速趋于一致，从而解决了集中式时间同步算法存在的抗毁性差的问题。

　　关键词： Markov链；数学模型；时间同步

　　中图分类号：TP311 文献标识码：A 文章编号：1006-4311（2013）16-0209-02

　　0 引言

　　传统时间同步算法RBS、TPSN、FTSP、DMTS等建立拓扑结构来实现时间同步[1]，这种算法中一旦根节点或重要路由节点失效，其他节点将不能进行时间同步。

　　近年来出现的分布式时间同步协议DCTS[2-5]通过邻居节点间的信息融合，使全网节点都同步到一个虚拟的时间，避免了根节点失效所带来的问题。但DCTS依赖于扩散传递同步信息，其收敛速度很慢。

　　为了更好地解决上述问题，本文考虑将时间同步过程映射到马尔可夫链状态转移过程。

　　1 问题背景及数学模型

　　分布式时间同步算法中每个节点通过与邻居节点交换时间信息，把自己下一时刻的时间信息更新为自己及邻居节点当前时间信息的加权和。于是，节点vi本地时间信息的迭代更新过程可以用数学模型式（1）来表示，其中m为迭代次数，Ni为vi的邻居节点集合，Wij表示vi更新时间信息时节点vj对应的权重。

　　一个网络可以用图的方式表示为N（V，E），其中V={v1，v2，…，vn}表示节点集合，E对应于节点间的单跳通信链路集合E={（i，j）}。假设网络是强连通的，节点间的通信双向可达。令t（m）=（t1（m），t2（m），…，tn（m））为网络节点在m时刻的时间信息向量，W为一阶更新迭代矩阵，DCTS的迭代过程可用矩阵形式（2）来表示：

　　本文采用马尔可夫链的相关理论来分析DCTS算法的收敛特性，首先把DCTS的迭代过程映射为马尔可夫链的状态转移过程。映射关系如式（3），其中网络中的节点对应于马尔可夫链的各个状态S={s1，s2，…，sn}，为区别于迭代矩阵W，用P表示马尔可夫链的转移概率矩阵。

　　2 基于Markov链的时间同步算法实现

　　2.1 算法的收敛性

　　在强连通且节点数有限的网络中，DCTS迭代映射得到的马尔可夫链MN是有限不可约遍历链。根据马尔可夫链的相关理论可知，存在正整数k，使Pk>0，式（4）中第一部分成立，其中π是马尔可夫链MN的唯一稳态分布，是满足1Tπ=1的正列向量。

　　2.2 时间同步算法实现

　　每个节点通过与邻居节点交换时间信息，把自己下一时刻的时间信息更新为自己及邻居节点当前时间信息的加权和。当迭代有限次数后，马尔可夫链达到均匀稳态分布，所有网络节点的时间趋于一致，完成全网节点的时间同步。

　　3 结论

　　文章通过建立分布式时间同步算法的Markov链数学模型，实现了全网节点的时间同步，解决了集中式时间同步算法存在的抗毁性差的问题。另外，为了更好地实现算法的时间同步速度，接下来的研究中可考虑对Markov链数学模型进行加速设计，以实现更快的时间同步速度。

　　参考文献：

　　[1]D. Culler， D. Estrin， and M. Srivastava， "Overview of Sensor Networks，" IEEE Computer， vol. 37， no. 8， pp. 41-49， Aug. 2004.

　　[2]Schenato L and Gamba G. A distributed consensus protocol for clock synchronization in wireless sensor network. 46th IEEE Conference on Decision and Control， New Orleans， LA， USA， 2007： 2289-2294.

　　[3]Gang X and Kishore S. Second order distributed consensus time synchronization algorithm for wireless sensor networks. Global Telecommunications Conference， IEEE， New Orleans， LA， USA， 2008： 1-5.

　　[4]Sommer P and Wattenhofer R. Gradient clock synchroni-zation in wireless sensor networks. International Conference on Information Processing in Sensor Networks， San Francisco， USA， 2009： 37-48.

　　[5]Li Q， Rus D. Global clock synchronization in sensor networks.IEEE Transactions on Computers， 2006， 55（2）： 214-226.