基于EKF的MDS-MAP定位算法

范海红 沈水金

(1.浙江邮电职业技术学院 管理信息学院，浙江 绍兴 312000;2.绍兴文理学院 数理信息学院，浙江 绍兴 312000)

0 引言

近几年，无线传感器网络(Wireless Sensor Networks, WSN)在人类的生活中具有广泛的应用[1-2].而作为应用的基础——传感器节点的自定位问题[3-4]就变得非常具有研究价值，国际上对此早就进行了初步的研究，但是直到最近，定位算法才取得了迅速的发展，并提出了许多新的算法，得到了不断改善和提高.

定位算法按节点位置计算方式的不同可以分为：集中式定位、分布式定位和增量式定位[5-6].集中式定位算法是指未知节点的位置计算是通过中心点来完成的，而各个节点只需将数据传输给中心节点.常见的集中式算法有MDS-MAP[7]、APIT[8].分布式算法是不依赖于中心节点，而通过节点间的相互协作和信息交流，让未知节点自己计算，从而达到定位.经典的算法有SPA[9]、APS[10].增量式算法通常是以3、4个锚节点为出发点，通过三角测量等优化算法来计算未知节点的位置，同时将已经确定的节点作为锚节点，按此方法下去，直到所有的未知节点都完成定位.该类经典的算法有ABC算法[11].

MDS-MAP算法是集中式算法，多维标度分析技术(MDS)是通过无线传感器网个节点间的关系来实现对多个节点的同时定位，在不存在锚节点的条件下，也可以获得和实际拓扑结构接近的相对拓扑结构图.本文分析了MDS技术，并结合MDS-MAP算法，以扩展卡尔曼滤波(EKF)[12]来进行求精，从而提高了节点的定位精度，本文将此定位称为EKF-MDS算法.该算法可以划分成两个阶段：第一个是MDS-MAP定位阶段、第二个是EKF求精阶段，其主要是以MDS-MAP的位置作为EKF初始信息，并多次迭代计算未知节点的邻节点数据，从而提高未知节点位置信息的精度.

1 奇异值分解

在节点定位过程中，把节点间的距离当作节点之间的差异性，从而利用MDS算法求解出节点的位置信息，关键步骤是将中心化后的距离平方矩阵做奇异值分解[13](SVD)，从而得到节点位置的坐标表达式.

考虑网络中存在N个节点，位置信息对于的坐标向量是X=[x1,x2…xn]T，而xi=[xi,yi].则dij表示为第i节点和第j节点间的欧氏距离值：

(1)

当i、j两节点相邻时，dij直接用测量所得到的距值来表示；反之，dij则表示为i、j两节点间的最短测距路径.

若D矩阵表示为节点之间的距离矩阵，那么D2则是距离矩阵的平方(简称为平方距离矩阵)，不然用3个节点作为示例，则平方距离矩阵表示为：

假设

B=XXT

(3)

(4)

而先前假设B=XXT，从公式(4)已经得到B，则可以求向量X，也就是可以求出节点的位置信息.若认为X0为公式(3)的一个解，那么对于任何一个正交矩阵W，X0W也都仍然是公式(3)的解，即：

(5)

因此最后只需求出特殊解，MDS方法可以使用SVD分解方法，对B进行奇异值分解，从而得到MDS的坐标位置解.其中A矩阵表示SVD分解后的特征值矩阵，Q为对应特征向量矩阵.则

B=QAQT=Q(A1/2·A1/2)QT

=(QA1/2)·(QA1/2)T

(6)

即QA1/2为公式(3)的解，此解与向量X相差正交矩阵W，而矩阵W没法从方程中得到，但可以用锚节点的坐标位置信息得到.而对于相对定位的MDS-MAP算法则只需相对坐标，因此QA1/2就是定位后的节点位置坐标.

2 EKF-MDS定位算法

本文提出的EKF-MDS定位算法是基于MDS-MAP算法，由于距离与所要得到的坐标位置之间呈非线性关系，因此，本文引入针对此关系的扩展卡尔曼滤波来对计算结果进行求精，因而EKS-MDS算法分为2个阶段：定位阶段和求精阶段.

2.1 EKF-MDS的定位阶段

EKF-MDS定位算法的定位阶段采用了MDS技术，可在基于测距方式下和距离无关方式下两种情况进行定位，本文利用基于测距方式下的MDS-MAP.在该算法中，首先将整个网络用一个无向图来表示，顶点V表示网络中的节点，边E表示为节点之间的估计距离.因此MDS-MAP算法过程为：

第一步，生成以距离赋边权值的网络拓扑结构图：在节点距离可测时，将该距离值赋值给距离矩阵；若节点间距离不可测时，就赋距离值为1.按照Dijkstra或Floyd算法[14]可以给出网络中任意节点之间的最短距离，从而得到MDS技术所需要的节点间最短距离矩阵D；

第二步，双中心化操作平方距离矩阵D2

(7)

第三步，SVD分解，求得特征值矩阵A和特征向量矩阵Q，选择其中最大的2个特征值，从而可以构造特征值矩阵Ar和特征向量矩阵Qr，最后得到定位坐标：

(8)

在使用SVD分解时，3维坐标计算量比2维坐标计算量增加很少，这一点明显优于三边/多边定位算法；

