An Improved Location Fingerprint Localization Matching Algorithm in Coal Mine*

LI Lun，DING Enjie*，HAO Lina，ZHANG Lei

(1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China; 2.Internet of Things Perception Mine Research Center，China University of Mining and Technology，Xuzhou Jiangsu 221008，China)

An Improved Location Fingerprint Localization Matching Algorithm in Coal Mine*

LI Lun1，2，DING Enjie1，2*，HAO Lina1，2，ZHANG Lei1，2

(1.School of Information and Electrical Engineering，China University of Mining and Technology，Xuzhou Jiangsu 221116，China; 2.Internet of Things Perception Mine Research Center，China University of Mining and Technology，Xuzhou Jiangsu 221008，China)

The environment of coal mine is very complicated，which requires great accuracy of personnel positioning. Currently，in the mine roadway，the location of the fingerprint localization algorithm based on RSSI(Received Signal Strength Indication)has some deficiencies，such as targeting drift，jitter，and low positioning accuracy.This paper proposes a modified matching localization algorithm.This algorithm combines K nearest neighbor algorithm with the shortest historical path matching and uses speed-limited location estimation compensation algorithm to correct the positioning accuracy.Based on the authentic-measured data from the coal mine tunnel，this article verifies and analyses the error for the improved matching algorithm.The simulation results show that the improved matching algorithm can improve positioning accuracy and meet the requirements of mine personnel positioning，target tracking，and target trajectory querying.

wireless sensor networks;RSSI;location fingerprint;mine tunnels;matching algorithm

随着传感器网络技术、矿山机电通信技术、微机电系统(MEMS)、物联网、云计算技术和大数据的快速发展，感知矿山物联网技术正广泛应用于煤矿开采。然而矿山地质开采条件复杂、生产体系庞大、采掘环境恶劣，需要应用物联网技术进行实时监测监控［1］。感知矿山物联网分别由感知层、传输层和应用层组成［2］。作为运行在应用层的人员定位系统，能够提供井上/下人员信息交流、人员位置感知和环境参数感知等功能。当矿井遭受自然灾害时，系统可以提供实时的矿工位置信息，辅助决策者快速及时地制定出营救方案，减少煤矿人员伤亡和财产损失。

在煤矿巷道中，基于无线传感器网络WSN (Wireless Sensor Networks)的人员定位技术是煤矿安全开采技术中的重要组成部分，它可以保障煤矿企业日常生产安全，提高生产效率。传感器节点定位技术有许多种分类，目前大致可分为基于距离的节点定位和与距离无关的节点定位两大类［3-4］。基于距离的节点定位主要是通过测量传感器节点之间的距离或角度来实现对未知节点的定位，如RSSI (接收信号强度指示)测试法、TOA(到达时间)法、TDOA(到达时间差)法和AOA(到达角)测量法等;与距离无关定位是利用网络内部连通性来实现对未知节点的定位，如质心方法、DV-Hop、Amorphous和APIT是常见的定位方法。总的来说，这两种定位方法应用于不同场景，各有其优缺点。前者对收发节点之间的时间性有严格要求，对硬件条件要求较高，但定位精度相对较高;后者简单易于实现，对硬件要求低，定位精度差。

本文提出了一种改进的指纹定位匹配算法，该算法将K邻近算法和最短历史路径匹配法联合，并利用速度限定位置估计补偿算法对定位精度进行修正，以此获得较高的定位精度。利用在山煤霍尔辛赫煤业井下主运大巷中的实测数据，对改进的匹配算法进行了验证与误差分析。仿真结果表明，由于巷道空间狭窄、并布有支架、电缆和各种管道、时有机车和工人通过、多径干扰、折射、散射、驻波和非视距传输等因素的影响［6］，对无线射频信号的发送与接收存在干扰，改进后的算法能够提高定位精度，误差相对较小，满足矿井人员定位要求。

1 基于RSSI的位置指纹定位算法

