无线传感器网络WSN时间同步.pptx

《无线传感器网络WSN时间同步.pptx》由会员分享，可在线阅读，更多相关《无线传感器网络WSN时间同步.pptx（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1无线传感器网络无线传感器网络WSN时间同步时间同步内容提要内容提要1.1.基本概念2.2.传统与挑战3.3.典型时间同步协议4.4.新型同步机制5.5.小结第1页/共53页WSN时间同步技术背时间同步技术背景景n n集中式系统与分布式系统集中式系统与分布式系统n n集中式：事件间有着明确的时间先后关系，不存在同步问集中式：事件间有着明确的时间先后关系，不存在同步问题题n n分布式：同步是必需的，只是对同步的要求程度不同分布式：同步是必需的，只是对同步的要求程度不同n n无线传感器网络时间同步无线传感器网络时间同步n n典型的分布式系统典型的分布式系统n n是无线传感器网络应用的基础是无

2、线传感器网络应用的基础n n需要解决的问题需要解决的问题n n同步精度同步精度n n功耗功耗n n可扩展性可扩展性第2页/共53页时间同步技术的分类时间同步技术的分类排序、相对同步与绝对同步递进关系各自具有典型的协议代表外同步与内同步参考源不同局部同步与全网同步同步对象的范围不同第3页/共53页时间同步技术的应用场时间同步技术的应用场合合n n多传感器数据压缩与融合n n低功耗MAC协议、路由协议n n测距、定位（位置相关报务，LBS）n n分布式系统的传统要求n n协作传输、处理的要求n n.第4页/共53页时钟模型时钟模型n n硬件时钟模型n n软件时钟模型第5页/共53页硬件时钟模型硬件

3、时钟模型n n基本名词基本名词n n时间、晶振、时钟（时间、晶振、时钟（RTCRTC）n n时钟偏移（时钟偏移（clock offsetclock offset）n n时钟飘移（时钟飘移（clock driftclock drift）n n速率恒定模型速率恒定模型n n最常用，但不适应环境变化剧烈的场合最常用，但不适应环境变化剧烈的场合n n飘移有界模型飘移有界模型n n常用于确定同步误差上下界常用于确定同步误差上下界n n飘移变化有界模型飘移变化有界模型第6页/共53页软件时钟模型软件时钟模型n n软件虚拟时钟n n一般是个分段连续、严格单调的函数第7页/共53页传统与挑战传统与挑战n n传

4、统同步方法n n传感器网络的挑战第8页/共53页传统同步：传统同步：NTP与与GPSNTP：网络时间协议GPS：全球定位系统第9页/共53页NTP（Network Time Protocol）体系结构（网络）第10页/共53页NTP（Network Time Protocol）n n体系结构（单机）第11页/共53页NTP（Network Time Protocol）n nNTP不适合于WSNn n体积、计算能力和存储空间存在限制n n传输方式不同：无线而非有线n n目标不同：局部最优而非全局最优第12页/共53页GPS（Global Position System）n n从根本上解决了人类在

5、地球上的导航与定位问题。n n每颗卫星上配备有高精度的铷、铯原子钟，并不断发射其时间信息n n地面接收装置同时接收4颗卫星的时间信息，采用伪距测量定位方法可计算出时间和位置信息n n缺点（室内、功耗、安全性、分布式）第13页/共53页传感器网络的挑战传感器网络的挑战n n室内、矿井、森林，有遮挡n n低功耗、低成本和小体积n n传输延迟的不确定性n n可扩展性、移动性n n健壮性、安全性n n网络规模大、多点协作第14页/共53页传输延迟的不确定性传输延迟的不确定性SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropag

6、ationtimeSenderReceiver第15页/共53页传输延迟的进一步细传输延迟的进一步细化化(在在Mica2上上)时间时间典型值典型值特性特性Send time&Receive time0100ms不确定，依赖处理器负载、操不确定，依赖处理器负载、操作系统系统调用开销作系统系统调用开销Access time10500ms不确定，依赖信道负载。不确定，依赖信道负载。Transmission time&Reception time1020ms确定，依赖报文长度和发送速确定，依赖报文长度和发送速率。率。Propagation time1s（距离（距离300米）米）确定，依赖收发方物理距离

