（计算机应用技术专业论文）无线传感器网络定位算法的研究及应用.pdfVIP

南京航空航天大学硕士学位论文 i 摘 要 无线传感器网络集中了微机电技术、感知技术、嵌入式计算技术、 分布式信息处理技术和无线通信技术，孕育出一种全新的信息获取 和处理模式。布局和覆盖、节点定位、网络通信协议是传感器网络 研究中的几个基本问题。其中，节点定位问题是传感器网络进行目 标识别、监控、跟踪等众多应用的前提，也是传感器网络研究中的 热点问题之一。 应 用 于 传 感 器 网 络 节 点 定 位 的 技 术 主 要 有 基 于 测 距 ( r a n g e - b a s e d ) 的定位技术和无需测距( r a n g e - f r e e ) 的定位技术。前 者定位精度高，但是传感器节点需要额外的硬件设备。后者定位精 度较低，对硬件要求也较低。论文主要研究了基于测距的无线传感 器网络定位算法。由于锚节点的多少直接决定了定位算法的不同， 所以在锚节点密集和锚节点稀疏两种情况下分别进行算法研究。在 锚节点密集的情况下，依据三个锚节点共线时定位的误差最大，而 三 个 锚 节 点 所 构 成 的 三 角 形 是 等 边 三 角 形 则 定 位 的 误 差 最 小 的 原 理 ， 提 出 了 角 度 权 值 定 位 算 法 。 在 锚 节 点 稀 疏 的 情 况 下 ， 对 d v - distance 定位算法进行改进，提出了改进的 d v - distance 误差修正 定位算法，仿真实验表明，这两个算法在一定程度上提高了节点的 定位精度。 在利用移动锚节点进行定位的机制中，锚节点的移动路径是一个 关键的问题。论文讨论了锚节点在网络监控区域的移动路径问题， 以及将 b o u n d i n g - b o x定位算法应用到移动锚节点定位中，并在此基 础上提出了一种改进的基于移动锚节点的 b o u n d i n g - b o x定位算法。 关 键 字 ： 无 线 传 感 器 网 络 ， 定 位 ， 角 度 权 值 算 法 ， d v - distance 算法，移动锚节点，b o u n d i n g - b o x算法 无线传感器网络定位算法的研究及应用 ii abstract wireless sensor networks, which integrate technologies of micro- electro- mechanism, sensing, embedded computing, distributed information processing and wireless communication, lead to a new pattern of information gathering and processing. the fundamental problems of sensor networks are deployment and coverage, localization, and networking protocols. and localization, which has been focused as a basic problem, is the precondition of many applications of sensor networks, such as target identification, surveillance and tracking. the location techniques for wsn can be divided into two categories: range- based approaches and range- free approaches. range- based methods have better accuracy, but require additional hardware at the sensor nodes. range- free methods have lower accuracy and requirement of hardware. the thesis mainly focuses the investigation on the range- based algorithms for wsn. because the number of the anchor nodes determines the difference of the localization algorithms, the algorithms are investigated in the two cases- the dense anchor nodes and the thin anchor nodes. in the situation of the dense anchor nodes, when three anchor nodes is in line ,the localization error is most and when the triangle which three anchor nodes form is equilateral triangle, the localization error is least. according to the above principle, a angular weighted localization algorithm is presented. in the situation of the thin anchor nodes, dv- distance localization algorithm improved, an improved dv- distance error correction localization algorithm is presented. simulations show that the two algorithms can improve the localization accuracy on certain degree. a key problem of the localization with a mobile anchor node is the mobile path. the thesis discusses the problem of the mobile path in the area of wsn. the bounding- box localization algorithm is applied to the mobile anchor node localization. at the base, an improved 南京航空航天大学硕士学位论文 iii bounding- box localization algorithm is presented. key words: wireless sensor networks, localization, angular weighted localization algorithm, dv- distance algorithm, mobile anchor node, bounding- box algorithm 南京航空航天大学硕士学位论文 vii 图清单 图 1.1 典型传感器网络结构 . 4 图 2.1 凸 规 划 示 意 图 . 14 图 2.2 d v - h o p定 位 算 法 示 意 图 . 15 图 2.3 euclidean 定 位 算 法 示 意 图 . 16 图 2.4 pit 原 理 示 意 图 . 18 图 2.5 apit 原 理 示 意 图 . 19 图 2.6 ahlos 定 位 算 法 示意图 . 20 图 2.7 n- hop multilateration primitive 中 节 点 位 置 的 初 始 估 算 . 21 图 3.1 t d o a测距技术示意图 . 25 图 3.2 三边测量法示意图 . 26 图 3.3 最 大 似 然 估 计 法 示 意 图 . 27 图 3.4 锚 节 点 分 布 的 两 个 特 例 . 28 图 3.5 三 个 锚 节 点 形 成 三 角 形 . 28 图 3.6 两个锚节点得到两个位置坐标 . 29 图 3.7 判 断 两 个 坐 标 的 方 法 示 意 图 . 30 图 3.8 三角计算距离示意图 . 31 图 3.9 角度权值定位算法的仿真结果 . 36 图 3.10 改 进 的 dv- distance 误 差 修 正 定 位 算 法 的 仿 真 结 果 . 37 图 4.1 锚节点的移动路径 . 41 图 4.2 离 散 通 讯 模 型 . 43 图 4.3 5 个 节 点 的 位 置 关 系 . 44 图 4.4 坐标系建立示意图 . 45 图 4.5 算 法 仿 真 结 果 . 47 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导 下，独立进行研究工作所取得的成果。尽我所知，除文中已 经注明引用的内容外，本学位论文的研究成果不包含任何他 人享有著作权的内容。对本论文所涉及的研究工作做出贡献 的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复 印件，允许论文被查阅和借阅, 可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或其 他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 第一章 绪论 1 . 1研究背景 1 . 1 . 1无线传感器网络的发展 321、 随着传感器技术、嵌入式计算技术、通信技术和半导体与微机 电系统制造技术的飞速发展和日益成熟，使得制造大量价格低廉、 体积小、功耗低，同时具有感知能力、计算存储能力和通信能力的 微型传感器成为可能，这些微型传感器开始广泛应用到军事、工业、 农业和宇航等各个领域。无线网络传感器是集传感器执行器、控制 器和通信装置于一体，集传感与驱动控制能力、计算能力、通信能 力于一身的资源受限的嵌入式设备。由这些微型传感器构成的网络 称之为无线传感器网络。这种传感器网络综合了传感器技术、嵌入 式计算技术、分布式信息处理技术和通信技术，能够协作地实时监 测、感知和采集网络分布区域内的各种环境或监测对象的信息，并 对这些信息进行处理，获得详尽而准确的信息，传送到需要这些信 息的用户。 无线传感器网络是一种无基础设施的无线网络。它作为一种全新 的研究技术，在基础理论和工程技术两个层面向科技工作者提出了 大量的挑战性研究课题。美国商业周刊在预测未来技术发展的报告 中，将无线传感器网络列为 21 世纪最有影响力的 21 项技术之一。 麻省理工学院的技术评论杂志评出了对人类未来生活产生深远 影响的十大新兴技术，无线传感器网络位于这十种新技术之首。无 线传感器网络、塑料电子学和仿生人体器官又被称为全球未来的三 大高科技产业。 无线传感器网络的研究开始于 20 世纪 90 年代末期。从 2000 年 起，国际上开始出现一些有关无线传感器网络研究结果的报道。美 国自然科学基金委员会 2003 年制定了传感器网络研究计划，进行相 关基础理论的研究。美国国防部和各军事部门都对传感器网络给予 了高度重视，把传感器网络作为一个重要研究领域，设立了一系列 的军事传感器网络研究项目。美国英特尔公司和微软公司等信息工 无线传感器网络定位算法的研究及应用 2 业界巨头也开始了传感器网络方面的工作，纷纷设立或启动相应的 行动计划。日本、英国、意大利、巴西等国家也对传感器网络表现 出了极大的兴趣，纷纷展开了该领域的研究工作。但是，这些研究 成果目前大部分处于起步阶段，距离实际需求还相差甚远。我 国 在 传感器网络方面的研究相对较少，但近年来，国内一些高等院校和 研究机构也开始展开了无线传感器网络的理论和应用的研究工作， 主要有清华大学、中科院软件所、浙江大学、哈尔滨工业大学、中 科院自动化所、中国人民大学等。目前国内研究重点主要集中在穿 戴式计算、上下文感知环境、智能教室等领域。 1 . 1 . 2无线传感器网络定位技术 654、 在无线传感器网络中，位置信息通常是传感器网络节点监测消息 中所必须包含的重要内容。对于一个没有事件发生位置或者获得信 息的节点位置的监测消息，可能对于监测活动是没有任何意义的。 在无线传感器网络的各种应用中，当节点监测到网络中某个地方事 件发生时，它所关心的一个重要的问题就是该事件发生的位置。因 此，确定事件发生的位置或确定获取消息的节点位置是无线传感器 网络所必需具备的一项功能，对无线传感器网络应用的有效性起着 至关重要的作用。 无线传感器网络的节点通常都是随机部署的，以自组织的方式相 互协调工作，节点的部署具有不可控制性。因此，网络中的各个节 点事先无法知道自身的位置，这就需要网络节点在部署后能够进行 实时定位。无线传感器网络的节点定位通常是利用少数已知位置的 节点（这种节点称之为锚节点） ，按照某种定位的机制确定未知节点 的位置。无线传感器网络的节点定位是提供监测事件位置信息的前 提依据。 全球卫星定位系统(global positioning system, gps)是目前应用 最广泛最成熟的定位系统，gps 系统利用精确的同步卫星时钟提供 授时和测距以对用户节点进行定位，具有定位精度高、实时性好、 抗干扰能力强等优点，但是 gps 定位仅适应于无遮挡的室外环境， 其用户设备通常能耗高体积大，成本也较高，而传感器节点受到成 本、能量和体积的限制，gps 的成本和功耗是传感器节点所无法接 受的，gps 不适用于低成本的无线传感器网络。 在无线传感器网络中，传感器节点能量有限、可靠性差、网络规 南京航空航天大学硕士学位论文 3 模大且节点随机布放、无线模块的通信距离有限，对定位算法和定 位技术提出了很高的要求。因此，必须针对传感器网络的以上特点 设计出具有自组织性、健壮性、节能性、分布式计算特点的定位技 术和算法。 剑桥实验室最早于 1992 年开发出室内定位系统 active badge 之 后，各国研究者一直致力于无线传感器网络定位系统和算法的研究。 最近已有一些无线传感器网络的定位系统被提出，其中有代表性的 研 究 成 果 包 括radar 7 , active bat 8 , active badge 9 , radio camera 10 ,active office 11 , easy living 12 , spoton 13 , hiball tracker 14 , parc tab 15 ,smart floor 16 , smart rooms 17 , 3d- id 18 , wherenet 19 等，文献 21,20 中对这些定位系统作了详细的描述和分析。 经过多年的努力，研究者们也不断提出了无线传感器网络的各种定 位技术和算法，这些技术和处理算法都能够在一定程度上解决无线 传感器节点的自身定位问题，但由于每一种算法是用来解决不同的 问题或支持不同的应用，它们在用于定位的物理现象、传感器设备 的组成、能量需求、基础设施和时空的复杂性等多方面都有不同。 研究者们针对不同的环境要求提出各种各样的解决方案，在相对的 条件下很多都能达到很好的效果，但真正的应用还比较少，而且一 般条件限制都是非常严格的。因此，该领域还需要更多的人提出更 好的办法，以求更好地解决传感器网络节点的定位问题。 传感器网络节点定位问题的研究在国内才刚刚起步，国外虽有 一定研究，但偏重于定位算法的理论研究，距离实用化也还有一定 的差距。 1 . 2传感器网络的体系结构 典 型 的 无 线 传 感 器 网 络 由 传 感 器 节 点 、 接 收 发 送 器(也称网关节 点、sink 节点)、internet 或通信卫星、任务管理节点等部分构成 22 。 传感器节点分布在网络的感知区域内，当节点收集到感知数据时， 就将数据通过多跳路由的方式传送到网关节点。网关节点也可以通 过 多 跳 路 由 的 方 式 将 数 据 发 送 给 各 传 感 器 节 点 。 网 关 节 点 直 接 与 internet 或通信卫星相连接，通过 internet 或通信卫星实现任务管理 节点(观察者)与传感器之间的通信，如图 1.1 所示 23 。 无线传感器网络定位算法的研究及应用 4 图 1.1 典型传感器网络结构 传感器节点本质上是一个微型化的嵌入式系统 24 ，由电池提供 能量，由于其具有有限的计算、存储、通信能力，传感器节点的通 信距离也相对比较短，所以传感器节点一般只能与其相邻的节点进 行数据的交换，通过多跳路由的方式传输数据。因此，传感器节点 在网络中兼顾传统网络节点的终端和路由器的双重功能，除了进行 本地数据采集和处理外，还要与其他节点协作进行数据的存储、交 换、融合等操作。相比较而言，网关节点的计算、存储、通信能力 较强，可以是特殊的网关设备，它实现了传感器网络和外部网络的 互连。 1 . 3无线传感器网络的特点 无线传感器网络为中短距离、低速率网络，射频传输成本低，各 节点只需要很少的能量，功耗小适于电池长期供电，可实现一点对 多点、两点间对等通信、快速组网自动配置、自动恢复和高级电源 管理，任意两个传感器节点之间可相互协调实现数据通信。与目前 常见的其他无线网络，如移动通信网、无线局域网、蓝牙网络以及 ad- hoc 网络相比，无线传感器网络由于其使用目的以及要求不同， 存在着许多特点 2625、 ，具体如下： 1、传感器网络节点数量多且分布广泛 无线传感器网络一般都分布在地理范围较大的区域，传感器节点 布置的数量也较多，可以达到几万，甚至几十万。传感器网络的这 检测区域 互 联 网 、 卫 星 或 移 动 通 信网络 监 控 中 心 （ 观 察 者 ） 南京航空航天大学硕士学位论文 5 种节点数量多、分布广的特点使得网络的维护有一定的困难。 2、网络的自组织、自识别 由于网络开始架构时传感器节点是被任意布置的，不依赖于任何 预先设定的网络设施。节点通过分层协议与分布式算法协调各自的 行为，快速组成一个独立网络。 3、能源受限制 在 网 络 中 节 点 采 用 电 池 作 为 能 量 来 源 ， 而 由 于 其 特 殊 的 应 用 领 域，决定了电池在使用过程中既不能接受充电也不能被更换，这就 使得电池能量完全决定了节点的寿命。为此，网络节点硬件设计方 面一定要考虑最大限度节电，而软件设计方面各层协议也要将节能 置于重要地位，必要时甚至可以为节能而牺牲其他网络性能指标， 尽可能地提高节点的工作寿命，从而延长整个网络的工作时间。 4、硬件资源有限 在 无 线 传 感 器 网 络 中 ， 节 点 的 计 算 能 力 与 内 存 空 间 受 到 种 种 限 制，如价格、体积，最主要的是能耗，因此，相较于普通计算机， 它们的功能要弱很多。 5、通信能力有限 无线传感器网络的传感器的通信带宽有限而且经常变化，通信覆 盖范围只有几十到几百米。传感器节点之间的通信断接频繁，经常 导致通信失败。 6、动态拓扑 无线传感器网络是动态网络，因为在网络中节点可以随处移动， 网络中随时可能发生节点加入或退出网络的事件，这样会使网络的 拓扑结构随时发生变化，故网络中应具有动态拓扑组织功能。 7、感知数据流巨大 无 线 传 感 器 网 络 中 的 每 个 传 感 器 节 点 通 常 都 产 生 较 大 的 流 式 数 据，并具有实时性。这就需要研究强有力的分布式数据流管理、查 询、分析和挖掘方法。 1 . 4无线传感器网络的关键技术 无线传感器网络作为当今信息领域一个新的研究热点，涉及多 学科交叉的研究领域，有非常多的关键技术有待发现和研究，下面 仅列出部分关键技术 2726、 。 无线传感器网络定位算法的研究及应用 6 1、网络拓扑控制 对于无线的自组织的无线传感器网络而言，网络拓扑控制具有特 别重要的意义。通过拓扑控制自动生成的良好的网络拓扑结构，能 够提高路由协议和 mac 协议的效率，可为数据融合、时间同步和目 标定位等很多方面奠定基础，有利于节省传感器节点的能量来延长 网络的生存期。所以，拓扑控制是无线传感器网络研究的核心技术 之一。 2、路由协议 传统的网络路由协议设计一般将服务质量高放在第一位，能量高 效放在第二位考虑。但是由于无线传感器网络的节点能量有限，而 且传感器节点在数据传输中需要消耗大量的能量。因此，无线传感 器网络的这些特征所决定的讲究高能量效率的路由协议无法采用传 统的路由算法。目前研究人员正致力于开发新的能量效率高的路由 技术。 3、定位技术 位置信息是传感器节点采集数据中不可缺少的部分，没有位置信 息的监测消息通常毫无意义。确定事件发生的位置或采集数据的节 点位置是传感器网络最基本的功能之一。为了提供有效的位置信息， 随机部署的传感器节点必须能够在布置后确定自身位置。由于传感 器节点存在资源有限、随机部署、通信易受环境干扰甚至节点失效 等特点，定位机制必须满足自组织性、健壮性、能力高效、分布式 计算等要求。 4、网络安全 无线传感器网络作为任务型的网络，不仅要进行数据的传输，而 且要进行数据的采集和融合、任务的协同控制等。如何保证任务执 行的机密性、数据产生的可靠性、数据融合的高效性以及数据传输 的安全性，就成为无线传感器网络安全问题需要全面考虑的内容。 5、数据融合 由于无线传感器网络对目标的观察存在数据冗余，若这些冗余数 据不加任何处理就传送给观察者，将会带来巨大的网络流量，从而 带来急剧的能量消耗；另一方面，这种流量通常都是不均衡分布的， 靠近观察者的节点非常容易因快速的能量消耗而失效。因此在各节 点收集数据的过程中，即可进行数据的融合，在数据融合的过程中 也滤除了部分噪声，提高了信息的准确度。 南京航空航天大学硕士学位论文 7 6、数据管理 从数据存储的角度来看，无线传感器网络可被视为一种分布式数 据库。以数据库的方法在传感器网络中进行数据管理，可以将存储 在网络中的数据的逻辑视图与网络中的实现进行分离，使得传感器 网络的用户只需要关心数据查询的逻辑结构，无需关心实现细节。 虽然对网络所存储的数据进行抽象会在一定程度上影响执行效率， 但可以显著增强传感器网络的易用性。 7、嵌入式操作系统 传 感 器 节 点 本 质 上 是 一 个 微 型 的 嵌 入 式 系 统 ， 硬 件 资 源 非 常 有 限，这就要求操作系统能够高效地使用其硬件资源。同时，传感器 节点具有并发程度高的特点，因此操作系统要能有效地满足发生频 繁 、 并 发 程 度 高 、 执 行 过 程 短 的 逻 辑 控 制 流 程 ， 目 前 berkeley 的 tinyos 采用基于组件的架构和基于事件的驱动来满足上述要求。 1 . 5本文的研究内容及结构安排 网络拓扑控制、定位问题、网络通信协议、网络安全是无线传 感器网络研究的几个基本问题。其中，节点定位问题是传感器网络 进行目标识别、监控等众多应用的前提，也是传感器网络研究中的 基础性问题和热点问题之一。本文就传感器网络的定位算法展开深 入探讨，论文的研究内容安排如下： 第一章主要介绍了无线传感器网络的研究背景、体系结构、特 点和关键技术。 第二章主要介绍了无线传感器网络节点定位的基本概念、分类 和评价标准，对当前几种典型的定位算法进行了分析比较。 第三章详细阐述了基于测距的定位算法。对锚节点密集和稀疏的 网络分别进行讨论，在锚节点密集的情况下，依据三个锚节点共线 时定位的误差最大，而三个锚节点所构成的三角形是等边三角形时 则定位的误差最小的原理，提出了角度权值定位算法；在锚节点稀 疏 的 情 况 下 ， 对d v - distance定 位 算 法 进 行 改 进 ， 提 出 了 改 进 的 d v - distance 误差修正定位算法。仿真实验表明，这两个算法在一定 程度上提高了节点的定位精度。 第四章详细探讨了基于移动锚节点的定位问题。讨论了锚节点 在网络监控区域的移动路径问题，以及将 b o u n d i n g - b o x定位算法应 无线传感器网络定位算法的研究及应用 8 用到移动锚节点定位中，并在此基础上提出了一种改进的基于移动 锚节点的 b o u n d i n g - b o x定位算法。该算法有效的减少了节点的定位 误差。 第五章总结全文，并展望未来的研究工作。 南京航空航天大学硕士学位论文 9 第二章 无线传感器网络的节点定位 2 . 1基本概念 在传感器网络节点定位技术中，根据节点是否已知自身的位置， 把传感器节点可以分为两类：锚节点和未知节点。锚节点在网络中 所占比例很小，可以通过携带 gps 定位系统或者预先在指定位置部 署等手段获得自身的精确位置。锚节点在定位技术中作为参考点， 以确定未知节点的实际位置。未知节点通过定位技术，根据锚节点 的位置信息来确定自身位置。 以下是在节点定位中常用的基本术语： 邻居节点：传感器节点通信半径之内的所有其他节点，也就是一 跳距离以内的所有节点，称为该节点的邻居节点； 跳数：两个节点之间一次通信所需要进行传递的次数，称为两个 节点之间的跳数； 锚节点：无线传感器网络中，通过携带 gps 定位系统或者根据预 先指定等手段获得自身的精确位置的传感器节点，称为锚节点； 未知节点：传感器网络中，位置信息有待确定的节点，称为未知 节点； rssi：接收信号强度指示，节点接收到无线信号的强度大小； 到达时间(toa)： 信号从一个节点传到另一个节点所需要的时间， 成为信号的到达时间； 到达角度(aoa)：节点接收到的信号相对于自身轴线的角度称为 信号相对接收点的到达角度； 到达时间差(tdoa)：接收节点收到两种信号到达的时间差，称 为到达时间差。 2 . 2无线传感器网络定位算法的分类 尽管至今无线传感器网络定位算法的分类没有一个统一的标准， 而且每一种分类并不一定适用于所有的定位系统和算法，但是这些 分类方法在一定程度上刻画了不同定位系统和算法的特点，以 下介 无线传感器网络定位算法的研究及应用 10 绍几种常用的分类方法： 2 . 2 . 1基于测距技术的定位和无需测距技术的定位 28 基于测距技术（range- based）的定位首先通过常用的测距方法 测 量 得 到 节 点 间 点 到 点 的 距 离 或 角 度 信 息 ， 然 后 使 用 三 边 测 量 法 （ trilateration ） 、 三 角 测 量 法 （ triangulation ） 或 最 大 似 然 估 计 (multilateration)法计算出节点的位置；无需测距技术（range- free） 的定位则不需要知道节点间的距离和角度信息，仅依靠网络连通性 等信息实现。 基于测距技术的定位常用的测距方法有 rssi，toa，tdoa 和 aoa。这些方法都需要额外的硬件支持，因此测距技术需要较大的 成本开销。除此之外，基于测距技术的定位机制还使用各种算法来 减小测距误差对定位的影响，包括多次测量，循环定位求精，这些 都要产生大量计算和通信开销。所以，基于测距技术的定位机制虽 然在定位精度上有可取之处，但并不适用于低功耗、低成本的应用 领域。对于无需测距技术的定位，由于其功耗和成本较低，虽然其 定位的精度不高，但是这足以满足一些应用，因此无需测距技术的 定位方案也广泛被使用。 dv- hop、凸规划和 mds- map 等算法就是典型的无需测距技术 的定位算法，其中 mds- map 还可以在基于测距技术条件下实现更 精确的定位。 2 . 2 . 2绝对定位与相对定位 20 绝对定位的定位结果是一个标准的坐标位置，如经纬度。而相对 定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系 统。绝对定位可为网络提供唯一的命名空间，受节点移动性影响较 小，有更广泛的应用领域。但研究发现，在相对定位的基础上也能 够实现部分路由协议，尤其是基于地理位置的路由，而且相对定位 不需要锚节点。 大多数定位系统和算法都可以实现绝对定位，典型的相对定位系 统和算法有 spa (self- positioning algorithm)，lps (local positioning system)，spoton，而 mds- map 定位算法可以根据网络配置的不同 分别实现两种定位。 2 . 2 . 3集中式计算与分布式计算 9 南京航空航天大学硕士学位论文 11 集中式计算是指把所需信息传送到某个中心节点，如服务器或 网关节点，并由该节点进行节点定位计算的方式；分布式计算是指 依赖节点间的信息交换和协调，由节点自行计算的定位方式。 集中式计算的优点在于从全局角度统筹规划，计算量和存储量几 乎没有限制，可以获得相对精确的位置估算。它的缺点是与中心节 点位置较近的节点会因为通信开销大而过早地消耗完电能，导致整 个网络与中心节点信息交流的中断，无法实时定位等。分布式计算 则在各节点进行，整个网络的流量与计算量分布能够保持一个较为 均衡的水平。 集中式定位算法包括凸规划， mds- map 等。 n- hop multilateration primitive 定位算法可以根据应用需求采用两种不同的计算模式。 2 . 2 . 4粗粒度与细粒度 21 依据定位所需信息的粒度可将定位算法和系统分为两类：根据信 号强度或时间、信号模式匹配等来度量与锚节点距离的称为细粒度 定位技术；根据与锚节点的接近度来度量的称为粗粒度定位技术。 一般而言，细粒度的定位技术大部分是基于测距技术的，细粒度又 可细分为基于距离和基于方向性测量两类。粗粒度一般是无需测距 的，其原理是利用某种物理现象来感应是否有目标接近一个已知的 位置。 radiocamera 定位系统中的信号模式匹配专利技术属于细粒度定 位。active badge、凸规划、xeror 的 parc tab 系统、佐治亚理工学 院的 smart floor 等则属于粗粒度定位。 2 . 2 . 5三角测量、场景分析和接近度定位 29 定位技术还可以分为三角测量、场景分析和接近度定位 3 类， 其中三角测量和接近度定位与粗、细粒度定位相似。而场景分析定 位是根据场景特点来推断目标位置。通常被观测的场景都有易于获 得、表示和对比的特点，如信号强度和图像。场景分析的优点在于 无需定位目标参与，有利于节能并具有一定的保密性；它的缺点在 于需要事先预制所需的场景数据集，而且当场景发生变化时，必须 重建该数据集。radar 系统 (基于信号强度分析)和 mit 的 smart rooms (基于视频图像)就是典型的场景分析定位系统。 无线传感器网络定位算法的研究及应用 12 2 . 3无线传感器网络定位算法的评价标准 无线传感器网络定位系统和算法的性能直接影响着其可用性和 应用的范围，需要满足自组织性、健壮性、能量有效性等需求。如 何评价它们是一个需要深入研究的问题。下面讨论几个常用的评价 定位系统和算法的标准。 1、 定位精度 定 位 精 度 是 无 线 传 感 器 网 络 定 位 系 统 和 算 法 的 首 要 的 评 价 标 准，它一般是用定位误差与节点无线射程的比值表示。例如，当节 点的通信半径为 r 时，定位精度为 0.3r，则表示定位误差与 r 的比 值为 0.3。有的定位系统将二维网络部署区域划分为网格，其定位结 果的精度也就是网格的大小。 2、锚节点密度 锚节点的多少直接影响着无线传感器网络节点的定位精度，同 时也决定着定位算法的选择。对于锚节点，可以通过人工部署和安 装 gps 两种方式确定其位置。人工部署锚节点的方式不仅受网络部 署环境的限制，还严重制约着网络和应用的可扩展性。而使用gps 定位，锚节点的费用会比普通节点高两个数量级，这意味着即使仅 有 10%的节点是锚节点，整个网络的价格将增加十倍。因此锚节点 密度也是评价定位系统和算法性能的重要指标之一。 3、功耗 功耗问题是无线传感器网络的设计和实现所必需考虑的问题。由 于传感器节点电池能量有限，因此在保证定位精度前提下，必须尽 可能减少定位过程中的能量消耗，与能量消耗密切相关的因素主要 有：计算量、通信开销、存储开销、时间复杂性等。 4、容错性和鲁棒性 通常，定位系统和算法都需要比较理想的无线通信环境和可靠的 网络节点设备。但在真实应用场合中常会有诸如以下的问题：网络 节点由于周围环境或自身原因（如电池耗尽、物理损伤）而出现失 效的问题；外界影响和节点硬件精度限制造成节点间点到点的距离 或角度测量误差增大的问题；外界环境中存在严重的多径传播、衰 减、非视距、通信盲点等问题。由于环境、能耗和其它原因，人工 维护或替换传感器节点或使用其他高精度的测量手段常常是十分困 难或不可行的。因此，定位系统和算法的软、硬件必须具有很强的 南京航空航天大学硕士学位论文 13 容错性和鲁棒性，能够通过自动调整或重构纠正错误、适应环境、 减小各种误差的影响，不会因为个别节点的实效而导致其他节点出 现无法定位或定位误差很大的情况。 5、覆盖率 定 位 覆 盖 率 指 能 够 实 现 定 位 的 未 知 节 点 的 数 目 与 未 知 节 点 总 数 的比例。尽管无线传感器网络大多是密集部署的，但总会有一些不 可达或连通度极低的未知节点存在，除了不可达节点，实现尽可能 多的未知节点的精确定位也是无线传感器网络定位算法和系统的追 求目标之一。 6、代价 传感器网络定位系统和算法的代价主要从时间代价、空间代价和 资金代价三个方面来考虑。时间代价是指一个系统从安装、配置到 定位完成共需花费的时间。空间代价是指一个定位系统或算法所需 的基础设施和网络节点的数量、硬件尺寸等。资金代价是指一种定 位系统或算法的基础设施、节点设备等的总费用。 上述 6 个性能指标不仅是评价无线传感器网络定位系统和算法 的标准，也是其设计和实现的优化目标。为了达到这些目标的优化， 有大量的研究工作需要完成。同时，这些性能指标是相互关联的， 必须根据应用的具体需求做出权衡，以选择和设计合适的定位技术。 2 . 4无线传感器网络典型的定位算法 2 . 4 . 1质心定位算法 21 质心定位算法是由南加州大学的 nirupama bulusu 等学者提出的 一种仅基于网络连通性的室外定位算法。该算法是一种无需测距的 定位算法，仅能实现粗粒度定位，需要较高的锚节点密度，但它非 常简单，完全基于网络连通性，无需锚节点和未知节点间协调。 其核心思想是：未知节点以所有在通信范围内的锚节点的几何质 心作为自己的位置估计。具体过程为：锚节点每隔一段时间向邻居 节点广播一个信号，信号中包含锚节点自身 id 和位置信息。当未知 节点在一段时间内接收到来自不同锚节点的信号数量超过某一个预 设门限后，该节点就确定自身位置为这些锚节点所组成的多边形的 质心。多边形的几何中心称为质心，多边形顶点坐标的平均值就是 质心节点坐标。 假设这些锚节点的坐标分别为 (x1,y1) 、 (x2,y2) 无线传感器网络定位算法的研究及应用 14 (xk,yk) ，则可以根据下式计算出未知节点的坐标： (x,y) = + + k yy k xx kk . . 11 , ( 2 - 1 ) 实验显示，大约有 90%未知节点定位精度小于锚节点间距的 1/3。 2 . 4 . 2凸规划定位算法 30 凸规划定位算法是由加州大学伯克利分校的 doherty 等人提出的 一种完全基于网络连通性诱导约束的定位算法。该算法将节点间点 到点的通信连接视为节点位置的几何约束，例如，若节点的通信半 径为 20m， 那么两个节点进行通信所蕴涵的几何约束就是这两个节点 的距离必定小于等于 20m， 这样产生一系列相邻的约束条件就蕴涵着 节点的位置信息。将这些约束条件组合起来，就可以得到此未知节 点可能存在的区域。 图 2.1 凸规划示意图 算法把整个网络模型化为一个凸集，从而将节点定位问题转化 为凸约束优化问题，然后使用线性矩阵不等式、半判定规划或线性 规划方法得到一个全局优化的解决方案，确定节点位置。同时也给 出了一种计算未知节点有可能存在的矩形区域的方法。如图 2.1，根 据未知节点与锚节点之间的通信连接和节点无线通信半径，可以估 算出节点可能存在的区域，并得到相应矩形区域，然后以矩形的质 心作为未知节点的位置。 凸规划是一种集中式定位算法，锚节点比例为10%的情况下， 定位误差约等于节点的通信半径。为了高效工作，锚节点需要 被部 署在网络的边缘，否则外围节点的位置估算会向网络中心偏移。 2 . 4 . 3 aps(ad- hoc positioning system) 332331、 a b c m 南京航空航天大学硕士学位论文 15 美国路特葛斯大学的 dragos niculescu等人利用距离矢量路由和 gps 定位的原理提出了一系列分布式定位算法，合称为 aps。它包 括 6 种定位算法：dv- hop，dv- distance，euclidean，dv- coordinate， dv- bearing 和 dv- radial。 1、dv- hop 定位算法 3332、 dv- hop 算法的基本思想是将未知节点到锚节点之间的距离用网 络平均每跳距离和两者之间的跳数乘积表示。该算法主要包括三个 阶段。首先通过使用距离矢量交换协议，使网络中所有的节点获得 该节点距锚节点之间的跳数。第二个阶段，各个锚节点在获得网络 中其他锚节点的位置信息和相距的跳数之后，就可以计算出网络的 平均每跳距离，然后将该距离以可控洪泛方式在网络中传播，网络 中的每个节点仅接受获得的第一个距离值，这样确保绝大多数节点 可从最近的锚节点接收到平均每跳距离。第三个阶段，各个未知节 点可以通过平均每跳距离和其距离锚节点的跳数计算出该节点与锚 节点之间的距离。当未知节点获得与 3 个或更多锚节点的距离时， 则可利用三边测量定位法进行定位。 如图 2.2 所示，已知锚节点 l1 与 l2、l3 之间的距离和跳数。 l2 计算得到的平均每跳距离为（30+50）/（2+5）=11.43。假设 l2 是距离未知节点 a 最近的锚节点， 则节点 a 从 l2 获得平均每跳距离， 则节点 a 与 3 个锚节点之间的距离分别为 l1： 311.43， l2： 211.43， l3：311.43，然后使用三边测量法确定未知节点 a 的位置。 图 2.2 d v - h o p定位算法示意图 dv- hop 算法在网络平均连通度为 10，锚节点比例