基于IGWO-GRNN的室内3D定位算法

高 媛，阳 媛，王鸿磊

(1.徐州工业职业技术学院 信息工程学院，江苏 徐州 221000；2.东南大学 仪器科学与工程学院， 江苏 南京 210096；3.中国矿业大学 信息与控制学院，江苏 徐州 221000)

0 引 言

目前，为实现更加精准的室内定位，有研究人员开始应用人工神经网络等人工智能理论结合接收信号强度RSSI(received signal strength indication)进行室内定位[1,2]。其中，广义回归神经网络(generalized regression neural network，GRNN)非线性映射能力强，数据拟合能力和学习速度也更优[3]，十分适合室内定位。其模型结构简单，预测性能很大程度上取决于参数σ的取值，而σ取值时主观影响较大[4]，需要寻找一种优化σ取值的方法来实现高精度定位。灰狼优化算法(grey wolf optimizer，GWO)[5]是一种新兴的群智能优化算法，收敛性能较强、参数少、易实现，可用于优化参数，被许多研究者广泛采用，但GWO算法在寻优过程中容易陷入局部最优。为进一步提升GWO算法的性能，文献[6]利用混沌Cat映射、粒子群算法个体记忆功能、高斯变异扰动和优胜劣汰选择规则来优化算法。文献[7]引入了混沌算法、改进了收敛因子，并对δ狼进行了融合变异。文献[8]采用改进的精英反向学习策略产生精英反向个体，避免算法早熟收敛。文献[9]在种群初始化、平衡全局和局部探索能力方面做出了改进，同时进行了Cauchy变异操作。但是以上4种改进算法并没有对位置更新策略进行改进，且全局和局部搜索能力的协调不够灵活，寻优能力和寻优效率还有待提高。本文提出一种改进的灰狼优化算法(improved grey wolf optimizer，IGWO)，通过对种群初始化的改进、控制参数的对数式调整以及适应度权值的引入，经过多次迭代，可获得更佳的适应度值和更快的收敛速度。同时将IGWO引入到GRNN模型中，利用IGWO优化平滑因子σ的取值，建立最优GRNN神经网络模型，准确定位待测节点的三维位置。

1 GRNN模型及问题描述

GRNN神经网络的结构如图1所示，由输入层、模式层、求和层和输出层4部分构成[10]。

图1 GRNN神经网络结构

将模型的输入向量表示为X=[X1,X2,…Xm]T，输出向量表示为Y=[y1,y2,…yn]T，联合概率密度函数表示为f(X,y)，y的观测值为Y，假定f(X,y)服从正态分布，则

(1)

式中：m为输入向量X的维度；n为学习样本数；σ为高斯函数的宽度系数，即GRNN网络的平滑因子。Xi为第i个输入向量，Yi为第i个输出向量。

y相对于X的回归为

(2)

在已知概率密度函数的情况下，由式(1)、式(2)计算可得

(3)

将室内定位时实际测量到的RSSI值作为输入向量输入GRNN模型，则可根据式(3)预测出被测目标的真实位置。GRNN模型结构简单，当样本数据确定后，综上可知，进行网络预测只需确定平滑因子σ，σ的取值直接影响着GRNN模型的泛化能力和预测精度[4,11]，所以适中的σ取值极其重要。本文采用改进的灰狼算法IGWO来优化平滑因子σ的取值。

2 IGWO-GRNN室内3D定位算法

2.1 传统灰狼算法

灰狼算法是一种根据灰狼群体捕食而提出的智能算法，猎物代表最优解，每只灰狼的位置代表一个可能的解[12]。灰狼群在捕猎过程中有着严格的社会等级制度，领导能力最强的灰狼被记为α，是适应度最佳、离最优解最近的狼；β狼和δ狼是适应度次于α狼的两种个体，猎捕过程中它们会协助α狼管理狼群以及决策出现的问题，同时也是α狼的候选者；剩余的狼记为ω，负责平衡狼群内务关系以及协助攻击猎物[13,14]。

GWO算法的数学模型具体描述如下：

Di=|C·Xp(t)-Xi(t)|

(4)

C=2·r2

(5)

其中，Di为灰狼个体i与猎物间的距离，Xp(t)和Xi(t)分别为t次迭代时猎物和灰狼个体i所处的位置，C为摆动因子。

