（电磁场与微波技术专业论文）无线传感器网络时间同步算法的研究.pdf

中国科学技术大学硕士论文 摘要 摘要 无线传感器网络集成了传感器、嵌入式计算技术和网络通信三大技术，并由于其巨大的应用前 景而备受学术界和工业界的广泛关注。它是集数据采集、融合处理和通信为一体的网络。由于无线 传感器网络如能量有限的、资源不能更新的特点，使得无线传感器网络的设计面i 临着巨大的挑战。 时间同步作为无线传感器网络应用的一项支撑技术，对无线传感器网络的设计和应用都是关键 的。传统的时间同步方法n t p 和g p s 因能量消耗大、代价高和成本高等原因都不适合无线传感器 网络。由于传感器节点受到成本、能量和体积的限制，使得无线传感器网络的时间同步遇到了很多 新的挑战，无线传感器网络的时间同步方法得到国内外无线传感器网络研究领域的广泛关注。 本文首先分析无线传感器网络时间同步的必要性、时间同步的设计要素、算法的评价指标以及 同步的基本原理。然后通过研究现有的无线传感器网络时间同步技术并对其进行分类，深入分析了 一些有代表性的算法并对其优缺点进行分析评价和比较，本文提出了一种既简单又节能的无线传感 器网络部分广播同步算法。该算法基于节点间的距离信息，只选择外层节点进行下一层网络等级的 广播，从而有效地降低同步过程中的通信开销。文章分析了在不同的网络节点密度下广播信息包数 与等级广播距离的关系，得到了不同网络节点密度下的最优等级广播距离。在均匀网络分布的情况 下，该算法与t p s n 相比，该算法有效地利用了网络中节点广播的信息，在保证网络同步精度的基 础上，大大减少了时间同步的开销，提高了网络的能量有效性。 通过对算法在特殊的网络拓扑形式下的仿真结果进行分析，本文提出了基于节点连接度的无线 传感器网络部分广播同步算法。它利用节点的连接度来选择广播节点，在特殊的网络拓扑下，以最 少广播节点实现最大数量的节点覆盖。本文最后通过对算法的第一阶段进行仿真，表明算法可以在 只进行第一阶段时，在保证大部分节点得到同步的情况下，降低网络同步开销，大大缩短网络同步 的时间，适用于特定的无线传感器网络的应用。 第1 页共5 9 页 中国科学技术大学硕士论文 a b s t r a c t a b s t r a c t w i r e l e s ss e n s o rn e 似，o r k ( w s n ) i n t e g r a t e s 也es e r l s o r ，e m b e d e dc o m p u t a t i o na n dc o m m u n i c a t i o n n e t w o f k s ，a n di n c r e a s i n gn u m b e ro fa c a d e m i cr e s e a r c h e r sa n di l l s i d e r sa r ee n g a g e dhd e v e l o p i n gw i r e l e s s s e n s o rn e m o r k sd u et ot 1 1 e i rb r i 曲tf u t u r ew i mv a r i o u s 印p l i c a t i o n s w i r e l e s ss e n s o rn e t w o r k sh a v e i n t e g 舭dc o l l e c t i n g ，p r o c e s s i n ga n dc o 删眦m i c a t i o n 。b e c a u s eo f t h el i n i t e do fe n e r g ya n du n r e n e w a b l eo f r e s o u r c e0 fw i r e l e s sn e 觚o r kn e 似o r k s ，t h e r ea r em 锄yc h a l l e n g e si i ld e s i g no fw i r e l e s sn e m o r kn e 似0 r k s t i m es y n c l l r o n i z a t i o ni sa 凡n d a m e n t a ls e r v i c ef o rb o 也d e s i g na n da p p l i c a t i o no fw i r e l e s ss e n s o f n e t 、 r o r k s h o w e v e r ，仃a d i t i o n a la l g o r i t h n ls u c ha l sn t pa 1 1 dg p sc a i l tp r o h i b i tt h e i rl l s ei nw s n b e c a u s eo f e n e r g y ，c o m p l e x 姆a n dc o s t b e c a u s eo ft h ec o s t ，p o 、v e r ，a n ds i z ec o n s 舰i n t so ft h ei i l d i v i d u a ln o d e s ，m e r e a f em a n yn e wc 量1 a l l e n g e s d e v e l o p j n gt i m es ，m c h r o n i z a t i o nm e t l l o d ss u i t a b i ef o rw i r e l e s ss e n s o rn e t w o r k s h a v e 甜r a c t e dw i d ea t t e n d i o l l 1 1 1 i st 1 1 e s i sf i r s t l yd e s c r i b 懿m en e c e s s t i y ，s o m ei m p o n a n tmd e s i g n ，e v a i u a t i o nc r i t e r i o no ft h e p e r f o 咖a n c ea n dm n d a 姗e n t a lp r i n c i p l e so ft i l i l es y n c h r o n i z a t i o i l ，孤ds t u d ye x i s t i n gt e c h n o l o g i e so f t i m e s ) ，i l c h r o n i z a t i o na n dc l a s s 毋t h e m s o m er e p r e s e n t a t i v es ”c h r o n i z a t i o na l g o r i t h m sa r ed i s c u s s e dd e e p l ya t t h es a m et i m e b a s e d0 nt h o s e ，an o v e ls i m p l ea 1 1 dl o w0 v e r h e a dt i m es y n c h r o n i z a t i o na l g o r i t l l mw h i c hi s s u i t a b l ef o rd e n s en e t 、v o r k si sp r e s e n t e d t h i sa l g o r i 1 r n ，w h i c hi sb a s e do nm el e y e ld i s c o v e 巧m e c h a n i s m u s e di nt p s n ，0 1 1 i ys e l e c t s 仔a c t i o m ln o d e si nm eb r o a d c a s t i n ga r e ao f l ec u n e n tl e v e ln o d e 嬲廿屺n e x t l e v e lb r o a d c a s t “t i a t en o d e s a sar e s u l t ，m eo v e i h e a do ft i m es y n c i l r o n i z a t i o ni sr e d u c e de 仃e c t i v e l y 1 1 1 e s e l e c t i o no fn e x tl e v e lb r o a d c 弱t m i t i a t en o d e si sa c c o r d i n gt od i s t a n c ei n f o m a t i o no fc u r r e n tl e v e ln o d e s t h er e l a t i o n s h i pb e ”e e nn u m b e ro fb r o a d c a s tp a c k e t sa n dl e v e l - b r o a d c a s td i s t a n c ei nd i f 衔e n tn o d e d e n s 时o fn e m o r k si sa l s oa 1 1 a l y z e d a n dt h eb e s tl e v e l - b r o a d c a s td i s t a i l c ei nv a r i o u sn o d cd e n s 时o f n e 时o r i ( si sg i v e ni n 出ep 印e r f i n a l l y ，s i m u l a t i o nw o r k sv a i i d a t et h a ti nu n i f o 吼n e 慨o f kt o p o l o g y ，t l l e a l g o r i t l l mg r e a t l yr e d u c e sm en u m b e ro fb r o a d c a s t i n gp a c k e t sf o rt i m es y n c l l r o n i z a t i o ni nh i g hd e n s i t y w i r e l e s ss e n s o rn e t w o r k s ，w h n em es y n c h r o n i z a t i o np r e c i s i o ni se q u i v a l e n tc o m p a r e dw i t ht p s n an e wt i m es y n c h r o n i z a t i o na l g o r i t i l mw h i c hi sb a s e do nc o 衄e c t i v i 哆o fn o d e si sa l s od e s c r i b e da f t e r a n a l y s i n gs i m u i a t i o ni ns p e c i a ln e t 、 ，o r kt o p o l o g y 。t h ea l g o r i t c h o o s 懿b r o a d c a s t i n gn o d e sa c c o r d i n gt o c o m l e c t i v i 妙o fn o d e sf o rc o v e r a g i n gm a x i m 啪n u m b e ro fn o d e s a tl a s t ，i ts h o w sm a tt h ea l g o r i t l l mc a n r e d u c eo v e r h e a da n dt i m eo fn e t w o r ks ”c h r o n i z a t i o ne f f e c t i v e l yw h i l em o s tn o d e sg e ts y n c h r o n i z a t i o n a c c o r d i n g t 0s i m u l a t i n gf l r s tp h a s eo ft h ea l g o r i t l l r n 第1 i i 页共5 7 页 中国科学技术大学硕士论文目录 插图目录 图1 1 无线传感器网络系统结构3 图1 2 无线传感器网络体系结构3 图2 1 主从同步方式3 图2 2 相互同步方式3 图2 3 时间同步的原因3 图2 4 信息包传递中的延迟3 图2 5 通过中间节点的参考广播，r e c e i v e r l 和i 也c e i v e r 2 进行节点间同步3 图2 6t p s n 的网络等级划分过程3 图2 7 两节点信息交换同步3 图2 - 8 利用q ：和6 l ：在数据点的约束3 图2 9d m t s 算法原理示意3 图2 1 0h i 玎s 的同步过程3 图2 1lo h m t s 的网络结构3 图3 1 网络节点数与同步建立时间的关系3 图3 2 网络节点数与同步精度的关系3 图3 3 节点密度增加产生的多余开销3 图3 4 部分节点同步阶段的流程图3 图3 5 孤漏节点请求同步的流程3 图3 6 阴影区为广播节点所在区域3 图3 7 归一化广播包数与洲，的关系3 图3 8 最优d ，与网络节点密度的关系3 图3 9 广播信息包数与网络节点密度的关系3 图3 1 0 同步精度与网络节点密度的关系3 图3 1 1 三种特殊的网络拓扑3 图3 1 2 各种网络拓扑下部分广播的表现3 图4 1 特殊网络拓扑对广播节点选择的影响3 图4 2 广播同步阶段的流程图3 图4 3 节点请求同步的流程3 第v i 页共5 7 页 中国科学技术大学硕士论文 目录 图4 4 基于连接度与基于距离的同步算法的比较3 图4 5 同步广播阶段时同步的覆盖率3 图4 6 同步广播阶段广播信息包数3 图4 7 部分广播与t p s n 在网络同步时间上的比较3 第v i i 页共5 7 页 中国科学技术大学硕士论文目录 表格目录 表1 1 无线传感器网络的应用前景3 表2 1 各种同步算法的比较3 第v i i i 页共5 7 页 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：螽盎望 舻召年多月口日 中国科学技术大学硕士论文绪论 第1 章绪论 1 1 无线传感器网络的概述 无线传感器网络( w i r e l e s s5 e n s o r n e t w o r k s ，w s n ) 是当前国际上备受关注的，由多学科交叉的 新兴前沿研究的热点领域，成为目前r r 领域中的研究热点之一。随着传感器技术、微机电系统、 现代网络和无线通信等技术的发展和进步无线传感器网络成为客观物理世界和逻辑上信息世界连 接的平台，扩展了人类获取信息的能力，在下一代互联网中将为人们提供最直接、最有效和最真实 的信息。 无线传感器网络是由大量的、微型的节点组成。它以无线的形式探测事件或收集信息并进行通 信，最终目的是将处理的数据传送到基站。图1 1 给出了一个典型的无线传感器网络的系统结构。 它通常包括了传感器节点( s e n s o rn o d e ) 、汇聚节点( s i l l i 【n 0 d e ) ，互联网( 或卫星) 和任务管 理节点等。其中，大量传感器节点随机部署在检测区域( s e r i s o rf i e l d ) 内部或附近，能够通过自组 织方式构成网络。传感器节点检测的数据沿着其他传感器节点进行多跳传输，在传输的过程中数据 可能被多个节点处理。在达到汇聚节点后，数据通过互联网或卫星链路到达管理节点。用户通过管 理节点对传感器网络进行配置和管理，发布检测任务和收集检测数据。 图1 1 无线传感器网络系统结构 纳米技术和微电子机械系统的发展推动了无线传感器网络向前发展，使得小小的传感器节点集 成了探测、处理和通信三个重要的部分。随着嵌入式计算，通信硬件的低功耗的起大规模集成电路 的发展，计算和通信的集中使其成为现实。这些都使无线传感器网络的应用有了广阔的前景和机 遇。 正是因为无线传感器网络的应用前景和对社会生活可能产生的巨大影响，国内外研究机构纷纷 展开了无线传感器网络的研究。随着无线传感器网络的深入研究和广泛应用，它将逐渐深入到人类 生产生活的各个领域： l 、 军事应用：该领域的应用需求是无线传感器网络产生和发展的主要推动力量。无线传 感器网络的由密集型、低成本、随机分布的节点组成，动态性和容错能力使其不会因 为某些节点在受到恶意攻击中损坏而导致整个系统的崩溃，而且由于无线传感器网络 第l 页共5 7 页 中国科学技术大学硕士论文 绪论 的无需外界配置管理和自组织特性，使无线传感器网络易于快速部署，非常适合应用 于恶劣的战场环境中。例如，u cb e r k e l y 大学的s m a nm o t e 的应用背景就是战场侦察 【2 】o 2 、 环境监测【2 巧j ：随着人们对环境问题的日益关注，环境科学所涉及的范围越来越广。无 线传感器网络的出现为原始数据的获取提供了便利，并且还可以避免传统数据收集方 式给环境带来破坏。其中，美国研究的a l e r t 系统就是用无线传感器网络进行洪水检 测的一个例子。研究人员开发了监测降雨量、水位、天气等环境条件的传感器，这些 传感器通过预定义的方式想中心数据库提供信息并以此预测山洪瀑发的可能性。 3 、 医疗健康【2 3 j ：无线传感器网络在医疗系统和健康护理方面的应用包括监测人体的各种 生理数据，跟踪和监控医院内医生和患者的行动，医院的药物管理等。如果在住院病 人身上安装特殊用途的传感器节点用途的传感器节点，利用无线传感器网络，医生就 可以随时了解被监护病人的病情，并进行及时处理，而安装在被监测对象的微型传感 器也不会给人的正常生活带来太多的不便。 4 、 工业控制及检测：现代化的生产车间以及厂房、仓库都需要对温度、压力以及其他跟 设备有关数据进行检测，利用无线传感器网络可以有效地降低成本，提高系统的可靠 性。在一些特殊的工业场合如矿井、核电站等，工作人员可以通过它来实现安全检 测。它可以大量降低检查设备的成本，同时可以提前发现问题，因此能够缩短停机时 间，提高效率，并延长设备的使用时间。 5 、 突发时间处理【2 - 3 j ：利用无线传感器网络技术可以在灾难或事故现场即刻组成一个通信 网络，协助进行人员救助，或对事故现场进行准确的定位。无线传感器网络还可以搜 集有关人群以及运输通道的状态信息。搜集到的传感器信息必须能够沿安全可靠的通 道传递给紧急事件处理人员。 6 、 其他领域：在其他的商业领域，无线传感器网络也有着广阔的应用前景，如智能家 居，城市交通的实时监控。 表1 1 总结归纳了无线传感器网络潜在的应用领域。 表1 1 无线传感器网络的应用前景 应用领域主要应用范围 军事领域兵力装备调配监视；战区监视：情报获取；目标追踪等。 环境科学森林火灾的监测：土壤监控：洪水监测；精密农业等。 工业应用库存管理；工业自动化；设备联网等。 医疗健康病人远程监测：医院内医生和患者的跟踪；药物管理等。 家庭应用家居自动化；居住环境智能化等。 空间探索 外星球表面监控、监测等。 商务应用大厦环境监控：交通监控；商店商品管理；智能玩具等。 第2 页共5 7 页 中国科学技术大学硕士论文 绪论 在无线传感器网络存在巨大应用前景的同时，无线传感器网络也面临着巨大挑战，比如，能量 是有限的，资源是不能更新的。 无线传感器网络与传统的a d - h o c 网络虽然有很多相似之处，但同时也存在着很大的差别。由 于无线传感器网络存在以下几个主要特点，使得它的首要设计目标是能量的高效利用，这也是无线 传感器网络与传统无线网络的最大区别： l 、 传感器节点的限制：这包括电源能量有限、通信能力有限和计算存储能力有限。节点 由于受价格、体积和功耗特别是电源能量有限，决定了在设计任何技术和协议时都要 以节能和低复杂度为前提，并且导致在设计无线传感器网络时必须考虑低功耗和低成 本两个重要的指标。 2 、 网络的大规模：这是无线传感器网络的又一大特点。无线传感器网络的大规模性包括 了两个方面的含义。一方面传感器节点分布在很大的地理区域内，需要布置大量的传 感器节点；另一方面传感器节点布置的很密集，在一个面积不大的空间内，密集的布 置了大量的传感器节点。 3 、 应用相关的网络：无线传感器网络是用来感知客观物理世界，获取物理世界信息量 的。不同的无线传感器网络应用关心不同的物理量，不同的应用背景对无线传感器网 络的要求不同，其硬件平台、软件系统和网络协议会有很大的差别。虽然在对于不同 的无线传感器网络应用存在着一些共性的问题，但更要关心不同应用下无线传感器网 络的差异。针对不同应用来研究无线传感器网络技术，这又是无线传感器网络设计不 同于传统网络的显著特征之一。 4 、 网络的自组织：在无线传感器网络的应用中，通常情况下传感器节点被放置在没有基 础结构的地方，传感器节点的位置不能预先精确设定。这就要求传感器节点具有自组 织的能力，能够自动进行配置和管理，通过拓扑控制机制和网络协议自动形成转发检 测数据的多跳无线网络系统。 5 、 多跳路由：网络中节点通信距离有限，节点只能与它的邻居直接通信。如果希望能与 通信范围之外的节点进行通信，则需要通过中间节点进行路由。固定网络的多跳路由 是使用网关和路由器来实现，而无线传感器网络中的多跳路由是由普通节点完成的。 这样每个节点既可以是信息的发起者，也是信息的转发者。 6 、 动态拓扑：无线传感器网络是一个动态的网络，节点可以随处移动；节点也可能因为 电池耗尽或故障退出网络；同样也可能有新的节点加入到网络中。这些都会使网络的 拓扑随时发生变化，因此网络应该具有动态拓扑组织功能。 正是由于无线传感器网络的这些特点，随着无线传感器网络的深入研究，无线传感器网络体系 结构也被广泛的提出。图1 2 给出了一种广为接受的无线传感器网络的体系结构，它也不同于传统 的计算机网络，是由分层的网络通信协议和传感器网络管理模块组成。分层的网络通信协议由物理 层、数据链路层、网络层、传输层和应用层组成，这和传统的计算机网络相类似。网络管理模块包 括能量管理、拓扑管理、q o s 控制、移动性管理和网络安全等。这个网络管理模块是根据无线传感 器网络的自身特点，专门针对无线传感器网络的设计要求所提出的。 、 第3 页共5 7 页 中国科学技术大学硕士论文绪论 图1 2 无线传感器网络体系结构 由于无线传感器网络的巨大应用价值和广阔的应用前景，使它引起了世界许多国家军事部门、 工业界和学术界的广泛关注。美国、英国、日本等国家的一些大学和研究机构也纷纷展开了该领域 的研究工作。目前无线传感器网络研究的热点、难点包括：设计小型化的节点设备；开发适合传感 器节点的嵌入式实时操作系统：无线传感器网络体系结构及各层协议；时间同步机制与算法：网络 节点自身定位算法和外部目标定位算法等。国内也从近期开始了这方面的研究工作。并且也取得了 一些初步成果。 尽管无线传感器网络的研究已经取得了一定的成果，但作为一个刚刚兴起的研究领域，无线传 感器网络的技术和应用还不十分成熟，有待进一步的研究。 1 2 时间同步在无线传感器网络中的重要性 时间同步是无线传感器网络的重要的支撑技术之一，是无线传感器网络应用的重要组成部分。 传感器数据融合、传感器节点自身定位等都要求节点保持时间同步”】。在无线传感器网络应用中， 传感器节点通常需要协调操作共同完成一项复杂的传感任务。例如在目标追踪应用中，传感器节点 将传感到的运动目标的位置、时间等信息发送给传感器网络中的根节点，根节点在对不同传感器发 来的数据进行处理后便可获得目标的移动方向、速度等信息：为了能够正确监测事件发生的次序要 求传感器节点之间实现相对时间同步。在火灾监测等应用中，事件的发生时间是相当重要的参数， 这要求每个节点维持唯一的全局时间以实现整个网络的时间同步。时间同步对无线传感器网络具体 应用可以体现在以下几个方面“。u j ： i 、 多节点的协同观测：分散的多个传感器节点协同观测能够提供多角度和多方位的信息， 并能有效地提高信噪比，提高发现和跟踪目标的能力。这需要多个节点的时间坐标保持 一致，才能提供准确的结果。若对同个目标进行监视的多个传感器节点的同步误差很 大，则可能会出现错判，造成严重的后果。 第4 页共5 7 页 中国科学技术大学硕士论文绪论 2 、 用于时分复用( t i m ed i v i s i o nm u l t i p l ea c c e s s ，t d m a ) 通信协议：t d m a 是无线传感 器网络一种重要的通信协议。采用时分复用的通信协议需要参与通信的节点之间保持很 高的同步精度。 3 、 数据融合：当来自多个节点或多个区域的数据到达汇聚节点或后方基站，对这些数据进 行融合时，需要一个统一的时间坐标。 4 、 测距和定位：定位包括节点定位和目标定位。节点通过发送和接收超声波或电磁波信号 来确定相互间的距离。此时同步精度越高，测距精度也越高。 5 、节点休眠等：由于无线传感器网络的特点，节点为了节省能量，有时需要进入休眠状 态。当节点唤醒时，其时钟将可能处于未知状态，需要进行时间同步。而且无线传感器 网络一般用于危险或环境恶劣的地区，在这些地方存在不可预期的环境变化，如温差 大、强电磁等，这对传感器节点的时钟有很大的影响。这些都要求无线传感器网络进行 时间同步。 简而言之，无线传感器网络作为一个分布式网络，协同合作是其基本的特性，为了实现其协同 合作的功能，时间同步就显得特别重要了。在分布式系统中，不同的节点都有自己的本地时钟。由 于不同节点的晶体振荡器频率存在偏差，以及温度变化和电磁波干扰等，即使在某个时刻所有节点 都达到时间同步，它们也会随着时间的流逝逐渐出现偏差，而分布式系统的协同工作需要工作节点 间的时间同步，因此时间同步机制是无线传感器网络的重要的关键技术之一。 同时，由于无线传感器网络具有自身一些不同于其他类型网络的特点，如有限的能源、较低配 置的资源、恶劣的环境、节点的易失性、网络的动态性等。正是由于无线传感器网络的这些特点， 在设计无线传感器网络时间同步机制时，需要考虑到以下几个方面： l 、 扩展性：在无线传感器网络的应用中，网络部署的地理范围大小不同，网络内节点密 度不同，时间同步机制要能够适应这种网络范围和节点密度的变化。 2 、稳定性：无线传感器网络在保持连通性的同时，因环境影响以及节点本身的变化，网 络拓扑结构将动态变化，时间同步机制能够在拓扑结构的动态变化中保持时间同步的 连续性和精度的稳定。 3 、 鲁棒性：由于各种原因可能造成传感器节点失效，另外现场环境随时可能会影响无线 链路的通信质量，因此要求无线传感器网络时间同步机制具有良好的鲁捧性。 4 、 收敛性：无线传感器网络具有拓扑结构变化的特点，同时传感器节点又存在能量约 束，这些都要求网络建立同步的过程很短，使节点能够及时知道它们的时间是否达到 同步。 5 、 能量感知：由于无线传感器网络的能量约束，为了减少能量消耗，保持网络时间同步 的交换信息数应尽量少，必需的网络通信和计算负载应该可以预知，时间同步机制应 该可以根据网络节点的能量分布，均匀使用网络节点的能量来达到能量的高效利用。 由于无线传感器网络应用的多样性，这直接导致了时间同步机制的多样性。我们不可能用一种 时间同步机制来满足所有的应用要求。所以，对同步机制的评价也就与无线传感器网络的应用有 关，描述无线传感器网络时间同步机制的参数主要有以下几个方面： 第5 页共5 7 页 中国科学技术大学硕士论文 绪论 i 、 精度：针对不同的应用，精度的要求具有很大的差别。对于某些应用，可能只需分辨 一些时间的先后关系就足够了，而对于有些应用就可能需要时间精确到毫秒级甚至微 秒级。 2 、 同步期限；这是指节点闻需要保持时间同步的时问长度。无线传感器网络需要在各种 时间长度内保持时间同步，从瞬间同步到伴随网络存在的永久同步。 3 、 同步范围：这个范围可以是地理上的范围，如一个长度距离或面积距离：也可以是逻 辑距离，如网络的跳数。 4 、 可用性：这是指在无线传感器网络范围内的覆盖完整性。有些时间同步机制需要同步 区域内所有节点；而有些同步机制由于对硬件或其他方面要求较高，只能同步网络中 部分节点。 5 、 成本和大小：由于传感器节点的尺寸很小，且成本低廉，而有些同步机制需要特定的 硬件，这就需要考虑部件的大小和成本。 6 、及时性：由于无限传感器网络可能应用于一些紧急事件的检钡，所以需要将发送的时 间立即发送给汇聚节点。 无线传感器网络对时间同步的诸多需求使得它成为一个关键性的技术。然而，应用的多样性又 使得时间同步成为一个难以解决的问题。例如声音应用要求精度达到几微秒，而传感任务则是以 小时甚至以天为计的：局部协作仅需要邻节点间的同步，而全局协作则需要全局的时间同步；事件 触发可能仅需要瞬间同步而数据记录或调试则经常需要长期的时间标度；与用户的通信需要外部 的人工时间标记如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 世界协调时间) ，而相对时间则对单纯的网 内比较重要。些节点有大电池可以一直运行。而其他节点可能因为电池非常有限只能偶尔地工 作，在读取一个传感器数据并传送出去后，又立即进入睡眠状态。所以，如何解决这些应用中的矛 盾是无线传感器网络同步算法设计中一个重要的方面。 在传统网络中，时间同步机制已经得到广泛应用，如网络时间协议n t p ( n e t w o r kt i m e p r o t o c o i ) 是i n t e m e t 采用的同步协议【1 l | 。g p s 、无线测距也可以用来提供网络的全局时间同步。但 由于传统网络和无线传感器网络的不同特点，这些现有的时间同步机制往往关注于最大的同步精度 等方面，而较少考虑计算和通信方面的开销，很少考虑节点消耗的能量。除此之外，在传统的分布 式系统的时间同步机制中也无法满足一个有如此广泛应用需求并且有如此多的设计需求的同步方 案。正是由于无线传感器网络的特点，以及能量、价格和体积等方面的约束，使得n t p 、g p s 等现 有的时间同步机制不适用于无线传感器网络，需要修改或重新设计时间同步机制来满足无线传感器 网络的要求。 2 0 0 2 年8 月，工e i s o n 和k r o m e r 在h o t n e t s i 这一影响未来网络研究发展方向的国际权威学 术会议上首次提出和阐述了无线传感器网络中的时间同步的研究课题，引起了无线传感器网络研究 领域的广泛关注【6 】。随着世界上各个大学和研究机构对这一领域的深入研究，至今已经提出了多种 时间同步算法。这些算法主要可以分为以下几类；1 ) 接收节点与接收节点之间的同步如 r b s n 利用“第三方，节点消除发送端延迟的影响：2 ) 信息交换的同步，如t p s n 【”、l t s 和 t i n y s y n c ，通过信息的交换来实现节点间的同步：3 ) 接收节点与发送节点的单向同步，如 d m t s 【1 4 1 和f t sp i 】”，通过估计信息在信道传播过程中延时，只发送一条广播信息即可实现节点间 的同步：4 ) 混合算法，如h r t s 【1 6 j ，结合了r b s 和。r p s n 优点：5 ) 网络分簇同步，如c h t s ， 第6 页共5 7 页 中国科学技术大学硕士论文绪论 利用网络分簇来提高整个网络的同步性能。它们利用不同的方法来解决无线传感器网络中节点的时 间同步问题，支持不同的无线传感器网络的应用，同时在能量需求、计算复杂度以及同步精度等方 面也各有不同。尽管无线传感器网络时间同步这一领域在国内外已经有了研究，但并不成熟，特别 是在多跳同步方面，并且无线传感器网络是与应用相关的，对时间同步的要求是多种多样的，应结 合特定的研究领域进行研究。 1 3 研究内容和论文结构 作为无线传感器网络重要的支撑技术之一，无线传感器网络时间同步的研究具有非常重要的意 义。本文对已有的无线传感器网络时间同步技术和算法进行了深入的分析，并针对多跳同步时能量 开销问题的基础上，提出了一种基于距离信息的、 对算法在不同的网络拓扑下进行仿真分析。最后， 点连接度的部分广播同步算法。 本论文的结构安排如下： 低开销的无线传感器网络部分广播同步算法，并 针对特殊网络拓扑下的问题，文章提出了基于节 第一章主要介绍了无线传感器网络的基本概念，论述了时间同步技术在无线传感器网络中的重 要性，并由此引述无线传感器网络时间同步算法的性能要求和评价标准。 第二章主要介绍了网络同步的基本知识和时间同步原理，以及现有的无线传感器网络的时间同 步算法，并对其进行总结分类。 第三章在完善n s - 2 仿真平台的基础下对t p s n 进行仿真，并分析多跳时间同步算法的问题， 在t p s n 的基础上，提出了基于距离信息的部分广播的同步算法。本章介绍了基于距离信息的部分 广播同步算法的基本思想和步骤，分析了等级广播距离的优化计算方法，给出了在不同网络节点密 度下广播信息包数与等级广播距离之间的关系。最后对算法进行不同的网络拓扑下进行仿真。 第四章分析了基于距离信息的部分广播算法在特殊网络拓扑下的问题，提出了基于节点连接度 的部分广播同步算法，并对算法进行仿真验证。最后只对算法第一阶段进行仿真，通过仿真表明只 进行第一阶段可以在保证大部分节点得到同步的情况下，降低网络同步开销，大大缩短网络同步的 时间，适用于特定的无线传感器网络的应用。 第五章对全文进行总结，并对下一步的研究工作进行了展望。 第7 页共5 7 页 中国科学技术大学硕士论文时间同步方法和性能分析 第2 章时间同步方法和性能分析 2 1 时间同步的概述 2 1 1 时间同步的基本知识 同步是数字通信中一个重要的问题。通信系统如果没有实现同步，就会使通信系统的性能降低 甚至通信失效。通信中的同步是指收发两端的载波、码元速率以及各种定时标志都应步调一致地进 行工作。按照同步的对象，它可以分为：载波同步、位( 码) 同步、帧同步和网同步。 载波同步：载波同步是指在数字调制解调系统中，当采用相干解调( 或同步检测) 时，接 收端必须获得一个与发送端载波同频同相的载波。这个载波的提取就是载波同步。 位( 码) 同步：位同步也可称为码同步。数字通信系统中，任何消息都是通过一串二进制码元 序列传送的，所以在接收端译码时，必须提供准确的码元判决时刻，使得判决时钟的周期 和相位都准确地与发送端一致。否则，误码率就会大大增大，通信就无法进行下去。 帧同步：数字通信在收发两端通常以帧的形式按次序连续不断地进行。为了让接收端辨认 每一帧的起止位置，发送端就必须提供每帧的起止标志。帧同步是指在接收端检测并获得 这一标志的过程。 网同步：以上三种同步是点到点的数字通信系统正常运行的基础。但在数字通信网中，为 了实现多点间可靠通信和数据交换，全网通常需要一个统一的时间标准，即全网需要同步 工作。实现整个网络的同步就称为网同步，也称为网络同步。 我们所研究的无线传感器网络的时间同步就属于网同步，目的就是为了使无线传感器网络有一 个统一的时间标准。 实现网同步的主要方式有三种：主从同步方式、相互同步方式和等级制主从同步方式。 主从同步方式是指在整个网络中设置一个高稳定度的主时钟源，其它节点的时钟全部以主时钟 为标准。它的工作方式如图2 1 所示。 主时钟源 图2 - 1 主从同步方式 第9 页共5 7 页 中国科学技术大学硕士论文 时间同步方法和性能分析 主从同步方式的优点是时钟稳定度高，方法简单。但它的主要缺点就是当主时钟源出故障时， 全网通信将中断。这种方法在小型网络中应用广泛。 相互同步方式的提出就是为了克服主从同步方式中过于依赖主时钟源的缺点。它的工作方式如 图2 2 所示。这种同步方式是一个相互控制的过程，它提高了网络的可靠性，但它的代价是增加了 方法的复杂性。 图2 2 相互同步方式 等级制主从同步方式是一种兼顾以上两种方式优点的同步方式。它是按时钟的频率稳定度分等 级进行相互同步。当高一级的时钟出问题时，可使用低一级的时钟。它可以看成两种同步方式的结 合。 2 1 2 时间同步的分类 如果不同时钟间的时刻差处于允许范围内，可认为它们在同一瞬时给出的时刻相同，则称为时 间同步。但在实际应用上有很多不同类型的时间同步。 l 、时钟速率同步和偏移同步 时钟速率同步是指各个节点测得的时间间隔相等，此时节点时钟的速率是相等的，即： 啊o ) 一啊( 岛) = o ) 一吃( ) = = 吃o ) 一吃( 岛) ( 2 一1 ) 时钟偏差同步是指节点在当前某个时刻f 的时间偏移相等，此时节点的软件时钟都显示的是同 一时刻，即： ( r ) = 绣( f ) = = 吃( f ) ( 2 - 2 ) 2 、连续同步和按需同步 连续同步是指网络中所有节点要一直保持同步。在这种同步方式下，维持同步的代价很大，随 着时间的推移，节点间误差逐渐增加，还要需要周期性地再同步。按需同步是指节点并不一直保持 同步，而只在相关事件发生前或发生后才进行同步。按需同步不需要大量的维护同步的通信开销， 节省了通信带宽和节点能量。 按需同步有两种：事件触发型和时间触发型。事件触发型是指节点仅在事件发生后才需要同 步。事后( p o s t f a c t o ) 同步就是事件触发型同步的一个例子。时间触发型同步是指为了在特定的时 间上从节点获得数据，节点在此特定的时刻进行同步。 第1 0 页共5 7 页 中国科学技术大学硕士论文时间同步方法和性能分析 3 、全网同步和局部同步 这是指网络的同步范围。有些情况下是指地理上的范围，有些情况是指逻辑上的距离。全网同 步是让网络中所有节点进行同步，而局部同步只需要某个区域内或某个跳数内的节点进行同步。 根据不同的应用，同步的范围可能是网络中所有节点或者只是部分节点。事件触发型同步仅需 要观察到事件的局部节点进行同步。采用t d m a 机制和基于一个检测目标的信号协同处理等情况 下，通常可以采用局部同步。而对于长期的目标追踪时间则需要大范围的同步。长时间长距离的任 务更需要容忍大的同步误差。 4 、绝对同步和相对同步 有些应用要求网络中每个节点都要与外部时间标度如u t c 保持同步，通常在与人交互的应用 中需要这种绝对同步。而有些情况只需要记录事件的暂时顺序，并不需要事件发生的绝对时间。在 多数情况下，计划执行的准确时间远没有保证所有节点同步执行重要，网络必须内部一致，而它们 与外部标准时间的关系并不重要，甚至不需要。 2 2 时钟模型和同步误差源分析 2 2 1 时钟模型 无线传感器网络中节点的本地时钟是依靠对自身晶振的中断计数来实现的。晶振的频率误差和 初始时刻的不同，使得节点间的本地时钟不同步。 节点时钟通常用晶体振荡器脉冲来度量的，所以任一节点f 在物理时刻f 的本地时钟读数可表 示为： c 。去：肌) 出托矧 ( 2 - 3 ) 其中，( f ) 的节点f 晶振的实际频率，石为节点晶振的标称频率，气代表开始计时的物理时 刻，是真实时间变量，q ( ，o ) 代表节点f 在岛时刻的时钟读数，q o ) 代表在f 时刻的时钟读数，间 隔f ) 一f 瓴) 被用来作为度量时间的依据。由于节点晶振频率在短时间内相对稳定，节点时钟又可 表示为： q o ) = q o 一气) + 6 i ( 2 4 ) 对于理想时钟，有讲c ( f ) 】衍= 1 ，也就是说理想时钟的变化速率为1 。但在实际应用中，因 为温度、压力、电源电压等外界环境变化往往会导致晶振频率产生波动，但在一般情况下，晶振频 率的波动幅度并非任意的，而在局限在一定的范围内： 1 一p 掣外p ( 2 5 ) 其中，p 为绝对频差上界，传感器节点的p 一般在1 1 0 0 刀聊，即一秒钟会偏移 l l o o s 。 一般有以下三个原因导致传感器节点的标记时间产生差异： 第l l 页共5 7 页 中国科学技术大学硕士论文时间同步方法和性能分析 l 、节点在开始计时时的初始时间就不同： 2