基于MPGA-SVM的地磁室内定位算法研究

韩雨辰，吕伟才*，仲 臣，肖星星 ，刘清华

(1.安徽理工大学 空间信息与测绘工程学院,安徽 淮南 232001；2.安徽理工大学 矿山采动灾害空天地协同监测与预警安徽普通高校重点实验室,安徽 淮南 232001；3.安徽理工大学 矿区环境与灾害协同监测煤炭行业工程研究中心,安徽 淮南 232001)

0 引言

日常生活中，人们在户外可以方便地利用各种随身设备通过GNSS信号实时定位，其精度可达到亚米级。随着无线终端设备的不断发展与创新，对高精度的室内定位服务需求愈加迫切。由于GNSS信号穿透墙体时其信号强度大幅衰减，无法再提供定位服务，室内定位往往需要室内无线信号介质完成[1]。如今基于WiFi、蓝牙、超宽带、射频识别、可见光和FM的室内定位技术被广泛研究，取得了较为满意的定位结果[2-7]。但这些技术需要一定的室内物理基础设施来完成，造价昂贵且需要不断维护更新。因此，地磁室内定位技术逐渐成为研究热点。

地磁场具有空间差异性，在某个区域内任意一处的地磁矢量值都不相同，这为地磁室内定位提供了基础；其次地磁定位具有全天候连续性、抗环境干扰能力强等特点。但地磁场的分辨率较低，在定位时易出现“回跳”现象[8]。因此，高精度地磁定位的关键在于匹配算法。针对这个问题，学者们进行了深入研究。文献[9]提出了一种基于布谷鸟非线性优化的在线磁校准算法，通过磁观测余差动态对非线性目标代价函数进行加权，有效解决了磁传感器中常存在的软磁误差和硬磁误差；文献[10]提出了改进动态时间规整(Dynamic Time Warping，DTW)的地磁匹配算法，对地磁数据序列与采集数据序列的距离与相似路径重新规整，并缩短地磁序列长度，在保证定位精度的同时提升了定位时效性；文献[11]中将RSSI信号与地磁分量进行融合，并将其矢量化，进行更深层次的提取，弥补了地磁信号存在的低分辨率缺陷。文献[12]受hausdorff距离测量点设置匹配理论启发，提出了基于初始定位误差约束的改进粒子滤波算法，避免迭代过程中粒子存在的不利影响，提升了定位的稳定性。

亦有学者通过融合机器学习算法对地磁室内定位进行研究，并取得了一定成果[13-15]。其中K最近邻算法存在误匹配的缺陷，且随着指纹数量的增加缺陷愈加明显，几乎无法应用大型场景的地磁定位。神经网络易因样本点数量不足而出现过拟合的现象，且对样本的采集要求较高。相比之下支持向量机(Support Vector Machine，SVM)存在更好的普适性，对空间复杂性的简化效果更好，在室内定位中的表现优于另外2种算法[16]。SVM的性能受其惩罚因子及核函数选取的影响较大，若核函数选取不当，定位精度会大幅下降。

为减少上述不利影响，提高定位精度，本文提出一种基于多种群遗传算法(Multi-Population Genetic Algorithm，MPGA)优化SVM的地磁室内定位算法。该算法选择高斯径向基核函数作为SVM的核函数，提高了定位匹配过程中的稳定性及准确性，并通过实验测试该算法的定位效果。

1 原理与方法

针对上述提出的KNN算法、神经网络在室内定位中存在的不足，将SVM模型应用到地磁匹配算法中，并针对核函数及相关参数的选取问题，提出基于粒子群优化SVM的算法进行地磁匹配。

1.1 SVM原理

SVM属于一种二分类模型，可将样本数据集映射为空间内存在的大量“点”，再利用某条“线”将这些点存在的不同类别最大程度区分开。对于给定的空间样本点{mi,ni},i=1,2,…,N,mi∈Rd,ni∈{+1,-1}，这条“线”即为划分超平面，可表示为：

ωT·m+b=0，

(1)

式中，ω=(ω1,ω2,ω3,…,ωd)作为超平面的方向；b为划分超平面至空间原点的位移量。

若样本集中所有样本点均被该超平面正确分类，则存在：

(2)

SVM的分类模型如图1所示。

图1 分类模型Fig.1 Classification model

图1中，h1,h2,h3均为分类函数，落在函数h1,h3上的样本“×”“○”即为支持向量；其分类间隔为：

(3)

此时需满足受约束的参数ω，b，同时找到最大分类间隔，以便完成最佳分类。即：

(4)

式(4)即为SVM基本型，同时依据划分超平面的函数模型，结合凸二次规划的优化解法构造函数求解[17]，则该函数为：

(5)

式中，μi(i=1,2,…,N)为拉格朗日乘子，则SVM的决策函数为：

(6)

式中，h(mi,mj)为核函数，通常可选择的核函数如表1所示。

表1 SVM核函数Tab.1 SVM kernel functions

