【毕业学位论文】（Word原稿）无线传感器网络基于移动信标优化路径的定位算法研究-控制理论与控制工程

广东工业大学硕士学位论文 ( 工 学 硕 士 ) 基于移动 信标 优化路径的 定位算法研究 二零 一 零年 五 月 分类号： 学校代号： 11845 密级： 学号： 2110704294 广东工业大学硕士学位论文 （ 工 学 硕 士 ） 基于移动 信标 优化路径的 定位算法研究 指导教师 姓名、职称 ： 教授 企业 导师 姓名、职称 ： 无 专业 或 领域 名 称 ： 控制理论与控制工程 学 生 所 属 学 院 ： 自动化学院 论 文 答 辩 日 期 ： 2010 年 5 月 11845 o.:2110704294 A s 010 510006摘 要 I 摘 要 无线传感器节点定位技术是无线传感器网络 的 关键技术之一， 是无线传感器网络大多数应用的基础。 无线传感器网络应用的 大多数领域 , 如：目标监 测与跟踪、路由 位置信息的获取 等 ，都需要知道节点的位置信息 。 为此我们需要研究更为有效的定位算法，降低定位成本，提高定位精度。 针对这种情况， 本论文 对 基于 移动 信标 优化路径的无线 传感器网络节点 算法进行了研究 ，该 定位算法 能够实现 节点的高效率定位。文章 在 位算法中引入移动信标节点 ， 并研究 信标节点的动态选择算法及 移动路径优化算法 。 本文的 主要完成的工作 有： 1、 分析 归纳常用的 无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制 ，研究利用移动信标的信息来进行定位计算 。 2、提出基于 移动 信标 改进的 位算法 ， 该算法在 位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标， 研究平均跳距离的加权算法和信标节点的动态选择算法， 降低定位的成本和布网的复杂度 ， 提高 节点定位 的精度和效率。 3、结合 基于 移动 信标 改进的 位算法 ，提出了面向无线传感器网络 的移动 信标 的路径规划方法，把图论引入 信标 移动路径规划 ， 获取针对所处网络连通状况的优化 信标 移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高 算法 的效率 。 最后 在 仿真环境下，仿真基于移动 信标 的定位算法， 建立包括 移动智能节点 和 普通节点的仿真模型，通过定位过程的通信和数据处理计算未知节点的位置，仿真表明 ，基于 移动 信标 优化路径的定位算法 既改善了定位的精度，又减少了定位 算法 的 通信开销 ， 提高无线 传感器网络节点 定位效率 。 关键词： 无线 传感器网络； 移动 信标 ； 优化路径 ； ； 智能节点 is of Its of of to of So we to In on of We 1. on of on 2. on a to in to a its We to of of 3. on we is by of we of of of of we + 广东工业大学硕士学位论文 IV by in s of on of of ； 录 V 目 录 摘 要 . 录 . V . 一章 绪 论 . 1 论文的研究背景及意义 . 1 究背景与意义 . 1 题来源 . 3 内外研究现状 . 3 论文的主要研究内容与结构 . 5 第二章 传感器网络常用节点定位算法相关研究 . 7 线传感器网络基于信标节点的定位算法 . 7 关工作 . 7 于信标定位算法的优点 . 9 线传感器网络常用的定位方式的实现 . 10 大似然估计法 . 10 边测量定位法 . 11 角测量定位法 . 12 用的节点定位算法 . 13 用的 点定位算法 . 13 用的 点定位算法 . 16 章小结 . 18 第三章 基于移动信标的节点定位算法 . 19 线传感器网络基于移动信标改进的 位算法 . 19 位算法 . 20 动信标节点定位算法 . 23 广东工业大学硕士学位论文 仿真分析 . 26 于移动信标动态选择改进 位算法 . 28 位算法平均跳距离计算误差来源分析 . 29 于移动信标动态选择的改进型 位算法过程 . 31 真分析 . 34 章小结 . 35 第四章 无线传感器 网络移动信标的路径优化 . 36 线传感器网络移动信标的移动模型分析 . 36 机移动 型 . 36 斯马尔可夫移动 型 . 37 线移动模型 . 38 向无线传感器网络节点定位的移动信标的路径优化 . 38 于图论的信标移动路径规划方法 . 39 向传感器网络的移动信标路径规划的仿真实现 . 40 章小结 . 42 第五章 基于移动信标优化路径定位算法的仿真实 现 . 43 真实验工具和实验方法简述 . 43 仿真实验平台介绍 . 43 位算法性能评价指标及分析方法 . 44 于移动信标的传感器网络定位算法的设计 . 45 线传感器网络仿真程序模型及程序设计 . 46 位过程仿真程序设计 . 51 于移动信标优化路径的定位算法性能分析 . 52 章小结 . 55 结论与展望 . 56 参 考 文 献 . 57 攻读学位期间发表的学术论文 . 60 攻读学位期间参加的科研项目 . 61 独创性声明 . 62 致 谢 . 63 . . V . . 1 . 1 . 1 . 3 . 3 . 5 . 7 . 7 . 7 . 9 . 10 . 10 . 11 . 12 . 13 . 13 . 16 . 18 . 19 . 19 . 20 . 23 . 26 . 28 . 29 of . 31 . 34 . 35 广东工业大学硕士学位论文 . 36 . 36 . 36 . 37 . 38 . 38 . 39 of . 40 . 42 . 43 . 43 . 43 . 44 . 45 . 46 of . 51 of . 52 . 55 . 56 . 57 . 60 . 61 . 62 . 63 第一章 绪 论 1 第一章 绪 论 论文的研究背景 及 意义 究背景 与意义 无 线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息获取和处理模式 1 。 无线传感器网络 (由部署在监测区内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域内感知对象的信息，并传送给观察者 2 。 传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络应用中，通常将节点撒播在很广的区域里，网络中大部分的节点的位置是未知的，事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才可能获取 到网络中事件的发生位置和信息来源位置 。 因此， 定位是无线传感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件及信息发生的具体位置 3 。节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。 此外，在设计路由协议时利用 节点位置信息还可以提高路由效率，为网络提供命名空间，向 网络 部署者报告 网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置 4 。因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向 。 传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自主确定位置被认为是其基本能力和系统的基本服务之一。对于 说，人工广东工业大学硕士学位论文 2 部署或为所有网络节点配置 置都会受到成本、功耗、拓展性等问题的限制，因此，寻求 身定位机制成为许多研究机构和学者共同探讨的问题 4 。 无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机制分为：基于测距的 (位和距离无关的 (位方法 5 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点 间距离关联关系计算目标节点位置。 量距离的具体的方法有6 ， 7 ， 8 和 9 等。 法能够实现精确定位，但由于需要在节点中加入 其它附加的测距的硬件设备，在实际应用中所需的成本较高。而 位算法由于降低了对节点硬件的要求，引起了更多的关注，典型算法有 0 算法 ,基于 1 算法 ,基于连通性的定位算法 12 等。 目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法，都需要移动节点至少获得 3 个或者 3 个以上信标节点提供的坐标和距离 13 。另一种思想则是使信标或者 信标 运动起来，通过带有 已知位置的移动 信标按某一规划好的路径或运动模型遍历未知节点的区域，并发送定位信号，其它节点获取这些信号来进行定位计算。 动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法 14 ，包括待测节点的运动和信标 节点的运动。当然从理论上讲，完全可以借鉴静态已有的成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时性要求较高，通常的改进方法是加入对节点运动的预测估计 15 ，或是使定位算法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。 虽然节点的移动性使定位过程复杂化，但是利用节点的移动性可提高定位精度，减少定位代价。在 的研究中，网络中有 2 个固定的 信标 向全网传送坐标信息，其余处 于运动状态的节点根据接收到的信号强度进行自身定位16 。 国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法第一章 绪 论 3 17 。但这些算法普遍存在以下局限 18 ： 依赖特殊硬件的支持； 需要特殊的网络拓扑结构。而在无线传感器 网络中引入移动节点，可以增强其功能。如文献 19 通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度分布不均匀的不足。文献 20 提到利用移动参考节点和 收信号强度指示 )方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得 术在实际应用中仍然存在困难。尤其是 节点对能耗，体积等要求严格时，更多的时候并不能应用这种基于测距的定位技术。 免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络连通情况或者 位等思想提出的一种分布式定位方法，无需测距，这无疑降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差，当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差，精度也相应的降低 21 。因此如何提高这种免测距定位算法的精度也成为 了一个研究的热点方向。 题来源 本课题来源于国家自然科学基金资助项目（编号： 60673132）；广东省自然科学基金重点项目（编号： 07117421）。 内外研究现状 基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖于信标节点的密度，网络的联通性。而信标节点的造价数倍甚至十几倍于普通节点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游移动的节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效率。所以移动信标的定位算法近来成为新的研究热点 ，国内外许多学者进行了许多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规划。为此，国内外有许多学者把移动信标与经典的质心定位算法、 位算法及 位算法等相结合来改进这些定位算法。而质心定位算法及广东工业大学硕士学位论文 4 位算法因为无需测距有着更多的优势也得到更多的研究。 无需测距（ 定位算法不需要直接测量距离信息，而是根据网络的连通性确定网络中节点之间的跳数，同时根据已知位置参考节点的位置等 信息估计每一跳的大致距离，然后估出节点在网络中的位置 22 。典型的无需测距的定位算法有 位算法， 位算法、质心定位算法、 位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成 。 通过移动 信标 ，或者说移动信标来对整个网络的未知节点进行定位的方法是最来兴起的一种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的飞行器上，并且该节点装有 其他定位装置，这样就构造 了移动 信标 23 。它可以在移动的过程中实时获得其当前的位置信息。 通过移动 信标 来定位的主要思想是：移动 信标 在“感兴趣的区域内（ of 称 24 移动的过程中，不断的广播包含其当前位置信息的分组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者三个以上的与其距离为 R 的 位置信息时，就可以利用三边测量法或极大似然估计法 17 计算该未知节点的位置。 国内外对于移动 信标 的定位方法及 信标 的移动路径的规划研究处于起步阶段，相关的文献并不多，提出的算法也不够成熟，文献 25 和 26 提出的定位方法只需要一个可 以移动的 信标 ，其中文 献 25 利用 距技术和质心法来计算待定位节点位置，文 献 26 不需要复杂的测