【完美升级版】毕业论文设计_无线传感器网络基于移动信标优化路径的定位算法研究

(此文档为word格式，下载后您可任意编辑修改！)

广东工业大学硕士学位论文

(工学硕士)

基于移动信标优化路径的

定位算法研究

Classified Index: School Code: 11845

A Dissertation for Master’s Degree of

Guangdong University of Technology

（Master of Engineering Science）

Research on Localization Algorithm Based on Mobile

Beacon with Optimal path

Candidate: Xie Xiaosong

Supervisor: Prof. Cheng Lianglun

May 2010

Faculty of Automation

Guangdong University of Technology

Guangzhou, Guangdong, P.R.China, 510006

摘要

无线传感器节点定位技术是无线传感器网络的关键技术之一，是无线传感器网络大多数应用的基础。无线传感器网络应用的大多数领域, 如：目标监测与跟踪、路由位置信息的获取等，都需要知道节点的位置信息。为此我们需要研究更为有效的定位算法，降低定位成本，提高定位精度。

针对这种情况，本论文对基于移动信标优化路径的无线传感器网络节点算法进行了研究，该定位算法能够实现节点的高效率定位。文章在DV-Hop定位算法中引入移动信标节点，并研究信标节点的动态选择算法及移动路径优化算法。本文的主要完成的工作有：

1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。

2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，研究平均跳距离的加权算法和信标节点的动态选择算法，降低定位的成本和布网的复杂度，提高节点定位的精度和效率。

3、结合基于移动信标改进的DV-Hop定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处

网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。

最后在OMNeT++仿真环境下，仿真基于移动信标的定位算法，建立包括移动智能节点和普通节点的仿真模型，通过定位过程的通信和数据处理计算未知节点的位置，仿真表明，基于移动信标优化路径的定位算法既改善了定位的精度，又减少了定位算法的通信开销，提高无线传感器网络节点定位效率。

关键词：无线传感器网络；移动信标；优化路径；OMNeT++；智能节点

ABSTRACT

Wireless sensor node localization is one of the key technologies for wireless sensor networks. It’s the foundation of most wireless sensor network applications, such as: target surveillance and tracking, routing and other location information acquiring, all of these need to know the location information of the nodes. So we need more effective localization algorithm to reduce the cost and increase the precision.

In response, the paper research the nodes localization algorithm for wireless sensor network base on mobile beacon with optimal path. This algorithm can achieve high efficiency of positioning nodes. We introduced mobile beacon node into DV-Hop localization algorithm, and study the dynamic beacon node selection algorithm and moving path optimal algorithm. These major works are:

1. Summarizes common range-free localization algorithm and the algorithms base on beacon, study the positioning mechanism of localization algorithms base on beacon.

2.Improving DV-Hop localization algorithm based on mobile beacon, the algorithm use a mobile beacon node to move in the network according to a predetermined path and broadcast it’s location information that create virtual beacons. We study the weighted average hop distance algorithm and the dynamic

beacon node selection algorithm to reduce localization costs and complexity of distribution networks and improve accuracy and efficiency of node localization.

3. Combined with the improved DV-Hop localization algorithm based on mobile beacon, we proposed mobile beacon path planning method for wireless sensor networks. Graph theory is introduced into the mobile path planning; by acquiring connectivity conditions of the network we optimize the path of mobile beacon. These make increase of positioning accuracy of positioning algorithm and reduce communication costs, improve efficiency of the algorithm.

Finally, we simulate mobile beacon base localization algorithm in OMNeT + + simulation environment by modeling mobile intelligent nodes and ordinary nodes in the network. The network computes the unknown node’s location through the positioning process of communication and data processing. The simulation results show that the algorithm base on mobile beacon with optimal path not only improves the positioning accuracy but also reduce the communication overhead of locatingm, these improve the efficiency of wireless sensor nodes localization.

Key words: WSN；Mobile anchor；Optimal path；OMNeT++；Smart node

目录

摘要.............................................................................................................................. I ABSTRACT ............................................................................................................... III 目录............................................................................................................................. V CONTENTS ............................................................................................................ VIII 第一章绪论 (1)

1.1 本论文的研究背景及意义 (1)

1.1.1 研究背景与意义 (1)

1.1.2 课题来源 (4)

1.2 国内外研究现状 (4)

1.3 本论文的主要研究内容与结构 (7)

第二章传感器网络常用节点定位算法相关研究 (10)

2.1无线传感器网络基于信标节点的定位算法 (10)

2.1.1相关工作 (10)

2.1.2基于信标定位算法的优点 (13)

2.2无线传感器网络常用的定位方式的实现 (15)

2.2.1极大似然估计法 (15)

2.2.2三边测量定位法 (16)

2.2.3三角测量定位法 (17)

