融合跳数修正与动态布谷鸟搜索的改进 DV⁃Hop 算法

任克强，温晓珍

（江西理工大学 信息工程学院，江西 赣州 341000）

0 引 言

无线传感器网络（Wireless Sensor Network，WSN）部署的各种应用中，所有传感器节点共同完成一个特定任务。这些传感器节点通过感知周围的环境现象，收集所需的环境信息送到监测人员处进行适当的处理[1]。由于能获取客观的物理信息，WSN 在森林监测、医疗及智能交通等诸多领域得到了广泛的应用[2]。在WSN 应用中，传感器感知到的环境数据需在事件发生位置已知的前提下才有实际意义[3]。因此，节点定位是WSN 应用中的一项关键技术，其定位精度直接关系到WSN 系统的整体性能。根据是否测量实际距离可将节点定位算法分为基于距离和距离无关两种算法[4]。TOA、TDOA、AOA和RSSI 是主要的基于距离的定位算法[5⁃7]，测距阶段易受环境因素的影响，并且需要增加额外的硬件开销，在资源受限的应用中是不实用的。相比基于距离的算法，距离无关算法无需实际测量节点间距离，硬件开销较小，主要分为质心算法、APIT 和 DV⁃Hop 等[8⁃10]。

DV⁃Hop 定位算法是一种应用广泛的距离无关的定位算法，具有复杂性低、可扩展性好等优点[11]。在传统的DV⁃Hop 算法中，跳数、跳距的处理误差和未知节点坐标的计算误差是导致定位不理想的主要原因。针对DV⁃Hop 算法定位精度不理想的问题，国内外相关文献给出了相应的解决策略，文献[12]提出一种基于布谷鸟优化的DV⁃Hop 算法，利用两种优化算法同时搜索，动态调整布谷鸟算法的概率参数，减小了距离误差在定位阶段的累加，有效提高了定位精度，但双种群并行搜索增加了算法复杂度。文献[13]提出一种基于误差距离加权与跳段算法选择的遗传优化DV⁃Hop 定位算法，利用最优节点通信半径对算法进行改进，并通过误差分析优化信标节点的分布，采用加权法求未知节点的位置，相对于传统DV⁃Hop 算法，减小了定位误差。文献[14]在未知节点已知所有信标节点之间的距离时，利用布谷鸟搜索方法估计节点的位置，该方法将定位问题转化为全局优化问题，减小了跳数误差积累。文献[15]提出一种改进的DV⁃Hop 无线传感器网络定位算法，将接收信号强度指示RSSI 加入定位系统对原算法进行改进，对节点间跳数进行修正，但RSSI 测距易产生误差，对定位精度的提高不够明显。文献[16]基于加权二乘的DV⁃Hop 定位算法，通过利用信标节点的影响力大小不同，确定最小二乘法的权重值，再运用加权似然估计方法和三边测量定位法，求得未知节点的位置坐标，定位精度有一定的提高。文献[17]提出了改进的布谷鸟算法（MCS）和共轭梯度（CG）作为二次优化技术，采用改进的布谷鸟算法进行权重选择，该融合算法具有较高的收敛速度和较好的性能，但计算复杂度较高。

针对DV⁃Hop 算法因跳数误差、平均每跳距离误差与未知节点坐标计算误差等因素导致的定位精度低的问题，本文采用了两种优化策略对定位算法进行改进。一是提出利用修正因子调整跳数，并引进虚拟交圆估计平均每跳距离，以减小由于不准确的跳数和平均每跳距离的偏移而导致的误差积累；二是在DV⁃Hop 定位的第三阶段，采用混合布谷鸟搜索方法进行优化，首先定义适应度函数并计算适应度值，将适应度值分为三类并进行动态计算，得出三类细分的最优搜索公式，协调以达到布谷鸟搜索的局部与全局最优，提高定位的精度。

1 DV⁃Hop 算法及分析

1.1 DV⁃Hop 算法实现步骤

DV⁃Hop 定位算法的实现包括三个步骤，具体如下：

1）计算节点间的最小跳数

信标节点将自身位置信息的分组进行广播，接收节点记录到的每个信标节点的最小跳数，然后将跳数值加1 后转发给邻居节点，以近似同心圆的方式使网络中所有节点能够记录到每个信标节点的最小跳数。

