第四章2无线传感器网络的支撑技术时间同步4学时

1、第四章第四章 无线传感器网络无线传感器网络的支撑的支撑技术技术课程目录课程目录4.14.1无线传感器网络定位技术无线传感器网络定位技术4.24.2无线传感器网络时间同步技术无线传感器网络时间同步技术无线传感器网络无线传感器网络数据融合数据融合技术技术4.24.2 什么叫时间同步？什么叫时间同步？ 时间同步时间同步：使网络中所有节点使网络中所有节点的的时间保持一致，按照时间保持一致，按照网络应用的深度可以分为三种不同的情况网络应用的深度可以分为三种不同的情况：u第一种第一种：时序确定时序确定，判断事件发生的先后顺序，对本判断事件发生的先后顺序，对本地时间的要求比较低，只需要知道本节点与其余节点地

2、时间的要求比较低，只需要知道本节点与其余节点的相对时间即可的相对时间即可u第二种第二种：相对同步相对同步，节点维护自己的本地时钟，周期，节点维护自己的本地时钟，周期性地获取其邻居节点与本节点的时钟偏移，实现本节性地获取其邻居节点与本节点的时钟偏移，实现本节点与邻居节点的时间同步点与邻居节点的时间同步u第三种第三种：绝对同步绝对同步，所有节点的本地时间严格同步，所有节点的本地时间严格同步，等同于标准时间，这种情况对节点的要求最高，因此等同于标准时间，这种情况对节点的要求最高，因此实现也最为复杂实现也最为复杂 为什么要时间同步？为什么要时间同步？估计目标的运行速度和方向估计目标的运行速度和方向数据

3、融合需要时间同步数据融合需要时间同步用户交互性需要用户交互性需要 时间同步的参考时间来源？时间同步的参考时间来源？参考时间来源有两种情况参考时间来源有两种情况：u外同步外同步：标准参考时间来自于外部标准参考时间来自于外部u内同步内同步：参考时间来自于网络内部参考时间来自于网络内部某个节点的时间某个节点的时间1硬件时钟模硬件时钟模式式在硬件系统的时钟计数中，计算时间的一个重要的公式是在硬件系统的时钟计数中，计算时间的一个重要的公式是：式中，式中，w(t)是晶振的角频率，是晶振的角频率，k是依赖于晶体物理特性的常量，是依赖于晶体物理特性的常量，t是真实时间是真实时间变量，变量， c(t)是当真实时