位置指纹定位算法［7］是根据传感器节点所在的位置定位卡(标签卡)所接收到的各无线接入点AP(Wireless Access Point)发送的信号强度值大小和待定位传感器节点的坐标信息来计算匹配用户的位置坐标［8］。

1.1 位置指纹算法描述

位置指纹算法分为两个阶段:离线采样阶段和实时定位阶段［9-10］。离线采样阶段的工作是在待定位区域内按照一定的间隔距离确定若干采样点，形成一个采样网格图，并将每个传感器节点测得的信号强度值及其位置信息一同存储在数据库中，这些信息被称为位置指纹(Location Fingerprints)。

离线指纹模拟采样的巷道如图1所示，巷道实际宽度约为3 m，长达几十km，所以在设定采样点坐标时，纵坐标y值根据巷道岩壁的坐标而定(多数巷道呈直线型，拐弯处较少，故此y值变化不大)，而横坐标x值变化较大。为了提高定位精确度，采样间距设定为2 m，即每隔2 m进行一次指纹采样，采样时间为60 s，遍历所需定位巷道，把采样到的数据存储到数据库中，结构和内容如表1。在实验测试过程时，采样时间设定为60 s，然而在实际的工程项目中，为了节省时间及减小项目复杂度，采样时间可以适当减少，减至40 s或者30 s。

图1 巷道模拟采样点

表1 采样点信号特征

由表1采样点特征可得，采样点(m1，m2，m3，…，mi)的坐标为(x，y，z)，其中x=2，4，6，8，…，2n;采掘水平，单位为m，Z值需要自定义设定，依据不同矿山的采掘水平定义Z值。

离线采样阶段指纹信息数据库建立之后，在实时定位阶段，对当前接收到的信号强度值进行处理，通过指纹匹配算法，使得当前的信号强度值和数据库中信号强度值进行最佳匹配度相比，此时终端的位置就估计约为数据库中这个有最佳匹配度信号强度值所在的位置坐标。

实时定位阶段接收到信号强度值也需要进行预处理:若Wi-Fi终端在实时定位阶段没有检测到某个AP的信号强度值，而在离线采样阶段能监测到该AP，则取一个较小的值作为其信号强度值，如-90 dBm。对于实时定位周期内(本文中周期为3 s)，为了减小误差，监测到的同一个AP的信号强度值处理方法与采样阶段相同，由式(1)计算它们的平均值。实时定位阶段对定位的实时性要求较高，接收到的信号强度值个数肯定比采样时的要少，所以数据处理速度也很快，保证了实时性。

1.2 K邻近法描述

K邻近法属于典型的确定性定位算法［11］。1968年，Hart和Cover提出了K邻近法，它是在手指模数据库中搜索与待定位节点接收到的信号强度值进行比较邻近性，K邻近法中K值可取任意值，根据定位环境取合适的K值［12-13］。该理论研究比较成熟，思路简单，易于实现，广泛应用于模式识别领域。

在现有的定位系统中，使用K邻近法的有LandMark和RADAR［14］等。它的定位思想主要是: Wi-Fi终端在某处实时接收到的信号强度特征信息，根据欧氏距离公式计算与该信号数据库中每一个采样点信息的距离，选择距离最小的K个采样点位置，根据这K个点再估计Wi-Fi终端的位置。

在微软RADAR定位系统中，数据库中存储的是来自各个AP信号强度的平均值，实时数据信息和数据库中信息计算完欧氏距离后，取最小值所对应的采样点的位置作为定位估计的位置。用式(2)表示。

其中，n是AP的个数，RSSi是指Wi-Fi终端实时监测到第i个AP的信号强度值，RSSi是指信号数据库中存储的采样点接收到的信号强度平均值。

取K=3时，求由3个最近估测点组成三角形的质心，将质心的坐标作为定位估计的位置坐标，用式(3)计算。

2 改进的定位估计匹配算法

