一种基于传播时延修正的网络时间互同步算法*

喻歆

(中国西南电子技术研究所，成都 610036)

1 引言

随着微机电系统和无线通信技术的不断发展，无线传感器网络(Wireless Sensor Network，WSN)在人体、动植物和环境监控，生化威胁探测，国土安全，以及诸多军事应用领域已经开始发挥出重要的功用［1－2］。网络时间同步指的是将网络中的所有时钟校正到同一个时间标准的过程，其对WSNs诸多操作和功能的正常运转起到了至关重要的作用［2］。

全球导航卫星系统(Global Navigation Satellite Systems，GNSS)能够很容易地解决时间同步问题，并且获得较高的精度［3］。但该方法对每个网络节点的硬件配置提出了额外要求，增加了成本，并且满足硬件配置要求的节点也无法与缺少相关硬件配置的网络节点进行时间同步。此外，即使所有网络节点都具备了通过GNSS进行时间同步的硬件配置，受通信系统所处环境(如室内、地下、森林等)影响，GNSS也无法总是提供可靠的网络时钟参考。因此，必须设计额外的网络时间同步机制。

过去十多年间，学者们提出了许多有效的时间同步算法［4－10］，这些算法大致可以分为中心式和分布式两类。中心式方法中，网络中存在一个参考时钟或称为主时钟，网络中的其他时钟都以主时钟为基准进行校正，而分布式方法则不需要参考时钟。较为流行的中心式方法包括TPSN(Time－synchronization Protocol for Sensor Networks)［6］、FTSP(Flooding Time Synchronization Protocol)［7］和 RBS(Reference Broadcast Synchronization)［8］。TPSN 和 FTSP中，当节点失效或者在移动环境中，选择新的根节点需要额外的通信开销。此外，叶子节点到根节点的距离会直接影响其同步精度。RBS中，主节点的选择和网络分簇的过程中都会引入较大的通信开销。分布式时间同步方法没有主时钟节点，因此不受单点失效的影响，具有较强的健壮性。同时，没有对主时钟节点的选择、管理和维护也使得这类时间同步方法具备较小的开销。

近年来，一种基于时钟采样的网络时间互同步(Clock－Sampling Mutual Network Synchronization，CS－MNS)［9］算法因其简单有效的特性备受关注，并且已经被用于实际系统当中［10］。CS－MNS算法中，每个节点与其1跳邻居周期交互同步消息，并基于该信息修正调整时钟偏移和时钟频率偏移的校正因子。CS－MNS算法具有诸多优点，例如无需直接访问物理时钟，无需主时钟，实现简单，同步精度较高等［9］。然而，CS－MNS并没有考虑各种时延对其性能的影响，这可能导致其在某些场景尤其是在具有较大地理覆盖范围的网络中性能不能满足要求。因此，本文首先简单介绍CS－MNS算法并分析其性能，然后对其进行改进，以期提高该算法在覆盖更大地理范围和处于更复杂环境中的Ad Hoc网络中的性能。

2 CS－MNS算法简介及分析

2.1 时钟定义及问题描述

一个包含N个节点的网络，每个节点的时钟都有不同的时钟频率偏移和初始时间，即第i个节点时钟的时间过程Ti(t)表示为

式中，t为真实时间，βi表示第i个时钟相对于真实时间的时钟频率偏移，Ti(0)为第 i个时钟的初始时间。

时间同步算法的目标是使网络中的所有时钟的时间过程满足:对于任意的i≠j，都有

其中，tc表示算法的收敛时间，ΔT表示容忍的同步误差。

2.2 CS－MNS 算法简介

CS－MNS对虚拟时钟进行同步，虚拟时戳由真实时戳乘上校正因子获得;CS－MNS根据收到的虚拟时戳消息对校正因子进行修正，从而达到同步虚拟时钟的目的［9］。虚拟时戳和校正因子的修正表达式分别为

式中，τ为采样周期，常数kp称为控制增益为第i个节点收到的发送时钟发送的时戳消息。

从公式(3)可以看出，每个节点发送时戳消息时只需包含发送该消息时本地的虚拟时戳;一个节点一旦接收到一条有效的时戳消息，就能立即独立地对时钟偏移和时钟频率偏移进行校正。

需要注意的是，CS－MNS不能为网络提供统一的绝对参考时间，但是统一的虚拟时钟能够保证如TDMA类协议的正常运转。

2.3 CS－MNS 算法的仿真分析

2.3.1 仿真环境设置

文献［9］在只有两个节点的场景中理论证明了CS－MNS的稳定性和收敛性，并通过仿真分析了CS－MNS在较大的网络规模(节点数60～140)、不同的控制增益kp(取值0.1～1.95)和不同的晶振稳定性(时钟偏移频率在某个时间段内发生突变)时的性能。为了更深入地分析和理解CS－MNS在不同场景中的性能，并考虑到本研究的应用场景，本文针对相对较小规模和较稀疏的网络展开一系列研究和分析。

