毕业论文无线传感器网络基于移动信标优化路径的定位算法研究

1、广东工业大学硕士学位论文(工学硕士)基于移动信标优化路径的定位算法研究classified index: school code: 11845udc: security class: class no.:2110704294a dissertation for masters degree of guangdong university of technology（master of engineering science）research on localization algorithm based on mobile beacon with optimal pathcandidate:

2、xie xiaosongsupervisor: 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+；智能节点 abstractwireles

5、s sensor 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

6、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 no

7、des. 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 me

8、chanism 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 its location information that create virtual beacons. we study the weight

9、ed 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 prop

10、osed 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 c

11、ommunication 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

12、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.

13、key words: wsn；mobile anchor；optimal path；omnet+；smart node目 录摘 要iabstractiii目 录vcontentsvii第一章 绪 论11.1 本论文的研究背景及意义11.1.1 研究背景与意义11.1.2 课题来源31.2 国内外研究现状31.3 本论文的主要研究内容与结构5第二章 传感器网络常用节点定位算法相关研究72.1无线传感器网络基于信标节点的定位算法72.1.1相关工作72.1.2基于信标定位算法的优点92.2无线传感器网络常用的定位方式的实现102.2.1极大似然估计法102.2.2三边测量定位法112.2.3三角测

14、量定位法122.3常用的节点定位算法132.3.1 常用的range-base节点定位算法132.3.2常用的range-free节点定位算法162.4本章小结18第三章 基于移动信标的节点定位算法193.1 无线传感器网络基于移动信标改进的dv-hop定位算法193.1.1 dv-hop定位算法203.1.2移动信标节点定位算法233.1.3 仿真分析263.2基于移动信标动态选择改进dv-hop定位算法283.2.1 dv-hop定位算法平均跳距离计算误差来源分析293.2.2基于移动信标动态选择的改进型dv-hop定位算法过程313.2.3仿真分析343.3 本章小结35第四章 无线传感

15、器网络移动信标的路径优化364.1无线传感器网络移动信标的移动模型分析364.1.1 随机移动rwp(random way point)模型364.1.2高斯马尔可夫移动gauss-markov模型374.1.3 螺线移动模型384.2面向无线传感器网络节点定位的移动信标的路径优化384.2.1基于图论的信标移动路径规划方法394.2.2面向传感器网络的移动信标路径规划的仿真实现404.3 本章小结42第五章 基于移动信标优化路径定位算法的仿真实现435.1仿真实验工具和实验方法简述435.1.1 omnet+仿真实验平台介绍435.1.2定位算法性能评价指标及分析方法445.2基于移动信标的

16、传感器网络定位算法的设计455.2.1无线传感器网络仿真程序模型及程序设计465.2.2定位过程仿真程序设计515.3基于移动信标优化路径的定位算法性能分析525.4 本章小结55结论与展望56参 考 文 献57攻读学位期间发表的学术论文60攻读学位期间参加的科研项目61独创性声明62致 谢63contentsabstract(chinese)iabstract(english)iiicontents(chinese)vcontents(english)viichapter 1 introduction11.1 research background and meaning of this s

17、ubject11.1.1 research background and meaning11.1.2 source of this subject31.2 domestic and foreign research status31.3 main content and structure of this subject5chapter 2 common nodes localization for sensor network72.1 localization algorithm base on beacon72.1.1 realative work72.1.2the advantage o

18、f localization algorithm base on beacon92.2 implement of common localization ways102.2.1 maximum likelihood estimation102.2.2 trilateration method localization112.2.3 triangulation method localization122.3 common nodes localization algorithm132.3.1 common range-base nodes localization algorithm132.3

19、.2 common range-free nodes localization algorithm162.4 summary of this chapter18chapter 3 localization algorithm based on mobile beacon193.1 improving dv-hop algorithm base on mobile beacon193.1.1 dv-hop localization algorithm203.1.2 nodes localization algorithm base on mobile beacon233.1.3 simulati

20、on result263.2 improving dv-hop algorithm base on mobile beacon dynamic selection283.2.1 analysis the error resource of dv-hop averager hop distance293.2.2 the process of the improving localization algorithm313.2.3 simulation result343.3 summary of this chapter35chapter 4 mobile beacon moving path o

