第06章时间同步技术要点.ppt

无线传感器网络Wireless Sensor Networks第五章、时间同步技术内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结基本概念nWSN时间同步技术背景n时间同步技术的分类n时间同步技术的应用场合n关键点：时钟模型WSN时间同步技术背景n集中式系统与分布式系统n不同节点晶振不同，时间长了存在偏差n受电池能量，存储空间，带宽限制n集中式：事件间有着明确的时间先后关系，不存在同步问题n分布式：同步是必需的，只是对同步的要求程度不同n无线传感器网络时间同步n典型的分布式系统是无线传感器网络应用的基础n需要解决的问题n同步精度n功耗n可扩展性时间同步技术的分类排序、相对同步与绝对同步递进关系各自具有典型的协议代表外同步与内同步参考源不同局部同步与全网同步同步对象的范围不同时间同步技术的应用场合n多传感器数据压缩与融合n低功耗MAC协议、路由协议n测距、定位（位置相关报务，LBS）n分布式系统的传统要求n协作传输、处理的要求n... ...时钟模型n硬件时钟模型n软件时钟模型硬件时钟模型n基本名词n时间、晶振、时钟（RTC）n时钟偏移（clock offset）n时钟飘移（clock drift）n速率恒定模型n最常用，但不适应环境变化剧烈的场合n飘移有界模型n常用于确定同步误差上下界n飘移变化有界模型软件时钟模型n软件虚拟时钟n一般是个分段连续、严格单调的函数内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结传统与挑战n传统同步方法n传感器网络的挑战传统同步：NTP与GPSNTP：网络时间协议GPS：全球定位系统NTP（Network Time Protocol） 体系结构（网络）NTP（Network Time Protocol）n体系结构（单机）NTP（Network Time Protocol）nNTP不适合于WSNn体积、计算能力和存储空间存在限制n传输方式不同：无线而非有线n目标不同：局部最优而非全局最优GPS（Global Position System） n从根本上解决了人类在地球上的导航与定位问题。

n每颗卫星上配备有高精度的铷、铯原子钟，并不断发射其时间信息n地面接收装置同时接收4颗卫星的时间信息，采用伪距测量定位方法可计算出时间和位置信息n缺点（室内、功耗、安全性、分布式）传感器网络的挑战n室内、矿井、森林，有遮挡n低功耗、低成本和小体积n传输延迟的不确定性n可扩展性、移动性n健壮性、安全性n网络规模大、多点协作传输延迟的不确定性SendtimeAccesstimeTransmissiontimeReception timeReceivetimePropagationtimeSenderReceiver传输延迟的进一步细化(在Mica2上)时间典型典型值特性特性Send time & Receive time0~100ms不确定，依不确定，依赖处理器理器负载、操、操作系作系统系系统调用开用开销Access time10~500ms不确定，依不确定，依赖信道信道负载Transmission time & Reception time10~20ms确定，依确定，依赖报文文长度和度和发送速送速率Propagation time<1μs（距离（距离<300米）米）确定，依确定，依赖收收发方物理距离和方物理距离和传播媒播媒质特性。

