基于余弦和k-means的新型wifi室内定位算法

北京理工大学珠海学院 缪 睿 刘建国

1 引言

在20世纪70年代，社会上对于定位的需求越来越高[1]，因此美国海军研究实验室提出了全球定位网计划，即全球定位系统（Global Positioning System），简称GPS。但是由于GPS技术在室内定位时，信号受建筑物影响大，定位精度和定位效率较低，因此GPS技术不适用于精准的室内定位，室内高精度定位的工作便需要其他无线定位技术来完成。

国内外的研究者提出了很多解决方案，主要有红外线室内定位技术、超声波室内定位技术、蓝牙室内定位技术等[2]。但是由于成本和技术等原因都没有找到很好的解决方法。随着wifi技术的发展与应用，国内外研究学者提出了一种新的解决方案——WIFI室内定位技术[3]。wifi室内定位技术是通过采集大量确定坐标点的信号强度形成指纹数据库[4,5]，新加入的待测坐标点由定位算法分析处理后，与指纹数据库进行比对而实现定位。wifi不受视距传播影响可用于遮蔽环境，信号覆盖范围大可用于大型场合，不受噪音信号干扰可用于复杂环境，共享网络与设备可减少硬件成本，比较其他无线定位技术具备更强室内定位理论优势，目前已经成为学术热点，且越来越多的被运用到实际应用场景中。然而由于wifi室内定位技术仍旧不成熟，室内定位在实际运用中的精度和速度尚有提升空间。

在以上的研究背景下，本文综述了WIFI室内定位技术的研究现状以及目前主要面临的问题，提出了一种基于余弦相似度算法[6]和k-means[7-10]算法的新型组合wifi定位算法，试图提升wifi室内定位技术的综合定位效率，并为该算法理论以及相关领域应用的研究者提供有益的参考。

2 基本原理和问题描述

随着用户对于精准定位需求的增加和国内外学者对于室内定位技术研究的深入，室内wifi定位算法已经成为室内定位的研究热点。其中，K-means聚类算法和余弦相似度算法是运用最广泛的两种指纹定位算法。本论文主要探讨K-means聚类和余弦相似度算法的优越点，并在两种算法的基础上进行进一步的研究。

2.1 K-means算法的基本原理和问题描述

由于K-means算法易于描述，具备时间效率高且适合处理大规模数据的特点，但是在数据庞大和定位环境复杂的情况下，单纯的K-means室内定位算法在实时定位过程中定位精度相对较低，不能满足移动时定位的要求。

2.2 余弦相似度算法的基本原理和问题描述

余弦相似度算法的算法思想为：在对两个同类事物进行对比时，按照同样的标准提取两个对象的特征信息，分别构造各自的特征向量，计算两个特征向量之间的余弦值，这个值越大代表二者的相似程度越高。其具体步骤如下：

分别提取目标比较对象X和Y的特征向量：

2） 按照公式计算两个特征向量的余弦值，即为二者的相似度。这个值越大表示二者之间的相似程度越高。

由于余弦相似性的定位算法，采用逐一比对每个坐标点并分析后根据单一指纹点给出的最终坐标的方法进行定位，所以其最终定位精度较高。但是由于该算法需要比对数据库所有指纹点[11,12]的数据，计算量大，定位速度较慢，在数据量庞大的情况下，实用性比较差。

3 系统模型

3.1 定位系统模型

无线信号在传播过程中，经过反射、折射、散射后，产生的与传播环境相关且独特的信号，被称为“位置指纹”。本文以位置指纹为基础构建定位系统模型[7]，系统在定位过程中包括离线与定位两个阶段。

在离线阶段，首先在实验区域建立直角坐标系，设定无线局域网设备发射信号为“AP信号”，AP信号的强度值和指纹特征为“RSS”，AP信号的MAC值为设备唯一标识参数。根据实验区域大小每1.5米选取一个坐标点，将每一个坐标点在环境中的M个AP的RSS值和MAC地址值记为(RSS1，MAC1，…RSSm,MACm)并作为该坐标点的指纹数据值，最终将采集的N个坐标点的指纹数据值的集合形成指纹数据库。

在定位阶段，移动终端首先会接收到周围N个AP接入点发出的信号特征，记为(RSS1，MAC1，…RSSn,MACn)，然后遍历指纹数据库对每一个指纹点的信息采取某种指纹算法进行矢量匹配，通过对比

分析结果，最后计算出最终坐标值。指纹定位系统模型如图1所示。

图1 指纹库匹配算法模型

3.2 指纹数据库模型

根据上节所述，建立离线数据库，用于进行定位指纹匹配。在Wi-Fi定位数据库采集的过程中，共选取N个参考值作为定位系统指纹点，每个参考点可以获得M个AP的RSSI和MAC值。集合所有的参考点信息表示为最终指纹库公式（3），假设有n个坐标点，每个坐标点的坐标信息用（x，y）表示，关联指纹数据库，那么指纹数据库可对应表示为公式（4）。公式（3）到（4）具体信息如下所示：

