无线传感器网络时钟同步技术.ppt

《无线传感器网络时钟同步技术.ppt》由会员分享，可在线阅读，更多相关《无线传感器网络时钟同步技术.ppt（50页珍藏版）》请在三一办公上搜索。

1、无线传感器网络时钟同步技术,Time Synchronization in Wireless Sensor Network System,提 纲,一,三,概述,MAC层协议分类,二,MAC层避免信道冲突技术,四,基于多信道的MAC层技术,时间同步,由于物理上的分散性，网络无法为彼此间相互独立的节点提供一个统一的全局时钟，每个节点各自维护它们的本地时钟。由于这些本地时钟的计时速率、运行环境存在不一致性，因此即使所有的本地时钟在某一时刻都被校准，一段时间后，这些本地时钟间也会出现失步。为了让这些本地时钟再次达到相同的时间值，必须进行时间同步操作。时间同步就是通过对本地时钟的某些操作，达到为分布式系

2、统提供一个统一时间标度的过程。传感器网络自身协议的运行及基于其上的应用，如标记数据采集时间、时分多址接入、协同休眠、定位、数据融合等都需要网络中节点的时钟保持同步。时间同步算法设计必须考虑到两方面的因素：1)减少时间同步自身带来的能量消耗；2)提供较高时间同步精度以有效减少其它关键技术带来的能量消耗。,WSN时间同步技术背景,集中式系统与分布式系统集中式：事件间有着明确的时间先后关系，不存在同步问题分布式：同步是必需的，只是对同步的要求程度不同无线传感器网络时间同步典型的分布式系统是无线传感器网络应用的基础同步协议需要解决的问题同步精度功耗可扩展性,时间同步技术的分类,排序、相对同步与绝对同步

3、递进关系排序只能区分事件发生的先后相对同步：维持本地时钟的运行，定期获取其他节点的时钟偏移和飘移，经过换算达到同步的目的。如RBS协议绝对同步：本地时钟和参考时钟保持一致，修改本地时钟。如TPSN协议外同步与内同步参考源不同，前者参考源为网络外部，如GPS。后者参考源为网络内部某个节点的时钟局部同步与全网同步同步对象的范围不同,时间同步技术的应用场合,多传感器数据压缩与融合邻近传感节点对相同事件的感知数据需要融合，基于时间戳判断是否同一事件，需要时钟同步低功耗MAC协议、路由协议不发送数据时，节点处于休眠状态，网络节点的同步休眠需要时钟同步测距、定位（位置相关报务，LBS）距离测量和定位是基于

4、无线电信号的传输时间，时间同步越准确，距离测量也越准确分布式系统的传统要求分布式系统的数据库查询，状态等一致性的要求协作传输、处理的要求协作传输是基于电磁波的能量累加效应，多个节点以相同的调制解调方式同时发送信号，使得远处的汇集节点能接收到信号,硬件时钟模型,基本名词时间、晶振、时钟（RTC）时钟偏移（clock offset）：是指两个时钟瞬时读数的差。晶振计时的时刻与实际时刻的差值，反映计时的准确性Clock Skew：是指两个时钟的频率差。它可以看作是Clock offset的一阶导数。时间漂移(Clock Drift)：是指时钟频率的变化，反映晶振的稳定性。实际晶振的频率有可能随着外界

5、环境温度、湿度的变化而有所改变。Clock Drift可以看作是Clock offset的二阶导数。速率恒定模型该模型认为频率保持恒定不变，最常用，但不适应环境变化剧烈的场合飘移有界模型常用于确定同步误差上下界，频率稳定度常用ppm（百万分之一）飘移变化有界模型时钟的漂移变化率是有限的。,软件时钟模型,软件虚拟时钟一般是个分段连续、严格单调的函,时间同步的不同目的,第一种是最简单的一种，要求也最低，它只需要保证节点之间事件发生的相对顺序，这样就不需要节点具有相等的本地时间；第二种时钟同步问题是保证节点之间的相对时钟，在需要的时候，节点的本地时间可以与其他节点的本地时间相互转换，目前大多数时钟同

