基于室内指纹定位的优化算法

甘 露，杨 君，郭娅婷

（1.武汉科技大学冶金自动化检测技术教育部工程研究中心，武汉，430081；2.武汉科技大学信息科学与工程学院，武汉，430081）

引 言

随着智慧城市的发展，基于位置的服务(Location based services, LBS) 逐渐成为人们生活中不可或缺的一环，提供实时、准确的位置信息成为了服务的最终目标。人们日常生活的场所大部分位于较为封闭的室内。室内环境中无法接收到完整的卫星信号，并且部署复杂多变，增大了高精度定位的难度[1-2]。因此，室内定位技术的研究具有重大意义。常见的室内定位技术有：（1）通过预先在室内部署红外、超声波、射频识别、无载波通信等[3-5]特殊设备实现；（2）借由智能手机的发展与普及，利用其内置的传感器(如加速度传感器、重力传感器、陀螺仪、地磁传感器、视觉传感器等)[6-7]获取相关位置信息；（3）根据室内活动的热点区域大多实现WiFi 网络覆盖的实际情况，利用WiFi 技术实现定位。相较于昂贵的特殊设备，WiFi 网络的基础设施可大量部署，十分便捷且成本低廉。WiFi 信号本身也具有传输速率高、通信能力良好的优点。本文采用的WiFi 技术定位方法主要包括基于测距的定位方法和基于指纹定位方法两种。但WiFi 信号受到非视距传播(Non-line-of-sight propagation, NLOS) 和多径效应的影响[8]，传统基于测距的方法(如到达时间（Time of arrival，TOA）、时间差定位法（Time difference of arrival，TDOA）、到达角（Angle of arrival，AOA）[9]等)精度受限，且需要额外的测量设备，实际中并不常用。而基于指纹的定位技术[10]可直接测量接收信号强度(Received signal strength, RSS)，建立RSS 与位置关系的数据库，通过匹配待定位点指纹信息来实现定位。成本低且精度高，是现阶段最常用的定位方法之一。文献[11]致力于将WiFi 指纹定位与行人航位推算法(Pedestrian dead reckoning, PDR)[12]相结合来实现定位，但接收信号强度指示（Received signal strength indication，RSSI）易受环境因素影响，其不稳定性使得定位精度不高。文献[13]则将WiFi 指纹定位与动态区域划分结合，以减小RSSI 不稳定导致的高成本，但并不能保证边界线一定存在，严重影响了区域划分的实用性。

因此，本文在此基础上提出一种基于室内指纹定位的优化算法。首先采用先限幅后滑动平均滤波的方法剔除突变性和周期性干扰，分配参考点所属区域编号，通过预处理和多维特征构建进行数据库优化；接着利用支持向量机(Support vector machine, SVM)算法[14]对待定位点进行分类，确定所属区域，将用于相似度计算的欧式距离、曼哈顿距离和切比雪夫距离相结合得到位置估计，最后，结合行人航位推算(Pedestrian dead reckoning, PDR)算法将所得的步长和航向角一起进行粒子滤波（Particle filter,PF）得到最终定位结果。

1 相关工作

指纹的定位算法主要分2 个阶段：（1）离线训练阶段：将定位区域离散化为合适间隔的参考点，采集各参考点位置上的RSSI,建立指纹数据库；（2）在线匹配阶段：记录真实路径上各待定位点的RSSI、遍历指纹数据库实现匹配算法，输出定位结果。

1.1 离线训练阶段

假设待定位区域内有M 个参考点，N 个接入点（Access point，AP）热点，每个参考点采样C 次。构建指纹数据库如式（1）所示

式中，rssii,n表示第i（i=1，2，…，M）个参考点接收到第n（n=1，2，…，N）个AP 点经过C 次测量的平均RSSI。

1.2 在线匹配阶段