4 COS-K算法

从实际应用的角度考虑，定位算法必须同时具有高定位精度与定位速度才可以满足实际应用的需求。根据章节一所述，现有算法不能满足这要求，所以本文从满足实际应用需求出发，使用K-means算法作为数据库聚类算法结合余弦相似度算法作为定位算法，提出了一种新型组合wifi定位算法。下面，本章首先概述了新型组合算法的总体算法流程，之后详细说明了聚类的流程与公式和最终定位的流程与公式。

4.1 cos-k算法流程

利用K-means算法作为数据库聚类算法，结合了余弦相似度算法作为定位算法，新型组合wifi定位算法具体流程可表述如图2所示。

1）首先将指纹数据库用K-means算法进行聚类，将指纹点分成K个簇，得到K个种子点；

2）开始定位，在定位过程中，首先使用余弦相似度算法计算用户与每个相似点的相似值；

3）通过比较，选取值最接近于1的种子点，提取该种子点代表的簇进行下一步运算；

3）使用余弦相似性算法计算用户所在簇中的所有指纹点的余弦相似度算法；

4）对比各个指纹点的余弦相似度算法的计算值，找到最终估计点。

图2 cos-k算法流程图

4.2 数据库聚类算法

cos-k算法利用K-means算法[8]作为数据库聚类算法，目的是为了减少在实际定位中组合算法的计算量，提升组合算法的运算速度。具体流程如图3所示：

图3 k-means聚类算法流程图

1）在包含n个元素的数据库中，从所有元素中选出K个中心点；

2）运用欧氏距离公式测度，将其余的元素划分成K个簇，即元素间相似度尽可能的高的同类子集，和元素间相似度尽可能的低的异类子集；

3）划分结果后根据误差平方和准则（即最小方差划分）再次计算第K个簇的新中心点，并按照新的中心点重新聚类；

4）多次重复后得到准确的聚类结果；

5）得到聚类结果，将最终结果输入数据库。

具体公式如下：

1）欧式距离公式

假设有两个向量a(x11,x12,…,x1k)和b(y11,y12,…,y1k)，n为向量维度，当n=2时，即二维向量时，则可以表示为公式（5），该公式用于得出种子点距离各元素的距离，按照距离将元素进行聚类。

公式具体表示如下：

2）误差平方和准则

最小平方误差可表示为公式（6），当簇的个数为K时，可表示为公式（7），其中E为误差平方和，p为选定的中心点，Ci为第i簇的均值向量。该公式用于将相似度高的元素聚类为同簇，减少错分元素，提高聚类准确度。

公式具体表示如下：

4.3 指纹定位算法

cos-k算法在利用K-means算法进行数据库聚类后，结合余弦相似度算法进行最终的定位。目的是实现较高的定位精度，满足实际定位需求。基本公式如下：

假设有两个向量a(x11,x12,…,x1k)和b(y11,y12,…,y1k)，根据章节1.2所述和AB向量间的余弦值以及欧几里得点积和量级公式，可得到公式（8），当多个向量时，向量A=（A1，A2，A3…）,B=（B1，B2，B3…），最终可得到公式（9）。当余弦值的范围在[1，-1]之间时，余弦值的范围越趋近1，则两个向量的之间的夹角越小，向量的方向越接近0，方向越一致，相似性越高。

公式（8）至（9）具体表示如下：

但是在实际WiFi定位过程中，由于室内环境复杂wifi信号具有很强的时变性[7]，室内W i-Fi信号的强时变性，会造成待测点的AP数量与MAC地址并不完全与指纹点的AP的数量和MAC地址相匹配，为了解决这个问题，本文对余弦算法进行改进：

1）首先将待测点的RSS(共K个)信息表示如公式（10）所示。

2）分别匹配FDi和FP中AP的MAC地址值，得到K个相同MAC地址的AP的RSSI和MAC地址的集合，如公式（11）所示。

3）最终结合余弦相似公式得到如下表达式，如公式（12）所示。

公式（10）至（12）具体表示如下：

其中RSS为用户当前AP的信号强度，RSS*为指纹数据库中的各条指纹点的AO信号强度。

比较N个指纹点的sm iliarity的值，得到最接近于1的那个指纹点的坐标就是用户当前的位置，x,y为指纹点对应坐标。

最终位置坐标可以表达为：

5 定位仿真实验

5.1 实验环境

本实验的实验地点设置在北京理工大学珠海学院37栋宿舍区，层级建筑面积约为160㎡，以宿舍层级建筑长边缘建立X轴，短边缘建立Y轴，构成区域坐标轴。

信号发射端设备为本楼栋间的所有可接收信号的无线AP设备，信号接收端设备为安卓5.0的华为手机，使用了自主开发的基于Android平台的室内外定位APP。信号发射端设备与信号接收端设备之间的障碍物主要有宿舍与宿舍间的隔墙、书桌与书桌间的木质隔板、层级与层级间的隔层这三种情况。