21、ptimization364.1 analysis the moving model of mobile beacon364.1.1 rwp(random way point) moving model364.1.2 gauss-markov moving model374.1.3 spire moving model384.2 mobile beacon moving path optimization for wsns384.2.1 mobile beacon path planning base on graph theory394.2.2 simulation of the mobil

22、e beacon path planning404.3 summary of this chapter42chapter 5 simulation of localzaition algorithm base on mobile beacon435.1 introduction of simulation tools and environment435.1.1 introduction of omnet+435.1.2 localization algorithm performance evaluation and analysis445.2 localization algorithm

23、design base on mobile beacon455.2.1 programming and modeling localization algorithm465.2.2 programming the process of the localization algorithm515.3 performance evaluation and analysis of the localization algrithm base on optimize path525.4 summary of this chapter55conclusion and prospect56referenc

24、es57published papers60participant projects61original creative statement62acknowledgements63第一章 绪 论1.1 本论文的研究背景及意义1.1.1 研究背景与意义无线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息获取和处理模式1 。无线传感器网络(wireless sensor networks，wsn)是由部署在监测区内大量的廉价微型传感器节点组成，

25、通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域内感知对象的信息，并传送给观察者2 。传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络应用中，通常将节点撒播在很广的区域里，网络中大部分的节点的位置是未知的，事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才可能获取到网络中事件的发生位置和信息来源位置。因此，定位是无线传感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件及信息发生的具体位置3 。节点必须明确自身位置

26、才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。此外，在设计路由协议时利用节点位置信息还可以提高路由效率，为网络提供命名空间，向网络部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置4 。因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向。传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自主确定位置被认为是其基本能力和系统的基本服务之一。对于wsn来说，人工部署或为所有网络节点配置gps装置都会受到成本、功耗、拓展性等问题的限制，因此，寻求wsn 自身定位

27、机制成为许多研究机构和学者共同探讨的问题4 。无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机制分为：基于测距的(range-based)定位和距离无关的(range-free)定位方法5 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置。range-based算法通过测量相邻节点间的实际距离或方位进行定位，测量距离的具体的方法有time of arrival(toa) 6 ，time difference of arrival(tdoa)7 ，radio signal strength(rss

28、i)8 和angle of arrival(aoa)9 等。range-based算法能够实现精确定位，但由于需要在节点中加入gps或其它附加的测距的硬件设备，在实际应用中所需的成本较高。而range-free定位算法由于降低了对节点硬件的要求，引起了更多的关注，典型算法有dv-hop10 算法,基于rssi的dv-hop11 算法,基于连通性的定位算法12 等。目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法，都需要移动节点至少获得3个或者3个以上信标节点提供的坐标和距离13 。另一种思想则是使信标或者信

29、标运动起来，通过带有gps的已知位置的移动信标按某一规划好的路径或运动模型遍历未知节点的区域，并发送定位信号，其它节点获取这些信号来进行定位计算。动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法14 ，包括待测节点的运动和信标节点的运动。当然从理论上讲，完全可以借鉴静态已有的成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时性要求较高，通常的改进方法是加入对节点运动的预测估计15 ，或是使定位算法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。虽然节点的移动性使定位过程复杂化，但是利

30、用节点的移动性可提高定位精度，减少定位代价。在bergamo等的研究中，网络中有2个固定的信标向全网传送坐标信息，其余处于运动状态的节点根据接收到的信号强度进行自身定位16 。国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法17 。但这些算法普遍存在以下局限18 ： 依赖特殊硬件的支持； 需要特殊的网络拓扑结构。而在无线传感器网络中引入移动节点，可以增强其功能。如文献19 通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度分布不均匀的不足。文献20 提到利用移动参考节点和rssi(接收信号强度指示)方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等

31、条件往往都是变化的，使得rssi技术在实际应用中仍然存在困难。尤其是节点对能耗，体积等要求严格时，更多的时候并不能应用这种基于测距的定位技术。免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络连通情况或者gps定位等思想提出的一种分布式定位方法，无需测距，这无疑降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差，当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差，精度也相应的降低21 。因此如何提高这种免测距定位算法的精度也成为了一个研究的热点方向。1.1.2 课题来源本课题来源于国家自然科学基金资助项目（编号：60673132）；广东省自然

