改进型DV－Hop 定位模型及其求解的混合视觉进化神经网络

郑 悦， 张著洪，2

（1 贵州大学 大数据与信息工程学院， 贵阳 550025； 2 贵州大学 贵州省系统优化与科学计算特色重点实验室， 贵阳 550025）

0 引 言

无线传感器网络（Wireless sensor network，WSN）是一种分布式自组织网络，是通过节点间相互协作实现对指定监控对象的数据感知、采集和处理，并将数据传输给用户；因其节点具有体积小、成本低、布设灵活及功耗低等特点［1］，使得传感器在诸如环境监测、医疗、军事、智能家居等领域中具有广阔发展前景［2］。WSN 定位包括测距定位和非测距定位［3］。 前者需通过测量节点间的实际距离或利用方位角进行准确定位，但硬件投入高。 相反，后者依据网络的连通性进行定位，其成本低、功耗小、抗干扰性能好，且实用性强。 距离矢量跳数（Distance Vector-Hop，DV-Hop）节点定位算法是一种基于GPS 定位的非测距定位方法，也是目前WSN 中应用最为广泛的算法之一［4］。由于其节点定位精度主要依赖WSN 的连通度完成对未知节点的定位，加之初始节点的分布具有随机性以及采用最小二乘法或数值迭代法估计未知节点的位置［5-7］，导致节点的定位性能有待提升。 例如，Kaur等学者［5］利用高斯-牛顿法估计未知节点的位置，能够提高未知节点的定位精度，但计算复杂度高。 张兢等学者［6］基于RSSI 与加权质心定位，将已被定位的未知节点转化为锚节点，进而对剩余节点定位，得到的算法能有效解决因节点连通度小而出现定位精度低的问题，但定位效果受环境干扰因素的影响较大。Ma 等学者［7］提出一种基于多通信半径的定位算法，其通过锚节点多次广播，计算锚节点与未知节点间的最小跳数，但未涉及未知节点间的最小跳数计算问题。 另外，智能优化算法已初步被用于未知节点的定位［8-9］。 例如，褚银菲等学者［8］利用改进型差分进化算法对未知节点进行定位，相较于DV-Hop 定位算法，能较大地提高定位精度，但性能受参数的影响较大，且种群多样性易于过早消失。

另一方面，视觉神经网络作为一种模拟视觉神经元响应特性而建立的前馈神经网络已得到可观研究进展，迄今为止则应用于机器人导航、目标跟踪、碰撞检测等方面［10-12］。 Fu 等学者［10］利用果蝇与蝗虫两种生物的视觉响应特性，提出一种混合神经网络模型，并已用于机器人的运动跟踪与导航。 另外，本文研究团队围绕视觉运动检测和最优化问题的求解，从视觉神经网络模型研究及应用角度已展开一些研究；例如，针对平移、旋转等运动模式的识别，利用蝗虫与猕猴等生物中的视觉响应特性提出人工蝗虫视觉神经网络［13］；基于视觉信息处理机制与种群进化或梯度下降思想，获得可调参数少且寻优精度高的视觉进化、学习神经网络［14-16］，并将其应用于RSSI 定位、复杂高维优化问题的求解，但算法的定位精度及搜索效果的稳定性有待提高。

综上，基于现有求解DV-Hop 节点定位问题的研究现状，本文在建立改进型节点跳数、平均跳距计算模型基础上，基于果蝇视觉、蝗虫视觉信息处理机制及哈里斯鹰优化的种群更新策略，提出一种混合视觉进化神经网络（Hybrid visual evolutionary neural network，HVENN），并用于DV-Hop 的节点定位。

1 改进型DV－Hop 模型与求解准备

1．1 DV－Hop 的距离计算

假定WSN 由m个锚节点和n个未知节点构成，锚节点i和未知节点j的位置分别为Ai（xi，yi） 及Oj（xj，yj），1 ≤i≤m， 1 ≤j≤n。 基本DV-Hop 定位方法经由锚节点与未知节点间的最小跳数以及锚节点的平均跳距计算未知节点到锚节点的距离。 具体如下:

