（通信与信息系统专业论文）大规模无线传感器网络的时间同步与节点定位技术研究.pdf

摘要 摘要 当今能源问题的日益凸显，对石油物探的要求不断提高。物探地震传感器数据采集与分 析是当今有效而重要的石油勘探技术，且地震传感器布设覆盖范围和密度不断增加己成为提 高石油探明率的必然发展趋势。与此同时，石油物探地震传感器数据采集通信网络技术形成 了从有线技术逐步向有，无线混合通信技术、全无线通信技术不断发展的趋势。 针对蜂窝式全无线大规模石油物探地震数据传感器采集通信网技术研究的背景，论文重 点就大规模无线传感器网络的时间同步与传感器节点定位技术开展了具体研究。论文全面介 绍了无线传感器网络基本原理与技术特点，在选择合适的节点时钟数学模型基础上，通过对 时钟误差来源的分析，给出了两种时钟同步的基本方案。在对现有多种无线传感器网络时钟 同步方法比较后，重点就适合课题背景的成对同步方法作了深入分析研究并提出了漂移补 偿改迸方案。 在对多种节点定位方法进行原理分析后，给出三种定位途径及影响定位精度的因素。通 过对现有定位算法的比较分析，提出基于月e 基于测距相结合的节点定位方式。此外，分析 了g p s 定位原理的基础上，探讨了基于脉冲超宽带定位可行性，为课题的进一步深入研究 与具体实现奠定了关键技术研究基础 关键字：无线传感器网络时间同步节点定位成对非基于距离 东南大学硕士学位论文 a b s 仃a c t t h ei s s u eo fe n e r g yi sb e c o m i n gi n c r e a s i n g l yp r o m i n e n tt o d a ya n dt h er e q u i r e m e n to f g e o p h y s i c a le x p l o r a t i o nf o ro nc o n t i n u e st oi n c r e s s e s e n s o rn e t w o r kp l a y sa ni n 甲o r t a mr o l ei n l a r g es c a l eg e o p h y s i c a le x p l o r a t i o nf o ro i l t h et e c h n o l o g yo fs e l u o p 3 d a t aa c q u i s i t i o no fs u c h n e t w o r kh a sg r a d a 曲l yc h a n g e df r o mt h em i xo f b o t hw i r e da n dw i r e l e s sc o m m u n i c a t i o nt ow h o l e n e t w o r kw i r e l e s s b a s e do nt h eb a c k g r o u n dr e s e a r c ho f t h ew i r e l e s sc e l l u l a rl a r g e - s c a l eo i lg e o p h y s i c a ls e i s m i c d a ma c q u i s i t i o nn e t w o r kt e c h n o l o g y , t h i sp a p e rf o c u s e s t h et e c h n o l o g yo f t i m es y n c h r o m z a t i o n a n dl o c a l i z a t i o no fl a r g es c a l ew i r e l e s s i s s o rn e t w o r k s ac o m p r e h a n s i v ei n m x l u c t i o no f b o t ht h e b a s i cp r i n c i p l e sa n dt h et e c h n i c a lf e a t u r e so fw i r e l e s s n s o rn e t w o r k si sg i v e i la tt h eb e g i n n i n g b a s e d t h ea p p r o p r i a t es e l e c t i o no fm a t h e m a t i c a lm o d e lo ft h en o d e s c l o c k , a n dt h r o u g ht h e a n a l y s i so ft h ec l o c ke r r o rs o l l r c e s ，t w ob a s i cm e t h o d so ft i m es y n c h r o n i z a t i o na r cg i v e n r e s e a r c h i n g t h e c o m p a r i s o na m o n gv a r i e t i e s o f e x i s t i n g w i r e l e s ss e n s o rn e t w o r k s t i m e s y n c h r o n i z a t i o ns c h e m e s ，t h e p a p e r f o c u s e so n t h ea n a l y s i s o f p a h - - w i s e ds y n c h r o n i z a t i o n m e t h o d , a n dp u tf o r w a r da ni m p r o v e da l g o r i t h mb yd r i r - c o 岬f i o n a f t e ra n a l y z i n gt h ep r i n c i p l e so fs o m el o c a l i z a t i o ns c h e m e so fw i r e l e s s t l s o rn e t w o r k s ， t h r e el o c a l i z a t i o nc h a n n e l sa n dt h e i rf a c t o r sa f f e c t i n gl o c a l i z a t i o na c c u r a c ya l eg i v e n t h r o u g h a n a l y s i sa n dc o m p a r i s o na m o n gt h ee x i s t i n gl o c a l i z a t i o na l g o r i t h m s 。am e t h o do fl o c a l i z a t i o n b a s e do nt h em i xo f b o t hr a n g e - f t e ea n dr a n g e - b a s e dl o c a l i z a t i o ns c h e m e si sg i v e n i na d d i t i o n , a n a l y z i n gt h ep r i n c i p l ea l g o r i t h mo fg p s ，t h ep a p e ri n v e s t i g a t e st h ef e a s i b i l i t yo fu l t r a - w i d e b a n d p u l s es i 刚p o s i t i o nm e c h a n i s m k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ，t i m es y n c h r o n i z a t i o n l o c a l i z a t i o n , p a i r - w i s e ， r a n g e - f r e e n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示了谢意。 研究生签名：e t 蜘跏8 ；多期：竺：! ：! 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 繇壶己一名：晔日期 第一章绪论 第一章绪论 1 1 课题背景 步入2 l 世纪，随着社会经济的发展，能源问题越来越得到关注。我国的能源需求迅速 增加，石油进口的比例逐年增长。与此形成鲜明对比的是，当今我国陆上大多数主力油田已 经进入中后期开发阶段。而陆上探明资源数量明显不足，未能形成产区的战略接替。海域油 田原油产量所占比重逐渐加大，但份额仍较低。因此亟需新的探明储量来支持现阶段国内能 源的高需求。 同时。信息技术的发展日新月异，极大地改变了我们的生活，也改变了我们的生产方式。 结合信息技术的物探数据采集技术在当今能源勘探技术中处于一个很重要的地位。当前矿藏 的巨大价值日益凸现。在这种背景下，对物探数据采集网络的研究日趋升温。 地震波检测技术是石油勘探技术的一种。传感器网络是地震波检测技术的得力工具。石 油物探地震数据采集中，传感器覆盖范围和密度不断增加成为提高探明率的必然趋势。其网 络面积超百平方公里，传感器间距密度小于2 0 米这样大规模、高密度的传感器网络如果 基于有线传输数据采集，在网络布设、移动、效率、维护、劳动强度等方面有难以克服困难 这就对现有有线布网方式的改变提出了要求。 无线技术在信息技术领域正扮演着越来越重要的角色，通信网络设备无线化已成为必然 趋势。随着无线传感器网络的兴起和相关技术的不断进步，大规模组网下，同传统人工布线、 有线组网相比，无线传感器网络的巨大优势是不言而喻的。石油物探传感器网络的覆盖范围 可达上百平方公里，在这么大的覆盖范围下人工步网，其材料设备需求量、人工需求量之大 是难以想象的，而且网络布设完毕后，不具备任何灵活性维护工作也相当困难采用现有 的有无线混合方式步网( 图1 1 ) ，虽然在一定程度上改进了步网方式但仍然难以从根本上 解决上述问题。 地震石油勘探中，仪器车必须对记录系统和引爆之间的时间同步进行精确控制。一般仪 器车距引爆装置几公里至十几公里，需要通过无线通讯进行引爆，并实现同步采样、记录 地震石油勘探原理决定了该时间同步精度为数据采集系统的关键技术之一”1 。 很多传感器网络应用需知道各节点物理位置的坐标信息，节点定位的重要性在于： l 、须知道传感器感知数据的发生位置才有应用价值。例如。目标跟踪时，传感器探测 出所跟踪的目标，需通过传感器的位置来计算目标位置：火灾报警需要准确的起火地点等 在地震i i 油勘探中，各处传来的震波必须准确对应到详细的地质地形图上，再加以分析研究 才能判断勘探地点的岩层下是否有石油因此各传感器收集的震波信息必须加上自身的位置 信息才有意义。 2 、w s n 的很多通信协议是在已知节点位置的基础上运行的如地理路由就是在无路由 表的情况下实施数据转发，因而具有很好的可扩展性，但条件是要求拥有节点坐标。另外基 l 东南大学硕士学位论文 于节点的已知位置可优化网络运行期间的值守调度机制，使网络中冗余节点不定期地轮休以 延长寿命 地震石油勘探原理同样决定了传感器节点定位为数据采集系统的关键技术之一。而通过 人工测量或配置来获得节点坐标的方法往往不可行。采用全球定位系统( o p s ) 是获得位置信 息的一种方法但是由于大规模传感器网络传感器节点的数量非常巨大。达到数千甚至数万， 成本很高。另外，传感器节点是采用电池供电，其电能不仅十分有限，而且基本不能补充， 因此不适宜每个节点都装备高能耗的g p s 设备。传感器网络通过网络内部节点之间的相互 测距和信息交换，形成一套全网节点的坐标。才是经济可行的定位方案。 上述石油物探原理对于时问同步和节点定位精度的要求，向现有的理论与技术提出了挑 战。特别是在大规模无线步网前提下，如何解决高精度时间同步和节点定位问题，将成为石 油物探传感器网络的技术重点目前国内在这一技术领域还没有找到很好的解决方案，该项 技术的研究，对推动石油物探技术以及无线传感器技术的发展具有重要的意义。 图1 】，现有有无线混合网络v i b t e c hi t s 系统 1 2 项目来源与目标 石油物探的特点决定了为其设计的无线传感器网络是一种大规模的传感器网络，其覆盖 面积为几到几十平方公里，传感器节点数量达到一万个以上，以数十米为间距分布于整个勘 探区。在勘探区引爆后，遍布于勘探区的传感器节点收集地震波信息，并传给数据中心。数 据中心据此进行分析，以获得该地区的石油分布情况的资料。 根据中国石油化工集团的要求，东南大学移动通信国家重点实验室承接该大规模石油物 探无线传感器网络项目的研究与开发，褡建试验网络 2 第一章绪论 以上大规模无线组网的特性，使得其与一般无线传感器网络有本质的区别，决定了网络 必须为分层结构。该项目中，将采用两层网络构架( 如图1 2 ) 这种组网方式统一兼顾了大 覆盖与灵活性，在网络节点密度很大时，具有很高的效率。 。 苫 无缝佑粤无肫基站( m 嚣- 斑由墨) j 【= 聚直( 接八点) 图i 2 、项目网络结构示意图 无墟链路( o f d m i 外l m h 芦) 无线硅略( o f d m 加加啊_ ) 上述组网方式为项目组的研究划定了方向。项目的总体目标为： 验证无线传输与网络技术在物探地震数据采集传感器数据传输中应用的可行性 研究并开发能够适应一定规模应用需求，有无线混合传输采集数据传输技术应用演 示网。 为未来大规模物探地震数据采集传感器数据无线传输网络研究开发奠定关键技术 与实现系统基础。 这就需要项目组研究网络各层之间的联系，制订协议，在差错控制、数据融合、数据处 理、提高效率、网络维护等方面进行研究。 1 3 课题要求与内容 石油物探对高精度时间同步和节点位置信息有很高的要求项目组对这两个方面的需求 也提出了具体要求。在项目中本人主要负责大规模组网下的时间同步技术研究，给出适合网 络的时间同步算法，对其进行仿真和改进。此外，还要对节点定位机制进行研究分析，对比 3 东南大学硕士学位论文 各现有方案的可行性，尤其在有，无g p s 设备的情况下定位机制的不同特性。最终给出适 合项且网络的节点定位方案论证 关于时间同步有两个概念是时间同步课题的两个方面，这两个概念就是“全网时间同 步”和“事件触发同步。前者指通过一定的时间同步机制和算法，使得全网全部节点保持 时问同步；后者指在有突发事件时，由突发的事件“触发”全网节点或部分节点同时工作。 前者研究时间同步机制或算法的糟度、复杂度、同步所需时间、能耗等；后者主要针对触发 方式，研究如何快速，准确的使节点同时工作 对于时间同步的研究将围绕四个方面进行： r 如何授时( 机制，方法) j 精度问题 i 时延问题 、系统维护( 休眠、唤醒) 课题的最终目标希望可以达到微秒级的节点间同步精度，找到快速触发全网的方法，并 在试验网络上加以验证。 节点定位是w s n 系统布设完成后面临的首要问题，它可表述为：依靠有限数量的位置 已知节点，确定布设区中其它节点的位置，在传感器节点问建立起一定的空间关系。这也是 节点定位课题研究的主要内容。此外，定位求精、功耗问题、各类节点密度也是课题研究的 重点。课题最终希望达到5 0 c m 以下的定位精度并给出针对不同网络节点的不同定位方案。 1 4 论文的安排 本文共分六个章节。第一章绪论之后，第二章详细介绍无线传感器网络，描述了网络的 节点结构、拓扑结构、通信协议栈以及协议各层构架，介绍了网络特点以及操作系统。第三 章从原理上分析了时间同步与节点定位技术。在分析误差来源的基础上，给出了两种时间同 步的基本方案。在定位方面，对定位进行分类并描述各自的原理，最后给出定位指标。时间 同步方案的详细研究在第四章进行。在分析了现有各类无线传感器网络时间同步方案的基础 上，重点分析适合项目网络的成对同步方案，给出同步模型，并对误差进行分析。在三种不 同情况下对成对同步的算法进行仿真并分析结果。在此基础上给出改进方案漂移补偿 对其进行仿真分析。随后对两种结构的试验网络进行时同同步仿真分析。第五章对各类定位 算法进行详细研究。分析了现有的定位算法并进行比较给出g p s 定位原理，并在此基础 上分析脉冲超宽带定位的可行性。最后第六章是总结与展望。 4 第二章无线传感器网络技术 第二章无线传感器网络技术 本章主要介绍传感器网络基本知识及其结构和特点，描述了无线传感器网络节点结构、 分层构架及各层的特点。 2 0 世纪9 0 年代以来，随着嵌入式系统、无线通信、网络及微电子机械系统等技术的快 速发展，具有感知、计算和无线网络通信能力的传感器以及由其构成的无线传感器网络 ( w i r e l e s ss e n s o r n e t w o r k 。w s n ) ；i 起了人们的极大关注。由随机分布的，集成有传感器、数 据处理单元和通信模块的微小节点通过自组织的方式构成网络，借助于节点中内置的形式多 样的传感器，协作地实时感知和采集周边环境中众多人们感兴趣的物质现象，并对这些信息 进行处理，获得更为详尽而准确的信息可以在任何时间、绝大多数地点和多种环境条件下 获取大量详实而可靠的信息”1 上述优点为无线传感器网络赋予了广阔的应用前景，主要表现在军事、环境、健康、家 庭和其他商业领域。例如，传感器网络可以向正在准备进行登陆作战的部队指挥官报告敌方 岸滩的详实特征信息，为制定作战方案提供可靠的信息：传感器网络也能用于环境监测帮 助监测人员方便地确定污染物的类型、浓度及位置。实际上，传感器网络为终端用户提供了 对监测环境更智能、更好地理解可以相信，传感器网络必将成为未来信息传输中不可缺少 的一部分。1 2 1 网络特点 w s n 的主要特点有以下几点： ( 1 ) 传感器节点数目大，密度高。为了保证网络的可用性和生存能力，可能有成千上万 的节点，单位空间内，节点密度非常高。 ( 2 ) 传感器节点能量、计算能力和存储容量有限。随着节点的微型化在设计中大部分 节点的能量靠电池提供，能量有限。这是整个w s n 设计的瓶颈直接决定网络工作寿命 另一方面，因传感器节点体积、结构限制，使得其不能进行复杂的计算和数据存储。 ( 3 ) w s n 拓扑结构易变化，具有自组织能力。由于节点节能的需要，节电可以在工作和 睡眠状态之间切换，也可能随时有节点因故障而失效或网络中添加新的节点。这些情况的发 生都使得w s n 的拓扑结构在使用中很容易发生变化。 ( 4 ) 传感器节点具有数据融合能力w s n 中由于传感器数目巨大，很多节点都会采集 到具有相同类型的数据，因而要求其中的一些节点具有数据融合能力，能对来自多个传感器 采集的数据进行融合再上传处理。数据融合可以减少冗余数据，从而减少在传送过程中的 能量消耗，延长网络的寿命。 5 东南大学硕士学位论文 2 2 节点结构 无线传感器网络的节点结构“1 如图2 1 所示 图2 1 俺感器节点结构模型 节点由传感单元、数据处理单元、数据传输和电源这4 部分组成。传感单元由传感器和 数模转换设备组成。数据处理常选用低功耗嵌入式微控制器。数据传输单元主要有相应的通 信协议及低功耗、短距离的无线通信模块组成。因为需要进行较复杂的人物调度和管理，系 统还需要一个微型化的实时操作系统电源一般由节点自带的各类小型电池提供。 2 3 拓扑结构 无线传感器网络的拓扑结构有3 种”1 ，如图2 2 ：星状网、网状网及混合网。每种拓扑 结构都有自身的优点和缺点。 基本的星状网拓扑结构是一个单跳系统，网络中所有无线传感器节点都与基站和网关进 行双向通信。基站可以是一台p c 、p d a 、嵌入式同络服务器或其它网关，除了向各节点传 输数据和命令外，基站还与因特网等更高层系统之间传输数据。各节点将基站作为个中间 点，相互之间并不传输数据或命令在各种无线传感器网络中。星状网整体功耗最低，但节 点与基站间的传输距离有限，般只有几十米 网状拓扑结构是多跳系统，其中所有无线传感器节点都相同，而且直接互相通信。网状 网的每个传感器节点都有多条路径到达网关或其它节点，因此它的容故障能力较强。这种多 跳系统比星状网的传输距离远得多，但功耗也更大，因为节点必须一直“监听”网络中某些 路径上的信息和变化 混合网力求兼具星状网的简洁和低功耗以及网状阿的长传输距离和自愈性等优点在混 合网中，路由器和中继器组成网状结构，而传感器节点则在它们周围呈星状分布中继器扩 6 第二章无线传感器网络技术 展了网络传输距离，同时提供了容故障能力。当某个中继器发生故障或某条无线链路出现干 扰时，网络可在其它路由器周围进行自组。 qp 、 n d j、 ， ao 星状结构 p 一譬- q 、 ? 。 t 一心、一0 、 v j 了。i 蔓，：，f q 、o (y一一_，：jjk：；三：j，ii、) 2 4 网络分层构架 混合结构 图2 2 、w s n 的三种拓扑结构 传感器节点的典型协议栈“1 如图2 3 所示 图2 3 、传感器节点协议栈 7 东南大学硕士学位论文 该模型既参考了现有通用网络的t c p i p 和o s l 模型的架构，同时又包含了传感网络特 有的电源管理、移动管理及任务管理。应用层为不同的应用提供了一个相对统一的高层接口： 如果需要，传输层可为传感网络保持数据流或保证与i n t m n e t 连接：网络层主要关心数据的 路由；数据链路层协调无线媒质的访问，尽量减少相邻节点广播时的冲突：物理层为系统提 供个简单、稳定的调制、传输和接收系统。除此而外，电源、移动和任务管理负责传感节 点能量、移动和任务分配的监溯，帮助传感节点协调感测任务，尽量减少整个系统的功耗。 2 4 1 物理层 物理层主要负责信号的调制解调、信号的发送和接收、功率控制等任务。目前电子电路 的技术水平在传送和接收相同长度的比特数据时发射所需的能量 接收所需的能j c p u 处理所需的能量。考虑到无线传感器网络节点的能量是十分有限的，节能对延长网络的生存 时间是十分重要的如何进行动态功率的管理和控制是无线传感器网络的一个非常重要的课 题。 2 4 2 数据链路层 数据链路层负责媒体接入控制和建立节点之间可靠的通信链路，主要由介质访问控制 ( m a c ) 组成。传统的基于竞争机制的m a c 协议很难适应无线传感器网络的需要。因为基于 竞争机制的m a c 协议需要多次握手，数据发生冲突的几率很大。造成能量的浪费，这在无 线传感器网络中是不可取的。因此，无线传感器网络的m a c 协议一般采用基于预先规划的 机制如t d m a 来保护节点的能量 m a c 层是无线传感器网络的研究热点之一。也是本项目研究的另一重点。 2 4 3 网络层 网络层的主要任务是发现和维护路由。因为多跳通信比直接通信更加节能，这也正好符 合数据融合和协同信号处理的需要，在无线传感器网络中，节点一般都采用多跳路由连接信 源和信宿。无线传感器网络必须开发属于自己的路由协议，主要是由于无线传感器同络具有 很强的具体应用背景，一个传感器网络通常是为某个具体的应用场合设计的，因此很难采用 通用的路由协议。和传统的以地址为中心的路由协议不一样。无线传感器网络的路由协议是 以数据为中心的没有一个全局的标识。一般是基于属性的寻址方式，通常采用按需的被动 式路由方式。 关于路由层的研究是无线传感器网络研究领域的一个十分活跃的分支，也是本项目的研 究重点。 当前很多无线传感器网络协议是基于传统的分层结构设计的这种分层结构实际上是一 种局部的次优方案。由于无线传感器网络的资源，如能量、带宽和节点的资源等是十分有限 8 第二章无线传感器网络技术 的，这种分层的次优结构很难适应无线传感器网络的发展需要。跨层设计“1 实际上是通过层 与层之间的信息共享来优化整个网络的性能。 不同的网络体系需要不同的设计方案，不同的应用同样要有不同的设计方案无线传感 器网络是一种基于应用的网络，具有很强的应用背景。无线传感器网络的具体应用环境常常 要求网络的生存时间要足够长、网络时延要尽量短，例如本项目时间同步中的“事件触发同 步”，这和无线传感器网络有限的能量供应、有限的节点资源和带宽是一对矛盾，传统的分 层结构很难解决这个问题。因此，需要引入跨层设计。特别在无线传感器网络这种无线通信 环境中，由丁各个层之间是紧密联系的，更加有必要跨层地考虑问题。 目前无线传感器网络已经有一些关于跨层设计的例子，如能量有效的m a c 协议、基于 能量的路由协议、对资源警觉的数据压缩等。下面举个简单的例子来说明传感器网络各个层 之间是如何协调地进行设计的。考虑无线传感器网络中传输的数据包大小的优化问题。为了 达到这个目的，要综合考虑网络层、m a c 层和物理层。从路由层的观点来看当数据包要 进行远距离传输时，数据包要求小一点。因为此时，如果是不可靠传输，数据包较小的话， 对这个事件的影响也较小：如是可靠传输，重传也较小。另外一个方面，包变小了，一个事 件所需要的传输次数就变多了从m a c 层的角度看包冲突的几率就变大了，这样m a c 层的能量消耗也就变大了。因此，在考虑传输包的大小时，要根据当前网络的总体状况，在 当中寻找一个折中的方案 跨层设计是最近很热门的一个研究方向，它基于层与层之间的信息共享提高各个层的适 应性，有望使整个网络性能得到很好的提高。但是，层与层之间的联合优化将会带来高复杂 度的算法，这对无线传感器网络节点的运算能力是一个极大的挑战 在本项目当中，石油物探的大规模无线传感器网络最大的特点是规模大、节点多，在组 网、数据传输和控制方面与一般小型传感器网络有很大不同，这就要求物理层、m a c 层和 网络层以及高层之问的设计不能孤立地进行，必须统筹兼顾，这正是跨层设计的一个缩影 以本人研究课题中的时间同步技术为例，与各层关系相对独立，但并非没有联系。如其 同步精度分辨率最终直接由物理层每b i t 时间来决定；时延与m a c 层接入时间息息相关； 网络层对于路由的确定，其跳数对时延亦有重要影响。也可作为定位信息的重要依据。其结 构如图2 4 所示。 争? 孽掣t 问莲 畿渺 孕赫嘲磷秘嘲单龋鞫黼翱_ ， ! 4 墨 & 塑愿i 爨。遴，薹蕊 图2 4 、时间同步与各层之间的关系 9 东南大学硕士学位论文 2 s 操作系统 操作系统是支撑无线传感器网络的关键技术之一，传统的操作系统w i n d o w s 和u n i x 显 然不能满足无线传感器网络的需要。人们需要开发新的操作系统，它既要能满足无线传感器 网络特殊的需要，又要能高效地利用无线传感器网络节点的有限硬件资源来为应用软件提供 服务。 美国加州大学伯克力分校计算机科学系“智能尘埃”课题组基于多线程技术，开发了一 种微型操作系统t i n y o s 就是为了适应这种需要产生的。这是一种基于组件( c o m p o n e n t - b a s e d ) 的构架方式能够快速地实现各种应用。另外一种无线传感器网络微型操作系统是由 美国科罗拉多大学开发的m a n t i so s ，它支持快速、灵活地构架无线传感器网络“1 。 1 0 第三章w s n 节点时间同步与定位技术原理 第三章w s n 节点时间同步与定位技术原理 本章从原理上分析了时间同步与节点定位技术。首先给出了w s n 节点时钟的数学模型。 在分析误差来源的基础上，给出了两种时间同步的基本方案。在定位方面，对定位进行分类 并描述各自的原理，最后给出定位指标。通过对定位原理的分析，给出三种定位途径及影响 定位精度的因素。 3 1w s n 节点时钟模型 在现代信息处理系统中，时钟通常用晶体振荡器脉冲来度量“3 ，即 c 形2 后j ：c o ( f ) d r + c 俐 ( 3 1 ) 其中：是晶振的频率：i 是依赖于晶振物理特性的常量；f 是真实时间变量；c 似是 构造的本地时钟，间隔c ( o c ( t o j 被用来作为度量时间。对于理想的时钟，有 ，似= d c ( t ) d t = 1 ，也就是说理想时钟的变化速率r 为1 ，但在工程实践中因为温度、 压力、电源电压等外界环境的变化往往会导致晶振频率产生波动。因此，构造理想时钟比 较困难。但在一股情况下，晶振频率的波动幅度并非任意的，而是局限在一定的范围之内 为了方便描述和分析定义如下3 种时钟模型“1 ： ( 1 ) 速率恒定模型 速率恒定模型假定时钟速率，倒= d c 似d t 是恒定的，即晶振频率没有波动发生当要 求的时钟精度远低于频率波动导致的偏差时，该模型的假定应该是合理的。 ( 2 ) 漂移有界模型 定义时钟速率吖p 相对于理想速率i 的偏差为时钟漂移p ( t ) ，即p ( t ) = r 例1 漂移 有界模型满足下面的约束条件： 一p m , x p ( f ) p m - x ，v t ( 3 2 ) 此外我们还有p ( t ) 一1 ，它的物理意义是时钟永远不会停止( p ( f ) = 一1 ) 或倒走 ( p ( f ) 3 ) 个参考节点另，乃j ，乞， ，t 只化，儿，到未知节点距离分别为d l 喀，吒。设m 坐标为0 ，y ) ，则满足： x l 严+ ( y y l p = d ： x 。户+ 一y 。严= ( 3 8 ) 通常采用极大似然估计法( m “i m u ml i k e l i h o o de s t i m a t i o n ，m l e ) 。其解可用 线性方程组表示为从= b ，其中 1 8 露 第三章w s n 节点时间同步与定位技术原理 a = 2 ( x t x 。)y | ) 2 ( x 。r x 4 ) 2 y 。r y 。) x = ( 匀 f 工石：+ ) ，；z + 彰一d ；、 6 。 x l - x ：+ y l ! z + d ：一j j 3 9 使用标准的最小均方差估计法可以得到节点m 的坐标为： 雪= c a 7 彬。a 7 b( 3 1 0 ) 此方法在测距存在一定误差的情况下仍能达到相当高的定位精度，然而其缺点在于需要 进行较多的浮点运算，其计算开销带来的能量消耗仍不容忽视，故而有必要寻求更为简单的 替代算法 3 3 2 3 迭代优化与递归定位“1 该阶段是可选的，主要目的是优化上一阶段中节点位置的计算结果，由于并非前两个阶 段中所有有用的信息都会起到作用，且测距和计算的过程中本身就存在相当可观的误差因 此上一阶段计算出的位置并不十分准确，即便是在连通度较高、测距误差较小的理想条件下 迭代优化可以根据预设的定位精度使用卡尔曼滤波技术在每个协作子树范围内( 每个节点 位置有唯一解) 对第二阶段的结果进行循环求精，可选用分布式或集中式两种计算模式 递归定位思想就是首先使用前两阶段的定位，当部分未知节点成功定位自身后，将其升 级为参考节点，并进入下一次循环，直到所有节点定位或没有满足原子和协作式定位条件的 节点存在时结束。该方法能够在一定程度上解决参考节点数量不足的问题然而又可能因前 次循环定位过程中产生的误差而致使误差传播的积累效应不可忽视，在迭代次数较多的情况 下，后续的定位结果可信程度将大大降低。 上述三个定位途径可看作是一般性定位的一个通用过程：由距离到坐标，再最后逐步求 精。并不是每次定位都需要执行这三步，可以根据需要选择。如只需要测距，则不需要2 、 3 两步，只有在需要定位精度很高、定位所需时间又比较充裕的情况下，才需要三步都执行。 3 3 3 影响定位精度的因素 w s n 自身定位系统和算法的性能直接影响其可用性，如何评价它们是一个需要深入研 究的问题。下面定性地讨论几个常用的评价标准“”。 ( 1 ) 定位精度 定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程的比例表示，例 如，定位精度为2 0 表示定位误差相当于节点无线射程的2 0 。也有部分定位系统将二维 9 东南大学硕士学位论文 网络部署区域划分为网格。其定位结果的精度也就是网格的大小，如微软的r a d a r ， w i r e l e s sc o r p o r a t i o n 的r a d i o c a m e r a 等 ( 2 ) 规模 不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅是一个房间内实 现定位。另外，给定一定数量的基础设旌或在一段时间内一种技术可以定位多少目标也是 一个重要的评价指标。例如，r a d a r 系统仅可在建筑物的一层内实现目标定位 ( 3 ) 锚节点密度 锚节点定位通常依赖人工部署或g p s 实现人工部署锚节点的方式不仅受网络部署环 境的限制，还严重制约了网络和应用的可扩展性。而使用g p s 定位，锚节点的费用会比普 通节点高两个数量级，这意味着即使仅有1 0 的节点是锚节点整个网络的价格也将增加 1 0 倍，但这仍然是无法避免的好的定位算法设计在锚节点的需求量上与一般方法有很大 区别，这直接影响系统造价，因此锚节点密度也是评价定位系统和算法性能的重要指标之 h ) 节点密度 在w s n 中。节点密度增大不仅意味着网络部署费用的增加，而且会因为节点问的通信 冲突问题带来有限带宽的阻塞。节点密度通常以网络的平均连通度来表示。许多定位算法的 精度受节点密度的影响，如d v - h o p 算法仅可在节点密集部署的情况下台理地估算节点位 置 ( 5 ) 容错性和自适应性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的网络节点设备。但在真 实应用场合中常会有诸如以下的问题：外界环境中存在严重的多径传播、衰减、非视距、通 信盲点等问题；网络节点由于周围环境或自身原因( 如电池耗尽、物理损伤) 而出现失效的 问题：外界影响和节点硬件精度限制造成节点问点到点的距离或角度测量误差增大的问题 由于环境、能耗和其他原因，物理地维护或替换传感器节点或使用其他高精度的测量手段常 常是十分困难或不可行的。因此定位系统和算法的软、硬件必须具有很强的容错性和自适 应性，能够通过自动调整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位精 度 ( 6 ) 功耗 功耗是对w s n 的设计和实现影响最大的因素之一。传感器网络的各类设计可以说都是 围绕功耗展开。由于传感器节点电池能量有限，因此在保证定位精度的前提下，与功耗密切 相关的定位所需的计算量，通信开销、存储开销、时间复杂性是一组关键性指标 ( 7 代价 定位系统或算法的代价可从几个不同方面来评价。时婀代价包括一个系统的安装时间、 配置时间、定位所需时间。空间代价包括个定位系统或算法所需的基础设旌和网络节点的 数量、硬件尺寸等。资金代价则包括实现一种定位系统或算法的基础设施、节点设备的总费 用。 第三章w s n 节点时间同步与定位技术原理 上述7 个性能指标因素不仅是评价w s n 自身定位系统和算法的标准。也是其设计和实 现的优化目标。为了实现这些目标的优化，有大量的研究工作需要完成。同时这些因素是 相互关联的，必须根据应用的具体需求做出权衡，以选择和设计合适的定位技术。 2 1 第四章w s n 时间同步方法研究 第四章w s n 时间同步方法研究 本章在分析w s n 时间同步局限性的基础上，介绍了符合本项目网络特性的几种时间同 步方法并进行比较分析。选择适合项目网络的“成对同步”并给出其模型和原理，进行误 差分析。就成对同步算法在三种情况下的性能进行仿真，对结果进行分析比较。在此基础上， 对传统成对同步方式进行改进，引入对时钟漂移的补偿修正并进行仿真。最后对两种试验网 络的时间同步进行仿真分析。 4 1 现有时间同步方法技术分析 4 1 1r b s ( r e f e r e n c eb r o a d e a s ts y n c h r o n i z a t i o n ) r b s 1 算法是由加州大学j e r e m ye i s o n 等2 0 0 2 年提出的以“第三方广播”的思想让参 照节点利用物理层广播周期性地向网络中其它节点发送参照广播，广播域中的节点用自己的 本地时钟记录各自的包接收时间，然后相互交换记录的时间信息。通过这种方式，接收节点 能够知道彼此之问的时钟偏移量然后利用偏移矩阵计算相对其它所有节点时钟偏移的平均 值。并用它对本地时钟进行相应调整当每个节点都取得相对其它所有节点时钟偏移量的平 均值时，所有接收到同一参照广播消息的接收节点便获得了一个相对网络时间 r b s 基于接收接收( r e c e i v e r - r e c e i v e r ) 方式，即多个接收者之间进行时间同步在接收 者之间互相交换信息，排除了发送方对同步精度的影响。第三方节点广播若干次同步信令， 广播域内各节点利用本地时钟记录信令的到达时刻，然后各接收节点之间交互时间记录，进 而两两校准时钟。r b s 算法利用了无线信道的广播特性，第三方信息基本同时到达广播域 内的所有接收站，消除了发送端时延的影响。而后，接收节点之闻交互信令序列到达时间， 利用最小方差线性拟合方法估计彼此之间的相位差和频率偏差。 节点发送参考消息给他的相邻节点，那些相邻节点记录下参考消息的到达时间，然后彼 此之间交换信息，某个节点通过计算可获得其本地时钟与其他节点时钟偏移量的平均值，进 而可以同步。 r b s 对多跳的支持是利用位于相邻广播域中的节点来完成时间信息转换的，通过这种 转换来同步网络中不同域中节点的时间实验表明，相邻的节点用3 0 个参照广播同步的平 均误差为l l z s l l l 最简单的r b s 形式是对2 个接收者的单脉冲广播。如图4 1 ： 一个发送者向二个接收者( i j ) 广播一个参考包。 每个接收者将参考包的到达时间( 相对本地时钟) 记录下来 接收者之间交换它们的记录。 东南大学硕士学位论文 图4 1 ，r b s 算法示意图 方案的性能与以下三个因素密切相关： 要同步的接收者的数目。 接收者的不确定性 接收者的时钟漂移。 对于多个接收者。发送者可以通过发送多个参考包来增加统计同步精度。相对偏移可按 式“1 ) 1 计算： 小一：啦，【f 一善( 巩一) ( 4 。) i ：接收者i j ：接收者j n ：接收机数量 m ：参考广播数量 z j ：节点r 接收到广播b 的时钟 由于采用接收者之间进行同步的方法，在关键路径中排除了发送方发送时间和访问时间 对同步精度造成的影响，多个参照广播允许更紧密地同步，且可以克服接收者之间较大的时 问偏移，还可以估计时钟偏差，并由此推断过去的偏移，这使事后同步可以在不经常和不可 预测地需要时间同步的应用中节约能量。r 8 5 允许节点创建本地时标，这对传感器网络或 其他需要同步的时间但又没有绝对参照时间的应用是有用的。当然它也可以维持绝对时标 1 1 2 1 r b s 的缺点是对网络有一定的要求，它不适合点对点通信的网络且要求网络有物理 广播信道。扩展性不好，因为节点间本地时间戳通信需要额外的消息交换开销，不能很好地 应用到大规模的多跳网络中。r b s 有很大的交换次数，对于具有n 个节点的单跳同络，需 第四章w s n 时问同步方法研究 要o ( n 2 ) 的消息交换，如果1 1 很大时，消息交换开销是相当大的，导致节点的计算开销也非 常之大。r b s 中接收节点之问进行相互同步，但并不与发送节点同步；实际上，在w g n 中 发送节点很可能也是一个普通的网络节点因而也需要同步，为使该节点和其它节点进行同 步，需要另外一个节点作为参照广播发射节点，这导致了相当高的能耗。 此外。在一般w s n 中，因为接收节点之间距离不远，传播时延差可以忽略，但在如石 油勘探这样的大型w s n 中，传播时延不能被忽略，这成为r b s 作用于大规模w s n 的瓶颈 4 2 2t 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 ) 基于发送- 接收( s e n d e r - r e c e i v e r ) 方式即同步在一个发送者和一个接收者之间成对进 行，同步采用典型的握手方式，两次消息交换法取得一对节点间的时钟同步t p s n 类似于 h l t e r n e t 所采用的n t p ( n c q w o r kt i m ep r o t o c 0 1 ) 算法，基于客户机，服务器架构。待同步节点向 基准节点发送同步请求包，基准节点回馈包含当前时间的同步包，待同步节点估算时延并校 准时钟。 t p s n 算法采用m a c 层打时间戳技术，避免了协议发送时延、接入时延和接受处理时 延( 详见4 2 2 1 ) 的影响，并通过构造分层网络实现多跳同步”1 。t p s n 采用双向通信，可 以把传送时延、传播时延和接收时延的影响降低5 0 。t p s n 的重要价值在于采用简单实用 的成对同步，它的原理以及在时延上的优势将在下- - d 节中详细描述。 t p s n 为传感器网络的时间同步问题提供了一种简单、有效并可升级的解决方案。此外， t p s n 非常灵活可以很容易的进行调整以满足精度要求以及更高级的算法。t p s n 同样可 以辅助改善传感器网络一些其他基本应用的精度，比如定位，目标跟踪、聚合。 t p s n 同