基于多通信半径和改进遗传算法的DV-Hop定位_余成成.pdf

2023 年第 2 期仪 表 技 术 与 传 感 器InstrumentTechniqueandSensor2023No2基金项目:国家自然科学基金(61540027，51174084)收稿日期:20220816基于多通信半径和改进遗传算法的 DVHop 定位余成成，徐巍，钟宇超，朱怀志(湖北工业大学机械工程学院，湖北武汉430068)摘要:针对无线传感器网络定位算法中 DVHop(distance vectorhop)算法定位精度不高的问题，从跳数和跳距两方面进行优化，提出了一种利用多通信半径和改进遗传算法优化的 DVHop 定位算法。首先，设置节点的通信半径为多个，细化节点间的跳数，降低跳数误差;其次，将局部搜索能力强的禁忌搜索算法与遗传算法相结合优化信标节点的平均跳距;最后，采用加权的方式修正未知节点的平均跳距，降低跳距误差。仿真结果表明:在同等条件下，本文改进算法比传统 DVHop 算法和有关改进算法定位精度更高。关键词:节点定位;DVHop 算法;多通信半径;遗传算法;禁忌算法中图分类号:TP393文献标识码:A文章编号:10021841(2023)02009905DVHop Localization Based on Multiple Communication adiusand Improved Genetic AlgorithmYU Cheng-cheng，XU Wei，ZHONG Yu-chao，ZHU Huai-zhi(College of Mechanical Engineering，Hubei University of Technology，Wuhan 430068，China)Abstract:Aiming at the low accuracy of DVHop(distance vector-hop)localization algorithm in wireless sensor networks，aDVHop localization algorithm optimized by using multiple communication radius and improved genetic algorithm was proposed tooptimize the hop number and hop distanceFirstly，the communication radius of nodes was set to multiple，and the hop count be-tween nodes was refined to reduce hop count errorSecondly，the tabu search algorithm with strong local search ability was com-bined with genetic algorithm to optimize the average hop distance of beacon nodesFinally，the average hop distance of unknownnodes was modified by weighting method to reduce the hop distance errorSimulation results show that the proposed algorithm ismore accurate than the traditional DVHop algorithm and other improved algorithms under the same conditionsKeywords:node positioning;DVHop algorithm;multiple communication radius;genetic algorithm;tabu algorithm0引言无线传感器网络(wireless sensor networks)的研究发展迅速，应用领域广泛，如环境监测，家居生活等方面12。节点精准定位是无线传感器网络应用的关键环节。若将无线传感器网络运用到复杂工况条件下，首先考虑以尽可能少的硬件设备完成节点精准定位。按照定位机制，有 2 种结点定位算法:基于测距(rangebased)的定位算法和无需测距(rangefree)的定位算法3。第 1 种方法是利用有关数学理论方法，要求在一定程度上依赖硬件装置获得节点间的距离和角度的数据，并对节点坐标进行计算。第 2 种方法则利用节点间的相邻关系、网络连通度即可进行定位，但定位精度有待提升。DVHop 定位算法属于后者，对硬件设施需求低，成本小，易实施。但此算法定位精度较低，误差主要体现在跳数、跳距和位置计算方面，许多学者对其改进:文献 4 提出双通信半径的策略精确化节点跳数，使最小跳数和平均跳距更加精准，改善了定位精度;王国武等5 引入偏差系数优化信标节点之间的最小跳数，并用遗传模拟退火算法优化信标节点的平均跳距，有效减小了定位误差;王磊等6 引入修正因子和权重系数修正测距值，最后使用改进鲸鱼算法计算节点坐标，定位误差明显降低;孙博文等7 通过对控制参数采取自适应调整策略改进灰狼算法，并以改进的灰狼算法估算节点位置有效提高了定位精度;范时平等8 通过加权优化平均跳距，使用改进粒子群算法估算未知节点位置，最终使得位置值更贴近真实值;余修武等9 除了采用双通信半径细化跳数，并使用最小均方误差准则和加权的方法优化平均跳距，最后，将三边测距法替换成全局人工鱼群算法，并对其进行100Instrument Technique and SensorFeb2023坐标计算，有效地提高了定位精度。在现有研究基础上，针对跳数和跳距误差，提出了一种将多通信半径与改进遗传算法结合的优化算法。该算法的主要思路是:让节点在多个通信半径内播报以细分节点之间的跳数，接着采用改进遗传算法优化信标节点的跳距，之后使用加权的方法，修正了未知节点跳距，最终明显提高了 DVHop 算法的定位性能10。1DVHop 算法及误差分析11DVHop 算法介绍111记录最小跳数信标节点将自身坐标、ID 和跳数的数据播送给通信区域内的节点，收到信息的节点将跳数加 1 继续播送。由于信息传输的途径有多种，每个节点就会收到多个到同一个信标节点的跳数数据，但只记录最小值。112获取平均跳距已知信标结点的准确位置，信标结点 i 的平均跳距由式(1)求出:Hopsizei=ij(xi xj)2+(yi yj)2ijhopij(1)式中:(xi，yi)和(xj，yj)分别为信标节点 i 和 j 的坐标;hopij为 i 和 j 之间的最小跳数。之后信标节点向网络播送包含平均跳距的数据包。同样，随着信息不断传播转发，未知节点会收到多个信标节点发来的跳距值，但只保存最近的信标节点的跳距作为它的平均跳距。113未知节点位置计算首先由式(2)估算未知节点 u 到各信标节点 i 的距离 dui:dui=Hopsizeuhopui(2)可得到如下的距离方程组:(x1xu)2+(y1yu)2=d2u1(x2xu)2+(y2yu)2=d2u2(xnxu)2+(ynyu)2=d2un(3)式中:(xu，yu)为待求坐标;(x1，y1)(xn，yn)为信标节点坐标;du1dun为未知节点 u 到各信标节点的距离。由最小二乘法可得待求坐标:X=(ATA)1ATB(4)其中A=(x1xn)(y1yn)(xn1xn)(yn1yn)(5)B=x21x2n+y21y2n+d2und2u1x2n1x2n+y2n1y2n+d2und2u(n1)(6)X=xu，yuT(7)12误差分析121跳数误差图 1 中，节点 A 的通信区域内分布着节点 B 和 C，则节点 B 和 C 到节点 A 均为 1 跳，那么对应的距离应相等，即默认均等于节点 A 的通信半径，但实际上并不相等。如果是多跳则会有更大的误差。图 1节点分布图122平均跳距误差信标节点平均跳距的计算与跳数直接相关，由于最小跳数会导致定位精度不高，因此平均跳距也会影响最终定位效果。如图 2 所示:已知节点 A 到节点 B和 C 的距离为 30 m 和 68 m，跳数为 3 跳和 4 跳，则由式(1)可得节点 A 的平均跳距为 14 m，由式(2)得节点 A 到 C 的估算距离为 56 m，与实际的 68 m 相差较大。并且未知节点平均跳距的获取仅参考了一个信标节点，然而信标节点自身的平均跳距本就不准确，最终由式(2)计算的距离也就更不准确。而且单个信标节点也不能准确反映未知节点附近的节点部署信息，因此未知节点的平均跳距也会带来误差。图 2节点分布图第 2 期余成成等:基于多通信半径和改进遗传算法的 DVHop 定位1012基于多通信半径和改进遗传算法的 DVHop 定位21多通信半径优化最小跳数从以上分析可知，最小跳数对定位精度影响很大，为得到节点间相对准确的跳数值，本文采用多通信半径的方法优化最小跳数值11。设节点的通信半径为，将通信区域划分为 m 个等间隔的同心圆，对每个圆覆盖的区域分别进行一次广播。节点间真实距离为 D，k 1，m 且为正整数，则两节点之间的跳数为:hop=1m0Dmkm(k1)mDkm1(m1)mD(8)原则上 m 越大，细化程度越高，最小跳数越精确，但每次细化会使得节点多广播一次，这就增加了节点能耗，综合考虑，本文将 m 取为 3。如图 3 所示，设通信半径 =30，则 hopAB=1/3，hopAC=2/3，hopAD=1，hopAE=4/3。图 3m=3 时广播示意图22改进遗传算法优化信标节点平均跳距本节将对遗传算法的第3 步进行改进以优化信标节点的跳距。遗传算法是模仿自然生物进化思想，按照一定的机制，在设定的解范围中从任一解出发找到全局最优解12。但是，该算法在局部搜索方面有欠缺，易出现未成熟收敛，使得解的更新处于暂停状态。由于禁忌算法邻域搜索能力较强，可跳出局部最优，因此禁忌算法与之结合优化信标节点平均跳距，补偿变异力度不够导致的局部搜索能力较差的短板13。221适应度函数选取传统的 DVHop 算法和很多改进算法计算信标节点的平均跳距均采用无偏估计准则，但均方误差准则更加合适准确14。因此本文根据最小均方误差准则构造适应度函数如下，并利用改进遗传算法求解:fitness=1ni=1nj=1(Hopsizei Hij Dij)2(9)式中:n 为信标节点总数;Hopsizei为信标节点 i 的平均跳距;Hij为经过 21 节优化后两信标节点间的跳数;Dij为两信标节点间的真实距离。文献 12 将 0，max(Dij)作为解空间寻优，然而实际上信标节点的平均跳距均匀分布在一个很小的区间内，并且这样增加了算法寻优的困难与复杂度。本文通过大量模拟实验将 6，3 作为解空间，即Hopsizei 6，3，为信标节点通信半径，本文将给出这 2 种情况和 DVHop 算法同等条件下的误差对比图。通过算法找出适应度最大的一组平均跳距。222选择根据每个个体的适应度值大小进行选择，选择的方式有多种，本文采用轮盘赌算法。个体 M 被选中的可能性大小由式(10)确定:PM=fMKL=1fL(10)式中:K 为个体的总量;fM为个体 M 的适应度，1MK;分母表示 K 个个体适应度之和。在每次选择中都随机生成 1 个 0，1的概率数，与 PM作比较，判断个体是否被选择，整个过程中保持种群数量不变。223交叉2 个具有双亲部分基因的新染色体通过 2 个父代染色体杂交产生的过程称为交叉。具体是将选择后种群中的个体无规律两两组合，之后随机将每一对个体中某个相同位置的基因作为交叉标记点，将标记点后的部分基因以某概率交换生成新一代个体。224变异禁忌先根据概率对交叉后的个体变异。对禁忌算法来说，一个较好的初始解能得到更好的搜索结果，因此将变异后的每个个体作为禁忌算法的寻优起始解。先由起始解按照设定