基于改进蝴蝶优化的DV-Hop定位算法*

叶 帅，余修武，刘 永

（南华大学，湖南 衡阳 421001）

无线传感器网络（Wireless Sensor Networks，WSNs）是一种由大量的传感器节点组成，通过无线方式进行通信、连接进而达到某种任务目的的网络[1]，其在军事侦察、地理环境监测以及交通路况监测[2]等领域都有广泛的前景。WSNs进行数据采集和检测时需要结合位置信息以确保信息的有效性[3]，因此定位技术成为WSNs技术中研究的热点。

目前无线传感网络定位算法大致分为基于测距和无须测距两类[4]。基于测距的定位算法主要有信号传输时间算法（Time Of Arrival，TOA）、到达时间差算法（Time Difference Of Arrival，TDOA）、接收信号强度指示算法（Received Signal Strength Indication，RSSI）和信号到达角算法（Arrival Of Angle，AOA）等。无须测距定位算法主要有质心算法、近似最佳三角形内点测试算法（Approximate Perfect Point-In-Triangulation Test，APIT）、Amorphous算法以及距离向量跳段算法[5]（Distance Vector-Hop，DV-Hop）等。相比基于测距的定位算法，无须测距定位算法虽然定位精度不高，但具有成本低、功耗小以及硬件设备简单等优势，从而备受关注。无须测距定位算法中的DV-Hop算法由于对物理测量单元的要求不高并且在各向同性网络中具有良好的性能[6]，引起了广大学者的关注。

为了解决DV-Hop算法定位精度不高的问题，学者们对该算法做了不同程度的改进。文献[7]通过引入多通信半径广播数据，减小平均跳数误差，改善了算法的定位精度，但由于只对前两个阶段进行改进，定位精度并不稳定。文献[8]使用局部加权线性回归（Locally Weighted Linear Regression，LWLR）选择最佳候选信标节点子集，提高了定位精度，但在信标节点密度较低的环境中，定位效果并不理想，具有一定的局限性。文献[9]提出了改进鲸鱼算法（Improved Whale Optimization Algorithm，IWOA），该算法采用深度神经网络（Deep Neural Networks，DNN）来初始化种群，并使用非线性策略以及二次插值对鲸鱼算法进行改进，提高了定位精度。文献[10]利用接收信号强度值和无偏估计对跳数和平均跳距进行了校正，使用差分进化算法估计未知节点算法，在一定程度上降低了平均定位误差。文献[11]提出了MA*-3DDV-Hop算法，该算法首先通过A*路由算法减小了跳数以及平均跳距不准确所带来的误差，在定位阶段采用非支配遗传算法（Non-dominated Sorting Genetic Algorithm-II，NSGA-II）替代原有的最小二乘法，提高了定位精度，但是算法复杂度较大。

上述方案在一定程度上提高了定位精度，但仍然存在很大的局限性。为了进一步提高DV-Hop算法的定位精确度，本文提出了基于改进蝴蝶优化的DV-Hop定位算法（Improved Butterfly Optimization Algorithm，IBOA）。首先通过细化信标节点广播半径以及引入跳距修正因子来减小传统DV-Hop算法前两个阶段产生的误差；
其次在定位阶段，将黄金正弦算法和蝴蝶算法相结合优化定位结果，从而减少节点定位误差，提高算法寻优能力。

1.1 DV-Hop算法

DV-Hop算法的定位过程分为以下3个阶段。

（1）获得最小跳数。所有的信标节点广播的信息中包括坐标信息和跳数的数据分组，初始化跳数为0。如果信标节点跳数小于前一个值，则更新并保存该最小值。根据此机制，在广播结束后，所有信标节点获得最小跳数。

（2）估计平均跳距。由第一阶段获得的任意两个信标节点的坐标信息以及最小跳数计算得到平均跳距为：

式中：(xi,xj)，(yi,yj)为信标节点i，j的坐标；
hij为信标节点i和j(j≠i)之间的跳数。

每个未知节点通过第二阶段获得的平均跳距乘以最小跳数得出到各信标节点之间的距离，其计算公式为：

式中：di为未知节点i到信标节点的估计距离；
hni为未知节点i到信标节点的最小跳数。

（3）计算未知节点坐标。当信标节点数大于或者等于3时，使用最小二乘法估计目标节点位置。

设目标节点的坐标为(x,y)，信标节点的坐标为(xi,xj)(i=1,2,…,n)，根据距离公式可得目标节点与各个信标节点间的距离关系为：

用向量表示为：

根据最小二乘法可得目标节点的坐标：

1.2 蝴蝶优化算法

蝴蝶优化算法[12]是一种自然启发式算法。该算法的主要思想就是通过模拟蝴蝶觅食和求偶行为来寻找最优解，具有操作简单、调整参数少、鲁棒性好等优点。

