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

第7章同步技术7.1时间同步的意义和特点7.2RBS同步机制7.3Tiny-sync/mini-sync同步机制7.4TPSN时间同步协议7.5时间同步的应用示例7.6本章小结7.1时间同步的意义和特点7.1.1传感网时间同步的意义7.1.2传感网时间同步协议的特点7.1.1传感网时间同步的意义无线传感网的同步管理主要是指时间上的同步管理。在分布式的无线传感器网络应用中，每个传感器节点都有各自的本地时钟。不同节点的晶体振荡器频率存在偏差，干扰等也会造成节点之间的运行时间的偏差。分布式系统的协同工作需要节点间的时间同步。时间同步机制是分布式系统基础框架中的一个关键机制。在分布式系统中，时间同步涉及“物理时间”和“逻辑时间”两个不同的概念。“物理时间”表示人类社会使用的绝对时间，而“逻辑时间”体现了事件发生的顺序关系，是一个相对概念。分布式系统通常需要—个表示整个系统时间的全局时间。全局时间根据需要可以是物理时间也可以是逻辑时间。时间同步机制在传统网络中已经得到了广泛应用，如网络时间协议(NetwolkTimeProtocl，NTP)是因特网采用的时间同步协议。另外，GPS和无线测距等技术也可以用来提供网络的全局时间同步。7.1.1传感网时间同步的意义（2）在传感网的很多应用中，同样需要时间同步机制。例如，在节点时间同步的基础上，可以远程观察卫星和导弹发射的轨道变化情况等。另外，时间同步能够用来形成分布式波束系统，构成TDMA调度机制，实现多传感器节点的数据融合，以及用时间序列的目标位置来估计目标的运行速度和方向，或者通过测量声音的传播时间确定节点到声源的距离或声源的位量。无线传感网时间同步机制的意义和作用主要体现在如下两方面。首先，传感器节点通常需要彼此协作，去完成复杂的监测和感知任务。数据融合是协作操作的典型例子，不同的节点采集的数据最终融合并形成一个有意义的结果。例如，在车辆跟踪系统中，传感器节点记录车辆的位置和时间，并传送给网关汇聚节点，然后结合这些信息来估计车辆的位置和速度。如果传感器节点缺乏统一的时间同步，则对车辆的位置估计将是不准确的。其次，传感网的一些节能方案是利用时间同步来实现的。例如，传感器可以在适当的时候休眠，在需要的时候再被唤醒。在应用这种节能模式的时候，网络节点应该在相同的时间休眠或被唤醒，也就是说在数据到来时，节点的接收器并没有关闭。在这里，传感网时间同步机制的设计目的，是为网络中所有节点的本地时钟提供共同的时间戳。7.1.2传感网时间同步协议的特点由于传感网节点的能量受限，以及低价格和小体积成为了传感网时间同步的主要限制。现有网络的时间同步机制往往关注最小化同步误差来达到最大的同步精度方面，而很少考虑计算和通信的开销，以及能耗问题。无法套用传统的时间同步机制协议。网络时间协议(NTP)在因特网得到了广泛使用，具有精度高、鲁棒性好和易扩展等优点。但是它依赖的条件在传感网中难以得到满足，因而不能直接移植运行，这主要是由于以下原因。（1）NTP协议很少考虑网络链路失效问题。而在传感网中，无线链路的通信质量受环境影响较大，甚至时常会有通信中断的情况。（2）NTP协议的网络结构相对稳定。而传感网的拓扑结构是动态变化的，简单的静态手工配置无法适应这种变化。（3）NTP协议中时间基准服务器间的同步需要通过其他基础设施的协助。如GPS系统和无线电广播报时系统，而在传感网的有些应用中，无法取得相应基础设施的支持。（4）NTP协议需要频繁交换信息，来不断校准时钟频率偏差带来的误差。并通过复杂的修正算法，消除时间同步消息在传输和处理过程中受到的非确定因素干扰，CPU使用、信道侦听和占用都不受任何约束。而传感网存在资源约束，必须考虑能量消耗。7.1.2传感网时间同步协议的特点（2）另外，GPS系统虽然能够以纳秒级的精度与世界标淮时间UTC保持同步，但需要配置高成本的接收机，同时无法在室内、森林或水下等有障碍的环境中使用。如果是用于军事目的，没有主控权的GPS系统也是不可依赖的。在传感网络中只可能为极少数节点配备GPS接收机，这些节点可以为传感网提供基准时间。基于传感网的特点，以及其在能量、价格和体积等方面的约束，使得NTP、GPS等现有时间同步机制并不适用于通常的传感网，需要专门的时间同步协议才能使其正常工作。7.1.2传感网时间同步协议的特点（3）目前几种成熟的传感网时间同步协议是：RBS（ReferenceBroadcastSynchronization，RBS)、Tiny-sync/Mini-Sync和TPSN(TimingsyncProtocolforSensorNetworks，TPSN)。RBS同步协议的基本思想是：多个节点接收同一个同步信号，然后在多个收到同步信号的节点之间进行同步。这种同步算法消除了同步信号发送方的时间不确定性。RBS同步协议的优点是时间同步与MAC层协议分离，它的实现不受限于应用层是否可以获得MAC层时间戳，协议的互操作性较好。这种同步协议的缺点是协议开销较大。Tiny-sync/Mini-sync是两种简单的轻量级时间同步机制。这两种算法假设节点的时钟漂移遵循线性变化，因此两个节点之间的时间偏移也是线性的，通过交换时标分组来估计两个节点间的最优匹配偏移量。为了降低算法的复杂度，通过约束条件丢弃冗余分组。TPSN时间同步协议采用层次结构，能够实现整个网络节点的时间同步。所有节点按照层次结构进行逻辑分级，表示节点到根节点的距离，通过基于发送者—接收者的节点对方式，每个节点与上一级的一个节点进行同步，最终所有节点都与根节点实现时间同步。7.2RBS同步机制RBS协议是基于接收者和接收者时间同步机制的代表协议，基本原理如图所示。发送节点广播一个参考（reference）分组，广播域中两个节点都能够接收到这个分组，每个接收节点分别根据自己的本地时钟记录接收到reference分组的时刻，然后交换它们记录的reference分组的接收时间。两个接收时间的差值相当于两个接收节点间的时间差值，其中一个节点根据这个时间差值更改它的本地时间，从而达到两个接收节点的时间同步。NIC接收者1接收者2关键路径7.2RBS同步机制（2）RBS机制中不是通告发送节点的时间值，而是通过广播同步参考分组来实现接收节点间的相对时间同步，参考分组本身不需要携带任何时标，也不需要知道是何时发送出去的。影响RBS机制性能的主要因素包括接收节点间的时钟偏差（时钟歪斜）、接收节点的非确定性因素、接收节点的个数等等。为了提高时间同步的精度，RBS机制采用了统计技术，通过多次发送参考消息，获得接收节点之间时间差异的平均值。对于时钟偏差问题，采用了最小平方的线性回归方法进行线性拟合，直线的斜率就是两个节点的时钟偏差，直线上的点就表示节点间的时间差。7.3Tiny-sync/mini-sync同步机制在通常情况下，节点的硬件时钟是时间的单调非递减函数。用来产生实时时间的晶体频率依赖于周围环境条件，在相当长一段时间内可以认为保持不变。由于节点之间时钟频偏和时钟相偏往往存在差异，但是它们时钟频偏或相偏之间的差值在一段时间内保持不变，根据节点之间的线性相关性，可以得出：122121)()(bttatt式中，a12和b12分别表示两个时钟之间的相对时钟频偏和相对时钟相偏。Tiny-sync算法和Mini-sync算法采用传统的双向消息设计来估计节点时钟间的相对漂移和相对偏移。节点1给节点2发送探测消息，时间戳是t0，节点2在接收到消息后产生时间戳tb。并且立刻发送应答消息。7.3Tiny-sync/mini-sync同步机制(2)121212120)()()()(bttattbttattbrb最后节点1在收到应答消息时产生时间戳tr，利用这些时间戳的绝对顺序和上面的等式可以得到下面的不等式：三个时间戳（t0、tb、tr）叫做数据点，Tiny-sync和Mini-sync利用这些数据点进行工作。随着数据点数目的增多，算法的精确度也提高。每个数据点遵循相对漂移和相对偏移的两个约束条件。7.3Tiny-sync/mini-sync同步机制(3)图7-3描述了数据点加在a12和b12上的约束。Tiny-sync中每次获得新的数据点时，首先和以前的数据点比较，如果新的数据点计算出的误差大于以前数据点计算出的误差，则抛弃新的数据点，否则就采用新的数据点，而抛弃旧的数据点。这样时间同步总共只需要存储三到四个数据点，就可以实现一定精度的时间同步。数据点1数据点2数据点31bt2t12a12b1rt01t12b12b12a12a1t7.3Tiny-sync/mini-sync同步机制(4)图7-4所示，在收到(A1,B1)和(A2,B1)后，计算出频偏和相偏的估计值，在收到数据点(A3,B3)之后，约束A1、B1、A3、B3被储存，A2、B2被丢弃了，但是后来接收到数据点(A4,B4)可以和(A2,B2)联合而构成更好的估计，但是此时(A2,B2)已经丢弃，只能获得次优估计。2t1t2A3B1B2B4A3A1A4BMini-sync算法是为了克服Tiny-sync算法中丢失有用数据点的缺点而提出的，该算法建立约束条件来确保仅丢掉将来不会有用的数据点，并且每次获取新的数据点后都更新约束条件。7.4TPSN时间同步协议7.4TPSN时间同步协议TPSN时间同步协议类似于传统网络的NTP协议，目的是提供传感网全网范围内节点间的时间同步。在网络中有一个节点可以与外界通信，从而获取外部时间，这种节点被称为根节点。根节点可装配诸如GPS接收机这样的复杂硬件部件，并作为整个网络系统的时钟源。TPSN协议采用层次型网络结构，首先将所有节点按照层次结构进行分级，然后每个节点与上一级的一个节点进行时间同步，最终所有节点都与根节点的时间同步，节点对之间的时间同步是基于发送者——接收者的同步机制。1．TPSN协议的操作过程TPSN协议假设每个传感器节点都有唯一的标识号ID，节点间的无线通信链路是双向的，通过双向的消息交换实现节点间的时间同步。TPSN协议将整个网络内的所有节点按照层次结构进行管理，负责生成和维护层次结构。很多传感网依赖网内处理，需要类似的层次型结构，如TinyDB需要数据融合树。这样，整个网络只需要生成和维护一个共享的层次结构。TPSN协议包括如下两个阶段。第一个阶段生成层次结构，每个节点部被赋予一个级别，根节点被赋予最高级别第0级，第级的节点至少能够与一个第（）级的节点通信；第二个阶段实现所有树节点的时间同步，第1级节点同步到根节点，第级的节点同步到第（）级的一个节点，最终所有节点都同步到根节点，实现整个网络的时间同步。下面详细说明该协议的两个阶段的实施细节。第一阶段被称为“层次发现阶段”。首先，在网络部署后，根节点通过广播“级别发现”分组，启动层次发现阶段。级别发现分组包含发送节点的ID和级别。根节点的邻居节点收到根节点发送的分组后，将自己的级别设置为分组中的级别加1，即为第1级，建立它们自己的级别，然后广播新的级别发现分组，其中包含的级别为1。节点收到第i级节点的广播分组后，记录发送这个广播分组的节点ID，设置自己的级别为（），广播级别被设置为（）的分组。这个过程持续进行，直到网络内的每个节点都被赋予了一个级别。节点一旦建立自己的级别，就忽略任何其他级别的发现分组，以防止网络产生洪泛拥塞。第二个阶段被称为“同步阶段”。在层次结构建立以后，根节点通过广播时间同步分组启动同步阶段。第1级节点收到这个分组后，各自分别等待一段随机时间，通过与根节点交换消息同步到根节点。第2级节点侦听到第1级节点的交换消息后，后退和等待一段随机时间，并与它在层次发现阶段记录的第1个级别的节点交换消息以进行同步。等待一段时间的目的是保证第2级节点在第1级节点的时间同步完成后才启动消息交换。最后每个节点与层次结构中最靠近的上一级节点进行同步，从而使所有节点都同步到了根节