硕士论文无线传感器网络定位算法的研究.doc

硕 士 学 位 论 文MASTERS DISSERTATION论文题目 无线传感器网络定位算法的研究A Dissertation in Computer Application TechnologySTUDY ON LOCALIZATION ALGORITHM OF WIRELESS SENSOR NETWORKby Hu YulanSupervisor: Professor Wang XinshengYanshan University2011.12燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文无线传感器网络定位算法的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。作者签字 日期： 年 月 日燕山大学硕士学位论文使用授权书无线传感器网络定位算法的研究系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 保密，在 年解密后适用本授权书。本学位论文属于 不保密。（请在以上相应方框内打“”） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日摘 要传感器节点的位置信息在无线传感器网络的监测活动等应用中起着至关重要的作用。而取得节点位置信息较简便、快捷、精确的方法是通过手动设定或携带GPS定位设备等手段，但通过这种方式获取的成本很高。因此，较好的方法是采用定位算法进行估计。本文将主要研究基于多维标度的无线传感器网络定位算法。首先，本文在查阅大量相关文献的基础上，综述了无线传感器网络的研究背景、研究意义及现状，并介绍了无线传感器网络的结构、特点以及典型的定位算法。其次，介绍了多维标度技术及其在无线传感器网络定位算法中的应用。在分析经典MDS-MAP定位算法的基础上，提出基于Hop-Euclidean的MDS-MAP(D)定位算法。该算法先采用分簇的算法，将大规模网络分成多个具有簇首的局部网络，在局部网络中通过Hop-Euclidean算法计算邻居节点间的欧氏距离来代替MDS-MAP算法中的所使用的最短路径距离，这样不仅提高了定位精度，而且有利于网络的扩展。再次，针对分布式加权MDS定位算法不能适应网络连通度变化、网络拓扑不规则且收敛速度较慢的不足，提出一种改进算法。本文采用的加权机制与邻居选择机制综合考虑1跳邻居数目、节点自身定位精度与测距误差，并且引入最速下降法优化其目标代价函数。最后，采用Matlab仿真平台从定位误差、拓扑结构等方面对提出的两种改进算法进行仿真分析并与原来算法做比较。仿真结果表明，提出的算法在定位精度提高的情况下对不规则、大规模网络有很好的适应性。关键词：无线传感器网络；多维标度；Hop-Euclidean算法；分布式加权；邻居选择机制AbstractLocation information has played an increasingly important role in many applications of wireless sensor networks, such as monitoring activities and so on. The simple, quick and precise way to obtain location information is either to set up manually or to install GPS, which will waste a vast amount of time and human resources. A better way to obtain location information is to use the localization algorithm.In this paper, we mainly focuse on the research of wireless sensor network location algorithm based on multi-dimensional scaling.Firstly, the research background, significance and status for WSN are summarized in this paper based on large amount of related literatures. And the framework, characteristics and typical localization algorithms of wireless sensor networks are introduced.Secondly, in this paper, we give details of classical multidimensional scaling and its application in wireless sensor network location algorithm. Based on the analysis of the classic MDS-MAP of the location algorithm, this paper presents Hop-Euclidean based MDS-MAP(D) location algorithm, which uses the clustering method to divide large-scale network into several local networks with cluster head, and in the local positioning, using the Hop-Euclidean algorithm in place of the shortest path distance to calculate Euclidean distance between the nodes neighbor. Obviously, this algorithm not only increases the positioning accuracy, but also is beneficial to the expansion of the network.Thirdly, in this paper, we propose an improved algorithm, which makes up for the shortage of the distributed weighted multi-dimensional scaling localization algorithm that can not adapt to the network connectivity change, the irregular network topology and the convergence speed is slow. We use the weighted mechanism and neighbor choice mechanism that comprehensively considerate the number of one hop neighbors, the node positioning precision and the location error. We also introduce the steepest descent method to ptimize the goal cost function.Lastly, the two improved algorithms are tested by simulations via Matlab according to localization error, network topology and so on. Simulation results show that these algorithms proposed in this paper improve the localization accuracy and are more adaptable to the irregular topology, large-scale network.Keywords: Wireless Sensor Network; Multi-dimensional scaling; Hop-Euclidean algorithm; Distribution weighted; Neighbors choice mechanism目 录摘 要IAbstractIII第1章 绪 论11.1 研究背景及研究意义11.2 国内外研究现状21.3 研究内容及主要工作41.4 论文结构安排5第2章 无线传感器网络及其定位技术72.1 无线传感器网络概述72.1.1 无线传感器网络体系结构72.1.2 无线传感器网络的特点82.2 定位技术的相关概念及术语92.3 基于测距技术的定位102.4 无需测距的定位算法112.4.1 DV-Hop算法112.4.2 Euclidean定位算法122.4.3 Hop-Euclidean定位算法132.4.4 MDS-MAP算法132.5 本章小结13第3章 基于MDS-MAP(D)定位算法的改进153.1 引言153.2 多维标度技术和MDS-MAP定位算法153.2.1 多维标度技术基本原理153.2.2 MDS-MAP定位算法163.3 基于Hop-Euclidean的MDS-MAP(D)定位算法173.3.1 改进算法的相关研究工作173.3.2 分簇算法183.3.3 局部定位203.3.4 求解全局坐标233.3.5 基于Hop-Euclidean的MDS-MAP(D)算法定位过程253.4 本章小结25第4章 分布式加权多维标度算法的改进274.1 引言274.2 分布式加权多维标度算法274.2.1 分布式加权多维标度算法概述274.2.2 dwMDS(G)算法定位过程284.3 dwMDS(G)算法的改进284.3.1 改进算法的相关研究工作284.3.2 邻居选择机制294.3.3 加权机制304.3.4 优化目标代价函数304.3.5 改进算法的定位过程324.4 本章小结33第5章 仿真实验与性能分析355.1 仿真平台介绍355.2 网络部署365.3 性能评价指标375.4 仿真结果及分析385.4.1 MDS-MAP算法及改进算法分析385.4.2 dwMDS(G)算法及改进算法分析425.5 本章小结47结 论48参考文献50攻读硕士学位期间承担的科研任务与主要成果53致 谢54作者简介55第1章 绪 论1.1 研究背景及研究意义随着科技发展步伐的加快，如今人类所处的时代是一个充满挑战和机遇的信息时代。因而，作为获取信息、传递信息的最基础的网络无线传感器网络的研究和应用发展非常迅猛。目前非常热门的两个概念物联网与智慧地球，其核心技术就是无线传感器网络。无线传感器网络WSN(wireless sensor network)1,2是指由大量成本低廉的，具有感知能力、无线通信能力、计算能力的传感器节点构成的网络。它主要针对缺乏或无法建立通信基础设施的区域，通过大规模的、具有一定定位能力、通信能力、数据处理能力的传感器节点建立联系，提供数据。这种网络系统在国家安全、国防军事、医疗卫生、环境监测、制造业、交通管理、灾难拯救、空间探索等领域3,4有着其他技术无可比拟的优势，能够在任何时间、地点、环境条件下获取可靠而有用的信息。在美国商业周刊和MIT技术评论的有关预测未来技术发展的报告都将WSN列入了21世纪最有影响力的21项技术和改变世界的10大技术之中。全球未来的三大高科技产业中最受重视的也是WSN5。通过将大量传感器节点分布于要监测的区域中来构建WSN，从而使得人类跟客观世界间相互通信的方式有所改善。其中传感器节点的位置信息是采集信息中不可缺少的，确定获取信息的节点所在的位置是提供监测事件位置信息的前提，在WSN的应用中起着至关重要的作用6,7。其一，节点自身位置的缺点是WSN中的很多特定应用的基础，在传感器节点的位置信息未知的情况下，所获取的传感器节点感知的数据是毫无意义的8。比如在军事应用中，对敌方军事目标的定位可以决定是否需集中火力进行打击；在森林中发生火灾时，监测发生火灾的具体区域与火势情况可以决定是否需要增加军力救助等等。其二，WSN的运行和管理仍需有节点位置信息的协助。例如计算网络覆盖范围、控制网络的负载均衡、对外部目标的定位和追踪、基于地理信息的路由、资源的有效配置等。因此，节点定位问题已成为WSN的一个至关重要的研究课题。毫无疑问，获得节点位置信息的直接方法是利用全球定位系统GPS(Global Positi-oning System)。GPS是目前使用的最著名的定位系统9，用GPS系统获取传感器节点位置信息，具有较好的实时性、较强的抗干扰能力、较高的定位精度等优点。但是，传感器节点成本低、电池供电、计算能力和通信能力有限，使得GPS不适用于低成本自组织的无线传感器网络，因为它没有考虑布网成本和能量消耗问题。根据WSN的特点，传感器节点的位置信息应该以最小通信开销和最低的硬件代价来获取。所以，实现WSN节点定位不能全依赖GPS系统来完成，只能是通过该系统获取少数节点的位置信息再通过其他的定位技术来实现其他大量节点的定位。近年来，不少研究者们在WSN定位技术方面已经取得了一定的研究成果，但是目前仍处于初级阶段，还有好多问题没有彻底解决，有一定的局限性。1.2 国内外研究现状由于WSN的应用前景非常广阔，它作为21世纪影响力巨大的全新技术之一，许多国家学术界、军界和工业界研究者们在其有关的研究中都注入了大量的人力与物力。传感器网络最初来源于美国先进国防研究项目局DARPA(Defense Advanced Research Projects Agency)的一个研究项目10,11。WSN的研究是20世纪90年代开始的，该网络最早是由军事领域的有关人事提出的。最初受客观条件的限制，传感器网络只能应用于军事领域的一些重要项目中，对其推广与发展是很困难的。后来随着相关学科的不断发展，WSN逐渐转向民用，在许多领域得到了大量研究者们的广泛而深入的研究。近年来随着无线通信技术、片上系统、MEMS的发展与进步，WSN的理想蓝图逐一实现，其应用越来越广泛，从而得到了研究者们的极度关注。WSN中的定位技术是大多数有关WSN应用的支撑技术和关键技术之一。该技术是指WSN通过特定系统或算法来获取传感器节点的位置信息。这种自组织网络定位包括两种定位，一种是节点自身定位，另一种是目标定位，前者是后者的基础。进入21世纪，军界、学术界和工业界都极其关注有关传感器网络技术的研究与发展。从2000年开始，许多有关WSN节点定位研究成果的报告开始在国际上陆续出现。2000年，Nimpama Bulusu教授等人提出了一种无需测距的定位算法质心算法12，此定位算法是基于网络连通性通过节点之间相互发送信息获得节点间的跳数信息进行定位的；适合部署在室内的传感器节点定位的RADAR系统是由微软公司的Bahl P等人开发出的唯一一种根据IEEE802.11网络标准设计的定位系统13；加州大学伯克利分校的Doherty等人，引入了“凸集”这一概念，将整个网络模型看作一个凸集，那么就可以把传感器节点的定位问题看作一个凸约束优化问题14，其中的几何约束是传感器节点间的通信连接；同年，麻省理工学院的Priyantha N也开发出了一种室内定位系统Cricket系统15,16。此系统主要是用于获取移动或静止的传感器节点所在房间的具体位置信息。2001年，Srdjan Capkun等人提出了一种针对无基础设施的移动无线网络的相对定位算法17；2002年8月，I.F Akyildiz等人发表了以“A Survey on Sensor Networks”为题的综述性学术论文以来，又一次激发了学术界对WSN的研究兴趣。2003年，Tian He等人提出了一种采用求解约束集合进行定位的APIT算法18；哥伦比亚大学的Shang Yi等人在Ad.Hoc网络时引进了MDS技术，提出了MDS-MAP，MDS-MAP(P)，MDS-MAP(C)等几种集中式定位算法19-22。随着集中式定位算法的研究趋于成熟及WSN规模的不断扩大，如今大量的科研工作者们致力于研究分布式的定位算法。2003年，Niculescu教授等人提出了一系列分布式定位算法，包括DV-Hop，DV-Distance，DV-Coordinate等算法23。2004年，麻省理工学院的RVSN和NMS两个研究小组在“分布式传感器网络的定位与追踪”项目中提出了一种分布式定位算法，该算法是通过节点间距离的估计值获取节点的二维坐标信息，有较高的覆盖率24。2006年，Costa J A, Patwari N等人提出了dwMDS(G)算法25，该算法最终是通过优化加权的目标代价函数计算出节点的坐标。近年来，随着科学技术的发展与WSN实用价值的不断提升，国内的一些高校和研究所也开始对有关WSN的理论和应用的研究工作26,27，2007年，在有关集成技术的国际会议上提出了一种自适应邻居选择的分布式定位算法28。2008年，北京交通大学的马震等提出了一种分布式的算法MDS-MAP(D)29。本文主要研究基于多维标度分布式的定位算法。目前已有不少研究者对这种定位算法作了多方面的改进，在分布式的多维标度定位算法的改进研究中，比如MDS-MAP(P)定位算法，是Yi Shang等人通过对经典MDS-MAP定位算法分析，发现当传感器节点不是均匀分布或者WSN的拓扑结构不是规则形状时(如C形状)，若节点之间相隔太远，最短路径长度跟欧氏距离是有很大差异的，且无法用线性关系来描述它们之间的关系。于是，针对MDS-MAP算法的不足，引入了“补丁”这一概念，提出了MDS-MAP(P)定位算法；文献30是一种基于非度量多维标度技术的定位算法，通过多次迭代来不断修正距离和相异性间的单调关系的过程。文献31是利用Euclidean算法改进经典MDS-MAP算法中估算最短距离的方法，但因为Euclidean算法由于直接测量两节点之间的距离时，受环境因素影响较大，所以使得该算法的定位精度降低了。但是几种算法所改进的只是在计算规模方面对算法进行了改进，并没有解决MDS-MAP所存在的全部问题。总而言之，提高对WSN研究的推广不仅会对人们未来的生活产生巨大的影响，而且也给研究者们带来巨大的挑战。然而虽然经过这些年学术界、军界及商业界的不断努力，目前无线传感器网络节点的自身定位问题在一定程度上能够解决，但仍有许多问题没有得到有效合理的解决，比如，通过测距技术获得的节点间距离仍有一定的误差、在定位过程中所需的通信开销仍比较大等问题。因此，我们仍需进一步去探索和研究WSN节点的定位问题。1.3 研究内容及主要工作在WSN的应用中，绝大多数情况下需要有节点位置信息，否则采集到的数据将没有任何意义，尤其是关于环境监测、桥梁结构变化监测、管道泄漏监测等，发生地点的地理位置信息非常重要。位置信息不仅可以用于监测事件发生的地点，还可用于跟踪目标、预测目标轨迹、协助路由及网络拓扑管理等。因此，WSN的节点定位技术有很大的研究价值，是WSN中重要的研究方向之一。本文主要研究的内容是基于多维标度技术的WSN定位算法。首先，重点分析研究了MDS-MAP定位算法，经过分析发现，经典的MDS-MAP定位算法在节点间的测量距离没有误差的情况下，通过MDS技术可以计算出准确的节点位置坐标。但是，由于该算法采用的是节点间的最短路径代替节点间的欧式距离，而很明显这两者有很大的差别，尤其是当节点间的连通度较小时，其表现更为明显；此外，该算法不适用于大规模密集型网络，因为在这样的网络部署下，节点间距矩阵会相当庞大，而且每当有节点增加或减少的时候，该算法都得重新开始计算，这样就会增加其计算复杂度，给本来能量就很有限的传感器节点增加了很大的负担，最终导致传感器节点还没完成定位就已经能量耗尽，无法完成任务。本文主要是针对MDS-MAP算法这两方面的不足提出了一种基于Hop-Euclidean的MDS-MAP(D)定位算法。提出的算法中加入了分簇的思想，先将大规模WSN采用本文提出的分簇算法划分为多个局部网络，然后各个局部网络中采用Hop-Euclidean算法获取节点间的距离，通过MDS方法计算出节点的局部坐标，最好通过线性转换将局部坐标转换为全局坐标。其次，重点分析研究了分布式加权多维标度定位算法，经过研究发现，该算法由于采用的是高斯加权机制和自适应2步邻居选择机制，造成离未知节点近的节点定位误差不断扩大；此外，如果网络稀疏时，会有部分节点的1跳邻居节点很少，这样就会使得这些节点无法实现定位。本文主要针对分布式加权多维标度定位算法这两方面的不足，提出了一种改进方案。本文提出的改进算法中采用的加权机制与邻居选择机制都综合考虑了节点间距离的远近与参与定位的邻居节点的定位误差等因素，同时为了加快算法的收敛速度，引入了无约束最优化中简单且收敛速度较快的最速下降法对其目标代价函数进行优化。最后，在MATLAB仿真平台上对改进的两种定位算法进行了仿真，并与其原算法做了比较。经过分析和仿真结果表明，改进的MDS-MAP定位算法在定位精度提高的情况下，对不规则网络和大规模密集型网络有更好的适应性；改进的分布式加权多维标度定位算法有效抑制了较大定位误差在网络中扩散，而且对不规则网络和大规模稀疏型网络都有很好的适应性。期望本文的研究工作能够给无线传感器网络的未来研究带来一定的帮助。1.4 论文结构安排本文是围绕着无线传感器网络的定位算法进行的，论文的结构安排如下。第2章简述了无线传感器网络的体系结构和特点，介绍了节点定位中用到的一些基本概念及术语，并对计算节点位置的基础方法及与本文相关的经典定位算法作了详细的阐述和分析。第3章详细阐述了多维标度技术在无线传感器网络定位算法中的应用及MDS-MAP定位算法，着重对MDS-MAP定位算法的不足之处做了较全面的分析，主要针对其有较大的距离误差及不适用于大规模密集型网络两方面的不足，提出了一种基于Hop-Euclidean的MDS-MAP(D)定位算法，并对其进行了详细的阐述。第4章 主要针对加权分布式多维标度定位算法的不足提出了一种改进方案。概述了加权分布式多维标度定位算法的特点与定位过程，同时主要针对其加权机制和自适应2步邻居选择机制的不足做了较全面的分析，接下来对改进的邻居选择机制与加权机制做了详细的阐述，并给出了采用最速下降法对其目标代价函数进行优化求解的具体过程。第5章用仿真实验验证了两种改进算法的有效性和可行性。最后对本文的研究工作做了总结和展望。第2章 无线传感器网络及其定位技术2.1 无线传感器网络概述随着科学技术的不断发展，如今的我们正处于信息时代。因而，传感器技术作为信息获取最基本且最重要的技术32，也在不断发展。传感器获取信息的技术已经从过去的单一化模型逐渐趋向集成化、网络化及微型化发展。WSN的发展将有助于物联网等前沿学科全面提升社会生产生活中信息互通性、信息感知能力和智能决策能力等，进而增强整个系统的性能。WSN是环境感知与监控领域的一场革命。WSN作为一个全新且热门的研究方向，给科技研究者们提出了许多在工程技术等层面的挑战性课题。2.1.1 无线传感器网络体系结构(1)WSN结构 WSN的结构33如图2-1所示，WSN系统通常由传感器节点(sensor node)、任务管理节点(task manager node)和汇聚节点(sink node)三部分组成。其中，传感器节点相对于汇聚节点，其通信能力、存储能力和处理能力通常较弱，而且其能量十分有限(通常利用电池供电)。图2-1 无线传感器网络体系结构在监测区域(sensor field)的内部或其附近随机部署大量传感器节点，这些节点以自组织方式组建成一个无线网络。其中的各个传感器节点都具有收集信息及监测数据的功能，而且可以将检测或收集到的数据传播给其他传感器节点，这样在传播的过程中就会出现“冗余”现象即有可能多个节点同时处理一个数据，因此都应先将这些被处理过的数据传输给汇聚节点，由汇聚节点进行相应的处理。最后，由汇聚节点直接通过通信卫星或Internet传达给管理节点(即观察者)34。(2)传感器节点结构 通常传感器节点是一个由采集模块(传感器，AC/DC转换器)、无线通信模块(主要有收发器)、能量供应模块(电池、DC/DC能量转换器)、控制模块(微处理器、存储器)以及其它辅助可选功能模块等部分组成的微型的嵌入式系统35，如图2-2所示。其中，采集监测区域内信息和转换其数据是由采集模块完成；与其他节点进行无线通信并接收与转发所采集的数据及控制信息是由无线通信模块完成；提供传感器节点运行所需的能量能量供应模块，通常采用微型电池；存储和处理本身采集的数据及其他节点发来的数据由控制模块完成36。图2-2 传感器节点体系结构2.1.2 无线传感器网络的特点WSN有很多地方与无线自组网络的很相似，同时也存在着很多技术方面的区别37。WSN是以数据为中心的，为了减少网络的流量、降低功耗同时提高系统利用率，其数据是尽可能早的由系统按照实际需要进行处理的。而传输数据才是无线自组网络的主要目的，它并不太关注数据的处理。因此，为Ad-Hoc网络设计的一部分协议和算法是不能够满足WSN应用的需求。除了这些，WSN还具有以下一些与无线自组网络不同的特点。(1) 网络规模大且部署密集 由于WSN主要是用来采集数据，而且采集的数据越准确完整越好，因此，一般需要将大量传感器节点密集部署在所要监测的区域中。系统的工作质量并不是通过提升单个设备的能力提高，而是靠大量冗余节点的协同工作来提高的。(2) 网络节点拓扑变化频繁 WSN是动态网络，由于在WSN中传感器节点的移动性和能量耗尽会使得节点失效或出现故障，因此WSN中随时有可能加入新的传感器节点进行替补，由此看来WSN的拓扑结构的改变是不可避免的。(3) 应用相关 WSN的设计有多种多样，只能根据其具体的应用场合进行设计比如有的需要获取非常准确的信息并不关心它所花费的时间，有的则需要对二者折中考虑，这样一来在设计WSN时的侧重点就不一样，那么其网络协议和软、硬件平台一定会有所不同。因此，针对具体应用来研究传感器网络技术，是WSN设计不同于传统网络的显著特征。(4) 寻址以数据为中心 WSN只关心数据本身，比如事件发生的时间、地点即位置，并不关心数据是哪个节点监测或采集到的。除了特殊需要，由于通常部署传感器节点的环境都比较恶劣，人类无法抵达只能通过飞机等方式进行撒播，而且用户也不需要知道每个节点的具体身份号，因此可采用以数据为中心的组网方式。(5) 网络可靠性 通常部署传感器节点的环境都比较恶劣甚至人类无法抵达，因此，传感器节点必须结实耐用，同时能够适应各种各样的恶劣环境。除此之外，为了使监测到的数据不被窃取而且能够获取较准确的而不是被篡改后的数据信息，WSN通信的保密性和安全性也是至关重要的，故而要想设计一个好的无线传感器网络的必须考虑其鲁棒性和容错性。(6) 节点资源有限 传感器节点资源包括两方面：其一是计算能力，其二是节点的能量。传感器节点由于受体积、价格及功耗的制约，其计算能力和内存空间是非常有限，与普通计算机相比会差的多，由于受这些因素的约束，因而为其设计的程序等都不能太复杂。此外，传感器节点的能力决定着传感器网络的寿命，而传感器节点通常部署在人们很难抵达的区域，为其更换电池是很不现实的，故而节点的能量是非常受限的。2.2 定位技术的相关概念及术语(1) WSN定位的基本概念在WSN中，节点定位(node localization)是指根据若干个位置已知的节点和节点间的连通性采用一定的方式获取WSN中其余节点的绝对(相对于地理经纬度)或相对位置信息。在WSN节点的定位技术中，根据节点是否已知自身的位置，将传感器节点分为两类：一类是位置已知的信标节点(beacon node)，另一类是需要获取其位置信息的未知节点(unknown node)。信标节点是指通过手动设置或携带GPS定位设备等手段获得自身的精确位置信息的传感器节点，其在WSN的节点中所占的比例是很低的。信标节点是未知节点定位的参考点，未知节点是根据信标节点的位置信息利用节点间的连通约束等通过一定技术来确定自身位置。(2) 基本术语邻居节点(neighbor node)：无线传感器网络中，在传感器节点通信半径内，可直接通信的所有其他节点称为此传感器节点的邻居节点。跳数(hop count)：两个节点之间建立通信需要经过的跳段总数，称为两点之间的跳数。跳段距离(hop distance)：两个节点之间进行通信所需的各跳段距离之和。网络密度(network density)：一个传感器节点通信时所覆盖区域内的节点平均数目，常记为。测距误差(range error)：节点间通过测距技术等估算所得的距离和其实际几何欧式距离的差值与节点的通信半径的比值。定位误差(position error)：通过定位算法计算出的坐标和其实际坐标的差值与节点的通信半径的比值。网络连通度(network connection degree)：所以传感器节点的邻居节点数的平均值。定位覆盖率(coverage rate)：无线传感器网络中，能确定坐标位置的未知节点占总节点数的比例。2.3 基于测距技术的定位基于测距技术的定位(Range Based)38是通过一定的方式或技术获得相邻节点之间的实际距离或方位进行定位，要求节点具有测距能力。目前WSN定位中，可以使用多种测距技术，如测量无线电、红外线、激光信号强度，测量无线电信号或超声波等到达的时间，测量无线电信号或超声波等到达的时间差等。基于测距技术的定位一般分为以下几个阶段：(1) 测距阶段 未知节点先采用上面介绍的测距方法获得自身与其邻居节点之间的距离或者角度信息，然后通过一定的方式利用自身与其邻居节点之间的距离或角度，计算出自身到离其最近的信标节点的距离或者角度，可以直接计算其直线距离，也可以用两者间的跳段距离来近似代替其直线距离。(2) 定位阶段 未知节点通过上面的测距阶段计算出与其3个(或3个以上)邻居信标节点间的距离(或角度)后，采用三边(或三角)测量法、极大似然估计法等方法计算出自身的位置坐标。(3) 修正阶段 采用迭代或递归优化等数值分析中的优化方法对求得的节点坐标进行求精，提高其定位精度。2.4 无需测距的定位算法无需测距的定位算法仅需依据网络连通性等信息就可得到未知节点在网络中的位置坐标，这样就会使得节点硬件的要求降低，从而使其更加适用于大规模WSN。无需测距的定位算法的定位性能几乎不会受环境的影响，即使其定位精度会有所下降，也可满足某些应用的需要。基于本文的研究重点与三种无需测距定位算法：DV-Hop算法、Euclidean定位算法和MDS-MAP算法有关，接下来具体介绍这三种经典的定位算法。2.4.1 DV-Hop算法DV-Hop算法39的基本思想是未知节点先计算到信标节点的最少跳数，并估算出平均每一跳的距离，然后用该值乘以最少跳数就可计算出与信标节点间的距离，当未知节点获得与三个或三个以上信标节点的距离时，则执行三边测量定位。如图2-3所示，已知信标节点与、之间的距离和跳数，计算得到校正值(即平均每跳距离)。假设节点从获得校正值，则与、之间的距离分别为:;:;:，然后根据三边测量法计算得出节点的位置坐标。图2-3 DV-Hop定位算法举例DV-Hop算法对节点硬件要求低，实现简单，其不足是以节点间最小跳段距离替代节点间的直线距离，由于通常节点间的最小跳段距离与其间的直线距离是有差别的，因而最终会有一定的定位误差。2.4.2 Euclidean定位算法Euclidean算法40是一种计算与信标节点相隔两跳的未知节点位置坐标的方法。该算法核心思想如图2-4所示。图2-4 Euclidean定位算法示意图假设，为未知节点，为信标节点。通过RSSI技术直接测得节点间距，和。节点与，相邻。在四边形中，己知所有边的长度与对角线的长度，则由三角形中的余弦定理即可通过式(2-1)、式(2-2)、式(2-3)计算出的长度(未知节点与信标节点间的距离)。 (2-1) (2-2) (2-3)使用这种方法，当未知节点获得与三个或三个以上信标节点距离后就可计算出自身的位置坐标。Euclidean定位算法的优点是与信标节点相隔两跳的未知节点均可实现定位，但其条件比较苛刻，从而该算法的可用性会受到一定的约束，此外该算法受环境影响大，这样会导致其定位误差增加。2.4.3 Hop-Euclidean定位算法Hop-Euclidean算法41是在Euclidean定位算法基础上，融入距离矢量路由和迭代循环的思想，设计出的一种定位算法。该算法针对Euclidean定位算法只有未知节点拥有三个以上邻居节点且这些邻居节点都必须彼此相邻才能统计出到信标节点的跳数的问题，通过融入距离矢量路由的思想，并且有选择性地把已定位节点逐渐升级为信标节点，以此来提高算法的定位精度的同时也扩展了算法的可用性。虽然Hop-Euclidean算法能够获得较准确的节点间距，但是由于采用的是最大似然估计法进行估算节点的位置，而这种估计方法本身存在