无线传感网 -第7章 同步技术

1、第第7章章 同步技术同步技术n7.1 时间同步的意义和特点时间同步的意义和特点n7.2 RBS同步机制同步机制n7.3 Tiny-sync/mini-sync同步机制同步机制n7.4 TPSN时间同步协议时间同步协议n7.5 时间同步的应用示例时间同步的应用示例n7.6 本章小结本章小结7.1 时间同步的意义和特点时间同步的意义和特点n7.1.1 传感网时间同步的意义传感网时间同步的意义n7.1.2 传感网时间同步协议的特点传感网时间同步协议的特点7.1.1 传感网时间同步的意义n无线传感网的同步管理主要是指时间上的同步管理。无线传感网的同步管理主要是指时间上的同步管理。q在分布式的无线传感器

2、网络应用中，每个传感器节点都有各自的本地时钟。不同节点的晶体振荡器频率存在偏差，干扰等也会造成节点之间的运行时间的偏差。分布式系统的协同工作需要节点间的时间同步。n时间同步机制是分布式系统基础框架中的一个关键机制。时间同步机制是分布式系统基础框架中的一个关键机制。n在分布式系统中，时间同步涉及在分布式系统中，时间同步涉及“物理时间物理时间”和和“逻辑时间逻辑时间”两个不同两个不同的概念。的概念。q“物理时间”表示人类社会使用的绝对时间，而“逻辑时间”体现了事件发生的顺序关系，是一个相对概念。分布式系统通常需要个表示整个系统时间的全局时间。全局时间根据需要可以是物理时间也可以是逻辑时间。n时间同

3、步机制在传统网络中已经得到了广泛应用，如网络时间协议时间同步机制在传统网络中已经得到了广泛应用，如网络时间协议(Netwolk Time Protocl，NTP)是因特网采用的时间同步协议。另外，是因特网采用的时间同步协议。另外，GPS和无线测距等技术也可以用来提供网络的全局时间同步。和无线测距等技术也可以用来提供网络的全局时间同步。7.1.1 传感网时间同步的意义（2）n在传感网的很多应用中，同样需要时间同步机制。在传感网的很多应用中，同样需要时间同步机制。q例如，在节点时间同步的基础上，可以远程观察卫星和导弹发射的轨道变化情况等。另外，时间同步能够用来形成分布式波束系统，构成TDMA调度机

4、制，实现多传感器节点的数据融合，以及用时间序列的目标位置来估计目标的运行速度和方向，或者通过测量声音的传播时间确定节点到声源的距离或声源的位量。n无线传感网时间同步机制的意义和作用主要体现在如下两方面。无线传感网时间同步机制的意义和作用主要体现在如下两方面。q首先，传感器节点通常需要彼此协作，去完成复杂的监测和感知任务。n数据融合是协作操作的典型例子，不同的节点采集的数据最终融合并形成一个有意义的结果。例如，在车辆跟踪系统中，传感器节点记录车辆的位置和时间，并传送给网关汇聚节点，然后结合这些信息来估计车辆的位置和速度。如果传感器节点缺乏统一的时间同步，则对车辆的位置估计将是不准确的。q其次，传

5、感网的一些节能方案是利用时间同步来实现的。n例如，传感器可以在适当的时候休眠，在需要的时候再被唤醒。在应用这种节能模式的时候，网络节点应该在相同的时间休眠或被唤醒，也就是说在数据到来时，节点的接收器并没有关闭。在这里，传感网时间同步机制的设计目的，是为网络中所有节点的本地时钟提供共同的时间戳。7.1.2 传感网时间同步协议的特点传感网时间同步协议的特点n由于传感网节点的能量受限，以及低价格和小体积成为了传感网时间同步的主要限制。由于传感网节点的能量受限，以及低价格和小体积成为了传感网时间同步的主要限制。n现有网络的时间同步机制往往关注最小化同步误差来达到最大的同步精度方面，而很少考虑现有网络的

