无线传感器网络时钟同步技术课件

《无线传感器网络时钟同步技术课件》由会员分享，可在线阅读，更多相关《无线传感器网络时钟同步技术课件（49页珍藏版）》请在装配图网上搜索。

1、无线传感器网络时钟同步技术无线传感器网络时钟同步技术Time Synchronization in Wireless Sensor Network System提提 纲纲概述概述 MAC层协议分类层协议分类MAC层避免信道冲突技术层避免信道冲突技术 基于多信道的基于多信道的MAC层技术层技术时间同步时间同步v由于物理上的分散性，网络无法为彼此间相互独立的节点提供一由于物理上的分散性，网络无法为彼此间相互独立的节点提供一个统一的全局时钟，每个节点各自维护它们的本地时钟。个统一的全局时钟，每个节点各自维护它们的本地时钟。v由于这些本地时钟的由于这些本地时钟的计时速率计时速率、运行环境运行环境存在不

2、一致性，因此即存在不一致性，因此即使所有的本地时钟在某一时刻都被校准，一段时间后，这些本地使所有的本地时钟在某一时刻都被校准，一段时间后，这些本地时钟间也会出现失步。为了让这些本地时钟再次达到相同的时间时钟间也会出现失步。为了让这些本地时钟再次达到相同的时间值，必须进行时间同步操作。值，必须进行时间同步操作。v时间同步就是通过对本地时钟的某些操作，达到为分布式系统提时间同步就是通过对本地时钟的某些操作，达到为分布式系统提供一个统一时间标度的过程。供一个统一时间标度的过程。v传感器网络自身协议的运行及基于其上的应用，如标记数据采集传感器网络自身协议的运行及基于其上的应用，如标记数据采集时间、时分

3、多址接入、协同休眠、定位、数据融合等都需要时间、时分多址接入、协同休眠、定位、数据融合等都需要网络网络中节点的时钟保持同步中节点的时钟保持同步。v时间同步算法设计必须考虑到两方面的因素：时间同步算法设计必须考虑到两方面的因素： 1) 减少时间同步自身带来的能量消耗能量消耗； 2)提供较高时间同步精度时间同步精度以有效减少其它关键技术带来的能量消耗。WSN时间同步技术背景时间同步技术背景v 集中式系统与分布式系统集中式系统与分布式系统集中式：事件间有着明确的时间先后关系，不存在同步问题分布式：同步是必需的，只是对同步的要求程度不同v 无线传感器网络时间同步无线传感器网络时间同步典型的分布式系统是

4、无线传感器网络应用的基础v 同步协议需要解决的问题同步协议需要解决的问题同步精度功耗可扩展性时间同步技术的分类时间同步技术的分类v 排序、相对同步与绝对同步排序、相对同步与绝对同步递进关系 排序只能区分事件发生的先后 相对同步：维持本地时钟的运行，定期获取其他节点的时钟偏 移和飘移，经过换算达到同步的目的。如RBS协议 绝对同步：本地时钟和参考时钟保持一致，修改本地时钟。如TPSN协议v 外同步与内同步外同步与内同步参考源不同，前者参考源为网络外部，如GPS。后者参考源为网络内部某个节点的时钟v 局部同步与全网同步局部同步与全网同步同步对象的范围不同时间同步技术的应用场合时间同步技术的应用场合

5、v 多传感器数据压缩与融合 邻近传感节点对邻近传感节点对相同事件的感知数据需要融合相同事件的感知数据需要融合，基于时间戳基于时间戳判断判断是否同一事件是否同一事件，需要时钟同步，需要时钟同步v 低功耗MAC协议、路由协议 不发送数据时，节点处于休眠状态，网络节点的不发送数据时，节点处于休眠状态，网络节点的同步休眠需同步休眠需要时钟同步要时钟同步v 测距、定位（位置相关报务，LBS） 距离测量和定位距离测量和定位是基于无线是基于无线电信号的传输时间电信号的传输时间，时间同步越，时间同步越准确，距离测量也越准确准确，距离测量也越准确v 分布式系统的传统要求 分布式系统的数据库查询，状态等分布式系统

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

7、：是指时钟频率的变化，反映晶振的稳定性。实际晶振的频率有可能随着外界环境温度、湿度的变化而有所改变。Clock Drift可以看作是Clock offset的二阶导数。v速率恒定模型速率恒定模型 该模型认为频率保持恒定不变，最常用，但不适应环境变化剧烈的场合v飘移有界模型飘移有界模型 常用于确定同步误差上下界，频率稳定度常用ppm（百万分之一）v飘移变化有界模型飘移变化有界模型 时钟的漂移变化率是有限的。软件时钟模型软件时钟模型v 软件虚拟时钟软件虚拟时钟v 一般是个分段连续、严格单调的函一般是个分段连续、严格单调的函时间同步的不同目的时间同步的不同目的v 第一种是最简单的一种，要求也最低，它

