K近邻快速匹配的WiFi指纹定位方法*

2018-08-03罗宇锋刘艳辉王国东

传感器与微系统 2018年8期

罗宇锋，刘艳辉, 王国东

(1.河南理工大学电气工程与自动化学院,河南焦作 454003；2.无锡九宇建筑设计院有限公司,江苏无锡 214000)

0 引言

无线局域网(WiFi)室内指纹定位具有成本低、易部署、不受视线约束等优点，已经成为当前室内定位研究的热点[1～3]。对室内WiFi指纹定位的研究中，Yang Z等人[4]使用监听物理层信道的状态进而提高WiFi指纹定位的精度。Laouudias C等人[5]基于指纹匹配的基础上，开发Airplace系统，使WiFi指纹定位的误差减小到2～4 m。Fang S H等人[6]通过从已测得的接收信号强度指示(received signal strength indication,RSSI)信号强度中取出特征性较强的信号，从而降低了室内多径效应对WiFi信号波动的影响，使室内指纹定位精度提高了40 %。Zandbergen P A等人[7]将WiFi与A-GPS、蜂窝定位进行联合，进一步的提高室内定位的精度。

本文采用高斯函数拟合和多次测量取平均值的方法来消除环境等因数对RSSI产生波动，使指纹库的数据更加准确和可靠；以距离为相似性测度的方法对数据库进行优化分类；通过引入相同接入点(access point,AP)数目作为参数，改进了K近邻匹配算法，并在对数据库分类的基础上，实现快速K近邻匹配算法，算法能去除冗余的数据，从而有效提高了匹配的精确度和速度。

1 基于WiFi指纹定位描述

环境对WiFi信号的多径传播的制约性很强[8]，信号的特征性很强，对于每一个固定的采样点，其信道的多径结构(即“指纹”)。定位卡在未知位置点上接收来自各个AP的信号强度与事先储存在WiFi指纹库中的信号强度进行匹配，实现对未知位置点的最佳估计。

1.1 RSSI信号处理

RSSI在定位起到重要的作用，RSSI的值越大，表明信号强度越大。由于信号的多径传播受环境影响很大，RSSI的值随测量距离的增大出现了不同程度的消减，随着时间的推移对应RSSI值也出现了不同程度的波动[9]。为了保证指纹数据库可靠性和准确性，本文先利用高斯函数拟合对采集的RSSI信号进行拟合，迅速选出高频段的RSSI。对于RSSI值的波动，用多次测量取平均值法对采样点接收的信号进行平滑处理。

高斯函数运用于采样点接收到的RSSI数据处理，可以去除一些小概率的数值(野值)，保留在正常范围内波动的高频WiFi信号值，使WiFi信号值接近真实的信号值。

高斯拟合函数为

(1)

先将采集到的RSSI矢量分别代入高斯拟合函数，用来保留可信的信号值然后对所保留的数据取均值，所得均值就是采样点的RSSI矢量。由于RSSI矢量数据众多，减少高斯拟合过程耗时，为了快速的筛选出想要的数据，采用近高斯拟合的方法

|RSSIi-μ|

(2)

式中μ为均值；σ为标准差；k为筛选区间RSSI值的个数，可根据数据保留的百分比M确定

(3)

式中N为采集的总次数。

若M取值过小，有可能破坏真实的数据，需适当增加k值用来增大筛选区间，提高RSSI矢量的保留比。在保证RSSI矢量不是真的情况下，快速有效地剔除错误数据。

1.2 WiFi指纹库训练阶段

1.2.1 定位区域的设定

首先，将定位的区域按照事先设计好的大小，分为若干个网格，每一个网格的顶点就是一个采样点；其次，确定坐标原点并按照一定规则对参考点进行编号，确定采样点的坐标位置，如图1所示。

图1 定位区域表格建立的坐标示意

1.2.2 WiFi指纹数据库建立

1.2.3 指纹数据库分类

1)在建立好的指纹库中选取若干个采样点与圆心点A(XA,YA)间的距离小于或等于R作为A类,即

(4)

选择不同的分类圆心，依照上式进行分类，可以在整个定位区域形成许多以R为半径的分类圆。如图2所示。

