无线传感器WSN期末报告

1、考查课程报告课程名称：无线传感器网路设计题目：无线传感器网络时间同步技术学院：信息工程与自动化学院专业：计算机科学与技术年级： 2010级学生姓名：指导教师：冯勇日期： 2012-12-25至 2013-1-1 教务处目录目录 .1 摘要 .2 1、背景.2 2、概述（包括定义、功能、分类方法等）.23、有代表性的协议（或算法） .3 4、对各种时间同步算法的比较.9 5、总结.11 无线传感器网络时间同步技术201010405227 孙正逵摘要无线传感器时间同步技术是无线传感器网络的一项重要技术, 它对无线传感器网络中许多技术的实现具有重大意义。有限的电池能量, 存储以及带宽限制等传感器固有

2、特性的存在 , 导致传统的时间同步算法不适合无线传感器网络。具体介绍了现有的无线传感器中的一些时间同步问题和时间同步算法, 并对其具体特性进行了深入的分析比较。1、背景近年来 , 无线传感器网络得到了快速的发展, 无线传感器网络实用与战场通信、抢险救灾和公共集会等突发性、临时性场合。 保持节点之间时间上的同步在无线传感器网络中非常重要, 它是保证无线传感网络中其他通信协议的前提, 如可靠的数据融合 , 精确的目标跟踪 , 低功耗 MAC 协议的设计 , 无线传感网络中大部分节点在没有工作的情况下都是处于休眠状态, 只有在需要的情况下才处于激活状态, 以及整个网络中为了保证数据可靠的传输, 减少

3、数据碰撞 , 在 MAC 层可直接采用 TDMA机制, 通过节点子节点个数动态分配时隙, 而这些的实现 , 就必须保持节点之间的同步 , 因此高效的同步机制就成了低功耗MAC 协议设计的前提。2002 年,Elson 等人在 HotNets 这影响未来网络研究发展方向的国际权威学术会议上首次提出无线传感器网络时间同步的研究课题以来, 得到了国内外研究学者的高度重视 , 目前也有相当多的研究成果被提出来, 并且单跳误差也控制在了微妙级 , 功耗也相当较低 , 可以符合大部分的环境需求。 NTP协议是目前因特网上采用的时间同步协议标准, 虽然精度高 , 当该协议的前提是网络中的链路失效非常小 ,

4、整个网络采用的是稳定的拓扑结构, 功耗大 , 采用的是有线传输 , 显然不适合于功耗、成本受限制的, 结构不稳定的无线传感网络中。GPS系统也可以提供高精度的时间同步 , 但它的信号穿透性差 ,GPS 天线必须安装在空旷的地方, 还有功耗较大 , 成本高, 所以不适合于无线传感网络中。 目前关于无线传感网络的同步机制研究中 , 主要有集中式同步机制 , 以及分布式一致同步机制, 因有集中式同步机制采用的是首先由根节点发起的拓扑生成树阶段, 在同步阶段 , 则采用相应的同步机制进行同步 , 节点只能与上一级节点同步, 无法与根节点直接同步 , 必然导致单跳累加的影响 , 整个网络的拓扑性差 ,

5、全网同步收敛速度慢。 随着无线传感网络规模的不断扩大, 节点体积不断缩小 , 集中式同步机制的运用越来越受到限制。 而分布式同步机制具有扩展性好, 抗毁性好等特性 , 通过邻居节点的信息融合,使节点的时间同步到一个虚拟的时间上, 不会因为根节点失效而导致全网重新同步的问题 , 收敛速度快。2、概述（包括定义、功能、分类方法等）2.1 量的廉价微型传感器节点组成， 通过无线传感器网络 （Wireless Sensor Network，WSN ） ：是由部署在监测区域内大无线通信方式形成的一个多跳的自组织的网络系统， 其目的是协作地感知、 采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者。

