基于归一化RSS和约束WKNN的WiFi指纹定位算法*
2018-09-27郭凯旋卢彦霖
冯 涛， 阮 超， 郭凯旋， 卢彦霖， 余 敏
(1.江西师范大学 计算机信息工程学院，江西 南昌 330022； 2.江西师范大学 软件学院，江西 南昌 330022)
0 引 言
利用WiFi进行室内定位为一项低成本、易实现的技术[1,2]。文献[3]将现有的室内定位方法分成3类：基于特定设备的定位方法、基于WiFi的定位方法和基于移动传感器的定位方法；文献[4]提出了改进的加权K最近邻(weighted K-nearest neighbor,WKNN)匹配算法进行定位，定位精度和稳定性方面较传统WiFi指纹定位算法有大幅提高；文献[5]提出了表征点位几何特性的点散发性强度(geometric strength of sporadic,GSS)概念，利用最邻近样本点的GSS判别移动终端所在控制网结构，动态地选择K最近邻(K-nearest neighbor,KNN)算法中的关键参数K，约束KNN能够有效地提高室内定位精度；文献[6]提出了自适应匹配预处理WKNN算法，可获得30 %以上的定位误差改善；文献[7]提出了利用众包来更新位置指纹库，针对用户的错误修正提出了基于密度的(density-based spatial clustering of applications with noise,DBSCAN)聚类的错误检测方法，该方法可以长时间保持较高的定位性能；文献[8]在高斯模型的基础上提出了一种改进高斯模型的滤波算法，再结合交点质心法得出一种新的距离估计方法，该方法能够准确定位并具有较高的定位精度和稳定性。
本文提出了基于归一化和的平方根(root-sum square,RSS)和约束 WKNN的WiFi指纹定位算法，运用高斯滤波归一化了WiFi无线信号权值，降低了信号的随机误差；并采用基于4—域系统WKNN匹配定位算法，防止离待测点较远的参考点参与匹配造成的误差。
1 WiFi位置指纹定位算法
1.1 离线建库阶段
1)将待测试区域划分若干网格，以每个网格的顶点作为参考点(reference point，RP)；
2)将每个RP的特征信息(包括坐标、RSS值)作为一组位置指纹存入位置指纹数据库。位置指纹库数据可表示为
(1)
1.2 在线定位阶段
1)实时测量待测点接收WiFi信号源的RSS值；
2)利用一定的匹配算法，包括确定性匹配算法：最近邻(nearest neighbor，NN),KNN,WKNN等，以及概率性匹配算法：朴素贝叶斯、最小均方误差(minimum mean square error,MMSE)[9]等，以及一些其他算法。与位置指纹数据库中的指纹数据进行匹配，估计最优的待测点位置信息。
2 改进的WiFi指纹定位算法
算法流程如图1所示。
图1 本文算法流程
2.1 离线—在线信号采集误差修正
本文提出了一种基于归一化RSS值权值的离线—在线信号采集误差修正算法。保留高概率的RSS值，对其概率进行归一化处理，提高高概率的RSS值的权值，将加权后求得的加权均值[10]作为其RSS值，使得结果更接近于真实值，确保定位精度。归一化处理过程如式(2)所示
(2)
求解更新后的RSS值
(3)
式中Ri为高概率RSS值,j为某一RP采集某一AP的RSS值。
2.2 约束WKNN的匹配定位过程
本文提出了一种确定性匹配算法WKNN,在KNN算法的基础上引入了权重系数，以权重系数代表不同位置指纹点在定位匹配中的重要程度，同时引入邻域的概念，用以提高定位精度。
1)待测点与参考点RP的相似度Li为
(4)
式中Rm为定位时接收到来自第m个AP的RSS值。
对Li进行升序排序，各指纹点所对应的坐标可以表述为Pi={P1,P2,…,Pk,…,Pi}，1≤k≤i。
2)邻域确定
图2 邻域
3)4—域系统判定
4)约束WKNN的匹配定位过程
5)待测点估算结果P
(5)
提出的约束WKNN的匹配定位过程来进一步约束选择参与最终匹配定位的参考点，有效减少了错误的参考点给定位带来的不利影响，再结合WKNN进行匹配，得到待测点的估算结果，提高了定位精度。
3 实验与结果分析
3.1 实验条件
定位区域的平面图如图3所示(包括4间办公室和2条走廊)。参考网格设置为2 m×2 m，无线AP型号采用TL-WR885N(按照图3所示，布置9个无线AP)，移动采集终端为华为荣耀6，在每个采样点采集RSS值15次。
图3 定位区域平面
3.2 实验结果分析
1)离线—在线信号采集误差修正效果
针对室内无线信号频繁的跳变现象，本文采用高斯滤波对RSS值进行滤波处理来提高定位精度。滤波后的效果如图4所示，其中横坐标为距离WiFi信号源的距离，纵坐标为RSS值的绝对值。
图4 高斯滤波效果
可以看出,归一化RSS值权值的离线—在线信号采集误差修正效果良好，滤波RSS值曲线逼近理想值。
2)约束WKNN算法对WKNN和KNN算法的优化效果
实验中，WKNN的关键参数K设置为3。约束WKNN算法(基于4—域系统的WKNN算法)、WKNN算法和KNN算法的累积误差分布(cumulative error distribution,CED)如图5所示。可以看出，约束WKNN算法的收敛距离为1.8 m左右，WKNN算法的收敛距离为2.4 m左右，KNN算法的收敛距离为2.8 m左右。在误差的整体分布上，约束WKNN算法的定位误差比WKNN算法和KNN算法低。
图5 累积误差分布
3)本文算法优化效果
从平均定位误差上来看：WKNN匹配算法为1.75 m、基于归一化RSS的WKNN匹配算法为1.66 m、约束WKNN匹配算法为1.5 m、本文定位算法为1.41 m。本文定位算法的定位优化效果明显，平均定位误差降低19.4 %。
4 结 论
提出的算法可以更好地估计用户的实际位置，平均定位误差降低了19.4 %，对基于WiFi的室内定位的发展起到了积极的推动作用。下一步工作将考虑采用众包更新的方式减轻离线数据采集和更新的工作量。
