一种井下人员无线定位算法研究

刘夏， 李国良， 张灵峰， 汪郁， 孙虎， 黄启能， 丁琼

(1.贵州工业职业技术学院 电子与信息工程学院，贵州 贵阳 551400；2.贵州大学 大数据与信息工程学院，贵州 贵阳 550025)

0 引言

随着人工智能、大数据、物联网、无线网络及无线传感器网络等技术的迅速发展[1-3]，学者们对无线定位技术在煤矿井下人员定位中的应用进行了大量研究[4-6]，提出了多种无线定位算法，其中指纹定位算法因扩展性强、易维护、覆盖范围广、成本较低等特点，应用较为广泛。文献[7]提出了基于BP神经网络的井下无线自适应指纹定位算法，利用模拟退火粒子群优化BP神经网络，定位效果较好，但需要在实验环境中采集大量指纹数据，实验人员采集数据工作量较大。文献[8]提出了基于支持向量回归的半集中式定位算法，采用支持向量机回归技术得到连通信息到节点位置的回归函数，由回归函数进行节点位置估算及定位，支持向量机在处理小样本预测、非线性回归和局部最优时能展现出良好性能，但参数取值缺少先验信息，从而导致搜索区域较大。文献[9]提出了基于支持向量机分类的煤矿井下人员指纹定位算法，利用支持向量机分类方法建立指纹数据库，再通过采样点的无线信息数据与指纹数据库进行对比，找出最佳匹配位置，但实验只是在小范围进行，节点数量少，支持向量机参数难以设定。文献[10]提出了支持向量机的混合相似度加权K近邻算法，对指纹数据库进行网格划分，利用支持向量机计算出所属网格，再通过加权K近邻算法进行定位，但该方法未考虑指纹数据库较大时支持向量机收敛速度慢的问题。文献[11]提出了基于改进支持向量机的定位方法，利用模拟退火算法搜寻支持向量机最优参数，将最优参数代回到支持向量机进行定位，但模拟退火算法存在搜索效率较低、收敛速度慢等问题。

针对上述定位算法存在的问题，本文提出了一种差分进化与人工鱼群算法优化最小二乘支持向量机(Differential Evolution and Artificial Fish Swarm Algorithm Optimization Least Squares Support Vector Machine，DEAFSA-LSSVM)的井下人员无线定位算法。该算法首先将井下实验区划分为多个小区域，并利用克里金插值算法估算预测点的接收信号强度(Received Signal Strength Indication, RSSI)，可减少指纹数据采集的工作量；然后利用差分进化和人工鱼群混合智能算法对LSSVM的2个关键参数进行优化，利用优化过的LSSVM进行分类，计算出所属小区域，提高算法分类准确率；最后通过加权K近邻算法估算出待定位点的坐标位置，提升算法定位精度。实验结果表明：该定位算法分类准确，工作稳定，且定位精度高。

1 差分鱼群算法优化最小二乘支持向量机

1.1 最小二乘支持向量机

假设训练集H={(x1,y1),(x2,y2),…,(xh,yh)},其中xh为n维输入数据，yh为一维输出数据，h为样本个数。LSSVM的优化问题[12]可表示为

(1)

式中：ω为权向量；b为偏差量；e为误差变量；γ为正则化参数且大于零。

考虑LSSVM中核函数的重要性，本文选择径向基核函数[13]，其数学表达式为

(2)

式中：x和xk为数据空间内的2个输入值；σ为核函数宽度。

LSSVM在处理非线性和小样本数据时具有一定的优势，但预测精度受到正则化参数γ和核函数宽度σ的限制，这2个参数会影响LSSVM的学习和泛化能力。

1.2 人工鱼群算法

人工鱼群算法[14](Artificial Fish Swarm Algorithm，AFSA)把需要优化的参数抽象成为一条人工鱼(以下简称为鱼)。假设鱼种群为Fn，每条鱼的位置为Z={z1,z2,…,zm}，其中zm为待寻优的参数。食物周围的拥挤因子为δ，则每条鱼当前所在位置食物浓度，即目标函数为