图2 基于WiFi信号强度分类的示意

2)根据圆半径进行分类，将会有若干个的孤点无法分类，把剩下的所有孤点作为孤点数据库。

1.3 未知位置点的分类

在定位匹配阶段，当移动用户走到一个未知的位置，定位卡首先扫描周围的AP，得到自身的RSSI矢量，根据定位卡实时接收的RSSI矢量确定所属的类，假定未知位置点的坐标(XtYt)=[R1R2…Ri…RW]，分类的思想为：以未知位置点与类别中心点的信号强度的均方误差最小P作为分类依据，如果均方误差大于P就把此未知位置点归到孤点数据库,P的取值是与实际地理环境和R的取值有关

(5)

1.4 改进K近邻匹配算法

WiFi指纹匹配最常用的是信号空间K近邻算法。在线定位时，定位卡首先扫描各个AP得到信号强度矢量SR=[R1R2…Ri…Rw]，其中，Ri(1≪i≪w)表示接收第i个AP的信号矢量，然后根据上述的分类规则，计算与建立好的分类指纹库中的每一个采样点的相似度Li。考虑到AP的传输距离为100 m，当定位区域过大时采样点就不能接收所有AP发出的信号，使得在空间距离相近的区域内采集到相同AP数目较多，相反，使得在空间距离较远的区域内采集到相同AP数目较少，因此，具有相同数目AP矢量在空间距离也相近。通过引入相同AP数目作为参数，计算相似度L，可以提高WiFi指纹匹配度

(6)

式中Mi为在线匹配阶段定位卡在未知位置点的AP和在第i个采样点AP的总数目；Msi为在线匹配阶段定位卡在未知位置点的AP和在第i个采样点相同AP的数目。图3为接收WiFi信号的示意，R1，R2为采样点，R1接收AP1，AP2，AP4，AP5的信号，R2接收AP2，AP3，AP5，AP6的信号。定位手机接收AP2，AP5的信号，在计算R1的相似度时，M1=6，Ms1=2。

图3 接收WiFi信号的示意

对所求的L进行排序并选取前K个较小的L所对应的坐标{P1,P2,…，Pi,Pk}(1≪i≪K),最终的定位结果为

(7)

本文采用改进的K近邻快速匹配定位原理如图4。

图4 K近邻快速匹配算法原理

2 实验与结果分析

2.1 实验部署

实验区域为长12 m，宽12 m，每隔3 m取一个采样点，共有25个采样点，在每个采样点处分别采集100次RSSI值经高斯拟合后取均值存入指纹库。实现快速的K近邻匹配算法分类的半径R=3 m,建立A，B，C，D和所有的孤点为一大类的孤点数据库。如图5所示。

图5 实验部署

实验采用基于Android平台开发的WiFi分析仪采集监测区域内的信号强度，采用SQL Serve 2008创建指纹数据库，将其配置到定位服务器，给服务器端程序提供数据支持，采用基于J2EE平台开发出的定位服务器负责接收客户端上传的数据并对其进行解析、计算、匹配最终实现定位。

2.2 实验结果分析

2.2.1 定位精度

在实验区域进行了多次定位实验，并记录了定位的结果。如图6所示从定位结果的最大误差分析，经过分类后的定位最大误差有了很大改善，可以看出，经过数据分类后的K近邻匹配在定位精度上明显优越于传统的K近邻匹配，最大平均误差从4.17 m降到了2.12 m，其中最大的改善从8.8 m降到1.9 m。说明分类后改进的K近邻使得定位结果跳动范围缩小。

图6 单点定位误差效果

2.2.2 定位时间

K近邻法主要耗时用于均方误差的计算。在实验中将25个采样点，分为A，B，C，D类和孤点的一大类，圆类别中有5个采样点，孤点数据库有9个采样点。传统的K近邻需要遍历整个数据库，计算25次均方误差，分类别后最多进行9次均方误差的计算。随着数据库中的采样点不断增多，分类改进后K近邻算法的优势就越来越明显。2种算法平均定位耗时K近邻为52.8 ms，改进K近邻为19.6 ms。