基于距离修正及灰狼优化算法对DV-Hop定位的改进∗

石琴琴，徐 强，张建平

(1.上海应用技术大学计算机科学与信息工程学院，上海201418；2.苏州中科先进技术研究院有限公司，江苏苏州215123；3.华车科技股份有限公司，上海200127)

DV-Hop[1]是广泛应用于无线传感器网络节点自定位的一种非基于直接测距的定位方法。无线传感器网络在物联网应用的信息采集环节发挥着重要作用，而能量高效和节点可定位则是提供有效数据信息的前提和基础。无需配备专门设备进行测距的定位方案因其经济且高效的定位模式，成为当前的研究热点。DV-Hop是一种开创性的定位方法，基于一定比例锚节点的已知位置信息与距离矢量路由传递实现网络内未知节点的定位，具备了无需测距定位方案的所有优点[2]。网络中的锚节点根据基站发出的定位需求指令或者既定的时间间隔发起消息传递，其余节点根据多跳路由协议获得距离锚节点的最小跳数。未知节点与锚节点之间的距离通过由最近锚节点提供的平均每跳距离校正值和上述最小跳数相乘获得，而后采用Lateration算法计算获得未知节点的坐标。根据传统DV-Hop方法的算法原理，最终的节点定位精度主要取决于节点密度、锚节点数量和网络拓扑，因为这些因素都直接影响着未知节点与锚节点之间距离估计值的精度。当网络具有较高的锚节点比例，节点布设密集均匀，网络拓扑基本趋于各向同性时，网络处于一种较为理想的状态，距离估计值较合理，定位精度较可靠。但是，实际应用中的网络环境往往会因为区域地形或者布设方法局限等原因，使得网络拓扑极难达到传统DVHop方法所需的理想状态，故而导致算法的适用性较差，定位精度难以保证，实际可行性受限[3-4]。

尽管经典DV-Hop方法存在应用层面的缺点，但因其开创性的无需直接测距的定位思路提供了一种良好的模型设计方向，使得相关的改进策略研究广泛开展。在保持DV-Hop算法优点的前提下，如何高效利用锚节点资源，提高距离估计精度，进而改善最终的定位精度是值得深究的问题。在国内外文献汇总的基础上，可将DV-Hop模型实现节点定位的步骤归纳为两步:距离估计与位置计算，并根据这一线索对现有改进方法进行分类，大致可分为三类:第一类只针对距离估计步骤进行改进，如文献[5-7]所述；第二类只针对位置计算步骤进行改进，如文献[8-10]所述；第三类对两个步骤都有改进，如文献[11-13]所述。在第一类的改进中，现有的改进方法企图通过算法找到一个未知节点到全网所有锚节点都适合的平均每跳距离，这一思路不适用于各向异性的网络，只有对锚节点比例、节点布设密度等相关参数进行可行性限定后才能达到提高定位精度的效果；第二类改进，假设了所获得的未知节点至锚节点距离的精确性，以距离为约束条件搜索未知节点的最优坐标值，在理论上可取得优于经典DVHop方法的定位精度，但脱离了距离不可能精确测量的实际；第三类改进方法在思路上较之前面两类更为合理，在特定的实验环境下都取得了较好的定位精度，为本文提供了良好的思路借鉴，但在针对距离修正的改进中仍然存在第一类改进的问题，仿真实验评价了优化所得的定位精度，未对距离估计阶段是否真正提高了距离精度进行定量分析。

本文提出的改进策略主要贡献在于:①针对未知节点与锚节点之间的距离估计，采用在所有锚节点对的多跳路径中选出与目标锚节点到此未知节点的多跳路径最相似的一条，独立确定未知节点与目标锚节点间的平均跳距值，以期使得估计距离尽可能接近真实距离；②在使用传统DV-Hop方法获得节点位置坐标后，将参与定位计算的距离与未知节点坐标同时作为待求未知数，进一步采用改进的灰狼算法[14]优化位置坐标，以期获得提高节点定位精度的效果。

1 DV-Hop方法既有改进策略分析