2）计算节点间的实际跳距

根据第一阶段记录的跳数信息，利用式（1）计算平均每跳的实际距离。

式中：(xi,yi)与 (xj,yj)为信标节点i,j的坐标；hij为信标节点间的最小跳数。

信标节点将计算的平均每跳距离进行广播，未知节点接收后，根据记录的跳数，计算到每个信标节点的跳转距离。

3）计算未知节点坐标

根据记录到的每个信标节点的跳转距离，利用三边测量法或极大似然估计法计算未知节点坐标。

1.2 DV⁃Hop 算法分析

分析DV⁃Hop 算法定位的三个阶段可知，影响DV⁃Hop 算法定位精度的主要因素有三个：跳数误差、平均每跳距离和节点位置计算方法。

1）跳数跳距误差分析

在DV⁃Hop 算法中，在估计信标节点间的跳数时，通信区域内所有邻居节点都被记为一跳，而实际每一跳的长度是不一致的，在计算节点间的最小跳数阶段，它们仍被统一记为一跳，这种计数方法对跳数计数和平均每跳距离的估计都有较大的影响，易产生较大的误差。

2）未知节点坐标计算方法误差分析

在DV⁃Hop 算法中，通常采用三边测量法或极大似然估计法进行节点定位计算，然而三边测量法对测距误差较为敏感，容易影响最终定位精度；在极大似然估计法中，矩阵的误差偏移也会影响节点坐标的精度，增加算法的定位误差。

2 布谷鸟算法分析

2.1 布谷鸟搜索算法原理

布谷鸟搜索（Cuckoo Search，CS）算法是一种仿生群体智能算法[18]，具有结构简单、参数少、易于实现等优点，可有效平衡算法局部与全局搜索能力。通过分析布谷鸟的繁衍习性，部分布谷鸟不筑巢，它们将卵产于其他鸟窝，以寄生方式由其他鸟代为育雏，若这些鸟蛋被宿主发现，宿主便会丢弃它们或者重新筑巢。

实现CS 算法需满足三个条件：

1）布谷鸟每次只产一个卵，且随机选择一个鸟巢放置；

2）在这组随机选择的鸟巢中，最好的那一个将被留至下一代；

3）可选择的鸟巢数量是不变的，宿主发现外来鸟蛋的概率是Pa，其中0 ≤Pa≤ 1。

设表示第i个鸟巢在第t代的位置，L(λ)为随机搜索路径，则布谷鸟寻巢的位置更新公式为：

式中：α表示步长控制量，取α0=0.01；⊕表示点对点乘法；L(λ)表示 Lévy 飞行随机搜索路径，充分利用 Lévy飞行可有效避免局部极值的吸引。

Lévy 飞行随机搜索路径与时间t的关系服从概率密度函数 Lévy 分布：

CS 算法通过式（3）对鸟巢位置进行更新，并且计算目标函数的适应度值，若该值优于上一代目标函数值，则更新位置，否则不变。模拟布谷鸟鸟蛋被宿主发现并移开的思想机制，用随机产生的服从0～1 分布的随机数r与Pa比较，若r＞Pa，则对进行改变，反之不变，最后保留较好的一组鸟巢位置。判断算法是否满足最大迭代次数，若满足，迭代结束，输出全局最优值；否则，继续寻优。

2.2 CS 算法存在的问题

目前，CS 算法面临的一个主要问题是算法在后期求解函数问题时收敛速度偏慢、求解精度不高和易陷入局部最优解。在求解实际问题时，对于具体的特定问题和问题的不同阶段，对算法的全局探索和局部开发能力的要求也不同，因此，要求在收敛速度快的同时，平衡算法的全局与局部搜索能力，加强个体间信息的传递，能够在前期快速确定全局最优解的范围，后期精准收敛到全局最优解，摆脱局部最优解的束缚，将是提高算法适应性的关键。

通过分析以上标准DV⁃Hop 算法定位误差较大及CS 算法易陷入局部最优的问题，本文利用修正因子和虚拟交圆对跳数、跳距进行修正，并引入动态搜索步长优化CS 算法，提出一种跳数修正与自适应布谷鸟搜索的改进DV⁃Hop 定位算法。