特性Interrupt waiting time在大多数情况下在大多数情况下<5μs，在重，在重负载下，可达下，可达30μs不确定，依不确定，依赖处理器理器类型和型和处理器理器负载Encoding time & Decoding time100~200μs，，<2μs的抖的抖动确定，依确定，依赖射射频芯片的种芯片的种类和和设置Byte alignment time0~400μs确定，依确定，依赖发送速率和收送速率和收发字字节偏移低功耗、低成本和小体积n软硬件都要受到该限制n存储与计算能力均比较小n加剧了电能供应的紧张（电池体积）n网络规模大、密度高n通信距离近  分布式、协作可扩展性（Scalability）n在大规模网络中尤为重要n是大规模无线传感器网络软硬件设计中非常重要的问题n满足不同的网络类型、网络规模n满足不同的应用需求健壮性n外部环境复杂，搞毁能力n需要应对安全性挑战n无线传感器网络拓扑动态性较强n网络规模变化、需求变化n影响：数据融合和休眠唤醒方式节能内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结典型时间同步协议nNTP（Network Time Protocol）nDMTS （Delay Measurement Time Synchronization） nRBS （Reference Broadcast Synchronization） nTPSN （Timing-sync Protocol for Sensor Networks） nHRTS （Hierarchy Referencing Time Synchronization Protocol） nFTSP （Flooding Time Synchronization Protocol） nGCS （Global Clock Synchronization） 发送者接收者：DMTS• 最简单直观• 单报文同步同步精度低• 广播方式同步能耗低发送者发送者接收者接收者发发送送前前导导码码、同步字同步字嵌嵌 入入 时时标标t0接接收收前前导导码码、、同步字同步字接接 收收ACK接收接收数据数据发发 送送ACK接接 收收处理处理时标时标t1时标时标t2发送时间发送时间访问时间访问时间DMTS（Delay Measurement Time Synchronization） 接收者接收者：RBSReceiverNICSenderCritical PathTimeNICSenderReceiver1Critical PathReceiver2RBS（Reference Broadcast Synchronization） RBS （Reference Broadcast Synchronization） n接收者接收者同步的基本依据：接收者时间相移均值为0单跳RBSn用最小二乘法估计clock skew提高同步精度多跳RBS时间路由技术：基于最短路径查找TPSN（Timing-sync Protocol for Sensor Networks） n否定：DMTSRBSn否定之否定：RBSTPSNnTPSN：双报文交换的发送者接收者同步节点节点A节点节点BT1T4T2T3RequestReply同步点TPSN（Timing-sync Protocol for Sensor Networks） n对同步误差的分析n很重要，是一种基本的分析方法n理论分析和实验证明：TPSN同步误差是RBS的一半n结合对clock skew的估计，可以提高TPSN的精度TPSN（Timing-sync Protocol for Sensor Networks） 多跳TPSNn全网周期性同步n“层发现”把网络组织成最短生成树n逐层在相邻两层节点间同步n网络内两个节点的同步n“后同步”查找两个节点间的路径n在路径的相邻两个节点间进行TPSN同步HRTS（Hierarchy Referencing Time Synchronization Protocol） nTPSN基于双向报文交换，因此同步精度高nTPSN本质上是对同步，因此全网同步的同步能耗高n由DMTS发现，广播能降低全网同步能耗n结合广播和节点间的双向报文交换同步HRTS协议 BS n1 n2 n3 (a) BS n1 n2 n3 (b) BS n1 n2 n3 (c) n4 BS n1 n2 n3 (d) n4 HRTS（Hierarchy Referencing Time Synchronization Protocol） n根节点和应答者节点本质上是采用TPSN同步n根节点和非应答者节点本质上是双向报文交换同步（但非TPSN）n应答者节点和非应答者节点本质上是接收者--接收者同步HRTS（Hierarchy Referencing Time Synchronization Protocol） FTSP（Flooding Time Synchronization Protocol） n同步精度高n工程实用性强n强调实现细节nMAC层时间戳技术n和平台直接相关，书中给出了在Mica2平台下的实现n基本同步原理n发送者--接收者同步n单个报文中包括多个时间戳（在报文的不同位置）n根据单个报文中的多个时间戳，可对中断等待时间进行补偿n对clock skew的补偿仍采用最小二乘法FTSP（Flooding Time Synchronization Protocol） 多跳FTSPn洪泛方式广播时间基准节点的时间n协议健壮n实际做了工程化的实现内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结新型同步机制n基于报文交换的同步机制面临着挑战n同步精度问题n可扩展性问题n新型同步机制n萤火虫同步n协作同步n两个概念n同时性与同步性萤火虫同步1935年，Science1975年, Peskin的RC模型1989年，M&S模型（无延迟）1998年，Ernst（有延迟）结论2005年，真实地实现简单，高效，可扩展性强M&S模型n研究由初始不同步状态如何达到同步状态n个体性质相同,因此一旦达到同步则永远同步n萤火虫之间的交互被建模成电量耦合n耦合延迟规定为0n最终结论为:系统的同步收敛性取决于个体在自由状态下的动力学特性n同步的实质：不同步产生了耦合，耦合改变了状态量，而状态量又改变了相位量 ,相位差通过同步过程不断缩小，最终达到完全相同,即同步状态 M&S模型n证明了全耦合系统的同步收敛性n没有证明多跳网络的同步收敛性Ernst的研究nM&S模型没有考虑耦合延迟，Ernst研究了耦合延迟固定时的情况nM&S模型只研究了正耦合的情况，Ernst还研究了负耦合的情况Ernst--正耦合（2个节点）存在两种情况不可能达到完全同步其实是M&S模型的扩展Ernst--负耦合（2个节点）存在三种情况和Peskin的结论一致结论：考虑固定耦合延迟的情况下，只有负耦合才可能取得同步收敛 负耦合下的全连接网络仿真研究方法和两个节点下的情况不同出现分簇现象其他一些研究与结论n理论上没有突破n单纯的仿真方法意义有限n萤火虫同步技术对耦合延迟、耦合强度、耦合性质、初始相位、网络拓扑等因素很敏感。

