基于坐标修正的改进WSN节点定位算法

柏 植，许海峰，郭 凯，李 昊

(宿州学院 机械与电子工程学院，安徽 宿州 234000)

无线传感器网络(WSN)是由很多具有无线通信收发能力的节点组成的多跳自组织的网络，随着科技的不断进步，WSN被广泛应用到军事、环境监测、健康防护、医疗救护等领域，因此无数的学者都投入到节点定位的研究之中[1-2]。

目前定位技术可以分为两大类：非测距定位和测距定位。其中测距定位算法就需要两相邻节点间的欧氏距离或角度的信息，这势必会提高对硬件设备的要求，其优点在于定位的精度比较高，常用的测距定位算法有：AOA、TOA、RSSI等，非测距定位算法是可以不通过测距的方法实现对节点的定位，主要是利用网络的拓扑关系和网络的连通性来实现对未知节点的定位，不需要昂贵的硬件，相比于测距定位算法具有成本低和易于实施等优点，但其缺点是误差较大，常见的非测距定位算法有：质心算法、DV-Hop、Amorphous和APIT等[3]。

为了提升DV-Hop算法的定位精度，提出了分别修正跳距和优化坐标来改进DV-Hop算法，在修正跳距阶段，通过计算得到每个信标节点与其他信标节点间的伪距误差因子，除去误差较大的信标节点，求得平均跳距，然后运用三边定位算法和最小二乘法求得未知节点的坐标信息，在优化坐标阶段，使用扩展卡尔曼滤波算法(EKF)优化坐标，调整观测噪声矩阵在合适的值，从而有效的提升节点定位精度。

1 DV-hop算法及误差分析

1.1 经典DV-Hop算法

DV-Hop算法是非测距定位算法中基于距离矢量路由原理的算法，主要有通过以下三个阶段来完成定位的。

1.1.1 所有的信标节点通过网络泛洪的形式将自身的坐标和初始的跳数广播出去，由于节点的功率有限，所以只有在通信半径内的邻居节点才能收到，所以信标节点可以接收到其他信标节点的坐标和最小跳数的信息，同理，未知节点也可以接收到距自己最近的信标节点坐标和最小跳数的信息。

1.1.2 信标节点之间相互通信之后，根据式(1)计算出信标节点i的平均跳距。

(1)

式中：Hopi为信标节点i的平均跳距，(xi,yi)和(xj,yj)为信标节点i和j的坐标，hij为信标节点i和j间的最小跳数。

(2)

1.1.3 得到上述的估计距离后，使用最小二乘法法完成定位。假设第i个信标节点的坐标是(xi,yi)，未知节点u的坐标是(x,y)，未知节点u到第i个信标节点的欧氏距离是di，所以有式(3)所示的方程组[4]。

(3)

上述的方程组可以转换为AX=B的形式，其中：

(4)

(5)

(6)

使用最小二乘法可计算得X，如式(7)所示。

X=(ATA)-1ATB

(7)

1.2 误差分析

DV-Hop在定位时精度较低，通过分析后发现该算法主要误差来源为以下三个方面。

(1)信标节点的分布状态和密度。WSN中信标节点都是随机分布的，这就会产生节点分布不均的情况，如图1所示，若节点间的跳数偏多，则它们间的理论距离就偏大于真实距离，就会产生误差[5]。

图1 信标节点分布状态对定位的影响

(2)未知节点平均跳距的影响。信标节点与未知节点间的距离是跳距估计值与跳数之积，但如果获取的平均跳距值偏差较大，就会影响定位的精度[11]。

(3)未知节点坐标求解方法的影响。运用三边定位法和最小二乘法求解未知节点的坐标信息，使用最小二乘法获取坐标时，将有误差的矩阵带入计算也会降低定位精度。

2 DV-Hop算法的改进

2.1 平均跳距修正

根据经典的DV-Hop算法理论，信标节点i和j间的伪距表达式如式(8)所示。

(8)

设信标节点i和j间的真实欧氏距离为dij，则它们之间的伪距误差因子表达式为：

(9)

在现实环境中伪距和真实距离通常存在误差，所以对节点i和j之间伪距误差因子降序排序，取排序的后k个节点来计算信标节点i的平均跳距，根据测试，k取值是总信标节点数的1/3-1/2倍时效果最佳。最终i的跳距修正为：

(10)

将修正后的平均跳距再用上节中式(2)计算跳距，根据式(7)定位未知节点，即可提高定位精度。

2.2 坐标修正

由于网络结构具有随机性和复杂性的特点，使得计算平均跳距值存在误差，运用最小二乘法求得的未知节点的坐标也会存在偏差，所以为了减少偏差，使用EKF算法对未知节点坐标进行修正，建立系统的状态方程和观测方程[6]为：

(11)

其中wk和vk分别表示在第k个信标节点定位时的状态噪声和观测噪声，它们的方差分别为Qk和Rk，且相互独立。

(12)

系统以未知节点到信标节点的欧氏距离的估计值作为观测量，系统的观测向量表达式为：

(13)

