Levy飞行策略结合三维灰狼优化的DV-hop定位算法

张 晶，郭一翰

1(昆明理工大学 信息工程与自动化学院，昆明 650500) 2(云南枭润科技服务有限公司，昆明 650500) 3(昆明理工大学 云南省人工智能重点实验室，昆明 650500) 4(昆明理工大学 云南省计算机技术应用重点实验室，昆明 650500)

1 引 言

无线传感器网络(Wireless Sensor Network，WSN)广泛应用于边缘计算[1]、森林防火、疾病预防等领域，在针对无线传感器网络节点的研究中，如何根据已知节点信息精确定位未知节点位置的研究已成为该领域的热点[2].

现有的定位算法依据需要测距与否的标准，将定位算法分为两种.第一种算法为测距式算法，一般是利用距离信息建立数学等式或是利用能量数据创建数学模型，通过测量所得到的数据信息的准确度就是关键信息所在.该算法虽然定位误差较低，但对嵌入式设备有一定的要求;另一种定位算法不需测距，且节约成本，耗能低，此外对所需嵌入式装备无过多要求，其代表为我们所熟知的传统DV-hop算法.DV-hop算法思想来源于贝尔曼-福特路由所改进的分布式定位方法[3]，该方法依赖不同节点之间的数据信息交互与协调，具有实现方法简单，定位误差低等特点，但是由于实际的无线传感器网络节点部署具有随机性，无法达到DV-hop算法的理想节点分布，导致在计算跳距以及跳数时不够精准[5]，并且在利用极大似然值估计算法估算待定节点位置时无法更加精确地提高未知节点的定位.

针对以上问题，文献[4]提出了一种距离修正结合灰狼算法对DV-Hop定位的改进算法，在经典DV-Hop算法的基础上，该算法引入灰狼算法优化节点间的跳数，为修正待定节点的实际与预测位置采用极大似然估计算法，但若单纯使用灰狼算法修正跳数，受到缩放因子和交叉概率的制约，不利于全局最优，且由于二维空间的局限性，会导致定位精度减弱.文献[5]提出了一种通过仅考虑最接近的锚节点来改进无线传感器网络中基于DV-Hop的定位算法，该算法为减少定位误差，仅根据最近锚节点信息来预测待定节点位置，但若锚节点与未知节点距离较远，会导致锚节点被忽略，也无法有效降低误差值.文献[6]提出了一种改进人工蜂群优化的DV-Hop定位算法，该优化算法在多边定位阶段使用改进的人工蜂群算法进行算法优化，在此文献中刘燕等在基本人工蜂群算法基础上引入数学优化模型，为该算法进行区域限定，以达到优化多边定位执行的目的，但该算法未考虑WSN节点部署不均，且受到二维空间限制，定位精度也会降低.

因此本文针对不同节点之间计算跳距、跳数不够精准及使用最小二乘法(Least sqaure method，LS)或极大似然值估计算法定位未知节点的精确度不高，而导致无法准确定位，误差较大的情况，提出一种Levy飞行策略结合三维灰狼优化的DV-hop 定位算法.该算法在计算平均跳距时，根据未知节点与信标节点之间的不同跳数引入权重因子，并且使用智能仿生三维灰狼算法，对每一个未知节点的位置进行仿生寻优计算，在加入灰狼算法的同时引入Levy飞行算法，提高灰狼算法的全局寻优能力，进而更好的提高算法精确度.

2 理论背景

2.1 传统DV-hop算法

传统DV-hop算法是利用贝尔曼-福特路由所引导出的定位算法，该算法的主要步骤主要分为3步：

1)信标节点(锚节点)通过传统的贝尔曼-福特路由交换协议向节点播送自己的信息数据，以此获得所有节点到每一个信标节点的最小跳数hopij以及位置信息.

2)每个信标节点利用其它锚节点的位置数据以及相隔的最小跳数hopij来求取平均跳距Ave_dis.如式(1)所示：

(1)

