徐同伟，何 庆，吴意乐，顾海霞

(贵州大学大数据与信息工程学院，贵阳550025)

基于自适应ABC/FOA融合定位算法研究*

徐同伟，何 庆*，吴意乐，顾海霞

(贵州大学大数据与信息工程学院，贵阳550025)

针对传统无线传感网络(WSN)节点定位算法定位慢、误差大的问题，提出了一种基于自适应ABC/FOA融合定位算法。该算法既吸收了ABC算法的全局寻优能力强的优点，又保留了FOA算法局部搜索能力强的特点;同时，引入自适应概念，对果蝇步长进行控制，提高种群多样性;接下来，对节点定位误差函数进行改进，提高了节点定位误差的区分度。仿真结果表明，利用自适应ABC/FOA融合定位算法以后，定位时间明显缩短，定位误差明显减小，能够满足工程领域对于定位精度的要求。

无线传感网络;定位算法;果蝇优化算法;人工蜂群算法;自适应

无线传感网络WSN(Wireless Sensor Network)是由传感器、单片机和无线通信设备共同组成的短距离无线通信技术［1］，因其成本低、功耗小、组网简单，被广泛应用于无线数据采集中。无线节点定位是实现数据采集的关键技术，然而，定位误差是影响无线节点定位的首要因素［2－3］。定位算法［4－5］一般分为基于测距的定位算法(Range-Based)和无需测距的定位算法(Range-Free)。基于测距的定位算法精度较高，在目前的工程领域应用较多，常用的定位方法有三边测量法、三角测量法和最大似然估计法。其中，WSN节点间的距离根据信号传输的时间(TOA)、信号传输的时间差(TDOA)、信号到达的角度(AOA)和节点接收到的信号强度(RSSI)等方法进行测量。张远［6］针对节点定位仅限于2D中，对邻节点的距离和角度信息研究，详细阐述了基于角度和信号强度的测距方法，将节点定位扩展到3D定位中;杨文铂等［7］为提高节点定位精度和环境适应性，修正了定位误差，使RSSI测距方法更精确;郄剑文等［8］将RSSI和TDOA测距方法组合，并进行一定的改进，提高节点定位精度。本文采用RSSI测距方法进行测距，对三边测量法的定位误差进行优化，提高定位误差区分度和定位精度。

群智能优化算法［9］是模仿生物界进化或者寻找食物原理提出的，研究学者常常用它来求解全局最优问题，常用的有遗传算法、蚁群算法、粒子群算法、人工蜂群算法、果蝇优化算法。赵雁航等［10］用改进的粒子群算法对定位算法中多边测量法进行迭代寻优，提高了定位精度，但是粒子群算法容易陷入局部最优，而且计算量大，增加网络节点的开销;吴意乐等［11］对粒子群算法进行自适应改进，提高种群的多样性，并对WSN覆盖策略进行优化，提高网络资源的利用率;梁美玉等［12］用蚁群算法对三边测量法的误差函数进行优化，来获得更高的定位精度，但是蚁群算法计算速度慢，易陷入局部最优，不适合WSN定位算法简单、高效的环境;李牧东等［13］将改进的人工蜂群算法运用到DV-Hop算法中，对未知节点的估计坐标进行优化，得到更精确的估计坐标，但是人工蜂群算法局部搜索能力不足，影响定位算法的精度;虞继敏等［14］将果蝇优化算法应用到节点定位中，通过迭代寻优，缩小未知节点与信标节点之间的距离误差，提高定位精度，但是果蝇算法容易陷入局部最优且误差函数区分度小，造成定位误差增大。

本文提出了一种基于自适应ABC/FOA融合定位算法进行WSN节点定位，该算法将人工蜂群算法和果蝇优化算法融合，在保留果蝇优化算法局部搜索能力的基础上，提高算法全局寻优的能力;同时，依据最优解未更新次数对果蝇步长自适应控制，并将改进的算法应用到三边测量法［15］中，找到定位误差最小的估计坐标;接下来，对三边测量法的定位误差函数进行改进，将定位误差进行分段处理，提高了不同估计坐标误差的区分度。通过仿真结果证明，改进的算法能较好的跳出局部最优，能较为高效的进行节点定位;同时证明，改进的误差函数使得节点定位更精确。