(3)

设鱼的视野为Fv，鱼的步长为Fs。步长随视野进行动态调整可降低算法复杂度，步长计算公式为

Fs=Fv·Rand( )

(4)

式中Rand( )为产生随机数的随机函数。

觅食行为：设2条鱼之间的距离为dij，当前鱼的位置为Zi，鱼觅食次数为Fq，在视野范围内dij

Zj=Zi+Fv·Rand( )

(5)

式中i,j为鱼的标号，i≠j，取值范围为[0,n]的整数。

利用Zi和Zj分别计算出各自位置食物浓度Fci和Fcj，若满足觅食更新条件Fci>Fcj，则更新当前鱼的位置：

(6)

若不满足觅食更新条件Fcj>Fci，则放弃Zj的位置，在视野范围内重新寻找新位置Zj；判断新位置Zj是否满足觅食更新条件，如满足更新条件,按照式(6)更新位置Zi+1，否则,再次尝试更新Zj。当尝试过Fq次后,若无法满足觅食更新条件，即Fcj

Zi+1=Zi+Fs·Rand( )

(7)

聚群行为：设当前鱼的位置为Zi，当前鱼的位置食物浓度为Fci；在视野范围内，鱼的数目为Fn1，中心位置为Zc，中心位置食物浓度为Fcc。若满足聚群更新条件Fcc/Fn1>δFci，则按照式(8)更新当前鱼的位置，否则执行觅食行为。

(8)

追尾行为：设当前鱼的位置为Za，当前鱼的位置食物浓度为Fca，在搜索视野范围内，搜寻出食物浓度最大值为Fcm，且鱼所在位置为Zm1；以Zm1为中心搜索视野范围内的鱼，鱼的数目为Fn2。若满足追尾条件Fcm/Fn2>δFca，则表明Zm1处不拥挤，按照式(9)更新当前鱼的位置，否则执行觅食行为。

(9)

1.3 差分进化算法

差分进化算法[15](Differential Evolution，DE)是随机、并行、直接的全局搜索算法。

(10)

式中：Ps1，Ps2，Ps3为随机选择的种群，s1，s2，s3为[1,2,…,Fn]的随机整数；ϑ为[0,2]的变异因子，主要用于控制差分向量的放大倍数。

(11)

选择操作：采用贪婪策略，其表达式为

(12)

1.4 差分鱼群优化最小二乘支持向量机算法

差分进化与人工鱼群混合智能算法[16](Differential Evolution and Artificial Fish Swarm Algorithm，DEAFSA)简称为差分鱼群算法。

DEAFSA在人工鱼群算法中引入差分进化算法的策略，通过差分进化中的变异操作、杂交操作和选择操作使之跳出局部最优，并能发挥差分进化算法在局部寻优的优势，提升寻优精度。

差分鱼群优化最小二乘支持向量机算法[17-18](DEAFSA-LSSVM)步骤如下：

步骤1：利用训练数据库和井下定位实验条件建立LSSVM模型，生成正则化参数γ和核函数宽度σ。

步骤2：设定DEAFSA参数，如鱼种群Fn、鱼视野Fv、鱼觅食次数Fq、拥挤因子δ、杂交概率常数Cr、变异因子ϑ、最大迭代次数tmax、收敛精度ε等。

步骤3：将正则化参数和核函数宽度映射到鱼个体中，设置迭代次数t=1；初始化鱼群，在可行区域内随机生成M条鱼。

教师可以在大学英语教学中融入中国文化元素，帮助学生更多地了解中国文化并发挥英语传播中国文化的作用。教师可以开设中国文化类英语课程，用英语授课，帮助学生系统地学习中国文化。教师也可以引导学生多途径、自主地进行学习，如引导学生通过电视（CCTV International中央电视台英语频道）、英语广播(China Radio International中国国际广播电台)、英文报纸（如China Daily《中国日报》、21stCentury《21世纪英文报》）来学习中国文化及中国视角和价值观。在教学中，让学生不仅学习西方文化的英语表述，也要学习中国文化的英语表述，获得用英语表达中国文化的能力。

