无线网络定位技术分析及发展综述

吕奇辰，庞丽莉，谢家烨

（1.中国人民解放军94789部队 江苏 南京 210018；2.南京工程学院 江苏 南京 211167）

无线网络定位技术分析及发展综述

吕奇辰1，庞丽莉2，谢家烨2

（1.中国人民解放军94789部队 江苏 南京 210018；2.南京工程学院 江苏 南京 211167）

基于梳理无线网络定位技术的发展现状、分析其现有定位算法和系统的优势及存在问题的目的，依据定位技术的基本原理和评估标准，采用分类对比法，从定位精度、定位规模、算法复杂度、算法适应性、算法可行性等几个方面对定位算法进行综合分析，在考虑定位算法和系统的定位精度以及可行性的情况下，得出不同应用环境下，定位方案的具体分类和优化改进措施。

无线网络；节点定位；二维定位；定位误差

无线网络中的定位技术是确定参考坐标系下物体的空间位置信息。对无线网络中的节点而言，不知道位置而感知的数据是没有意义的[1]。通过节点得到的数据只有与其位置、时间相对应，才能实现对探测目标和事件的定位和分析。现有的定位算法针对无线传感器网络中的节点定位及通信网络中的移动目标定位做了大量研究，针对应用需求提出了很多解决方案，比如无线传感器网络中的定位算法要考虑到节点能耗、硬件成本、定位精度（区域定位或精确定位）等；移动通信中的定位算法需要考虑基站分布、目标的移动性、环境中的干扰等。每种算法都有侧重及应用限制，但原理和过程基本一致，因此可以统称为无线网络中的节点定位。

获取位置信息的直接方法就是配备GPS接收装置，广泛用于定位的GPS技术对大部分无线应用而言，成本高并会受到环境及系统能耗等限制，在非视距 （non-line-of-sight，NLOS）传播环境中，微弱的卫星信号易被遮蔽。第二种方法是布置一定数量已知自身位置 （通过人工测量或者安装GPS接收机）的锚节点（anchor node），采用某种测量手段及估计方法确定位置信息未知的节点（unknown node）的位置，可以是绝对位置信息或者相对位置信息。第三种方法是系统中无锚节点，节点依据相互的距离信息或跳数来获得相对位置坐标。

1 定位算法的分类和评估指标

1.1 算法分类

获得节点位置信息的算法有很多，如图1所示按照定位范围、定位结果、算法处理方式、信息获取方式等进行分类，基于信息获取方式的分类方法更侧重于基本的定位原理且定位过程比较清晰，测距（range-based）定位法是对距离、角度等信息进行直接测量，然后对未知节点的位置进行计算或估计，定位精度相对较高，对节点本身硬件要求较高；非测距（range-free）定位法一般通过跳数或者通信范围来估算未知节点与锚节点之间的距离或相对信息，主要依赖网络部署，算法易实现，对硬件要求低，功耗低。

1.2 评估指标

评估指标包括精度、计算开销、硬件支持等，几种主要的评估标准如下。

定位误差：定位误差是评价定位算法性能的首要标准，通常可以用单点位置估计的均方误差（MSE）及均方根误差（RMSE）、与锚节点布局相关的几何稀释因子（GDOP）、误差限克拉美罗下界 （CRLB）和考虑通信射程的相对定位误差（RPE）等来表述。

算法开销：计算开销、通信开销、算法复杂度等。

锚节点个数：越多的锚节点越能为定位提供更多的参考，但增加锚节点会增加系统成本、算法复杂度和计算难度。

定位规模：如果锚节点的数量有限，且要求适当的定位精度，能对多少节点进行定位也是一项重要的评价指标，关系到定位算法的普适性。

是否需要辅助硬件支持：为了提高定位精度，有时会采用辅助手段，如GPS、气压测高、超声波辅助测距等，会增加系统的成本，限制算法的应用。

图1 定位算法的分类

图2 节点定位过程

2 节点定位过程

