基于SLFNs插值指纹粒子滤波的共享单车跟踪算法*

张栋梁， 曲 豪， 海本斋

(1.河南广播电视大学，河南 郑州 450008;2.河南师范大学 计算机与信息工程学院，河南 新乡 453007)

0 引 言

自2015年开始，共享单车逐渐在我国各线城市中得到覆盖，到2016年底，我国共享单车保有量达到了1 923万辆[1]。共享单车管理过程中，共享单车的定位跟踪是需要考虑的主要问题[2]。因为共享单车的出现时间较晚，对于共享单车的定位研究较少[3]。

在现有定位算法中，指纹和惯性测量相结合后的结果是平滑的、自校准的，但由于指纹算法需要假设唯一的指纹，所以精度仍然受到限制。实际应用中，由于多径效应和接入点位置的安排，两个遥远的参考点可以共享非常相似的指纹[4]。因此，模式识别算法不能保证正确的估计。不准确的位置估计会降低整体性能。同时，初始化粒子滤波(particle filtering,PF)所需的时间也是一个重要因素。全局初始化收敛速度较慢。在入口处部署额外的硬件增加了总成本。

本文对PF的改进有两个主要贡献：1)基于随机一致性抽样(random consistency sampling,RANSAC)方法得到从WiFi指纹在初始化阶段消除不准确的估计[5,6]。与全局初始化相比，其需要更少的迭代收敛。算法选择正确的估计，从指纹的行人航迹推算(pedestrian dead reckoning,PDR)数据建立了高斯模型。利用内点估计初始位置。2)为了克服初始化估计错误问题，通过单隐含层前馈网络(single hidden layer feedforward networks,SLFNs)插值对传统的PF加权模型的多个指纹概率进行分析[7]。考虑了不同的参考点WiFi指纹算法的概率，以尽量减少错误所带来的类似的指纹问题[8]。

1 基于RANSAC加权粒子滤波的定位算法

1.1 共享单车定位问题描述

基于粒子滤波的共享单车定位问题是对于时刻t查找共享单车轨迹v1:t的联合后验p(v1:t|z1:t,u1:t,m)。在该问题中，z1:t=z1,z2,…,zt为观测值，u1:t=u1,u2,…,ut为运动的里程计测量[9]。地图m在系统中通常已知。通常由惯性测量单元(inertial measurement unit,IMU)模块获得运动里程测量值。PDR是实现人类导航的常用方法。有多种方法获得观测结果，包括激光测距仪、红外、WiFi指纹等。本文主要集中于WiFi指纹的解决方案。

如图1所示，系统的输入包括WiFi RSSI扫描和IMU读数。对传统粒子滤波算法进行了两个重大改进。首先，将RANSAC初始化过程引入到系统[10,11]。需要对WiFi模块进行多次扫描，并使用PDR算法生成轨迹模型。过滤掉所有的异常点的轨迹并保持正确的初始化，以提高PF的收敛速度和精度。在正常采样阶段，引入了一种改进的重要性加权法。该阶段最初收集多个指纹估计的概率。用模型拟合算法构造高斯混合模型。每个粒子从构造模型中进行权重获取。最终进行基于权值的粒子重采样，并计算新粒子的位置均值。

图1 初始相位和改进加权粒子滤波方案

1.2 基于RANSAC的初始化

算法基于一致随机抽样的初始化过程

输入：指纹估计数据ψ、PDR模型MPDR、最大迭代数N、满足模型的最小数据点min、模型公差因子E、内部阈值Ith。

1)whileiterations

8)end if

9)end for

12)end if

13)end while

1.3 模型生成

为了构造PDR模型，首先执行c迭代的PDR算法。对于每一次迭代，用户的相对位置可以通过以下方式计算

(1)

(xi+1,yi+1)=(xi+Lisinφi,yi+Licosφi)

(2)