7、和确定，依赖收发方物理距离和传播媒质特性。传播媒质特性。Interrupt waiting time在大多数情况下在大多数情况下5s，在重，在重负载下，可达负载下，可达30s不确定，依赖处理器类型和处不确定，依赖处理器类型和处理器负载。理器负载。Encoding time&Decoding time100200s，2s的抖动的抖动确定，依赖射频芯片的种类和确定，依赖射频芯片的种类和设置。设置。Byte alignment time0400s确定，依赖发送速率和收发字确定，依赖发送速率和收发字节偏移。节偏移。第16页/共53页低功耗、低成本和小体积低功耗、低成本和小体积n n软硬件都要受到该限制

8、n n存储与计算能力均比较小n n加剧了电能供应的紧张（电池体积）n n网络规模大、密度高n n通信距离近 分布式、协作第17页/共53页可扩展性（可扩展性（Scalability）n n在大规模网络中尤为重要n n是大规模无线传感器网络软硬件设计中非常重要的问题n n满足不同的网络类型、网络规模n n满足不同的应用需求第18页/共53页健壮性健壮性n n外部环境复杂，搞毁能力n n需要应对安全性挑战n n无线传感器网络拓扑动态性较强n n网络规模变化、需求变化第19页/共53页典型时间同步协议典型时间同步协议n nNTPNTP（Network Time ProtocolNetwork Tim

9、e Protocol）n nDMTSDMTS （Delay Measurement Time SynchronizationDelay Measurement Time Synchronization）n nRBSRBS （Reference Broadcast SynchronizationReference Broadcast Synchronization）n nTPSNTPSN （Timing-sync Protocol for Sensor NetworksTiming-sync Protocol for Sensor Networks）n nHRTSHRTS （Hierarchy

10、Referencing Time Synchronization Hierarchy Referencing Time Synchronization ProtocolProtocol）n nFTSPFTSP （Flooding Time Synchronization ProtocolFlooding Time Synchronization Protocol）n nGCSGCS （Global Clock SynchronizationGlobal Clock Synchronization）第20页/共53页发送者发送者接收者：接收者：DMTS 最简单直观 单报文同步同步精度低 广播方式

11、同步能耗低发送者发送者接收者接收者发发送送前前导导码码、同步字同步字嵌嵌 入入 时时标标t0接接收收前前导导码码、同步字同步字接接 收收ACK接收接收数据数据发发 送送ACK接接 收收处理处理时标时标t1时标时标t2发送时间发送时间访问时间访问时间DMTS（Delay Measurement Time Synchronization）第21页/共53页接收者接收者接收者：接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchron

12、ization）第22页/共53页RBS（Reference Broadcast Synchronization）n n接收者接收者接收者同步的基本依据：接收者时接收者同步的基本依据：接收者时间相移均值为间相移均值为0 0第23页/共53页单跳单跳RBSn n用最小二乘法估计用最小二乘法估计clock skewclock skew提高同步精度提高同步精度第24页/共53页多跳多跳RBS时间路由技术：基于最短路径查找第25页/共53页TPSN（Timing-sync Protocol for Sensor Networks）n n否定：DMTSRBSn n否定之否定：RBSTPSNn nTPSN

13、：双报文交换的发送者接收者同步第26页/共53页节点节点A节点节点BT1T4T2T3RequestReply同步点TPSNTPSN（Timing-sync Protocol for Sensor NetworksTiming-sync Protocol for Sensor Networks）第27页/共53页n n对同步误差的分析n n很重要，是一种基本的分析方法很重要，是一种基本的分析方法n n理论分析和实验证明：理论分析和实验证明：TPSNTPSN同步误差是同步误差是RBSRBS的的一半一半n n结合对结合对clock skewclock skew的估计，可以提高的估计，可以提高TPSN

14、TPSN的精的精度度TPSNTPSN（Timing-sync Protocol for Sensor NetworksTiming-sync Protocol for Sensor Networks）第28页/共53页多跳多跳TPSNn n全网周期性同步全网周期性同步n n“层发现层发现”把网络组织成最短生成树把网络组织成最短生成树n n逐层在相邻两层节点间同步逐层在相邻两层节点间同步n n网络内两个节点的同步网络内两个节点的同步n n“后同步后同步”查找两个节点间的路径查找两个节点间的路径n n在路径的相邻两个节点间进行在路径的相邻两个节点间进行TPSNTPSN同步同步第29页/共53页HR

