无线传感网络中时钟同步的研究

　　无线传感网不同于现有的无线自组网，它的每个网络节点都受到计算能力、通信能力、储存能力和带电能力等诸多限制，并且以数据为中心、动态自组。正由于其上述限制，目前很多成熟的网络协议不再适合无线传感网，时钟同步协议就是其中之一。

　　1 时钟同步适用范围

　　时钟同步就是通过一定的机制使系统各节点的时间与标准时间同步，通常采用与协调世界时UTC(Coordinated Universal Time）同步。

　　有线网络设计的最终目的在于利用现有资源最大限度地增大链路带宽，提高服务质量，因而具有相对稳定的网络结构，可靠的链路连接，充足的能量供给。运行在其上的网络协议通常很少考虑节约能量，降低节点负载，充分挖掘运行效率。所以其时钟同步协议将更多以算法的精度、鲁棒性和易扩充性为标准。

　　无线传感网作为一个大范围的分布式网络，像其他网络一样，也需要时钟同步以达到系统事件的协调控制，正确的数据融合。但它受能量供给、节点计算能力、链路质量的限制，必须对现有的时钟同步协议重新分析和评估。如应用于Internet的网络时间协议NTP(Network Time Protocol)，它采用层次结构，次层节点通过两次包交换达到与上层节点时钟同步，但由于其运算复杂，且需要较稳定的网络结构作为支撑，因而不适应对于能量、体积和计算能力都受限制且动态性强的无线传感网络。

　　2 无线传感网络中时钟同步的基本概念

　　2.1 相关定义

　　要分析时钟偏差，需给出如下定义。
　　(1)时间：Cp（t）表示网络节点p的时间，当Cp（t）=t，表示p的时间与标准时间同步。
　　(2)震荡频率：时钟所拥有的震荡频率，在t时刻p节点的时钟频率为Cp（t）′。
　　(3)时钟偏差：表示某时钟与标准时钟的偏差，Cp（t）-t。两个不同节点p和l的时钟在t时刻的偏差可表示为Offset＝Cp（t）-Cl（t）。
　　(4)频率偏差：表示某时钟和标准时钟的频率偏差。两个不同时钟的Skew=Cp（t）′-Cl（t）′。

　　如果频率偏差限制在ρ，标准时钟频率为1，则时钟频率将在(1-ρ，1+ρ)中变化。快慢时钟与标准时钟的比较如图1所示。

　　(5)时钟偏移：表示时钟函数的二阶倒数Cp（t）″，两个不同时钟的Drift=Cp（t）″-Cl（t）″。
　　
　　从图1中可以发现，即使时钟在开始是同步的，经过一段时间后，由于时钟频率的不同而不断积累的时钟偏差将越来越明显。

　　2.2 网络延时分析

　　网络传输总会产生消息延时，因此一个节点的时间戳在到达对方节点时已不能代表自身的时间。这就需要对网络延时作充分的分析，确定延时带来的误差来源。无线传感网中消息发生延时的环节很多，其中主要存在于发送时间、访问时间、传送时间、广播时间、收到时间、接收时间、中断处理时间、编码时间和解码时间。其中每个环节都可能带来延时误差，对误差充分、准确的估计才能设计出精确度高、负载低的时钟同步算法。

　　3 无线传感网时钟同步协议分析

　　Jeremy Elson和Kay Romer在2002年8月的HotNets-I国际会议上率先提出并阐述了无线传感网中时钟同步机制的研究课题，在传感网络研究领域引起了关注。目前提出的基本同步机制有RBS、TPSN和DMTS等，同时新的算法仍在不断涌现，如TINY/MINI-SYNC和FTSP等。

　　3.1 RBS时钟同步协议

　　RBS(Reference Broadcast Synchronization)参考广播时钟同步协议是利用无线链路层广播信道的特点，一个节点发送广播消息，认为在同一广播域的其他节点同时收到广播消息，并记录该点的时间戳，之后接收节点通过消息交换它们的时间戳，通过比较和计算，达到高度精确时钟同步。时钟同步协议的关键路径如图2所示。对于传统的时钟同步协议关键路径是指从发送端读取时钟到接收端读取时钟所经过的时间，其中包含了信息包在进入信道之前在网络适配器(NIC)内的停留时间，如图2 (a)所示。而RBS的关键路径指从信息包进入信道到最后一个接收端读取时钟所经过的时间，消除了发送和访问时间，从而提高了精度，这也是RBS的优点所在，从图2可以看出RBS协议和传统的基于发送/接收方式的时钟同步协议在影响非决定性误差上有着明显的差异。

　　在RBS时钟同步协议中为了对网络上可能出现的非确定性延时作相应的补偿，采用了多次发包求平均值的方案。RBS的时间偏差为：
　　　　
　　其中，i，j代表不同节点。K为数据包的序列号，m表示最大次数。

　　RBS的另一个特色是无本地时钟校正，把计算出来的时钟偏差和频率偏差值保存在一张表中，当其他节点读本地时间时，本地节点将会查询该表翻译出正确的时间。这主要是从减少能量消耗的角度考虑。此外RBS协议还采用了次 同步方式，就是只有在时钟同步需要时才运行，这样大大减少了能量的消耗。RBS在多跳网络中也有应用。

　　3.2 TPSN时钟同步协议

　　无线传感网络时间同步协议TPSN(Timing- sync Protocol for Sensor Networks）与传统的NTP协议类似，采用如图3所示的两次握手交换时间戳来达到时钟同步。假设t为服务器和客户端之间的时间偏差，d为两者之间的往返时间。则由于：
　　

　　计算出时钟偏差t后就可以相应地调整本地时钟与上一层节点同步。为减小访问时间带来的延时误差，TPSN在MAC层开始发送时才打上发送时间戳。在 Mica平台测试的结果表明TPSN时钟同步平均偏差是16.9μs，而RBS是29.13μs，可见TPSN拥有更精确的时钟同步。TPSN时钟同步过程分为两阶段：第一阶段是层次发现阶段。该阶段是在网络部署后将网络节点层次化。分为0到n个层次；第二个阶段为时钟同步阶段，层次结构建立后，通过同步广播包，从0层次到n层次逐层时钟同步。TPSN协议可以支持外部时钟源，使整个无线传感网与外部时钟同步，通常采用根节点装载GPS同步设备。

　　3.3 DMTS时钟同步协议

　　延迟测量时间同步DMTS（Delay Measurement Time Synchronization）协议是利用合理的估计网络延时来设计时钟同步算法。时钟同步的步骤是：(1)在所有节点中选择一个主节点；(2)主节点广播其本地时钟，并且在发送前导帧和起始符时打上时间戳t0，前导帧和起始符主要用于接收节点进行接受同步；(3)接收节点收到广播分组后打上时间戳t1，并且在调整自身时钟前打上时间戳t2。该过程中假设发送1比特位需要时间为t，发送信息位的个数是n，则接收节点应该调整自己的时钟为t0＋nt＋（t2－t1）。图4说明了DMTS协议的时钟同步过程。

　　DMTS协议的精确性主要取决于延时测量的精确度，是一种灵活、轻量级、能量利用高效的时钟同步机制，可应用于时钟同步要求不太高的无线传感网络中。该机制还能够更好地支持与外部时钟源及多跳点的同步。

　　3.4 连续时钟同步协议

　　在时钟同步协议中，要求在重新调整时钟时不可以向后调整时钟，时钟的调整应该是一个逐渐平滑的过程，以保持系统事件的连续性。假设在18时第一次同步，在 20时第二次同步，而某系统事件定在19时发生，若采用瞬间同步，则系统就会将该事件忽略，导致数据不完整。连续时钟同步协议扩展了IEEE802.11 标准，采用了增大或减小时钟频率的方法来调整本地时钟与时钟源同步。

　　连续时钟同步协议中的时间路径如图5所示。主节点在t1时间准备一个指示分组，在t2时间向邻近节点广播；假设该分组被邻近节点及时接收，即在t3时间接收到分组且在t4时间记录本地的时间戳；在t5时间主节点又会发送一个确认分组。最后每个接收节点计算与主节点的时钟偏差并在t6时间调整本地时钟。这里的本地时钟是指与本地物理时钟相对应的虚拟时钟。

　　3.5 其他时无线网络时钟同步协议

　　作为一个新的领域无线传感网的很多协议没有向Internet上的协议那样有统一的标准，而且常常是一个协议在一个平台上是最优的，但到另外的平台可能不再是最优，所以相关的协议也在不断的发展中。时钟同步中也还有其他很多优秀的协议，如Maroti M等人提出的洪泛时间同步协议FTSP（Flooding Time Synchronization Protocol），Chaudhuri P提出的随机时钟同步协议PCS（Probabilistic Clock Synchronization）等。

　　4 协议比较

　　上述各种协议的设计思想都有不同的侧重点，所以在具备很多优点的同时也携带着这样或那样的不足。因此在选择相关协议或设计新的协议时都必须要权衡这些因素。以下是关于这些协议的优缺点比较。

　　RBS时钟同步协议中发送和媒体访问的时间偏差(即最大的时钟误差来源)被去除了。时钟的调整不会影响时钟偏差的计算，因为该协议不会调整本地的时钟，而是维持了一张时钟偏差表。RBS协议不仅适用于无线网络，也适用于有线网络。RBS的不足之处也很多，最重要的一个就是拥有O(N2)的时间复杂度，这对于能量有限的无线传感网而言是最大的能量开销。

　　TPSN时钟同步协议取得了比RSB更精确的时钟同步效果，而且方便地支持与外部时钟源同步。但是其能量开销相对较大，其最大的不足是在基于层次模型的情况下不利于网络的动态变化，而无线传感网的一个特点就是网络具有动态性。

　　DMTS时钟同步协议和上述两种协议相比需要传输的消息少，能量开销小，可以在全网络中时钟同步，并且支持与外部时钟源同步。但是，这种算法在能量开销与同步精度之间做了折中 ，所以精度相对弱些，可以应用于对精度要求不是很高的无线传感网络中。

　　连续时钟同步协议在传输延时很小的情况下，可达到较高的精度要求。时间复杂度也很小，一次同步只需要一次发包。尤其是采用了连续调整时钟的方法使得系统事件控制的连续性得以保证。

　　同样，其他的时钟同步协议也具有各种优缺点，这些因素都决定了协议的设计平台和系统的应用领域。

　　时钟同步协议是无线传感网的一个必不可少的要素，为系统的其他功能(如事件的协调、节点定位、系统安全等)提供了一个统一的时间轴。所以无线传感网时钟同步协议的研究和创新具有重要意义。

　　参考文献

1 Romer K.Time synchronization in adhoc networks.ACM Int′l symp mobile AD Hoc Networking and computing(MobiHoc)，Long Beach，USA，2001
2 Elson J，Griod L，Esrein D.Fine-grained network time syn　chronization using reference broadcasts.In：Proc 5th symp operating systems design and implementation，Boston，MA， 2002
3 Sichitiu M L，Veeraritiphan C，Simple accurate time synchronization for wireless sensor networks.In：Proceedings of IEEE wireless communication and networking conference，2003
4 Gurewitz O，Cidon I，Sidi M.Network time synchronization using clock offset optimization.In：Proceeding of the 11th IEEE international conference on network protocols(ICNP′03)， 2003
5 Mock M，Frings R，Nett E et al.Continuous clock synchro- nization in wireless real-time applications.In：Proceedings of 19th IEEE synposium on reliable distributed systems，2002