基于混合人工蜂群粒子群改进的WSN定位研究

朱正伟，宋丽萍

（常州大学信息科学与工程学院，江苏常州 213164）

0 引 言

近年来，随着计算机技术、微机电系统、人工智能等技术的发展，无线传感器网络得到了更为密切的关注，使得其广泛地应用于工业生产、环境监控、军事侦察等多个领域[1]。其中，对于无线传感器网络的定位技术是实现其应用的重要基础。全球定位系统（GPS）是目前应用最广泛、最成熟的定位系统，通过卫星的授时和测距对用户节点进行定位，其定位精度高，实时性好。但GPS 定位由于其高成本以及对硬件设施较高的要求使其无法适用于低成本自组织的无线传感器网络[2]中。因此，对于无线传感器的定位问题，现阶段已经出现了许多适应其要求的方法。

DV-Hop 作为一种无需测距的定位方法，其环境适应性强，应用方便，但是定位精度不高，针对这一缺点，国内外已经有大量学者对其做出了改进与优化。文献[3]通过分析网络节点分布特性得到最优节点通信半径，并使用最小二乘法校正锚节点的平均跳距，最后采用加权方法修正未知节点位置，使得定位精度得到了提高。文献[4]首先考虑最近锚节点之外的其他锚节点在局部范围和全局范围的影响，并依据阈值选择最优的校正平均跳距来估计距离，基于阈值机制与距离校正有效地降低了定位误差。文献[5]提出一种基于位置计算过程的参考节点选择算法，该方法在复杂的WSN 系统中仍然有较良好的定位精度。除了在原有的DV-Hop 算法中进行改进之外，将其他智能算法与DV-Hop 算法相结合也能大大提高其定位精度。文献[6]将自适应粒子群优化与DV-Hop 算法相结合，将定位精度提高了20%左右。同时,文献[7]运用人工蜂群算法与DV-Hop 算法相结合，也大大提高了定位精度。

综合看来，传统的DV-Hop 在定位中很难做到精准定位，只有通过与其他定位算法结合，修正未知节点与锚节点之间的距离，改进定位计算方法等手段才可以达到较为精准的定位效果。根据前人的研究发现，一些智能算法的引入可以较好地提高DV-Hop 的定位精度，本文在传统定位方法中首先引入人工蜂群算法，提高其定位精度，并针对其容易陷入局部最优解与求解速度慢的缺点，将变异粒子群算法的思想融入其中，使其能够更为快速地收敛从而实现节点的定位。

1 传统算法说明

在当前的节点定位问题研究中，往往基于以下3 个前提：

1）网络中有一定比例的节点位置己知或具有GPS定位功能，这些位置已知的节点可作为定位参考点。

2）节点具有与邻近节点通信的能力。

3）节点不具有自主移动能力。

根据定位过程中是否需要测量实际节点间的距离，定位算法可分为基于测距的定位算法和无需测距的定位算法。两者的区别在于前者定位精度相对较高，但对额外的硬件设施要求也比较高。后者成本低、功耗小、抗测量噪声能力强、硬件设备简单[8]。因为传感器网络往往具有数量大、分布杂等特点，所以一般采取无需测距的定位方法，而DV-Hop 则是这类算法中的一个，具有方法简单，易于实现等优点。

1.1 传统的DV-Hop 算法

DV-Hop 是利用距离矢量路由和GPS 定位的思想提出的一系列分布式定位方法之一。该算法的优点是在节点间无线传输距离有限的情况下，节点通过多跳路由的方式进行信息传送，节点自身仅需要与邻居节点进行通信以及数据交换，根据节点的分布密度和距离矢量信息，合理地将跳数以及跳距转换为节点间的距离[9]。

一般地，传统DV-Hop 算法的实现流程可以分为如下三个步骤：

1）通过典型的距离矢量交换协议获取未知节点和参考节点间的最小跳步数信息，在获取了最小跳步数信息后，可以通过式（1）利用参考节点之间的距离与跳数计算出跳步距离：

式中：i,j表示选择的不同参考节点，只要有两个参考节点被选择则可以计算出一个跳步距离，这里选择不同的参考节点会得到不一样的跳步距离，根据文献[10]的研究，利用加权算法得到加权跳步距离，该跳步距离会更好地与实际跳步距离匹配。

2）再根据式（2）计算出未知节点与参考节点之间的距离：

式中：Dwi表示未知节点与第i个节点之间的估计距离；hwi表示未知节点与第i个节点之间的跳步数。

3）判断未知节点是否获得了3 个或3 个以上的与已知节点的距离，若有，则说明该点可以被定位。