匹配算法分为基于概率性的和基于确定性的，概率匹配算法一般需要假设各AP 点与参考点间的RSSI 呈现高斯分布[15]。但实测表明RSSI 并不是标准的高斯分布，因此该算法定位精度并不高。所以一般采用基于确定性的加权K近邻法（Kweighted nearest neighborhood, WKNN）[16]。WKNN 算法通过实时采集WiFi 信号强度组成待定位点的RSSI 向量。计算与指纹库中参考点对应向量的相似度，确定相似度最高的K个参考点（本文取K=4）。利用式（2）求得这K个参考点位置坐标经过加权平均后的输出，如式（3）所示

式 中 ，i= 1,2,…,M;j= 1,2,…,N;k= 1,2,…,K，testn表 示 待 定 位 点 接 收 到 第n个AP 的RSSI，RSSIi,n表示指纹数据库中第i个参考点接收到来自第n个AP 点的RSSI，dis 为待定位点与参考点间RSSI 偏差。(xk,yk),(x,y)分别表示将dis 从小到大排序后前K个参考点坐标中的第k个和最终估计的位置输出。

2 算法改进

本文在传统指纹定位算法做出两点优化：（1）优化指纹数据库。引入限幅和滑动平均滤波做预处理；并根据区域分类的思想，给参考点所在区域分配ID（ID 表示参考点在定位区域内的区域编号），构建多维指纹数据库。（2）匹配算法优化。利用SVM 确定待定位点所在的区域id（id 表示通过分类算法计算后，待定位点所在区域的区域编号），匹配时仅在所属区域进行遍历，以此减小搜索空间的大小；引入曼哈顿距离和切比雪夫距离优化定位过程中的权重；结合PDR 算法进行PF 实现定位。算法框图如图1 所示。

2.1 数据库优化

图1 改进算法框图Fig.1 Block diagram of the improved algorithm

考虑2 种滤波方法进行预处理：

（1）限幅平均滤波：有效消除缓变信号中的突变干扰。根据经验将2 次采样允许的最大偏差设为阈值，采用式（4）更新采样值

（2）滑动平均滤波：用于数据更新率较高的实时系统，抑制周期性干扰。根据式（5）来更新采用值

式中，L 表示窗口大小（本文取L=4）。

本文结合两者优点，采用先限幅再滑动平均滤波来对RSSI 进行预处理，同时分配参考点所属区域ID 构成多维指纹数据库，如式（6）所示。

式中，RSSI 表示经预处理后的参考点指纹。

2.2 匹配算法优化

匹配算法优化主要分为3 步：

（1）在匹配待定位点坐标前，先对待定位点进行粗略的区域分类。假设有T 个待定位点，确定所在区域id 后，仅搜索对应ID 的指纹数据库便可提高搜索效率。SVM 在解决小样本、非线性及高维模式识别中有突出优势。根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的泛化能力。求解非线性问题时，需要将原始空间中的样本映射到高维特征空间中，高维特征空间中样本的内积等于原始空间中通过核函数计算的函数值，以此实现非线性问题到线性问题的转换。

求解式（7）得到带核函数的非线性SVM 的分类决策函数式（8）

式中，xi,xj表示指纹数据库中参考点的特征，yi,yj为参考点ID，αi,αj为采用拉格朗日乘子法对SVM 基本型求解的解，核函数K ( xi,xj) = xiTxj。待定位点实时测量得到的RSSI 代入分类决策函数得到其所在区域id，实现区域分类。

（2）WKNN 算法在进行相似度计算时只采用欧氏距离作为指标，本文进一步引入曼哈顿距离和切比雪夫距离，用3 种距离公式求出3 组位置估计坐标( xe,ye),( xm,ym),( xc,yc)作为三角形的3 个顶点，该三角形的重心( x,y )= ( ( xe+ xm+ xc) 3,( ye+ ym+ yc) 3 )便是改进后的定位结果。这3 种距离可由闵可夫斯基距离(Minkowski distance)共同定义。2 个n 维变量( x1,x2,…,xn)与( y1,y2,…,yn)间的闵可夫斯基距离定义为