狼群要根据猎物方位对自己位置进行更新，其数学描述如下

Xi(t+1)=Xp(t)-A·Di

(6)

A=2a·r1-a

(7)

a=2-t/tmax

(8)

A为协同系数向量，变量a随着迭代次数的增加从2线性减少到0，tmax为最大迭代次数，r1，r2表示[0,1]间的随机数。

包围猎物后，β狼和δ狼在α狼的带领下开始追捕猎物，灰狼的位置会随着猎物逃跑而改变，需要更新α、β、δ狼的位置来重新确定最优解，而其它灰狼个体则根据α、β、δ狼的位置来调整自己的位置，用Xi(t+1)表示。具体公式为

(9)

(10)

(11)

在一次捕猎的过程中，伴随着参数和迭代次数的不断调整，最终找到全局最优解。

2.2 改进的灰狼算法IGWO

2.2.1 种群初始化的改进

在传统灰狼算法中，初始的狼群种群是随机生成的[15]，种群的随机分布会使得初始解的个体不能遍历整个搜索空间，造成较优解的丢失，还可能会陷入局部最优值，降低了算法的寻优能力。而具有均匀分布的初始化种群可以一定程度上提高算法的寻优效果。本文采用文献[16]提出的佳点集方法初始化灰狼种群，以获得更均匀稳定的初始种群分布。

设狼群初始种群数为N，搜索空间的维数为D，则有

rd=ed,1≤d≤D

(12)

佳点集中第i个点的第d维可表示为

(13)

将佳点集映射到灰狼初始种群，搜索空间为1维，则第i个灰狼的1维空间的值为

Xi=l1+ri1(u1-l1),i=1,2,…,N

(14)

式中：u1和l1分别为灰狼个体的1维空间的上下限。

取灰狼种群数量为50，灰狼个体的1维值分布在[0,1]中，使用佳点集方法获得的初始种群分布的数据见表1，使用随机生成法和佳点集方法的种群分布如图2所示。

表1 佳点集获取初始分布数据

图2 两种方法获取初始种群分布情况

从表1和图2可以看出，佳点集构造的初始种群分布更加均匀，且没有重复的个体，从而更有助于算法遍历整个搜索空间，有效避免局部最优。

2.2.2 控制参数的对数式调整

对群体智能优化算法来说，全局和局部探索能力的协调至关重要。全局探索是群体需要搜索更广泛的区域，避免算法陷入局部最优[8]；局部探索则是利用已有信息对某些邻域进行密集搜索，决定着算法的收敛速度。使两者协调的算法才能具备较强的鲁棒性和较快的收敛速度。

由传统灰狼位置更新公式可知，在平衡GWO算法的全局和局部探索能力方面，参数A的大小起到关键的作用。当|A|>1时，灰狼群体扩大搜索范围；当|A|<1时，灰狼群体缩小搜索范围。分别对应于GWO算法的全局探索能力和局部探索能力。由式(7)可知，控制参数a决定A的值，a值越大，算法的探索能力越强；a值越小，搜索精度越高。由式(8)可知，控制参数a随迭代次数t的增加线性减小，由2变化到0。但是，结合实际，GWO算法的寻优过程是非常复杂的，寻优前期和后期的侧重点不同，要求也不一样，控制参数a仅随迭代次数t线性递减不能反映出实际的寻优过程。文献[8]和文献[9]提出了设计控制参数a随迭代次数t进行非线性变化，由测试结果可知，改进后的GWO算法寻优效果更佳。因此本文提出一种基于对数函数且曲率可变的控制参数计算方法，其表达式为

(15)

式中：μ为曲率参数。选取不同μ值，令tmax取500，控制参数a随迭代次数t的变化如图3所示。

图3 控制参数a随迭代次数t的变化

从图3中可以看出，该控制参数计算方法对应的曲线在寻优前期时，a的变化幅度不断变缓，有利于狼群的部署以及扩大搜索范围，以得到全局最优解；寻优后期曲线变得越来越陡峭，有利于加快算法的收敛速度，增加狼群捕猎精度。随着μ取值的不断增大，曲线的曲率也不断增大，实际应用时，可根据实际需要适当调整μ值，计算出的a能更好地协调全局与局部探索能力。

2.2.3 适应度权值的引入

