基于最优信标组的扩展卡尔曼定位算法*

孟文超，俞 立，董齐芬，王 铭

(浙江工业大学信息工程学院，杭州310023)

无线传感器网络(Wireless Sensor Networks)是一门集微电子、通信、计算机和传感器技术为一体的技术，具有广泛的应用领域。随着无线传感器网络的快速发展，传感器节点的位置信息在WSNs的诸多应用中扮演着不可或缺的重要角色，如在环境监测、战场侦察、目标跟踪等应用中，监测数据只有与节点位置信息绑定才有意义［1］。另外，节点位置信息也是大多数路由协议的基础［2－3］。

近年来，国内外学者对无线传感网定位技术进行了深入研究。根据定位过程中是否测量节点间的距离，定位算法主要分为基于测距算法和无需测距算法［4］。无需测距的定位方法仅根据网络的连通性来定位，定位精度在一定程序上依赖于网络平均每跳距离的估计精度，而且当网络的拓扑结构不规则时，算法的性能急剧下降。如DV-Hop算法、APIT算法、质心算法等［5］。基于测距的定位算法通过测量节点间距离或角度信息完成定位过程，如基于接收信号强度衰减的定位(RSSI)、基于到达时间的定位(TOA)、基于到达时间差的定位(TDOA)和基于角度的定位(AOA)。基于测距算法的定位精度一般高于无需测距算法，但一般需要额外硬件的支持［6］。

本文通过分析基于RSSI的定位技术存在的问题，提出一种新的基于最优信标组的扩展卡尔曼定位算法(BBG-EKF)。该算法在分析未知节点与信标节点的距离及信标节点间的共线性对定位精度影响的基础上，提出一种最优信标组选择机制，进而通过扩展卡尔曼滤波实现定位，这样既提供了较强的环境干扰鲁棒性，又没有增加网络通信开销。实验结果表明，本文提出的定位算法在定位精度、通信量和环境干扰鲁棒性等方面具有优越性。

论文其余部分安排如下:第1部分，介绍基于RSSI的测距原理;第2部分，分析影响定位精度的因素，并在此基础上提出一种选择最优信标组机制;第3部分，引入扩展卡尔曼滤波消除RSSI测量中的环境噪声;最后是算法仿真与总结。

1 RSSI测距模型

为适应实际环境中存在的多径效应、绕射、障碍物等因素，本文利用RSSI值并结合传播路径损耗经验模型计算未知节点到信标节点的距离。通常引入随机干扰的对数－正态分布模型作为无线传感器网络路径损耗模型［12］。

式中，d是发射节点与接收节点之间的距离，P(d)是距离为d时的接收信号强度，d0为参考距离，通常取1 m，P0(d0)是距离为d0时的接收信号强度，Xσ的均值为0、标准差为σ的高斯白噪声，n是与环境相关的路径损耗指数。由于不同的环境对测距有较大影响，为了得到更高的定位精度，需要针对特定的环境，通过实验获得相应的n和Xσ。

2 信标节点选择

无论是基于测距的定位还是测距无关的定位，都要利用信标节点。一般来说，可选择的信标节点信息越多，估计的位置越准确。另外，信标节点之间的位置拓扑关系及未知节点与信标节点之间的距离都在很大程度上影响定位结果。本节主要从这两方面分析它们对定位精度的影响，为合理选择最优信标节点提供依据。

2．1 未知节点与信标节点之间的距离

在基于RSSI测距的定位技术中，参与定位的信标节点数越多，定位精度越高。但是，当信标组中存在远离未知节点的信标节点时，定位效果将变差。定义距离估计误差即发射节点与接收节点的估计距离与真实距离 d的差值为，则=－d。由式(1)易得与 d、Xσ的关系式为:

从式(3)可以看出:当RSSI测距模型中的σ2及n确定时，距离测量误差与发射节点和接收节点间的距离成正比，距离越远，距离测量误差越大。为了分析距离对定位精度的影响，考虑未知节点与信标节点的距离分别从1 m至10 m变化，测距误差随距离变化的结果如图1所示。

