（通信与信息系统专业论文）基于多维标度的无线传感器网络节点定位方法研究.pdf

西南科技大学硕士研究生学位论文第1 页 摘要 作为一种全新的信息获取和处理技术，无线传感器网络广泛应用在各种 各样的领域，而定位是这些应用的前提和基础。因此，针对无线传感器网络 节点定位技术的研究具有重要实际意义。 本文考虑的应用场景是高密度高连接度的网络，相邻节点间能进行一定 精度的测距。基于该应用场景，研究一种具有较高定位精度、较少通信量和 计算量的定位方法。在对现有节点定位方法进行研究和分析后，选择适应性 和鲁棒性强的多维标度( m d s ) 定位的方法，作为研究无线传感器网络定位算 法的一种新思路。在研究多维标度算法的过程中，确定了在己知部分测距信 息的情况下，采取先求初值再进行迭代计算的基本定位模式。然后对现有的 几种初值计算方法进行了详细分析，并对其中一种初值生成算法进行了改进， 提出了a f l 直角坐标初值生成算法。 针对高连接度的网络，结合集中式与分布式计算的优点，提出了h l m d s 分层定位的思想。通过筛选出具有固定连接度的框架节点并分步定位，使得 该方法的计算复杂度与网络连接度无关，更能适用于高连接度的网络。由于 采用了分层定位的策略，该方法能快速获得整个网络框架结构的粗定位结果， 并能实现部分节点或全部节点的定位。 最后，在m a t l a b 仿真平台上进行h l m d s 分层定位仿真，仿真实验 结果表明h l m d s 算法在均匀和非均匀网络中具有较好的定位灵活性和实用 性。方法在项目中得到了很好的应用。 关键词：无线传感器网络多维标度分层定位 a f l 西南科技大学硕士研究生学位论文第l l 页 a b tr a c t w i r e l e s ss e n s o rn e t w o r k s ( w s n ) ，an o v e lt e c l l i l o l o g ya b o u ta c q u i r i n ga n d p r o c e s s i n gi n f 0 m a t i o n ，h a v eb e e na p p l i e dt oaw i d ev a r i e t yo fa p p l i c a t i o n s l o c a l i z a t i o ni sc r u c i a lf o rt h o s e a p p l i c a t i o n s s o ，r e s e a r c ho nn o d e s l o c a l i z a t i o n i nw s nh a v ei m p o r t a n tp r a t c t i c a ls i g n i f i c a n c e t h el o c a l i z a t i o n a p p l i c a t i o ns e c n ec o n s i d e r e di np a p e ri sh i g hd e n s i t y c o n n e c t i o nn e t w o r k s ，a n dw ec a na c q u i r ea p p r o x 姐n a t ed i s t a n c e sb e t w e e n n e i g h b o u m o d e s u n d e rt h ec i r c u m s t a n c e ，w ew i l lr e s e a r c ha1 0 c a l i z a t i o nm e t h o d w i t hh i g h e rl o c a l i z a t i o np r e c i s i o n ，l o w e rt r a 伍ca n dc o m p u t e r a r e re x t e n s i v e i n v e s t i g a t i o n 2 l b o u t p r e s e n t1 0 c a l i z a t i o nm e t h o d s ， t h er o b u s t a d a p t a b i l i t y a l g o r i t h m s - m u l t i d i m e n s i o n a ls c a l i n g ( m d s ) i sw e l l - s u i t e dt on o d el o c a l i z a t i o ni n w s n s ow ec h o o s em d s - b a s e da l g o r i t h ma so u rp r i m a 巧s o l u t i o nt oc o m p u t i n g t h ep o s i t i o no fs e n s o rn o d e s l o c a l i z a t i o nm e t h o dw h i c hc o m p u t e si n i t i a lv a l u e s o fn o d e s p o s i t i o na n do p t i m i z i n ge a c hn o d e sp o s i t i o nb yi t e r a t i o ni sc h o s e na s t h eb a s em o d eo fo u rm e t h o d t h e n ，w ea n a l y s es e v e r a li n i t i a lv a l u eg e n e r a t e a l g o r i t h m s ，a n di m p r o v eo no n eo ft h e mn a m e da f l ( a n c h o r f r e el o c a l i z a t i o n ) a l g o r i t h m c o n s i d e r e dt h e a d v a n t a g e s a n dd e f i c i e n c i e sb e t w e e nc e n t r a l i z e da n d d i s t r i b u t e d1 0 c a l i z a t i o nm e t h o d s ， a na p p r o a c hc a l l e dh i e r a r c h i c a ll o c a l i z a t i o n m d s ( h l m d s ) a l g o r i t h mi sp r o p o s e dt os o l v et h en o d e s 1 0 c a l i z a t i o np r o b l e m c l a s s i f i e s i n gn o d e si n t of r a m e w o r kn o d e sa n dn o n l l a ln o d e sm a k e st h ec o m p u t e r c o m p l e x i t yo ft h em e t h o di su n c o n c e m e dw i t hn o d ec o n n e c t i o n h m d sm e t h o d i sm o r es u i t a b l ef o rh i g hd e n s i t yw s n t h em e t h o di su s e dt o c o m p u t et h e 行a m e w o r kn o d e s1 0 c a t i o na n dt h en o m a ln o d e sl o c a t i o nr e s p e c t i v e l y ，a n dc a n i m p l e m e n ta 1 1a n dp a r t i a ln o d el o c a l i z a t i o n a tl a s t ，h l m d sa l g o r i t h mi ss i m u l a t e do nt h em a t l a bp l a t f o m s 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 ef l e x i b i l i t ya n dp r a c t i c a l i t yo ft h em e t h o d p e r f 0 m sw e l li nr e g u l a r l y - s h a p e da n dp a r t i a li r r e g u l a r l y - s h a p e dn e t w o r k s t h i s m e t h o dh a sb e e nw e l lu s e di no u rp r o j e c ta p p l i c a t i o n k e yw o r d s ：w s n ；m d s ；h i e r a r c h i c a ll o c a l i z a t i o n ；a n c h o r f r e el o c a l i z a t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得西南科技大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 签名：之弓立日期：艺_ 罗6 ， 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 新签名：娥哗日期：删z f7 西南科技大学硕士研究生学位论文第1 页 1绪论 1 1 课题背景及来源 无线传感器网络( w s n ：w i r e l e s ss e n s o rn e t w o r k ) 是当前在国际上备受关 注的、涉及多学科高度交叉、知识高度集成的前沿热点研究领域。它综合了 传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理 技术等，能够通过各类集成化的微型传感器协作地实时监测、感知和采集各 种环境或监测对象的信息，这些信息通过无线方式被发送，并以自组多跳的 网络方式传送到用户终端，从而实现物理世界、计算世界以及人类社会三元 世界的连通“。传感器网络具有十分广阔的应用前景，在军事国防、工农业、 城市管理、生物医学、等许多重要领域都有潜在的实用价值，已经引起了许 多国家学术界和工业界的高度重视，被认为是对2 1 世纪产生巨大影响力的技 术之一日，。 无线传感器网络作为一种新型的信息获取和处理模式。随机分布的集成 有传感器、数据处理单元和通信模块的节点，借助于内置的形式多样的传感 器测量其所在周边环境中的热、红外、声纳、雷达和地震波信号，从而探测 包括温度、湿度、噪声、光强度等众多网络部署者感兴趣的物质现象。随着 因特网技术、无线通信技术与电子技术的高速发展，无线传感器网络在世界 范围内引起了广泛的关注饽”。 本论文以国防科工委基金项目“x x x x x x x x 设计 ( 项目编号： 2 0 0 6 a 宰幸木宰木木0 2 6 4 ) 为依托。项目基于多移动智能体研究，研究移动智能体 运动协同、目标任务规划和目标探测作业及运行测控等任务，包括移动智能 体工作状态、环境感知、路径规划、目标信息获取传输和集群作业；各移动 智能体组队通过无线传感器网络快速感知自身或环境的状态信息，组建自组 织抗毁无线通信系统。无线传感器网络其目的是感知、采集和处理网络覆盖 区域中被监测对象的信息，并通过多跳中继方式将监测数据传送到智能体节 点( a g e n t n o d e ) ，智能体通过因特网或卫星链路将数据传送到远程中心进行 集中处理。图1 1 描述了无线传感器网络与多智能体( a g e n t ) 的数据融合方 式。 西南科技大学硕士研究生学位论文第2 页 集中 g e n t 活动监控区域 e 一 图卜1无线传盛器阿结与多智能体的数据融合 f lg 卜1t h ed a t a “s i o nb e t w e e nw s na n dm u l t l 一 g e n t 我们把整个活动区域分成为a g e n t 活动螗拄k 域和无线传感器监测i ) 域，如图l - l 所示，智能体通过无线自组组织网络( a d h o cn e t w o r k ) 建 立鲁棒性强的通信体系。a g e n t 之间通过任务规划分为主从模式，图中 a g e n t ( m ) 是我们所说的主智能体，a g e n t ( s ) 是从智能体。a g e n t ( m ) 有支配和 控制a g e n t ( s ) 的能力。当然，要实现强鲁棒性的通信网络可以根掘任务规 划和环境变化的情况，重新变更a g e n t ( m ) 和a g e n t ( s ) 的主从关系。我们研究 的重点是无线传感器监测区域的节点定位，例如现要通过a g e n t ( m ) 监控无 线传感器监控区域中t n 节点处的环境参数，t n 竹点可以通过在传感器嘲 络中多跳柬与a g e n t ( m ) 实现数据融合，然后由a g e n t ( m ) 通过因特网或卫星 链路向集中式控制台发送监控环境参数。这样对节点的位覆信息获知是必然 的。无线传感器网路节点的定位方法研究是项口研究中的关键部分的基础研 户嬲j 黝 j 础 凰 西南科技大学硕士研究生学位论文第3 页 究，因为节点的位置信息是监控和路由的基础，也仅有在知道节点位置定位 信息后才能够进行监控和路由等应用。 1 2 国内外研究动向 无线传感器网络的研究起步于2 0 世纪9 0 年代末期，被认为是2 l 世纪最 重要的技术之一，由于其在医疗卫生、环境监测和军事等领域广阔的应用前 景，引起了各国军事部门、工业界和学术界的极大关注，在基础理论和工程 技术层面提出了大量极具挑战性的研究课题。国际上最早开展无线传感器网 络研究的国家是美国，比较有代表性的项目有1 9 9 3 1 9 9 9 年间加州大学洛杉 矶分校( u c l a ) 开展的w i n s 项目；1 9 9 9 2 0 0 1 年间u cb e r k e l e y 开展的s m a r t d u s t 项目；1 9 9 8 2 0 0 2 年加州大学伯克利分校等2 5 个机构联合开展的s e n s i t 计划；1 9 9 9 2 0 0 4 年问海军研究办公室的s e a w 曲计划；2 0 0 4 年哈佛大学启 动的c o d e b u l e 平台研究计划等。2 0 0 5 年国家自然科学基金资助的项目 中，仅面上项目涉及传感器网络的就有15 项之多。2 0 0 6 年国家自然科学基 金将水下移动传感器网络的关键技术列为重点研究方向。清华大学、中科院 计算所、上海微系统所、沈阳自动化所、电子科技大学等多家高校和研究单 位均已开展了无线传感器网络相关领域的研究。 近1 0 年来，无线传感器网络节点定位问题研究的进展十分可喜，取得 了丰富的研究成果。特别是进入2 1 世纪后，对无线传感器网络w s n 的定位 问题有了许多新颖的解决方案和思想。但是，这个领域的研究从总体上说尚 处于一个起步的阶段，已有的研究工作正在为该领域提出越来越多需要解决 的问题，比如由成千上万节点组成的大规模或超大规模网络定位问题的低成 本( 时空、功耗、价格) 和高精度的实现以及在移动网络环境下具有自调整性 的定位算法的实现协，等等。现有的各种定位算法都是在一定的条件下提出， 适合于某种情况下的应用，得到的结果都是在定位精度、定位误差、可定位 节点的覆盖度、能量消耗、计算与通信代价、对网络形状和信标节点( 已知自 身位置的节点) 的部署要求上各有取舍儿“。由于各种用差别很大，没有普遍 适合于各种应用的定位算法，所以应针对不同的应用，通过综合考虑节点的 规模、成本及系统对定位精度等要求，来设计最适合的无线传感器节点定位 方法。 西南科技大学硕士研究生学位论文第4 页 1 3 研究的意义和主要内容 与传统的无线网络如移动通信网、无线局域网、蓝牙网络等相比，无线 传感器网络具有硬件资源受限、自组织、多跳、节点数量众多等特点。由于 这些特点，现有网络中的许多技术并不能直接应用于无线传感器网络，因此 无线传感器网络中有许多关键技术值得研究，节点定位技术就是其中之一。 节点定位算法是一个至关重要的问题，它是各种应用的基础。在无线传 感器网络的各种应用中，采集数据的节点位置是需要知道的最基本的信息之 一，在环境检测、目标跟踪等应用中如果不知道采集点的位置，那么所采集 的数据将是毫无意义的；其次，无线传感器网络的很多关键技术都需要利用 节点位置信息。例如，地理路由协议需要直接利用节点位置信息进行数据传 递，以避免信息在整个网络中的扩散，并可以实现定向的信息查询，有些路 由协议也需要节点位置信息来提高路由效率；网络拓扑控制机制需要利用节 点位置信息构建拓扑结构图，并评估节点的分布情况。 在无线传感器网络中，节点数量往往成百上千，并且大多数节点都是随 机分布的，而应用环境经常是那些人类难以进入或管理的区域，因此很难预 先布置好每个节点的位置，同时，为了尽可能地降低成本，每个节点的处理 器性能、存储器容量、无线收发器的通信距离以及电池能量都是极其有限的， 如果让所有节点都安装全球定位系统( g p s ) 、覆盖中国全境的“北斗一号” 双星定位系统曲“引等，不仅增加了成本，而且会使节点的能量很快消耗殆尽， 因而这种方法不适合实际使用。传感器节点能力的限制也要求定位技术尽可 能地降低计算复杂度和节点间的通信开销，以降低功耗，延长整个网络的生 命周期。另外，由于没有基础设施的协助，各种协议和算法应该采用分布式 计算方式，这对定位技术又提出了更高的要求。由此可见，无线传感器网络 迫切需要一种精度高、分布式、复杂度低和容错能力强的定位算法来得到所 有未知节点的位置，这方面能够提高无线传感器网络的性能，另一方面也 能降低成本，有利于它的大规模应用，。总之，人工部署和为所有网络节点 安装卫星通信设备都会受到成本、功耗、扩展性等诸多问题的限制，甚至在 某些场合可能根本无法实现，因此必须采用一定的机制和算法实现节点定位。 1 本文考虑的应用场景为高密度高连接度的网络，相邻节点间能进行一定 精度的测距，不同的监测任务对节点定位精度有不同要求，定位精度可由粗 到细。基于该应用场景，我们将研究以下两个问题：一是研究具有较高的定 位精度、较少的通信量和计算量的定位方法；二是研究在一定通信量和计算 西南科技大学硕士研究生学位论文第5 页 量的约束条件下具有灵活性的定位方法。 1 4 论文结构安排 论文全文共分为六部分 论文第一部分，描述了无线传器网路节点定位的研究背景和意义，联系 比较国内外发展现状，阐述本课题的主要研究内容。 论文第二部分，首先介绍了无线传感器网络的特点、体系结构、协议层 次，然后阐述了节点定位的基本概念，根据计算节点位置的基本方法，以及 无线传感器网络节点定位的基本术语。 论文第三部分，论述了无线传感器网络节点定位算法的各项性能评价标 准。分类介绍当前典型的无线传感器网络节点定位算法。选择适应性和鲁棒 性强的多维标度( m d s ) 定位的方法，作为研究无线传感器网络定位算法的定 位起点分析。 论文第四部分，对第三章当前典型的定位算法分析后，首先对计量型 m d s 的经典解法和迭代解法做了讨论。研究了m d s 算法迭代初值对计算结 果的影响，分析了现有的几种初值生成算法，并对a f l 算法的初值生成做了 改进，用m a t l a b 仿真比较了改进后的初值生成算法的优缺点。 论文第五部分，由于第四章中发现集中式松弛迭代m d s 计算方法对于 节点数量众多的大型网络适性较差。提出了集中与分布相结合的h l m d s 分 层定位方法，针对高连接度的网络，结合集中式计算与分布式计算的优点， 给上层应用提供了高低两种精度的可选定位方案，增加了定位的灵活性。采 用m a t l a b 仿真h l m d s 分层定位方法，并在不同的拓扑结构中分析定位性能。 最后是全文总结，并展望后续工作。 西南科技大学硕士研究生学位论文第6 页 2 无线传感器网络及节点定位原理 本章介绍了无线传感器网络的特点、体系结构和无线传感器网络协议， 描述节点定位技术的基本原理，以及无线传感器网络节点定位相关术语。 2 。1无线传感器网络 无线传感器网络由大量高密度分布的处于被观测对象内部或周围的传感 器节点组成。其节点不需要预先安装或预先决定位置，这样提高了动态随机 部署于不可达或危险地域的可行性。 2 1 1 无线传感器网络的特点 无线传感器网络属于一种特殊的a d - h o c 网络，它的实现需要自组织网络 技术，它虽然与传统的a d h o c 网络有很多相似的地方，但无线传感器网络与 传统无线网络( 如w l a n 和蜂窝移动电话网络) 有着不同的设计目标n ，。后 者在高度移动的环境中通过优化路由和资源管理策略最大化带宽的利用率， 同时为用户提供一定的服务质量保证。而无线传感器网络中除少数节点需要 移动外，大部分节点都是静止的。由于它们通常部署在人类无法接近的恶劣 甚至危险的远程环境中，对电池的更换是非常困难甚至是不可能的，但是无 线传感器网络的生存时间却要求长达数月甚至数年，。因此，如何在不影响 功能的前提下，尽可能节约无线传感器网络的电池能量成为无线传感器网络 软硬件设计中的核心问题。 随着研究的不断深入，人们发现无线传感器网络与传统无线网络有着明 显不同的技术要求，前者以数据为中心，数据是被分散处理的，系统会根据 需要尽早对数据进行处理，这样可以减少网络的流量，降低功耗并提高系统 利用率。而后者以传输数据为目的，一些为a d h o c 网络设计的协议和算法并 不适合传感器网络的特点和应用的需求。和网络中单个节点上的信息相比， 无线传感器网络的应用程序更关心与其相关的中间节点上的数据处理、融合 和缓存等。在密集的无线传感器网络中，相邻节点间的距离非常短，低功耗 的多跳通信模式节省功耗，同时增加了通信的隐蔽性，避免了长距离的无线 通信易受外界干扰的影响。与传统的无线网络相比，无线传感器网络具有以 下特点，： ( 1 ) 电源容量有限无线传感器网络节点一般由电池供电，而且在使用过程 中也不能给电池充电或更换电池。因此无线传感器网络设计的基本原则 西南科技大学硕士研究生学位论文第7 页 就是要以节能为前提。 ( 2 ) 资源有限传感器节点由于受到低成本、小体积和低功耗的限制，其硬 件、软件资源非常有限。 ( 3 ) 无中心无线传感器网络一般是一个对等式的网络。 ( 4 ) 自组织线传感器网络的布设和展开无需依赖于任何预设的基础设施。 ( 5 ) 多跳路由网络中节点通信距离有限，如果希望与较远的节点进行通信， 则需要通过中间节点多跳路由来实现。 ( 6 ) 动态拓扑无线传感器网络是一个动态的网络，节点可以随处移动，网 络的拓扑结构会随时发生变化，因此网络应该具有动态拓扑组织功能。 ( 7 ) 分布密集为了对一个区域执行监测任务，传感器节点往往分布得非常 密集，利用节点之间高度连接性来保证系统的容错性和抗毁性。 2 1 2 无线传感器的结构 在不同的应用中，传感器节点的结构不尽相同，但一般都由传感单元、 数据处理单元、数据收发单元、电源单元等功能模块组成。传感单元由各类 传感器及数模转换设备组成，传感器的类型是由被监测物理信号的形式决定 的，数据处理通常选用低功耗嵌入式微控制器，短距离的无线通信模块组成。 因为需要进行较复杂的任务调度与管理，系统还需要一个微型化的实时操作 系统，加州大学伯克利分校为此专门开发了t i n y o s ，另外还有u c o s 等 n 。”。图2 1 描述了无线传感器节点的一般组成。除此之外，根据具体应用 的需要，可能还会有定位系统、电源再生单元和移动单元等。 图2 1传感器网络节点组成框图 f i g 2 1 t h eb i o c kd i a g r a mo fw ir e i e s ss e n s o rn e t w o r k 西南科技大学硕士研究生学位论文第8 页 2 1 3 无线传感器网络的协议层次 根据网络的体系结构和具体应用范围的不同，w s n 的协议层次也不完全 相同，并且到目前为止，还没有形成w s n 的标准协议栈。最典型的情况是自 下而上包含物理层、数据链路层、网络层、传输层、应用层；另外，协议栈 还包括能量管理平台、移动管理平台和任务管理平台m ，。如图2 2 所示： 图2 2无线传感网络通信协议栈 fig 2 2t h ec o m m u nic a t ep r o t o c ols t a c ko fwlr eie s s s e n s o rn e t w o r k 物理层：负责提供简单而健壮的信号调制和无线收发技术。 数据链路层：数据链路层负责介质访问控制( m a c ) 和差错控制。 网络层：网络层负责路由协议发现和维护，是w s n 的重要协议层，也是目 前研究的热点之一。 传输层：传输层负责将传感器网络的数据提供给外部网络，比如因特网。 应用层：包括一系列基于监测任务的应用软件。 能量管理平台：管理传感器节点如何使用能源，在各个协议层都需要考虑节 省能量。 移动管理平台：监测并注册传感器节点的移动，维护到汇聚节点的路由，使 传感器节点能动态跟踪其邻居的位置。 任务管理平台：在一个给定的区域内平衡和调度监测任务。 西南科技大学硕士研究生学位论文第9 页 2 2 定位技术基本原理 无线传感器网络中的未知节点在直接或间接地获得其到网络信标节点的 距离或相对角度信息后，通常使用下述方法之一计算自身位置。在获得节点 间的距离( 或角度) 后就可以采用三边测量法( t r i l a t e r a t i o n ) ，三角测量法 ( t r i a n g u l a t i o n ) 或最大似然估计法( m u l t i l a t e r a t i o n s ) 计算节点的位置。 2 2 1三边测量法 三边测量法m 2 3 ，如图2 3 所示，已知a 、b 、c 三个节点的坐标分别为 ( 屯，儿) 、( ，虼) 、( t ，儿) ，以及它们到未知节点d 的距离分别为吃、吃、吃， 假设节点d 的坐标为( x ，j ，) 。那么存在下列公式： i ( x 一艺) 2 + ( y 一儿) 2 = 吃 ( x 一) 2 + o 一儿) 2 = 吃 ( 2 1 ) l ( 石一) 2 + o 一咒) 2 = 吃 由公式( 2 1 ) 可以得到节点d 的坐标为： ； = 主 乏二乏；主爱二芰； 。1 薹二茎：委二萎：凄二凄 c 2 - 2 ， l y jl 2 ( 一t ) 2 ( 一儿) jl 一+ 露一谚+ 衫一l 、叫 fig 2 3 图2 3三边测量法图示 西南科技大学硕士研究生学位论文第1 0 页 2 2 2 三角测量法 三角测量定位方法2 儿”，也称为信号到达角度( a o a ) 定位法或方位测量 定位法。该方法是通过未知节点接收器天线或天线阵列测出锚节点发射电波 的入射角，从而构成一根从未知节点到锚节点的径向连线，即方位线。在二 维平面中，利用两个或更多锚节点的a o a 测量值，按照a o a 定位算法确定1 多条方位线的交点，即可计算出未知节点的估计位置。 图2 4三角测量定位 f i g 2 4 t h et rii a t e r a t io nl o c a liz a t i o nm e t h o di llu s r a t i o n 三角测量法如图2 4 所示，已知a 、b 两个锚节点的坐标分别为( 屯，咒) 、 ( 而，儿) ，假设未知节点d 的坐标为( x ，y ) ，并假设d 测得锚节点a 、b 发出信 号的到达角度分别为( 岛，岛) ，则下式成立： t a n ( 劬= 生，汪1 ，2 y 一咒 ( 2 3 ) 通过求解上述非线性方程，可以求出节点d 的坐标( x ，y ) 。 2 2 3 极大似然估计法 极大似然估计法，也称多边测量法m ，如图2 5 所示。己知l 、2 、3 等n 个节点的坐标分别为( 五，乃) 、( 而，兄) 、( 毛，乃) 、( 毛，儿) ，以及它们到未知 节点d 的距离分别为日、d 2 、b 、见，假设节点d 的坐标为( x ，y ) 。 西南科技大学硕士研究生学位论文第1 1 页 图2 5极大似然估计法图示 f i g 。2 5 t h em a x i 川u mii k e lj h o o dg a u g ejil u s t r a t j o n 那么，存在下列公式： ( 五一x ) 2 + ( 乃一y ) 2 = 吐2 ( 一x ) 2 + ( 只一y ) 2 = 吒2 从第一个方程开始分别减去最后一个方程，得： 么= ( 2 4 ) 而一恐一2 “一毛) + 衍一z 一2 ( 乃一儿) y = 盔2 一 ( 2 5 ) 靠。一一2 ( 。一矗h + 蠕一z 一2 ( 以一。一以) y = 一刃 的线性方程表示方式为：删= 6 ，其中： 2 瓴一毛) 一五) 撕一咒) l 。 l ， 1 ，6 = i 2 一咒) j 彳一+ 并一+ 一砰 i 乙一+ 乙一z + 一z 乙 m _ = _ ( 2 - 6 ) 使用标准最小均方差估计方法可以得到节点d 的坐标为：童= ( 彳7 彳) 4 r 6 。 西南科技大学硕士研究生学位论文第1 2 页 2 3 节点定位的基本术语 为了后面的研究工作的开展，这里我们将简单介绍一些常见节点定位的 基本术语阳”。 邻居节点( n e i 曲b o rn o d e s ，n n ) ： 传感器节点通信半径内的所有其他节点，称为该节点的邻居节点； 跳数( h o pc o u n t ，h c ) ： 两个节点之间间隔的跳段总数，称为两个节点间的跳数； 跳段距离( h o pd i s t a n c e ，h p ) ： 两个节点之问间隔的各跳段距离之和，称为两节点间的跳段距离； 基础设施( i n f r a s t r u c t u r e ) ： 协助传感器节点定位的已知自身位置的固定设备，如卫星、基站； 到达时间( t i m e0 f a 币v a l ，t o a ) ： 信号从一个节点传播到另一个节点所需要的时间，称为信号的到达时间； 到达时间差( t i m ed i f i f e r e n c eo f a v a l ，t d o a ) ： 两种不同传播速度的信号从一个节点传播到另一个节点所需要的时间之 差，称为信号的到达时间差； 接收信号强度指示( 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 i ) ： 节点接收到无线信号的强度大小，称为接收信号的强度指示； 到达角度( a n 9 1 eo f a 币v a l ，a o a ) ： 节点接收到的信号相对于自身轴线的角度，称为信号相对接收节点的到 达角度； 视线关系( l i n eo fs i g h t ，l o s ) ： 两个节点间没有障碍物间隔，能够直接通信，称为两个节点问存在视线 关系； 非视线关系( n ol o s ，n l o s ) ： 两个节点间存在障碍物，不能够直接通信，称为两个节点间存在非视线 关系； 西南科技大学硕士研究生学位论文第1 3 页 2 4 本章小结 本章介绍了关于无线传感器网络的特点、结构、协议层次，并对传感器 节点定位的基本概念和术语进行了说明和解释，并对无线定位机制、节点测距 方法、计算节点位置的基本方法给于了总结说明。下章无线传感器网络定位 算法的综述将在此基础上分析当前的典型无线传感器网络节点定位算法。 西南科技大学硕士研究生学位论文第1 4 页 3 无线传感器网络及定位算法综述 在上一章的定位理论分析后，我们对当前典型的传感器网络定位算法分 析，以便选择一个适合于文中定位场境的算法研究。首先介绍了无线传感器 网络自身定位系统和节点定位算法的主要性能评价指标，然后根据当前无线 传感器网络定位系统和定位算法的特点进行分类，并对每个类别中的典型算 法和系统进行了详细的阐述和分析，引出了以多维标度( m d s ) 的数据处理 技术作为研究无线传感器网络定位算法的定位起点分析。 3 1 无线传感器网络节点定位算法的性能评价 w s n 定位系统和算法的性能直接影响其可用性，如何评价它们是一个需 要深入研究的问题。下面定性地讨论几个常用的评价定位系统和算法的标准 【1 1 f 】| l o 】。 ( 1 ) 定位精度 定位技术首要的评价指标就是定位精度，一般用误差值与节点无线射程 的比例表示，例如，定位精度为2 0 表示定位误差相当于节点无线射程的 2 0 。也有部分定位系统将二维网络部署区域划分为网格，其定位结果的精 度也就是网格的大小，如微软的r a d a r ，w i r e l e s sc o 印o r a t i o n 的r a d i o c a m e r a 在占 守o ( 2 ) 规模 不同的定位系统或算法也许可在园区内、建筑物内、一层建筑物或仅仅 是一个房间内实现定位。另外，给定一定数量的基础设施或在一段时间内， 一种技术可以定位多少目标也是一个重要的评价指标。例如，r a d a 系统仅 可在建筑物的一层内实现目标定位，剑桥的a c t i v e0 硒c e 定位系统每2 0 0 m s 定一个节点。 ( 3 ) 锚节点密度 锚节点定位通常依赖人工部署或g p s 实现。人工部署锚节点的方式不仅 受网络部署环境的7 限制，还严重制约了网络和应用的可扩展性。而使用g p s 定位，锚节点的费用会比普通节点高两个数量级，这意味着即使仅有1 0 的 节点是锚节点n ”，整个网络的价格也将增加1 0 倍。因此，锚节点密度也是评 价定位系统和算法性能的重要指标之一。 西南科技大学硕士研究生学位论文第1 5 页 ( 4 ) 节点密度 在w s n 中，节点密度增大不仅意味着网络部署费用的增加，而且会因 为节点间的通信冲突问题带来有限带宽的阻塞。节点密度通常以网络的平均 连通度来表示。许多定位算法的精度受节点密度的影响，如d v h o p 【l 算法仅 可在节点密集部署的情况下合理地估算节点位置。 ( 5 ) 容错性和自适应性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的网络节 点设备。但在真实应用场合中常会有诸如以下的问题：外界环境中存在严重 的多径传播、衰减、非视距( n o n l i n e o f s i 曲t ，n l o s ) 、通信盲点等问题； 网络节点由于周围环境或自身原因( 如电池耗尽、物理损伤) 而出现失效的问 题；外界影响和节点硬件精度限制造成节点间点到点的距离或角度测量误差 增大的问题。由于环境、能耗和其他原因，物理地维护或替换传感器节点或 使用其他高精度的测量手段常常是十分困难或不可行的。因此，定位系统和 算法的软、硬件必须具有很强的容错性和自适应性，能够通过自动调整或重 构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。 ( 6 ) 功耗 功耗是对w s n 的设计和实现影响最大的因素之一。由于传感器节点电 池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的 计算量、通信开销、存储开销、时间复杂性是一组关键性指标。 ( 7 ) 代价 定位系统或算法的代价可从几个不同方面来评价。时间代价包括一个系 统的安装时间、配置时间、定位所需时间。空间代价包括一个定位系统或算 法所需的基础设施和网络节点的数量、硬件尺寸等。资金代价则包括实现一 种定位系统或算法的基础设施、节点设备的总费用。 上述7 个性能指标不仅是评价w s n 定位系统和算法的标准，也是其设 计和实现的优化目标。为了实现这些目标的优化，有大量的研究工作需要完 成。同时，这些性能指标是相互关联的，必须根据应用的具体需求做出权衡， 以选择和设计合适的定位技术。 3 2无线传感器网络定位算法的分类 尽管无线传感器网络定位系统和算法的分类还没有一个统一的标准，也 西南科技大学硕士研究生学位论文第1 6 页 不一定适用于每一种定位系统和算法，但下面这些分类方法能在一定程度上 刻画不同定位技术的特点。 3 2 1基于测距和无需测距的定位 根据定位过程中是否测量实际节点的距离，把定位算法分为：基于距离 的( r a n g e b a s e d ) 定位算法和距离无关的( r a n g e f r e e ) 定位算法。前者通过测量 节点间的距离或角度信息，使用三边测量法、三角测量法或最大似然估计法 计算节点位置；后者则无需距离和角度信息，仅根据网络连通性等信息实现。 下面分别介绍这两类方式中的典型定位算法；后者无需测量节点的绝对距离 或方位，而是利用节点间的估计距离计算节点位置。 r a n g e b a s e d 定位算法常用的测距技术有r s s i ，t o a ，t d o a 和a o a 。 r s s i ( r e e e i v e ds i g n a ls t r e n g t hi n d i e a t o r ) 虽然符合低功率、低成本的要求，但 有可能产生士5 0 的测距误差；t o a ( t i m eo f a r r i v a l ) 功需要节点精确的时间 同步；t d o a ( t i m ed i f 诧r e n c eo na r r i v a l ) 技术受限于超声波传播距离有限和 n l o s 问题对超声波等信号的传播影响；a o a ( a n g l eo fa 玎i v a l ) 也受外界环 境影响，而且需要额外硬件，在硬件尺寸和功耗上可能无法用于传感器节点 。除上述测距技术的局限性外，r a n g e b a s e d 定位机制使用各种算法来减小 测距误差对定位的影响，包括多次测量叫循环定位求精准，这些都要产生大 量计算和通信开销。所以r a n g e b a s e d 定位机制虽在定位精度上有可取之处， 却并不适用于许多应用领域( 低功耗、低成本) 。因功耗和成本因素，以及定 位精度对大多数应用己足够( 当定位误差小于4 0 时，对路由性能和目标追踪 精确度的影响不会很大) ，r a n g e f r e e 定位方案倍受关注 m “。 3 2 2 绝对定位与相对定位 绝对定位与物理定位类似，定位结果是一个标准的坐标位置，如经纬度。 而相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。 绝对定位有广泛的应用领域，但相对定位也有自己的应用场合。尤其是基于 地理位置的路由，只需相对定位即可。典型的相对定位算法和系统有s p a n 3 1 ( s e l f - p o s i t i o n i n ga 1 9 0 r i t h m ) ， l p s ( l o c a lp o s i t i o n i n gs y s t 锄) ， s p o t o n 等， m d s m a p 定位算法，可以根据网络配置的不同分别实现两种定位。 实现绝对定位需要有部分已知位置的参考节点，又叫锚节点，这类节点 西南科技大学硕士研究生学位论文第1 7 页 一般由人工部署在指定地点或者通过卫星定位系统获取绝对位置。其余的节 点则利用锚节点的位置作参考实现绝对定位。 3 2 3集中式定位与分布式定位 集中式计算就是指把所需信息传送到某个中心节点，并在那里进行节点 定位计算的方式；分布式计算是指依赖节点间的信息交换和协调，节点自行 计算的定位方式。 集中式计算的优点在于从全局角度统筹规划，计算量和存储量几乎没有 限制，可获得相对精确的位置估算。它的缺点包括与中心节点位置较近的节 点会因为通信量大而过早消耗完电能，导致整个网络与中心节点信息交流的 中断，无法实时定位等。集中式定位算法包括凸规划( c o n v e x o p t i m i z a t i o n ) 】【l ”、m d s m a p 。n - h o pm u l t i l a t e r a t i o np r i m i t i v e 1 定位算法可 根据应用需求采用两种不同的计算模式。 分布式定位与集中式定位相反，尽量将计算量分摊到网络中的各个节点 上，而不是在某一个节点上完成，以减小甚至消除对中心节点计算能力的要 求，对于资源受限和无中心自组织的无线传感器网络来说是比较理想的定位 方法。典型的分布式定位方法有a p s 、a f l 、e i g e n 、m d s m a p ( p ，r ) 引她们 等。这些方法在节点部署方式、信号复杂程度、定位精度等方面作了不同程 度的折衷。 3 3无线传感器网络定位算法与系统 目前为止，w s n 定位系统和算法的研究大致经过了两个阶段。第一阶段 主要偏重予i n f r a s t m c t u r e - b a s e d 类定位技术，代表性的研究成果有a c t i v e b a d g e ，a c t i v eb a t ，r a d a r 1 等。而对于a d h o ci n f r a s t r u e t u r e f r e e 定位技术 的关注和研究可以认为是w s n 定位系统和算法研究的第二阶段，目前已经 成为w s n 研究领域一个不小的热点。下面就其中典型的定位系统和算法归 纳总结。 3 3 1质心定位算法 质心算法h 7 1 是南加州大学的n i m p a