6、时间同步机制往往关注最小化同步误差来达到最大的同步精度方面，而很少考虑计算和通信的开销，以及能耗问题。无法套用传统的时间同步机制协议。计算和通信的开销，以及能耗问题。无法套用传统的时间同步机制协议。n网络时间协议网络时间协议(NTP)在因特网得到了广泛使用，具有精度高、鲁棒性好和易扩展等优点。但在因特网得到了广泛使用，具有精度高、鲁棒性好和易扩展等优点。但是它依赖的条件在传感网中难以得到满足，因而不能直接移植运行，这主要是由于以下原因。是它依赖的条件在传感网中难以得到满足，因而不能直接移植运行，这主要是由于以下原因。n（1）NTP协议很少考虑协议很少考虑网络链路网络链路失效问题。而在传感网中，

7、无线链路的通信质量受环境影失效问题。而在传感网中，无线链路的通信质量受环境影响较大，甚至时常会有通信中断的情况。响较大，甚至时常会有通信中断的情况。n（2）NTP协议的协议的网络结构网络结构相对稳定。而传感网的拓扑结构是动态变化的，简单的静态手工相对稳定。而传感网的拓扑结构是动态变化的，简单的静态手工配置无法适应这种变化。配置无法适应这种变化。n（3）NTP协议中协议中时间基准时间基准服务器间的同步需要通过其他基础设施的协助。如服务器间的同步需要通过其他基础设施的协助。如GPS系统和无系统和无线电广播报时系统，而在传感网的有些应用中，无法取得相应基础设施的支持。线电广播报时系统，而在传感网的有

8、些应用中，无法取得相应基础设施的支持。n（4）NTP协议需要协议需要频繁交换信息频繁交换信息，来不断校准时钟频率偏差带来的误差。并通过复杂的修，来不断校准时钟频率偏差带来的误差。并通过复杂的修正算法，消除时间同步消息在传输和处理过程中受到的非确定因素干扰，正算法，消除时间同步消息在传输和处理过程中受到的非确定因素干扰，CPU使用、信道侦使用、信道侦听和占用都不受任何约束。而传感网存在资源约束，必须考虑能量消耗。听和占用都不受任何约束。而传感网存在资源约束，必须考虑能量消耗。7.1.2 传感网时间同步协议的特点（传感网时间同步协议的特点（2）n另外，另外，GPS系统虽然能够以纳秒级的精度与世界标

9、淮时间系统虽然能够以纳秒级的精度与世界标淮时间UTC保保持同步，但需要配置高成本的接收机，同时无法在室内、森林或持同步，但需要配置高成本的接收机，同时无法在室内、森林或水下等有障碍的环境中使用。如果是用于军事目的，没有主控权水下等有障碍的环境中使用。如果是用于军事目的，没有主控权的的GPS系统也是不可依赖的。系统也是不可依赖的。n在传感网络中只可能为极少数节点配备在传感网络中只可能为极少数节点配备GPS接收机，这些节点可接收机，这些节点可以为传感网提供基准时间。以为传感网提供基准时间。n基于传感网的特点，以及其在能量、价格和体积等方面的约束，基于传感网的特点，以及其在能量、价格和体积等方面的约

10、束，使得使得NTP、GPS等现有时间同步机制并不适用于通常的传感网，等现有时间同步机制并不适用于通常的传感网，需要专门的时间同步协议才能使其正常工作。需要专门的时间同步协议才能使其正常工作。7.1.2 传感网时间同步协议的特点（传感网时间同步协议的特点（3）n目前几种成熟的传感网时间同步协议是：目前几种成熟的传感网时间同步协议是：RBS（Reference Broadcast Synchronization，RBS)、Tiny-sync/Mini-Sync和和TPSN(Timing sync Protocol for Sensor Networks，TPSN) 。nRBS同步协议的基本思想是：

11、多个节点接收同一个同步信号，然后在多个收到同步信同步协议的基本思想是：多个节点接收同一个同步信号，然后在多个收到同步信号的节点之间进行同步。这种同步算法消除了同步信号发送方的时间不确定性。号的节点之间进行同步。这种同步算法消除了同步信号发送方的时间不确定性。RBS同步协议的优点是时间同步与同步协议的优点是时间同步与MAC层协议分离，它的实现不受限于应用层是否可以获层协议分离，它的实现不受限于应用层是否可以获得得MAC层时间戳，协议的互操作性较好。这种同步协议的缺点是协议开销较大。层时间戳，协议的互操作性较好。这种同步协议的缺点是协议开销较大。nTiny-sync/Mini-sync是两种简单的

