无线传感器网络节点定位算法的研究

姜圣，张俊虎，高栋梁

0 引言

信息的生成、获取、存储、传输、处理及其应用，是现代信息科学的六大组成部分，其中信息的获取是信息技术产业链上的重要环节。随着现代微电子技术、微机电系统（MEMS）、片上系统SoC、无线通信技术、信号处理技术、计算机网络技术等的进步以及互联网的迅猛发展，传统传感器技术向微型化、智能化、网络方向发展，无线传感器网络（wireless sensor network ，简称WSN）[10][6]正是在这种背景下产生。由于它具有无线、自组织、成本低、体积小、不需基础设施支持的特点，在实际应用中越来越受到人们的关注。

无线传感器网络的工作区域很广，适用于人们无法接近的恶劣或特殊环境，传感器节点主要通过飞行器撒播、人工埋置和火箭弹射等方式任意散落在被监测区域内。节点的位置信息都是随机的，节点所采集到的数据，若没有位置信息几乎是没有应用价值的。所以，在无线传感器网络的应用中，节点的定位也就成为了关键的问题。

1 节点定位的相关算法

无线传感器网络节点定位算法很多，简述如下

（2）基于TOA(Time of Arrival)[16][3]的定位使用发射机到接收机之间往返的时间来计算收发机之间的距离，这种方法要求发射机和接收机是严格时间同步的。

（3）基于 TDOA(Time Difference Of Arrival)[16][2]的定位与TOA定位类似，不同之处在于它使用两种不同传播速度的信号，例如超声波信号和射频信号，二者传播速度不同，因此到达时间会有差异，从而利用这个时间差来求距离。

（4）基于AOA(Angle Of Arrival )[13]的定位是一种估算邻居节点发送信号方向的技术，可通过天线阵列或多个接收器结合来实现，AOA定位技术也受外界环境的影响，如噪声、NLOS问题等都会对测量结果产生不同影响。

（5）质心算法[8]是由BULUSUN等人提出的一个粗糙定位算法，在该算法中，参考节点周期性的向周围邻居节点广播参考节点分组，分组中含有参考节点标识号和位置信息，当未知节点收到来自不同参考节点分组数量超过某一个门限值后，就确定自身为这些参考节点组成的多边形的质心。

（6）DV-Hop算法[14][1]的基本思想是将未知节点到参考节点间的距离用平均每跳距离和两者之间的跳数乘积表示，该算法首先使用典型的距离矢量交换协议，使网络中所有节点获得距离最近的参考节点的跳数；获得其他参考节点位置和相隔跳数之后，参考节点计算网络平均每跳距离值，并将其广播至网络中。该值采用可控洪泛法在网络中传播，这样保证了绝大多数节点可从最近的参考节点接收该值。

（7）DV-distance算法[9]与DV-Hop算法类似，所不同的是相邻节点使用RSSI测量节点间点到点距离，然后，利用类似于距离矢量路由的方法传播与参考节点的累计距离。当未知节点获得 3个或更多参考节点的距离后使用三边测量定位。该算法适用于节点密集型网络。

（8）凸规划定位算法[7]将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集, 从而将节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方案，确定节点位置。

（9）Amorphous定位算法[15]分成两步，首先确定节点与每个参考节点之间的跳数，这个跳数是最小的跳数。然后通过节点与多个参考节点的跳数，使用多边测距来估计出最小均方差意义上的距离。

（10）APIT算法[11]的基本思想是未知节点侦听所有听得见的参考节点，再从这些参考节点中任选3个不共线的参考节点构成1个三角形，通过近似三角形内点测试法确定未知节点是否在三角形中，测试所有的三角形组合，就可确定多个包含未知节点的三角形区域。这些三角形区域的交集是一个多边形，计算这个多边形的重心，使用这个重心来估计未知节点的。

2 节点定位算法的定位精度分析