分析经典DV-Hop方法的定位原理可知，计算未知节点与锚节点间距离的必要参数是平均每跳距离估值与最短路径跳数。每一锚节点对应一个平均每跳距离估值，是通过网内其余锚节点到该锚节点间的距离和除以跳数和得到的，再转发临近的未知节点，据此计算未知节点与目标锚节点之间的距离。如果网络节点分布不均匀，则采用该方法获得的平均每跳距离估值不能合理代表未知节点与目标锚节点间的平均跳距，因此导致未知节点与锚节点之间的距离估值存在较大误差，进而，定位算法Lateration对距离估计误差极为敏感[15]，最终使得未知节点的坐标不能被精确估计。而无线传感器网络的室外应用场景一般为人员难以到达区域，节点通常采用随机播撒或弹射等非均匀布设的方式，网络拓扑极易呈现各向异性，降低了经典DV-Hop方法在应用层面的可行性。

针对上述DV-Hop方法的不足之处，文献[5]提出的改进算法引入多通信半径策略细化锚节点间的跳数，而后依照式(1)获得每个锚节点的平均每跳距离估值；针对每一未知节点，通过剔除孤立节点，并对获得的锚节点平均跳距值进行加权平均作为未知节点到全网锚节点的平均跳距；这一改进方法获得了一个理论上到全网锚节点都为最优的平均每跳距离值，适用于各向同性网络，不符合实际应用中各向异性网络的特点，且多通信半径发射信号会增加网络能耗。文献[6]引入人工蜂群算法来搜索一个适用于全网的平均每跳距离值，定位阶段仍沿用经典DV-Hop中的Lateration算法，未能从本质上描述出当网络拓朴各向异性时，不同多跳路径平均每跳距离估值应存在的差异，且无法有效地规避人工蜂群算法陷入局部优化而导致的估计偏差。文献[7]提出了一种改进的无偏距离估计与节点定位算法，分析期望距离和跳数的关系，建立了一种新的期望距离与跳数关系模型，根据节点通信半径是否已知分别推导了两种未知节点与锚节点间距离的求解形式，较之原DV-Hop算法提高了距离估计与定位的精度，但距离估计模型的建立是基于网络各向同性的假设，对网络布设有条件限制。文献[8-10]对原DV-Hop方法的距离估计算法未做修正，在得出未知节点的初始坐标后，分别使用非线性共轭梯度法、Steffensen算法以及遗传算法进行迭代优化；这些算法都可在文献设定条件下提高未知节点的定位精度，但回避了对距离估计的误差修正，则不能从根本上保证计算条件的合理性，不符合实际应用场景。文献[11]针对每个未知节点，对设定跳数阈值内的锚节点的平均每跳距离估值根据相距跳数进行加权平均，以此确定每个未知节点对应的平均每跳距离估值；完成初步定位计算后，利用未知节点位置信息反推锚节点的位置，并计算所有锚节点位置误差的加权平均值来反向修正未知节点位置。文献[12]提出一种基于误差距离加权与跳段算法选择的遗传优化DV-Hop定位算法，改进算法包括3个改进点:①首先基于误差与距离生成每个锚节点对应平均每跳距离的权值，而后加权平均确定未知节点的平均每跳距离估值；②根据位置关系是否最近选择相应的跳段距离计算方法来确定未知节点与锚节点间的跳段距离；③用改进的遗传算法优化未知节点坐标来确定未知节点坐标的最优解。仿真结果表明，改进定位算法的性能明显优于原DV-Hop定位算法，达到了提高定位精度的目的。文献[13]中提出一种基于蝙蝠算法的改进方案，在距离估计阶段首先求得所有锚节点对之间的距离误差均值作为一个修正参数，并将未知节点到锚节点的跳数取倒数并归一化，取作权值，而后使用所有锚节点保存的平均跳距加权求和作为未知节点对应的平均跳距，以此修正距离估计值；在定位阶段，使用改进了适应度函数、搜索速度以及迭代规则的蝙蝠算法对定位结果进行迭代优化。文献[11]、[12]、[13]算法的共同缺点是在距离估计阶段仍然通过数学方法计算未知节点到全网锚节点适用的平均跳距，需要限定网络拓扑；在位置计算阶段以距离为约束条件搜索节点的最优位置，假设了距离估计值的精确性。