1 自适应ABC/FOA融合算法

人工蜂群算法ABC(Artificial Bee Colony Algorithm)［16］计算简洁、收敛速度快，且具有较强的全局寻优能力;果蝇优化算法FOA(Fruit Fly Optimization Algorithm)［17－18］具有参数少、算法简单、容易实现等优点。目前主要应用于神经网络参数训练、支持向量机参数优化、TSP路径优化、WSN路由算法优化、WSN定位算法优化等方面。

本文针对果蝇优化算法易陷入局部最优的缺点，结合人工蜂群算法较强的全局寻优能力，并使用最优解未更新次数Flag对果蝇步长进行自适应控制，提出了自适应人工蜂群/果蝇优化融合算法(ABC/FOA)。本文利用自适应ABC/FOA融合算法对WSN节点定位误差进行优化，具体优化策略将在3.2节进行详细阐述。算法流程如下:

S1:初始化 随机初始化果蝇群体位置(X_axis，Y_axis)，设定迭代次数Maxgen、种群规模Sizipop、随机搜索半径R、最优解未更新次数阈值mFlag，并置最优解未更新次数标志Flag为零。

S2:随机搜索 果蝇个体(Xi，Yi)在自适应搜索半径范围内，利用嗅觉随机搜索食物源，即对问题的可行解进行自适应随机搜索。

S3:计算味道浓度判定值 首先计算果蝇个体到原点的距离Di，然后求味道浓度判定值Si。

S4:计算适应度值 利用味道浓度判定值，计算味道浓度函数或适应度函数Function()中，得到果蝇个体坐标的味道浓度Smelli。

S5:找出当代最优 通过贪婪选择法找出果蝇群体中味道浓度最小的果蝇。

S6:判断味道浓度是否优于上一代的味道浓度值，若是则执行步骤S7，否则跳到步骤S8。

S7:更新最优点 保留最小的味道浓度值和果蝇种群位置，果蝇群体利用视觉飞往该位置，并将最优解未更新次数标志Flag置为零，跳到步骤S10。

S8:记录最优解未更新次数，并保留上一代最优值，果蝇群体位置不变。

S9:判断次数标志是否达到阈值mFlag，若是，则在可行解范围内生成果蝇群体位置(侦察蜂变异)，并置最优解未更新次数标志Flag为零，执行步骤S10，否则，直接跳到步骤S10。

S10:判断是否达到算法最大迭代次数，若达到，则算法结束，输出最优值，否则继续迭代执行算法。

自适应ABC/FOA融合算法流程图如图1所示。

图1 自适应ABC/FOA融合算法流程图

在自适应ABC/FOA融合算法中，引入人工蜂群算法中的产生侦察蜂的阈值mFlag与最优解未更新次数标志Flag和侦察蜂的变异方式，共同对算法陷入局部最优的次数进行限制，能有效解决FOA算法易陷入局部最优的问题。阈值mFlag由算法应用的对象决定，如果mFlag设定过大则算法改善甚微，设定过小则局部搜索能力减弱，需要根据具体情况确定mFlag的值，本文根据经验值将mFlag设定为种群规模和问题维数的乘积［19］。在大多数文献中，为了增强算法的局部搜索能力，由适应度值来改变进化的步长;为了提高算法的全局寻优能力，会根据迭代次数来控制步长;针对本算法的情况，为提高种群多样性，避免算法陷入局部最优，本文提出使用Flag对步长进行控制，对步长自适应处理。

2 定位误差函数改进与算法实现

本文将自适应ABC/FOA融合算法应用到三边测量法中，将未知节点的估计坐标(即可行解)作为食物源，对定位误差进行迭代寻优，提高定位精度。三边测量法是利用几何方法计算的定位方法，根据锚节点的位置和未知节点到各锚节点的距离，对未知节点的位置进行估计。其中，锚节点位置已知，未知节点到各锚节点的距离利用RSSI测距方法进行测量。