式中(xk,yk)为第k个信标节点的坐标，对h(k,Xk)求偏导即可得雅克比矩阵Hk如式(14)所示。

(14)

应用EKF算法定位的过程可分为两大部分，具体如下所示[7]。

(1)时间更新。用上一状态真实坐标计算这一状态的预测坐标，并得到预测误差值的方差。

(2)量测更新。根据求得的雅克比矩阵，即可以得到状态增益矩阵，进而可以得到这一状态的估计值和协方差矩阵。

通过使用EKF滤波算法进一步修正未知节点的定位坐标，进而提高定位的精度。

2.3 定位算法过程

综合2.1和2.2所述的方法，下面对定位方法做简要的描述。

首先网络初始化，信标节点向网络中广播自身位置，运用经典的距离矢量交换协议，根据式(1)得到每个信标节点的初始跳距，并定义伪距误差因子，根据式(10)修正信标节点的跳距。未知节点收到广播后，判断是否是第一次收到，若是就保存该信标节点位置信息，否则与缓冲区的条数值比较，保存较小的跳数值。然后根据式(2)重新计算每个未知节点的跳距，根据式(7)利用最小二乘法估算未知节点的初始坐标。将该初始坐标作为EKF的初始值，以未知节点到信标节点的欧氏距离的估计值作为观测量进行滤波融合，最终得到未知节点的坐标，流程图如图2所示。

图2 EKF-DV-Hop定位算法流程

3 仿真与分析

为验证提出算法的有效性，对经典的DV-Hop算法和改进后的算法分别在MATLAB仿真平台上做仿真验证，为评判不同定位算法的性能，定义平均相对误差，其计算公式如式(15)所示[8]。

(15)

式中(xi,yi)、(Xi,Yi)分别指的是未知节点i的估计坐标和真实坐标，n为未知节点的数目，R为节点间的通信半径。

仿真区域设置为100m×100m的矩形空间，在该区域中随机产生节点。分别使用传统的DV-Hop算法、跳距修正的DV-Hop算法、EKF-DV-Hop算法进行100次仿真，取其平均值作为最终的数据。

分析信标节点所占比例对定位的平均相对误差的影响，随机产生100个节点，仿真中设置节点的通信半径是30m，信标节点所占比例从5%到40%并以步长为5%变化，仿真数据如图3所示。

图3 平均定位误差随信标节点比例变化

从图3不难得出，随着信标节点所占比例的不断增加，平均定位误差随之不断减小，并逐渐趋向平稳，这是因为信标节点比例增加，提高计算跳距的准确度的同时，还降低了节点之间的最小跳数，误差也就随之减小。信标节点所占比例小于15%时，平均定位误差受其影响较大，大于15%时，平均定位误差处于缓慢平稳状态。与传统的DV-Hop定位算法相比，跳距修正的DV-Hop和EKF-DV-Hop算法的平均定位误差降低了约1.7%和12.26%，证明了提出的EKF-DV-Hop算法的可行性和有效性。

分析节点之间的通信半径的变化对平均定位误差的影响。仿真时，随机产生100个节点，设置信标节点所占比例是30%，节点之间的通信半径从24m到44m并以步长4m增长，仿真结果如图4所示。

图4 平均定位误差随通信半径变化

从图4不难得出，图中所示的四种算法，节点间通信半径的不断增加，未知节点的平均定位误差都随之呈现不断减小的趋势，这是由于节点间的通信半径变大就会增加系统的连通度，计算得到的跳距就会更准确。当通信半径大于30m的时候，减小的趋势开始变缓，并趋于平稳；和传统的DV-Hop算法相比，跳距修正的DV-Hop算法和EKF-DV-Hop算法平均定位误差降低了约1.459%和12.674%；通信的半径的持续增加时，平均定位误差反而有变化的趋势，说明通信半径并不是越大越好。所以，提出的定位算法是优于其他两种定位算法的。

分析节点总数的变化对平均定位误差的影响。仿真时，设置节点的通信半径为20m，信标节点所占的比例为30%，节点总数从100到300，并以40为步长增加，仿真图如图5所示。

图5 平均定位误差随节点总数变化

从图5可以看出，随着节点总数不断增加，四种算法的定位误差都在下降，主要是因为随着节点数目的增加，网络节点的密度随之增加，在节点的通信半径内就会出现更多的邻居节点，使得网络的拓扑结构更加的规则，误差也会随之减小，相比于传统的DV-Hop定位算法，跳距修正的DV-Hop算法、EKF-DV-Hop算法的平均定位误差降低了约1.334%和16.703%。实验结果表明本文提出的算法更优，可以进一步减小定位误差。

4 结论

针对DV-Hop在定位过程中，平均跳距估算不准确，定位偏差较大，环境适应力弱的问题，使用跳距修正和坐标优化的方法，提高了算法定位精度和环境适应力。首先使用伪误差因子的方法，降低了平均跳距的误差，然后使用EKF算法对未知节点的估计坐标进行优。仿真表明，提出的算法能够明显的提升未知节点的定位精度，具有一定的参考价值。