0 引言
在井下无线传感器网络中，可通过网络MAC地址、接收信号强度信息(RSSI)和传输时间等进行人员定位[1]。在井下无线定位方法中，基于AOA(到达角度)的方法[2]计算复杂度高，基于TOA(到达时间)[3]、TDOA(到达时间差)[4]的方法对设备有严格的时间同步要求，而基于RSSI的方法获取定位信号强度方便，功耗低、成本低，是一种较好的井下定位方式[5-7]。
基于RSSI的井下定位方法有三边定位、质心定位和指纹定位等。尚俊龙等[8]提出了井下加权三边定位算法，用加权三边测算出待测点位置，定位精度为3 m；赵彤等[9]提出了井下节点合作加权质心定位算法，利用改进的小区域加权质心定位算法对待测点进行定位，定位精度为1.5 m，但其实验场地为楼道，与井下环境差距较大；王永星等[10]提出了基于信息传输模型的井下目标定位算法，利用最小二乘法建立指纹模型，定位精度为2.73 m。董建平等[11]提出了基于指纹模的井下定位算法，利用采样点信息形成指纹数据库，并利用K近邻算法进行在线匹配定位，但该方法存在以下问题：指纹数据库未进行数据分类，定位时必须计算出全部参考点的欧氏距离，才能得到K个最近的参考点，计算量较大，实时性不好；在K近邻算法中采用K个点的平均值计算定位位置，未考虑距离较远和较近的参考点的权重值问题，从而影响到定位精度。
针对上述问题，本文提出了基于聚类和K近邻算法的井下人员定位算法，用二分k-means聚类算法[12-13]对井下巷道中采集的数据进行分类，建立离线指纹数据库；用动态修正器反馈井下巷道中的电磁变化量，实时修正权重值；再利用软硬件动态修正加权K近邻算法(Software and Hardware Dynamic Correction WKNN，SAHDC-WKNN)进行在线实时位置估算。实验结果表明，该无线定位算法提高了定位系统的稳定性和实时性，定位精度达到1.62 m。
1 煤矿井下人员定位系统结构及原理
1.1 系统结构
煤矿井下人员定位系统由地面控制中心和井下的光纤交换机、AP(接入点)、动态修正器和井下作业人员携带的无线移动终端等组成，如图1所示。
图1 井下人员定位系统结构
Fig.1 Structure of underground personnel positioning system
1.2 系统原理
井下人员定位过程包括离线建库和实时定位2个阶段，如图2所示。
图2 井下人员定位系统原理
Fig.2 Principle of underground personnel positioning system
离线建库阶段包含采样和聚类生成离线指纹数据库。
采样：在井下巷道中选取采样点，测量该点的物理位置；利用自制无线移动终端多次采集该点的RSSI值，通过无线网络传输采样数据并存储到原始信息数据库。按照这种方法采集所有采样点的数据，由服务器对所有采样点RSSI求平均值，将RSSI值和采样点物理位置信息进行组合并存入原始信息数据库。在采样的同时，动态修正器也采集RSSI数据，通过无线网络传输并存储到动态修正数据库。
聚类生成离线指纹数据库：利用二分k-means聚类算法对原始信息数据库中所有采样点的数据进行聚类分析，得到离线指纹数据库。
实时定位阶段：一方面，待测点通过无线移动终端采集实时RSSI值并传送到在线定位数据库；另一方面，动态修正器也实时采集RSSI值，传送到动态修正数据库。利用待测点和动态修正器的离线数据和实时数据，用SAHDC-WKNN算法计算权重值，结合离线指纹数据库中待测点的物理位置信息估算其实时位置。
2 二分k-means聚类算法
2.1 原始信息数据库的建立
设m个采样点的位置坐标为(x1,y1),(x2,y2),…,(xm,ym)，在每个采样点能够获得n个AP节点的RSSI值，则第i个采样点接收的RSSI值的组合可表示为
Ri=(Ri1,Ri2,…,Rin)
(1)
式中Rin为第i个采样点接收的第n个AP节点的RSSI值，i=1,2,…,m。
将采样点坐标及其接收的RSSI值组合起来，表示为
Mi=(Ri1,Ri2,…,Rin,xi,yi)
(2)
将m个采样点的数据都以式(2)所示的数据结构存储到原始信息数据库中，以备聚类运算时调用。
2.2 标准k-means聚类算法原理
设聚类数目为k(k≤m)，经过标准k-means聚类算法生成的簇集合为C={C1,C2,…,Ck},每个簇的中心点Ok为
(3)
由式(3)可得标准k-means聚类算法的目标函数为
(4)
标准k-means聚类算法的目标是找到最小化误差平方和的聚类结果。具体来说，首先设置聚类个数k，从数据集中选择k个初始中心点；然后将每一个数据对象指派到距离最近的中心点所属的类中，从而构成k个簇；计算每个簇中包含的数据对象的平均值，将其作为簇中心点的新值；重复进行指派和更新这2个步骤，对簇的分布进行迭代更新，直到簇中样本不再发生变化，整个聚类过程完成。
2.3 二分k-means聚类算法流程
二分k-means聚类算法将所有点看作一个簇，将这个簇分裂为2个簇，之后迭代这个过程，每次都选取一个簇进行分裂，并将其分为2个新簇，最终得到k个簇。
用二分k-means聚类算法生成井下人员定位离线指纹数据库时，输入为m个采样点的组合数据Mi和聚类个数k，输出为最终聚类结果。具体算法流程如下：
(1) 初始化簇表，将m个采样点组合成一个簇。
(2) 从簇表中取出一个簇，设聚类数目为2，使用标准k-means聚类算法对选定的簇进行聚类。
(3) 从聚类结果中选取误差平方和最小的一组簇，将其添加到簇表中。
(4) 判断簇数量是否达到k个，若达到则聚类结束，否则跳转到步骤(2)。
与标准k-means聚类算法相比，二分k-means聚类算法的聚类结果更加稳定，但计算时间也更长。因为建立的是离线指纹数据库，在实时定位阶段不需要重复计算，离线建库阶段增加的计算时间可以不用考虑，所以，二分k-means聚类算法更适用于建立无线定位离线指纹数据库[14-15]。
3 SAHDC-WKNN算法
SAHDC-WKNN算法中的权重值wi由2个部分组成[16-17]：一部分是与待测点欧氏距离最小的K(K≤P,P为巷道中安装的动态修正器的数量)个采样点的权重值wsi；另一部分是与待测点欧氏距离最小的K个动态修正器的权重值whi。
(1) 设实时定位阶段待测点D接收到的RSSI信号的平均值集合为(RD1，RD2,…,RDn),则D点和第i(i=1,2,…,K)个采样点的欧氏距离为
(5)
与待测点欧氏距离最小的K个采样点的权重值wsi为
(6)
(7)
(2) 与待测点欧氏距离最小的K个动态修正器接收的数据包含离线数据和实时数据。离线数据集合GOL为
(8)
式中
为离线建库阶段第K个动态修正器接收的第n个AP节点的RSSI值。
对GOL中的数据求平均值：
(9)
实时数据集合GRT为
(10)
式中
为实时定位阶段第K个动态修正器接收的第n个AP节点的RSSI值。
对GRT中的数据求
的标准差si：
(11)
与待测点欧氏距离最小的K个动态修正器的权重值whi为
(12)
(13)
由式(6)和式(12)得到权重值wi为
(14)
(3) 结合离线指纹数据库中待测点的物理位置信息，求待测点的实时位置(X,Y)：
(15)
4 实验分析
4.1 设备选用及测点布置
考虑到煤矿井下各类机电设备电磁干扰严重、杂物堆放、人员设备移动等因素，选取贵州某煤矿井下回风巷、切眼和运输巷共计896 m的巷道进行实验，如图3所示。巷道中共安装了9个动态修正器，回风巷中3个，切眼中2个，运输巷中4个。
根据巷道的作业环境和走向，将AP之间的距离控制在80 m内，实现井下巷道无线网络全覆盖且无盲点。选用本质安全型无线AP，2.4 GHz频段，同时限制WiFi发射功率不超过100 mW。自制动态修正器和无线移动终端主要由主控芯片STC8A8K64S4A12、WiFi模块ESP8266EX和电源模块等组成，经过防爆测试，符合煤矿井下设备本质安全性要求[18-22]。
图3 井下实验巷道
Fig.3 Underground experiment roadway
根据巷道截面宽度，笔者设计并定制了一种由尼龙棒组成的田字格形状的可拆卸塑料架子(可拆解成日字形或口字形)，长宽均为3 m，一次可放9个无线移动终端，能同时采集9个采样点，大大提高了采集效率。在实际采样过程中，采样点与采样点的间距基本控制在1.5～2 m，每个采样点采集10次RSSI数据，共1 724个采样点。同时，测试人员另外采集了102次测试数据，组成测试数据集。
4.2 定位结果
将采样点数据全部存放到原始信息数据库，进行相应处理后，通过二分k-means聚类算法建立离线指纹数据库。设置k值为1—9，用WKNN算法和SAHDC-WKNN算法进行实时定位，定位成功率(误差在2 m以下)对比见表1。
表1 WKNN算法和SAHDC-WKNN算法定位成功率对比
Table 1 Comparison of positioning success rate of WKNN algorithm and SAHDC-WKNN algorithm
从表1可看出，当k值取3时能达到较好的定位效果，同时计算量适中，因此，SAHDC-WKNN算法中k值定为3。
实时定位阶段，作业人员携带无线移动终端进入测试区域后，将实时接收到的RSSI值发送回服务器，系统将该RSSI值存放到在线定位数据库中，再调用权值修正程序、动态修正WKNN程序进行井下作业人员位置估算。设(xs，ys)为井下作业人员实际的物理位置坐标(实测坐标)，(xe，ye)为定位系统估算出的井下作业人员物理位置坐标(估算坐标)，用式(16)、式(17)计算系统定位标准误差E(i)和平均误差
结果见表2。
(16)
(17)
表2 SAHDC-WKNN算法定位结果
Table 2 positioning results of SAHDC-WKNN algorithm m
从表2可看出，最小标准误差为0.46 m，最大标准误差为3.26 m，系统的平均误差为1.62 m。
4.3 对比分析
通过在线定位数据库中所有待测点的数据，采用NN(最近邻)，KNN(K近邻)，WKNN(加权K近邻)，SAHDC-WKNN等4种近邻算法进行定位，用每种算法进行500次独立定位并计算误差，得到定位误差对比，如图4所示。
从图4可看出，SAHDC-WKNN算法的误差比最低，定位精度最高。
实时性也是井下人员定位系统的一个很重要的性能指标，将“未聚类分析+KNN”[11]、“聚类分析+WKNN”与本文提出的“聚类分析+SAHDC-WKNN”算法的精度和实时性进行对比，结果见表3。
从表3可看出，与“未聚类分析+KNN”相比，本文算法的精度更高，实时性更好；与“聚类分析+WKNN”相比，本文算法的运算时间略有增加，但定位精度提高了37.21%。因此，本文提出的“聚类分析+SAHDC-WKNN”算法的定位效果最好，更能满足煤矿井下人员定位要求。
图4 定位误差对比
Fig.4 Comparison of positioning error
表3 算法定位精度与实时性比较
Table 3 Comparison of positioning accuracy and real-time performance of the algorithms
5 结论
(1) 针对煤矿井下特定的地理和通信环境，提出了基于聚类和K近邻算法的井下人员定位算法。通过二分k-means聚类算法对离线数据进行分类，提高了定位算法实时性；通过在巷道中增加动态修正器来实时反馈井下电磁环境情况，动态修正权重值，提高了定位算法精度。
(2) 实验分析结果表明，所提定位算法的最小标准误差为0.46 m，最大标准误差为3.26 m，平均误差为1.62 m。对比分析结果表明，与未进行聚类分析的算法相比，本文算法的精度更高，实时性更好；与未动态修正权重值的算法相比，本文算法的运算时间略有增加，但定位精度提高了37.21%。
(3) 在接下来的工作中，应继续优化无线定位算法，提高定位精度，在定位性能不变的前提下减少采样点数量。
参考文献：
[1] 孙继平.煤矿信息化自动化新技术与发展[J].煤炭科学技术,2016,44(1):19-23.
SUN Jiping.New technology and development of mine informatization and automation[J].Coal Science and Technology,2016,44(1):19-23.
[2] 闫雷兵,陆音,张业荣.基于改进最小二乘算法的TDOA/AOA定位方法[J].电波科学学报,2016,31(2):394-400.
YAN Leibing,LU Yin,ZHANG Yerong. Improved least-squares algorithm for TDOA/AOA-based localization[J].Chinese Journal of Radio Science,2016,31(2):394-400.
[3] 孙继平,蒋恩松.基于WiFi信号二次扩频的矿井TOA测距方法[J].工矿自动化,2017,43(10):53-58.
SUN Jiping,JIANG Ensong. Mine TOA ranging method based on re-spread spectrum to WiFi signal[J].Industry and Mine Automation,2017,43(10):53-58.
[4] 孙哲星,孙继平.异步测时矿井人员精确定位方法[J].煤炭学报,2018,43(5):1464-1470.
SUN Zhexing,SUN Jiping.Underground coal mine accurate personnel positioning method based on asynchronous time-measuring[J].Journal of China Coal Society,2018,43(5):1464-1470.
[5] FANG Xuming,JIANG Zonghua,NAN Lei,et al.Optimal weighted K-nearest neighbor algorithm for wireless sensor network fingerprint location in noisy environment[J].IET Communications,2018,12(10):1171-1177．
[6] 孙哲星.基于时间测距的矿井人员定位方法研究[J].工矿自动化,2018,44(4):30-33.
SUN Zhexing.Research on mine personnel positioning method based on time range[J].Industry and Mine Automation,2018,44(4):30-33.
[7] 钱志鸿,孙大洋,LEUNG Victor.无线网络定位综述[J].计算机学报,2016,39(6):1237-1256.
QIAN Zhihong,SUN Dayang,LEUNG Victor. A survey on localization model in wireless networks[J].Chinese Journal of Computers,2016,39(6):1237-1256.
[8] 尚俊龙,胡建华,邓红卫.基于加权三边测算的井下人员精确定位研究[J].中国安全科学学报,2011,21(2):126-130.
SHANG Junlong,HU Jianhua,DENG Hongwei. Accurate positioning of mine staff based on measurement of weighted trilateration[J].China Safety Science Journal,2011,21(2):126-130.
[9] 赵彤,李先圣,张雷,等.煤矿井下节点合作加权质心定位算法[J].工矿自动化,2018,44(8):32-38.
ZHAO Tong,LI Xiansheng,ZHANG Lei,et al.Weighted centroid localization algorithm based on node cooperation in coal mine underground[J].Industry and Mine Automation,2018,44(8):32-38.
[10] 王永星,华钢,徐永刚,等.基于信号传输模型的指纹井下目标定位算法[J].中国科技论文,2015,10(20):2463-2466.
WANG Yongxing,HUA Gang,XU Yonggang,et al.Localization algorithm of coal mine miner based on the signal transmission model fingerprint[J].China Sciencepaper,2015,10(20):2463-2466.
[11] 董建平,杨诚,陆小丽.基于WiFi的井下指纹模定位算法[J].工矿自动化,2014,40(10):87-89.
DONG Jianping,YANG Cheng,LU Xiaoli. Underground fingerprint module positioning algorithm based on WiFi[J].Industry and Mine Automation,2014,40(10):87-89.
[12] 张宪超.数据聚类[M].北京:科学出版社,2017.
[13] 陈平华,陈传瑜.基于满二叉树的二分K-means聚类并行推荐算法[J].计算机工程与科学,2015,37(8):1450-1457.
CHEN Pinghua,CHEN Chuanyu. A bisecting K-means clustering parallel recommendation algorithm based on full binary tree[J].Computer Engineering &Science,2015,37(8):1450-1457.
[14] 杨慧琳,黄智刚,刘久文,等.基于核模糊C均值指纹库管理的WIFI室内定位方法[J].浙江大学学报(工学版),2016,50(6):1126-1133.
YANG Huilin,HUANG Zhigang,LIU Jiuwen,et al.WIFI fingerprinting localization based on kernel fuzzy C-means II clustering[J].Journal of Zhejiang University (Engineering Science),2016,50(6):1126-1133.
[15] XUE Weixing,YU Kegen,HUA Xianghong,et a1. APs' virtual positions based reference point clustering and physical distance based weighting for indoor WiFi positioning[J].IEEE Internet of Things Journal,2018,5(4):3031-3042．
[16] 石欣,印爱民,张琦.基于K最近邻分类的无线传感器网络定位算法[J].仪器仪表学报,2014,35(10):2238-2247.
SHI Xin,YIN Aimin,ZHANG Qi.Localization in wireless sensor networks based on K-nearest neighbor[J].Chinese Journal of Scientific Instrument,2014,35(10):2238-2247.
[17] 田洪亮,钱志鸿,梁潇,等.离散度WKNN位置指纹Wi-Fi定位算法[J].哈尔滨工业大学学报,2017,49(5):94-99.
TIAN Hongliang,QIAN Zhihong,LIANG Xiao,et al.Discrete degree WKNN location fingerprinting algorithm based on Wi-Fi[J].Journal of Harbin Institute of Technology,2017,49(5):94-99.
[18] 莫树培.煤矿井下配电系统电容电流的测量方法研究[J].煤炭技术,2014,33(9):209-211.
MO Shupei.Research on measuring method of capacitive current of distribution system in coal mine[J].Coal Technology,2014,33(9):209-211.
[19] 王怡婷,郭红.基于层次聚类的 WiFi 室内位置指纹定位算法[J]. 福州大学学报(自然科学版),2017,45(1):8-15.
WANG Yiting,GUO Hong. WiFi indoor position fingerprinting localization algorithm based on hierarchical clustering [J]. Journal of Fuzhou University (Natural Science Edition),2017,45(1):8-15.
[20] 莫树培.悬臂式掘进机截齿截割模型构建及受力分析[J].煤矿机械,2015,36(1):113-115.
MO Shupei.Force analysis and modeling of cutting pick of boom roadheader[J].Coal Mine Machinery,2015,36(1):113-115.
[21] 孙利民,张书钦,李志,等. 无线传感器网络理论及应用[M].北京:清华大学出版社,2018.
[22] 孙继平,李晨鑫.基于TOA技术的煤矿井下人员定位精度评价方法[J].煤炭科学技术,2014,42(3):66-68.
SUN Jiping,LI Chenxin.Evaluation method of positioning accuracy for mine underground personnel based on TOA technology[J].Coal Science and Technology,2014,42(3):66-68.