对未知节点进行定位可分为3个阶段，信息获取阶段、位置估计阶段和定位求精阶段，如图2所示。信息获取阶段是获取未知节点和锚节点间的距离信息和连通度，距离信息包括测距/测角或距离估计，而连通度表征了未知节点能够接收到来自锚节点的信息，可用于节点定位。位置估计阶段包括用代数方法解方程，或用几何方法对未知节点的位置进行约束。经过前两个阶段，可得到未知节点的位置信息，但误差累积会严重影响定位结果，因此对每个阶段产生的误差进行修正和处理，才能得到更精确的定位信息。

2.1 信息获取阶段

TOA（Time of arrival）：对未知节点和锚节点之间的无线信号传播时间进行测量，根据信号传播速率求得距离。可分为单程测距和双程测距，单程测距需要严格的时间同步；双程测距包含了简单的时间同步算法。基于TOA测距技术的定位算法精度很高，GPS全球定位系统就是其典型应用。

TDOA（Time Difference of Arrival）：一是采用不同的信号进行测距，需增加超声波装置等额外的硬件，根据两种信号的到达时间差以及传输速率来计算未知节点与锚节点间的距离，典型的应用系统有Cricket系统和AHLos系统；二是Chan[2]采用的算法，用同一种无线信号，记录未知节点和两个不同锚节点的信号传播时间差，只需锚节点时间同步即可。

AOA（Angel of Arrival）：能够得到无线信号的发送或者接收方向，获得未知节点和锚节点之间的角度信息。基于AOA的定位算法能确定节点的坐标和方位，需要天线阵列等硬件，通信能耗增加，且测距过程易受环境影响。E911系统中就采用此方案来确定目标方位，另外机器人导航系统中也常采用AOA技术。

RSSI（Received Signal Strength Indicator）：表示节点接收到的信号强度，定义为：RSSI（d）=PT-P（d），d为发送端到接收端间的距离，PT为发射信号强度，P（d）是与发送端距离为d处的信号强度，是在参考距离d0处的信号强度，n是路径损耗因子，接收节点距离发射节点越近RSSI值越大。获取RSSI值十分容易，无需额外硬件支持，典型的应用有RADAR和SpotON等。

距离估计方法：如DV-Hop（Distance Vector-Hop）算法[3]中，锚节点根据彼此之间的跳数和已知的距离来计算平均跳距，未知节点由此获得与锚节点之间的估计距离。DV-Hop算法完全基于节点密度以及部署条件，交换距离的方式大大增加节点间的通信量，另外利用跳距对距离进行估计，会导致平均定位误差增大。类似的还有 Amorphous定位算法[4]，与DV-Hop算法不同的是其平均跳距的确定与通信半径和网络连通度有关。

2.2 位置估计阶段

主要包括代数法和几何法，未知节点通过与锚节点间的距离或角度信息用代数法计算坐标，或者根据接收到的锚节点信号，及节点的通信半径，建立几何约束关系，确定位置。

2.2.1 代数求解方法（以二维空间为例）

三边测量法：以锚节点为圆心画半径为锚节点到未知节点之间距离的圆，已知3个锚节点的坐标（x1，y1），（x2，y2）和（x3，y3）以及它们到未知节点的距离r1，r2和r3，估算出未知节点的坐标：。在不考虑测量误差和NLOS误差的理想情况下，如图3所示，当3个锚节点位于一条直线上时方程无唯一解，需要更多锚节点或其它辅助措施作为参考来确定未知节点的位置坐标。

三角测量法：以AOA测角方法为基础，锚节点的坐标和未知节点与锚节点的角度已知。如图4所示，已知两个锚节点A和C的坐标，X与A和C之间的角度为∠AXC，由α=∠AOC=，可唯一确定一个圆，得到圆心坐标（xo，yo）和半径r1。同理可得另两个圆的圆心坐标和半径，由这3个圆的交点，用三边测量法，可得未知节点坐标。

图3 不能唯一确定未知节点的位置

图4 三角测量法

多边测量法：也可称为极大似然估计法，是锚节点较多的情况下的一种优化解法，有n个锚节点，已知它们的坐标（x1，y1），…，（xi，yi），…，（xn，yn），以及到未知节点的距离 r1，…，ri，…，rn，然后列出一个二元二次方程组，用最小二乘法得到未知节点的坐标。

2.2.2 几何约束方法

根据锚节点与未知节点的连通度或者通信情况，用多边形、三角形等几何形状限定未知节点的范围，并用其质心来估计未知节点的位置。几何约束方法的定位精度与锚节点的密度和分布有密切关系。

