具有稳健性的无线传感器网络定位算法

宋 伟，樊孝明，王 玫

(桂林电子科技大学 信息与通信学院，广西 桂林541004)

位置信息往往是许多无线传感器网络应用的前提［1］。近年来，超宽带(UWB)、chirp线性调频(CCS)技术广泛应用于无线传感器网络的定位，IEEE 802.15.4a就规定了这两种信号作为物理层［2］，利用信号的波达时间来测量信标节点与位置节点之间的距离。在测距精度、抗多径干扰上都有很好的表现。但是非视距(NLOS)误差还是一个影响定位精度的主要问题，关于非视距误差，Venkatesh和Buehrer提出了一种基于线性优化的算法，此算法的假设条件是对测距值中是否包含非视距误差已经做出了鉴别，这在实际应用中往往难以实现［3］。因为关于非视距的鉴别，通常是通过大量的统计实现的，Wylie就基于包含非视距误差的测距值比不包含的测距值的标准差大，提出将实测的测距值的标准差与视距环境时的标准差进行比较，在无线传感器网络中，节点通常体积、电池能量都很有限，进行多次测量求标准差，势必消耗大量的能量［4］。CHEN提出一种残差加权算法，通过不同的组合分别求出目标节点的位置，再根据与测距值的残差来进行加权，对非视距误差有一定的抑制作用，缺点是计算量太大，在能量有限的无线传感器网络中同样不适用［5］。

本文基于最小一乘法思想，提出一种组合中位最小二乘定位(Combination Median Least Squares)算法，在少数未知节点与信标节点之间出现非视距误差时，有很好的抑制作用。

1 传统定位算法

传统的基于距离的定位算法一般采用极大似然估计法(Maximum Likelihood Estimation)［3］，如图1，已知1，2，3等n个节点的坐标分别为(x1，y1)，(x2，y2)，(x3，y3)，…，(xn，yn)，它们到节点D的距离分别为d1，d2，d3，…，dn，假设节点D的坐标为(x，y)，那么存在

图1 极大似然估计法示意图

这是一个非线性方程组，把x2+y2作为一个未知项，方程组可以化为一个线性方程，此线性方程表示式为AX=B，其中v=x2+y2，且

此线性方程一般用线性最小二乘法，有确定的解的形式

测距值的表达式

式中:di为测量距离值;dit为真实距离值;ei为测距误差，通常可以认为是标准差很小，均值为0的正态分布;ni为非视距误差，通常可以认为是服从具有正均值和较大方差的正态分布［6］。可见，非视距误差是影响定位精度的主要因素。

2 最小二乘法与最小一乘法比较

最小二乘法产生于1795年，18岁的高斯应用最小二乘法准确地预测了神谷星(Ceres)的运行轨道［7］。最小二乘最简单的解释方式就是算数平均，设要对一个未知量α做估计，观察了n次，结果分别是x1，x2，x3，x4，…，xn，估计真值为b，设残差

这导致了以下做法，即设

找出b，使L(b)得最小值，利用求导取最小值

求出的即为测量值的算数平均值。

最小二乘法在数据不存在异常值的情况下有很好的效果，但最小二乘法对超出量很敏感［8］。如果有一种方法对超出量不敏感，即说这种方法具有稳健性。于此相对，波斯维奇在1760年提出了最小一乘法，他在测量子午线的时候，提出了最小一乘准则。与最小二乘准则不同，最小一乘准则是使残差的绝对值的和最小即

式(10)取最小值，在一维的情况下便是测量值的中位数med［9］。

举个简单的例子，比如要求一只篮球队的平均年龄，假设分别为(20，21，22，25，30，31，19)，如果按照最小二乘准则，平均年龄为27，根据最小一乘准则，得出中位数22，但如果出现了超量值，比如说球队中有两个教练，年龄为60与65，根据最小二乘准则，平均年龄为32，根据最小一乘准则，得出中位数为25，明显，这个值更符合人们对这只球队年龄的认识。有人做过实验，大量测量数据用最小二乘法与最小一乘法分别拟合一条直线，最小一乘法更加符合人眼的直观印象。所以说，最小一乘法有更好的稳健性。最小一乘法比最小二乘法诞生更早，但由于计算上的问题无法得以解决，所以直到1950年提出了线性规划的方式求解以及电子计算机的出现，才一定程度上解决了最小一乘法的计算问题。

3 算法与仿真

3.1 算法描述

根据最小一乘法对超量误差的抑制以及计算上的困难，提出一种组合中位最小二乘(Combination Median Least Squars)算法，仿真证明，在有少量非视距误差存在的情况下，对非视距误差有显著的抑制效果。CMLS算法有以下步骤:

1)如果有m个信标节点，1个未知节点，进行定位最少需要3个信标节点，所以m个节点就有种组合，设=k。

2)每一种组合用线性最小二乘法计算出一个坐标值，k组定位结果为(x1，y1)，(x2，y2)，(x3，y3)，…，(xk，yk)。