2.3常用的节点定位算法 (18)

2.3.1 常用的Range-base节点定位算法 (18)

2.3.2常用的Range-free节点定位算法 (22)

2.4本章小结 (26)

第三章基于移动信标的节点定位算法 (27)

3.1 无线传感器网络基于移动信标改进的DV-Hop定位算法 (27)

3.1.1DV-Hop定位算法 (29)

3.1.2移动信标节点定位算法 (33)

3.1.3 仿真分析 (37)

3.2基于移动信标动态选择改进DV-Hop定位算法 (40)

3.2.1 DV-Hop定位算法平均跳距离计算误差来源分析 (41)

3.2.2基于移动信标动态选择的改进型DV-Hop定位算法过程 (43)

3.2.3仿真分析 (48)

3.3 本章小结 (50)

第四章无线传感器网络移动信标的路径优化 (51)

4.1无线传感器网络移动信标的移动模型分析 (51)

4.1.1随机移动RWP(Random Way Point)模型 (52)

4.1.2高斯马尔可夫移动Gauss-Markov模型 (53)

4.1.3 螺线移动模型 (54)

4.2面向无线传感器网络节点定位的移动信标的路径优化 (54)

4.2.1基于图论的信标移动路径规划方法 (55)

4.2.2面向传感器网络的移动信标路径规划的仿真实现 (57)

4.3 本章小结 (59)

第五章基于移动信标优化路径定位算法的仿真实现 (60)

5.1仿真实验工具和实验方法简述 (60)

5.1.1 OMNeT++仿真实验平台介绍 (60)

5.1.2定位算法性能评价指标及分析方法 (61)

5.2基于移动信标的传感器网络定位算法的设计 (63)

5.2.1无线传感器网络仿真程序模型及程序设计 (65)

5.2.2定位过程仿真程序设计 (71)

5.3基于移动信标优化路径的定位算法性能分析 (73)

5.4 本章小结 (76)

结论与展望 (78)

参考文献 (80)

攻读学位期间发表的学术论文 (83)

攻读学位期间参加的科研项目 (84)

独创性声明 (85)

致谢 (86)

CONTENTS

ABSTRACT(Chinese) .................................................................................................. I ABSTRACT(English) ............................................................................................... III CONTENTS(Chinese) ................................................................................................ V CONTENTS(English) ............................................................................................ VIII Chapter 1 Introduction (1)

1.1 Research Background and Meaning of This Subject (1)

1.1.1 Research Background and Meaning (1)

1.1.2 Source of This Subject (4)

1.2 Domestic and Foreign Research Status (4)

1.3 Main Content and Structure of This Subject (7)

Chapter 2 Common Nodes Localization for Sensor Network (10)

2.1 Localization Algorithm Base on Beacon (10)

2.1.1 Realative work (10)

2.1.2The Advantage of Localization Algorithm Base on Beacon (13)

2.2 Implement of Common Localization Ways (15)

2.2.1 Maximum likelihood estimation (15)

2.2.2 Trilateration Method Localization (16)

2.2.3 Triangulation Method Localization (17)

2.3 Common Nodes Localization Algorithm (18)

2.3.1 Common Range-base Nodes Localization Algorithm (18)

2.3.2 Common Range-free Nodes Localization Algorithm (22)

2.4 Summary of This Chapter (26)

Chapter 3 Localization Algorithm based on Mobile Beacon (27)

3.1 Improving DV-Hop Algorithm base on Mobile Beacon (27)

3.1.1 DV-Hop Localization Algorithm (29)

3.1.2 Nodes Localization Algorithm base on Mobile Beacon (33)

3.1.3 Simulation Result (37)

3.2 Improving DV-Hop Algorithm base on Mobile Beacon Dynamic Selection 40

3.2.1 Analysis the Error Resource of DV-Hop Averager Hop Distance (41)

3.2.2 The Process of the Improving Localization Algorithm (43)

3.2.3 Simulation Result (48)

3.3 Summary of This Chapter (50)

Chapter 4 Mobile Beacon Moving Path Optimization (51)

4.1 Analysis the Moving Model of Mobile Beacon (51)

4.1.1 RWP(Random Way Point) Moving Model (52)

4.1.2 Gauss-Markov Moving Model (53)

4.1.3 Spire Moving Model (54)

4.2 Mobile Beacon Moving Path Optimization for WSNs (54)

4.2.1 Mobile Beacon Path Planning base on Graph Theory (55)

4.2.2 Simulation of the Mobile Beacon Path Planning (57)

4.3 Summary of This Chapter (59)

Chapter 5 Simulation of Localzaition Algorithm base on Mobile Beacon (60)

5.1 Introduction of Simulation Tools and Environment (60)

5.1.1 Introduction of OMNeT++ (60)

