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

甘露，杨君，郭娅婷; GAN Lu; YANG Jun; GUO Yating

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

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

- ORCID：
甘露 ^1,2
- ORCID：
杨君 ^1,2
- ORCID：
郭娅婷 ^1,2

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

中图分类号： TP393

最近更新：2020-10-21

DOI：10.16337/j.1004-9037.2020.05.011

摘要

针对室内环境中WiFi信号强度易受外界干扰，其不稳定性使得在指纹数据库中进行匹配时准确性较低，定位精度不高的问题，提出一种基于室内指纹定位的优化算法。该算法分别对指纹数据库和匹配算法进行优化。数据库优化采用限幅和滑动平均滤波进行预处理，并根据室内环境分配采样点所属区域编号，构建多维指纹数据库；匹配算法优化首先根据支持向量机（Support vector machine，SVM）对待定位点分类，获取其对应的区域编号，再将欧氏距离、曼哈顿距离和切比雪夫距离三者结合得到位置估计。最后，结合行人航位推算（Pedestrian dead reckoning， PDR）算法将得到的步长与航向角一同进行粒子滤波（Particle filtering， PF）实现定位。实验表明：本文的算法将定位精度提高了13.92%。

关键词

室内定位; 指纹定位算法; 曼哈顿距离; 切比雪夫距离; 粒子滤波

引言

