基于人工鱼群算法的dv-hop定位算法改进研究

韦世雄

摘要：随着无线网络传感器在各行各业的广泛应用，实际应用场景中的许多问题逐渐浮现出来，尤其是定位算法缺陷。文章主要从无线传感器定位的dv-hop算法局限性出发，指出其用跳段距离代替直线距离的显著缺点，并基于各项研究，提出应用人工鱼群算法的全局密集网络特点对dv-hop定位算法进行改进。经验证，基于人工鱼群算法改进后的dv-hop定位算法能显著弱化无线传感器节点定位误差大，减少节点硬件开销，提升无线传感器的定位精度和效率。

关键词：人工鱼群算法；dv-hop；定位算法；无线网络传感器

中图分类号：TN915.03

文献标志码：A

0 引言

随着定位技术的发展，在计算机视觉领域中，位置信息作为重要的数据挖掘依据与问题处理过程参照，受到越来越多的学者关注。无线网络传感器的重要内容之一就是定位算法。传统的定位算法主要是dv-hop算法，其具有实现简单、节点无需额外增加硬件要求的优势。

在具体的应用和发展过程中，dv-hop的一些缺陷也逐渐随着应用场景的增加和需求的变换浮现，这些问题严重影响着无线网络传感器的定位精度、连接效率和应用体验。

1 dv-hop定位算法在当前应用场景中出现的问题

dv-hop作为定位算法中的经典代表之一，其节点定位是基于非测距的，即用跳段距离代替直线距离。应用这种定位方式的不足是定位精度低，即在计算平均跳距和定位坐标的时候容易产生误差。

2 dv-hop定位算法精度不佳的原因分析

这种误差主要出现于估算位置节点坐标的场景下，未知节点在估算距离时常常依赖最近锚节点的平均跳距，对网络中节点位置密度有很大的限制要求。研究人员可先从dv-hop定位算法的具体步骤特点展开讨论。

2.1 dv-hop定位算法的定位步骤

关于dv-hop定位算法的误差分析要先了解dv-hop定位的具体步骤。其定位过程一般分为以下几个步骤。

第一步，锚节点通过无线网络传感器向全网节点发送数据信息，相应的节点在接收到信息后，会通过更新最小值来获得锚节点的最小跳数。

第二步，测算锚节点和未知节点之间的距离。不同的节点都会通过周围通信锚节点的坐标信息和位置数据来计算自身的平均跳距。

第三步，在估算自身节点位置的时候，普通节点往往使用的方式是三边测量法或者最小二乘法。

2.2 误差分析

本研究提出的对dv-hop定位算法的误差分析侧重从其定位步骤展开^［1］。

首先，通信半径内节点的值恒定。不论采用何种定位算法，其节点都是随机分布的。在通信半径之内，节点之间所有的距离都被记为1跳，经过不断叠加，节点越少，误差就越大。

其次，考虑平均距离的影响。这种定位算法将平均跳距和最小跳数的乘积作为节点间实际距离的计算方式。如果平均距离原本就存在误差，那么误差就越大。

最后，计算未知节点坐标。dv-hop定位算法对于初始值较为敏感，应用三边测量法计算节点之间的位置，必然会受到初始值的深刻影响，致使定位精度出现极大偏差。

3 dv-hop定位算法误差减小的策略——人工鱼群算法的应用

通过上述分析，本文从dv-hop定位算法的距离估算角度出发，提出了基于人工鱼群算法来对改进dv-hop定位误差的解决策略。

3.1 人工鱼群算法的概念

3.1.1 人工鱼群算法提出背景

人工鱼群算法是根据鱼群集体觅食的特点而模拟的一种寻求最优解的定位算法。这是因为鱼群在寻找食物时，常常会将食物浓度作为食物来源和方向的判断依据。当食物的浓度达到一定程度，鱼群就会自觉朝着食物的来源方向游去，同时许多觅食的鱼之间还会出现追尾情况，这样多个鱼群就能都找到食物，也可以认为这是鱼群之间的一种分布式合作觅食策略。這种群体性的合作方式算法智能性较强，有助于解决一些最优解问题。

3.1.2 人工鱼群算法的具体内容