8、只需第一种是最简单的一种，要求也最低，它只需要保证节点之间事件发生的要保证节点之间事件发生的相对顺序相对顺序，这样就，这样就不需要节点具有相等的本地时间；不需要节点具有相等的本地时间；v 第二种时钟同步问题是保证节点之间的第二种时钟同步问题是保证节点之间的相对时相对时钟钟，在需要的时候，节点的本地时间可以与其，在需要的时候，节点的本地时间可以与其他节点的本地时间相互转换，目前大多数时钟他节点的本地时间相互转换，目前大多数时钟同步算法同步算法 ， 都是针对该种同步问题；都是针对该种同步问题；v 第三种即最高要求的同步就是第三种即最高要求的同步就是全网同步全网同步，全网，全网所有节点随时都要与网络

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

10、ilable to software Register change rate gives achievable time resolution Node 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 nodesv A (node-local) software clock is usually deri

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

12、 n agree on time within bound d when |Li(t) Lj(t)|d for all i,j不精确的原因不精确的原因vNodes are switched on at random times, phases i hence can be random随机打开的节点的相位也是随机的随机打开的节点的相位也是随机的 vActual oscillators have random deviations from nominal frequency (drift, skew)实际的振荡器与标准的频率之间有一定实际的振荡器与标准的频率之间有一定的随机偏差的随机偏差 De

13、viations are specified in ppm (pulses per million), the ppm value counts the additional pulses or lost pulses over the time of one million pulses at nominal rate The cheaper the oscillators, the larger the average deviation For sensor nodes values between 1 ppm (one second every 11 days) and 100 ppm

14、 (one second every 2.8 hours) are assumed, Berkeley motes have an average drift of 40 ppmvOscillator frequency depends on time (oscillator aging) and environment (temperature, pressure, supply voltage, .)振荡振荡器的频率会随着使用期限、温度等因素而出现偏差器的频率会随着使用期限、温度等因素而出现偏差 Especially the time-dependent drift rates call

15、for frequent re-synchronization, as one-time synchronization is not sufficient However, stability over tens of minutes is often a reasonable assumption时间同步算法时间同步算法vPhysical time vs. logical timevExternal vs. internal synchronizationvGlobal vs. local algorithms Keep all nodes of a WSN synchronized or

16、 only a local neighbourhood?vAbsolute vs. relative timevHardware vs. software-based mechanisms A GPS receiver would be a hardware solution, but often too heavyweight/costly/energy-consuming in WSN nodes, and in addition a line-of-sight to at least four satellites is requiredvA-priori vs. a-posterior

17、i synchronization Is time synchronization achieved before or after an interesting event? Post-facto synchronizationvDeterministic vs. stochastic precision boundsvLocal clock update discipline Should backward jumps of local clocks be avoided? (Users of make say yes here .) Avoid sudden jumps?时间同步算法的性

18、能和功能模块时间同步算法的性能和功能模块vMetrics: 性能度量性能度量 Precision: maximum synchronization error for deterministic algorithms, error mean / stddev / quantiles for stochastic ones Energy costs, e.g. # of exchanged packets, computational costs Memory requirements Fault tolerance: what happens when nodes die?vFundament

19、al 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 other nodes clocks with the help of exchanging packets Clock correction bl

20、ock: compute adjustments for own local clock based on estimated clocks of other nodes Synchronization mesh setup block: figure out which node synchronizes with which other nodesWSNs中时间同步算法的限制中时间同步算法的限制v An algorithm should scale to large networks of unreliable nodesv Quite diverse precision requirem

21、ents, from ms to tens of secondsv Use of extra hardware (like GPS receivers) is mostly not an optionv low mobilityv Often there are no fixed upper bounds on packet delivery times (due to MAC delays, buffering, .)v Negligible propagation delay between neighboring nodesv Manual node configuration is n

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

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

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

25、有节点时间的分组，待同步节点测量分组的传输延迟，并且将自己的本地时间设置为接收到的分组中包含的时间加上分组传输延迟，这样所有广播范围内的节点都可以与主节点进行同步。DMTS (Delay Measurement Time Synchronization)vDMTS基于同步消息在传输路径上所有延迟的估计，实现节点间基于同步消息在传输路径上所有延迟的估计，实现节点间的时间同步的时间同步v在在DMTS机制中，选择一个节点作为时间主机制中，选择一个节点作为时间主(leader)节点广播同步节点广播同步时间。所有接收节点测量这个时间广播分组的延迟，设置它的时时间。所有接收节点测量这个时间广播分组的延迟，