2 本文改进策略

针对原DV-Hop方法在距离估计与位置计算步骤中所采用的算法存在的不足，本文进行了如下的改进:①修正平均每跳距离估计策略，提出一种相似路径搜索算法，为每一未知节点与目标锚节点之间的多跳路径计算出最匹配平均每跳距离估计值，以期提高距离估计精度；②引入改进的灰狼群体智能算法对未知节点的初始位置进行优化，以期进一步提高定位精度。

2.1 相似路径搜索算法

在距离估计阶段，为未知节点到目标锚节点之间的多跳路径匹配最相似的锚节点对之间的多跳路径，由该最相似路径计算出一个平均每跳距离值，作为未知节点到目标锚节点之间最优的平均每跳距离估值，进而乘以最短路径跳数即可估计出未知节点到目标锚节点之间距离。详细的算法步骤描述如下:

首先，将锚节点至全网节点的多跳最短路径信息记录为节点编号组成的集合，针对每一未知节点，其相距某个目标锚节点的最短路径集合和其他锚节点对间的最短路径集合进行相似度比较运算，选出相似度最高的锚节点对间路径计算平均每跳距离值，并作为未知节点至目标锚节点的平均每跳距离估值，进而与最小跳数值相乘获得距离估计值。算法中使用Ochiai系数[16]来衡量路径集合间的相似度，Ochiai系数的定义如式(1)所示:

此处A和B是集合，n()表示集合包含的元素个数。

上述算法的具体步骤①～⑤如下:

①记录未知节点至某一目标锚节点的最短路径节点编号集合A；

②分别记录其余锚节点至该目标锚节点的最短路径节点编号集合B；

③分别计算集合A与集合B的Ochiai系数值；

④将Ochiai系数值最大的锚节点对间的平均每跳距离值作为未知节点至该目标锚节点的平均每跳距离估值；

⑤将步骤④获得的平均每跳距离估值与多跳最短路径跳数相乘计算出未知节点到该目标锚节点的距离估计值。

以图1所示拓朴关系为例对上述步骤进行说明。 图 1 中 a1，a2，a3，a4，a5，a6为锚节点，其余为未知节点。当估计未知节点u1到锚节点a6的距离时，首先，记录未知节点u1到信标节点a6的最短路径节点编号集合，其结果为:{u1，a2，u3，u6，u7，a6}；再记录其余锚节点到锚节点a6的最短路径节点编号集合，其结果如下:

第一路径:{a1，u2，u3，u6，u7，a6}；

第二路径:{a2，u3，u6，u7，a6}；

第三路径:{a3，u4，u3，u6，u7，a6}；

第四路径:{a4，u5，u4，u3，u6，u7，a6}；

第五路径:{a5，u6，u7，a6}。

根据上文对集合相似度Ochiai系数的描述可计算出u1至a6路径集合与各条锚节点对间路径集合的相似度值为:与第一路径集合的相似度为0.667；与第二路径集合的相似度为0.913；与第三路径集合的相似度为0.667；与第四路径集合的相似度为0.617；与第五路径集合的相似度为0.612。故采用第二路径a2到a6间的平均每跳距离值来近似u1到a6间的平均每跳距离值，再乘以u1到a6的最小跳数获得距离估计值。以此类推，可获得所有未知节点到所有锚节点的距离估计值。

图1 相似路径搜索算法说明图

2.2 改进的灰狼优化算法

灰狼优化算法是一种群体智能优化算法，具有结构简单、易于实现等特点，可用于无法直接使用数学方法求解的复杂问题的求解[17]。经典DV-Hop方法在估计出未知节点到3个以上锚节点的距离后，使用Lateration算法完成定位计算。本文策略在位置计算阶段，首先沿用Lateration算法获得未知节点的初始定位值，且选择在距离估计阶段路径相似度参数值最大的4个锚节点参加定位计算；而后列出式(2)所示的非线性方程组，使用改进的灰狼算法迭代求方程组最优解。