人工鱼群算法将需要解决的定位无线网络空间假设为一个求解空间。将不同节点间的定位看做一种协作和竞争。当需要求解定位距离的时候，求解空间的变换会对节点估测结果产生重要的影响。同时，不同节点之间的位置变换也会对求解空间产生相应的影响。在人工鱼群算法中，个体活动会对整个无线网络空间传感器的定位坐标产生关键作用，也就是各节点位置和整体的求解空间相互作用，才能使整体的传感器定位数值获得全局最优解，而不是局部的最优解。

3.2 人工鱼群算法在改进 dv-hop定位算法中的应用

3.2.1 加入RSSI加权质心算法

假设某一求解空间中有n个锚节点，其坐标分别设为（x₁，y₁），（x₂，y₂）……（x_n，y_n）^［2］，这些锚节点与需要定位的节点之间距离用RSSI来测量，其距离分别假设为d₁，d₂，d₃……d_n。本研究利用三边测量法求得需要定位的节点坐标为（x，y），二者关系如公式（1）所示：

对于与需要定位的节点周围相关的n个锚节点而言，其误差函数如公式（2）所示：

在具体的应用过程中，不同的情况需要调整不同锚节点的加权值。如果距离较远，则考虑应用较小的权值；如果距离较近，则可使用较大的权值。此外，采用待定位节点与锚节点距离的倒数作为误差函数的加权系数，是一种构造人工鱼群算法的适应度函数。具体计算过程如公式（3）所示：

基于人工鱼群算法结合加权质心算法，对传统的dv-hop定位算法进行改进，可以通过记录未知节点与锚点之间的估测距离，并将所得数值与实际的距离进行比较，获得误差最小、精度较高的数值，这样配合的方式在全网求解空间内获取的节点位置更为精准^［3-4］。

3.2.2 建立仿真实验环境Matlab平台

基于dv-hop定位算法的几个步骤，在Matlab平台建立一个基于人工鱼群质心算法在不同锚节点密度、不同节点密度和不同的节点通信半径场景下的求解区域空间。将求解空间设定为100 m×100 m的正方形场域。将所有的未知节点和锚节点都随机分布在这个区域内。将人工鱼群算法的群内解的个数设定为50，记为N，迭代次数设为100，记为IT，拥挤度因子设定为1，记为δ，视野visual设定为10，步长step为8。为最大限度减少实验中受到的误差干扰，本次实验将每组参数独立运行50次^［5］，其定位误差将以50次运行的结果平均值为准，其定位误差error计算过程如公式（4）所示：

4 应用人工鱼群算法后dv-hop定位算法的改进效果

在仿真实验平台中，当总节点数量为100，节点的通信半径为30 m时，同时锚节点的数量由12个增加至30个的场景下，可获得不同锚节密度下具体的定位误差对比。

随着区域内锚节点密度的不断增加，应用不同的算法定位误差都与锚节点个数呈现负相关关系，即定位误差随着锚节点密度的增加而降低。由此可知，增加锚节点数量，可以使dv-hop的算法误差降低。

这也是基于dv-hop定位只计算平均跳距和定位坐标产生误差而提出的算法。基于人工鱼群算法是将平均跳距扩展为全域的平均跳距，而不再是單个锚节点的平均跳距。利用人工鱼群算法，可以克服dv-hop定位算法跳距默认为1的缺陷，当未知节点和锚节点都处于1跳区域时，能保持平均跳数精度不变^［6］。

在作用域扩大到不再局限于锚节点周围半径时，如果锚节点和未知节点之间节点密度差异较大，那么二者的平均跳距差别会变得更大。如果仅采用未知节点的平均跳距显然是不科学的。基于此，本研究提出的扩大平均跳域作用范围是一个不错的解决方案。根据锚节点和未知节点之间的跳距参数，在计算二者之间距离时，如果将靠近未知节点的1/2跳数按照未知节点平均跳距来计算，那么剩下的1/2则取锚节点的平均跳距可以作为参考。

经验证，改进后的dv-hop定位算法在锚节点数量适合、比例适中和通信半径相对小的场景中，可以最大限度减小定位误差，提升定位的精度。这种方式非常适用于功耗低、范围大的无线传感器网络环境^［7］。

5 dv-hop的定位算法改进前景

