一种改进鲸鱼算法的无线传感器网络定位优化研究∗

陈 暄顾 锦毛科技吴吉义

(1.浙江工业职业技术学院，浙江 绍兴312000；2.衢州市水利局，浙江 衢州324000；3.浙江工业大学计算机科学与技术学院，浙江 杭州310014；4.浙江省人工智能学会，浙江 杭州310012)

无线传感网络(Wireless Sensor Networks，WSNs)一直都是信息网络技术研究的热点之一，它具有低成本、体积小、传输距离远等优点，广泛的应用在工业、军事、医疗等监测等方面[1]。节点定位技术作为无线传感网络中关键技术，在很多领域具有非常重要的作用。针对现有的节点定位技术中存在精度低的问题，国内外学者从不同的方向提出了改进策略。有的学者专注DV-HOP算法的研究。如文献[2]提出了一种降低节点间平均跳距的DV-HOP算法，提高了定位效果但增加了算法复杂度；文献[3]从距离差异的角度改进了DV-HOP算法，定位效果具有一定提升但并不十分明显；文献[4－5]提出在DV-HOP算法中分别使用粒子群算法和猫群算法进行优化，提高节点定位效果但增加了时间复杂度。有的学者专注于传统经典定位方法的研究，如文献[6]提出了一种基于距离估计的改进蒙特卡罗定位算法，减少了无效节点定位，获得更高的定位精度，但提高了算法复杂度；文献[7]提出基于测距修正的无迹卡尔曼滤波优化定位算法，降低算法平均误差率，但提高了节点能耗。有的学者将元启发式算法用于节点定位研究中，如文献[8]提出的基于人工蜂群算法的WSN节点定位策略，虽然提高了节点定位的准确率和精度，但是定位误差无法避免；文献[9]提出一种自适应罚函数优化粒子群的定位算法，具有更好的定位精度和收敛速度，但提高了算法复杂度；文献[10]提出一种基于果蝇优化算法的无线传感器网络节点定位方法，具有较好的定位精度，但缺乏与其他的算法进行对比，定位效果有待进一步验证；文献[11]提出基于极限学习机和粒子群算法融合的定位算法，节点定位精度得到了明显的改善，但无法解决节点能耗；文献[12]提出了一种基于飞蛾算法的无线传感器网络定位方法，降低了节点定位能耗，但延长了定位时间；文献[13－14]分别提出采用灰狼算法和鸡群算法用于无线传感节点定位，提高了定位精度，但算法性能有待进一步提高。从上述研究成果中发现节点定位问题是一个较为复杂的数学模型，而采用元启发式算法进行节点定位求解取得了不错的效果。鲸鱼算法是近几年来一种新的元启发式算法，在收敛性和鲁棒性方面具有一定的优势，为降低无线传感的节点定位误差提供了一种新的解决方法。

目前，节点定位的精度还存在较大的提升空间，因此，本文提出了改进鲸鱼算法与定位模型相结合的研究策略，对鲸鱼算法的种群、包围捕食行为、个体筛选采用了不同策略进行优化，最后将改进的鲸鱼算法用于节点定位指标中进行对比，提高节点定位精度。

1 定位节点模型构建

无线传感中的节点定位一般分为测距和非测距两种。尤其非测距定位具有简单易实现、定位精度较高等优点被广泛采用。DV-HOP是一种使用较为广泛的非测距算法，它主要使用最小二乘法计算未知节点坐标，但定位精度受到来自累计误差因素的影响。本文以二维平面为例进行研究，建立节点定位模型，并对产生的误差进行分析。设定(x，y)为未知节点坐标，(xi，yi)为参考节点坐标，未知节点与参考节点之间对应的距离为di，因此表达如下:

在实际环境过程中肯定会存在一些误差因素ε，它们给节点定位带来很大的干扰，因此必须考虑将上述的线性方程组修正为AL＋ε＝b，通过最小二乘法表示如下:

