全局跳数优化与跳距误差修正的DV-Hop改进算法

任克强,邓 浪

(江西理工大学信息工程学院,江西 赣州 341000)

无线传感器网络(Wireless sensor Network,WSN)中,采用多个节点随机分布,自组织一个多跳网络,部署在需要监测的某些特定区域,采集与处理监测到的信息,同时将处理后的信息发送给监测人员[1]。WSN作为物理世界与数字世界的桥梁,在目标追踪、环境监测、军事侦察甚至在能量管理中已被广泛的应用[2]。在实际的应用中,缺少位置信息的感知数据是没有意义的[3]。因此,了解目标的位置信息对许多环境感知的应用十分重要,节点定位技术也成为WSN研究的关键技术之一。

在WSN现有的定位机制中,根据测量距离方式的不同可以划分成基于测距(Range-based)算法和非测距(Range-free)算法两个类别[4]。获取角度或距离信息对于Range-based算法来说十分重要,所以对整个传感器网络的硬件配置要求更为严格,同时也具有更好的定位精确度。Range-based算法主要有:AOA(Angle of Arrival)、TOA(Time of Arrival)、TDOA(Time Difference of Arrival)和RSSI(Received Signal Strength Indicator)等[5]。与Range-based算法相比较,从硬件成本和实现复杂度等方面考虑,Range-free算法实现简单,成本较低,但精度稍有不足。目前,Range-free算法主要有:质心定位(Centroid)、凸规划定位(Convex Programming)、DV-Hop(Distance-Vector-Hop)、MDS-MAP和APIT(Approximate PIT Test)等算法[6]。

作为Range-free算法的代表之一,DV-Hop算法应用广泛、易于扩展并且受限制的条件更少,能做到符合大多数应用场景所要求的定位效果,所以得到了广泛应用与研究[7]。针对DV-Hop自身的一些不足之处,国内外相关学者从诸多方面提出了相应的改进方法。文献[8]对多种Range-free定位技术进行了评估,采用基于粒子群(PSO)的DV-Hop算法,与传统DV-Hop算法相比具有更好的定位精度和鲁棒性,虽然PSO算法收敛速度快,但是容易陷入局部最优并且不适合用于处理离散的优化问题。文献[9]针对计算过程中容易产生误差积累的最小二乘法提出改进方案,并对锚节点跳距进行权值处理,通过改善平均跳距的相对误差值,提高定位的准确率,但在增加了定位准确率的同时,加大了全网的计算量。文献[10]采用混合加权定位的方法,通过对质心算法进行两次加权以获取更好的定位精度,相较于其他混合算法,该算法在耗能控制和计算量方面具有一定优势。文献[11]在对误差距离权值处理的基础上,对网络中节点位置关系进行判断,利用距离未知节点最近的3个锚节点的跳距信息通过归一化加权的方式计算未知节点的估算跳距,同时针对节点的坐标估算,采用改进的遗传算法进行处理,但采用遗传算法需要考虑到早熟收敛的问题,进化至后期时局部搜索的能力较弱。文献[12]提出基于PSO-BP传感器位置确定的改进策略,通过利用改进后的卡尔曼算法对RSSI值进行相关优化,目的是减少噪声与误差,最后优化阈值与权值,该算法具备获取全局最优值同时避免局部最优值出现的能力,有效的改善神经网定位算法的效果。文献[13]首先对DV-Hop的洪泛机制进行改进,获取最近锚节点的平均跳距参与估算,然后通过改进的差分校正算法减少跳距的累积误差,最后对整个预测的区域使用粒子滤波,提升估计节点坐标的准确率且通信开销相对较低。

针对DV-Hop算法跳数不合理及跳距估算阶段误差累积的问题,本文对DV-Hop算法的跳数及跳距两个方面进行优化与修正,提出了一种基于全局跳数优化与跳距误差修正的DV-Hop改进算法,采用通信半径等相关参数优化跳数的取值,使跳数趋于合理,通信双方之间估算跳距的误差进一步减少,以提升定位精度。

1 DV-Hop算法及定位误差

1.1 DV-Hop算法

DV-Hop算法是基于矢量路由的经典Range-free算法之一,定位过程主要包含3个基本步骤[14]:

①节点间跳数的估算

所有锚节点将位置与跳数数据发送给可通信节点,接收节点收集到该数据后,保留该数据并使跳数加1,继续转发至未获得节点数据的目标,直至整个网络中相对距离最近的锚节点都能获取到的对方位置和跳数数据。

②节点间跳距的估算

网络中全部的锚节点获得了最近锚节点的最小跳数值与节点位置信息,利用获得的数据通过式(1)对节点平均每跳距离进行估算:

(1)

式中:(xi,yi)与(xj,yj)为锚节点i、j的实际位置坐标,hij为锚节点i、j之间的最小跳数,Hopsizei为锚节点i平均每跳距离。

通过式(2)计算锚节点i、j之间的估算距离dij:

dij=Hopsizei×hij

(2)

③未知节点坐标的估算

利用节点距离和跳数的估算数据,采取极大似然法估算出未知节点的坐标。

1.2 定位误差