图1 距离误差分布

仿真结果表明:在基于RSSI的测距技术中，由于误差的累积性，当接收节点远离发射节点时，距离测量误差也会随之增加，从而影响定位精度。因此，为了优化定位效果，应选择未知节点最近的K个信标节点进行定位。理论上，信标节点与未知节点的距离越近，RSSI值越大，所以在定位过程中，直接选择RSSI值最大的K个信标节点。

2．2 信标节点的共线度

在二维空间中，未知节点只需获得三个信标节点的位置信息，就可以确定自身的位置。然而，当3个信标节点共线或接近共线时，较小的测距误差都会导致很大的定位误差［13］。如图2所示:当信标节点B1、B2、B3几乎在一条直线上时，信标节点通信圆周的交点不唯一，也就无法确定未知节点究竟是在N1还是在N2。

图2 信标节点共线情况

为了解决信标节点的共线问题，引入共线度NC的定义。共线度NC定义为信标节点组成的三角形中最小角的余弦值。如图3(a)所示，A、B、C是三个信标节点，∠A是三角形ABC中最小角，则用∠A的余弦值来衡量信标节点组的共线程度，即:

因为共线度定义为三角形最小角的余弦值，最小角的取值范围为0°～60°，对应共线度NC的取值范围为0．5～1。当NC值等于0．5时，代表信标节点组成的三角形是等边三角形，此时用这组信标节点进行定位，效果最好。当NC值等于1时，代表信标节点组在一条直线上，此时定位效果最差。

图3 共线度的定义与实验示意图

如图3(b)所示，为了分析共线度对定位精度的影响，保持信标节点A、B的距离不变，通过改变信标C的位置来获得不同的NC值，信标节点C从AB的中点移动到三个信标节点构成等边三角形的位置，未知节点N放置在等边三角形ABC的中心。采用传统的极大似然估计对未知节点N进行定位，得到共线度与定位精度的关系如图4所示。实验结果表明:平均定位误差随着共线度NC的增大而增大，当NC小于0．75时，定位性能比较稳定，而在NC大于0．75时，定位性能随着NC的增大发生明显恶化。为了提高定位精度，设定共线度阈值CM，筛选NC≤CM的信标节点组。

图4 共线度与定位精度的关系

2．3 最优信标组

由以上分析可知，信标节点距离未知节点越远，信标节点间共线度越大，未知节点的平均定位误差越大，这为合理选择最优信标组提供了依据，最优信标组应选择未知节点附近共线度最小的一组信标组。

图5 最优信标组

为减少计算复杂度，定义一组信标组包含三个信标节点。最优信标组的选择如图5所示，离未知节点N最近的四个信标节点分别是A、B、C、D，组成ABC、ABD、BCD、ACD等四个导标三角形，根据共线度的定义易知三角形ACD的共线度最小，为未知节点N的最优信标节点组。

3 扩展卡尔曼定位

理论上，根据上述信标选择机制确定了最优信标组后，利用极大似然法即可得到较高精度的定位效果。然而，实际环境中，噪声、多径效应、非视线关系等条件的变化使得实际接收到的信号强度存在比较大的误差，该误差表现为高斯白噪声，影响定位结果。卡尔曼滤波［14－15］在高斯白噪声的动态系统中是一种最优滤波器，可以有效地抑制RSSI测量中噪声，增强环境干扰鲁棒性，提高定位精度，本节分析利用基于扩展卡尔曼的定位算法。

3．1 扩展卡尔曼模型

(1)状态方程模型

式中，xk=(xk，yk)T表示未知节点在第k－1个信标位置进行滤波计算后的坐标向量，wk是系统噪声，服从N(0，Qk)高斯分布，φk是系统矩阵，在未知节点的定位过程中，认为未知节点的位置是固定的，所以φk为二阶单位矩阵，系统噪声方差Qk=0。

(2)测量方程模型

文中选用未知节点到信标节点之间的距离作为EKF的测量值，测量方程为