32、科学基金重点项目（编号：07117421）。1.2 国内外研究现状基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖于信标节点的密度，网络的联通性。而信标节点的造价数倍甚至十几倍于普通节点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游移动的节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效率。所以移动信标的定位算法近来成为新的研究热点，国内外许多学者进行了许多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规划。为此，国内外有许多学者把移动信标与经典的质心定

33、位算法、apit定位算法及dv-hop定位算法等相结合来改进这些定位算法。而质心定位算法及dv-hop定位算法因为无需测距有着更多的优势也得到更多的研究。无需测距（range-free）的定位算法不需要直接测量距离信息，而是根据网络的连通性确定网络中节点之间的跳数，同时根据已知位置参考节点的位置等信息估计每一跳的大致距离，然后估出节点在网络中的位置22 。典型的无需测距的定位算法有dv-hop定位算法，apit定位算法、质心定位算法、amorphous定位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成。通过移动信标，或者说移动信标来对整个网络的未知节点进行定位的方法是最来兴起的一

34、种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的飞行器上，并且该节点装有gps或其他定位装置，这样就构造了移动信标23 。它可以在移动的过程中实时获得其当前的位置信息。通过移动信标来定位的主要思想是：移动信标在“感兴趣的区域内（region of interest，简称roi）”24 移动的过程中，不断的广播包含其当前位置信息的分组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者三个以上的与其距离为r的位置信息时，就可以利用三边测量法或极大似然估计法17 计算该未知节点的位置。国内外对于移动信标的定位方法及信标的移动路径的规划研究处于起步阶段，相关的文献并不多，提

35、出的算法也不够成熟，文献25 和26 提出的定位方法只需要一个可以移动的信标，其中文献25 利用toa测距技术和质心法来计算待定位节点位置，文献26 不需要复杂的测距技术，而是通过信标的不断运动并利用几何限制关系来计算待定位节点位置。文献27 则在dv-hop的基础上引入移动的信标形成一种新的m-a-dv-hop算法，实现在不提高硬件成本的情况下，又能达到同样定位效果的构想。其定位的主要思想是：当移动信标在定位区域内移动时，移动到若干个新位置，立即在该位置补充一个普通节点。根据信标的即时位置信息，新位置的普通节点知道自身的位置。它们就等同于信标。另外，增加普通节点的同时，也提高了随机网络的连通

36、度。引入移动信标的优势是即使只有一个信标也可以实现对未知节点的定位。本论文针对基于信标的定位算法需要较高的信标节点密度导致定位成本提高的情况，引入移动信标在网络中移动并广播自己的位置分组信息在网络中构成虚拟信标的方法来定位未知节点，在dv-hop定位算法的基础上将移动信标构成的虚拟信标来计算平均跳距离并结合跳数信息来对未知节点定位，通过规划优化的路径来提高定位效率。对于移动信标的移动路径的规划也是一个重要的问题，本文进行了初步的研究。当采用移动信标在网络中移动来广播定位信息时，移动信标的移动路径及广播时间的选取，则很大程序上决定了网络定位的能量消耗及定位的效率。故研究信标的移动路径规划，使网络

37、中的节点以最小的代价获得足够多用于自身定位的信息成为一个重要的研究内容。目前国内外主要的路径规划均为静态的路径，研究如何使移动节点的移动轨迹可以尽量覆盖网络区域。这样的算法显然不能最大限度的节约节点的能耗，对于严格要求能源的传感器网络节点来说，必然需要更为优化及适用于当前网络的路径规划算法来使节点移动路径尽可以少，减少广播的信息来减少网络节点的通信消耗。根据现有的路径规划方法，可以把路径的规划分为静态和动态规划，静态的路径规划与网络的连通状况无关，根据需要定位的roi区域，规划以尽可能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可夫移动模型，螺线移动模型和scan移动模型

38、。而国外有根据网络的联通状况来进行路径规划的动态算法，文献28 提出几条最优路径的选择原则，本文主要进行动态路径优化研究。1.3 本论文的主要研究内容与结构针对无线传感器网络基于信标节点的无需测距定位算法精度低，定位效率低的情况，本文提出基于移动信标优化路径的无线传感器网络节点定位算法。研究的内容主要如下：1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。2、提出基于移动信标改进的dv-hop定位算法，该算法在dv-hop定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形

