无线传感器网络的时间同步技术

无线传感器网络的时间同步技术第一页，共61页。内容提要基本概念传统与挑战典型时间同步协议新型同步机制总结第二页，共61页。内容提要基本概念传统与挑战典型时间同步协议新型同步机制总结第三页，共61页。基本概念WSN时间同步技术背景时间同步技术的分类时间同步技术的应用场合关键点：时钟模型第四页，共61页。WSN时间同步技术背景集中式系统与分布式系统集中式：事件间有着明确的时间先后关系，不存在同步问题分布式：同步是必需的，只是对同步的要求程度不同无线传感器网络时间同步典型的分布式系统是无线传感器网络应用的基础需要解决的问题同步精度功耗可扩展性第五页，共61页。时间同步技术的分类排序、相对同步与绝对同步递进关系各自具有典型的协议代表外同步与内同步参考源不同局部同步与全网同步同步对象的范围不同第六页，共61页。时间同步技术的应用场合多传感器数据压缩与融合低功耗MAC协议、路由协议测距、定位（位置相关报务，LBS）分布式系统的传统要求协作传输、处理的要求......第七页，共61页。时钟模型硬件时钟模型软件时钟模型第八页，共61页。硬件时钟模型基本名词时间、晶振、时钟（RTC）时钟偏移（clockoffset）时钟飘移（clockdrift）速率恒定模型最常用，但不适应环境变化剧烈的场合飘移有界模型常用于确定同步误差上下界飘移变化有界模型第九页，共61页。软件时钟模型软件虚拟时钟一般是个分段连续、严格单调的函数第十页，共61页。内容提要基本概念传统与挑战典型时间同步协议新型同步机制总结第十一页，共61页。传统与挑战传统同步方法传感器网络的挑战第十二页，共61页。传统同步：NTP与GPSNTP：网络时间协议GPS：全球定位系统第十三页，共61页。NTP（NetworkTimeProtocol）体系结构（网络）第十四页，共61页。NTP（NetworkTimeProtocol）体系结构（单机）第十五页，共61页。NTP（NetworkTimeProtocol）NTP不适合于WSN体积、计算能力和存储空间存在限制传输方式不同：无线而非有线目标不同：局部最优而非全局最优第十六页，共61页。GPS（GlobalPositionSystem）从根本上解决了人类在地球上的导航与定位问题。每颗卫星上配备有高精度的铷、铯原子钟，并不断发射其时间信息地面接收装置同时接收4颗卫星的时间信息，采用伪距测量定位方法可计算出时间和位置信息缺点（室内、功耗、安全性、分布式）第十七页，共61页。传感器网络的挑战室内、矿井、森林，有遮挡低功耗、低成本和小体积传输延迟的不确定性可扩展性、移动性健壮性、安全性网络规模大、多点协作第十八页，共61页。传输延迟的不确定性SendtimeAccesstimeTransmissiontimeReceptiontimeReceivetimePropagationtimeSenderReceiver第十九页，共61页。传输延迟的进一步细化(在Mica2上)时间典型值特性Sendtime&Receivetime0~100ms不确定，依赖处理器负载、操作系统系统调用开销Accesstime10~500ms不确定，依赖信道负载。Transmissiontime&Receptiontime10~20ms确定，依赖报文长度和发送速率。Propagationtime<1μs（距离<300米）确定，依赖收发方物理距离和传播媒质特性。Interruptwaitingtime在大多数情况下<5μs，在重负载下，可达30μs不确定，依赖处理器类型和处理器负载。Encodingtime&Decodingtime100~200μs，<2μs的抖动确定，依赖射频芯片的种类和设置。Bytealignmenttime0~400μs确定，依赖发送速率和收发字节偏移。第二十页，共61页。低功耗、低成本和小体积软硬件都要受到该限制存储与计算能力均比较小加剧了电能供应的紧张（电池体积）网络规模大、密度高通信距离近分布式、协作第二十一页，共61页。可扩展性（Scalability）在大规模网络中尤为重要是大规模无线传感器网络软硬件设计中非常重要的问题满足不同的网络类型、网络规模满足不同的应用需求第二十二页，共61页。健壮性外部环境复杂，搞毁能力需要应对安全性挑战无线传感器网络拓扑动态性较强网络规模变化、需求变化第二十三页，共61页。内容提要基本概念传统与挑战典型时间同步协议新型同步机制总结第二十四页，共61页。典型时间同步协议NTP（NetworkTimeProtocol）DMTS（DelayMeasurementTimeSynchronization）RBS（ReferenceBroadcastSynchronization）TPSN（Timing-syncProtocolforSensorNetworks）HRTS（HierarchyReferencingTimeSynchronizationProtocol）FTSP（FloodingTimeSynchronizationProtocol）GCS（GlobalClockSynchronization）第二十五页，共61页。发送者接收者：DMTS最简单直观单报文同步同步精度低广播方式同步能耗低发送者接收者发送前导码、同步字嵌入时标t0接收前导码、同步字接收ACK接收数据发送ACK接收处理时标t1时标t2发送时间访问时间DMTS（DelayMeasurementTimeSynchronization）第二十六页，共61页。接收者接收者：RBSReceiverNICSenderCriticalPathTimeNICSenderReceiver1CriticalPathReceiver2RBS（ReferenceBroadcastSynchronization）第二十七页，共61页。RBS（ReferenceBroadcastSynchronization）接收者接收者同步的基本依据：接收者时间相移均值为0第二十八页，共61页。单跳RBS用最小二乘法估计clockskew提高同步精度第二十九页，共61页。多跳RBS时间路由技术：基于最短路径查找第三十页，共61页。TPSN（Timing-syncProtocolforSensorNetworks）否定：DMTSRBS否定之否定：RBSTPSNTPSN：双报文交换的发送者接收者同步第三十一页，共61页。节点A节点BT1T4T2T3RequestReply同步点TPSN（Timing-syncProtocolforSensorNetworks）第三十二页，共61页。对同步误差的分析很重要，是一种基本的分析方法理论分析和实验证明：TPSN同步误差是RBS的一半结合对clockskew的估计，可以提高TPSN的精度TPSN（Timing-syncProtocolforSensorNetworks）第三十三页，共61页。多跳TPSN全网周期性同步“层发现”把网络组织成最短生成树逐层在相邻两层节点间同步网络内两个节点的同步“后同步”查找两个节点间的路径在路径的相邻两个节点间进行TPSN同步第三十四页，共61页。HRTS（HierarchyReferencingTimeSynchronizationProtocol）TPSN基于双向报文交换，因此同步精度高TPSN本质上是对同步，因此全网同步的同步能耗高由DMTS发现，广播能降低全网同步能耗结合广播和节点间的双向报文交换同步HRTS协议第三十五页，共61页。

