（电路与系统专业论文）一种无需测距的无线传感器网络节点定位技术研究[电路与系统专业优秀论文].pdf

武汉理工大学硕士学位论文 摘要 无线传感器网络在军事国防、环境监测、抢险救灾和危险区域的远程控制 等诸多领域具有广泛的应用前景。网络节点或监测目标的定位是其中众多应用 的一个关键条件，而且无线传感器网络的某些路由机制、覆盖信息、负载均衡 和拓扑控制等都依赖于网络中传感器节点的位置信息。因此，定位在无线传感 器网络的应用、运行和管理等方面都有着重要作用，针对无线传感器网络节点 自身定位技术的研究也具有重要的理论与实际意义。 传感器网络中的定位问题包括节点自身定位和外部目标定位两部分，其中 后者依赖于前者。本文研究无线传感器网络节点自身定位的相对定位算 法t v - p h a s e 定位算法。本文主要的研究工作从以下几个方面展开： ( 1 ) 首先归纳总结了无线传感器网络的体系结构、特点、应用范围、国内 外研究现状以及无线传感器网络定位的关键技术和基本原理。 ( 2 ) 其次分析t d v - h o p 定位算法的机制，并在仿真章节将其与另外一种基 于跳数机制的算法进行了比较。 ( 3 ) 同时还分析了t e r r a i n 算法的原理，它是在节点相互连通的情况下， 通过r s s i ( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) 或单跳邻居节点信息进行拓展半径 的获取，节点在获取至少三个锚节点信息后采用三边测量方法进行自身定位， 实验数据显示这种定位误差呈指数趋势上升。 ( 4 ) 在第四章对采用的t w o p h a s e 定位算法迸行了改迸。在迸行全局泛浃之 前，结合线性回归方式算出节点之间的单跳测距值，在第一阶段采用 h o p - t e r r a i n ( t r i a n g u l a t i o nv i ae x t e n d e dr a n g ea n dr e d u n d a n ta s s o c i a t i o no f i n t e r m e d i a t en o d e s ) 算法将单跳距离值广播，进行大致节点位置的估计，在循环 求精( r e f i n e m e n t ) 阶段，针对不同节点引入不同置信参数使用加权最小二乘法 进行三边测量方法以计算更精确的新位置。 ( 5 ) 最后在m a t l a b 仿真平台上进行仿真实验，对比算法在不同锚节点数 目下的定位精度，并在文章最后章节进行了全文的总结与展望。 关键字：无线传感器网络，d v - h o p ，h o p - t e r r a i n ，循环求精，节点自身定位 武汉理工大学硕士学位论文 a b s t r a c t w i r e l e s ss e n s o rn e t w o r k sh a v eg r e a tp r o s p e c ti nt h ea p p l i c a t i o n so fm i l i t a r y a f f a i r s ，c i r c u m s t a n c eo b s e r v a t i o n , d i s a s t e rr e l i e f o p e r a t i o n , d a n g e r o u s a r e a d o m i n a t i o n ，e t e o n eo ft h ek e yq u a l i f i c a t i o n sf o rt h e s ea p p l i c a t i o n si sl o c a l i z a t i o no f t h et a r g e t sn e e d e dm o n i t o r i n ga n dt h en e t w o r kn o d e a n ds o m er o u t i n gs c h e m e ， i n f o r m a t i o no f n e t w o r kc o v e r a g e ，l o a db a l a n c e ，t o p o l o g yc o n t r 0 1 a l lo f w h i c hd e p e n d o nt h el o c a t i o ni n f o r m a t i o no ft h en o d e si nn e t w o r k s a 1 lt h e s ei n d i c a t et h a t l o c a l i z a t i o ni saf u n d a m e n t a la n dc r i t i c a li s s u ef o rt h ea p p l i c a t i o n , o p e r a t i o na n d m a n a g e m e n to fw i r e l e s ss e l i s o rn e t w o r k s t h es t u d yf o rs e l f - p o s i t i o n i n go fw i r e l e s s 默m s o rn e t w o r k sp o s s e s s e sg r e a ts i g n i f i c a n c ei nt h et h e o r ya n dp r a c t i c e a n di tw i l l b e c o m e 觚i m p o r t a n tp a r ti nt h er e s e a r c ha r e a t h ew i r e l e s ss e n s o rn e t w o r kp o s i t i o n i n gs y s t e mc o n t a i n ss e l f - p o s i t i o n i n ga n d t r a c k i n go u t s i d et a r g e t s ，a n dt h el a t e ra l w a y sd e p e n d so nt h ef o r m e r i nt h i st h e s i s t w o - p h a s ep o s i t i o n i n ga l g o r i t h mi sr e s e a r c h e da n dt h em a i nw o r k sa l ed e p l o y e da s f o l l o w s ： ( 1 ) t h ef r a m e w o r ko fw i r e l e s ss e n s o rn e t w o r k s , i t sc h a r a c t e r i s t i c s ，a p p l i c a t i o n a n dr e s e a r c h i n gs i t u a t i o n sa th o m ea n da b r o a da l es u m m a r i z e d s o m ek e y t e c h n o l o g i e sa n dp r i n c i p l eo f n o d e sp o s i t i o n i n ga l ea l s oa n a l y z e d ( 2 ) t h em e c h a n i s mo fd v - h o pa l g o r i t h mi sa n a l y z e da n dac o m p a r i s o nw i t h a n o t h e ra l g o r i t h mb a s e do nh o pm e c h a n i s mi sa l s op r e s e n t e di nt h es i m u l a t i o n s e e t i o n ( 3 ) t h ep r i n c i p l eo ft e r r a i n ( t r i a n g u l a t i o nv i ae x t e n d e dr a n g ea n dr e d u n d a n t a s s o c i a t i o no fi n t e r m e d i a t e n o d e s ) i sp r e s e n t e d o nt h ec o n d i t i o no fn o d e s c o n n e c t i v i t y , i tu s e sr s s i ( r e c e i v e ds i g n a ls t r e n g t hi n d i c a t o r ) t e c h n o l o g yo ri t so n e h o pn e i g h b o ri n f o r m a t i o nt og e te x t e n d e dr a n g et oc o m p u t et h ec o o r d i n a t i o no f n o d e s w h e nt h et a r g e tn o d ea c q u i r e sa tl e a s tt h r e ea n c h o r si n f o r m a t i o n , b u tt h ee x p e r i m e n t d a t as h o w st h et e r r a i na l g o r i t h md i r e c t l ys u f f e r sf r o ma nu n a c c e p t a b l eh i 曲 t e n d e n c yt oe x p o n e n t i a l l yi n t e n s i f ye n d fl e v e l s 武汉理工大学硕士学位论文 ( 4 ) 1 h ct w o p h a s ep o s i t i o n i n ga l g o r i t h ma d o p t e di nt h et h e s i si si m p r o v e d a n dt h em a t hr e g r e s s i o nm e t h o da p p l i e di nt h et w o p h a s ea l g o r i t h mi su s e dt o c o m p u t et h eo n eh o pr a n g em e a s u r e m e n tb e f o r ef l o o d i n g a ts t a r tp h a s e ，t h e h o p - t e r r a i na l g o r i t h mb r o a d c a s t st h i so n eh o pr a n g ei n f o r m a t i o na n de s t i m a t e s t h ec o a r s ev a l u eo ft h en o d e si nt h en e t w o r k i nt h er e f i n e m e n tp h a s e ，i tu s e st h e w e i g h t e dl m s t ot r i a n g u l a t en e w p o s i t i o n so f n o d e si nt h en e t w o r k ( 5 ) a tl a s t , d i f f e r e n ta l g o r i t h m su n d e rd i f f e r e n tn u m b e ro fa n c h o r sa r e s i m u l a t e do nt h em a t l a bp l a t f o r m 1 1 l es i m u l a t i o nr e s u l t si n d i c a t et h a tt h e i m p r o v e da l g o r i t h mh a sab e t t e rf e a s i b i l i t ya n dp r a c t i c a b i l i t y i nt h el a s ts e c t i o n , i t c o n c l u d e st h et h e s i sa n dp r o s p e c t st h ef u t u r ew o r ko fp o s i t i o n i n gs c h e m ei nw i r e l e s s s e n s o rn e t w o r k s 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 s ，d v - h o pp o s i t i o n i n ga l g o r i t h m , h o p - t e r r a i np o s i t i o n i n ga l g o r i t h m ，r e f i n e m e n tp o s i t i o n i n ga l g o r i t h m ， s e r f - p o s i t i o n i n gs y s t e m m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写的成果，也不包含为获得武汉理工大学或其它教育机构学 位证书而使用过的材料。与我一起工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 签名：缝日期：二啦 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 凝；壅p w 武汉理工大学硕士学位论文 1 1 项目来源 第1 章绪论 本学位论文的研究工作主要得到如下项目的资助： ( 1 ) 教育部博士点基金“无线传感网络在结构健康监测中的数据同步和融合 技术研究”( 2 0 0 5 0 4 9 7 0 0 6 ) ( 2 ) 新世纪优秀人才支持计划“无线传感网络技术在结构健康监测中的应用 及装备”( n c e 0 5 0 6 5 7 ) ( 3 ) 湖北省青年杰出人才基金项目“面向结构工程健康监测的无线传感器网 络研究”( 2 0 0 6 a b b 0 2 8 ) 1 2 研究背景 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟，具 有感知能力、计算能力和通信能力的微型传感器开始在世界范围内出现。由这 些微型传感器构成的传感器网络引起了人们的极大关注。这种传感器网络综合 了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术，能够协作 地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息，并对 这些信息进行处理，获得详尽而准确的信息，传送到需要这些信息的用户。例 如，传感器网络可以向正在准备进行登陆作战的部队指挥官报告敌方岸滩的详 实特征信息，如丛林地带的地面坚硬度、干湿度等，为制定作战方案提供可靠 的信息。传感器网络可以使人们在任何时间、地点和任何环境条件下获取大量 详实而可靠的信息。因此，这种网络系统可以被广泛地应用于国防军事、国家 安全、环境监测、交通管理、医疗卫生、制造业、反恐抗灾等领域。传感器网 络是信息感知和采集的一场革命。传感器网络作为一个全新的研究领域，在基 础理论和工程技术两个层面向科技工作者提出了大量的挑战性研究课题。 传感器网络系统是当今前沿性的热点研究方向之一，有着巨大的科学意义 和应用前景，被认为是将对2 1 世纪产生巨大影响力的高技术之一。2 0 0 3 年2 月份 武汉理工大学硕士学位论文 的美国技术评论i l i 杂志评选出对人类未来生活产生深远影响的十大新兴技术， 传感器网络即被列为第一。美国商业周刊在2 0 0 3 年8 月的技术评论中，已经 将传感器网络定位成2 1 世纪高技术领域的四大支柱型产业之一，其潜在的市场 需求十分巨大。 1 3 国内外研究现状 由于传感器网络的巨大应用价值，它已经引起了世界许多国家的军事部门、 工业界和学术界的极大关注。美国自然科学基金委员会2 0 0 3 年制定了传感器网 络研究计划，投资3 ，4 0 0 万美元，支持相关基础理论的研究。美国国防部和各 军事部门都对传感器网络给予了高度重视，在c 4 i s r 的基础上提出了c 4 k i s r 计 划，强调战场情报的感知能力、信息的综合能力和信息的利用能力，把传感器 网络作为一个重要研究领域，设立了一系列的军事传感器网络研究项目。美国 国防高级研究计划局把智能传感器及网络作为一项最高优先发展的研究计划， 出资近7 亿美元，以求获得所谓战区“超视觉”数据。美国国家科学基金会n s f 一 期资助4 0 0 0 万美元在u c l a 成立了传感器网络研究中心，联合各高校展开“嵌入 式智能传感器”的研究项目，以求对物理世界实现全方位的监测与控制。美国英 特尔公司、美国微软公司等信息工业界巨头也开始了传感器网络方面的工作， 纷纷设立或启动相应的行动计划。欧盟2 0 0 2 年开始实施为期3 年的e y e s ( 自组 织和协作有效能量的传感器网络) 计划。2 0 0 4 年3 月，日本总务省成立“泛在传感 器网络( u b i q u i t o u ss e n s o r n e t w o r k ) ”调查研究会。英国、意大利、巴西等国家 也对传感器网络表现出了极大的兴趣，纷纷展开了该领域的研究工作。国外的 一些著名大学，如加州大学洛杉矶分校、康奈尔大学、麻省理工学院和加州大 学伯克利分校等也先后开展了传感器网络方面的研究工作。加州大学洛杉矶分 校在生态监控方面研究了小气候传感器和视频传感器网络技术，在地震监控和 响应结构方面研究了数据通信控制器和网络时间同步、传感器可靠部署、宽带 地震网络、结构检测的无线地震监控网络。加州大学伯克利分校实旆了w i n s 项 目，项目包括n e s t ( 网络嵌入系统技术) ，为网络嵌入系统开发了一系列的软 硬件实验平台，包括在小型传感器器上运行的t m y o s t 2 1 操作系统，t o s s i m 模拟 器，数据查询系统t m y d b ，以及在t i n y o s 上运行的编译器n e s c ，用于传感器网 络的定位系统c a l a m a r i ，链路层加密算法t i n y o s n 络的数据流管理系统集成框 2 武汉理工大学硕士学位论文 架，查询优化技术，网络节约能量的拥塞控制等，中间件技术比如定位、追踪 和联网等，大型传感器网络可扩展算法，还研究了传感器网和移动装置网的分 布算法，这些研究获得了n s f 、d a r p a 和空军太空实验室的支持。 在国内传感器网络系统方面的研究起步较晚，近年来才受到广泛的关注。“传 感器网络系统的基础软件及数据管理关键技术的研究”已被列为国家自然科学基 金委员会信息科学部与微软亚洲研究院正式签署的第二期联合资助项目之一， 国家“十五”科技攻关项目把传感器网络列为重大研究项目。对传感器网络系统信 息获取与处理相关技术的研究，符合国家的整体科技发展计划，对国防科学技 术和国家经济建设具有重要的战略意义。在国防技术方面，传感器网络信息获 取与处理系统可以将大量地理上分散的战区传感器、指挥控制中心、主战武器 平台以及处于动态移动的目标等联系起来，从而提高综合战斗能力和预防能力。 在民用方面，在环境监测、生态保护、交通、工业控制等方面，传感器网络可 以为我们及时准确的提供全方位的监测手段和监测信息。 1 4 研究内容与论文组织 普遍网络化孕育的无线传感器网络是一种新的信息获取和处理技术。在特 殊领域，它有着传统技术不可比拟的优势，同时也必将开辟出不少新颖而有价 值的商业应用。作为重要的共性支撑技术之一，无线传感器网络的自身定位问 题研究极具研究价值。本文着重归纳和总结了己有的无线传感器网络自身定位 系统和算法研究，并在此基础上分析了一种新的自身定位算法，期望能为未来 研究提供一个良好基础。 本论文的工作是围绕着无线传感器网络自身定位算法这一崭新的课题进行 的，论文的研究内容安排如下： 第1 章主要介绍了研究背景和意义。 第2 章概述了无线传感器网络的体系结构、协议、及其相关应用，并列举了 定位系统的关键技术和性能评价指标。 第3 章首先描述了无线传感器网络节点定位的概念和基本的节点坐标计算 方法，然后对d v h o p 算法的定位机制进行了分析，并在文章最后章节对其进行 了仿真分析与对比。 第4 章结合数学线性回归方法测出节点的单跳测距值，并在第一阶段 3 武汉理工大学硕士学位论文 h o p - t e r r a i n 算法中将这个单跳测距值广播，h o p t e r r a i n 算法同时还融入 了拓展半径的距离思想，然后对h o p t e r r a i n 算法及其核心思想进行了分析。 第5 章针对d v h 叩和改进后的h o p t e r r a i n 以及循环求精算法进行仿真实 验证，并分析比较了仿真实验结果。 第6 章进行总结全文和对下一步的研究工作的展望。 4 武汉理工大学硕士学位论文 第2 章无线传感器网络及其节点定位概述 2 1 无线传感器网络概述 近十几年来，随着微电机系统、无线通信和数字电子等技术的快速发展， 使得具有数据采集、计算处理和无线通信能力的低成本、低功耗、微型传感器 的研制和生产得以成为现实【3 l 。w s n 就是由大量微型传感器节点以a dh o e 方 式组成的无线网络，其目的是通过所部署的大量无线传感器节点相互协作地感 知、采集和处理网络覆盖范围内的各种监测对象的信息，这些信息再通过无线 方式传送到数据处理中心或基地站。传感器、感知对象和观察者构成了w s n 的 三个要素l ”。 w s n 被认为是2 1 世纪最重要的技术之一，它将对人类的生产和生活产生深 远的影响。如果说因特网构成了逻辑上的信息世界，改变了人与人之间的沟通 方式，那么，w s n 就是将逻辑上的信息世界与客观上的物理世界融合在一起， 改变了人类与自然界的交互方式p l 。作为一种全新的信息获取和处理技术，它 在军事国防、环境监测，抢险救灾、危险区域的远程控制等许多领域都具有广 泛的应用前景。w s n 与传统的无线网络有着不同的设计目标和技术要求，即使 是a dh o e 网络的协议和算法也未必适合其特点和应用条件。 2 1 1 无线传感器的结构 在不同的应用中，传感器节点的结构不尽相同，但一般都由传感单元、数 据处理单元、数据收发单元、电源单元等功能模块组成。传感单元由各类传感 器及数模转换设备组成，传感器的类型是由被监测物理信号的形式决定的，数 据处理通常选用低功耗嵌入式微控制器，数据传输单元主要由相应的通信协议 ( 主要是m a c 协议) 及低功耗、短距离的无线通信模块组成。因为需要进行较复杂 的任务调度与管理，系统还需要一个微型化的实时操作系统，加州大学伯克利 分校为此专门开发t t i n y o s ，另外还有u c o s i i 等。电源是影响节点寿命的关 键因素。图2 - - 1 描述了无线传感器节点的一般组成。除此之外，根据具体应用 的需要，可能还会有定位系统、电源再生单元和移动单元等。 武汉理工大学硕士学位论文 图2 一l 传感器网络节点的组成 2 1 2 无线传感器网络的体系结构 图2 2 传感器网络体系结构 一个典型的传感器网络由传感器节点( s e i l s o rn o d e ) 、汇聚节点( s i n kn o d e ) 、 i n t e m e t 或通信卫星、任务管理节点等部分构成。传感器节点任意散落在被监测 区域内，这一过程是通过飞行器撤播、人工埋置和火箭弹射等方式完成的。节 点再以自组织形式构成网络。每个节点都可以收集数据，并通过“多跳”路由方式 把数据传送到汇聚节点。它也可以用同样的方式将信息发送给各节点。汇聚节 点直接与i n t e m e t 或通信卫星相连，通过i n t e m e t 或通信卫星实现任务管理节点( 即 观察者) 与传感器之间的通信。用户通过管理节点对传感器网络进行配置和管理， 发布监测任务以及收集监测数据。图2 2 描述了w s n 的基本网络的体系结构， 但是针对特定的应用环境，无线传感器网络的体系结构有所不同。 6 武汉理工大学硕士学位论文 2 1 3 无线传感器网络的协议层次 根据网络的体系结构和具体应用范围的不同，w s n 的协议层次也不完全相 同，并且到目前为止，还没有形成w s n 的标准协议栈。最典型的情况是自下而 上包含物理层、数据链路层、网络层、传输层、应用层；另外，协议栈还包括 能量管理平台、移动管理平台和任务管理平台。如图2 3 ( a ) 所示： ( b ) 图2 3 无线传感网络通信协议栈 物理层：负责提供简单而健壮的信号调制和无线收发技术。 数据链路层：数据链路层负责介质访问控制( m a c ) 和差错控制。 网络层：网络层负责路由协议发现和维护，是w s n 的重要协议层，也是目前 研究的热点之一。 传输层：传输层负责将传感器网络的数据提供给外部网络，比如因特网。 应用层；包括一系列基于监测任务的应用软件。 能量管理平台：管理传感器节点如何使用能源，在各个协议层都需要考虑 节省能量。 移动管理平台：监测并注册传感器节点的移动，维护到汇聚节点的路由， 使传感器节点能动态跟踪其邻居的位置。 任务管理平台：在一个给定的区域内平衡和调度监测任务。 图2 3 嘞是在上一种协议栈的基础上经过改进得到的另一种协议栈模型。 2 1 4 无线传感器网络的相关应用 w s n 作为一种全新的信息获取和处理技术，特别适用于完成大规模、复杂 7 武汉理工大学硕士学位论文 的监测和追踪任务。其广泛的应用前景体现在许多领域。 军事应用：w s n 具有可快速部署、可自组织、隐蔽性强和高容错性等特点， 因此非常适合在军事上应用。无线传感器节点可以被大量投放到敌方控制区或 者冲突区，实现对敌军兵力和武器装备的监控、战场的实时监视、敌方军事目 标的定位、战场评估、核攻击和生物化学攻击的监测和搜索等功能。 生态环境研究 6 , 7 1 ：w s n 在生态环境方面可用于观测农作物灌溉和生长情 况、土壤和空气成分、野生动物的生存状况和大面积的地表监测，准确及时预 报森林火灾、山洪爆发和泥石流等灾害。 医疗护理：可以在病人身上安装用于检测身体机能的微型传感器节点，它 们可对病人的心率和血压等生理指标进行远程实时检测 g l ，并将信息汇总传送 给医生，进行及时处理，为远程医疗创造条件；利用w s n 长期收集被观察者的 人体生理数据，对了解人体健康状况和研制新药品都很有帮助。 空间探索：可以借助航天器向外星球表面大量撒播无线传感器节点，建立 大规模的w s n 来感知收集外星球表面的环境数据，然后通过卫星信道传输给外 太空轨道上的航天器或探测卫星。由于w s n 具有很好的抗毁性和自组织性，如 果能很好的解决能量供给问题，则可以作为一种长期、可靠的外星球环境探测 方式。美国宇航局喷气推进实验室研制了s e n s o rw e b s 9 1 ，用于将来对火星的科 学探测。除了上述列出的一些应用领域，w s n 还将广泛用于工业控制、智能交 通、智能农业和智能建筑等。总之，w s n 的应用将深入人类社会生产和生活的 各个领域，成为影响人类未来生存状态的一项重大科技创新。 2 1 5 无线传盛罨网络的研究现状 传感器网络的挑战性也为研究人员提供了广阔的研究空间。美国军方最先 开始这一领域的研究，并且投入巨大。目前，军事部门、民用领域和学术界都 在对其开展深入而广泛的研究。 在军事领域，美国陆军提出的“智能传感器网络通信计划”、“无人值守地面传 感器群”项目，美国海军确立的“传感器组网系统”项目、“协同作战能力研究等。 在民用领域，美国交通部1 9 9 5 年提出“国家智能交通系统项且规划”，i n t e l 公司2 0 0 2 年发布“基于微型传感器网络的新型计算发展规划”等。 在学术界，美国的多个著名高校和研究机构都在从事w s n 的理论和应用方 面的研究，并且处于领先地位。比如，加州大学伯克利分校研制的传感器系统“智 武汉理工大学硕士学位论文 能尘埃”( s m a r td u s t ) ，其体积只有一立方毫米，可以悬浮在空中；并研制了传感 器操作系统t m y o s 和感知数据库系统t i n y d b 1 0 1 。加州大学洛杉矶分校研制了 w i n s 无线集成网络传感器( w i t e l e s si n t e g r a t e dn e t w o r ks e n s o r s ) 。麻省理工学院致 力于基于知识的信号处理技术。哈佛大学研究传感器网络中通讯的理论基础。 在国内，中科院上海微系统研究所、沈阳自动化所、软件研究所、计算所、 电子所、自动化所和合肥智能技术研究所等科研机构，哈尔滨工业大学、清华 大学、北京邮电大学、西北工业大学、天津大学和国防科技大学等院校在国内 较早开展了这一领域的研究，并已经取得一些初步成果。 2 2 无线传感器网络定位的关键技术及自身定位的意义 2 2 1 无线传感器网络定位的关键技术 为实现传感器网络的自身定位，需要解决以下三个方面的问题。 2 2 1 1 时间同步 利用电磁波信号和声音信号的时间差测量，节点发送的电磁波信号兄和声波 信号s 必须一一匹配，接受方根据接受时间差计算同发送方之间的距离。否则 由于信号的广播特性，若接收方相继收到电磁波信号和声波信号来自不同发送 方，距离计算将会产生很大的误差。所以在启始阶段需要对网络进行时间同步， 并在同步基础上，采用t d m a i ”1 方法为每个n o d e 节点分配发包时隙，避免数 据包冲突。此外，还有一种更加快速节能的时间同步方案： ( 1 ) 引入第三方时间同步节点，由它发送时间同步命令。命令包中包含同 步时刻瓦，时隙长度t i m e s l o t 和每个周期包含的时隙总数n 三个参数。 ( 2 ) 每个n o d e 节点在接受到时间同步命令之后，分布式计算自己的发包时 隙，第k 个节点发包时隙计算公式为： 巩= t o + t i m e s l o t m o d ( i ，| ) + t i m e s l o t n k ( 2 - - 1 ) 其中k = 【o 1 2 ，n 一1 】为节点编号，i = 【o ，l ，2 ， 】为数据包计数。 相比c s m a ! “1 在冲突之后的随机退让，这种基于t d m a 的时隙分配方法能 够有效的避免通信冲突并且更加快速节能。 9 武汉理工大学硕士学位论文 2 2 1 2 距禹测量 在时隙分配之后，n o d e 节点在每个周期的自身时隙内发送电磁波信号和声 波信号对，b e a c o n 节点收到这对信号，并且根据时间差计算同n o d e 节点之间的 距离，觅公式( 2 2 ) 。 z ，肚= ( 毛。，一强。一7 知) ( 2 - - 2 ) 其中i 是发包n o d e 节点，j 是收包b e a c o n 节点，k 是周期计数，。是b e a c o n j 在第k 个周期内接到n o d ei 的声音的信号时刻，强，。是接收到的电磁波信号 的时刻，毛胁是声波相比电磁波的发送延迟。由于n o d e 节点周期性发包，b e a c o n j 测得的同n o d e i 之间的距离是一个序列：4 。，哦朋，z ”所以z ，是根据节 点所获得的距离序列对i ，j 之间距离的一个估计；吐，= 吐，z 。，z 。：，z ， ) 。 也可以用滚动平均方法，在每个周期不断更新对z 的估计值： d u ( 七+ 1 ) = ( 七d i d ( 七) + d ，乒“) ( 竞d u ( 露) + d 。， + i ) ( k + 1 ) ( 2 - - 3 ) 2 2 1 3 位置计算 经过几个周期的测距之后，西，的估计值构成距离矩阵d ，位置计算根据距 离矩阵d 和坐标b e a c o n 坐标求n o d e 节点坐标，见公式( 2 4 ) 。 ( t ，咒) = ( 置，只) l ( 瓦，k ，d ) ) ，d = 4 1 而， mom 反】 a n ( 2 4 ) 存在最小二乘、加权平均等多种计算方法。其中基于几何关系的三边测量 方法以其计算量小，计算相对准确的特点在低能耗，计算较弱的传感器节点上 具有显著优势。根据四边形中的两对三边测量关系见公式( 2 5 ) ，( 2 6 ) ，有 一套鲁棒性好的位置计算方法。为叙述清楚，介绍了四个b e a c o n 布置成正方形 时的计算方法，如图2 4 所示，在b e a c o n 的其它布置方式下，三边测量方法 可以通过修改公式( 2 5 ) ，( 2 6 ) 中的b e a c o n 之间的距离来实现，即d i s 参 数依然有效。 1 0 武汉理工大学硕士学位论文 n o d e 节点 b e a c o n 节点 图2 - - 4 锚节点与目标节点位置关系 公式( 2 - - 5 ) ，( 2 - - 6 ) 是在图2 - - 4 的二维平面上，获得距离d l ，d 2 ，呜，d 4 之 后计算k 力坐标的两对三边测量关系。由于无线信道的不稳定和环境的干扰， d 矩阵中不是所有的距离量都能测到，当b e a c o n 间距离较远时，d 矩阵中将出 现很多0 元素。针对这个问题，如下鲁棒性很好的位置计算方法可以解决： ( 1 ) 当四个b e a c o n 都能测到同n o d e 之间的距离时： z ：! 塑：蟹二丝篓二堡( 2 5 ) 4 d i s x ：! 望! 。1 2 ：竺2 2 = 竺2 21 竺1 2 二竺2( 2 6 ) x = = 一 l z o ， 4 d s ( 2 ) 当只有三个b e a c o n 能测到同n o d e 之间的距离时； 善：2 d i s 2 + d ：- d ；，或x ：兰塑：篓二堡( 2 一一7 ) 善= 一，戥= ：二土 l 一7 j 2 矗舔2 瘟f ) ，= 警，或_ ) ，= t 2 d i ：+ d ：- 刃 ( 2 _ 8 ) z 口f sz 口l s ( 3 ) 当只有两个b e a c o n 能测到同n o d e 之间的距离时，则假定此n o d e 节 点距离另两个b e a c o n 距离较远，计算公式为： x = 三旦学，j ，= 一( 再+ j i 二i 而) 2 ( 2 9 ) 了= 型篆堑，y = d i s + ( 厨了+ 何而2 ( 2 - - 1 0 ) 武汉理工大学硕士学位论文 ) ，= 型篆垄，一( 厨+ 4 d ；- ( d i s - y ) 2 ) 2 ( 2 - 1 1 ) ) ，= 2 d i s 2 蕊+ d 2 1 一- d ：，x = 如+ ( 耵+ 厨而) 2 ( 2 _ 1 2 ) ( 4 ) 当只有一个或没有b e a c o n 能够测到同n o d e 之间的距离时，放弃对该 n o d e 的定位。 2 2 2 研究无线传赢器网络自身定位技术的意义 为了适应广泛的应用程序，传统网络的设计遵循着“端到端”的边缘论思想， 强调将一切与功能相关的处理都放在网络的端系统上，中间节点仅仅负责数据 分组的转发，对于传感器网络，这未必是一种合理的选择。些自组织的a d - h o e 网络设计的协议和算法未必适合传感器网络的特点和应用的要求。节点标识( 如 地址等) 的作用在传感器网络中就显得不是十分重要，因为应用程序不怎么关 心单节点上的信怠；中间节点上与具体应用相关的数据处理、融合和缓存也显 得很有必要。在密集性的传感器网络中，相邻节点间的距离非常短，低功耗的 多跳通信模式节省功耗，同时增加了通信的隐蔽性，也避免了长距离的无线通 信易受外界噪声干扰的影响。这些独特的要求和制约因素为传感器网络的研究 提出了新的技术问题。 作为一种全新的技术，无线传感器网络科技工作者提出了许多具有挑战性 的研究课题，而定位就是其中之一。定位是大多数应用，特别是军事应用的基 础。无线传感器网络中的定位机制与算法包括两部分：节点自身定位和外部目 标定位，前者是后者的基础。对于大多数应用，不知道传感器位置而感知的数 据是没有意义的。传感器节点必须明确自身位置才能详细说明在什么位置或区 域发生了特定事件，实现对外部目标的定位和追踪。另一方面，了解传感器节 点位置信息还可以提高路由效率，为网络提供命名空间，向部署者报告网络的 覆盖质量，实现网络的负载均衡以及网络拓扑的自配置。 w s n 节点的微型化和有限的电池供电能力使其在节点硬件的选择上受到很 大限制，低功耗是其最主要的设计目标。而人工部署和为所有网络节点安装g p s 接收器都会受到成本、功耗、扩展性等问题的限制，甚至在某些场合可能根本 无法实现，因此必须针对其密集性，节点的计算、存储和通信等能力都有限的 武汉理工大学硕士学位论文 特点设计有效的低功耗定位算法。从1 9 9 2 年a t & tl a b o r a t o r i e sc a m b r i d g e 开发出 室内定位系统a c t i v eb a d g e 至今，研究者们一直致力于这一领域的研究。事实上， 已有许多系统和算法能够解决w s n 自身定位问题。但是，每种系统和算法都用 来解决不同的问题或支持不同的应用，它们在用于定位的物理现象、网络组成、 能量需求、基础设施和时空的复杂性等许多方面有所不同。 2 3 无线传廖器网络自身定位系统和算法的性能指标评价 w s n 自身定位系统和算法的性能直接影响其可用性。目前定位算法性能评 价的模型化和量化还是个热点问题，不过已经有研究入员提出了某些可行的评 价指标。 定位精度：这是定位技术的首要指标，只有满足一定定位精度的定位系统 才有实用价值，一般用误差值与节点无线射程的比例表示。例如，定位精度为 2 0 表示定位误差相当于节点无线射程的2 0 。也有部分定位系统将二维网络部 署区域划分为网格，其定位结果的精度也就是网格的大小，如微软的r a d a r t l 2 】， 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 等。 规模：不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或 仅仅是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内， 一种技术可以定位多少目标也是一个重要的评价指标。例如，r a d a r 系统仅可 在建筑物的一层内实现目标定位，剑桥的a c t i v eo f f i c e 定位系统【1 4 1 每2 0 0 m s 定 位一个节点。 锚节点密度：锚节点定位通常依赖人工部署或g p s 实现。人工部署锚节点的 方式不仅受网络部署环境的限制，还严重制约了网络和应用的可扩展性。而使 用g p s 定位，锚节点的费用会比普通节点高两个数量级i t s ，这意味着即使仅有 1 0 的节点是锚节点，整个网络的价格也将增加l o 倍。因此，锚节点密度也是评 价定位系统和算法性能的重要指标之一。 节点密度：在w s n 中，节点密度增大不仅意味着网络部署费用的增加，而 且会因为节点问的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的 平均连通度来表示。许多定位算法的精度受节点密度的影响，如d v - h 0 p 【1 6 j 7 1 算 法仅可在节点密集部署的情况下合理地估算节点位置。 容错性和自适应性：通常，定位系统和算法都需要比较理想的无线通信环 武汉理工大学硕士学位论文 境和可靠的网络节点设备。但在真实应用场合中常会有诸如以下的问题：外界环 境中存在严重的多径传播、衰减、非视距( n o n 1 i n e - o f - s i g h t ，简称n l o s ) 、通信 盲点等问题；网络节点由于周围环境或自身原因( 如电池耗尽、物理损伤) 而出现 失效的问题；外界影响和节点硬件精度限制造成节点间点到点的距离或角度测 量误差增大的问题。由于环境、能耗和其它原因，物理地维护或替换传感器节 点或使用其它高精度的测量手段常常是十分困难或不可行的。因此，定位系统 和算法的软、硬件必须具有很强的容错性和自适应性，能够通过自动调整或重 构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。 功耗：功耗是对w s n 的设计和实现影响最大的因素之一。由于传感器节点 电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的 计算量、通信开销、存储开销、时间复杂性是一组关键性指标。 代价：定位系统或算法的代价可从几个不同方面来评价。时间代价包括一 个系统的安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或 算法所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一 种定位系统或算法的基础设施、节点设备的总费用。 上述7 个性能指标不仅是评价w s n 自身定位系统和算法的标准，也是其设 计和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需要完成。 同时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡【l 。1 ，以 选择和设计合适的定位技术。 1 4 武汉理工大学硕士学位论文 第3 章无线传感器网络d v - h o p 定位算法 3 1 节点定位概念 定位，简单的说就是确定目标的位置信息。在w s n 中，位置信息对传感器 网络的监测活动至关重要，事件发生的位置或获取信息的节点位置是传感器节 点监测消息中所需要的重要信息。 w s n 中定位算法的研究有着重要的意义，这主要体现在两个方面： ( 1 ) w s n 中的很多特定应用都依赖于传感器节点或者目标物体的地理位