39、成多个虚拟信标，未知节点采用加权处理的方法计算平均跳距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实现节点精确定位。并研究移动信标的动态选择算法来选择能获得最大计算精度的移动信标节点进行定位计算。仿真证明，相对于dv-hop算法，基于移动信标改进的dv-hop定位算法降低了定位的成本和布网的复杂度，提高节点定位的精度和效率。3、结合基于移动信标改进的dv-hop定位算法，提出了基于roi(region of interest)的移动信标的路径规划方法，并把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，

40、提高算法的效率。文章结构层次安排如下：第1章 阐述了本课题的研究背景、研究意义及项目来源。通过对国内外相关领域的研究现状进行探讨，确立传感器网络定位算法的研究的方向。第2章 介绍了信标节点定位算法的相关工作，阐述了常用的基于移动信标的无线传感器节点定位算法，并分析了这几种常用算法的特点。第3章 研究基于移动信标的无线传感器网络节点的定位算法，将移动信标引入到dv-hop定位算法中，提出了基于移动信标的dv-hop定位算法和基于移动信标动态选择的改进dv-hop定位算法，同时分析了改进算法在特定移动模型下的定位精度。第4章 结合基于移动信标改进的dv-hop定位算法，提出了面向无线传感器网络的移

41、动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径。第5章 在omnet+仿真平台上进行无线传感器网络节点算法的仿真，设计移动信标节点的模型和移动模型，并通过仿真论证优化路径对定位算法的影响。 第二章 传感器网络常用节点定位算法相关研究无线传感器网络节点定位方法的不同，分成两种定位类型：基于信标节点和不基于信标节点(也有论著将其分为无锚节点和有锚节点的定位算法，信标节点也可称为锚节点)。不基于信标节点的定位方法属于相对定位，基于信标的定位算法可以得出未知节点的绝对坐标。当前绝大多数节点定位算法均假设网络中存在少量信标节点，以实现整个网络的绝对定位。2.

42、1无线传感器网络基于信标节点的定位算法2.1.1相关工作基于信标节点的定位算法在研究集中在移动信标的选择、移动路径、定位计算方法及移动节点的研究。由于信标节点需要移动，其在网络中的作用更为重要，需要根据传感器网络的特点进行移动信标节点的设计及无线传感器网络的应用系统的研究。构建无线传感器网络应用系统，需要考虑网络在应用中的成本、数量、通信方面存在的诸多问题，主要需要考虑以下几个方面：1、低成本：系统必须是低成本，不仅从节点硬件、软件考虑，而且传感器也必须采用相对价格低的产品；2、低功耗：系统中采用普通aaa电池供电，所以要求网络必须是低功耗的，保证网络的生命周期尽量长；3、实时监测：监测信息需

43、实时传输到管理服务器，方便用户实时查询；4、网关无线通信：由于监测区域的特殊性，不一定存在有线网络，例如：internet、有线局域网等，故网关具有把采集的环境信息无线传输到服务器的功能，不受监测区域的影响；5、精度：传感器决定了采集数据的精度，传感器采集数据的精度可以在规定范围内存在一定程度的误差；6、传感器接口灵活：系统根据环境参数的不同采用不相同的接口，传感器的类型也需根据实际需要而定，因此节点的传感器接口需灵活设定。传感器节点主要由低功耗的单片机，无线射频模块以及车载平台等组成，它首先采集各个模拟信号，把模拟信号转化成数字信号，经过单片机处理后，通过无线射频模块把数据传送到汇聚节点。汇

44、聚节点的处理器采用arm9 s3c2410，它还包括gprs模块，无线射频模块，网络接口等，它的功能主要是接收附近所有传感器节点发送过来的数据，并且通过internet或者gprs模块上传到上层监控软件。无线传感器网络移动节点定位系统的硬件系统需要根据上面所述的要求建立合适的传感器系统，为此设计的传感器移动节点主要由低功耗的微处理器，射频模块，传感器接口，电源模块以及车载平台5部分组成，如图2-1所示，普通节点则没有车载平台。图2-1传感器移动节点结构fig. 2-1 sensor network mobile nodes structure根据此模型设计制作的移动节点如下图2-2所示。节点采

