基于测距修正及改进鲸鱼优化的DV-HOP定位算法

王 磊，刘晶晶，齐俊艳，贺军义

(河南理工大学计算机科学与技术学院，河南焦作 454000)

0 引言

无线传感器网络(wireless sensor network，WSN)是由大量节点组成的自组织网络，通过相互协作，节点可以实现对指定监控区域对象的数据感知、采集和处理，并将数据传输给用户[1]，具有快速部署、安全可靠的良好性能，有着广阔的应用前景。无线传感器网络在工业控制、环境监测等领域显示出巨大的潜力和应用价值[2]。无线传感器网络在一些应用领域需要掌握节点的位置信息。比如森林火灾监测，天然气管道泄漏。针对这类事件的发生，首先需要确定的是传感器节点的地理位置信息。因此，无线传感器节点的定位具有重要的意义。

目前经常用的定位算法可以分为基于测距的定位算法和无测距的定位算法。常用的测距技术有TOA[3]、TDOA[4]、RSSI[5]以及AOA[6]等。常用非测距定位技术主要有APIT[7]法、质心法[8]、DV-HOP[9]和凸规划[10]等。在实现基于测距的定位算法之前，需要计算节点间的距离。在实际应用中，需要额外的硬件，且能耗和成本较高，不能广泛应用于特定环境，无需测距的定位技术利用节点间的连通性实现定位。无需额外硬件的支持，可以节约成本，降低能耗。因此，无需测距定位方法在实际应用中得到更广泛的应用[11-12]。DV-HOP定位算法是一种典型的无测距定位方法。它具有硬件要求低、实现简单等优点，受到了国内外研究者的广泛关注。然而，也存在定位误差大、定位精度低等问题，因此研究者做了大量的研究。

现有DV-HOP定位算法从修正最小跳数或平均跳距、选择最优信标节点、优化坐标等方面进行了改进。文献[13]提出了一种基于RSSI跳数量化与误差修正的DV-HOP定位算法。从跳数量化、修正平均距离和未知节点坐标等方面对DV-HOP定位算法进行改进，但是RSSI测量技术需要额外硬件支持，增加了成本。为了修正节点间的最小跳数，文献[14]提出了双通信半径改进节点最小跳数。虽然算法的精确度得到改善，但是算法复杂度高。在此基础上，文献[15]中提出一种改进多通信半径的DV-HOP定位算法，在多个通信半径定位的基础上利用余弦定理修正最小跳数和估计距离，解决了节点分布不均匀时存在的误差。通信半径越多，定位误差越小，网络的开销越大。文献[16]将DV-HOP算法与半测量加权质心相结合，信标节点通过质心算法进行自身定位，并将定位精度作为未知节点的权重，修改未知节点和信标节点之间的跳距，减少DV-HOP算法的误差，但算法复杂度高且难以实现。文献[17]采用相似路径匹配法校正信标节点与未知节点之间的距离，并采用改进灰狼优化算法优化节点坐标。定位误差减小，定位精度提高，但是没有考虑节点稀疏、相似度不高的环境。文献[18]提出基于DV-HOP测距修正的动态调参差分进化算法，利用多通信半径和节点远近度修正测距值，通过动态调整差分进化参数进行寻优搜索，在算法精度提高的同时也加大了网络的开销和算法复杂度。为了更好地提高算法的精确度，本文提出了一种基于鲸鱼优化改进的DV-HOP定位算法。在估计距离阶段，通过添加修正因子和权重，以提高未知节点估计距离的精度，在定位阶段，引入改进WOA算法优化定位结果，从而减小节点定位误差。

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

1.1 DV-HOP定位算法

DV-HOP(distance vector-hop)算法是Niculescu等人基于矢量路由原理提出的一种无需测距的定位算法，DV-HOP定位算法可以分为以下3个阶段。

1.1.1 计算未知节点与每个信标节点的最小跳数

每一个信标节点发出1个包含其自身位置信息、跳数和地址的包，跳数的初始值为0。在从信标节点接收到该数据包后，邻近的其他节点检查自身的跳数是否小于之前从信标节点接收到的跳数。如果是，在数据加1后广播包。最后，网络中所有未知节点都能知道到信标节点的最小跳数。

1.1.2 计算未知节点与信标节点之间的距离

根据信标节点自身获得的其他信标节点的坐标信息和跳数，利用式(1)计算信标节点每跳的平均跳距并向全网广播，根据式(2)计算未知节点m与信标节点i之间的估计距离。