首先，WSN 网络中一个锚节点（例如节点A） 向所有其它锚节点和未知节点均发送一个包含自身位置、跳数和地址的包，跳数初始值为0；然后，距离节点A最近的锚节点（例如节点B） 向剩余的锚节点和未知节点也发送一个同类型的包。 如此继续，直到所有锚节点均发送自身的包为止。 之后，经由DV-Hop 的节点跳数计算方法［4］，可获WSN 中锚节点Ai到锚节点Aj的最小跳数hopij及到未知节点Oj的最小跳数Hopij。 其次，节点Ai依据式（1） 得到自身的平均跳距:

进而，经由式（2） 计算Oj到Ai的距离:

1．2 改进型节点定位优化模型

由于未知节点的位置具有不确定性，加之节点的位置分布不均匀，导致DV-Hop 定位算法存在以下缺陷:

（1） 在计算锚节点与未知节点的距离时，通过把节点间的连线当作直线来计算最小跳数值，导致因传感器节点的分布不均匀，跳数的计算存在误差。

（2） 锚节点与未知节点间的距离是通过节点间的平均跳距而获得，进而因平均跳距、跳数的计算误差，使得未知节点的定位精度受到极大影响。

针对DV-Hop 定位存在的以上缺陷，这里对锚节点到锚节点和锚节点到未知节点的最小跳数（hopij、Hopij） 以及平均跳距计算模型做如下改进:

（1） 改进型最小跳数计算模型。 假设锚节点A的通信半径为R，以其为圆心，R、3R／4、R／2、R／4 为半径产生4 个同心圆，如图1 所示。 锚节点A以R／4为半径向网络中泛洪广播数据，接收到节点A信号的未知节点首先查询是否接收到过该节点的跳数；若有，则维持之前跳数信息不变；否则，将未知节点与该节点A间的跳数记为1／4 跳。 以此类推，直到节点A以R为半径向网络中泛洪广播数据为止。

图1 4 种通信半径下的广播跳数Fig． 1 Number of broadcast hops at four communication radii

若节点Ai与Oj的实际距离为d，则最小跳数Hopij经由式（3） 确定:

其次，在锚节点Ai与未知节点间引入如下加权因子:

获得节点Ai到Oj的如下改进型最小跳数计算模型:

（2） 改进型平均跳距计算模型。获得锚节点Ai与Aj间的最小跳数hopij后，经由式（6） 计算锚节点Ai的平均跳距:

在此，dij为锚节点Ai到Aj的距离。 进而，基于二者的最小跳数hopij和式（6），获得二者间的距离估计模型:

另一方面，为进一步减小跳数计算误差，利用锚节点间的实际距离与估计距离误差修正Ahopi，即:

其中，εi为锚节点i的平均每跳误差。 最后，由该跳距和跳数求出未知节点Oj到锚节点Ai的距离，即:

结合式（10），n个未知节点的位置估计问题可通过求解如下DV-Hop 模型（DV-Hop model， DVHop-M）加以解决:

其中，x表示n个未知节点的位置坐标构成的决策向量。

1．3 模型求解准备

考虑如下最优化问题:

其中，D为p维欧式空间中有界闭区域；f（x）为连续型函数；称x*为最优解，若对于D中任意候选解或称为状态的x，均有f（x*）≤f（x）。 取M×N个状态构成抽象的状态矩阵A， 即A＝（xij）M×N；将状态x对应的目标函数值f（x） 视为灰度值或光强度，A中各状态对应的灰度值构成的灰度图记作f（A）。 第t时刻的状态矩阵A（t）对应的灰度图记为f（A（t））。 在此，，相应的灰度图为f（A（t））。 以f（A（t）） 作为视觉输入图像，借助果蝇、蝗虫视觉系统的信息处理机制，在已有神经网络［17-18］基础上，建立混合型视觉神经网络（Hybrid visual neural network，HVNN）。 随后，借助此神经网络输出的局部行为量λij（t）、全局行为量ρ（t），以及哈里斯鹰优化的种群更新策略，经由式（13） 转移状态矩阵A（t）中状态为

在此，λij（t） 和ρ（t） 作为调节因子引导状态的转移。

2 混合视觉进化神经网络

2．1 混合视觉神经网络