文献[14]提出并分析了灰狼算法，该算法模拟自然界中灰狼的等级制度与狩猎行为，其算法思想为:灰狼是一种群居的顶级掠食者，整个狼群分为四组:α、β、δ、ω，按照等级由高到低排列，前三组引导最低级狼(ω)进行目标搜索；在搜索过程中，狼群依照一定的规律更新α、β、δ、ω的位置，最终输出的α狼的位置信息即为目标位置。

灰狼算法在本文中用于对未知节点初始位置进行优化，详细步骤如下:

①初始化狼群个体，将未知节点的坐标、未知节点与4个信标节点之间的距离组成未知数向量，即灰狼个体，可表示为一个 6 维向量[x，y，d1，d2，d3，d4]；每个灰狼个体的分量初始值都设置为既有的距离估计值与未知节点初始坐标值；设定最大迭代次数 max＝300。

②根据式(3)中所列适应度函数公式初始化所有灰狼个体的适应度值，式中，fitnessi为灰狼个体i的适应度值，(xi，yi)为 i的平面位置坐标，(xj，yj)为锚节点j的位置坐标，dj为未知节点到锚节点j的估计距离；选择适应度函数值最小的3个灰狼个体，依次将它们记为 α、β、δ。

③如果α狼的向量变化已满足迭代退出条件，或者已达既定迭代次数上限，则算法结束，输出α狼的坐标信息，即为最终未知节点位置优化结果；否则，进入下一步骤。

④依次根据式(4)～式(7)更新ω狼的当前位置信息Xω(t)。其中，C为摇摆因子；A为收敛因子；a为控制因子，其值随着迭代次数从2到0线性递减；r1和r2均为[0，1]区间的随机数；t是当前迭代次数，X(t)表示迭代t次时灰狼个体位置；max是设定的最大迭代次数。

⑤根据式(3)计算所有灰狼个体的适应度值，选出新的 α、β、δ，回到步骤③。

迭代计算完成后所得解向量中的x，y元素值即为最终求得的未知节点坐标优化值。

文献[18]也阐述了一种灰狼算法在无线传感器网络未知节点位置优化中的应用，相对而言，本文应用在灰狼个体的维度表示与迭代计算过程方面进行了改进。既有应用的灰狼个体表示为仅包含未知节点坐标的二维行向量[x，y]，而本文的灰狼改进算法将未知节点至锚节点之间的距离与未知节点坐标一起看作非线性方程组的未知数，同步迭代优化，因为选择具有最高路径相似度的4个锚节点参加定位计算，故而灰狼个体表示为 6 维行向量[x，y，d1，d2，d3，d4]。这一改进基于DV-Hop距离估值为非精确值的考量，忽略距离估值的误差而将其作为方程组常量会导致误差的持续传播，故而本文在灰狼优化步骤中将其作为具有合理初值的未知数进一步优化。

3 仿真实验

使用MATLAB软件编程进行算法实验，通过对比本文算法与经典DV-Hop算法及文献[13]中所述DV-Hop改进算法(下文简称IBDV-Hop)在距离估计精度、定位精度、计算量等评价指标方面的表现，证明其可行性与优越性。

3.1 实验环境

网络布设区域为100 m×100 m的二维平面，所有传感器节点具有相同结构及通信半径，节点随机布设，自组成网。网内未知节点个数为N，网内锚节点个数为M，节点通信半径为R，dij、＾dij分别表示节点间真实距离与估计距离，Pj、＾Pj分别表示未知节点的真实位置与估计位置，式(8)所示为归一化的网络距离估计精度，式(9)所示为归一化的定位精度。

分别变换节点总数、锚节点比例和通信半径参数值的设置来模拟不同的网络拓朴结构，分析这些参数变化对距离估计及定位的影响规律，具体可组合为三类实验场景:场景一固定节点总数为100，通信半径为15 m，锚节点比例从5%渐次提高到30%；场景二固定通信半径为15 m，锚节点比例为15%，节点总数改从100渐次提高到225；场景三固定节点总数为100，锚节点比例为15%，通信半径从15 m提高到35 m。