采样时，手持已开启wifi功能的手机在楼层间进行数据采集，采集后数据库自动生成位置坐标，如A（x1,y1）和B（x2,y2）。采集样本需要有多次数据采集以积累足够的数据样本，同时在每个样本采集时为确保准确性需要在当前位置进行5次重复的数据采集并取其中的均值，采集后的数据提交给在线数据库。

5.2 仿真性能分析

以宿舍楼层建立二维直角坐标系，以1.5m*1.5m为间隔，在测试区域下方选取_24_个测试点，坐标系中X轴和Y轴分别为宿舍楼层的长和宽，其中楼层总长度为22.44m，宽为11.15m，每间宿舍长为1.85m，宽为2.65m。

待测定位坐标分别由余弦相似度算法定位算法、K-means算法和COS-K值组合定位算法这三种算法计算。

COS-K组合算法实测，黑色为真实坐标。红色点为COS-K组合算法的实测得出的定位点，构建待测点-定位点仿真图如图4所示：

图4 COS-K组合算法待测点-定位点仿真图

根据测试环境及预设数据，对COS-K组合算法、余弦算法、kmeans算法这三种算法进行比对分析。

图5给出了定位误差测试结果。纵坐标表示误差平均值，数值越大则误差越大。K-means聚类算法和COS-K以及余弦相似度算法三种算法的误差平均值分别为1.53m，1.06m和1.03m，根据结果可得COS-K值组合算法比K-means算法精确度提升30.07%，与余弦相似度算法基本持平。

图5 三种算法定位误差实测

图6 三种算法定位耗时实测

图6给出了定位耗时的测试结果。纵坐标表示定位耗时，数值越大则耗时越多。K-means聚类算法和COS-K以及余弦相似度算法三种算法分别耗时1.09s，1.23s和2.41s，根据结果可得COS-K值组合算法比余弦相似度算法定位算法减少耗时48.97%，相对于K-means算法提升了12.8%。

图7 综合系统消耗对比

图7给出了综合消耗的测试结果。设综合消耗为精度与速度的乘积，则纵坐标越大消耗越大，如图4所示。COS-K组合算法与K-means算法相比综合效率提升了21%，与余弦算法相比综合效率提升了47%。

综上所述，在综合分析了定位耗时和定位准确度两方面的测试结果后，本文提出的COS-K值组合算法在定位过程中实现了更短的定位时间和更高的定位精度，具备良好的综合效率，比单纯的余弦相似度算法定位算法和k-means算法更加强大。

6 结束语

本文以提高定位精度和降低定位耗时为算法原则，结合了余弦相似性定位算法和k-means聚类算法，提出了基于改进型余弦相似度算法和k-means算法的组合wifi定位算法，简称为cos-k值组合定位算法。经过测试和分析，cos-k值组合定位算法在定位耗时方面具备了k-means的低耗时的优点，弥补了纯余弦相似度算法定位算法的定位耗时长的缺陷；在定位精度方面具备了余弦相似度算法的高精度的优点，弥补了纯k-means定位算法的定位精度低的缺陷，具有很高的综合效率。

随着定位技术的发展，定位需求会越来越大，尤其是室内场合。针对目前科学研究的重要方向——室内定位，cos-k值组合定位算法将在具有更复杂的干扰因素、更大量的指纹样本、更广阔的室内面积如商场等地区进行进一步的测试并优化，使cos-k值组合定位算法更加趋于完善。

[1]杨靖宇.地理信息服务的思考与探索[A].郑州:信息工程大学,2009.

[2]王淑婷.基于位置指纹的wifi定位算法研究[D].吉林:吉林大学,2015.

[3]Probabilistic Room Location Service for W ireless Networked Environments. Castro P.,Chiu P.,Kremenek T.et al.The3rd International Conference on Ubiquitous Computing (UbiComp2001),2001.

[4]Method for yielding a database of location fingerprints in W LAN.Li,B.,W ang,Y.,Lee,H.K.,Dem pster,A.,R izos,C.Communications,IEE Proceedings-,2005.

[5]Performance Comparison of Indoor Positioning Techniques based on Location Fingerprinting in W ireless Networks. Tsung-Nan Lin,Po-Chiang Lin. W ireless Networks, Communications and Mobile Computing,2005.

[6]李嘉诚.室内W I-FI基于余弦匹配算法的研究与实现[A].南昌:南昌大学,2016.

[7]孔港港.一种基于位置指纹定位的K_均值聚类算法的改进[A].郑州:信息工程大学,2016.

[8]张伟.wifi指纹定位的一种新组合算法[A].湖北:武汉大学,2017.

[9]覃玉清.基于深度学习的wifi定位算法[D].南京:南京大学,2014.

[10]汤丽.基于模糊聚类KNN的室内W LAN定位算法研究[D].哈尔滨工业大学,2009.

[11]J Dong,Underground fingerprint module positioning algorithm based on wifi,Industry & M ine Automation,2014.

[12]陆音.复杂室内环境下的wifi定位技术研究[A].江苏:南京邮电大学,2016.