通常核函数的选取标准不唯一，根据实际问题来确定。二维高斯函数具有旋转对称性，且可分离性较好，因此本文选择高斯径向基核函数，代入式(6)得：

(7)

式中，C为惩罚因子；η为核函数的参数。

1.2 SGA算法

标准遗传算法(Standard Genetic Algorithm，SGA)受达尔文进化论以及孟德尔遗传学说的启发，模拟生物在大自然中的繁衍进化机制，对特定目标进行迭代式概率寻优。其算法流程如下：

① 设定参数范围，均匀生成一个初始种群并确定该种群的大小。

② 确定适应度函数，将该函数作为衡量种群中个体是否优秀的标准。本文选取定位精度G(x)为适应度函数：

(8)

式中，N为数据库样本点数；x′i，y′i分别为第i(i∈[1,N])个样本预测定位点坐标；xi，yi分别为其实际坐标。

③ 选择遗传算子，该算法中适应度越大的个体被选择遗传到下一代的概率越大。假设初始种群个体数量为K，个体i的适应度为hi，则该遗传算子被选择的概率为：

(9)

④ 交叉和变异，新个体通常由交叉、变异产生；若其参数选取不当，遗传算法的全局搜索能力会大幅下降。参数公式为：

(10)

式中，pa，pb分别为交叉概率、变异概率；d为0～1之间的任意常数。

⑤ 设定迭代结束准则，达到所设定的迭代次数时，算法终止，输出结果。

1.3 MPGA算法

上述SGA算法具有较好的收敛性与随机性。但收敛速度较慢，且样本数量大时稳定性较差[18]。因此本文基于SGA的基础提出了MPGA，该算法的改进之处是将单个初始种群展开为含有不同交叉、变异参数的多个种群，每个种群同时进化；并在种群之间建立移民机制,即每次迭代后将单个种群中适应度最小的个体剔除，换取其他种群中适应度最大的个体；将所有种群中每代适应度最大的个体聚合建立精华种群，该种群不存在选择、交叉和变异。并将该精华种群不断地延续获取更多的优秀个体，以此达到最佳寻优。其算法流程图如图2所示。

图2 MPGA算法流程Fig.2 Flowchart of MPGA algorithm

1.4 MPGA-SVM模型建立

将上文所述SVM模型中的两参数C，η作为MPGA所寻最优解，建立MPGA-SVM模型，其算法流程如下：

① 采集实验所需的地磁样本集，并将其划分为SVM学习与测试2种不同类别。

② 确定粒子群的大小，设置参数C，η的取值范围，并将每个粒子群初始化。粒子群再展开为M个粒子群，将所有粒子群以及每个种群中的所有粒子进行编码，一般选择二进制编码，并利用式(10)确定交叉、变异概率。

③ 解码并确定适应度函数。本文选取式(8)作为适应度函数。

④ 将M个粒子群进行选择、交叉和变异生成新的M个粒子群，并确定其中每个粒子的自适应度。

⑤ 进行移民机制，即每次迭代后将单个种群中适应度最小的个体剔除，换取其他种群中适应度最大的个体。将所有种群中每代适应度最大的个体聚合建立精华种群。

⑥ 算法迭代，重复步骤③～步骤⑤，当迭代100次或者达到最优迭代次数时，算法终止，输出结果。

⑦ 利用该输出结果对应的SVM参数C，η构建地磁室内定位模型。其算法流程图如图3所示。

图3 MPGA-SVM算法流程Fig.3 Flowchart of MPGA-SVM algorithm

2 基于MPGA-SVM的地磁室内定位

地磁定位通常有2种方式：单点定位或序列匹配，具体情况由特征值的选择而定[19]。本文把X,Y,Z地磁三轴分量作为特征值，采用单点定位方式。

2.1 定位模型

在定位区域内随机采集多个样本点的磁场强度，并将第i个样本点的位置信息(xi,yi)记录，数据格式为(xi,yi,Mi1,Mi2,Mi3)，设该点与周围3个样本点的相对磁场强度为(Mi1,Mi2,Mi3)。将这些点作为参考点，利用三角函数模型建立坐标值与磁场强度之间的映射关系；由于室内环境存在不利影响，输入的磁场强度与输出坐标值具有随机且复杂的非线性关系，可利用统计学的思想融合SVM，构建地磁室内定位回归模型，如图4所示。

图4 地磁定位回归模型图Fig.4 Model diagram of geomagnetic positioning regression

2.2 定位原理

单点定位过程分为离线阶段和在线阶段[20]。离线阶段在定位区域获取各个位置的地磁特征值，与采集点坐标相对应，经高斯滤波去噪后建立地磁指纹库；在线阶段将实时采集的地磁特征值与地磁指纹库匹配，利用上文建立的定位模型及匹配算法输出用户的实时位置，其定位框架如图5所示。

图5 地磁定位框架图Fig.5 Frame diagram of geomagnetic positioning

2.3 数据预处理