式(1)中，(xi，yi)、(xj，yj)分别是信标节点i，j在网络坐标的已知位置，求出平均跳距Ave_dis后将其作为勘误值播送到WSN中.

3)根据以上两步所获得的最小跳数hopij以及平均跳距Ave_dis使用最小二乘法(LS)或极大似然值估计算法求取待定位节点的位置[6].

设(xk，yk)表示一个未知节点K的位置，dki表示需定位节点K到信标节点ANi在空间上的估测距离，见公式(2)：

dki=Ave_disk×hopki

(2)

其中，hopki是K到ANi的最小跳数，Ave_disk表示K所保存的平均跳距.

根据信标节点的实际位置以及预估到未知节点的距离，可形成如公式(3)所示：

(3)

将方程组中的每一个方程等号两边开根号，所形成的新方程组转换成矩阵CX=D，其中C，D和X如式(4)所示：

(4)

通过LS获得该矩阵方程，可以确定未知节点K的预估位置：

X=(CTC)-1CTD

(5)

从以上算法的运行过程来看，计算的误差主要来自于最小跳数和平均跳距计算精度以及多个位置节点目标定位的优化.本文主要使用跳数加权对平均跳距进行改进以及使用飞行策略改进的三维狼群算法在多目标定位阶段增加定位精度.

3 改进的传统DV-hop算法

3.1 跳数加权改进

由文献[7]可知在实际中，无线传感器网络节点是不均匀分布的，这就导致平均跳距以及最小跳数计算的不准确性.为减少这一误差，本文在计算未知节点的Ave_dis时，根据未知节点K到其他信标节点的不同跳数引入权重因子，公式为：

(6)

式中，hopk表示是未知节点到各个信标节点的跳数，m代表所有信标节点个数，hopk越大，Wk的值就越小，因此，未知节点与信标节点跳数多的未知节点需要给予较小比重，跳数少的应当给予较大比重，改进后的平均跳距可以表示为：

(7)

3.2 灰狼算法

基本的灰狼算法(GWO)是由澳籍研究者Mirjalili等人[8]提出的一种仿生种群优化算法.其具有较强的收敛性能，所用参数较少，容易实现等特点，近年来成为定位算法的研究热点.

灰狼隶属于犬科群居动物，处于食物链顶层的他们严格遵守着社会等级支配关系，如图1所示.

图1 灰狼等级图Fig.1 Gray wolf hierarchy diagram

社会等级最高的灰狼称为α，α灰狼具有最高统治地位，对其他的狼具有绝对的支配能力，社会等级第2与第3的灰狼称为β狼和δ狼，社会等级最底层的狼称为ω狼，ω狼需要服从其他层次的狼，ω狼的作用是为了防止狼群内部的自相残杀.GWO的具体步骤如下：

1)社会阶级分层(Social Hierarchy)：在设计灰狼算法时，首先根据适应度函数，将适应度最好的3只狼分别标记为α狼、β狼和δ狼，剩下的灰狼则称为ω狼.GWO优化就是由迭代更新过程中最好的3个解α、β和δ来完成.

2)围困猎物(Encircling prey)：灰狼群在搜寻猎物时，会逐渐形成一个包围圈围困猎物目标，该行径数学模型如下：

(8)

式(8)中，t为此时的迭代次数；∘ 为哈达玛乘积操作；Xp为优化目标的位置；X(t)表示此时狼的定位向量；在迭代的开始到结束，a从2从线性降到0；r1和r2是0～1中的随机向量；A和B是协同的系数向量值；Dis表示灰狼之间的距离.

3)狩猎(Venery)：灰狼拥有分辨潜在目标定位的天赋，搜索过程中主要由α、β和δ3匹高阶灰狼来引领完成，但由于解空间特征的未知性，狼群确定不了最优目标的完美定位，所以为更好地模拟灰狼的捕猎行为，假定α、β和δ具有很好的区分目标定位天赋，所以在每次迭代时保留灰狼群中的等级高层狼α、β和δ，再根据他们的位置数据来更新其他ω狼的位置，该行为的数学模型如下：

(9)

