基于改进模拟退火的DV-Hop定位算法

惠海波，张玲华

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

无线传感器网络(wireless sensor networks，WSN)[1]是人们用来感知、采集、处理信息的重要工具，而节点定位技术[2]是其进行各种应用的基础。该技术主要包括两类：即基于测距(range-base)和非测距(range-free)技术[3-5]。

在非测距技术的定位算法中，DV-Hop算法因其成本低、开销小、实现相对简单等优点而广泛使用。但其定位精度不高，对此国内外的许多学者都提出了改进方法。比如，文献[6]是利用多通信半径来修正跳数，并加权处理未知节点平均跳距的改进算法。文献[7]在计算锚节点的平均跳距时引入了蛙跳算法，并用遗传算法求解未知节点坐标。文献[8]引入加权系数修正节点的平均跳距，并用模拟退火算法代替最小二乘法求解未知节点坐标。文献[9]在求解未知节点坐标时引入遗传模拟退火算法，该算法弥补了模拟退火算法全局搜索能力较差的缺陷，有效提高其定位精度，从而减小误差传播。然而，目前对模拟退火算法的改进方法大多需要设定和控制的参数较多，且各参数之间的相互作用也会影响算法结果，因此在应用上存在局限性。

因此，本文在基于模拟退火算法研究的基础上，针对DV-Hop算法存在的一些问题，提出了一种改进算法。该算法先使用多通信半径来修正最小跳数，再结合模拟退火算法的优势，并对其进行改进，用改进后的算法对锚节点的平均跳距进行优化，然后再使用加权因子处理未知节点的平均跳距，最后，采用加权最小二乘法来求解未知节点的坐标，利用解得冗余信息对未知节点坐标进行二次修正。由仿真结果可知，本文改进算法比传统DV-Hop算法具有更好的定位精度。

1 传统DV-Hop算法

1.1 计算过程

DV-Hop定位算法[10]是由美国Niculescu等提出的，一种基于距离矢量交换协议来获得跳数的算法。具体流程如下：

(1)计算锚节点与未知节点的最小跳数。锚节点通过泛洪方式[11]将自身数据包广播到整个网络中，数据包内含有锚节点的位置信息以及跳数值，未知节点接收到锚节点发出的包并更新自身跳数信息，将数据包的跳数值加1后并进行保存。为确保网络中所有节点都能获得每个锚节点的最小跳数(hui)信息，接收数据包的节点只需保留较小跳数值的数据包。

(2)估算锚节点与未知节点间的距离。每个锚节点收到其余锚节点坐标和最小跳数后，根据式(1)计算其平均跳距

(1)

式中： (xi，yi)， (xj，yj) 为锚节点i，j的坐标，hij表示为锚节点i，j之间的跳数，Hopsizei代表锚节点i平均跳距。未知节点u到锚节点i的估算距离dui为

dui=Hopsizei×hui

(2)

(3)估算未知节点位置。由式(2)求出估算距离dui，再结合最小二乘法来估算未知节点的位置。

1.2 误差分析

(1)传统的DV-Hop算法是通过最小跳数来衡量节点之间的距离，即在锚节点的通信半径范围内，无论未知节点距离锚节点多远，跳数都记为1跳。而未知节点与锚节点之间的跳数越多，则所求节点的平均跳距误差也越大，从而影响其定位精度。

(2)在计算锚节点的平均跳距时，传统DV-Hop算法利用实际总距离与总跳数的比值得到，即直线距离表示跳段距离，随着节点间跳数增加，得到的跳段距离误差也会增大。然后未知节点采用最近锚节点的平均跳距作为自身的平均跳距，也会导致较大的定位误差。

(3)估算未知节点的定位坐标通常采用最小二乘法，但该方法未考虑测量信息而直接使用，并且会产生残差影响定位精度，造成定位误差偏大。

因此，针对上述定位误差产生的原因，本文分别从节点的最小跳数、锚节点和未知节点的平均跳距、估算未知节点坐标等角度对DV-Hop算法进行改进。

2 改进的DV-Hop算法

2.1 多通信半径改进最小跳数

由DV-Hop定位算法计算跳数的方法可知，若两点间的欧式距离小于通信半径，则将其跳数当作1跳。若节点的分布状态如图1所示，则锚节点O分别到节点A、B、C、D的跳数都为1跳，但图中明显可以看出OA的距离小于OD的距离，因此，使用该方法计算节点间的最小跳数会产生误差，并在节点的定位过程中逐渐积累误差。