由于室内环境多变，采集地磁指纹过程中存在着不可避免的误差，使样本数据波动较大。本文采用高斯滤波去除样本集中小概率的噪声干扰，进一步提升定位可靠性。每次数据采集均可视为独立且地磁分量服从正态分布，选取概率更高的地磁分量值利用几何平均法求值，并将其作为滤波输出。

设存在正态分布模型P(h)，对于第n号点的地磁分量值Mn的测量结果x的均值为：

(11)

方差以及概率密度函数为：

(12)

(13)

式中，x应满足μ-σ≤x≤μ+σ，将其对应的地磁分量值加权平均即为最终输出结果：

(14)

地磁分量滤波结果如图6所示，结果表明高斯滤波能较好地剔除样本集中的噪声，保证了数据的准确性。

图6 高斯滤波Fig.6 Gaussian filtering

3 应用实例

3.1 实验场景

本文选择安徽理工大学空间信息与测绘工程学院一楼作为实验场所，场地大小为20 m×42 m，如图7所示。将整个试验场地均匀划分为1 m×1 m的网格，在每个网格节点进行地磁指纹采集，采集设备为VIVO S9，采集频率设置为50 Hz，采集过程中设备的姿态保持不变。数据采集完成后利用高斯滤波预处理，并对实验结果进一步对比分析。

图7 实验场景Fig.7 Experimental scenario

3.2 结果分析

为体现MPGA-SVM算法的性能，本文选用粒子群(Particle Swarm Optimization，PSO)优化SVM算法与其做对比并进行结果分析。粒子群算法是模拟鸟类群体之间信息的相互共享交换衍生的算法，具有较好的寻优性。实验整体分为静态定位实验以及动态定位实验两部分。

3.2.1 静态定位

将预处理后整体数据集的20%作为测试集，剩余数据作为训练集。采用五折交叉验证法将样本输入至已建立的MPGA-SVM地磁室内定位模型中，MPGA-SVM与PSO-SVM的定位结果如图8所示,累计误差分布图如图9所示。

图8 定位结果统计Fig.8 Statistics of positioning results

图9 累计误差分布图Fig.9 Cumulative error distribution

分析图8和图9可得，MPGA-SVM定位误差集中在2 m以内，最大定位误差不超过6 m；PSO-SVM有一半以上的定位误差在2 m以上，最大定位误差超过7 m，且1 m以内的精确定位误差占比仍小于MPGA-SVM算法。由分析结果可知，MPGA优化的SVM在地磁室内定位方面具有更好的性能。PSO-SVM与MPGA-SVM的动态定位精度对比如表2所示。

表2 静态定位精度对比Tab.2 Comparison of static positioning accuracy 单位：m

由表2可知，MPGA-SVM算法的最小定位误差、最大定位误差、平均定位误差均小于PSO-SVM；MPGA-SVM平均定位误差为1.39 m，较之PSO-SVM定位精度提升1.1 m；MPGA-SVM定位标准差明显小于PSO-SVM的定位标准差，具有更好的定位稳定性。

3.2.2 动态定位

首先确定行人的初始位置坐标，按照规划的路线行走并进行地磁数据采集，采集设备、频率设置均不变，采集过程中保持设备的姿态保持不变。将预处理后的数据作为测试集，离线阶段采集的全部地磁数据作为训练集，将训练样本输入至已建立的MPGA-SVM地磁室内定位模型中，其定位结果如图10所示，动态定位精度对比如表3所示。

由图10可以直观地看出，使用SVM模型应用到地磁室内定位是可行的，同时MPGA-SVM算法与PSO-SVM算法相比具有更好的定位真实性。由表2和表3可知，2组实验中MPGA-SVM算法的各项定位指标均优于PSO-SVM。由整体定位结果可得，MPGA-SVM算法在定位精度、定位稳定性方面均优于PSO-SVM算法。

图10 定位轨迹图Fig.10 Positioning trajectory diagram

表3 动态定位精度对比Tab.3 Comparison of dynamic positioning accuracy 单位：m

4 结束语

随着室内定位技术的不断发展与应用，基于地磁的室内定位技术具有连续性强、抗环境干扰能力强等优势；且不需要额外的室内物理设施支持，拥有较可观的发展前景。本文针对地磁匹配中的传统难点以及现有算法的缺陷，选择高斯径向基核函数作为SVM的核函数；利用MPGA的寻优性与其融合提出基于MPGA-SVM的地磁室内定位算法。试验结果表明，该算法具有更好的定位精度及稳定性，可有效应用于中小型场景室内定位。由于地磁场分辨率低，在大型场景中，随着指纹数量的增加，不同位置坐标对应的地磁特征值会存在更多相似的情况，导致单点定位误匹配概率较大。因此，未来可引入其他室内定位技术例如WiFi定位、蓝牙定位和行人航迹推算等与其融合，增加不同坐标对应的特征量，弥补单一地磁定位技术缺陷的同时进一步提升定位精度与稳定性。