对于位置指纹定位算法来说，实时定位阶段的位置匹配算法是至关重要。矿井巷道与室内环境无线信号传输所受的影响不同，巷道狭长的特点以及多径效应影响对实际收发干扰严重，都使得在研究匹配算法时要契合巷道的需求。在实时定位阶段，Wi-Fi终端接收到信号强度值后首先会对其求均值进行预处理，然后通过K邻近法选出欧氏距离较小的3个匹配值，再次经过深度为3的最短历史路径匹配算法和速度限定位置估计补偿算法共同定位，定位估算出最佳匹配位置。

算法步骤1

K邻近法采用确定性的定位算法是在K邻近法的基础之上，提出适用于煤矿井下改进的定位匹配算法。K邻近法应用在本文算法的前期估计位置的处理上，取K=3，先选出3个最邻近的估测值，用式(4)所示。

通过计算欧氏距离选出3个最邻近点，之后再用最短历史路径匹配算法和速度限定位置估计补偿算法进行改进补偿，提高定位精度。

算法步骤2

最短历史路径匹配算法在定位时，假设t1时刻，待定位节点接收到的信号强度经过前期预处理后的值为S1，其位置为L(t1)，根据计算得出的欧几里德距离，L(t1)对应地图中的3个可能的位置点，而每隔一个较小的时间Δt(Δt=1 s，终端会相应地移动一个小的距离)，待定位的点会接收到新的信号强度值，假设此时的信号强度值为S2，其位置为L(Δt+t1)，根据计算得出的欧几里德距离，选出最小的3个欧氏距离，L(Δt+t1)对应地图中的3个可能的位置点，这样可以滤掉一部分不合理的位置点。随着采集次数的增加，最终能够得出一条欧氏距离最小路径，路径终点即为定位点位置。

如图2所示，终端经过三次位置计算后，最终通过历史路径法得出最短历史路径［15］，估算出黑色六边形的位置即估计位置。图2中所有的点均是离线采样阶段数据库中存储的，每2 m有一个采样点，黑色圆形是t1时刻经欧几里德距离得出的3个位置，黑色正方形是t2时刻经欧几里德距离得出的3个位置，黑色六边形是t3时刻欧几里德距离得出的3个位置，经过历史路径最短距离匹配算法，最终估计的位置是图中标定位节点的位置。其中，红色圆形是离线采样阶段规划的采样点，而在本次实时定位阶段并未估计到的位置。

图2最短历史路径匹配算法(有唯一估计值时)

图2 中的历史路径轨迹是常见的，但是也有找不出唯一定位点的情况出现。如果经过深度为3的最短历史路径找不出唯一定位点时，如图3所示，标有数字1、2、3中的黑色六边形为t3时刻欧几里德距离得出的3个位置。但根据最近历史路径算法，t2时刻的黑色正方形在2 m的步长内找不到唯一的黑色六边形的位置，此处情况下，选定1、2、3定位点的平均值坐标为估算位置，由式(5)所示。

图3 最短历史路径匹配算法(没有唯一估计值时)

算法步骤3

矿井下基于信号强度的位置指纹匹配算法，主要由上述的两种匹配算法组成，为了保证算法的定位精度，提出了速度限定位置估计补偿算法进行算法修正。该补偿算法的基本思想是:矿井下需要定位的有矿工和运输机车，矿工在井下的运动状态有静止、步行和乘坐载人机车，静止和步行时速度较慢，使用上述两种算法的结合算法后定位精度也很高;而在矿工乘坐机车时，机车运行的速度小于10 m/s，若本次定位估计值和上一次定位估计值之间的距离大于10 m时，取两个坐标的均值坐标作为定位估计值，对机车的定位算法补偿也适用该方法。

在矿井巷道的定位过程中，Wi-Fi终端通常可设置每一秒发送和接收到的信号强度值，定位引擎服务器在t时刻根据以上算法(K邻近法和最短历史路径匹配算法)后估算出Wi-Fi终端当前所在位置的坐标为(xt，yt，z)，在(t-1)时刻估计的位置坐标为(xt-1，yt-1，z)，执行以下具体步骤:

①若经式(6)计算得出d＜10 m，则当前估计的位置有效，坐标定为(xt，yt，z);定位结束;修正为

③若修正后的坐标和上一时刻的坐标经式(6)计算得出d;

④若d＜10 m，执行①;

⑤若d≥10 m，执行②;

速度限定位置估计补偿算法可以消除因Wi-Fi终端位置跳变过大而引起的较大误差，采用矿井下最大运行速度来限定定位估计位置，这种方法在一定程度上减小了定位误差。

本文算法流程简易图4所示。

图4 算法流程

3 实验性能比较与结果分析

3.1 实验测试平台

由于煤矿巷道电磁环境的特殊性，无线信号传播的规律与室内传播规律有很大的差别。文中的信号强度值实验数据取自于山煤集团霍尔辛赫煤业有限公司国家物联网示范工程项目所测得，实验平台架构图如图5所示。

图5 实验测试结构

实验平台:Wi-Fi用户终端、无线接入点AP、定位引擎服务器、Aero Scout Analysis无线信号分析软件等;

实验环境:山煤霍尔辛赫煤业井下主运大巷;

实验内容:记录Wi-Fi终端接收到的AP的信号强度值，主要对接收信号强度值(RSSI)在巷道中因时间变化而呈现的浮动和信号强度值随距离变化而呈现的衰减。巷道中的AP安装在墙壁一侧，这是考虑巷道中电缆和通风设备等放置规范而设定的，如图6所示。

图6AP安装在巷道中的位置

3.2 实验算法描述

本文位置指纹定位算法的实验内容为:①对霍尔辛赫煤矿-600 m主运大巷进行规划区域采样，每2 m接收到的信号强度采样一次，形成采样指纹数据库。②实时定位阶段，测试人员以约1 m/s的速度行走，随身携带Wi-Fi终端，上层定位服务器Aero Scout Analysis软件进行每秒一次不间断记录Wi-Fi终端发送上来的RSSI值。③根据以上数据利用改进后的位置指纹定位算法，求其定位误差。

3.3 性能比较及其仿真分析

为了验证算法的可行性，选择在山西霍尔辛赫煤矿-600 m大巷进行离线采样和实时定位信息指纹采集。在实时定位阶段的信号强度值所在位置按1 m/s的速度在计算，最大限度的保证定位的实时性。上层服务器接收到的信号强度值以3 s为一个单位运用深度为3最短历史路径匹配算法计算所得的位置坐标与实际坐标的对照如图7所示。最短历史路径匹配算法是文章提出算法的其中一步，由于巷道内无线信号多径衰落等因素的影响，定位误差有比较大的情况，所以后面一步的速度限定算法会矫正一些前后定位结果浮动较大的情况。速度限定位置估计补偿算法［16］是根据矿井巷道中矿工或机车的行驶速度一般小于10 m/s，本次定位位置与上一次定位位置之间不会超过10 m，改进的算法设定10 m为界来矫正定位误差。

图7 离线采样点和实时定位点位置比较

从图8可以看出，最短历史路径匹配算法定位估计的前后位置距离大于10 m的只有一次，若在定位过程中把后一次的定位结果使用速度限定位置估计补偿算法进行校正后，定位误差会减小，如图9所示。比较图8和图9来看，经速度限定位置估计补偿算法矫正之后，定位误差趋势曲线变得更缓和。从巷道中的实验数据来看，靠近一个AP距离在40 m以内时，算法的定位误差较小，随着远离一个AP向邻近的AP靠近的过程中，误差会呈现先变大后变小的趋势。

图8 最短历史路径匹配算法的误差

图9 速度限定位置估计补偿算法矫正后的误差