2.1 定位误差函数改进

在大多数文献中，将未知节点的估计坐标(^x，^y)到各锚节点的距离与测得距离之间的差值求平均后，当作误差函数，如式(14)所示。当定位精度要求较高，则对计算工具的要求较高;并且，当分别代表着局部最优和全局最优的估计坐标的定位误差都很小时，可能因未发现这细小的误差，而使算法陷入局部最优，这就需要提高定位误差的区分度，避免算法陷入局部最优。为了提高定位误差的区分度，本文对误差函数进行改进，如式(15)所示。当误差小于1时，不同估计坐标的定位误差可能很小，因此，求定位误差的倒数，提高定位误差的区分度;当误差大于1时，不同的定位误差相对大一些，求定位误差的负数，这样就将求解函数的最小值，变为求解最大值问题。改进的误差函数，对于不同定位误差的差别很小时，加大了不同定位误差的区分度，提高了定位精度和探索能力。

式(15)中ε'值与定位误差负相关，当ε'取得最大值，即定位误差函数最小时，未知节点的估计坐标最精确，本文利用自适应ABC/FOA融合算法，对误差函数进行迭代寻优，找到定位误差最小的估计坐标。

2.2 自适应ABC/FOA融合定位算法

在自适应ABC/FOA融合算法中，将到源节点的距离求倒数后作为味道浓度判定值，然后代入适应度函数，寻求最优味道浓度。在WSN节点定位算法中，对距离Di、味道浓度判定值Si和味道浓度函数Smelli进行相应的改变，以适应WSN节点定位算法。设Dij为果蝇个体i的估计坐标(^xi，^yi)到锚节点j的定位误差，则

本文将未知节点的估计坐标到锚节点j的定位误差Dij代入到式(14)的定位误差中，得到果蝇个体i的节点定位误差Si，即新的味道浓度判定值Si。

式中:n(n≥3)为锚节点个数，i(1≤i≤Sizepop)为果蝇个体i。

将新的味道浓度判定值Si，代入适应度函数，求解味道浓度Smelli，使节点定位误差最小，找到精确的定位坐标;同时，为了解决不同定位误差之间区分度小的缺陷，根据式(15)，适应度函数可表述为:

式中:i(1≤i≤Sizepop)为果蝇个体i。

自适应ABC/FOA融合定位算法对式(18)进行迭代寻优，即基于改进误差函数的自适应ABC/FOA融合算法。该算法通过寻找Smell()函数的最大值，即定位误差的最小值，得到定位精度最高的未知节点估计坐标。

3 实验仿真与分析

本文采用MATLAB对算法进行仿真，通过对比分析不同算法的定位精度和性能，来验证自适应ABC/FOA融合算法的优越性、改进误差函数的有效性和自适应ABC/FOA融合定位算法的高效性。

3.1 改进算法的优越性分析

文献［14］将果蝇优化算法应用到WSN节点定位算法中，但果蝇优化算法容易陷入局部最优，本节将自适应ABC/FOA融合算法与其进行对比，评价自适应ABC/FOA融合算法的优越性。

本节利用节点定位算法，对节点P(1.5，1.5)进行仿真定位，假设3个锚节点的坐标为A(0，0)、B(3，1)、C(1.5，3)，则定位节点到锚节点的距离分别为rA=在实际定位中通过RSSI等测距方法得到)。自适应ABC/FOA融合算法中，种群规模Sizepop=30，算法迭代次数Maxgen=300，随机搜索半径R=1 m，次数标志阈值mFlag=60，采用式(15)的定位误差进行对比。仿真结果如下:

如图2所示，上半部分为利用FOA算法求得的最小定位误差的仿真曲线，下半部分为自适应ABC/FOA融合算法的仿真曲线。从图2可以看出，自适应ABC/FOA融合算法当定位误差不进行更新时，跳出局部最优，寻求更好的定位节点坐标。所以，自适应ABC/FOA融合定位算法减小了定位误差，较为精确地获得未知节点的坐标。

图2 FOA算法与自适应ABC/FOA融合算法对比