6、步算法，都是针对该种同步问题；第三种即最高要求的同步就是全网同步，全网所有节点随时都要与网络中的一个参考时钟同步，这就需要在网络中传播公共的时间标记。,传统同步：NTP与GPS,NTPNTP不适合于WSN体积、计算能力和存储空间存在限制GPS每颗卫星上配备有高精度的铷、铯原子钟，并不断发射其时间信息地面接收装置同时接收4颗卫星的时间信息，采用伪距测量定位方法可计算出时间和位置信息缺点（室内、功耗、安全性、分布式）,节点上的时钟,hardware clock 振荡器以固定频率产生脉冲每隔一定脉冲后计数寄存器增加1Only register content is available to soft

7、wareRegister change rate gives achievable time resolutionNode is register value at real time t is Hi(t)Convention:small letters(like t,t)denote real physical times,capital letters denote timestamps or anything else visible to nodesA(node-local)software clock is usually derived as follows:Li(t)=qi Hi

8、(t)+fi(没有考虑计数寄存器的益处)qi is the(drift)rate,fi the phase shift时间同步就是要修正 qi 和 fi,而不是计数寄存器,同步精确性,外部同步与外部的时间表（如UTC）同步Nodes i=1,.,n are accurate at time t within bound d when|Li(t)t|d for all i因此，至少有一个节点具有外部的时间表内部同步无外部的时间表,所有节点具有公共时间表Nodes i=1,.,n agree on time within bound d when|Li(t)Lj(t)|d for all i,j,

9、不精确的原因,Nodes are switched on at random times,phases i hence can be random随机打开的节点的相位也是随机的 Actual oscillators have random deviations from nominal frequency(drift,skew)实际的振荡器与标准的频率之间有一定的随机偏差Deviations are specified in ppm(pulses per million),the ppm value counts the additional pulses or lost pulses ove

10、r the time of one million pulses at nominal rateThe cheaper the oscillators,the larger the average deviationFor sensor nodes values between 1 ppm(one second every 11 days)and 100 ppm(one second every 2.8 hours)are assumed,Berkeley motes have an average drift of 40 ppmOscillator frequency depends on

11、time(oscillator aging)and environment(temperature,pressure,supply voltage,.)振荡器的频率会随着使用期限、温度等因素而出现偏差Especially the time-dependent drift rates call for frequent re-synchronization,as one-time synchronization is not sufficientHowever,stability over tens of minutes is often a reasonable assumption,时间同步

12、算法,Physical time vs.logical timeExternal vs.internal synchronizationGlobal vs.local algorithmsKeep all nodes of a WSN synchronized or only a local neighbourhood?Absolute vs.relative timeHardware vs.software-based mechanismsA GPS receiver would be a hardware solution,but often too heavyweight/costly/

13、energy-consuming in WSN nodes,and in addition a line-of-sight to at least four satellites is requiredA-priori vs.a-posteriori synchronizationIs time synchronization achieved before or after an interesting event?Post-facto synchronizationDeterministic vs.stochastic precision boundsLocal clock update

14、disciplineShould backward jumps of local clocks be avoided?(Users of make say yes here.)Avoid sudden jumps?,时间同步算法的性能和功能模块,Metrics:性能度量Precision:maximum synchronization error for deterministic algorithms,error mean/stddev/quantiles for stochastic onesEnergy costs,e.g.#of exchanged packets,computatio

15、nal costsMemory requirementsFault tolerance:what happens when nodes die?Fundamental building blocks of time synchronization algorithms:Resynchronization event detection block:when to trigger a time synchronization round?Periodically?After external event?Remote clock estimation block:figuring out the

16、 other nodes clocks with the help of exchanging packetsClock correction block:compute adjustments for own local clock based on estimated clocks of other nodesSynchronization mesh setup block:figure out which node synchronizes with which other nodes,WSNs中时间同步算法的限制,An algorithm should scale to large n

17、etworks of unreliable nodesQuite diverse precision requirements,from ms to tens of secondsUse of extra hardware(like GPS receivers)is mostly not an optionlow mobilityOften there are no fixed upper bounds on packet delivery times(due to MAC delays,buffering,.)Negligible propagation delay between neig

18、hboring nodesManual node configuration is not an option,时间同步算法分类,基于Sender/Receiver的时间同步通信双方中的发送节点需要记录时间消息发送时刻的时间信标，而接收节点则需要记录时间消息接收时刻的时间信标，同步过程中只需要一次通信。该模式的代表算法是洪泛广播时间同步协议。基于Receiver/Receiver的时间同步在实现时间同步的过程中，节点只需要在接收时间消息的时刻记录时间信标，而发送时刻不需要记录时间信标，节点只需要知道接收到时间消息的精确时刻。典型协议有RBS等。基于Pair-Wise的时间同步这种算法利用成对同