基于以上分析，本文采用4个通信半径的方式来细化跳数，从图1可以看出，未知节点A、B、C、D到锚节点O的跳数分别记为0.25、0.5、0.75、1，从而使得最小跳数的获取更加精确，平均跳距的计算也更加准确。

2.2 改进的模拟退火算法优化锚节点的平均跳距

2.2.1 改进的模拟退火算法

模拟退火算法[12](simulated annealing， SA)利用Metropolis抽样准则，在解空间中有一定概率寻找到目标函数的最优解。在重点抽样时，若新解更好，则接受；若更差，则以一定的概率接受。随着温度T逐渐趋于0时，则不再接受任何恶化解。同时该算法存在一些问题，即计算时间过长、初始温度难以确定,且没有记忆功能导致重复搜索。

模拟退火算法步骤：

(1)选取合适的目标函数。

(2)初始化参数：设置初始解状态X0、初试温度T0、迭代次数的初始值k=0。

(3)产生新解并计算其目标函数S2。然后计算增量Δ=S2-S1。

(4)根据Metropolis准则，若Δ<0，则接受当前新解为最优解；若Δ≥0，则以概率e-Δ/T接受新解为当前最优解

(3)

(5)若k小于终止次数，令k=k+1，然后转向(3)，否则转向(6)。

(6)若没有到达冷却状态，令T=T×α，α为降温系数，α∈(0,1)。 并转向(4)；当满足终止条件，则输出当前的最优解，算法结束。

捕食搜索算法定义请参见文献[13]，该算法搜索效率高，能够调节搜索区域的范围，可与模拟退火算法结合使用，即基于捕食搜索策略的模拟退火优化算法。

该算法主要从以下3个方面改进：

(1)初始温度改进

温度T在模拟退火算法中决定了退火走向。而T的初值大小与最优解的获取几率成正相关，同时，函数自身的复杂程度对T的初值也有较大的影响，因此，为使算法有更高的概率获取最优解，本文引用参考文献[14]的初值定义

T=T0×ln(1+ρ)

(4)

ρ=log10(f-g)+(m+n)

(5)

T0代表温度初始值；ρ代表函数的复杂程度；f、g分别为函数的最大值和最小值；m、n分别为函数的波峰数和波谷数。

(2)降温系数改进

降温系数决定了温度下降的快慢。为提高算法的搜索效率，需要使初期的退火速率保持较高的数值，并在退火后期保持下降平缓的特性。新的降温系数定义如下

(6)

α为降温系数，α∈(0,1)，j代表当前的迭代次数。从式(6)分析可知，若令h=α1/sqrt(j)， 则迭代次数j与h成正比关系，当迭代次数j逐渐增加，h的值也逐渐增大，但取值范围仍在(0,1)内，从而满足其在初期降温速度快，且在后期下降平缓的要求。

(3)增加记忆功能

由于传统的模拟退火算法在进行最优解搜索时，有一定的概率会接受当前较差的解而遗失最优解；并且对访问过的解还会重复搜索，造成运行时间增加，因此，本文引入禁忌搜索算法的禁忌表功能，将最优解存入禁忌表中，从而避免一些重复性的数值搜索。禁忌表中的元素被称为禁忌对象，禁忌长度是指被禁忌对象不能被选取的迭代次数。

在实际的操作过程中，给禁忌表中的被禁对象Y一个数t(禁忌长度)，即被禁对象Y在t步范围内被禁。该禁忌表可以用tabu(Y)=t来记忆，每进行一次迭代，即做运算tabu(Y)=t-1， 当tabu(Y)=0 时解禁。其中，禁忌长度的大小十分关键，若禁忌长度过小，很容易造成搜索循环，过早陷入局部最优，若禁忌长度过大，会造成计算时间过长，也会导致计算无法继续下去。因此，在本文的改进算法中，禁忌长度t被赋值为10。

2.2.2 优化锚节点的平均跳距

在传统的DV-Hop算法中，平均跳距的算法是基于无偏估计准则的。然而，一般情况下的误差服从高斯分布，由参数估计理论可知，使用均方误差准则[15]比无偏估计更加合理。因此，构造计算平均跳距的数学模型要基于最小均方误差准则，并且利用改进的模拟退火算法进行求解。

由于锚节点的位置信息已知，根据两点间的距离公式可求出锚节点i到j的实际距离为

(7)

