基于聚类和K近邻算法的井下人员定位算法.pdf

扫码移动阅读第４５卷第４期２０１９年４月工矿自动化ＩｎｄｕｓｔｒｙａｎｄＭｉｎｅＡｕｔｏｍａｔｉｏｎＶｏｌ．４５Ｎｏ．４Ａｐｒ．２０１９文章编号１６７１－２５１Ｘ（２０１９）０４－００４３－０７ＤＯＩ１０．１３２７２／ｊ．ｉｓｓｎ．１６７１－２５１ｘ．２０１８１１００７２基于聚类和Ｋ近邻算法的井下人员定位算法莫树培１，２，唐琎２，汪郁１，赖普坚２，金礼模１（１．贵州工业职业技术学院图书与信息中心，贵州贵阳５５１４００；２．中南大学信息科学与工程学院，湖南长沙４１００８３）摘要针对现有基于指纹模的井下定位算法存在的计算量大、实时性低、定位精度较低的问题，提出了基于聚类和Ｋ近邻算法的井下人员定位算法。用二分ｋ－ｍｅａｎｓ聚类算法对采集的ＲＳＳＩ数据进行分类，建立离线指纹数据库；无线移动终端和动态修正器实时采集ＲＳＳＩ值，分别存储到在线定位数据库和动态修正数据库；根据待测点和动态修正器的离线数据和实时数据，采用软硬件动态修正加权Ｋ近邻算法计算权重值，结合离线指纹数据库中待测点的物理位置信息估算其实时位置。实验分析结果表明，所提定位算法的最小标准误差为０．４６ｍ，最大标准误差为３．２６ｍ，平均误差为１．６２ｍ。对比分析结果表明，与未进行聚类分析的算法相比，本文算法的精度更高，实时性更好；与未动态修正权重值的算法相比，本文算法的运算时间略有增加，但定位精度提高了３７．２１％。关键词井下人员定位；指纹定位；二分ｋ－ｍｅａｎｓ聚类算法；软硬件动态修正加权Ｋ近邻算法；动态修正中图分类号ＴＤ６５５．３文献标志码Ａ收稿日期２０１８－１１－３０；修回日期２０１９－０３－１０；责任编辑胡娴。基金项目贵州省科技厅项目（黔科合ＬＨ字〔２０１６〕７０６９）；贵州工业职业技术学院校级科研课题（２０１８００９）。作者简介莫树培（１９８２－），男，布依族，贵州都匀人，副教授，硕士，主要研究方向为无线网络传感器、模式识别与人工智能，Ｅ－ｍａｉｌ４１８５１３４８＠ｑｑ．ｃｏｍ。引用格式莫树培，唐琎，汪郁，等．基于聚类和Ｋ近邻算法的井下人员定位算法［Ｊ］．工矿自动化，２０１９，４５（４）４３－４８．ＭＯＳｈｕｐｅｉ，ＴＡＮＧＪｉｎ，ＷＡＮＧＹｕ，ｅｔａｌ．ＵｎｄｅｒｇｒｏｕｎｄｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｌｕｓｔｅｒｉｎｇａｎｄＫ－ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒａｌｇｏｒｉｔｈｍ［Ｊ］．ＩｎｄｕｓｔｒｙａｎｄＭｉｎｅＡｕｔｏｍａｔｉｏｎ，２０１９，４５（４）４３－４８．ＵｎｄｅｒｇｒｏｕｎｄｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｌｕｓｔｅｒｉｎｇａｎｄＫ－ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒａｌｇｏｒｉｔｈｍＭＯＳｈｕｐｅｉ１，２，ＴＡＮＧＪｉｎ２，ＷＡＮＧＹｕ１，ＬＡＩＰｕｊｉａｎ２，ＪＩＮＬｉｍｏ１（１．ＢｏｏｋａｎｄＩｎｆｏｒｍａｔｉｏｎＣｅｎｔｅｒ，ＧｕｉｚｈｏｕＩｎｄｕｓｔｒｙＰｏｌｙｔｅｃｈｎｉｃＣｏｌｌｅｇｅ，Ｇｕｉｙａｎｇ５５１４００，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＣｅｎｔｒａｌＳｏｕｔｈＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８３，Ｃｈｉｎａ）ＡｂｓｔｒａｃｔＩｎｖｉｅｗｏｆｐｒｏｂｌｅｍｓｏｆｌａｒｇｅａｍｏｕｎｔｏｆｃａｌｃｕｌａｔｉｏｎ，ｌｏｗｒｅａｌ－ｔｉｍｅｐｅｒｆｏｒｍａｎｃｅａｎｄｌｏｗｐｏｓｉｔｉｏｎｉｎｇａｃｃｕｒａｃｙｏｆｅｘｉｓｔｉｎｇｆｉｎｇｅｒｐｒｉｎｔ－ｂａｓｅｄｕｎｄｅｒｇｒｏｕｎｄｐｏｓｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍ，ｕｎｄｅｒｇｒｏｕｎｄｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｃｌｕｓｔｅｒｉｎｇａｎｄＫ－ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄ．Ｂｉｓｅｃｔｉｎｇｋ－ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｉｓｕｓｅｄｔｏｃｌａｓｓｉｆｙｃｏｌｌｅｃｔｅｄＲＳＳＩｄａｔａｔｏｅｓｔａｂｌｉｓｈａｎｏｆｆｌｉｎｅｆｉｎｇｅｒｐｒｉｎｔｄａｔａｂａｓｅ．ＲｅａｌｔｉｍｅＲＳＳＩｖａｌｕｅｓａｒｅｃｏｌｌｅｃｔｅｄｂｙｗｉｒｅｌｅｓｓｍｏｂｉｌｅｔｅｒｍｉｎａｌａｎｄｄｙｎａｍｉｃｃｏｒｒｅｃｔｏｒａｎｄｓｔｏｒｅｄｉｎｏｎｌｉｎｅｐｏｓｉｔｉｏｎｉｎｇｄａｔａｂａｓｅａｎｄｄｙｎａｍｉｃｃｏｒｒｅｃｔｉｏｎｄａｔａｂａｓｅｒｅｓｐｅｃｔｉｖｅｌｙ．Ａｃｃｏｒｄｉｎｇｔｏｏｆｆｌｉｎｅｄａｔａａｎｄｒｅａｌ－ｔｉｍｅｄａｔａ，ｗｅｉｇｈｔｖａｌｕｅｉｓｃａｌｃｕｌａｔｅｄｕｓｉｎｇｓｏｆｔｗａｒｅａｎｄｈａｒｄｗａｒｅｄｙｎａｍｉｃｃｏｒｒｅｃｔｉｏｎｗｅｉｇｈｔｅｄＫ－ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒａｌｇｏｒｉｔｈｍ，ａｎｄｒｅａｌ－ｔｉｍｅｐｏｓｉｔｉｏｎｉｓｅｓｔｉｍａｔｅｄｂｙｃｏｍｂｉｎｉｎｇｔｈｅｐｈｙｓｉｃａｌｌｏｃａｔｉｏｎｉｎｆｏｒｍａｔｉｏｎｏｆｔｈｅｐｏｉｎｔｔｏｂｅｍｅａｓｕｒｅｄｉｎｔｈｅｏｆｆｌｉｎｅｆｉｎｇｅｒｐｒｉｎｔｄａｔａｂａｓｅ．Ｔｈｅｅｘａｍｐｌｅａｎａｌｙｓｉｓｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｍｉｎｉｍｕｍｓｔａｎｄａｒｄｅｒｒｏｒｏｆｔｈｅｐｒｏｐｏｓｅｄｐｏｓｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｉｓ０．４６ｍ，ｔｈｅｍａｘｉｍｕｍｓｔａｎｄａｒｄｅｒｒｏｒｉｓ３．２６ｍ，ａｎｄｔｈｅａｖｅｒａｇｅｅｒｒｏｒｉｓ１．６２ｍ．Ｔｈｅｒｅｓｕｌｔｓｏｆｃｏｍｐａｒａｔｉｖｅａｎａｌｙｓｉｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｈａｓｈｉｇｈｅｒｐｒｅｃｉｓｉｏｎａｎｄｂｅｔｔｅｒｒｅａｌ－ｔｉｍｅｐｅｒｆｏｒｍａｎｃｅｔｈａｎｔｈｅａｌｇｏｒｉｔｈｍｗｉｔｈｏｕｔｃｌｕｓｔｅｒｉｎｇａｎａｌｙｓｉｓ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅａｌｇｏｒｉｔｈｍｗｉｔｈｏｕｔｄｙｎａｍｉｃｃｏｒｒｅｃｔｉｏｎｏｆｗｅｉｇｈｔｓ，ｔｈｅｃｏｍｐｕｔａｔｉｏｎｔｉｍｅｏｆｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｓｌｉｇｈｔｌｙｉｎｃｒｅａｓｅｄ，ｂｕｔｔｈｅｐｏｓｉｔｉｏｎｉｎｇａｃｃｕｒａｃｙｉｓｉｎｃｒｅａｓｅｄｂｙ３７．２１％．ＫｅｙｗｏｒｄｓＵｎｄｅｒｇｒｏｕｎｄｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇ；ｆｉｎｇｅｒｐｒｉｎｔｐｏｓｉｔｉｏｎｉｎｇ；ｂｉｓｅｃｔｉｎｇｋ－ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍ；ｓｏｆｔｗａｒｅａｎｄｈａｒｄｗａｒｅｄｙｎａｍｉｃｃｏｒｒｅｃｔｉｏｎｗｅｉｇｈｔｅｄＫ－ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒａｌｇｏｒｉｔｈｍ；ｄｙｎａｍｉｃｃｏｒｒｅｃｔｉｏｎ０引言在井下无线传感器网络中，可通过网络ＭＡＣ地址、接收信号强度信息（ＲＳＳＩ）和传输时间等进行人员定位［１］。在井下无线定位方法中，基于ＡＯＡ（到达角度）的方法［２］计算复杂度高，基于ＴＯＡ（到达时间）［３］、ＴＤＯＡ（到达时间差）［４］的方法对设备有严格的时间同步要求，而基于ＲＳＳＩ的方法获取定位信号强度方便，功耗低、成本低，是一种较好的井下定位方式［５－７］。基于ＲＳＳＩ的井下定位方法有三边定位、质心定位和指纹定位等。尚俊龙等［８］提出了井下加权三边定位算法，用加权三边测算出待测点位置，定位精度为３ｍ；赵彤等［９］提出了井下节点合作加权质心定位算法，利用改进的小区域加权质心定位算法对待测点进行定位，定位精度为１．５ｍ，但其实验场地为楼道，与井下环境差距较大；王永星等［１０］提出了基于信息传输模型的井下目标定位算法，利用最小二乘法建立指纹模型，定位精度为２．７３ｍ。董建平等［１１］提出了基于指纹模的井下定位算法，利用采样点信息形成指纹数据库，并利用Ｋ近邻算法进行在线匹配定位，但该方法存在以下问题指纹数据库未进行数据分类，定位时必须计算出全部参考点的欧氏距离，才能得到Ｋ个最近的参考点，计算量较大，实时性不好；在Ｋ近邻算法中采用Ｋ个点的平均值计算定位位置，未考虑距离较远和较近的参考点的权重值问题，从而影响到定位精度。针对上述问题，本文提出了基于聚类和Ｋ近邻算法的井下人员定位算法，用二分ｋ－ｍｅａｎｓ聚类算法［１２－１３］对井下巷道中采集的数据进行分类，建立离线指纹数据库；用动态修正器反馈井下巷道中的电磁变化量，实时修正权重值；再利用软硬件动态修正加权Ｋ近邻算法（ＳｏｆｔｗａｒｅａｎｄＨａｒｄｗａｒｅＤｙｎａｍｉｃＣｏｒｒｅｃｔｉｏｎＷＫＮＮ，ＳＡＨＤＣ－ＷＫＮＮ）进行在线实时位置估算。实验结果表明，该无线定位算法提高了定位系统的稳定性和实时性，定位精度达到１．６２ｍ。１煤矿井下人员定位系统结构及原理１．１系统结构煤矿井下人员定位系统由地面控制中心和井下的光纤交换机、ＡＰ（接入点）、动态修正器和井下作业人员携带的无线移动终端等组成，如图１所示。图１井下人员定位系统结构Ｆｉｇ．１Ｓｔｒｕｃｔｕｒｅｏｆｕｎｄｅｒｇｒｏｕｎｄｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇｓｙｓｔｅｍ１．２系统原理井下人员定位过程包括离线建库和实时定位２个阶段，如图２所示。图２井下人员定位系统原理Ｆｉｇ．２Ｐｒｉｎｃｉｐｌｅｏｆｕｎｄｅｒｇｒｏｕｎｄｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇｓｙｓｔｅｍ离线建库阶段包含采样和聚类生成离线指纹数据库。采样在井下巷道中选取采样点，测量该点的物理位置；利用自制无线移动终端多次采集该点的４４工矿自动化２０１９年第４５卷ＲＳＳＩ值，通过无线网络传输采样数据并存储到原始信息数据库。按照这种方法采集所有采样点的数据，由服务器对所有采样点ＲＳＳＩ求平均值，将ＲＳＳＩ值和采样点物理位置信息进行组合并存入原始信息数据库。在采样的同时，动态修正器也采集ＲＳＳＩ数据，通过无线网络传输并存储到动态修正数据库。聚类生成离线指纹数据库利用二分ｋ－ｍｅａｎｓ聚类算法对原始信息数据库中所有采样点的数据进行聚类分析，得到离线指纹数据库。实时定位阶段一方面，待测点通过无线移动终端采集实时ＲＳＳＩ值并传送到在线定位数据库；另一方面，动态修正器也实时采集ＲＳＳＩ值，传送到动态修正数据库。利用待测点和动态修正器的离线数据和实时数据，用ＳＡＨＤＣ－ＷＫＮＮ算法计算权重值，结合离线指纹数据库中待测点的物理位置信息估算其实时位置。２二分ｋ－ｍｅａｎｓ聚类算法２．１原始信息数据库的建立设ｍ个采样点的位置坐标为（ｘ１，ｙ１），（ｘ２，ｙ２），，（ｘｍ，ｙｍ），在每个采样点能够获得ｎ个ＡＰ节点的ＲＳＳＩ值，则第ｉ个采样点接收的ＲＳＳＩ值的组合可表示为Ｒｉ＝（Ｒｉ１，Ｒｉ２，，Ｒｉｎ）（１）式中Ｒｉｎ为第ｉ个采样点接收的第ｎ个ＡＰ节点的ＲＳＳＩ值，ｉ＝１，２，，ｍ。将采样点坐标及其接收的ＲＳＳＩ值组合起来，表示为Ｍｉ＝（Ｒｉ１，Ｒｉ２，，Ｒｉｎ，ｘｉ，ｙｉ）（２）将ｍ个采样点的数据都以式（２）所示的数据结构存储到原始信息数据库中，以备聚类运算时调用。２．２标准ｋ－ｍｅａｎｓ聚类算法原理设聚类数目为ｋ（ｋ≤ｍ），经过标准ｋ－ｍｅａｎｓ聚类算法生成的簇集合为Ｃ＝｛Ｃ１，Ｃ２，，Ｃｋ｝，每个簇的中心点Ｏｋ为Ｏｋ＝  Ｍｉ∈ＣｋＭｉ｜Ｃｋ｜（３）由式（３）可得标准ｋ－ｍｅａｎｓ聚类算法的目标函数为Ｓ（Ｃ）＝  ｋｊ＝１  Ｍｉ∈Ｃｋ ‖Ｍｉ－Ｏｊ‖ ２（４）标准ｋ－ｍｅａｎｓ聚类算法的目标是找到最小化误差平方和的聚类结果。具体来说，首先设置聚类个数ｋ，从数据集中选择ｋ个初始中心点；然后将每一个数据对象指派到距离最近的中心点所属的类中，从而构成ｋ个簇；计算每个簇中包含的数据对象的平均值，将其作为簇中心点的新值；重复进行指派和更新这２个步骤，对簇的分布进行迭代更新，直到簇中样本不再发生变化，整个聚类过程完成。２．３二分ｋ－ｍｅａｎｓ聚类算法流程二分ｋ－ｍｅａｎｓ聚类算法将所有点看作一个簇，将这个簇分裂为２个簇，之后迭代这个过程，每次都选取一个簇进行分裂，并将其分为２个新簇，最终得到ｋ个簇。用二分ｋ－ｍｅａｎｓ聚类算法生成井下人员定位离线指纹数据库时，输入为ｍ个采样点的组合数据Ｍｉ和聚类个数ｋ，输出为最终聚类结果。具体算法流程如下（１）初始化簇表，将ｍ个采样点组合成一个簇。（２）从簇表中取出一个簇，设聚类数目为２，使用标准ｋ－ｍｅａｎｓ聚类算法对选定的簇进行聚类。（３）从聚类结果中选取误差平方和最小的一组簇，将其添加到簇表中。（４）判断簇数量是否达到ｋ个，若达到则聚类结束，否则跳转到步骤（２）。与标准ｋ－ｍｅａｎｓ聚类算法相比，二分ｋ－ｍｅａｎｓ聚类算法的聚类结果更加稳定，但计算时间也更长。因为建立的是离线指纹数据库，在实时定位阶段不需要重复计算，离线建库阶段增加的计算时间可以不用考虑，所以，二分ｋ－ｍｅａｎｓ聚类算法更适用于建立无线定位离线指纹数据库［１４－１５］。３ＳＡＨＤＣ－ＷＫＮＮ算法ＳＡＨＤＣ－ＷＫＮＮ算法中的权重值ｗｉ由２个部分组成［１６－１７］一部分是与待测点欧氏距离最小的Ｋ（Ｋ≤Ｐ，Ｐ为巷道中安装的动态修正器的数量）个采样点的权重值ｗｓｉ；另一部分是与待测点欧氏距离最小的Ｋ个动态修正器的权重值ｗｈｉ。（１）设实时定位阶段待测点Ｄ接收到的ＲＳＳＩ信号的平均值集合为（ＲＤ１，ＲＤ２，，ＲＤｎ），则Ｄ点和第ｉ（ｉ＝１，２，，Ｋ）个采样点的欧氏距离为ｄｉ＝  ｎｊ＝１（ＲＤｊ－Ｒｉｊ槡）（５）与待测点欧氏距离最小的Ｋ个采样点的权重值ｗｓｉ为ｗｓｉ＝ｗ′ｓｉ  ｋｉ＝１ｗ ′ｓｉ（６）ｗ′ｓｉ＝１ｄ２ｉ（７）（２）与待测点欧氏距离最小的Ｋ个动态修正５４２０１９年第４期莫树培等基于聚类和Ｋ近邻算法的井下人员定位算法器接收的数据包含离线数据和实时数据。离线数据集合ＧＯＬ为ＧＯＬ＝Ｒ′１１Ｒ′１２Ｒ′１ｎＲ′２１Ｒ′２２Ｒ′２ｎ  Ｒ′Ｋ１Ｒ′Ｋ２Ｒ′ 熿燀燄燅Ｋｎ（８）式中Ｒ′ Ｋｎ为离线建库阶段第Ｋ个动态修正器接收的第ｎ个ＡＰ节点的ＲＳＳＩ值。对ＧＯＬ中的数据求平均值珚Ｒ′ｉ＝１ｎ ｎｊ＝１Ｒ ′ ｉｊ（９）实时数据集合ＧＲＴ为ＧＲＴ＝Ｒ″１１Ｒ″１２Ｒ″１ｎＲ″２１Ｒ″２２Ｒ″２ｎ  Ｒ″Ｋ１Ｒ″Ｋ２Ｒ″ 熿燀燄燅Ｋｎ（１０）式中Ｒ″Ｋｎ为实时定位阶段第Ｋ个动态修正器接收的第ｎ个ＡＰ节点的ＲＳＳＩ值。对ＧＲＴ中的数据求珚Ｒ′ｉ的标准差ｓｉｓｉ＝１ｎ ｎｊ＝１（Ｒ″ ｉｊ－珚Ｒ′ｉ）槡２（１１）与待测点欧氏距离最小的Ｋ个动态修正器的权重值ｗｈｉ为ｗｈｉ＝ｗ′ｈｉ  Ｋｊ＝１ｗ ′ｈｊ（１２）ｗ′ｈｉ＝ｓｉ珚Ｒ′ｉ（１３）由式（６）和式（１２）得到权重值ｗｉ为ｗｉ＝１２（ｗｓｉ＋ｗｈｉ）（１４）（３）结合离线指纹数据库中待测点的物理位置信息，求待测点的实时位置（Ｘ，Ｙ）（Ｘ，Ｙ）＝  Ｋｉ＝１ｗｉ（ｘｉ，ｙｉ）（１５）４实验分析４．１设备选用及测点布置考虑到煤矿井下各类机电设备电磁干扰严重、杂物堆放、人员设备移动等因素，选取贵州某煤矿井下回风巷、切眼和运输巷共计８９６ｍ的巷道进行实验，如图３所示。巷道中共安装了９个动态修正器，回风巷中３个，切眼中２个，运输巷中４个。根据巷道的作业环境和走向，将ＡＰ之间的距离控制在８０ｍ内，实现井下巷道无线网络全覆盖且无盲点。选用本质安全型无线ＡＰ，２．４ＧＨｚ频段，同时限制ＷｉＦｉ发射功率不超过１００ｍＷ。自制图３井下实验巷道Ｆｉｇ．３Ｕｎｄｅｒｇｒｏｕｎｄｅｘｐｅｒｉｍｅｎｔｒｏａｄｗａｙ动态修正器和无线移动终端主要由主控芯片ＳＴＣ８Ａ８Ｋ６４Ｓ４Ａ１２、ＷｉＦｉ模块ＥＳＰ８２６６ＥＸ和电源模块等组成，经过防爆测试，符合煤矿井下设备本质安全性要求［１８－２２］。根据巷道截面宽度，笔者设计并定制了一种由尼龙棒组成的田字格形状的可拆卸塑料架子（可拆解成日字形或口字形），长宽均为３ｍ，一次可放９个无线移动终端，能同时采集９个采样点，大大提高了采集效率。在实际采样过程中，采样点与采样点的间距基本控制在１．５～２ｍ，每个采样点采集１０次ＲＳＳＩ数据，共１７２４个采样点。同时，测试人员另外采集了１０２次测试数据，组成测试数据集。４．２定位结果将采样点数据全部存放到原始信息数据库，进行相应处理后，通过二分ｋ－ｍｅａｎｓ聚类算法建立离线指纹数据库。设置ｋ值为１９，用ＷＫＮＮ算法和ＳＡＨＤＣ－ＷＫＮＮ算法进行实时定位，定位成功率（误差在２ｍ以下）对比见表１。表１ＷＫＮＮ算法和ＳＡＨＤＣ－ＷＫＮＮ算法定位成功率对比Ｔａｂｌｅ１ＣｏｍｐａｒｉｓｏｎｏｆｐｏｓｉｔｉｏｎｉｎｇｓｕｃｃｅｓｓｒａｔｅｏｆＷＫＮＮａｌｇｏｒｉｔｈｍａｎｄＳＡＨＤＣ－ＷＫＮＮａｌｇｏｒｉｔｈｍｋ定位成功率／％ＷＫＮＮ算法ＳＡＨＤＣ－ＷＫＮＮ算法１３２．０４４５．２６２４２．１５６７．５８３６３．７６８１．０５４５０．０１７６．５６５４７．２４７２．９１６４０．２６６４．３８７３９．２６５８．３２８３６．５９５４．６４９３３．７１４８．５９从表１可看出，当ｋ值取３时能达到较好的定位效果，同时计算量适中，因此，ＳＡＨＤＣ－ＷＫＮＮ算法中ｋ值定为３。６４工矿自动化２０１９年第４５卷实时定位阶段，作业人员携带无线移动终端进入测试区域后，将实时接收到的ＲＳＳＩ值发送回服务器，系统将该ＲＳＳＩ值存放到在线定位数据库中，再调用权值修正程序、动态修正ＷＫＮＮ程序进行井下作业人员位置估算。设（ｘｓ，ｙｓ）为井下作业人员实际的物理位置坐标（实测坐标），（ｘｅ，ｙｅ）为定位系统估算出的井下作业人员物理位置坐标（估算坐标），用式（１６）、式（１７）计算系统定位标准误差Ｅ（ｉ）和平均误差珚Ｅ，结果见表２。Ｅ（ｉ）＝［ｘｓ－ｘｅ］２＋［ｙｓ－ｙｅ］槡２（１６）珚Ｅ＝  ｎｉ＝１Ｅ（ｉ）ｎ（１７）表２ＳＡＨＤＣ－ＷＫＮＮ算法定位结果Ｔａｂｌｅ２ｐｏｓｉｔｉｏｎｉｎｇｒｅｓｕｌｔｓｏｆＳＡＨＤＣ－ＷＫＮＮａｌｇｏｒｉｔｈｍｍ序号实测坐标（ｘｓ，ｙｓ）估算坐标（ｘｅ，ｙｅ）标准误差１（３４．００，４．００）（３４．６６，３．８２）０．６８２（１２５．００，３．５０）（１２２．１２，３．３１）２．８９３（２４８．００，２．００）（２４９．９２，２．２８）１．９４４（３２１．００，０．５０）（３１９．１１，０．５５）１．８９５（４５２．００，２．５０）（４５３．７３，２．７２）１．７４６（５７９．００，１．５０）（５８０．５４，１．６５）１．５５７（６３５．００，２．００）（６３４．２１，１．９８）０．７９８（７２４．００，２．５０）（７２３．０１，２．３７）１．００９（８０５．００，２．００）（８０１．７６，２．３４）３．２６１０（８７８．００，３．００）（８７８．４２，２．８１）０．４６从表２可看出，最小标准误差为０．４６ｍ，最大标准误差为３．２６ｍ，系统的平均误差为１．６２ｍ。４．３对比分析通过在线定位数据库中所有待测点的数据，采用ＮＮ（最近邻），ＫＮＮ（Ｋ近邻），ＷＫＮＮ（加权Ｋ近邻），ＳＡＨＤＣ－ＷＫＮＮ等４种近邻算法进行定位，用每种算法进行５００次独立定位并计算误差，得到定位误差对比，如图４所示。从图４可看出，ＳＡＨＤＣ－ＷＫＮＮ算法的误差比最低，定位精度最高。实时性也是井下人员定位系统的一个很重要的性能指标，将“ 未聚类分析＋ＫＮＮ” ［１１］、 “ 聚类分析＋ＷＫＮＮ”与本文提出的 “ 聚类分析＋ＳＡＨＤＣ－ＷＫＮＮ” 算法的精度和实时性进行对比，结果见表３。从表３可看出，与“ 未聚类分析＋ＫＮＮ” 相比，本文算法的精度更高，实时性更好；与“ 聚类分析＋ＷＫＮＮ” 相比，本文算法的运算时间略有增加，但定图４定位误差对比Ｆｉｇ．４Ｃｏｍｐａｒｉｓｏｎｏｆｐｏｓｉｔｉｏｎｉｎｇｅｒｒｏｒ表３算法定位精度与实时性比较Ｔａｂｌｅ３Ｃｏｍｐａｒｉｓｏｎｏｆｐｏｓｉｔｉｏｎｉｎｇａｃｃｕｒａｃｙａｎｄｒｅａｌ－ｔｉｍｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｓ算法平均误差／ｍ运算时间／ｓ未聚类分析＋ＫＮＮ３．１５１．１６３聚类分析＋ＷＫＮＮ２．５８０．４０９聚类分析＋ＳＡＨＤＣ－ＷＫＮＮ１．６２０．４９５位精度提高了３７．２１％。因此，本文提出的“ 聚类分析＋ＳＡＨＤＣ－ＷＫＮＮ” 算法的定位效果最好，更能满足煤矿井下人员定位要求。５结论（１）针对煤矿井下特定的地理和通信环境，提出了基于聚类和Ｋ近邻算法的井下人员定位算法。通过二分ｋ－ｍｅａｎｓ聚类算法对离线数据进行分类，提高了定位算法实时性；通过在巷道中增加动态修正器来实时反馈井下电磁环境情况，动态修正权重值，提高了定位算法精度。（２）实验分析结果表明，所提定位算法的最小标准误差为０．４６ｍ，最大标准误差为３．２６ｍ，平均误差为１．６２ｍ。对比分析结果表明，与未进行聚类分析的算法相比，本文算法的精度更高，实时性更好；与未动态修正权重值的算法相比，本文算法的运算时间略有增加，但定位精度提高了３７．２１％。（３）在接下来的工作中，应继续优化无线定位算法，提高定位精度，在定位性能不变的前提下减少采样点数量。参考文献（Ｒｅｆｅｒｅｎｃｅｓ）［１］孙继平．煤矿信息化自动化新技术与发展［Ｊ］．煤炭科学技术，２０１６，４４（１）１９－２３．ＳＵＮＪｉｐｉｎｇ．Ｎｅｗｔｅｃｈｎｏｌｏｇｙａｎｄｄｅｖｅｌｏｐｍｅｎｔｏｆｍｉｎｅｉｎｆｏｒｍａｔｉｚａｔｉｏｎａｎｄａｕｔｏｍａｔｉｏｎ［Ｊ］．ＣｏａｌＳｃｉｅｎｃｅ７４２０１９年第４期莫树培等基于聚类和Ｋ近邻算法的井下人员定位算法ａｎｄＴｅｃｈｎｏｌｏｇｙ，２０１６，４４（１）１９－２３．［２］闫雷兵，陆音，张业荣．基于改进最小二乘算法的ＴＤＯＡ／ＡＯＡ定位方法［Ｊ］．电波科学学报，２０１６，３１（２）３９４－４００．ＹＡＮＬｅｉｂｉｎｇ，ＬＵＹｉｎ，ＺＨＡＮＧＹｅｒｏｎｇ．Ｉｍｐｒｏｖｅｄｌｅａｓｔ－ｓｑｕａｒｅｓａｌｇｏｒｉｔｈｍｆｏｒＴＤＯＡ／ＡＯＡ－ｂａｓｅｄｌｏｃａｌｉｚａｔｉｏｎ［Ｊ］．ＣｈｉｎｅｓｅＪｏｕｒｎａｌｏｆＲａｄｉｏＳｃｉｅｎｃｅ，２０１６，３１（２）３９４－４００．［３］孙继平，蒋恩松．基于ＷｉＦｉ信号二次扩频的矿井ＴＯＡ测距方法［Ｊ］．工矿自动化，２０１７，４３（１０）５３－５８．ＳＵＮＪｉｐｉｎｇ，ＪＩＡＮＧＥｎｓｏｎｇ．ＭｉｎｅＴＯＡｒａｎｇｉｎｇｍｅｔｈｏｄｂａｓｅｄｏｎｒｅ－ｓｐｒｅａｄｓｐｅｃｔｒｕｍｔｏＷｉＦｉｓｉｇｎａｌ［Ｊ］．ＩｎｄｕｓｔｒｙａｎｄＭｉｎｅＡｕｔｏｍａｔｉｏｎ，２０１７，４３（１０）５３－５８．［４］孙哲星，孙继平．异步测时矿井人员精确定位方法［Ｊ］．煤炭学报，２０１８，４３（５）１４６４－１４７０．ＳＵＮＺｈｅｘｉｎｇ，ＳＵＮＪｉｐｉｎｇ．Ｕｎｄｅｒｇｒｏｕｎｄｃｏａｌｍｉｎｅａｃｃｕｒａｔｅｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇｍｅｔｈｏｄｂａｓｅｄｏｎａｓｙｎｃｈｒｏｎｏｕｓｔｉｍｅ－ｍｅａｓｕｒｉｎｇ［Ｊ］．ＪｏｕｒｎａｌｏｆＣｈｉｎａＣｏａｌＳｏｃｉｅｔｙ，２０１８，４３（５）１４６４－１４７０．［５］ＦＡＮＧＸｕｍｉｎｇ，ＪＩＡＮＧＺｏｎｇｈｕａ，ＮＡＮＬｅｉ，ｅｔａｌ．ＯｐｔｉｍａｌｗｅｉｇｈｔｅｄＫ－ｎｅａｒｅｓｔｎｅｉｇｈｂｏｒａｌｇｏｒｉｔｈｍｆｏｒｗｉｒｅｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｆｉｎｇｅｒｐｒｉｎｔｌｏｃａｔｉｏｎｉｎｎｏｉｓｙｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］．ＩＥＴＣｏｍｍｕｎｉｃａｔｉｏｎｓ，２０１８，１２（１０）１１７１－１１７７．［６］孙哲星．基于时间测距的矿井人员定位方法研究［Ｊ］．工矿自动化，２０１８，４４（４）３０－３３．ＳＵＮＺｈｅｘｉｎｇ．Ｒｅｓｅａｒｃｈｏｎｍｉｎｅｐｅｒｓｏｎｎｅｌｐｏｓｉｔｉｏｎｉｎｇｍｅｔｈｏｄｂａｓ