26、设置它的时间为接收到分组携带的时间加上这个广播分组的传输延迟，这样间为接收到分组携带的时间加上这个广播分组的传输延迟，这样所有接收到广播分组的节点都与主节点进行时间同步。时间同步所有接收到广播分组的节点都与主节点进行时间同步。时间同步的精度主要由延迟测量的精度所决定。的精度主要由延迟测量的精度所决定。v主节点在检测到信道空闲时，给广播分组加上时间戳主节点在检测到信道空闲时，给广播分组加上时间戳t0，用来去，用来去除发送端的处理延迟和除发送端的处理延迟和MAC层的接入延迟。层的接入延迟。v在发送广播分组前，主节点需要发送前导码和起始字符，以便接在发送广播分组前，主节点需要发送前导码和起始字符，以

27、便接收节点进行接收同步，根据发送的信息位个数收节点进行接收同步，根据发送的信息位个数n和发送每比特位和发送每比特位需要的时间需要的时间t，可以估计出前导码和起始字符的发送时间位，可以估计出前导码和起始字符的发送时间位nt。v接收节点在广播分组到达时刻加上接收节点在广播分组到达时刻加上时间戳时间戳t1，并在调整自己的时，并在调整自己的时钟之前时刻再记录钟之前时刻再记录时间时间t2，接收端的接收处理延迟就是，接收端的接收处理延迟就是(t2t1)。这样，如果忽略无线信号的传播延迟，接收节点从这样，如果忽略无线信号的传播延迟，接收节点从t0时刻到调整时刻到调整时钟前的时间长度约为时钟前的时间长度约为n

28、t + (t2t1) 。因此，接收节点为了与发。因此，接收节点为了与发送节点时钟同步，调整其时钟为送节点时钟同步，调整其时钟为t0 + nt + (t2t1) 。v发送者在信道空闲后或争用到信道后才插入本地时间t0v接收处理报文的时间：前导码时间nt，报文处理时间t2-t1v接收方的同步时刻为：t0+ nt+ t2-t1v单报文同步同步精度低v广播方式同步能耗低v最简单直观，未考虑传播延迟和编解码时间vDMTS机制通过使用单个广播时间分组，能够同步单跳广播域内的所有机制通过使用单个广播时间分组，能够同步单跳广播域内的所有节点，同时无需复杂的运算和操作，是一种轻量的能量有效的时间同步节点，同时无

29、需复杂的运算和操作，是一种轻量的能量有效的时间同步机制。机制。vDMTS机制在多跳网络中采用层次型分级结构实现全网内所有节点的时机制在多跳网络中采用层次型分级结构实现全网内所有节点的时间步，为此定义了时间源级别的概念，时间源级别用来表示节点到时间间步，为此定义了时间源级别的概念，时间源级别用来表示节点到时间主节点的跳数距离。每个节点都有一个时间源级别：主节点的跳数距离。每个节点都有一个时间源级别： 时间主节点时间主节点的级别是0； 与时间主节点相邻的节点，即时间主节点一跳范围内的节点属于级别1； 与级别i节点相邻的节点，也就是到时间主节点的跳数为(i+1)的节点属于级别(i+1)； 以此类推每

30、个节点的级别。v时间主节点周期性广播它的时间，与主节点直接或间接同步的节点在给时间主节点周期性广播它的时间，与主节点直接或间接同步的节点在给定时间内广播且定时间内广播且仅广播一次仅广播一次它的时间。它的时间。v在一段时间间隔内，节点收到时间广播分组时，检查发送该分组的节点在一段时间间隔内，节点收到时间广播分组时，检查发送该分组的节点级别是否低于自己的级别。如果是，就与这个广播时间进行同步，否则级别是否低于自己的级别。如果是，就与这个广播时间进行同步，否则丢弃该分组。丢弃该分组。v这样，主节点的时间以最小跳数传播到整个网络内的所有节点，并且全这样，主节点的时间以最小跳数传播到整个网络内的所有节点

31、，并且全网内时间广播分组的总个数达到最少，等于网络内所有节点的个数之和，网内时间广播分组的总个数达到最少，等于网络内所有节点的个数之和，没有任何冗余数据包传输。没有任何冗余数据包传输。v因此，在节点组大级别为因此，在节点组大级别为N的传感器网络中，的传感器网络中，时间同步的最大误差时间同步的最大误差是单是单跳同步误差的跳同步误差的N倍倍。由于多跳网络的每一跳误差可能为正也可能为负，。由于多跳网络的每一跳误差可能为正也可能为负，多跳同步误差的总和可以抵消部分单跳误差。多跳同步误差的总和可以抵消部分单跳误差。v DMTS算法结合链路层标记时间戳和时延估计算法结合链路层标记时间戳和时延估计等技术，消

32、除了发送时间和访问时间的影响，等技术，消除了发送时间和访问时间的影响，算法简单，通信开销小。算法简单，通信开销小。v DMTS单跳同步误差受同步精度和计时精度影单跳同步误差受同步精度和计时精度影响。多跳精度随跳数的增加而下降，由于误差响。多跳精度随跳数的增加而下降，由于误差的正负相加抵消了一部分，两跳的误差约为单的正负相加抵消了一部分，两跳的误差约为单跳误差的跳误差的1.5倍。倍。v DMTS算法没有估计时钟的频率偏差，时钟保算法没有估计时钟的频率偏差，时钟保持同步的时间较短；也没有消除时钟计时对同持同步的时间较短；也没有消除时钟计时对同步精度的影响，因而其精度不高，不适用于定步精度的影响，因