除了以上方法外，不少学者针对dv-hop的定位算法改良提出了不同见解。例如：李牧东等^［8］提出基于人工蜂群算法的dv-hop定位改进法。该方法是利用节点见的距离和锚节点的位置信息来建立目标优化函数，从而实现在保持不增加传感器节点的硬件开销优势的同时，有效降低定位误差。王亚民等^［9］在《基于RSSI的改进加权质心定位算法》中提出基于三角质心定位、改进信号强度比值的加权质心混合定位算法。该方法以近似点代替信标节点作为顶点，节点之间的距离比值作为权值，有效降低了路径损耗指数对定位精度的影响，在实现区域定位方面有一定突破。熊欢等^［10］在《基于跳数修正和改进粒子群优化dv-hop定位算法》中指出修正锚节点广播跳数，让随机静态分布的锚节点移动，从而优化迭代过程，可明显提升传统算法的定位精度和算法的稳定性。随着dv-hop的定位算法的广泛应用与研究热度的上升，未来将会有更多更好的改进方式，促使其获得更好的应用效果。

6 结语

无线网络传感器的广泛应用使其获得了学界的高度关注，同时其缺陷也成为改进方案讨论的热点。本文阐述了dv-hop算法中存在的问题，依据其算法步骤指出问题存在的根本原因，并给出一种基于人工鱼群算法的改进策略，即通过加入RSSI加权质心算法来提高阵列节点间邻居个数并优化相邻节点的聚类效果；同时利用仿真实验平台，在原始二维平面建立仿真求解空间，通过多次运行获取的数值平均数，以最大限度提升实验数据的可参考性，进而顺利找到目标点，从而解决定位过程中的最优寻找、相似性度量以及最小化邻域长度等问题。

参考文献

［1］汪晨，张玲华.基于人工鱼群算法的改进质心定位算法［J］.计算机技术与发展，2018（5）：103-106.

［2］余修武，秦晓坤，刘永，等.基于全局人工鱼群算法优化的DV-Hop定位算法［J］.四川大学学报（工程科学版），2022（4）：54.

［3］王浩.基于优先节点定位和人工鱼群优化的DV-Hop算法研究［D］.徐州：中国矿业大学，2016.

［4］张爱清，叶新荣，胡海峰，等.基于RSSI每跳分级和跳距修正的DV-HOP改进算法［J］.仪器仪表学报，2012（11）：2552-2559.

［5］林金朝，陈晓冰，刘海波.基于平均跳距修正的无线传感器网络节点迭代定位算法［J］.通信学报，2009（10）：107-113.

［6］夏正龙，邓斌.一种基于人工鱼群算法的LCL滤波器参数优化方法：110442995A［P］.2019-11-12.

［7］李鳳超，高美凤.无线传感器网络中改进的dv-hop定位算法［J］.传感器与微系统，2018（2）：124-126.

［8］李牧东，熊伟，郭龙.基于人工蜂群算法的dv-hop定位改进法［J］.计算机科学，2013（1）：33-36.

［9］王亚民，王海英，何佩伦.基于RSSI的改进加权质心定位算法［J］.计算机工程与设计，2016（11）：2865-2868.

［10］熊欢，毛永毅.基于跳数修正和改进粒子群优化DV-Hop定位算法［J］.现代电子技术，2018（18）：76-79.

（编辑 王永超）

Improvement of dv-hop localization algorithm based on artificial fish algorithm

Wei Shixiong^1，2

（1.Guangxi Houpu Digital Technology Co.， Ltd.， Nanning 530009， China;

2.Wuzhou Vocational College， Wuzhou 543002， China）

Abstract： With the wide application of wireless network sensors in all walks of life， many problems in the practical application scenarios gradually emerge， especially the defects of the positioning algorithm. This paper starts from the limitations of dv-hop algorithm for wireless sensor positioning， points out the significant disadvantages of using jump distance instead of straight line distance， and improves the dv-hop positioning algorithm by using the dense network characteristics of artificial fish swarm algorithm based on various studies. It has been proved that the improved dv-hop positioning algorithm based on the artificial fish group algorithm can significantly weaken the node positioning error of wireless sensors， reduce the hardware cost of nodes， and improve the positioning accuracy and efficiency of wireless sensors.

Key words： artificial fish swarm algorithm; dv-hop; positioning algorithm; wireless network sensor