3.2 实验结果与分析

在3.1节所述三种实验场景中，根据距离估计步骤统计的距离精度与位置计算步骤统计的定位精度对算法进行对比分析；另外，还将对比分析迭代次数与定位误差的关系以及优化算法种群数量与定位误差的关系；最后，通过平均时耗定量对比算法的复杂度。

3.2.1 距离估计精度

图2～图4分别对比了锚节点比例、节点总数及通信半径参数变化条件下三种算法的测距精度表现。结果显示:随着锚节点比例的提高，本文算法较之原DV-Hop测距精度可提高约67%，较之IBDVHop测距精度可提高约35%；随着网络节点布设密度的增大，分别可提高约66%和33%；随着通信半径的增大，分别可提高约64%和38%。在各类场景下，本文算法的测距精度整体表现较高且稳定。

图2 测距误差vs.锚节点比例

图3 测距误差vs.节点总数

图4 测距误差通信半径

3.2.2 定位精度

图5～图7分别对比了锚节点比例、节点总数及通信半径参数变化条件下三种算法的定位精度表现。结果显示:随着锚节点比例的提高，本文算法较之原DV-Hop方法定位精度可提高约46%，较之IBDV-Hop定位精度可提高约15%；随着网络节点布设密度的增大，分别可提高约37%和19%；随着通信半径的增大，分别可提高约45%和20%。在各类场景下，本文算法的定位精度整体表现较高且稳定。

图5 定位误差vs.锚节点比例

图6 定位误差vs.节点总数

图7 定位误差vs.通信半径

图8 定位误差vs.种群数量

3.2.3 种群数量与迭代次

节点总数设为100，锚节点的比例设为15%，通信半径设为15 m。在此场景下，本文算法与IBDVHop算法就种群数量对定位精度影响的对比如图8所示，结果表明:随着种群数量的增加定位误差不断降低，IBDV-Hop算法在种群数量达到100之后定位误差即无明显降低，而本文算法在种群数量达到60之后定位误差无明显降低，本文算法相比IBDV-Hop算法在优化定位阶段的时耗更低。本文算法与IBDV-Hop算法就迭代次数对定位精度影响的对比如图9所示，结果表明:随着迭代次数的增加定位误差不断降低，IBDV-Hop算法在迭代次数达到160之后定位误差即无明显降低，而本文算法在迭代次数达到120之后定位误差无明显降低，本文算法相比IBDV-Hop算法在优化定位阶段的收敛速度更快。

图9 定位误差vs.迭代次数

3.2.4 时耗

表1比较了本文算法、经典DV-Hop算法以及IBDV-Hop算法的计算量，用以秒为单位的时耗值统计，由所有模拟场景下的时耗平均值获得。结果显示:本文算法时耗约为相原DV-Hop算法的1.7倍，约为IBDV-Hop算法的1.3倍。在当前高性能数据处理平台的支持下，本文算法小幅增加的时耗可忽略不计，但可观地提高了定位精度。

表1 算法时耗对比

4 结束语

以应用于无线传感器网络节点定位的经典DVHop方法为研究对象，提出了一种基于距离修正及灰狼优化算法的改进策略。距离修正采用一种相似路径搜索算法，实现了未知节点与目标锚节点之间平均每跳距离计算的局部化，改进了原方法使用所有锚节点参与校正值计算存在的全局平均问题；灰狼优化算法起到了进一步校正未知节点初始位置，提高Lateration算法定位精度的作用。仿真实验表明，本文策略较好地解决了原DV-Hop方法在各向异性网络拓朴条件下的适用性问题，极大地提高了原方法的定位精度，并且性能优于文献[13]中提出的典型改进算法。

在后续研究中将进一步深入研究以下问题:①锚节点位置对网络拓朴的控制规律；②其他群体智能算法在节点位置优化中的应用改进；③更真实的应用场景模拟策略。