第四步，将第三步得到的定位结果作为EKF滤波的初始值，通过RSSI测距[15]可以得到未知节点与邻节点间的距离信息和位置信息，利用EKF迭代，得到节点的最终位置信息.

仿真[16]显示，当网络连通度达到12.2时，95%以上的节点都可以实现定位；在网络中有200个节点的条件下，得到平均连通度为12.1，测距误差为5%时的定位误差为16%.

2.2 EKF模型的建立

EKF的滤波模型的建立如下：

2.2.1 非线性状态方程

Xk=f(Xk-1)+wk=A·Xk-1+wk

(9)

2.2.2 观测方程模型

把未知节点到其邻节点的测量距离值作为观测量，再利用RSSI的测距方式得到测量距离，则观测方程可以表示为：

(10)

zi为未知节点到第i个邻节点的测量距离值，(x,y)为未知节点的位置坐标，(xk,yk)为第k个邻节点的位置坐标，vk为测距的噪声，服从平均值是0的高斯分布，N为未知节点附近的邻节点总数.

由公式10可以看出，状态向量X=[xk,yk]T与观测量z(k)之间是非线性的关系h(Xk)，因此，不能直接使用卡尔曼滤波器滤波.EKF是针对非线性关系的滤波算法，主要利用数的泰勒级数展开的方式，取一次项作为近似值，从而将其线性化：

h(Xk+ΔX)=h(xk+Δx,yk+Δy)

(11)

则状态方程化为线性模型：

z(k)=Hk·Xk+v(k)

(12)

其中，Hk为h(Xk)的雅克比矩阵。

(14)

其中,1≤i≤N

2.2.3 滤波初值的选定

2.3 EKF-MDS的求精阶段

以图1为例说明算法的求精过程.未知节点O经过MDS-MAP定位算法可以得到初始位置信息为(x0,y0)，而其邻节点有未知节点1、2、3，通过MDS-MAP算法后得到，记为(x1,y1),(x2,y2),(x3,y3).现在要利用EKF滤波算法对O节点的初始坐标进行求精，从而提高定位的精度.在每次迭代过程中，都使用节点O的所有邻节点信息.EKF迭代的初始值如下：

图1 迭代实例

首先令X0=(x0,y0)，

ek为未知节点和邻节点间的距离预测值.从而完成EKF的初始化，开始了迭代过程.节点最后的定位精度与EKF算法的迭代次数相关，根据具体问题要求的定位能耗[17]，设置迭代的终止条件，本文中设置为：

(15)

Δ为预设的容错值，本文实验中Δ=0.01.EKF具体的迭代过程如图2所示，其中R为测量噪声的协方差矩阵，Kg为卡尔曼增益.

图2 EKF滤波迭代过程

图2续图 EKF滤波迭代过程

3 算法仿真结果及分析

EKF滤波器与MDS-MAP算法结合，可以提高定位精度.它以MDS-MAP算法的坐标作为EKF-MDS的初始信息，多次迭代求取最佳定位解.本文利用MATLAB软件进行仿真，来比较MDS-MAP与EKF-MDS的定位精度，实验中，假定网络涵盖范围是100*100，节点的最大通信距离是25，网络中所有节点的坐标都是服从正态分布，测距的误差为高斯白噪声随机数[18-19].在仿真过程中，首先认为在通信范围内的2个节点之间的距离是已知的，此距离可以根据两个点的真实坐标计算得到dij，用服从正态分布的随机变量来模拟实际中的测距误差，将dij加上测距误差后的值模拟实际应用中测量得到的两点之间的距离值.

图3是以图1为例，对于一个节点进行EKF仿真求精的结果，本实验中预设的容错值Δ=10e-5.仿真中，假定节点0～3的实际位置为(44,94),(47,40),(84,53),(19,66).现在要对节点0应用EKF进行求精.假设在经过MDS-MAP定位后得到的0～3节点的坐标为：(35,88),(40,48),(80,45),(15,60).测距误差为服从正态随机分布的随机变数.从图3中可以看出，节点的初始位置估计在经过EKF滤波后，能够更加靠近实际位置.“□”号表示真实位置，“*”号表示EKF算法每次迭代后的未知节点坐标位置.

图3 节点迭代实例

图4-图7分别为网络中节点数为50(连通度为9.8)时，原始网络拓扑图、与MDS-MAP相对坐标网络拓扑图、MDS-MAP绝对坐标网络拓扑图以及EKF_MDS生成的绝对坐标网络拓扑图.图8为MDS-MAP与EKF-MDS算法定位的比较，MDS-MAP计算后的节点坐标用红色“·”表示，EKF-MDS计算后的节点坐标用黑色“·”表示，节点的实际位置用“*”号表示，连线表示定位的精度，越短表示越高，相反，则越低[20].从连线可以看出，EKF-MDS的定位精度明显优于MDS-MAP.图9为通信半径为30，网络中节点数为50(连通度为14.13时)，分别对2个算法仿真10次的定位误差.

4 结束语

本文对MDS技术原理进行了分析，并提出了EKF-MDS算法.它以MDS-MAP位置坐标作为EKF的初始值，利用所有邻节点信息进行迭代计算未知节点， 从而提高定位精度.EKF-MDS与MDS-MAP相比在计算量方面有所增加，但是由于是集中式的定位算法，中心节点具有较强的计算能力和足够的能耗，因此EKF-MDS是可行的.