15、TSHRTS（Hierarchy Referencing Time Synchronization Hierarchy Referencing Time Synchronization ProtocolProtocol）n nTPSNTPSN基于双向报文交换，因此同步精度高基于双向报文交换，因此同步精度高n nTPSNTPSN本质上是对同步，因此全网同步的同本质上是对同步，因此全网同步的同步能耗高步能耗高n n由由DMTSDMTS发现，广播能降低全网同步能耗发现，广播能降低全网同步能耗n n结合广播和节点间的双向报文交换同步结合广播和节点间的双向报文交换同步HRTSHRTS协议协议第30页/共

16、53页 BS n1 n2 n3(a)BS n1 n2 n3(b)BS n1 n2 n3(c)n4 BS n1 n2 n3(d)n4 HRTSHRTS（Hierarchy Referencing Time Synchronization Hierarchy Referencing Time Synchronization ProtocolProtocol）第31页/共53页n n根节点和应答者节点本质上是采用TPSN同步n n根节点和非应答者节点本质上是双向报文交换同步（但非TPSN）n n应答者节点和非应答者节点本质上是接收者-接收者同步HRTSHRTS（Hierarchy Referenci

17、ng Time Synchronization Hierarchy Referencing Time Synchronization ProtocolProtocol）第32页/共53页FTSP（Flooding Time Synchronization Protocol）n n同步精度高n n工程实用性强n n强调实现细节第33页/共53页n nMACMAC层时间戳技术层时间戳技术n n和平台直接相关，书中给出了在和平台直接相关，书中给出了在Mica2Mica2平台下的实现平台下的实现n n基本同步原理基本同步原理n n发送者发送者-接收者同步接收者同步n n单个报文中包括多个时间戳（在报文

18、的不同位置）单个报文中包括多个时间戳（在报文的不同位置）n n根据单个报文中的多个时间戳，可对中断等待时间进行补偿根据单个报文中的多个时间戳，可对中断等待时间进行补偿n n对对clock skewclock skew的补偿仍采用最小二乘法的补偿仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol）第34页/共53页多跳多跳FTSPn n洪泛方式广播时间基准节点的时间n n协议健壮n n实际做了工程化的实现第35页/共53页GCS（Global Clock Synchronization）n n节点遍历模式n n聚类分层模式n n扩散模式第36页

19、/共53页GCS：节点遍历模式：节点遍历模式n n游走阶段：记录游走的出发和到达时间游走阶段：记录游走的出发和到达时间n n时间校正阶段：根据节点在游走环的位置和游时间校正阶段：根据节点在游走环的位置和游走时间对节点时间进行校正走时间对节点时间进行校正n n理论假设：每段游走的时间花费相同理论假设：每段游走的时间花费相同第37页/共53页GCS：聚类分层模式：聚类分层模式n n单纯的节点遍历方式导致遍历环过长，同步功耗大n n通过分簇协议，把网络组织成簇结构n n簇头节点间以节点遍历方式同步n n簇内节点可以节点遍历或RBS等方式进行同步第38页/共53页GCS：扩散模式：扩散模式n n越简单

20、的方法往往是越有效的n n同步过程：对接收到的时间进行平均操作，并对自己的时间进行扩散n n理论证明：当把所有节点的时间当成一张快照时，经过若干轮扩散过程，所有节点时间最终将收敛到所有节点时间的平均值上第39页/共53页新型同步机制新型同步机制n n基于报文交换的同步机制面临着挑战n n同步精度问题同步精度问题n n可扩展性问题可扩展性问题n n新型同步机制n n萤火虫同步萤火虫同步n n协作同步协作同步n n两个概念n n同时性与同步性同时性与同步性第40页/共53页萤火虫同步萤火虫同步1935年，Science1975年,Peskin的RC模型1989年，M&S模型（无延迟）1998年，E

21、rnst（有延迟）结论2005年，真实地实现简单，高效，可扩展性强第41页/共53页M&S模型模型n n研究由初始不同步状态如何达到同步状态研究由初始不同步状态如何达到同步状态n n个体性质相同个体性质相同,因此一旦达到同步则永远同步因此一旦达到同步则永远同步n n萤火虫之间的交互被建模成电量耦合萤火虫之间的交互被建模成电量耦合n n耦合延迟规定为耦合延迟规定为0 0n n最终结论为最终结论为:系统的同步收敛性取决于个体在自由状态下的动力学系统的同步收敛性取决于个体在自由状态下的动力学特性特性n n同步的实质：不同步产生了耦合，耦合改变了状态量，而状态量同步的实质：不同步产生了耦合，耦合改变了