5.1.2 Localization Algorithm Performance Evaluation and Analysis (61)

5.2 Localization Algorithm Design base on Mobile Beacon (63)

5.2.1 Programming and Modeling Localization Algorithm (65)

5.2.2 Programming the Process of the Localization Algorithm (71)

5.3 Performance Evaluation and Analysis of the Localization Algrithm base on Optimize Path (73)

5.4 Summary of This Chapter (76)

Conclusion and Prospect (78)

References (80)

Published Papers (83)

Participant Projects (84)

Original Creative Statement (85)

Acknowledgements (86)

第一章绪论

1.1 本论文的研究背景及意义

1.1.1 研究背景与意义

无线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息获取和处理模式错误！未找到引用源。。

无线传感器网络(Wireless Sensor Networks，WSN)是由部署在监测区内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域内感知对象的信息，并传送给观察者[1] 。

传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络应用中，通常将节点撒播在很广的区域里，网络中大部分的节点的位置是未知的，事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才可能获取到网络中事件的发生位置和信息来源位置。因此，定位是无线传感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件及信息发生的具体位置[2]。节点必须明确自身位置才能

详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。此外，在设计路由协议时利用节点位置信息还可以提高路由效率，为网络提供命名空间，向网络部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置[2]。因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向。

传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自主确定位置被认为是其基本能力和系统的基本服务之一。对于WSN来说，人工部署或为所有网络节点配置GPS装置都会受到成本、功耗、拓展性等问题的限制，因此，寻求WSN 自身定位机制成为许多研究机构和学者共同探讨的问题[2] 。

无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机制分为：基于测距的(range-based)定位和距离无关的(range-free)定位方法[2] 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置。Range-based算法通过测量相邻节点间的实际距离或方位进行定位，测量距离的具体的方法有Time of Arrival(TOA) [3] ，Time Difference of Arrival(TDOA)[4]，Radio Signal Strength(RSSI)[5]和Angle of Arrival(AOA)[5]等。

Range-based算法能够实现精确定位，但由于需要在节点中加入GPS或其它附加的测距的硬件设备，在实际应用中所需的成本较高。而Range-free定位

算法由于降低了对节点硬件的要求，引起了更多的关注，典型算法有DV-Hop[6] 算法,基于RSSI的DV-Hop[6] 算法,基于连通性的定位算法[6]等。

目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法，都需要移动节点至少获得3个或者3个以上信标节点提供的坐标和距离[6] 。另一种思想则是使信标或者信标运动起来，通过带有GPS的已知位置的移动信标按某一规划好的路径或运动模型遍历未知节点的区域，并发送定位信号，其它节点获取这些信号来进行定位计算。

动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法[7]，包括待测节点的运动和信标节点的运动。当然从理论上讲，完全可以借鉴静态已有的成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时性要求较高，通常的改进方法是加入对节点运动的预测估计[7] ，或是使定位算法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。

虽然节点的移动性使定位过程复杂化，但是利用节点的移动性可提高定位精度，减少定位代价。在Bergamo等的研究中，网络中有2个固定的信标向全网传送坐标信息，其余处于运动状态的节点根据接收到的信号强度进行自身定位[7]。

国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法[7] 。但这些算法普遍存在以下局限[8]：①依赖特殊硬件的支持；②需要特殊

的网络拓扑结构。而在无线传感器网络中引入移动节点，可以增强其功能。如文献[9] 通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度分布不均匀的不足。文献[9] 提到利用移动参考节点和RSSI(接收信号强度指示)方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得RSSI技术在实际应用中仍然存在困难。尤其是节点对能耗，体积等要求严格时，更多的时候并不能应用这种基于测距的定位技术。

免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络连通情况或者GPS定位等思想提出的一种分布式定位方法，无需测距，这无疑降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差，当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差，精度也相应的降低[10] 。因此如何提高这种免测距定位算法的精度也成为了一个研究的热点方向。

1.1.2 课题来源

1.2 国内外研究现状

基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖于信标节点的密度，网络的联通性。而信标节点的造价数倍甚至十几倍于普通节点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游移动的节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效率。所以移动信标的定位算法近来成为新的研究热点，国内外许多学

者进行了许多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规划。为此，国内外有许多学者把移动信标与经典的质心定位算法、APIT定位算法及DV-Hop定位算法等相结合来改进这些定位算法。而质心定位算法及DV-Hop定位算法因为无需测距有着更多的优势也得到更多的研究。

无需测距（range-free）的定位算法不需要直接测量距离信息，而是根据网络的连通性确定网络中节点之间的跳数，同时根据已知位置参考节点的位置等信息估计每一跳的大致距离，然后估出节点在网络中的位置[10] 。典型的无需测距的定位算法有DV-Hop定位算法，APIT定位算法、质心定位算法、Amorphous 定位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成。

