无线传感器组网-时间同步技术要点.ppt

第七章 时间同步技术 内容提要 基本概念传统与挑战典型时间同步协议新型同步机制总结 内容提要 基本概念传统与挑战典型时间同步协议新型同步机制总结 基本概念 时间同步的定义WSN时间同步技术背景时间同步技术的分类时间同步技术的应用场合关键问题 时钟模型 时间同步技术的定义 无线传感器网络中每个节点都有自己的内部时钟 即本地时间 由于不同节点的晶体振荡频率存在偏差 再加上温度的差异 电磁波干扰等 即使在某个时间点所有节点时钟一致 一段时间后他们的时间也会再次出现偏差 无线传感器网络的时间同步是指各个独立的节点通过不断与其他节点交换本地时钟信息 最终达到并且保持全局时间协调一致的过程 即以本地通信确保全局同步 思考 为什么需要时间同步 时间同步能解决什么问题 根据CSMA CA协议 当节点要传输一个分组时 它首先侦听信道状态 如果信道空闲 而且经过一个帧间间隔时间DIFS后 信道仍然空闲 则站点立即开始发送信息 如果信道忙 则站点始终侦听信道 直到信道的空闲时间超过DIFS 当信道最终空闲下来的时候 节点进一步使用二进制退避算法 进入退避状态来避免发生碰撞 CSMA CA协议需要严格的时间同步 网络节点在进入退避状态时 启动一个退避计时器 当计时达到退避时间后结束退避状态 在退避状态下 只有当检测到信道空闲时才进行计时 如果信道忙 退避计时器中止计时 直到检测到信道空闲时间大于DIFS后才继续计时 当多个节点推迟且进入随机退避时 利用随机函数选择最小退避时间的节点作为竞争优胜者 侦听 侦听 睡眠 睡眠 节点协同进行周期性侦听和睡眠的状态切换 确保节点能同步进行侦听和睡眠调度 调度周期 周期性侦听和睡眠的时间之和为一个调度周期 S MAC协议需要严格的时间同步 S MAC协议 SensorMAC 是在802 1lMAC协议的基础上 针对传感器网络的节省能量需求而提出的 流量自适应侦听机制的基本思想是在一次通信过程中 通信节点的邻居在通信结束后不立即进入睡眠状态 而是保持侦听一段时间 如果节点在这段时间内接收到RTS 则可以立刻接收数据 无须等到下一次调度侦听周期 从而减少了数据分组的传输延迟 如果在这段时间内没有接收到RTS 则转入睡眠状态直到下一次调度侦听周期 流量自适应侦听机制需要时间同步 RTS A 数据1 RTS 数据2 B CTS ACK 侦听 侦听 CTS ACK RTS A 数据1 RTS 数据2 侦听 睡眠 WSN时间同步技术背景 集中式系统与分布式系统集中式 在事件间有着明确的时间先后关系时 不存在同步问题 时间关系不明确时仍存在 分布式 同步是必需的 只是对同步的要求程度不同需要解决的问题同步精度功耗可扩展性 WSN时间同步机制的主要性能参数 最大误差 一组传感器节点之间的最大时间差或相对外部标准时间的最大差值 同步期限 节点保持时间同步的时间长度 同步范围 节点保持时间同步的区域范围 可用性 范围覆盖的完整性 效率 达到同步精度所经历的时间以及消耗的能量 代价和体积 需要考虑节点的价格和体积 时间同步技术的分类 根据同步的级别 可以分为排序 相对同步与绝对同步 其间为递进关系 排序只能区分事件发生的先后相对同步 维持本地时钟的运行 定期获取其他节点的时钟偏移和飘移 经过换算达到同步的目的 如RBS协议绝对同步 本地时钟和参考时钟保持一致 修改本地时钟 如TPSN协议根据参考源不同 可以分为外同步 与外部某时间同步 如GPS 与内同步 网络内部某个节点的时钟 根据同步对象的范围不同 可以分为局部同步与全网同步 时间同步技术的应用场合 多传感器数据压缩与融合邻近传感节点对相同事件的感知数据需要融合 基于时间戳判断是否同一事件 需要时钟同步低功耗MAC协议 路由协议不发送数据时 节点处于休眠状态 网络节点的同步休眠需要时钟同步测距 定位距离测量和定位是基于无线电信号的传输时间 时间同步越准确 距离测量也越准确分布式系统的传统要求分布式系统的数据库查询 状态等一致性的要求协作传输 处理的要求协作传输是基于电磁波的能量累加效应 多个节点以相同的调制解调方式同时发送信号 使得远处的汇集节点能接收到信号 时间同步技术的重要性 时间同步技术对无线传感器网络的节点定位 无线信道时分复用 低功耗睡眠 路由协议 数据融合 传感事件排序等应用及服务 都会产生直接或间接地重要影响 时间同步机制几乎渗透至每一个与数据相关的环节 其实现的好坏直接决定了以数据为中心的无线传感器网络整体系统性能的优劣 关键问题 时钟模型 硬件时钟模型软件时钟模型 硬件时钟模型 基本名词时间 晶振 时钟 RTC 时钟偏移 clockoffset 是指两个时钟瞬时读数的差 晶振计时的时刻与实际时刻的差值 反映计时的准确性时钟率偏移 ClockSkew 是指两个时钟的频率差 它可以看作是Clockoffset的一阶导数 时间漂移 ClockDrift 是指时钟频率的变化 反映晶振的稳定性 实际晶振的频率有可能随着外界环境温度 湿度的变化而有所改变 ClockDrift可以看作是Clockoffset的二阶导数 速率恒定模型该模型认为频率保持恒定不变 最常用 但不适应环境变化剧烈的场合飘移有界模型常用于确定同步误差上下界 频率稳定度常用ppm 百万分之一 飘移变化有界模型时钟的漂移变化率是有限的 软件时钟模型 以软件虚拟时钟一般是个分段连续 严格单调的函数 相关术语 信标节点和未知节点邻居节点跳数 跳段距离基础设施到达时间 到达时间差接收信号强度指示到达角度视线关系 非视线关系 内容提要 基本概念传统方法与面临的挑战典型时间同步协议新型同步机制总结 传统同步 NTP与GPS NTP 网络时间协议GPS 全球定位系统 NTP NetworkTimeProtocol 体系结构 NTP提供准确时间 首先要有准确的时间来源 这一时间应该是国际标准时间UTC NTP获得UTC的时间来源可以是原子钟 天文台 卫星 也可以从Internet上获取 这样就有了准确而可靠的时间源 时间按NTP服务器的等级传播 按照离外部UTC源的远近将所有服务器归入不同的Stratum 层 中 Stratum 1在顶层 有外部UTC接入 而Stratum 2则从Stratum 1获取时间 Stratum 3从Stratum 2获取时间 以此类推 但Stratum层的总数限制在15以内 所有这些服务器在逻辑上形成阶梯式的架构相互连接 而Stratum 1的时间服务器是整个系统的基础 NTP NetworkTimeProtocol 体系结构 单机 NTP的适用性 NTP不适合于WSN 体积 计算能力和存储空间存在限制传输方式不同 无线而非有线目标不同 WSN仅需局部最而非全局最优 GPS GlobalPositionSystem 从根本上解决了人类在地球上的导航与定位问题 每颗卫星上配备有高精度的铷 铯原子钟 并不断发射其时间信息地面接收装置同时接收4颗卫星的时间信息 采用伪距测量定位方法可计算出时间和位置信息缺点 室内 功耗 安全性 可靠性 时间同步协议应用于无线传感器网络面临的挑战 室内 矿井 森林 有遮挡网络规模大 多点协作传输延迟的不确定性低功耗 低成本和小体积可扩展性 移动性健壮性 安全性 传输延迟的不确定性 发送时间 发送节点构造和发送时间同步消息所用时间 e g 系统调用时间 内核调度时间 消息从主机发送到网络接口时间 访问时间 发送节点等待访问网络传输信道的时间 传输延迟 发送节点传输到接收节点所经历的时间 传播时间 Transmissiontime 发送节点发送数据所经历的时间接收时间 从接收节点的网络接口接收到消息到消息接收结束收到时间 Receivetime 通知主机消息达到事件所经历的时间间隔 传输延迟的进一步细化 低功耗 低成本和小体积 软硬件都要受到该限制存储与计算能力均比较小电能供应的紧张 电池体积有限 网络规模大 密度高通信距离近 分布式 协作 可扩展性 Scalability 在大规模网络中尤为重要满足不同的网络类型 网络规模满足不同的应用需求 健壮性 外部环境复杂 抗干扰能力要强需要应对安全性挑战无线传感器网络拓扑动态性较强网络规模变化 需求变化 内容提要 基本概念传统与挑战典型时间同步协议新型同步机制总结 典型时间同步协议 NTP NetworkTimeProtocol DMTS DelayMeasurementTimeSynchronization RBS ReferenceBroadcastSynchronization TPSN Timing syncProtocolforSensorNetworks HRTS HierarchyReferencingTimeSynchronizationProtocol FTSP FloodingTimeSynchronizationProtocol DMTS DelayMeasurementTimeSynchronization DMTS基于同步消息在传输路径上所有延迟的估计 实现节点间的时间同步在DMTS机制中 选择一个节点作为时间主节点 leader 广播同步时间 所有接收节点测量这个时间广播分组 packet 的延迟 设置它的时间为接收到分组携带的时间加上这个广播分组的传输延迟 这样所有接收到广播分组的节点都与主节点进行时间同步 时间同步的精度主要由延迟测量的精度所决定 主节点在检测到信道空闲时 给广播分组加上时间戳t0 用来去除发送端的处理延迟和MAC层的接入延迟 在发送广播分组前 主节点需要发送前导码和起始字符 以便接收节点进行接收同步 根据发送的信息位个数n和发送每比特位需要的时间t 可以估计出前导码和起始字符的发送时间位nt 接收节点在广播分组到达时刻加上时间戳t1 并在调整自己的时钟之前时刻再记录时间t2 接收端的接收处理延迟就是 t2 t1 这样 如果忽略无线信号的传播延迟 接收节点从t0时刻到调整时钟前的时间长度约为nt t2 t1 因此 接收节点为了与发送节点时钟同步 调整其时钟为t0 nt t2 t1 发送者 接收者 DMTS 简单直观单报文同步 同步精度低t0 nt t2 t1 广播方式 同步能耗低 发送者在信道空闲后或争用到信道后才插入本地时间t0 接收处理报文的时间 前导码时间nt 报文处理时间t2 t1 接收方的同步时刻为 t0 nt t2 t1 DMTS的优缺点 DMTS算法结合链路层标记时间戳和时延估计等技术 消除了发送时间和访问时间的影响 算法简单 通信开销小 DMTS单跳同步误差受同步精度和计时精度影响 多跳精度随跳数的增加而下降 由于误差的正负相加抵消了一部分 两跳的误差约为单跳误差的1 5倍 DMTS算法没有估计时钟的频率偏差 时钟保持同步的时间较短 也没有消除时钟计时对同步精度的影响 因而其精度不高 不适用于定位等要求高精度同步的应用 RBS ReferenceBroadcastsynchronization RBS协议不是去同步报文的收发双方 而是去同步报文的多个接收者 如下图所示 在由3个节点组成的单跳网络中 参考节点每发出一个参考报文 其广播域内的其他接收者节点都将接收到该报文 并各自记录下接收到该参考报文时的本地时刻 接收者相互交换它们记录的时刻并计算差值 该差值就是接收者之间的时钟偏移 但这有一个前提 就是接收者必须同时收到此消息 即接收者同步 假设是否成立 RBS接收节点时间相移 接收者 接收者同步的基本依据 接收者时间相移均值为0 RBS性能的影响因素及改善技术 影响RBS机制性能的主要因素包括时钟偏差 接收节点间的时间速率 接收节点非确定因素和接收节点的个数等 为提高时间同步精度 RBS机制采用了统计技术 通过发送节点发送多个消息 获得接收节点之间时间差异的平均值 RBS的优点 RBS中是通过广播同步信标分组实现接收节点之间的相对时间同步 信标分组本身并不需要携带任何时标 不依赖于信标的发送时间 由于无线信道的广播特性 信标分组相对所有接收节点而言同时发送到物理信道上 这样就除去发送时间和访问时间引入的时间同步误差 对于传播时间 RBS只关心各个接收节点之间消息传播时间的差值 对于射频信号来说 传播时间差值非常小 RBS忽略了传播时间带来的时间偏差 RBS的不足 RBS的缺点是对网络有一定的要求 它不适合点对点通信的网络 且要求网络有物理广播信道 扩展性不好 因为节点间本地时间戳通信需要额外的消息交换开销 不能很好地应用到大规模的多跳网络中 RBS有很大的交换次数 对于具有2个节点的单跳网络 需要O n2 的消息交换 如果n很大时 消息交换开销是相当大的 导致节点的计算开销也非常之大 RBS中接收节点之间进行相互同步 但并不与发送节点同步 实际上 在WSN中发送节点很可能也是一个普通的网络节点因而也需要同步 为使该节点和其它节点进行同步 需要另外一个节点作为参照广播发射节点 这导致了相当高的能耗 TPSN Timing syncProtocolforSensorNetworks 传感器网络时间同步协议 2003年11月 SaurabhGaneriwal提出了TPSN同步机制 目的是通过采用层次型网络结构来提供全网范围内节点同步 该机制分为拓扑建立阶段和同步建立阶段 考虑了传播时间和接收时间 利用双向消息交换计算消息的平均延迟 提高了精度 TPSN时间同步协议思想 Saturday April18 2020 1 TPSN是类似于NTP NetworkTimeProtocol 时间同步协议2 目的是提供传感器网络全网范围内节点间的时间同步3 节点结构中包含一个根节点 它与外界通信获取外界时间 以此作为整个网络系统的时钟源4 将节点分级后 根节点是0级 累加 每个节点同上一级的一个节点进行时间同步 最终与根节点同步5 节点对之间的同步采用发送者 接收者同步机制 每个传感器节点都有唯一的标识号ID节点间的无线通信链路是双向的 通过双向消息交换实现节点间的时间同步整个网络内所有节点按层次结构管理 由TPSN协议生成和维护 TPSN协议过程 1 协议准备阶段 Saturday April18 2020 目的 生成节点层次结构 每个节点被赋予一个级别 根节点为0级 第i级的节点至少能够与一个第 i 1 级得节点通信网络部署后 由根节点广播级别发现分组来启动层次发现阶段 级别发现分组包含本节点的ID和级别邻居节点收到分组后 将自己的级别设置为分组中的级别加1 然后广播新的级别发现分组节点收到第i级节点的广播分组后 记录发送这个广播分组的节点ID 设置自己的级别为 i 1 广播级别为 i 1 的分组 这个过程持续到网络内每个节点都被赋予一个级别节点一旦建立自己的级别 就忽略任何其他级别发现分组 防止网络产生洪泛拥塞 第一阶段层次发现阶段 LevelDiscoveryPhase Saturday April18 2020 TPSN协议过程 2 目的 实现所有树节点的时间同步 第1级节点同步到根节点 第i级的节点同步到第 i 1 级的一个节点 最终所有节点同步到根节点 实现整个网络的时间同步层次结构建立以后 根节点通过广播时间同步分组启动同步阶段第1级节点收到分组后 各自分别等待一段随机时间 再通过与根节点交换消息同步到根节点第2级节点侦听到第1级节点的交换消息后 等待一段随机时间 再与它记录的上一级别的节点交换消息进行同步 网络中的节点依次与上一级节点同步 最终都同步到根节点等待一段随机时间是为了保证该级节点在上一级节点同步完成后才启动消息交换 第二阶段同步阶段 SynchronizationPhase Saturday April18 2020 TPSN协议过程 3 TPSN原理 相邻级别节点间的同步机制 令 为当节点A的本地时刻为T1时 节点A和B之间的时偏 报文的传输延迟均为d TPSN算法优点与缺点 TPSN算法优点 TPSN基于双向报文交换 因此同步精度高 对任意节点其同步误差取决于它距离根节点的跳数 而与网络中节点总数无关 使TPSN同步精度不会随节点数目增加而降级 从而使TPSN具有较好的扩展性 TPSN算法的缺点 TPSN本质上是对同步 因此全网同步的同步能耗高 一旦根节点失效 就要重新选择根节点并重新进行分级和同步阶段的处理 增加了计算和能量开销 另外 TPSN算法没有对时钟的频差进行估计 这使得它需要频繁同步 开销较大 理论分析和实验证明 TPSN同步误差是RBS的一半结合对clockskew的估计 可以提高TPSN的精度 TPSN同步误差的分析 HRTS HierarchyReferencingTimeSynchronizationProtocol 基于双向报文交换 如TPSN 的传感器网络时间同步协议具有同步精度高的优点 但一次只能同步一对节点 n个节点的单跳网络则需要n 1次同步操作 同步功耗较大 RBS只需要一次同步过程就可完成一个单跳网内所有节点间的同步 同步功耗低 当然同步精度也相对变差 HRTS是一种结合了RBS所使用的参考广播同步技术和TPSN所使用的双向报文交互同步技术的方法 减少了同步所需的报文开销 图描述了层级时间同步的过程 假设单跳网络有包含时间基准节点在内的3个节点BS n1和n2 步骤1 时间基准节点BS发出一个同步请求报文 该报文随机指定一个邻居节点 例如n1 作为应答者节点 即对应于上图中的B节点 n1记录报文到达时刻T2 同时n2也记录下该报文的到达时刻 记为T2 步骤2 应答者节点n1向BS节点发一个同步应答报文 报文中包含了T2与T3 步骤3 现在BS节点已经和n1节点进行了一次双向报文交换 BS节点计算出它与n1节点之间的时钟偏移 步骤4 BS节点发送一个包含 和T2信息的报文 步骤5 当n1 n2节点接收到该报文 对于应答者节点n1来说 只要将其本地时间减去 就达到与BS节点的瞬时同步 对于其他节点来说 只要在其本地时间加上T2 T2 即可达到与BS节点间的瞬时同步 HRTS同步过程 HRTS协议的特点 根节点和应答者节点本质上是采用TPSN同步 根节点和非应答者节点本质上是双向报文交换同步 但非TPSN 应答者节点和非应答者节点本质上是接收者 接收者同步 HRTS协议充分利用了无线传输的广播特性 类似于DMTS 来进一步降低协议的同步功耗 FTSP FloodingTimeSynchronizationProtocol 泛洪时间同步协议 FloodingTimeSynchronizationProtocol 由Vanderbilt大学Miklos Branislav等提出 目标是实现整个网络的时间同步并且误差控制在微秒级 该算法使用单个广播消息实现发送节点与接收节点之间的时间同步 多跳的FTSP协议采用层次结构 根节点为同步源 可以适应大量传感器节点 对网络拓扑结构的变化和根节点的失效有健壮性 精确度较好 该算法通过采用MAC层时间戳和线性回归偏差补偿弥补了相关的错误源 FTSP FloodingTimeSynchronizationProtocol FTSP协议的同步原理 在传感网络中每个节点有唯一的ID号 通过根节点的自动选择算法选出ID号最小的节点为根节点 根节点就是选中的同步时间基准点 同步从根节点开始 时间同步信息分组采用广播的方式发送 未同步节点接收到已同步节点广播的时间信息分组后 从信息分组中估算本地时间与全局时间的时间漂移和时钟偏移 调整自己的本地时间 使之与全局时间达成统一 在节点同步后 生成新的时间信息分组广播到网络中 重复这个过程 直到整个网络每个节点都时间同步 FTSP协议主要采用下面机制来降低时间延迟对时间同步精度的影响 在MAC层记录时间信标 细分消息传输中的时间延迟并对这些延迟进行补偿 利用线性回归算法估算时间漂移 FTSP的特点 FTSP算法通过对收发过程的分析 把时延进一步分为发送中断处理时延 编码时延 传播时延 解码时延 字节对齐时延 接收终端处理时延 进一步降低了时延的不确定性 通过发射多个时间戳 单个报文中包括多个时间戳 使得接收节点可以利用最小方差线性拟合估算自己和发送节点的漂移和偏移差 通过良好的根节点选举机制 针对根节点失效 新节点加入以及拓扑结构变化等情况进行了优化 使得算法的健壮性很好 适合于军事等恶劣应用情况 FTSP的特点与典型应用 FTSP是现有的典型时间同步协议中精度最高的同步协议 并且有良好的健壮性 不会因为个别节点的失效而收到影响 但FTSP基于MAC层时间戳技术的细节技术的实现来提高同步精度 使得FTSP协议的通用性不强 并且洪泛的方式使得能耗开销巨大 用于ZigBee网络的同步休眠与唤醒算法 内容提要 基本概念传统与挑战典型时间同步协议新型同步机制总结 萤火虫同步 1935年 Science1975年 Peskin的RC模型1989年 M S模型 未考虑延迟 1998年 Ernst 考虑有延迟 2005年 真实地实现 简单 高效 可扩展性强 M S模型 研究由初始不同步状态如何达到同步状态个体性质相同 因此一旦达到同步则永远同步萤火虫之间的交互被建模成电量耦合耦合延迟规定为0最终结论为 系统的同步收敛性取决于个体在自由状态下的动力学特性同步的实质 不同步产生了耦合 耦合改变了状态量 而状态量又改变了相位量 相位差通过同步过程不断缩小 最终达到完全相同 即同步状态 Ernst的研究 M S模型没有考虑耦合延迟 Ernst研究了耦合延迟固定时的情况M S模型只研究了正耦合的情况 Ernst还研究了负耦合的情况 萤火虫同步的特点 同步可直接在物理层而不需要以报文的方式实现 直接用硬件实现 使得同步精度不会受到MAC延迟 协议处理与软件实现等的影响 由于对任何同步信号的处理方式均相同 与同步信号的来源无关 因此可扩展性以及适应网络动态变化的能力很强 机制非常简单 不需要对其它节点的时间信息进行存储 萤火虫同步算法的一个限制是要求每个节点具有相似性 但这种机制在非相似节点所组成的网络下能否起到同步的作用 目前还不清楚 由于萤火虫同步的理论研究还远未结束 工程实用性还有待考察 萤火虫同步技术的未来发展 萤火虫同步技术对耦合延迟 耦合强度 耦合性质 初始相位 网络拓扑等因素很敏感 虽然在如两个振荡器的同步收敛性等研究上取得了一定的进展 但无论是理论研究还是仿真研究 研究者在某些结论上还不能达成一致的认识 但可以认同的一点是 在实际系统中 基于萤火虫同步策略的同步技术会取得在一定误差范围内的同步 内容提要 基本概念传统与挑战典型时间同步协议新型同步机制总结 总结 在无线传感器网络中 时间同步不仅要关注同步精度 还需要关注同步能耗 可扩展性和健壮性需求经典的时间同步协议侧重于同步精度和同步能耗的需求 采用时钟飘移补偿 MAC层时间戳技术以及双向报文交换来提高同步精度 充分利用无线传输的广播特性来降低同步能耗萤火虫同步侧重于提高可扩展性和健壮性 非常适合于大规模无线传感器网络的应用 时间同步算法分类 基于Sender Receiver的时间同步通信双方中的发送节点需要记录时间消息发送时刻的时间信标 而接收节点则需要记录时间消息接收时刻的时间信标 同步过程中只需要一次通信 该模式的代表算法是FTSP DMTS 基于Receiver Receiver的时间同步在实现时间同步的过程中 节点只需要在接收时间消息的时刻记录时间信标 而发送时刻不需要记录时间信标 节点只需要知道接收到时间消息的精确时刻 典型协议有RBS等 基于Pair Wise 成对 的时间同步这种算法利用成对同步方法进行发送节点和接收节点间的时间同步 然后扩展到整个网络形成网络的时间同步 此类算法使得网络的同步报文开销较大 对于低开销要求较高的工业无线网络应用有一定的局限性 而且同步阶段所用时间随节点数目的增加而线性增加 不适合对快速性要求较高的工业无线网络 典型的算法主要有TPSN等 主要参考文献 详见原著 1 ElsonJ R merK Wirelesssensornetworks anewregimefortimesynchronization ACMSIGCOMMComputerCommunicationReview 2003 33 1 149 154 3 ElsonJ GirodL EstrinD Fine grainedtimesynchronizationusingreferencebroadcasts In Proc 5thSymposiumonOperationSystemDesignandImplementation Boston 2002 147 163 4 GaneriwalS KumarR SrivastavaM Timing syncprot