改进克里金插值算法的井下无线定位指纹库构建方法*

刘 夏,莫树培

(1.贵州工业职业技术学院电子与信息工程学院,贵阳 550000;2.中南大学信息科学与工程学院,长沙 410000)

为提高煤矿安全生产保障能力,国家强制要求全国煤矿都必须建立和完善安全避险六大系统,其系统包括监测监控、人员定位、供水施救、压风自救、通信联络、紧急避险等。煤矿井下人员定位系统能够及时、准确的将井下各个区域人员的动态情况,使管理人员能够随时掌握井下人员运动轨迹。当事故发生时,救援人员可根据井下人员定位系统所提供的数据,迅速获取有关人员的位置情况,提高应急救援工作的效率。目前井下人员定位系统[1]主要采用RFID区域位置监测技术,只能将井下工作人员定位到一个区域,定位精度不高,无法满足煤矿智能化对人员或设备定位的需求。

为解决煤矿井下人员定位技术难题,学者们研究用惯性导航、UWB、ZigBee和WIFI等技术进行井下人员定位,其中惯性导航[2]需要移动终端设备增加陀螺仪、加速度计和磁力计等传感器才能进行定位;UWB技术[3]通信距离在10 m左右,不适合将长距离定位;ZigBee技术[4]传输效率慢,对信道带宽要求较高,从而影响定位效果;WIFI技术[5]因带宽高、传输速度快、价格便宜、部署方便等特点,近年来已经成为研究热点。WIFI定位技术通过获取无线信号的相关信息估算出目标位置数据,目前主要有DV-Hop定位[6]、到达时间定位、质心定位和指纹定位等方法,其中到达时间定位[7]需要精确测量信号的传播时间,对无线设备硬件要求高;质心定位[8]必须已知3个以上无线网络传感器或AP节点信息才能实现定位;指纹定位[9]一般分为离线采集阶段和在线匹配阶段,其关键点在于离线采集阶段建立采集点密集分布的定位指纹库[10],传统方法是逐点采集信号,会耗费大量的人力和时间。针对此问题,郭红成等[11]提出线性插值法构建指纹库,存在基点处不光滑,插值精度低;LI等[12]提出反距离加权插值法构建指纹库,未考虑数据在空间分布情况,会造成观测点权值不对应而造成估计结果产生偏差;王永星等[13]提出克里金插值算法构建指纹库,采用克里金插值算法进行估算预测点,但随着距离h不断增大,空间相关性不断减弱,变异性不断增强,从而会使样本反映的统计特性偏离实际,导致插值准确度降低。

本文在上述方法基础上,提出利用模拟退火人工蜂群混合优化算法对克里金插值算法中理论变异函数寻找全局最优解,再利用少量观测点的信号数据,通过改进克里金插值算法估算出预测点的插值数据,构建完整井下指纹数据库。实验结果表明,该构建方法进一步提高定位系统的稳定性和定位精度,而人工采集指纹数据的工作量可减少50%。

1 普通克里金插值算法

克里金插值算法[14]是法国统计学家乔治斯·马瑟伦(Georges Matheron)于1963年提出,其定义为对已知样本加权平均,估计平面上的未知点,并使得估计值与真实值的数学期望相同且方差最小的地质统计学过程。

克里金插值算法也称空间局部插值,其建立在变异函数理论和结构分析的基础上,能够对区域变量进行线性无偏最优估计。该算法已经广泛应用在地质学、环境科学、大气科学等领域。

设预测点RSSI数据的估计值为z*(x0),第i个位置观测值为z(x)i,其公式可表示为:

式中λi为第i位置观测值的权重,m为用于估计待预测点的数量。

区域化变量是指在区域内所在位置有关的随机变量,在本文中是指在区域内不同位置上的信号强度信息RSSI。设在空间中两个不同的点x和x+h处的特征值z(x)和z(x)+h存在一定相关性,相关度与两点间的距离h有关。