33、而其精度不高，不适用于定位等要求高精度同步的应用。位等要求高精度同步的应用。RBS (Reference Broadcast synchronization)v RBS协议不是去同步报文的收发双方，而是去协议不是去同步报文的收发双方，而是去同步报文的同步报文的多个接收者多个接收者。v 如右图所示：在由如右图所示：在由3个节点组成的单跳网络中，参考节点个节点组成的单跳网络中，参考节点每发出一个参考报文，其广播域内的其他接收者节点都将每发出一个参考报文，其广播域内的其他接收者节点都将接收到该报文，并各自记录下接收到该参考报文时的本地接收到该报文，并各自记录下接收到该参考报文时的本地时刻。时刻。接收

34、者相互交换接收者相互交换它们记录的时刻并计算差值，该差它们记录的时刻并计算差值，该差值就是接收者之间的时钟值就是接收者之间的时钟偏移偏移。v 根据根据偏移信息偏移信息可以实现发送者可以实现发送者-接收者同步，接收者同步，若能精确地估计出报文传输延迟，这种方法将若能精确地估计出报文传输延迟，这种方法将能够取得很高的精度。然而仅根据单个报文的能够取得很高的精度。然而仅根据单个报文的传输很难准确地估计出传输延迟。传输很难准确地估计出传输延迟。v 左图为左图为发送者发送者-接收者接收者同步机制。可以看出，同步机制。可以看出，发送者发送者-接收者同步机制的同步关键路径为从接收者同步机制的同步关键路径为从

35、发送方到接收方。关键路径过长，导致传输延发送方到接收方。关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高。迟不确定性的增加，因此同步精度不可能很高。v 右图则是右图则是接收者接收者-接收者接收者同步机制，其关键路同步机制，其关键路径大为缩短，完全排除了发送时间和访问时间径大为缩短，完全排除了发送时间和访问时间的影响。的影响。 v RBS中是通过广播同步信标分组实现接收节点中是通过广播同步信标分组实现接收节点之间的相对时间同步，信标分组本身并不需要之间的相对时间同步，信标分组本身并不需要携带任何时标，不依赖于信标的发送时间。携带任何时标，不依赖于信标的发送时间。v 由于无线信道的

36、广播特性，信标分组相对所有由于无线信道的广播特性，信标分组相对所有接收节点而言同时发送到物理信道上，这样就接收节点而言同时发送到物理信道上，这样就除去发送时间和访问时间引入的时间同步误差。除去发送时间和访问时间引入的时间同步误差。v 对于传播时间，对于传播时间，RBS只关心只关心各个接收节点之间各个接收节点之间消息传播时间的差值消息传播时间的差值。对于射频信号来说，传。对于射频信号来说，传播时间差值非常小，播时间差值非常小，RBS忽略了传播时间带来忽略了传播时间带来的时间偏差。的时间偏差。v影响影响RBS机制性能的主要因素包括接收节点间的时间速率、接收机制性能的主要因素包括接收节点间的时间速率

37、、接收节点非确定因素和接收节点的个数等。节点非确定因素和接收节点的个数等。v为提高时间同步精度，为提高时间同步精度，RBS机制采用了统计技术，通过发送节点机制采用了统计技术，通过发送节点发送多个消息，获得接收节点之间时间差异的平均值。发送多个消息，获得接收节点之间时间差异的平均值。v对于时间速率问题，采用最小方差线性拟合，直线斜率就是两个对于时间速率问题，采用最小方差线性拟合，直线斜率就是两个节点的时间速率，直线上的点表示节点间的时间差异。节点的时间速率，直线上的点表示节点间的时间差异。vRBS的缺点是对网络有一定的要求，它不适合点对点通信的网络，的缺点是对网络有一定的要求，它不适合点对点通信

38、的网络，且要求网络有物理广播信道。且要求网络有物理广播信道。v扩展性不好，因为节点间本地时间戳通信需要额外的消息交换开扩展性不好，因为节点间本地时间戳通信需要额外的消息交换开销，不能很好地应用到大规模的多跳网络中。销，不能很好地应用到大规模的多跳网络中。RBS有很大的交换有很大的交换次数，对于具有，次数，对于具有，2个节点的单跳网络，需要个节点的单跳网络，需要O(n2)的消息交换，的消息交换，如果如果n很大时，消息交换开销是相当大的，导致节点的计算开销很大时，消息交换开销是相当大的，导致节点的计算开销也非常之大。也非常之大。vRBS中接收节点之间进行相互同步，但并不与发送节点同步；实中接收节点

