TPSN时间同步算法研究PPT课件.pptx

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