基于FCM聚类及位置区切换的室内地磁定位研究
摘 要： 针对目前室内地磁定位技术中存在的地磁指纹库太大及地磁指纹不惟一所造成的运算量大、定位误差大的问题，提出一种基于模糊C?均值聚类与位置区切换相结合的室內地磁定位方法。首先对待定位点的位置区进行判别，然后对该点地磁矢量所属的聚类进行判别，最后在其所属的位置区及聚类对应的匹配范围内进行匹配定位。经过以上两步判别，可以缩小地磁指纹的匹配范围，减小匹配运算量，同时降低了地磁矢量接近但地理位置上相距较远时加大定位误差的风险。经实验及仿真验证，改进的方法相比WKNN（KNN）算法减少了约41%的运算耗时（1 000个地磁指纹的情况下），定位精度提高了约76%。
关键词： 室内地磁定位； 地磁定位技术； 地磁指纹库； 模糊C?均值聚类； 位置区切换； 匹配定位
中图分类号： TN953+.7?34； TP391 文献标识码： A 文章编号： 1004?373X（2018）14?0096?05
Research on indoor geomagnetic positioning based on FCM
clustering and location area switching
SONG Yu， YU Wenju， CHENG Chao
（School of Computer Science and Engineering， Changchun University of Technology， Jilin 130012， China）
Abstract： In allusion to the problems of big amount of computations and big positioning errors caused by much hugeness of the geomagnetic fingerprint database and non?uniqueness of the geomagnetic fingerprints existing in the current indoor geomagnetic positioning technology， an indoor geomagnetic positioning method based on the combination of fuzzy C?means clustering and location area switching is proposed. The location area of the to?be positioned point is discriminated， the cluster that the geomagnetic vector of the point belongs to is discriminated， and the matching positioning is performed in the location area of the point and within the matching range corresponding to the cluster. The above two discriminations can reduce the matching range of geomagnetic fingerprints， the amount of matching computations， and the risk of increasing positioning errors when the geomagnetic vectors are approximate but geographically far away. The results of the experiment and simulation verification show that in comparison with the WKNN（KNN） algorithm， the improved method can reduce the computation time consumption by about 41% in the case of 1000 geomagnetic fingerprints and improve the positioning accuracy by about 76%.
Keywords： indoor geomagnetic positioning； geomagnetic positioning technology； geomagnetic fingerprint database； fuzzy C?means clustering； location area switching； matching positioning
随着科学技术的进步，基于位置服务（LBS）的增值业务对室内定位的需求越来越多。但是目前的全球卫星导航系统比如GPS，BDS等，由于卫星信号受到建筑物或其他障碍物的阻挡导致在一些密闭的室内无法定位。因此自2000年以来，高精度、低成本的室内定位技术一直是相关学者研究的热点[1]。目前室内定位技术有RFID，UWB，蓝牙，ZigBee等[2?5]，但这些定位技术需要铺设专门的基础设施或者需要高成本的定位终端。
地磁场是地球的固有磁场。对于室内环境，由于地磁场受到钢筋混凝土建筑、铺设的电缆管道、大型金属或电磁制品等的影响而发生扭曲[1]，造成室内不同位置的地磁场矢量差异化加大，因此可将其作为一种位置指纹用于室内定位。
相比其他室内定位技术，基于地磁的室内定位技术不需要专设任何基础设施，只依靠室内被建筑物扭曲的地磁场即可。同时，地磁定位可以用已经普及的智能手机作为定位终端。
室内地磁定位技术目前还不成熟，有很多问题有待解决。其中，地磁指纹库太大造成的运算量大以及地磁指纹不唯一[6?7]造成的定位误差大这两个问题比较典型。文献[8]运用惯导辅助地磁的定位方法缩小地磁匹配范围来解决以上问题，取得了较高的精度，但其惯导初始点的更新依赖前一点定位的准确度，而本文从新的角度提出的对地磁指纹分类与位置区切换相结合的方法中，位置区状态的更新只依赖前一个定位点的位置区状态是否正确，并不直接依赖前一点定位的准确度，因而鲁棒性有所提高。
1 地磁定位系统组成
地磁定位流程分为离线地磁指纹库的建立和在线定位两个阶段。本文定位方法的系统框图如图1所示。
2 室内地磁指纹库的建立
本文选择地磁场在参考坐标系上的三个轴分量组成匹配矢量。下面结合具体的实验环境来说明地磁指纹库的建立过程。
2.1 实验环境设定
实验环境选在本校某楼，包括三楼两个实验室房间、走廊、楼梯及四楼一条走廊。采样区域面积大约为160 m2。本文按0.5 m×0.5 m的网格（1个点因阻挡除外）共设定238个参考点。实验环境和参考点分布如图2所示。
本文使用的地磁采集设备是小米5手机，其配备了AKM公司生产的型号为AK09915的三轴磁力计，该磁力计测量精度为0.149 536 13 μT。同时小米5手机还配备了LSM6DS3加速度计、LSM6DS3陀螺仪及QTI方向传感器等，为采集的地磁矢量进行坐标系的转化提供了条件。
2.2 地磁指纹采集方法
具体的地磁指纹采集步骤如下：
1） 根据室内结构和所需定位精度进行参考点的确定，并给定所有参考点的坐标。
2） 在每个参考点正上方固定高度用采集软件对地磁矢量、手机姿态等参数进行多方位重复采集。
3） 通过手机姿态数据将采集的地磁矢量从载体坐标系转化到导航坐标系[9]以便所有地磁矢量能够直接进行匹配。转化后将每个参考点的地磁矢量分别进行平均，并与位置坐标结合后存入数据库。通过坐标系转换后的x轴数值都接近0，可忽略不计。
4） 将采集好的所有地磁矢量通过FCM算法进行聚类。
5） 参考点聚类之后，进行位置区、缓冲区、切换区的划分。
3 地磁定位算法
3.1 FCM聚类算法
模糊C?均值聚类（Fuzzy C?means，FCM）是基于目标函数的软聚类算法，每个元素属于每个类的程度都用隶属度的大小表示[10]。隶属度对地磁匹配范围的调整有参考意义。
FCM算法是基于目标函数的最小值[11]，如下：
[Jm=i=1Dj=1Nμmijxi-cj2] （1）
式中：D表示需要聚类的数据个数；N表示所聚的类数；[m]是模糊划分矩阵指数，用以控制模糊重叠度，[m]>1，一般取[m]=2；[xi]是第i个参考点的地磁矢量；[cj]是第j个类的聚类中心； [μij]是[xi]属于第j类的隶属度，且满足式（2）：
[j=1Nμij=1] （2）
FCM算法步骤如下[11]：
1） 随机初始化聚类的隶属度值，并给出聚类的类数N、停止阈值ε、最大迭代次数P；
2） 依据式（3）计算每个聚类的聚类中心：
[cj=i=1Dμmijxii=1Dμmij] （3）
3） 依据式（4）更新[μij]：
[μij=1k=1Nxi-cjxi-ck2m-1] （4）
4） 计算目标函数式（1）的值[Jm]；
5） 重复步骤2）～步骤4），直到[Jm]的值小于给定的停止阈值ε或者大于给定的最大迭代次数P为止。
为了防止因测量误差导致待定位点分类错误，本文设定当待测点的最大隶属度低于0.55时，在最终确定的匹配范围内将隶属度较大的前两类指纹点作为匹配点。
3.2 位置区切换
对参考点地磁矢量进行聚类后发现，同一类的地磁矢量在地理位置上往往是不连续的。因此，当待定位点在同一类但位置上不连续的多个分区进行地磁匹配时，如果多个分区中都存在一些点和待定位点地磁矢量非常接近，就可能导致很大的定位误差。该问题是由地磁指纹不惟一引起的，引入位置区切换就是为了应对这一问题。
3.2.1 位置区切换原理
Michael Angermann等研究了现代的工字钢梁和钢筋混凝土建筑物对地磁场强度的影响[7，12]，结果发现工字钢梁的砖墙附近磁场变化率为7.15 μT/m，钢筋混凝土建筑的走廊、大厅分别为2.17 μT/m和1.15 μT/m。从该结果可以发现砖墙附近、走廊的地磁变化率相对较大。本文实验环境下的参考点聚类结果如图3所示。通过图3发现，室内的一些特殊位置例如门口、墙边、楼梯等地方是不同聚类的交接地带，也是分属不同聚类的零散点聚集区，说明了这些地带地磁变化率相对较大，形成了天然的“地磁分界线”。这些地带基本都靠近墙体，侧面印证了Michael Angermann等人的结论。本文实验环境下，位置区、切换区和缓冲区的划分见图3。图3中①代表BA缓冲Ⅱ區，②和③范围代表BA缓冲Ⅰ区；②代表BC缓冲Ⅱ区，①和④范围代表BC缓冲Ⅰ区。
本文利用这些 “地磁分界线”将整个定位范围划分成包含若干个聚类且每个类在地理位置上都连续的多个位置区，然后使定位终端在所处的位置区内进行匹配定位，这样就降低与待定位点距离较远但地磁矢量非常接近的点导致定位误差加大的风险。
本文将定位终端在图4中所处的区域称为位置区状态。两个位置区的切换是通过二者之间的切换区进行过渡。这些地磁变化率较大的地带地磁特征明显，当范围有限时进行匹配定位的准确率相比地磁变化率较小的空旷区域高一些。在定位过程中，本文依据连续多个定位点所落入的区域来判定目前终端的位置区状态，因此定位准确率高的地带容易准确判定位置区状态，可以设为切换区。切换区之外的区域为位置区。
3.2.2 位置区的划分及其切换过程
位置区划分的原则如下：
1） 对所有参考点聚类之后，进行位置区划分时大体遵循一个位置区内每个聚类都在地理位置上连续的准则，简称聚类不分裂原则。但实验中，总有个别聚类点在位置分布上夹杂在别的聚类中间。根据实验，当这些零散点距离该类主体点最近距离不超过3 m时，这些零散点对定位结果影响不大，所以一般不考虑聚类不分裂原则，否则就根据实际情况重新划分位置区。
2） 位置区之间设置切换区，并且每个位置区与切换区接壤地带设置两个相连的缓冲区。其目的是进一步缩小匹配范围。切换区一般设置在前述的地磁变化率较大的地方。切换区和缓冲区的设定依据具体环境和相应地带的定位误差分布，一般最窄处大于2 m，该值可依实际情况调整。
位置区切换的过程即地磁匹配范围更新的过程。当定位终端处于图4中除A0区和B0区外的任何区域，其地磁匹配范围包括定位终端所处区域和与该区域接壤的其他区域。当定位终端处于A0区，其地磁匹配范围是整个A位置区，处于B0区时同理。
本文将在同一个位置区内但不同类的相邻边缘点互相作为对方的补充点，以减小类别边缘值的定位误差。为避免終端因定位误差大而定位到错误区域，造成系统错误更改地磁匹配范围，算法规定终端的位置区状态更新时，在移动过程中（速度建议在0.5～1 m/s）必须有连续L个点或L+1个点中有L个点都定位在新的区域，系统才会更新终端的位置区状态及相应的地磁匹配范围。
3.3 WKNN（KNN）地磁定位算法
K近邻算法（KNN）和加权K近邻算法（WKNN）[10]都是最基本的匹配算法。
本文的定位算法将FCM聚类、位置区切换、WKNN进行了融合，简称该融合算法为FLSWKNN。同时将FCM聚类、位置区切换、KNN融合的算法简称为FLSKNN。算法步骤如下：
1） 首先对定位终端的磁力计进行校准，然后给定初始点位置及其位置区状态。
2） 判断经预处理后的待定位点地磁矢量在该位置区状态下所属的聚类，然后在该聚类对应的匹配范围中进行匹配定位并输出结果，同时按位置区状态更新的规则保持或更新下一个定位点的初始位置区状态。
4 定位实验及仿真
实验环境如第3.1节所述，在指纹库建立完毕后，实验人员任选多条不同实验路线（部分重复），并保持定位终端在采集基准值时的高度（误差上下5 cm）行走进行定位效果的验证，待定位点共采样816个。所测数据在Matlab上以本文改进的算法进行处理。算法中每秒定位2次，行走速度在0.5～1 m/s之间，L取4。按FLSWKNN（K=3）算法的其中一条实验路线定位结果如图5所示。
WKNN（KNN），FLSWKNN（FLSKNN）定位算法的实验对比结果如表1、图6所示。
表1中单点匹配耗时不包括测量耗时。由于WKNN（KNN）算法匹配耗时跟地磁指纹库数据量相关性很强，为了上述几种算法的匹配耗时对比明显，将匹配数据库扩展到1 000条（定位精度指标仍按原有实测数据库）。通过表1可知，所改进的算法FLSWKNN（FLSKNN）比WKNN（KNN）算法耗时减少近41%，说明匹配运算量大大减少。这种优势将随着地磁指纹库的增大而更加明显。
由表1和图6可看出，所改进的融合算法FLSWKNN（FLSKNN）比WKNN（KNN）算法在定位精度上有大幅度提升。FLSWKNN（K=3）算法平均误差为1.46 m，效果最佳。
本次实验中，FLSKNN（K=3）算法在BC缓冲Ⅱ区定位时发生了一次位置区状态判别错误，致使定位失败，经分析是由于当时磁力计测量误差较大导致，这说明了本方法鲁棒性需要改进加强。
5 结 语
本文将FCM聚类、WKNN算法与位置区切换进行了融合，使得匹配耗时大幅下降且平均定位误差达到了1.46 m，能够满足一般的室内定位需求。但位置区切换对环境有一定依赖性，本文的改进算法适用于地磁特征相对明显的室内区域。后续的研究重点是将其他定位方法与位置区切换相结合，以降低位置区切换对环境的依赖性，达到耗时少且误差小的定位目的。
参考文献
[1] 谢宏伟.基于智能手机平台的地磁室内定位系统[D].南京：南京大学，2015.
XIE Hongwei. Geomagnetic indoor localization system based on the smart phone platform [D]. Nanjing： Nanjing University， 2015.
[2] 孙晓玲，李伟勤.基于RFID的二维室内定位算法的实现[J].现代电子技术，2010，33（24）：90?92.
SUN Xiaoling， LI Weiqin. Implementation of two?dimensional indoor location algorithm based on RFID [J]. Modern electronics technique， 2010， 33（24）： 90?92.
[3] 张桀，沈重.联合TDOA改进算法和卡尔曼滤波的UWB室内定位研究[J].现代电子技术，2016，39（13）：1?5.
ZHANG Jie， SHEN Chong. Research on UWB indoor positioning in combination with TDOA improved algorithm and Kalman filtering [J]. Modern electronics technique， 2016， 39（13）： 1?5.
[4] 王益健.蓝牙室内定位关键技术的研究与实现[D].南京：东南大学，2015.
WANG Yijian. Research and implementation on key technologies of Bluetooth indoor positioning [D]. Nanjing： Southeast University， 2015.
[5] 李尧，汪明，于晓谕.基于ZigBee室内定位算法[J].计算机系统应用，2016，25（6）：180?184.
LI Yao， WANG Ming， YU Xiaoyu. Indoor location algorithm based on ZigBee [J]. Computer systems & applications， 2016， 25（6）： 180?184.
[6] CHUNG J， DONAHOE M， SCHMANDT C， et al. Indoor location sensing using geo?magnetism [C]// Proceedings of International Conference on Mobile Systems， Applications， and Services. New York： ACM， 2011： 141?154.
[7] ANGERMANN M， FRASSL M， DONIEC M， et al. Characterization of the indoor magnetic field for applications in localization and mapping [C]// Proceedings of International Conference on Indoor Positioning and Indoor Navigation. Sydney： IEEE， 2013： 1?9.
[8] 宋镖，程磊，周明达，等.基于惯导辅助地磁的手机室内定位系统设计[J].传感技术学报，2015（8）：1249?1254.
SONG Biao， CHENG Lei， ZHOU Mingda， et al. The design of cellphone indoor positioning system based magnetic assisted inertial navigation technology [J]. Chinese journal of sensors and actuators， 2015（8）： 1249?1254.
[9] 格罗夫斯.GNSS与惯性及多传感器组合导航系统原理[M].李涛，练军想，曹聚亮，等译.北京：国防工业出版社，2011.
Groves P D. Principles of GNSS， inertial， and multisensor integrated navigation systems [M]. LI Tao， LIAN Junxiang， CAO Juliang， et al， translation. Beijing： National Defense Industry Press， 2011.
[10] 毛红文.基于模糊聚类的位置指纹室内定位优化技术研究[D].昆明：云南大学，2014.
MAO Hongwen. Optimization technology research on location fingerprint indoor positioning based on fuzzy clustering [D]. Kunming： Yunnan University， 2014.
[11] JANG J， GULLEY N. Fuzzy logic toolbox user′s guide [M]. Natick： Mathworks， Inc.， 2015.
[12] GHODSI M， LOGHMANIAN S M R. Effect of forging on ferromagnetic properties of low-carbon steel [C]// Proceedings of 4th International Conference on Modeling， Simulation and Applied Optimization. Kuala Lumpur： IEEE， 2011： 1?3.