39、之间进行相互同步，但并不与发送节点同步；实际上，在际上，在WSN中发送节点很可能也是一个普通的网络节点因而也中发送节点很可能也是一个普通的网络节点因而也需要同步，为使该节点和其它节点进行同步，需要另外一个节点需要同步，为使该节点和其它节点进行同步，需要另外一个节点作为参照广播发射节点，这导致了相当高的能耗。作为参照广播发射节点，这导致了相当高的能耗。TPSN (Timing-sync Protocol for Sensor Networks)v 图中的图中的T1、T4用节点用节点A的本地时间记录，的本地时间记录，T2、T3用节点用节点B的本地时间记录。的本地时间记录。v 节点节点A向节点向节点

40、B发送一个同步请求报文。节点发送一个同步请求报文。节点B在接收在接收到该报文后，记录下接收到时刻到该报文后，记录下接收到时刻T2，并立即向节点，并立即向节点A返返回一个同步应答报文，并把回一个同步应答报文，并把T2和该报文的发送时刻和该报文的发送时刻T3嵌入在报文中。当节点嵌入在报文中。当节点A接收到该报文时，记录下接收接收到该报文时，记录下接收到时刻到时刻T4。v 令令为当节点为当节点A的本地时刻为的本地时刻为T1时，节点时，节点A和和B之间的之间的时时偏偏。报文的。报文的传输延迟传输延迟均为均为d。多跳多跳TPSNv 全网周期性同步全网周期性同步“层发现”把网络组织成最短生成树逐层在相邻两

41、层节点间同步v 网络内两个节点的同步网络内两个节点的同步“后同步”查找两个节点间的路径在路径的相邻两个节点间进行TPSN同步v TPSN算法优点：算法优点：TPSN基于双向报文交换，因此同步精度高。对任意节点其同步误差取决于它距离根节点的跳数，而与网络中节点总数无关，使TPSN同步精度不会随节点数目增加而降级，从而使TPSN具有较好的扩展性。v TPSN算法的算法的缺点：缺点：TPSN本质上是对同步，因此全网同步的同步能耗高。一旦根节点失效，就要重新选择根节点并重新进行分级和同步阶段的处理，增加了计算和能量开销。另外，TPSN算法没有对时钟的频差进行估计，这使得它需要频繁同步，开销较大。HRT

42、S ( Hierarchy Referencing Time Synchronization Protocol )v 基于双向报文交换的用于传感器网络的时间同步协议基于双向报文交换的用于传感器网络的时间同步协议具有同步精度高的优点，但一次只能同步一对节点。具有同步精度高的优点，但一次只能同步一对节点。n个节点的单跳网络则需要个节点的单跳网络则需要n-1次同步操作，同步功耗较次同步操作，同步功耗较大。大。v RBS只需要一次同步过程就可完成一个单跳网内所有只需要一次同步过程就可完成一个单跳网内所有节点间的同步，同步功耗降低，当然，同步精度也相节点间的同步，同步功耗降低，当然，同步精度也相对变差。

43、对变差。v HRTS是一种结合了是一种结合了RBS所使用的参考广播同步技术所使用的参考广播同步技术和和TPSN所使用的双向报文交互同步技术，减少了同步所使用的双向报文交互同步技术，减少了同步所需的报文开销。所需的报文开销。v 图描述了层级时间同步的过程。假设单跳网络有包含图描述了层级时间同步的过程。假设单跳网络有包含时间基准节点在内的时间基准节点在内的3个节点个节点BS、n1和和n2。v步骤步骤1：时间基准节点：时间基准节点BS发出一个同发出一个同步请求报文，该报文随机指定一个邻步请求报文，该报文随机指定一个邻居节点（例如居节点（例如n1）作为应答者节点）作为应答者节点（即对应于图（即对应于图

44、1中的中的B节点）。同时节点）。同时n2也记录下该报文的接收到时刻，记为也记录下该报文的接收到时刻，记为T2 。v步骤步骤2：应答者节点：应答者节点n1向向BS节点发一节点发一个同步应答报文，报文中包含了个同步应答报文，报文中包含了T2与与T3。v步骤步骤3：现在：现在BS节点已经和节点已经和n1节点进节点进行了一次双向报文交换，行了一次双向报文交换，BS节点计算节点计算出它与出它与n1节点之间的时钟偏移节点之间的时钟偏移。v步骤步骤4：BS节点发送一个包含节点发送一个包含和和T2信息的报文。信息的报文。v步骤步骤5：当：当n1、n2节点接收到该报文，节点接收到该报文，对于应答者节点对于应答者

45、节点n1来说，只要将其本来说，只要将其本地时间减去地时间减去就达到与就达到与BS节点的瞬时节点的瞬时同步。对于其他节点来说，只要在其同步。对于其他节点来说，只要在其本地时间加上本地时间加上T2 T2 即可达到与即可达到与BS节点间的瞬时同步节点间的瞬时同步 v 根节点和应答者节点本质上是采用根节点和应答者节点本质上是采用TPSN同步。同步。v 根节点和非应答者节点本质上是双向报根节点和非应答者节点本质上是双向报文交换同步（但非文交换同步（但非TPSN）。）。v 应答者节点和非应答者节点本质上是接应答者节点和非应答者节点本质上是接收者收者-接收者同步。接收者同步。v HRTS协议充分利用了无线传

