haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中历政地初中历政地

第4章-5 时间同步

发布时间:2014-01-11 15:57:28  

第4章-5 WSN时间同步

5.1 时间同步概述 5.1.1消息传递过程分解 将消息在WSN节点间传递的过程分解成不同的阶段是对时间同步问题研究 的关键,一条消息在WSN节点间的传递过程可分解成以下六个部分。 (1)Send Time:发送节点构造一条消息所需要的时间,包括内核协议处理 和缓冲时间等,它取决于系统调用开销和处理器当前负载。 (2)Access Time:消息等待传输信道空闲所需时间,即从等待信道空闲到 消息发送开始时的延迟,它取决于网络当前负载状况。 (3)Transmission Time:发送节点按位(bit)发射消息需时间,该时间取决 于消息长度和发射速率。 (4)Propagation Time:消息在两个节点之间传输介质中的传播时间,该时 间主要取决于节点间的距离(电磁波在空气中的传播速率是一定的)。 (5)Reception Time:接收节点按位(bit)接收消息并传递给MAC层的时间, 这个过程和(3)相对应。 (6)Receive Time:接收节点重新组装消息并传递给上层应用所需的时间。

5.1.2 算法设计的影响因素 第一,传感器节点需要彼此并行操作和协作去完成复杂的传感任务。数据 融合是这种并行操作的实例,不同的节点收集的数据集合为一个有意义的结 果。例如,在车辆跟踪系统中,传感器节点记录车辆的位置和时间并传送给 网关节点,然后结合这些信息估计车辆的位置和速度。很明显,如果传感器 节点缺乏统一的时间戳(也就是说没有同步),估计将是不准确的。 第二,许多节能方案是利用时间同步来实现的。例如,传感器可以在适当 的时候休眠(通过关闭传感器和收发器进入节能模式),在需要的时候再唤醒。 当应用这种节能模式的时候,节点应该在同等的时间休眠和唤醒,也就是说 当数据到来时,节点的接收器并没有关闭。这个需要传感器节点间精确的定 时。调度算法,例如TDMA,能够通过不同的时隙共享信道,进而去估计传 输阻塞和保存能量。因此,同步是信道调度的基础。

5.1.3 算法的性能指标 WSN时间同步方案设计的目的是为网络中节点的本地时钟提供共同的时间 戳[6]。评价一个WSN时间同步算法的性能,一般包含网络能量效率、可扩展 性、精确度、健壮性、寿命、有效范围、成本和尺寸、直接性等指标。 (1) 能量效率。无线传感器网络的主要特点就是节点的能量受限问题,设 计的时间同步算法需以考虑传感器节点有效的能量资源作为前提。 (2) 可扩展性。WSN需要部署大量的传感器节点,时间同步方案应该有效 扩展网络中节点的数目或者密度。 (3) 精确度。精确度的需求依赖于特殊的应用和时间同步的目的而有所不 同,对于某些应用,知道时间和消息的先后顺序就够了,然而

某些其他的, 则要求同步精确到微秒。 (4) 健壮性。WSN可能在敌对区域长时间无人管理,一旦某些节点失效, 在余下的网络中,时间同步方案应该继续保持有效并且功能健全。

(5) 寿命。时间同步算法提供的同步时间可以是瞬时的,也可以和网络的寿命一 样长。

(6) 有效范围。时间同步方案可以给网络内所有的节点提供时间,也可以给局部 区域内的部分节点提供时间。由于可扩展性的原因,全面的时间同步是有难度的, 对于大面积的传感器网络,考虑到能量和带宽的利用,也是非常昂贵的。另一方 面,大量节点达到共同时间需要收集来自遥远节点的用于全面同步的数据,对于 大规模的无线传感器网络是很难实现的,而且直接影响了同步的精确度。
(7) 成本和尺寸。WSN节点非常小而且廉价。因此,在传感器网络节点上安装 相对较大或者昂贵的硬件(例如GPS接收器)是不合逻辑的。WSN的时间同步方案 必须考虑有限的成本和尺寸。 (8) 直接性。某些WSN的应用,比如紧急情况探测(例如气体泄漏检测,入侵检 测等)需要将发生的事件直接发送到网关。在这种应用中,网络不容许任何的延迟, 但是某些协议是在依赖事件发生后的额外处理而设计的,这些协议需要节点在任 何时间达到预先同步,这样看来,似乎和前面提到的直接性有些矛盾。 人们已经提出了很多关于WSN的时间同步算法。例如RBS,TPSN等等,本章 就现存的用于WSN的各种时间同步协议进行了综述和总结。