3)再用最小一乘法分别求出横坐标与纵坐标的中位数。对x1，x2，x3，…，xk与y1，y2，y3，…，yk分别进行最小一乘法，即找出了x1，x2，x3，…，xk与y1，y2，y3，…，yk的中位数。

这样就把一些包含非视距误差的组合所定出的点排除在外。根据中位数可知，只要有超量误差的数量不超过总量的一半，最后的取值一定还是在没受到超量误差影响的值中，所以不会影响到所得的结果。

3.2 实验仿真

为体现CMLS算法的效果，将本文算法与CHEN提出的RWGH［5］算法以及传统的LS算法进行比较。因为算法的效果不仅与测量噪声与非视距误差有过，还与节点的分布有关，所以设在50 m×50 m的区域平均分布生7个点，(21.34，25)，(30，20)，(38.66，25)，(38.66，35)，(30，40)，(21.34，35)，(30，30)，其中(30，30)是未知节点的真实位置，其余为信标节点。未知节点与信标节点的真实距离为d1t=d2t=d3t=d4t=d5t=d6t=10 m。根据式(6)，设测距误差满足ei～N(0，0.52)，定位精度用均方根误差(RMSE)来评价

针对固定长度的NLOS误差来仿真，做1 000次仿真求RMSE，设d3中有非视距误差，仿真结果如图2所示。

图2 1/6的信标节点包含NLOS误差情况下的均方根误差比较

可以发现组合中位最小二乘法(Combination Median Lesat Squares，CMLS)比传统的最小二乘法(Least Squares，LS)以及RWGH算法在针对非视距误差有显著的抑制作用。RWGH算法虽然在一定程度上也有效，但是根据非视距误差的增大，效果变得不稳定，而CMLS算法一直有很好的表现。RWGH与CMLS均需要进行多个LS运算，但CMLS所需要的运算量要少于RWGH，对比见表1，而且RWGH还需要进行残差加权，更增加了运算量。

表1 RWGH与CMLS算法LS运算量的对比

但是也要指出，在6个信标节点中，如果出现2个或多个信标节点到未知节点之间有非视距误差时，此算法的性能将显著下降，如图3所示。

图3 2/6的信标节点包含NLOS误差情况下的均方根误差比较

如图3显示，6个信标节点中有两个测距值出现NLOS误差时，RWGH与CMLS算法性能均不能满意。需要说明的是，CMLS算法在有6个信标节点时，3个1组，将有20种组合，如果一个信标节点出现非视距误差，将污染=10组定位数据，刚好是所有数据的一半。根据最小一乘法取中位数的思想，在20个横坐标或纵坐标中取中位数，只要被污染的数据不超过总量的一半，就可以抑制这些超量误差对最后结果的影响。比如13个信标节点的测量值中包含2个非视距误差时，将污染120组数据，而总共有286组数据。18个信标节点中3个非视距误差污染的测量值时，将污染256组数据，而总数有816组数据。这些情况下都可以很好地抑制非视距误差。

4 结论

通过分析传统的最小二乘法与NLOS误差之间的关系，提出了CMLS算法。该算法不需要鉴别非视距误差是否存在，更不需要对测量值进行加权，只需一次测距，就可以在少量存在非视距误差的情况下很好地抑制非视距误差。此算法与定位系统的物理层无关，可以应用在蜂窝无线定位等其他基于距离的定位系统中。此算法还避免了最小一乘法计算困难的缺点。

［1］KIM Y J，GOVINDAN R，KARP B，et al.Geo-graphic routing made practical［C］//Proc.NSDI’05.Berkeley，CA，USA:USENIX Association，2005:217-230.

［2］IEEE P802.15.4a/D4，Wireless medium access control(MAC)and physical layer(PHY)specifications for low-rate wireless personal area networks［S］.2006.

［3］VENKATESH S，BUEHRER R M.A linear programming approach to nlos error mitigation in sensor networks［C］//Proc.IPSN’06.New York，NY，USA:ACM，2006:301-308.

［4］WYLIE M P，HOLTZMAN J.The non-line-of-sight problems in mobile location estimation［C］//Proc.IEEE Int.Conf.Universal Personal Communications.［S.l.］:IEEE Press，1996:827-831.

［5］CHEN P C.A non-line-of-sight error mitigation algorithm in location estimation［C］//Proc.Wireless Communication and Networking Conference.Piscataway:IEEE Press，1999:316-320.

［6］WYLIE M P，HOLTZMAN J.The non-line-of-sight problems in mobile location estimation［C］//Proc.5th IEEE International Conference on Universal Personal Communications.［S.l.］:IEEE Press，1996:827-831.

［7］陈希孺.数理统计学简史［M］.长沙:湖南教育出版社，2002.

［8］GONIN R，MONEY A H.Nonlinear lp-norm estimation［M］.New York，NY，USA:Marcel Dekker，Inc.，1989.

［9］李仲来.最小一乘法介绍［J］.数学通报，1992(2):42-45.