而锚节点i与j之间的估计距离可由式(1)和式(2)可得，即d′ij=hij×Hopsizei， 再令δ=|dij-d′ij| 代表实际距离与估计距离之间的误差，当误差δ越小，代表估计距离越接近实际距离，即所求的Hopsizei越接近最优解，因此，要求解合适的自变量Hopsizei，则需要选择合适的目标函数来进行最小值问题的求解，该目标函数为

(8)

基于以上分析，在利用改进的模拟退火算法求解Hopsizei时，先在解空间 [0,max(dij)] 内随机产生初始解，并根据式(8)对所求解进行评价，然后再结合该改进算法的搜索策略来找出Hopsizei的最优解。求锚节点平均跳距的计算步骤如下：

步骤1 初始化各参数，在解空间 [0,max(dij)] 内随机产生初始解。

步骤2 在当前温度下，根据初始解的邻域随机取5个解，并且代入目标函数(8)中求其相应的目标值，按照升序排列并加入限制，即restriction[1-5]，初始解的目标值存放在restriction[0]，并设best=restriction[0]，将其放入禁忌表中。此外，设限制等级L=0，counter=0。

步骤3 若L

步骤4 在当前限制等级下产生邻域解，选择邻域最优解，并判断是否在禁忌表中出现过，若出现则重新产生邻域解；设Δ为当前值与目标值之差，根据Metropolis准则，若Δ<0，则接受当前新解为最优解；若Δ>0，则以概率e-Δ/T接受新解为当前最优解。接受转步骤5，不接受转步骤6。

步骤5 设限制等级L=0，counter=0，重新计算限制，并将新解加入禁忌表中，转步骤4。

步骤6 令counter=counter+1，如果counter>Cthreshold(用于增大限制等级L的指针阈值)，则转步骤7，跳出当前限制等级，否则，转步骤4。

步骤7 令L=L+1，counter=0，如果L=2，则令L=LhighThreshold(LhighThreshold表示较高的适应等级，该值设为4)，此时由邻域限制搜索转为广域搜索，同时转步骤3。

步骤8 随着温度降低，该过程会产生新的解，并把新解与禁忌表中的对象对比，若没有相同解，则转步骤2；若有相同解，则重新产生新解，若多次产生的解在禁忌表中都能找到，则代表已无最优解，结束当前循环，否则，转步骤2。

步骤9 重复步骤3～步骤8，直到收敛条件满足时结束。

步骤10 在禁忌表中寻找最优解，并输出最优跳距Hopsizei。

2.3 未知节点平均跳距的加权处理

在传统DV-Hop算法中，未知节点是把距离最近的锚节点的平均跳距值作为自身的平均跳距，但是在实际的网络中，节点分布在不同的区域其自身的状况也是不同的，且平均每跳距离也不相同，这明显会导致较大的误差，因为网络中单个锚节点的平均跳距并不能反映网络的真实属性。因此，可以采用多个锚节点来计算其平均跳距的方式，即引用加权系数来减小误差。加权系数公式如下

(9)

式中：n为未知节点可以通信的锚节点个数；hi为锚节点i与未知节点的最小跳数值。由此获取的未知节点的加权平均跳距为

(10)

通过对式(9)、式(10)的处理，每个与未知节点进行通信的锚节点，其平均跳距都可以参与未知节点平均跳距的计算，即每个锚节点的平均跳距都是按照与未知节点的距离远近来进行加权，从而使每个未知节点在依据平均跳距来计算其自身坐标时使之更加贴近真实的网络情况。

2.4 求解未知节点的坐标

如图2所示，假设未知节点U的坐标为(x，y)，锚节点A1、A2、…、An的坐标为 (x1，y1)， (x2，y2)， …， (xi，yi) (i=1，2，…，n)，di为锚节点Ai与未知节点U间估算的距离。

由两点间的距离公式可得方程组

(11)

由于di的获取本就存在误差，若再进行平方运算，会使其误差增大，使得定位精度下降。因此直接使用开平方的方式，从而避免因取平方造成的误差加大，然后再将上式的前(n-1)行全部减去最后一行，如方程组(12)所示

(12)

(13)

(14)

(15)

(16)

在求解未知节点坐标的过程中，每个参数的设置都采用了相同的权值，也就是说有一样的定位精度，若此时采用最小二乘法[16]直接计算未知节点坐标，所造成的误差会积累到最终的结果中。因此，本文采用加权最小二乘法来进一步减小定位误差，即引入权重矩阵W，该矩阵为对称的正定矩阵，如式(17)所示

