第7章时间同步技术

1、第七章 时间同步技术 l 时间同步技术概述l 时间同步技术研究现状与发展l 时间同步技术关键问题l 传统时间同步技术l 新型时间同步技术第七章 时间同步技术时间同步时间同步：使网络中所有节点的时间保持一致，按照网络应用的深度可以分为三种不同的情况：u第一种第一种：时序确定，判断事件发生的先后顺序，对本地时间的要求比较低，只需要知道本节点与其余节点的相对时间即可u第二种第二种：相对同步，节点维护自己的本地时钟，周期性地获取其邻居节点与本节点的时钟偏移，实现本节点与邻居节点的时间同步u第三种第三种：绝对同步，所有节点的本地时间严格同步，等同于标准时间，这种情况对节点的要求最高，因此实现也最为复杂时

2、间同步的参考时间来源也有两种情况：u外同步外同步：标准参考时间来自于外部u内同步内同步：参考时间来自于网络内部某个节点的时间第七章 时间同步技术l 时间同步技术概述无线传感器网络时间同步协议必须要解决三个方面的问题：同步的误差要尽可能地小，这样才能保证整个网络间节点应用的正常进行因为无线传感器网络节点的电池不可替换，因此协议要尽可能地简单，功耗要低，以尽可能地延长网络的生命周期具有可扩展性，随着无线传感器网络规模的扩大，时间同步协议要同样有效第七章 时间同步技术l 时间同步技术概述第七章 时间同步技术l 时间同步技术概述时间同步的两个重要的时间参数：时钟偏移时钟偏移：在真实时刻t时定义时钟偏移

3、为c(t)t，即本地时间与真实时间的差值。时钟漂移时钟漂移：在真实时刻t时定义时钟漂移为(t)=r(t)1，即本地时间变化速率与1的差值。在节点的两种时间计数方式：硬件计数硬件计数模式：模式：即利用晶振来实现时间的计数软件时钟软件时钟模式：模式：采用虚拟的软件时钟来实现时钟的计数1硬件时钟模硬件时钟模式式在硬件系统的时钟计数中，计算时间的一个重要的公式是：式中，w(t)是晶振的角频率，k是依赖于晶体物理特性的常量，t是真实时间变量， c(t)是当真实时间为t时节点的本地时间。2软件时钟软件时钟模式模式在软件时钟模型中，也存在一个用于记录时钟脉冲的计数器，软件时钟模型与硬件模型不同，它不直接修改