图3是分别利用文献［10］中的算法和本文中的算法，不同锚节点的情况下，对节点进行定位，得到的锚节点的定位误差曲线。因此，在WSN定位算法中，自适应ABC/FOA融合算法比FOA算法定位精度更高。

图3 不同算法、不同锚节点定位对比

3.2 改进误差函数的有效性分析

本节将改进的误差函数和未改进的误差函数分别带到自适应ABC/FOA融合算法中，对仿真结果进行比较，验证改进的误差函数的有效性。

图4 误差函数改进前后对比

从图4可以看出，基于改进误差函数的自适应ABC/FOA融合算法，即自适应ABC/FOA融合定位算法，定位误差区分度高，收敛速度快，能够较快找出更小的定位误差，所以，改进的误差函数是有效的，并且提高了定位精度。

3.3 改进算法的高效性分析

本节将从定位误差、定位时间两个方面对算法的高效性进行分析，使用多个锚节点进行仿真，并将蚁群算法(ACO)、粒子群算法(PSO)、FOA算法和自适应ABC/FOA融合算法获得的最小定位误差进行对比，分析改进的定位算法的优越性。

对上述4种算法多次仿真，得到定位误差对比表(表1)。从表1可以看出，自适应ABC/FOA融合定位算法误差最小，且随着锚节点个数的增加，定位误差有一定改善，在图3中也有体现。在仿真实验中，只有一个未知节点，锚节点个数对于定位误差影响不大，在实际网络环境中，未知节点个数多于锚节点个数，随着锚节点个数的增加，定位误差将明显减小，后期将做进一步研究。

表1 定位误差对比表

从表2可以看出，FOA算法的定位时间明显优于ACO和PSO算法;自适应ABC/FOA融合定位算法定位时间虽然稍高于FOA算法，但还是明显优于其他两个算法;而且定位精度比FOA算法提高了1倍，所以，毫秒级的时间损失还是可以接受的。

表2 定位时间对比表

4 结束语

本文针对FOA算法易陷入局部最优的缺点，综合考虑ABC算法全局寻优能力强和FOA算法简单高效的优点，同时，为增加种群多样性，利用最优解未更新次数Flag对果蝇步长自适应控制，提出了自适应ABC/FOA融合算法。在WSN节点定位算法中，三边测量法的误差函数由于区分度不高，影响定位精度，本文对误差函数进行改进，提高了不同估计坐标间定位误差的区分度。本文将改进的误差函数作为自适应ABC/FOA融合算法的适应度函数，得到自适应ABC/FOA融合定位算法，找到最小定位误差的估计坐标，减小了定位误差，提高了定位算法的精确度。仿真结果表明，自适应ABC/FOA融合算法具有较强的跳出局部最优的能力，并且算法简单、计算速度快、容易实现，应用到WSN节点定位算法可行性高，对硬件要求低;改进的误差函数增加了定位误差的区分度，对于定位精度的提高是有效的。自适应ABC/ FOA融合定位算法具有较好的优越性和高效性，不仅定位时间明显缩短，而且定位误差明显减小，能够满足工程领域对于定位精度的要求。

［1］ 青岛东合信息技术有限公司.无线传感器网络技术原理及应用［M］.西安:电子科技大学出版社，2013.

［2］ 王晟.无线传感网络节点定位与覆盖控制理论及技术研究［D］.武汉:武汉理工大学，2006.

［3］ Xu L，Deng Z，Ren W，et al.A Location Algorithm Integrating GPS and WSN in Pervasive Computing［C］//Third International Conference on Pervasive Computing and Applications，2008.ICPCA 2008.IEEE，2008:461－466.

［4］ 田孝华.无线电定位理论与技术［M］.北京:国防工业出版社，2011.

［5］ 彭宇，王丹.无线传感器网络定位技术综述［J］.电子测量与仪器学报，2011，25(5):389－399.

［6］ 张远.基于距离和角度信息的无线传感网节点定位问题研究［D］.山东大学，2012.

［7］ 杨文铂，邢鹏康，刘彦华.一种基于自适应RSSI测距模型的无线传感器网络定位方法［J］.传感技术学报，2015(1):137－141.