南加州大学的Nirupama Bulusu等人提出的质心算法即多边形约束，未知节点接收邻近锚节点的信号，由锚节点组成多边形的质心确定位置，算法基于网络连通性，简单易行。

APIT（Approximate point-in-triangulation test）算法[5]基于区域划分，对网络连通性有较高要求。未知节点接收所有邻近锚节点的信息，每3个不同的锚节点组成三角形，穷举所有锚节点的组合方案，根据PIT算法，判断未知节点是否位于这些三角形内，位于其内的所有三角形的交集，就是未知节点可能的位置范围，可用交集的质心作为未知节点的位置估计。

圆形区域约束是利用未知节点与锚节点之间的通信连接状况，能够通信的锚节点作为圆心，以节点的通信半径为半径，所有圆的交集（形成一个阴影）作为未知节点的存在范围，能够得到的锚节点信息越多，部署位置越接近未知节点，则约束范围越小，但由于阴影的形状不规则，较难选取最优的位置点，加利福利亚大学伯克利分校的Doherty等提出的Convex Position Estimatation算法中，将阴影的外矩形求出，并以矩形的质心作为未知节点的位置。

2.2.3 其它定位技术

除了上述方法，其它领域的技术也被应用于定位，如起源于心理测度学的数据分析技术多维标度法（MDS）、指纹识别（FP）等。前者可以获取各点之间的相对位置关系，后者通过大量的现场数据建立指纹库，对未知节点的信息进行判别，以达到定位的目的。

2.3 误差主要来源和解决方法

2.3.1 信息获取阶段产生的误差及针对性算法

在信息获取阶段，测距时就会产生测量误差。其中NLOS传播会给测距结果带来极大的影响。精确的测距方法都是以视距传播（Line of Sight，LOS）为基础的，甚至RSSI值的获取也会因为NLOS存在较大偏差。当无线传输信号受到遮挡、干扰时，节点之间的无线传播是非直线的，只有反射和衍射路径，导致无线信号中的LOS信号很弱，接收端无法检测出直射路径信号，产生NLOS误差。在TOA测距方法中，由于NLOS传播，使得信号传播存在很大的延时，导致测量值大于实际距离，再利用三边测量法或极大似然法进行定位时，无法得到精确的定位结果。而RSSI测距方法中，由于障碍干扰导致信号衰减过大，影响对未知点和锚节点之间距离的判断。实际环境中NLOS传播是普遍存在的，其统计特性在不同信道环境下有所不同，难以估计。由于与传播环境有关，即使提高接收装置对TOA的测量精度也无法消除NLOS误差的影响。很多研究[6]都针对降低NLOS误差做了大量的工作，P.C.Chen提出了残差加权算法（Rwgh），利用定位残差对定位结果进行加权，以抑制NLOS误差，该算法无需信道的统计模型和先验知识，但网络规模变大时，算法的复杂度随之增加。

除了NLOS误差之外，TOA/TDOA算法的误差来源主要是时间不能严格同步造成的，可用时钟同步算法减小此类误差，或采用协同算法同时完成时钟同步和测距定位。TDOA算法虽然降低了对时间同步的要求，但辅助测量手段的引入也会带来一定的测量误差。

多径传播效应会干扰AOA测距算法的准确性，并会引起基于时间的定位算法的测量误差，最小均方估计和边缘检测技术等能较好的抑制多径干扰的影响。

RSSI算法是一种很粗略的测距技术，有可能产生±50%的测距误差[7]，环境状况对信道产生的影响难以用模型准确表达，文献[8]对RSSI描述的对数衰减模型进行修正，将路径损耗因子与未知节点与锚节点之间距离的变化用负指数函数表示，在节点覆盖范围较广的情况下，采用此模型优势较为明显。如果节点覆盖范围不大（如室内等），也可以采用循环滤波等方法抑制噪声，使RSSI和距离的关系趋于稳定。

文献[9]中用K-means聚类方法通过聚类分析对误差较大的距离信息进行筛选，有效的降低定位误差。另外，采用两种或以上定位技术或者采用其它辅助手段混合的数据融合定位法，如TOA/AOA，TOA/RSSI等，以互补的优势和较高的精度被广泛使用。