从式(6)中发现参数b是求解L的关键，而影响参数b的因素是dn，当dn值比较大，用于计算具体节点坐标的最小二乘法无法适用。针对这个问题，将误差较大环境下的定位问题转换为函数约束的优化问题，节点间的距离测量误差表示如下:

式中:f(x，y)的值越小表示求解的坐标值与实际值就越接近。因此将无线传感网络中的节点定位问题转换为多维约束优化方程，利用元启发式算法寻找最优值的特性，求解所获节点具体位置逐步迭代到最小差值，直到获得最佳值。

2 鲸鱼算法

鲸鱼算法(Whale Optimization Algorithm，WOA)[15]是一种模仿大自然海洋中的鲸鱼动物进行捕食猎物的元启发式的智能优化算法，它的核心思想主要包括三个行为:包围捕食、气泡袭击和寻找猎物。在鲸鱼算法中，设定整个鲸鱼种群规模为N，在D维搜索空间中搜索最优解，第i只鲸鱼在第D维空间中的位置表示为猎物的位置就是对应问题的全局最优解。

2.1 包围捕食

在算法的初始阶段，鲸鱼能够识别猎物的位置并进行包围，但是算法并没有事先设定全局最优的位置，因此设定当前群体中的最优位置为所需要捕获的猎物，指引种群中的其他鲸鱼个体向着当前的最优个体靠拢捕食，使用式(10)进行个体的更新位置:

式中:rand1和rand2表示(0，1)之间的随机数，a为收敛因子，伴随着迭代次数的逐渐增加，其值从2线性递减到0。a的表达如下

式中:tmax为最大迭代次数。

2.2 气泡攻击

鲸鱼算法通过收缩包围和螺旋更新位置模拟鲸鱼捕食吐出气泡捕捉食物的行为，从而达到鲸鱼局部寻优的目的。

①收缩包围机制

根据式(11)、式(13)模拟鲸鱼进行收缩包围，当｜A｜<1的时，鲸鱼个体向着当前最优位置的鲸鱼个体靠近，并且｜A｜值越大，鲸鱼个体的游走步伐就越大，否则步伐就减少。

②螺旋更新位置

鲸鱼个体计算与当前最优位置鲸鱼之间的距离，以螺旋方式进行猎物的搜索，螺旋游走方式的表达式如下所示:

式中:D′＝｜Xp(t)－X(t)｜表示第i只鲸鱼个体与最优位置的鲸鱼之间的距离，b表示用于限定对数螺旋形状的常数，l表示一个随机数，其值为[－1，1]。在优化过程中选择收缩包围机制和螺旋位置更新的概率相同都取值为0.5。

2.3 寻觅猎物阶段

上述行为都是鲸鱼在进行局部范围的寻找解的方式，其实鲸鱼算法也可以随机寻找当前鲸鱼个体进行全局优化，其表达式为:

式中:Xrand(t)是当前群体中随机选取的鲸鱼个体位置。

3 改进的鲸鱼算法的节点定位研究

像大部分元启发式算法一样，鲸鱼算法存在易陷入局部最优且收敛速度慢等缺点。为了更好提高鲸鱼算法在节点定位中效果。从以下三个方面进行算法改进:采用神经网络算法提高鲸鱼初始位置的多样性；通过优化非线性和自适应策略避免算法过早陷入局部最优；通过二次插值进行个体筛选缓解鲸鱼位置多样性衰减。

3.1 种群初始化

本文提出一种基于深度神经网络(Deep Neural Network，DNN)构架的最优种群初始化过程。其整体结构如图1所示。

图1显示了鲸鱼算法通过深度神经网络初始化的过程，其步骤如下:

图1 基于深度神经网络的种群初始化过程

步骤1 假设随机初始化种群xi，i∈1，2，…，N；假设一共有M层网络，其中第j层网络层第i个节点多对应的N个网络权值为wk，i，j，k∈1，2，…，N，j∈1，2，…，M；第j个网络层的输入为Ii，j；第j个网络层的输出为Oi，j；第j个网络层的激活函数为ψj；第j个网络层的第i个节点偏移值为θi，j；那么Oi，j的表达式可以表示为:

根据式(16)可以获得第j＋1个网络层的输出为Oi，j＋1，其可以表示为:

步骤2 深度学习神经网络的学习和训练。首先通过穷举法产生一定规模范围内的样本数据，然后通过深度学习进行训练获得可以满足任意规模的网络模型。深度学习神经网络根据初始化产生的种群，依靠深度神经网络中的训练和学习使得种群具有多样性。为了能够让神经网络收敛，因此引入熵函数作为该模型的激活函数，即式(18)所示。深度学习神经网络中定义训练目标函数为归一化后的初始位置和重心之间的距离，如式(19)所示:

式中:μ表示xi的均值，当式(18)的结果为0，表示种群完全没有多样性，当结果越接近1，则表示多样性越大。在深度学习神经网络中将随机产生的种群xi作为网络的输入数据，将网络输出结代入式(18)得到的值作为深度学习神经网络的训练目标。

步骤3 获得多样性种群。假设通过训练之后，得到网络权值为wlearningk，i，j，熵激活函数ψj＝Hj(X)，然后将随机产生的鲸鱼经过神经网络变换后得到熵更大的鲸鱼集合，作为鲸鱼算法的输入。其数学表达式为:

此时，由式(20)得到的Oi，j，i∈1，2，…，N即具有尽可能大的多样性种群。

3.2 参数优化

在鲸鱼算法中，参数A和C决定着鲸鱼个体位置的更新，而另一个参数a直接决定着A的数值变化，由于算法中参数a的值被设定为2~0之间的线性变化范围，因此一定程度上无法有效的体现算法的个体寻优的过程，容易导致算法在后期才进行局部搜索，延长了算法的搜索时间，为了使个体能够尽快进入局部搜索阶段，针对参数a提出一种非线性变化的策略，公式如下:

从式(23)的中发现非线性变化策略能够使得参数a的值在算法前期迅速减小，使得鲸鱼个体尽早进入局部搜索阶段，提升算法求解精度与收敛速度，而另外一个参数C在鲸鱼算法仅仅是一个(0，2)随机数，根据粒子群算法中关于位置更新的启发，在鲸鱼的全局阶段中优化参数C能够减少了搜索的不确定性，使得鲸鱼个体位置更新具有自适应性，较好的保持区域搜索和局部勘探的能力。因此，本文针对参数C进行如下优化:

式中:Cmin和Cmax分别表示参数的最小值，最大值，f表示当前鲸鱼个体的适应度值，fmin和fave分别表示适应度值的最小值和平均值。

随着迭代次数的不断增大，算法逐渐运行到后期，鲸鱼个体的搜索能力会呈现逐渐减弱的趋势，这主要是因为种群多样性正在逐渐消失。二次插值[16]作为一个搜索算子，它能够提高启发式算法中的个体的搜索寻优能力，其中心思想是不断使用二次多项式来近似目标函数，并使用插值多项式中的极小的值逼近搜索问题的极小点。假设X＝(x1，x2，…，xd)，Y＝(y1，y2，…，yd)，Z＝(z1，z2，…，zd)是三个个体，适应度值分别是f(X)，f(Y)，f(Z)，采用二次插值法，根据式(25)产生一个个体

3.3 个体筛选

在更新所有个体位置的同时将所有个体的适应度值从小到大进行排序，依次取出个体Mk，Mk＋1，Mk＋2，通过式(25)生成新的个体，按照式(26)对比Mk和¯Mk的适应度值，然后选择优秀的个体进行下一次迭代。

3.4 改进算法渐近性分析

