无线传感器网络定位算法研究进展
开篇：润墨网以专业的文秘视角，为您筛选了一篇无线传感器网络定位算法研究进展范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：无线传感器网络作为一种全新的信息获取和处理技术，可以在广泛的领域内实现目标监测、信息采集和目标追踪等任务，节点定位问题则是许多应用的基础，是无线传感器网络的支撑技术之一。对基于测距定位算法和免于测距定位算法进行了分析对比，并对无锚节点这一新的节点定位技术做了介绍。最后对节点定位算法的优缺点作了总结，并对节点定位技术未来趋势进行展望。
关键词：无线传感器网络； 节点定位； 基于测距定位； 免于测距定位； 无锚节点定位
中图分类号：TN71134； TP393文献标识码：A文章编号：1004373X(2011)23002704
Research on Localization Algorithm for Wireless Sensor Network
WANG Liang, CAO Jianan
(Institute of Electrical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)
Abstract： Wireless sensor network (WSN) as a new information acquisition and processing technology can be widely used within the field of target monitoring, information acquisition and target tracking. Sensor node localization problem is a basis for many applications and one of the support technologies of WSN. The rangebased WSN localization algorithm and rangefree WSN localization algorithm are analyzed, and a new nonanchor node localization technology is introduced. Finally, the advantages and disadvantages of existing localization algorithm are summarized and the future trend is put forward.
Keywords： WSN; node localization; rangebased; rangefree; nonanchor node localization
收稿日期：201105110引言
无线传感器网络(WSN)［1］是由大量的廉价微型传感器节点组成的一个多跳、自组织的无线网络系统，其目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者。在大多数应用中, 不知道传感器节点位置的数据是没有意义的，节点具备定位能力(如借助GPS或其他定位手段)对于许多应用来说是一个非常重要的前提。
自1992年AT&T实验室开发出室内定位系统ActiveBage至今，研究者们已经提出许多定位系统和算法。但是每一种系统和算法都是应用于不同的问题或领域，它们在用于定位的物理现象、网路组成、能量需求、基础设施等许多方面都有所不同。目前，应用于实际环境的WSN定位算法研究尚不完善，还需要进一步的研究工作，提出更高效、健壮的定位算法。
文中需要定位的节点称为未知节点；已知自身位置并协助未知节点定位的节点称为参考节点或锚节点(anchornode)。
1定位算法性能评价和分类
WSN定位系统和算法的性能直接影响其可用性，定位算法的评价是一个需要深入研究的问题。常用的评价标准有［2］：定位精度、锚节点密度、功耗、成本、规模、网络连通度、容错性和自适应性等。这些标准也是WSN定位系统和算法设计和实现的优化目标；但在实际的应用中，需要根据具体的需求做出权衡，选择设计合适的定位算法。
无线传感器网络节点定位算法有许多种不同的分类方法［23］：根据定位结果分为绝对定位和相对定位；根据计算方式分集中式算法和分布式算法；根据有无测距分为基于测距算法和免于测距算法；根据计算次数分为一次求精算法和循环求精算法；根据定位信息粒度分为细粒度算法和粗粒度算法；根据有无锚节点分为有锚节点算法和无锚节点算法。
2测距定位算法
测距定位算法(Rangebased)可分两个步骤实现：
(1) 测距/测角，用特定的方法测量估计两节点之间的距离或角度信息；
(2) 定位估计，根据距离信息采用相关的定位方法获得节点的位置信息。
2.1测距/测角技术
(1) 接收信号强度［4］(Received Signal Strength Indicator,RSSI)：根据接收到的RSSI值计算出信号的传播损耗，然后利用信号传播模型将其转化为距离信息，该技术主要使用RF信号。商业无线芯片本身具有RSSI获取功能，无需额外硬件；故其是一种低功率、低成本的测距技术。缺点在于测距误差较大，误差主要来源有遮挡、反射、多径传播、非视距(Nonlineofsight,NLOS)、天线增益等。
(2) 信号传播时间(Time of Arrival,TOA)：已知信号的传播速度根据信号两点间的传播时间来计算传输距离，需要精确的时间同步，因此需要昂贵的、高能耗的电子设备来确保时间同步，如GPS定位系统。因WSN节点的硬件尺寸、价格和功耗等限制，实际应用TOA技术的的定位方案比较少。
(3) 信号传播时间差(Time Difference on Arrival,TDOA)：根据两种信号在两点间的到达时间差及信号传播速度计算出两点间的距离，不需要时间同步。一般在节点上安装超声波收发器和RF收发器，测距时在发射端同时发送两种无线信号，利用声波和电磁波在空气中传播速度的巨大差异，在接收端记录两种信号的到达时间，直接把时间转换为距离。该技术定位精度高，可达厘米级，但受限于超声波传播距离限制和NLOS问题对超声波信号的影响。
(4) 信号到达角度(Angle of Arrival,AOA)：通过天线阵列或多接收机感知接收节点信号到达方向，计算接收节点和发射节点间的相对方位或角度。AOA技术易受外界环境影响，如噪声、NLOS问题等都会对测量结果产生不同影响。同时，AOA还需要额外的硬件，不满足传感器节点对成本和功耗的要求。
以上四种测距方法各有利弊测距技术比较见表1。其中，RSSI技术低功耗、低成本的特点更适合于无线传感器网络的需求。
表1测距技术比较
测距技术精度功耗硬件成本RSSI低低低TOA较高高高TDOA高高高AOA中高高
2.2定位计算方法
对基于测距的定位技术来说，提高测距精度是提高定位精度最有效的途径，但难点在于测距的实现要受到节点能量、硬件复杂度及尺寸限制。而实际应用中，测距精度不可能无限调高，这就需要从算法的角度进一步提高定位精度。这类定位机制中典型的定位方法有三边测距法或多边测量、三角测距法等,如图1所示。
图1定位原理图(1) 三边测距法和多边测距法
在二维空间中，知道一点到三点或三点以上的距离就可以确定该点的坐标，如图1(a),图1(b)所示，三边测距法的原理就是求解三个已知半径和圆心坐标的圆的交点，可表示为：(x-xi)2+(y－yi)2=r2i,i=1,2,3(1)由于在实际应用中，节点间测距存在误差，往往无法相交于一点，为求解出与实际坐标差异最小的点，常使用最小二乘估计法来计算未知节点坐标。设锚节点坐标分别为(x1，y1)，(x2，y2)，…，(xk，yk)，未知节点S的坐标为(x，y)，S到锚节点的测量距离为Si；根据最小二乘法原理：
设目标函数:F=min∑(dSi－Si)2式中:dSi=(x-xi)2+(y－yi)2采用优化的方法使估计位置与实际位置间的差最小，从而估计出节点S的坐标。
(2) 三角测距法
三角测距法也称AOA定位法，如图1(c)所示，设参考节点A和B的坐标分别为(x1，y1),(x2，y2)，待定位节点S的坐标为(x，y)，节点S到参考节点A和B的角度分别为θ1和θ2，则有如下关系式：tan θi=x－xiy－yi,i=1,2(2)通过上述非线性方程组可得未知节点S的坐标(x，y)。
3免于测距定位算法
基于测距的定位技术定位精度相对较高，但是对节点的硬件也要求较高。针对无线传感器网络的特点，研究者们提出了免于测距定位技术(Rangefree)，这类定位方法仅需要得到待定位节点与相邻节点间的连通信息，然后利用各种优化方法估计待定位节点位置。
3.1质心定位算法
质心定位算法是一种基于网络连通性的粗略定位，其主要思想［5］是：参考节点每隔一段时间向相邻节点广播一个含有自身ID和位置信息信标数据包，当接收到不同参考节点的数据包数量超过某一个阈值或接收一定时间后，该节点就确定自身位置为这些参考节点所组成的多边形的质心，如图2所示。设待定位节点D的坐标为(X，Y)，参考节点数量为N，则利用如下公式来估计它的位置：(X,Y)=X1+X2+…+XNN,Y1+Y2+…+YNN(3)质心定位算法的明显优势是简单和易于实现，完全基于网络连通性，但显然，该算法仅能实现粗粒度定位，需要较高的节点密度。
图2质心算法3.2DVHop算法
DVHop算法主要由三个阶段［67］组成：
(1) 利用典型的距离矢量路由协议，是网络中所有待定位节点获得距参考节点的跳数信息。
(2) 在获得其他参考节点位置和与自身相隔跳数信息后，每个参考节点估计整个网络的平均每跳距离，第i个参考节点估计的平均每跳距离HopSizei为：HopSizei=∑(xi-xj)2+(yi-yj)2∑hj(4)式中：(xj，yj)为第j个参考节点的位置;hj为从第j个参考节点到第i个参考节点的跳数；然后将所获的平均距离作为一个校正值广播至整个网络。
(3) 待定位节点根据所获得的跳数和平均距离校正值计算距参考节点的距离，当得到3个或3个以上的参考节点的距离信息后，采用三边测距或多边测距定位法执行。
DVHop算法不需要节点具备测距能力，算法简单、易于实现，对于各向同性的密集网络，可以得到合理的平均每跳距离，从而达到合适的定位精度。但对于不规则的网络拓扑，定位精度迅速下降。
3.3Amorphous定位算法
Amorphous算法［8］与DVHop类似，区别在于该算法采用不同的方法估单跳平均距离。该方法假设单节点的连通度nlocal已知，根据KleinrockSlicerster公式来离线计算平均每跳距离HopSize：
HopSize=R(1+e-nlocal-∫-1le-nlocalπ(arccos t-t1-t2 ))(5)
与DVhop类似的方法来获得距参考节点的跳数(称为梯度值)。待定节点i收集相邻节点的梯度值，计算关于某个参考节点的局部梯度平均值，即：Si=∑j∈nrbs(i) hj+hi|nrbs(i)|+1-0.5(6)式中:hi为节点i的梯度值；nrbs(i)为节点i的所有邻居节点。
待定位节点i使用Si×HopSize来计算与每个参考节点间的距离，最后利用三边测距法或多边测距法来进行定位估计。
该算法仅需要通过局部信息和局部通信协调就可实现定位，当网络平均连通度在15以上时能实现较好的定位精度；缺点是需要预知网络平均连通度，且需要较高的节点密度。
3.4MDSMAP算法
MDSMAP算法是一种集中式定位算法，可在rangefree和rangebased两种情况下运行，并可根据实际情况实现相对定位和绝对定位。该算法有三个步骤［9］：
(1) 首先从全局角度生成网络拓扑连通图，并为图中每条边赋予距离值。当节点具有测距能力时， 该值就是测距结果；当仅拥有连通性信息时，则此边赋值为1。然后使用最短路径算法(如Floyd算法)，生成节点间的距离矩阵。
(2) 对距离矩阵应用MDS技术，生成整个网络的二维或三维相对坐标系统。
(3) 当拥有足够的参考节点(二维最少3个，三维最少4个)，可将相对坐标转化为绝对坐标系统。
文献［9］中的实验结果显示，该算法定位精度与锚节点密度相关，当网络连通度达到12.2时，几乎所有节点都可实现定位，定位误差约为30%；而在测距条件下，定位误差为16%(测距误差为5%)。
3.5APIT算法
APIT算法的主要思想［10］是一个待定位节点入选3个相邻参考节点，测试自己是否属于它们所组成的三角形中；使用不同参考节点组合重复测试直到穷尽所有组合或达到所需定位精度，最后计算包含待定位节点的所有三角形的交集质心，并以这一点作为待定位节点位置，如图3所示。
APIT算法的优点在于硬件要求较低，定位能耗小，且定位性能也较好；缺点在于参考节点密度要求较高。
图3APIT定位总体而言，免于测距算法性能受通信距离、参考节点数量以及参考节点的分布方式等因素影响。几种算法的侧重点也不同，DVHop和Amorphous算法侧重于距离估计技术，及如何较好地估计待定位节点与参考节点间的距离，然后用基于测距的方法进行定位估计；质心算法、MDSMAP算法和APIT算法侧重于位置估计，及如何仅根据网络内节点连通信息来获得比较精确的位置估计,五种算法的性能比较见表2。
表2距离无关定位算法性能比较
算法精度锚节点密度通信开销计算开销质心算法与锚节点密度相关高小小DVHop算法低中高较高Amorphous算法中中较高较高MDSMAP算法与锚节点密度相关高较高高APIT算法与锚节点密度相关高中小
4无锚节点定位算法
基于锚节点的定位算法定位精度受锚节点密度、拓扑结构的限制，考虑到这些限制和成本等因素，近年来，研究者提出几种锚节点无关的定位技术。锚节点无关算法无预先确定位置信息，仅根据局部距离信息确定节点坐标,目前已提出的锚节点无关算法有AFL算法、KPS算法和ABC算法。
(1) AFL［3］(Anchor Free Localization)算法是一种完全分布式算法。该算法分两步：第1步运用启发式原理得到一个无折叠区域结构接近实际的布局；第2步采用基于质点弹簧模型的优化算法修正误差。
(2) KPS［11］(Deploymentknowledgebasedpositioning System)算法是一种预先配置知识和配置概率分布的算法。该算法首先建立预先配置的知识模型，然后根据预配置的模型进行初步定位，最后应用最大似然估计方法计算位置信息。