人工果蝇视觉神经网络（Artificial fly visual neural network， AFVNN）［17］与蝗虫视觉神经网络（Locust visual neural network， LVNN）［18］是分别源于果蝇、蝗虫视觉信息处理机制的前馈神经网络。AFVNN 由4 个视觉信息处理层（光感受器（Photoreceptor）、视网膜（Retina）、薄膜（Lamina）、髓质（Medulla））和一个小叶板切向细胞（Lobula plate tangential cell， LPTC）构成；在此，光感受器接收视觉环境中的光亮强度；视网膜将光感受器获取的光亮强度经平滑处理，提取运动目标；薄膜层经侧抑制机制产生刻画运动目标变化状态的兴奋量；髓质层输出运动目标的局部方向行为量；LPTC 汇集所获局部方向行为量，并产生刻画运动目标变化状态的全局方向行为量。 LVNN 由光感受器层（Photoreceptor）、 兴 奋 层（ Excitation）、 抑 制 层（Inhibition）、兴奋抑制合成层（Stimulation）和一个蝗虫视觉神经元构成。 在此，兴奋层和抑制层接收当前及上一时刻的灰度图；兴奋抑制合成层汇聚此2 层输出的行为量，并经由侧抑制获取运动目标的局部方向行为量；蝗虫视觉神经元聚合此局部方向行为量，并产生刻画运功目标变化状态的全局运动方向行为量。 AFVNN 和LVNN 的视觉神经生理学理论和设计原理可由文献［17-18］获知。 由于果蝇与蝗虫的视觉系统均具有特征提取和运动方向检测神经元，所以如此2 种神经网络均能输出刻画运动目标逼近、偏离摄像头的全局运动方向量。

HVNN 由AFVNN 中的Retina、Lamina、Medulla、LPTC 以及LVNN 中的Inhibition、Stimulation 层构成，其拓扑结构如图2 所示。 各层的设计如下:

图2 混合视觉神经网络Fig． 2 Hybrid visual neural network

（1） Retina:由M × N个Retina 节点以矩阵形式排列而成， 节点（i，j） 在t时刻接收A（t）中状态对应的光强度，并经由式（14）生成光强度偏差量:

若节点（i，j） 处的状态未被激活，则经由以下扰动策略激活:

其中，ζ是每个分量在0 与1 之间服从均匀分布的随机向量；max 与min 分别是A（t）中所有状态对应的灰度值中最大和最小值；Gmax为最大时间步。 记B（t）＝（yij（t））M×N。

于是，节点（i，j） 的光强度偏差量由式（16） 确定:

（2） Lamina:由果蝇的cartridge （cart）和蝗虫的Inhibition （I）层构成，每个子层的节点数均为M ×N。 cartridge 层经由对Retina 层做扩边处理后，cart节点（i，j） 将接收Retina 层中对应节点处3×3 邻域内节点的光强度偏差量，并经由高斯卷积获输出行为量，即:

其中，w是下列权重矩阵的元素之和:

这里，wkl是W中位置（k，l） 处的元素。

Inhibition 层对cartridge 层做扩边处理后，节点（i，j） 接收来自cartridge 层中对应节点的3×3 邻域内节点的行为量，并经由以下侧抑制策略获得该节点的抑制量［15］:

其中，(i，j) ≠(0，0) ，wI（i，j） 是局部抑制权重，即下列权重矩阵中位置（i，j） 处的元素:

（3） Medulla:此层由m1、m2两个节点子层构成，且各层的规模均为M × N。m1节点（i，j） 首先接收Inhibition 层中节点（i，j） 的3×3 邻域内节点的输出，然后基于单向EMD 运动方向检测器［19］，获得输出行为量:

随后，m2节点（i，j）经由与之匹配的m1节点处3×3 邻域内节点的方向量， 以及AFVNN 中［17］Medulla 的设计，获得该节点在水平、竖直方向的方向量m2h（i，j） 及m2v（i，j）。

（4）Stimulation:由M × N个节点以矩阵形式排列而成，节点（i，j） 接收m2节点（i，j） 在水平、竖直方向的输出行为量，进而通过改进文献［12］中激励层的设计，经由式（20） 获得该节点在水平和竖直方向的行为量:

其中，

其 中，Ceh（i，j） 和Cev（i，j） 由 文 献［12］的Stimulation 层设计确定。

（5） LPTC:借助Stimulation 层中节点在水平、竖直方向的方向量，获得LPTC 的输出，即:

需要指出的是， HVNN 与AFVNN 及LVNN 在设计上存在较大差异，主要体现在4 个方面，分述如下。

（1）结构设计不同:HVNN 是在AFVNN 基础上，经由利用LVNN 的Inhibition、Stimulation 层分别取代AFVNN 中侧抑制层及m2节点层而获得。HVNN 的各层均由M ×N个神经节点按矩阵形式排列表示，而AFVNN 中各层的神经节点数随层数的递增而逐渐减少；LVNN 不含视觉信息投影层，信息处理层过于单一。

（2）视觉信息处理存在差异:HVNN 利用LVNN的Inhibition 层执行侧抑制，而AFVNN 通过分流抑制动力学模型计算兴奋与抑制量；也利用LVNN 的Stimulation 层生成神经节点的局部方向行为量。

（3）HVNN 利用扰动策略激活状态不变的节点，而AFVNN 未含状态扰动策略。

（4）应用对象不同:AFVNN 和LVNN 用于运动目标检测，而HVNN 适用于求解最优化问题。

2．2 状态更新

经由式（16）获知，状态矩阵A（t）经由HVNN 中Retina 层作用后变为B（t）。 此状态矩阵中每个状态依据HVNN 的Stimulation 层中节点（i，j） 输出的行为量λij（t） （局部学习率）、LPTC 输出的行为量ρ（t） （全局学习率），以及哈里斯鹰优化算法［20］中哈里斯鹰的位置更新策略进行状态更新；在此，将哈里斯鹰（i，j） 的位置视为A（t）中位置（i，j） 处的状态。B（t）中状态借助哈里斯鹰的局部与全局捕食策略，经由式（24）进行更新:

其中，E为最大时间步T下猎物的逃逸能量，即:

在此，r1～U(-1，1) 。是经由哈里斯鹰（i，j） 在全局学习率ρ（t） 引导下，经由全局开采策略生成的位置，即

其中，ζ、r2和r3为［0，1］上的随机数，a及b分别为第1.3 节所述候选解所在区域D中各维度的左、右端点值构成的向量；是随机生成的状态；为A（t）中所有状态的平均（即M × N只哈里斯鹰的平均位置）；为B（t）中最好的状态。

在式（26）中，ρ（t） 作为全局学习率被引入到第一式中，其主要作用在于调节所有哈里斯鹰的位置转移幅度，增强全局开采能力；第二式的目的是强化哈里斯鹰位置的普遍历性，扩大捕食范围。

其中，r ～U（0，1），进而推得:

其中，I是由0～1 之间随机生成的p个值构成的列向量；u和v为［0，1］ 上的随机数；β为常数，设置为1.5；σ是Levy 飞行函数；min（x，y） 表示2 个p维向量x与y的相同位置处分量的最小值构成的向量。

在式（27）中，第一式经由局部学习率λij（t） 被引入到包围猎物搜索策略而获得，其目的在于借助λij（t） 引导劣质哈里斯鹰（i，j） 逐渐朝更有利于捕食的方向转移； 第二式经由搜索猎物策略而获得，其目的是增强状态转移的多样性；第三式通过引导哈里斯鹰进行位置信息交互，确保种群位置的多样性。

2．3 HVENN 的算法描述

HVENN 作为一种循环神经网络，由HVNN 和一个M ×N神经节点矩阵顺次连接而成。 HVNN 以第t -1、t时刻的状态矩阵A（t）及A（t-1）对应的灰度图的差图作为输入， 依次经由Retina、Cartridge、Inhibition、Medulla、Stimulation 及神经元LPTC 做视觉信息处理，获得的局部学习率和全局学习率在以上状态转移策略下，引导状态转移。 算法描述如下。

步骤1参数设置:灰度图的分辨率M × N，最大时间步T。

步骤2置t←1，随机生成M ×N个候选解，构成初始状态矩阵A（t）。

步骤3计算f（A（t）），且A（t）中灰度值或目标值最小的状态，记和xgb。

