TPSN时间同步算法研究.ppt
,TPSN时间同步算法研究,CONTENTS,目 录,WSN时间同步概述,TPSN时间同步算法,一种基于优化拓扑的时间同步算法N-TPSN,01,WSN时间同步概述,4,WSN时间同步概述,概念：各个节点定期或不定期与其他节点交换本地时钟信息，并在协议或算法控制下调整本地时钟，实现全局时间一致的过程。,WSN为何需要时间同步：不同节点晶体振荡不同，存在累计误差；受能量、存储、带宽限制；分布式系统，要求节点必须实现同步，不同系统要求程度不同。,时间同步要解决的问题：保证同步的精度；尽量小的功耗；保证网络的可扩展性。,WSN时间同步概述,时间同步的误差来源,晶体振荡不同节点的晶体振荡器间存在误差，并且也会受到环境影响，这一误差会随时间累积。,成本、资源由于WSN资源受限，通信信道质量不佳时；节点密度大时，易造成延迟和出错，导致时间误差。,同步协议需在性能和开销间取得平衡，即用较小的通信代价取得较好的同步效果。,协议执行信道出错，导致部分节点不能被同步，影响网络的整体时间同步情况。,WSN时间同步概述,时间同步算法的分类（1）,（1）基于接收者接收者（Receiver-Receiver）的时间同步,基于接收者接收者的时间同步算法，主要利用了无线信道的广播属性。主要原理是引入一个节点作为辅助节点，由该节点广播一个参考分组，在广播域内的一组 接收节点接收到这个参考分组，通过比较各自接收到消息的的本地时间，实现它们之间的 时间同步。由于其他节点只需要监听信息而不需要同步到参考节点，该类型算法的优点在于可以避免 发送节点时延的影响，但缺点在于信息交换次数较多，能耗较大。该种类型的代表性算法是 RBS 算法。,WSN时间同步概述,时间同步算法的分类（2）,（2）基于发送者接收者（Sender-Receiver）的双向时间同步,基于发送者接收者的双向时间同步算法，类似于传统Internet 中的 NTP协议，即基 于客户机服务器架构。待同步节点发送时间同步请包，基准节点接收到这一同步请求后反馈自身当前时间，待 同步节点接收到反馈的信息后计算时间偏差并予以调整，完成时间同步。该类型算法优点在于同步的高精度，而缺点就是节点分层的维护和多次两点间信息交换，大大增加了能耗。该种类型的代表性算法是 TPSN 算法、LTS 算法。,WSN时间同步概述,时间同步算法的分类（3）,（3）基于发送者接收者（Sender-Receiver）的单向时间同步,基于发送者接收者的单向时间同步算法，相对于双向的时间同步算法，只需要基准 节点向待同步节点进行单向数据包传递。主要原理是基准节点广播包含自己节点时间信息的时间同步数据包，待同步节点在接受到 这一数据包后，根据时间戳信息，开始计算数据通信过程中数据包延迟的各个组成部分，得到时间差值的待同步节点将对这些时延进行补偿，并完成了自己向参考节点的同步。该类型算法优点在于算法复杂度低、能耗小，缺点在于同步精度较低。该种类型的代表性算法是 DMTS 算法和 FTSP 算法。,02,TPSN时间同步算法,TPSN时间同步算法,主要思想,层次发现,时间同步,采用层次型网络结构，分为层次发现和时间同步两个阶段。,实现所有树节点的时间同步，第 i 层的节点与第(i-1)层的一个节点同步，最终所有节点都能在时间上与根节点同步，从而实现整个网络的时间同步。,每一个节点赋予一个层次，第 i 层的节点至少要能够与第(i-1)层的节点通信；,主要思想,TPSN时间同步算法,层次发现阶段,该阶段主要工作是把整个网络进行分层。,时钟源节点作为根节点，广播级别发现数据包来启动分层过程。数据包中包含着节点自身的 ID 和所属层次。,每个初次接收到级别发现数据包的节点需要将层次加 1 并继续广播，直到完成整个网络的分层工作。,当根节点的邻居收到这一数据包，便把自己的层次置为 1，并向下继续广播新的级别发现数据包。,TPSN时间同步算法,时间同步阶段,d,d,A：i 层节点,B：i+1 层节点,TPSN时间同步算法,时间同步阶段,B 节点根据与 A 节点的时间偏差同步到 A 节点的时间,结论：,缺点,优点,在MAC层消息开始发送到无线信道时才添加时间信标，消除了访问时间带来的误差；利用双向交换信息计算消息的平均时延，精度相对较高。,节点失效（尤其是靠近根节点的节点失效）会导致同步错误，并在网络扩散；新节点加入时，需初始化层次发现步骤，扩展性差；不适合移动节点或多跳同步等情况。,TPSN时间同步算法,优、缺点,03,一种基于优化拓扑的时间同步算法N-TPSN,N-TPSN时间同步算法,问题描述,无线传感器网络各项技术具有一项共同的性能指标，即能量消耗。传感器节点除了待机耗能外，几乎所有能量都用来通过无线信道发送和接收数据包。,问题：,研究方向：,对于无线传感器网络时间同步算法，也希望降低算法能量损耗,降低在时间同步过程中的数据包交换次数。,N-TPSN时间同步算法,算法思想（1）,本次算法设计的应用背景是大规模、多跳、弱动态的无线传感器网络，其单跳拓扑图如图所示，其中，实线表示 1 跳节点向参考节点发送的时间同步请求，虚线表示参考节点回馈的数据包。,根据 TPSN 算法流程，在网络分层结束同步过程开始后，每个 1 跳节点需要向参考节点发送同步请求数据包，等待参考节点回馈后完成时间差值计算，同步到参考节点；,随着节点数量的增加，节点密度增大，单跳范围内节点数量变大到 n，在 TPSN 协议中，此单跳范围内的数据包交换次数为 2n。,由于节点密度增大后，某个 1 跳节点（假设为 A 节点）和参考节点的通信范围内很可能覆盖其他的 1 跳节点，由于无线信道广播特性，A 节点和参考节点的数据包交换过程可以被其他被覆盖的 1 跳节点监听到。,利用这些信息，这些被覆盖的 1 跳节点便能发现自己与参考节点的时间差值进而同步到参考节点。以此思路为基础进行单跳层次内的算法优化设计。,N-TPSN时间同步算法,算法思想（2）,上图示意了 2 跳内的 TPSN 算法，节点的编号 0-1 表示该节点是第 0 层的 1 号节点，1-9表示该节点是第 1 层的 9 号节点，依此类推。,N-TPSN时间同步算法,层次内开销优化设计（1）,TPSN 算法的数据包交换流程如图 3-4 所示，O 为上层节点，A、B、C 均为下层节点。图中节点按 A、B、C 顺序依次与 O 节点进行时间同步，实现表示下层节点发送时间同步请求，虚线表示上层节点回馈。,N-TPSN算法数据包交换流程如图3-5所示，B、C 节点均在 A 和 O 节点的单跳范围内，由于无线信道具有广播特性，A 与 O 节点间的数据包交换可以被 B、C 两个节点监听到。,以单跳内四个节点为例，,N-TPSN时间同步算法,层次内开销优化设计（2）,1.同步请求,2.上层回馈,3.偏差计算,4.时间修正,上图可以完成1跳范围内某节点与上层节点通信范围覆盖的所有节点的时间同步工作，这些被覆盖的节点只需要监听无线信道并对接收到的数据包进行分析计算即可，大大降低了 TPSN的算法开销。,N-TPSN时间同步算法,层次间开销优化设计（1）,网络拓扑简化，采用选择最佳邻居的拓扑优化思路，该算法被命名为 best-Neighbor TPSN，即 N-TPSN。,N-TPSN时间同步算法,层次间开销优化设计（2）,检测 1 跳邻居,计算 2 跳邻居,计算最佳邻居,保存选中名单,1 号节点的 1 跳节点中只有 2、4、6、8 号节点需要向1 号节点发送时间同步请求数据包，3、5、7、9 号节点只需要进行无线信道的监听。在 1 跳范围内的节点被同步到 1 号节点之后，2 跳节点只需要向之前进行了同步数据交换的节点发送请求，即 10、11 节点只需要向 2 号节点发送时间同步请求数据包。相对于 TPSN 协议，一方面 3、5、7、9 四个节点节省了 1 跳范围内时间同步时主动发起的一次数据请求，另一方面节省了下层节点时间同步时与他们的一次完整的数据交换。,THANK YOU,