19、步方法进行发送节点和接收节点间的时间同步，然后扩展到整个网络形成网络的时间同步。此类算法使得网络的同步报文开销较大，对于低开销要求较高的工业无线网络应用有一定的局限性。而且同步阶段所用时间随节点数目的增加而线性增加,不适合对快速性要求较高的工业无线网络。典型的算法主要有TPSN、LTS、Tiny-sync和Miny-Sync等。,1、基于接收者和接收者的时间同步机制基于接收者和接收者的时间同步机制充分利用了无线数据链路层的广播信道特性，引入一个节点作为辅助节点，由该节点广播一个参考分组，在广播域内的一组接收节点接收到这个参考分组，通过比较各自接收到消息的本地时间，实现它们之间的时间同步。2、基

20、于发送者和接收者的双向时间同步机制基于发送者和接收者的双向时间同步机制类似于传统网络中的NTP协议，基于客户机一服务器架构。待同步节点向基准节点发送同步请求包，基准节点回馈包含当前时间的同步包，待同步节点估算时延并校准时钟。3、基于发送者和接收者的单向时问同步机制为了避免往返传输时间(RTT：Roundtrip Time)估计，减少交换消息的数量，同时兼顾可扩展性、能量消耗和估算成本，、产生了基于发送者和接收者的单向时间同步机制。在基于发送者和接收者的单向时间同步机制中，基准节点广播含有节点时间的分组，待同步节点测量分组的传输延迟，并且将自己的本地时间设置为接收到的分组中包含的时间加上分组传输

21、延迟，这样所有广播范围内的节点都可以与主节点进行同步。,DMTS(Delay Measurement Time Synchronization),DMTS基于同步消息在传输路径上所有延迟的估计，实现节点间的时间同步在DMTS机制中，选择一个节点作为时间主(leader)节点广播同步时间。所有接收节点测量这个时间广播分组的延迟，设置它的时间为接收到分组携带的时间加上这个广播分组的传输延迟，这样所有接收到广播分组的节点都与主节点进行时间同步。时间同步的精度主要由延迟测量的精度所决定。主节点在检测到信道空闲时，给广播分组加上时间戳t0，用来去除发送端的处理延迟和MAC层的接入延迟。在发送广播分组前，

22、主节点需要发送前导码和起始字符，以便接收节点进行接收同步，根据发送的信息位个数n和发送每比特位需要的时间t，可以估计出前导码和起始字符的发送时间位nt。接收节点在广播分组到达时刻加上时间戳t1，并在调整自己的时钟之前时刻再记录时间t2，接收端的接收处理延迟就是(t2t1)。这样，如果忽略无线信号的传播延迟，接收节点从t0时刻到调整时钟前的时间长度约为nt+(t2t1)。因此，接收节点为了与发送节点时钟同步，调整其时钟为t0+nt+(t2t1)。,发送者在信道空闲后或争用到信道后才插入本地时间t0接收处理报文的时间：前导码时间nt，报文处理时间t2-t1接收方的同步时刻为：t0+nt+t2-t1

23、单报文同步同步精度低广播方式同步能耗低最简单直观，未考虑传播延迟和编解码时间,DMTS机制通过使用单个广播时间分组，能够同步单跳广播域内的所有节点，同时无需复杂的运算和操作，是一种轻量的能量有效的时间同步机制。DMTS机制在多跳网络中采用层次型分级结构实现全网内所有节点的时间步，为此定义了时间源级别的概念，时间源级别用来表示节点到时间主节点的跳数距离。每个节点都有一个时间源级别：时间主节点的级别是0；与时间主节点相邻的节点，即时间主节点一跳范围内的节点属于级别1；与级别i节点相邻的节点，也就是到时间主节点的跳数为(i+1)的节点属于级别(i+1)；以此类推每个节点的级别。时间主节点周期性广播它