基于RSSI的定位使用理论或经验的信号传播模型将传播损耗转化为距离，该技术主要使用RF信号。它容易受到多径衰减（Multi-path Fading ）和非视距阻挡（Non-Line-Of-Sight，NLOS）的影响，具有时变特性，测量误差很大，精确度偏低。Euclidean算法是基于RSSI定位技术的一种算法。

基于 TOA的定位是通过测量信号传播时间来测量距离。该定位技术使用高能耗的电子设备和精确的时间计算元件，在测量精度上较高。Cooperative ranging算法和Two-phase positioning算法是基于该定位技术的算法。

基于 TDOA的定位使用两种不同传播速度的信号来测量节点距离，通常使用超声波和电磁波，由于受到超声波传播距离有限和 NLOS问题对超声波信号的传播影响，测量精度不高。AHLos 算法和 N-HOP multilateration primitive算法是基于该定位技术的算法。

基于AOA的定位是一种估算邻居节点发送信号方向的技术，可通过天线阵列或多个接收器结合来实现，AOA技术也受外界环境的影响，如噪声、NLOS问题等都会对测量结果产生不同影响。同时，AOA定位需要特殊硬件测量接收信号的方向夹角，因为测量信号夹角时很难得到精确值，定位精度不高。 DV-Bearing算法和DV-Radial算法是基于该定位技术的算法。

质心算法是根据网络的连通性确定目标节点周围的参考节点，直接求解参考节点构成的多边形的质心。质心算法的定位精度与两个相邻参考节点之间的距离有关，参考节点的部署位置将影响到定位精度，质心算法实现的是粗粒度定位。

DV-Hop算法将待定位节点到参考节点之间的距离用网络中节点的平均每跳距离和节点之间的跳数的乘积来表示，使用三角定位来获得节点的位置信息。

DV-distance算法中相邻节点使用RSSI定位技术测量节点间点到点的距离，然后利用距离矢量路由的方法传播与参考节点的累计距离，在测量点到点距离时产生的误差将会影响到算法的定位精度。

凸规划定位算法将节点定位问题转化为凸约束优化问题，然后使用半定规划和线性规划方法得到一个全局优化的解决方案，凸规划定位算法的定位精度较高。

Amorphous定位算法建立在两个前提条件下：一是所有节点的有效通信半径相同且已知；二是网络布设区内节点密度足够大或网络连通性较高，这种方法的本质是应用广度优先准则建立以跳数作为距离的最短路径。

APIT算法需要找到若干个由参考节点构成的三角形，需要定位的节点在三角形内，则节点必然在这些三角形的交集内。使用这个交集的重心估计节点的位置。APIT算法在不规则传播信号模式和节点随机部署的条件下，精度可以达到厘米级。

不同的定位算法的定位精度会因为不同的因素影响而有差别，正如表1所示的那样：

表1 节点定位算法定位精度分析

3 节点定位算法对节点密度依赖性分析

基于RSSI的定位由于容易受到环境因素例如：多径衰减和非视距阻挡的影响，在节点间距离长时这种影响将会增大从而增加了误差，所以这种定位技术适合节点密度高的区域。

基于TOA的定位主要依靠高功耗的节点来实现精确计算，这种定位技术对节点的密度要求不高，节点密度的高低不是影响定位精度的决定因素。

基于 TDOA的定位使用两种不同传播速度的信号来进行距离测量，在节点密度过大时，容易产生通信冲突，所以它更适合节点密度低的场合。

基于AOA的定位是依靠测量角度来求得距离，需要估算邻居节点发送信号的方向，需要多个天线阵列和节点接收器来实现，节点密度大时更利于方向的测量。

质心算法需要根据网络的连通性确定参考节点，需要较高的节点密度，参考节点部署的位置对定位效果影响很大。

DV-Hop算法不需要节点具备测距能力，对节点的硬件要求低但是需要在节点密度高的网络中，才能合理的估算平均每跳距，DV-Hop算法要求较高的节点密度。

DV-distance算法也仅适用于节点密度高的网络但对于节点性能的要求比较低，节点不用储存网络中各个节点的位置信息，降低了节点的能耗。