(17)

其中，Wr,i表示未知节点r与锚节点i的权重因子，hr,i表示未知节点r到锚节点i的最小跳数。公式如下

(18)

最后结合普通最小二乘法可得

X=(ATWA)-1ATWB

(19)

2.5 修正未知节点的坐标

由式(19)解得未知节点坐标(x，y)和r后，则应该判断是否满足r=x2+y2， 若满足条件，该解即为所求坐标，若不满足该条件，则令

(20)

将式(20)带入r=x2+y2中，求出参数a，然后得出x1和y1的值，最后修正的未知节点坐标为

(21)

3 仿真实验与分析

3.1 仿真实验

为验证该改进算法的性能，在MATLAB2016b环境下进行仿真实验。先设置100m×100m的正方形区域，再将100个节点随机分布在该区域中。本文改进算法将与传统DV-Hop算法、文献[6]所提算法、文献[8]所提算法就锚节点数、通信半径两方面性能进行比较。

改进模拟退火算法的默认参数为：设定温度T的初始值为200，衰减因子设为0.96，限制等级为restriction[0]到restriction[5]，指针阈值Cthreshold设为1，为使算法更加稳定，每种算法循环运算50次并取平均值来当作最后的定位误差。假设总结点数为100个，锚节点数为10个，该节点的初始分布如图3所示。

定义平均定位误差[17]

(22)

3.2 锚节点个数对定位算法的影响

在图4中，DWDV-Hop为文献[6]的改进算法；SA+WDV-Hop为文献[8]的改进算法；SAPS+WDV-Hop为本文改进的DV-Hop算法。总节点数为100个，锚节点的通信半径为50 m，锚节点数从10个增长到50个(每次增长5个)。4种算法在相同条件下，随着锚节点数量的增加，相应的定位误差都在逐渐减小并趋于平缓，这是因为锚节点的增多使得定位节点的信息更详细，从而使得定位误差降低。由图4可知，在较低密度锚节点的网络中，本文所改进的DV-Hop算法明显优于传统DV-Hop算法，并且与文献[6]、文献[8]所提算法相比，其定位精度分别提升约7%和4%。

3.3 通信半径对定位算法的影响

在图5中，总节点数为100个，锚节点数为30个，随机分布在100m×100m的正方形区域中，并且通信半径从20 m增长到50 m(每次增长5 m)，其它条件保持不变。观察发现，随着通信半径R的逐渐增大，这4种算法的平均定位误差都在逐渐减小，但通信半径在大于40 m之后出现了一定程度的上升，经过分析可知，由于通信半径的增大会使网络连通性变好，所以定位误差一开始会降低，但当通信半径过大，会使平均跳距误差增大从而导致定位精度下降。由图5可知，本文算法的定位精度明显优于传统DV-Hop算法，并且与文献[6]所提算法相比，在定位精度上提升约8%，与文献[8]相比，定位精度提升约3%。

3.4 算法的复杂度分析

与传统DV-Hop算法相比，改进算法在运算量上增加了一些额外开销，该额外开销主要来源于在计算锚节点的平均跳距时，使用改进的模拟退火算法来优化锚节点的平均跳距，该改进算法继承了捕食搜索算法的区域精密搜索和广域搜索方式，增加了内外双循环运算，即每个限制等级下都要寻找最优解，此外，模拟退火算法本身随着温度下降产生的新解也要参与循环运算，直至满足收敛条件时结束，这些都在一定程度上导致运行时间增加。因此，改进算法是以一定的额外运算开销为代价取得更高的定位精度。

4 结束语

针对DV-Hop算法存在的误差，本文提出一种改进算法，先使用多通信半径来修正最小跳数，再引入改进的模拟退火算法计算锚节点的平均跳距，并使用加权因子处理未知节点的平均跳距，从而减小平均跳距引起的误差，最后在估算未知节点坐标采用不直接对方程进行平方运算的方式，并采用加权最小二乘法来求解未知节点的坐标，以及利用解得冗余信息对未知节点坐标进行二次修正。仿真实验证实，本文提出的改进算法在定位精度上有较大幅度的提升，并且具有良好的稳定性，但是，由于改进算法在锚节点计算平均跳距引入了改进的模拟退火算法，增加了一部分计算量，导致能耗增大。因此，下一步的研究将考虑在保持定位精度的条件下如何减少能耗。