式中xi和yi为坐标,Li和φi为第i步的步幅和方向。利用高斯最小二乘拟合方法对高斯模型G(x)进行拟合。结合本文模型,将函数移到地图上的任意位置，利用(x′,y′)的2组系数对初始点进行估计，有

(3)

(4)

式中Distance(d;MPDR(x,y))为实例和模型之间的距离。并在曲线(xo,yo)上选择最接近点o。最终计算距离为

Distance(d;MaPDR(x,y))=

(5)

式中C为d到两个端点距离的最小值。

1.4 模型评价

RANSAC可将评价问题作为一个优化问题归结为

(6)

(7)

1.5 利用SLFNs插值的指纹概率建模

(8)

(9)

(10)

图2 SLFNs插值算法框架

在实际应用中使用插值算法，建议使用极限学习机(extreme learning machine,ELM)算法，主要优点是：1)学习速度非常快，训练时间在毫秒(ms)范围。2)ELM网络支持训练集的任何小训练误差，而隐藏的神经元不大于训练样本的数量。

2 实验分析

收集PDR数据和指纹数据。实验在人们进入共享单车跟踪场景时进行，RSSI样本受环境因素的影响，如移动物体和人。因此，基于接收信号强度指示(received signal strength indication,RSSI)指纹的方法受到多径效应和运动目标的显著影响，这与实际场景相似。PDR算法在手机上实现，使用IMU收集的数据。应用这些数据测试所提出的PF方案的初始化阶段和估计精度。对于指纹算法，在30 m×35 m范围内选择了84个参考点。在每个参考点收集了30个指纹。选择了支持向量机和概率估计算法作为对比算法。

2.1 初始化实验阶段

为了测试所提出的初始化方法，在10个不同轨道上不同位置的初始条件下收集了10个数据集。每个初始数据集包括11个步骤和11个WiFi扫描。首先研究每个数据集上的高斯模型拟合。PF在所获取的模型的当前位置初始化。实验的模拟结果如表1。

表1 初始化实验结果

PDR模型拟合误差用于检验模型的精度，结果表明：平均误差为0.21 m。数量的异常值论证了RANSAC方法的有效性。本实验中，该方法平均滤除了4.2个离群值。初始化误差距离和最大误差距离说明初始化的准确性。作为比较算法，选择基于K最近邻(K-nearest neighbor,KNN)的指纹初始化。该方法将平均误差距离减小1.6 m，减小最大误差距离2.6 m。为提高收敛速度，该方法只需要这11个迭代过程进行模型拟合和RANSAC算法。作为比较，全局初始化需要平均19.1次迭代才能收敛。

2.2 PF方案测试实验

实验中，所有的算法均使用相同的指纹数据库和相同的PDR数据。图3(a)给出了用原始指纹法估计的共享单车轨迹。利用红线连接进行连续估计。可以看出：结果受到不一致的观察和估计。在某些情况下，由于缺失值、噪声数据或指纹的相似性，连续估计的彼此距离较远。图3(b)给出了来自原始PDR的轨迹。图中，每个点代表一个步骤。方法在前3个走廊表现良好，但是积累了大量的错误。图3(c)给出本文方法的轨迹，结合了指纹和PDR的信息。实验结果表明，本文算法对含噪指纹数据和PDR数据进行了修正，提高了最终性能。

图3 跟踪轨迹

如表2所示，本文方法与SVM和概率算法的平均误差距离分别为1.2 m和1.3 m。这个值较PDR值低1 m，利用经典高斯加权法融合PF的概率方法。在最大误差距离方面也有很大改进。

表2 不同方法的误差距离

3 结束语

本文提出一种基于SLFNs插值指纹粒子滤波的共享单车跟踪算法，利用惯性传感器进行数据测量，并提出了一种新的PF方案，产生平稳和稳定的局部化知识。同时利用随机一致性抽样进行算法初始化，以减少收敛时间。实验结果验证了本文算法性能优势。