基于差分进化和人工蜂群混合策略的DV—Hop改进算法
赵宏才+赵晓杰+王茂励+孟庆龙
摘 要： 为了解决无线传感器网络依靠DV?Hop算法定位过程中存在误差偏高的问题，将人工蜂群算法和差分进化算法融合，引入传统DV?Hop算法中，提出一种HDV?Hop算法。该算法在继承经典DV?Hop算法的前提下，获取锚节点的信息及平均跳距距离，在未知节点定位阶段引入混合策略的目标函数，优化搜索算法，提高定位精度，完成对未知节点的定位。仿真分析表明，该算法相比于DV?Hop算法和基于人工蜂群的定位算法能有效降低定位误差，提高稳定性。
关键词： DV?Hop算法； 人工蜂群； 差分进化； 定位
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）15?0129?04
Abstract： In order to solve the big error of the wireless sensor network （WSN） relying on DV?Hop algorithm in position process， the artificial bee colony algorithm and differential evolution algorithm are fused， and introduced into the traditional DV?Hop algorithm to propose a HDV?Hop algorithm. Under the premise of inheriting the classic DV?Hop algorithm， the objective function of the mixed strategy is introduced into the positioning stage of unknown node after getting the anchor node information and average hop distance， the search algorithm is optimized， and the positioning accuracy is improved to locate the unknown nodes. The simulation analysis results show that， in comparison with the DV?Hop algorithm and positioning algorithm based on artificial bee colony， the proposed algorithm can reduce the positioning error effectively， and improve the stability.
Keywords： DV?Hop algorithm； artificial bee colony； differential evolution； positioning
0 引 言
智能控制技术的发展极大地带动了智能传感器的发展，由大量传感器节点自组而形成的无线传感器网络（WSNs）成为控制领域的研究热点。无线传感器网络节点的位置信息对传感器网络的监测活动至关重要，没有位置信息的监测是毫无意义的[1]。DV?Hop算法依靠其不用测距的特点成为无线网络定位技术中重点关注的算法，但其定位精度较低，无法满足高精度需求的场所，提高精度是该算法亟需解决的问题[2]。近年来，大量专家和学者已经针对这一问题提出了一系列提高精度的改进方法[3?7]。本文在文献[7]研究的基础上，在算法的节点定位阶段，采用将差分进化算法（DE算法）和人工蜂群算法（ABC算法）融合的混合人工蜂群算法（HABC）[8]来优化目标函数，进行定位信息计算，从而提高DV?Hop算法的定位精度。
1 算法描述
1.1 DV?Hop算法
DV?Hop定位算法的定位过程分为以下三个阶段[2，9]：
（1） 计算未知节点的最小跳数。锚节点不断向通信区域内邻居节点广播包含跳数（定义初始值为0）、锚节点标志以及坐标等的相关信息。未知节点记录自同一个锚节点发出的最小跳数，丢弃其余数据，并将跳数值加1后继续广播给邻居节点。
（2） 锚节点与未知节点的实际每跳跳距。锚节点利用步骤（1）中接收到的跳数与位置信息，通过式（1）计算自己的平均每跳距离：
式中：是锚节点的坐标；是锚节点之间的跳数。
平均每跳的距离被锚节点通过可控洪泛法广播到网络中，每个节点记录下来自锚节点的第一个平均跳距并在丢掉之后接收到的跳距信息。未知节点根据接收到的信息，利用式（2）计算与锚节点之间的距离：
（3） 计算未知节点的坐标。未知节点将计算后的与锚节点之间的距离信息通过极大似然估计法或三边测量法来获取未知节点的坐标信息，最终实现节点定位。
1.2 差分进化算法
差分进化算法（DE算法）是一种高效的随机并行搜索算法，能有效解决复杂的优化难题。算法寻优求解的思想概括为：对当前种群进行变异和交叉运算，衍生出一个新的种群；进而利用贪婪策略从两个种群中选优并保留至下一代，形成新一代种群。差分改进算法始终保持种群的规模不变，算法过程如下[8，10]：
在问题的可行解空间对种群进行初始化为种群规模，个体表征问题解，为解空间的维数。然后对当前种群通过式（3）和式（4）进行变异和交叉操作，生产新种群。然后进行选择操作，将优于父个体的子代个体保留，否则，父个体保留至下一代。变异和交叉运算公式如下：
式中：为个体生成的变异个体；为种群中互不相同的3个个体；是缩放比例因子，用来决定差向量的影响比重；为之间的随机数；为杂交参数。
1.3 人工蜂群算法
文献[11]提出人工蜂群算法（ABC算法），其能够有效地解决群体智能优化的问题。该算法寻求最优解的过程概括为：采蜜蜂依据其存储的蜜源信息在蜜源的一定范围内发现一个新的蜜源，然后将蜜源位置发送给跟随蜂，跟随蜂通过贪婪策略确定一个蜜源，并依据当前蜜源信息在其邻域内搜寻新的蜜源，依次循环，最终寻得最优解[12]。
ABC算法中跟随蜂通过观察采蜜蜂传递的信息来判断蜜源的收益率，并确定蜜源。收益率通过适应度值来表示，选择概率如下：
式中是第个目标函数。
根据贪婪机制选择收益度较大的个体作为新的蜂群，依次循环，循环次数达到limit限定参数后，这个解依然没有得到优化，则这个解陷入局部最优，这些采蜜蜂则转变为侦查蜂。
2 改进的DV?Hop算法
基于人工蜂群的定位算法主要存在以下问题：
（1） 人工蜂群算法寻优过程中容易出现“早熟”的收敛性缺陷，从而陷入局部最优，进而影响算法的性能；
（2） 局部搜索能力差，收敛速度比较慢。
针对人工蜂群算法的不足，本文将人工蜂群算法和差分进化算法融合，以期提高人工蜂群算法的搜索精度和收敛速度，从而提高DV?Hop算法的定位精度。
由式（1）可知，未知节点与锚节点距离满足公式考虑到实际测量及外部因素的影响，与实际距离存在一定的误差，将影响定位的准确性。令为实际误差，则。将的计算融入到人工蜂群算法的适应度值的计算中，以期将误差降为最小，从而提高定位精度。定义适应度函数如下：
算法的基本思路是：首先利用DV?Hop算法计算出未知节点与锚节点之间的最小跳数和每跳距离。利用人工蜂群算法优化出一个新的搜索策略，并扩大个体的搜索区间，从而提高搜索能力；然后，通过淘汰规则来提高算法的收敛能力，满足规则后，依次抽取一个个体，与最优个体的变异或算术杂交来更新自己，以加快适应度向最优更新；最后，对未知节点进行差分操作，优化处理后完成定位。改进的定位算法基本步骤如下：
（1） 计算未知节点最小跳数。
（2） 设置规模阈值以及DE算法和ABC算法的初始相关参数，随机生成个解构成初始蜜源的位置。
（3） 按照人工蜂群搜索策略式（8）搜索一个新解，并计算其适应度，如果新解优于原先的解，则用新解替换原先的解。
（4） 侦查蜂根据蜜源的花蜜含量，依概率大小选择一个蜜源位置，并根据式（8）产生一个新位置，评价该位置，如果新解优于侦查蜂所选的解，则用新蜜源替换所选蜜源。
（5） 判断是否需要放弃该解。若存在放弃的解，则跳转到步骤（3），用新解替换原来的解。
（6） 经过次循环后，最优适应值下降量小于阈值时，随机选择一个个体，按照式（9）和式（10）产生两个新的解，并评价他们的适应度值，用贪婪选择机制进行更新。
（7） 对未知节点进行差分变异、交叉和选择操作，更新未知节点的位置，并记录下当前的最优位置及适应值，判断是否都满足终止条件，若满足条件则输出最优解，否则跳转到步骤（5）。
3 仿真实验及性能分析
本文通过Matlab工具软件对算法进行仿真来验证改进算法的性能，设定锚节点和未知节点随机分布在200 m2的正方形区域内；锚节点的坐标已经确定；节点通信半径设定为25 m。设置种群数量循环实验次数为并定义为未知节点的实际坐标，为未知节点的估计坐标，定位节点的个数用表示。则基于次仿真结果统计的评价指标定义为：
式中：error为定位误差，在仿真实验中作为定位精度的评价指标；为定位的节点个数；为节点的通信半径。
3.1 不同锚节点数条件下定位结果比较
对算法进行100次仿真，对比DV?Hop算法、基于ABC算法的DV?Hop算法（ABDV?Hop算法）以及本文基于差分进化和人工蜂群融合的改进DV?Hop算法（HDV?Hop算法），由图1可以看出，这三种算法的平均定位误差均随着锚节点占总数的比例增大而减小，而且在占比达到35%之后，锚节点占比对定位误差影响减小，表明锚节点数占比在一定区间内有利于减小定位误差，但是当锚节点数占比超过定值之后，对定位误差的影响就会保持稳定。通过仿真可知，本文算法相比于传统定位误差平均减小24.44%，相对于ABDV?Hop算法的定位误差平均减小17.22%。
3.2 不同通信半径条件下定位结果比较
在仿真区域随机分布200个节点，锚节点数为30个，对三种算法在通信半径为30～70 m的区间内对归一化的平均定位误差进行对比，实验结果如图2所示。
从图2中可以看出：三种定位算法的定位误差随着通信半径的增大而减小，并且最终趋于稳定；定位算法在通信半径为40 m之后，通信半径长度对定位误差的影响基本不变，所以不能一味地通过增加通信半径来提高定位误差；本文定位算法相对于传统定位算法和人工蜂群定位算法，定位误差平均减小了10.33%和1.22%。
3.3 不同节点总数条件下定位结果比较
设定通信半径为20 m，初始锚节点总数为20且始终占总节点数的10%，在仿真区域内，节点总数从100～400逐渐增加，对比三种算法归一化平均定位误差，结果如图3所示。通过仿真结果可知，三种算法随着节点总数的增加，定位误差逐渐减小并且最终趋于稳定；本文定位算法，在节点总数不同的条件下，平均定位误差较传统定位算法平均减小了13.71%，较人工蜂群定位算法降低了8.21%。
4 結 语
本文针对ABDV?Hop算法在定位过程中容易出现局部最优、收敛速度慢和定位精度低的问题，引进差分进化算法，在未知节点坐标的计算过程中将两种算法融合，进行了优化求解，在原有资源的前提下提高定位精度和稳定性。仿真结果表明，本文提出的HDV?Hop算法在解决传感器网络定位上提供了一种高精度、易实现的定位方案。
参考文献
[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005：146?168.
[2] NICOLESCU D， NATH B. Ad Hoc positioning system （APS） [C]// Proceedings of the 2001 IEEE Global Telecommunications Conference. [S.l.]： IEEE， 2001： 1?11.
[3] 周玲，康志伟，何怡刚.基于三角不等式的加权双曲线定位DV?HOP算法[J].电子测量与仪器学报，2013，27（5）：389?390.
[4] 金纯，叶诚，韩志斌，等.无线传感器网络中DV?Hop定位算法的改进[J].计算机工程与设计，2013，34（2）：401?402.
[5] 胡鹏莎.WSN中DV?Hop节点定位算法的改进研究[D].南京：南京林业大学，2013.
[6] HU Yu， LI Xuemei. An improvement of DV?Hop localization algorithm for wireless sensor networks [J]. Telecommunication systems， 2013， 53（1）： 13?18.
[7] 李牧东，熊伟，郭龙.基于人工蜂群算法的DV?Hop定位改进[J].计算机科学，2013，40（1）：33?36.
[8] 高卫峰，刘三阳，姜飞，等.混合人工蜂群算法[J].系统工程与电子技术，2011，33（5）：1167?1170.
[9] 张伟.面向精细农业的无线传感器网络关键技术研究[D].杭州：浙江大学，2013：48?49.
[10] 刘波，王凌，金以慧.差分进化算法研究进展[J].控制与决策，2007，22（7）：721?722.
[11] KARABOGA D. An idea based on honey bee swarm for numerical optimization [R]. Erciyes： Erciyes University， 2005.
[12] 秦全德，程适，李丽，等.人工蜂群算法研究综述[J].智能系统学报，2014，9（2）：127?132.
摘 要： 为了解决无线传感器网络依靠DV?Hop算法定位过程中存在误差偏高的问题，将人工蜂群算法和差分进化算法融合，引入传统DV?Hop算法中，提出一种HDV?Hop算法。该算法在继承经典DV?Hop算法的前提下，获取锚节点的信息及平均跳距距离，在未知节点定位阶段引入混合策略的目标函数，优化搜索算法，提高定位精度，完成对未知节点的定位。仿真分析表明，该算法相比于DV?Hop算法和基于人工蜂群的定位算法能有效降低定位误差，提高稳定性。
关键词： DV?Hop算法； 人工蜂群； 差分进化； 定位
中图分类号： TN911?34； TP393 文献标识码： A 文章编号： 1004?373X（2017）15?0129?04
Abstract： In order to solve the big error of the wireless sensor network （WSN） relying on DV?Hop algorithm in position process， the artificial bee colony algorithm and differential evolution algorithm are fused， and introduced into the traditional DV?Hop algorithm to propose a HDV?Hop algorithm. Under the premise of inheriting the classic DV?Hop algorithm， the objective function of the mixed strategy is introduced into the positioning stage of unknown node after getting the anchor node information and average hop distance， the search algorithm is optimized， and the positioning accuracy is improved to locate the unknown nodes. The simulation analysis results show that， in comparison with the DV?Hop algorithm and positioning algorithm based on artificial bee colony， the proposed algorithm can reduce the positioning error effectively， and improve the stability.
Keywords： DV?Hop algorithm； artificial bee colony； differential evolution； positioning
0 引 言
智能控制技术的发展极大地带动了智能传感器的发展，由大量传感器节点自组而形成的无线传感器网络（WSNs）成为控制领域的研究热点。无线传感器网络节点的位置信息对传感器网络的监测活动至关重要，没有位置信息的监测是毫无意义的[1]。DV?Hop算法依靠其不用测距的特点成为无线网络定位技术中重点关注的算法，但其定位精度较低，无法满足高精度需求的场所，提高精度是该算法亟需解决的问题[2]。近年来，大量专家和学者已经针对这一问题提出了一系列提高精度的改进方法[3?7]。本文在文献[7]研究的基础上，在算法的节点定位阶段，采用将差分进化算法（DE算法）和人工蜂群算法（ABC算法）融合的混合人工蜂群算法（HABC）[8]来优化目标函数，进行定位信息计算，从而提高DV?Hop算法的定位精度。
1 算法描述
1.1 DV?Hop算法
DV?Hop定位算法的定位过程分为以下三个阶段[2，9]：
（1） 计算未知节点的最小跳数。锚节点不断向通信区域内邻居节点广播包含跳数（定义初始值为0）、锚节点标志以及坐标等的相关信息。未知节点记录自同一个锚节点发出的最小跳数，丢弃其余数据，并将跳数值加1后继续广播给邻居节点。
（2） 锚节点与未知节点的实际每跳跳距。锚节点利用步骤（1）中接收到的跳数与位置信息，通过式（1）计算自己的平均每跳距离：
式中：是锚节点的坐标；是锚节点之间的跳数。
平均每跳的距离被锚节点通过可控洪泛法广播到网络中，每个节点记录下来自锚节点的第一个平均跳距并在丢掉之后接收到的跳距信息。未知节点根据接收到的信息，利用式（2）计算与锚节点之间的距离：
（3） 计算未知节点的坐标。未知节点将计算后的与锚节点之间的距离信息通过极大似然估计法或三边测量法来获取未知节点的坐标信息，最终实现节点定位。
1.2 差分进化算法
差分进化算法（DE算法）是一种高效的随机并行搜索算法，能有效解决复杂的优化难题。算法寻优求解的思想概括为：对当前种群进行变异和交叉运算，衍生出一个新的种群；进而利用贪婪策略从两个种群中选优并保留至下一代，形成新一代种群。差分改进算法始终保持种群的规模不变，算法过程如下[8，10]：
在问题的可行解空间对种群进行初始化为种群规模，个体表征问题解，为解空间的维数。然后对当前种群通过式（3）和式（4）进行变异和交叉操作，生产新种群。然后进行选择操作，将优于父个体的子代个体保留，否则，父个体保留至下一代。变异和交叉运算公式如下：
式中：为个体生成的变异个体；为种群中互不相同的3个个体；是缩放比例因子，用来决定差向量的影响比重；为之间的随机数；为杂交参数。
1.3 人工蜂群算法
文献[11]提出人工蜂群算法（ABC算法），其能够有效地解决群体智能优化的问题。该算法寻求最优解的过程概括为：采蜜蜂依据其存储的蜜源信息在蜜源的一定范围内发现一个新的蜜源，然后将蜜源位置发送给跟随蜂，跟随蜂通过贪婪策略确定一个蜜源，并依据当前蜜源信息在其邻域内搜寻新的蜜源，依次循环，最终寻得最优解[12]。
ABC算法中跟随蜂通过观察采蜜蜂传递的信息来判断蜜源的收益率，并确定蜜源。收益率通过适应度值来表示，选择概率如下：
式中是第个目标函数。
根据贪婪机制选择收益度较大的个体作为新的蜂群，依次循环，循环次数达到limit限定参数后，这个解依然没有得到优化，则这个解陷入局部最优，这些采蜜蜂则转变为侦查蜂。
2 改进的DV?Hop算法
基于人工蜂群的定位算法主要存在以下问题：
（1） 人工蜂群算法寻优过程中容易出现“早熟”的收敛性缺陷，从而陷入局部最优，进而影响算法的性能；
（2） 局部搜索能力差，收敛速度比较慢。
针对人工蜂群算法的不足，本文将人工蜂群算法和差分进化算法融合，以期提高人工蜂群算法的搜索精度和收敛速度，从而提高DV?Hop算法的定位精度。
由式（1）可知，未知节点与锚节点距离满足公式考虑到实际测量及外部因素的影响，与实际距离存在一定的误差，将影响定位的准确性。令为实际误差，则。将的计算融入到人工蜂群算法的适应度值的计算中，以期将误差降为最小，从而提高定位精度。定义适应度函数如下：
算法的基本思路是：首先利用DV?Hop算法计算出未知节点与锚节点之间的最小跳数和每跳距离。利用人工蜂群算法优化出一个新的搜索策略，并扩大个体的搜索区间，从而提高搜索能力；然后，通过淘汰规则来提高算法的收敛能力，满足规则后，依次抽取一个个体，与最优个体的变异或算术杂交来更新自己，以加快适应度向最优更新；最后，对未知节点进行差分操作，优化处理后完成定位。改进的定位算法基本步骤如下：
（1） 计算未知节点最小跳数。
（2） 设置规模阈值以及DE算法和ABC算法的初始相关参数，随机生成个解构成初始蜜源的位置。
（3） 按照人工蜂群搜索策略式（8）搜索一个新解，并计算其适应度，如果新解优于原先的解，则用新解替换原先的解。
（4） 侦查蜂根据蜜源的花蜜含量，依概率大小选择一个蜜源位置，并根据式（8）产生一个新位置，评价该位置，如果新解优于侦查蜂所选的解，则用新蜜源替换所选蜜源。
（5） 判断是否需要放弃该解。若存在放弃的解，则跳转到步骤（3），用新解替换原来的解。
（6） 经过次循环后，最优适应值下降量小于阈值时，随机选择一个个体，按照式（9）和式（10）产生两个新的解，并评价他们的适应度值，用贪婪选择机制进行更新。
（7） 对未知节点进行差分变异、交叉和选择操作，更新未知节点的位置，并记录下当前的最优位置及适应值，判断是否都满足终止条件，若满足条件则输出最优解，否则跳转到步骤（5）。
3 仿真实验及性能分析
本文通过Matlab工具软件对算法进行仿真来验证改进算法的性能，设定锚节点和未知节点随机分布在200 m2的正方形区域内；锚节点的坐标已经确定；节点通信半径设定为25 m。设置种群数量循环实验次数为并定义为未知节点的实际坐标，为未知节点的估计坐标，定位节点的个数用表示。则基于次仿真结果统计的评价指标定义为：
式中：error为定位误差，在仿真实验中作为定位精度的评价指标；为定位的节点个数；为节点的通信半径。
3.1 不同锚节点数条件下定位结果比较
对算法进行100次仿真，对比DV?Hop算法、基于ABC算法的DV?Hop算法（ABDV?Hop算法）以及本文基于差分进化和人工蜂群融合的改进DV?Hop算法（HDV?Hop算法），由图1可以看出，这三种算法的平均定位误差均随着锚节点占总数的比例增大而减小，而且在占比达到35%之后，锚节点占比对定位误差影响减小，表明锚节点数占比在一定区间内有利于减小定位误差，但是当锚节点数占比超过定值之后，对定位误差的影响就会保持稳定。通过仿真可知，本文算法相比于传统定位误差平均减小24.44%，相对于ABDV?Hop算法的定位误差平均减小17.22%。
3.2 不同通信半径条件下定位结果比较
在仿真区域随机分布200个节点，锚节点数为30个，对三种算法在通信半径为30～70 m的区间内对归一化的平均定位误差进行对比，实验结果如图2所示。
从图2中可以看出：三种定位算法的定位误差随着通信半径的增大而减小，并且最终趋于稳定；定位算法在通信半径为40 m之后，通信半径长度对定位误差的影响基本不变，所以不能一味地通过增加通信半径来提高定位误差；本文定位算法相对于传统定位算法和人工蜂群定位算法，定位误差平均减小了10.33%和1.22%。
3.3 不同节点总数条件下定位结果比较
设定通信半径为20 m，初始锚节点总数为20且始终占总节点数的10%，在仿真区域内，节点总数从100～400逐渐增加，对比三种算法归一化平均定位误差，结果如图3所示。通过仿真结果可知，三种算法随着节点总数的增加，定位误差逐渐减小并且最终趋于稳定；本文定位算法，在节点总数不同的条件下，平均定位误差较传统定位算法平均减小了13.71%，较人工蜂群定位算法降低了8.21%。
4 結 语
本文针对ABDV?Hop算法在定位过程中容易出现局部最优、收敛速度慢和定位精度低的问题，引进差分进化算法，在未知节点坐标的计算过程中将两种算法融合，进行了优化求解，在原有资源的前提下提高定位精度和稳定性。仿真结果表明，本文提出的HDV?Hop算法在解决传感器网络定位上提供了一种高精度、易实现的定位方案。
参考文献
[1] 孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005：146?168.
[2] NICOLESCU D， NATH B. Ad Hoc positioning system （APS） [C]// Proceedings of the 2001 IEEE Global Telecommunications Conference. [S.l.]： IEEE， 2001： 1?11.
[3] 周玲，康志伟，何怡刚.基于三角不等式的加权双曲线定位DV?HOP算法[J].电子测量与仪器学报，2013，27（5）：389?390.
[4] 金纯，叶诚，韩志斌，等.无线传感器网络中DV?Hop定位算法的改进[J].计算机工程与设计，2013，34（2）：401?402.
[5] 胡鹏莎.WSN中DV?Hop节点定位算法的改进研究[D].南京：南京林业大学，2013.
[6] HU Yu， LI Xuemei. An improvement of DV?Hop localization algorithm for wireless sensor networks [J]. Telecommunication systems， 2013， 53（1）： 13?18.
[7] 李牧东，熊伟，郭龙.基于人工蜂群算法的DV?Hop定位改进[J].计算机科学，2013，40（1）：33?36.
[8] 高卫峰，刘三阳，姜飞，等.混合人工蜂群算法[J].系统工程与电子技术，2011，33（5）：1167?1170.
[9] 张伟.面向精细农业的无线传感器网络关键技术研究[D].杭州：浙江大学，2013：48?49.
[10] 刘波，王凌，金以慧.差分进化算法研究进展[J].控制与决策，2007，22（7）：721?722.
[11] KARABOGA D. An idea based on honey bee swarm for numerical optimization [R]. Erciyes： Erciyes University， 2005.
[12] 秦全德，程适，李丽，等.人工蜂群算法研究综述[J].智能系统学报，2014，9（2）：127?132.