45、用msp430低功耗单片机，芯片集成spi，iic，12位a/d等标准接口，可以通过spi接口与射频模块cc2420进行连接，节点还设计了了标准的传感器接口，可以通过接口连接到常用的传感器模块。为了实验方便，节点集成了ds18b20温度传感器，tsl2561光强度传感器。同时，把节点放在车载平台上，实现节点的移动。图2-2传感器网络节点fig. 2-2 sensor network nodes 黎大鹏在文献29 中研究了基于信标节点动态调整的移动节点的定位算法。对基于锚节点动态调整的传感器网络移动节点定位系统进行了研究，该系统能够实现移动节点的高效率定位。文章分别从嵌入式硬件平台的硬件设计，移

46、动节点定位算法，以及定位系统的程序设计与实现三方面来对该系统进行研究。提出基于vwmc（voronoi and weight monte carlo method）的传感器网络移动节点定位算法，该算法在mcl（monte carlo localization）算法的基础上加入voronoi图和权值分析技术。仿真证明，相对于mcl算法，基于vwmc的传感器网络移动节点定位算法提高了移动节点定位的精度和效率。结合基于vwmc的传感器网络移动节点定位算法以及锚节点动态调整策略，提出了基于锚节点动态调整的传感器网络移动节点定位算法，提高了算法对外界干扰的抵御能力。2.1.2基于信标定位算法的优点相对定

47、位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可为网络提供唯一的命名空间，受节点移动性影响较小，有更广泛的应用领域。但研究发现，在相对定位的基础上也能够实现部分路由协议，尤其是基于地理位置的路由(geo-routing)，而且相对定位不需要信标节点。在某些无需网络节点绝对位置的应用中，可以采用无信标节点的定位算法来实现整个网络的相对定位。典型的无信标节点的定位算法包含spa30 、sdgps31 、afl32 等定位算法。spa算法选择网络中密度最大处的一组节点作为建立网络全局坐标系统的参考点，并在其中选择连通度最大的一个节点作为坐标系统的原点。首先根据节点间的测距结果在

48、各个节点上建立局部坐标系统，通过节点间的信息交换与协调，以参考点为基准通过坐标变换逐步建立全局坐标系统。spa算法的主要缺点是网络通信开销太大。sdgpsn算法在spa算法的基础上，提出了基于聚类的定位思想。基本思想:网络部署完后，每个传感器节点开始运行一个随机的定时器，如果与邻居节点相比，节点i的定时器最先到期且没有收到任何邻居节点的消息，则i升级为主节点，并向邻居节点广播此消息，所有接收到该消息的邻居节点中止其定时器并成为该主节点的从节点。这些节点构成一个以主节点i为坐标原点的节点域，并随扫a择两个与i相邻的从节点为辅助节点对，构建一个局部坐标系。节点域内的所有其他从节点通过选择适当的辅助

49、节点对来计算其在此局部坐标系中的坐标。然后相邻的节点域依靠两个域的共同边际节点的相关坐标信息，以主节点id较小的局部坐标系为参照，进行相邻局部坐标系间的坐标转换，直至建立一个全局坐标系。sdgpsn算法和spa算法相比，通信开销明显降低，这使得它更适于大规模无线传感器网络的部署。afl算法是完全分布式的节点定位方法。利用amp所有节点从随机初始坐标分配开始，只利用局部距离估计和通过局部信息交换收敛到一个与距离估计一致的坐标分配。在给定一个未知坐标的节点集合和一种节点可以估测它到其邻居节点距离机制的条件下，通过局部节点间的通信决定每个节点的位置坐标。基于信标节点的定位算法依赖于某些已知坐标位置的

50、节点。这种定位算法需要预先定位信标节点，否则无法正常运行，另外为了减小定位误差，信标节点的数目还须足够多。基于信标节点的定位算法的一个重要特征是定位精度取决于信标点密度。为了解决基于信标节点的定位算法对信标节点的密度的依赖，近年来许多学者进行了移动信标节点定位算法的研究，通过在引入移动信标节点在网络中按预定轨迹漫游并广播自己的位置分组在构成虚拟信标节点，可以大大减少信标节点的投入。因为信标节点造价往往比普通节点高，在许多固定的传感器网络中，定位成功后信标节点将转为普通节点使用，极大的浪费了资源。所以基于移动信标节点的定位算法成为近年来研究的一个热点。本章首先介绍无线传感器网络常用的定位方式及其