式中，di为未知节点到第i个信标节点的距离，它是根据1节描述的测距方法测得，(Xi，Yi)是第i个信标节点的坐标，(x，y)是未知节点的坐标，vi是测量噪声，服从均值为零，方差为R的高斯分布。通过在平衡点展开泰勒级数对测量方程线性化处理，平衡点取上一次滤波后未知节点的坐标向量，线性化后的测量方程为:

图6 EKF定位流程图

扩展卡尔曼定位的流程图如图6所示，主要包括状态变量及误差方差阵初始化、状态方程及测量方程线性化、计算卡尔曼增益、更新状态变量、预测等五个步骤。状态初值和初始状态误差方差阵的正确选择，对于EKF的收敛速度和定位精度有很大的影响，为了减少算法的复杂度，初值任意选取，而不是采用特定定位算法给出比较准确的值，但同时为加快EKF的收敛速度，本文选取比较大的初始状态及误差协方差。

4 算法过程

(1)信标节点周期性发送包含节点ID、位置坐标信息包。

(2)未知节点收到信标节点的信息后，对信标节点依其RSSI值从大到小排序，并建立RSSI值与未知节点到信标节点距离的映射，建立3个集合。

信标节点集合:

未知节点到信标节点距离集合:

信标节点位置集合:

(3)未知节点首先从信标集合Beacon_set中选取离未知节点最近的4个节点，然后每3个信标节点组成一组信标组，总共可以分成C34组，分别计算各个信标组的共线度后，选取共线度最小的一组作为最优信标组。

(4)未知节点坐标向量的初值任意取定，初始状态误差协方差P0取值偏大些，使EKF尽快收敛于真实值。把x0，P0代入图6的流程图中，迭代到指定次数或者满足定位精度要求为止。

5 仿真实验

为了检验BBG-EKF算法的可行性和有效性，本部分主要对算法进行仿真。仿真在Matlab平台上进行，默认的仿真参数P0(d0)=5，σ=4，并通过与扩展卡尔曼定位算法(EKF)、基于最优信标组的极大似然估计算法(BBG-MLE)、极大似然估计算法(MLE)做比较，分析该算法的性能。不失一般性，假设200个未知节点和一定数目的信标节点随机部署于50 m×50 m的正方形区域C中，当未知节点通信范围内少于3个信标节点，采用弗洛伊德算法(Floyd Algorithm)获得与其它信标节点的最短距离。

图7是通信半径R=15、信标节点数M=20时BBG-EKF的定位效果，其中圆圈表示未知节点，方块表示信标节点，直线连接未知节点的真实坐标和它的估计坐标，直线越长，定位误差越大。仿真结果表明:BBG-EKF的平均定位误差约为1．5 m，C1区域中，信标节点的共线度较小，未知节点的定位误差偏小，相反，C2区域中，信标节点几乎在同一条直线上，未知节点的定位误差偏大，同时受边缘效应的影响，在区域边缘的平均定位误差明显偏大。

图7 BBG-EKF定位效果

扩展卡尔曼定位算法的定位精度受迭代次数的影响，迭代次数越多，定位精度越高。图8是坐标为(5，5)的未知节点分别采用BBG-EKF及BBG-MLE的定位效果，仿真结果表明，BBG-EKF定位算法在迭代15次左右收敛于真实坐标，而BBG-MLE定位算法始终发散。

图8 迭代次数影响

如图9所示是不同通信半径下平均定位误差的比较，其中信标节点占25%。在一定范围内，通信半径与网络连通度成正比，即节点通信半径越大，平均每个未知节点周围可通信的节点个数越多。仿真实验表明:BBG-EKF算法、EKF算法、MLE算法的定位准确度均随着网络连通度的增大逐渐提高，BBGMLE虽然存在最优信标选择机制，但由于没有扩展卡尔曼滤波过程，当通信半径大于25 m时平均定位误差反而增大。与其他三种算法相比BBG-EKF算法稳定性最好，在网络连通度变化的情况下，都具有较高的定位精度。