变异函数能够反应区域化变量的空间结构特征,其计算公式可表示为

(2)

在区域内满足二阶平稳假设条件下,对任意两点间的距离h,有E[z(x)]=E[z(x)+h],则变异函数可表示为:

如果γ(x,h)仅依赖于变量h,而于具体的位置x无关,再根据实验中已测得信号强度信息数据估计出变异函数称为实验变异函数,可表示为:

式中M(h)为距离h时的点对数目。

在实验中采集到样本有限,对于实验变异函数γ′(h)在整个区间上随距离h变化需要通过理论模型来拟合。

理论模型有纯块金效应模型、球状模型、指数模型和高斯模型等模型,而利用定位区域中无线信息强度求解实验变异函数是最接近球状模型的变异函数。球状模型公式,可表示为:

式中C0为块金常数,C为供高,C0+C为基台值,a为变程。

由式(1)可知,要求出z*(x0)的信号强度就必须权值λi的值,λi的值是通过实验变异函数在无偏性和最小方差条件下,计算得到;由此可以推到出普通克里金方程组为:

(6)

式中μ为Lagrange函数因子。

由式(1)中λi可以通过方程组形式表示为:

式中,γ(xi-xj)的值可以通过球状模型的变异函数来获得。式(7)方程组能够简写为:

AW=Z

(8)

式中A,W和Z相应表示式(7)中左、中右矩阵。

权值向量W能够通过式(8)计算得出:

W=A-1Z

(9)

求解矩阵方程式(9)得到权值λi,待入式(1)可计算出z*(x0),即预测点RSSI的无偏估计插值。

用插值算法可以减少人工采集量指纹的工作量,考虑到井下无线信号强度的空间相关性,克里金插值算法通过整体空间球状模型变异理论对预测点的作用,当距离h较小时计算出的插值准确度较高;但随着距离h不断增大,空间相关性不断减弱,变异性不断增强,从而会使样本反映的统计特性偏离实际,导致插值准确度降低。为此本文提出利用模拟退火人工蜂群混合优化算法对理论变异函数球状模型参数进行优化,使之能达到全局最优,从而提高插值准确度。

2 模拟退火人工蜂群混合优化算法

人工蜂群算法是模仿蜜蜂行为提出的一种优化方法,可解决多变量函数优化问题,但易陷进局部最小值,且易出现适应值更新停滞现象。为此本文提出利用模拟退火算法来改善人工蜂群算法,结合二种算法优势,使理论变异函数球状模型参数能寻到全局最优的解。

2.1 人工蜂群算法

人工蜂群[15-16]ABC(Artificial Bee Colony)算法是由蜂群采蜜行为启发的算法,通过蜂个体的局部寻优行为,最终在群体中突现全局最优的值。算法中蜂群主要由引领蜂、侦察蜂和跟随蜂组成,其中引领蜂和跟随蜂各占整个峰群数量的一半,引领蜂与蜜源两者之间一一对应,且两者数量相等。每个蜜源的位置代表优化问题的一个解,蜜源的蜜量对应着算法适应度,适应度值的大小反映蜜源质量,也就是优化问题解的质量,而寻找蜜源任务是由引领蜂和侦察蜂来完成。

人工蜂群算法初期是由引领蜂随机选择蜜源位置,并储存蜜源位置信息,然后根据式(10)在领域内搜索新的蜜源位置,并获取该蜜源信息。其中式(10)可表示为:

υij=xij+φij(xij-xkj)

(10)

式中υij为新蜜源位置;xij为原来蜜源位置;φij为随机数,其范围为[-1,1];j为第j个待优化问题参数维度,j={1,2,…,D},其中D为总维度数;k为随机选择的蜜源标号且k≠i。

当所有引领蜂搜索完蜜源后,会用摇摆舞方式将蜜源信息传递给跟随蜂,跟随蜂根据获得的蜜源信息选择蜜源,蜜源量越大被选中的概率也就越大。其概率Pi可表示为:

(11)

式中fiti表示蜜源i的适应度值,N为蜜源的数量。

当某一蜜源未更新的次数达到limit后,舍弃该蜜源,蜜源对应的引领蜂变为侦察蜂,并随机产生一个新的蜜源位置Sij,产生的公式可表示为:

因为本文需要对克里金插值的理论变异函数进行优化,所以采用的适应度函数[17]为

式中γ′(h)为实验变异函数,γ(h)为理论变异函数,M为分离距离个数,hm为第m个分离距离。

2.2 模拟退火算法

模拟退火[18]SA(Simulated Annealing)算法是模拟固体退火过程,利用高温时粒子的无序性,有效地跳出局部最优的陷阱。

将模拟退火算法与人工蜂群算法进行融合,当新蜜源适应度值低于当前蜜源时,按照一定的概率接受新蜜源,从而跳出局部最优的陷阱。其概率PSA可表示为:

式中f(mot)为当前蜜源的适应度值,f′(dau)为新蜜源的适应度值,Tk为当前温度。

设温度下降函数为:

Tk=βTk-1

(15)

式中β为降温系数,β∈[0.75,0.99]。

2.3 模拟退火人工蜂群混合优化算法

根据上述算法公式的建立,模拟退火人工蜂群混合优化[19](SA-ABC)算法实施步骤如下:

步骤1初始化人工蜂群和模拟退火的参数,如蜂群总数SN,蜜源的数量N,蜜源未更新次数limit,初始温度T0,终止温度Tmin,退火系数β,最大迭代数Kmax,迭代数k,收敛精度ε等,并把需要优化参数映射到蜜源;

步骤2引领蜂随机选择一个蜜源,按式(13)计算当前蜜源的适应度值;

步骤3进入引领蜂阶段,引领蜂按式(10)在领域内搜索新蜜源位置,并按式(13)计算新蜜源的适应度值。按照模拟退火机制选择是否接受新蜜源:若新蜜源更优即f(mot)ϑ时接受新蜜源,否则保留当前蜜源。

步骤4进入跟随蜂阶段,引领蜂用摇摆舞方式将蜜源信息传递给跟随蜂,然后跟随蜂按式(11)选择蜜源,并在蜜源领域附近进行搜索新蜜源,并按式(13)计算两个蜜源的适应度值,按照模拟退火机制选择是否接受新蜜源。

步骤5当某个蜜源未更新的次数超过limit,则舍弃该蜜源,蜜源对应的引领蜂变为侦察蜂,并按式(12)产生一个新的蜜源,并按式(13)计算该蜜源的适应度值。

步骤6记录本次迭代的最优解,模拟退火算法按式(15)进行降温。

步骤7检查是最优蜜源适应度是否满足精度要求或迭代次数达到最大迭代次数或当前温度达到终止温度,若满足条件则算法结束,输出最优的解;否则k=k+1,跳转到步骤2。

3 SA-ABC-Kriging插值算法流程

模拟退火人工蜂群混合算法优化克里金SA-ABC-Kriging(Simulated Annealing and Artificial Bee Colony optimization Kriging)插值算法流程为:首先由井下采集少量指纹组成采集指纹库,将该指纹库信息数据结合Kriging插值构建算法模型;其次对插值算法中的变异函数进行初步拟合,把理论变异函数球状模型参数映射到模拟退火算法与人工蜂群算法中;再次由模拟退火算法与人工蜂群算法寻优,输出全局最优的参数;最后完成建立SA-ABC-Kriging插值算法模型,具体流程如图1所示。

图1 插值算法流程图

4 煤矿井下指纹库构建方法流程

煤矿井下指纹库构建方法流程需要经过采集阶段和插值阶段,才能生成插值井下无线定位指纹库,具体流程如图2所示。