51、实现，然后介绍常用的基于测距和无需测距的定位算法，并根据这些算法的特点，分析其优缺点，为下一章提出新的基于移动信标的定位算法奠定了理论基础。2.2无线传感器网络常用的定位方式的实现2.2.1极大似然估计法传感器网络移动节点定位系统中节点有可能和多于3个的不同信标相连。因此可以使用更多的节点以获得冗余信息来计算未知节点的位置。极大似然估计多边测量33 就采用了上面的方法，已知n个节点的坐标分别为(x1,y1)，(x2,y2)，(x3,y3)，.，(xn ,yn )，它们到未知节点 d 的距离分别为dl，d2，d3，.，dn，假设节点 d的坐标为(x，y)。那么，存在下列公式： (2.1)最后，使

52、用标准的最小均方差估计方法可以得到未知节点 d 的坐标。2.2.2三边测量定位法三边测量法是通过 rssi值得出未知节点到 3 个信标的距离，通过这3个距离值计算出未知节点的位置。如下图2-1所示，当节点p1，p2，p3未知节点p发出的定位信号时，根据 rssi值，可以得到 p1到 p，p2到 p，p3到 p的距离d1，d2，d3；分别以 p1，p2，p3为圆心，d1，d2，d3为半径作圆，通过这 3个圆相交区域定出未知节点的位置。图2-3三边测量法原理fig. 2-3 trilateration method principle但是在真实环境下三边测量法存在巨大的缺陷，如图3-6所示，实际上

53、测量得到的3个距离rp1，rp2，rp3存在着误差，导致以rp1，rp2，rp3为半径建立的3个圆并不是相交于一点，而是相交于一个区域。这样建立起来的等式方程组没有解，根本无法实现对节点的定位。有些文章提出了以区域的质点作为节点的位置，这种方法也不好，节点定位的误差会随着相交区域的增大而大大地提高。总的来说，针对节点的定位算法都是在理想的仿真环境下进行研究的，当节点处于存在干扰或者移动的情况下，这些算法或不能够实现节点精确的定位，或算法的计算量太大。2.2.3三角测量定位法三角测量法原理如图2-2所示，已知a、b、c三个节点的坐标分别为(xa,ya),(xb,yb)，(xc,yc)，节点d相对

54、于节点a、b、c的角度分别为：adb，adc，bdc，假设节点d的坐标为(x，y)，d为图2-2中三个圆的交点。图2-4三角测量法示意图fig. 2-4 triangulation method principle对于节点a，c和角adc，如果弧段ac在abc内，那么能够唯一确定一个圆，设圆心为，半径为r1，那么，并存在下列公式： (2.2)由式(2.2)能够确定圆心o1点的坐标和半径r1。同理对a，b，adb和b，c，bdc分别确定相应的圆心、半径r2、圆心和半径r3。最后根据已知的r1，r2，r3，采用三边测量法确定d点坐标。2.3常用的节点定位算法2.3.1 常用的range-base节

55、点定位算法根据定位过程中是否测量实际节点间的距离，定位算法可分为：基于距离(range-based)的定位算法和距离无关(range-free)的定位算法34 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置35 。1、基于信号强度（rssi）定位rssi(received signal strength indicator)是接收到的信号强度指示器，是一种利用信号衰减推测距离的测距技术36。目前很多定位算法都是利用rssi技术实现的。目前，wsn网络中无线通信芯片主要有两种：cc1000和cc2420。cc10

56、00的工作频带为315mhz,868mhz,915mhz，数据传送速率可达72.8kbit/s，适用于跳频协议。cc2420工作频带在2.4ghz-2.4835ghz，采用的是o-qpsk调制方式，数据速率在250kbit/s，具有较高的抗干扰能力。对于cc1000通信芯片，rssi值是一个10位的寄存器值，而对于cc2420，该值却是一个8位的寄存器值。它是通过a/d转换器转换而来的，芯片不同，rssi的转换方式也是不同的。若芯片是cc1000： （2.3） （2.4） （2.5） （2.6）其中，rssi是寄存器值，也就是节点接收到的信号强度值，vrssi是a/d转换前的rssi电压值，单位为(v)；vbat为电源电压，该值为一个常数值3v；pcurrent是当前节点的发射功率，单位为dbm；p0为当节点与源节点足够远时接收到的功率值，一般来说p0取-80dbm；p为功率衰减值。（2.6）式是由（2.3），（2.4），（2.5）联合而得的，表明在当前发射功率下，发送到最远的距离