步骤4：根据式(3)计算各条鱼个体当前位置的食物浓度，并进行比较，将适应度最优值放置到公告板上。

步骤5：根据式(5)—式(9)执行人工鱼群算法，分别让每条鱼执行觅食行为、追尾行为和聚群行为，并选择行动后适应度更优鱼群，继续进行下一步骤。

步骤6：根据式(10)—式(12)执行差分进化算法，分别对每条鱼进行变异操作、杂交操作和选择操作，差分进化后将会得到适应度更优的新一代鱼群。

步骤7：更新公告板，将最优鱼个体的适应度与公告板上的适应度进行比较，把适应度最优值放置到公告板上。

步骤8：令t=t+1，判断DEAFSA是否满足终止条件(迭代次数到达最大迭代次数或公告板上最优适应度达到收敛精度)；若满足终止条件，则进行下一步骤，否则跳转到步骤5。

步骤9：将DEAFSA寻找到的最优解代回到LSSVM，此时DEAFSA寻优过程结束。

步骤10：利用定位训练数据库对LSSVM进行训练，并使其达到算法要求的收敛精度，最终完成DEAFSA-LSSVM算法模型的建立。

2 实验环境

实验环境为贵州某煤矿井下747 m的总风道和回风巷，巷道内已覆盖工业以太网，巷道截面宽度为4 m左右。在此基础上搭建井下人员无线定位系统，只需要安装光纤交换机和本质安全型AP(接入点)终端。实验区域为总风道和回风巷，巷道中基本没有杂物堆放和大型机电设备。巷道墙面粗糙，分布着水管、支架、电缆和光纤等设备；巷道相对比较直且弯道较小，过往作业人员也不是太多。实验环境中电磁环境相对稳定，AP节点与AP节点之间的距离控制在100 m左右，实验区域如图1所示。

图1 井下实验巷道

从图1可看出，起点在总风道，终点在回风巷，在整个实验区域共安装7个本质安全型AP节点，可实现巷道内无线全覆盖。

3 井下无线定位算法实现

井下无线定位算法实现过程分4个步骤，依次为区域划分、插值数据估算、算法训练和实时定位。

3.1 区域划分

根据井下巷道的环境，将747 m的实验区域划分为166个实验小区域，每个实验小区域长为4.5 m，宽为3 m。实验小区域划分如图2所示。

从图2可看出，在4.5 m×3 m区域内共有12个点，其中6个采集点，需要实验人员采集该点的无线信息数据；6个预测点，需要利用采集点的信息数据，通过服务器和利用克里金插值算法估算它们的无线信息数据，完成实验小区域指纹信息采集工作，这种方法可以减少50%采集工作量。图2中有一条中轴线，在井下采集数据时，以该中轴线为巷道中心位置进行采集。

图2 实验小区域划分

由实验人员携带无线采集接收终端进入实验区域完成所有采集点的无线信息数据采集。指纹数据采集流程如图3所示。

图3 指纹数据采集流程

由无线采集接收终端将扫描、处理后得到的无线信息数据(RSSI值、IP地址和MAC地址)，通过无线网络传输到服务器，每个采集点进行12次采集工作，再由服务器对其求出RSSI的平均值，确保每个采集点的RSSI值稳定可靠；最后将RSSI平均值与采集点的实际坐标进行组合，并将组合数据存放到指纹数据库。在实验区域内共采集750个点的无线信息数据，建立采集指纹数据库，完成指纹数据采集工作。

3.2 插值数据估算

插值数据估算利用文献[19]的模拟退火人工蜂群混合算法优化克里金插值算法，完成750个预测点的估算工作，插值数据估算流程如图4所示。

图4 插值数据估算流程

