1、精品毕业论文设计无线传感器网络基于移动信标优化路径的定位算法研究广东工业大学硕士学位论文(工学硕士)基于移动信标优化路径的定位算法研究Classified Index: School Code: 11845A Dissertation for Masters Degree of Guangdong University of Technology（Master of Engineering Science）Research on Localization Algorithm Based on Mobile Beacon with Optimal pathCandidate: Xie Xiaos
2、ongSupervisor: Prof. Cheng LianglunMay 2010Faculty of AutomationGuangdong University of TechnologyGuangzhou, Guangdong, P.R.China, 510006摘 要无线传感器节点定位技术是无线传感器网络的关键技术之一，是无线传感器网络大多数应用的基础。无线传感器网络应用的大多数领域, 如：目标监测与跟踪、路由位置信息的获取等，都需要知道节点的位置信息。为此我们需要研究更为有效的定位算法，降低定位成本，提高定位精度。针对这种情况，本论文对基于移动信标优化路径的无线传感器网络节点算法
3、进行了研究，该定位算法能够实现节点的高效率定位。文章在DV-Hop定位算法中引入移动信标节点，并研究信标节点的动态选择算法及移动路径优化算法。本文的主要完成的工作有：1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，研究平均跳距离的加权算法和信标节点的动态选择算法，降低定位的成本和布网的复杂度，提高节点定位的精度和效率。3、结合基于移动信标
4、改进的DV-Hop定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。 最后在OMNeT+仿真环境下，仿真基于移动信标的定位算法，建立包括移动智能节点和普通节点的仿真模型，通过定位过程的通信和数据处理计算未知节点的位置，仿真表明，基于移动信标优化路径的定位算法既改善了定位的精度，又减少了定位算法的通信开销，提高无线传感器网络节点定位效率。关键词：无线传感器网络；移动信标；优化路径；OMNeT+；智能节点 ABSTRACTWireless sensor
5、node localization is one of the key technologies for wireless sensor networks. Its 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
6、. 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 i
7、ntroduced 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 o
8、f 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 its location information that create virtual beacons. We study the weighted averag
9、e 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 mobi
10、le 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 communicat
11、ion 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 nodes location through the positioning process o
12、f 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
13、: WSN；Mobile anchor；Optimal path；OMNeT+；Smart nodeCONTENTS第一章 绪 论1.1 本论文的研究背景及意义1.1.1 研究背景与意义无线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息获取和处理模式1 。无线传感器网络(Wireless Sensor Networks，WSN)是由部署在监测区内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感
14、知、采集和处理网络覆盖区域内感知对象的信息，并传送给观察者2 。传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络应用中，通常将节点撒播在很广的区域里，网络中大部分的节点的位置是未知的，事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才可能获取到网络中事件的发生位置和信息来源位置。因此，定位是无线传感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件及信息发生的具体位置3 。节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定
15、位和追踪。此外，在设计路由协议时利用节点位置信息还可以提高路由效率，为网络提供命名空间，向网络部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置4 。因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向。传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自主确定位置被认为是其基本能力和系统的基本服务之一。对于WSN来说，人工部署或为所有网络节点配置GPS装置都会受到成本、功耗、拓展性等问题的限制，因此，寻求WSN 自身定位机制成为许多研究机构和学者共同探讨的问题4 。无线传感器网络中，根
16、据定位过程中是否实际测量节点间的距离，把定位机制分为：基于测距的(range-based)定位和距离无关的(range-free)定位方法5 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置。Range-based算法通过测量相邻节点间的实际距离或方位进行定位，测量距离的具体的方法有Time of Arrival(TOA) 6 ，Time Difference of Arrival(TDOA)7 ，Radio Signal Strength(RSSI)8 和Angle of Arrival(AOA)9 等。Ran
17、ge-based算法能够实现精确定位，但由于需要在节点中加入GPS或其它附加的测距的硬件设备，在实际应用中所需的成本较高。而Range-free定位算法由于降低了对节点硬件的要求，引起了更多的关注，典型算法有DV-Hop10 算法,基于RSSI的DV-Hop11 算法,基于连通性的定位算法12 等。目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法，都需要移动节点至少获得3个或者3个以上信标节点提供的坐标和距离13 。另一种思想则是使信标或者信标运动起来，通过带有GPS的已知位置的移动信标按某一规划好的路径或
18、运动模型遍历未知节点的区域，并发送定位信号，其它节点获取这些信号来进行定位计算。动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法14 ，包括待测节点的运动和信标节点的运动。当然从理论上讲，完全可以借鉴静态已有的成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时性要求较高，通常的改进方法是加入对节点运动的预测估计15 ，或是使定位算法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。虽然节点的移动性使定位过程复杂化，但是利用节点的移动性可提高定位精度，减少定位代价。在Bergamo等的研
19、究中，网络中有2个固定的信标向全网传送坐标信息，其余处于运动状态的节点根据接收到的信号强度进行自身定位16 。国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法17 。但这些算法普遍存在以下局限18 ： 依赖特殊硬件的支持； 需要特殊的网络拓扑结构。而在无线传感器网络中引入移动节点，可以增强其功能。如文献19 通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度分布不均匀的不足。文献20 提到利用移动参考节点和RSSI(接收信号强度指示)方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得RSSI技术在实际应用中仍然存在困难。尤其
20、是节点对能耗，体积等要求严格时，更多的时候并不能应用这种基于测距的定位技术。免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络连通情况或者GPS定位等思想提出的一种分布式定位方法，无需测距，这无疑降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差，当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差，精度也相应的降低21 。因此如何提高这种免测距定位算法的精度也成为了一个研究的热点方向。1.1.2 课题来源1.2 国内外研究现状基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖于信标节点的密度，网络的联通性。而信标节点的造价数倍
21、甚至十几倍于普通节点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游移动的节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效率。所以移动信标的定位算法近来成为新的研究热点，国内外许多学者进行了许多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规划。为此，国内外有许多学者把移动信标与经典的质心定位算法、APIT定位算法及DV-Hop定位算法等相结合来改进这些定位算法。而质心定位算法及DV-Hop定位算法因为无需测距有着更多的优势也得到更多的研究。无需测距（range-free
22、）的定位算法不需要直接测量距离信息，而是根据网络的连通性确定网络中节点之间的跳数，同时根据已知位置参考节点的位置等信息估计每一跳的大致距离，然后估出节点在网络中的位置22 。典型的无需测距的定位算法有DV-Hop定位算法，APIT定位算法、质心定位算法、Amorphous定位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成。通过移动信标，或者说移动信标来对整个网络的未知节点进行定位的方法是最来兴起的一种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的飞行器上，并且该节点装有GPS或其他定位装置，这样就构造了移动信标23 。它可以在移动的过程中实时获得其当前的位置信息。通过移
23、动信标来定位的主要思想是：移动信标在“感兴趣的区域内（Region of interest，简称ROI）”24 移动的过程中，不断的广播包含其当前位置信息的分组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者三个以上的与其距离为R的位置信息时，就可以利用三边测量法或极大似然估计法17 计算该未知节点的位置。国内外对于移动信标的定位方法及信标的移动路径的规划研究处于起步阶段，相关的文献并不多，提出的算法也不够成熟，文献25 和26 提出的定位方法只需要一个可以移动的信标，其中文献25 利用TOA测距技术和质心法来计算待定位节点位置，文献26 不需要复杂的测距技术，而是通过信标
24、的不断运动并利用几何限制关系来计算待定位节点位置。文献27 则在DV-Hop的基础上引入移动的信标形成一种新的M-A-DV-Hop算法，实现在不提高硬件成本的情况下，又能达到同样定位效果的构想。其定位的主要思想是：当移动信标在定位区域内移动时，移动到若干个新位置，立即在该位置补充一个普通节点。根据信标的即时位置信息，新位置的普通节点知道自身的位置。它们就等同于信标。另外，增加普通节点的同时，也提高了随机网络的连通度。引入移动信标的优势是即使只有一个信标也可以实现对未知节点的定位。本论文针对基于信标的定位算法需要较高的信标节点密度导致定位成本提高的情况，引入移动信标在网络中移动并广播自己的位置分
25、组信息在网络中构成虚拟信标的方法来定位未知节点，在DV-Hop定位算法的基础上将移动信标构成的虚拟信标来计算平均跳距离并结合跳数信息来对未知节点定位，通过规划优化的路径来提高定位效率。对于移动信标的移动路径的规划也是一个重要的问题，本文进行了初步的研究。当采用移动信标在网络中移动来广播定位信息时，移动信标的移动路径及广播时间的选取，则很大程序上决定了网络定位的能量消耗及定位的效率。故研究信标的移动路径规划，使网络中的节点以最小的代价获得足够多用于自身定位的信息成为一个重要的研究内容。目前国内外主要的路径规划均为静态的路径，研究如何使移动节点的移动轨迹可以尽量覆盖网络区域。这样的算法显然不能最大
26、限度的节约节点的能耗，对于严格要求能源的传感器网络节点来说，必然需要更为优化及适用于当前网络的路径规划算法来使节点移动路径尽可以少，减少广播的信息来减少网络节点的通信消耗。根据现有的路径规划方法，可以把路径的规划分为静态和动态规划，静态的路径规划与网络的连通状况无关，根据需要定位的ROI区域，规划以尽可能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可夫移动模型，螺线移动模型和SCAN移动模型。而国外有根据网络的联通状况来进行路径规划的动态算法，文献28 提出几条最优路径的选择原则，本文主要进行动态路径优化研究。1.3 本论文的主要研究内容与结构针对无线传感器网络基于信标节
27、点的无需测距定位算法精度低，定位效率低的情况，本文提出基于移动信标优化路径的无线传感器网络节点定位算法。研究的内容主要如下：1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。2、提出基于移动信标改进的DV-Hop定位算法，该算法在DV-Hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，未知节点采用加权处理的方法计算平均跳距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实现节点精确定位。并研究移动信标的动态选择算法来选择能获得最大计
28、算精度的移动信标节点进行定位计算。仿真证明，相对于DV-Hop算法，基于移动信标改进的DV-Hop定位算法降低了定位的成本和布网的复杂度，提高节点定位的精度和效率。3、结合基于移动信标改进的DV-Hop定位算法，提出了基于ROI(region of interest)的移动信标的路径规划方法，并把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。文章结构层次安排如下：第1章 阐述了本课题的研究背景、研究意义及项目来源。通过对国内外相关领域的研究现状进行探讨，确立传感器网络定位算法的研究的方向。第2章 介绍了信标
29、节点定位算法的相关工作，阐述了常用的基于移动信标的无线传感器节点定位算法，并分析了这几种常用算法的特点。第3章 研究基于移动信标的无线传感器网络节点的定位算法，将移动信标引入到DV-Hop定位算法中，提出了基于移动信标的DV-Hop定位算法和基于移动信标动态选择的改进DV-Hop定位算法，同时分析了改进算法在特定移动模型下的定位精度。第4章 结合基于移动信标改进的DV-Hop定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径。第5章 在OMNeT+仿真平台上进行无线传感器网络节点算法的仿真，设计移动信标节点的模型和
30、移动模型，并通过仿真论证优化路径对定位算法的影响。 第二章 传感器网络常用节点定位算法相关研究无线传感器网络节点定位方法的不同，分成两种定位类型：基于信标节点和不基于信标节点(也有论著将其分为无锚节点和有锚节点的定位算法，信标节点也可称为锚节点)。不基于信标节点的定位方法属于相对定位，基于信标的定位算法可以得出未知节点的绝对坐标。当前绝大多数节点定位算法均假设网络中存在少量信标节点，以实现整个网络的绝对定位。2.1无线传感器网络基于信标节点的定位算法2.1.1相关工作基于信标节点的定位算法在研究集中在移动信标的选择、移动路径、定位计算方法及移动节点的研究。由于信标节点需要移动，其在网络中的作用
31、更为重要，需要根据传感器网络的特点进行移动信标节点的设计及无线传感器网络的应用系统的研究。构建无线传感器网络应用系统，需要考虑网络在应用中的成本、数量、通信方面存在的诸多问题，主要需要考虑以下几个方面：1、低成本：系统必须是低成本，不仅从节点硬件、软件考虑，而且传感器也必须采用相对价格低的产品；2、低功耗：系统中采用普通AAA电池供电，所以要求网络必须是低功耗的，保证网络的生命周期尽量长；3、实时监测：监测信息需实时传输到管理服务器，方便用户实时查询；4、网关无线通信：由于监测区域的特殊性，不一定存在有线网络，例如：Internet、有线局域网等，故网关具有把采集的环境信息无线传输到服务器的功
32、能，不受监测区域的影响；5、精度：传感器决定了采集数据的精度，传感器采集数据的精度可以在规定范围内存在一定程度的误差；6、传感器接口灵活：系统根据环境参数的不同采用不相同的接口，传感器的类型也需根据实际需要而定，因此节点的传感器接口需灵活设定。传感器节点主要由低功耗的单片机，无线射频模块以及车载平台等组成，它首先采集各个模拟信号，把模拟信号转化成数字信号，经过单片机处理后，通过无线射频模块把数据传送到汇聚节点。汇聚节点的处理器采用ARM9 S3C2410，它还包括GPRS模块，无线射频模块，网络接口等，它的功能主要是接收附近所有传感器节点发送过来的数据，并且通过Internet或者GPRS模块上传到上层监控软件。无线传感器网络移动节点定位系统的硬件系统需要根据上面所述的要求建立合适的传感器系统，为此设计的传感器移动节点主要由低功耗的微处理器，射频模块，传感器接口，电源模块以及车载平台5部分组成，如图2-1所示，普通节点则没有车载平台。图2-1传感器移动节点结构Fig. 2-1
