基于余弦相似度的加权K近邻室内定位算法

黄运稳 陈 光 叶建芳

(东华大学信息科学与技术学院 上海 201600)

0 引 言

随着社会的进步与发展，人们对室内位置服务LBS(Location Based Services)的需求日益强烈[1]。将全球定位系统GPS应用于室内定位时，由于卫星信号受建筑物环境的影响很大，定位的效率较低，定位的精度也较差，因此不能达到实时和准确的定位要求。

随着无线通信技术的应用发展，基于接收信号强度的Wi-Fi室内定位成为目前研究的热点[2-3]。Wi-Fi信号不受视距传播的影响，信号的覆盖范围较大，而且不易受到噪声的干扰，适合于复杂的室内环境定位。尤其是，Wi-Fi指纹定位不用添加其他任何硬件，利用现有的WLAN，通过软件编程就可以在移动智能终端上实现定位[4-6]。

有鉴于此，国内外学者近年来对Wi-Fi指纹定位的匹配算法做了大量深入的研究，其中KNN[7]、WKNN[8-10](K Weighted Nearest Neighbor)以及余弦相似度[11-12]算法由于计算简单、易于实现而得到广泛应用。以上算法的核心在于通过RSS进行欧氏距离或相似度的匹配。然而一方面，由于接收信号强度自身的不稳定性与环境的多变性，导致接收信号强度不能完全准确反映客观物理位置。另一方面，欧氏距离体现的是接收信号强度数值的绝对差异，而余弦相似度是从方向上区分接收信号强度的差异，以上因素导致各算法在定位过程中容易引入奇异点[14]。针对上述问题，本文对K最近邻和余弦相似度的组合策略进行了分析研究与实验比较，给出了定位精度更高的优化组合算法。

1 Wi-Fi指纹定位匹配算法

1.1 KNN匹配算法

KNN算法通过测量两个向量之间欧式距离来度量它们之间的相似度。该算法将待定位点采集到的信号强度RSS向量[s1,s2,…,sn]与指纹数据库中的信号强度RSS均值矩阵[Si1,Si2,…,Sin]相匹配。设定位区域有m个参考点，共有n个AP，sj为待测点收到第j个AP的信号强度，Sij为指纹库中第i个参考点采集到第j个AP的RSS均值，i=1,2,…,m，j=1,2,3，…,n。距离的定义公式如下：

(1)

KNN算法在欧氏距离中从小到大依次选取K个参考点，然后以该K个参考点的质心作为估计位置。

(2)

KNN定位算法原理相对简单，以信号强度来反映物理位置关系，有利于定位系统的实现。

1.2 余弦相似度匹配算法

余弦相似度通过测量两个向量内积空间夹角的余弦值来度量它们之间的相似性。余弦值越接近1，表示两个向量的夹角越接近0度，向量的方向越相近，即表示两个向量越相似。如A和B的余弦相似度的计算公式如下：

(3)

基于余弦相似度算法理论，定位点采集的RSS矩阵s=[s1,s2,…,sn]与指纹数据库中第i个参考点的RSS均值矩阵Si=[Si1,Si2,…,Sin]相匹配，通过式(4)计算余弦值，以余弦值从大到小依次选取K个参考点，并以式(2)计算得出估计位置。

(4)

通过余弦相似度算法匹配，考虑了RSS向量的内在联系。余弦相似度使用两个向量夹角的余弦值作为衡量两个向量间差异的大小。相比欧氏距离，余弦相似度更加注重两个向量在方向上的差异。

2 基于余弦相似度的加权KNN算法

2.1 算法提出依据

针对以上对两种定位算法的介绍，通过三维坐标来进一步分析欧式距离和余弦相似度的区别，如图1所示。

图1 KNN与余弦相似度区别

由图1可以看出，欧氏距离衡量的是空间各点的绝对距离，即与RSS向量各分量的大小直接相关；而余弦相似度衡量的是空间向量的夹角，体现的是RSS向量在方向上的差异。KNN和余弦相似度算法各自有不同的计算方式和衡量特征，KNN算法能够体现RSS向量的绝对差异，余弦相似度是从方向上区分差异，而对绝对的数值不敏感。

针对以上分析，本文提出了基于KNN和余弦相似度的组合算法，旨在弥补单一区分方式的不足，从而提高定位精度。