DV-Hop算法中网络连通度和锚节点间距离信息对未知节点位置估算十分重要[15],定位过程中产生误差的原因主要有:

①DV-Hop算法的定位精度很大程度上取决于平均跳距的估算值是否合理,单一的锚节点估算出的平均跳距不能完全代表整个网络的跳距情况,并且多跳情况下,未知节点与锚节点的估算距离并不是按照直线计算,节点密度低的区域节点的折线率增大,距离误差将进一步累积,对定位效果产生影响。

②网络中随机播撒的WSN节点拓扑结构往往不规则,区域内节点密集程度也就存在差异,不同节点密度估算出的节点间跳数信息以及平均跳距存在一定的误差。根据DV-Hop算法的特性,锚节点通信范围内可通信的节点均被视为单跳节点,当大量单跳节点参与距离估算,平均跳距就不能真实的反映网络中各节点间的距离,导致估算距离与真实距离之间存在差异,降低定位精度。

因此,本文从节点之间的跳数以及节点之间估算距离对DV-Hop算法进行修正。

2 本文算法

2.1 节点间跳数修正

DV-Hop算法估算节点间跳数时,通信区域内的所有邻居节点都被视作1跳。如图1所示,B、C、D和E都为节点A的单跳节点,但对应的真实距离却各不相同,如果这类节点都按照DV-Hop算法处理,会产生较大的定位误差。针对此类情况,本文引入节点偏差系数、节点相对最佳跳数以及跳数差值修正系数,并与影响跳数的相关参数相结合,提出一种全局节点跳数优化的方法。

图1 通信范围内单跳误差

对节点的通信区域内单跳的数值进行限制,将节点i、j之间的真实距离dij与通信半径R之比定义为相对最佳跳数Hij:

Hij=dij/R

(3)

比较估算跳数hij和相对最佳跳数Hij二者的差值,通过式(4)定义偏差系数σij:

σij=(hij-Hij)/hij

(4)

偏差系数σij能够体现互相通信的锚节点间估算跳数hij与相对最佳跳数Hij存在的差异情况。σij越大,标志着二者之间存在更大的偏差。在通信半径不变的情况下,估算跳数将大于或等于相对最佳跳数,针对此类情况利用式(5)定义差值修正系数ωij,以优化跳数信息减少误差的累积。

(5)

此外,跳数数据还受到多个参数的影响,锚节点占比、播撒区域面积和通信半径都会影响通信过程中的路径选择,使跳数数据发生变化。局部区域内锚节点数量增多,将对定位效果产生一定的影响,对于此类区域,锚节点占比增加,网络连通情况更好,会使一定通信半径内局部单跳节点增多,将此类节点估算出来的跳数应用于全网,使相对最佳跳数之间误差进一步加大。于是定义跳数修正系数θij:

(6)

式中:L为正方形播撒区域的边长,ρ为锚节点占比。

θij随着整个网络连通度的增加而减少,当网络连通情况较差且锚节点比例较低时,利用θij对跳数进行修正,降低单跳节点对整体跳距计算的影响。当网络连通度较好且锚节点比例较高时,θij值将会变小,对跳数的影响也会降低,避免多跳情况下的误差累积。

通过差值修正系数ωij与跳数修正系数θij对锚节点跳数进行修正:

(7)

将差值修正系数ωij与跳数修正系数θij共同应用于全网节点的跳数估算:

(8)

2.2 平均每跳距离修正

DV-hop算法中平均跳距对于节点间距离的估算十分重要。如图2所示,数据通过节点A发送至节点B共需3跳,DV-Hop算法中折线距离为估算距离,显然与虚线所示的真实距离存在较大的误差。因此,本文利用最佳指数下的最小均方误差准则计算平均跳距并且与依据实际距离得出的单跳平均误差共同修正平均跳距,以进一步降低平均跳距的误差,改善定位效果。

图2 节点间距离误差

对于锚节点,通过式(2)可估算出锚节点平均每跳距离的估计值,已经获取锚节点位置信息的前提下,可以利用锚节点i与s的真实距离与估算距离计算出二者的总体差值:

(9)

通过式(9)求出的总差值除以总跳数计算出平均每跳距离误差εi:

(10)

利用估算距离加上平均每跳的距离误差,得到校正后的平均跳距Dhopε:

Dhopε=hopsizei+εi

(11)

采用自适应的最小均方误差准则,目的是使总误差全局最小,相对于偏差和方差来说应用于跳距的计算更加合理,但需要使代价函数f满足:

(12)

对代价函数f求hopsizei的偏导并取值为0,得到平均跳距Dhopf:

(13)

通过式(13)计算出的平均跳距,估算距离与实际距离的误差较小,此外本文将变化的指数值μ引入式(13),根据不同μ值对定位误差的影响,选取最佳值应用于平均跳距的修正,式(13)改写为:

(14)

为了避免单一跳距均值不能很好的反映整个网络中跳距的情况,减少数据不够准确而带来误差累积的风险,将已校正的平均跳距值与使用最佳μ值下的最小均方误差计算出的平均跳距进行二次平均,得到修正后的平均跳距Dhopave:

(15)