12、轻量级时间同步机制。这两种算法假设节点的时钟是两种简单的轻量级时间同步机制。这两种算法假设节点的时钟漂移遵循线性变化，因此两个节点之间的时间偏移也是线性的，通过交换时标分组来漂移遵循线性变化，因此两个节点之间的时间偏移也是线性的，通过交换时标分组来估计两个节点间的最优匹配偏移量。为了降低算法的复杂度，通过约束条件丢弃冗余估计两个节点间的最优匹配偏移量。为了降低算法的复杂度，通过约束条件丢弃冗余分组。分组。nTPSN时间同步协议采用层次结构，能够实现整个网络节点的时间同步。所有节点按照时间同步协议采用层次结构，能够实现整个网络节点的时间同步。所有节点按照层次结构进行逻辑分级，表示节点到根节点的距

13、离，通过基于发送者层次结构进行逻辑分级，表示节点到根节点的距离，通过基于发送者接收者的节点接收者的节点对方式，每个节点与上一级的一个节点进行同步，最终所有节点都与根节点实现时间对方式，每个节点与上一级的一个节点进行同步，最终所有节点都与根节点实现时间同步。同步。7.2 RBS同步机制同步机制nRBS协议是基于接收者和接收者时间同步机制的代表协议，基本原理如图所示。协议是基于接收者和接收者时间同步机制的代表协议，基本原理如图所示。n发送节点广播一个参考（发送节点广播一个参考（reference）分组，广播域中两个节点都能够接收到这个）分组，广播域中两个节点都能够接收到这个分组，每个接收节点分别根

14、据自己的本地时钟记录接收到分组，每个接收节点分别根据自己的本地时钟记录接收到reference分组的时刻，分组的时刻，然后交换它们记录的然后交换它们记录的reference分组的接收时间。分组的接收时间。n两个接收时间的差值相当于两个接收节点间的时间差值，其中一个节点根据这个两个接收时间的差值相当于两个接收节点间的时间差值，其中一个节点根据这个时间差值更改它的本地时间，从而达到两个接收节点的时间同步。时间差值更改它的本地时间，从而达到两个接收节点的时间同步。7.2 RBS同步机制（同步机制（2）nRBS机制中不是通告发送节点的时间值，而是通过广播同步参考机制中不是通告发送节点的时间值，而是通过

15、广播同步参考分组来实现接收节点间的相对时间同步，参考分组本身不需要携分组来实现接收节点间的相对时间同步，参考分组本身不需要携带任何时标，也不需要知道是何时发送出去的。带任何时标，也不需要知道是何时发送出去的。n影响影响RBS机制性能的主要因素包括接收节点间的时钟偏差（时钟机制性能的主要因素包括接收节点间的时钟偏差（时钟歪斜）、接收节点的非确定性因素、接收节点的个数等等。歪斜）、接收节点的非确定性因素、接收节点的个数等等。n为了提高时间同步的精度，为了提高时间同步的精度，RBS机制采用了统计技术，通过多次机制采用了统计技术，通过多次发送参考消息，获得接收节点之间时间差异的平均值。对于时钟发送参考

16、消息，获得接收节点之间时间差异的平均值。对于时钟偏差问题，采用了最小平方的线性回归方法进行线性拟合，直线偏差问题，采用了最小平方的线性回归方法进行线性拟合，直线的斜率就是两个节点的时钟偏差，直线上的点就表示节点间的时的斜率就是两个节点的时钟偏差，直线上的点就表示节点间的时间差。间差。7.3 Tiny-sync/mini-sync同步机制同步机制n在通常情况下，节点的硬件时钟是时间的单调非递减函数。用来产生在通常情况下，节点的硬件时钟是时间的单调非递减函数。用来产生实时时间的晶体频率依赖于周围环境条件，在相当长一段时间内可以实时时间的晶体频率依赖于周围环境条件，在相当长一段时间内可以认为保持不变