6、 传感器、感知对象和观察者构成了无线传感器网络的三个要素。2.2 无线传感器时间同步技术： 是一项解决传统网络时间同步存在的问题的一项技术。2.3 无线传感器时间同步技术的功能：由于传感器节点的时钟并不完美，会在时间上发生漂移， 所以观察到的时间对于网络中的节点来说是不同的。但很多网络协议的应用， 都需要一个共同的时间以使得网路中的节点全部或部分在瞬间是同步的。所以它具有以它主要解决下列问题：第一，传感器节点需要彼此之间并行操作和协作去完成复杂的传感任务。如果在收集信息过程中， 传感器节点缺乏统一的时间戳（即没有同步） ，估计 将是不准确的。第二，许多节能方案是利用时间同步来实现的。例如，传感

7、器可以在适当的时候休眠（通过关闭传感器和收发器进入节能模式），在需要的时候再唤 醒。在应用这种节能模式的时候，节点应该在同等的时间休眠和唤醒，也就是说当数据到来时， 节点的接收器可以接收， 这个需要传感器节点间精确的定时。2.4 时间同步技术所关注的主要性能参数时间同步技术的根本目的是为网络中节点的本地时钟提供共同的时间戳。对无线传感器网络WSN（Wireless Sensor Networks）的时间同步应主要应考虑以下几个方面的问题：(1) 能量效率。同步的时间越长，消耗的能量越多，效率就越低。设计WSN的时间同步算法需以考虑传感器节点有效的能量资源为前提。(2) 可扩展性和健壮性。 时间

8、同步机制应该支持网络中节点的数目或者密度的有效扩展，并保障一旦有节点失效时，余下网络有效且功能健全。(3) 精确度。针对不同的应用和目的，精确度的需求有所不同。(4) 同步期限。节点需要保持时间同步的时间长度可以是瞬时的，也可以和网络的寿命一样长。(5) 有效同步范围。可以给网络内所有节点提供时间，也可以给局部区域的节点提供时间。(6) 成本和尺寸。 同步可能需要特定的硬件，另外，体积的大小也影响同步机制的实现。(7) 最大误差。一组传感器节点之间的最大时间差，或相对外部标准时间的最大差。2.5 现有主要时间同步方法研究时间同步技术是研究WSN 的重要问题，许多具体应用都需要传感器节点本地时钟

9、的同步，要求各种程度的同步精度。WSN 具有自组织性、多跳性、动态拓扑性和资源受限性， 尤其是节点的能量资源、 计算能力、通信带宽、 存储容量有限等特点， 使时间同步方案有其特殊的需求，也使得传统的时间同步算法不适合于这些网络。3、有代表性的协议（或算法）3.1 用于传感器网络的时间同步协议（TPSN ）: 最易于想到的同步方法为：发送者在同步报文中嵌入其本地时间，在接收到该报文后， 接收者立即把自己的本地时间设置为嵌在该报文中的时间。但这种方法没有考虑到报文的传输延迟。而延迟测量时间同步协议（ DMTS ，Delay Measurement Time Synchronization）在此方法

10、的基础上， 进一步考虑了报文的传输延迟，接收者测量报文的传输延迟，并将本地时间设置为发送时刻加上报文传输延迟。延迟测量时间同步协议简单，但同步精度不高。美国加州大学洛杉矶分校（UCLA ）联网和嵌入式系统实验室（ NESL, Networked and Embedded Systems）的甘纳瑞沃尔 （S.Ganeriwal ）指出：传统的发送者 -接收者同步协议的同步精度较低的根源在于基于单向报文所估算出的报文传播延迟不够精确。如果采用双向报文， 基于报文传输的对称性， 有可能精确地计算出报文的传输延迟，因此能获得更高的同步精度。为此，他引入了NTP协议中的双向报文交换协议（如图1 所示）