每一次仿真时，算法每完成一次同步迭代操作，我们就记录当前网络中所有节点虚拟时间之间的最大差值的绝对值;针对每一组参数，我们都执行了100次仿真，最终仿真结果由100次仿真的平均值得到。算法使用MATLAB编码实现，开发环境为MATLAB Version 7.1.0.246(R14)Service Pack 3，平台环境为Windows XP Professional SP 3操作系统，Intel Core 2 Quad CPU Q8400@ 2.66 GHz 2.66 GHz的 CPU，以及1.96 GB 的内存。

2.3.2 仿真结果及分析

本文一共进行了5组仿真，每组仿真采用的公共参数设置如表1所示。

5组仿真中，仿真1研究网络节点密度，即节点的平均单跳邻居数目的影响;仿真2研究消息交互周期的影响;仿真3研究消息接收成功率的影响;仿真4研究不同拓扑结构(体现在网络节点密度和网络覆盖范围)的影响;仿真5综合研究各种因素包括网络覆盖范围、网络节点密度、网络动态性以及消息传播时延的影响。每组仿真各自的仿真参数如表2所示。

表1 每组仿真采用的公共参数设置Table 1 Common parameters setting of all simulations

表2 每组仿真采用的参数设置(区间符号表示取区间内的随机值)Table 2 Other parameters setting of each simulation(interval notation means random values within the range)

图1 仿真4中测试的3种拓扑结构:链式、环式和网格Fig.1 Three network topologies tested in the fourth simulation:tandem，ring and grid

根据仿真结果可以观察到的现象以及得出的结论分析如下:

首先，在消息接收成功率100%的前提下，网络节点密度越大，算法的收敛速度越快。网络节点密度较小时(2个节点和4个节点)，算法甚至会先经历一个发散的过程，最终才会收敛到一个稳定状态。网络节点密度越大，每个节点修正自己时间时，就能参考网络中更多节点的折衷时间信息，从而加速了收敛的过程;

其次，消息交互周期越长，算法收敛速度越慢;消息接收成功率越低，算法收敛速度越慢。原因很直观，因为消息交互周期的变长和消息接收成功率的降低都会导致节点之间时戳消息交互次数的减少，从而减少了算法的成功迭代次数。对于一些基于竞争的MAC(Media Access Control)层接入协议，网络节点密度的增大将增加节点之间碰撞的概率，导致消息接收成功率降低［11］，所以使用此类MAC协议的网络中，节点密度的增大并不总是会加快CS－MNS的收敛过程。此外，虽然缩短消息交互周期可以提高算法收敛速度，但是增加了网络开销。还需注意的是，即使在消息接收成功率只有20%时，算法仍然能够收敛;

第三，仿真网格拓扑结构收敛最快，链式拓扑结构收敛最慢。仔细分析各拓扑结构，链式结构中，节点之间最小间隔跳数的最大值为7，节点平均邻居数约为1.78;环式结构中，节点之间最小间隔跳数的最大值为4，节点平均邻居数为2;网格结构中，节点之间最小间隔跳数的最大值为3，节点平均邻居数为2.67。由前面分析结果，在100%的消息接收成功率前提下，节点平均邻居数越多，收敛越快;此外，节点之间间隔跳数越多，单跳之间时间相互修正的结果传播到全网就需要越长的时间，因此算法在网格结构中收敛最快，链式结构中收敛最慢;

最后，仿真网络动态性越高(节点移动速度越快)，算法收敛越快。这是因为，动态性越高的网络，节点的平局邻居数在时间轴上作平均后大于动态性较低的网络中对应的值。此外，可以发现由于考虑了传播时延，虽然算法能够收敛，但是同步精度受到了较大的影响。

综上，CS－MNS算法具有很强的健壮性，其在不同场景和环境中都能够保证收敛。但是该算法受消息传播时延影响较大，同步精度性能较差(达到了1 ms左右)。

3 CS－MNS算法的改进

3.1 基于传播时延修正的CS－MNS算法

从对CS－MNS的仿真分析中可以发现传播时延对其同步精度的性能影响较大，而在实际的应用场景中，尤其是在节点之间间距较远时传播时延是不能忽略的。因此，本文设计了一种基于传播时延修正的 CS－MNS算法，记为 CS－MNS－d，以改进算法在实际应用场景中的同步精度性能。

具体地，CS－MNS－d根据传播时延对公式(3)所示CS－MNS的校正因子递归控制规则进行了修正。新的校正因子递归控制规则如下所示:

根据真实时戳计算节点间传播时延原理如图2所示。计算时，忽略了节点i和j之间的时钟频率偏移差别。

图2 传播时延计算原理图Fig.2 The principle of calculating propagation delay

令ΔTij表示之间的时钟偏差，则有

由公式(5)和公式(6)可得

注意，T1和T4为节点i的真实时戳，T2和T3为节点j的真实时戳。因此，每个节点发送的同步消息中需要同时包含虚拟和真实时戳。

3.2 仿真性能对比

采用与上一节仿真5完全一样的场景和算法参数设置，经过100次仿真后，CS－MNS－d的仿真结果如图3所示。

图3 CS－MNS－d在仿真5场景中的仿真结果Fig.3 Results of the CS－MNS－d algorithm in the scenario of the fifth simulation

由图3所示结果可以看出，CS－MNS－d在3种动态场景中都能快速收敛，即使在最慢的情况下(节点移动时间间隔∈［11，15］s)，算法在不到40s的时间内同步误差能够达到100μs以下，在不到60s的时间内同步误差能够达到50μs以下，而CS－MNS在最好情况下在30s左右就接近收敛，并且最终收敛时的同步误差也在1000μs以上。因此，相对于 CS－MNS，CS－MNS－d 更适用于传播时延不能忽略的覆盖了较大地理范围的实际无线通信网络中。

4 结语

本文通过仿真分析，说明了CS－MNS算法具有较强的健壮性，以及其在不同场景和环境中具有较好的收敛性，但是该CS－MNS算法受消息传播时延影响较大。基于此，本文提出了一种基于传播时延修正的改进算法，仿真结果表明，改进后的算法在不能忽略传播时延的环境中同步精度大大提高，具有一定的实际应用价值。CS－MNS还存在一些需要进一步改善的地方，例如算法迭代初期，网络中的时钟会有一个发散的过程，因此增加了算法收敛的时间;再如，如果网络初始时间相差非常大时CS－MNS会不稳定等，这些都是进一步研究的重点。

［1］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14(7):1282－1291.REN Feng－yuan，HUANG Hai－ning，LIN Chuang.Wireless Sensor Networks［J］. Journal of Software，2003，14(7):1282－1291.(in Chinese)

［2］Wu Y－C，Chaudhari Q，Serpedin E.Clock Synchronization of Wireless Sensor Networks［J］.IEEE Signal Processing Magazine，2011，28(1):124－138.

［3］黄琳，马文杰，李国军，等.基于GNSS的通信星座系统的时间同步研究［J］.航天器工程，2010，19(6):67－74.HUANG Lin，MA Wen－jie，LI Guo－jun，et al.Study on GNSS－based Time Synchronization for a Communications Satellite Constellation System［J］.Spacecraft Engineering，2010，19(6):67－74.(in Chinese)

［4］Sivrikaya F，Yener B.Time Synchronization in Sensor Networks:A Survey［J］.IEEE Network，2004，18(4):45－50.

［5］易胜蓝.嵌入式Linux下IEEE 1588时间同步的实现［J］.电讯技术，2012，52(5):800－803.YI Sheng－lan.Implementation of IEEE 1588 Time Synchronization under Embedded Linux［J］.Telecommunication Engineering，2012，52(5):800－803.(in Chinese)

［6］Ganeriwal S，Kumar R，Srivastava M B.Timing－sync Protocol for Sensor Networks［M］.New York:ACM Press，2003:138－149.

［7］Maroti M，Kusy B，Simon G，et al.The Flooding Time Synchronization Protocol［M］.New York:ACM Press，2004:39－49.

［8］Elson J，Girod L，Estrin D.Fine－grained Network Time Synchronization Using Reference Broadcasts［C］//Proceedings of the Fifth Symposium on Operating System Design and Implementation.Boston，MA:IEEE，2002:163－167.

［9］Rentel C H，Kunz T.A Mutual Network Synchronization Method for Wireless Ad Hoc and Sensor Networks［J］.IEEE Transactions on Mobile Computing，2008，7(5):633－646.

［10］Kunz T，MacNeil M.Implementing Clock Synchronization in WSN:CS－MNS vs.FTSP［C］//Proceedings of the 2011 IEEE 7th International Conference on Wireless and Mobile Computing，Networking and Communications.Wuhan:IEEE，2011:157－164.

［11］蹇强，龚正虎，朱培栋，等.无线传感器网络MAC协议研究进展［J］.软件学报，2008，19(2):389－403.JIAN Qiang，GONG Zheng－hu，ZHU Pei－dong，et al.Overview of MAC Protocols in Wireless Sensor Networks［J］.Journal of Software，2008，19(2):389 －403.(in Chinese)