随着智慧城市的发展，基于位置的服务 (Location based services, LBS) 逐渐成为人们生活中不可或缺的一环，提供实时、准确的位置信息成为了服务的最终目标。人们日常生活的场所大部分位于较为封闭的室内。室内环境中无法接收到完整的卫星信号，并且部署复杂多变，增大了高精度定位的难度^[

1⁃2]。因此，室内定位技术的研究具有重大意义。常见的室内定位技术有：（1）通过预先在室内部署红外、超声波、射频识别、无载波通信等^{[参考文献 3⁃5}3⁃5]特殊设备实现；（2）借由智能手机的发展与普及，利用其内置的传感器(如加速度传感器、重力传感器、陀螺仪、地磁传感器、视觉传感器等)^{[参考文献 6⁃7}6⁃7]获取相关位置信息；（3）根据室内活动的热点区域大多实现WiFi网络覆盖的实际情况，利用WiFi技术实现定位。相较于昂贵的特殊设备，WiFi网络的基础设施可大量部署，十分便捷且成本低廉。WiFi信号本身也具有传输速率高、通信能力良好的优点。本文采用的WiFi技术定位方法主要包括基于测距的定位方法和基于指纹定位方法两种。但WiFi信号受到非视距传播 (Non⁃line⁃of⁃sight propagation, NLOS) 和多径效应的影响^{[参考文献 8
百度学术}8]，传统基于测距的方法(如到达时间（Time of arrival， TOA）、时间差定位法（Time difference of arrival， TDOA）、到达角（Angle of arrival， AOA）^{[参考文献 9
百度学术}9]等)精度受限，且需要额外的测量设备，实际中并不常用。而基于指纹的定位技术^{[参考文献 10
百度学术}10]可直接测量接收信号强度(Received signal strength, RSS)，建立RSS与位置关系的数据库，通过匹配待定位点指纹信息来实现定位。成本低且精度高，是现阶段最常用的定位方法之一。文献[11]致力于将WiFi指纹定位与行人航位推算法(Pedestrian dead reckoning, PDR)^{[参考文献 12
百度学术}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）所示

R S S I_{M \times N} = [\begin{matrix} r s s i_{1,1} & \dots & r s s i_{1, N} \\ ⋮ & ⋱ & ⋮ \\ r s s i_{M, 1} & \dots & r s s i_{M, N} \end{matrix}]

（1）

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

1.2 在线匹配阶段

匹配算法分为基于概率性的和基于确定性的，概率匹配算法一般需要假设各AP点与参考点间的RSSI呈现高斯分布^[

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

d i s = \sqrt[]{\sum_{n = 1}^{N} (t e s t_{n} - R S S I_{i, n})^{2}}

（2）

(x, y) = \frac{\sum_{k = 1}^{K} \frac{1}{d i s_{k}} (x_{k}, y_{k})}{\sum_{k = 1}^{K} \frac{1}{d i s_{k}}}

（3）

式中， $i = 1,2, \dots, M; j = 1,2, \dots, N; k = 1,2, \dots, K$ ， $t e s t_{n}$ 表示待定位点接收到第n个AP的RSSI， $R S S I_{i, n}$ 表示指纹数据库中第i个参考点接收到来自第n个AP点的RSSI，dis为待定位点与参考点间RSSI偏差。 $(x_{k}, y_{k}), (x, y)$ 分别表示将dis从小到大排序后前K个参考点坐标中的第k个和最终估计的位置输出。

2 算法改进

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

图1 改进算法框图

Fig.1 Block diagram of the improved algorithm

2.1 数据库优化

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

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

r s s i_{i}^{j} = \{\begin{array}{l} r s s i_{i}^{j} & |r s s i_{i}^{j} - r s s i_{i}^{j - 1}| \leq P \\ r s s i_{i}^{j - 1} & |r s s i_{i}^{j} - r s s i_{i}^{j - 1}| > P \end{array}

（4）

式中， $r s s i_{i}^{j}, r s s i_{i}^{j - 1}$ 是指第i个参考点第j和j-1次的测量值，P是设定的最大偏差阈值（本文取P=3）。为了避免初始值突变，在滤波之前需将第1次的测量值与C个测量值的中位数进行比较，若差值大于5 dBm，则用中位数替换初始值；若小于或等于5 dBm，则不改变。

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

r s s i_{i}^{j} = \frac{r s s i_{i}^{j} + r s s i_{i}^{j + 1} + \dots + r s s i_{i}^{j + L}}{L}

（5）

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

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

D A T A = [\begin{matrix} R S S I & I D \end{matrix}]

（6）

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

2.2 匹配算法优化

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

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

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

\begin{array}{l} \begin{matrix} \underset{α}{M a x} & \sum_{i = 1}^{T} α_{i} - \frac{1}{2} \sum_{i = 1}^{T} \sum_{j = 1}^{T} α_{i} α_{j} y_{i} y_{j} K (x_{i}, x_{j}) \end{matrix} \\ \begin{matrix} s . t . & \sum_{i = 1}^{T} α_{i} y_{i} \end{matrix} = 0 α_{i} \geq 0, i = 1,2, \dots, T \end{array}

（7）

f (x) = \sum_{i = 1}^{T} α_{i} y_{i} K (x_{i}, x) + b

（8）

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

（2）WKNN算法在进行相似度计算时只采用欧氏距离作为指标，本文进一步引入曼哈顿距离和切比雪夫距离，用3种距离公式求出3组位置估计坐标 $(x_{e}, y_{e}), (x_{m}, y_{m}), (x_{c}, y_{c})$ 作为三角形的3个顶点，该三角形的重心 $(x, y) = ((x_{e} + x_{m} + x_{c}) / 3, (y_{e} + y_{m} + y_{c}) / 3)$ 便是改进后的定位结果。这3种距离可由闵可夫斯基距离(Minkowski distance)共同定义。2个n维变量 $(x_{1}, x_{2}, \dots, x_{n})$ 与 $(y_{1}, y_{2}, \dots, y_{n})$ 间的闵可夫斯基距离定义为

d = \sqrt[p]{\sum_{k = 1}^{n} {|x_{k} - y_{k}|}^{p}}

（9）

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

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

图2 PDR原理图

Fig.2 Schematic diagram of PDR

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

\begin{matrix} y_{t} = y_{0} + \sum_{i = 1}^{t} d_{i} s i n θ_{i} \\ x_{t} = x_{0} + \sum_{i = 1}^{t} d_{i} c o s θ_{i} \end{matrix}

（10）

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

3 实验

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

图3 室内定位部署图

Fig 3 Location area deployment diagram

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

图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实现定位，完成匹配算法优化。最后，通过实验验证了本文算法有效地提高了定位精度。

参考文献

LI Xiaoming, TAN Xinglong, ZHAO Changsheng. PSO-LSSVR assisted GPS/INS positioning in occlusion region[J]. Sensors, 2019, 19 (23): 5256-5270. [百度学术]

GU Yangying, LO A, NIEMEGEERS I. A survey of indoor positioning systems for wireless personal networks[J]. IEEE Communications Surveys & Tutorials, 2009, 11 (1): 13-32. [百度学术]

MAINETTI L, PATRONO L, SERGI I. A survey on indoor positioning systems[C]//Proceedings of 2014 22nd International Conference on Software, Telecommunications and Computer Networks (SoftCOM). Split, Croatia: IEEE, 2015: 111-120. [百度学术]

SECO F, ANTONIO R J. Smartphone-based cooperative indoor localization with RFID technology[J]. Sensors, 2018, 18 (1): 266-289. [百度学术]

CHEN Pengzhan, KUANG Ye, CHEN Xiaoyue. A UWB/improved PDR integration algorithm applied to dynamic indoor positioning for pedestrians[J]. Sensors, 2017, 17 (9): 2065-2085. [百度学术]

XIE Hongwei, GU Tao, TAO Xiaoping, et al. A reliability-augmented particle filter for magnetic fingerprinting based indoor localization on smartphone[J]. IEEE Transactions on Mobile Computing, 2016, 15 (8): 1877-1892. [百度学术]

LI Bing, MUNOZ P J, RONG Xuejian, et al. Vision-based mobile indoor assistive navigation aid for blind people[J]. IEEE Transactions on Mobile Computing, 2018, 18 (3): 702-714. [百度学术]

GABER A, OMAR A. Utilization of multiple-antenna multicarrier systems and NLOS mitigation for accurate wireless indoor positioning[J]. IEEE Transactions on Wireless Communications, 2016, 15 (10): 6570-6584. [百度学术]

MA Yongtao, WANG Bobo, PEI Shuyang, et al. An indoor localization method based on AOA and PDOA using virtual stations in multipath and NLOS environments for passive UHF RFID[J]. IEEE Access, 2018 (6): 31772-31782. [百度学术]

SHU Yuanchao, HUANG Yinghua, ZHANG Jiaqi, et al. Gradient-based fingerprinting for indoor localization and tracking[J]. IEEE Transactions on Industrial Electronics, 2016, 63 (4): 2424-2433. [百度学术]

LU Qian, LIAO Xuewen, XU Shulin, et al. A hybrid indoor positioning algorithm based on WiFi fingerprinting and pedestrian dead reckoning[C]// Proceedings of 2016 IEEE 27th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC). Valencia, Spain: IEEE, 2016: 2545-2550. [百度学术]

KOO B, LEE S, LEE M, et al. PDR/fingerprinting fusion indoor location tracking using RSS recovery and clustering[C]// Proceedings of 2014 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Busan, Korea: IEEE, 2014: 699-704. [百度学术]

JUN J, HE Liang, GU Yu, et al. Low-overhead WiFi fingerprinting[J]. IEEE Transactions on Mobile Computing, 2018, 17 (3): 590-603. [百度学术]

CHOW K H, HE Suining, TAN Jiajie, et al. Efficient locality classification for indoor fingerprint-based systems[J]. IEEE Transactions on Mobile Computing, 2018, 18 (2): 290-304. [百度学术]

XU He, DING Ye, LI Peng, et al. An RFID indoor positioning algorithm based on Bayesian probability and K-nearest neighbor[J]. Sensors, 2017, 17 (8): 1806-1823 [百度学术]

XUE Weixing, HUA Xianghong, LI Qingquan, et al. A new weighted algorithm based on the uneven spatial resolution of RSSI for indoor localization[J]. IEEE Access, 2018 (6): 26588-26595. [百度学术]

您是本站第访问者

通信地址：南京市御道街29号南京航空航天大学(明故宫校区)

邮编：210016 传真：025-84892742

电话：025-84892742 E-mail：sjcj@nuaa.edu.cn

技术支持：北京勤云科技发展有限公司