凸规划定位算法主要是将整个网络模型化为一个凸集，然后找到全局优化解决方案，在这个过程中主要是实现了计算方式的转化，节点密度的高低并不影响到转化后的计算，所以这种算法并不要求高的节点密度。

Amorphous定位算法引入了多参考节点进行估计求精，并且该算法有一个前提假设即为网络布设区内节点密度足够大，所以不定型算法需要较高的节点密度才能实现精确地定位。

APIT算法需要足够的PIT三角形才能够达到精度要求，因为不在同一条直线的三个点才能构成一个三角形，这就需要在通信范围内有足够的参考节点。对于通信范围内的节点密度有较高要求。

总之，节点定位算法中许多对节点密度要求很高，但是也有部分算法适用于节点密度低的场合。如表2所示：

表2 节点定位算法对节点密度依赖性分析

4 节点密度和定位精度相关性分析

通过表1和表2可以看出，节点定位算法在节点密度高的条件下，更能实现较高精度的定位，节点稀疏的条件是不适合的。通常定位精度会随着节点密度的增加而有所增加。这是由无线传感网络的特性决定的。

图1 节点密度和定位精度间关系示意

在图 1中可以看到算法的定位精度是随着节点密度增加而逐步增加的。在上图中，基于TOA定位算法是较特殊的一种算法，主要是因为该算法主要是依赖高能耗的电子设备和精确计算元件来测量距离，因而节点密度增加的时候，定位精度不是很快的增加，所以该算法对于节点密度的要求也不是很高。

5 节点定位算法的通信开销分析

基于RSSI的定位是通过信号的衰减来测量距离，当节点间距离较大时，会受到 NLOS的影响从而增大了节点间的通信量，通信开销较大。

基于TOA的定位是利用单程信号传播来测量距离，只要求发射机将信号发出然后接收机接收即可，也就是说它只需要收发节点的同步信息，这样通信开销就降低了。

基于 TDOA的定位使用两种不同的信号，信号在发射机和接收机之间进行往返传播，这样信号的传输距离较大从而增加了通信开销。

基于AOA的定位是依靠角度测量的方式来测量节点间距离，接受机只需要接收信号即可，这样单程信号传播所造成的通信开销较小。

质心算法中由于是参考节点周期性的向邻近节点广播带有参考节点标识号的分组，并不是持续不断的信息传送，所以该算法的通信开销小。

DV-Hop算法在获得平均每跳距离的计算过程中，使用泛洪的形式在整个网络中广播每个参考节点的信息，使得每个未知节点统计出距离每个参考节点的最短跳数和坐标信息，这样算法的通信开销就很大。

DV-distance算法中节点不用存储网络中各个节点的位置信息，减少了节点间的通信量，所以该算法的通信开销很小。

凸规划定位算法将节点间点到点的通信连接视为节点位置的几何约束，把整个网络模型化为一个凸集，把定位问题转化为凸约束优化问题，这样节点间的通信开销就得到降低。

Amorphous定位算法实质上是DV-Hop算法的增强，引入了多参考点测量进行估计求精的步骤，而且采用通信半径作为每跳距离，大大减少了通信开销。

APIT算法在实现过程中要把参考节点以3个为一组后穷尽所有参考节点，判断这3个点构成的三角形中是否包含未知节点，这样在不断测试参考节点的过程中，就使通信开销增大。

定位算法的通信开销因为各自算法设计思想的不同而有所区别，如表3所示：

表3 节点定位算法的通信开销分析

6 通信开销与定位精度相关性分析

通过对表1和表3的分析可以发现节点定位算法的通信开销和定位精度间有一定关系，如图2所示：

由图2可以看到随着通信开销的增加，定位精度也会随着通信开销而增加，这是因为在通信开销增加的时候，节点所传输的信息量就大，从而能够更加准确的进行定位。