24、的时间，与主节点直接或间接同步的节点在给定时间内广播且仅广播一次它的时间。在一段时间间隔内，节点收到时间广播分组时，检查发送该分组的节点级别是否低于自己的级别。如果是，就与这个广播时间进行同步，否则丢弃该分组。这样，主节点的时间以最小跳数传播到整个网络内的所有节点，并且全网内时间广播分组的总个数达到最少，等于网络内所有节点的个数之和，没有任何冗余数据包传输。因此，在节点组大级别为N的传感器网络中，时间同步的最大误差是单跳同步误差的N倍。由于多跳网络的每一跳误差可能为正也可能为负，多跳同步误差的总和可以抵消部分单跳误差。,DMTS算法结合链路层标记时间戳和时延估计等技术，消除了发送时间和访问时间

25、的影响，算法简单，通信开销小。DMTS单跳同步误差受同步精度和计时精度影响。多跳精度随跳数的增加而下降，由于误差的正负相加抵消了一部分，两跳的误差约为单跳误差的1.5倍。DMTS算法没有估计时钟的频率偏差，时钟保持同步的时间较短；也没有消除时钟计时对同步精度的影响，因而其精度不高，不适用于定位等要求高精度同步的应用。,RBS(Reference Broadcast synchronization),RBS协议不是去同步报文的收发双方，而是去同步报文的多个接收者。如右图所示：在由3个节点组成的单跳网络中，参考节点每发出一个参考报文，其广播域内的其他接收者节点都将接收到该报文，并各自记录下接收到该

26、参考报文时的本地时刻。接收者相互交换它们记录的时刻并计算差值，该差值就是接收者之间的时钟偏移。,根据偏移信息可以实现发送者-接收者同步，若能精确地估计出报文传输延迟，这种方法将能够取得很高的精度。然而仅根据单个报文的传输很难准确地估计出传输延迟。左图为发送者-接收者同步机制。可以看出，发送者-接收者同步机制的同步关键路径为从发送方到接收方。关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高。右图则是接收者-接收者同步机制，其关键路径大为缩短，完全排除了发送时间和访问时间的影响。,RBS中是通过广播同步信标分组实现接收节点之间的相对时间同步，信标分组本身并不需要携带任何时标，不依赖

27、于信标的发送时间。由于无线信道的广播特性，信标分组相对所有接收节点而言同时发送到物理信道上，这样就除去发送时间和访问时间引入的时间同步误差。对于传播时间，RBS只关心各个接收节点之间消息传播时间的差值。对于射频信号来说，传播时间差值非常小，RBS忽略了传播时间带来的时间偏差。,影响RBS机制性能的主要因素包括接收节点间的时间速率、接收节点非确定因素和接收节点的个数等。为提高时间同步精度，RBS机制采用了统计技术，通过发送节点发送多个消息，获得接收节点之间时间差异的平均值。对于时间速率问题，采用最小方差线性拟合，直线斜率就是两个节点的时间速率，直线上的点表示节点间的时间差异。RBS的缺点是对网络

28、有一定的要求，它不适合点对点通信的网络，且要求网络有物理广播信道。扩展性不好，因为节点间本地时间戳通信需要额外的消息交换开销，不能很好地应用到大规模的多跳网络中。RBS有很大的交换次数，对于具有，2个节点的单跳网络，需要O(n2)的消息交换，如果n很大时，消息交换开销是相当大的，导致节点的计算开销也非常之大。RBS中接收节点之间进行相互同步，但并不与发送节点同步；实际上，在WSN中发送节点很可能也是一个普通的网络节点因而也需要同步，为使该节点和其它节点进行同步，需要另外一个节点作为参照广播发射节点，这导致了相当高的能耗。,TPSN(Timing-sync Protocol for Sensor

29、 Networks),图中的T1、T4用节点A的本地时间记录，T2、T3用节点B的本地时间记录。节点A向节点B发送一个同步请求报文。节点B在接收到该报文后，记录下接收到时刻T2，并立即向节点A返回一个同步应答报文，并把T2和该报文的发送时刻T3嵌入在报文中。当节点A接收到该报文时，记录下接收到时刻T4。令为当节点A的本地时刻为T1时，节点A和B之间的时偏。报文的传输延迟均为d。,多跳TPSN,全网周期性同步“层发现”把网络组织成最短生成树逐层在相邻两层节点间同步网络内两个节点的同步“后同步”查找两个节点间的路径在路径的相邻两个节点间进行TPSN同步,TPSN算法优点：TPSN基于双向报文交换，