式中：DV-Hop 中的距离表示在传统DV-Hop 算法中根据三边测量法或极大似然估计法来计算未知节点的位置，即xw与yw。

1.2 人工蜂群算法

人工蜂群算法（Artificial Bee Colony，ABC）是模拟蜜蜂的采蜜行为来解决生活中一些多维和多模的优化问题[11]。在该算法中，用蜜源表示解，用蜜源的花粉数量表示解的适应值。并把蜜蜂分为雇佣蜂、跟随蜂和探索蜂。在数量上雇佣蜂和跟随蜂各占蜂群总数的一半。每种蜜蜂有着不同的职责，雇佣蜂的任务是寻找蜜源并将其信息共享，跟随蜂则主要负责根据雇佣蜂提供的信息去采蜜，探索蜂负责在原有蜜源被抛弃后随机寻找新的蜜源。

在算法的实现中，首先生成初始蜂群，然后不断进行迭代，最终得到收敛结果。具体实现步骤如下：

1）初始化蜂群

生成初始蜜蜂，并将其均匀地分布于寻优空间，其中雇佣蜂与跟随蜂的数量相等且为种群数的一半。产生一个新蜜源的公式如下：

式中：Xi,j代表第i个蜜源Xi的第j维度值，而Xi,jmax和Xi,jmin分别表示Xi的第j个分量的上限和下限。

2）找寻新蜜源阶段

式中：ni,j代表新的蜜源；φij为在[-1，1]中的随机数。

根据式（4）产生了新蜜源后，与原来的旧蜜源相比较，雇佣蜂择优采蜜。

3）蜜蜂舞蹈阶段

蜜蜂会通过舞蹈来传递蜜源的信息，跟随蜂通过观察舞蹈，依据轮盘赌策略选择蜜源开采，这样可以保证适应值更高的蜜源开采率更高。

4）丢弃蜜源

若一个蜜源在多次开采后没有得到更新，那么该蜜源会被抛弃，并重新进入搜索阶段，搜索阶段的公式与式（3）一样。

1.3 粒子群算法

粒子群算法源于针对鸟群捕食行为的研究，所以也叫做鸟群算法。PSO 算法的优势在于可以较为简便地求出多个粒子共存或合作时的最优解。定义单个粒子在飞行过程中所获取的最优解为个体最优解（pBest），在整个粒子群所获得的最优解记作全局最优解（gBest），用N维速度Vi=(vi1,vi2,…,viN) 与位置Pi=(pi1,pi2,…,piN)进行粒子状态的表示，在算法中不断通过自身速度与位置进行状态更新，可以产生新一代群体。

式（6）表示的是速度的更新值，该值取决于个体最优解与全局最优解，还与学习因子常数c1，c2有关。式（7）则表示位置的更新方式。

该方法的具体实现流程如下：

1）粒子群初始化，将粒子群中各个参数设置好；

2）在适应度函数的基础上，将每一个粒子适应度值表示出来；

3）将粒子的当前适应度值与历史最优适应度值比较，更新历史最优值；

4）将当前适应度与种群历史最优位置适应度值比较，更新历史最优值；

5）运用方程（5）与方程（6）进行计算；

6）若获得最优值，则输出最优值结果，否则跳转步骤2）继续进行迭代。

2 混合人工蜂群粒子群改进的DV-Hop 算法

在未引入智能算法的传统DV-Hop 算法中，未知节点与参考节点之间的线路复杂，仅仅依靠平均每跳距离或者加权每跳距离均不能很好地反映实际距离，所以得到的预测距离与实际距离之间存在一个误差，若记该误差为ε，则在DV-Hop 中的节点估算距离可以表示为：

为引入适应度函数，将该公式进行变形，将变量体现出来，并将其作为适应度函数，式（9）也是算法的目标函数。

根据式（9）可以利用人工蜂群算法进行未知节点的计算。本文所提出的的混合方法在原有的人工蜂群算法中引入粒子群算法思想，在雇佣蜂寻找新蜜源时，由原来的式（5）进行修改得到式（10）：

式中：ni,j代表新蜜源；ω代表粒子群算法中的惯性权重；c代表学习因子常数；Xi,j代表原始解；Xi,jbest 代表局部最优解。由于在WSN 定位中，仅考虑在通信范围内寻找最优解，所以不存在全局最优。

雇佣蜂在寻找新蜜源时，按照局部最优解提供的方向去找寻，但是若该点本身为最优点，则需要运用：这是为了防止陷入初始最优解，不断对最优解进行更新。算法的具体步骤如下：

1）初始化蜂群，随机生成蜂群初始种群，均布于寻优空间，其中雇佣蜂与跟随蜂的数量相等且为种群数的一半。