3 本文算法

3.1 跳数跳距修正

3.1.1 跳数计数方式改进

在DV⁃Hop 算法中，跳数计数方式的不合理会引起较大的定位误差。如图1 所示，未知节点x，y都在信标节点A的通信半径内，在DV⁃Hop 算法进行定位过程中，未知节点x，y到A的距离都被记为一跳，而实际这两个距离存在一定的误差。

图1 通信范围内单跳误差

针对这一情况，本文引入理想跳数、节点偏差系数以及跳数差值修正系数，提出一种全局节点跳数修正的方法。对信标节点的跳数计数方式进行修正，当节点间的跳数hij＞2 时，利用理想跳数δij对信标节点间跳数hij进行修正，定义hij与通信半径R的比值为理想跳数δij：

比较信标节点间跳数hij与理想跳数δij之间的误差，定义εij为节点偏差系数：

εij越大，表明hij与δij之间的偏差越大。在通信半径R不变的情况下，估算跳数将大于或等于理想跳数，定义跳数差值修正系数为σij，以优化跳数信息，减少误差的累积：

信标节点间跳数计数公式修正为：

3.1.2 平均每跳距离修正

若DV⁃Hop 算法记录的未知节点的跳数值为1，则表明该节点位于信标节点的通信半径R区域内，在平均每跳距离估计时，这类节点的跳数被计算为1 个，而实际每跳距离却有很大的不同，这将给定位带来较大的误差。本文提出一种虚拟分区法计算信标节点间距离，如图2 所示。

图2 虚拟分区法计算距离

信标节点的通信半径是R，根据R3，2R3 将该信标节点的单跳通信区域划分为3 个互不相交的子区域，通信半径R中的节点以R3 为半径构造虚拟圆，m1,m2,m3,m4为通信半径内的未知节点，A为信标节点，以未知节点m1为例，m1的虚拟圆与3 个子区域的相交部分分别记为S11,S12,S13。假设节点到信标节点的距离已知，则可通过几何方法计算出相交面积的大小；反之，当相交面积已知时，节点到信标节点的距离也可计算得出。

假设节点到信标节点的距离为di，通过几何分析，各相交部分面积为：

假设n个节点不均匀分布，通信区域面积为S，3 个子区域内的节点总数分别为ni1,ni2,ni3，则可得出每个相交区域的面积分别如下：

面积估计法可求出未知节点到信标节点间的距离，采用非线性方程di=f(Si)计算节点间距离。分析的节点均在通信半径R内，因此此方法计算出来的节点间距离即为修正的单跳距离。

3.2 动态分组自适应CS 算法

传统的随机游动机制的布谷鸟搜索算法对优化性能有较大的影响，步长相对较大时，算法较容易地找到全局最优值，但搜索精度难以达到要求；反之，当步长较小时，搜索精度相对提高，但全局搜索能力相应降低。因此，本文提出一种改进的自适应动态调整步长的改进CS 策略，根据个体与种群的适应度值，将种群划分为3 个组，通过控制步长实现局部搜索与全局搜索的相对平衡。

设置种群数目为n，xk表示第k代个体，适应度值记为为平均适应度值，最好的适应度值记为fbest，当最优适应度值优于平均适应度值时，将最优适应度值记为，根据适应度函数值将种群划分为三种类型。

类型1：将适应度值优于的划分为第一组，其相应的步长控制调整方程为：

式中：αmin是预先设定的步长控制量的最小分量；αk,i表示第k次迭代的第i个个体对应的步长控制向量分量。

类型3：将适应度值低于的划分为第三组，其相应第k次迭代的第i个个体对应的步长控制为：

式中：h1,h2,Δ为控制参数当个体分布越分散时，Δ值越大，当个体分布越集中时，Δ值相应减小。

本文提出的改进自适应动态调整步长的布谷鸟搜索策略的适应度函数取为：

式中：f(x,y)为适应度值；n为信标节点数目；di为未知节点到信标节点的距离。

3.3 本文算法描述

本文算法将DV⁃Hop 定位问题用混合布谷鸟搜索最优距离的方法来解决：利用动态调整搜索步长策略将种群划分为三个类型，当最佳精度达不到设定值时，依次更改控制步骤，每次迭代更新后，用新的解决方案替代旧的解决方案，最后保持最优解。算法流程如下：