30、因此同步精度高。对任意节点其同步误差取决于它距离根节点的跳数，而与网络中节点总数无关，使TPSN同步精度不会随节点数目增加而降级，从而使TPSN具有较好的扩展性。TPSN算法的缺点：TPSN本质上是对同步，因此全网同步的同步能耗高。一旦根节点失效，就要重新选择根节点并重新进行分级和同步阶段的处理，增加了计算和能量开销。另外，TPSN算法没有对时钟的频差进行估计，这使得它需要频繁同步，开销较大。,HRTS(Hierarchy Referencing Time Synchronization Protocol),基于双向报文交换的用于传感器网络的时间同步协议具有同步精度高的优点，但一次只能同步一对

31、节点。n个节点的单跳网络则需要n-1次同步操作，同步功耗较大。RBS只需要一次同步过程就可完成一个单跳网内所有节点间的同步，同步功耗降低，当然，同步精度也相对变差。HRTS是一种结合了RBS所使用的参考广播同步技术和TPSN所使用的双向报文交互同步技术，减少了同步所需的报文开销。图描述了层级时间同步的过程。假设单跳网络有包含时间基准节点在内的3个节点BS、n1和n2。,步骤1：时间基准节点BS发出一个同步请求报文，该报文随机指定一个邻居节点（例如n1）作为应答者节点（即对应于图1中的B节点）。同时n2也记录下该报文的接收到时刻，记为T2。步骤2：应答者节点n1向BS节点发一个同步应答报文，报文

32、中包含了T2与T3。步骤3：现在BS节点已经和n1节点进行了一次双向报文交换，BS节点计算出它与n1节点之间的时钟偏移。步骤4：BS节点发送一个包含和T2信息的报文。步骤5：当n1、n2节点接收到该报文，对于应答者节点n1来说，只要将其本地时间减去就达到与BS节点的瞬时同步。对于其他节点来说，只要在其本地时间加上T2 T2 即可达到与BS节点间的瞬时同步,根节点和应答者节点本质上是采用TPSN同步。根节点和非应答者节点本质上是双向报文交换同步（但非TPSN）。应答者节点和非应答者节点本质上是接收者-接收者同步。HRTS协议充分利用了无线传输的广播特性来进一步降低LTS协议的同步功耗。,LTS(

33、Lightweight Tree-based synchronization),LTS同步算法是一种与TPSN非常类似的算法。LTS侧重于降低时间同步的复杂度，在有限的计算代价下获得合理的同步精度。LTS有集中式和分布式两个版本，在集中式版本中，首先以时间参考节点为根建立生成树，然后从树根开始 逐级向叶子节点进行同步：首先根节点同步其子节点，然后这些子节点再分别同步其子节点，如此继续下去，直到全部节点都被同步。另外，为了达到最高的同步精度，要求生成树的深度尽可能的小。在分布式版本中，任何节点都可以发起同步过程，不需要建立生成树，但是每个节点都必须知道参考节点的位置，并且知道其到这些节点的路径。

34、节点根据自己的时钟漂移确定需要同步的时间，需要同步时，节点选择距离自己最近的一个参考节点，并向其发出同步请求，然后参考节点向该节点的路径上的节点逐对进行同步，直到该节点被同步。,在分布式同步算法中，由于节点有机会决定它自己的同步，这就节约了不必要的同步开销。同时，通过融合同步请求，降低了相同路径上请求的数目，节约了资源。在LTS算法中，网络中的节点避免了TPSN中与多个上层节点同步，而只与其直接父节点同步，减少了消息交换数目和同步时间。该算法目的在于最小化复杂度以此降低能耗，精度一般。同步次数是节点距离根节点跳数的线性函数，降低了消息交换次数，同时也降低了同步精度。算法的运行时间与树的深度成比

35、例，因此具有最小深度的生成树时，收敛时间最短，但构造最小生成树也需要一定的计算和通信开销。算法依赖于节点和参考节点的信息可靠性，错误的消息导致同步失败。,LTS算法与TPSN协议的区别在于，LTS算法中节点只与自己的父节点进行同步，其同步次数是路径长度的线性函数，同时精度也随路径的长度线性降低，即在降低计算代价的同时降低了同步精度。,基于receiver/receiver的时间同步,In this class of schemes the receivers of packets synchronize among each other,not with the transmitter of