46、输的广播特协议充分利用了无线传输的广播特性来进一步降低性来进一步降低LTS协议的同步功耗。协议的同步功耗。LTS (Lightweight Tree-based synchronization)v LTS同步算法是一种与同步算法是一种与TPSN非常类似的算法。非常类似的算法。LTS侧重于侧重于降低时间同步的复杂度，在有限的计算代价下获得合理的降低时间同步的复杂度，在有限的计算代价下获得合理的同步精度。同步精度。v LTS有集中式和分布式两个版本，在有集中式和分布式两个版本，在集中式版本集中式版本中，首先中，首先以时间参考节点为根建立生成树，然后从树根开始以时间参考节点为根建立生成树，然后从树根

47、开始 逐级向逐级向叶子节点进行同步：叶子节点进行同步： 首先根节点同步其子节点，然后这些子节点再分别同步其子节点，如此继续下去，直到全部节点都被同步。 另外，为了达到最高的同步精度，要求生成树的深度尽可能的小。v 在在分布式版本分布式版本中，任何节点都可以发起同步过程，不需要中，任何节点都可以发起同步过程，不需要建立生成树，但是每个节点都必须知道参考节点的位置，建立生成树，但是每个节点都必须知道参考节点的位置，并且知道其到这些节点的路径。节点根据自己的时钟漂移并且知道其到这些节点的路径。节点根据自己的时钟漂移确定需要同步的时间，需要同步时，节点选择距离自己最确定需要同步的时间，需要同步时，节点

48、选择距离自己最近的一个参考节点，并向其发出近的一个参考节点，并向其发出同步请求同步请求，然后参考节点，然后参考节点向该节点的路径上的节点逐对进行同步，直到该节点被同向该节点的路径上的节点逐对进行同步，直到该节点被同步。步。v 在分布式同步算法中，由于节点有机会决定它自己的在分布式同步算法中，由于节点有机会决定它自己的同步，这就节约了不必要的同步开销。同时，通过融同步，这就节约了不必要的同步开销。同时，通过融合同步请求，降低了相同路径上请求的数目，节约了合同步请求，降低了相同路径上请求的数目，节约了资源。资源。v 在在LTS算法中，网络中的节点避免了算法中，网络中的节点避免了TPSN中与多个上中

49、与多个上层节点同步，而只与其直接父节点同步，减少了消息层节点同步，而只与其直接父节点同步，减少了消息交换数目和同步时间。该算法目的在于最小化复杂度交换数目和同步时间。该算法目的在于最小化复杂度以此降低能耗，精度一般。以此降低能耗，精度一般。v 同步次数是节点距离根节点跳数的线性函数，降低了同步次数是节点距离根节点跳数的线性函数，降低了消息交换次数，同时也降低了同步精度。算法的运行消息交换次数，同时也降低了同步精度。算法的运行时间与树的深度成比例，因此具有最小深度的生成树时间与树的深度成比例，因此具有最小深度的生成树时，收敛时间最短，但构造最小生成树也需要一定的时，收敛时间最短，但构造最小生成树

50、也需要一定的计算和通信开销。算法依赖于节点和参考节点的信息计算和通信开销。算法依赖于节点和参考节点的信息可靠性，错误的消息导致同步失败。可靠性，错误的消息导致同步失败。v LTS算法与算法与TPSN协议的区别在于，协议的区别在于，LTS算法中节点算法中节点只与自己的父节点只与自己的父节点进行同步，进行同步，其同步次数是路径长度的线性函数，同其同步次数是路径长度的线性函数，同时精度也随路径的长度线性降低，即在时精度也随路径的长度线性降低，即在降低计算代价的同时降低了同步精度。降低计算代价的同时降低了同步精度。 基于基于receiver/receiver的时间同步的时间同步v In this cl

51、ass of schemes the receivers of packets synchronize among each other, not with the transmitter of the packetv RBS = Reference Broadcast Synchronization (Elson et al)v RBS has two components: Synchronize receivers within a single broadcast domain A scheme for relating timestamps between nodes in diff

52、erent domainsv RBS does not modify the local clocks of nodes, but computes a table of conversion parameters for each peer in a broadcast domainv RBS allows for post-facto synchronizationTiny-Sync/Mini-Sync v 该算法基于一个假设：传感器网络中的该算法基于一个假设：传感器网络中的时钟频率恒定且线性相关。时钟频率恒定且线性相关。v Tiny-sync算法的思想算法的思想在每次获得新的数据点时，首