在BOA中，蝴蝶的香味强度f与所受刺激强度I有关。香味强度的计算公式为：

式中：c表示感官模态；
a表示香味强度衰减指数。

蝴蝶优化算法在初始化阶段定义目标函数和解空间，并对算法中的相关参数赋值，然后在解空间中随机生成蝴蝶的位置，并根据目标函数和式（9）计算每只蝴蝶的香味强度。迭代过程中，蝴蝶种群会随机移动或者向着全局最优的蝴蝶移动。若处于全局搜索阶段，其位置更新公式为：

若处于局部游走阶段，其位置更新公式为：

2.1 DV-Hop算法优化

2.1.1 跳数的改进

在传统的DV-Hop算法中，其跳数是通过节点的通信半径来确定的，只要在信标节点广播半径范围内的节点跳数均记为一跳。如图1所示，图中信标节点A和未知节点B、C、D、E间跳数均记为一跳，但实际上AB、AC、AD、AE的距离相差很大。这种方式记录得出的跳数存在巨大误差，因此本文采用多通信半径方式对跳数进行细化，提高跳数的准确性，从而提高算法的定位精度。其中，R为节点的通信半径。

图1 多通信半径图示

随着广播次数增加，信标节点所消耗的能量也随之加大。考虑到无线传感器节点能量的有限性，设定信标节点的广播半径为0.25R，0.5R，0.75R和R。

2.1.2 跳距的改进

（1）信标节点跳距的改进

为了减小信标节点平均跳距误差对定位结果的影响，本文引入修正因子ei优化信标节点的平均跳距。修正因子的计算公式为：

式中：dij为信标节点间的实际距离；
为信标节点间的估计距离。

优化后的平均跳距表达式为：

（2）未知节点跳距的改进

由于现实无线传感器网络中节点都是随机分布的，未知节点到信标节点的距离不尽相同，从而导致较大误差。因此，本文根据每个信标节点的跳数信息引入权重因子wi，从而改进未知节点的平均跳距。假设未知节点m接收到n个信标节点的平均跳距，权重因子wi的表达式为：

式中：hmi为未知节点i到信标节点m的最小跳数。

未知节点的平均跳距为：

2.2 基于改进蝴蝶算法的定位优化

2.2.1 佳点集初始化种群

原始的蝴蝶优化算法在搜索空间中随机产生初始种群，从而造成初始解分布不均匀。为了使初始解分布更加均匀，本文引入佳点集初始化种群。佳点集[13]是由我国数学家华罗庚等人提出，其原理为，设Gs是s维欧式空间单位立方体，如果r∈Gs，有：

式中：{r1(n)×k}表示取小数部分。则称pn(k)为佳点集，r称为佳点。其偏差φ(n)=C(r,ε)n(-1+ε)，其中C(r,ε)为只与r,ε(ε＞0)有关的常数。取r={2cos(2π/p)}，1≤k≤s，p是满足(p-3)/2≥s的最小素数。将其映射到搜索空间，则有：

式中：ubj和lbj为种群第j维的上下界。

假设种群规模为100、空间维度为2。图2和图3分别表示随机分布和佳点集初始化的种群，可以看出由佳点集初始化的种群分布更加均匀，覆盖更加充分。x,y分别表示节点对应的横、纵坐标。

图2 随机初始化种群分布

图3 佳点集初始化种群分布

2.2.2 动态切换概率策略

p用于全局搜索和局部探索的切换。标准的BOA中的p是一个固定的值[14]，在算法的后期搜索最优个体的能力弱，易陷入局部最优，因此本文采用动态转换概率来实现全局搜索和局部搜索的转换，从而提高算法后期的寻优能力，更好平衡全局搜索和局部搜索。转换概率公式为：

式中：i，N_iter分别为当前迭代次数和最大迭代次数。

2.2.3 全局扰动因子

为了进一步加强算法的探索能力和提高收敛精度，受到正态分布的启发，在传统全局位置更新处引入全局扰动因子Ψ，其表达式为：

式中：normrnd(0,1)表示服从正态分布的随机数；
randn()表示(0,1)之间的随机数。改进后的全局位置更新公式为：

2.2.4 黄金正弦搜索策略

黄金正弦算法（Gold-SA）[15]是于2017年提出的一种新型元启发式优化算法。与传统的元启发式优化算法相比，Gold-SA算法具有鲁棒性好、设置参数少、寻优能力强等特点。另外，Gold-SA算法在位置更新的过程中融入黄金分割系数，在每次迭代过程中都充分搜索能产生优解的区域，加快了算法的收敛速度，增强了局部开发能力。

针对传统BOA算法局部搜索能力弱，无法快速准确寻找到最优解，本文引入黄金正弦算法来替代原算法的局部搜索进行寻优，提高了算法的搜索效率和定位准确性。改进后的局部搜索公式为：

式中：r1为区间[0,2π]中的随机数；
r2为区间[0,π]中的随机数。θ1和θ2的表达式为：