36、the packetRBS=Reference Broadcast Synchronization(Elson et al)RBS has two components:Synchronize receivers within a single broadcast domainA scheme for relating timestamps between nodes in different domainsRBS does not modify the local clocks of nodes,but computes a table of conversion parameters fo

37、r each peer in a broadcast domainRBS allows for post-facto synchronization,Tiny-Sync/Mini-Sync,该算法基于一个假设：传感器网络中的时钟频率恒定且线性相关。Tiny-sync算法的思想在每次获得新的数据点时，首先与以前的数据点比较，如果新的数据点计算出的误差大于以前数据点计算的误差，则抛弃新的数据点；否则，采用新的数据点，抛弃旧的数据点。Tinysync算法仅需存储三到四个数据点的信息。,节点i的硬件时钟是时间t是一个单调非递减的函数Ci(t)，在相当长一段时间内可以认为保持不变。在一段时间内节点间的时

38、钟频偏或相偏的差值保持不变，根据节点之间的线性相关性可以得出：C1(t)=a12C2(t)+b12Tiny-Sync算法和MiniSync算法采用传统的双向消息设计来估计节点时钟间的相对漂移和相对偏移。Sender-receiver 双向数据交换Node 1 sends a probe message to node 2 time-stamped with t0Node 2 generates timestamp tb and responds immediatelyNode 1 generates timestamp tr不等式:t0a12tb+b12tr其中a12和b12分别表示两个时钟之

39、间的相对时钟频偏和相对时钟相偏，相对时钟频偏表示两者频率之比，相对时钟相偏表示两者相位之差。如果两个时钟精确同步，相对时钟频偏等于1，而相对时钟相偏等于零。三个时间戳(t0,tb,tr)叫做数据点，算法通过不断地收集数据点来估计a12和b12，并且随着数据点个数的增加，算法的精度不断提高。,注意到a12、b12对应的直线必定在所有的数据点对之间，因此图中最陡的和最缓的两条虚线给出了a12、b12的上下界。并且上下界的区间越小，精度越高。通过求解所有数据点约束下的线性规划问题，别可以得到最优解。但是，这种方法太过复杂，无法在计算资源有限的无线传感器网络中实现。,C2(t),数据点 1,数据点 3

40、,t0,tr,C1(t)=a12H2(t)+b12,C1(t),Node 1,Node 2,t0,tr,tb,tb,a12,b12,参数估计,Relative drift a12 and offset b12The tighter the bound,the higher the synchronization precisionRequires high amount of data points and quite complexAlgorithms precision increases with the increased number of data points.,Tiny-Syn

41、c与Mini-Sync之间的不同,Different methods in selecting useful data pointsTiny-SyncKeep only four constrains of all data pointsDoes nor always give the best solution for the boundsMini-Sync is an extension of Tiny-SyncMore optimal solution with increased complexityKeeps also the data points which may be use

42、ful by some future data points to give tighter boundsA data point is discarded only if it is definitely uselessQuite complex selection criterion.,TS/MS算法是基于并非所有观察的数据点都有效的思想。每个数据点有两个限制漂移和偏移的元素组成，TS仅保持产生最佳边界估计的四个约束。但算法可能会因为排除了一些当时看来没有而后来很可能提供最佳估计的数据点而导致算法效果并非一直是最佳。MS是TS算法的扩展，以较小的计算代价获得最优解决方法。是为避TS算法排除

43、将来可能有用的数据点而提出的，它通过定义一个标准来确保丢弃确实没用的数据点。TS/MS通过多个数据点来提供具有确定误差界限的偏移和估计，比一般简单的双程同步算法精度要高，且能够容忍消息丢失，可以扩展到任何允许双向数据通信的网络，适合与带宽、存储容量和计算能力非常有限的网络。该算法的缺点：收敛时间比较长，同步开销是一般成对同步算法的k倍。文献中建议MS存储40个三元组数据，存储开销较大。对于需要长期检测的传感器网络应用，传感器节点低成本的晶体振荡器很难保证时间速率和时间偏差的长时间稳定性，因而影响估计结果。,FTSP(Flooding Time Synchronization Protocol)

