基于累加跳距和校正因子的无线传感网定位算法

孙博文，韦素媛，李东林

(火箭军工程大学，陕西西安 710025)

0 引言

无线传感器网络(Wireless sensor net-work，WSN)是由若干个具有数据采集、处理、传输功能的节点通过自组织方式形成的网络，节点之间进行信息传递，达到对特定区域敏感数据实时监测的功能[1]。它在目标跟踪、环境监测等领域有广泛的应用，引起学术界的广泛关注和研究[2-3]。在应用中，节点时常被随机布置或播撒在监测目标区域内，因此事件发生的位置或获取信息的节点位置是传感器节点监测消息中的重要信息，定位技术也就成为WSN应用中的一项关键技术[4]。根据在定位过程中是否直接测量节点间的距离，可将WSN定位算法分为测距(Range-based)定位算法和非测距(Range-free)定位算法[5]。与基于测距的定位算法相比，基于非测距的定位算法具有成本低、功耗小、抗测量噪声能力强以及硬件设备简单等优势，且能够提供误差允许范围内的定位服务[6]，受到越来越多的瞩目。

在基于非测距定位算法中，DV-Hop算法是比较经典的定位算法之一，但当WSN中传感器节点分布不均匀和不规则时，DV-Hop算法存在定位误差较大的缺陷[7]。为了使定位的结果更加准确，研究者对其算法进行了不同程度的改进。文献[8]考虑了在计算锚节点间距离时可能存在彼此处于通信半径之内的情况，细化了锚节点间距离，使得平均跳距更加准确；文献[9]采用多通信半径的方法由锚节点多次广播信息，有效改善了定位精度，但是提高了网络连通度，影响网络成本与节点能耗；文献[10]提出将全网中所有锚节点平均跳距的平均值作为统一跳距，再通过细菌觅食算法来定位节点位置，但忽略了未知节点各自跳距的差异；文献[11]提出引入校正因子的概念，调整未知节点到锚节点的距离，达到了提高定位精度的目的；文献[12]先利用加权质心定位算法估算位置，再结合TDOA信标节点计算未知节点的坐标并修正，但该算法增加了成本且算法复杂度较高。

本文提出一种改进的DV-Hop定位算法，通过优化并累加未知节点平均跳距的方法计算出未知节点与锚节点间的距离，并引入校正因子进行二次定位修正未知节点估算坐标，使得未知节点估算坐标更接近实际值，提高了算法的定位精度。

1 DV-Hop定位算法及误差分析

1.1 传统DV-Hop定位算法简介

DV-Hop定位算法由Niculescu等提出[13]，其主要定位步骤分为以下3部分：

(1)锚节点先通过距离矢量交换协议路由广播自身信息，网络中所有节点记录下锚节点的坐标及相应的最小跳数[14]，锚节点广播消息结构如图1所示。

i

j

x

i

y

i

x

j

y

j

h

ij

i

j

i

i

i

(1)

每个未知节点u接收到距离其最近的锚节点的平均跳距信息，舍弃其他锚节点传来的信息，再根据步骤(1)中获取的跳数信息，估算出未知节点u与各个锚节点之间的距离。计算方法见式(2)。

duj=Hopsizeu×huj

(2)

式中：duj为未知节点u与锚节点j间的距离；Hopsizeu为未知节点选取的平均跳距；huj为未知节点与锚节点间的跳数。

(3)当未知节点确定了与3个或3个以上锚节点间距离后，利用极大似然法或三边测量法估计未知节点的坐标。

1.2 误差分析

(1)在计算锚节点自身平均跳距时，锚节点利用的是除自身以外其他所有锚节点，得到的平均跳距反应的是全局范围内的锚节点分布情况，但是忽略了各锚节点贡献度的大小情况。因此，若网络分布不均匀时造成的平均跳距误差会较大。

(2)计算未知节点与锚节点间距离时，根据一个未知节点平均跳距乘以跳数的方法，没有考虑链路中其余节点的平均跳距，误差较大。

(3)传统的DV-Hop法得到未知节点坐标后便结束了，没有对坐标精度进行修正的过程，可以通过已有的条件进行调整优化。

2 改进DV-Hop算法描述

2.1 平均跳距的改进

2.1.1 基于最小均方误差准则求锚节点平均跳距

传统DV-Hop定位算法在计算锚节点平均跳距时采用的是基于无偏估计准则，即通过公式(3)求得：

(3)

式中：dij为锚节点间距离；Hopsizei为需要求的平均跳距；hij为跳数；令f1等于零即可求出平均跳距。

然而，经过多次试验发现，误差服从高斯分布。根据参数估计理论，作为估计子误差的代价函数，使用最小均方差比使用无偏估计更为合理[6]。本文采用基于最小均方差准则来计算锚节点平均跳距，即对公式(4)求偏导来求Hopsizei的值。

(4)

(5)

通过上述分析，锚节点i平均跳距是由跳数hij乘以距离dij的和除以跳数hij平方和得到。

2.1.2 加权求未知节点自身平均跳距

传统的DV-Hop算法中，规定未知节点接收到第一个锚节点传来的跳距信息则作为自身平均跳距，此方法会带来定位误差，有许多学者提出了加权DV-Hop定位算法的概念[15-16]。本文在计算未知节点自身平均跳距时，不仅考虑离节点最近的锚节点的跳距信息，同时通过加权系数体现不同锚节点对未知节点坐标运算的影响力大小，算出加权平均跳距信息为之后求坐标打下基础。加权系数Qi通过式(6)计算得：

(6)

将加权系数代入步骤(2)中得未知节点自身平均跳距值Hopsizewci，见式(7)：

(7)

