基于残差修正法的无线传感器网络定位技术*

吴晓平，谈士力，胡军国

(1.浙江农林大学低碳与物联网技术联合实验室，浙江 临安311300;2.上海大学机器人研究所，上海200444)

对于无线传感器网络的大部分应用场合，采用无线传感器网络进行信息收集和处理，这些数据必须和位置信息相捆绑才有意义，甚至有时需要传感器发回单纯的位置信息[1－2]。从应用角度来讲，传感节点的定位是传感网络中最为重要和传统的问题，研究具有低成本、高精度的传感器网络定位系统是该领域的主要问题之一[3]。

无线传感器网络节点定位算法可分为基于测距和非测距方法两大类，非测距的节点定位技术定位不需要额外的硬件设备，成本低，在定位精度要求不高的场合下使用有较大优势。对定位精度要求较高的场合建议使用测距定位技术。目前定位技术中使用最广泛的定位系统当属全球定位系统(Global Positioning System，GPS)，GPS系统利用精确的同步卫星时钟提供授时和测距以对用户节点进行定位，具有定位精度高、实时性好、抗干扰能力强等优点，但是GPS定位仅仅适应于无遮挡的室外环境，其用户设备通常能耗高、体积大、成本高[4]。这使得它不适用于大规模环境下的无线传感器网络定位。这种方法的局限性激发了一种新的传感器网络节点定位方法，即利用已知位置的信标节点去推算其余未知的节点位置坐标，这种方法需要未知节点与信标节点间的一些信息，比如距离或角度。在无线传感器网络领域，信号接受强度指示(RSSI)距离测量被认为是一种具有较高性价比的测量方法。RSSI测距无需额外硬件，实现简单，具备低功耗、低成本等特点，应用十分广泛[5－7]。如果在 RSSI实际测量中，节点刚好处于一个坑中，天线出错，节点供电不足，严重的障碍物遮挡，会导致距离测量出现潜在的大量非高斯误差的数据。也就是说，某些距离测量结果严重失真(坏测距)，有些测量结果误差较少(好测距)。坏测距数据的出现严重地降低了传感器节点定位的准确性。Lirong Jian等基于冗余的测距节点提出了以刚性理论识别和判断出坏测距节点，以提高定位精度[8]。徐向华等针对传感网测量中出现的错误数据，提出了一种故障容忍的事件定位算法，以提高定位精度[9]。H.T.Kung等提出了误差容忍的定位算法，对判断出的坏测距数据进行容忍定位，减少了坏测距带来的定位误差放大[10]。

采用极大似然相似法是目前无线传感器网络定位所采用的主要方法，极大似然相似法的解法有很多，其中非线性最小平方残差是所有方法中定位精度较高的一种算法。采用非线性最小平方残差定位时，如果没有加以区分好测距与坏测距，没有对坏测距引起的残差项加以修正，会导致定位误差的放大。针对于此，本文提出一种能有效估计坏测距的测距误差的方法，并由此设计了一种非线性最小平方残差下无线传感器网络定位的误差控制方法，以提高定位精度。

1 非线性最小平方残差定位原理

在二维平面上，节点定位至少需要知道与三个信标节点的距离(不共线)[11]。假设未知节点坐标为(x，y)，已知信标节点 i的坐标为(xi，yi)，以及未知节点到信标节点的真实距离，应该满足:

在实际测量中，距离测量经常是不准确的，假设实际距离测量值为 di，则。

定位可以被归纳为一个非线性最小平方残差优化问题。以距离测量值作为约束，找到一个满足最小平方残差时的坐标(x，y)。定位过程中，残差的定义为距离测量值和定位中所产生的估计值之差。式(2)表示了未知节点与信标节点i之间的距离残差ri。

定位过程是通过最小化平方残差，即是下列目标函数:

式(4)中，n为与未知节点间可测距的信标节点数量，通过该式求出的坐标(x，y)即为未知节点的坐标。

式(4)所描述的非线性最小平方问题可以采用高斯牛顿迭代法求解。但采用高斯牛顿迭代法采用近似的线性模型，可能会陷入局部最优。为全局最优，建议采用Levenberg-Marquardt(LM)算法迭代求解。由于采用了二阶导数信息，LM算法比传统的高斯牛顿法收敛速度更快[12]。

2 残差修正法定位

2.1 数学模型

实现二维平面上的未知节点定位，仅需要三个不共线的信标节点。在实际的大规模定位系统中，信标节点的数目往往超过这个数目，也就是说，信标节点的数目是有冗余的。测距误差的大小对于定位误差的控制起到了关键的作用，理想的定位结果是尽量多利用测距误差较小的好测距数据，抑制测距误差较大的坏测距数据对于残差的放大。为追求较高的定位精度，有必要对测距的误差进行正确区分，区分是好测距还是坏测距，对估计出的坏测距数据进行修正。为此，对式(4)进行改进:

式(5)中，Δdi是测距误差的估计值，其理想值是测量距离di的真实误差值。该式中利用测距误差的估计值修正了原有的残差。当然Δdi的估计值与真实值越靠近，定位误差就越小。如果能有效地估计出测距误差值，然后再用式(5)修正，定位效果会显著提高。残差是由测距误差引起的，在高斯分布的测距误差作用下，各个节点的残差分布具有一定的随机性，各个信标节点的测距误差难以估计。但对于非高斯测距数据，具有较大误差的坏测距误差值在残差项中了占了绝对优势，测距误差较小的好测距误差在残差中的作用较小。忽略测距误差较小的好测距数据对于残差的影响，突出测距误差较大的坏测距数据对残差的影响，可以将坏测距数据的测距误差大致估计出来。方法就是通过分析残差与误差间的分布关系，对引起残差的测距误差分解，找出坏测距数据，大致估计出坏测距的测距误差，然后再通过式(5)修正定位结果，下面就非高斯分布下的测距误差进行分解。

设未知节点坐标的真实坐标为(x，y)，由非线性最小平方残差法，通过式(4)，定位出的未知节点坐标为(x0，y0)，则未知节点到信标节点i的真实距离应为，对此采用泰勒级数展开，忽略高次项，有:

因此，梯度矩阵J可以表示为:

未知节点的坐标增量矩阵H=(h，k)，有:

则残差矩阵:

式(9)中，A=J(JTJ)－1J－I残差矩阵可由式(4)计算，梯度矩阵J由式(6)求出。由于矩阵A非满秩，误差矩阵无法求解。式(9)表示了测距误差对于残差的分配关系。当此系统中，坏测距信标节点数目小于好测距信标节点数，坏测距信标节点分配给好测距信标节点的残差较小，所以残差矩阵中具有较大残差的往往有较大的测距误差，可将矩阵A按残差值大小进行好测距与坏测距分解:

A11表示了好测距的测距误差对好测距残差的分配关系;A12表示了好测距的测距误差对坏测距残差的分配关系;A21表示了坏测距的测距误差对好测距残差的分配关系;A22表示了坏测距的测距误差对坏测距残差的分配关系。从内在含义上看，矩阵A表示了残差对误差的分配关系。具有好测距的测距误差较小，坏测距节点的测距误差较大。忽略好测距对于坏测距节点的残差分配，可以将坏测距节点的测距误差大致分离出来。同样地，对也进行分解，有

因此，坏测距的测距误差可由式(13)近似估计:

2.2 算法的实现流程

①以非线性最小平方残差原理，根据式(4)采用LM迭代算法计算出初次定位结果和残差矩阵。②以初次定位的未知节点坐标代入式(6)计算梯度矩阵J，进而计算出误差与残差间的关系矩阵A。③根据残差值大小对残差矩阵判断是好测距还是坏测距，并以此为依据对A按式(10)进行分解，同时对和也进行分解，按式(13)计算出坏测距误差的近似估计值。④假设好测距误差为零，采用③计算出的测距误差作为坏测距误差估计值，并代入式(5)，修正坏测距项的残差值，好测距项的残差不需要修正，计算出的即是经过一次修正后的定位结果。⑤若有④计算出的一次修正后的残差分布大小均匀，可认为修正已基本完成;若残差项大小变化显著，可重新按步骤②进行再次修正。

3 仿真分析

用MATLAB进行算法仿真，无线传感器网络在100 m×100 m区域内。在该区域内上随机部署了12个信标节点，将未知节点的坐标预先设置在(50，50)点。每个仿真实验运行200次，所有仿真结果取200次的平均值。仿真实验首先测试了残差与测距误差间的关系。

3.1 残差与测距误差关系

坏测距与好测距的判断依据主要是残差值大小。当坏测距误差显著大于好测距误差时，坏测距项的残差值也显著大于好测距项的残差值。随着坏测距数量的增加，好测距的残差受到坏测距的影响，也随之增加，两者之间的区分度不够明显。在12个信标节点中随机选择了2或4个节点作为坏测距节点，其余信标节点的测距误差服从高斯分布N(0，12)，改变2或4个坏测距节点的测距误差，图1绘出了随着坏测距节点测距误差增加时，好测距与坏测距项残差值的变化关系。由图1可见，坏测距项的残差明显大于好测距项的残差，同时，随着坏测距数量的增加，好测距项与坏测距项的残差差异会有所减少，采用残差值大小来区分是好测距与坏测距也会越不可靠。