(1)

dmi=HopSizei×hmi

(2)

式中：(xi、yi)、(xj，yj)为信标节点i，j的坐标；hij是信标节点i与j(i≠j)之间的最小跳数；dmi为未知节点m与信标节点i之间的估计距离；hmi为未知节点m与信标节点i之间的最小跳数。

1.1.3 计算未知节点坐标

未知节点收到3个或更多信标节点的距离，根据式(3)进行自身位置的计算。

(3)

式中：(xm,ym)为未知节点m的坐标；(xi,yi)为信标节点i的坐标，i=1,2,3,…，n。

将式(3)中的前n-1个方程分别减去第n个方程并用矩阵AX=B的形式表示，其中A、X和B可由式(4)表示：

(4)

利用最小二乘法计算未知节点的估计坐标，由式(5)表示:

X=(ATA)-1ATB

(5)

1.2 DV-HOP定位算法误差分析

在WSN的实际应用中，节点是随机部署在环境中的，不能保证节点的均匀性。而DV-HOP的定位过程要基于矢量信息和拓扑结构的连通性。当节点分布不均匀时，会存在较大的误差。定位算法主要误差来源有：

(1)DV-HOP定位算法的定位过程依赖于信标节点的平均跳距，当节点分布不均匀时，节点之间的最小跳数往往是折线，当用折线代替直线求节点间的距离时就会产生误差。

(2)WSN的网络结构具有多样性，采用未知节点最近的信标节点的平均跳距对未知节点的距离进行估计时，具有单一性和偶然性，将对定位的精度产生影响。

(3)在DV-HOP的最后1个阶段，利用最小二乘法求未知节点的坐标时，用前n-1个方程分别减去第n个方程，会造成误差积累。

2 改进定位算法

2.1 信标节点平均跳距的修正

(6)

(7)

利用实际距离与估计距离之间的差值求修正因子ei,如式(8)所示。然后通过式(9)修正信标节点的平均跳距。

(8)

(9)

2.2 未知节点平均跳距的修正

DV-HOP定位算法，在第2阶段求未知节点到信标节点的距离时，采用靠近未知节点的信标节点的平均跳距值，由于无线传感网络中节点的分布具有随机性，未知节点到每个信标节点的平均跳距值并不相同，这会导致距离估计值的误差较大。因此本文考虑未知节点接收到的其他信标节点跳距值，根据未知节点到各个信标节点的跳数信息引入权重因子，并利用2.1节中修正后的信标节点的平均跳距值修正未知节点的平均跳距，假设未知节点m共收到n个信标节点的平均跳距，权重因子wi可用式(10)表示。

(10)

式中：wi为权重因子；hmi为未知节点m到信标节点i的最小跳数。

未知节点的平均跳距可用式(11)表示。

(11)

2.3 改进鲸鱼算法优化定位结果

2.3.1 标准鲸鱼优化算法

鲸鱼优化算法(WOA)是澳大利亚学者Mirjalili和Lewis等人提出的群智能优化算法[19]。它的思想是通过模拟座头鲸的独特搜索方法和环绕狩猎机制寻找最优解，具有原理简单、参数设置少、搜索能力强等优点。包括包围猎物、泡泡网攻击和搜索猎物3个阶段。

2.3.1.1 包围猎物

鲸鱼在觅食时通过确定猎物的位置包围和捕食猎物。最佳搜索代理假设当前最佳候选解决方案是猎物或靠近目标的位置。其他鲸鱼根据最佳候选解决方案更新自己位置。该行为可以用式(12)表示：

(12)

式中：t为当前迭代次数；X*(t)为t代中最优解的位置；X(t)为第t代当前解的位置；D为最优解与当前个体差距；A和C为系数；r为[0,1]区间的随机数；a随着迭代次数的增加从2到0线性递减；t_max为最大迭代次数。

2.3.1.2 泡泡网攻击策略(利用阶段)

鲸鱼的泡泡网攻击策略包括两种机制。第一种是收缩包围机制，通过降低收敛因子a来实现。a随着迭代次数增加逐渐减小，A为[-a,a]区间上的随机数。当|A|≤1时，鲸鱼以收缩包围的方式更新位置。第二种是螺旋更新位置机制，当座头鲸发现猎物且随机概率大于0.5，以螺旋状移向猎物。可由式(13)表示：

X(t+1)=D′·ebl·cos(2πd)+X*(t)

(13)