53、先与以前的数据点比较，如果新的数据点计算出的误差大于以前数据点计算的误差，则抛弃新的数据点；否则，采用新的数据点，抛弃旧的数据点。Tinysync算法仅需存储三到四个数据点的信息。v 节点节点i的硬件时钟是时间的硬件时钟是时间t是一个单调非递减的函数是一个单调非递减的函数Ci(t) ，在相当长一段时间内可以认为保持不变。在一段时间内节在相当长一段时间内可以认为保持不变。在一段时间内节点间的时钟频偏或相偏的差值保持不变，根据节点之间的点间的时钟频偏或相偏的差值保持不变，根据节点之间的线性相关性可以得出：线性相关性可以得出：C1(t)=a12C2(t)+b12v Tiny-Sync算法和算法和Mi

54、niSync算法采用传统的双向消息设算法采用传统的双向消息设计来估计节点时钟间的相对漂移和相对偏移。计来估计节点时钟间的相对漂移和相对偏移。v Sender-receiver 双向数据交换双向数据交换 Node 1 sends a probe message to node 2 time-stamped with t0 Node 2 generates timestamp tb and responds immediately Node 1 generates timestamp trv 不等式不等式: t0a12tb+b12tr 其中a12和b12分别表示两个时钟之间的相对时钟频偏和相对时钟

55、相偏，相对时钟频偏表示两者频率之比，相对时钟相偏表示两者相位之差。如果两个时钟精确同步，相对时钟频偏等于1，而相对时钟相偏等于零。 三个时间戳(t0, tb, tr)叫做数据点，算法通过不断地收集数据点来估计a12和b12，并且随着数据点个数的增加，算法的精度不断提高。 注意到注意到a12、b12对应的直线必定在所有的数据点对之间，因此图中最陡的对应的直线必定在所有的数据点对之间，因此图中最陡的和最缓的两条虚线给出了和最缓的两条虚线给出了a12、b12的上下界。的上下界。 并且上下界的区间越小，精度越高。通过求解所有数据点约束下的线性规并且上下界的区间越小，精度越高。通过求解所有数据点约束下的

56、线性规划问题，别可以得到最优解。但是，这种方法太过复杂，无法在计算资源有划问题，别可以得到最优解。但是，这种方法太过复杂，无法在计算资源有限的无线传感器网络中实现。限的无线传感器网络中实现。C2 (t)数据点 1数据点 3t0trC1(t) = a12H2(t) + b12C1(t)Node 1Node 2t0trtbtba12b12参数估计参数估计v Relative drift a12 and offset b12v The tighter the bound, the higher the synchronization precisionv Requires high amount o

57、f data points and quite complexv Algorithms precision increases with the increased number of data points.Tiny-Sync与与Mini-Sync之间的不同之间的不同v Different methods in selecting useful data pointsTiny-Sync Keep only four constrains of all data points Does nor always give the best solution for the boundsMini-S

58、ync is an extension of Tiny-Sync More optimal solution with increased complexity Keeps also the data points which may be useful by some future data points to give tighter bounds A data point is discarded only if it is definitely useless Quite complex selection criterion.vTS/MS算法是基于并非所有观察的数据点都有效的思想。每

59、个数算法是基于并非所有观察的数据点都有效的思想。每个数据点有两个限制漂移和偏移的元素组成，据点有两个限制漂移和偏移的元素组成，TS仅保持产生最佳边界仅保持产生最佳边界估计的四个约束。但算法可能会因为排除了一些当时看来没有而估计的四个约束。但算法可能会因为排除了一些当时看来没有而后来很可能提供最佳估计的数据点而导致算法效果并非一直是最后来很可能提供最佳估计的数据点而导致算法效果并非一直是最佳。佳。vMS是是TS算法的扩展，以较小的计算代价获得最优解决方法。是算法的扩展，以较小的计算代价获得最优解决方法。是为避为避TS算法排除将来可能有用的数据点而提出的，它通过定义一算法排除将来可能有用的数据点而

60、提出的，它通过定义一个标准来确保丢弃确实没用的数据点。个标准来确保丢弃确实没用的数据点。vTS/MS通过多个数据点来提供具有确定误差界限的偏移和估计，通过多个数据点来提供具有确定误差界限的偏移和估计，比一般简单的双程同步算法精度要高，且能够容忍消息丢失，可比一般简单的双程同步算法精度要高，且能够容忍消息丢失，可以扩展到任何允许双向数据通信的网络，适合与带宽、存储容量以扩展到任何允许双向数据通信的网络，适合与带宽、存储容量和计算能力非常有限的网络。和计算能力非常有限的网络。v该算法的该算法的缺点：缺点：收敛时间比较长，同步开销是一般成对同步算法收敛时间比较长，同步开销是一般成对同步算法的的k倍。