Step1：网络初始化。初始区域为M×M，信标节点数量为N1，未知节点数量为N2，通信半径为R。信标节点广播自己的信息{ID，(x,y)，hop}，其他节点接收信标节点信息。

Step2：节点进行跳数计算，信标节点计算平均每跳距离Hopsizei和平均每跳校正误差，利用面积估计法修正平均每跳距离Hopsizei。

Step3：生成适应度函数值f(x,y)并初始化CS种群。

Step4：计算目标函数值，并根据上述改进的CS 算法自动调整三类种群步长的控制。

Step5：更新适应度值，并保留较好的值。

Step6：判断当前迭代次数t是否大于最大迭代次数Tmax，若t＜Tmax，继续迭代；否则，输出最优值。

4 仿真结果与分析

为测试本文定位算法的性能，采用Matlab R2016b仿真平台对本文定位算法的性能进行测试，从通信半径、信标节点密度、节点总数三个方面对DV⁃Hop 算法、文献[12]的CS⁃D 算法和本文算法的性能进行仿真实验对比。采用归一化平均定位误差作为算法的评价标准：

式中：xi为节点的实际位置；n为测试区域节点总数为算法对未知节点的估计位置；R是通信半径。

图3 为在信标节点密度为20%时，不同通信半径下DV⁃Hop 算法、文献[12]的 CS⁃D 算法和本文算法的归一化平均定位误差比较情况，其中，总节点数目为100。

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

由图3 可以看出，通信半径由15 m 增至40 m 的过程中，三种算法的平均定位误差均呈下降趋势，表明节点通信半径越大，定位的精度越高。其中，DV⁃Hop 算法的整体平均定位误差最大，文献[12]的CS⁃D 算法次之，本文算法的平均定位误差最低。在通信半径增加至40 m时，实验得出 DV⁃Hop 与 CS⁃D 两种算法的平均定位误差为34%和27.2%，而本文算法低至19.3%，在相同通信半径下，本文算法误差低于 DV⁃Hop 算法与 CS⁃D 算法，定位性能更佳。

图4 为节点总数M=100，通信半径R=25 m 时DV⁃Hop 算法、文献[12]的 CS⁃D 算法和本文算法在不同的信标节点密度下的性能表现。由图4 可以看出，信标节点数目越多，三种算法的平均定位误差越低，表明信标节点越密集，定位信息越全面、定位精度越高。其中，当控制仿真区域内信标节点密度为10%时，三种算法的平均定位误差都有明显降低，在节点密度高于15%后，三种算法的定位性能趋于稳定，在信标节点密度不变的情况下，DV⁃Hop 算法的平均定位误差虽有下降趋势，但误差值整体较高，效果最差；CS⁃D 算法次之，本文算法的定位误差明显低于其他两种算法，定位精度最高，表现的性能最好。

图4 不同信标节点密度的平均定位误差

图5 为通信半径R=25 m，信标节点密度为10%时，DV⁃Hop 算法、CS⁃D 算法以及本文算法的平均定位误差比较情况。

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

由图 5 可以看出，DV⁃Hop 算法、文献[12]的 CS⁃D 算法和本文算法的平均定位误差均随着节点总数的增加而降低，其中，本文算法的误差下降趋势最明显，在节点总数高于200 后，本文算法的优越性更突出，在节点总数不变时，相比较 DV⁃Hop 算法和 CS⁃D 算法，本文算法的平均定位误差更低，定位性能最好。

5 结 论

本文提出一种融合跳数修正与自适应布谷鸟搜索优化的改进DV⁃Hop 定位算法，利用修正因子修正跳数误差，对单跳区域的子区域进行划分以修正跳距，并通过自适应动态调整步长的布谷鸟搜索测距对定位进行优化。为了测试验证本文改进策略的成效，在不同条件下对算法进行仿真测试比较。仿真结果显示，在硬件条件不变的情况下，本文定位算法的表现优于DV⁃Hop 算法和文献[12]的CS⁃D 算法，具有更高的节点定位精度。如何进一步提升算法的性能，是后期要重点研究的方向。