在α、β、δ狼随着猎物的移动而更新自身的位置后，其它灰狼个体ω则根据α、β、δ狼的位置来调整自己的位置，由传统灰狼算法可知，当迭代次数达到规定次数时，将α狼的位置作为全局最优解输出。所以，α狼的位置是最接近猎物的位置，ω狼位置更新时应着重倾向于向α狼的位置移动，故本文引入适应度权值。将α、β、δ狼的位置加权一定的系数后，得到ω狼的位置，这样，能够缩短整个狼群和猎物间的距离，增大捕获的成功率，提高算法的寻优效率。首先构造适应度函数计算灰狼个体的适应度值，本文构造适应度函数为

(16)

式中：(x′j,y′j,z′j)是GRNN模型的第j个预测位置，(xj,yj,zj)是第j个样本实际位置，M为测试位置样本数。根据计算出的适应度值选出值最小的3个灰狼个体，适应度值按从小到大分别记为fα、fβ、fδ，将α、β、δ狼的适应度权值分别记为：kα、kβ、kδ，数学表达式如式(17)～式(19)所示

(17)

(18)

(19)

由此计算ω狼的位置如式(20)所示

(20)

式中：X1i、X2i、X3i分别为α、β、δ狼更新后的位置。

2.3 IGWO-GRNN室内3D定位流程

将GRNN模型的参数平滑因子σ映射为灰狼种群中的灰狼，第i个灰狼个体表示为Xi={σi}，i=1,2,…,N，基于IGWO-GRNN室内3D定位算法的总体流程如图4所示。

图4 IGWO-GRNN室内3D定位算法流程

其中，改进的灰狼优化算法IGWO调整平滑因子的流程如图5所示。

图5 IGWO调整平滑因子的流程

本文将定位过程分为两个阶段：模型训练阶段和三维坐标预测阶段。在模型训练阶段，利用在测试场所采集到的RSSI值和对应的测试节点实际三维坐标样本数据训练网络并建立IGWO-GRNN模型；在三维坐标预测阶段，将待定位节点与信标节点之间采集到的RSSI值输入训练好的IGWO-GRNN模型中，神经网络的输出即为待定位节点的三维坐标。

具体步骤如下：

步骤1初始化算法参数：灰狼种群规模N取值100，取值范围介于[0,1]之间，最大迭代次数tmax=50，搜索空间维数D=1。

步骤2初始化灰狼个体位置Xi。采用式(14)的佳点集方法对狼群进行初始化，保证狼群较均匀分布。

步骤3按照式(16)构造适应度函数并计算所有灰狼个体的适应度值。

步骤4根据计算出的适应度值选出值最小的3个灰狼个体，并将其位置分别保存为Xα、Xβ、Xδ。

步骤5根据式(15)计算控制参数a，本文中曲率参数μ取值300，然后计算A、C

(21)

C=2rand(0,1)

(22)

rand(0,1)表示[0,1]上均匀分布的随机数。

步骤6根据式(9)、式(10)、式(20)更新α、β、δ以及ω灰狼个体的位置。

步骤7判断是否达到最大迭代次数tmax，如未达到，则返回步骤3，如达到，则输出Xα作为最优解，即得到最优平滑因子σ。

步骤8输入训练样本集数据对神经网络模型进行训练，如满足误差要求，则训练完成，得到最优GRNN定位模型，终止训练并保存模型，否则，重复步骤8。

步骤9将测试样本集数据输入最优GRNN定位模型，获得待定位节点三维坐标。

3 实验及结果分析

我们将实验选择在一个12 m×10 m的办公环境内，基于Zigbee定位系统，准备5个信标节点(AP)，分别放置在测试场所天花板的4个角落和中心位置，用来接收定位节点发送的数据，测试场所内存在各种障碍物。将测试区域划分为120个小区域，每个小区域大小为1 m×1 m，小区域中心位置作为测试点。测试人员随身携带定位节点，从(0,0)位置出发，遍历每个测试小区域。在每个测试点处，定位节点向5个信标节点分别发送100个数据包，形成[RSSI1,RSSI2,RSSI3,RSSI4,RSSI5,(xi,yi,zi)]样本数据，i=1,2,3,…,120，作为样本集数据。从120组样本数据中抽取100组数据作为训练样本集，剩余20组作为测试样本集。将训练样本集中的RSSI值作为网络模型的输入，训练神经网络，对应测试点的坐标作为输出，满足误差要求后，则得到最优定位模型，再用测试样本集数据来验证该网络模型的定位效果。

