基于改进海洋捕食者算法的WSNs 定位

程忙忙，杨靖，2

（1 贵州大学 电气工程学院，贵阳 550025；2 贵州省互联网+协同智能制造重点实验室，贵阳 550025）

0 引言

DV-Hop 作为一种无测距定位算法，由于算法简单、覆盖率高、可行性好，将节点之间的估计距离转换为跳数值和每跳平均距离的乘积［1-3］，已成为一种经济、且至关重要的定位算法。算法包括3 个步骤：

（1）利用广播使网络中的所有节点获得其到锚节点的最小跳数。

（2）计算所有锚节点每一跳的平均距离，并通过将每跳的平均距离与最小跳数值相乘来获得估计距离。

（3）利用与未知节点距离最近的3 个及以上的锚节点和彼此间的估计距离，使用最小二乘法来计算未知节点的位置，但最小二乘法容易陷入局部最优。

然而，对于某些应用场景，DV-hop 定位法的定位精度不够精确，改善其定位精度是研究的关键问题。Singh 等人［4］应用了一种改进的定位算法，使用粒子群优化算法来优化结果。Gumida 等人［5］提出了一种基于混合混沌策略的改进定位算法。Harikrishnan 等人［6］使用差分进化算法来最小化无线传感器网络中的定位误差。文献［7］提出一种改进的人工免疫算法（AIA）优化DV-Hop 未知节点坐标。Cui 等人［8］通过相邻节点之间的公共单跳节点的值改进了跳数的值，并将离散的跳数值转换成更精确的连续值。

本文中提出了一种基于改进海洋捕食者算法［9-10］（MPA）的DV-Hop 定位算法。利用改进的海洋捕食者算法较好的寻优能力，替代DV-Hop 算法中的最大似然估计法，在不增加网络通讯量和硬件的情况下有效降低节点定位误差，对此流程可重点表述为：首先，通过泛洪的方式，获得节点间通讯的最小跳数；其次，通过锚点之间的距离，计算出平均每跳的估计距离，进而计算出未知节点到锚点之间的估计距离；最后，构建目标函数，利用改进海洋捕食者算法来搜索出节点的位置。

1 MPA 算法改进及性能分析

1.1 海洋捕食者算法

（1）初始化：首先初始化算法种群X。对此可表示为：

其中，Xmax和Xmin分别表示搜索区域的上、下边界，rand表示［0，1］之间的随机数。

（2）迭代优化：考虑猎物与捕食者不同的速度比，同时模拟捕食者和被捕食者的整个生命，MPA 优化过程分为3 个主要阶段，对此拟做研究分述如下。

①阶段1：在高速比下，猎物比捕食者移动得快。由于猎物比捕食者移动得快，捕食者的最佳运动策略是Brown 运动，因此当Iter ＜时（这里的Iter表示当前迭代次数，Max_Iter表示最大迭代次数），研究给出的运动数学模型如下；

其中，RB是一个基于非正态分布的随机数向量，代表Brown 运动；“ ⊗”表示逐级乘法，RB与猎物的乘积模拟了猎物的运动；P是一个常数，P＝0.5；R是［0，1］中的均匀随机数向量。

③《中华人民共和国侵权责任法》第五十八条患者有损害，因下列情形之一的，推定医疗机构有过错：（一）违反法律、行政法规、规章以及其他有关诊疗规范的规定。

②阶段2：在单位速度比中，捕食者和猎物以几乎相同的速度移动。由于捕食者和猎物以相同的速度移动，捕食者的运动策略是Brown 与Levy 策略。因此，在这个阶段一半的种群在做Brown 运动，一半的种群在做Levy 运动。故当时，对于前一半的群体来说，建立数学模型如下：

其中，RL是一个基于Levy 分布的随机数向量，代表Levy 运动。RL与Prey的乘积模拟Levy 方式下的动物运动，并添加步长到猎物的位置模拟猎物的运动。对于种群的后一半，推得的数学公式可写为：

其中，CF表示控制捕食者移动步长的自适应参数。RB和Elite的乘积模拟了布朗运动中捕食者的运动，而猎物则根据布朗运动中捕食者的运动来更新自己的位置。

其中，RL和Elite的乘法模拟了Levy 策略中捕食者的移动，在Elite位置中加入步长模拟了捕食者的移动，帮助更新猎物的位置。

通过3 个阶段的优化，捕食者得到了最佳的位置。海洋中还有许多不可控因素干扰捕食者的运动，例如人工投放的装置、涡流等，因此还要考虑这些因素的影响，故建立数学模型如下：

其中，FADs＝0.2是FADs对优化过程的影响概率；U是包含0 和1 的二进制向量，是通过在［0，1］中生成一个随机向量来构造的，如果数组小于0.2，则将其数组更改为0，如果数组大于0.2，则将其数组更改为1；r是［0，1］中的均匀随机数；Xmin和Xmax是包含维数上界和下界的向量；r1和r2 表示猎物矩阵的随机指标。

1.2 改进海洋捕食者算法（IMPA）

（1）原MPA 算法采用的是随机方式生成算法初始种群，rand函数是一种伪混沌的随机方式，产生的初始种群多样性低，因此引入Tent 混沌映射［11］初始化算法初始种群，提高算法的多样性。Tent 混沌映射的数学公式见如下：

