（电路与系统专业论文）无线传感器网络的平均时钟同步技术研究.pdf

摘要 摘要 时间同步机制是无线传感器网络的必要机制和关键技术，近年来受到了越来 越广泛的关注。本文首先分析研究了无线传感器网络的时钟同步这一课题的背景、 必要性及意义，然后主要在分析算法的鲁棒性、扩展性、同步精度以及减少信息 包传递次数、保持能量高效使用上，提出了三个无线传感器网络的平均时钟同步 算法，并对各个算法进行了严格的数学证明和收敛性分析，同时做了实验仿真。 第一个方案a t s p 算法，考虑了相位偏置，频率漂移以及信息传输过程中的随 机延时，并与t p s n 算法做了对比，在数学理论和仿真实验的证明下，说明了该 算法具有的高同步精度，但这是以大量的信息交换为代价的，为了改进这个不足， 我们提出了第二个平均时钟同步的算法。 第二个方案c a t s 算法，受r b s 算法的启发，将传感器网络划分成交互相连 的簇结构网络，提出簇内节点的局部平均时钟同步方法，考虑了相位偏置和频率 漂移，与r b s 算法做对比，有较好的能量保持和同步精度，不过该算法没有考虑 信息传输过程中的随机延时，是比较理想情况下的一种同步算法。 第三个方案a c a t s 算法，受p b s 算法的启发，运用了监听思想，对c a t s 算法中的簇内节点的局部平均时钟同步方法做了改进，减少了簇内节点同步过程 中所需的信息交换次数，同时还考虑了相位偏置，频率漂移以及信息传输过程中 的随机延时，对适用于实际的网络有重要的意义。 本论文选题来源于国家自然科学基金项目( n o 6 1 0 7 2 1 3 9 ) 。 关键字：无线传感器网络平均时钟同步随机延时频率补偿 a b s t r a c t t i m es y n c h r o n i z a t i o ni san e c e s s a r ym e c h a n i s ma n dk e yt e c h n o l o g yi n 眦代j e s s s e n s o rn e t w o f k s ，w h i c hi si n c r e a s i n g l yw i d e s p r e a dc o n c e r n e di nr e c e n ty e a r s b a s e d o n t h er e s e a r c h e so nt h es u b j e c to fw s n s i nb a c k g r o u n d ，n e c e s s i t ya n ds i g n i f i c a l l c ei nt h e f i r s t t h i sp a p e ri sd e v e l o p e d w ep u tf o r w a r dt h r e ea l g o r i t h m s o na v 盯a g en m e s v n c l l r o i l i z a t i o no fw s n s ，m a i n l ya n a l y z i n gt h er o b u s t n e s s ，s c a l a b i l i t y , s y n c h r o n i z a t l o n a c c l l r a c v 孤dr e d u c t i o no ft h en u m b e ro fm e s s a g ee x c h a n g e s ，a n dm a i n t e n a n c ee n e r g y e f f i c i e u ti nu s eo ft h ea l g o r i t h m i na d d i t i o n ，w ei m p l e m e n ts t r i c t m a t h e m a t l c a lp r o o l a i l dc o n v e r g e n c ea n a l y s i st oe a c ha l g o r i t h m ，a n dt h ee x p e r i m e n t a l s i m u l a t i o n1 sa l s o e x e c u t e d i nt h ef i r s ts c h e m ea t s pa l g o r i t h m ，t h ep h a s eo f f s e t ，f r e q u e n c yd r i f ta n dr a n d o m t i m ed e l a y mt h ep r o c e s so fi n f o r m a t i o nt r a n s m i s s i o n a l ea l lc o n s i d e r e d ，a l l dt h e c o n 删e x p e r i m e n t sw i t ht p s na l g o r i t h m i sa l s om a d e u n d e rt h ea n a l y s e s o f m a t h e m a t i c a lt h e o r ya n ds i m u l a t i o ne x p e r i m e n t ，t i m es y n c h r o n i z a t i o n a p p r o a c n o l a t s pa l g o r i t h mi sp r o v e dh i g h a c c u r a c y , y e ta tt h ec o s to f al a r g ea m o u n to fm e s s a g e e x c h a n g e s i no r d e rt oi m p r o v et h i ss h o r t a g e ，w ep u tf o r w a r dt h e s e c o n da v e r a g et l m e s y n c h r o n i z a t i o na l g o r i t h m t h es e c o n ds c h e n l ec a t sa l g o r i t h m ，i n s p i r e db yr b sa l g o r i t h m ，m a k e s ad i v i s i o n o ft h ei i l t e r s e c t c dc l u s t e fs t r u c t u r em o d e lb e t w e e ne a c ho t h e ra b o u ts e n s o rn e t w o r k ，a n a a1 0 c a la v e m g et i m es y n c h r o n i z a t i o na p p r o a c hi na c l u s t e ri sp u tf o r w a r d s i m i l a r l y ，i t a l s oc o n s i d e r st h ep h a s eo f f s e ta n df r e q u e n c yd r i f t ，a n dt h ec o n t r a s te x p e r i m e n t sw l t h r b sa l g o r i t h mi sa l s om a d e ag o o de n e r g yc o n s e r v a t i o na n dh i g hs y n c h r o n l z a l l o n a c c u r a c vi sd e m o n s t r a t e d ，b u tc a t sa l g o r i t h mm a ya p p l yt oa n i d e a lc o n d l t l o n ，n o c o n s i d e r i n gt h er a n d o mt i m ed e l a yi nt h ep r o c e s s o fi n f o r m a t i o nt r a n s m l s s l o n t h em i r ds c h e m ea c a t sa l g o r i t h m ，u s i n g ah e a r - t h o u g h ti n s p i r e db yp b s a l 蛳t ，m a k e sa ni m p r o v e m e n t i nt h el o c a la v e r a g et i m es y n c h r o n i z a t i o nm e t h o dm a c l u s t e r i tr e d u c e st h en u m b e ro fm e s s a g ee x c h a n g en e e d e da m o n g n o d e si nac l 似e rm m es 1 i ，1 1 c h r o n o u sp r o c e s s ，a n di t a l s oc o n s i d e r st h ep h a s eo f f s e t ，f r e q u e n c yd r i f ta n d r a n d o mt i m ed e l a yi nt h ep r o c e s so fi n f o r m a t i o nt r a n s m i s s i o n ，a p p l y i n gt ot h e a c t u a l s e n s o rn e t w o r k s p r o j e c ts u p p o r t e db y t h en a t u r a ls c i e n c ef o u n d a t i o no f c h i n a ( n o 6 1 0 7 2 1 3 9 ) i v a b s t r a c t k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s a v e r a g et i m es y n c h r o n i z a t i o n r a n d o m t i m ed e l a y f r e q u e n c yc o m p e n s a t i o n 第一章绪论 第一章绪论 1 1 研究背景 无线传感器网络最初来源于美国高级国防研究项目署( d a r p a ) 的一个研究项 目，当时处于冷战时期，为了监测敌方潜艇的活动情况，需要在海洋中布置大量 的传感器，使用这些传感器所监测的信息来实时监测海水中潜艇的行动。但是由 于受到当时技术条件的限制，使得无线传感器网络的应用只能局限于军方的一些 项目中，难以得到推广和发展。在当今信息技术飞速发展的时代，微电子技术、 计算技术和无线通信技术等的进步1 2 j 1 3 儿训，推动了低功耗多功能传感器的快速发展， 使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。无线传 感器网络技术涉及众多学科，成为目前信息技术领域的研究热点之一。无线传感 器网络扩展了人们的信息获取能力，将逻辑上的信息世界和客观上的物理世界融 合在一起，将客观世界的物理信息和传输网络结合在一起，为人们提供最直接、 最有效和最真实的信息1 4 j ，具有十分广阔的前景。 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 1 4 j 就是由部署在检测区 域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个自组织的网 络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并 发送给观察者，传感器网络体系结构如图1 1 所示。人们可以通过无线传感网络直 接感知客观世界，从而极大地扩展现有网络的功能和人类认识世界的能力。 图1 1 传感器网络体系结构 点 无线传感器网络的平均时钟同步 传感器模块处理器模块无线通信模块 。忙怔到忖m c h 1 能量供应模块 图1 2 传感器节点构造 传感器节点由传感器模块、处理器模块、无线通信模块和能量供应模块四模 块组成，如图1 2 示，其中能量供应模块通常采用微型电池，仅携带少量有限的能 量，而且由于节点体积微小，使得其处理和存储能力也很有限。这就导致了利用 有限资源处理规模宏大的传感器网络，从一定程度上必须要求提高无线传感器网 络的使用效率1 钔。 由于传感器网络中多数节点是随机放置、无人值守的，导致了即使是进行侦 听通信也会消耗大量能量，使得能量的消耗成为问题。在无线传感器网络中，节 点时钟同步对于路由发送和节能是非常重要的，这是一个公开的研究课题1 5 】1 6 1 。传 感器所获得的数据必须具有准确的时间和位置信息，否则采集的信息也是不完整 的。此外，传感器节点的数据融合、时分多址t d m a 的定时、休眠周期的同步等 都要求传感器节点具有统一的时剐4 。 n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 协议1 7 】是i n t e m e t 上广泛使用的网络时间协议， 但只适用于结构相对稳定、链路很少失败的有线网络系统；g p s 系统能够以纳秒 级精度与世界标准时间u t c ( u n i v e r s a lt i m ec o o r d i n a t e d ) 保持同步，但需要配置 固定的高成本接收机，同时在室内、森林或水下等有掩体的环境中无法使用g p s 系统，因此，考虑到传感器网络的特点，以及能量、价格和体积等方面的约束， 它们都不适合应用在传感器网络中1 4 j 。 j e r e m ye l s o n 和k a yr o m e r 在2 0 0 2 年8 月的h o tn e t s i 国际会议上首次提出 和阐述了传感器网络中的时间同步机制的研究课题，在传感器网络研究领域引起 了广泛关注1 4 】。大学和科研机构纷纷开始对这个领域进行深入研究，提出了多种时 间同步机制，其中r b s ( r e f e r e n c eb r o a d c a s ts y n c h r o n i z a t i o n ) 1 8 1 、t i n y m i n i s y n c l 9 l 和t p s n ( t i m i n g s y n cp r o t o c o lf o rs e n s o rn e t w o r k s ) i lo j 被认为是三种基本的同步 机制1 4 1 。其它一些同步机制还有c l u s t e r - b a s e ds y n c h r o n i z a t i o n t l l 】，l i g h t w e i g h t t r e e b a s e ds y n c h r o n i z a t i o n ( l t s ) t 12 1 ，f l o o d i n gt i m es y n c h r o n i z a t i o np r o t o c o l ( f t s p ) 【1 3 1 ，p a i r w i s eb r o a d c a s ts y n c h r o n i z a t i o n ( p b s ) ! 1 4 】，p c op r o t o c o l 1 5 】s e l f - c o r r e c t i n g t i m es y n c h r o n i z a t i o n ( s c t s ) 0 6 j 以及a d v a n c e ds e l f - c o r r e c t i n gt i m es y n c h r o n i z a t i o n ( a s c t s ) t 1 7 1 ，等等。近年来，受萤火虫同时闪亮的启发，a ne ta 1 提出了耦合振荡 器模型，可应用于无线传感器网络的时钟同步【1 8 】。 第一章绪论 现在越来越多的企业、单位、学者投入到无线传感器网络应用的研究中，实 现时钟同步的方案策略也如泉涌般出现，以期望有更高效、更好的同步机制应用 到实际的网络中。 1 2 设计时钟同步机制考虑的关键因素 通常在传感器网络中，除了非常少量的传感器节点携带如g p s 的硬件时间同 步部件外，绝大多数传感器节点都需要根据时间同步机制交换同步消息，与网络 中的其他传感器节点保持时间同步。在设计传感器网络的时间同步机制时，需要 从以下几个方面进行考虑| 4 】1 1 3 1 ： ( 1 )扩展性：在传感器网络应用中，网络部署的地理位置大小不同，网 络内节点密度不同，时间同步机制要能够适应这种网络范围或节点 密度的变化； ( 2 )稳定性：传感器网络在保持连通性的同时，因环境影响以及节点本 身的变化，网络拓扑结构将动态变化，时间同步机制要能够在拓扑 结构的动态变化中保持时间同步的连续性和精度的稳定； ( 3 )鲁棒性：由于各种原因可能造成传感器节点失效，另外现在环境随 时可能影响无线链路的通信质量，因此要求时间同步机制具有良好 的鲁棒性； ( 4 )收敛性：传感器网络具有拓扑结构动态变化的特点，同时传感器节 点又存在能量约束，这些都要求建立时间同步的时间很短，使节点 能够及时知道它们的时间是否达到同步； ( 5 )能量感知：为了减少能量消耗，保持网络时间同步的交换信息数尽 量少，必需的网络通信和计算负载应该可预知，时问同步机制应该 根据网络节点的能量分布，均匀使用网络节点的能量来达到能量的 高校使用。 1 3 应用前景 随着传感器网络的深入研究和广泛应用，传感器网络将逐渐深入到人类生活 的各个领域。w s n 的应用前景非常广阔1 4 j ： 在军事上应用 由于传感器网络具有可快速部署、可自组织、隐蔽性强和高容错性的特点， 利用传感器网络能够实现对敌军兵力和装备的监控、战场的实时监视、目标的定 位、战场评估、核攻击和生物化学攻击的坚持和搜索等功能。 4 无线传感器网络的平均时钟同步 在环境研究方面 有数种传感器来检测降雨量、河水水位和土壤水分，并依此预测爆发山洪的 可能性，利用传感器网络能够实现对森林环境检测和火灾报告，通过协同合作会 在很短的时间内将火源的具体地点、火势的大小等信息传送给相关部门。 此外，w s n 还能够广泛应用于健康护理，智能家居、建筑物状态监控、复杂 机械监控、城市交通、空间探索、大型车间和仓库管理，以及机场、大型工业园 区的安全检测等领域。 1 4 研究的必要性和意义 在分布式系统中，不同的节点都有自己的本地时钟。由于不同节点的晶体振 荡器频率偏差，以及温度变化和电磁波干扰等，即使在某个时刻所有节点都达到 时问同步，它们的时间也会逐渐出现偏差，而分布式系统的协同工作需要节点间 的时间同步，因此时间同步机制是分布式系统集成框架的一个关键机制【4 1 。 本文的课题研究是使网络各节点时钟以分布式方式同步于网络节点的时钟平 均值，即网络节点收敛于时间平均值。文中介绍的算法主要在鲁棒性、扩展性、 同步精度以及减少信息包传递次数、保持能量高效使用上有所贡献。 ( 1 ) 不依赖网络的阶层结构，是各个节点的时间向周围节点逐层扩散的过程， 这就使算法具有鲁棒性； ( 2 ) 它不依赖于某个固定根节点或外部时钟源，使算法更加稳定、安全；同 时该算法使节点采用分布式的交互通信，可适用于任意规模和结构的网络，自适 应网络拓扑结构的变化，提高了网络的可扩展性； ( 3 ) 基于簇平均的时钟同步算法替代了现有多种协议的阶梯式同步方法，减 少传感器节点之间的包传递次数( 特别是对大规模网络) ，从而减少能耗，延长网络寿 命。 1 5 论文的架构安排 本文在分析无线传感器网络特点的基础上，分析了网络时间同步算法基本原 理，研究了同步的关键技术。论文针对同步误差的主要来源和频率漂移进行了同 步研究，并给出了系统的时钟同步模型。在总结前面方案的优点和不足基础上， 提出了基于改进簇平均的平均时钟同步( a c a t s ) 算法。 本文的主要内容可分为以下几部分： 第一章介绍了无线传感器网络时钟同步的研究背景、关键因素和无线传感器 网络中时钟同步的国内外发展概况，以及必要性和意义。 第一章绪论 第二章介绍了基于成对交换信息实现无线传感器网络的平均时钟同步方法， 考虑了相位偏置、频率漂移和随机延时，以分布式的方式实现了时钟同步，介绍 了算法中应用到的数学基础理论，并分析了算法的收敛性和同步误差的估计，同 时做了实验仿真和与t p s n 算法的对比。 第三章介绍了基于簇平均实现无线传感器网络的平均时钟同步方法，分析了 同步误差来源和相应的数学基础理论，提出建立了簇结构模型，分簇内局部同步 和簇间全局同步两部分介绍了该算法，并分析了算法的收敛性和实验仿真。 第四章在总结前面方案的优点和不足基础上，对减少信息交换次数、降低能 耗以及提高能量使用效率问题上进行了研究，提出了基于改进的簇平均实现无线 传感器网络的平均时钟同步算法。同时也分析了算法的收敛性和同步误差的估计， 并做了实验仿真。 第五章是总结本文算法的优点和不足之处，以及对未来的展望。 第二章基于成对信息交换实现w s n s 的平均时钟同步 7 第二章基于成对信息交换实现w s n s 的平均时钟同步 本章介绍了基于成对交换信息实现无线传感器网络的平均时钟同步方法 ( a t s p ) ，考虑了相位偏置、频率漂移和随机延时，以分布式的方式实现了时钟同 步。首先介绍了算法中应用到的数学基础理论，然后介绍算法的框架与如何实施， 最后分析了算法的收敛性和同步误差的估计，同时做了实验仿真和与t p s n 算法 的对比。 2 1 数学基础理论 假设一个节点的无线传感器网络，用图论中的一个图g ( v ，e ，彳) 来表示这个 传感器网络，其中v = “，1 ；2 ， 是节点集，e = h 】是边集，a = 【a o 】是图g 对 应的邻接矩阵。如果v 和1 ，是邻居，那么口。e 。假设对应的无向图的边的邻接 矩阵元素都是1 ，比如e e 就说口j ，= 1 ，= 0 ，其中江l ，n 。 节点v 的本地时间通常表示为 ( f ) = c w , t + ( o ) ，f = 1 ，n ( 2 - 1 ) 其中，t ( f ) 是节点v 在，时刻的本地时间，是节点v i 内晶体振荡器的频率，c 是 一个常系数，x ，( 0 ) 是f = 0 时的初始时间。时钟模型( 2 1 ) 式【1 9 】等价于文献中的 ( 2 ) 式和文献【2 l 】中的时钟模型。 为了清楚的表达，我们说在传感器网络中一次操作就意味着所有节点或是部 分节点的本地时间和频率更新一次。 定义2 1( 平均时钟同步) 如果传感器网络中所有节点的晶体振荡器都有相同的 频率，或是都可以补偿到一个统一的频率，也就是说w l = w = = w u = w ，那么 网络经过几次操作后，所有的节点时钟可以达到如下的状态： x a v g 。( ，) = c w t + 嘴( x ( o ) ) ，f = 1 ，n ， ( 2 2 ) 其中， a v g ( x ( 0 ) ) = 百1 乙州h , 薯( 0 ) ( 2 - 3 ) 是f = 0 时刻所有节点的平均时间，这时称网络达到了平均时钟同步，称( 2 2 ) 式 是传感器网络在，时刻的平均时间标度。 由( 2 2 ) 式可知，如果所有节点内晶体振荡器的频率是相同的，那么，时刻的 平均时间标度仅与f = 0 初始时刻的平均时间有关。 无线传感器网络的平均时钟同步 假设起始时间为t = 0 ，经过几次操作后，也就是更新所有节点或是部分节点 的本地时钟，那么r 时刻所有节点的时间表达式为 五( f ) = c w t + q ( ，) ) = 刑h 岛( ， ( 2 4 ) x u ( t ) = c w t + 知( ，) 其中，变量t ( f ) 是节点时问偏置， 乞( f ) = t ( ，) 一c w t ，i = 1 ，n ， ( 2 - 5 ) 变量占( f ) 在本章下文对平均时钟同步算法( a t s p ) 的分析和证明过程中都非常重 要和常见。简便地说，称变量，( f ) 为，时刻节点v 的时间偏置。无论传感器网络同 步与否，所有网络节点的本地时间总是随时间流逝而增长的，但( ，) 不会变。因 为由( 2 4 ) 式可知，当网络节点时钟达到同步状态时，变量幺( ，) 是一个常数。因 此，使用变量，( ，) 来代替x i ( ，) 进行分析节点时钟同步的演化过程是非常方便的。 为了使传感器网络达到同步状态，离散化更新网络的节点时钟是有必要的， 也是不可避免的。在传感器网络中经过k 步操作，节点的本地时钟可以表示为 x l ( k ) = c w t ( k ) + q ( 七) ，七) = 洲( 七) + 岛( 扪， ( 2 6 ) h ( 七) = c w t ( k ) + “( 后) 其中，置( 七) 是节点v 经过k 次操作后的本地时间，( 七) 是经过k 次操作后的离散时 间表达。( 2 - 6 ) 式中的f ( 七) 与式( 2 - 2 ) 、( 2 - 4 ) 和式( 2 - 5 ) 中的r 没有什么实际的 不同，只是，( 七) 在离散式子中常用，而，在连续式子中常用。 在式( 2 6 ) 中，t ( 后) 是节点v 经过k 次操作后的时间偏置，那么由式( 2 - 6 ) 可知， q ( 七) = ( 七) 一c w t ( k ) ，f = l ，n ， ( 2 - 7 ) 当t = 0 的时候， e ( 0 ) = 薯( 0 ) ，i = 1 ，n 。 通过比较式( 2 1 ) ( 2 2 ) 和式( 2 4 ) ，很显然可以看到，如果网络达到同步状态， 就有 口曙( x ( o ) ) = 万1 乙脚uq ( 。) = 万1 乙瑚uq ( ，) 。 可推知， 二q ( f ) a v g ( x ( o ) ) = ：。( o ) 。 ( 2 8 ) ( 2 9 ) 第二章基于成对信息交换实现w s n s 的平均时钟同步 9 式( 2 9 ) 表示，如果网络达到平均时钟同步状态，所有节点的时间偏置( ，) 的和 在每次操作前后是一个不会发生变化的。 由以上分析，得到了两个离散形式的引理，它们将在本章的下面部分的算法 收敛证明中用到。 引理2 1 假设经过有限次数的操作，传感器网络最终达到了时钟同步，那么如果 所有节点时间偏置s ，( 七) 的和在每次操作后保持不变，就说传感器网络达到了平均 时钟同步。也就是说 ：。t ( 七) = ：e , ( k - i ) 。 ( 2 1 0 ) 证明：假设经过k 次操作后，网络达到了时间同步，那么有 而( f ) = t ( ，) = = h ( ，) 。 由( 2 - 4 ) 式知，薯( ，) = 丙i 乙州l qt ( ，) = c w t + 土n y i = i e ( ，) 。 ( 2 1 1 ) 因为( 2 1 0 ) 式对于每次操作都成立，就有 ：。乞( 七) = ：。( 七一1 ) = = ：，q ( o ) = ：。一( o ) 。 由式( 2 1 0 ) 和( 2 1 1 ) 知满足了( 2 2 ) 式的条件。由定义2 1 ，引理2 1 得证。 如果式( 2 1 0 ) 在几次操作中不成立，一般来说，网络不能保证可以达到平均 时钟同步。不过可以很容易证实( 2 1 0 ) 式的条件能够满足，在基于比率的同步的 扩散算法和异步的扩散算法中都有1 1 】【2 2 】。 在传感器网络中，为了保证经过一次操作后( 2 1 0 ) 式的条件也能够满足，需 要至少两个节点在此操作中，并更新他们的本地时间，如果只有一个节点更新了 本地时间，那不可避免的必然会不满足( 2 一1 0 ) 式。 引理2 2 假设q ，乞和是三个不全相等的常数，即满足q 岛占，那么 ( q 一) 2 + ( 岛一) l2 ( c 1 + c 2 占) 2 ( 2 1 2 ) 证明：使口= 毛一，6 = 乞一占，那么2 ( 世2- 占) 2 = 2 ( 二a 丁+ b ) 2 = 圭( 口+ 6 ) 2 。 式( 1 2 ) 等价于 口2 + 6 2 j 1 t 口2 + 6 2 ) 或a 2 + 6 2 2 口6 ( 2 - 1 3 ) 显然地，当a b 时，( 口一6 ) 2 0 ，式( 2 1 3 ) 成立。引理2 2 得证。 2 2 基于成对信息交换的时钟同步算法架构 在无线传感器网络中，时钟同步通常可以有广播或成对( p a i r w i s e ) 交换时间 1 0 无线传感器网络的平均时钟同步 信息等方式来达到【8 ，9 ，1o ，1 4 , 2 3 , 1 6 1 。我们在这提出了适用于大规模网络的时钟同步算 法基于成对交换信息实现无线传感器网络的平均时钟同步方法。 为了分析简便，在本节提出了最简单情况时的时钟同步算法，即不考虑频率 漂移和随机延时，这是本章以后几节在数学分析和证明上的基础。算法将在2 2 1 小节中描述，数学分析和证明在小节2 2 2 中。 2 2 1 时钟同步算法 由于不断移动的传感器节点，导致了传感器网络的拓扑也是不断切换的。在 本章中，无线传感器网络的切换拓扑由算法收敛性分析中的切换边来表达。 描述无线传感器网络的图g ( v ，e ，彳) 是个无向图，其邻接矩阵是对称的，p 。e 意味着e 。 我们的同步算法中( 如算法2 1 所示) ，尽管一个节点可能有很多个邻居节点， 但在一次操作中这个节点仅与它的一个邻居节点交换时间信息。无向图或许有很 多条边，但是只有一条或若干条边在一次操作中同时处于通信状态。在数学表达 上，用一个切换信号s ( k ) 来启动哪条或哪几条边在第k 次操作时是处于通信工作状 态的，如何确定边这里有一个约束条件就是每个节点同一时刻只与它的一个邻居 节点进行信息交换。例如，s ( 七) = e l ，e ：。) 表示在第k 次操作有两个边被开启，有 两对节点在分别进行各自的信息交换。s ( 后) = q ，e i 。) 是不允许的，因为节点v 的 两个边都被切换信号激活打破了约束条件，不可行。 在我们的算法中，如果切换信号在第五个时间步激活了一条边e ，那么节点v j 和v ，就彼此发送时间信息五( 七一1 ) 和x ，( 七一1 ) ，然后分别更新它们各自的本地时间 到时间平均值薯( 七) = x j ( k ) = ( t ( 七一1 ) + x ，( j j 一1 ) ) 2 。 算法2 1 基于成对信息交换的平均时钟同步 b e g i n ： 1 切换信号s ( k ) 依次开启传感器网络的每条边。 2 边连接着的两个节点( 比如和_ ) 交换它们的本地时间五( 七一1 ) 和一( 七一1 ) ； 3 两节点更新本地时间为t ( 七) = x j ( k ) = ( t ( 七一1 ) + x ：( k - 1 ) ) 2 。 e n d 2 2 3 收敛性分析 假设一个无向图是连通图，为了分析平均时钟同步算法的收敛性，需要定义 一个能量函数或称l y a p u n o v 函数来描述k 次操作后网络的状态和网络达到平均时 钟同步状态时的差值。 第二章基于成对信息交换实现w s n s 的平均时钟同步 l 1 f ( 七) = ：l 【t ( 七) 一哪( x ( o ) ) 】2 ( 2 1 4 ) 如果能量函数随k 的增加逐渐趋于零，就说传感器网络通过l y a p u n o v 稳定性定理 逐渐达到平均时钟同步状态。显然地，f ( k ) 也是测量同步误差的一种方式。使用 能量函数来分析无线传感器网络的时钟同步是由复杂网络中对同步的研究所启发 的1 2 4 , 2 5 , 2 6 。 定理2 1 假设描述传感器网络拓扑的图是连通图，在k 一的有限时间内，图的 每条边都能够被激活，那么传感器网络将通过算法2 1 渐渐达到平均时钟同步状 态。 证明：不失一般性，假设在第k 个时间步，切换信号激活了节点m 和v 2 之间的连接 边，并且这个两个节点都将自己的本地时间从五( 后- 1 ) 和屯( 七- 1 ) 更新到 x l ( k ) = j c 2 ( 七) = ( 五( 足- d + x 2 ( k - d ) 2 ，网络中其他节点保持不变。由( 2 6 ) 式知， 毛( 七) = ( 七) 一c w t ( k ) = 去( j c l ( 七一1 ) + x 2 ( k 一1 ) ) 一c w t ( k ) 么 ( 2 1 5 ) 1 = - 4 ( e , ( k - 1 ) + 乞( 七一1 ) ) 二 同样地， 1 c 2 ( k ) = 去( 毛( 尼- d + e 2 ( k 一1 ) ) ( 2 1 6 ) 并且t ( 七) = q ( 七一1 ) ，f - 3 ，n 。所以对于这个网络( 2 - 1 0 ) 式是满足的。由引理 2 1 ，如果网络达到时钟同步，那它达到的是平均时钟同步状态。 将式( 2 1 5 ) 和( 2 1 6 ) 代入( 2 1 4 ) 式中，得到 ，( 七) = ：，【( 七) 一a v g ( x ( o ) ) 】2 + 【q ( 七) 一口v g ( x ( o ) ) 】2 + 【s 2 ( 七) 一口v g ( x ( o ) ) 2 -2 = ：，【e ( 七) 一a v g ( x ( o ) ) 】2 + 2 【去( q ( 七一1 ) + i r 2 ( k 1 ) ) 一a v g ( x ( o ) 】 当q ( 七一1 ) 岛( 七一1 ) 或五( 七一1 ) x 2 ( k 1 ) 时，由引理2 2 可得， ，( 七) f ( k 1 ) ( 2 1 7 ) 式( 2 1 7 ) 表示，如果在第k 个时间步切换信号激活了两节点的连接边，并且 两节点的本地时间是不同步的，那么能量函数f ( k ) 本质上是会减小的。因为无向 图是连通的，并且每条边都能够被激活，能量函数f ( k ) 最终会趋近于零，网络会 达到平均时钟同步。若干条边在同一时刻被激活的情况的证明也是相同的。定理 2 1 得证。 推论2 1 可以由定理2 1 直接得到，这是算法2 1 能够达到平均时钟同步的另 一种判定准则。 推论2 1 假设描述传感器网络拓扑的图是连通的j 在有限的时间段丁内图的每条边 无线传感器网络的平均时钟同步 至少被激活一次，那么传感器网络将通过算法2 1 逐渐达到平均时钟同步。 证明：因为在有限的时间段丁内，每条边都会被至少激活一次，那么在随k 一的 无限时间里必然会被激活，这样直接由定理2 1 得证。 对于平均时钟同步的扩散算法1 2 2 1 ，许多节点在同一时刻的操作中同时通信( 如 算法2 3 和证吲2 2 j ) 。如果在无限的时间里图的每条边都会被激活，那么平均时钟 状态同步也能够达到。 2 2 4 仿真实例 由( 2 4 ) 式知，如果网络达到同步，那么节点的时间偏置都相等， q ( ，) = 岛( ，) = = s ( ，) ( 2 - 1 8 ) 再由( 2 1 4 ) 式可知，如果网络达到同步，那么节点的时间偏置都相等，且是常数 毛( ，) = e 2 ( t ) = = 知( ，) = a v g ( x ( o ) ) ( 2 1 9 ) 另一方面，如果( 2 1 9 ) 式成立，由式( 2 - 4 ) 可以得到式( 2 - 2 ) ，由定义2 1 网络 达到平均一致性。式( 2 1 9 ) 是能否达到平均时钟同步的充分必要条件。 如果节点的时间偏置e ( ，) 都相等，也就是( 2 1 8 ) 式成立，那么由( 2 - 4 ) 式 网络能够达到时钟同步。但是，网络能否达到平均时钟同步要由( 2 1 9 ) 式判定。 为了在分析和计算机仿真上能方便的检测是否达到了平均时钟同步，引入了一个 新的变量屈( ，) ，由( 2 1 9 ) 式，使得 屈( ，) = ( ，) 一a v g ( x ( o ) ) ，待1 ，n ( 2 - 2 0 ) 其中，屈( ，) 是能探知平均时钟同步状态的变量，称为偏置差量。如果所有的偏置 差量屈( f ) 趋近于零，就说网络达到了平均时钟同步；如果所有的偏置差量屈( f ) 趋 近于一个常数，而不是零，也说网络达到了时钟同步，但不是平均时钟同步。用屈( f ) 的离散形式屈( 七) 来表示网络节点经过k 次操作后的偏置差量。显然，屈( 七) 和 i 屈( 七) i 也是测量平均时钟同步误差的一种方式。 演示一个1 0 节点的传感器网络的简单实例，如图2 1 所示，假设其节点频率 是相同的。在，= 0 的初始时刻，1 0 节点的本地时间分别为：0 0 3 5 0 ，0 8 7 1 0 ，1 2 2 8 3 ， 2 6 1 2 2 ，- 0 8 5 7 3 ，- 0 5 2 2 6 ，1 5 3 7 8 ，0 11 0 2 ，0 8 8 1 3 ，和o 8 1 5 5 ，这些初始时间是 由计算机随机生成的，服从均值为0 5 方差为l 的高斯分布。设切换信号s ( k ) 周期 的开启图2 1 中的每条边，每次只开启一条边。当图2 1 中所有边都开启过一遍后， 开始下一个循环，依此进行下去。仿真结果如图2 2 所示，大约每条边经过1 5 次 操作后，所有节点的时间偏置( ，) 都趋近于0 5 ( 如图2 2 ( a ) 示) ，此时网络达 到了时钟同步。图2 2 ( b ) 显示了所有节点的偏置差量的变化曲线，即大约每条 边经过1 5 次操作后，节点的偏置差量都趋近于零，所以说网络达到了平均时钟同 第二章基于成对信息交换实现w s n s 的平均时钟同步 1 3 步。 v v 4 图2 1 传感器网络拓扑图 陟 1 ；j f ! i o51 0 5加为衢40 每条边上的切换次数 ( a ) 节点的时间偏置随每条边上操作的次数的变化 【! 蕤 夥9 051 0 52 02 5 3 0 筠4 0 每条边上的切换次数 ( b ) 节点的时间偏置差量随每条边上操作的次数的变化 图2 2 网络的平均时钟同步 2 3 具有随机延时的时钟同步 在上一节中，算法2 1 忽略了信息延时。实际上，从发送信息到接收到信息， 延时包括发送时间、访问时间、传播时间和接受时间【2 7 1 2 引。信息延时在t p s n 1 0 l 3 弱 2 协 ， 帖 o ：宝 j 掌制增u瓢粤厘鲁 ：；3 2 ， o 帖 。 惦 晕锹3触靳瓢摹星莒 1 4 无线传感器网络的平均时钟同步 中分解为发送时间( s e n d ) 、访问时间、传送时间( t r a n s m i s s i o n ) 、传播时间 ( p r o p a g a t i o n ) 、接待时间( r e c e p t i o n ) 和接收时间( r e c e i v e ) 。信息延时的不确定 性是导致同步误差的主要来源【2 9 1 。在本节中，具有延时的算法将在2 3 1 小节中介 绍；带有固定延时和随机延时的算法的理论分析将分别在2 3 2 和2 3 3 小节中描 述；与t p s n 算法的性能比较叙述在2 3 2 小节。 2 3 1 时钟同步算法 具有包延时的成对信息交换同步机制在t p s n ，l t s ，t s y n c 和t s m s 等算法 中已经介绍了，图2 3 ( a ) 说明了它信息传递的基本步骤： 1 节点v 在本地时间z 时给节点1 ，发送一个数据包，节点，在本地时间乃时接 收到这个数据包，那么不= 五+ d + 6 ，其中d 和6 分别是包延时和两节点的相 位偏置。 2 节点1 ，在本地时间五时发还给节点u 一个确认包，其中包含有乃和五信息。 节点v 在本地时间瓦时接收到这个确认包，其中瓦= 五+ d 一6 。 经过两次数据包的发送与接收，节点v 能够计算出包延时 d = ( 瓦一五+ 瓦- t , ) 2 和相位偏置万= ( 五一瓦+ 互一7 ；) 2 。然后节点b 可以调节本 地时钟，将本地时间更新到节点1 ，的本地时间1 2 8 1 1 2 9 1 。 为了实现平均时钟同步，节点v | 不能不将包延时d 和相位偏置万再发送给节点 ，这样开始了第三个数据包的传送，如图2 3 ( b ) 示。 1 第一个数据包。节点v 将它自己的本地时间正时发送给节点v ，节点，在本 地时间乃时接收到这个数据包，那么正= z + 吐+ 万。这个是与传统的传递方法 相同的。 2 第二个数据包。节点1 ，在本地时间兀时发还给节点m 一个确认包，其中包含 有乃、正和4 信息。节点v j 在本地时间瓦时接收到这个数据包，并更新自己 的本地时间为= ( 五十五+ 碣+ 破) 2 ，其中正= 五+ 4 万，d 2 = 五一互，这样 可以计算出4 = ( 正一五十乃一正) 2 。 3 第三个数据包。节点v 在本地时间不时发还给节点v ，这第三个包，其中包含 有瓦、巧、正和西信息。当节点v ，在本地时间瓦接收到数据包时，便更新 自己的本地时间为r = ( 五+ 瓦+ 4 + 吃) 2 ，其中以= 正一五。 节点v j 节点v i t l 7 乃 l d 一 dj 7 ( a ) 传统的两个数据包的的传递方案 第二章基于成对信息交换实现w s n s 的平均时钟同步 1 5 节点v j 节点v i x f j ( k q d 2 r t 6 对 7 刁 弋sl 乃 d 3 飞、 卜d ，一 x s f ( 后一1 )一d 1 专 ( b ) 平均时钟同步的三个数据包的传递方案，f = 4 + 破 图2 3 节点m 和间具有包延时的成对信息交换 假