倪振心，殷锋，袁平

（1.四川大学计算机学院，成都610065；2.西南民族大学计算机科学与技术学院，成都610041；3.重庆第二师范学院数学与信息工程学院，重庆400067）

0 引言

随着现代交通的日渐发达，人们的活动范围也越来越广，因此在任何地方都有对基于位置服务（Loca⁃tion-Based Service，LBS）的需求。不得不说成熟的卫星导航（GPS导航、北斗星导航）给户外活动带来了极大的便利，米级的定位精度使得人们在出行的路途中不再迷失方向。然而，在室内环境中卫星导航技术的信号会被建筑物屏蔽，室内的LBS只能另寻他法。现有的室内定位方案也比较丰富，包括Wi-Fi、RFID、蓝牙、地磁和惯导等技术。考虑到多方面的因素，基于地磁的定位方案综合比较后更显优势。地磁与类似Wi-Fi这样的传统射频技术不同，不需要部署额外的基础设施，且由于室内建筑结构的干扰和异常，使得室内的磁场有可以用于位置估计的可辨性[1]。且地磁信号也比较稳定，长时间间隔也不会发生较大变化。在保证定位精度的前提下，设备功耗也相对较低。综上，使用地磁信号进行定位是一种用于室内定位的较好方案。

1 算法可行性分析

室内定位系统的核心便是其定位算法，现有的算法大致可分为五类。Wang等人采用地标匹配的方法[2]；Shu等人采用DTW方法进行定位且有较好效果[3]；机器学习中的HMM方法被Ma等人使用进行定位[4]；Xie等人采用粒子滤波方法精度也较高[5]；也有Lee等人使用深度学习方法进行相关研究[6]。在定位系统或目标跟踪系统中，由于定位环境的复杂多样性和定位目标行为的不可预知性，对目标的准确定位就存在较大的困难。对于这种实时非线性动态运动模型通常用转移模型和观测模型来进行分析。模型是描述目标状态随时间变化的过程，观测模型则是将实时目标的状态与目标的输出信息关联起来[7]。通过将两种模型结合可更直观描述对目标的定位跟踪过程。

因为目标的运动是一个时序的过程，将整个过程离散化后假设f是目标从t-1时刻到t时刻的状态转移函数，h是目标在t时刻的输出观测函数，xt表示该目标在t时刻的状态，yt表示目标在t时刻的输出观测值，ut和vt则表示目标的转移噪声和观测噪声。

本文采用的粒子滤波算法是一种基于马尔可夫模型和蒙特卡罗方法的解决非线性滤波问题的算法[8]。主要思想就是在面对数值方法不容易解决的问题时，用类似统计采样的方法来近似的估算出其概率，通过进一步计算得到一个最优近似解。

假设目标状态数据集为x0:t={ }xn,n=0,…,t，在t时刻目标状态的先验条件概率为p(xt)，假设到t时刻为止获取到的观测数据集为y0:t={ }yn,n=0,…,t。则t时刻目标状态的后验概率p(xt|y0:t)，且假设重要性概率密度为q(xt|y0:t)。算法是基于统计采样的方法，每个粒子都有其对应的权值{ωi,i=1,…,N} 。假设重要性概率密度用目标状态的先验概率来代替，通过运算可以将后验概率表示为：

粒子的权值更新公式为：

因此目标状态的后验概率可通过所有粒子的加权求和求解。

应用到实际定位系统中，基本粒子滤波算法可以分为以下步骤：

（1）对采样粒子集进行初始化，保证采样粒子均匀分布于位置范围内，初始化各个粒子权值

（3）根据观测模型获取到的观测值yt更新各个粒子的权值

（5）进行重采样，在权值较高的分布中重新采样N个粒子。

（6）重复（2）到（5）直到粒子群收敛，计算出最终位置。

从粒子滤波的整个流程上可以看出，通过蒙特卡罗的思想对粒子群进行不断的采样、计算和估计，最终迭代更新到最趋近于真实情况的某几个粒子上，得到目标的定位结果。但也不难看出转移模型、观测模型的精度对结果有较大影响。

2 改良粒子滤波算法

型的跟踪与定位，但也存在一些不够完美之处。首先，采用蒙特卡罗方法虽然在一定程度上增加了整个系统的灵活性，但也变相地增大了整个系统的计算量。如果能在保证定位精度的前提下减少定位所需的粒子数，相当于也就减轻了系统的运算负载。Xie等人采用类似Wi-Fi的粗定位系统先确定一个大致的范围，再从这个范围开始计算收敛[9]。这种方法不仅需要额外的外设进行辅助，增加了系统的部署成本，且Wi-Fi本身就有不够稳定易受干扰的特点，粗定位带来的误差必定会对后续的定位结果造成影响。

2.1 方向可行性采样模型

粒子滤波算法的传统采样方法是将定位地图划分为一定单位大小，用手机对各个单位格点进行地磁信号数据采样。为了保证系统的定位精度，划分的单位必定不能太大，不能远大于人的平均步长约50cm左右。获取到各个单位格点的地磁值后，再用三次样条插值或者克里金插值等方法计算出整个地图的完整地磁指纹库[7]。不同的室内建筑对应不同的室内地图，假设在一个一百平米的室内环境进行采样，以1m2为单位进行划分也需要采集一百个左右的方格地磁数据，可见采集数据的成本过大。