式中Xα、Xβ、Xδ分别是灰狼群中的α、β和δ的方位向量；X代表灰狼的位置；Disα、Disβ、Disδ分别代表当前的灰狼与灰狼α、β和δ间的距离；当|A|>1时，灰狼群成员之间分散在各区域并搜寻目标；当|A|<1时，灰狼群成员将集中在某特定区域搜索猎物目标.

由图2可见，α、β和δ定义的随机圆位置内就是候选狼最终的位置所在.总而言之，ω灰狼在此时的α、β和δ3只高阶灰狼预测出猎物目标的大体方位之后，在猎物周围任意更新高阶灰狼的位置.

图2 狩猎时选狼ω移动方式图Fig.2 Diagram of choose wolf movement when hunting

4)攻击目标(Attacking target)：创建模型时，根据步骤2可知，a数值的降低也会改变A的值，A是[-a，a]区间的随机向量.当A在区间[-1，1]上时，则此时灰狼与目标之间的位置就是代理搜索的下一刻位置.

5)寻找猎物(Look for prey)：主要依靠α、β和δ3只高阶灰狼搜寻猎物，他们分散地去寻找猎物目标方位，然后集中攻击.在分散模型中，当|A|>1时使得代理搜索远离猎物，使得算法可以进行全局寻优.

GWO算法是一种模仿灰狼群体捕猎启发的一种新型仿生群体智能算法，具有收敛性能较高，且易于实现等特点，可用于WSN节点定位，降低算法误差，但与众多仿生算法一样，有着过早收敛，全局搜索能力较弱等问题，以至于所得到的最终解精度不高.

3.3 飞行策略改进灰狼算法

根据文献[9，10]可知灰狼算法存在过早收敛以及全局寻优能力不高的特性，因此为提高灰狼算法的全局寻优能力且丰富灰狼算法的种群多样性，本文利用Levy飞行算法的随机游走性能，将Levy飞行算法[11]融合到灰狼算法中，进行WSN未知节点的位置计算.算法改进如下：

在α狼、β狼、δ狼和ω狼在每次迭代更新位置时，使用Levy飞行公式(11)执行一次飞行优化，公式如下：

(10)

(11)

3.4 改进的灰狼算法修正未知节点位置

在经典DV-hop第3阶段，使用极大似然值估计算法确定待求节点方位，由于该方法的局限性不能有效提高计算精度，因此使用三维狼群算法对最后未知节点的位置进行改进，改进如下：

1)首先初始化α、β和δ3只高阶灰狼，使用Positions函数将灰狼算法中灰狼的位置维度改为3维，并且设定好最大迭代次数以及种群个数.

2)根据式(10)适应度函数得到所有灰狼的初步适应度值Fw，式中，(xw，yw，zw)为待定位节点位置，也就是狼群算法中猎物位置，(xg，yg，zg)为信标节点节点位置，dwg为待定位节点到信标节点节点的位置，选择最小适应值的3只狼分别将他们标记为α、β和δ.

(12)

3)灰狼群根据之前提到的式(8)和式(9)进行更新狼群位置信息X，如果α狼已达到最大迭代次数或者满足迭代循环结束条件，则停止循环，输出的α狼坐标信息即为未知节点最终改进位置.

4 算法仿真分析

4.1 仿真环境与参数设置

为验证改进后的DV-hop算法与之前传统的DV-hop算法相比定位更精确，分别将4种算法在Matlab2016a软件上进行仿真实验，通过4种算法对平均定位精确度数据Ave_er在不同的锚节点数，节点总数以及通讯半径的不同数据条件下变化趋势，判断本文算法有效性.

在边长为100的正方体三维立体空间中，任意投放400个WSN节点，如图3所示.

图3 三维节点随机分布图Fig.3 Three-dimensional random distribution of nodes

以全部未知节点的平均定位精确度数据作为实验对照图的纵坐标，以对比不同算法的精度，未知节点的平均定位精确度数据Ave_er计算见公式(13)：

(13)

式(13)中，xf′、yf′、zf′分别为未知节点f在三维坐标轴上的值，UNa是未知节点的个数.

