无线传感器网络_李善寿_第7章(时钟同步2学时).ppt

第七章WSN的时钟同步技术 主讲 李善寿 安徽建筑大学电信学院 第七章 WSN的时钟同步技术 时钟同步的基本概念 典型时间同步协议 WSN的新型同步机制 简述WSN的定义 分析现有无线网络与WSN的不同点简述拓扑控制与路由的关系 叙述DRNG算法实现的基本过程简述DD协议实现的基本过程 回答DD协议存在的不足 简述MAC协议中的CSMA CA机制和随机退避时间技术简述ZIGBEE网络中三种节点类型 分析ZIGBEE组网过程 简述质心定位算法 RBS同步协议的基本原理 WSN时间同步技术背景 集中式系统与分布式系统集中式 事件间有着明确的时间先后关系 不存在同步问题分布式 同步是必需的 只是对同步的要求程度不同无线传感器网络时间同步典型的分布式系统是无线传感器网络应用的基础需要解决的问题同步精度功耗可扩展性 WSN时间同步机制的主要性能参数 最大误差 一组传感器节点之间的最大时间差或相对外部标准时间的最大差值 同步期限 节点保持时间同步的时间长度 同步范围 节点保持时间同步的区域范围 可用性 范围覆盖的完整性 效率 达到同步精度所经历的时间以及消耗的能量 代价和体积 需要考虑节点的价格和体积 时间同步技术的分类 排序 相对同步与绝对同步递进关系各自具有典型的协议代表外同步与内同步参考源不同局部同步与全网同步同步对象的范围不同 时间同步技术的应用场合 多传感器数据压缩与融合低功耗MAC协议 路由协议测距 定位 位置相关报务 LBS 分布式系统的传统要求协作传输 处理的要求 时钟模型 硬件时钟模型软件时钟模型软件虚拟时钟一般是个分段连续 严格单调的函数 相关术语 信标节点和未知节点邻居节点跳数 跳段距离基础设施到达时间 到达时间差接收信号强度指示到达角度视线关系 非视线关系 传统与挑战 传统同步方法NTP 网络时间协议GPS 全球定位系统传感器网络的挑战 NTP NetworkTimeProtocol 体系结构 网络 NTP NetworkTimeProtocol 体系结构 单机 NTP NetworkTimeProtocol NTP不适合于WSN体积 计算能力和存储空间存在限制传输方式不同 无线而非有线目标不同 局部最优而非全局最优 GPS GlobalPositionSystem 从根本上解决了人类在地球上的导航与定位问题 每颗卫星上配备有高精度的铷 铯原子钟 并不断发射其时间信息地面接收装置同时接收4颗卫星的时间信息 采用伪距测量定位方法可计算出时间和位置信息缺点 室内 功耗 安全性 分布式 传感器网络的挑战 室内 矿井 森林 有遮挡低功耗 低成本和小体积传输延迟的不确定性可扩展性 移动性健壮性 安全性网络规模大 多点协作 挑战 传输延迟的不确定性 发送时间 发送节点构造和发送时间同步消息所用时间 e g 系统调用时间 内核调度时间 消息从主机发送到网络接口时间 访问时间 发送节点等待访问网络传输信道的时间 传播延迟 发送节点传输到接收节点所经历的时间 接收时间 从接收节点的网络接口接收到消息到通知主机消息达到事件所经历的时间间隔 传输延迟的进一步细化 在Mica2上 挑战 低功耗 低成本和小体积 软硬件都要受到该限制存储与计算能力均比较小加剧了电能供应的紧张 电池体积 网络规模大 密度高通信距离近 分布式 协作 挑战 可扩展性 Scalability 在大规模网络中尤为重要是大规模无线传感器网络软硬件设计中非常重要的问题满足不同的网络类型 网络规模满足不同的应用需求 挑战 健壮性 外部环境复杂 搞毁能力需要应对安全性挑战无线传感器网络拓扑动态性较强网络规模变化 需求变化 典型时间同步协议 典型时间同步协议 NTP NetworkTimeProtocol DMTS DelayMeasurementTimeSynchronization RBS ReferenceBroadcastSynchronization TPSN Timing syncProtocolforSensorNetworks HRTS HierarchyReferencingTimeSynchronizationProtocol FTSP FloodingTimeSynchronizationProtocol GCS GlobalClockSynchronization 发送者 接收者 DMTS 最简单直观单报文同步 同步精度低t0 nt t2 t1 广播方式 同步能耗低 DMTS DelayMeasurementTimeSynchronization 基于同步消息在传输路径上所有延迟的估计 实现节点间的时间同步 接收者 接收者 RBS ReferenceBroadcastSynchronization 通过广播同步指示分组实现接收点间的相对时间同步RF信号的传播时间差值非常小可以消除接收节点的接收协议处理 上下文切换 网络接口向主机传送影响RBS机制性能的因素 时钟偏差 接收点飞确定性因素以及接收点的个数 RBS ReferenceBroadcastSynchronization 接收者 接收者同步的基本依据 接收者时间相移均值为0 单跳RBS 用最小二乘法估计clockskew 时钟漂移 提高同步精度 多跳RBS 时间路由技术 基于最短路径查找 TPSN Timing syncProtocolforSensorNetworks 否定 DMTS RBS否定之否定 RBS TPSNTPSN 双报文交换的发送者 接收者同步 TPSN Timing syncProtocolforSensorNetworks 对同步误差的分析很重要 是一种基本的分析方法理论分析和实验证明 TPSN同步误差是RBS的一半结合对clockskew的估计 可以提高TPSN的精度 TPSN Timing syncProtocolforSensorNetworks 多跳TPSN 全网周期性同步 层发现 把网络组织成最短生成树逐层在相邻两层节点间同步网络内两个节点的同步 后同步 查找两个节点间的路径在路径的相邻两个节点间进行TPSN同步 HRTS HierarchyReferencingTimeSynchronizationProtocol TPSN基于双向报文交换 因此同步精度高TPSN本质上是对同步 因此全网同步的同步能耗高由DMTS发现 广播能降低全网同步能耗结合广播和节点间的双向报文交换同步 HRTS协议 HRTS HierarchyReferencingTimeSynchronizationProtocol 根节点和应答者节点本质上是采用TPSN同步根节点和非应答者节点本质上是双向报文交换同步 但非TPSN 应答者节点和非应答者节点本质上是接收者 接收者同步 HRTS HierarchyReferencingTimeSynchronizationProtocol FTSP FloodingTimeSynchronizationProtocol 同步精度高工程实用性强强调实现细节 MAC层时间戳技术和平台直接相关 书中给出了在Mica2平台下的实现基本同步原理发送者 接收者同步单个报文中包括多个时间戳 在报文的不同位置 根据单个报文中的多个时间戳 可对中断等待时间进行补偿对clockskew的补偿仍采用最小二乘法 FTSP FloodingTimeSynchronizationProtocol 多跳FTSP 洪泛方式广播时间基准节点的时间协议健壮实际做了工程化的实现 GCS GlobalClockSynchronization 节点遍历模式聚类分层模式扩散模式 GCS 节点遍历模式 游走阶段 记录游走的出发和到达时间时间校正阶段 根据节点在游走环的位置和游走时间对节点时间进行校正理论假设 每段游走的时间花费相同 GCS 聚类分层模式 单纯的节点遍历方式导致遍历环过长 同步功耗大通过分簇协议 把网络组织成簇结构簇头节点间以节点遍历方式同步簇内节点可以节点遍历或RBS等方式进行同步 GCS 扩散模式 越简单的方法往往是越有效的同步过程 对接收到的时间进行平均操作 并对自己的时间进行扩散理论证明 当把所有节点的时间当成一张快照时 经过若干轮扩散过程 所有节点时间最终将收敛到所有节点时间的平均值上 新型同步机制 新型同步机制 基于报文交换的同步机制面临着挑战同步精度问题可扩展性问题新型同步机制萤火虫同步协作同步两个概念同时性与同步性 萤火虫同步 1935年 Science1975年 Peskin的RC模型1989年 M S模型 无延迟 1998年 Ernst 有延迟 结论2005年 真实地实现 简单 高效 可扩展性强 M S模型 研究由初始不同步状态如何达到同步状态个体性质相同 因此一旦达到同步则永远同步萤火虫之间的交互被建模成电量耦合耦合延迟规定为0最终结论为 系统的同步收敛性取决于个体在自由状态下的动力学特性同步的实质 不同步产生了耦合 耦合改变了状态量 而状态量又改变了相位量 相位差通过同步过程不断缩小 最终达到完全相同 即同步状态 M S模型 证明了全耦合系统的同步收敛性没有证明多跳网络的同步收敛性 Ernst的研究 M S模型没有考虑耦合延迟 Ernst研究了耦合延迟固定时的情况M S模型只研究了正耦合的情况 Ernst还研究了负耦合的情况 Ernst 正耦合 2个节点 存在两种情况不可能达到完全同步其实是M S模型的扩展 Ernst 负耦合 2个节点 存在三种情况和Peskin的结论一致结论 考虑固定耦合延迟的情况下 只有负耦合才可能取得同步收敛 负耦合下的全连接网络 仿真研究方法和两个节点下的情况不同出现分簇现象 其他一些研究与结论 理论上没有突破单纯的仿真方法意义有限萤火虫同步技术对耦合延迟 耦合强度 耦合性质 初始相位 网络拓扑等因素很敏感 虽然在例如两个振荡器的同步收敛性研究上取得了一定的进展 但无论是理论研究还是仿真研究 研究者在某些结论上还不能达成一致的认识 但可以认同的一点是 在实际系统中 基于萤火虫同步策略的同步技术会取得在一定误差范围内的同步 实践 RFA算法RFA ReachbackFireflyAlgorithm 在24个Micaz节点组成的网络上实现同步误差是存在的 和同步操作的频率直接相关核心思想 将某轮同步周期内接收到的同步报文的影响推后到下一轮同步周期的起始时刻 总结 萤火虫同步 同步可直接在物理层而不需要以报文的方式实现 直接用硬件实现 使得同步精度不会受到MAC延迟 协议处理与软件实现等的影响 由于对任何同步信号的处理方式均相同 与同步信号的来源无关 因此可扩展性以及适应网络动态变化的能力很强 机制非常简单 不需要对其它节点的时间信息进行存储 萤火虫同步算法的一个限制是要求每个节点具有相似性 但这种机制在非相似节点所组成的网络下能否起到同步的作用 目前还不清楚 此外