2.2 算法步骤

在KNN算法筛选出K个近邻点的条件下，计算K个近邻点的余弦值。由1.2节分析可知，余弦值越大，表示两个向量越相似，在欧氏距离相近的前提下，余弦值大的近邻点定位精度越高。本文采用线下加权的方式来确定权值，从而包含位置指纹全部数据信息，进而提升定位精度。算法步骤如下：

1) 筛选近邻点。基于式(1)计算出定位点RSS向量与指纹库中各向量的欧氏距离Li，在Li中从小到大顺次筛选出K个参考点，坐标为(xi,yi)，i=1,2,…,K。

2) 计算余弦值。基于式(4)分别计算待定位点与K个参考点之间的余弦值，余弦值的大小分别为S1,S2,…,SK。

3) 确定权值。S1,S2,…,SK中，余弦值越大，在位置估算时所作的贡献越大，那么第i个参考点的权重值ωi可表示为：

(5)

4) 位置估计。利用权重值对K个参考点估算定位点的位置坐标，即：

(6)

3 实验分析

3.1 实验环境与系统

为了检验组合算法的定位性能，进行如下实验。实验环境为东华大学2号学院楼第六层，平面图如图2所示。

图2 实验环境平面图

文献[15]得出结论，当K=5或K=6时，系统定位的效果最佳。因此本文K值选择5对参考点坐标进行筛选。其中数据库信号采集与定位软件界面如图3所示。

(a) 离线信号采集 (b) 在线定位图3 软件界面截图

离线采集：选用魅族M578C建立离线指纹数据库，并将数据库信息存储在服务器。离线采样间隔为1 m，为了减少数据库建立的误差，每个离线采样点采集20组数据，以20组信号强度均值作为采样点的最终样本值。其中，数据库中的数据包括采样点坐标、扫描到每个AP的ID和接收到每个AP信号强度。

在线定位：选取30个定位点测试，分别包括每个实验室选取2个参考点，走廊选取10个参考点。移动终端向服务器发送连接请求，并向服务器发送当前RSS向量，服务器接受RSS向量后通过组合算法进行匹配，估算定位点的坐标，并将坐标信息发送到移动终端。

3.2 性能分析

图4为走廊中间位置的定位点连续进行30次RSS采集，参与定位AP数量为5个时RSS的变化。由图可知，室内环境复杂多变，引起AP信号强度起伏变化。因此单一的传统算法极易造成匹配出现偏差，引入奇异点。

图4 不同定位点信号强度变化曲线

首先在实验环境中选2个AP参与在线定位阶段，分别是6F-03和6F-07中的AP，采集30个参考点接收到参与定位的2个AP的数据，与数据库中的数据相匹配，不参与定位的AP不匹配，计算此条件下，组合算法及传统算法定位的平均误差。然后每次增加一个AP参与定位，以相同方式算出不同算法的定位平均误差。实验中第六个AP是校园公共网络。不同算法在AP个数不同情况下，定位平均误差的结果如图5所示。

图5结果表明，当不同个数的AP参与定位时，组合算法的平均误差均低于传统算法，由此排除了组合算法在特定AP数量下提升定位性能的可能性。

图5 参与定位的AP个数对定位结果影响

根据性能分析中不同AP个数对定位精度影响，我们选用5个AP参与定位，进一步比较不同算法的累加误差概率，如图6所示。

图6 不同算法的CDF曲线

由图6可知，本文提出的组合算法定位精度明显优于单一的传统算法。组合算法定位精度优于1 m的置信概率为42%，优于2 m的置信概率为72%，最大误差为4.3 m，相对传统算法均有改善。实验结果表明，文中提出的基于余弦相似度的加权KNN算法能够有效地提高室内定位的精度。

4 结 语

为了提高室内定位的精度，考虑到KNN和余弦相似度匹配算法在定位特点的互补性，提出了基于余弦相似度的加权KNN算法，从而弥补单一传统算法的不足。实验结果表明，基于余弦相似度的加权KNN算法在5个AP参与定位时，平均误差减少到1.67 m，定位精度明显提高。

随着室内定位技术的发展，基于余弦相似度的加权KNN算法需要在更大面积的环境、更复杂的干扰因素、更大量的指纹样本条件下进一步测试和优化，使得该算法更加完善。