ISSN 
AWKNN Indoor Location Methods Based on Kalman Smoothing
-
摘要: 基于接收信号强度指示的WIFI室内定位方案存在采集信息跳变现象，进而影响定位精度的问题，提出一种基于卡尔曼滤波的改进自适应加权K最近邻（AWKNN）定位方法。对比分析多种平滑RSSI算法可行性，验证基于卡尔曼滤波对RSSI值进行平滑处理的优势，结合AWKNN算法并采用均方差计算匹配度，通过实时监控相匹配的无线接入点个数后自动调整均方差分母大小，以此实现定位误差的有效控制。实验结果表明，该基于卡尔曼的AWKNN算法在稳定性和定位精度方面较传统WIFI指纹算法有较大幅度提高。Abstract: Aiming at the problem of the information jump in WIFI indoor location based on the received signal strength indication (RSSI), which influences the positioning accuracy, an improved adaptive weighted K nearest neighbor (AWKNN) localization method based on Kalman filter is proposed. In this paper, the feasibility of smoothing the RSSI algorithm is compared and analyzed, and the advantages of smoothing the RSSI based on the Kalman filter are verified. Combining with the AWKNN algorithm and taking advantage of the mean square deviation to calculate the matching degree, the size of denominator m in the mean square error can be adjusted automatically through monitoring the number of matching wireless access points in real time to achieve the effective control of positioning error. The experimental results show that the AWKNN algorithm based on Kalman filter is more effective than the traditional WIFI fingerprint algorithm in terms of stability and positioning accuracy.
-
Keywords:
- AWKNN /
- fingerprint algorithm /
- indoor location /
- Kalman smoothing /
- RSSI
-
基于接收信号强度指示(RSSI)的室内定位方法，因具备性价比高、定位范围广且精度高的优势在众多领域存在应用价值[1-4]。但受室内障碍物遮挡、人员走动以及信号源功率不稳定影响，使用移动终端采集的RSSI信号中包含波动数据(“噪点”)，导致基于指纹库的传统定位方法在移动终端位置估计中出现不准确现象[5-6]。由于现有指纹定位算法对于“噪点”处理较粗糙，而指纹库的好坏又对定位精度产生影响。如何剔除指纹库中信号“噪点”，通过优化指纹库来降低定位误差是室内定位技术中有待解决的关键问题。
本文基于现有无线接入点(access point, AP)个数，提出一种基于卡尔曼平滑的改进自适应加权K最近邻(AWKNN)位置指纹定位算法。通过求取RSSI均方差代替欧氏距离，解决在一些错误匹配点上由于欧氏距离中的项数远小于匹配个数而导致欧氏距离变小，从而误判为最佳匹配点的问题。
1. WIFI指纹定位
根据图 1所示的WIFI定位原理可看出，定位过程主要包括指纹数据库建立(离线阶段)和导航位置信息实时获取(在线阶段)两个阶段[7]。建立指纹数据库的主要工作是进行数据采集[8]。在待定位区域按照一定的距离间隔部署若干个参考点(reference point, RP)，在每个参考点处采集接收到的来自所有AP的MAC地址、RSSI值以及对应的位置坐标等信息构建信号指纹库。为提高定位精度，可根据实际情况适当增加各RP处的采集时间，通过数据滤波方法将来自某一AP的RSSI值序列进行滤波处理，滤波结果作为该参考点上对应AP的RSSI值存入指纹数据库。
在导航位置信息实时获取阶段，首先在测试点实时采集N组WIFI的RSSI值，通过比较测试点AP的RSSI与RP中记录的对应AP的RSSI，利用测试点AP的RSSI相似程度最大，即信号强度最接近的参考点估计位置作为目标定位结果[9-10]。
2. 滤波优化RSSI值
由于障碍物遮挡、人员走动、信号源功率不稳定以及多路径效应影响，导致移动终端采集的信号存在波动较大的数据，影响指纹库精确度[11-12]。围绕该问题，本文对比性分析均值滤波、高斯滤波和卡尔曼滤波对于改善RSSI精度的可行性。
2.1 均值滤波
均值滤波是将参考点中各AP接收到的RSSI值分别求算术平均值：
$$ \overline {{R_i}} = \frac{1}{n}\sum\limits_{k = 1}^n {{\text{RSS}}{{\text{I}}_{ik}}} $$ (1) 式中，n为AP中RSSI样本数。均值滤波算法计算量小，无法对随机性误差进行有效处理。当RSSI样本数大、波动幅度低、突变次数少时，均值滤波对于信号的平滑度较高；当RSSI数值波动较大时，均值滤波对于误差的处理能力有限[13]。
2.2 高斯滤波
高斯滤波是一种线性平滑滤波，通过假设数据的误差特性符合高斯分布，保留高斯分布密度较大区域的数值，过滤掉因干扰产生的小概率数值[14]。
假设移动终端接收到的RSSI值服从N${\text{(}}0,{\sigma ^2}{\text{)}}$的高斯分布，用变量x来表示RSSI，可得到：
$$ F(x) = \frac{1}{{\sigma \sqrt {2\pi } }}{{\text{e}}^{\frac{{{{(x - \mu )}^2}}}{{2{\sigma ^2}}}}} $$ (2) 式中，
$$ \mu = \frac{1}{n}\sum\limits_{i = 1}^n {{x_i}} $$ (3) $$ \sigma = \sqrt {\frac{1}{{n - 1}}\sum\limits_{i = 1}^N {{{({x_i} - \mu )}^2}} } $$ (4) $$ P(\mu - \sigma \leqslant {x_i} \leqslant \mu + \sigma ) = 0.682\;6 $$ (5) 如式(5)所示，当RSSI范围处于$[\mu - \sigma ,\mu + \sigma ]$之间时，保存滤波后结果，否则舍弃。
根据高斯滤波降噪特性，可有效过滤跳变大且远离真值的数据，在一定程度上解决了RSSI数据稳定性较差的问题。但对于随机误差的影响以及样本数量较少时，其处理效果不理想。
2.3 卡尔曼滤波
卡尔曼滤波是以最小均方误差为估计，利用观测值对当前预测值加以修正产生最佳估计值，不断递推得到优化后的结果[15]。通过不断优化后设置卡尔曼滤波观测误差$r = 4$、初始状态误差${p_0} = 10$，得到估计值${x_k}$的推导过程为：
$$ {x_0}{\text{ = }}{y_1} $$ (6) $$ {x_{k,k - 1}} = {x_{k - 1}} $$ (7) $$ {p_{k,k - 1}} = {p_{k - 1}} $$ (8) $$ {k_k} = \frac{{{p_{k,k - 1}}}}{{{p_{k,k - 1}} + r}} $$ (9) $$ {x_k} = {x_{k,k - 1}} + {k_k}({y_k} - {y_{k,k - 1}}) $$ (10) $$ {p_k} = (1 - {k_k}){p_{k,k - 1}} $$ (11) 式中，${y_1}$为第一个观测值；${x_{k,k - 1}}$为状态一步预测；${k_k}$为卡尔曼滤波增益；${p_k}$为状态估计误差。
卡尔曼滤波以预测值、实测值、修正值的顺序递推，极大地跟随真值变动，是最贴近真值的适应动态环境的跟随算法。
2.4 滤波效果与分析
在同一个参考点上选取一个AP的120组RSSI值，分别对其进行均值滤波、高斯滤波和卡尔曼滤波，得到解算之后对比效果如图 2所示。
通过对图 2分析可以看出，均值滤波信号平滑度相当高，当RSSI样本数大，波动幅度低时，可信度较高；但当样本数量少，数据突变多时，误差增大明显。高斯滤波保留RSSI分布密度大的数值，过滤掉偏离较大的数据，对于解决信号稳定性差这一问题做出了贡献，它对抑制服从正态分布的噪声效果很好。表面上高斯滤波结果与原始数据跟随性最好，但实际上对于对应区间内RSSI值高于粗差的波动，高斯滤波采用直接剔除法，没有对这些具有较大偏差数据进行更恰当的处理。当样本量较少、RSSI值波动严重时，高斯滤波处理可能会剔除大量原始数据，与实际所求相差甚远。卡尔曼滤波的核心思想是“预测+校正”，它可以对系统状态进行最优估计，跟随原始数据变化，以预测值、实测值、修正值的顺序递推，极大地跟随真值变动，是最贴近真值的适应动态环境的跟随算法。
综上所述，卡尔曼滤波既能跟随原始数据变动，又可明显减缓波形抖动，减小误差，是对原始RSSI值进行滤波处理的最佳选择。本文将每个参考点中的每个AP的多个RSSI数据进行卡尔曼滤波后再求均值，最后将每个参考点中各个AP对应的数据存入指纹数据库中。
3. AWKNN定位算法
在线定位阶段，主要进行移动用户的位置解算。传统WKNN是将测试点收到的RSSI与各个参考点的RSSI进行匹配。首先利用欧氏距离公式计算测试点与指纹库中各个参考点之间的欧氏距离，然后找出欧氏距离最小的K个参考点，最后将这K个参考点的位置坐标进行加权平均，估计出测试点的位置。由此得到测试点i接收来自n个AP的信号强度值为：
$$ {\text{RSS}}{{\text{I}}_i} = ({\text{RSS}}{{\text{I}}_{i,1}},{\text{RSS}}{{\text{I}}_{i,2}}, \cdots ,{\text{RSS}}{{\text{I}}_{i,n}}) $$ (12) 在现实环境中，由于信号遮挡、人员走动、其他设备干扰以及WIFI覆盖范围有限等因素，在定位区域较大的情况下，不同的位置点不可能接收到来自所有AP的无线信号。在一些错误匹配点上，测试点与参考点中相匹配的AP个数较其余测试点显著减少，这可能导致计算的欧氏距离较小，容易把这些错误匹配位置判断为最佳匹配点[16-17]。
为规避这种错误，提出一种以测试点与参考点RSSI值均方差为相似性度量的改进自适应WKNN定位算法。
1) 选取测试点中1个AP与1个参考点中的各个AP进行匹配，当MAC地址相同时，匹配项数加1。2)选取该测试点中的其他AP依次与该参考点的各个AP进行匹配，当MAC地址相同时，匹配项数加1。3)对该测试点与该参考点接收到有相同的MAC地址的RSSI值计算均方差。4)该测试点依次与指纹库中所有的参考点遍历前3步。5)最后选取K个均方差最小的参考点，选其倒数为加权系数，对这K个参考点坐标进行加权处理，估计测试点坐标。6)对下一个测试点遍历前5步。
均方差公式和估计的测试点坐标$(x,y)$分别为：
$$ {d_{ij}} = \sqrt {\frac{{\sum\limits_{l = 1}^m {{{({\text{rss}}{{\text{i}}_{i,l}} - {\text{rss}}{{\text{i}}_{j,l}})}^2}} }}{m}} $$ (13) $$ ({x_i},{y_i}) = \frac{{\sum\limits_{j = 1}^K {\left( {\frac{1}{{{d_{ij}} + \varepsilon }}({x_j},{y_j})} \right)} }}{{\sum\limits_{j = 1}^K {\frac{1}{{{d_{ij}} + \varepsilon }}} }} $$ (14) 式中，m为测试点i与参考点j匹配的AP个数；$\varepsilon $是为了防止分母为零而选取的一个随机接近于零的数。
4. 实验结果及分析
测试环境如图 3所示，以地板砖(尺寸：0.6 m×0.6 m)为基准进行划分选取参考点，共选取2×80个方格点作为参考点。
实验所用AP均为学校统一布设，但路由器位置不相同，定位时均用该点可测得的所有AP。实验过程中，采集数据所用的软件为利用Java语言编写基于Android平台的数据采集APP，采集各个点的MAC地址、RSSI值、位置坐标等信息，如图 4所示。在离线阶段每个参考点采集20次，RSSI检测间隔为1 s。
在线阶段在走廊上选取30个测试点，每个点上采集20次，基于信号强度跳变是一直存在的现象，在定位阶段仍需对数据进行卡尔曼平滑处理。图 5为基于AWKNN定位算法的测试分析图，图中以平面图所示方向建立坐标系，x、y轴均为坐标值，‘○’为参考点的位置，它是以0.6 m×0.6 m为间隔，图中‘+’为测试点的真实位置，‘×’为测试点的解算位置。
为进一步验证本文AWKNN定位算法的有效性和可行性，采用相同的经过卡尔曼滤波的指纹数据库，分别进行WKNN和AWKNN两种算法的定位实验，得到这两种算法的误差比较及误差累计分布分别如图 6和图 7所示。
如图 6所示，AWKNN算法的收敛距离为3.8 m，优于WKNN算法的4.5 m收敛距离，AWKNN算法相较传统的WKNN算法而言，定位精度整体有所提升，整体平均误差由原来的2.93 m降低到2.36 m，定位误差在4 m内的比例由原来的70%提高到86.7%，定位在3 m内的比例由原来的60%提高到76.7%。
根据图 7，从定位精度稳定性和收敛距离来分析，基于卡尔曼平滑的AWKNN算法优于WKNN算法，这在无线路由众多并要求精度达到可视距离的建筑内可满足使用要求。
5. 结束语
移动端采集的RSSI受外界因素影响存在跳变数据，导致定位误差大。本文对比性地分析均值滤波、高斯滤波和卡尔曼滤波对于优化RSSI值的可靠性，验证了卡尔曼滤波具有良好的跟随真值变动特性。提出的AWKNN算法，通过利用m个相匹配AP均方差代替欧氏距离进行解算。对比性实验测试表明，基于卡尔曼滤波的AWKNN定位算法得到的收敛距离优于WKNN算法得到的结果，定位误差得到有效控制。本文的定位方法可为今后开展室内WIFI定位方案的优化提供参考。
本文的研究工作得到了辽宁工程技术大学研究生教育创新计划(YS201608)的资助，在此表示感谢!
-
[1] PAHLAVAN K, LI Xin-rong. Indoor geo-location science and technology[J]. IEEE Communications Magazine, 2002, 40(2):112-118. DOI: 10.1109/35.983917
[2] YIM J. Introducing a decision tree-based indoor positioning technique[J]. Expert Systems with Applications, 2008, 34(2):1296-1302. DOI: 10.1016/j.eswa.2006.12.028
[3] HUI T. Signals of opportunity assisted ubiquitous positioning and its key elements for outdoor/indoor environment[J]. Geomatics & Information Science of Wuhan University, 2009, 34(11):1372-1376. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=QK200902742547
[4] LIU J, ZHAI C, SONG D, et al. Indoor pseudolites precise point positioning based on improved time-satellites difference[J]. Geomatics & Information Science of Wuhan University, 2009, 34(1):105-108. http://en.cnki.com.cn/Article_en/CJFDTotal-WHCH200901026.htm
[5] 刘春燕, 王坚.基于几何聚类指纹库的约束KNN室内定位模型[J].武汉大学学报(信息科学版), 2014, 39(11):1287-1292. http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201411005 LIU Chun-yan, WANG Jian. A constrained KNN indoor positioning model based on a geometric clustering fingerprinting technique[J]. Geomatics & Information Science of Wuhan University, 2014, 39(11):1287-1292. http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201411005
[6] ZHUANG Y, SYED Z, LI Y, et al. Evaluation of two WIFI positioning systems based on autonomous crowd sourcing on handheld devices for indoor navigation[J]. IEEE Transactions on Mobile Computing, 2016, 15(8):1982-1995. DOI: 10.1109/TMC.2015.2451641
[7] 王磊, 周慧, 蒋国平, 等.基于WIFI的自适应匹配预处理WKNN算法[J].信号处理, 2015, 31(9):1067-1074. DOI: 10.3969/j.issn.1003-0530.2015.09.005 WANG Lei, ZHOU Hui, JIANG Guo-ping, et al. WIFI-based self-adaptive matching and preprocessing WKNN algorithm[J]. Journal of Signal Processing, 2015, 31(9):1067-1074. DOI: 10.3969/j.issn.1003-0530.2015.09.005
[8] 汪伦杰, 廖兴宇, 潘伟杰, 等.基于信号均值滤波+k-means+WKNN的WIfI指纹定位算法研究[J].微电子学与计算机, 2017, 34(3):30-34. http://d.old.wanfangdata.com.cn/Periodical/wdzxyjsj201703007 WANG Lun-jie, LIAO Xing-yu, PAN Wei-jie, et al. WIFI fingerprint location algorithm in indoor location based on signal mean filter+k-means+WKNN[J]. Microelectronics & Computer, 2017, 34(3):30-34. http://d.old.wanfangdata.com.cn/Periodical/wdzxyjsj201703007
[9] 姜莉.基于WIFI的室内定位关键技术的研究[D].大连: 大连理工大学, 2010. http://cdmd.cnki.com.cn/Article/CDMD-10214-1017046727.htm JIANG Li. Research on the key technologies of indoor location based on WIFI[D]. Dalian: Dalian University of Technology, 2010. http://cdmd.cnki.com.cn/Article/CDMD-10214-1017046727.htm
[10] SHUM K C Y, CHENG Q J, NG J K Y, et al. A signal strength based location estimation algorithm within a wireless network[C]//IEEE International Conference on Advanced Information Networking and Applications.[S.l.]: IEEE Computer Society, 2011: 509-516. http://ieeexplore.ieee.org/document/5763469/
[11] ZHUANG Y, LI Y, QI L, et al. A two-filter integration of MEMS sensors and WIFI fingerprinting for indoor positioning[J]. IEEE Sensors Journal, 2016, 16(13):5125-5126. DOI: 10.1109/JSEN.2016.2567224
[12] 李桢, 黄劲松.基于RSSI抗差滤波的WIFI定位[J].武汉大学学报(信息科学版), 2016, 41(3):361-366. http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201603013 LI Zhen, HUANG Jin-song. WIFI positioning using robust filtering with RSSI[J]. Geomatics & Information Science of Wuhan University, 2016, 41(3):361-366. http://d.old.wanfangdata.com.cn/Periodical/whchkjdxxb201603013
[13] LI H, CHEN X, JING G, et al. An indoor continuous positioning algorithm on the move by fusing sensors and WIFI on smartphones[J]. Sensors, 2015, 15(12):31244-31267. DOI: 10.3390/s151229850
[14] 孙铁强, 朱明辉.一种基于RSSI的混合滤波算法[J].工业控制计算机, 2015, 28(10):64-65. DOI: 10.3969/j.issn.1001-182X.2015.10.029 SUN Tie-qiang, ZHU Ming-hui. A hybrid filter algorithm based on RSSI[J]. Industrial Control Computer, 2015, 28(10):64-65. DOI: 10.3969/j.issn.1001-182X.2015.10.029
[15] 董思宇.基于混合滤波算法的无线传感网络定位系统的研究[D].呼和浩特: 内蒙古大学, 2016. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y3027746 DONG Si-yu. Research of positioning system in wireless sensor network based on mixed filter algorithm[D]. Hohhot: Inner Mongolia University, 2016. http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y3027746
[16] 赵聘, 陈建新.利用现有无线局域网进行室内定位算法研究[J].信号处理, 2014(11):1413-1418. DOI: 10.3969/j.issn.1003-0530.2014.11.029 ZHAO Pin, CHEN Jian-xin. A study on indoor localization algorithm using existing wireless local area network[J]. Journal of Signal Processing, 2014(11):1413-1418. DOI: 10.3969/j.issn.1003-0530.2014.11.029
[17] 陈空, 宋春雷, 陈家斌, 等.基于改进WKNN的位置指纹室内定位算法[J].导航定位与授时, 2016, 3(4):58-64. http://d.old.wanfangdata.com.cn/Periodical/dhdwyss201604011 CHEN Kong, SONG Chun-lei, CHEN Jia-bin, et al. An indoor location fingerprint algorithm based on improved WKNN[J]. Navigation Positioning & Timing, 2016, 3(4):58-64. http://d.old.wanfangdata.com.cn/Periodical/dhdwyss201604011
-
期刊类型引用(9)
1. 孙伟，孙沛伦. 非视距环境下的UWB/INS室内定位方法. 测绘科学. 2023(01): 1-7 . 
百度学术
2. 孙伟，孙沛伦. 一种基于机器学习分类器的UWB异常信号识别方法. 测绘科学. 2023(05): 1-8+34 . 百度学术
3. 宋玲，王立颖. SAE-DSN:一种具有去噪能力的室内定位回归模型. 小型微型计算机系统. 2023(10): 2255-2261 . 百度学术
4. 吴昌冬，华程. 基于人工神经网络的室内定位算法研究. 信息与电脑(理论版). 2022(20): 107-109 . 百度学术
5. 胡佳烨，梁中华，张培玟，胡雅悦. 基于深度学习的WiFi指纹室内定位方法. 计算机与数字工程. 2022(11): 2485-2489+2508 . 百度学术
6. 张旭，姚善化. 未调制可见光室内定位. 湖南文理学院学报(自然科学版). 2021(03): 58-61+80 . 百度学术
7. 李康乐，邵小强，潘红光，郭德锋，郑润洋，卫晋阳. 自适应抗差卡尔曼滤波对井下定位NLOS时延抑制方法的研究. 西安科技大学学报. 2020(01): 173-180 . 百度学术
8. 曹子腾，郭阳，赵正旭. 基于RSSI的定位技术中数据预处理的滤波算法. 电脑编程技巧与维护. 2020(01): 123-126 . 百度学术
9. 王轩，陈国良，曹晓祥，杨梦怡，王睿. 自适应K值及指纹库扩充的WLAN室内定位方法. 测绘科学. 2020(07): 26-32 . 百度学术
其他类型引用(10)
下载:
计量
- 文章访问数: 6471
- HTML全文浏览量: 2236
- PDF下载量: 114
- 被引次数: 19