图2 指纹库构建流程图

从图2中可看出,采集阶段首先井下巷道中选取采集点,其次采集点通过无线采集设备扫描各个AP节点的RSSI值传送回服务器,为保障采集数据准确每个点采集20次,然后由服务器对采集点传来20次RSSI值求其平均值与采集点的坐标位置进行式(16)组合,最后存放到采集指纹数据库中,完成采集过程。

采集点的信息数据是按组合的方式存放数据库中,其组合可以表示为:

xi={Xi,Yi,Ri1,Ri2,…,RiP}

(16)

式中P为AP节点数目,RiP表示第i个采集点接收到第P个AP节点的RSSI值,Xi,Yi为第i个采集点坐标位置。

插值阶段首先根据采集指纹数据库选取预测点,其次根据采集指纹数据库生成SA-ABC-Kriging插值算法,再次调用所需观测点的RSSI值,利用SA-ABC-Kriging插值算法对预测点RSSI值进行估算,并存放到插值指纹数据库中,然后将采集指纹数据库和插值指纹数据库进行整合,最终生成插值井下无线定位指纹库。

5 实验结果分析

5.1 实验条件及采集方法

实验条件为贵州某煤矿井下500 m工业以太网已覆盖的回风巷中,巷道截面宽度在4 m左右,井下实验区工程平面如图3所示。

图3 实验区域工程平面图

由图3可看出,实验区域为回风巷,在回风巷500 m区域范围内共放置6个AP终端,AP节点之间距离在80 m内,可实现实验区域无线全覆盖。

采集方法:考虑到煤矿井下特殊地理环境,且井下巷道为二维平面。井下回风巷实验区域长度500 m,井下截面宽度在4 m左右,为此把实验区域分成为100个4 m×3 m小区域,小区域与小区域间距为1 m。在小区域内共有20个点,具体如图4所示。

图4 小区域指纹采集图

由图4可知,在小区域内选取10个点为采集点,10个点为插值估算预测点。由此可见整个实验区域需要用到的采集点应为1 000个点,插值估算预测点应为1 000个点,建立完整井下定位指纹数据库就需要2000个点的信息数据。

采样阶段:实验人员佩戴自制无线采集设备到巷道中采集RSSI数据。其自制无线采集设备由主控芯片STC15W4K56S4、液晶显示模块LCD1602、无线芯片ESP8266EX和锂电池供电模块组成。该设备经过防爆测试,完全到达井下设备本质安全要求。自制无线采集设备工作原理:由主控芯片发送“AT+SCAN”(扫描AP)指令给无线模块,无线模块立即扫描当前位置处各个AP节点返回信息数据(包括IP地址,MAC地址和接收的信号强度指示RSSI值),主控芯片对该信息数据进行处理后,通过无线网络传输给服务器。

为检验SA-ABC-Kriging插值算法的性能,实验人员按照式(16)存放方式和逐点采集方法,点与点之间距离1 m,把实验区域可采集2 000个点的信息数据全部采集完成,并存放到原始井下无线定位指纹库。再从该数据库中按照小区域采集方法把1 000个采集点的信息数据提取出来,组成采集指纹库。

在完成2 000个点的采集任务后,实验人员又重新随机采集100组测试数据,存入测试数据库,为检验性能提供数据支撑。

插值阶段:首先根据100个小区域选取出1 000个预测点,其次根据采集指纹数据库生成Kriging插值算法模型,对SA-ABC算法初始化,设置蜂群总数SN=60,蜜源的数量N=30,蜜源未更新次数limit=100,初始温度T0=600,终止温度Tmin=0,退火系数β=0.96,最大迭代数Kmax=800,迭代数k=0,收敛精度ε=0.01,然后根据SA-ABC-Kriging插值算法流程建立算法模型。