17、。由于节点之间时钟频偏和时钟相偏往往存在差异，但认为保持不变。由于节点之间时钟频偏和时钟相偏往往存在差异，但是它们时钟频偏或相偏之间的差值在一段时间内保持不变，根据节点是它们时钟频偏或相偏之间的差值在一段时间内保持不变，根据节点之间的线性相关性，可以得出：之间的线性相关性，可以得出：122121)()(bttatt式中，a12和b12分别表示两个时钟之间的相对时钟频偏和相对时钟相偏。Tiny-sync算法和Mini-sync算法采用传统的双向消息设计来估计节点时钟间的相对漂移和相对偏移。节点1给节点2发送探测消息，时间戳是t0，节点2在接收到消息后产生时间戳tb。并且立刻发送应答消息。7.3

18、Tiny-sync/mini-sync同步机制同步机制(2)121212120)()()()(bttattbttattbrb最后节点1在收到应答消息时产生时间戳tr，利用这些时间戳的绝对顺序和上面的等式可以得到下面的不等式：三个时间戳（t0、tb、tr）叫做数据点，Tiny-sync和Mini-sync利用这些数据点进行工作。随着数据点数目的增多，算法的精确度也提高。每个数据点遵循相对漂移和相对偏移的两个约束条件。7.3 Tiny-sync/mini-sync同步机制同步机制(3)图7-3描述了数据点加在a12和b12上的约束。Tiny-sync中每次获得新的数据点时，首先和以前的数据点比较，

19、如果新的数据点计算出的误差大于以前数据点计算出的误差，则抛弃新的数据点，否则就采用新的数据点，而抛弃旧的数据点。这样时间同步总共只需要存储三到四个数据点，就可以实现一定精度的时间同步。7.3 Tiny-sync/mini-sync同步机制同步机制(4)图图7-4所示，在收到所示，在收到(A1,B1)和和(A2,B1)后，计算出频偏和相偏的估计值，在收到数据点后，计算出频偏和相偏的估计值，在收到数据点(A3,B3)之之后，约束后，约束A1、B1、A3、B3被储存，被储存，A2、B2被丢弃了，但是后来接收到数据点被丢弃了，但是后来接收到数据点(A4,B4)可以可以和和(A2,B2)联合而构成更好的

20、估计，但是此时联合而构成更好的估计，但是此时(A2,B2)已经丢弃，只能获得次优估计。已经丢弃，只能获得次优估计。Mini-sync算法是为了克服Tiny-sync算法中丢失有用数据点的缺点而提出的，该算法建立约束条件来确保仅丢掉将来不会有用的数据点，并且每次获取新的数据点后都更新约束条件。7.4 TPSN时间同步协议时间同步协议7.4 TPSN时间同步协议时间同步协议nTPSN时间同步协议类似于传统网络的时间同步协议类似于传统网络的NTP协议，目的是提供传感协议，目的是提供传感网全网范围内节点间的时间同步。网全网范围内节点间的时间同步。n在网络中有一个节点可以与外界通信，从而获取外部时间，这

21、种在网络中有一个节点可以与外界通信，从而获取外部时间，这种节点被称为根节点。根节点可装配诸如节点被称为根节点。根节点可装配诸如GPS接收机这样的复杂硬接收机这样的复杂硬件部件，并作为整个网络系统的时钟源。件部件，并作为整个网络系统的时钟源。nTPSN协议采用层次型网络结构，首先将所有节点按照层次结构进协议采用层次型网络结构，首先将所有节点按照层次结构进行分级，然后每个节点与上一级的一个节点进行时间同步，最终行分级，然后每个节点与上一级的一个节点进行时间同步，最终所有节点都与根节点的时间同步，节点对之间的时间同步是基于所有节点都与根节点的时间同步，节点对之间的时间同步是基于发送者发送者接收者的同

22、步机制。接收者的同步机制。1TPSN协议的操作过程协议的操作过程nTPSN协议假设每个传感器节点都有唯一的标识号协议假设每个传感器节点都有唯一的标识号ID，节点间的无线通信链路是双向的，通过双向的消息，节点间的无线通信链路是双向的，通过双向的消息交换实现节点间的时间同步。交换实现节点间的时间同步。TPSN协议将整个网络内的所有节点按照层次结构进行管理，负责生成和维协议将整个网络内的所有节点按照层次结构进行管理，负责生成和维护层次结构。很多传感网依赖网内处理，需要类似的层次型结构，如护层次结构。很多传感网依赖网内处理，需要类似的层次型结构，如TinyDB需要数据融合树。这样，整需要数据融合树。这

23、样，整个网络只需要生成和维护一个共享的层次结构。个网络只需要生成和维护一个共享的层次结构。TPSN协议包括如下两个阶段。第一个阶段生成层次结构，协议包括如下两个阶段。第一个阶段生成层次结构，每个节点部被赋予一个级别，根节点被赋予最高级别第每个节点部被赋予一个级别，根节点被赋予最高级别第0级，第级的节点至少能够与一个第（）级的节点级，第级的节点至少能够与一个第（）级的节点通信；第二个阶段实现所有树节点的时间同步，第通信；第二个阶段实现所有树节点的时间同步，第1级节点同步到根节点，第级的节点同步到第（）级的级节点同步到根节点，第级的节点同步到第（）级的一个节点，最终所有节点都同步到根节点，实现整个

24、网络的时间同步。下面详细说明该协议的两个阶段的一个节点，最终所有节点都同步到根节点，实现整个网络的时间同步。下面详细说明该协议的两个阶段的实施细节。实施细节。n第一阶段被称为第一阶段被称为“层次发现阶段层次发现阶段”。首先，在网络部署后，根节点通过广播。首先，在网络部署后，根节点通过广播“级别发现级别发现”分组，启动层次分组，启动层次发现阶段。级别发现分组包含发送节点的发现阶段。级别发现分组包含发送节点的ID和级别。根节点的邻居节点收到根节点发送的分组后，将自己和级别。根节点的邻居节点收到根节点发送的分组后，将自己的级别设置为分组中的级别加的级别设置为分组中的级别加1，即为第，即为第1级，建立

25、它们自己的级别，然后广播新的级别发现分组，其中包级，建立它们自己的级别，然后广播新的级别发现分组，其中包含的级别为含的级别为1。节点收到第。节点收到第i级节点的广播分组后，记录发送这个广播分组的节点级节点的广播分组后，记录发送这个广播分组的节点ID，设置自己的级别为，设置自己的级别为（），广播级别被设置为（）的分组。这个过程持续进行，直到网络内的每个节点都被赋予了一个级别。（），广播级别被设置为（）的分组。这个过程持续进行，直到网络内的每个节点都被赋予了一个级别。节点一旦建立自己的级别，就忽略任何其他级别的发现分组，以防止网络产生洪泛拥塞。节点一旦建立自己的级别，就忽略任何其他级别的发现分组，

26、以防止网络产生洪泛拥塞。n第二个阶段被称为第二个阶段被称为“同步阶段同步阶段”。在层次结构建立以后，根节点通过广播时间同步分组启动同步阶段。第。在层次结构建立以后，根节点通过广播时间同步分组启动同步阶段。第1级节点收到这个分组后，各自分别等待一段随机时间，通过与根节点交换消息同步到根节点。第级节点收到这个分组后，各自分别等待一段随机时间，通过与根节点交换消息同步到根节点。第2级节点级节点侦听到第侦听到第1级节点的交换消息后，后退和等待一段随机时间，并与它在层次发现阶段记录的第级节点的交换消息后，后退和等待一段随机时间，并与它在层次发现阶段记录的第1个级别的节个级别的节点交换消息以进行同步。等待一段时间的目的是保证第点交换消息以进行同步。等待一段时间的目的是保证第2级节点在第级节点在第1级节点的时间同步完成后才启动消息级节点的时间同步完成后才启动消息交换。最后每个节点与层次结构中最靠近的上一级节点进行同步，从而使所有节点都同步到了根节点。交换。最后每个节点与层次结构中最靠近的上一级节点进行同步，从而使所有节点都同步到了根节点。7.5 时间同步的应用示例n磁阻传感网如何对机动车辆进行测速。n网络必须先完成时间同