图9 通信半径与定位精度的关系

图10是R=25时信标节点密度对定位误差的影响。平均定位误差随着信标节点密度的增加而降低，在同样信标节点密度的情况下，BBG-EKF算法具有更好的定位性能，比如在信标密度为15%时，BBG-EKF算法平均定位误差约为0．37 m，而EKF算法平均定位误差约为0．52 m，BBG-MLE算法平均定位误差约为1．42 m，MLE算法平均定位误差约为0．98 m。另外，BBG-EKF对信标节点密度要求不高，信标节点密度为10%时算法平均定位误差为0.6 m左右，所以，BBG-EKF不仅具有很好的定位效果，而且适用于信标节点稀疏的环境中。

图10 信标节点密度与定位精度的关系

6 总结

本文采用无线传感网中的RSSI测距技术，提出一种基于最优信标组的扩展卡尔曼定位算法(BBGEKF)，该算法研究了未知节点与信标节点的距离、信标节点的共线性对定位精度的影响，为合理选择最优信标节点组进行定位提供了一种方法，最后通过扩展卡尔曼定位技术获得未知节点的位置信息。仿真实验表明，本文提出的基于最优信标组的扩展卡尔曼定位算法在没有增加网络开销的情况下，提高了定位精度，在不同通信半径及信标节点密度的网络中都表现中良好的性能。

［1］ 孙利民．无线传感器网络［M］．北京:清华大学出版社，2005:137－140．

［2］ Capkun S，Hamdi M，Hubaux J P．GPS-Free Positioning in Mobile Ad-Hoc Networks［J］．Cluster Computing，2002，5(2):161 －176．

［3］ Niculescu D，Nath B．Trajectory Based Forwarding and its Applications［C］//Proceedings of the 9th Annual International Conference on Mobile computing and Networking．ACM New York，NY，USA，2003:260－272．

［4］ 刘新华，李方敏．一种分布式的无线传感器网络Range-free节点定位算法［J］．传感技术学报，2008，21(1):154 －157．

［5］ 田增山，罗磊，何维．一种分布式的无线传感器网络节点定位算法［J］．传感技术学报，2009，22(3):387 －390．

［6］ Neal P，Joshua N，Spyros K，et al．Locating the Nodes:Cooperative Localization in Wireless Sensor Networks［J］．IEEE Signal Processing Magazine，2005，22(4):54 －69．

［7］ Mao G，Fidan B，Anderson B．Wireless Sensor Network Localization Techniques［J］．Computer Networks，2007，51(10):2529 －2553．

［8］ 杨东勇，顾东袁，傅晓婕．一种基于RSSI相似度的室内定位算法［J］．传感技术学报，2009，22(2):264 －268．

［9］ Yi J，Yang S．Multi-Hop Based Monte Carlo Localization for Mobile Sensor Networks［C］//Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，San Diego，CA，2007:162 －171．

［10］ Poqqi C，Mazzini G．Collinearity for Sensor Network Localization［C］//IEEE 58th Vehicular Technology Conference，Ferrara，IT，2003:3040－3044．

［11］ Wang C L，Chiou Y S，Dai Y S．An Adaptive Location Estimator Based Kalman Filtering for Wireless Sensor Networks［C］//IEEE 65th Vehicular Technology Conference，Dublin，IR，2007:864 －868．

［12］ Wang J，Ghosh R K．A Survey on Sensor Localization［J］．Journal of Control Theory and Applications，2010，8(1):2 －11．

［13］吴凌飞，孟庆虎，梁华为．一种基于共线度的无线传感器网络定位算法［J］．传感技术学报，2009，22(5):722 －727．

［14］ Sreenath K，Lewis F L，Popa D O．Simultaneous Adaptive Localization of a Wireless Sensor Network［J］．Mobile Computing and Communications Review，2007，11(2):14 －28．

［15］ Yim J，Park C，Joo J．Extended Kalman Filter for Wireless LAN Based Indoor Positioning［J］．Decision Support Systems，2008，45(4):960－971．