采用这种加权方式为的就是减少测距误差给定位带来的影响，多数情况下，与未知节点跳数多的锚节点会带来更多的误差[17]。

2.2 未知节点与锚节点之间距离的计算

如图2所示，根据上述DV-Hop定位步骤(2)中方法，计算未知节点1与锚节点5间距离时的表示式(8)如下所示：

d15=Hopsize1×4

(8)

但实际过程中经过的未知节点都有其各自的平均跳距，从图中也可以看出节点2、3间的跳距明显与节点1、2间的跳距不同，且未知节点只需计算与其较近的3个锚节点的距离，连接跳数不会太多。

因此，现提出一种依据自身平均跳距计算未知节点与锚节点距离的改进方法。计算未知节点与锚节点间距离时，采取“步步累加”的办法，即累加未知节点与锚节点网络连接过程中各未知节点自身的平均跳距。如图2所示，计算各未知节点与锚节点距离时，表示式(9)如下：

d15=Hops1+Hops2+Hops3+Hops4
d25=Hops2+Hops3+Hops4
d35=Hops3+Hops4
d45=Hops4

(9)

式中Hops1、Hops2、Hops3、Hops4分别为未知节点1、2、3、4通过加权求出的自身平均跳距。

2.3 未知节点坐标的修正

求出未知节点与锚节点间距离后，根据三边测量法能够得到未知节点的一个估计坐标，定义这些点为“锚节点”，运用定位算法计算出锚节点的估计位置(xe,ye)，将锚节点估计坐标与实际坐标做差求出调整因子Ti，Ti的表示式见式(10)，其中(xi,yi)为实际坐标。

(10)

运用极大似然估计法确定未知节点位置，计算公式如下，其中m为锚节点总个数Qi为2.1中的加权系数：

(11)

(12)

(13)

将上式看作线性方程组AX=b，解得：

(14)

(15)

(16)

得未知节点坐标为

Xa=(ATA)-1ATb

(17)

改进的算法整个流程图如图3所示。

3 算法的仿真及性能分析

3.1 仿真参数与环境

为验证算法的定位性能，使用matlab对DV-Hop算法、基于改进粒子群的定位算法(MPDV-Hop)[18]、文献[19]算法(WSGDV-Hop)和本文算法进行实验仿真，并对实验数据进行分析。实验仿真环境：在100 m×100 m正方形环境内，随机布设100个节点，其中锚节点有20个，节点的通信半径设为25 m。以下仿真实验，采取控制变量法，若无特殊说明，默认使用以上参数。且为了实验数据的准确性，最终仿真结果为100次仿真实验结果取平均值。

(18)

3.2 试验结果分析

由图4可知，当通信半径为25 m，节点总数为100时，4种算法的定位误差都随着锚节点比例的增加而逐渐减小，且锚节点比例低于25%时，定位误差随着锚节点比例增加明显下降，锚节点比例大于25%后，定位误差下降逐渐趋于平缓。这是由于锚节点数量的增多使得在计算平均跳距时，未知节点能够得到更多更有效的锚节点跳距信息，进而增加了定位的精度。不过当取相同锚节点比例时，本文算法定位误差始终低于其他3种算法，其定位误差较DV-Hop算法、MPDV-Hop算法和WSGDV-Hop算法平均减小了13.6%、7.7%和4.6%。

图4 锚节点比例与定位误差关系图

图5表示的是当节点总数为100，锚节点个数为20时，通信半径从20～50 m，4种算法的定位误差与通信半径的关系图。从图中可以看出，归一化定位误差随着通信半径的增加在逐渐减少，且在通信半径增加到35 m之后，定位误差的变化趋于平缓。这是由于随着通信半径的增加，每个节点的覆盖率得到提升，影响了网络的连通度，计算的平均跳距也能更准确。但是通信半径增加到一定程度后，定位误差有微小上升趋势或减少缓慢，这是因为锚节点的平均跳距随着通信半径的增加误差更大了，影响了定位精度。但当通信半径相同时，本文算法的误差均小于其他3种算法，本文算法的误差比DV-Hop算法、MPDV-Hop算法和WSGDV-Hop算法分别平均减小12.2%、6.9%、3.6%。

图5 通信半径与定位误差关系图

在图6中，保持通信半径为25 m，锚节点比例0.1，节点数从100到350均匀变化，4种算法的归一化定位误差随着节点总数的增加而减少，这是由于节点数量的增加，减小了节点之间的距离。且当节点总数超过250后，定位误差的下降速度减缓，这是因为此时制约定位误差的因素不再是节点总数。但在相同的节点总数条件下，本文算法比DV-Hop算法、MPDV-Hop算法和WSGDV-Hop算法的定位误差分别降低了12.9%、7.0%和3.7%。

图6 节点总数与定位误差关系图

4 结束语

本文针对传统DV-Hop定位算法在随机分布网络环境中的局限性，对算法原理及产生的误差进行了分析，提出了一种基于累加跳距和校正因子的DV-Hop算法。该算法较传统DV-Hop进行了三方面的改进：利用最小均方误差准则代替基于无偏准则的方法求锚节点平均跳距，并考虑网络中所有锚节点的影响，加权计算出未知节点自身平均跳距；累加未知节点与对应锚节点链路中各未知节点自身平均跳距，得到两者之间的距离；最后将未知节点看做“”反求原锚节点的估计坐标，加入权值修正，得到最终定位结果。从matlab仿真结果看，本文算法相比DV-Hop算法、MPDV-Hop算法及WSGDV-Hop算法在改善定位误差方面有更好的表现，且没有增加额外设备。由于算法需要计算优化的平均跳距和修正因子，因此计算量有少量的增加。