首先利用区域划分得到采集指纹数据库，初步构建克里金插值算法模型，并初步完成变异函数拟合。其次利用模拟退火人工蜂群混合算法优化变异函数球状模型参数，从而建立克里金插值算法模型。再次利用该算法模型和采集指纹数据库对预测点的RSSI值进行估算，并将其估算值与预测点坐标位置进行组合后，存入插值指纹数据库。最后结合采集指纹数据库和插值指纹数据库，生成由166个实验小区域组成的实验小区域无线定位指纹数据库。利用模拟退火人工蜂群混合算法优化克里金插值算法可估算预测点RSSI值，建立插值指纹数据库，从而可减少50%采集工作量，且插值精度较高。

3.3 算法训练

将区域划分和插值数据估算得到的实验小区域无线定位指纹数据库用来训练经过DEAFSA优化后的LSSVM。本文中DEAFSA主要参数设置见表1。

表1 DEAFSA主要参数设置

算法训练流程如图5所示。首先利用实验小区域无线定位指纹数据库初步构建LSSVM算法模型，并生成正则化参数γ和核函数宽度σ；其次按照表1进行DEAFSA参数设置，并对需要优化参数搜索全局最优解；再次将最优解代回到LSSVM算法模型，并利用实验小区域无线定位指纹数据库进行训练；最后建立DEAFSA-LSSVM算法模型。

图5 算法训练流程

3.4 实时定位

实时定位是利用加权K近邻(Weighted K-nearest Neighbor，WKNN)算法[20]完成定位点坐标位置估算。实时定位流程如图6所示。

图6 实时定位流程

首先利用无线采集接收终端获取待定位点的无线信息数据，经无线网络传输到服务器。其次将待定位点的RSSI值代到DEAFSA-LSSVM算法模型，计算出所属实验小区域。再次设定WKNN算法中的K为4,并在实验小区域无线定位指纹数据库找到相关点的RSSI值。最后利用WKNN算法估算出定位点的坐标位置，完成建立差分鱼群优化最小二乘支持向量机的加权K近邻(DEAFSA-LSSVM-WKNN)定位算法。

4 实验分析

4.1 实验数据采集

在建立实验小区域无线定位指纹数据库和DEAFSA-LSSVM算法模型后进行实时定位。由作业人员携带无线采集接收终端进入实验区域进行实时定位实验，无线采集接收终端每3 s自动采集1次无线信息数据，并将其传输到服务器实时定位数据库中。无线采集接收终端主要由主控芯片STC15W4K56S4、液晶显示模块LCD1602、无线芯片HF-LPB100、独立按键和锂电池供电模块组成,其优点为体积小、功耗低、工作时间长、携带方便。该终端能扫描出各个 AP节点的RSSI值和MAC地址等信息，通过主控芯片对数据进行处理后，可将有用信息通过无线网络传输到对应的数据库服务器中。

作业人员从起点先以1 m/s速度走到终点，从终点以2 m/s速度快速走回到起点，再从起点以3 m/s速度慢跑到终点，从终点以4 m/s速度跑回到起点，到达起点或终点时都停留60 s，实验过程共用时1 800 s，采集得到600组待定位无线信息数据，将这600组信息数据生成实时定位数据库。

为对比各种算法性能，需要采用统一的检测数据源，因此,再由实验人员携带无线采集接收终端进入实验区域，在井下巷道中随机采集200个检测点的无线信息数据和坐标位置，建立检测指纹数据库。

4.2 DEAFSA的优化性能分析

为检测本文提出的DEAFSA的优化性能，利用实验小区域无线定位指纹数据库对LSSVM进行训练，建立DEAFSA-LSSVM算法模型。

利用表1中的参数分别对需要比较的差分优化最小二乘支持向量机(DE-LSSVM)算法和人工鱼群优化最小二乘支持向量机(AFSA-LSSVM)算法进行设置，利用实验小区域无线定位指纹数据库分别对2种智能优化算法进行寻优，通过50次寻优得到平均迭代次数；寻优结束后建立DE-LSSVM算法模型和AFSA-LSSVM算法模型。