如图10所示，误差的变化趋势是开始误差小，随着慢慢远离AP1，误差变大，然后随着远离AP1、接近AP2，误差又变小。整个测试过程是从距离AP1约10 m的距离开始，以1 m/s的速度行走，经过90 s后，定位服务器所采集的信号强度值由位置指纹算法计算后，误差所呈现的趋势。从图9误差趋势来看，距离AP越近，误差就越小。再从矿井下信号强度值变化趋势图来看，距离AP越近，信号强度值变化幅度较大，而距离AP约60 m后信号强度值浮动较小。由此可看出，随着距离增加，信号强度值变化幅度大时，算法对位置的区别度就越大，误差就越小。反之，从总体算法误差趋势变化图来看，距离AP越远，误差就越大;当靠近下一个AP时，误差又会变小。

图10 总体算法误差趋势变化

本文改进的定位匹配算法在矿井巷道中的定位情况与在同样的实验场景下使用微软RADAR定位系统的算法进行实验比较:离线采样阶段的信号采集、信息存储和上面介绍的方法相同，区别在于实时定位阶段的匹配原理不同［17］。这两种方法使用的实验数据的采集都在霍尔辛赫煤矿-600 m水平主运大巷中测试，每隔2 m进行一次信号采样，实时定位时测试人员手持Wi-Fi终端以1 m/s的速度行走，服务器中记录软件同步对Wi-Fi终端接收到的无线信号特征进行记录。分别使用典型算法和本文提出的改进算法进行定位估计，得出的定位误差如图11所示。

图11 典型算法和改进算法误差比较

从图11可以看出，典型算法在矿井巷道中的定位误差要比改进后的算法大很多，这也验证改进后的算法在矿井巷道中使用的可行性。从误差趋势角度上来看，改进后算法的误差大小趋势和典型算法一致，都是随着Wi-Fi终端远离AP，而误差变大，靠近AP时误差变小。典型算法中误差较大，最小误差5 m，最大误差达到26 m，且定位时位置浮动较大。改进后的算法得出最大定位误差为18 m，最小定位误差为1 m。

4 结论

针对煤矿巷道自身的电磁环境特点，在位置指纹定位算法的基础上提出一种改进的定位方法。在算例中，将离线采样的指纹数据库和实时定位的数据进行比对，采用K邻近法、最短历史路径匹配法相结合，并利用速度限定位置估计补偿方法逐步修正定位结果。实验数据的采集全部来自山西霍尔辛赫煤矿-600 m水平主运大巷，通过改进匹配算法进行匹配定位估计，节点定位位置浮动较大，利用速度限定位置估计补偿算法来减少位置浮动较大的问题，提高了定位精度。仿真分析得出最大定位误差为18 m，最小定位误差为1 m，对于长达几十km的狭长矿井巷道而言，最大误差18 m是可以接受的范围。

［1］吴立新，汪云甲，丁恩杰，等.三论数字矿山——借力物联网保障矿山安全与智能采矿［J］.煤炭学报，2012，37(3):357 -365.

［2］钱建生，孙彦景.煤矿安全生产物联网关键技术及研究［C］//中国煤炭学会成立五十周年高层学术论坛论文集，2012.

［3］Malekpour A，Ling T C，Lim W C.Location Determination Using Radio Frequency RSSI and Deterministic Algorithm［C］//Communication Networks and Services Research Conference，2008.CNSR 2008.6th Annual.IEEE，2008:488-495.

［4］邓彬伟，黄光明.无线传感器网络移动节点辅助定位算法［J］.仪器仪表学报，2011，32(3):563-570.

［5］陈锡剑，程良伦.基于RSSI的功率匹配定位算法的研究与实现［J］.传感技术学报，2013，26(5):710-714.

［6］任维政，徐连明，邓中亮，等.基于RSSI的测距差分修正定位算法［J］.传感技术学报，2008，27(7):1247-1248.

［7］Jain A K，Feng J，Nandakumar K.Fingerprint Matching［J］.Computer，2010，43(2):36-44.