本文提出一种基于方向可行性的采样模型。同样将地图以60cm×60cm大小的方格进行划分，每个方格都如下进行表示：

其中x,y表示该方格在地图上的二维坐标。M表示该方格分布范围内的地磁值，且由于不同的手机内置不同型号的地磁传感器，导致不同的手机的地磁读数会存在一些的差异。对比实验后可发现只有把手机读取的数值作为相对值才能使用。假设方格一条边上的地磁值为m1，对边的地磁值为m2，取两个值的差值作为在该方格分布内的地磁值，可以解决不同手机间采样数据存在差异的问题。D表示该方格分布内的方向可行性，取地图中的路径的主要方向为o1,o2,o3,o4，若该方格可通行的方向为o1,o3则d1=1,d3=1,D=(1,0,1,0)，所有的方格可构成一个方向可行性矩阵：

基本粒子滤波算法尽管能够满足对非线性动态模

2.2 改良算法与定位实验

对上述数据进行收集首先需要将采样地图按照路径的方向可行性划分为多条采样路径，然后分别对每一条划分路径进行采样。每次采样将手机放置于智能小车上，操纵小车从头至尾走完该路径，置于手机中的地磁传感器会读取到整个路径的方向和地磁时序数据。由于小车可以在某路径上做匀速运动，可以认为地磁在时序上的取值与在路径上的取值一一对应。以四川大学计算机学院4楼地图为例，方向可行性划分后的路径图如图1。

图1方向可行性划分路径

由图1可以看出主要的路径分为两种相互垂直的路径，令正北方向为0°，顺时针方向增加，经实测，该建筑较长端的方向约为西北方向310°，由此可得该地图路径的主要方向o1,o2,o3,o4分别约为40°、130°、220°和310°。假设取其中一条路径收集数据，首先读取地磁值序列，将数据转换到每一个方格上并求出其对应的地磁值M。同时读取传感器的方向数据，计算出与其差值最小的主方向（若不是路径的开始和结尾通常还包括其反方向）并更新该方格的可行性数据。

基于方向可行性的改良粒子滤波算法分为以下步骤：

（1）根据方向值和方向可行性矩阵U计算出采样坐标分布范围，对N个采样粒子进行初始化，保证采样粒子均匀分布于位置范围内，初始化各个粒子权值

（3）根据观测模型获取到的观测值yt更新各个粒子的权值

（5）进行重采样，为防止出现粒子退化的现象，Liu JS等人[10]提出一种计算有效粒子数的方法：

Nthreshold为判断是否需要重采样的阈值。若需要重采样则将权值较低的Nlow个粒子舍弃，通过方向可行性矩阵U计算出重采样位置分布，重采样Nlow个粒子。

（6）重复（2）到（5）直到粒子群收敛，计算出最终位置，。

相比于基本粒子滤波算法，这种基于方向可行性的粒子滤波算法不仅通过方向可行性的判断缩小了采样范围，减少了采样总粒子数，进而降低了系统整体的运算量；还在重采样阶段通过快速生成重采样位置分布，增加了粒子多样性防止出现粒子退化的现象。

为了通过实验验证该理论的有效性，同样以四川大学计算机学院4楼地图为例。在已经对地图进行采样并构建完地图数据集的前提下，定位初始化时实际测得的初始方向为37°，与路径主要方向o1最为接近，因此通过方向可行性矩阵U可得在o1方向上可行的所有方格集{ }Sj,j=1,…,k，显示在地图上如图2所示。

图2某可行方向上方格集

假设地图总方格数为K，o1方向上可行方个数为k,k∈K，在保证采样粒子分布密度不变的条件下，改良后采样粒子数与方格数成正相关N'∝k。采样粒子节省率为：

已知地图总共方格数为416个，实际测得o1,o2,o3,o44个主路径方向上方格数分别为176,242,183,239，粒子节省率如图3所示。可见通过使用方向可行性采样方法，可有效减少实际所需的采样粒子数，进而提升系统整体的计算速度。但不难发现采样粒子节省率与实际室内场景的路径结构有较大关系，若路径单一可能达不到理想的效果。

图3各个方向采样粒子节省率

实验采用Huawei P30作为实验手机，分别采用基本粒子滤波算法和改良粒子滤波算法在四川大学计算机学院3楼和4楼进行实地定位。在构建好两层楼的地磁数据库后，进行了反复的实验，最终定位精度对比如图4所示。可见改良粒子滤波算法有效地缩小了定位误差距离，提高了定位精度。

图4基本粒子滤波算法与改良粒子滤波算法定位结果

3 结语

本文的目的是对地磁室内定位中现有的基本粒子滤波方法进行改良，首先介绍了基本粒子滤波算法存在的计算量大和粒子退化的问题，因此提出了一种基于方向可行性的采样方法，在不借助其他外设的条件下，能有效地减少系统定位所需的粒子数，降低了系统计算量和时间消耗。且在重采样阶段增加了采样粒子的多样性，提升了系统的定位精度。但该方法比较依赖地图的整体路径结构情况，在一些空旷单一或者路径不规则且复杂的场景下可能达不到理想的效果，因此后面的工作将从其通用性上去考虑，在多种室内场景定位中减少系统计算量，并尝试能否进一步提升定位精度。