假设第t次迭代IWOA算法最优解的集合为St，其通过算法中的行为更新之后，得到新的集合S′t，那么第t次迭代将要搜索的最优解的空间范围为S1＝St∪S′t，选择更新前后，最优解空间的相同解空间为为S2＝St∩S′t，那么新的最优解可以表示为S′t－St∩S′t，那么存在如下两个情况:①如果新的最优解比原来的t次迭代时的最优解差，那么此时，最优解的鲸鱼个体依然选择原来的最优解对应的鲸鱼个体。那么存在一个参数k使得在迭代次数t－k＋1时，S′t－k＋1－St－k＋1∩S′t－k＋1≠Φ即t－k＋1时刻，其相对于t－k时刻，新增加的最优解不是空集。那么在St－k＋1中存在最优解x′t－k＋1使得其更接近最优解x∗，但x′t－k＋1≠x∗，那 么 显 然 E[f(x′t－k＋1)－f(x′t－k)]＝E(－ε)＝－ε，此时E(Dt－k＋1)－E(Dt－k)＝－ε，取t′＝tk，即得到E(Dt′＋1)－E(Dt′)＝－ε；②如果新的最优解数值比原来的t次迭代时的最优解好，那么在最优解鲸鱼个体在选择过程中将从优化后的鲸鱼算法选择得到。此时，S′t－St∩S′t≠Φ那么在St′中存在最优解x′t使得其更接近最优解x∗，但x′t≠x∗，那么显然E[f(x′t＋1)－f(x′t)]＝E(－ε)＝－ε，此时E(Dt＋1)－E(Dt)＝－ε。

证明完毕

3.5 算法步骤

步骤1 建立无线传感网络中的节点定位与鲸鱼算法之间的对应关系。即鲸鱼算法将节点定位问题中的每一个解当作鲸鱼个体。在鲸鱼算法的每次迭代中，通过设定的适应度函数来判别当前鲸鱼的优劣，最后寻找最优的鲸鱼个体来获得最佳的节点定位。鲸鱼算法适应度函数表达式如下:

式中:(x，y)表示待观测的节点的位置，(xi，yi)表示第i个已知节点的位置，通过求解的fitness(i)最小值来获得节点位置；

步骤2 初始化鲸鱼算法的相关参数和节点定位相关参数，设置最大迭代次数；

步骤3 按照3.1节采用基于深度神经网络的种群初始化；

步骤4 按照3.2节中的式(22)、式(23)对式(10)、式(11)进行包围捕食行为进行更新；

步骤5 执行气泡攻击和寻觅食物；

步骤6 按照3.3节在每次迭代后根据式(25)、式(26)进行个体筛选；

步骤7 判断是否优化达到Tmax，如果达到则找到最优的鲸鱼个体即待测节点最优位置的近似值，否则转步骤4，迭代次数加1。

4 仿真实验

为了进一步验证本文提出改进的鲸鱼算法(IWOA)在节点定位精度方面具有的效果，选取了较新的两种改进的元启发式算法即文献[14]的基于优化鸡群算法(ICSO)和文献[17]提出的反向蛙跳－教学优化(OSFL-TLBO)用于节点定位实验中的对比算法，对比算法的参数设置均来自各自文献。实验对比主要内容为时间复杂度，未知节点定位、参考节点比例、节点密度、通信半径和区域面积共6个方面。无线传感网络中的环境相关参数如表1所示。

表1 仿真环境参数

仿真实验中将误差结果取平均值，对比三种定位算法性能的优劣，平均定位误差公式如下:

①算法时间复杂度对比

图2显示了三种算法的时间复杂度对比结果，随着种群规模的不断增大，三种算法的时间复杂度逐渐增长，但本文算法的时间复杂度低于ICSO和OSFL-TLBO，说明了IWOA算法通过种群初始化，参数优化和个体筛选等措施后，确实能够提升算法的性能。

图2 三种算法复杂度对比

②未知节点定位的影响

图3显示三种算法在未知节点定位中的误差变化的效果，随着未知节点的数目逐渐增多，三种算法呈现剧烈的波动，但IWOA算法相比于其他两种算法幅度偏小，从整体上来看IWOA算法的定位误差平均数值小于ICSO算法和OSFL-TLBO算法，分别提高了12.1%和9.4%，说明采用IWOA算法在不同数量的未知节点定位方面具有良好的稳定性，主要由于该算法进行了优化，增强了算法的性能。