22、状态量，而状态量又改变了相位量又改变了相位量 ,相位差通过同步过程不断缩小，最终达到完全相相位差通过同步过程不断缩小，最终达到完全相同同,即同步状态即同步状态 第42页/共53页M&S模型模型n n证明了全耦合系统的同步收敛性n n没有证明多跳网络的同步收敛性第43页/共53页Ernst的研究的研究n nM&S模型没有考虑耦合延迟，Ernst研究了耦合延迟固定时的情况n nM&S模型只研究了正耦合的情况，Ernst还研究了负耦合的情况第44页/共53页Ernst-正耦合（正耦合（2个节点）个节点）存在两种情况不可能达到完全同步其实是M&S模型的扩展第45页/共53页Ernst-负耦合（负耦合（

23、2个节点）个节点）存在三种情况和Peskin的结论一致结论：考虑固定耦合延迟的情况下，只有负耦合才可能取得同步收敛 第46页/共53页负耦合下的全连接网络负耦合下的全连接网络仿真研究方法和两个节点下的情况不同出现分簇现象第47页/共53页其他一些研究与结论其他一些研究与结论n n理论上没有突破理论上没有突破n n单纯的仿真方法意义有限单纯的仿真方法意义有限n n萤火虫同步技术对耦合延迟、耦合强度、耦萤火虫同步技术对耦合延迟、耦合强度、耦合性质、初始相位、网络拓扑等因素很敏感。合性质、初始相位、网络拓扑等因素很敏感。虽然在例如两个振荡器的同步收敛性研究上虽然在例如两个振荡器的同步收敛性研究上取得

24、了一定的进展，但无论是理论研究还是取得了一定的进展，但无论是理论研究还是仿真研究，研究者在某些结论上还不能达成仿真研究，研究者在某些结论上还不能达成一致的认识。但可以认同的一点是：在实际一致的认识。但可以认同的一点是：在实际系统中，基于萤火虫同步策略的同步技术会系统中，基于萤火虫同步策略的同步技术会取得在一定误差范围内的同步。取得在一定误差范围内的同步。第48页/共53页实践：实践：RFA算法算法RFA(Reachback Firefly Algorithm)在24个Micaz节点组成的网络上实现同步误差是存在的，和同步操作的频率直接相关核心思想：将某轮同步周期内接收到的同步报文的影响推后到下

25、一轮同步周期的起始时刻 第49页/共53页总结：萤火虫同步总结：萤火虫同步n n同步可直接在物理层而不需要以报文的方式实现。同步可直接在物理层而不需要以报文的方式实现。直接用硬件实现，使得同步精度不会受到直接用硬件实现，使得同步精度不会受到MACMAC延延迟、协议处理与软件实现等的影响。迟、协议处理与软件实现等的影响。n n由于对任何同步信号的处理方式均相同，与同步信由于对任何同步信号的处理方式均相同，与同步信号的来源无关，因此可扩展性以及适应网络动态变号的来源无关，因此可扩展性以及适应网络动态变化的能力很强。化的能力很强。n n机制非常简单，不需要对其它节点的时间信息进行机制非常简单，不需要

26、对其它节点的时间信息进行存储。萤火虫同步算法的一个限制是要求每个节点存储。萤火虫同步算法的一个限制是要求每个节点具有相似性，但这种机制在非相似节点所组成的网具有相似性，但这种机制在非相似节点所组成的网络下能否起到同步的作用，目前还不清楚。络下能否起到同步的作用，目前还不清楚。n n此外，由于萤火虫同步的理论研究还远未结束，工此外，由于萤火虫同步的理论研究还远未结束，工程实用性还有待考察。程实用性还有待考察。第50页/共53页协作同步协作同步本质：空间平均而非时间平均实现上直接受限于信号处理技术 第51页/共53页小节：小节：n n重点掌握内容：传感器网络时间同步的要求、网络时间同步机制、传感器网络时间同步机制n n了解：萤火虫同步第52页/共53页