在图中可以看到，Amorphous算法的通信开销比较小，但是定位精度却很高，主要是由于该算法有两个前提条件：一是所有节点的有效通信半径相同且已知；二是网络布设区内节点密度足够大或网络连通性较高，并且该算法还引入了多个参考节点进行估计求精，并修正了跳数的估计方法和每跳距离估计方法，这样就在通信开销较小的情况下可以实现高精度的节点定位。

图2 通信开销和定位精度相关性示意

7 节点定位算法健壮性分析

基于RSSI的定位如Euclidean算法受环境影响较大，受环境影响所造成的如反射、多径传播、非视距、天线增益等问题都会对相同距离产生不同的传播损耗。所以，这种定位的自适应能力较差，健壮性较低。

基于TOA的定位由于节点间具有精确地时间同步，并且节点具有较高的能耗，不易受环境的影响，自适应能力较高，具有较高的健壮性。

基于 TDOA的定位主要依靠超声波进行传播，但是超声波传播距离有限并容易受NLOS问题影响，健壮性一般。

基于AOA定位技术也容易受外界环境影响，如噪声、NLOS问题等都会对测量结果产生不同的影响，这就降低了它的健壮性。

质心算法实现的是一种粗粒度定位，参考节点的分布对定位精度的影响很大，该算法的自适应能力不高，健壮性较低。

DV-Hop算法仅在节点密度高的网络中，才能估算平均每跳距离，当网络中节点密度下降时，该算法就无法有效定位。

DV-distance算法也仅适用于节点密度高的网络中，当网络中节点密度较低时，该算法的测量误差就增大，所以该算法的自适应能力不高。

凸规划定位算法将定位问题转化为凸优化约束问题，具有容忍错误的能力，这样算法的容错性就得到提高。

Amorphous定位算法既可以不使用测距来定位，也可以使用测距来定位，并且引入了多参考节点来提高精度，该算法的自适应能力和容错性较好。

APIT算法需要足够的PIT三角形才能达到精度要求，当定位区域内节点稀疏时则很难找到足够的三角形，也就实现精度定位，所以该算法在节点变为稀疏的时候无法有效定位。

节点定位算法的健壮性也是评价算法优劣的重要指标，不同算法的健壮性也是不同的，如表4所示：

表4 节点定位算法健壮性分析

8 节点定位算法对硬件设施的依赖性分析

基于RSSI的定位依靠发射机和接收机来测量，主要影响问题是信号的传输衰减。对于硬件的依赖程度不高。

基于TOA的定位对硬件的依赖很大，以GPS定位技术最为代表性，它需要依靠高能耗的电子设备和精确的电子时钟来进行全球定位。

基于TDOA的定位和基于TOA的定位比较相似，只是使用的信号不同，这种定位技术也对硬件设施有较高的依赖。

基于AOA的定位需要特殊硬件测量接收信号的方向夹角，所以该定位技术对硬件的依赖也较高。

质心算法的实现比较简单，根据网络的连通性确定参考节点，直接就求解参考节点构成的多边形的质心。该算法对硬件的依赖程度较低。

DV-Hop算法使用三边测量（Trilateration）或者多边测量（Multilateration）的方法计算出节点的位置，所以对硬件的依赖程度不高。

DV-distance算法和DV-Hop算法类似，区别在与节点测量间距的方式不同，所以该算法对硬件的依赖程度不高。

凸规划定位算法对硬件设施的依赖程度也不高。

Amorphous定位算法实质是DV-Hop算法的增强，所以，该算法对硬件的依赖程度不高。

APIT算法使用三角形内点测试法，对硬件的依赖程度较低。

不同节点定位算法对硬件的依赖是不同的，这与算法本身的定位方式有关，不同定位算法对硬件的依赖性如表5所示：

表5 节点定位算法对硬件依赖性分析

9 结论

据是样分析，将定位算法的特点归纳成表如表6所示：

表6 节点定位算法的分析综合表