图1 平均绝度值残差与测距误差关系

3.2 测距误差的估计值

采用式(15)评价测距误差估计值的准确性，定义si为测距误差估计值的相似度。

式(15)中，Δdi为测距误差的估计值为真实的测距误差。在12个信标节点中随机选择了4个节点作为坏测距节点，其余信标节点的测距误差服从高斯分布N(0，12)，改变4个坏测距节点的测距误差，采用算法分解出的测距误差估计值的相似度在图2中绘出。从图2可以看出，在测距误差较小时，由于节点间的残差也服从高斯分布，坏测距的测距误差难以从节点中分离开。但是随着坏测距的测距误差增大，坏测距的误差在残差中占主要成分，可以很容易将坏测距节点的测距误差分解并计算出来。

图2 测距误差估计值相似度

3.3 残差修正法的定位

实验的初始设置同上，也在12个信标节点中随机选择了4个节点作为坏测距节点，其余信标节点的测距误差服从高斯分布N(0，12)，改变4个坏测距节点的测距误差，图3说明了两种不同定位方法的定位误差结果。从图3中可看出，未经过修正的非线性最小平方残差定位法，定位误差随着测距误差的增加也剧烈加大，但经过一次残差修正后，定位误差基本保持稳定，定位效果大大改善。

图3 两种不同定位方法下的定位误差

随着坏测距数目的增加，由于好测距信标节点的残差项受到坏测距的分配影响，坏测距信标节点的测距误差分配给好测距节点，所以坏测距节点的误差估计越来越不准确。好测距信标节点的测距误差服从高斯分布N(0，12)，坏测距的测距误差设置在10 m，改变坏测距信标节点的数目，图4绘出了随着坏测距节点数量的增加，两种不同的定位方法下的定位误差。从图4可以看出，随着坏测距节点数目的增加，定位误差稍有加大，经过修正后的定位结果明显优于原有的定位值。

图4 坏测距数目对定位误差的影响

4 结论

本文提出了在非线性最小平方残差法定位时，采用误差与残差的关系矩阵分解出坏测距项的测距误差值，并以此修正相应项的残差，这种方法对于提高非高斯测距误差分布下的定位效果，具有显著作用。但该算法也有不足的一面，当坏测距信标节点数量较多时，由于好测距节点的残差项受到坏测距节点残差项的影响，好测距项的残差值与坏测距节点的残差没有显著区别，所以难以区分是好测距还是坏测距，坏测距的测距误差也就难以估计。

[1]Yunhao Liu，Zheng Yang，Xiaoping Wang.Location，Localization，and Localizability[J].JournalofComputer Science and Technology，2010，25(2):274－297.

[2]Dragos Niculescu，Badri Nath.DV Based Positioning in Ad Hoc Networks[J].Journal of Telecommunication Systems，2003，22(4):267－280.

[3]孙立民，李建中，陈渝，等.无线传感器网络[M].北京:清华大学出版社，2005.

[4]Capkun S，Hamdi M，Hubaux J P.GPS-Free Positioning in Mobile Ad-Hoc Networks[J].Cluster Computing，2002，5(2):157－167.

[5]Ziguo Zhong，Tian He.Achieving Range-Free Localization beyond Connectivity[C]//Proceedings of the 7th International Conference on Embedded Networked Sensor Systems，2009:281－294.

[6]方震，赵湛，郭鹏.基于 RSSI测距分析[J].传感技术学报，2007，20(11):2526－2530.

[7]赵昭，陈小惠.无线传感器网络中基于RSSI的改进定位算法[J].传感技术学报，2009，22(3):391－394.

[8]Lirong Jian，Zheng Yang，Yunhao Liu.Beyond Triangle Inequality:Sifting Noisy and Outlier Distance Measurements for Localization[C]//Proceedings of the 28th Conference on Computer Communications，2009:1972－1980.

[9]徐向华，高学勇，万健.无线传感器网络中故障容忍的事件定位算法[J].传感技术学报，2009，24(3):429－435.

[10]Kung H T，Chit-Kwan Lin，Tsung-Han Lin，et al.Localization with Snap Inducing Shaped Residuals(SISR):Coping with Errors in Measurement[C]//Proceedings of the 15th Annual International Conference on Mobile Computing and Networking，2009:333－344.

[11]Juan Liu，Ying Zhang，Feng Zhao.Robust Distributed Node Localization with Error Management[C]//Proceedings of the 4th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing，2006:250－261.

[12]Madsen K，Nielsen H B，Tingleff O.Optimization with Constraints[M].2nd Edition.IMM，DTU，2004.