5.2 时间同步算法 5.2.1经典时间同步算法 1.基于参考广播的时间同步协议(RBS) 2.WSN时间同步协议(TPSN)

3.Tiny-Sync算法和Mini-Sync算法
4.LTS算法

1.基于参考广播的时间同步协议(RBS)
由于RBS算法将发送者的不确定性从关键路径中排除(如图7-1),所以获得 了比传统的利用节点间双向信息交换实现同步的方法较好的精确度。由于发 送者的不确定性对RBS算法的精确度没有影响,误差的来源主要是传输时间 和接收时间的不确定性。首先假设单个广播在相同时刻到达所有接收者,因 此,传输误差可以忽略。当广播范围相对较小(相对于同步精确度好几倍的光 速),这种假设是正确的,而且也满足传感器网络的实际情形,所以在分析这 个模型精确度的时候,只需要考虑接收时间误差。

RBS(Reference Broadcast Synchronization)算法[7]是Elson等人以“第三 节点”实现同步的思想而提出的。该算法是一个典型的接受者——接受者模 式的同步算法。它是利用无线链路层广播信道特点,一个节点发送广播消息, 在同一广播域的其它节点同时接收广播消息,并记录该点的时间戳。之后接 收节点通过消息交换它们的时

间戳,通过比较和计算达到时间同步。该算法 中,节点发送参考消息给它的相邻节点,这个参考消息并不包含时间戳。相 反的,它的到达时间被接收节点用作参考来对比本地时钟。此算法并不是同 步发送者和接收者,而是使接收者彼此同步。

在RBS算法最简单的构成中,节点广播单个脉冲给两个接收者,接收者在 收到脉冲的基础上再交换记录的脉冲时间,进而估计节点间相对的相位偏移。 这种基本的RBS算法可以扩展为两个方面:① 通过单个脉冲同步个节点(>2)。 ② 通过增加参考脉冲的数目提高精确度通过仿真,在同步两个节点的时候, 30个参考广播(对于时间的单同步)能够将精确度从11μs提高到1.6μs,同时可 以利用这个冗余信息估计时钟歪斜。 与通过多个观测值取相位偏移的平均值不同(例如30个参考脉冲平均),RBS 算法是通过最小均方线性衰落的方法取得这个数据。然后,节点本地时钟相对 于远端节点的频率和相位可以通过图线的斜率和截取值获得。

2.WSN时间同步协议(TPSN)
TPSN(Timing-Sync Protocol for Sensor Networks)算法[8]是Ganeriwal等 人提出的适用于WSN整个网络范围内的时间同步算法。该算法分两步:分级 和同步。第一步的目的是建立分级的拓扑网络,每个节点有个级别。只有一 个节点定为零级,叫做根节点。在第二步,i级节点与i-1级节点同步,最后所 有的节点都与根节点同步,从而达到整个网络的时间同步。 (1)分级 (2)同步

TPSN算法不仅应用在了Berkeley的Mica上,而且利用了在MAC层给包打 时间戳,这样可以降低发送者的不确定性。Ganeriwal等人声称TPSN算法获 得的精确度两倍于RBS算法,而且声明RBS算法的6.5μs的精确度是由于使 用了高级操作系统(Linux)和更加稳定的晶体,因此,RBS算法应用在Mica中 获得了和TPSN算法一样优良的精确度。在早些时候,RBS算法确实在 Berkeley Motes上测试过,获得的精确度是11μs。但是,Ganeriwal等人证 明说RBS算法在Mica上的实验结果是29.13μs,而TPSN算法在相同的平台上 是16.9μs。本质上来说,通过在底层加时间戳使得发送端的不确定性对整个 同步的误差影响很小,因此,在WSN中,经典的“发送—接收同步”比“接 收—接收同步”更加有效。

3.Tiny-Sync算法和Mini-Sync算法 Tiny-Sync算法和Mini-Sync算法是由Sichitiu和Veerarit tip han 提出的两种 用于WSN的时间同步算法[9]。该算法假设每个时钟能够与固定频率的振荡器 近似。就像前面讨论的一样,两个时钟C1(t),C2(t)假设线性相关: C1(t)=a12· C2(t)+b12(2) 其中:是a12两个时钟的相对漂移,b12是两个时钟的相对偏移。

