6--无线传感器网络时间同步技术v1.1

《无线传感器网络技术》讲义第六章、时间同步技术2007年8月20日内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结基本概念•WSN时间同步技术背景•时间同步技术的分类•时间同步技术的应用场合•关键点：时钟模型WSN时间同步技术背景•集中式系统与分布式系统–集中式：事件间有着明确的时间先后关系，不存在同步问题–分布式：同步是必需的，只是对同步的要求程度不同•无线传感器网络时间同步–典型的分布式系统–是无线传感器网络应用的基础•需要解决的问题–同步精度–功耗–可扩展性WSN时间同步机制的主要性能参数•最大误差：一组传感器节点之间的最大时间差或相对外部标准时间的最大差值。•同步期限：节点保持时间同步的时间长度。•同步范围：节点保持时间同步的区域范围。•可用性：范围覆盖的完整性。•效率：达到同步精度所经历的时间以及消耗的能量。•代价和体积：需要考虑节点的价格和体积。时间同步技术的分类•排序、相对同步与绝对同步–递进关系–各自具有典型的协议代表•外同步与内同步–参考源不同•局部同步与全网同步–同步对象的范围不同时间同步技术的应用场合•多传感器数据压缩与融合•低功耗MAC协议、路由协议•测距、定位（位置相关报务，LBS）•分布式系统的传统要求•协作传输、处理的要求•......时钟模型•硬件时钟模型•软件时钟模型软件时钟模型•软件虚拟时钟•一般是个分段连续、严格单调的函数相关术语•信标节点和未知节点•邻居节点•跳数、跳段距离•基础设施•到达时间、到达时间差•接收信号强度指示•到达角度•视线关系、非视线关系内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结传统与挑战•传统同步方法•传感器网络的挑战传统同步：NTP与GPS•NTP：网络时间协议•GPS：全球定位系统NTP（NetworkTimeProtocol）•体系结构（网络）NTP（NetworkTimeProtocol）•体系结构（单机）NTP（NetworkTimeProtocol）•NTP不适合于WSN•体积、计算能力和存储空间存在限制•传输方式不同：无线而非有线•目标不同：局部最优而非全局最优GPS（GlobalPositionSystem）•从根本上解决了人类在地球上的导航与定位问题。•每颗卫星上配备有高精度的铷、铯原子钟，并不断发射其时间信息•地面接收装置同时接收4颗卫星的时间信息，采用伪距测量定位方法可计算出时间和位置信息•缺点（室内、功耗、安全性、分布式）传感器网络的挑战•室内、矿井、森林，有遮挡•低功耗、低成本和小体积•传输延迟的不确定性•可扩展性、移动性•健壮性、安全性•网络规模大、多点协作传输延迟的不确定性SendtimeAccesstimeTransmissiontimeReceptiontimeReceivetimePropagationtimeSenderReceiver•发送时间：发送节点构造和发送时间同步消息所用时间。e.g.,系统调用时间；内核调度时间；消息从主机发送到网络接口时间。•访问时间：发送节点等待访问网络传输信道的时间。•传播延迟：发送节点传输到接收节点所经历的时间。•接收时间：从接收节点的网络接口接收到消息到通知主机消息达到事件所经历的时间间隔。传输延迟的进一步细化(在Mica2上)时间典型值特性Sendtime&Receivetime0~100ms不确定，依赖处理器负载、操作系统系统调用开销Accesstime10~500ms不确定，依赖信道负载。Transmissiontime&Receptiontime10~20ms确定，依赖报文长度和发送速率。Propagationtime1μs（距离300米）确定，依赖收发方物理距离和传播媒质特性。Interruptwaitingtime在大多数情况下5μs，在重负载下，可达30μs不确定，依赖处理器类型和处理器负载。Encodingtime&Decodingtime100~200μs，2μs的抖动确定，依赖射频芯片的种类和设置。Bytealignmenttime0~400μs确定，依赖发送速率和收发字节偏移。低功耗、低成本和小体积•软硬件都要受到该限制•存储与计算能力均比较小•加剧了电能供应的紧张（电池体积）•网络规模大、密度高•通信距离近分布式、协作可扩展性（Scalability）•在大规模网络中尤为重要•是大规模无线传感器网络软硬件设计中非常重要的问题•满足不同的网络类型、网络规模•满足不同的应用需求健壮性•外部环境复杂，搞毁能力•需要应对安全性挑战•无线传感器网络拓扑动态性较强•网络规模变化、需求变化内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结典型时间同步协议•NTP（NetworkTimeProtocol）•DMTS（DelayMeasurementTimeSynchronization）•RBS（ReferenceBroadcastSynchronization）•TPSN（Timing-syncProtocolforSensorNetworks）•HRTS（HierarchyReferencingTimeSynchronizationProtocol）•FTSP（FloodingTimeSynchronizationProtocol）•GCS（GlobalClockSynchronization）发送者接收者：DMTS•最简单直观•单报文同步同步精度低t0+nt+(t2-t1)•广播方式同步能耗低发送者接收者发送前导码、同步字（nt）嵌入时标t0：发送端的处理延迟和MAC层的访问延迟接收前导码、同步字接收ACK接收数据发送ACK接收处理时标t1时标t2发送时间访问时间DMTS（DelayMeasurementTimeSynchronization）基于同步消息在传输路径上所有延迟的估计，实现节点间的时间同步接收者接收者：RBS（ReferenceBroadcastSynchronizationReceiverNICSenderCriticalPathTimeNICSenderReceiver1CriticalPathReceiver2•通过广播同步指示分组实现接收点间的相对时间同步•RF信号的传播时间差值非常小•可以消除接收节点的接收协议处理、上下文切换、网络接口向主机传送•影响RBS机制性能的因素：时钟偏差、接收点飞确定性因素以及接收点的个数RBS（ReferenceBroadcastSynchronization）•接收者接收者同步的基本依据：接收者时间相移均值为0单跳RBS•用最小二乘法估计clockskew提高同步精度多跳RBS•时间路由技术：基于最短路径查找TPSN（Timing-syncProtocolforSensorNetworks）•否定：DMTSRBS•否定之否定：RBSTPSN•TPSN：双报文交换的发送者接收者同步节点A节点BT1T4T2T3RequestReply同步点2)34()12(TTTTTPSN（Timing-syncProtocolforSensorNetworks）•对同步误差的分析–很重要，是一种基本的分析方法–理论分析和实验证明：TPSN同步误差是RBS的一半–结合对clockskew的估计，可以提高TPSN的精度TPSN（Timing-syncProtocolforSensorNetworks）多跳TPSN•全网周期性同步–“层发现”把网络组织成最短生成树–逐层在相邻两层节点间同步•网络内两个节点的同步–“后同步”查找两个节点间的路径–在路径的相邻两个节点间进行TPSN同步HRTS（HierarchyReferencingTimeSynchronizationProtocol）•TPSN基于双向报文交换，因此同步精度高•TPSN本质上是对同步，因此全网同步的同步能耗高•由DMTS发现，广播能降低全网同步能耗•结合广播和节点间的双向报文交换同步HRTS协议BSn1n2n3(a)BSn1n2n3(b)BSn1n2n3(c)n4BSn1n2n3(d)n4HRTS（HierarchyReferencingTimeSynchronizationProtocol）•根节点和应答者节点本质上是采用TPSN同步•根节点和非应答者节点本质上是双向报文交换同步（但非TPSN）•应答者节点和非应答者节点本质上是接收者--接收者同步HRTS（HierarchyReferencingTimeSynchronizationProtocol）FTSP（FloodingTimeSynchronizationProtocol）•同步精度高•工程实用性强•强调实现细节•MAC层时间戳技术–和平台直接相关，书中给出了在Mica2平台下的实现•基本同步原理–发送者--接收者同步–单个报文中包括多个时间戳（在报文的不同位置）–根据单个报文中的多个时间戳，可对中断等待时间进行补偿–对clockskew的补偿仍采用最小二乘法FTSP（FloodingTimeSynchronizationProtocol）多跳FTSP•洪泛方式广播时间基准节点的时间•协议健壮•实际做了工程化的实现GCS（GlobalClockSynchronization）•节点遍历模式•聚类分层模式•扩散模式GCS：节点遍历模式•游走阶段：记录游走的出发和到达时间•时间校正阶段：根据节点在游走环的位置和游走时间对节点时间进行校正•理论假设：每段游走的时间花费相同GCS：聚类分层模式•单纯的节点遍历方式导致遍历环过长，同步功耗大•通过分簇协议，把网络组织成簇结构•簇头节点间以节点遍历方式同步•簇内节点可以节点遍历或RBS等方式进行同步GCS：扩散模式•越简单的方法往往是越有效的•同步过程：对接收到的时间进行平均操作，并对自己的时间进行扩散•理论证明：当把所有节点的时间当成一张快照时，经过若干轮扩散过程，所有节点时间最终将收敛到所有节点时间的平均值上内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结新型同步机制•基于报文交换的同步机制面临着挑战–同步精度问题–可扩展性问题•新型同步机制–萤火虫同步–协作同步•两个概念–同时性与同步性萤火虫同步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的结论一致•结论：考虑固定耦合延迟的情况下，只有负耦合才可能取得同步收敛负耦合下的全连接网络•仿真研究方法•和两个节点下的情况不同•出现分簇现象其他一些研究与结论•理论上没有突破•单纯的仿真方法意义有限•萤火虫同步技术对耦合延迟、耦合强度、耦合性质、初始相位、网络拓扑等因素很敏感。虽然在例如两个振荡器的同步收敛性研究上取得了一定的进展，但无论是理论研究还是仿真研究，研究者在某些结论上还不能达成一致的认识。但可以认同的一点是：在实际系统中，基于萤火虫同步策略的同步技术会取得在一