2）雇佣蜂在寻优区间内寻优，每次寻优结束会更新最优值，并增加训练数，若为最优点，则进行随机优化。

3）将已经由迭代产生坐标的未知节点进行更新，当做已知节点看待，并进行下次迭代。

4）在训练过程中若发现有蜜源的训练数超过边界值，则需要抛弃该蜜源，重新选择新的蜜源。软件的具体流程图如图1 所示。

3 仿真实验及结果分析

为了验证该算法是否能提高定位精度，将上述算法在Matlab 中进行模拟仿真。在算法参数的确定中，人工蜂群算法中蜂群的初始大小与DV-Hop 的节点个数有关，并将各种网络节点的参数进行变化，测试在不同条件下传统DV-Hop 的定位精度与本文方法的差异，搜索范围均为100 m 的正方形区域，混合人工蜂群粒子群算法收敛条件为式（9）提出的适应度ε≤10-4。

3.1 各方法定位精度比较

在以往的DV-Hop 算法优化中，已经有不少人提出了将一些智能算法引入，从而优化DV-Hop 算法。其中，人工蜂群算法利用蜜蜂之间寻优的正反馈机制，有效加快全局寻优过程，并且算法中参数较少，但在接近最优解时速度会变慢。这一缺点在粒子群算法中并未出现，而粒子群算法在后期精度无法得到进一步提高，容易陷入局部最优解。本文将这两种算法相结合，首先在参数相同的情况下比较几种算法的定位精度。

图1 混合方法的流程图Fig.1 Flowchart of hybrid method

WSN 的网络参数边界为100 m 的正方形，总节点数为100，已知节点个数为10，通信距离为20 m。对于人工蜂群算法的参数种群数量为50，最大循环数为1 000，蜜源的放弃参数为10。粒子群算法中粒子的惯性参数选为0.6，学习因子为2。利用Matlab 生成的模拟网络节点图如图2 所示。

图2 WSN 模拟节点图Fig.2 Diagram of simulation nodes of WSN

针对该网络，首先用传统DV-Hop 算法进行未知节点的定位，然后再分别利用人工蜂群算法、粒子群算法、混合算法进行定位，从90 个未知节点中随机取出30 个，比较他们的定位误差。误差比较图如图3 所示。

图3 四种方法的定位相对误差对比Fig.3 Comparison of relative errors for positioning of four methods

表1 为误差精度的比较。从表1 中可以看出，在传统的DV-Hop 算法中，对于未知的30 个节点的定位效果都浮动很大，最大的相对误差达到了72.12%，最小的相对误差为20.19%，平均相对误差为38.40%。在引入了算法进行优化后，定位精度得到了提升，从图3反映的整体定位精度来看，定位精度由低到高依次是传统DV-Hop算法、粒子群算法、人工蜂群算法、混合算法。本文提出的混合算法在同等条件下，定位的最大误差为47.26%，最小为10.07%，平均降低了18.28%。同时也发现了在传统DV-Hop 算法不能取得良好定位精度时，采用优化算法有时也不能提高其精度，这或许是因为在DV-Hop算法中运用了跳步数乘平均跳步距离所引入的误差过大所导致的。

表1 四种方法的定位相对误差对比Table 1 Comparison of relative errors for positioning of four methods %

本文提出的算法在收敛性上也要优于仅仅使用单一算法进行定位。

3.2 不同算法的收敛情况比较

三种定位算法的收敛性比较如图4 所示。从图4 中发现，本文算法与人工蜂群算法和粒子群算法相比收敛速度较快，定位函数值更准确。本文算法当迭代次数为410 时，算法基本收敛，收敛值为10-12左右。虽然人工蜂群算法在320 次迭代就收敛，但陷入了局部最优解，收敛值为10-6，粒子群算法也更早的陷入了局部最优解。说明本文的混合算法在定位中具有一定的优势，究其原因是在本文算法中优化了算法粒子的寻优项，这样降低了由于算法速度引起算法收敛的问题，通过扰动因子有效降低算法的局部收敛可能性，使得算法能够以更快的速度获得最优解。

图4 三种算法收敛情况比较Fig.4 Comparison of convergence of three algorithms

4 结 论

本文针对传统DV-Hop 算法中定位精度不高，误差较大的问题，提出混合蜂群粒子群的方法对该问题进行求解，并引入估算距离与跳步距离的差值的适应度函数，通过优化该值从而得到精确的定位，比以往的方法具有更好的效果。

通过实验仿真模拟，该算法在同样的传感器网络条件下，相较于单一使用人工蜂群或者粒子群算法均具有一定的优化性，且参数较少，操作方便，具有一定的实用价值。