式中：α和β的初始值分别取-π和π；
τ为黄金分割系数

2.3 改进DV-Hop算法流程

为了提高DV-Hop算法的定位精度，本文提出了基于改进蝴蝶的DV-Hop算法。改进后的算法流程如下：

（1）在无线传感器网络中随机分布若干个节点，根据改进的DV-Hop算法得到最小跳数以及节点间的最优跳距。

（2）运用佳点集初始化种群，并设置迭代次数、蝴蝶种群数量、官能模态以及刺激强度等相关参数。

（3）根据目标函数计算种群的适应度值，并记录最佳的适应度值以及所对应个体的位置。

（4）根据式（21）和式（22）对个体位置进行更新，并且记录每次更新之后最佳个体的适应度值以及所对应的位置。

（5）如果满足迭代终止条件，则终止算法执行并且输出全局最优解以及相对应的位置，否则返回步骤4继续进行迭代优化。

为了验证本文所提出IBOA算法的有效性，利用MATLAB 2018a进行了仿真实验，并与传统的DVHop算法和文献[16]算法进行比较。如图4所示，设在100 m×100 m的方形区域内随机部署100个传感器节点，其中信标节点20个。为了增加实验结果的准确度，实验选取模拟50次的平均值作为最终的结果。

图4 网络节点随机部署

本文通过依次改变信标节点比例、节点通信半径以及节点总数来验证提出算法的性能，并且采用归一化相对误差作为定位算法的评价标准。其计算公式为：

3.1 信标节点比例对定位精度的影响

在网络区域内随机布设100个节点，保持通信半径R=20 m不变，信标节点的比例从5%变换至25%，对比3种算法，结果如图5所示。

图5 信标节点比例对定位精度的影响对比

3种算法的平均定位误差总体上均随着信标节点比例增大而减小，其中改进算法定位误差明显要低于另外两种对比算法。在信标节点比例较小时，定位误差曲线下降的幅度较大。信标节点比例增加到15%之后，曲线趋于平稳。在不同信标节点比例下，本文改进算法的平均定位精度相比传统DV-Hop算法和文献[16]算法分别提高了23.51%和4.7%。

3.2 通信半径对定位精度的影响

在网络区域随机分布100个节点，其中信标节点个数为10，通信半径R从20 m依次增加到40 m。对比3种算法，结果如图6所示。

图6 通信半径对定位精度的影响对比

3种算法的定位误差总体上随着通信半径的增加逐渐减小。当通信半径较小时，定位误差曲线下降幅度较大，当通信半径增加到20 m时，曲线开始趋于平稳。在相同条件下，本文提出的算法定位精度始终都是最高的。在不同通信半径条件下，本文改进算法平均定位精度相比传统DV-Hop算法和文献[16]算法分别提高了22.33%和2.81%。

3.3 节点总数对定位精度的影响

在网络区域内随机分布10个信标节点，保持通信半径R=20 m不变，节点总数从60增加到100，对比3种算法，结果如图7所示。

图7 节点总数对定位精度的影响对比

3种定位算法的定位误差总体随着节点总数的增加而逐渐减小。当节点总数较小时，定位误差下降幅度较大，当总数达到90以后，曲线开始趋于平稳。在不同的节点总数下，本文改进算法平均定位精度相比传统DV-Hop算法和文献[16]算法分别提高了30.35%和12.10%。

针对传统DV-Hop算法定位精度低的问题，本文提出了IBOA的无线传感器定位算法。IBOA首先采用多通信半径的方式降低信标节点间的跳数，其次通过引入修正因子降低未知节点到信标节点的平均跳距，最后使用黄金蝴蝶算法计算未知节点的坐标。实验结果表明，本文提出的IBOA算法相比传统的DV-Hop算法以及其他现有算法在定位精度上有了明显的提高。

猜你喜欢跳数信标定位精度一种基于置信评估的多磁信标选择方法及应用中国惯性技术学报(2020年6期)2020-04-06基于DDoS安全区的伪造IP检测技术研究计算机技术与发展(2019年9期)2019-09-28GPS定位精度研究智富时代(2019年4期)2019-06-01GPS定位精度研究智富时代(2019年4期)2019-06-01立式车床数控回转工作台定位精度研究制造技术与机床(2018年10期)2018-10-13RFID电子信标在车-地联动控制系统中的应用铁道通信信号(2018年3期)2018-04-19高分三号SAR卫星系统级几何定位精度初探雷达学报(2017年1期)2017-05-17跳数和跳距修正的距离向量跳段定位改进算法现代电子技术(2017年7期)2017-04-14经典路由协议在战场环境下的仿真与评测电脑知识与技术(2016年7期)2016-05-19基于信标的多Agent系统的移动位置研究长春理工大学学报（自然科学版）(2015年4期)2015-12-07