BS

n1

n2

n3

(a)

BS

n1

n2

n3

(b)

BS

n1

n2

n3

(c)

n4

BS

n1

n2

n3

(d)

n4

HRTS（HierarchyReferencingTimeSynchronizationProtocol）第三十六页，共61页。根节点和应答者节点本质上是采用TPSN同步根节点和非应答者节点本质上是双向报文交换同步（但非TPSN）应答者节点和非应答者节点本质上是接收者--接收者同步HRTS（HierarchyReferencingTimeSynchronizationProtocol）第三十七页，共61页。FTSP（FloodingTimeSynchronizationProtocol）同步精度高工程实用性强强调实现细节第三十八页，共61页。MAC层时间戳技术和平台直接相关，书中给出了在Mica2平台下的实现基本同步原理发送者--接收者同步单个报文中包括多个时间戳（在报文的不同位置）根据单个报文中的多个时间戳，可对中断等待时间进行补偿对clockskew的补偿仍采用最小二乘法FTSP（FloodingTimeSynchronizationProtocol）第三十九页，共61页。多跳FTSP洪泛方式广播时间基准节点的时间协议健壮实际做了工程化的实现第四十页，共61页。GCS（GlobalClockSynchronization）节点遍历模式聚类分层模式扩散模式第四十一页，共61页。GCS：节点遍历模式游走阶段：记录游走的出发和到达时间时间校正阶段：根据节点在游走环的位置和游走时间对节点时间进行校正理论假设：每段游走的时间花费相同第四十二页，共61页。GCS：聚类分层模式单纯的节点遍历方式导致遍历环过长，同步功耗大通过分簇协议，把网络组织成簇结构簇头节点间以节点遍历方式同步簇内节点可以节点遍历或RBS等方式进行同步第四十三页，共61页。GCS：扩散模式越简单的方法往往是越有效的同步过程：对接收到的时间进行平均操作，并对自己的时间进行扩散理论证明：当把所有节点的时间当成一张快照时，经过若干轮扩散过程，所有节点时间最终将收敛到所有节点时间的平均值上第四十四页，共61页。内容提要基本概念传统与挑战典型时间同步协议新型同步机制总结第四十五页，共61页。新型同步机制基于报文交换的同步机制面临着挑战同步精度问题可扩展性问题新型同步机制萤火虫同步协作同步两个概念同时性与同步性第四十六页，共61页。萤火虫同步1935年，Science1975年,Peskin的RC模型1989年，M&S模型（无延迟）1998年，Ernst（有延迟）结论2005年，真实地实现简单，高效，可扩展性强第四十七页，共61页。M&S模型研究由初始不同步状态如何达到同步状态个体性质相同,因此一旦达到同步则永远同步萤火虫之间的交互被建模成电量耦合耦合延迟规定为0最终结论为:系统的同步收敛性取决于个体在自由状态下的动力学特性同步的实质：不同步产生了耦合，耦合改变了状态量，而状态量又改变了相位量,相位差通过同步过程不断缩小，最终达到完全相同,即同步状态第四十八页，共61页。M&S模型证明了全耦合系统的同步收敛性没有证明多跳网络的同步收敛性第四十九页，共61页。Ernst的研究M&S模型没有考虑耦合延迟，Ernst研究了耦合延迟固定时的情况M&S模型只研究了正耦合的情况，Ernst还研究了负耦合的情况第五十页，共61页。Ernst--正耦合（2个节点）存在两种情况不可能达到完全同步其实是M&S模型的扩展第五十一页，共61页。Ernst--负耦合（2个节点）存在三种情况和Peskin的结论一致结论：考虑固定耦合延迟的情况下，只有负耦合才可能取得同步收敛第五十二页，共61页。负耦合下的全连接网络仿真研究方法和两个节点下的情况不同出现分簇现象第五十三页，共61页。其他一些研究与结论理论上没有突破单纯的仿真方法意义有限萤火虫同步技术对耦合延迟、耦合强度、耦合性质、初始相位、网络拓扑等因素很敏感。虽然在例如两个振荡器的同步收敛性研究上取得了一定的进展，但无论是理论研究还是仿真研究，研究者在某些结论上还不能达成一致的认识。但可以认同的一点是：在实际系统中，基于萤火虫同步策略的同步技术会取得在一定误差范围内的同步。第五十四页，共61页。实践：RFA算法RFA(ReachbackFireflyAlgorithm)