式中：b为常数；l为[-1,1]区间上的随机数；D′为第i只鲸鱼与当前最优解(猎物)的距离，D′=|X*(t)-X(t)|。

鲸鱼收缩包围猎物的同时沿螺旋型路径游动。为描述两者的同步行为，假设鲸鱼在两者方式之间更新位置的可能性为50%。由式(14)表示

(14)

式中p为[0,1]之间的随机数。

2.3.1.3 搜索猎物机制(探索阶段)

在探索阶段，当|A|>1时，鲸鱼个体会远离本来的目标猎物。算法不再会根据目标猎物的位置更新自己的位置，而是随机选择1个搜索代理替换目标猎物。其数学模型用式(15)表示：

(15)

式中Xrand表示当前种群随机一个搜索代理的位置。

2.3.2 改进鲸鱼优化算法

2.3.2.1 Tent混沌映射初始化种群

鲸鱼优化算法具有参数少、模型简单、容易实现等优点，标准鲸鱼优化算法在搜索空间中随机产生初始种群，会造成搜索空间中的种群分布不均匀，为使种群在初始空间中均匀分布，引入Tent混沌映射初始化种群。Tent混沌映射的随机性和遍历性可以使算法在一定范围内不重复的遍历所有状态，保证种群均匀分布在解空间内。Tent混沌映射方程如式(16)所示：

(16)

式中xn为[0,1]区间的一个随机数。

2.3.2.2 非线性收敛因子与自适应惯性权重策略

在优化过程中，WOA算法会出现全局搜索和局部开发不平衡的现象。但是全局搜索和局部开发都受参数A的影响，参数A的变化依赖于收敛因子a。在标准鲸鱼优化算法中，迭代过程中的收敛因子a从2线性下降到0，不能满足实际情况。本文对收敛因子a进行了改进。用式(17)表示收敛因子a的变化。

(17)

式中：t表示当前迭代次数；t_max表示最大迭代次数。

鲸鱼优化算法在迭代过程中猎物引导鲸鱼进行位置更新时会存在差异，为了充分利用最优解，提高算法的寻优精度。在WOA算法更新公式中，引入自适应参数作为惯性权重。

自适应权重表达式如式(18)所示：

(18)

式中：μmax=1；μmin=0。

改进后的鲸鱼算法更新公式为：

(19)

X(t+1)=μXrand-AD

(20)

2.3.2.3 差分变异操作

在WOA算法中，当前最优个体会靠近全局最优个体，如果当前最优个体位置不是全局最优，那么随着迭代次数的增加，种群中的个体会向局部最优聚集。结果导致种群中多样性降低，算法收敛早，寻优精度低。为此，本文中引入差分变异策略，将随机选择的个体和当前最优的个体与当前个体进行随机差分生成新个体。增加种群个体多样性，避免算法因早熟收敛而陷入局部最优。随机差分变异策略如式(21)所示：

X(t+1)=r1(X*(t)-X(t))+r2(X′(t)-X(t))

(21)

式中：r1和r2为[0,1]的随机数；X′(t)为种群随机选取的个体。

2.4 设置适应度函数

在无线传感网络中，求估计距离的方法影响定位精度。为了减小定位误差的影响。本文利用改进的WOA优化算法进行优化。适应度函数如式(22)所示：

(22)

式中：(xm,ym)为未知节点m的坐标；(xi,yi)为信标节点i的坐标；dmi为未知节点m和信标接地点i的估计距离。

2.5 改进DV-HOP定位算法流程

为解决DV-HOP算法中定位误差的问题，本文提出了基于误差修正和改进WOA的DV-HOP的定位算法。改进后的DV-HOP定位算法流程如下：

(1)初始化网络区域大小以及网络中的节点数，信标节点发送数据包，其他节点通过接收到的数据包计算节点间的最小跳数。

(2)通过式(6)～式(11)对未知节点的平均跳距进行改进，并将最小跳数和改进后的平均跳距的乘积作为未知节点到信标节点的估计距离。

(3)设置相关参数，主要有鲸鱼规模N，最大迭代次数t_max。

(4)利用tent混沌映射初始化种群。

(5)根据式(22)计算种群个体适应度值。利用改进的更新式(19)和式(20)对个体位置进行更新。根据式(21)执行随机差分变异扰动。

(6)如果满足迭代终止条件，则终止算法的执行并输出全局最优解;否则返回步骤(5)继续迭代优化。

(7)重复步骤(4)～步骤(6)，直到输出所有未知节点的估计坐标。