4.LTS算法 LTS(Lightweight Tree-Based Synchronization)算法是Greunen和Rabaey 提出

的[10],与其他算法最大的区别是该算法的目的并不是提高精确度,而 是减小时间同步的复杂度。该算法在具体应用所需要的时间同步精确度范围 内,以最小的复杂度来满足需要的精确度。WSN的最大时间精确度相对较低 (在几分之一秒内),所以能够利用这种相对简单的时间同步算法。 Greunen和Rabaey提出了两种用于多跳网络同步的LTS算法,它们都是基 于文献[7]的pair-wise同步方案,两个算法都需要节点与一些参考节点同步,例 如WSN中的网关节点。 第一种算法是集中算法,首先要构造树状图,然后沿着树的n-1子叶边缘进行 成对同步。希望通过构造树状图使同步精度最大化,因此,最小深度的树是最 优的。 第二种多跳LTS算法通过分布式方法实现全网范围内的同步。每个节点决 定自己同步的时间,算法中没有利用树结构。

5.2.2基于前同步思想的同步算法 前同步是不论系统是否有触发条件,都要进行时间同步,也就是说系统会定 期的自动进行时间同步的校正。常见方法如下 1.延时测量时间同步协议(DMTS)

2.泛洪时间同步协议FTSP(Flooding Time Synchronization Protocol)
3.HRTS(Hierarchy Referencing Time Synchronization Protocl) 和BTS 4.其它同步思想

1.延时测量时间同步协议(DMTS) 文献[11]提到的延时测量时间同步(Delay Measurement Time Synchronization),它是在多跳网络中采用了层次型的分级结构来实现全网范 围内的时间同步,它避免了冗余分组的传输,只接收级别比自己低的节点广播 的分组。该协议能更好的支持与外部时间源及多个网络的同步。该协议是在 RBS的基础上做了改进,它是一种基于广播时间的时间同步机制,和RBS相比 它为了避免往返传输时间估计,减少消息交换量,同时兼顾可扩展性,能量消耗 和估算成本,它是选择一个节点作为主节点,广播含有节点时间的分组,接收节 点对分组的传输延迟进行测量,并且将自己的本地时间设置为接收到的分组中 包含的时间加上分组传输时延。这样所有广播范围内的节点都可以与主节点 进行同步。 但是由于DMTS在能量开销和同步精度之中做了折中,所以它主要应用在对 精度要求不是很高的无线传感网中。

2.泛洪时间同步协议FTSP(Flooding Time Synchronization Protocol) 2004年Maroti M等人提出Flooding Time Synchronization Protocol (FTSP) [11,12]的目标是实现整个网络的时间同步并将误差控制在微秒级,它考虑了 根节点的选择,根节点和子节点的失效造成的拓扑变化以及冗余信息的处理 等方面的问题,同时它采用了线性回归算法使同步精度提高,适用于军事场 合。 DMTS和FTSP都是RBS的演进,它们完全不考虑发送时间和访问时间, 绝对的路径变短,使得同步误差大大的减少。

只是DMTS算法是传输的消息 条数减少,从而使算法的开销最小,可是精度不如RBS。

3.HRTS(Hierarchy Referencing Time Synchronization Protocl) 和BTS 2004年Dai.H提出的HRTS[13]是在TPSN模型和RBS模型基础上演变出来 的一种时间同步算法,当一个节点发时间请求的时候,所有的相关节点都收到 请求,并记录接到请求的本地时间。例如O发M1进行时间同步的请求,K、P 节点都接到请求,他们记录收到请求时的本地时间,其中K节点和O进行信息 交互,计算出K、O节点间的时间偏差,O节点再次发送M2(其中包含时间偏 差和K接到同步请求时的本地时间),此时K、P根据接收到的时间信息,进行 时间信息的同步 。

BTS[13]思想和HRTS类似,但做了如下改进: ① 用捎带技术,将M2的信息附带在下一次的M1中进行发送,使同步报文个 数降为HRTS的2/3, ② 各节点不直接对节点的本地时间进行修改,保证了节点本地时间的连贯 性,③用最小均方线性回归算法对误差进行分析。其时间同步的原理如图7-6 所示。