2.3.2 位置估计阶段产生的误差及针对性算法

当一些误差较大的测距信息被排除掉后，如果只有两3个锚节点与未知节点的距离（角度）信息，可直接进行定位，如果锚节点较多，如何利用这些距离（角度）信息进行定位，涉及到算法复杂度和最终的定位误差。对某一个未知节点而言，锚节点的分布对其定位是有很大影响的，考虑到锚节点的布局规划对整个网络定位精度的影响，一些算法专门针对锚节点的几何布局进行了研究。还有采用移动锚节点进行辅助定位的方法，相当于布设了大量的静态锚节点，兼顾信号覆盖率以及几何位置对未知节点的定位影响，但移动锚节点的路径规划也存在许多待研究的问题。

在几何约束方法中，定位精度直接受锚节点的数量和分布的影响，而对测量误差不敏感，如果锚节点数量较少，定位误差会非常大，因此为了改善定位效果，可将已定位的节点升级为锚节点或采用移动锚节点，或者直接采用MDS或FP方法减少锚节点数量对定位的影响。

2.4 定位方案优势分析

根据节点定位过程，可以采用不同组合方式对未知节点进行定位，较常见的主要方案有：

TOA+三边测量法/极大似然估计：适用于对定位要求较高的场合等。除了GPS系统采用这种方案，很多算法都会在考虑时间同步及抑制NLOS误差的前提下采用此算法，如文献[6]中提出的考虑非视距传播影响的TOA定位算法，在恶劣的工业环境中的TOA优化定位方法[10]等。

TDOA+三边测量法/极大似然估计：适用于范围较小（若采用超声波测距）的无线网络中节点定位，对节点性能要求不高，算法复杂度适中。Cricket系统采用了TDOA+三边测量法，适合锚节点较少的情况。AHLos系统则采用了TDOA+极大似然估计，并将已定位的节点升级为锚节点来缓解锚节点较少的问题，但会造成误差累积。比较典型的Chan[2]算法，利用TDOA+极大似然估计对未知节点进行定位，在测量噪声为零均值的高斯随机噪声时，其定位解能达到CRLB，定位精度高，但当存在NLOS干扰时，定位精度明显下降，很多定位算法[6]都借鉴了其思想并加以改进。

RSSI+位置估计：无线传感网络一般会采用此方案，算法简单、无需额外硬件、能耗低、精度不高，根据文献[5]中的研究，当定位误差小于传感器节点无线通信半径的40%时，对路由性能、目标跟踪的精确度等影响不会很大。方案包括：RSSI+三边测量法，如DV-distance算法[11]；RSSI+几何定位法，例如采用RSSI值筛选锚节点，利用距离较近的锚节点用质心算法对未知节点定位[12]，定位精度介于测距与非测距算法之间，算法复杂度则与非测距算法类似；采用RSSI值（或节点连通度）+MDS建立相对坐标系统的MDS-MAP算法[13]，无需锚节点就可定位，如果提供几个锚节点，也可实现绝对坐标定位；RSSI+指纹识别，微软的RADAR系统是较早使用指纹识别的定位系统，采用匹配数据的方法定位，考虑了环境因素，需要大量的离线训练数据，且对于不同的环境需要重新采集数据，成本较高，文献[14]中提出无需训练的指纹识别定位算法，通过时域有限差分（FDTD）仿真来建立指纹库，节省离线训练时间。

单独使用AOA+三角测量法的算法较少，多作为辅助手段与其它算法配合定位。另外在特定的场合会采用特定的算法，比如适用于农田环境的无需锚节点的定位算法[15]，可以取得节点的相对位置坐标，但对环境知识的依赖度较高；在水下定位中，由于环境的特殊性以及不易部署固定的锚节点，RSSI测距以及几何约束方法不适合应用于此。

3 结束语

大部分无线网络应用都受限制于能量，而现有的定位算法中，高精度和低能耗的矛盾还没有更好的解决方法，平衡精度和能耗且具有较广的适用范围，是定位算法需要考量的重要方向。其次，目前无线网络的覆盖率高、发展迅速，基于无线网络的节点定位面临着不能忽视的安全问题，如节点的定位过程中受到攻击、对恶意节点定位造成的能耗等都会影响节点的正常工作。