通过移动信标，或者说移动信标来对整个网络的未知节点进行定位的方法是最来兴起的一种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的飞行器上，并且该节点装有GPS或其他定位装置，这样就构造了移动信标[11] 。它可以在移动的过程中实时获得其当前的位置信息。

通过移动信标来定位的主要思想是：移动信标在“感兴趣的区域内（Region of interest，简称ROI）”[11] 移动的过程中，不断的广播包含其当前位置信息的分组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者三个以上的与其距离为R的位置信息时，就可以利用三边测量法或极大似然估计法[7]计算该未知节点的位置。

国内外对于移动信标的定位方法及信标的移动路径的规划研究处于起步阶

段，相关的文献并不多，提出的算法也不够成熟，文献[11] 和[11] 提出的定位方法只需要一个可以移动的信标，其中文献[11] 利用TOA测距技术和质心法来计算待定位节点位置，文献[11] 不需要复杂的测距技术，而是通过信标的不断运动并利用几何限制关系来计算待定位节点位置。

文献[12] 则在DV-Hop的基础上引入移动的信标形成一种新的M-A-DV-Hop算法，实现在不提高硬件成本的情况下，又能达到同样定位效果的构想。其定位的主要思想是：当移动信标在定位区域内移动时，移动到若干个新位置，立即在该位置补充一个普通节点。根据信标的即时位置信息，新位置的普通节点知道自身的位置。它们就等同于信标。另外，增加普通节点的同时，也提高了随机网络的连通度。引入移动信标的优势是即使只有一个信标也可以实现对未知节点的定位。

本论文针对基于信标的定位算法需要较高的信标节点密度导致定位成本提高的情况，引入移动信标在网络中移动并广播自己的位置分组信息在网络中构成虚拟信标的方法来定位未知节点，在DV-Hop定位算法的基础上将移动信标构成的虚拟信标来计算平均跳距离并结合跳数信息来对未知节点定位，通过规划优化的路径来提高定位效率。

对于移动信标的移动路径的规划也是一个重要的问题，本文进行了初步的研究。当采用移动信标在网络中移动来广播定位信息时，移动信标的移动路径及广播时间的选取，则很大程序上决定了网络定位的能量消耗及定位的效率。故研究信标的移动路径规划，使网络中的节点以最小的代价获得足够多用于自

身定位的信息成为一个重要的研究内容。

目前国内外主要的路径规划均为静态的路径，研究如何使移动节点的移动轨迹可以尽量覆盖网络区域。这样的算法显然不能最大限度的节约节点的能耗，对于严格要求能源的传感器网络节点来说，必然需要更为优化及适用于当前网络的路径规划算法来使节点移动路径尽可以少，减少广播的信息来减少网络节点的通信消耗。根据现有的路径规划方法，可以把路径的规划分为静态和动态规划，静态的路径规划与网络的连通状况无关，根据需要定位的ROI区域，规划以尽可能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可夫移动模型，螺线移动模型和SCAN移动模型。而国外有根据网络的联通状况来进行路径规划的动态算法，文献[12] 提出几条最优路径的选择原则，本文主要进行动态路径优化研究。

1.3 本论文的主要研究内容与结构

针对无线传感器网络基于信标节点的无需测距定位算法精度低，定位效率低的情况，本文提出基于移动信标优化路径的无线传感器网络节点定位算法。研究的内容主要如下：

1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。

2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广

播自己的位置信息，形成多个虚拟信标，未知节点采用加权处理的方法计算平均跳距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实现节点精确定位。并研究移动信标的动态选择算法来选择能获得最大计算精度的移动信标节点进行定位计算。仿真证明，相对于DV-Hop算法，基于移动信标改进的DV-Hop定位算法降低了定位的成本和布网的复杂度，提高节点定位的精度和效率。

3、结合基于移动信标改进的DV-Hop定位算法，提出了基于ROI(region of interest)的移动信标的路径规划方法，并把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。

文章结构层次安排如下：

第1章阐述了本课题的研究背景、研究意义及项目来源。通过对国内外相关领域的研究现状进行探讨，确立传感器网络定位算法的研究的方向。

第2章介绍了信标节点定位算法的相关工作，阐述了常用的基于移动信标的无线传感器节点定位算法，并分析了这几种常用算法的特点。

第3章研究基于移动信标的无线传感器网络节点的定位算法，将移动信标引入到DV-Hop定位算法中，提出了基于移动信标的DV-Hop定位算法和基于移动信标动态选择的改进DV-Hop定位算法，同时分析了改进算法在特定移动模型下的定位精度。

第4章结合基于移动信标改进的DV-Hop定位算法，提出了面向无线传感