隹Isl^iSls V12021年第02期(总第218期)西藏英文
基于改进灰狼优化算法的DV-Hop定位算法
王冠锂，邹立颖
(齐齐哈尔大学通信与电子工程学院，黑龙江齐齐哈尔161006)
摘要：针对无线传感器网络节点DV-Hop定位算法由于节点分布不均，距离估计不准确，导致定位精度较低的问题，提出了一种基于改进灰狼优化算法的DV-Hop定位算法，采用先进的灰狼优化算法以寻找最优值的方式得到未知节点、坐标。同时，为进一步提高优化算法的寻优能力，克服可能出现局部最优的情况，将优化算法与免疫算法相结合，提高优化算法中灰狼种群的多样性，进而提高对最优解的搜索能力，达到提高定位精度的目的。实验结果表明，相对于普通的DV-Hop 定位算法和普通的灰狼优化算法，改进之后的定位算法精度更高。
关键词：无线传感器网络；节点定位;DV-HOP；灰狼优化；免疫算法
中图分类号:TP393文献标识码:A文章编号：2096-9759(2021)02-0061-03
DV-hop localization algorithm bad on improved gray wolf optimization algorithm
Wang Guanyu,Zou Liying
(College of Telecommunication and Electronic Engineering,Qiqihar University,Qiqihar161006China) Abstract:Aiming at the problem of low positioning accuracy caud by uneven distribution of nodes and inaccurate distance estimation in wireless nsor network node DV hop localization algorithm,a DV hop localization algorithm bad on improved gray wolf optimization algorithm is propod,which us the advanced gray wolf optimization algorithm to find the optimal value to obtain the unknown node coordinates.At the same time,in order to further improve the optimization ability of the optimization algorithm and overcome the possible local optimal situation,the optimization algorithm and immune algorithm are combined to improve the diversity of gray wolf p opulation in the optimization algorithm,and then improve the arch ability of the optimal solution,so as to improve the positioning accuracy.The experimental results show that,compared with the ordinary DV hop localization algorithm and the common gray wolf optimization algorithm,the improved localization algorithm has higher accuracy.
滑梯 英文
Key words:wireless nsor network;node location;DV-HOP;Grey wolf optimization;Immune algorithm
无线传感器网络以其具有的数据釆集、无线传输和自组织组网等工作特点在各个领域中得到了广泛的
应用叫在当今智能社会中，需要釆集大量的信息进行分析和处理，为人们的生活提供便利，而其中的位置信息则是进行信息处理的前提和基础，只有将获得的数据和位置信息结合起来进行传回才有意义121O无线传感器网络定位算法主要分为基于测距和无需测距两大类，其中基于测距算法对硬件和环境有一定的要求，定位精度较高。而无需测距算法对硬件和环境要求较低，应用更加广泛，但是精度较低叫无需测距算法中的DV-HOP算法以其实现容易、信标节点密度要求低、通信和计算开销小等特点得到了越来越多的应用叫为进一步提高定位精度，许多学者也对该算法进行了深入研究，在计算节点距离过程中通过运用加权、融合通信过程的参数和设置可信度等手段提高距离估算精度。节点坐标的计算中以优化算法代替极大似然估计方法，提高节点位置计算的精度，但由于优化算法容易陷入局部最优，在定位精度上还有提升空间。
本文提出的改进DV-HOP定位算法通过灰狼优化算法寻找未知节点坐标的最优值，克服极大似然估计误差较大的缺点。应用灰狼优化算法时，与免疫算法相结合，通过计算灰狼个体的免疫选择概率，保留适应度高、浓度低的个体，提高灰狼种群的寻优能力，进一步提高定位精度。
会计师从业资格证考试时间
1DV-HOP定位算法
DV-Hop(Distance Vector-Hop)定位算法主要包含三个阶段：
第一阶段：信标节点向所有可以通信的节点发送包含自身位置和跳数的信息，其他节点收到后转发。
最终网络中的所有节点都能得到距离每个信标节点的最小跳数。
第二阶段：根据第一阶段节点间的实际距离和最小跳数估算出网络中节点间的每一跳的平均距离。
第三阶段：根据信标节点的坐标和未知节点到信标节点的距离，利用极大似然估计未知节点坐标，完成定位。
DV-HOP定位过程是依靠网络中节点之间的通信完成的，对硬件要求不高，实现简单。但是定位过程中也存在较大的定位误差，误差主要来源于第二阶段节点之间的距离估计和第三阶段根据节点间距通过极大似然估计法求解未知节点坐标。
2改进算法
本文主要针对定位算法的第三阶段进行改进，通过灰狼优化算法通过寻找最优解的方式得到未知节点坐标，考虑到
收稿日期：2020-12-28
基金项目：黑龙江省省属高等学校基本科研业务费科研项目(项目编号:135309454)
作者简介：王冠锤(1994-)，男，硕士，助教，主要研究方向：信息智能检测理论与技术；邹立颖(1980-)，女，博士，副教授，主要研究方向：飞行器控制，非线性控制。
61
灰狼优化算法容易陷入局部最优，影响精度的问题，将免疫算法与灰狼优化算法相结合，通过免疫选择保留亲和度髙但浓度低的解，提高解的多样性，进而提高定位精度。
2.1灰狼优化算法
灰狼优化算法是一种新型群体智能算法，以其模拟灰狼捕食过程而得名叫算法思想是按照最优解将狼群分为4类：a、p、&、3,a、队Y三类等级较高，负责引导3对最优解进行搜索，在搜索中更新a、p、&、3，最终将a作为最优解输出。运用灰狼优化算法定位时，未知节点坐标作为求解对象，也就是最优解，灰狼优化算法实现步骤为：
(1)初始化灰狼种群，随机生成M个未知节点坐标，将M 个未知节点坐标作为灰狼个体；
四年级英语上册教案(2)划分社会等级，将灰狼按解的适应度值从小到大排序，前三名分别设置为a，卩和6狼，其余为3狼。适应度函数为：
cinderella什么意思
乃尸-(1)
/-l
式中(x”yj为灰狼个体坐标,a,»)为信标节点的坐标，审为信标节点和灰狼个体之间距离,n为信标节点个数。
(3)更新灰狼个体位置，由a，陣引导韵g进行追捕猎物，即对每组解进行更新叫
D a^xM-x(f)
•勺(')-X(r)(2)
D s=\C3X s(t)-X(f)
■X2(f+l)=X/l(t)-A2D fi(3)
()=X|0+1)+X2(r+1)+X3(r+1)
''3(4)式中：为当前的迭代次数;X(什1)为更新后灰狼的位置，
和为其它灰狼3与a，卩和5狼的距离。A和C的计算公式为
\A-2ari-a(5)
C=(6)式中:a的值从2线性递减到0；“和『2为区间［1,0］的随机向量。honesty is the best policy
重复进行上述优化过程，达到迭代次数后，将最优解作为未知节点坐标输出。
灰狼优化算法具有原理简单，参数设置少，容易实现等特点，与其他优化算法一样，搜索结果可能陷入局部最优值的情况叫
2.2免疫算法
2013六级作文免疫算法起源于自然界中的免疫系统，将目标函数的解作为抗体，目标函数的特征作为疫苗。算法通过抽取疫苗和免疫选择两个步骤实现。抽取疫苗是将目标函数中最优的M个解选取出来，引导求解过程求出最优解。同时随机生成N个解，增加解的多样性。免疫选择是通过构造选择概率函数，对(M+N)个解进行评价，挑选出亲和度高，浓度低的解，抑制亲和度低，浓度高的解，能够保证目标函数解的多样性，提高对最优解搜索能力叫若将灰狼优化算法与免疫算法相结合，提高灰狼种群的寻优能力，进而达到提高定位精度的目的。
免疫选择概率函数构造是免疫算法的关键，免疫选择综合考虑适应度、浓度，保证解的多样性。
(1)亲和度函数
亲和度表明当前解与最优解的相似程度，当前解x与最优解越接近，亲和度越高。在定位过程中，亲和度函数A3)为:
心)=£-(7)
可见适应度函数越小，待求解与最优解越接近，亲和度越大。
tickets(2)浓度函数
当前解与其它解的相似程度解，相似程度越高，浓度越高，多样性越差呗。浓度函数为：
%"垃吐7⑻
(3)免疫选择概率
免疫选择概率表示当前解被选中参与计算最优解的概率，与亲和度和浓度有关，首先应对适应度和浓度归一化计算得到对应的概率：
%(Q=(9)
免疫选择概率用亲和度的概率和浓度概率加权表示;
尺齐)=禺(齐)+(1-咖(£)(10)通过调节P，将亲和度高，浓度低的抗体选择概率设置的高一些，有助于将更加接近最优解的抗体选出来，提高抗体的多样性，提高算法的寻优能力。
2.3改进灰狼优化算法DV-HOP定位过程
改进灰狼优化算法DV-HOP定位过程如下：
(1)启动无线传感器网络，收集信标节点之间的跳距，计算网络中每一跳平均距离；
(2)收集未知节点到信标节点的最小跳数，计算未知节点到信标节点的距离；
(3)初始化灰狼种群，随机生成M个灰狼个体；
(4)计算灰狼个体的适应度，根据适应度划分灰狼等级；
(5)更新灰狼个体位置；
(6)随机生成N个灰狼个体，与步骤3)中灰狼个体混合，根据式6~8，计算M+N个灰狼个体的选择概率，选择概率按大小排序，选择前M个灰狼个体；
(7)如果达到迭代次数，输出a狼代表的位置坐标，否则返回步骤4)。
3实验与仿真
3.1仿真环境设置
为了验证本文提出的改进灰狼优化DV-HOP定位算法的性能，利用MATLAB软件进行仿真实验，试验区域设置为lOOmxlOOm的正方形区域。分别进行普通DV-HOP定位算法、普通灰狼优化DV-HOP定位算法和本文提出的改进灰狼优化DV-HOP定位算法。为了提高实验结果的可靠性，重复实验30次，取平均值作为实验结果。算法归一化定位误差为:
E=-i=l-------------------------------------
NxR
式中：a”》)为定位算法计算得到的未知节点坐标,(*强)为未知节点的实际坐标。”为未知节点的个数,r为节点的通信半径。
62
3.2仿真分析
(1)信标节点比例对定位精度的影响
设置节点的通信半径2?=30m，改变信标节点所占的比例，验证信标节点比例对定位精度的影响，实验结果如图]所示。随着信标节点比例的增加，定位误差逐渐减小，这是因为信标节点数量越多，对每跳距离的估算越准确，解出的位置节点坐标越准确。当信标节点比例相同时，改进灰狼优化DWHOP 定位算法的定位误差量小。
图1信标节点比例对定位精度的影响
(2)通信半径对定位精度的影响
将30个节点作为信标节点，改变通信半径，验证通信半径对定位精度的影响，实验结果如图2所示。当通信半径小于30m时，随着通信半径的增加，网络连通度变好，对节点间距的估计更加准确，定位误差逐渐减小。当通信半径大于30m时，定位误差变化缓慢甚至出现微小上升，这是由于通信半径增大，每跳距离增大，对每跳距离的估计误差增大，同时网络内的通信量也会增加，可见通信半径并非越大越好。同时可以看出，改进灰狼优化DV-HOP定位算法的定位误差小于灰狼优化DV-HOP定位算法和普通DV-HOP定位算法。
图2通信半径对定位精度的影响
(3)节点数量对定位精度的影响
设置节点的通信半径430m，选择30%的节点作为信标节点，改变节点数量，验证节点数量对定位精度的影响，实验结果如图3所示。随着节点数量的增加，定位误差呈下降趋势，当通节点总数超过200时，定位误差下降平缓。改进灰狼优化DV-HOP定位算法的定位精度优于灰狼优化DV-HOP定位算法和普通DV-HOP定位算法。
035
DV-HOP
换犯优化dv-hop
说唱英文
本文算法
°50100150200250300
信标节点数倉个
图3信标节点数■对定位精度的影响
4结语
本文在分析DV-HOP定位算法的工作原理和误差来源的基础上，运用灰狼优化算法计算未知节点坐标，并且针对灰狼优化算法存在局部最优问题，结合免疫算法，计算每个灰狼个体的免疫选择概率，选择出适应度好，浓度低的个体，保证灰狼个体的多样性，提高算法的寻优能力，提高定位精度。实验结果表明改迸算法与灰狼优化DV-HOP定位算法和普通W HOP定位算法相比，提高了定位精度。但是与两种算法相比，算法的复杂度有所提高，后期的研究应注重提高算法的效率。参考文献：
[1]GHASEMIM,AZARNIA M,JAMALIM,et al.Wireless
nsor networks localization algorithms:a comprehensive survey[J].International Journal of Computer Networks Communications,2013,5(6)：748-755.
[2]程超，钱志鸿，付彩欣，等.一种基于误差距离加权与跳段
算法选择的遗传优化DV・Hop定位算法[J].电子与信息学报,2015(10):136-141.
[3]Kumar S,Lobiyal D K.Power efficient range-firee locali
zation algorithm for wireless nsor networks[J].Wireless Networks,2014,20(4):681-694.
[4]CUI Z.SUN B.al.A novel oriented cuckoo
arch algorithm to improve DV-Hop performance for cyberPhysical systems[J].Journal ofPaiallel Distributed Computing,2016,103.
[5]王磊，巫韦华，齐俊艳，等.基于跳距修正与差分进化优化
的改进DWHop定位算法[J].重庆邮电大学学报(自然科学版),2020,032(01):113-120.
[6]孙博文，韦素媛.基于自适应调整策略灰狼算法的DV-
Hop定位算法[J].计算机科学,2019,046(5):77-82.
[7]石琴琴，徐强，张建平.基于距离修正及灰狼优化算法对
DV-Hop定位的改进[J].传感技术学报,2019.
[8]朱海波，张勇.基于差分进化与优胜劣汰策略的灰狼优化算
法[J].南京理工大学学报(自然科学版)，2018,042⑹: 678-686.
[9]吴珍珍，方旺盛.免疫粒子群优化的DWHop定位算法[J].
信息技术与网络安全,201&37(4):88-91.
veteranworker
[10]胡诚，肖本贤•基于自适应免疫粒子群优化的DWHop定
位算法[J].传感器与徹系统,2020,039(001):121-124.
63