根据现有的研究情况分析，二维定位算法的体系相对比较成熟，从定位精度、适用范围等方面都有大量深入的研究，但其应用比较有局限性。需要定位的节点往往位于三维环境中，由于增加了一个维度，定位所需的硬件要求和算法复杂度增加，导致二维定位算法在三维定位中不一定适用，可能会引起定位多解的问题。因此，对三维定位算法的研究不能仅从定位精度考虑，需要新的思路以保证算法有效可行。

[1]王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报，2005，16（5）:857-868.

[2]Chan Y T，Ho K C.A simple and efficient estimator for hyperbolic location[J].Signal Processing，IEEE Transactions on，1994，42（8）:1905-1915.

[3]Niculescu D，Nath B.Ad hoc positioning system （APS）[C]// GlobalTele-communications Conference，2001.GLOBECOM'01. IEEE.IEEE，2001（5）:2926-2931.

[4]Nagpal R，Shrobe H，Bachrach J.Organizing a global coordinate system from local information on an ad hoc sensor network [C]//Information Processing in Sensor Networks. Springer Berlin Heidelberg，2003:333-348.

[5]He T，Huang C，Blum B M，et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th annual international conference on Mobile computing and networking.ACM，2003:81-95.

[6]王昕，王宗欣，刘石.一种考虑非视线传播影响的TOA定位算法[J].通信学报，2001，22（3）:1-8.

[7]Meguerdichian S，Slijepcevic S，Karayan V，et al.Localized algorithms in wireless ad-hoc networks:location discovery and sensor exposure[C]//Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking&computing.ACM，2001:106-116.

[8]王日明，冯久超.改进的对数衰减动态非视距定位[J].应用科学学报，2014，32（4）:372-378.

[9]孙大洋.无线传感器网络中多边定位的聚类分析改进算法[J].电子学报，2014，42（8）:1601-1607.

[10]Lewandowski A，Wietfeld C.A comprehensive approach for optimizing toa-localization in harsh industrial environments [C]//Position Location and Navigation Symposium（PLANS），2010 IEEE/ION.2010:516-525.

[11]Niculescu D，Nath B.DV based positioning in ad hoc networks[J].Telecommunication Systems，2003，22（1-4）: 267-280.

[12]王慧锋，高瞻.认知无线电网络中基于接收信号强度的定位算法[J].数据采集与处理，2014，29（3）:465-471.

[13]Shang Y，Ruml W，Zhang Y，et al.Localization from mere connectivity[C]//Proceedings of the 4th ACM international symposium on Mobile ad hoc networking&computing. ACM，2003:201-212.

[14]Bisio I，Cerruti M，Lavagetto F，et al.A trainingless WiFi fingerprint positioning approach over mobile devices[J].IEEE Antennas&Wireless Propagation Letters，2014，13（1）: 832-835.

[15]郭建全，赵伟，黄松岭.农田环境无线传感器网络无锚节点定位算法[J].仪器仪表学报，2009，30（8）:1577-1583.

Analysis and development of positioning technology in wireless network

LV Qi-chen1，PANG Li-li2，XIE Jia-ye2
（1.94789 Troop，PLA，Nanjing 210018，China；2.Nanjing Institute of Technology，Nanjing 211167，China）

In the interest of combing through the development of wireless network positioning technology，and analyzing the advantages and problems of the existing positioning algorithms and systems，these positioning algorithms were compared from positioning accuracy，positioning scale，algorithm complexity，algorithm adaptability and feasibility based on the basic principle and evaluation criteria of the positioning technology.Considering the positioning accuracy and the feasibility of the positioning algorithms and systems，the specific classification and optimization of the positioning scheme for different applications are obtained.

wireless network；node-positioning；two-dimensional positioning；positioning error

TN98

A

1674－6236（2016）23-0162-04

2015-11-17稿件编号：201511161

江苏省高校自然科学研究面上项目（15KJB510014）；南京工程学院高层次引进人才科研启动基金项目（YKJ201444）

吕奇辰（1981—），男，湖北钟祥人，硕士，工程师。研究方向：信号处理、无线定位等。