步骤4执行HVNN，将A（t）转移为B（t），同时获得局部学习率λij（t） 和全局学习率ρ（t）。

步骤5A（t）中所有状态依据式（24） 执行状态更新，获得状态矩阵A（t＋1）。

步骤6计算A（t＋1）对应的灰度图f（A（t＋1）），并借助A（t＋1）中的状态，更新xgb。

步骤7置t←t ＋1， 若t≤T，则返回步骤4；否则，结束且输出xgb。

以上算法利用HVNN 输出的全局学习率控制状态的变化幅度，防止因状态转移的幅度过大而导致状态远离最优解的位置，增强算法的收敛性。 同时，对状态分量进行随机扰动，防止算法过早陷入局部搜索，增强算法的全局搜索能力。 另外，局部学习率被用于调节状态局部转移的幅度，增强算法的局部搜索能力。

HVENN 的计算复杂度由HVNN 和状态更新策略确定。 在HVNN 中，Retina 层共执行MN次加减运算；Cartridge 层共运行28MN次；Inhibition 层共执行18MN次加减法；Medulla 层执行27MN次运算；Stimulation 层共执行12MN次乘除法运算、10MN次加减运算、MN次求最大值和取绝对值运算；Lobula层共执行7MN次运算。 状态更新模块需要执行15MNp次运算以及MNmp次目标函数评价，在此mp表示优化问题中目标函数的计算次数。 于是，在一个执行周期内，HVENN 的运行次数为MN（mp ＋15p ＋104）。 因此，HVENN 的计算复杂度由M、N、p和mp确定。 又因要求M、N的取值较小，所以算法的效率由优化问题本身而定。

3 数值实验

在配置为Windows10／CPU 3.7 GHz／RAM 4.0 GB／Matlab R2018a 环境下展开数值实验。 首先，借助基准函数和参与比较的算法测试HVENN 求解函数优化问题的性能；其次，将HVENN 应用于DV-Hop 节点定位问题，测试其应用效果和所获锚节点与未知节点之间的距离计算模型设计的合理性。

3．1 HVENN 的性能测试

选取6 种元启发式随机搜索算法参与HVENN的比较，即灰狼优化（GWO）［20］、麻雀搜索算法（SSA）［9］、飞蛾扑火优化（MFO）［21］、多元宇宙优化（MVO）［22］、蝴蝶优化算法（BOA）［23］及哈里斯鹰优化（HHO）［24］。 测试事例包括维度均为30 的13 种基准测试函数优化问题f1～f13［22］，其中f1～f7是单峰值函数，f8～f13是含大量局部最优解的多峰值函数。 参与比较算法的种群规模均为100，其它参数设置源于相应文献。 HVENN 的参数设置为M ＝N＝10。 对于每个测试问题，各算法的终止条件是最大迭代数为500 或获得的最好解的目标值为0，且均独立运行30 次。 各算法获得每个问题的30 个最好目标值的均值、均方差及在显著性水平为5%下的t检验值用于算法的比较分析，见表1； 以f1、f3、f5、f7、f9、f11为例，算法的搜索曲线如图3 所示。

经由表1 的均值和方差可知，HHO 和HVENN求解f1～f13所获解的质量明显优于其它参与比较的算法所获解质量，且均能稳定地获得优化问题的最优解或近似解，搜索效果稳定。 相对而言，HVENN 比HHO 获得的解的精度更高，且获得最优解的基准测试问题个数更多，尤其是求解较为困难的F8， 其搜索效果较为稳定。 其次，GWO 和BOA求解以上13 个优化问题时，无论是解的质量、还是搜索效果的稳定性，均优于SSA、MFO 和MVO，分析其原因在于二者仅分别不能有效求解2、4 个问题。最后，MFO 不能有效求解13 个测试问题；SSA 和MVO 不能求解9 个测试问题。 结合表1 中t检验值可知，HVENN 求解以上问题的性能最好，HHO 次之，而MFO 的性能最差。

表1 各算法求解每个问题时，独立运行30 次后获得的统计结果比较Tab． 1 Comparison of the statistical results obtained after 30 independent runs when each algorithm solves each problem