4.2 实验仿真结果解析

实验环境与参数设定：在Matlab2016a软件[12]上进行实验，将节点通讯半径设为50，节点总数设为400，在不同的锚节点数量条件下，设定灰狼算法迭代次数为350次，狼群数量为100，Levy飞行策略中的α′设为1，统计原始DV-hop算法、三维加权DV-hop算法未使用飞行策略的灰狼算法以及本文算法的Ave_er，4种算法Ave_er随锚节点数量的增加而发生变化的情况，如图4所示.

图4 不同锚节点数各算法误差比较图Fig.4 Error of each algorithm varies with different anchor nodes

由图4可知，当锚节点个数为120时，本文改进的算法与原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.6342、0.2004、0.0222；当锚节点个数为180时，本文改进的算法与经典DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.6562、0.1741、0.0286；当锚节点个数为240时，本文改进的算法与经典DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.6675、0.1669、0.0176.

由此将实验环境与参数设定：在Matlab2016a软件上进行实验，将锚节点数设为160，节点总数设为400，在不同通讯半径条件下，设定灰狼算法迭代次数为350次，狼群数量为100，Levy飞行策略中的α′设为1，统计原始DV-hop算法、三维加权DV-hop算法未使用飞行策略的灰狼算法以及本文算法的Ave_er，4种算法Ave_er随锚节点数量的增加而发生变化的情况，如图5所示.

由图5可知，当通讯半径r为40时，本文改进的算法与原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.7187、0.1502、0.0756；当r为55时，本文算法与原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.6588、0.2016、0.0488；当r为70时，本文改进的算法与原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.4030、0.1388、0.0309.

图5 不同通讯半径各算法误差比较图Fig.5 Error comparison of different algorithms of different communication radius

由此将实验环境与参数设定：在Matlab2016a软件上进行实验，将锚节点数设为总结点数的40%，通讯半径设为50，在不同的节点总数条件下，设定灰狼算法迭代次数为350次，狼群数量为100，Levy飞行策略中的α′设为1，统计原始DV-hop算法、三维加权DV-hop算法未使用飞行策略的灰狼算法以及本文算法的Ave_er，4种算法Ave_er随节点总数量的增加而发生变化的情况，如图6所示.

由图6可知，当节点总数设为100时，本文改进的算法与经典DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.5684、0.1402、0.0533；当节点总数设为250时，本文改进的算法与原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.6580、0.1881、0.0478；当通讯半径为400时，本文改进的算法与原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，Ave_er分别降低了0.6973、0.1974、0.0203.

图6 不同节点总数各算法误差比较图Fig.6 Error comparison of the algorithms with different sum points

由实验结果表明，4种算法对平均定位精确度数据Ave_er在不同的锚节点数，节点总数以及通讯半径的不同数据条件下，本文算法的精确度明显优于原始DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法，并且在加入Levy飞行策略时相较未使用飞行策略的灰狼算法，定位误差又降低了5%左右，相对于经典DV-hop算法、三维加权DV-hop算法以及未使用飞行策略的灰狼算法相比，降低的未知节点定位误差区间分别为40%～69%、13%～20%、1.7%～7.6%，表明了本文算法的精确性.

5 总 结

本文针对WSN DV-hop[13]定位算法的待定位节点定位精度不高的情况，提出一种Levy飞行策略结合三维灰狼优化的DV-hop定位算法.算法仿真实验结果表明Levy飞行策略[14]平衡了灰狼算法的全局与局部搜索能力，与原灰狼算法相比，本文算法提高了灰狼算法的全局搜索性能，规避该算法收敛过早的弊端，此外根据待定位节点与信标节点之间的不同跳数引入权重因子，避免待定位节点直接使用信标点的平均跳距，在相同的自变量计量下定位精度也有显著提高.此外，由于每次仿真实验的节点分布不同，会出现极少数未使用Levy飞行策略的原始狼群算法优于本文算法，如何区分辨别这一小部分节点以获得精确度更高的定位策略是今后的研究工作.