图3 未知节点定位误差对比

③参考节点比例的影响

图4显示了三种算法在不同的参考节点比例下的定位误差变化的效果。随着参考节点的比例升高，三种算法的曲线整体上都呈现下降趋势，定位误差都在逐渐变小，但IWOA算法在定位误差的效果上表现更好，定位精度相比于ICSO算法和OSFLTLBO算法分别提高了15.19%和7.2%。从总体上看IWOA算法在参考节点比例方面能够有效的提高定位精度，充分说明了IWOA算法适用于参考节点逐步增多条件下的节点定位。

图4 参考节点比例定位误差对比

④节点密度的影响

图5显示了三种算法在不同的节点密度下的定位误差变化效果，随着节点数量逐渐增多，三种定位算法的误差都在不同程度的减少，IWOA算法的定位精度相比于ICSO算法和OSFL-TLBO算法分别提高了9.38%和8.23%。尤其是在节点比例在5%~30%之间，IWOA算法误差下降的最为明显。当节点比重增加到40%以后，定位误差并没有大幅度降低，曲线趋于稳定，究其原因主要是节点密度加大，增加了节点之间的相互通信，但是节点的能量消耗也有所增加，因此根据实际情况选择节点数目是降低误差的一个不容忽视的因素，尤其是节点密度较小的情况下，IWOA算法仍然具有良好的定位效果，说明IWOA算法稳定性优于另外两种算法。在节点密度方面IWOA算法能够有效的提高定位精度。

图5 节点密度下的定位误差对比

⑤通信半径的影响

图6显示了三种算法在不同的通信半径下的定位误差变化效果，随着通信半径的逐渐增大，三种算法的曲线都具有一些波动，这主要是因为DV-HOP算法与节点之间的距离没有关系，而通信半径对定位误差的影响较大。IWOA算法的定位精度相比于ICSO算法和OSFL-TLBO算法分别提高了7.41%和5.8%。当通信半径较小的时，锚节点的数量较小，导致定位效果不理想。但是由于IWOA算法性能的提升，相比于ICSO和OSFL-TLBO算法具有更高的精度，说明了通信半径的大小对IWOA算法影响不大。

图6 通信半径下的定位误差对比

⑥区域面积的影响

图7显示了三种算法在不同的区域面积下的定位误差的变化效果，随着区域面积逐渐扩大，三种算法的定位误差都有不同程度的增加，IWOA算法相比于ICSO和OSFL-TLBO分别降低了8.19%和7.95%，尤其在定位区域面积比较大的情况下，IWOA算法的曲线比较稳定，依然能够保持较好的定位精度，说明了IWOA算法自身的性能能够有效的适应定位区域面积较大的环境，拓宽了节点定位的应用面积。

图7 不同区域面积下的定位误差对比

⑦不同性能参数对比

表2展示了三种算法运行100次的性能对比。从表中发现IWOA算法与OSFL-TLBO和ICSO算法相比，具有更小的定位误差、算法的迭代时间更短，能够在精度和时间上快速确定未知节点的位置，因此非常适合无线传感网络中的对节点精确定位的要求。

表2 三种算法的性能对比

5 结束语

针对无线传感网络中最小二乘法节点定位误差大、精度低的缺点，本文提出了一种将节点定位模型与改进的鲸鱼算法相结合的IWOA算法，在种群初始化采用深度神经网络提高初始位置多样性，对包围捕食行为中的参数采用非线性和自适应策略避免算法过早陷入局部最优，在迭代搜索过程中利用二次插值法缓解鲸鱼位置多样性衰减问题，最终达到较好的位置搜索效果。仿真实验中本文算法能够有效的提高节点定位精度，下一步将考虑如何该算法在三维空间下的节点定位的效果，拓宽该算法的应用范围。