其中，Tent 映射的混沌区间为（0，1）。

Tent 混沌映射初始化种群如式（8）所示：

（2）引入柯西变异［12］和反向学习策略［13］对算法更新后位置进行随机扰动，当随机数rand ＞0.5时，用柯西变异进行扰动，否则采用反向学习策略扰动个体位置，这样可以产生更多的解，有效地提高算法的多样性。数学公式具体如下：

1.3 算法仿真分析

为体现出改进算法的性能，在23 个测试函数中分别选择了3 个50 维单峰函数和3 个50 维多峰函数进行仿真。3 个单峰函数分别是：F1（Sphere）、F2（Schwefel）、F6（Quartic）测试函数，3 个多峰函数分别是F9（Sum Square）、F10（Rosenbrock）、F11（Zakharov）测试函数。并与原MPA、差分进化算法（DE）和粒子群优化算法［14］（PSO）做了对比，结果如图1 所示。

图1 改进算法与其他算法寻优效果对比Fig.1 Comparison of the optimization effect between the improved algorithm and other algorithms

由图1 可以看出，无论是在单峰测试函数、还是多峰测试函数上，改进算法的寻优速度和寻优能力均高于原算法、差分进化算法和粒子群优化算法，说明了本文改进算法的优越性。

2 基于IMPA-DV-Hop 的定位算法

IMPA 算法拥有很好的优化性能，因此将IMPA引入DV-Hop 定位算法中，取代原始算法中最大似然估计部分，得到IMPA-DV-Hop 定位算法。算法步骤如下。

步骤1泛洪。通过泛洪过程得到节点间的最小跳数，尤其是未知节点到锚节点的最小跳数和锚节点间的最小跳数，为下一步计算做准备。

步骤2通过锚点之间的距离计算出平均每跳的距离，并利用最小跳数计算未知节点u到锚节点i的估计距离du，i。

步骤3利用IMPA 来寻找适应度函数的最优解，即：

其中，（xu，yu）表示第u个未知节点的估计位置；（xi，yi）表示第i个锚节点的坐标；du，j表示未知节点u与锚节点j之间的估计距离；m表示锚节点的数量。

至此，运算得到所有未知节点的估计位置。

3 仿真结果及分析

在1 000∗1 000 m2的区域内，随机部署和均匀部署1 000个节点，其中锚节点200个，未知节点800个。分别利用原始DV-Hop 算法、基于粒子群的DV-Hop 算法（PSODV-Hop）以及本文提出的IMPA-DV-Hop算法进行节点定位并进行对比，群体智能算法的参数设置见表1。

节点分布如图2 所示。图2中，蓝色圆圈为未知节点，红色“∗”为锚节点的位置。分别采用原始的DV-Hop 算法、基于粒子群的DV-Hop 算法（PSODVHop）以及MPA-DV-Hop 算法对未知节点进行定位，得到定位误差图如图3 所示。

图2 节点分布图Fig.2 Distribution map of nodes

图3中，蓝色短线表示未知节点的估计位置到真实未知的连线，连线越短，定位误差越小，精度越高。

图3（a）～（c）表示随机部署情况下分别采用DV-Hop、PSODV-Hop 和MPA-DV-Hop 定位算法进行定位的定位误差图，图3（d）～（f）表示均匀部署情况下分别采用DV-Hop、PSODV-Hop 和MPADV-Hop定位算法进行定位的定位误差图。通过对比，可以直观地看到DV-Hop 算法的定位误差最大，PSODV-Hop 将未知节点估计到了搜索区域外，效果也比较差，MPA-DV-Hop 的定位效果最好。为了克服偶然因素的影响，对每个算法运行30次，求定位误差的平均值见表2。

图3 定位误差图Fig.1 Distribution map of positioning error

表2 定位误差对比表Tab.2 Comparison of positioning error table

从表2 可以得出，本文所提出的算法定位值是最小的，远小于DV-hop 算法，随机部署情况下，定位误差相对于DV-Hop 算法减小了63%，相对于PSODV-Hop 定位误差减小了7%；均匀部署情况下，定位误差相对DV-Hop 算法减小了约83%，相对PSODV-Hop 减小了20%。因此，本文提出的定位算法有效地提高了定位精度。

4 结束语

首先，本文对海洋捕食者算法进行了改进，引入Tent 混沌映射初始化算法的种群，并运用柯西变异和反向学习对算法更新后的位置进行扰动，通过3个单峰测试函数和3 个多峰测试函数仿真对比证明，有效地提高了算法的寻优能力和寻优速度。然后，本文提出了IMPA-DV-Hop 定位算法，将其用到了无线传感器网络节点定位中，在2 种不同部署方式下进行了仿真，并将其与DV-Hop、PSODV-Hop算法进行了对比。仿真结果表明，提出的算法有效地提高了定位精度，相对于DV-Hop 定位算法，定位误差得到了明显的提升。但所改进的算法没有在其它函数集上进行测试比较，提出的定位算法只在矩形部署环境中进行了验证，下一步把该算法推广到更多的场景中。