11、，提出了用于传感器网络的时间同步协议。图 1 NTP协议的双向报文交换图中的 T1、T4 用节点 A 的本地时间记录， T2、T3 用节点 B的本地时间记录。节点 A向节点 B发送一个同步请求报文。节点B在接收到该报文后，记录下接收到时刻 T2， 并立即向节点 A返回一个同步应答报文，并把 T2 和该报文的发送时刻T3嵌入在报文中。当节点A接收到该报文时，记录下接收到时刻T4。令? 为当节点 A的本地时刻为 T1时，节点 A和 B之间的时偏。由于T1T4时间比较短，可认为当节点A的本地时刻为 T4时，其与节点 B之间的时偏没有变化。假设报文的传输延迟相同，均为 d。由：因此在 T4时刻，若在节

12、点 A的本地时间上增加修正量 ? ，就达到和节点 B 之间的瞬时的时间同步。用于传感器网络的时间同步协议将NTP时间同步方法引入无线传感器网络，可以获得比使用延迟测量时间同步协议更高的精度，但是其计算较为复杂，功耗较大，并且同步精度受到报文的传输延迟的影响；同时如果报文的双向传输不对称，同步精度也会受到影响。3.2 轻量基于树形分布的同步算法（LTS ）: LTS同步算法是一种与TPSN非常类似的算法。无线传感器网络通常只具有非常有限的计算资源， 但是其并不要求非常高的时间同步精度。针对无线传感器网络的这一特点， LTS侧重于降低时间同步的复杂度，在有限的计算代价下获得合理的同步精度。LTS有

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

14、选择距离自己最近的一个参考节点， 并向其发出同步请求， 然后参考节点向该节点的路径上的节点逐对进行同步，直到该节点被同步。LTS算法与 TPSN协议的区别在于，LTS算法中节点只与自己的父节点进行同步，其同步次数是路径长度的线性函数，同时精度也随路径的长度线性降低，即在降低计算代价的同时降低了同步精度。3.3 参考广播时钟同步协议（RBS ）用于传感器网络的时间同步协议可以看作是NTP在无线传感器网络上的改进版本， 而无线传感器网络的数据传播介质是无线信道，能否利用无线信道的广播特性设计相关的时间同步算法呢？参考广播时钟同步协议所依据的就是这样的算法。 与用于传感器网络的时间同步协议不同，参考

15、广播时钟同步协议不是去同步报文的收发双方，而是去同步报文的多个接收者。如图 2 的右图所示：在由 3 个节点组成的单跳网络中， 参考节点每发出一个参考报文，其广播域内的其他接收者节点都将接收到该报文，并各自记录下接收到该参考报文时的本地时刻。接收者们交换它们记录的时刻并计算差值，该差值就是接收者之间的时钟偏移。图 2 发送者 -接收者同步机制与接收者-接收者同步机制根据偏移信息可以实现发送者-接收者同步，若能精确地估计出报文传输延迟，这种方法将能够取得很高的精度。然而仅根据单个报文的传输很难准确地估计出传输延迟。 图 2 的左图为发送者 - 接收者同步机制。 可以看出，发送者 - 接收者同步机

16、制的同步关键路径为从发送方到接收方。关键路径过长，导致传输延迟不确定性的增加，因此同步精度不可能很高。 右图则是接收者-接收者同步机制，其关键路径大为缩短，完全排除了发送时间和访问时间的影响。3.4 层级时间同步协议（ HRTS ）基于双向报文交换的用于传感器网络的时间同步协议具有同步精度高的优点，但一次只能同步一对节点。n 个节点的单跳网络则需要n-1 次同步操作，同步功耗较大。 参考广播时钟同步协议只需要一次同步过程就可完成一个单跳网内所有节点间的同步，同步功耗降低， 当然，同步精度也相对变差。层级时间同步协议 6 是一种结合用于传感器网络的时间同步协议和参考广播时钟同步协议思想的同步方法

17、。图 3 描述了层级时间同步的过程。 假设单跳网络有包含时间基准节点在内的3 个节点 BS 、n1 和 n2。同步步骤如下：步骤 1：参见图 3，时间基准节点 BS相当前面图 1 中的 A节点，按照与用于传感器网络的时间同步协议相同的同步方式，时间基准节点BS发出一个同步请求报文，该报文随机指定一个邻居节点（例如n1）作为应答者节点（即对应于图 1 中的 B节点） 。同时 n2 也记录下该报文的接收到时刻，记为T2。步骤 2：与用于传感器网络的时间同步协议对同步方式相同，应答者节点 n1 向 BS节点发一个同步应答报文，报文中包含了T2与T3。步骤 3：现在 BS节点已经和 n1 节点进行了一