位基于AOA的定位 一般 高 较低 较低 较低质心算法 较低 高 较低 一般 较低DV-Hop算法 一般 高 高 较低 一般DV-Distance算法 一般 高 较低 较低 较低凸规划定位算法 高 一般 一般 一般 一般Amorphous算法 一般 高 较低 高 较低APIT算法 一般 高 一般 较低 较低

定位技术是无线传感器网络应用的前提，定位的准确性直接关系到传感器节点采集数据的有效性，无线传感器自身所有的特点决定定位算法必须具有好的健壮性，在这一点上，凸规划算法具有较好的健壮性；为了使传感器的使用寿命延长，算法的通信开销尽量要低，这一点上 Amorphous定位算法做得较好，在无线传感器的现实应用性方面，还没有一种普遍适用的算法，一方面由于应用的场合不尽相同，另一方面算法自身都有各自的不足，所以必须针对不同的应用场合来选择合适的定位算法。

[1]白进京,严新平,张存保.基于加权质心和DV-Hop混合算法WSN定位方法研究.计算机应用研究[J]2009 (6)2247-2250.

[2]刘爱平,刘忠,梁钥,周伟.基于距离的分布式无线传感器网络定位算法.计算机应用研[J],2008,25(8):2528—2531.

[3]焦磊,邢建平,张军.一种非视距环境下具有鲁棒特性TOA无线传感网络定位算法[J]. 传感技术学报,2007,22(7): 1625- 1629.

[4]周祖德,王晟.一种适用于复杂环境的无线传感定位算法[J].武汉理工大学学报, 2006, 28(11): 121-124.

[5]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857—8687.

[6]David Culler, Prabal Dutta, Cheng Tien Eee, Rodrigo Fonseca, JonathanHui,Philip Levis, Joseph Polastre, Scott Shenker, Ion Stoica, Gilman Tolle. Towards a Sensor Network Architecture: Lowering the Waistline.In:Proceedings of the Tenth Workshop on Hot Topics in Operating Systems 2005.

[7]Xiang Ji,Zha Hong—yuan.Sensor positioning in wireless ad-hocsensor networks using multidimensional scaling[J].IEEE INFOCOM2004 一The Conference on Computer Communications，2004，23(1)：2652—2661.

[8]Morre D, Leonard J, Rus D, Teller S.Robust Distributed Network Local-ization with Noisy Range Measurement.SenSys’04,Nov 2004.

[9]Niculescu D, Nath B. Ad hoc positioning system (APS)using AoA. In: Proc. of the IEEE INFOCOM 2003. Vol.3,San Francisco: IEEE Computerand Communications Societies, 2003. 1734−1743.

[10]Ren FY, Huang HN, Lin C. Wireless sensor networks.Journal of Software, 2003,14(2):1148−1157.

[11]SIMIC S N，SASTRY S.Distributed localization in wireless ad hocnetworks[R]，Berkely：university of California，2002.

[12]Girod L, Bychovskiy V, Elson J, Estrin D. Locating tiny sensors in time and space: A case study. In: Werner B, ed.Proc. of theT2002 IEEE Int’l Conf. on Computer Design:VLSI in Computers and Processors. Freiburg: IEEE Computer Society, 2002. 214−219.

[13]Girod L, Estrin D. Robust range estimation using acoustic and multimodal sensing. In: Proc. of the IEEE/RSJ Int’l Conf.onIntelligent Robots and Systems (IROS 01). Vol.3,Maui: IEEE Robotics and Automation Society, 2001.1312−1320.

[14]Bulusu N, Heidemann J, Estrin D.Density Adaptive Algorithms for Bea-Con Placement in Wireless Sensor Networks.Technical Report ULCA-CS-010013,2001.

[15]Doherty L, Pister KSJ, Ghaoui LE. Convex position estimation in wireless sensor networks. In: Proc. of the IEEE INFOCOM 2001.Vol.3, Anchorage: IEEE Computer and Communications Societies, 2001.1655−1663.

[16]Harter A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. In: Proc. of the 5th Annual ACM/IEEEInt’l Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999. 59−68.