（信号与信息处理专业论文）无线传感器网络节点自定位技术研究.pdf

摘要 摘要 节点的自定位技术是传感器网络的关键技术之一。大量随机布放的传感器节 点无法事先知道自身位置，因此必须能够在布放后进行定位。无论是否已知节点 间的距离信息，基于多维标度的传感器网络定位算法都能实现定位，因此本文将 重点研究基于多维标度的无线传感器网络定位算法。 首先，本文在查阅大量相关文献的基础上，介绍了无线传感器网络定位技术 的研究背景及国内外现状，综述了无线传感器网络定位系统和算法的性能评价标 准、分类方法，着重描述了近年来在该领域具有代表性的算法的原理和特点。 其次，本文介绍基于经典多维标度的传感器网络定位技术。在深入分析基于 质心参考点情况下经典多维标度算法的基础上，给出了基于节点参考点的经典多 维标度算法的公式推导，并比较了两者的定位效果。仿真表明，基于质心参考点 的经典多维标度算法具有更好的定位性能。 然后，本文提出了迭代多维标度算法的改进形式。它利用节点的通信半径和 节点间的跳段数信息，应用经典多维标度方法计算得到节点初始位置矩阵，并且 改进了目标函数的形式。仿真实验表明，本文改进的迭代多维标度算法比原方法 有更好的定位性能。 最后，本文将松弛解法引入到节点的位置估计中，提出了一种快速算法。该 方法的每一步不期望使整个目标函数最小化，而只要求使其中的某一项取最小。 仿真表明，本文的快速算法有效地节约了计算量，提高了计算效率。 关键词：无线传感器网络；定位技术；多维标度；改进迭代多维标度；快速算法 a b s t r a c t a b s t r a c t a u t o m a t i cl o c a l i z a t i o no fe v e r ys e n s o ri sak e ye n a b l i n gt e c h n o l o g yo fw i r e l e s s s e e t l s o rn e t w o r k s w i t han e t w o r ko f t h o u s a n d so f n o d e s ，i ti su n l i k e l yt h a tt h ep o s i t i o no f e a c hn o d ec 距b ep r e d c t e r m i n c d t h u s ，e s t i m a t i n gn o d e s p o s i t i o ni sn e e d e da f t e r d e p l o y i n g l o c a l i z a t i o na p p r o a c h e sb a s e do nm u l t i d i m e n s i o n a ls c a l e i n gc o u l dw o r k e f f i c i e n t l yo nr a n g e - b a s e do rr a n g e - f r e e ，s ot h i sp a p e rw i l lb ef o c u s e do nw i r e l e s ss e n s o r n e t w o r k sl o c a l i z a t i o na p p r o a c h e sb a s e do nm u l t i d i m e n s i o n a ls c a l i n g f i r s to fa l l ，t h er e s e a r c hs t a t u so fw i r e l e s sl o c a t i o nt e c h n i q u e sa n dp o s i t i o n i n g s y s t e m sf o rw i r e l e s ss e n s o rn e t w o r k sa r es u m m a r i z e db a s e do nt h es t u d yo fp l e n t yo f r e l a t e dl i t e r a t u r e s t h ec r i t e r i o no fp e r f o r m a n c ee v a l u a t i o na n dt h et a x o n o m yf o r w i r e l e s ss e n s o rn e t w o r k sl o c a l i z a t i o ns y s t e m sa n da l g o r i t h s m sa r ed e s c r i b e d t h e p r i n c i p l e sa n dc h a r a c t e r i s t i c so fr e c e n tr e p r e s e n t a t i v el o c a l i z a t i o na p p r o a c h e sa r ea l s o d i s c u s s e da n dp r e s e n t e d t h e n , t h i sp a p e ri n 仃o d u c e ds a i s o rn e t w o r k sl o c a l i z a t i o nt e c h n o l o g yb a s e do n c l a s s i c a lm u l t i d i m e n s i o n a l s c a l i n g o nt h eb a s i s o f a n a l y s e s o nc l a s s i c a l m u l t i d i m e n s i o n a ls c a l i n ga l g o r i t h mb a s e do nc e n 自r o i dr e f e r e n c ep o i n t , t h i sp a p e r d e r i v e st h em u l t i d i m e n s i o n a ls c a l i n ga l g o r i t h mw h i c h u s i n gn e t w o r k n o d e sa sr e f e r e n c e p o i n t s i m u l a t i o nr e s u l ts h o w st h a tc l a s s i c a lm u l t i d i m e n s i o n a ls c a l i n ga l g o r i t h mb a s e d o nc o n t r o i dr e f e r e n c ep o 衄i sm o r ep r e c i s et h a no t h e ro n e f u r t h e r m o r e , t h i sp a p e rp r o p o s e dm o d i f i e di t e r a t i o nm u l t i d i m e n s i o n a ls c a l i n g a l g o r i t h m i tu t i l i z e dn o d e sc o m m u n i c a t i o nr a d i u sa n dh o pc o u n ti n f o r m a t i o nb e t w e e n n o d e s n o d e si n i t i a lp o s i t i o nm a t r i xi sc o m p u t e db yc l a s s i c a lm u l t i d i m e n s i o n a ls c a l i n g a n dc o s tf u n c t i o n sf o r m i sa l s oi m p r o v e d s i m u l a t i o nr e s u l tp r o v e st h a tt h em o d i f i e d a p p r o a c hi se f f e c t i v ea n dh a sb e t t e rp e r f o r m a n c et h a nc o n v e n t i o n a lo n e a tl a s t , t h i sp a p e ri n t r o d u c e dr e l a x a t i o ns o l u t i o ni n t on o d ep o s i t i o ne s t i m a t i o na n d p r o p o s e saf a s ta l g o r i t h m t h i sa l g o f i t t n nd i dn o te x p e c tm i n i m i z i n gw h o l ec o s tf u n c t i o n o ne a c hs t e pa n dm i n i m i z e do n et e r mo ne a c hs t e p s i m u l a t i o nr e s u l ts h o w st h a tt h ef a s t a l g o r i t h me f f i c i e n t l yr e d u c e dc o m p u t a t i o nc o m p l e x i t ya n di m p r o v e dc o m p u t i n g e f f i c i e n c y n a b s t r a c r k e y w o r d s ：w i r e l e s s s e n s o rn e t w o r k s ；l o c a l i z a t i o nt e c h n o l o g y ；m u l t i d i m e n s i o n a l s c a l i n g ；m o d i f i e di t e r a f i v em u l t i d i m e n s i o n a ls c a l i n g ；f a s ta l g o r i t h m l i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：；三邈日期：2 。7 年，月厶日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：乞哆罗年月r 舻e l 第一章绪论 1 1 研究背景及意义 第一章绪论 更小、更廉价的低功率计算设备代表的“后p c 时代”冲破了传统台式计算机 和高性能服务器的设计模式：普遍的网络化带来的计算处理能力是难以估量的； 微机电系统( m i c r o - e l e c t r o - m e c h a n i s ms y s t e m ，简称m e m s ) 的迅速发展奠定了设计 和实现片上系统( s y s t e mo nc h i p ，简称s o c ) 的基础，以上3 方面的高度集成又孕 育出很多新的信息获取和处理模式，无线传感器网络就是其中一例。 无线传感器网络( w i r e l e s ss e n s o r n e t w o r k s ，简称w s n ) 就是由布置在监测区域 内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织 网络系统，其目的是协作地感知、采集和处理网络覆盖区域中对象的信息。微电 子、网络和无线通信等技术的进步，推动了低功率、多功能传感器的快速发展， 使其在微小体积内能够集成信息采集、数据处理和无线通信等多种功能。传感器 网络具有广阔的应用前景，能广泛用于军事、环境监测和预报、城市交通、建筑 物状态监控以及医疗护理等领域【1 】【2 】【3 】。 通过布置大量传感器节点于监测区域，传感器网络将改变我们与客观世界的 交互方式。但是位置信息是传感器节点采集信息中不可缺少的部分，没有位置信 息的监测信息通常是无意义。因此，确定获取信息的节点位置是传感器网络最基 本的功能之一，对传感器网络应用的有效性起着关键的作用f 4 】i s 。如在环境监测应 用中需要知道采集的环境信息所对应的具体区域；对于突发事件，如需要知道森 林火灾的现场位置，战场上敌我车辆运动的区域，化工管道泄漏的具体地点等。 对于这些问题，传感器节点必须首先知道自身的地理位置，这是进一步采取措施 的基础【6 】。 另一方面，传感器节点位置信息的获得又可以优化网络在其它方面的应用， 比如提高网络路由效率、向布置者报告网络的覆盖质量、实现网络的负载均衡和 网络拓扑的自配置等。 在传感器网络中，传感器节点存在着能量有限、可靠性差、节点规模大且随 机布放、无线模块的通信距离有限等特点，传统的定位技术无法很好得适用于传 感器网络。全球定位系统( g l o b a lp o s i t i o ns y s t e m ，简称g p s ) 成本和能耗高，限制 电子科技大学硕士学位论文 了它在无线传感器网络中的应用。局部定位系统( l o c a lp o s i t i o ns y s t e m ，简称l p s ) 需建立高性能的基站设施，这对大多数低配置的传感器网络来说无疑是昂贵的负 担。因此，必须针对无线传感器网络节点的低成本、低能耗和通信能力有限的特 点设计有效的定位算法。 1 2 国内外研究现状 传感器网络的研究起步于2 0 世纪9 0 年代。从2 1 世纪开始，传感器网络技术 引起了学术界、军界和工业界的极大关注。美国所有著名院校几乎都有研究小组 在从事传感器网络相关技术的研究，欧洲和日本等国家的研究机构也加入到传感 器网络的研究之中。 在传感器网络中，传感器节点自身的正确位置是提供监测事件位置信息的前 提。定位技术作为传感器网络应用的关键技术之一，同样引起了各国研究者的关 注。随着传感器网络研究的深入开展，已经有一些应用于无线传感器网络的定位 系统被提出，其中比较有代表性的定位系统有a c t i v eb a d g e 系统【7 1 ，a c t i v eb a t 系 纠8 】，r a d a r 系纠9 1 ，c r i c k e t 系冽1 0 】【n 】，m e d u s a 系统1 2 1 等。 a t & t c a m b r i d g e 的a c t i v e b a d g e 系统是最早的室内定位系统，它是由在建筑 物内布置一个通过以太网连接的红外线传感器节点组成的网络，系统的定位精度 以房间为单位。但是由于红外线在阳光下无法正常工作，所以该系统的应用区域 受到限制。同时，红外信号传播距离短，使系统在建筑物内不得不安装许多传感 器，导致系统扩展能力很差，需要巨额的安装、配置和维护费用。 a c t i v eb a t 系统是在b a d g e 系统上的优化，它使用了超声波测距技术提供了比 b a d g e 更精确的定位功能。但是，a c t i v eb a t 系统同样存在着可扩展性差、布置代 价和总体成本高的缺点。 r a d a r 系统是微软公司基于i e e e8 0 2 1 1 无线网络标准设计的一种室内定位 系统。在r a d a r 系统中，主要考虑建筑物的墙壁对信号传播的影响，建立信号 衰落和传播距离间的关系。虽然在试验环境中r a d a r 系统表现出良好的特性， 但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得该技 术在实际应用中仍然存在很多困难。 c r i c k e t 系统是麻省理工学院的o x y g e n 项目的一部分，用来确定移动或静止节 点在建筑物内的具体房间位置。该系统利用无线射频信号和超声波信号到达时间 间隔计算出未知节点到该发信号节点的距离。然后通过比较到各个邻近发信号节 2 第一章绪论 点的距离，选择出离自己最近的发信号节点，从而确定自身的房问位置。c r i c k e t 系统受超声波传播方向性限制，不能实现任意两点间的测距和定位。 a h l o s 系统是一种迭代的定位算法，它利用信号到达时问差测量邻居节点间 的距离。该算法对信标节点( 己知自身位置的节点) 的密度要求高，不适用于规模大 的传感器网络，而且迭代过程中存在累积误差。 我国无线传感器网络研究及其应用几乎与发达国家同步启动。中科院上海微 系统研究所、沈阳自动化所、软件研究所、计算所、电子所和合肥智能技术研究 所等科研机构，哈尔滨工业大学、清华大学、浙江大学、西北工业大学和国防科 技大学等院校在国内较早开展了传感器网络的研究。 目前国内对传感器网络定位技术的研究还不多，史龙【1 3 】等在综合分析大量传 感器网络定位算法的技术文献和最新研究成果的基础上，从测距技术和定位计算 两方面阐述传感器网络节点定位的基本原理，着重论述和比较现有的经典定位算 法。钱字【1 4 】等主要讨论了无线传感器网络在军事上的应用，并展望了该技术的美 好前景。王建刚1 1 5 等在论文中通过对典型分布式节点定位算法进行分析后，提出 了一种新的分布式定位算法。李春蓉【1 6 】等重点对距离无关的定位算法进行研究和 改进，提出一种改进的节点自定位算法，给出了算法的基本原理和实现方法。而 陈红阳【l h 等则重点研究基于距离的定位算法，提出了基于接收信号强度均值的定 位方案，并且在现场环境下验证了该方案的计算效率和定位性能。 1 3 论文研究思路及章节结构 无线传感器网络节点定位技术是一项较复杂的技术，涉及的内容多、范围广 由于传感器节点资源受限的特点，与传统蜂窝网络相比，解决其目标节点定位问 题有更大的挑战。传感器网络节点的能量有限，存储能力和计算能力有限，这些 约束要求定位算法必须是低复杂性的。要进一步延长网络的生存周期，就必须要 减少定位过程中的通信开销，因为无线通信的能耗是节点的主要能耗。目前的算 法大都在能耗、成本和精度上作了折中考虑，通过综合考虑节点的规模、成本及 系统对定位精度的要求，来选择最合适的定位算法。 本论文的工作是围绕无线传感器网络节点自定位算法这一崭新课题进行的， 论文的研究内容安排如下： 第一章主要介绍了无线传感器网络和其定位技术的研究背景及意义、国内外 的研究现状； 3 电子科技大学硕士学位论文 第二章讨论了无线传感器网络的概念、结构及特点，节点定位技术的概念， 并总结了近年来典型的定位系统和算法，最后还给出了定位算法性能评价标准。 接着，在第三章本文重点讨论了基于经典多维标度的传感器网络定位技术， 并进行了不同参考点情况下经典多维标度定位算法的仿真实验。 在第四章中，重点讨论基于最小二乘标度定位算法的无线传感器网络定位机 制，介绍了现有基于最小二乘标度定位算法。在分析迭代多维标度定位算法基础 上提出了其改进形式。本章又针对现有的最小二乘标度算法对节点计算能力和存 储能力要求高的问题，引入松弛解法思想，提出一种快速定位算法。 第五章是结论和展望，对课题研究工作进行总结，并对今后进一步的研究工 作提出一些建议。 4 第二章无线传感器网络定位技术 第二章无线传感器网络定位技术 2 1 无线传感器网络概述 传感器网络是当前国际上倍受关注的、由多学科高度交叉的新兴前沿研究领 域。传感器网络综合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、 分布式信息处理技术等，能够通过各类集成化的微型传感器协作地实时监测、感 知和采集各种环境或监测对象的信息，通过嵌入式系统对信息进行处理，并通过 随机自组织无线通信网络以多跳中继方式将所感知信息传送到用户终端，从而真 正实现“无处不在的计算”的理念。传感器网络的研究采用系统发展模式，因而 必须将先进的微电子技术、微加工技术、系统s o c 芯片设计技术、纳米材料与技 术、现代信息通讯技术、计算机网络技术等相融合，以实现其微型化、集成化、 多功能化及系统化、网络化，实现传感器网络特有的低功耗系统设计。传感器网 络具有十分广阔的应用前景，在军事国防、环境观测预报、医疗护理、智能家居、 建筑物状态监控等许多领域都有重要的科研价值和巨大的实用价值，已经引起了 世晃上很多国家的高度重视。 2 1 1 传感器网络结构 在不同的应用中，传感器网络节点的组成不尽相同，但一般都包括传感器节 用户 图2 1 传感器网络体系结构 5 电子科技大学硕士学位论文 点( s e n s o rn o d e ) 、汇聚节点( s i n kn o d e ) 和管理节点。大量传感器节点随机布置在 监测区域内部或附近，能够通过自组织方式构成网络。传感器节点监测的数据沿 着其它传感器节点逐跳传输，在传输过程中监测数据可能被多个节点处理，经过 多跳后路由到汇聚节点，最后通过互联网或卫星到达管理节点。用户通过管理节 点对传感器网络进行配置和管理，发布监测任务以及收集监测数据。传感器网络 的结构如图2 1 所示。 2 1 2 传感器节点结构 传感器节点由传感器模块、处理器模块、无线通信模块和能量供应模块四部 分组成，如图2 2 所示。传感器模块负责监测区域内信息的采集和数据转换，被监 测物理信号的形式决定了传感器的类型：处理器模块负责控制整个传感器节点的 操作，存储和处理本身采集的数据以及其它节点发来的数据，处理器通常选用嵌 入式c p u ；无线通信模块负责与其它传感器节点进行无线通信，交换控制消息和 收发采集数据，主要由低功耗、短距离的无线通信设备组成；能量供应模块为传 感器节点提供运行所需的能量，通常采用微型电池。 传感器模块篙癸 无线通信模块 卜h 一一圈母一i ttt i能量供应模块 2 1 3 传感器网络的特点 图2 - 2 传感器节点结构 与传统的无线网络相比，无线传感器网络具有以下主要特点f 1 8 】【1 争】： 大规模网络：为了对一个区域进行监测，需要布置大量传感器节点，节点的数 量可能达到成百上千。传感器节点分布非常密集，通过大量采集信息能够提高 监测的精确度，冗余节点的存在使系统有很强的容错能力。 硬件资源有限：节点由于受价格、体积和能耗的限制，其处理能力、存储艟力 6 第二章无线传感器网络定位技术 和通信能力等都十分有限。与传统无线网络相比，传感器网络首要设计目标是 能源的高效利用。 无中心、自组织性：网络没有严格的控制中心，所有节点地位平等，组成对等 式网络。网络布设和展开无需依赖于任何预设的网络设备，节点通过拓扑控制 和网络协议自动形成无线网络。 动态拓扑：无线传感器网络是个动态网络，部分节点由于能量耗尽或环境因素 造成失效，也有一些节点由于需要被补充到网络中。这些都使网络的拓扑结构 发生变化，因此网络应该具有动态拓扑功能。 多跳路由：网络中节点通信距离有限，节点只能与它的邻居节点直接通信。如 果希望与其通信覆盖范围外的节点进行通信，则需要通过中间节点进行路由。 无线传感器网络中的多跳路由是由普通节点完成的，网络中每个节点既是信息 的发送者，也是信息的转发者。 以数据为中心：目前的互联网是一个以d 地址为中心的网络。传感器网络由 于节点随机布置，节点编号与节点位置没有必然联系。在使用传感器网络时， 用户只关心事件出现的位置和时间，并不关心哪个节点监测到事件的。 应用相关性：不同的应用背景对传感器网络的要求不同，其软、硬件平台和网 络协议必然会有很大差别。只有让系统更贴近应用，才能做出更高效的目标系 统。针对具体应用来研究传感器网络技术，是传感器网络设计不同于传统网络 的显著特征。 2 2 传感器节点定位技术简介 2 2 1 基本概念和术语 传感器节点定位是无线传感器网络布置完成后面临的主要问题之一。根据节 点是否已知自身位置，把传感器节点分为信标节点f o e a c o nn o d e 或a n c h o r ，又称 锚节点) 和未知节点( u n k n o w nn o d e ) 。信标节点可以通过携带g p s 定位设备等手段 获得自身精确位置。未知节点通过信标节点的位置信息来确定自身位置。无线传 感器网络节点定位闯题可表述为：依靠有限的信标节点，确定布置区域内未知节 点的位置，并在传感器节点间建立起一定的空间关系。 下面对无线传感器网络定位中一些常用术语进行说明： 邻居节点( n e i g h b o rn o d e s ) ：传感器节点通信半径内的其它节点，称为该节 7 电子科技大学硕士学位论文 点的邻居节点； 跳数( h o pc o u n t ) ：两个节点之间间隔的跳段总数，称为两个节点间的跳数； 跳段距离( h o pd i s t a n c e ) ：两个节点之间间隔的各跳段距离之和，称为两节 点间的跳段距离； 连通( c o n n e c t i b l e ) ：是指节点间可以进行无线通信，称该节点互为连通； 连通度( c o n n e c t i v i t y ) ：一个节点拥有的邻居节点数目，称为该节点的连通 度； 信标节点密度( b e a c o nd e n s i t y ) ：传感器网络中信标节点数目与所有节点数 目的比值，称为该网络的信标节点密度； 2 2 2 定位算法分类 无线传感器网络自定位算法的分类还没有一个统一的标准，现有的分类标准 也不一定适用于每一种定位算法。但下面这些分类方法能在一定程度上代表不同 定位算法的特点： ( 1 ) 基于距离的定位算法和距离无关的定位算法 根据定位过程中是否测量节点间的实际距离，把定位算法分为：基于距离 ( r a n g e - b a s e d ) l 筘j 定位算法和距离无关g e - 丘e e ) 的定位算法【2 0 】。在基于距离的定位 中，测量节点间距离或方位主要采用的方法有：到达角度西eo fa r r i v a l ， a o a ) 1 2 ，到达时间( t i m eo f a r r i v a l ，t o a ) ，到达时间差( t i m ed i f f e r e n c eo f a r r i v a l ， t d o a ) t 2 2 1 ，接收信号强度( 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 ，r s s l ) t 2 3 1 等。基于距 离的定位机制通常定位精度比较高，但对节点的硬件也提出了很高的要求。而距 离无关的定位机制无需测量节点间的距离或方位，降低了对节点的硬件要求，使 得节点成本更适合于大规模传感器网络，但定位误差相应的有所增加。 ( 2 ) 递增式定位算法和并发式的定位算法 根据节点定位的先后次序，把定位算法分为：递增式( i n c r e m e n t a l ) 定位算法和 并发式的( c o n r r t ) 定位算法1 2 4 1 。递增式的定位算法通常从信标节点开始，信标 节点附近的节点首先定位，依次向外延伸，各节点逐次进行定位，这类算法的主 要缺点是定位过程中传播、累积测量误差；并发式的定位算法中所有的节点同时 进行位置计算。 ( 3 ) 基于信标节点的定位算法和无信标节点的定位算法 根据定位过程中是否使用信标节点，把定位算法分为：基于信标节点的 第二章无线传感器网络定位技术 ( b e a c o n - b a s e d ) 定位算法和无信标节点的( b e a c o n - 丘e e ) 定位算法【列【2 嚣。前者在定位过 程中，以信标节点作为定位的参考点，各节点定位后产生绝对坐标系统；后者只 关心节点间的相对位置，在定位过程中无需信标节点，各节点先以自身作为参考 点，将邻近的节点纳入自己定义的坐标系中，相邻的坐标系统依次转换合并，最 后产生全局相对坐标系统。绝对坐标系统可为网络提供唯一的命名空间，受节点 移动性影响较小，有更广泛的应用领域。 ( 4 ) 集中式定位算法和分布式定位算法 根据定位过程中是否需要集中式定位计算，把定位算法分为：集中式 ( c e n t r a f i z e dc o m p u t a t i o n ) 定位算法和分布式( d i s t r i b u t e dc o m p u t a t i o n ) 定位算法1 2 川。集 中式定位是指把所需信息传送到某个中心节点，进行节点的定位计算；分布式定 位依赖节点闻的信息交换和协调，计算节点位置的工作在各个节点上完成。 2 2 3 节点间距离( 或角度) 的测量方法 在基于距离的定位中，测量节点间距离或方位时采用的方法有r s s i 、t o a 、 t d o a 和a o a 等。 r s s i ：该技术已知发射节点的信号强度，接收节点根据收到信号的强度，计 算出信号的传播损耗，利用传输损耗经验模型估计传播距离，再根据定位算法计 算出节点的位置。该技术主要使用射频信号。虽然在实验环境中r s s i 表现出良好 的特性，但是在现实环境中，反射、多径传播、非视距、天线增益等问题都会影 响传播损耗，使得该技术在实际应用中存在困难。 t o a ：该技术已知信号的传播速度，通过测量信号传播时间来计算节点间的 距离。基于t o a 的测距技术定位精度较高，但要求节点间保持准确的时间同步， 因此对传感器节点的硬件和功耗提出了高要求。 r d o a ：该技术被广泛应用于无线测距方案。无线传感器网络在利用t d o a 技术测量节点间距离时与蜂窝无线网络的移动台定位不同。如图2 3 所示，发射节 点同时发射两种不同传播速度的无线信号( 通常为无线射频信号和超声波信号) ，接 收节点根据两种信号到达时间差以及已知两种信号的传播速度，计算两个节点之 间的距离。发射节点b 发射两个信号，它们之间延迟小，接收节点a 记录两个 信号到达时间t | 幽、k 蛐d ，已知两个信号的传播速度为c 。d i o 、c 。l d ，那么两点之 间的距离 d = ( c i 如一) ( 。d f 。m 一屯曲) ( 2 一1 ) 9 电子科技大学硕士学位论文 t d o a 技术的测距精度较r s s i 高，但对硬件的要求也较高。 图2 - 3t d o a 测距原理示意图 a o a ：该技术是一种估算邻居节点发送信号方向的技术。接收节点通过阵列 天线或多个接收器感知发射节点信号的到达方向，计算接收节点和发射节点之间 的相对方位或角度。同样，a o a 技术也受外界环境影响，如噪声、非视距问题等 都会对测量结果产生不同影响；同时，实现a o a 技术要求节点配备高精度的智能 天线，设备比较复杂，影响其在传感器网络中应用。 以上四种测距方法各有利弊，其中r s s i 和t d o a 两种方法最为常用。 2 2 4 节点位置计算方法 传感器节点定位过程中，未知节点在获得与邻近信标节点的距离，或邻近的 信标节点与未知节点之间的相对角度后，通常使用下列方法计算自己的位置。 2 2 4 1 三边测量法 三边测量法中，已知a 、b 、c 三个节点的坐标分别为( 毛，y a ) 、( ，) 、( 吒，y c ) ， 它1 l i e u 未知节点d 的距离分别为屯、以、也，假设节点d 的坐标为( 工，y ) 。那么， 存在下列方程： ( 工 o ) 2 + ( y ) 2 + ( j ， 艺) 2 + ( 2 2 ) 由式( 2 2 ) 可以得到节点d 的坐标为： ； = i ：乏：乏；2 儿：芰； 一l i - 妥2 2 ( y b：薹：瑟：薹：鬈：鬈 。一s ， l y j1 2 ( 毛一t )一儿) j 【一+ 露一一+ 一露j 1 0 、，j 小。撒、弘。 = = = p r p 儿儿 第二章无线传感器网络定位技术 2 2 4 2 三角测量法 三角测量法原理如图2 - 4 所示，已知a 、b 、c 三个节点的坐标分别为瓴，儿) 、 ( ，) 、也，咒) ，节点d 相对于节点a 、b 、c 的角度分别为：z a d b 、z a d c ， z b d c ，假设d 的坐标为如y ) 。 豳2 _ 4 三角测量法原理图 对于节点a 、c 和角z a d c ，如果弧段a c 在a a b c 内，那么能够唯一确定一 个圆，设圆心为o , ( x o l ，y 0 1 ) ，半径为，i ，那么口= a a 0 1 c = ( 2 r e 一2 a a d c ) ，并存在 下列公式： j ( 一) 2 + 眈，一咒) 2 = f1 一毛) 2 + 饥1 一儿) 2 = 彳 ( 2 - 4 ) i ( 一) 2 + ( 咒一咒) 2 = 2 r t 2 - 2 r 1 2 c o s t z i 由式( 2 q 能够确定圆心q 点的坐标和半径吒，同理对a 、b 、z a d b 和b 、c 、 么丑d c 分别确定相应的圆心d 2 ( 而2 ，：) 、吃，圆心0 3 ( ，) 、弓。 最后利用三边测量法，由点o , ( x o 。，y o ，) 、d 2 ( 而：，：) 、d ，( 砀，3 ) 以及距离、 吃、弓确定d 点坐标。 2 2 4 3 最大似然估计法 最大似然估计法已知n 个节点的坐标分别为“，乃) ，如，m ) ，如，乃) ， ( ，咒) 它们到节点d 的距离分别是弓，如，砖，假设节点d 的坐 电子科技大学硕士学位论文 i ( 五- x ) 2 + ( m - y ) 2 = 砰j i ( 一工) 2 + ( 以- y ) 2 = f # 一- 2 ( x a 一弦+ 卯一z - 2 ( y , - y 。) y = 砰一刃1 i 矗，一- 2 ( x 。一。- x n ) x - i - k 2 。一z - 2 ( y 。一。- y 。) y = 船一刃i a = 蔗矧，b = ：二蔓巍卜x 习 = l ； f ，= i ； l ，= rl 【2 ( 一- 一矗) 2 ( 以一- 一只) jl 矗一+ 后一露+ 砰一缸i v 。 2 3 现有的传感器网络定位算法 目前为止，传感器网络自定位技术的研究已经成为传感器网络研究领域的热 点之一，已经有一些应用于无线传感器网络的定位算法被提出，下面就其中具有 代表性的算法进行介绍。 2 3 1 质心算法 质心算法嘲1 2 7 1 是一种完全基于网络连通性，无需信标节点和未知节点之间的 协调的定位算法。该算法的核心思想是：未知节点以所有在其通信范围内的信标 节点的几何质心作为自己的估计位置。具体过程为：信标节点周期性地向邻近节 点发送信号，信号中包含信标节点的标识号和位置信息。当未知节点接收到来自 不同信标节点的信号数量超过某预设门限后，就确定自身位置为这些信标节点所 组成多边形的质心： ( 毛，) ：洋，弩7( 毛，) = 学业，刍丝勺( 2 ) 其中( 置，x ) ，( 置，e ) ，c 瓦，e ) 为位置节点能够接收到其信号的信标节点 坐标。 质心算法假设节点都拥有理想的球型无线信号传播模型，而实际上无线信号 1 2 第二章无线传感器网络定位技术 的传播模型并非理想球型；另外，该方法的精确度与信标节点的密度以及分布有 很大的关系，密度越大，分布越均匀，定位精度越高。文献2 8 1 对质心算法进行了 改进，提出了一种自适应算法，通过在信标节点密度低的区域增加信标节点，以 提高定位的精度。 2 3 2 凸规划算法 凸规划定位算法【2 9 】 3 0 ( s e r n i d e f i n i t ep r o g r a m m i n g ) 将节点间的连通性视为节点 位置的几何约束，这些约束给出了未知节点可能存在的凸区域，从而将定位问题 转化为凸约束优化问题。如图2 5 所示，根据未知节点( 空心点) 与信标节点( 实心点) 间的连通性和节点通信范围，计算出未知节点可能存在的区域( 图中阴影部分) ，并 得到相应矩形区域( 图中虚线部分) ，最后以虚线矩阵的质心位置作为未知节点的位 置。 凸规划方法是一种集中式定位算法，它的计算比较简单、容易实现。与质心 算法相比，凸规划算法已知节点的通信距离，其定位精度有所提高。为了高效工 作，凸规划算法需要信标节点被布置在网络的边缘，否则外围节点的位置估算会 向网络中心偏移。 图2 - 5 凸规划算法定位过程 文献【3 1 】中提出一种b o u n d i n gb o x 算法，与以通信距离r 为半径的圆作为通信 模型不同，该算法将网络覆盖区域分为n 个正方形单元，采用了边长为2 d 个单元 的正方形作为节点通信区域，未知节点的位置估算就在矩阵区域的交集中，如式 ( 2 8 ) ： m a x ( x , 一d ) ，m a x ( y , 一d ) 】 m i n ( 玉+ d ) ，m i n ( y , + d ) 】i = 1 ，2 ，n ( 2 8 ) 未知节点的位置就是交集区域的中心，如图2 - 6 所示。 电子科技大学硕士学位论文 图2 - 6b o u n d i n gb o x 算法示意 2 3 3 近似三角内点测量算法 在近似三角内点测量算法( a p p r o x i m a t ep o i n t - i n - t r i a n g u l a t i o nt e s t ，a _ p i n 【捌中， 未知节点首先收集其邻近信标节点的信息，然后从这些信标节点组成的集合中任 意选取三个信标节点。假设集合中有n 个元素，那么共有口种不同的选取方法， 确定q 个不同的三角形，逐一测试未知节点是否位于每个三角形内部，直到穷尽 所有种组合或达到定位所需精度；这些包含未知节点三角形的重叠区域确定了 更小的区域，然后将重叠区域的质心位置作为未知节点的位置。如图2 7 所示，阴 影部分区域是包含未知节点的所有三角形的重叠区域，把该区域组成的多边形的 质心位置作为未知节点的位置。 a p i t 算法的理论基础是最佳三角形内点测试法p i t ( p e r f e c t p o i n t i n - t r i a n g u l a t i o nt e s t ) ，它的原理如图2 - 8 所示：假设存在一个方向，节点m 沿着这个方向移动会同时远离或接近顶点a 、b 、c ，那么节点m 位于a a b c 外； 否则，节点m 位于a a b c 内。 为了在静态的环境中实现三角形内点测试，提出了近似的三角形内点测量法： 假设在节点m 的所有邻居节点中，相对节点m 同时远离或靠近三个信标节点，那 么节点m 在a a b c 外；否则，节点m 在a a b c 内。近似的三角内点测量利用网络 中相对较高的节点密度来模拟节点移动，利用无线信号的传播特性来判断是否远 离或靠近信标节点，通常在给定方向上，一个节点距离另一个节点越远，接收到 信号的强度越弱。邻居节点通过交换各自接收到信号的强度，判断距离某一信标 节点的远近，从而模仿p i t 中的节点移动。 1 4 第二章无线传感器网络定位技术 图2 7 a p i t 定位原理图2 - 8 p i t 原理 在无线信号传播模式不规则和传感器节点随机布置的情况下，a p i t 算法的定 位精度高，性能稳定，但因未知节点必须与信标节点直接通信的需要，该算法要 求较高的信标节点密度。相对于质心算法，a p i t 计算复杂，但定位精度高，对信 标节点的分布要求低。 2 3 4 a p s 算法 d r a g o s n i c u l e s c u 等人利用距离向量路由的思想提出了一系列定位算法一合称 a p s ( a dh o cp o s i t i o n i n gs y s t e m ) 2 1 】【3 2 1 3 3 11 3 4 ，又称为距离向量算法。该类方法利用 平均每跳距离，对节点硬件要求低，实现简单。其缺点是利用跳段距离代替实际 距离，存在一定的误差。 2 3 4 1 距离向量跳段算法 距离向量跳段( d i s t a n c ev e c t o r - h o p ，d v - h o p ) 定位过程分为以下三个阶段。 1 ) 计算未知节点与每个信标节点的最小跳数 2 ) 在获得其它信标节点位置和相隔跳数，根据公式( 2 9 ) 估算平均每跳的距离。 然后将其广播至网络中。未知节点仅记录接收到的第一个每跳平均距离， 并转发给邻居节点。这个策略确保了绝大多数节点从最近的信标节点接收 每跳平均距离值。节点根据记录的跳数，计算到每个信标节点的跳段距离。 ( 而一_ ) 2 + ( 乃一) o ) 2 吒枷= 旦弋可一 ( 2 9 ) l h | l * j 其中( ，咒) 、，y ，) 是信标节点i 、j 的坐标，一是信标节点f - - 与j ( i ，) 之 间的跳段数。 3 ) 利用三边测量法或最大似然估计法计算自身位置 电子科技大学硕士学位论文 1 0 0 m h - “ 图2 - 9d v - h o p 定位算法示意( 实线表示连通约束，虚线表示l l 到l 3 最短路径) 如图2 - 9 所示，已知信标节点l l 、l 2 和l 3 之间距离和跳数。l 2 计算得到的 每跳平均距离为0 0 + 7 5 ) ( 2 + 5 ) 。假设a 从l 2 获得每跳平均距离，则节点a 与三个 信标节点之间的距离分别为：l 1 3 1 6 4 2 ，l 2 2 1 6 4 2 ，l 3 3 1 6 ，4 2 。 文献 2 0 1 的仿真结果显示，d v - h o p 算法在网络平均连通度为1 0 ，信标节点比例 为1 0 的各向同性网络中平均定位误差大约为3 3 。其缺点是仅在各向同性的密 度网络中，才