利用式(15)求得修正后的平均跳距,能够更接近于整个网络中实际平均跳距,进一步减少跳距误差累积的影响,从而提升定位精度。

3 仿真结果与分析

为了测试本文算法的性能表现,采用MATLAB R2016b仿真平台对本文算法、DV-Hop算法和文献[14]算法从最小均方误差的不同μ值、差值修正系数的不同n值、网络内节点总数、节点通信半径以及锚节点占比对定位误差的影响进行仿真实验。仿真实验环境:100 m×100 m的仿真区域内,随机安置150个节点,其中锚节点比例为10%,所有节点的通信半径均为R=30 m。

采用平均定位误差Errorave作为评价定位效果的标准。

(16)

图3 μ值变化下的平均定位误差

首先验证最小均方准则下的指数值的变化对平均跳距修正的影响,在100 m×100 m的仿真区域内,安置150个节点,锚节点占比为10%,通信半径R=30 m,本文对μ取1.95到2.05,步长为0.01。从图3中能够了解到,μ值取1.98时平均定位误差最小。相较于初始原始取值2,平均定位误差稍稍降低,与μ值取1.95相比较,平均定位误差减少约1.7%,表明采用最小均方误差准则估算平均跳距时,μ的取值将会对平均跳距产生干扰,改变最后的定位效果。本文算法在验证各参数对平均误差影响的实验中,均以1.98为最小均方误差最佳指数值。

图4表明了在100 m×100 m的仿真实验环境下,n值变化下的平均定位误差的变化情况。本文对n取1.95到2.05,单次增幅为0.01。从图4中可以看到n取值变化的过程中,平均定位误差存在些许波动,在1.96取值下定位效果优于其他取值,相较于2.05的取值,效果提升了1.85%。表明n的取值会干扰到跳数值的测定,影响定位误差。本文算法在验证各参数对平均误差影响的实验中,差值修正系数中n均取1.96。

图4 n值变化下的平均定位误差

图5表明仿真实验环境下,设置通信半径由20 m单次递加4 m最高至40 m条件下,本文算法、文献[14]算法以及DV-Hop算法平均定位误差的变化情况。随着通信半径的增长,3种算法定位精度均有所提升,但在增至到某一数值时,例如36 m,文献[14]的平均定位误差出现了些许波动,表明在某些条件下,半径的增加对文献[14]的算法而言,定位精度提升不明显。总体来说,本文算法平均定位误差相比于文献[14]和DV-Hop算法减少约6.58%～9.56%和13.1%～14.5%,且相较于文献[14]与DV-Hop两种算法,大通信半径导致节点路径选择减少的情况下,整体性能表现较好。

图5 不同通信半径的平均定位误差

图6表明仿真实验环境下,锚节点比例单次增长2%,由初始的8%增长至20%的条件下,本文算法和对比算法定位效果。随着仿真环境中锚节点占比的增长,3种算法的定位效果都不同程度的增长。DV-Hop算法锚节点占比由8%增至10%的过程中,定位精度有明显的提升,而后锚节点占比的增长对定位效果的影响较小,逐渐趋于平稳。本文算法与文献[14]算法均能针对DV-Hop算法在锚节点比例较低时节点随机分布不均影响定位效果的情况进行优化,定位精度提升明显。控制锚节点占比固定值为12%的条件下,DV-Hop算法平均定位误差为32.8%,文献[14]算法为27.6%,而本文算法为22.04%,并且整体效果也优于其他两种算法图7表明仿真实验环境下,节点总数在100～200范围内,每次增加20的条件下,DV-Hop、文献[14]以及本文算法在节点数量变化下平均定位误差的趋势。DV-Hop算法整体表现较为平稳,误差最大值与最小值仅相差1.7%,而本文算法与文献[14]算法整体效果依然优于DV-Hop算法,由于节点总数的增长,单个锚节点覆盖的未知节点数也一同增长,使整个网络的连通度更好,提升了定位精度。相较于文献[14]与DV-Hop算法,本文算法总体定位精度提升约3.39%与9.69%,表明在WSN总节点数增加的情况下,本文改进算法效果好于文献[14]算法与DV-Hop算法。

图6 不同锚节点占比的平均定位误差

图7 不同节点总数的平均定位误差

4 结束语

针对WSN中DV-Hop算法信息转发时跳数不合理和跳距误差累积的问题,为了降低累积误差,以改善定位效果为目的,本文提出了一种跳数优化与跳数修正的DV-Hop改进算法。改进算法通过定义跳数修正系数对跳数信息进行优化,再对指数最佳值下的平均跳距和校正后的平均跳距进行二次优化,并在选取最佳μ值与最佳n值的前提下,对WSN环境中不同通信半径、不同锚节点比例和不同节点总数的环境下进行定位性能仿真测试。实验结果表明,在多种仿真环境且不增加额外的硬件开销和通信成本的条件下,本文算法的定位表现优于DV-Hop算法与相关算法,表明本文对DV-Hop算法的改进能够有效提升WSN中节点的定位精度。如何进一步降低跳距误差累积,以使未知节点位置信息更加准确是后续研究的重点方向。