［8］ 郄剑文，贾方秀，李兴隆，等.基于组合测距的无线传感器网络自定位算法［J］.传感技术学报，2016(5):739－744.

［9］ 梁艳春.群智能优化算法理论与应用［M］.北京:科学出版社，2009.

［10］赵雁航，钱志鸿，尚小航，等.基于跳距修正粒子群优化的WSN定位算法［J］.通信学报，2013，34(9):105－114.

［11］吴意乐，何庆，徐同伟.改进自适应粒子群算法在WSN覆盖优化中的应用［J］.传感技术学报，2016，29(4):559－565.

［12］梁美玉，李莉，陈坤.基于蚁群算法的井下无线传感器网络节点定位研究［J］.煤矿机械，2010，31(12):48－50.

［13］李牧东，熊伟，梁青.基于人工蜂群改进算法的无线传感器网络定位算法［J］.传感技术学报，2013，26(2):241－245.

［14］虞继敏，王海云，唐贤伦.改进果蝇优化算法的WSNs节点定位方法［J］.微电子学与计算机，2014(11):111－115.

［15］高雷，郑相全，张鸿.无线传感器网络中一种基于三边测量法和质心算法的节点定位算法［J］.重庆工学院学报(自然科学版)，2009，23(7):138－141.

［16］Karaboga D.An Idea Based on Honey Bee Swarm for NumericalOptimization［R］.Technical Report－tr06，Erciyes University，Engineering Faculty，Computer Engineering Department，2005.

［17］潘文超.果蝇最佳化演算法［M］.台北:沧海书局，2011.

［18］Wen-Tsao P.A New Fruit Fly Optimization Algorithm:Taking the Financial Distress Model as an Example.Knowledge-Based Systems，2012，26:69－74.

［19］张超群，郑建国，王翔.蜂群算法研究综述［J］.计算机应用研究，2011，28(9):3201－3205.

徐同伟(1991－)，男，山东滕州人，贵州大学硕士生，主要研究方向为认知无线网络、无线传感网络、群智能优化算法;

吴意乐(1991－)，男，江苏苏州人，贵州大学硕士生，主要研究方向为无线传感网络、群智能优化算法;

何 庆(1982－)，男，贵州都匀人，博士，贵州大学副教授，主要研究方向为认知无线网络、无线传感网络、群智能优化算法，16353735@qq.com;

顾海霞(1993－)，女，江苏泰州人，贵州大学硕士生，主要研究方向为无线传感网络、认知无线网络、群智能优化算法。

Research on the Localization Algorithm Based on Adaptive ABC/FOA Fusion*

XU Tongwei，HE Qing*，WU Yile，GU Haixia
(College of Big Data and Information Engineering，Guizhou University，Guiyang 550025，China)

In order to solve the tardiness and big error of traditional node localization algorithm in wireless sensor network(WSN)，a new localization algorithm based on adaptive ABC/FOA fusion is proposed.In this algorithm，not only is the global optimizing capacity of ABC algorithm absorbed，but also the strong local searching ability of FOA algorithm is remained.At the same time，the adaptive concept is introduced to control the step size of fruit fly and to improve the diversity of the population.And then，to increase the partition degree of node localization error，the error function of node localization is improved.The simulation shows the promising results:This algorithm can shorten the localization time significantly，decrease the localization error obviously，satisfy the engineering requirement of localization accuracy，and so on.

wireless sensor network;localization algorithm;fruit fly optimization algorithm;artificial bee colony algorithm;adaptive

C:6150P;7230

10.3969/j.issn.1004－1699.2017.02.019

TP393;TP301.6;TN92

A

1004－1699(2017)02－0278－06

项目来源:贵州省教育厅青年科技人才成长项目(黔教合KY字［2016］124);贵州省科技厅项目贵州省科技计划课题项目(黔科合LH字［2014］7628);贵州大学引进人才科研项目(贵大人基合字［2010］010);贵州大学研究生创新基金项目(研理工2017012)

2016－05－28 修改日期:2016－07－14