18、次双向报文交换，按照用于传感器的时间同步协议， BS节点计算出它与 n1 节点之间的时钟偏移? 。图 3 层级时间同步协议同步过程步骤 4：BS节点发送一个包含 ? 和T2信息的报文。步骤 5：当 n1、n2 节点接收到该报文，对于应答者节点n1 来说，只要将其本地时间减去 ? 就达到与 BS节点的瞬时同步。对于其他节点来说，只要在其本地时间加上T2-T2-? 即可达到与 BS节点间的瞬时同步。 层级时间同步协议充分利用了无线传输的广播特性来进一步降低LTS协议的同步功耗。和 LTS协议不同，基本同步单元不再是广度优先生成树的边，而是广度优先生成树中非叶子节点的单跳广播区域。同步次数是广度优先

19、生成树非叶子节点个数的线性函数，因此降低了同步功耗。但在同步精度上，层级时间同步协议略逊于LTS协议。3.5 Tiny-Sync/Mini-Sync Tiny-Sync 和 Mini-Sync 是两种适用于无线传感器网络的轻量级时间同步算法。该算法基于一个假设：传感器网络中的时钟频率恒定且线性相关。即对于时钟 T1、T2 有：其中 a12 为相对时钟漂移， b12 为相对时钟偏移。算法采用双向报文交换来估计相对时钟漂移和相对时钟偏移，如图4 所示：图 4 Tiny-Sync 和 Mini-Sync 的双向报文交换首先节点 1 向节点 2 发送一个探测数据包， 并加入发送时刻的本地时间To；节点

20、 2 收到该数据包后， 立即返回给节点 1 的一个数据包， 其中包含收到探测数据包的本地时间Tb；最后，当节点1 收到节点 2 发回的数据包时记录本地时间 Tr。通过这三个时间戳的绝对位置，可以得到：三个时间戳组成的三元组 (To,Tb,Tr)称作一个数据点。算法通过不断地收集这样的数据点估计a12 和 b12，并且随着数据点个数的增加，算法的精度不断提高。 如图 5 所示, 每个数据点对应于两个约束 （Tb,To）和（Tb,Tr ） 。注意到 a12、b12 对应的直线必定在所有的数据点对之间，因此图中最陡的和最缓的两条虚线给出了a12、b12 的上下界。并且上下界的区间越小，精度越高。通过

21、求解所有数据点约束下的线性规划问题，别可以得到最优解。但是， 这种方法太过复杂，无法在计算资源有限的无线传感器网络中实现。通过观察可以发现，计算上下界时并不需要所有数据点。如图5 所示，上下界其实只由第1、3 个数据点确定。 Tiny-Sync算法就利用了这一点，而只保存确定最优边界的4 个约束点，因此降低了计算复杂度。 但是，这种方法并不能总是给出最优的上下界， 在某些情况下算法可能会丢弃一些给出最优上下界的点。 Mini-Sync 是对 Tiny-Sync 的扩展，其思路是防止算法丢弃可能在未来能够给出更小的上下界的数据点，作者给出了一个标准来判断是否一个约束有可能会被用于计算最优边界，而

22、只在确认某一个约束不会被用到的时候才将其丢弃。 这样在提高了计算复杂度的情况下保证能够找到最优解。图 5 Tiny-Sync/Mini-Sync算法中数据点对时钟漂移和时钟偏移的约束Tiny-Sync 和 Mini-Sync 这两个算法，非常符合无线传感器网络的要求，即所需存储空间和计算资源非常少，同时对带宽的要求也很小。 但这种算法的假设条件（传感器网络节点时钟的漂移和偏移恒定）在低成本的传感器网络节点上是很难达到的。3.6FTSP 算法泛洪时间同步协议FTSP （Flooding Time Synchronization Protocol ）由 Vanderbilt大学 Branislav