4、本地时钟，而是根据本地时钟h(t)与真实时间的关系来换算成真实时间的函数c(h(t)。c(h(t)=t0+h(t)h(t0)就是一个最简单的虚拟软件时钟的例子，实际应用中，软件时钟还要考虑到时钟漂移对时钟的影响，因此更加复杂。第七章 时间同步技术l 时间同步技术概述到目前为止，时间同步技术的研究已经有了30年之久，最早的时间同步机制是美国一所大学提出的网络时间协议（NTP）。NTP协议的时间同步精度可以达到毫秒级，通过外界一个精准的时间源接收机，顶层的时间服务器可以获得高精度的参考时间，并向全网内提供统一的时间服务。第七章 时间同步技术l时间同步技术研究现状与发展NTPNTP协议采用的是分层结

5、构，拓扑结构如图所示，整个NTP协议分为三层结构，其中A1、A2、A3为顶层的时间服务器，B1、B2、B3为第二层时间服务器，其余均为客户机。第一层时间服务器通过GPRS或者广播网络等方式来获得标准的UTC时间，其他层的时间服务器或者客户机选择一个或者多个上一层的时间服务器来同步本地时间，从而使整个网络所有服务器和客户机时间同步。第七章 时间同步技术l时间同步技术研究现状与发展NTP通过上层服务器的标准参考时间，服务器利用一个闭环控制系统来调整自己的本地时间第七章 时间同步技术l时间同步技术研究现状与发展NTP1973年，美国国防部为了实现军事部门对海陆空设施进行高精度导航和定位，建立了一种新

6、的网络系统GPS网络系统，该系统成为继阿波罗登月计划和航天飞机计划之后的第三项庞大空间计划，它从根本上解决了人类在地球上的导航和定位问题，在军事和工农业等领域得到了广泛的应用。GPS系统由三个部分组成：空间卫星空间卫星、地面监控地面监控和用户终端用户终端。由于GPS信号的穿透性比较差，为了接收到GPS的信号，GPS天线必须安装在空旷的室外，并且要求没有高大阻挡物体，加上接收机功耗比较大，因此不适宜在无线传感器网络中应用。第七章 时间同步技术l时间同步技术研究现状与发展GPS在设计无线传感器网络的时间同步协议时，需要满足以下几点要求： 能量有限 可扩展 稳定性第七章 时间同步技术l时间同步技术关

7、键问题1、传输延迟不可预测传输延迟不可预测无线传感器网络中，时间同步技术的一个重要难题是报文传输延迟的不确定，由于处理器处理能力有限、网络负载不确定等因素的影响，延迟不能够被精确地计算出来；另外传输延迟比要求的时间同步的精度要大得多。第七章 时间同步技术l时间同步技术关键问题影响时间同步的传输时延发送时间发送时间：发送方用于组装并将报文换交给发送方MAC层的时间。访问时间访问时间：指在发送方MAC层从获得报文后到获取无线信道发送权的等待时间。传送时间传送时间：发送方发送报文的时间，即从报文的第一个字节开始发送到发送完最后一个字节的时间。传播时间传播时间：报文从发送方以电磁波的形式传送到接收方所

8、花费的时间。接收时间接收时间：接收方接收报文的时间。它和传送时间完全相同，具有确定性。接受时间接受时间：用于处理接收到的报文的时间。第七章 时间同步技术l时间同步技术关键问题第七章 时间同步技术l时间同步技术关键问题2高能效高能效无线传感器网络的软/硬件设施要求节点体积尽量小，尽量廉价，因此要求时间同步技术具有高能效的特点。3可扩展、健壮可扩展、健壮采用逐跳的时间同步机制，因此随着网络规模的扩大，时间同步技术必须保证网络扩展后同步误差不会超过误差界限，并且能够稳定工作。第七章 时间同步技术l时间同步技术关键问题发送者发送者-接收者同步模式接收者同步模式：发送者发送带有时间戳的同步包给接收者，同

9、步接收者的时间，这种模式的缺陷是不能够准确地估计算出报文的传输延迟，精度不高，通过单个报文的传输不能够准确地估算传输延迟。主要代表协议为DTMS协议。接收者接收者-接收者同步模式接收者同步模式：多个接收者利用发送者发送的同步包在若干接收者之间进行同步，接收者-接收者模式缩短了关键路径，避免发送者到接收者的关键路径过长而导致的不准确的传输延迟估计，主要代表协议为RBS协议第七章 时间同步技术l传统时间同步技术同步机制第七章 时间同步技术l传统时间同步技术同步机制DMTS协议协议： 一种简单的同步技术，发送者通过发送单个广播报文，同步一跳内的所有节点。该协议主要考虑报文的传输延迟，在设置本地时间时

10、，报文中嵌入的时间为发送时刻的本地时间加上传输延迟的时间。第七章 时间同步技术l传统时间同步技术DMTSDTMS报文同步的传输过程：为了避免发送等待事件对本地时间的干扰，发为了避免发送等待事件对本地时间的干扰，发送方在检测到信道空闲之后才在报文中嵌入发送时间送方在检测到信道空闲之后才在报文中嵌入发送时间t0，根据无线传感器通信协议规定，报文在发送之前需要先发送一定数量的前导码和同步字，根据发送速率我们可以知道单个比特的发送时间为t。而接收者在同步字结束的时候后，记录下此时的本地时间t1，并在即将调整自己的本地时间之前记录下此时的时刻t2，由此我们知道接收方的报文处理延迟为t2t1。接收者将自己

11、的时间改为t0+nt+t2t1，以达到与发送者之间的时间同步。第七章 时间同步技术l传统时间同步技术DMTSDMTS同步协议是一种简单灵活的同步技术，该算法网络流量非常小，能量消耗也非常少，但是没有考虑传播延迟、编/解码的影响，对时钟漂移也没有考虑，同步的精度不是很高，还有待进一步的改进。第七章 时间同步技术l传统时间同步技术DMTS第七章 时间同步技术l传统时间同步技术RBS根据无线信道的广播特性，发送者发送的消息对所有接收节点而言是同一个发送节点发送的，RBS算法利用这个优势来消除发送时间和访问时间所造成的传输时间误差，从而提高时间的同步精度。RBS同步机制的工作流程如下：假设有N个节点组

12、成的单跳网络，1个发送节点，N1个接收节点，发送节点周期性地向接收节点发送参考报文，广播域内的接收节点都将收到该参考报文，并各自记录收到该报文的时刻。接收者们通过交换本地时间戳信息，这样这一组节点就可以计算出它们之间的时钟偏差。RBS算法中广播的时间同步消息与真实的时间戳信息并无多大关系，它也不关心准确的发送和接收时间，而只关心报文传输的差值，RBS同步算法完全排除了发送时间和接收时间的干扰。第七章 时间同步技术l传统时间同步技术RBS在RBS算法中，接收节点只需比较接收节点接收报文的时间之差，因此在发送节点发送的参考报文中无须携带发送节点的本地时间。同步误差只与接收者们是否在同一时刻记录本地

13、时间有关，为了减小时间同步的误差，RBS采用了统计技术，同时广播多个时间同步消息，求相互之间消息到达的时间差的平均值，这样就能在最大程度上消除非同时记录的影响另外对于节点间的时钟漂移情况，RBS采用最小平方误差的线性回归方法，对从某时刻开始的节点间的时钟偏移数据进行线性拟合。考虑RBS协议应用于多跳网络情况：RBS能够消除发送节点引起的同步误差，在忽略传播时间的情况下，主要的误差来源就只剩下接收节点之间的处理时间差，以及发送节点和接收节点间的无线电同步误差，这两者都只有s级，因此RBS算法的同步精度非常高，但RBS算法的网络开销比较大，对于单播域中的n个节点和m个参考广播消息，RBS算法的复杂

14、度为O(mn2)。第七章 时间同步技术l传统时间同步技术RBS在图示网络中存在三个不同的单跳域A、B和C，其中4号和7号节点处于两个单跳域的交界，4号节点可以同步A区域和C区域的时间，7号节点可以同步B区域和C区域的时间，根据这两个节点我们可以得到相邻两区域的时间转换关系，从而达到全网的时间同步。 接收者-接收者同步模式虽然消除了发送方的不确定性，但由于需要在若干节点中交换信息，通信开销较大。S.Ganeriwal从另外一个角度来考虑问题：传统的发送者-接收者同步协议的精确度低的根本原因在于单向报文不能够准确地估算出报文传播延迟，基于报文传输的对称性，采用双向报文就能够解决这个问题，获得较高的

15、精确度，因此他提出了一种双向报文交换协议TPSN。TPSN可以分为层次发现阶段层次发现阶段和时间同步时间同步两个阶段。第七章 时间同步技术l传统时间同步技术TPSN1层次发现阶段层次发现阶段在网络部署后，根节点首先广播以使发现分组，启动层次发现阶段。级别发现分组包含发送节点的ID和级别。根节点是0级节点，在根节点广播域内的节点收到根节点发送的分组后，将自己的级别设置为分组中的级别加1，即为第1级，然后将自己的级别和ID作为新的发现分组广播出去。当一个节点收到第i级节点的广播分组后，记录发送这个广播分组的节点的ID，设置自己的级别为i+1。这个过程持续下去，直到网络内的每个节点都具有一个级别为止

16、。如果节点已经建立自己的级别，就忽略其他的级别发现分组。第七章 时间同步技术l传统时间同步技术TPSN2时间同步阶段时间同步阶段层次结构建立以后，根节点就会广播时间同步分组，启动时间同步阶段。第1级节点收到这个分组后。在等待一段随机时间后，向根节点发送时间同步请求消息包，进行同步过程，与此同时第2级节点会侦听到第1级节点发送的时间同步请求消息包，第2级节点也开始自己的同步过程。这样，时间同步就由根节点扩散到整个网络，最终完成全网的时间同步。建立层次之后，相邻层次之间的节点通过双向报文机制来进行时间同步，假设节点A是第i层的节点，节点B是第i1层的节点，根据TPSN报文交换协议，我们规定T1和T

17、4为节点A的时间，T2和T3为节点B的时间，节点A在T1向节点B发送一个同步报文，节点B在收到该报文后，记录下接收到该报文的时刻T2，并立刻向节点A发回一个应答报文，将时刻T2和该报文的发送时刻T3嵌入到应答报文中。当节点A收到该应答报文后，记录下此时刻T4。我们假设当节点A在T1时刻，A和B的时间偏移为，因为T1到T4两个报文发送的时间非常短，我们可以认为没有变化，假设报文的传输延迟都是相同且对称的，均为d，那么有T2=T1+d T4=T3+d，第七章 时间同步技术l传统时间同步技术TPSN这两个方程联立可解得：=(T2T1)(T4T3)/2， d=(T2T1)+(T4T3)/2在T4时刻，

18、节点A在本地时间上面加上一个偏移量，A和B就达到了同步。从双向同步协议的同步过程中可以看出，在TPSN协议中，当双向报文的传输完全对称时其精确度最高，即同步误差最小。另外TPSN的同步误差与双向报文的传输延迟有关，延迟越短，同步误差越小。第七章 时间同步技术l传统时间同步技术TPSNFTSP（泛洪时间同步协议）也采用单个广播消息实现发送节点与接收节点之间的时间同步，采用同步时间数据的线性回归方法估计时钟漂移和偏差。综合考虑了能量感知、可扩展性、鲁棒性、稳定性和收敛性等方面的要求。FTSP算法实现步骤如下：（1）FTSP算法在完成SYNC字节发射后给时间同步消息标记时间戳并将其发射出去。（2）接

19、收节点记录SYNC字节最后到达时间，并计算位偏移。在收到完整的消息后，接收节点计算位偏移产生的时间延迟，这可通过偏移位数与接收速率得出。（3）接收节点计算与发送节点问的时钟偏移量，然后调整本地时钟和发送节点时间同步。第七章 时间同步技术l传统时间同步技术FTSP1精度方面精度方面RBS协议协议：因为无线信道的广播特性，使得发送节点发出的消息相对所有节点而言是同时发送到物理信道上的，相当于将消息传递过程中两项最不确定的时延被去除了，所以能够得到较高的同步精度。TPSN协议协议：在网络传输的时延中，访问时延的不确定性是最高的。为了提高两个节点之间的时间同步精度，TPSN协议直接在MAC层记录时间信

20、标，这样可以有效地消除发送时延、访问时延、接收处理时延所带来的时间同步误差。并利用双向消息交换计算消息的平均延迟，提高了时间同步的精度。FTSP协议协议：采用在MAC层记录时间信标，细分消息传输中的时间延迟对这些延迟进行补偿，利用线性回归估计时间漂移等措施来降低时间同步误差。第七章 时间同步技术l传统时间同步技术比较2收敛性方面收敛性方面RBS协议协议：发送参考广播的节点是预先选定的，其他节点接收到参考广播消息后，就开始同步的过程。考虑到通信冲突，在几个同步周期后，全网就可以达到时间同步，收敛时间也比较短。TPSN协议协议：这种同步方法的消息传递机制分为两个过程，包括分层阶段和同步阶段，因此其

21、收敛时间较长。FTSP协议协议：该协议的根节点选择过程是伴随时间同步一起进行的，根节点的选择不会对收敛性造成影响，在几个同步周期后，全网就能达到时间同步，收敛时间也比较短。第七章 时间同步技术l传统时间同步技术比较3扩展性方面扩展性方面RBS协议协议：在全网达到同步后，新节点的加入不会影响到参考广播节点的地位，也就不会对全网的结构造成影响。但是，加入新的参考广播节点会使得情况变得复杂，必须考虑处于不同广播域内的节点达到同步的问题。对于多跳网络的RBS协议需要依赖有效的分簇方法，保证簇之间具有共同的节点，以便簇间进行时间同步。TPSN协议协议：从分层过程可以看出，新节点加入后会对网络的拓扑结构造

22、成很大的影响，应此，该协议的扩展性很差，这也是这个协议最大的缺点之一。FTSP协议协议：如果加入的是ID号最小的节点，该节点首先使自己与网络达到同步，然后再进行根节点选择，不会影响网络时间同步。如果不是ID号最小的节点，该节点只需要进行时间同步并广播时间同步消息。第七章 时间同步技术l传统时间同步技术比较4鲁棒性方面鲁棒性方面RBS协议协议：由RBS协议的同步原理可以看出，节点失效或网络通信故障不会破坏整个拓扑结构，每个节点都有大量的冗余消息来保证时间同步。但是参考节点失效就会影响到该节点广播域内所有节点的同步。该协议具有较好的鲁棒性。TPSN协议协议：当某个节点失效，该节点以下的节点就有可能

23、接收不到时间同步消息，这样就会造成连锁反应，影响到该节点所有的后续节点的时间同步。全网的时间同步会受到个别节点的影响，鲁棒性很差。FTSP协议协议：如果是根节点失效，那么其他节点就会开始根节点选择的过程，重新选出一个根节点，这在段时期内会破坏时间同步，但全网很快就能重新达到同步。如果是其他节点失效，由于大量冗余消息的存在，个别节点不会影响全网时间同步。FTSP协议也具有良好的鲁棒性。第七章 时间同步技术l传统时间同步技术比较5能耗方面能耗方面可以利用网络中的节点在一次时间同步中平均接收和发送消息的次数来简单的估计时间同步协议的能耗。RBS协议协议：要实现两个节点之间的时间同步，节点需要接收一次

24、广播消息，然后再交换一次时间同步消息，平均需要2次消息发送和3次消息接收。协议的能量消耗较大。TPSN协议协议：由于这个方法采用的是类客户/服务器模式，所以实现一次时间同步，节点平均需要2次消息发送和2次消息接收，协议的能量消耗相对较小。FTSP协议协议：在该协议中，节点接收到时间同步消息后，使得节点本地时间与全局时间达到同步，然后形成新的时间同步消息并发送出去。每次同步，节点平均需要1次消息发送和1次消息接收，协议的能量消耗是最小的。第七章 时间同步技术l传统时间同步技术比较传统的无线传感器网络时间同步机制的研究已经非常成熟，实用性也非常强，主要应用在单跳网络中，同步误差在Mica2平台上已

25、经达到几至十几微秒的量级，同步功耗也较低，能够满足大多数应用场合的需要。然而，当这些时间同步协议被扩展到多跳网络时，目前普遍采取的方法是首先按照节点之间的通信连接关系建立起一定的网络拓扑结构，在该拓扑结构上，按照时间同步协议的约定，未同步节点和所选定的已同步节点之间通过交换含时间信息的同步报文，从而间接间接地实现与时间基准节点之间的同步。这种同步机制的特点在于：除时间基准节点的邻居节点外，其余节点并不能直接和时间基准节点同步。鉴于它们与传统的因特网时间同步协议（Network Time Protocol，NTP）在该特点上的相似性，故将它们称为无线传感器网络的传统时间同步协议。第七章 时间同步

26、技术l传统时间同步技术分析由于传统时间同步协议在体系结构上的限制，节点不能直接和时间基准节点同步而只能和与时间基准节点存在同步误差的节点进行同步，因此必将出现节点的同步误差随着其离时间基准节点跳距（Hop Distance）的增加而增加的现象，即出现了同步误差的累积同步误差的累积。理论分析和一些实际实验表明，在这些传统的时间同步协议下，即使在最好的情况下，节点的同步误差至少与其跳距的平方根呈正比。随着无线传感器网络的发展，同步误差累积问题将越来越严重：u一方面由于传感器节点体积的不断减小，使得节点的单跳传播距离减小u另一方面由于网络规模的不断扩大使得网络直径不断增加这两个因素均会导致平均节点跳

27、距的增加，使得同步误差的累积现象更加严重。这对大规模无线传感器网络的应用提出了挑战。第七章 时间同步技术l传统时间同步技术分析传统无线传感器网络时间同步协议还面临着可扩展性问题可扩展性问题的挑战：u传统的时间同步协议在同步之前总是力图建立起网络拓扑结构，从而把网络中的所有节点有机地组织起来，u当网络规模较小时，这是完全可行的，但当网络规模较大时，由于无线传输的不稳定性以及节点工作的动态性，只有频繁地进行拓扑更新才能跟踪拓扑的变化。u这一方面对于本已非常有限的网络带宽和节点电能供应来说是不可想象的，另一方面把网络拓扑维护的繁重工作交给时间同步协议来解决也并不合适。第七章 时间同步技术l传统时间同

28、步技术分析两个新的时间同步技术试图解决传统时间同步技术中的同步积累误差和可扩展性问题：u协作同步技术协作同步技术u萤火虫同步技术萤火虫同步技术尽管目前这两种技术由于存在较多的假设，绝大多数实验还停留在仿真的阶段，但它们确实不失为解决无线传感器网络时间同步的新颖方法，可能会把无线传感器网络时间同步推入一个新的研究阶段。需要说明的是，传统时间同步协议的目的为了实现节点时间的一致性，即达到同时性；而新型同步技术则是为了实现节点（或个体）之间的同步性（Synchrony），即使节点的某些周期性动作具有相同的周期和相位。同时性和同步性在一定程度上可以看做两个等价的概念，节点的时间完全一致，则它们自然可以

29、生成具有相同周期和相位的动作；而节点的动作具有同步性，若以同步周期为基本时间单位，也就达到了节点间的同时性。第七章 时间同步技术l新型时间同步技术协作同步的具体过程：时间基准节点按照相等的时间间隔发出m个同步脉冲，这m个脉冲的发送时刻被其一跳邻居节点接收并保存，随后这些邻居节点根据最近的m个脉冲的发送时刻估计估计出时间基准节点的第m+1个同步脉冲的发送时刻，并在该时刻与时间基准节点同时发出同步脉冲。由于信号的叠加，因此复合的同步脉冲复合的同步脉冲可以到达更远的范围。如此重复下去，最终网内所有节点都达到了同步，如图所示：第七章 时间同步技术l新型时间同步技术协作同步萤火虫同步算法是目前人们解决群同步问题的最新方法，其基本思想来源于仿生学中的萤火虫同步发光现象。1