利用检测指纹数据库分别对LSSVM算法模型、DE-LSSVM算法模型、AFSA-LSSVM算法模型和DEAFSA-LSSVM算法模型进行计算，并计算出分类准确率，经过50次运算得到其平均值。不同算法的寻优实验结果对比见表2。

表2 不同算法的寻优实验结果对比

由表2可看出，未经优化的LSSVM算法分类准确率只有86.43%；经过DE算法和AFSA算法优化过的LSSVM算法分类准确率都有所提高，但迭代次数都达到500次以上，增加了计算量；而本文提出的DEAFSA-LSSVM算法分类准确率达到98.87%，迭代次数只有382次。

通过迭代次数和准确率的实验结果可以得出，本文提出的DEAFSA-LSSVM算法相较于LSSVM算法、DE-LSSVM算法和AFSA-LSSVM算法，收敛速度更快，分类准确率更高，且具有较强的泛化能力。DEAFSA全局搜索能力更强，能及时跳出局部极值陷阱，从而提高算法搜索精度，且优化性能更好。

4.3 井下无线定位算法的定位性能分析

为检测本文提出的DEAFSA-LSSVM-WKNN定位算法的定位性能，将其与k均值聚类的加权K近邻(k-means-WKNN)定位算法和LSSVM的加权K近邻(LSSVM-WKNN)定位算法的定位效果进行对比。

首先利用k均值聚类算法对实验小区域无线定位指纹数据库进行聚类，重新分解成166个簇，利用WKNN算法进行定位，建立k-means-WKNN定位算法模型。再利用训练好的LSSVM算法模型，配合WKNN算法进行定位，建立LSSVM-WKNN定位算法模型。最后在检测指纹数据库中随机选出25个测试点，并进行随机排序，建立测试数据集。将WKNN算法中的K设为4，利用k-means-WKNN定位算法、LSSVM-WKNN定位算法和本文提出的DEAFSA-LSSVM-WKNN定位算法进行定位，定位结果如图7所示。

由图7可看出，DEAFSA-LSSVM-WKNN定位算法的定位精度比k-means-WKNN定位算法和LSSVM-WKNN定位算法都要高，该结果说明利用DEAFSA优化LSSVM，不仅能提高分类准确度，同时也能提高算法定位精度。3种不同算法的定位误差对比见表3。

图7 不同算法定位误差分布对比

表3 不同算法的定位误差对比

由表3可知，DEAFSA-LSSVM-WKNN定位算法的平均定位误差为1.51 m，小于LSSVM-WKNN定位算法和k-means-WKNN定位算法的1.86 m和2.94 m。DEAFSA-LSSVM-WKNN定位算法比LSSVM-WKNN定位算法的定位精度提高了18.82%。

综合上述实验结果可以得出，DEAFSA-LSSVM-WKNN定位算法相较于另外2种定位算法，无论是最大误差、最小误差还是平均误差都较小，取得了较好的定位效果。该定位算法鲁棒性更好，其定位精度更高，更适合在煤矿井下复杂环境中应用。

5 结论

(1)提出了DEAFSA优化LSSVM的井下无线定位算法。该算法首先将实验区域划分为多个实验小区域，限制了误差范围，减少了定位的计算量，提高了定位的实时性；然后结合人工鱼群和差分进化2种智能优化算法优化正则化参数和核函数宽度，提升了支持向量机分类准确率；最后利用所属实验小区域内的无线信息数据，通过WKNN算法完成实时定位。

(2)实验结果表明：该定位算法与同类定位算法相比，具有收敛速度快、分类准确、定位精度高等特点，分类准确率高达98.87%，平均定位误差为1.51 m，能适应煤矿井下特殊环境的定位需求。

(3)在接下来的研究工作中，将利用差分鱼群算法进一步优化LSSVM，提高其收敛速度和分类准确率，从而提升算法的定位精度。