（计算机科学与技术专业论文）无线传感器网络时间同步算法研究.pdf

摘要 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟，无线 传感器网络这种由传感器、微处理器和无线通信接口组成的，集数据采集、融合 处理和通信为一体的网络，在国防军事、环境监测、医疗卫生、家庭护理、空间 探索和灾难拯救等领域都显示了广阔的应用前景，已经引起了许多国家学术界和 工业界的高度重视，成为当前国际上备受关注的研究热点。 时间同步作为无线传感器网络应用的一项支撑技术，对无线传感器网络的设 计和应用都是关键的，而传统的同步方法n ，r p 和g p s 因复杂度和能量问翘、代价 及尺寸因素都不适合传感器网络使用。由于传感器节点受到成本、能量和体积的 限制，使得无线传感器网络的时间同步遇到了很多新的挑战，研究适合传感器网 络的时间同步方法得到国内外传感器网络研究领域的广泛关注。 本文是围绕无线传感器时间同步算法展开研究的。首先，分析无线传感器网 络时间同步的必要性、同步的基本原理、存在的挑战性、算法的评价指标以及设 计要素。然后，研究了现有的同步技术并对其进行分类，深入研究了一些有代表 性的算法并对其优缺点进行分析评价和比较。在此基础上，本文提出了一种适合 密集网络的既简单又节能的时间同步算法，该算法结合了单向广播同步机制和双 向成对同步机制，使网络中节点单跳广播域内只有一个下层节点与之进行双向成 对同步，并采用在m a c 层标记时闻使算法达到了较好的精度。与t p s n 算法相比， 该算法有效地利用了网络中节点广播的信息，并大大减少了时间同步的消息交换 开销，这对无线传感器网络来说是个很大的改进。通过仿真结果可以看出，该算 法具有较低的消息交换开销和不错的同步精度。在时间同步算法实现方面，也做 了初步探索，为进一步研究奠定了良好的基础。另外，文章还从安全角度出发， 分析研究了现有同步机制可能受到的威胁以及相应的对策。在本文的最后，对全 文做了总结。 关键字：无线传感器网络，时间同步算法，安全攻击 a b s t r a c t i r c n l c n d o l l sa d v a n c e si nc o m m l i n i c a t i o n 曲1 b e d d e dc o m p i l t a t i o n 粕d 舢o r t c c h n o l o g yh a v eo c c 埘e di l l 也ed e v e l o p m e n to f 谢r c l e s ss s o r 触，w h i c hi s m a d eb ys 盯l s o r s ，m i c r o p r o c e s s o ra n dw i r e l e s sc o m m i 】n i c a 缸o ni n t e r f h ，趴d 妇v e i n t e g r a ：c c dc o u e c 缸g ，p r o c e s s i n ga 1 1 dc o m m u l l i c a t i o na i l - i n - e ah u g es u r g eo f 硫饿s t i nt h i s 丘i e dh 髂b c 吼t r i g g e r e d b yl a 蝎ep o t 衄t i a li na 诵d c 瑚g e o f 印p n c 撕。璐s u c h 鹳： m i l i t f 町洲v e n l 锄c e ；e n v h o n l e n t a lm o n i t o r i i l g ；m e d i c a ls a n i 协t i o n ；p h y s i o l o g i c a l m o n i t o r i i l g ；s m a r ts p e s ；仃a g e d ys a l v a t i o n a n di ta l s oh a sb 蝴h i g h l yv a l u e db y a c a d 眦i c 锄di n d u 姗a lf i e l d s t i m es y n c h r o n i z a t i o ni saf i l n d 锄髓t a 王s e r 、，i c ef o rb o t hd e s i 弘a n da p p l i c a t i o no f w i r c l e s ss e l i s o rn 吐w o r k s h o w e v e r ，t h ec o m p l e x i 吼吼e 玛y c o s ta n ds i 臻c 删c t s b e 骶e n 仃a d 砸o n a la l g o 埘吼s u c h 鹤n t pa n dg p s 眦dw s np r o h i b i tm e i r 唧i n w s n b e c a l l s eo f t h ec o s t ，p o w e ra n ds i z cc o 璐打础1 协o f 也ei n d i v i d u a in o d e s ，t 王l e 撇 衄m yn e wc i l a _ n e l l g e s d “e l o p m gt i m es y n c h r o n i z 瓶o nm e m o d ss u i t a ：b l ef o rw h l e s s s e n s o rn e 咖r k sh a v ea 1 陶旧c t e dw i d ea n e n t i o n t h er c s e a r c ho ft h i st 圭l e s i si st i m es y n c l l l 0 n j z a 廿o ni nw i r e l 鹤ss e n s o rn e 咖r k s f i r s t ，也en e c e s s i 吼f 洒d a m e n 锄p r i n c i p l e s ，c x i s t e dc h a l l e l l g e s ，c 、，a l u 撕o nc r i t e r i o no f t h ep 盯f b n n a n c ea n ds o m ei n l p o r t a l l ti nd e s i g no f 缸es y n c b r o n i z a t i o na r cd e s c r i b e d t h e n ，s n l d ye ) 【i s t i i l gt e c l l i l o l o 萄e so f 缸璩s y n c h r o n i z a 主i o na n dc l a s s i 母t h e m s o m e r e l ，r e s e n 嘶v es ) ，l l c 圭l r o n i z a t i o na l g o r i t h m sa r cd i s c 瑚s e dd e 印l y b 鹤e do nn l e s e ，an o v e l s i i n p l e 锄dl o wc o s t 廿i n es y n c h r o n i z a t i o na l g o r i i l l m ，w i l i c hi s s u i 诅b l ef o rd e i l s e 邛蜘r k ，i sp 1 e s e n t e d i tc o m du l l i d i r c c t i o n a 王r e f 孤c eb r o a d c a s t 粕dp 缸w i s e m e c h a l l i s m ，s ot l l a to i l l yo n en o d ei nb r o a d c a s td o m a i nn e e d s 血n es y n c l l r o 捌o nt o 妣 t i m e s t a m p i n ga tm a cl a ) ，e rm 缸砖i ta c h i e 、n 姻ag o o dp r c c i s i o n c o m p a r e dt ot p s n ， o u ra l g o r i t l l i nm a k e s9 0 0 du s eo fb r o a d c a s ti l l 】f b 珊a t i o n ，a i l d d u c e sc o 删删c a t i o n m e s s a g e sg r e a d y s i m l l l a t i o nr e s u 蛔s h o wt h 砒i th 鹊ag o o dp r e c i s i o n 眦dl o wm e s 船g o c o s t a f i e rt l l a t ，w ei m p l e m e n t e dn e wa l g o r i t h mo no u rt e s “) c d s i l ia d d i t i o nt ot h e ， w ea l s oa i l a l y z et i ：m es y n c h r o n i z a t i o ni n 铷so fs e c u r i t y f i n a l l y w es m m n a r i z e dt l l i 3 p a p e l k 锣w o r d s ：w i r e l e s ss e 璐o rn 娟v o r k ，1 恤es y n c h r o n i z a t i o n ，s e c i l r i t y 甜a c l 【3 西北工业大学业 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属于西北工业大学。学校有权保留并向国家有关部门或机构送交论文的复印件 和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关 数据库进行检索。可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时本人 保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名：羞幽l 竭 指导教师签名： 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明；所呈交的学位论文。是本 人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 和致谢的地方外，本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果， 不包含本人或其他已申请学位或其他用途使用过的成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式表明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任 学位论文作者签名：蕉型翊 弦呷年3 月夕日 西北工业大学硕士论文第一章引言 1 1 研究背景 第一章引言 低功耗无线通信技术、嵌入式计算技术、微型传感器技术及集成电路技术的 飞速发展和日益成熟，使得大量的低成本微型传感器通过无线链路自组织成无线 传感器网络成为现实。无线传感器网络是由散布在工作区域中大量小体积、低成 本、具有无线通信、传感和数据处理能力的传感器节点组成的。每个节点可能具 有不同的感知形态，如声纳、振荡波、红外线等，节点可以完成对目标信息的采 集、传输、决策制定与实施，实现区域监控、目标跟踪、定位和预测等任务。无 线传感器网络作为一种具有传感能力的网络，并不是简单的将传感器连接网络构 成，它综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技 术，能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的 信息，并对这些信息进行处理，获得详尽而准确的信息，传送到需要这些信息的 用户，从而实现“无处不在的计算”理念【l j 。由于无线传感器网络集数据的采集、 传输、融合分析于一体，是信息技术的一个新领域，在环境监测、医疗监护、城 市交通管理、仓储管理、军事侦察等领域具有广阔的应用前景，被认为是2 l 世纪 最重要的技术之一，它将会对人类未来的生活方式产生深远影响【2 】2 0 0 3 年2 月 份的美国技术评论杂志【3 】评出对人类未来生活产生深远影响的十大新兴技术， 无线传感器网络即被列为第一。2 0 0 4 年i e e es p e c t r u m 杂志发表一期专集传 感器的国度，论述无线传感器网络的发展和可能的广泛应用。近年来无线传感器 网络得到越来越多的应用： 1 军事应用 由于无线传感器网络具有快速布设、无基础设施、自组织能力和自容错等特 性，使其将会成为c 4 i s r t ( c o m l n 觚d ，c o 曲砒c o 咖m l n i c a t i o n ，c 鲫刖t i l l g h l t e l l i g e n c e ，s u n ，c i l l a n c e ，r e c o 珊i a i s s 锄c ea n dt a r g e 血g ) 系统不可或缺的一部分。 c 4 i s r t 系统的目标是利用先进的高科技技术，为未来的现代化战争设计一个集命 令、控制、通信、计算、智能、监视、侦察和定位于一体的战场指挥系统，因此 受到了军事发达国家的普遍重视。因为无线传感器网络是由密集型、低成本、随 机分布的节点组成的，自组织性和容错能力使其不会因为某些节点在恶意攻击中 的损坏而导致整个系统的崩溃，这一点是传统的传感器技术所无法比拟的，也正 是这一点，使无线传感器网络非常适合应用在恶劣的战场环境中，包括监控我军 西北工业大学硕士论文第一章引言 兵力、装备和物资；监视冲突区；侦察敌方地形和布防；定位攻击目标；评估损 失；侦察和探测核、生物和化学攻击。在战场，指挥员往往需要及时准确地了解 部队、武器装备和军用物资供给的情况敷设的传感器将采集相应的信息，并通 过汇聚节点将数据送至指挥所，再转发到指挥部，最后融合来自各战场的数据形 成我军完备的战区态势图。在战争中，对冲突区和军事要地的监视也是至关重要 的，通过铺设传感器网络，以更隐蔽的方式近距离的观察敌方的布防；当然，也 可以直接将传感器节点撒向敌方阵地，在敌方还未来得及反应的时间内迅速收集 利于作战的信息。 2 0 0 5 年美国军方成功测试了由美国c r o s s b o w 产品组建的枪声定位系统，节点 被安置在建筑物周围，能够有效地按照一定的程序组建成网络进行突发事件( 如 枪声、爆炸源等) 的监铡，为救护、反恐提供了有力手段。 2 环境的监测和保护 随着人们对于环境问题的关注程度越来越高，需要采集的环境数据也越来越 多，无线传感器网络的出现为研究数据获取提供了便利，并且还可以避免传统数 据收集方式给环境带来的侵入式破坏。无线传感器网络可以跟踪候鸟和昆虫的迁 移，研究环境变化对农作物的影响，监测海洋、大气和土壤的成分，也可以进行 森林火灾监测、洪水监测等。其中，美国研制的a l e r t 系统【4 l 就是用无线传感器 网络进行洪水监测的一个例子。在该系统中，研究人员开发了监测降雨量、水位、 天气等环境条件的传感器，这些传感器通过预定义的方式向中心数据库提供信息 并以此预测山洪暴发的可能性口】。另外，澳洲科学家利用无线传感器网络来探测北 澳大利亚蟾蜍的分布情况。用蟾蜍的声音作为检测特征，将采集到的信号在节点 上就地处理，并将处理后的数据发回到控制中心，通过处理来了解蟾蜍的分布、 栖息情况。 3 医疗护理 无线传感器网络也可以应用在医疗研究、护理领域，并为未来的远程医疗提 供了更加方便、快捷的技术实现手段。它在医疗中的应用包括：患者的综合检测、 诊断，医院的药品管理，对人类生理数据的无线检测，在医院中对医护人员和患 者进行追踪和监控。， ， 英特尔公司推出的无线传感器网络的家庭护理技术就是作为探讨应对老龄化 社会的技术项目c e n t e rf o ra g i n gs e r v i c e st e c h n 0 1 0 9 i e s ( c a s t ) 的一个环节 开发的。该系统通过在鞋、家具以家用电器中嵌入半导体传感器，帮助老龄人士、 阿尔茨海默氏病患者以及残障人士的家庭生活。利用无线通信将各传感器联网可 高效传递必要的信息从而方便接受护理，而且还可以减轻护理人员的负担。 2 西北工业大学硕士论文第一章引言 4 工业控制及监测 现代化的生产车间以及厂房、仓库都需要对温度、压力、以及其他跟设备有 关的数据进行监测，利用无线传感器网络可以有效降低成本，提高系统的可靠性。 在一些特殊的工业场合如矿井、核电厂等，工作人员可以通过它来实施安全监测。 英特尔正在对工厂中的一个无线网络进行测试，该网络由4 0 个传感器节点上的2 l o 个传感器组成，这样组成的监控系统将可以大大改善工厂的运作条件。它可以大 幅降低检查设备的成本，同时由于可以提前发现问题，因此能够缩短停机时间， 提高效率，并延长设备的使用时间。 5 ，空间探索 无线传感器网络技术为空间探索提供了一个有效的信息获取手段，借助于航 天器布撒的传感器网络节点实现对星球表面长时间的监测，应该是一种经济可行 的方案。n a s a 的j p l ( j c tp r o p l l l s i o nl a b o r a t o 啪实验室研制的s e 璐0 rw c b s l 6 】就是 为将来的火星探测进行技术准备的，已在佛罗里达宇航中心周围的环境监测项目 中进行测试和完善。 6 其他领域 在其他的商业领域，无线传感器网络也有广阔的应用前景，如智能家居，城 市交通拥堵的实时监控，沙尘环境的监控，水源污染监控，森林火灾监控，城市 车辆监控和跟踪，在仓储管理、工厂自动化生产线等众多领域，无线传感器网络 都会孕育出全新的设计和应用模式。 由于无线传感器网络的巨大应用价值和广阔的应用前景，使它引起了世界许 多国家军事部门、工业界和学术界的广泛关注。美国国防部和各军事部门在c 4 i s r 的基础上提出了c 4 i s r 计划，强调战场情报的感知能力、信息的综合能力和信息 的利用能力，把w s n 作为一个重要研究领域，并设立了一系列计划，如2 0 0 1 年 的“灵巧传感器网络通信”计划，美国海军开展的网状传感器系统( c e c ，c 0 0 p c r a 廿v c c n g a g 黜e n tc 印a b i l 妨) 。n s f ( 美国自然科学基金委员会) 在2 0 0 3 年制定了w s n 研究计划，投资3 4 0 0 万美元支持相关基础理论的研究。在n s f 的推动下，美国的 加州大学伯克利分校、洛杉矾分校、麻省理工学院、洛克威尔研究中心等机构开 始了w s n 的基础理论和关键技术研究。英国、日本等国家的一些大学和研究机构 也纷纷展开了该领域的研究工作，并取得了一定的成果。目前研究的热点、难点 包括：设计小型化的节点设备；开发适合传感器节点的嵌入式实对操作系统；无 线传感器网络体系结构及各层协议；时间同步机制与算法；网络节点的自身定位 算法和以其为基础的外部目标定位算法等。国内研究机构如中科院、黑龙江大学、 浙江大学等也展开了这方面的研究，而且越来越多的高校掀起了这股研究热潮。 西北工业大学硕士论文 第一章引言 尽管无线传感器网络研究已经取得了不少成果，但作为一个刚刚兴起的研究 领域，无线传感器网络的技术和应用还不十分成熟，要达到希望的要求还会有很 长一段发展历程，有待继续研究开发。 1 2 无线传感器网络的时间同步问题 时间同步是任何分布式系统的一个重要基础，也是无线传感器网络的一项基 础支撑技术。在无线传感器网络的应用中，传感器节点采集的数据如果没有空间 和时间信息是无任何意义的。准确的时间同步是实现传感器网络自身协议的运行、 数据融合、t d m a 调度、协同睡眠、定位等的基础【 姗。 传感器网络中节点间通常需要相互协作以减少数据传输，这对传感器网络能 量的充分利用非常重要。统一的物理时间是对节点的基本要求，它用来推断现实 世界中发生的事件。例如，需要精确的时间来测量声音的传播时间；形成分布式 波束成形阵列：构成低能量t d 凇无线调度；多传感器节点时序信息的融合来进行 速度估计；识别不同节点对同一事件的重复探测来压缩冗余信息。除了这些特定 领域的要求外，传感器网络应用通常依赖于同步作为典型的分布式系统来进行数 据库查询、加密和验证方案、未来行动的协调、与用户交互、系统调试时有序的 日志事件等等。 无线传感器网络中对同步时间的诸多需求使得它成为一个关键性的基础服 务。然而，这些需求的多样性使得时间同步成为一个难以解决的问题。不同的应 用对时间同步的精确度、寿命、范围、可用性以及能量开销等方面的要求也是有 相当大的差别的。例如，声音应用要求精度达到几微秒，而传感任务则是以小时 或天为时间标度的。局部协作仅需要邻接点闻的同步，两全局协作则需要全局时 闯同步。事件触发可能仅需要瞬时同步，而数据记录或调试则经常需要长期一致 的时间标度。与用户的通信需要外部的人工时间标记如u t c ( 1 1 1 1 i v e r s a lt i m e c o o r d i n a t e d ，世界协调时间) ，而相对时间则对单纯的网内比较重要。一些节点有 大电池且一直可以运行，而其他的电池非常有限以至于它们只是偶尔地工作，读 取一个传感器读数并传送出去，随后又立即进入睡眠状态。 即使在传统的分布式系统中，构造一个能满足如此广阔应用需求的同步方案 也是很有挑战性的。在无线传感器网络中，加上能量有效、可扩展性和动态自适 应性这些额外需求使得这个任务变得更加困难。无线传感器中的悖论就是，它们 对时间同步的要求比传统的分布式系统要高得多，而同时又缺少达到同步所需的 资源。这个饽论使得传统的时间同步方案不适合无线传感器网络。而且这些综舍 因素的影响使得无线传感器网络的时间同步比传统的时间同步要困难得多。 i n t e r n e t 上广泛使用的n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 协议l i l 】，只适用于结构 4 西北工业大学硕士论文第一章引言 相对稳定、链路很少失败的有线网络系统；g p s ( g l o b a lp o s “i o i l i l l gs y s t e m ) 【1 2 i 系统 能够以纳秒级的精度与世界标准时间u t c 保持同步，但需要配置固定的高成本接 收器，同时在室内、森林或水下等有遮盖物的环境中无法使用。因此，他们都不 适用于传感器网络【”j 2 0 0 2 年8 月，j ，e 1 s o n 和k r o m e r 在h o t t s 这一影响未来网络研究发展 方向的国际权威学术会议上首次提出和阐述了无线传感器网络中的时间同步的研 究课题，引起了无线传感器网络研究领域的广泛关注。经过近几年的不懈努力， 至今已经提出了多种时间同步算法【1 3 】【1 4 l 。纵观这些算法主要可以分为以下三类嗍t 基于接收者一接收者( r e c e i v e r r e c e i v e r ) 的同步算法，基于成对( p a i r l i s e ) 同步的双向同步算法和基于发送者一接收者( s e n d e r _ r e c e i v e r ) 的单向同步算法。 它们用不同的方法来解决无线传感器网络中节点的时间同步问题，支持不同的应 用，同时在能量需求、基础设施和时空复杂度方面也各有不同。因此，时间同步 这一研究领域尽管在国外已经有研究，但并不成熟，国内的研究也才刚刚开始， 还处于初级阶段。 1 3 研究内容及论文组织 作为无线传感器网络重要的支撑技术之一，无线传感器网络时间同步问题的 研究具有非常重要的意义。本文对已有的无线传感器网络时间同步技术和算法进 行了深入的研究，跟踪了国内外在该领域的研究进展，在此基础上提出了一种新 的时间同步算法，并进行了仿真验证。对于在实际的原型实验平台上实现时间同 步算法也做出了初步的探索。 论文组织如下 第一章主要介绍了研究背景和研究意义以及具体的研究内容，由此引出了后 面的具体研究内容。 第二章论述了无线传感器网络时间同步算法的基本原理、性能要求以及评价 标准，为后面的研究工作提供良好的基础。 第三章综述了无线传感器网络时间同步算法的分类方法以及典型的时间同步 算法，并对它们作以分析评价和比较。 第四章详细介绍了一种新的简单节能的时间同步算法，并进行了仿真验证， 对算法的性能进行了综合分析。 第五章介绍了在实际的原型实验平台上实现的同步算法，对同步算法在实用 性方面做出了初步的探索，并为将来实现其他同步算法提供了研究基础。 第六章论述了无线传感器网络时间同步可能遭受的攻击以及应对策略。 最后对全文进行了总结。 5 西北工业大学硕士论文第二章无线传感器网络时间同步的基本原理 第二章无线传感器网络时间同步的基本原理 准确地估计消息包的传输延迟，通过偏移补偿或漂移补偿的方法对时钟进行 修正，是无线传感器网络中实现时间同步的关键。目前，绝大多数现有的时间同 步算法都是对时钟偏移进行补偿的。也有对漂移进行补偿的，后者精度相对较高 但实现比较困难。本章从分析影响时间同步的关键因素入手，通过分析节点时钟 问的关系，论述用偏移补偿和漂移补偿进行时间同步的原理，最后分析无线传感 器网络时间同步设计面临的挑战以及算法性能评价指标。 2 1 影响时间同步的关键因紊 在无线传感器网络中，为完成节点间的时间同步，消息包的传输是必须的。 为更好地分析包传输中的误差，可将消息包收发的时延分为以下六部分【8 16 】： 发送节点 接收节点 s 饥d n m oa c s st i m et 哪s m i s s j o n 岫e +卜 t 蛳e r e c 印吐o n 虹m c r e c e v e 廿m e 图2 一l 信息收发时延分解 ( 1 ) 发送时间( s e n d l 洳e ) ：发送节点构造一条消息和发布发送请求到m a e 层所需时间，包括内核协议处理、上下文切换时间、中断处理时间和缓冲时间等， 它取决于系统调用开销和处理器当前负载，可能高达几百毫秒。 ( 2 ) 访问时间( a c c e s st i m e ) ：消息等待传输信道空闲所需时间，即从等待 信道空闲到消息发送开始时的延迟，它是消息传递中最不确定的部分，与低层m a c 协议和网络当前负载状况密切相关。在基于竞争的m a c 协议如以太网中，发送节 点必须等到信道空闲时才能传输数据，如果发送过程中产生冲突需要重传。无线 局域网8 0 2 1 1 协议的r t s c t s 机制要求发送节点在数据传输之前先交换控制信 息，获得对无线传输信道的使用权：t d m a 协议要求发送节点必须得到分配给它 的时间槽时才能发送数据。 ( 3 ) 传输时间( t r a n s m i s s i o nn m e ) ：发送节点在无线链路的物理层按位( 矗秘 发射消息所需时间，该时间比较确定，取决于消息包的大小和无线发射速率。 6 西北工业大学硕士论文第二章无线传感器网络时间同步的基本原理 ( 4 ) 传播时间( p m p a g a t i o n1 硒e ) ：消息在发送节点到接收节点的传输介质 中的传播时间，该时间仅取决于节点间的距离，与其他时延相比这个时延是可以 忽略的。 ( 5 ) 接收时间( 融p t i o nt i m e ) ：接收节点按位( 五i 0 接收消息并传递给m a c 层的时间，这个过程和( 3 ) 相对应。 ( 6 ) 接收处理时间( r - e c c i v en n e ) ：接收节点重新组装消息并传递给上层应 用所需的时间，包括系统调用、上下文切换等时间，与( 1 ) 类似。 2 2 基本原理 传感器网络中节点的本地时钟依靠对自身晶振中断计数实现，晶振的频率误 差和初始计时时刻不同，使得节点之间的本地时钟不同步。如果能估算出本地时 钟与物理时钟的关系或者本地时钟之间的关系，就可以构造对应的逻辑时钟以达 成同步。 节点时钟通常用晶体振荡器脉冲来度量的，所以任一节点f 在物理时刻f 的本 地时钟读数可表示为： 啪) = 去j ：他) 机砒) 公式( 2 1 ) 其中，( f ) 是节点f 晶振的实际频率，五为节点晶振的标称频率，f 0 代表开 始计时的物理时刻，c ，“) 代表节点f 在，o 时刻的时钟读数，是真实时间变量， c f ( f ) 是构造的本地时钟，间隔c ( f ) 一c ( f o ) 被用来作为度量时间的依据。由于节 点晶振频率短时间内相对稳定，节点时钟又可表示为： c l ( r ) = q o 一岛) + 6 ， 公式( 2 2 ) 对于理想的时钟，我们有，( f ) = 如( f ) 次= l ，也就是说理想时钟的变化速率 r ( f ) 为l ，但工程实践中，因为温度、压力、电源电压等外界环境的变化往往会导 致晶振频率产生波动，因此，构造理想时钟比较困难，但一般情况下，晶振频率 的波动幅度并非任意的，而是局限在一定的范围之内： 7 西北工业大学硕士论文第二章无线传感器网络时间同步的基本原理 1 一p 掣m p口f 公式( 2 3 ) 其中，p 为绝对频差上界，由制造厂家标定的，一般p 多在l 1 0 0 p p m 左右， 即一秒钟内会偏移l 1 0 0 s 。 在传感器网络中主要有以下三个原因导致传感器节点间时间的差异： ( 1 )节点开始计时的初始时间不同； ( 2 ) 每个节点的石英晶体可能以不同的频率跳动，引起时钟值的逐渐偏离， 称为偏差( s k e w ) 误差； ( 3 )随着时间推移，时钟老化或随着周围环境如温度的变化而导致时钟频 率的变化，称之为漂移( d r i 鼬误差。 对任何两个时钟a 和b ，分别用g ( d 和g o ) 来表示它们在f 时刻的时间值， 那么【1 4 l 【1 7 l ： 偏移( o 魅c t ) 可表示为：巳o ) 一q ( ，) d 已( f ) d ( ) 偏差( s k e w ) 可表示为： 班出 a 2 巴a 2 g o ) 漂移( d r i r ) 或频率( r a t c ) 可表示为： 西4研2 假定c ( f ) 是一个理想的时钟。如果在r 时刻，有c o ) = q 时钟，我们称时钟 c ，o ) 在f 时刻是准确的( c o r 咒c t ) ；如果蔬吲拈必例出，则称时钟q 在f 时刻是 精确的( a c c u r a c y ) ；而如果q = 龟囝，则称时钟q 在r 时刻与时钟q d 是同步的 ( s y n c h r o l l i z c d ) 。上面的定义表明：两个同步的时钟不一定是准确或精确的，时 间同步与时间的准确性和精度没有必然的联系，只有实现了与理想时钟( 即真实 的物理时间) 的完全同步之后，三者才是统一的。对于大多数的传感器网络应用 而言，只需要实现网络内部节点问的时间同步，这就意味着节点上实现同步的时 钟可以是不精确甚至是不准确的。 本地时钟通常由一个计数器组成，用来记录晶体振荡器产生脉冲的个数。在 本地时钟的基础上，我们可以构造出逻辑时钟，目的是通过对本地时钟进行一定 的换算以达成同步。节点的逻辑时钟是任一节点f 在物理时刻f 的逻辑时钟读数， 可以表示为：三q ( r ) = 肠，c ，( ，) + 碱，其中e ( f o ) 为当前本地时钟读数，缸，啦为 频率修正系数和初始偏移修正系数。采用逻辑时钟的目的是对本地为了同步任意 两个节点f 和，构造逻辑时钟有两种途径： 盛 堡! ! 三兰兰奎堂堕主堡奎墨三兰垂垡堡壁墨塑塑堕囹旦垄箜萎查墨墨 根据本地时钟与物理时钟等全局时间基准的关系进行变换。由式( 2 2 ) 反变 换可得： f ；土e + 瓴一马 a la t 公式( 2 - 4 ) 将概，慨设为对应的系数，即可将逻辑时钟调整到物理时间基准上。 另一种途径是根据两节点本地时钟的关系进行对应换算。由式( 2 - 2 ) 可知， 任意两个节点f 和_ ，本地时钟之间的关系可表示为： 勺o ) = 吩c f ( f ) + 公式( 2 5 ) 其中。苗，。屯一i 岛。将弛，啦设为对应的嘞，构造出个逻辑 时钟，即可与节点j 的时钟达成同步。 以上的两种方法都估计了频率修正系数和初始偏移修正系统，精度较高；对 于低精度类应用，还可以简单地根据当前的本地时钟和物理时钟的差值或本地时 钟之间的差值进行修正。 一般情况下。我们都采用后面的方法进行时钟闻的同步。其中，4 。和分别 称为相对漂移和相对偏移。式( 2 - 5 ) 给出了两种基本的同步原理：偏移补偿和漂移 补偿。如果在某个时刻，通过一定的算法求得了，也就意味着在该时刻实现时 钟q 和c ，( r ) 的同步。偏移补偿同步没有考虑时钟漂移，因此同步时间间隔越大， 同步误差越大，为了提高精度，可以考虑增加同步频率；另外一种解决途径是估 计相对漂移量，并进行相应的修正来减小误差。可见漂移补偿是一种有效的同步 手段，在同步间隔较大时效果尤其明显。当然实际的晶体振荡器很难长时间稳定 工作在同一频率上，因此，综合应用偏移补偿和漂移补偿才能实现高精度的同步 算法。 2 3 无线传感器网络时间同步设计要素 在无线传感器网络中，单个节点的能力非常有限，整个系统所要实现的功能 需要网络内所有节点相互配合共同完成。时间同步在无线传感器网络系统中起着 非常重要的作用。在分布式系统中，时间可分为“逻辑时间”和“物理时间”。“逻 辑时间”的概念是建立在l 硼p o r t 【l 剐提出的超前关系上，体现了系统内事件发生的 9 西北工业大学硕士论文第二章无线传感器网络时间同步的基本原理 逻辑顺序。“物理时间”是用来描述在分布式系统中所传递的一定意义上的人类时 间【1 9 l 。对于直接观测物理世界现象的无线传感器网络系统来说，物理时间的地位 更为重要，因为现象发生的事件本身就是一个非常重要的信息。此外，节点间的 协同信号处理、节点闻通信的调度算法等对系统提出了不同精度的物理时间同步 要求。 如果将时钟偏移定义为某个时间段内两个时钟之间因为漂移而产生的时间上 的差异，则分布式系统物理时钟服务定义了一个系统中所允许的时钟偏移的最大 值。只要两个时钟之间的差值小于所定义的最大物理时钟偏移量，就可以认为两 个时钟是保持了同步刚。 无线传感器网络中的时间同步指使网络中部分或所有节点拥有相同的时间基 准，即不同节点有着相同的时钟，或者节点可以彼此将对方的时钟转换为本地时 钟【2 1 1 ，使不同的节点记录的信息就象同一个节点记录的一样。传统的时间同步协 议如n t p 协议和( 沪s 授时等在有线网络中得到普遍应用，但它们由于很多原因而 不适合无线传感器网路。无线传感器网络中的时间同步需要更新更健壮的方法。 彻底的理解无线传感器网络所面临的挑战是成功设计适合无线传感器网络同步协 议的关键。下面就无线传感器网络的特点做以讨论： ( 1 )有限的能量 随着计算设备效率的迅速增长，能耗成了无线传感器网络的一个瓶颈。由于 传感器节点小尺寸和廉价可用性，传感器网络可以使用大量的传感器节点，这使 得不可能为每个传感器节点提供有线能源，且无人管理的操作方式也使得传感器 必须由电池供电。由于传感器节点可用能量非常有限，时间同步必须在保持节约 能量的同时以有效的方式达到。 ( 2 )有限的带宽 在传感器网络中处理数据的能耗远小于传输。带宽限制直接影响传感器之间 的消息交换，而没有消息交换同步是不可能完成的。 ( 3 )有限的硬件资源 由于传感器节点尺寸较小，因而它的硬件资源是非常有限的。为了完成各种 任务，无线传感器网络节点需要完成监测数据的采集和转换、数据的管理和处理、 响应汇聚节点的任务请求和节点控制等多种工作。如何有效利用有限的计算和存 储资源完成同步任务也是必须要考虑的。 ( 4 )不稳定的网络连接 无线介质容易受外界干扰导致消息丢失率较高，且连接也受带宽和间歇性连 接的限制，因而网络拓扑结构经常发生变化。 1 0 西北工业大学硕士论文第二章无线传感器网络时间同步的基本原理 因而，在无线传感器网络中完成节点间的时间同步面l 晦以下挑战： ( 1 )g p s 可以将本地时钟与u t c ( 世界协调时间) 同步，但体积、成本、 能耗等方面的限制使得无线传感器网络中的绝大部分节点不具备g p s 功能。 ( 2 )节点间无线通信以多跳的方式进行数据交换，在低速带宽的条件下， 同步信标传输过程中的延迟具有很大不确定性。 ( 3 )底层协议的节能操作使得节点在大部分时间都处于“休眠状态”，不能 在系统运行期间持续地保持时间同步。 ( 4 )由于环境、能量等因素的影响，节点易损坏，无线传感器网络拓扑结 构频繁变化，不可能随时间基准的获取路径进行静态配置。 ( 5 )如果在网络规模较大的情况下实现全局时钟同步很难保证全局同步精 度具有确定的上限。 无线传感器网络时间同步算法设计的目的是为网络中节点的本地时钟提供共 同的时间戳。由于以上诸多原因，我们在设计时间同步方案时不仅要考虑到同步 精度，还要考虑能量的有效性，算法的健壮性、可扩展性等。因而评价一个无线 传感器网络时间同步算法的性能，也就包括网络能量效率、可扩展性、精确度、 健壮性、寿命、有效范围、成本和尺寸、及时性等指标。 ( 1 ) 能量效率。无线传感器网络的主要特点就是节点的能量受限问题，涉及 的时间同步算法需以考虑节点有效的能量资源为前提。 ( 2 ) 可扩展性。无线传感器网络需要部署大量的传感器节点，时间同步方案 应该有效扩展网络中节点的数目或者密度。 ( 3 ) 精确度。精确度的需要依赖于特殊的应用和时间同步的目的而有所不同， 对某些应用，知道时间和消息的先后顺序就够了，而对某些其它的，则要求同步 精确到微秒级。 ( 4 ) 健壮性。无线传感器网络可能在敌对区域长期无人管理，一旦某些节点 失效，在余下的网络中，时间同步方案应该继续保持有效并且功能健全。 ( 5 ) 寿命。时间同步算法提供的同步时间可以是瞬时的，也可以和网络寿命 一样长。 ( 6 ) 有效范围。时间同步方案可以给网络内所有节点提供时间，也可以给局 部区域内的部分节点提供时间。由于可扩展性的原因，全面地时间同步是有难度 的，对于大面积的传感器网络，考虑到能量和带宽的利用，也是非常昂贵的。另 一方面，大量节点达到共同时间需要收集来自遥远节点的用于全面同步的数据， 对于大规模的无线传感器网络是很难实现的，而且影响了同步的精确度。 ( 7 ) 成本和尺寸。无线传感器网络节点非常小而且廉价。因此，在传感器网 西北工业大学硕士论文第二章无线传感器网络时间同步的基本原理 络节点上安装相对较大或者昂贵的硬件( 如g p s 接收器) 是不合逻辑的，无线传 感器网络的时问同步方案必须考虑有限的成本和尺寸。 ( 8 ) 及时性。某些无线传感器网络的应用，比如紧急情况探测( 如气体泄漏 检测、入侵检测等) 需要将发生的事情立即发送到网关，这种特性称之为“及时 性”。若在事件发生后再进行同步就没有意义了，因此节点之间需要经常性的“预 同步”。 西北工业大学硕士论文 第三章时间同步算法的研究与分析 第三章时间同步算法的研究与分析 2 0 0 2 年8 月，j e l s o n 和k 瞰 m e r 在h o l n 哪这一影响未来网络研究发展方 向的国际权威学术会议上首次提出和阐述了无线传感器网络中的时间同步的研究 课题圈，引起了无线传感器网络研究领域的广泛关注。近年来，国内外许多大学 和研究机构都对无线传感器网络的同步技术进行了深入研究并提出了多种时间同 步机制，从不同方面满足传感器网络的应用需要。到目前为止，已经提出了十几 种不同的实现算法，典型的有r b s 【7 1 、t p s n 【引、l t s 【2 3 1 、t s m s 【2 4 】、t s y n c 嘲、 d m r s l 2 6 l 、f t s p 【2 7 l 郾】、a d 例、t s s 口o 】和 p 【3 ”。本章将对目前的同步算法进行 分类，研究现有的同步技术，并对典型的同步算法进行深入研究和分析。 3 1 同步分类 同步一般理解为使时钟显示相同的时间，但实际上有很多种不同类型的同步。 下面对各种同步方法作以整体的了解。在为给定的应用选择同步算法时，要在最 大程度满足应用的同时尽可能将计算、存储尤其是能量开销降到最低。 1 时钟速率同步和偏移同步 时钟速率同步是指各个传感器节点测量所得的时间间隔相等，即： ( f ) 一啊( f 0 ) = 见( f ) 一吃( f 0 ) = = ( f ) 一( f 。) 在一些应用中，如测量目标对象出现和消失的时间，速率同步对比较目标对 象在不同节点测量范围内的持续时间的长短已经足够，而且也是非常必要的。 偏移同步是指传感器节点在当前时刻f 的时间偏移相等，即在r 时刻传感器节 点的软件时钟都显示c ( ，而不管时钟速率是否同步，即： c 1 ( f ) = c 2 ( f ) = = q ( f ) 偏移同步对传感器网络中不同节点间的时戳结合是必须的。 2 寿命：连续同步与按需同步 时间同步的寿命是指同步要保持的时问长短。如果时间同步是连续的，网络 节点要一直保持同步。在这种同步方式下，维持同步的代价是很大的，随着时间 的推移，节点间误差逐渐增加，可能还需要周期性地再同步。按需同步是指传感 器节点的时间并不一直保持同步，而只有在相关事件发生前或后才进行同步，它 不需要大量的维护同步的通信开销，节省了通信带宽和节点能量。对一些传感器 网络的应用，按需同步在同步精度方面可能和连续同步一样好，但效率更高。在 1 3 西北工业大学硕士论文 第三章时间同步算法的研究与分析 没有事件发生时，没必要保持同步，这样可以降低通信开销进而降低能量开销。 如果连续事件之间的间隔变短，连续同步和按需同步表现都不错。 按需同步有两种：事件触发型和时间触发型。事件触发型是为标记传感器事 件，传感器节点仅需在事件发生后才需要同步时钟。它可以计算事件发生的最近 过去时间，事后( p o s “缸t 0 ) 同步就是事件触发型同步的一个例子。我们在特定 时间从多个传感器节点获得数据时使用时间触发型同步，也就是没有事件触发传 感器节点，但节点必须在非常正确的时间进行采样。我们称之为事前( p f a c t 0 ) 同步。 3 同步范围：全网同步和局部同步 同步范围是定义网络哪些节点需要同步的。在有些情况下，范围可能纯粹是