4.其它同步思想 2003年M. Sichitiu 和C. Veerarittiphan 提出了tiny sync and M ini sync[14]同 步算法,它们利用线性拟合得出节点间时钟的相对漂移和相对偏移的范围。采用 夹逼的方法估计频偏和相偏,这是放宽了时间精度的范围为前提的。 同样在2003年J.Greunen和J.Rabaey 提出了降低同步开销的轻量级时间同步 机制LTS[15] (Lightweight Time Synchronization),该协议侧重降低同步开销, 并且具有鲁棒性和自配置的特点,同时它包含了从上往下的集中式和从下往上 的分布式两类多跳时间同步。 2007年杨博、廖明宏提出了SCPS[16] (statistic clock protocol for sensor networks) ,它周期对节点时钟采样,计算本地时钟和参考时钟的差值,进而修正本 地时钟,在网络初始化过程时以及工作了一段时间后,协议要测量传输时的时延值, 作为同步计算中的修正值,然后进行簇内时间同步,头节点收到同步请求后,连续 发送多个同步消息,簇内节点收到后根据传输时延值计算出和头节点的时钟间的 偏差值,修正本地时钟。由于网络节点设置不同的级别,每个节点只和其上级节点 保持同步从而达成了该范围内的时钟同步。通过实验得到采用该方法能有效的 降低能量的消耗和带宽消耗,它适用于由大量节点组成的传感网络中。