首先从采集指纹数据库调用所需采集点的RSSI值。其次利用SA-ABC-Kriging插值算法对每个预测点RSSI值进行20次估算。再次用20次估算出的RSSI值,求出该预测点的RSSI平均值,已确保每个预测点的RSSI值更精确。然后再将预测点的RSSI平均值存放到插值指纹数据库,并将采集指纹数据库和插值指纹数据库进行整合,最终生成插值井下无线定位指纹库,完成插值过程。

5.2 性能分析

为检验样子本文提出插值算法的插值精度,利用K最邻近算法[20]KNN(K-nearest neighbor)和加权K最邻近算法[21]WKNN(WeightedK-Nearest Neighbor)两种算法验证原始井下无线定位指纹库和插值井下无线定位指纹库的性能。

利用测试数据库中信息数据,带到KNN和WKNN算法进行在线定位,其K设为3。经过50次调用测试数据库中100组测试数据定位运行,统计两个井下定位指纹数据库在2 m内的定位误差累计概率,其结果如表1所示。

表1 指纹库2 m定位误差累计概率对比单位:%

从表1可看出,原始井下无线定位指纹库和插值井下无线定位指纹库定位精度基本一样。再利用KNN算法进行定位,设K为5。经过50次调用测试数据库中100组测试数据定位运行,统计两个井下定位指纹数据库在3 m内的定位误差累计概率,其结果如表2所示。

表2 指纹库3 m定位误差累计概率对比单位:%

图5 3种指纹库定位精度对比图

从表2可看出,插值井下无线定位指纹库可以达到原始井下无线定位指纹库定位精度。由此可见采用本文的方法构建井下指纹库,可使人工采集信号强度的工作量减少50%,且指纹库定位精度不变。

将文献[12]的反距离加权插值法建立文献[12]指纹库、文献[13]的克里金插值算法建立文献[13]指纹库、本文提出SA-ABC-Kriging插值算法建立插值井下无线定位指纹库,三种插值指纹库采用WKNN算法,设K为3。经过100次调用测试数据库中100组测试数据对三种指纹库定位运行,得到其定位性能如图5所示。

从图5可以看出,文献[12]指纹库采用WKNN算法的定位误差较大,定位精度函数收敛性差;文献[13]指纹库定位性能优于文献[12]指纹库,但定位精度函数收敛较慢;而本文指纹库采用WKNN算法定位精度最优,定位精度函数收敛最快。根据上述实验结果,对比三种指纹库定位误差数据,得到定位误差对比如表3所示。

表3 3种指纹库定位误差对比表 单位:m

由表3可知,文献[12]指纹库定位平均误差为3.16 m,文献[13]指纹库定位平均误差为1.98 m,本文指纹库定位平均误差为1.59 m;所以本文提出SA-ABC-Kriging插值算法建立插值井下无线定位指纹库比文献[12]指纹库定位精度提升49.68%,比文献[13]指纹库定位精度提升19.70%。

6 结论

本文针对煤矿井下无线指纹定位技术中离线采集阶段构建指纹库,需要大量采集工作的问题,提出了一种采用SA-ABC-Kriging插值算法构建井下指纹数据库的方法。在实验定位区域内采集少量的指纹库,利用采集指纹数据库构建Kriging插值算法模型,通过模拟退火人工蜂群混合优化算法对理论变异函数搜索全局最优解,从而建立SA-ABC-Kriging插值算法模型;再利用采集指纹数据库中观测点的信息数据通过插值算法模型估算出预测点的信息数据,建立插值数据库,最后将采集指纹数据库和插值指纹数据库生成插值井下无线定位指纹库,该构建方法提升未测量点的插值精度,大幅减少构建指纹库所要指纹的采集量。通过实验表明,本文方法在插值精度和定位精度上都优于传统Kriging插值算法,在定位精度不变的情况下可将指纹库采集工作量减少50%。

在接下来工作中,对SA-ABC-Kriging插值算法进行优化,提升算法性能,进一步提高插值精度和定位精度。