式中，p 是一个变参数，根据变参数的不同，闵氏距离可以表示一类的距离。当p=1 时，就是曼哈顿距离；当p=2 时，就是欧氏距离；当p→∞时，就是切比雪夫距离。闵氏距离的缺点主要有2 个：（1）将各个分量的量纲，也就是“单位”同等看待；（2）没有考虑各个分量的分布(期望，方差等)可能是不同的。但使用RSSI 进行计算时，由于特征的性质是相同的，都是RSS，单位均为dBm,克服了上述的缺点。

（3）用六轴惯性传感器沿待定位点构成的路径行走采集加速度、角速度。根据步频检测算法和四元数法对行人行走的步数、步长、方向进行推算和统计，PDR 算法获得行人行走轨迹和位置等信息。PDR 原理图如图2 所示。

已知初始位置(x0,y0)，根据方向角和步长就能根据式（10）算出待定位点坐标。

图2 PDR 原理图Fig.2 Schematic diagram of PDR

本文结合PDR 算法将所获得的步长信息和方向角以及经过优化匹配算法后得到的位置估计作为PF 的输入，输出最终的定位坐标。

3 实 验

在一个宽12 m，长16 m 的室内环境进行实验。根据定位需求和实际环境的分布，在待定位区域建立1 m×1 m 的网格采样密度分布，部署参考点并选取4 个AP 点。数据采集过程中（由于所有测量数据受到外界干扰源几乎一样，即忽略不计），每个参考点采样10 次，采样间隔为0.05 s，并提前对参考点所属区域进行编号。定位时，实时采集待定位点的信号强度信息，并且将六轴惯性传感器绑在脚部同时采集加速度、角速度和角度信息。区域部署图如图3 所示，其中圆圈表示221 个参考点，连接“*”的线表示实时路径，线上的“*”表示48 个待定位点。

本文在使用RSSI 数据前均会对其进行先限幅再滑动平均滤波的预处理，一定程度上消除离群数据的影响，构建更精确且反映实际信号特征的指纹数据库。图4 虚线记录了在同一参考点进行100 次采样的RSSI，实线是预处理滤波后的RSSI。观察可知原始数据中的突变干扰被消除，RSSI趋于稳定。

图3 室内定位部署图Fig 3 Location area deployment diagram

图4 预处理Fig.4 Pre-processing

经预处理且分配区域ID 后，构建多维指纹数据库。先使用SVM 根据参考点10 次测量，共计2 110组的指纹特征及其所属ID 训练分类器，再对实时采集的48 个待定位点进行分类，分类的正确率达到83.33%，再将欧式距离、曼哈顿距离、切比雪夫距离结合实现定位。将得到的位置估计坐标作观测值。实时采集RSSI 时，六轴惯性传感器沿图3 中路径同时获得了加速度、角速度和角度信息，根据步频检测算法和四元数法得到待定位点的步长及航向角，结合PDR 算法经PF 后的路径和真实路径对比如图5所示。各待定位点位置坐标的误差如图6 所示。其中，若不进行任何优化处理，只用文献[16]提到的WKNN 算法进行定位，精度仅为2.73 m，单独使用曼哈顿距离或切比雪夫距离的定位精度分别为2.71、2.77 m。进行数据库和匹配算法优化后，精度为2.35 m，分别提高了13.92%、13.28%、15.16%。最终经PF 后精度可提高到0.75 m。

图5 真实路径与最终定位路径图Fig.5 Real path and final positioning path

图6 待定位点的定位误差Fig.6 Positioning error of undetermined sites

4 结束语

本文提出一种基于室内指纹定位的优化算法，对以下两方面进行优化处理：离线阶段通过预处理和多维特征构建来优化指纹数据库；在线匹配则先用分类算法进行区域分类，接着将欧氏距离、曼哈顿距离和切比雪夫距离结合对位置进行估计，再结合PDR 算法将得到的步长和航向角一起进行PF 实现定位，完成匹配算法优化。最后，通过实验验证了本文算法有效地提高了定位精度。