61、倍。 文献中建议MS存储40个三元组数据，存储开销较大。对于需要长期检测的传感器网络应用，传感器节点低成本的晶体振荡器很难保证时间速率和时间偏差的长时间稳定性，因而影响估计结果。FTSP (Flooding Time Synchronization Protocol)vFTSP 协议属于发送者协议属于发送者接收者协议。接收者协议。vFTSP协议基于协议基于MAC层时间戳技术，发送者节点在报文中的多个层时间戳技术，发送者节点在报文中的多个位置嵌入不同的时间戳。位置嵌入不同的时间戳。 发送节点在完成SYNC字节发送后在MAC层给以后发送的每个字节标记时间戳，接收节点在接收完SYNC字节也做同样的标

62、记，这样在发送节点和接收节点处都获得了多个时间戳，当消息传输完后双方分别对这些时间戳做同样的处理。 最后接收节点获得(global time，local time)时间对，因而得到相对于发送节点的偏移，调整本地钟。vFTSP算法对时钟漂移进行了线性回归分析。算法对时钟漂移进行了线性回归分析。FTSP算法考虑到在算法考虑到在特定的时间范围内节点时钟晶振频率是稳定的，因此节点间时钟特定的时间范围内节点时钟晶振频率是稳定的，因此节点间时钟偏移量偏移量(时间速率时间速率)与时间成线性关系：与时间成线性关系： 通过发送节点周期性广播时间同步消息，接收节点取得多个数据对(time，offset)，并构造最

63、佳拟合直线L(time)。通过回归直线L(time)，在误差允许的时间间隔内，节点可直接通过L(time)计算某一时间点节点间的时钟偏移量而不必发送时间同步消息进行计算，从而减少了消息的发送次数并降低了系统的能量开销。vFTSP也提供了多跳时间同步。也提供了多跳时间同步。 多跳的FTSP协议采用洪泛(Flooding)的方法广播时间基准节点的时间。当网络中的时间基准节点正常工作时，每个一段时间，它将广播一个报文。 广播消息由三个域组成：时间戳(timestamp)，根节点工D号(rootID)和顺序号(seqNum)。每次时间基准节点发送一个新的报文指示变量的值就加1(可以理解为同步的轮数)。

64、 当接收到消息，节点计算它的全局时间和嵌入在消息中的发送节点的全局时间之间的偏移，更新自己的全局时间，并广播自己的全局时间到邻居节点。 为避免在线性回归中使用冗余信息，每个节点保留接收到的消息的最大序号和最后一次接收到的消息所使用的rootID。同步消息只有在seqNum大于目前接收到的最大序号且新消息的rootID小于或等于最后一次接收到的rootID时才用于回归。 另外，如果节点在ROOT_TIMEOUT时间内没有监听到同步消息，它就宣布自己为新的根节点。为确保网络中仅有一个根节点，如果一个根节点听到来自于节点号更低的节点的时间同步消息，就放弃自己的根节点状态。v FTSP算法通过对收发过

65、程的分析，把时延进算法通过对收发过程的分析，把时延进一步分为发送中断处理时延、编码时延、传播一步分为发送中断处理时延、编码时延、传播时延、解码时延、字节对齐时延、接收终端处时延、解码时延、字节对齐时延、接收终端处理时延，进一步降低了时延的不确定性。理时延，进一步降低了时延的不确定性。v 另外，通过发射多个信令包，使得接收节点可另外，通过发射多个信令包，使得接收节点可以利用最小方差线性拟合估算自己和发送节点以利用最小方差线性拟合估算自己和发送节点的漂移和偏移差。通过良好的根节点选举机制，的漂移和偏移差。通过良好的根节点选举机制，针对根节点失效、新节点加入以及拓扑结构变针对根节点失效、新节点加入以

66、及拓扑结构变化等情况进行了优化，使得算法的健壮性很好，化等情况进行了优化，使得算法的健壮性很好，适合于军事等恶劣应用情况。适合于军事等恶劣应用情况。v FTSP是现有的典型时间同步协议中精度是现有的典型时间同步协议中精度最高的同步协议，并且有良好的健壮性，最高的同步协议，并且有良好的健壮性，不会因为个别节点的失效而收到影响。不会因为个别节点的失效而收到影响。v 但但FTSP基于基于MAC层时间戳技术的细节层时间戳技术的细节技术的实现来提高同步精度，使得技术的实现来提高同步精度，使得FTSP协议的通用性不强。并且洪泛的方式使协议的通用性不强。并且洪泛的方式使得能耗开销巨大。得能耗开销巨大。v 用于用于ZigBee网络的同步休眠与唤醒算法网络的同步休眠与唤醒算法同步算法总结同步算法总结v通过分析发现，通过分析发现，TPSN、LTS、和、和TSMS都用泛洪广播的方式构造层次都用泛洪广播的方式构造层次树，然后用双程同步的方法进行上下层节点间的时钟同步。但它们都没树，然后用双程同步的方法进行上下层节点间的时钟同步。但它们都没有有效地利用泛洪广播的信息，致使同步阶段消息丌销较大。有有效地利用泛洪广