23、 Kusy 等提出，目标是实现整个网络的时间同步且误差控制在微秒级。 该算法用单个广播消息实现发送节点与接收节点之间的时间同步。其特点为：(1) 通过对收发过程的分析，把时延细分为发送中断处理时延、编码时延、传播时延、解码时延、字节对齐时延、接收中断处理时延，进一步降低时延的不确定度；(2) 通过发射多个信令包，使得接收节点可以利用最小方差线性拟合技术估算自己和发送节点的频率差和初相位差；(3) 设计一套根节点选举机制，针对节点失效、新节点加入、拓扑变化等情况进行优化，适合于恶劣环境。FTSP算法对时钟漂移进行了线性回归分析。此算法考虑到在特定时间范围内节点时钟晶振频率是稳定的， 因此节点间时

24、钟偏移量与时间成线性关系，通过发送节点周期性广播时间同步消息，接收节点取得多个数据对， 构造最佳拟合直线，通过回归直线， 在误差允许的时间间隔内， 节点可直接通过它来计算某一时间节点间的时钟偏移量而不必发送时间同步消息进行计算，从而减少了消息的发送次数并降低了系统能量开销。FTSP结合 TPSN 和 RBS的优点，不仅排除了发送方延迟的影响，而且对报文传输中接收方的不确定延迟 （如中断处理时间、 字节对齐时间、 硬件编解码时间等）做了有效的估计。多跳的FTSP协议采用层次结构，根节点为同步源，可以适应大量传感器节点， 对网络拓扑结构的变化和根节点的失效有健壮性，精确度较好。该算法通过采用 MA

25、C 层时间戳和线性回归偏差补偿弥补相关的错误源，通过对一个数据包打多个时戳， 进而取平均和滤除抖动较大的时戳，大大降低了中断和解码时间的影响。 FTSP 采用洪泛的方式向远方节点传递时间基准节点的时间信息，洪泛的时间信息可由中转节点生成，因此误差累积不可避免。 另外， FTSP的功耗和带宽的开销巨大。3.7DMTS 算法延迟测量时间同步 DMTS(delay measurement time synchronization)算法的同步机制是基于发送方-接收方的同步机制。 DMTS 算法的实现策略是牺牲部分时间同步精度换取较低的计算复杂度和能耗，是一种能量消耗轻的时间同步算法。DMTS算法的基本

26、原理为：选择一个节点作为时间主节点广播同步时间，所有接收节点通过精确地测量从发送节点到接收节点的单向时间广播消息的延迟并结合发送节点时间戳， 计算出时间调整值， 接收节点设置它的时间为接收到消息携带的时间加上广播消息的传输延迟，调整自己的逻辑时钟值以和基准点达成同步，这样所有得到广播消息的节点都与主节点进行时间同步。发送节点和接收节点的时间延迟td 可由 td=nt+(t2-t1)得出。其中， nt 为发送前导码和起始字符所需的时间， n 为发送的信息位个数， t 为发送一位所需时间； t1 为接收节点在消息到达时的本地时间；t2 为接收节点在调整自己的时钟之前的那一时刻记录的本地时间， (t

27、2-t1)是接收处理延迟。DMTS 算法的优点是结合链路层打时间戳和时延估计等技术，消除了发送时延和访问时延的影响，算法简单，通信开销小。但DMTS 算法没有估计时钟的频率偏差，时钟保持同步的时间较短， 没有对位偏移产生的时间延迟进行估计，也没有消除时钟计时精度对同步精度的影响，因此其同步精度比FTSP略有下降，不适用于定位等要求高精度同步的应用。基于发送方 -接收方单向同步机制的算法在上述三类方法中需要发送的时间同步消息数目最少。 发送节点只要发送一次同步消息，因而具有较低的网络流量开销和复杂度，减少了系统能耗4、对各种时间同步算法的比较上面介绍的传感器网络时间同步协议代表了当前几类基本的时