本文为了验证IGWO-GRNN在室内3D定位中的准确性和优越性，将IGWO-GRNN与GWO-GRNN和文献[11]中提出的GA-GRNN以及将文献[9]中提出的一种改进非线性收敛方式的灰狼优化算法CGWO用于室内3D定位进行比较。初始种群规模N取值100，平滑因子σ取值范围设置在[0,1]之间，最大迭代次数tmax=50。其中本文算法IGWO中曲率参数μ取值300，CGWO算法的非线性调节系数k值直接取自文献[9]中实验性能最佳时的值。GWO、GA、CGWO和IGWO这4种算法的寻优对比如图6所示，从图中可以看出，GWO算法在24代左右收敛，GA算法在34代左右收敛，CGWO算法在16代左右收敛，而IGWO算法在13代左右已经收敛。同时可以看到，4种算法寻优最终平稳下来的适应度值IGWO算法最低，GA算法最高。综上表明，在算法的收敛速度方面和精准度方面，IGWO都要明显优于另3种算法。

图6 GWO、GA、CGWO和IGWO寻优对比

通过上面4种算法不断迭代更新，在寻优结束时，得到各自最优平滑因子σ。其中，GWO算法得到σ=0.572，GA算法得到σ=0.667，CGWO算法得到σ=0.407，IGWO算法得到σ=0.336。各自构建神经网络模型，进行定位效果的比较。

GWO-GRNN、GA-GRNN、CGWO-GRNN和IGWO-GRNN这4种模型的定位效果如图7所示。

将4种模型的定位误差进行对比，如图8所示，GA-GRNN模型的最大定位误差是0.86 m，最小定位误差是0.07 m，实际坐标与模型输出坐标差在0.3 m内的点只有8个，GWO-GRNN模型的最大定位误差是0.61 m，最小定位误差是0.03 m，实际坐标与模型输出坐标差在0.3 m内的点有13个，CGWO-GRNN模型的最大定位误差是0.46 m，最小定位误差是0.02 m，实际坐标与模型输出坐标差在0.3 m内的点有16个，而IGWO-GRNN模型的最大定位误差是0.37 m，最小定位误差是0 m，实际坐标与模型输出坐标差在0.3 m内的点有18个。由以上数据可知，GA-GRNN模型定位精度明显低于GWO-GRNN模型。由文献[11]实验结果可知，GA-GRNN模型在定位精度和收敛速度上都优于目前广泛研究的FOA-GRNN以及BP神经网络算法。所以利用灰狼算法优化GRNN平滑因子σ进而实现室内3D定位是有明显优势的。而将灰狼优化算法进行改进后，CGWO-GRNN与IGWO-GRNN模型定位精度显著提高，本文提出的IGWO-GRNN模型定位精度最高。

图7 4种模型的定位效果

图8 3种模型定位误差对比

本文选用均方根误差(RMSE)对模型的预测效果进行评价，公式如下

(23)

式中：(xi,yi,zi)为测试样本集第i个样本的真实位置，(x′i,y′i,z′i)为预测值，n为测试样本集样本数，均方根误差值越小，模型的预测性能越好。表2为4种模型的均方根误差对比结果。可以看出，GA-GRNN模型的均方根误差最大，IGWO-GRNN模型的最小，再次表明，利用IGWO优化GRNN平滑因子σ，可以获得更好的定位效果。

表2 4种模型的均方根误差对比结果

4 结束语

本文提出一种基于IGWO-GRNN的室内3D定位算法。该算法将待测节点与信标节点间的RSSI值作为GRNN的输入，待测节点的三维坐标作为输出，训练神经网络拟合RSSI值与三维坐标最终建立网络模型。该算法引入改进的灰狼算法IGWO优化GRNN网络的平滑因子σ，有效解决了因人为选择参数不当而导致的预测效果不好和过拟合现象，提高了模型的预测精度。仿真结果表明，与GWO-GRNN、GA-GRNN、CGWO-GRNN相比，本文提出的算法定位精度更高且寻优速度更快，基本满足定位要求，为室内定位提供了一种方法。