5.2.3 基于后同步思想的时间同步协议[1] 文献[17]曾首次提出用后同步思想进行时间的同步,该思想是在通常情况下 节点的时间不进行同步,只有检测到一个感兴趣的事件发生后,节点才进行时 间同步。 单脉冲同步机制[18。该同步思想是加入第三方信标节点,在检测到感兴趣 的事件后,信标节点立即广播一个同步脉冲,接收到这个脉

冲的节点把这个同 步脉冲作为一个即时的时间参考并且根据这个同步脉冲打上这个事件的时间 戳。该同步思想在节点比较少的情况下工作性能很好。结合“后同步”思想 的RBS时间同步机制。它能在较大的范围内提供时间同步。但是RBS的评估 算法需要多个同步脉冲来获得节点的时钟偏差,这需要一定的时间,所以可能 引入新的误差。

文献[18]介绍的基于路由结合的时间同步协议RITS[18] (Routing Integrated Time Synchronization) ,这是一种被动的时间同步协议。它并不执 行明确的时间同步。在某个事件发生的时候,它以汇聚节点的本地时间为基准, 获得多个观测到该事件的节点的观测时间,当包含时间戳的数据包从一个节点 传送到另一个节点的时候,它所带的时间戳相应的转换为对应节点的本地时间 戳。通过实验得到,带有时间偏差补偿的误差率比不带时钟偏差补偿的要小的 多。 2003年ElsonJ. E提出的Post facto[12,15]为事件后发的同步方法,当激励信 号到达后,各节点记录激励到达时的本地时间,一个节点广播一个同步脉冲给 本地网络的所有节点,各节点将本地脉冲作为瞬时的相关时间标记来标准化自 己的时间,在多事件同时发生的时候会引起系统时钟的不稳定。 基于后同步思想的时间同步协议因为在事件发生之后才进行节点间的时间 同步。所以在能耗方面比前摄时间同步协议做的好。

5.3 算法比较分析 对于无线传感网络而言影响时间同步精度的重要原因是时延的不确定性。 Kopetz和Schwabl曾把等待时间分解为6个组成部分[11],分别是:发送时延, 访问时延,传送时延,传播时延,接受时延,接收时延。下表将常见的几种 时间同步方法进行了对比,比较分析了各种不同算法的优缺点和适用场合。
同步方法 优点 缺点 适用环境 不仅适用于无线网络也适用于有 线网络,课广泛应用于商用硬件 设备和已有的无线传感网软件

RBS

1.不考虑发送时延和访问时延,甚 时间算法复杂度高,能量消 至排除了接受时间的不确定性。 耗大补适合有限能量供给的 2.时钟的调整不会影响时钟偏差的 应用场合 计算。 1.不考虑发送时延和访问时延,甚 至排除了接受时间的不确定性。 1.能量开销大 2.精度可以几百微秒是RBS的两倍 2.不适合网络的动态变化。 并支持外部时钟源同步 DMTS的同步精度低于 TPSN.FTPS,RBS.

TPSN

对时间精度要求较高的稳定网络

DMTS

算法灵活比RBS和TPSN能量消耗少。

对时间精度要求不高的无线传感 器网络

FTPS

它的同步精度虽然比DMTS算 适合拓扑机构和冗余处理,用线性 法高但是位于TPSN与RBS之 回归算法使同步精度高。 间。 采用了时间组合算法,减少了节点 间的同

步误差,时间同步精度高 有效降低了能耗和带宽消耗 通信耗能和节点数成正比 实验得到精度以0.9965的概率 小于80us(精度不是很高)

适用于军事场合

BTS

不适合大规模的网络

SCPS

由大量节点组成的传感器网络

无线传感器网络在不同的应用环境中,表现出来不同的特点,对时间同步 的要求也就存在差异,所以上述算法针对具体的应用环境也表现出不同的特 点。在分析无线传感器网络时间同步算法时,一般在网络结构、同步方式、 误差、能耗和有效范围等方面进行比较。

表中☆代表了算法在某个方面的性能等级,☆的数量越多代表算法在这 个方面的性能越优良。文献[12]中给出了RBS算法和TPSN算法应用到MICA 平台的同步误差等参数,比较了两种算法的不同。RBS算法由于采用了与其 他算法不同的同步方式,精确度比较好,但是由于节点的射频范围有限,使 得算法的应用范围受限;TPSN由于采用了分级的方式和传统的同步方式, 使得同步效果比较好,但是增加了能耗和复杂度;LTS算法是针对精确度要 求不高的应用环境而研究的一种简单的算法;Mini-Sync算法的复杂度相对较 低,但是对于计算和存储的要求较高。总之,每种算法的应用需要考虑无线 传感器网络的具体应用环境进行选择。

目前,无线传感器网络时间同步算法的研究已经取得了很大进展,今后的 研究热点将集中在节能和超大规模、可变拓扑中的时间同步以及时间同步的 安全性方面。这将对算法的容错性、有效范围和可扩展性提出更高的要求。 下表对几种算法就分级结构、同步机制、误差、精度、能耗和复杂度等方面 作了对比分析
算法 分级结构 同步机制 误差 精度 能耗 复杂度 RBS 否 R-R 29.1 一般 一般 较高 TPSN 是 成对 16.9 高 较高 一般 Mini-sync 是 成对 / 较低 一般 较低 LTS 是 成对 / 较低 一般 一般 DMTS 是 S-R 32 一般 较低 较低 FTSP 是 S-R 21.8 较高 较低 较低

5.4 小结 以上介绍的各种协议算法就在这几种基本同步方法的基础上演进出来的, 他们的设计思想有不同的侧重点,有的首先考虑节能,有的首先关注精度。 因此,选择WSN的时间同步算法要根据具体的应用场合,在对精度要求不高 的时候,我们应尽量减少时间同步的频率,同时可降低参与同步的节点数目 以降低节点通信的能耗;在对精度要求比较高的场合,可以增加广播同步分 组的次数,引入线性回归算法等数据处理方法。总之,对特定的应用场合, 我们需要研究开发特定的时间同步机制。

目前对WSN时间同步算法的研究已取得了很大进展,但是现有的WSN时 间同步算法还不够完善,以下几个方面值得进一步研究。

大规模WSN时间同步一一随着硬件技术的发展传感器节点的成本将会逐渐 降低,使今后进行大规模传感器节点的部署成为可能,现有的WSN时间同步 算法都是对中小规模的WSN时间同步进行仿真和实验的,因此WSN时间同 步算法在大规模WSN中的应用是今后研究的方向之一。 健壮性和容错性一一目前提出的WSN时间同步算法基本上都是在实验室环 境或在状况较好的室外环境下进行的实验测试,实际的WSN应用环境经常是 人们难以接近的恶劣环境并且存在各种难以预测的干扰因素,因此WSN时间 同步算法在真实应用环境下的健壮性和容错性也是一个不能忽视的研究方向。

可变拓扑下时间同步一一目前的同步算法主要针对网络拓扑结构固定的 WSN,即节点处于静止状态下的时间同步,下一代的传感器网络可能包括移 动的传感器节点,WSN的拓扑结构也会不断发生变化,如何处理可变拓扑下 的时间同步也需要我们进一步研究。 性能评价模型一一现有WSN时间同步算法之间的性能对比都是通过相同运 行环境下的实验进行,因此建立一个标准的性能评价模型也是一个值得研究 的方向。 总之,WSN时间同步是一个比较新的研究领域,其中还有许多问题有待解 决,值得广大研究人员关注并进一步研究。


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com