【最新版】无线传感器网络基于移动信标优化路径的定位算法研究_

1、(此文档为word 格式，下载后您可任意编辑修改！广东工业大学硕士学位论文(工学硕士基于移动信标优化路径的定位算法研究分类号： 学校代号：11845广东工业大学硕士学位论文（工学硕士）基于移动信标优化路径的定位算法研究指导教师姓名、职称： 教授企业导师姓名、职称： 无专业 或 领域 名 称： 控制理论与控制工程学 生 所 属 学 院： 自动化学院论 文 答 辩 日 期：School Code: 11845A Dissertation for Masters Degree ofGuangdong University of Technology（Master of Engineering Sci

2、ence）Research on Localization Algorithm Based on MobileBeacon with Optimal pathCandidate: Xie XiaosongSupervisor: Prof. Cheng LianglunMay 2010Faculty of AutomationGuangdong University of Technology摘 要无线传感器节点定位技术是无线传感器网络的关键技术之一，是无线传感器网络大多数应用的基础。无线传感器网络应用的大多数领域, 如：目标监测与跟踪、路由位置信息的获取等，都需要知道节点的位置信息。为此我们需

3、要研究更为有效的定位算法，降低定位成本，提高定位精度。针对这种情况，本论文对基于移动信标优化路径的无线传感器网络节点算法进行了研究，该定位算法能够实现节点的高效率定位。文章在DV-Hop 定位算法中引入移动信标节点，并研究信标节点的动态选择算法及移动路径优化算法。本文的主要完成的工作有：1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。2、提出基于移动信标改进的DV-Hop 定位算法，该算法在DV-Hop 定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，

4、研究平均跳距离的加权算法和信标节点的动态选择算法，降低定位的成本和布网的复杂度，提高节点定位的精度和效率。3、结合基于移动信标改进的DV-Hop 定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。最后在OMNeT+仿真环境下，仿真基于移动信标的定位算法，建立包括移动智能节点和普通节点的仿真模型，通过定位过程的通信和数据处理计算未知节点的位置，仿真表明，基于移动信标优化路径的定位算法既改善了定位的精度，又减少了定位算法的通信开销，提高无线传感器网络节点

5、定位效率。关键词：无线传感器网络；移动信标；优化路径；OMNeT+；智能节点ABSTRACTWireless 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,

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

7、lgorithm 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 th

8、e 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 its location informa

9、tion 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 lo

10、calization 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 positi

11、oning 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 t

12、he unknown nodes 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

13、 efficiency of wireless sensor nodes localization.Key words: WSN ；Mobile anchor；Optimal path；OMNeT+；Smart node目 录摘 要 . .I ABSTRACT . . I II 目 录 . . V CONTENTS . . VII第一章 绪 论 . . 11.1 本论文的研究背景及意义 . 11.2 国内外研究现状 . 31.3 本论文的主要研究内容与结构 . 5第二章 传感器网络常用节点定位算法相关研究 . . 72.1无线传感器网络基于信标节点的定位算法 . 72.2无线传感器网络常用的定

14、位方式的实现 . 102.3常用的节点定位算法 . 132.4本章小结 . 18第三章 基于移动信标的节点定位算法 . . 193.1 无线传感器网络基于移动信标改进的DV-Hop 定位算法 . 193.2基于移动信标动态选择改进DV-Hop 定位算法 . 283.3 本章小结 . 35第四章 无线传感器网络移动信标的路径优化 . . 364.1无线传感器网络移动信标的移动模型分析 . 364.2面向无线传感器网络节点定位的移动信标的路径优化 . 384.3 本章小结 . 42第五章 基于移动信标优化路径定位算法的仿真实现 . . 425.1仿真实验工具和实验方法简述 . 425.2基于移动信

15、标的传感器网络定位算法的设计 . 455.3基于移动信标优化路径的定位算法性能分析 . 515.4 本章小结 . 54结论与展望 . . 55参 考 文 献 . . 56攻读学位期间发表的学术论文 . . 59攻读学位期间参加的科研项目 . . 60独创性声明 . . 61致 谢 . . 62CONTENTSABSTRACT(Chinese . .I ABSTRACT(English . I II CONTENTS(Chinese . V CONTENTS(English . VIIChapter 1 Introduction . . 11.1 Research Background and

16、Meaning of This Subject . 11.2 Domestic and Foreign Research Status . 31.3 Main Content and Structure of This Subject . 5Chapter 2 Common Nodes Localization for Sensor Network . . 72.1 Localization Algorithm Base on Beacon . . 72.2 Implement of Common Localization Ways . . 102.3 Common Nodes Localiz

17、ation Algorithm. 132.4 Summary of This Chapter . 18Chapter 3 Localization Algorithm based on Mobile Beacon . 193.1 Improving DV-Hop Algorithm base on Mobile Beacon . 193.2 Improving DV-Hop Algorithm base on Mobile Beacon Dynamic Selection . . 283.3 Summary of This Chapter . 35Chapter 4 Mobile Beacon

18、 Moving Path Optimization . 364.1 Analysis the Moving Model of Mobile Beacon . 364.2 Mobile Beacon Moving Path Optimization for WSNs . . 384.3 Summary of This Chapter . 42Chapter 5 Simulation of Localzaition Algorithm base on Mobile Beacon . 425.1 Introduction of Simulation Tools and Environment . .

19、 425.2 Localization Algorithm Design base on Mobile Beacon . . 455.3 Performance Evaluation and Analysis of the Localization Algrithm base onOptimize Path . 515.4 Summary of This Chapter . 54Conclusion and Prospect . 55References . 56Published Papers . . 59Participant Projects . 60Original Creative

20、Statement . 61Acknowledgements . 62第一章 绪 论1.1 本论文的研究背景及意义无线传感器网络综合了传感器、嵌入式计算、分布式信息处理和无线通信等技术，由许多相同或不同类型传感器节点通过无线通信实现自组织，形成分布式自治网络。它打破了传统的点对点的数据信息交互方式，带来了一种全新的信息获取和处理模式错误！未找到引用源。无线传感器网络(Wireless Sensor Networks，WSN 是由部署在监测区内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感知、采集和处理网络覆盖区域内感知对象的信息，并传送给观察者

21、1 。传感器网络节点在部署时往往是不可控制的，比如在大型的无线传感器网络应用中，通常将节点撒播在很广的区域里，网络中大部分的节点的位置是未知的，事先不能确定，但无线传感器网络的大多数应用都需要知道网络中节点的位置信息，才可能获取到网络中事件的发生位置和信息来源位置。因此，定位是无线传感器网络的主要应用领域之一，对于大多数应用，不知道节点位置而感知的数据是没有意义的。只有在传感器节点自身正确定位后，才能确定传感器节点监测到的事件及信息发生的具体位置2 。节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件”，实现对外部目标的定位和追踪。此外，在设计路由协议时利用节点位置信息还可以提高

22、路由效率，为网络提供命名空间，向网络部署者报告网络的覆盖质量，实现网络的负载均衡以及网络拓扑的自配置2 。因此，节点的定位问题已经成为无线传感器网络的一个重要的研究方向。传感器节点自身定位就是一种通过估计至邻居节点的距离或邻居数目，利用节点间的信息交换来确定各节点自身位置的机制。在传感器网络中，节点能够自主确定位置被认为是其基本能力和系统的基本服务之一。对于WSN 来说，人工部署或为所有网络节点配置GPS 装置都会受到成本、功耗、拓展性等问题的限制，因此，寻求WSN 自身定位机制成为许多研究机构和学者共同探讨的问题2 。无线传感器网络中，根据定位过程中是否实际测量节点间的距离，把定位机制分为：

23、基于测距的(range-based定位和距离无关的(range-free定位方法2 。前者需要测量相邻节点间的绝对距离或方位，然后利用该实际距离来确定未知目标节点位置；后者则仅利用节点间距离关联关系计算目标节点位置。Range-based 算法通过测量相邻节点间的实际距离或方位进行定位，测量距离的具体的方法有Time of Arrival(TOA 3 ，Time Difference of Arrival(TDOA4 ，Radio Signal Strength(RSSI5 和Angle of Arrival(AOA5 等。Range-based 算法能够实现精确定位，但由于需要在节点中加入G

24、PS 或其它附加的测距的硬件设备，在实际应用中所需的成本较高。而Range-free 定位算法由于降低了对节点硬件的要求，引起了更多的关注，典型算法有DV-Hop 6 算法, 基于RSSI 的DV-Hop 6 算法, 基于连通性的定位算法6 等。目前基于距离的定位算法都是利用静态的几何关系来确定节点位置，且对信标节点的布置和密度要求高，如三边、多边测量定位、基于角度测量定位等算法，都需要移动节点至少获得3个或者3个以上信标节点提供的坐标和距离6 。另一种思想则是使信标或者信标运动起来，通过带有GPS 的已知位置的移动信标按某一规划好的路径或运动模型遍历未知节点的区域，并发送定位信号，其它节点获

25、取这些信号来进行定位计算。动态算法的研究是最近兴起的一个热点，理论还不完善，有别于静态算法所涉及的都是固定节点，其主要是讨论对传感网中移动节点定位的方法7 ，包括待测节点的运动和信标节点的运动。当然从理论上讲，完全可以借鉴静态已有的成熟算法，计算出特定时刻的节点位置，但因为节点的运动，对定位算法的实时性要求较高，通常的改进方法是加入对节点运动的预测估计7 ，或是使定位算法能自动适应不同节点运动的方式，从而提高对运动节点的定位准确性。虽然节点的移动性使定位过程复杂化，但是利用节点的移动性可提高定位精度，减少定位代价。在Bergamo 等的研究中，网络中有2个固定的信标向全网传送坐标信息，其余处于

26、运动状态的节点根据接收到的信号强度进行自身定位7 。国内外学者对定位问题进行了大量研究，提出了几种比较典型的定位算法7 。但这些算法普遍存在以下局限8 ： 依赖特殊硬件的支持； 需要特殊的网络拓扑结构。而在无线传感器网络中引入移动节点，可以增强其功能。如文献9 通过将几个未知节点移动到网络节点密度相对稀疏的区域以弥补节点密度分布不均匀的不足。文献9 提到利用移动参考节点和RSSI(接收信号强度指示 方法对未知节点进行定位，但是在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得RSSI 技术在实际应用中仍然存在困难。尤其是节点对能耗，体积等要求严格时，更多的时候并不能应用这种基于测距

27、的定位技术。免测距的定位算法不需要测量节点间的距离，而是利用距离矢量路由、网络连通情况或者GPS 定位等思想提出的一种分布式定位方法，无需测距，这无疑降低了组网成本。但由于没有相应的硬件测距支持，定位存在一定程序的误差，当网络中存在障碍物时，节点间的欧氏距离会因为弯曲路径而产生较大的误差，精度也相应的降低10 。因此如何提高这种免测距定位算法的精度也成为了一个研究的热点方向。1.2 国内外研究现状基于移动信标的定位算法是近年来的研究热点。由于网络定位算法大多依赖于信标节点的密度，网络的联通性。而信标节点的造价数倍甚至十几倍于普通节点，所以其定位成本较高。而移动信标节点通过引入一个可在网络中漫游

28、移动的节点来广播自己的位置信息构成虚拟信标，从而可以降低定位成本，提高定位效率。所以移动信标的定位算法近来成为新的研究热点，国内外许多学者进行了许多的研究，基于移动信标的定位算法主要研究问题是如何将移动信标与现在的定位算法结合，研究构造的虚拟信标的动态选择算法及移动信标的移动路径的规划。为此，国内外有许多学者把移动信标与经典的质心定位算法、APIT 定位算法及DV-Hop 定位算法等相结合来改进这些定位算法。而质心定位算法及DV-Hop 定位算法因为无需测距有着更多的优势也得到更多的研究。无需测距（range-free ）的定位算法不需要直接测量距离信息，而是根据网络的连通性确定网络中节点之间

29、的跳数，同时根据已知位置参考节点的位置等信息估计每一跳的大致距离，然后估出节点在网络中的位置10 。典型的无需测距的定位算法有DV-Hop 定位算法，APIT 定位算法、质心定位算法、Amorphous 定位算法等，它们所需的网络模型都是由参考节点和未知位置的节点组成。通过移动信标，或者说移动信标来对整个网络的未知节点进行定位的方法是最来兴起的一种新的定位方法，将节点装载在移动机器人上或是进行节点撒播的飞行器上，并且该节点装有GPS 或其他定位装置，这样就构造了移动信标11 。它可以在移动的过程中实时获得其当前的位置信息。通过移动信标来定位的主要思想是：移动信标在“感兴趣的区域内（Region

30、 of interest，简称ROI ）”11 移动的过程中，不断的广播包含其当前位置信息的分组，在其通信半径内的节点将接收到这些广播分组，当未知节点接收到三个或者三个以上的与其距离为R 的位置信息时，就可以利用三边测量法或极大似然估计法7 计算该未知节点的位置。国内外对于移动信标的定位方法及信标的移动路径的规划研究处于起步阶段，相关的文献并不多，提出的算法也不够成熟，文献11 和11 提出的定位方法只需要一个可以移动的信标，其中文献11 利用TOA 测距技术和质心法来计算待定位节点位置，文献11 不需要复杂的测距技术，而是通过信标的不断运动并利用几何限制关系来计算待定位节点位置。文献12 则

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

32、op 定位算法的基础上将移动信标构成的虚拟信标来计算平均跳距离并结合跳数信息来对未知节点定位，通过规划优化的路径来提高定位效率。对于移动信标的移动路径的规划也是一个重要的问题，本文进行了初步的研究。当采用移动信标在网络中移动来广播定位信息时，移动信标的移动路径及广播时间的选取，则很大程序上决定了网络定位的能量消耗及定位的效率。故研究信标的移动路径规划，使网络中的节点以最小的代价获得足够多用于自身定位的信息成为一个重要的研究内容。目前国内外主要的路径规划均为静态的路径，研究如何使移动节点的移动轨迹可以尽量覆盖网络区域。这样的算法显然不能最大限度的节约节点的能耗，对于严格要求能源的传感器网络节点来

33、说，必然需要更为优化及适用于当前网络的路径规划算法来使节点移动路径尽可以少，减少广播的信息来减少网络节点的通信消耗。根据现有的路径规划方法，可以把路径的规划分为静态和动态规划，静态的路径规划与网络的连通状况无关，根据需要定位的ROI 区域，规划以尽可能短的路径覆盖区域为目标，目前静态的路径主要有随机移动模型，高斯马尔可夫移动模型，螺线移动模型和SCAN 移动模型。而国外有根据网络的联通状况来进行路径规划的动态算法，文献12 提出几条最优路径的选择原则，本文主要进行动态路径优化研究。1.3 本论文的主要研究内容与结构针对无线传感器网络基于信标节点的无需测距定位算法精度低，定位效率低的情况，本文提

34、出基于移动信标优化路径的无线传感器网络节点定位算法。研究的内容主要如下：1、分析归纳常用的无需测距的定位算法和基于信标的定位算法，研究基于信标的定位算法的定位机制，研究利用移动信标的信息来进行定位计算。2、提出基于移动信标改进的DV-Hop 定位算法，该算法在DV-Hop 定位算法的基础上，利用一个移动的信标节点在网络中按预定的路径移动并不断的广播自己的位置信息，形成多个虚拟信标，未知节点采用加权处理的方法计算平均跳距及其与各虚拟信标的距离，最后利用三边测量法计算未知节点的位置信息，实现节点精确定位。并研究移动信标的动态选择算法来选择能获得最大计算精度的移动信标节点进行定位计算。仿真证明，相对

35、于DV-Hop 算法，基于移动信标改进的DV-Hop 定位算法降低了定位的成本和布网的复杂度，提高节点定位的精度和效率。3、结合基于移动信标改进的DV-Hop 定位算法，提出了基于ROI(region of interest 的移动信标的路径规划方法，并把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径，提高算法的定位精度，减少算法定位过程的通信开销，提高算法的效率。文章结构层次安排如下：第1章 阐述了本课题的研究背景、研究意义及项目来源。通过对国内外相关领域的研究现状进行探讨，确立传感器网络定位算法的研究的方向。第2章 介绍了信标节点定位算法的相关工作，阐述了常用的基于移

36、动信标的无线传感器节点定位算法，并分析了这几种常用算法的特点。第3章 研究基于移动信标的无线传感器网络节点的定位算法，将移动信标引入到DV-Hop 定位算法中，提出了基于移动信标的DV-Hop 定位算法和基于移动信标动态选择的改进DV-Hop 定位算法，同时分析了改进算法在特定移动模型下的定位精度。第4章 结合基于移动信标改进的DV-Hop 定位算法，提出了面向无线传感器网络的移动信标的路径规划方法，把图论引入信标移动路径规划，获取针对所处网络连通状况的优化信标移动路径。第5章 在OMNeT+仿真平台上进行无线传感器网络节点算法的仿真，设计移动信标节点的模型和移动模型，并通过仿真论证优化路径对

37、定位算法的影响。第二章 传感器网络常用节点定位算法相关研究无线传感器网络节点定位方法的不同，分成两种定位类型：基于信标节点和不基于信标节点(也有论著将其分为无锚节点和有锚节点的定位算法，信标节点也可称为锚节点 。不基于信标节点的定位方法属于相对定位，基于信标的定位算法可以得出未知节点的绝对坐标。当前绝大多数节点定位算法均假设网络中存在少量信标节点，以实现整个网络的绝对定位。2.1无线传感器网络基于信标节点的定位算法基于信标节点的定位算法在研究集中在移动信标的选择、移动路径、定位计算方法及移动节点的研究。由于信标节点需要移动，其在网络中的作用更为重要，需要根据传感器网络的特点进行移动信标节点的设

38、计及无线传感器网络的应用系统的研究。构建无线传感器网络应用系统，需要考虑网络在应用中的成本、数量、通信方面存在的诸多问题，主要需要考虑以下几个方面：1、低成本：系统必须是低成本，不仅从节点硬件、软件考虑，而且传感器也必须采用相对价格低的产品；2、低功耗：系统中采用普通AAA 电池供电，所以要求网络必须是低功耗的，保证网络的生命周期尽量长；3、实时监测：监测信息需实时传输到管理服务器，方便用户实时查询；4、网关无线通信：由于监测区域的特殊性，不一定存在有线网络，例如：Internet 、有线局域网等，故网关具有把采集的环境信息无线传输到服务器的功能，不受监测区域的影响；5、精度：传感器决定了采集

39、数据的精度，传感器采集数据的精度可以在规定范围内存在一定程度的误差；6、传感器接口灵活：系统根据环境参数的不同采用不相同的接口，传感器的类型也需根据实际需要而定，因此节点的传感器接口需灵活设定。传感器节点主要由低功耗的单片机，无线射频模块以及车载平台等组成，它首先采集各个模拟信号，把模拟信号转化成数字信号，经过单片机处理后，通过无线射频模块把数据传送到汇聚节点。汇聚节点的处理器采用ARM9 S3C2410，它还包括GPRS 模块，无线射频模块，网络接口等，它的功能主要是接收附近所有传感器节点发送过来的数据，并且通过Internet 或者GPRS 模块上传到上层监控软件。无线传感器网络移动节点定

40、位系统的硬件系统需要根据上面所述的要求建立合适的传感器系统，为此设计的传感器移动节点主要由低功耗的微处理器，射频模块，传感器接口，电源模块以及车载平台5部分组成，如图2-1所示，普通节点则没有车载平台。 图2-1传感器移动节点结构Fig. 2-1 Sensor Network Mobile Nodes Structure根据此模型设计制作的移动节点如下图2-2所示。节点采用MSP430低功耗单片机，芯片集成SPI ，IIC ，12位A/D等标准接口，可以通过SPI 接口与射频模块CC2420进行连接，节点还设计了了标准的传感器接口，可以通过接口连接到常用的传感器模块。为了实验方便，节点集成了D

41、S18B20温度传感器，TSL2561光强度传感器。同时，把节点放在车载平台上，实现节点的移动。 图2-2传感器网络节点Fig. 2-2 Sensor Network Nodes黎大鹏在文献12 中研究了基于信标节点动态调整的移动节点的定位算法。对基于锚节点动态调整的传感器网络移动节点定位系统进行了研究，该系统能够实现移动节点的高效率定位。文章分别从嵌入式硬件平台的硬件设计，移动节点定位算法，以及定位系统的程序设计与实现三方面来对该系统进行研究。提出基于VWMC （V oronoi and Weight Monte Carlo Method）的传感器网络移动节点定位算法，该算法在MCL （Mo

42、nte Carlo Localization）算法的基础上加入V oronoi 图和权值分析技术。仿真证明，相对于MCL 算法，基于VWMC 的传感器网络移动节点定位算法提高了移动节点定位的精度和效率。结合基于VWMC 的传感器网络移动节点定位算法以及锚节点动态调整策略，提出了基于锚节点动态调整的传感器网络移动节点定位算法，提高了算法对外界干扰的抵御能力。相对定位通常是以网络中部分节点为参考，建立整个网络的相对坐标系统。绝对定位可为网络提供唯一的命名空间，受节点移动性影响较小，有更广泛的应用领域。但研究发现，在相对定位的基础上也能够实现部分路由协议，尤其是基于地理位置的路由(geo-routi

43、ng，而且相对定位不需要信标节点。在某些无需网络节点绝对位置的应用中，可以采用无信标节点的定位算法来实现整个网络的相对定位。典型的无信标节点的定位算法包含SPA 13 、SDGPS 14 、AFL 14 等定位算法。SPA 算法选择网络中密度最大处的一组节点作为建立网络全局坐标系统的参考点，并在其中选择连通度最大的一个节点作为坐标系统的原点。首先根据节点间的测距结果在各个节点上建立局部坐标系统，通过节点间的信息交换与协调，以参考点为基准通过坐标变换逐步建立全局坐标系统。SPA 算法的主要缺点是网络通信开销太大。SDGPSN 算法在SPA 算法的基础上，提出了基于聚类的定位思想。基本思想:网络部

44、署完后，每个传感器节点开始运行一个随机的定时器，如果与邻居节点相比，节点i 的定时器最先到期且没有收到任何邻居节点的消息，则i 升级为主节点，并向邻居节点广播此消息，所有接收到该消息的邻居节点中止其定时器并成为该主节点的从节点。这些节点构成一个以主节点i 为坐标原点的节点域，并随扫A 择两个与i 相邻的从节点为辅助节点对，构建一个局部坐标系。节点域内的所有其他从节点通过选择适当的辅助节点对来计算其在此局部坐标系中的坐标。然后相邻的节点域依靠两个域的共同边际节点的相关坐标信息，以主节点ID 较小的局部坐标系为参照，进行相邻局部坐标系间的坐标转换，直至建立一个全局坐标系。SDGPSN 算法和SPA 算法相比，通信开销明显降低，这使得它更适于大规模无线传感器网络