28、间同步方法。接下来 , 将对这几种典型的时间同步算法在精度、收敛性、扩展性等各个方面进行详细的比较 , 以便大家可以选择出适合的时间同步算法。4.1 精度：RBS协议: 该协议可以有效地消除发送时延、访问时延和传输时延造成的时间同步误差。 RBS算法通过去除这3 个主要误差来源来提高时间同步的精度。Elson 等人在实际传感器平台上实现并测试了RBS算法, 获得了该算法的精度性能。所用的平台是BerkeleyMotes,RBS 算法在该平台上所得到的精度在11s以内。TPSN 协议: 与 RBS相比,TPSN协议考虑了传输时延、传播时延和接收时延所造成的影响 , 利用双向消息交换计算消息的平均

29、延迟, 提高了时间同步的精度。TPSN 协议的提出者在Mica 平台上实现了 TPSN和 RBS两种协议 , 所测得的 TPSN的时间同步平均误差是16.99s, 而 RBS的平均误差是 29.19s。Tiny-Sync/Mini-Sync算法 : 该算法利用多个时间同步数据点, 采用统计学的方法估计时间漂移和时间偏移, 这样虽然降低了时间同步的复杂性, 但是时间同步的精度也降低了。 而该算法所采用的数据过滤算法可以有效降低错误数据点对时间同步精度的影响。FTSP协议:FTSP 的提出者在 Mica 平台上实现了FTSP协议, 所测得的两个节点间时间同步的平均误差为1.5s, 这个运行结果明显

30、优于 RBS和 TPSN 协议在相同平台上的运行结果。 但是 FTSP协议对硬件的依赖性比较强。4.2 收敛性RBS协议: 发送参考广播的节点是预先选定的, 其他节点接收到参考广播消息后, 就开始了同步的过程 , 考虑到通信冲突 , 在几个同步周期后 , 全网就可以达到时间同步 , 收敛时间也比较短。TPSN 协议和 Tiny-Sync/Mini-Sync算法: 这两个时间同步方法的消息传递机制是相似的 , 都是分为两个过程 , 包括分层阶段和同步阶段 , 因此, 收敛时间较长。FTSP协议: 该协议的根节点选择过程是伴随时间同步一起进行的, 根节点选择不会对收敛性造成影响, 在几个同步周期后

31、 , 全网就能达到时间同步 , 收敛时间也比较短。4.3 可扩展性RBS协议: 在全网达到同步后 , 新节点的加入不会影响到参考广播节点的地位, 也就不会对全网的结构造成影响。 但是, 加入新的参考广播节点就会使得情况变得复杂 , 必须考虑处于不同广播域内的节点达到同步的问题。对于多跳网络的RBS协议需要依赖有效的分簇方法, 保证簇之间具有共同的节点以便簇间进行时间同步。TPSN协议和 Tiny-Sync/Mini-Sync算法: 从分层这个过程可以看出 , 新节点加入后会对网络的拓扑结构造成很大的影响, 因此, 两个协议的扩展性都很差, 这也是这两个协议最大的缺点之一。FTSP 协议: 如果

32、加入的是 ID 号最小的节点 , 该节点首先使自己与网络达到同步, 然后再进行根节点选择 , 不会影响网络时间同步。 如果不是 ID 号最小的节点 ,该节点只需要进行时间同步并广播时间同步消息。4.4 鲁棒性RBS 协议: 由 RBS 协议的同步原理可以看出, 节点失效或网络通信故障不会破坏整个拓扑结构 , 每个节点都有大量的冗余消息来保证时间同步。但是参考节点失效就会影响到该节点广播域内所有节点的同步。TPSN协议和 Tiny-Sync/Mini-Sync算法: 当某个节点失效 , 该节点以下的节点就有可能接收不到时间同步消息。全网的时间同步会受到个别节点的影响, 鲁棒性很差。FTSP协议 : 如果是根节