图3 中，n表示迭代次数，f表示适应度值。 图3 表明，相较于参与比较的算法，HVENN 的全局搜索能力强且收敛速度最快；HHO 相比于其它参与比较的算法，搜索速度快，但获得的解的精度有待提高，且易于收敛到近似解；BOA 的进化能力比GWO、SSA、MFO、MVO 的能力强，但收敛速度比GWO 的慢。

图3 算法的平均搜索曲线比较Fig． 3 Comparison of the average search curves of the algorithms

3．2 DV－Hop 定位

为测试HVENN 求解1.2 节中DV-Hop-M 的性能，选取经典DV-Hop 算 法［4］、MVODV-hop［21］、GWODV-Hop［9］、BOADV-Hop［23］参与节点定位误差比较。 设置锚节点和未知节点所在矩形的面积为100 m×100 m，且随机抛撒m个锚节点及n个未知节点，如图4 所示。 图4 中，“*”表示红色信标节点，“◦”表示黑色未知节点。 依据以下节点定位的平均误差指标检测各算法的性能:

图4 网络节点分布：m＝20，n＝80Fig． 4 Network node distribution： m＝20，n＝80

其中，（xi，yi）和分别是未知节点i的估计和实际位置；R是通信半径；Err是n个未知节点的平均定位误差。 式（31） 表明，Err越小，则算法的节点定位精度越高；反之，精度越低。 这里，给出研究内容详述如下。

（1）情形1:锚节点数量。 设置R＝25 m，锚节点数为m＝10＋5k（0 ≤k≤8），未知节点数为n＝100 -m，节点总数为100。

在给定的k值下，各算法求解DV-Hop-M 100次，获得的100 个Err的均值形成的曲线如图5（a）所示。 经由图5（a）获知，随着k的增大，锚节点数量逐渐增多，因而未知节点数逐渐减少，定位精度逐渐提高。 HVENN 的Err为28.7%，参与比较的4 种算法的Err分别为66.5%、57.2%、52.2%及45.3%。因此，HVENN 的节点定位偏差最小，而DV-Hop 的节点定位偏差最大。

（2）情形2:节点通信半径。 矩形区域面积同上；设置m＝30，n＝70，通信半径R＝15＋5k（单位为m），0≤k≤5。 同上，在给定k值下，各算法获得的定位精度曲线如图5（b）所示。 经由图5（b）获知，当20≤R≤35 时，随着通信半径的加大，未知节点收集到的定位信息越多，网络连通性越强，定位精度逐渐提高；当R ＞35 时，各算法获得的节点定位精度逐渐趋于平稳。 主要原因在于，当通信半径较小时，每个节点的相邻节点较少，网络连通性较低，导致平均跳距存在一定误差，进而定位效果较差。 当通信半径增大时，节点间的跳距变小，从而定位误差减小；当通信半径达到35 m 时，区域内的2个节点间的跳距都在3 跳之内，所以随着R的增大，定位误差趋于稳定且较小。 相较于其它基准对比算法，HVENN 的定位精度最高，但DV-Hop 的定位精度最低。

图5 定位误差对比Fig． 5 Comparison of positioning errors

4 结束语

为了解决DV-Hop 定位模型存在定位误差大的问题，在改进节点跳数和平均跳距计算模型基础上，将未知节点的定位问题描述为非约束确定性优化问题，进而利用果蝇和蝗虫视觉系统的信息处理机制获得混合视觉神经网络，并将其输出与哈里斯鹰的位置更新策略结合，获得混合视觉进化神经网络（HVENN）。 理论分析表明，该神经网络的计算复杂度由其分辨率和优化问题的维度确定。 实验结果表明，将视觉神经网络与元启发方法结合，探讨求解优化问题的视觉进化神经网络，是一条切实可行的新路径；相比于其它基准对比算法，HVENN 在求解精度和收敛速度方面均有明显优势，且能较好地解决WSN 的节点定位问题，HHO 次之，而其它基准对比算法的性能较差。 另外，本文仅涉及到静态环境下的节点定位问题及其求解，至于如何探讨不确定环境下的节点定位以及HVENN 是否具有适应环境的能力，仍需做后续进一步的研究探讨。