44、,FTSP 协议属于发送者接收者协议。FTSP协议基于MAC层时间戳技术，发送者节点在报文中的多个位置嵌入不同的时间戳。发送节点在完成SYNC字节发送后在MAC层给以后发送的每个字节标记时间戳，接收节点在接收完SYNC字节也做同样的标记，这样在发送节点和接收节点处都获得了多个时间戳，当消息传输完后双方分别对这些时间戳做同样的处理。最后接收节点获得(global time，local time)时间对，因而得到相对于发送节点的偏移，调整本地钟。FTSP算法对时钟漂移进行了线性回归分析。FTSP算法考虑到在特定的时间范围内节点时钟晶振频率是稳定的，因此节点间时钟偏移量(时间速率)与时间成线性关系：

45、通过发送节点周期性广播时间同步消息，接收节点取得多个数据对(time，offset)，并构造最佳拟合直线L(time)。通过回归直线L(time)，在误差允许的时间间隔内，节点可直接通过L(time)计算某一时间点节点间的时钟偏移量而不必发送时间同步消息进行计算，从而减少了消息的发送次数并降低了系统的能量开销。,FTSP也提供了多跳时间同步。多跳的FTSP协议采用洪泛(Flooding)的方法广播时间基准节点的时间。当网络中的时间基准节点正常工作时，每个一段时间，它将广播一个报文。广播消息由三个域组成：时间戳(timestamp)，根节点工D号(rootID)和顺序号(seqNum)。每次时间

46、基准节点发送一个新的报文指示变量的值就加1(可以理解为同步的轮数)。当接收到消息，节点计算它的全局时间和嵌入在消息中的发送节点的全局时间之间的偏移，更新自己的全局时间，并广播自己的全局时间到邻居节点。为避免在线性回归中使用冗余信息，每个节点保留接收到的消息的最大序号和最后一次接收到的消息所使用的rootID。同步消息只有在seqNum大于目前接收到的最大序号且新消息的rootID小于或等于最后一次接收到的rootID时才用于回归。另外，如果节点在ROOT_TIMEOUT时间内没有监听到同步消息，它就宣布自己为新的根节点。为确保网络中仅有一个根节点，如果一个根节点听到来自于节点号更低的节点的时间

47、同步消息，就放弃自己的根节点状态。,FTSP算法通过对收发过程的分析，把时延进一步分为发送中断处理时延、编码时延、传播时延、解码时延、字节对齐时延、接收终端处理时延，进一步降低了时延的不确定性。另外，通过发射多个信令包，使得接收节点可以利用最小方差线性拟合估算自己和发送节点的漂移和偏移差。通过良好的根节点选举机制，针对根节点失效、新节点加入以及拓扑结构变化等情况进行了优化，使得算法的健壮性很好，适合于军事等恶劣应用情况。,FTSP是现有的典型时间同步协议中精度最高的同步协议，并且有良好的健壮性，不会因为个别节点的失效而收到影响。但FTSP基于MAC层时间戳技术的细节技术的实现来提高同步精度，使

48、得FTSP协议的通用性不强。并且洪泛的方式使得能耗开销巨大。用于ZigBee网络的同步休眠与唤醒算法,同步算法总结,通过分析发现，TPSN、LTS、和TSMS都用泛洪广播的方式构造层次树，然后用双程同步的方法进行上下层节点间的时钟同步。但它们都没有有效地利用泛洪广播的信息，致使同步阶段消息丌销较大。TPSN采用在MAC层做时间标记达到了16.9us的同步精度，因此在设计算法时可以考虑采用MAC层标记的方法提高同步精度。RBS算法在单跳内有较好的同步精度，但不适合用来进行多跳节点间的同步，对于分簇网络可以考虑用这种方法同步簇内节点。TSync用双信道的方法，结合了广播同步机制和双程同步算法，消息开销小。但它假定每个节点都知道它的下层邻节点号，在真正进行同步时这还是个需要解决的问题。对于一些对精度要求不高要求计算复杂度低的应用，可以考虑用DMTS算法。对于一些刚加入网络的节点可以用AD算法与其周围节点进行同步。根据不同的应用环境，也可以用多种方法结合的方法进行网络同步。在多种条件衡量下，没有一种是最优的。对于不同的应用要求可以从多方面权衡来选择合适的算法。对于不同的设计目标，每个算法都有优于其他算法的地方，可以相互借鉴，来设计出更好的算法。,谢谢大家，欢迎提问！,