4、间为是当真实时间为t时节点的本地时间。时节点的本地时间。2软件时钟软件时钟模式模式在软件时钟模型中，也存在一个用于记录时钟脉冲的计数器，软件时钟模型在软件时钟模型中，也存在一个用于记录时钟脉冲的计数器，软件时钟模型与硬件模型不同，它不直接修改本地时钟，而是根据本地时钟与硬件模型不同，它不直接修改本地时钟，而是根据本地时钟h(t)与真实时与真实时间的关系来换算成真实时间的函数间的关系来换算成真实时间的函数c(h(t)。c(h(t)=t0+h(t)h(t0)就是一个最简就是一个最简单的虚拟软件时钟的例子，实际应用中，软件时钟还要考虑到时钟漂移对时单的虚拟软件时钟的例子，实际应用中，软件时钟还要考虑

5、到时钟漂移对时钟的影响，因此更加复杂。钟的影响，因此更加复杂。 如何实现时间同步？如何实现时间同步？到目前为止，时间同步技术的研究已经有了到目前为止，时间同步技术的研究已经有了30年之久，最早的时间同步年之久，最早的时间同步机制是美国一所大学提出的网络时间协议（机制是美国一所大学提出的网络时间协议（NTP）。）。NTP协议的时间同步协议的时间同步精度可以达到毫秒级，通过外界一个精准的时间源接收机，顶层的时间服精度可以达到毫秒级，通过外界一个精准的时间源接收机，顶层的时间服务器可以获得高精度的参考时间，并向全网内提供统一的时间服务。务器可以获得高精度的参考时间，并向全网内提供统一的时间服务。l时

6、间同步技术起源时间同步技术起源NTPNTPNTP协议采用的是分层结构，拓扑结协议采用的是分层结构，拓扑结构如图所示，整个构如图所示，整个NTP协议分为三层结协议分为三层结构，其中构，其中A1、A2、A3为顶层的时间服为顶层的时间服务器，务器，B1、B2、B3为第二层时间服务为第二层时间服务器，其余均为客户机。器，其余均为客户机。第一层时间服务器通过第一层时间服务器通过地球观测卫星地球观测卫星或者或者位于科罗拉多的位于科罗拉多的WWV短波电台短波电台获获得标准的得标准的UTC时间，其他层的时间服务时间，其他层的时间服务器或者客户机选择一个或者多个上一层器或者客户机选择一个或者多个上一层的时间服务

7、器来同步本地时间，从而使的时间服务器来同步本地时间，从而使整个网络所有服务器和客户机时间同步。整个网络所有服务器和客户机时间同步。l时间同步技术起源时间同步技术起源NTPNTP通过上层服务器的标准参考时间，服务器利用一个闭环通过上层服务器的标准参考时间，服务器利用一个闭环控制系统来调整自己的本地时间控制系统来调整自己的本地时间l时间同步技术起源时间同步技术起源NTPNTPT1T2T3T4客户端客户端服务器服务器1221112TT234TT212)21()34(TTTT)34()12(TTTT假定假定，可计算出：，可计算出：假定客户端时钟比服务器时钟快假定客户端时钟比服务器时钟快l时间同步技术起

8、源时间同步技术起源NTPNTPNTP协议NTP协议层次型树形结构协议层次型树形结构UTC时间源一级时间基准服务器二级时间基准服务器客户端一级时间基准服务器二级时间基准服务器二级时间基准服务器一级时间基准服务器二级时间基准服务器客户端 NTPNTP不适合于不适合于WSNWSN 体积、计算能力和存储空间存在限制体积、计算能力和存储空间存在限制 目目标不同：局部最优而非全局最优标不同：局部最优而非全局最优l时间同步技术起源时间同步技术起源NTPNTPWSN同步算法与协议设计一跳一跳内内同步同步全网全网络络同步同步点到点点到点同步同步点到多点点到多点广播同步广播同步核心：消除关键路径引入核心：消除关键

9、路径引入的误差的误差构建层次构建层次逐跳同步逐跳同步各自同步各自同步协同优化协同优化核心：减小误差（方差）核心：减小误差（方差）累计累计在设计无线传感器网络的时间同步协议时，需要满在设计无线传感器网络的时间同步协议时，需要满足以下几点要求足以下几点要求： 能量有限能量有限 可扩展可扩展 稳定性稳定性l时间同步技术关键问题时间同步技术关键问题1、传输延迟不可预测传输延迟不可预测无线传感器网络中，时间同步技术的一个重要难题是报文传无线传感器网络中，时间同步技术的一个重要难题是报文传输延迟的不确定，由于处理器处理能力有限、网络负载不确输延迟的不确定，由于处理器处理能力有限、网络负载不确定等因素的影响

10、，延迟不能够被精确地计算出来；另外传输定等因素的影响，延迟不能够被精确地计算出来；另外传输延迟比要求的时间同步的精度要大得多延迟比要求的时间同步的精度要大得多。l时间同步技术关键问题时间同步技术关键问题影响时间同步的传输时延影响时间同步的传输时延发送时间发送时间：发送方用于组装并将报文换交给发送方：发送方用于组装并将报文换交给发送方MAC层的时层的时间。间。访问时间访问时间：指在发送方：指在发送方MAC层从获得报文后到获取无线信道发层从获得报文后到获取无线信道发送权的等待时间。送权的等待时间。传送时间传送时间：发送方发送报文的时间，即从报文的第一个字节开：发送方发送报文的时间，即从报文的第一个

11、字节开始发送到发送完最后一个字节的时间。始发送到发送完最后一个字节的时间。传播时间传播时间：报文从发送方以电磁波的形式传送到接收方所花费：报文从发送方以电磁波的形式传送到接收方所花费的时间的时间。接收时间接收时间：接收方接收报文的时间。它和传送时间完全相同，：接收方接收报文的时间。它和传送时间完全相同，具有确定性。具有确定性。接受时间接受时间：用于处理接收到的报文的时间：用于处理接收到的报文的时间。l时间同步技术关键问题时间同步技术关键问题2高能效高能效无线传感器网络的软无线传感器网络的软/硬件设施要求节点体积尽量小，硬件设施要求节点体积尽量小，尽量廉价，因此要求时间同步技术具有高能效的特点。

12、尽量廉价，因此要求时间同步技术具有高能效的特点。3可扩展、健壮可扩展、健壮采用逐跳的时间同步机制，因此随着网络规模的扩大，采用逐跳的时间同步机制，因此随着网络规模的扩大，时间同步技术必须保证网络扩展后同步误差不会超过误时间同步技术必须保证网络扩展后同步误差不会超过误差界限，并且能够稳定工作。差界限，并且能够稳定工作。l时间同步技术关键问题时间同步技术关键问题课程目录课程目录4.2.14.2.14.2.24.2.2时间同步模型时间同步模型时间同步协议时间同步协议无线传感器网络时间同步技术无线传感器网络时间同步技术4.24.21时钟模型时钟模型2时间同步机制时间同步机制4.2.14.2.1时间同步

13、模型时间同步模型1时钟模型时钟模型传感器网络中节点的本地时钟依靠对自身传感器网络中节点的本地时钟依靠对自身晶晶振中断计数实现振中断计数实现。 晶振的频率误差和初始计时时刻不同，使得晶振的频率误差和初始计时时刻不同，使得节点之间本地时钟不同步。节点之间本地时钟不同步。 如果能估算出本地时钟与物理时钟的关系或如果能估算出本地时钟与物理时钟的关系或本地时钟之间的关系，就可以构造对应的逻本地时钟之间的关系，就可以构造对应的逻辑时钟以达成同步。辑时钟以达成同步。 目前的逻辑时钟同步算法，同步精度已达到目前的逻辑时钟同步算法，同步精度已达到1 s，可以满足传感器网络中绝大部分应用的，可以满足传感器网络中绝

14、大部分应用的需求。需求。4.2.14.2.1时间同步模型时间同步模型（1）节点本地时钟模型）节点本地时钟模型在计算机系统中，时钟通常用在计算机系统中，时钟通常用晶体振荡器脉冲晶体振荡器脉冲来度量来度量:4.2.14.2.1时间同步模型时间同步模型（1）节点本地时钟模型）节点本地时钟模型两个主要参数：两个主要参数：4.2.14.2.1时间同步模型时间同步模型（1）节点本地时钟模型）节点本地时钟模型在工程实践中，因为温度、压力、电源电压等外界环境的在工程实践中，因为温度、压力、电源电压等外界环境的变化，往往会导致变化，往往会导致晶振频率产生波动晶振频率产生波动。因此，构造理想时。因此，构造理想时钟

15、比较困难。钟比较困难。在一般情况下，晶振频率的波动幅度并非是任意的，而是在一般情况下，晶振频率的波动幅度并非是任意的，而是局限在一定的范围之内，为了方便描述和分析，定义如下局限在一定的范围之内，为了方便描述和分析，定义如下3种时钟模型种时钟模型:4.2.14.2.1时间同步模型时间同步模型 速率恒定模型。速率恒定模型。速率恒定模型假定时钟速率是恒定的，速率恒定模型假定时钟速率是恒定的，即晶振频率没有波动发生。当要求的时钟精度远低于频率即晶振频率没有波动发生。当要求的时钟精度远低于频率波动导致的偏差时，该模型的假定应该是合理的。波动导致的偏差时，该模型的假定应该是合理的。 漂移有界模型。漂移有界

16、模型。定义时钟速率定义时钟速率 相对于理想速率相对于理想速率1的偏差的偏差为时钟漂移为时钟漂移(drift) ，即，即 。漂移有界模型在工程实践中非常有用，常用来确定时钟的漂移有界模型在工程实践中非常有用，常用来确定时钟的精度或误差的上下界。精度或误差的上下界。 漂移变化有界模型。漂移变化有界模型。该模型假定时钟漂移的变化该模型假定时钟漂移的变化 是有界的是有界的时钟漂移的变化主要是温度和电源电压等因素发生变化所时钟漂移的变化主要是温度和电源电压等因素发生变化所引起的，一般变化速率相对缓慢，可以通过适当的补偿算引起的，一般变化速率相对缓慢，可以通过适当的补偿算法加以修正。法加以修正。4.2.1

17、4.2.1时间同步模型时间同步模型（2）节点逻辑时钟模型）节点逻辑时钟模型任一节点任一节点i在物理时刻在物理时刻t的逻辑时钟读数可以表示为的逻辑时钟读数可以表示为其中，其中， 为当前本地时钟读数，为当前本地时钟读数， 为频率修正系数，为频率修正系数， 为初为初相位修正系数。采用逻辑时钟的目的是对本地时钟进行一相位修正系数。采用逻辑时钟的目的是对本地时钟进行一定的换算以达成同步。为了同步任意两个节点定的换算以达成同步。为了同步任意两个节点i和和j，构造，构造逻辑时钟有两种途径：逻辑时钟有两种途径： 根据本地时钟与物理时钟等全局事件基准的关系进行根据本地时钟与物理时钟等全局事件基准的关系进行变换变

18、换 根据两个节点本地时钟的关系进行对应换算。根据两个节点本地时钟的关系进行对应换算。两种方法都估计了频率修正系数和初相位修正系数，两种方法都估计了频率修正系数和初相位修正系数，精度较高。精度较高。4.2.14.2.1时间同步模型时间同步模型2同步机制同步机制节点时间校正技术是无线传感器网络时间同节点时间校正技术是无线传感器网络时间同步的核心和基础。目前主要的时间校正技术有单步的核心和基础。目前主要的时间校正技术有单向报文传递、双向报文交换、广播参考报文和参向报文传递、双向报文交换、广播参考报文和参数拟合技术数拟合技术。4.2.14.2.1时间同步模型时间同步模型（1）单向报文传递）单向报文传递

19、类似于类似于发送者发送者-接收者同步模式接收者同步模式4.2.14.2.1时间同步模型时间同步模型（1）单向报文传递）单向报文传递节点节点i在本地时间在本地时间 时刻向节点时刻向节点j发送一个报文，发送一个报文，包含时间戳包含时间戳 。假设节点。假设节点j在本地时间在本地时间 时刻收时刻收到上述报文。节点到上述报文。节点j不知道报文的传递时延不知道报文的传递时延d，所，所以只能对以只能对d进行估计，如果知道进行估计，如果知道d的上界和下界，的上界和下界，则可以得到则可以得到进而估计节点进而估计节点i和节点和节点j之间的时间偏差公式为之间的时间偏差公式为4.2.14.2.1时间同步模型时间同步模

20、型发送者发送者-接收者同步模式：发送者发送带有时间戳的同步包接收者同步模式：发送者发送带有时间戳的同步包给接收者，给接收者，以此来以此来同步接收者的时间。同步接收者的时间。这种模式的缺陷是不能够准确地估计算出报文的传输延迟，精度不高，通过这种模式的缺陷是不能够准确地估计算出报文的传输延迟，精度不高，通过单个报文的传输不能够准确地估算传输延迟单个报文的传输不能够准确地估算传输延迟，并且，并且假设报文传递过程中只有假设报文传递过程中只有传播延时，忽略了无线信道的许多不确定因素的影响传播延时，忽略了无线信道的许多不确定因素的影响 。（2）双向报文交换）双向报文交换双向报文交换时间校正技术复杂双向报文

21、交换时间校正技术复杂的的多。节点多。节点i在本地时在本地时钟钟 时刻向节点时刻向节点j发送同步报文，节点发送同步报文，节点j在本地时钟时刻在本地时钟时刻 接收到该报文，之后立即向节点接收到该报文，之后立即向节点i发送应答报文，节点发送应答报文，节点i在在本地时钟时刻本地时钟时刻 接收到该应答报文。则报文的往返时间接收到该应答报文。则报文的往返时间为为D，大小为，大小为 ，报文的传递时延，报文的传递时延d在在0D之间。如果之间。如果知道知道d的上界和下界，节点的上界和下界，节点j可以确定可以确定d在在 和和 之间。由此可以确定节点之间。由此可以确定节点i、j之间的时间之间的时间偏差为偏差为 假设

22、上行报文和下行报文的时间延迟相假设上行报文和下行报文的时间延迟相等，即等，即 双向报文交换是应用很广泛的一种时间校正技术，精双向报文交换是应用很广泛的一种时间校正技术，精度比较高。但是网络负载比较大，耗能较高，而且需要周度比较高。但是网络负载比较大，耗能较高，而且需要周期性地执行同步过程。期性地执行同步过程。4.2.14.2.1时间同步模型时间同步模型（3）广播参考报文）广播参考报文利用第三个节点利用第三个节点k作为参考节点，发送时间同步的参作为参考节点，发送时间同步的参考广播报文给相邻的节点考广播报文给相邻的节点i和节点和节点j。假设这个参考广播报。假设这个参考广播报文到达节点文到达节点i和

23、节点和节点j的时间延迟相等的时间延迟相等 。节点。节点j收到参收到参考广播报文后，立即发送包含有考广播报文后，立即发送包含有 信息的报文给节点信息的报文给节点i，于是节点于是节点i就可以计算收到两条报文的时间间隔就可以计算收到两条报文的时间间隔D为为广播参考报文的方法只能使节点间的时钟保持相对同步。广播参考报文的方法只能使节点间的时钟保持相对同步。4.2.14.2.1时间同步模型时间同步模型接收者接收者-接收者同步模式：多个接收者利用发送者发送的同接收者同步模式：多个接收者利用发送者发送的同步包在若干接收者之间进行同步，接收者步包在若干接收者之间进行同步，接收者-接收者模式缩短了接收者模式缩短

24、了关键路径，避免发送者到接收者的关键路径过长而导致的不关键路径，避免发送者到接收者的关键路径过长而导致的不准确的传输延迟估计准确的传输延迟估计。课程目录课程目录4.2.14.2.14.2.24.2.2时间同步模型时间同步模型时间同步协议时间同步协议无线传感器网络时间同步技术无线传感器网络时间同步技术4.24.21时间同步的类别时间同步的类别时间同步一般理解为使许多节点的时钟显示相同的时时间同步一般理解为使许多节点的时钟显示相同的时间，实际上有很多种不同类型的同步。间，实际上有很多种不同类型的同步。在为给定的应用选择同步算法时，要在最大程度满足在为给定的应用选择同步算法时，要在最大程度满足应用的

25、同时尽可能将计算、存储，尤其是能量开销降到最应用的同时尽可能将计算、存储，尤其是能量开销降到最低低。4.2.24.2.2时间同步协议时间同步协议（1）时钟速率同步与偏移同步）时钟速率同步与偏移同步速率同步是指各个传感器节点测量所得的时间间隔相速率同步是指各个传感器节点测量所得的时间间隔相等，在目标跟踪、定位等应用中，节点时钟速率同步是最等，在目标跟踪、定位等应用中，节点时钟速率同步是最低的同步要求。低的同步要求。偏移同步是指传感器节点在当前时刻偏移同步是指传感器节点在当前时刻t的时钟时间显的时钟时间显示相等，即在时刻示相等，即在时刻t传感器节点的时钟读出时间同为传感器节点的时钟读出时间同为T，

26、而，而不管时钟速率是否同步不管时钟速率是否同步，偏移同步对传感器网络中不同节偏移同步对传感器网络中不同节点间的时戳结合是必须的。点间的时戳结合是必须的。2 24.2.24.2.2时间同步协议时间同步协议（2）同步期限：长期同步与按需同步）同步期限：长期同步与按需同步时间同步的同步期限是指同步要保持的时间长短。在时间同步的同步期限是指同步要保持的时间长短。在长期同步的情况下，维持同步的代价是很大的，随着时间长期同步的情况下，维持同步的代价是很大的，随着时间的推移，节点间误差逐渐增加，可能还需要周期性地再同的推移，节点间误差逐渐增加，可能还需要周期性地再同步。步。按需同步是指传感器节点的时间在相关

27、事件发生前后按需同步是指传感器节点的时间在相关事件发生前后进行同步，它不需要大量的维护同步的通信开销，节省了进行同步，它不需要大量的维护同步的通信开销，节省了通信带宽和节点能量。对一些传感器网络的应用，按需同通信带宽和节点能量。对一些传感器网络的应用，按需同步效率更高。步效率更高。4.2.24.2.2时间同步协议时间同步协议（3）同步范围：全网同步与局部同步）同步范围：全网同步与局部同步同步范围是定义网络中哪些节点同步范围是定义网络中哪些节点是是需要同步的。在有需要同步的。在有些情况下，范围可能纯粹是地理上的距离。而在其他情况些情况下，范围可能纯粹是地理上的距离。而在其他情况下，逻辑距离更有用

28、，如网络中的跳数。根据不同的应用，下，逻辑距离更有用，如网络中的跳数。根据不同的应用，范围可能是网络中所有节点或者部分节点。范围可能是网络中所有节点或者部分节点。4.2.24.2.2时间同步协议时间同步协议（4）内同步和外同步）内同步和外同步一些应用只需要记录事件发生的先后顺序以及时间间一些应用只需要记录事件发生的先后顺序以及时间间隔，并不需要事件发生的绝对时间。这种情况下，只需要隔，并不需要事件发生的绝对时间。这种情况下，只需要内同步（相对同步），网络必须内部一致，不需要它们与内同步（相对同步），网络必须内部一致，不需要它们与外界标准时间保持一致性。外界标准时间保持一致性。另一类应用要求外同

29、步（绝对同步），即每个节点都另一类应用要求外同步（绝对同步），即每个节点都要与外部时间标度（如要与外部时间标度（如UTC）保持同步。通常的环境监控）保持同步。通常的环境监控或者需要数据存档的应用中，比较需要外同步，而且要求或者需要数据存档的应用中，比较需要外同步，而且要求的同步期限比较长。的同步期限比较长。4.2.24.2.2时间同步协议时间同步协议（5）发送者接收者同步与接收者接收者同步）发送者接收者同步与接收者接收者同步在进行发送者接收者同步时，发送者在报文中嵌入在进行发送者接收者同步时，发送者在报文中嵌入报文发送时间，而接收者在接收到报文后记录下接收时间，报文发送时间，而接收者在接收到报

30、文后记录下接收时间，并利用这些时间信息计算出收发双方的时钟偏移，进而达并利用这些时间信息计算出收发双方的时钟偏移，进而达到收发双方的时间同步。到收发双方的时间同步。接收者接收者同步时，发送者发送一个同步报文到接收者接收者同步时，发送者发送一个同步报文到多个接收者，这些接收者通过对同一个报文时间的比较，多个接收者，这些接收者通过对同一个报文时间的比较，计算出它们之间的时钟偏移，从而达到接收者一接收者同计算出它们之间的时钟偏移，从而达到接收者一接收者同步。步。4.2.24.2.2时间同步协议时间同步协议接收者接收者-接收者同步模式：多个接收者利用发送者发送的同接收者同步模式：多个接收者利用发送者发

31、送的同步包在若干接收者之间进行同步，接收者步包在若干接收者之间进行同步，接收者-接收者模式缩短了接收者模式缩短了关键路径，避免发送者到接收者的关键路径过长而导致的不关键路径，避免发送者到接收者的关键路径过长而导致的不准确的传输延迟估计准确的传输延迟估计。2典型的时间同步协议典型的时间同步协议（1）LTS协议协议（2）RBS协议协议（3）TPSN协议协议（4）DMTS协议协议（5）FTSP协议协议（6）HRTS协议协议（7）GCS协议协议（8）几种协议的比较）几种协议的比较4.2.24.2.2时间同步协议时间同步协议（1）LTS协议（协议（Lightweight Tree-based Synch

32、ronization） LTS同步算法的设计目标就是适用于低成本、同步算法的设计目标就是适用于低成本、低复杂度的传感器节点时间同步低复杂度的传感器节点时间同步； 侧重最小化同步的能量开销，同时具有鲁侧重最小化同步的能量开销，同时具有鲁棒性和自配置的特点棒性和自配置的特点。 划分为划分为3个组成部件：个组成部件： 重同步监测重同步监测 远程时钟估计远程时钟估计 时钟修正时钟修正4.2.24.2.2时间同步协议时间同步协议17/20LTS机制LTS应用于多跳网络应用于多跳网络根根节节点点1211111122222222222集中式集中式根根节节点点1211111122222222222分布式分布式

33、（2）RBS协议（协议（Reference Broadcast Synchronization） 参考广播时间同步协议参考广播时间同步协议 利用无线数据链路层的广播信道特性，一个利用无线数据链路层的广播信道特性，一个节点发送广播消息，接收到广播消息的一组节点发送广播消息，接收到广播消息的一组节点通过比较各自接收到广播消息的同步时节点通过比较各自接收到广播消息的同步时刻，来实现它们之间的时间同步。刻，来实现它们之间的时间同步。4.2.24.2.2时间同步协议时间同步协议工作原理：工作原理： RBS算法通过接收节点对时抵消发送时间和算法通过接收节点对时抵消发送时间和访问时间，发送节点广播一个信标分

34、组，广播域访问时间，发送节点广播一个信标分组，广播域中两个节点都能接收到这个分组，交换接收时间，中两个节点都能接收到这个分组，交换接收时间，两个接收时间的差值相当于两个接收节点间的时两个接收时间的差值相当于两个接收节点间的时间差值，其中一个节点可以根据这个时间差值更间差值，其中一个节点可以根据这个时间差值更改它的本地时间，从而实现两个节点的时间同步改它的本地时间，从而实现两个节点的时间同步。4.2.24.2.2时间同步协议时间同步协议7/20 RBS同步机制RBS机制的基本原理机制的基本原理发送节点发送节点接收节点接收节点信标分组信标分组接收节点接收节点接收信标分组本地时间接收信标分组本地时间

35、调整时间接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） 在RBS算法中，接收节点只需比较接收节点接收报文的时间之差，因此在发送节点发送的参考报文中无须携带发送节点的本地时间。同步误差只与接收者们是否在同一时刻记录本地时间有关，为了减小时间同步的误差，RBS采用了统计技术，广播多个时间同步消息，求相互之间消息到达的时间差的平均值，这样就能在最大程度上消除非同时记录的影响RBS （Reference

36、 Broadcast Synchronization） 接收者接收者同步的基本依据：接收者时间相移均值为0单跳RBS 用最小二乘法估计clock skew提高同步精度8/20 RBS同步机制RBS机制应用于多跳网络机制应用于多跳网络AB1432765考虑RBS协议应用于多跳网络情况：RBS能够消除发送节点引起的同步误差，在忽略传播时间的情况下，主要的误差来源就只剩下接收节点之间的处理时间差，以及发送节点和接收节点间的无线电同步误差，这两者都只有s级，因此RBS算法的同步精度非常高，但RBS算法的网络开销比较大，对于单播域中的n个节点和m个参考广播消息，RBS算法的复杂度为O(mn2)。在图示网

37、络中存在三个不同的单跳域A、B和C，其中4号和7号节点处于两个单跳域的交界，4号节点可以同步A区域和C区域的时间，7号节点可以同步B区域和C区域的时间，根据这两个节点我们可以得到相邻两区域的时间转换关系，从而达到全网的时间同步。 9/20RBS同步机制 RBS同步机制总结：RBS机制利用信道的广播特性来同步接收节点时间，去除了时间同步误差中所有发送节点引入的部分。通过多次广播分组获取平均值，能够提高RBS的时间同步精度。对于单个广播域内的n个节点和m个广播消息，RBS机制的复杂度为O（mn）。用于多跳网络的RBS机制需要依赖有效的分簇方法，保证簇之间有共同节点以便进行簇间时间同步10/20RB

38、S同步机制 后同步思想：后同步思想：通常情况下节点的时间不用同步，只有监测到一个事件发通常情况下节点的时间不用同步，只有监测到一个事件发生时，节点才首先用它的本地时间记录事件发生的时间，生时，节点才首先用它的本地时间记录事件发生的时间，然后采用然后采用RBS机制，一个机制，一个“第三方第三方”节点广播信标消息给节点广播信标消息给区域内的所有节点，接收节点利用这个同步消息作为一个区域内的所有节点，接收节点利用这个同步消息作为一个瞬时的时间参考点，同步它们监测到的事件发生时间。瞬时的时间参考点，同步它们监测到的事件发生时间。后同步机制能够实现后同步机制能够实现瞬时的节点间时间同步瞬时的节点间时间同

39、步，但是受限于，但是受限于广播信标分组的传输范围，它不适应于长距离或长时间通广播信标分组的传输范围，它不适应于长距离或长时间通信的时间同步。信的时间同步。后同步机制能够提供精确的局部空间范围的时间同步。后同步机制能够提供精确的局部空间范围的时间同步。（3）TPSN协议协议 通过采用层次型网络结构来提供全网范围内通过采用层次型网络结构来提供全网范围内节点同步。节点同步。 该机制分为拓扑建立阶段和同步建立阶段，该机制分为拓扑建立阶段和同步建立阶段，考虑了传播时间和接收时间，利用双向消息考虑了传播时间和接收时间，利用双向消息交换计算消息的平均延迟，提高了精度。交换计算消息的平均延迟，提高了精度。4.

40、2.24.2.2时间同步协议时间同步协议TPSN （ Timing-sync Protocol for Sensor Networks ）TPSN时间同步协议思想TPSN （ Timing-sync Protocol for Sensor Networks ）Thursday, July 07, 20221、TPSN是类似于NTP（Network Time Protocol）时间同步协议2、目的是提供传感器网络全网范围内节点间的时间同步3、节点结构中包含一个根节点，它与外界通信获取外界时间，以此作为整个网络系统的时钟源4、将节点分级后（根节点是0级，累加），每个节点同上一级的一个节点进行时间同

41、步，最终与根节点同步5、节点对之间的同步采用发送者-接收者同步机制（RBS）11/20TPSN时间同步协议根节点11212122222层次发现阶段层次发现阶段（广播级别发现分组）（广播级别发现分组）根节点11212122222同步阶段同步阶段（广播时间同步分组）（广播时间同步分组）每个传感器节点都有唯一的标识号ID节点间的无线通信链路是双向的，通过双向消息交换实现节点间的时间同步整个网络内所有节点按层次结构管理，由TPSN协议生成和维护TPSN协议过程协议准备协议准备目的：生成节点层次结构，每个节点被赋予一个级别，根节点为0级，第i级的节点至少能够与一个第（i-1）级得节点通信网络部署后，由根

42、节点广播级别发现分组来启动层次发现阶段，级别发现分组包含节点的ID和级别邻居节点收到分组后，将自己的级别设置为分组中的级别加1，然后广播新的级别发现分组节点收到第i级节点的广播分组后，记录发送这个广播分组的节点ID，设置自己的级别为（i+1），广播级别为（i+1）的分组，这个过程持续到网络内每个节点都被赋予一个级别节点一旦建立自己的级别，就忽略任何其他级别发现分组，防止网络产生洪泛拥塞TPSN协议过程第一阶段第一阶段 层次发现阶段（层次发现阶段（Level Discovery PhaseLevel Discovery Phase）Thursday, July 07, 2022目的：实现所有树节

43、点的时间同步，第1级节点同步到根节点，第i级的节点同步到第（i-1）级的一个节点，最终所有节点同步到根节点，实现整个网络的时间同步层次结构建立以后，根节点通过广播时间同步分组启动同步阶段第1级节点收到分组后，各自分别等待一段随机时间，再通过与根节点交换消息同步到根节点第2级节点侦听到第1级节点的交换消息后，等待一段随机时间，再与它记录的上一级别的节点交换消息进行同步，网络中的节点依次与上一级节点同步，最终都同步到根节点等待一段随机时间是为了保证该级节点在上一级节点同步完成后才启动消息交换TPSN协议过程第二阶段第二阶段 同步阶段（同步阶段（Synchronization PhaseSynchr

44、onization Phase）Thursday, July 07, 2022TPSN协议过程相邻级别节点间的同步机制相邻级别节点间的同步机制Thursday, July 07, 2022i-1级级i级级消息传播消息传播时延时延两节点间的两节点间的时间偏差时间偏差TPSN协议过程相邻级别节点间的同步机制相邻级别节点间的同步机制结论结论Thursday, July 07, 2022优点减少同步误差减少同步误差TPSN同步协议在MAC层消息开始发送到无线信道是才给消息添加时标，消除了访问时间带来的时间同步误差提高同步精度提高同步精度考虑了传播时间和接收时间，利用双向消息交换计算消息的平均延迟，提高

45、了时间同步的精度Thursday, July 07, 2022缺点Thursday, July 07, 2022没有考虑根节点失效问题新的节点加入时，需要初始化层次发现阶段，级别的静态特性减少了算法的鲁棒性使用范围Thursday, July 07, 2022TPSN能够实现全网范围内节点间的时间同步，同步误差与跳数距离成正比适合实现短期间的全网节点时间同步，若要长时间的全网节点时间同步，需要周期的执行TPSN协议进行同步，间隔时间根据具体情况决定考虑能耗问题，TPSN可以与后同步策略结合使用（4）DMTS协议（协议（Delay Measurement Time Synchronization

46、） 延迟测量时间同步通过对同步报文在传输路径上所有延迟测量时间同步通过对同步报文在传输路径上所有的延迟进行估计来实现节点间的时间同步。的延迟进行估计来实现节点间的时间同步。 其基本原理为：其基本原理为： 选择一个节点作为时间主节点（选择一个节点作为时间主节点（Leader）广播同步）广播同步报文，同步报文中嵌入其本地时间。报文，同步报文中嵌入其本地时间。 所有的接收节点测量这个时间广播报文的延迟，设所有的接收节点测量这个时间广播报文的延迟，设置其时间为接收到分组携带的时间加上报文的传输置其时间为接收到分组携带的时间加上报文的传输延迟时间。延迟时间。 时间同步精度主要由测量延迟的精度所决定。时间

47、同步精度主要由测量延迟的精度所决定。4.2.24.2.2时间同步协议时间同步协议发送者接收者：DMTS 最简单直观 单报文同步同步精度低 广播方式同步能耗低发送者发送者接收者接收者发送前导码发送前导码、同步字同步字嵌 入 时嵌 入 时标标t0接收前导码、接收前导码、同步字同步字接收接收ACK接收接收数据数据发送发送ACK接收接收处理处理时标时标t1时标时标t2发送时间发送时间访问时间访问时间DMTS（Delay Measurement Time Synchronization） DMTS机制的同步报文传输过程如机制的同步报文传输过程如下下图所示。主节点图所示。主节点在检测到信道空闲时，排除同步

48、报文发送的处理延迟和在检测到信道空闲时，排除同步报文发送的处理延迟和MAC层的访问延迟的影响，再在广播报文嵌入时间戳层的访问延迟的影响，再在广播报文嵌入时间戳t0。由于通信机制的要求，报文在发送前主节点必须先发送一由于通信机制的要求，报文在发送前主节点必须先发送一定数量的前导码（定数量的前导码（Premble）和同步字（）和同步字（Sync Word），以），以便同步节点进行接收同步报文。便同步节点进行接收同步报文。4.2.24.2.2时间同步协议时间同步协议14/20 DMTS同步机制发送者：接收者：同步消息MAC延迟发送前导码起始字符发送数据接收ACK加上时标t0接收前导码接收数据发送AC

49、K接收处理时标t1时标t2n=发送信息位个数t=发送每比特位需要的时间前导码和起始字符的发送时间=nt接收处理延迟=t2-t1忽略无线信号的传播延迟接收节点时钟为t0+nt+（t2-t1）15/20 DMTS同步机制vDMTS机制在多跳网络中采用机制在多跳网络中采用层次型层次型分级结分级结构实现全网内所有节点的时间同步构实现全网内所有节点的时间同步vDMTS同步机制总结：同步机制总结： DMTS是一种灵活的、轻量的和能量高效的能够实现全部网络节点时间同步的机制。 与RBS机制相比，DMTS机制的计算开销小，需要传输的消息条数少。 能够与外部世界标准时间同步，但同步精度相对较低。 DMTS在实现

50、复杂度、能量高效与同步精度之间进行了折中，能够应用在对时间同步要求不是非常高的网络中。 （5）FTSP协议（协议（Flooding Time Synchronization Protocol） 使用单个广播消息实现发送节点与接收节点之间的时使用单个广播消息实现发送节点与接收节点之间的时间同步间同步 算法的具体实现与算法的具体实现与DMTS有所不同有所不同 FTSP算法实现步骤如下算法实现步骤如下： FTSP算法在完成算法在完成SYNC字节发射后给时间同步消息标字节发射后给时间同步消息标记时间戳记时间戳t并并发送发送；SYNC字节类似字节类似DMTS算法中的算法中的Start Symbols；

51、时间戳时间戳t为当前时间减去包含时间戳为当前时间减去包含时间戳t的消息数据部的消息数据部分的发射时间分的发射时间； 消息数据部分的发射时间可通过数据长度和发射速消息数据部分的发射时间可通过数据长度和发射速率得出。率得出。4.2.24.2.2时间同步协议时间同步协议 接收节点记录接收节点记录SYNC字节最后到达时间字节最后到达时间t，并计算位偏移，并计算位偏移（bit offset）。在收到完整消息后，接收节点计算位偏移）。在收到完整消息后，接收节点计算位偏移产生的时间延迟产生的时间延迟tb，这通过偏移位数与接收速率得出。，这通过偏移位数与接收速率得出。 接收节点计算与发送节点间的时钟偏移量接收

52、节点计算与发送节点间的时钟偏移量， 然后调整然后调整本地时钟和发送节点时钟同步。本地时钟和发送节点时钟同步。4.2.24.2.2时间同步协议时间同步协议 MAC层时间戳技术 和平台直接相关，书中给出了在Mica2平台下的实现 基本同步原理 发送者-接收者同步 单个报文中包括多个时间戳（在报文的不同位置） 根据单个报文中的多个时间戳，可对中断等待时间进行补偿 对clock skew的补偿仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） (6) HRTS(6) HRTS（Hierarchy Referencing Time Hierarchy Referencing Time Synchronization ProtocolSynchronization Protocol） TPSN基于双向报文交换，因此同步精度高 TPSN本质上是对同步，因此全网同步的同步能耗高。 由DMTS发现，广播能降低全网同步能耗 结合广播和节点间的双向报文交换同步HRTS协议 BS n1 n2 n3 (a) BS n1 n2 n3 (b) BS n1 n2 n3 (c) n4 BS n1 n2 n3 (d) n4 HRTS（Hierarchy Referencing Time Synchronization Protocol） 根节