虽然在例如两个振荡器的同步收敛性研究上取得了一定的进展，但无论是理论研究还是仿真研究，研究者在某些结论上还不能达成一致的认识但可以认同的一点是：在实际系统中，基于萤火虫同步策略的同步技术会取得在一定误差范围内的同步总结：萤火虫同步n同步可直接在物理层而不需要以报文的方式实现直接用硬件实现，使得同步精度不会受到MAC延迟、协议处理与软件实现等的影响n由于对任何同步信号的处理方式均相同，与同步信号的来源无关，因此可扩展性以及适应网络动态变化的能力很强n机制非常简单，不需要对其它节点的时间信息进行存储萤火虫同步算法的一个限制是要求每个节点具有相似性，但这种机制在非相似节点所组成的网络下能否起到同步的作用，目前还不清楚n此外，由于萤火虫同步的理论研究还远未结束，工程实用性还有待考察协作同步本质：空间平均而非时间平均实现上直接受限于信号处理技术 内容提要1.基本概念2.传统与挑战3.典型时间同步协议4.新型同步机制5.总结总结 n在无线传感器网络中，时间同步不仅要关注同步精度，还需要关注同步能耗、可扩展性和健壮性需求n经典的时间同步协议侧重于同步精度和同步能耗的需求，采用时钟飘移补偿、MAC层时间戳技术以及双向报文交换来提高同步精度，充分利用无线传输的广播特性和捎带技术来降低同步能耗n萤火虫同步和协作同步则侧重于提高可扩展性和健壮性。

非常适合于大规模无线传感器网络的应用 主要参考文献（详见原著）n[1] Elson J., Römer K.. Wireless sensor networks: a new regime for time synchronization. ACM SIGCOMM Computer Communication Review, 2003, 33(1): 149-154.n[3] Elson J., Girod L., Estrin D.. Fine-grained time synchronization using reference broadcasts. In: Proc. 5th Symposium on Operation System Design and Implementation, Boston, 2002, 147-163.n[4] Ganeriwal S., Kumar R., Srivastava M.. Timing-sync protocol for sensor networks. In: Proc. 1st ACM Conference on Embedded Networked Sensor Systems, Los Angeles, 2003, 138-149.n[7] Mills D. L.. Network time protocol (Version3) specification, implementation and analysis. University of Delaware, DARPA Network Working Group Report: RFC-1305, 1992. n[13] Miklos M., Branislav K., Gyula S., Akos L.. The flooding time synchronization protocol. In: Proc. 2th ACM Conference on Embedded Networked Sensor Systems, Baltimore, 2004, 39-49.n[14] Su Ping, Delay measurement time synchronization for wireless sensor networks, Intel Research. Berkeley Lab, 2003.n[19] Dai H., Han R.. TSync: a lightweight bidirectional time synchronization service for wireless sensor networks. ACM Mobile Computing and Communications Review, 2004, 8(1): 125-139.n[26] Li Q., Rus D.. Global clock synchronization in sensor networks. IEEE Transactions on Computers, 2006, 55(2): 214-226.n[34] Ernst U., Pawelzik K., Geisel T.. Delay-induced multistable synchronization of biological oscillators. Phys Review E, 1998, 57: 2150-2162. n[36] Hong Y., Scaglione A.. A scalable synchronization protocol for large scale sensor networks and its applications. IEEE Journal of Selected Areas in Communications, 2005, 23(5): 1085-1099.。