［8］张明华，张申生，曹健.无线局域网中基于信号强度的室内定位［J］.计算机科学，2007，34(6):68-75.

［9］Brunato M，Battiti R.Statistical Learning Theory for Location Fingerprinting in Wireless LANs［J］.Computer Networks，2005，47 (6):825-845.

［10］Fang S H，Lin T N.A Dynamic System Approach for Radio Location Fingerprinting in Wireless Local Area Networks［J］.IEEE Transactions on Communications，2010，58(4):1020-1025.

［11］Jiang Shengyi，Pang Guansong，Wu Meiling.An Improved K-Nearest-Neighbor Algorithm for Text Categorization［J］.Expert Systems with Applications，2012，29(1):1503-1509.

［12］Saxena M，Gupta P，Jain B N.Experimental Analysis of RSSIBased Location Estimation in Wireless Sensor Networks［C］// Communication Systems Software and Middleware and Workshops，2008.COMSWARE 2008.3rd International Conference on IEEE，2008:503-510.

［13］Huang C N，Chan C T.ZigBee-Based Indoor Location System by k-Nearest Neighbor Algorithm with Weighted RSSI［J］.Procedia Computer Science，2011(5):58-65.

［14］Bahl P，Padmanabhan V N.RADAR:An in-Building RF-Based User Location and Tracking System［C］//INFOCOM 2000.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE.Ieee，2000，2:775-784.

［15］毛少武，张焕国，黄崇超，等.改进的K最短路径算法在通信网络中的应用［J］.武汉大学学报(理学版)，2013，59(6):534-538.

［16］郭红成，罗海勇，尹浩，等.基于线性插值和动态指纹补偿的分布式定位算法［J］.传感技术学报，2009，22(12):7795-1801.

［17］Narzullaev A，Park Y，Yoo K，et al.A Fast and Accurate Calibration Algorithm for Real-Time Locating Systems Based on The Received Signal Strength Indication［J］.AEU-International Journal of Electronics and Communications，2011，65(4):305-311.

李论(1984-)，男，土家族，贵州省印江县人，中国矿业大学信息与电气工程学院通信与信息系统专业硕士研究生，主要研究方向为无线传感器网络，liluncumt@163.com;

丁恩杰(1962-)，男，山东青岛人，博士，教授，博士生导师，中国矿业大学物联网(感知矿山)研究中心常务副主任，主要研究方向为无线传感器网络、现场总线与煤矿物联网及其自动化，enjied@cumt.edu.cn。

一种改进的煤矿井下指纹定位匹配算法*

李论1，2，丁恩杰1，2*，郝丽娜1，2，张雷1，2
(1.中国矿业大学信息与电气工程学院，江苏徐州221116;2.中国矿业大学物联网(感知矿山)研究中心，江苏徐州221008)

煤矿井下环境复杂多变，对人员精确定位技术挑战很大。目前矿井巷道中采用基于接收信号强度指示RSSI(Received Signal Strength Indication)的位置指纹定位算法存在定位目标漂移、抖动和定位精度不高等问题。提出一种改进的指纹定位匹配算法，该算法将K邻近算法和最短历史路径匹配法联合并利用速度限定位置估计补偿算法对定位精度进行修正。利用在煤矿巷道中的实测数据，对改进的匹配算法进行了验证与误差分析。仿真结果表明，改进后的算法能够提高定位精度，满足矿井人员定位、目标跟踪和目标轨迹查询等要求。

无线传感器网络;RSSI;指纹定位;矿井巷道;匹配算法

TP929.4

A

1004－1699(2014)03－0388－06

2013-09-12修改日期:2014-02-25

C:6150;6210C;7110

10.3969/j.issn.1004－1699.2014.03.022

项目来源:国家科技支撑计划资助项目(2012BAH12B01，2012BAH12B02);国家高技术研究发展计划(863)资助项目(2013AA06A411)