在24个Micaz节点组成的网络上实现同步误差是存在的，和同步操作的频率直接相关核心思想：将某轮同步周期内接收到的同步报文的影响推后到下一轮同步周期的起始时刻第五十五页，共61页。总结：萤火虫同步同步可直接在物理层而不需要以报文的方式实现。直接用硬件实现，使得同步精度不会受到MAC延迟、协议处理与软件实现等的影响。由于对任何同步信号的处理方式均相同，与同步信号的来源无关，因此可扩展性以及适应网络动态变化的能力很强。机制非常简单，不需要对其它节点的时间信息进行存储。萤火虫同步算法的一个限制是要求每个节点具有相似性，但这种机制在非相似节点所组成的网络下能否起到同步的作用，目前还不清楚。此外，由于萤火虫同步的理论研究还远未结束，工程实用性还有待考察。第五十六页，共61页。协作同步本质：空间平均而非时间平均实现上直接受限于信号处理技术第五十七页，共61页。内容提要基本概念传统与挑战典型时间同步协议新型同步机制总结第五十八页，共61页。总结在无线传感器网络中，时间同步不仅要关注同步精度，还需要关注同步能耗、可扩展性和健壮性需求经典的时间同步协议侧重于同步精度和同步能耗的需求，采用时钟飘移补偿、MAC层时间戳技术以及双向报文交换来提高同步精度，充分利用无线传输的广播特性和捎带技术来降低同步能耗萤火虫同步和协作同步则侧重于提高可扩展性和健壮性。非常适合于大规模无线传感器网络的应用第五十九页，共61页。主要参考文献（详见原著）[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-syncprotocolforsensornetworks.In:Proc.1stACMConferenceonEmbeddedNetworkedSensorSystems,LosAngeles,2003,138-149.[7]MillsD.L..Networktimeprotocol(Version3)specification,implementationandanalysis.UniversityofDelaware,DARPANetworkWorkingGroupReport:RFC-1305,1992.[13]MiklosM.,BranislavK.,GyulaS.,AkosL..Thefloodingtimesynchronizationprotocol.In:Proc.2thACMConferenceonEmbeddedNetworkedSensorSystems,Baltimore,2004,39-49.[14]SuPi