无线传感器网络节点定位技术

２０１１年第２Ｏ卷第９期　ｈｔｒｐ：ｌｌｗｗｗ．ｃ—Ｓ—ａ．ｏｒｇ．ｃｎ　计算机系统应用　无线传感器网络节点定位技术①　秦小虎，辛云宏，夏海峰，吴俊林　ｆ陕西师范大学物理学与信息技术学院，西安７１００６２）　摘要：对无线传感器网络定位技术进行了深入的探讨，从ＷＳＮ节点的定位机制、定位算法的分类、已有的定　位算法及算法性能的评价标准等方面进行分析，并对比了质心定位算法、ＤＶ－Ｈｏｐ算法、凸规划定位算法、ＡＰＩＴ　算法等几种经典的方法。结果表明：各种算法在不同的应用环境下所表现的性能差别较大，没有哪种算法是最　优的，应根据最感兴趣的性能指标选择合适的算法。最后提出了无线传感器网络节点定位技术需要解决的问题　和研究方向。　关键词：无线传感器网络；节点定位；定位机制；评价标准；定位算法　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　Ｎｏｄｅ　Ｌｏｃａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　ＱｒＮ　Ｘｉａｏ－Ｈｕ，ＸＩＮ　Ｙｕｎ—Ｈｏｎｇ，ＸＬ　Ｈａｉ－Ｆｅｎｇ，ＷＵ　Ｊｕｎ—Ｌｉｎ　（Ｃｏｌｌｅｇｅ　ｏｆＰｈｙｓｉｃｓ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａａｎｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｌｌ　７１００６２．Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｔｈｏｒｏｕｇｈ　ｄｉｓｃｕｓｓｉｏｎ　ａｂｏｕｔ　ｔｈｅ　ｌｏｃａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　ｔｈｅ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ　ｔｈａｔ　ｗａｓ　ａｎａｌｙｚｅｄ　ｉｎ　ｓｏｍｅ　ａｓｐｅｃｔｓ　ｓｕｃｈ　ｓａ　ｔｈｅ　ｂａｓｉｃ　ｐｒｉｎｃｉｐｌｅ　ｏｆ　ｔｈｅ　ｌｏｃａｌｉｚａｔｉｏｎ，ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ｏｆ　ｌｏｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ，ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｌｏｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ，ａｎｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｅｖａｌｕａｔｉｏｎ　ｃｒｉｔｅｒｉａ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｍｈｓ　ｉｎ　ｄｅｔａｉｌ．Ｗｅ　ｈａｖｅ　ｃｏｍｐａｒｅｄ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｓｏｍｅ　ｃｌａｓｓｉｃ　ａｌｇｏｒｉｔｍｈｓ，ｓｕｃｈ　ａｓ　ｃｅｎｔｒｏｉｄ　ｌｏｃａｌｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ＤＶ－Ｈｏｐ　ａｌｇｏｒｉｔｈｍ，ｃｏｎｖｅｘ　ｐｒｏｇｒａｍｍｉｎｇ　ｌｏｃａｌｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｍｈ　ａｎｄ　ＡＰＩＴ　ａｌｇｏｒｉｔｈｍ　ｅｔｃ．Ａｎａｌｙｓｉｓ　ｒｅｓｕｌｓｔ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　ｖａｒｉｏｕｓ　ａｌｇｏｒｉｔｍｈｓ　ｉｎ　ｄｉｆｆｅｒｅｎｔ　ｅｎｖｉｒｏｎｍｅｎｔｓ　ｈａｖｅ　ｓｈｏｗｎ　ｇｒｅａｔ　ｄｉｆｅｒｅｎｃｅｓ　ｉｎ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ．Ｎｏｎｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｍｈｓ　ｉｓ　ｏｐｔｉｍａ１．Ｗｅ　ｓｈｏｕｌｄ　ｓｅｌｅｃｔ　ｔｈｅ　ａｐｐｒｏｐｒｉａｔｅ　ａｌｇｏｒｉｔｍｈ　ｂａｓｅｄ　ｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｎｄｉｃａｔｏｒｓ　ｏｆ　ｍｏｓｔ　ｉｎｔｅｒｅｓｔ．Ａｔ　ｌａｓｔ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ｔｈｅ　ｐｒｏｂｌｅｍｓ　ｔｏ　ｂｅ　ｓｏｌｖｅｄ　ｎａｄ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｄｉｒｅｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｗｉｅｒｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ　ｎｏｄｅ　ｌｏｃａｔｉｏｎ　ｔｅｃｈｎｏｌｏｇｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ；ｎｏｄｅ　ｌｏｃａｌｉｚａｔｉｏｎ；ｌｏｃａｌｉｚａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ；ｅｖａｌａｕｔｉｏｎ　ｓａｔｎｄａｒｄ；ｌｏｃａｌｉａｚｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　１　引言　的定位算法，定位系统和算法在定位精度、节点密度、　无线传感器网络（ＷＳＮ）是在无线通信、数字电子　覆盖率、能耗等方面各有优势【４】。　技术和微机电系统发展的基础上形成的ｌ¨，其重要支　撑技术有：布局和覆盖、时钟同步、节点定位、网络　２定位机制　通信协议等［２１。节点定位是传感器网络环境监测、目　在ＷＳＮ中传感器节点能量有限、可靠性差、节点规　标追踪、空间探测的前提，是ＷＳＮ最基本的功能之　模大且随机分布、无线通信的距离有限，对定位算法　一。定位系统和算法的研究大体经历了两个发展阶段，　和定位技术要求很　，定位算法应具备鲁棒性强、　第一阶段主要偏重于紧密耦合型和基于基础设施的定　能量高效、自组织性等特点。　位系统，第二阶段偏重于松散耦合型和无需基础设施　节点定位一般分为三个步骤：第一步，未知节点　的定位技术，其又可分为两类，包括距离相关和距离　通过一定的测量手段获得到邻居锚节点的距离或角　无关定位算法【引。最新的研究主要在基于移动锚节点　度，常用的方法有ＲＳＳＩ、ＴＯＡ、ＴＤＯＡ和ＡＯＡ，或　①基金项目：国家高技术研究发展计划（８６３）（０８２Ｏｌ０２ｌ０３２）；陕西省自然科学基金（２ｏ０６Ｆ４７）；２ｏ０９年度陕西师范大学优秀科技预研项Ｉ￣（２００９０２００６）　收稿时间：２０１１—０１—２３；收到修改稿时间：２０１１．０２—２６　Ｒｅｓｃ￣ｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ研究开发１　１　７　汁算机系统应用　ｈｔｔｐ：ｌｌｗｗｗ．Ｃ－Ｓ—ａ．ｏｒｇ．ｃａ　２０１１年第２Ｏ卷第９期　者根据网络的连通信息估计节点间的距离：第二步，　运用某种算法或技术实现位置估计，计算方法有三边　测量法、三角测量法和极大似然估计法；第三步，对　估计值进行优　们。　２性能评价指标　】　无线传感器网络节点定位算法的性能直接影响其　可用性，以下是评价ＷＳＮ定位性能的几项关键指标：　定位精度：这是定位技术首要的评价指标，一般　用误差值与节点无线射程的比例表示。　锚节点密度：锚节点通常依赖人工部署或ＧＰＳ　实现定位，人工部署方式不仅受到部署环境的限制，　还严重制约了网络和应用的可扩展性。锚节点的费用　会比普通节点高两个数量级，所以应尽量减少锚节点　数量。　覆盖率：覆盖率指可实现定位的未知节点与总的　未知节点数之比。传感器网络中总会存在一些不可到　达或连通度很低的不良节点，从而降低了节点的定位　精度。　容错性和自适应性：容错性指在故障存在的情　况下定位系统不失效，仍能正常工作；自适应性指　复杂系统对若干不协调因素的包容和整合。定位系　统和算法都需要比较理想的无线通信环境和可靠　的网络节点设备，但实际应用中，外界环境中存在　严重的多径传播、衰减、非视距、通信盲点等问题；　网络节点失效问题；节点间点到点的通信距离变化　及角度测量误差等问题都会导致定位过程十分困　难或不可行，因此定位系统和算法必须具有容错性　和自适应性。　功耗：功耗是对无线传感器网络的设计和实现影　响最大的因素之一，决定功耗大小的因素有定位所需　的计算量、通信开销、存储开销、时间复杂性等指标。　代价：时间代价包括一个系统的安装时间、配置　时间、定位所需时间。空间代价包括一个定位系统或　算法所需的基础设施和网络节点的数量、硬件尺寸等。　资金代价包括实现一种定位系统或算法的基础设施、　节点设备的总费用。　３　无线传感器网络定位算法分类［８’９】　无线传感器网络节点定位算法的分类方法较多，　可从不同的角度进行分类，没有统一的标准。　１　Ｉ　８研究开发Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　３．１基于测￣（Ｒａｎｇｅ．ｂａｓｅｄ　ｍｅｔｈｏｄｓ）的定位和无需测　￣［（Ｒａｎｇｅ．ｆｒｅｅ　ｍｅｔｈｏｄｓ）的定位　前者需要测量相邻节点间的绝对距离或方位，并　利用节点间的实际距离来计算未知节点的位置；后者　无需测量节点的绝对距离或方位，利用节点问的估计　距离计算节点位置。Ｒａｎｇｅ．ｂａｓｅｄ定位算法常用的测距　技术有：接收信号强度测距ＲＳＳＩ，到达时间测距ＴＯＡ，　时间差测距ＴＤＯＡ和到达角测距ＡＯＡ。　３＿２绝对定位与相对定位　绝对定位与物理定位类似，定位结果是一个标准　的坐标位置，如经纬度。而相对定位通常以网络中部　分节点为参考建立整个网络的相对坐标系统。绝对定　位可为网络提供唯一的命名空间，受节点移动性影响　较小，有更广泛的应用领域。但是在相对定位的基础　上也能够实现部分路由协议，尤其是基于地理位置的　路由，而且相对定位不需要锚节点，这使相对定位有　了更广的应用范围。　３Ｉ３集中式（Ｃｅｎｔｒａｌｉｚｅｄ　Ｃｏｍｐｕｔａｔｉｏｎ）计算与分布式　（Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔａｔｉｏｎ）计算　集中式计算是把所需信息传送到某个中心节点，　并在那里进行节点定位计算的方法。分布式计算是依　赖节点间的信息交换和协调，由节点自行计算的方法。　３．４紧密耦合（ｔｉｇｈｔｌｙ　Ｃｏｕｐｌｅｄ）与松散耦合（１ｏｏｓｅｌｙ　Ｃｏｕｐｌｅｄ）　紧密耦合定位指锚节点不仅被仔细地部署在固定　的位置，并且通过有线媒介连接到中心控制器；而松　散型定位系统的锚节点采用无中心控制器的分布式无　线协调方式。　３．５细粒度与粗粒度　细粒度定位是根据信号强度或时间来度量与锚节　点距离的，其中又可分为基于距离和基于方向测量两　类；粗粒度定位是根据与锚节点的接近度来度量的。　４几种典型的无线传感器网络自身定位系　统和算法　无线传感器网络节点定位算法很多，不同算法在　不同环境下的性能表现各异。由于节点能量有限，存　储能力和计算能力有限，所以要求算法是低复杂度的。　在实际应用中，虽然Ｒａｎｇｅ．ｂａｓｅｄ定位算法定位精度较　高，但其系统复杂，能耗大，不适于低功耗、低成本　系统，而Ｒａｎｇｅ．ｆｒｅｅ算法的定位精度对大多数应用已　２０１１年第２Ｏ卷第９期　ｈｔｔｐ：／／ｗｗｗ．ｃ—Ｓ－ａ．ｏｒｇ．ｅｌｌ　计算机系统应用　经足够，在此主要介绍两种经典定位系统和几种典型　ｍａｎｎ等提出的一种ｒａｎｇｅ．ｆｒｅｅ的粗精度定位法，同时这　的Ｒａｎｇｅ．ｆｒｅｅ定位算法。　也奠定了ｒａｎｇｅ．ｆｒｅｅ定位算法的基石。该算法思想是：　４．１　Ｃｒｉｃｋｅｔ定位系统【Ｊ　ＵＪ　早期的紧密耦合型定位系统无法适用于Ａｄ．ｈｏｃ　式网络，需要事先的网络部署或数据生成工作。为了　弥补紧密耦合定位系统的不足，ＭＩＴ开发了最早的松　未知节点以所有在其通信范围内的锚节点构成的多边　形的几何质心作为自己的估计位置。锚节点周期性地　向邻近节点广播锚节点分组，这个分组包含了节点自　身ＩＤ和位置信息。当未知节点接收到来自不同锚节点　的分组数量超过某一个门限值Ｋ或接收一定时间后，　散耦合定位系统Ｃｒｉｃｋｅｔ，它由散布在建筑物内位置固　定的锚节点和需要定位的人或物体携带的未知节点组　便利用下述质心公式确定自身位置为这些锚节点组成　成。锚节点随机地同时发射无线电波和超声波信号，　无线电波信号中包含该锚节点的位置和ＩＤ。未知节点　使用ＴＤＯＡ技术测量其与锚节点的距离，当它能够获　得３个以上锚节点距离时就使用三边测量法进行物理　定位。然而Ｃｒｉｃｋｅｔ定位系统是应用在普适计算中的，　这需要细粒度、三维的定位和方位信息。普适计算中　各节点的定位信息是私有的，只能由信标节点发送这　些定位信息，接收器通过被动的监听从基础设施中发　射来的信标信息来定位自身。Ｃｒｉｃｋｅｔ定位系统的优点　是厘米级精确度。　４．２　ＲＡＤＡＲ系统【ＪＩＪ　ＲＡＤＡＲ定位系统是由ＭｉｃｒｏＳｏｆｔ公司开发的基于　ＩＥＥＥ８０２．１１无线网络技术，属于射频场景信息的室内　定位系统，它提供了场景分析和三边测量两种实现方　式。ＲＡＤＡＲ定位系统分为两个部分：一部分是位置．　场景数据库，一部分是匹配定位功能模块。系统的工　作过程也相应分为两步，第一步首先离线完成建库的　工作，即把节点处于各种位置时的场景参数记录下来，　通常是由一个节点在定位范围内漫游，由一些固定的　节点记录下接收到的漫游节点信号强度或角度等，再　把这些信息和当前漫游节点位置配对记入数据库；第　二步则是在线的位程匹配定位，当接收到一个待定位　节点发出的信号，立即使用该信号和数据库中己有的　场景参数配对，选取场景参数中最接近元组的位置信　息作为此节点当前的位置。在三边测量定位方式下，　未知节点根据ＲＳＳＩ计算与多个基站的距离，然后使用　三边测量法定位，系统能够以５０％的概率获得４．１米　的精度。系统最少仅需要三个无线网基站就可以实现。　虽然场景分析的定位精度很高，但被定位目标必须支　持无线网连接，这对于小型或能源受限的设备是不现　实的，且该系统易受外界因素影响。　４－３质心定位算法［１２，１３１　此算法是南加州大学Ｎｉｒｕｐａｍａ　Ｂｕｌｕｓｕ和Ｊ．Ｈｅｉｄｅ．　的多边形的质心：　＝，　［　＋　十・十　）　十・十　／剜　（１）　其中（Ｘ　，　）…（　，　）为未知节点能够接收到其　他分组的锚节点坐标。　该算法最大的优点是完全基于网络的连通性，实　现较为简单且计算量较小。但该算法仅能提供粗粒度　的定位，定位精度不高，且与锚节点的密度、分布有　很大关系。后来Ｎ．Ｂｕｌｕｓｕ用著名的密度自适应算法　（ＨＥｍ）来改进了这一算法，通过放置额外的锚节点减　少定位误差。　４．４　ＤＶ－Ｈｏｐ算法［１４，１５］　美国路特葛斯大学（Ｒｕｔｇｅｒｓ　Ｕｎｉｖｅｒｓｉｔｙ）的Ｄｒａｇｏｓ　Ｎｉｃｕｌｅｓｃｕ等利用距离矢量路Ｉ￣（ｄｉｓｔａｎｃｅ　ｖｅｃｔｏｒ　ｒｏｕｔｉｎｇ）　和ＧＰＳ定位原理提出了一系列分布式定位算法，合称　为ＡＰＳ（Ａｄ　ｈｏｃ　Ｐｏｓｉｔｉｏｎｉｎｇ　Ｓｙｓｔｅｍ，包括ＤＶ－ｈｏｐ，ＤＶ－　ｄｉｓｔａｎｃｅ，Ｅｕｃｌｉｄｅａｎ，ＤＶ－Ｃｏｏｒｄｉｎａｔｅ，ＤＶ－Ｂｅａｒｉｎｇ和　ＤＶ－Ｒａｄｉａｌ等６种算法），ＤＶ－Ｈｏｐ算法就是其中之一。　ＤＶ－Ｈｏｐ算法的基本思想是将未知节点到参考节　点之间的距离用网络平均每跳距离和两者之间最短路　径跳数乘积表示，然后使用三边测量法获得节点位置　信息。ＤＶ－ｈｏｐ算法由三个环节组成：　第１步，通过采用经典的距离矢量交换协议使得　网络中的所有节点都获得距离锚节点的跳数（ｄｉｓｔａｎｃｅ　ｉｎ　ｈｏｐｓ）。每个节点都将所有锚节点的坐标以及距离它　们的跳数记录下来，并把该信息与邻居节点交换以更　新信息。　第２步，对于任意一个锚节点可以利用它们之间　的欧几里得距离之和除以它们间的跳数之和来计算该　锚节点在网络中的平均每跳距离，并将其作为一个校　正值（Ｃｏｒｒｅｃｔｉｏｎ）广播至网络中。锚节点向网络广播一　个信标，信标中包含有此锚节点的位置信息和一个初　始值为１的表示跳数的参数。此信标在网络中被以泛　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ研究开发１　１　９　计算机系统应用　ｌｎｔｐ：／／ｗｗｗ．ｃ—Ｓ—ａ．ｏｒｇ．ｃｎ　２０１１年第２Ｏ卷第９期　洪的方式传播出去，信标每次被转发时跳数都增加Ｉ。　接收节点在它收到的关于某一个锚节点的所有信标中　保存具有最小跳数值的信标，丢弃具有较大跳数值的　同一锚节点的信标。通过这一机制，网络中所有节点　（包括其他锚节点）都获得了到每一个锚节点的最小跳　数值。　点间的距离就小于等于１５ｍ，这样产生一系列相邻的　约束条件就能确定节点可能存在的位置区域。　该算法把整个网络模型化为一个凸集，从而将节　点定位问题转化为凸约束优化问题，然后使用半判定　规划（ＳＤＰ）或线性规划（ＬＰ）方法得到一个全局优　化的解决方案，确定节点位置。同时也给出了一种计　当接收到校正值之后，节点根据跳数计算与锚节　算未知节点有可能存在的矩形区域的方法。　点之间的距离，如下式：　平均每跳距离：　√（　）　（２）　——　ｄｉ＝　×　（３）　其中　表示参考节点ｉ到参考节点ｊ的跳数。　第３步，当未知节点求得与三个或更多锚节点的　距离时，则利用三边测量法进行定位。　，ｌ　／　／　／　，　一　～　ｏ　～　图１　ＤＶ－ＨＯＰ算法　一　＼　＼　、　、Ｉ　如图１所示，己知锚节点Ｌ１与Ｌ２、Ｌ３之间的距　离和跳数。计算得到校正值（即平均每跳距离）：　（４０＋７５）／（２＋５）＝１６．４２。在上例中，假设Ａ从Ｌ２获得校　正值，则它与３个锚节点之间的距离分别为Ｌｌ：３×　１６．４２，Ｌ２：２×１６．４２，Ｌ３：３×１６．４２，然后使用三边测量　法确定节点Ａ的位置。　ＤＶ－ｈｏｐ算法在网络平均连通度为ｌ０，锚节点比　例为１０％的各向同性网络中定位精度约为３３％。其缺　点是对网络的锚节点密度要求较高。　４．５凸规划定位算法【ｌ　６Ｊ　加州大学伯克利分校的Ｄｏｈｅｒｔｙ等人提出的一种　完全基于网络连通性诱导约束的定位算法，将节点间　点到点的通信连接视为节点位置的几何约束。例如，　如果节点间的通信半径是１５ｍ，则两个相互通信的节　１２０研究开发Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　如图２所示，根据未知节点与锚节点之间的通信　连接和节点无线射程，计算出未知节点可能存在的区　域（图中红色部分），并得到相应矩形区域，然后以该区　域的质心作为未知节点的位置。　／　／　，　＼　Ｉ　、　、　、　＼　Ｉ　＼　，　／　＼／　＼　／、／　～一一ｏ锚节点　・未知节点　图２凸规划定位算法　凸规划是一种集中式定位算法，锚节点比例为　１Ｏ％的情况下，定位误差约等于节点的通信半径。锚　节点应被部署在网络的边缘，可减少定位误差。　４．６ＡＰＩＴ算法【ｌ７】　弗吉尼亚大学的ＨｅＴ等人提出的ＡＰＩＴ算法，其　理论基础是Ｐｅｒｆｅｃｔ　Ｐｏｉｎｔ－Ｉｎ．Ｔｒｉａｎｇｕｌａｔｉｏｎ　Ｔｅｓｔ　Ｔｈｅｏｒｙ　（ＰＩＴ）。该算法的主要思想是首先未知节点收集所有邻　居锚节点的信息，并测试未知节点是否位于不同的三　个锚节点组成的三角形内，重复测试，直到穷尽所有　组合或达到所需定位精度。如图３计算所有包含该未　知节点的三角形的重叠区域，用该区域的质心作为未　知节点的坐标。　图３　ＡＰＩＴ算法　２０１１年第２Ｏ卷第９期　ｈｔｔｐ：／／ｗｗｗ．Ｃ—Ｓ—ａ．ｏｒｇ．ｃａ　计算机系统应用　此法误差概率相对较小（最差情况下１４％），平均　３　Ｃａｐｋｕｎ　Ｓ，Ｈａｍｄｉ　Ｍ，Ｈｕｂａｕｘ　ＪＰ．ＧＰＳ—Ｆｒｅｅ　ｐｏｓｉｔｉｏｎｉｎｇ　ｉｎ　定位误差小于节点通信半径的４０％，但该算法要求较　高的参考节点密度。　现有定位系统和算法还有很多种，例如ＭＤＳ．ＭＡＰ、　Ｎ．ｈｏｐ　ｍｕｌｔｉｌａｔｅｒａｔｉｏｎ　ｐｒｉｍｉｔｉｖｅ、ＳＰＡ相对定位算法、　Ｅｕｃｌｉｄｅａｎ定位算法等。　ｍｏｂｉｌｅ　ａｄ－ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｃｌｕｓｔｅｒ　Ｃｏｍｐｕｔｉｎｇ，２００２，５（２）：　１５７－１６７．　４　Ｈｉｇｈｔｏｗｅｒ　Ｊ．Ｂｏｒｒｉｅｌｌｏ　Ｇ　Ｌｏｃａｔｉｏｎ　ｓｅｎｓｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ．　Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ　ＵＷ　ＣＳＥ，Ｓｅａｔｔｌｅ：Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＷａｓｈｉｎｇｔｏｎ，２００１．　在实际应用过程中，现有定位系统和算法还存在　５陈娟，李长庚，宁新鲜．基于移动信标的无线传感器网络节点　很多具体问题，主要表现在：　１）未知节点必须与锚节点直接相邻，且要求锚节　点密度过高；　２）定位精度高度依赖于网络部署条件；　３）节点通信中对距离／角度测量的误差值进行传　播和积累，使定位精度降低；　４）循环求精过程产生了大量的通信和计算开销，　且无法预估循环的次数，增加了算法的不确定性。　解决上述问题是各类定位算法的基本目标，对所　有应用环境都适用的定位系统是不存在的，我们应根　据性能要求选择最佳的定位算法、测距技术和校正方　法。　５结语　本文对ＷＳＮ节点定位所涉及到的定位机制、性　能评价标准、算法的分类和典型定位系统与几种经典　的Ｒａｎｇｅ．ｆｒｅｅ定位算法进行了介绍，比较了各自的优　缺点，并提出了现有算法存在的问题。传感器网络是　面向应用的一类远程自组网测控系统，在实际应用中，　对算法性能的要求差异很大，应尽量使设计的方法性　价比最优。因此，设计出适合感知网络自身特点的、　节能高效、定位精确、可扩展的节点定位算法，是无　线传感器网络研究的一个重要目标。　参考文献　１孙利民，李建中，陈渝，朱红松．无线传感器网络．北京：清华大　学出版社．２００５．１３５—１５５．　２汪炀．无线传感器网络定位技术研究［博士学位论文】．合肥：　中国科学技术大学，２００７．　定位．传感技术学报，２００９，２２（１）：１２２—１２３．　６王福豹，史龙，任丰原．无线传感器网络中的自身定位系统和　算法．软件学报，２００５，１６（５）：８５９—８６５．　７李明忠．无线传感器网络自定位算法研究【硕士学位论文】．　西安：西安电子科技大学，２００９．　８　ＢｕｌｕＳＵ　Ｎ，Ｈｅｉｄｅｍａｎｎ　Ｊ，Ｅｓｔｒｉｎ　Ｄ　Ａｄａｐｔｉｖｅ　ｂｅａｃｏｎ　ｐｌａｃｅ・　ｍｅｎｔ．Ｉｎ：Ｙｏｕｎｇ　ＤＣ，ｅｄ．Ｐｒｏｃ．ｏｆｔｈｅ　２１ｓｔ　Ｉｎｔ’ｌ　Ｃｏｎ￣ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ．Ｍｅｓａ：ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　Ｓｏｃｉｅｔｙ，２００　１．４８９－４９８．　９马祖长，孙怡宁．无线传感器网络节点的定位算法．计算机工　程，２００４，３０（７）：１３—１５．　１Ｏ付华，胡冰．一种无线传感器网络节点定位算法的改进．传　感器与微系统，２００９，２８（３）：２７－２９．　１１　Ｓｈａｎｇ　Ｙ　Ｒｕｍｌ　Ｗ　Ｚｈａｎｇ　Ｆｒｏｍｈｅｒｚ　ＭＰＪ．Ｌｏｃａｌｉｚａｔｉｏｎ　ｆｒｏｍ　ｍｅｒｅ　ｃｏｎｎｅｃｔｉｖｉｔｙ．Ｐｒｏｅ．ｏｆｔｈｅ　４ｔｈ　ＡＣＭ　Ｉｎｔ’ｌ　Ｓｙｍｐ．　ｏｎ　Ｍｏｂｉｌｅ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｋｉｎｇ＆Ｃｏｍｐｕｔｉｎｇ．Ａｎｎａｐｏｌｉｓ：　ＡＣＭ　Ｐｒｅｓｓ，２００３．２０１－２１２．　１２尚志军，曾鹏，于海斌．无线传感器网络节点定位问题．计算　机科学，２００４，３１（１０）：３５—３８．　１３　Ｈｉｇｈｔｏｗｅｒ　Ｊ．Ｂｏｒｉｅｌｌｏ　Ｇ　Ｌｏｃａｔｉｏｎ　ｓｙｓｔｅｍｓ　ｆｏｒ　ｕｂｉｑｕｉｔｏｕｓ—　ｃｏｍｐｕｔｉｎｇ．Ｃｏｍｐｕｔｅｒ，２００１，３４（８）：５７－６６．　１４刘艳文，王福豹，段渭军．基于ＤＶ－ＨＯＰ定位算法和ＲＳＳＩ　测距技术的定位系统．计算机应用，２００７，２７（３）：５１６—５１９．　１５邱萌，徐惠民．一种无线传感器网络无测距分布式定位算　法．计算机工程，２００８，３４（９）：１２１—１２３．　１６章磊，黄光明．基于ＲＳＳＩ的无线传感器网络节点定位算法．　计算机工程与设计，２０１０，３１（２）：２９１—２９３．　１７任丰原，黄海宁，林闯．无线传感器网络．软件学报，２００３，１４　（２）：１　１４８一ｌ１５７．　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ研究开发１２１