无线传感器网络定位算法

. . . . 论文题目 无线传感器网络定位算法的研究作者 胡玉兰学科专业 计算机应用技术指导教师 王新生 教授2011年12月11 / 69中图分类号：TP393学校代码：10216UDC：621.3密级：公开无线传感器网络定位算法的研究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 speedis 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 adaptableto 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(DefenseAdvancedResearchProjectsAgency)的一个研究项目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.1DV-Hop算法DV-Hop算法39的基本思想是未知节点先计算到信标节点的最少跳数，并估算出平均每一跳的距离，然后用该值乘以最少跳数就可计算出与信标节点间的距离，当未知节点获得与三个或三个以上信标节点的距离时，则执行三边测量定位。如图2-3所示，已知信标节点与、之间的距离和跳数，计算得到校正值(即平均每跳距离)。假设节点从获得校正值，则与、之间的距离分别为:;:;:，然后根据三边测量法计算得出节点的位置坐标。图2-3 DV-Hop定位算法举例DV-Hop算法对节点硬件要求低，实现简单，其不足是以节点间最小跳段距离替代节点间的直线距离，由于通常节点间的最小跳段距离与其间的直线距离是有差别的，因而最终会有一定的定位误差。2.4.2Euclidean定位算法Euclidean算法40是一种计算与信标节点相隔两跳的未知节点位置坐标的方法。该算法核心思想如图2-4所示。图2-4 Euclidean定位算法示意图假设，为未知节点，为信标节点。通过RSSI技术直接测得节点间距，和。节点与，相邻。在四边形中，己知所有边的长度与对角线的长度，则由三角形中的余弦定理即可通过式(2-1)、式(2-2)、式(2-3)计算出的长度(未知节点与信标节点间的距离)。 (2-1) (2-2) (2-3)使用这种方法，当未知节点获得与三个或三个以上信标节点距离后就可计算出自身的位置坐标。Euclidean定位算法的优点是与信标节点相隔两跳的未知节点均可实现定位，但其条件比较苛刻，从而该算法的可用性会受到一定的约束，此外该算法受环境影响大，这样会导致其定位误差增加。2.4.3Hop-Euclidean定位算法Hop-Euclidean算法41是在Euclidean定位算法基础上，融入距离矢量路由和迭代循环的思想，设计出的一种定位算法。该算法针对Euclidean定位算法只有未知节点拥有三个以上邻居节点且这些邻居节点都必须彼此相邻才能统计出到信标节点的跳数的问题，通过融入距离矢量路由的思想，并且有选择性地把已定位节点逐渐升级为信标节点，以此来提高算法的定位精度的同时也扩展了算法的可用性。虽然Hop-Euclidean算法能够获得较准确的节点间距，但是由于采用的是最大似然估计法进行估算节点的位置，而这种估计方法本身存在一定误差，这样就会扩大节点的定位误差。2.4.4MDS-MAP算法MDS-MAP算法42是一种不论传感器节点是否具有测距能力都可以实现定位的集中式定位算法，而且依据实际情况既可以实现相对定位，也能够实现绝对定位。该算法采用了一种源自心理测量学和精神物理学的数据分析技术多维标度技术MDS(Multi-dimensional scaling)，这种技术通常用于探索性的数据分析或信息可视化。该算法可分为3个步骤。第一，若传感器节点具备测距能力，则直接通过测距技术所得的传感器节点间的距离值。否则使用最短路径算法，生成多维标度技术MDS所需节点间距矩阵；第二，对节点间距矩阵利用多维标度技术计算出各个节点在整个网络中位置的相对坐标；第三，如果拥有足够数量的信标节点，则可将相对坐标系统经过线性变换转换成相应的绝对坐标系统。MDS-MAP算法是一种集中式定位算法，通常会增加传感器节点的计算量与通信量，从而会消耗大量的能量，而传感器节点的能量有限，这样就会造成节点在中途能量耗尽无法实现最终的定位。此外，当传感器网络中的节点密度减小或网络拓扑结构不规则时，其节点的定位误差会增大，甚至会有大量的传感器节点无法实现定位。2.5 本章小结本章主要是对无线传感器网络与其定位技术作了介绍。首先，主要从无线传感器网络体系结构和传感器节点结构两方面阐述了无线传感器网络的体系结构；第二，介绍了无线传感器网络的特点；第三，阐述了无线传感器网络定位技术的基础知识，其中包括节点定位的基本概念、术语与定位算法的分类；最后，重点介绍了现有的几种与本文研究相关的经典定位算法：DV-Hop算法、Euclidean定位算法、MDS-MAP算法，同时对这三种算法的优缺点作了分析。第3章基于MDS-MAP(D)定位算法的改进3.1 引言随着信息化时代的到来，目前WSN商业化应用也不断兴起，同时涌现出大量的科研工作者热衷于对无线传感器网络节点定位技术的研究，于是现已有许多种定位算法，但是各种不同的定位算法适用的环境都不尽一样。比如，DV-Hop算法是适合于硬件配置较低、对节点定位精度要求不太高的应用；而Euclidean定位算法是适合于节点具有测距能力的、且环境中的噪声相对较小的应用场合下使用；MDS-MAP算法是适合于网络连通度相对比较大、且传感器节点的能量充足、计算能力较强的小规模拓扑规则的无线传感器网络。所以定位算法的设计都需要根据实际应用的环境与硬件条件等要求来进行。通过研究分析发现，MDS-MAP算法是使用节点间的最短路径距离替换其实际几何距离，但通常最短路径距离比实际几何距离小，这样就会扩大节点间的几何距离，最终会导致较大定位误差。此外，MDS-MAP算法是采用MDS技术根据距离矩阵进行求解对应节点的位置坐标，但通常距离矩阵都比较庞大，则会导致其计算复杂度较大，且当节点增加或移动时，需要重新求解，这将会严重阻碍网络的扩展。为了实现大规模无线传感器网络中节点的定位，本文采用分簇算法将大规模网络划分为多个区域同时在各个区域中选出各自的簇头节点，然后采用Hop-Euclidean算法计算出每个区域节点之间的距离，再让各个簇头节点采用多维标度技术通过簇节点之间的距离矩阵计算出各个区域传感器节点的局部相对坐标，最后通过融合算法将其融合为全局相对坐标并根据信标节点信息通过线性转换将器相对坐标转变为绝对坐标。3.2 多维标度技术和MDS-MAP定位算法3.2.1 多维标度技术基本原理多维标度技术MDS(Multi-dimensional scaling)是一种将实体间的相似信息转换成空间几何信息的数据分析技术，常用于探索性数据分析或信息可视化，最初应用于心理测验学的数据分析，现在已作为一种通用的数据分析技术广泛应用于各个领域。本章算法的基础是多维标度定位算法，下面具体介绍一下多维标度定位算法。假设研究对象和之间的相异性用表示，各研究对象间的相异性构成相异性矩阵。构造多维空间上点的坐标矩阵用表示，其中为坐标点的个数，为坐标点的维数，实体对象和的坐标分别为，多维空间上和之间的欧式距离用表示。多维标度技术就是利用各实体间的相异性来构造多维空间上点的相对坐标图，使与尽可能地接近，在多维标度中其接近程度用胁强系数(STRESS)来衡量。定义胁强系数为： (3-1)其具体实现分为四步：(1) 构造相异性矩阵；(2) 将矩阵中的各元素乘方，得到；(3) 将双重中心化,即的两边同时乘以中心矩阵,的计算公式见(3-2)。 (3-2)式中为阶的单位矩阵，为阶的全1矩阵，双重中心化后的矩阵见式(3-3)。 (3-3)(4) 将进行奇异值分解，求最大的个正特征值和对应的个特征向量，个向量组成维对角矩阵，个特征向量组成维矩阵,所有节点的相对坐标为 (3-4)3.2.2MDS-MAP定位算法无线传感器网络中节点定位的实质是未知节点通过与少量位置已知的信标节点之间的连通性信息来确定自身在相应空间中的位置坐标,而MDS技术就是根据各个对象(或实体)间的相异(似)信息构建多维空间上点的相对坐标图。于是，在研究无线传感器网络的定位时引入了MDS技术。传统的MDS-MAP算法，由美国密里哥伦比亚大学Yi等人提出。该算是利用MDS技术来生成相对坐标系统的，在较小规模规则且分布均匀的网络中，可以获得较高的定位精度，被广泛应用于无线传感器网络的相关项目中。MDS-MAP算法分为三步：(1) 生成距离矩阵首先从全局角度生成网络拓扑连通图，如果节点具备测距能力，则通过测距技术获得的节点间的距离值。否则根据最短路径算法，求出最短路径距离，生成节点之间的距离矩阵。(2) 估算相对位置对上一步生成的节点之间的距离矩阵采用MDS技术，估算出整个网络中所有未知节点在多维空间上的相对位置的坐标。(3) 将相对坐标转换为绝对坐标当网络中有足够的信标节点时，前一步执行完后，可以得到每个信标节点通过MDS技术估算出的相对坐标，根据估算出的信标节点坐标与原本已知的坐标关系，能够找到一个线性变换关系式，然后利用该线性变换关系式将相对坐标系统转化为绝对坐标系统。3.3 基于Hop-Euclidean的MDS-MAP(D)定位算法3.3.1 改进算法的相关研究工作如果所有节点之间的欧几里德距离没有误差，则采用经典的MDS定位算法求出的节点位置坐标是精确的。但是通常节点间通信会受到环境的影响，因而通过信号传播测出的节点间的距离值都是有误差的，最终会导致定位误差的出现。在实际的WSN应用中，求解全网络节点间的距离只能依据相邻节点之间的距离信息进行估计。而经典的MDS-MAP算法就是采用跳数与通信距离乘积来取代节点间的实际几何距离，从而扩大了节点的定位误差。MDS-MAP算法是采用MDS技术根据距离矩阵进行求解对应节点的位置坐标，但通常距离矩阵都比较庞大，则会导致其计算复杂度较大，且当节点增加或移动时，需要重新求解，这将会严重阻碍网络的扩展。针对经典MDS-MAP定位算法的上述问题，本文提出了一种基于Hop-Euclidean的MDS-MAP(D)定位算法。在采用基于Hop-Euclidean的MDS-MAP(D)算法定位之前，需做以下假设：(1) 为了计算方便，设定部署传感器节点的区域是二维的，且部署后位置静止；(2) 传感器节点的ID是唯一的；(3) 节点具有测距能力；(4) 采用的是自由空间电波传播模型，节点之间的通信能力是对称的，而且所有的消息都可以被正确接收。(5) 部分节点的位置信息已经通过安装GPS接收器或人工部署的方式确定(即信标节点)；(6) 无线传感器网络的全局时间是统一的，每个传感器节点都装备着定时器。3.3.2 分簇算法分簇算法可将一个大型的WSN划分成多个区域并选出各个区域中负责数据的路由转发同时管理其簇节点的簇头节点，这样既能够保证原有覆盖围的书籍通信，又在很大程度上节省了节点的能量。为了提高本章提出的定位算法的定位性能，在本节提出了一种适用于本章定位算法的分簇算法。分簇算法分为以下两大步：第一步 选择簇头节点假定簇各节点与簇头节点间的通信是选择最短的路径进行的，然而距离簇头节点近的节点除了要将自身的相关信息传播给簇头节点，点信息转发给簇头节点。假设簇头节点的邻居节点平均转发数据总流量为，簇头的连通度为，簇头节点的邻居节点平均转发的数据流量：与成反比。由于簇头节点既要将簇节点的相关信息存储起来，又要管理其簇节点，因此，其通信量与计算量都会远大于其簇节点，故簇头节点应比簇节点具有更高的能量。于是本文把连通度和残存能量信息作为选择簇头的两个主要参数，首先根据实际应用预先设定节点能量门限值为，连通度门限值为，假定需要选择个簇头节点，则具体选择过程分以下几种情况：第一种情况 能量值大于其门限值，且连通度大于门限值作为初选簇头节点，如果其数量大于所需的簇头节点数量，则根据公式(3-4)计算出初选簇头节点的综合性能值，将初选簇头节点按照其综合性能值的大小进行从大到小排序。 (3-4)式中 、权值，具体怎么取根据实际情况设定，只要满足即可。最后选择其中的前个节点作为最终的簇头节点。第二种情况 初选簇头节点个数等于所需的簇头节点数量，则无需再计算其综合性能值，初选簇头节点都是最终的簇头节点。第三种情况 初选簇头节点个数为小于所需簇头节点数量，则其余的个簇头节点需则根据公式(3-4)计算出剩余节点的综合性能值，将剩余节点按照其综合性能值的大小进行从大到小排序，选择其中的前个节点作为最终的簇头节点。第二步 划分簇由于本文计算簇节点间的距离时所采用的方法可以直接计算出相隔两跳的节点间的距离，而且考虑到后面通过局部定位求出的局部坐标需要通过融合算法转换为全局坐标，所以相邻簇之间应拥有相应的重叠度，因此为了提高本章定位算法的性能，将上一步选择出的簇头节点的两跳邻居节点作为其从节点来进行划分簇，且相邻簇间的重叠度为大于2且小于5，因为如果重叠度较大，一个节点会属于多个簇，在这些个簇都需要对其进行定位即需要重复定位的节点会增多，这样不仅会降低算法的定位效率，还会消耗更多珍贵的能量。接下来阐述上述问题的解决方案，为了更直观些，通过下面例子进行分析。如图3-1 a)所示，簇2中的所有节点都分别属于簇1和簇3，如节点8、9、10、11、13既在簇1中又在簇2中，节点12、14、15既在簇2中又在簇3中，如果按正常的处理方式，这九个节点都得进行两次定位，这样就会造成的重复定位，既浪费时间又浪费能量，从表面上看此时的簇头节点2可以取消，但是由于簇1与簇3没有重叠的部分，所以此时的簇2还必须保留，只是定位时，如果重叠度大于5，则从重叠的节点中选择2个在两个簇中都进行局部定位以便最后一步参与融合算法。对于剩余的重叠节点，先比较所属簇的簇头节点的残余能量的大小，在残余能量大的簇头节点所在簇中进行局部定位即可。如图3-1 b)所示，簇2中的所有节点都分别属于簇1和簇3，如节点8、9、10、11、13既在簇1中又在簇2中，节点11、12、13、14、15既在簇2中又在簇3中，如果按正常的处理方式，这9个节点都需进行两次定位，这样就会造成的重复定位，既浪费时间又浪费能量，像这样的情况簇2完全可以取消。a) 其他两簇没有重叠部分b) 其他两簇有重叠部分图3-1一个簇中的节点分别属于其他两簇分簇结束后，同时属于多个簇的节点起到了簇头间的连接与求解坐标转换参数的作用。在下面的