3 算法仿真结果与分析

为了验证本文改进算法的性能，利用仿真平台，对传统DV-HOP、文献[20]算法(ABCDV-HOP)、文献[21]算法(DEDV-HOP)以及本文提出的算法进行了仿真比较，如图1所示，设置100 m×100 m的矩形仿真区域，把100个传感器节点随机分布在仿真区域中，鲸鱼的种群个体设置为30，迭代300次。为了避免实验结果的偶然性，实验结果取50次实验的平均值。本文用归一化定位误差比较算法的定位性能。归一化定位误差如式(23)所示：

图1 节点随机部署区域图

(23)

3.1 信标节点对定位精度的影响

如图2所示，为研究信标节点对定位精度的影响，传感器节点的数量设置为100，信标节点的数量由5逐渐增加到40，通信半径设置为25。当信标节点的数量逐渐增加时，4种算法的性能分析比较的仿真结果表明，随着信标数量的增加，四种算法的待定位误差逐渐减小。在数量达到25后定位误差的变化都逐渐稳定。其中本文提出的WOADV-HOP算法，定位误差始终最小，比DV-HOP，ABCDV-HOP和DEDV-HOP算法的平均误差分别减小52%，46%，27.6%。

3.2 通信半径对定位精度的影响

如图3所示，为通信半径对定位精度的影响，图中，传感器节点设置为100，节点的通信半径从15到40逐渐增加。仿真结果显示，4种算法的节点定位误差随着通信半径的增加而减小。当通信半径到达30后，定位误差减小变慢。这是由于节点通信半径的大小会影响网络的连通性，从而影响算法的准确性。从图3中可以看出，WOADV-HOP的定位算法优于其他3种，WOADV-HOP算法的定位误差比DV-HOP减少了49%，比ABCDV-HOP减少了40%，和DEDV-HOP相比减少了21%。

图3 通信半径对定位精度影响对比图

3.3 节点总数对定位精度的影响

如图4所示，为节点总数对定位的精度影响对比图。设置通信半径为30，信标节点占节点总数的10%。节点的总数量从100逐渐增加到400。仿真结果显示，4种算法的定位误差随着节点数量的增加逐渐减小。当节点总数大于300时，误差趋于稳定。通过对比分析可知，在其他条件相同的情况下，本文提出的WOADV-HOP定位算法定位误差低于其他算法，WOADV-HOP算法的定位误差相比DEDV-HOP和ABCDV-HOP分别减少了25%、21%，相比于传统DV-HOP减少了39%。

图4 节点总数对定位精度影响对比图

3.4 定位算法耗时对比

设置节点通信半径为30，信标节点比例为10%,节点总数分别取100、150、200、250时，算法运行时间取20次运行时耗的平均值。4种算法的仿真时间如表1所示，随着节点数量的增加，算法的计算时间增加。由表1可以看出，4种算法中传统DV-HOP算法用时最短，在提高优化算法精度的同时，增加了算法的复杂度和运行时间。文献[20](ABCDV-HOP)只利用蜂群优化算法优化了定位阶段，因此算法的计算时间相比于传统DV-HOP增加较少。本文算法和文献[21](DEDV-HOP)算法既优化了测距阶段又优化了定位阶段，算法计算时间比传统DV-HOP增加较多。本文算法计算时间虽然有所增加，但是计算时间比DEDV-HOP短，精度在4种算法中最高。

表1 不同节点数量下算法平均计算时间对比表 s

4 结论

在无线传感器网络中，大多数应用需要知道传感器节点的确切位置。本文通过分析传统DV-HOP定位误差来源，提出了基于测距修正及鲸鱼优化改进的DV-HOP定位算法。该算法通过添加修正因子和惯性权重修改测距值，利用改进鲸鱼优化算法代替最小二乘法求待定位节点的坐标。在改进的鲸鱼算法中，采用Tent混沌映射提高算法的收敛速度和算法的遍历性，利用非线性收敛因子和惯性权重提高算法的全局开发和局部探索能力。最后通过差分变异策略防止算法过早收敛陷入局部最优。实验结果表明，与传统DV-HOP算法、文献[20]算法和文献[21]算法相比，本文算法提高了算法的定位精度，拥有较好的稳定性。由于算法对平均跳距进行了修正，坐标进行了优化，增加了算法的复杂度。在后期的工作中，将降低算法的复杂度，进一步研究高精度低能耗的定位算法。