基于加权余弦相似度的WiFi指纹室内定位

吴 赟, 蒋新华, 齐雁飞, 蒋学芹

(1.东华大学 信息科学与技术学院,上海 201620;2.上海航天电源技术有限责任公司 轨道交通事业部,上海 201615)

基于加权余弦相似度的WiFi指纹室内定位

吴 赟1, 蒋新华2, 齐雁飞1, 蒋学芹1

(1.东华大学 信息科学与技术学院,上海 201620;2.上海航天电源技术有限责任公司 轨道交通事业部,上海 201615)

基于WiFi的室内定位具有低成本、易部署、覆盖范围广、精度高等优点,成为室内定位技术研究的热点.WiFi指纹定位法可以对抗多径的影响,具有较高的定位精度.但是由于智能移动终端的种类繁多,使得室内定位系统离线建立的指纹数据库难以兼容不同的智能移动设备,降低了定位系统的适用性.为解决此问题,提出了加权余弦相似度算法,使用信号强度的加权余弦相似度作为匹配特征.实测表明,采用加权余弦相似度算法可有效解决终端差异性,提高了室内定位系统的精度和普适性.

室内定位; 终端差异; 加权余弦相似度; WiFi

0 引 言

现今,WLAN已经覆盖了人们活动的绝大多数室内环境.基于接收信号强度(RSS)的WLAN定位不用添加其他硬件装置,仅通过软件编程就可以在任何一款内置无线模块的智能移动设备上实现,并且利用指纹法可以有效降低多径传播和阴影衰落对定位系统的影响[1-2],因此成为目前研究的热点.

随着科技的发展,智能移动终端的种类越来越丰富,不同种类的智能移动终端采用不同标准的无线模块.这使得室内定位系统在线定位阶段所用的智能移动设备和离线阶段建立数据库所用的智能移动设备存在种类差异,导致在线阶段测量的RSS向量与所建立的指纹库不能有效匹配,降低了定位系统的普适性.为解决终端差异问题,提高定位系统的定位精度和普适性,本文作者提出一种基于加权余弦相似度算法的WiFi指纹定位技术,使用信号强度的加权余弦相似度作为匹配特征,消除了终端差异的影响.

1 系统总体设计

系统的定位原理框图如图1所示,离线阶段把室内空间按照适当的间隔均匀地划分为不同的区域,形成参考点网格,在每一个参考点处接收周围无线接入点(AP)的RSS并建立样本向量,每个参考点的位置信息与对应的RSS样本向量构成位置指纹,然后,将所有参考点的位置指纹信息存储起来构成指纹库.建立指纹库的具体过程如下:

假设在室内区域有L个参考点,并且每个参考点处可以探测N个AP的RSS,则第i个参考点处指纹信息向量为Ri={xi,yi,bi1,bi2,…,biN},其中i∈(1,2,…,L),(xi,yi)为第i 个参考点处的位置坐标.参考点的数量和有效性直接影响着定位系统在线阶段的定位精度,定位精度随着参考点的增加有所提高,但是,参考点增多使离线阶段搜集指纹信息的工作量增大,因此,离线阶段应该根据室内环境合理地选择参考点的数量.在线定位阶段,首先通过移动设备在待测区域实时采集AP的RSS向量,然后,将采集的RSS向量与离线指纹库中的数据进行匹配,得出定位结果[3-7].

图1 WiFi指纹定位系统的原理框图

2 室内定位算法

经研究发现,不同设备接收到AP的RSS向量不同,终端差异使得基于欧式距离算法的室内定位系统的定位精度降低,甚至会出现定位失败的情况.但是RSS向量的趋势相同,RSS向量间欧式距离的剧烈变化并没有引起向量间夹角发生剧烈变化,可以引入余弦相似度来衡量向量的相似性,余弦相似度算法公式如下:

(1)

式中,a为在线阶段移动终端在待测区域内实时采集到的来自N 个AP的RSS向量,bi为准备阶段所构建的指纹库中第i个参考点处收集到的周围的N个AP的RSS向量,采用余弦相似度算法计算出在线阶段信号强度向量与指纹库中向量的相似性,相似程度越大,两个参考点就越匹配[8],然后,对结果进行排序,选取相似程度较大的前K个参考点.将选取的K个参考点的位置坐标作均值处理,估算出移动定位终端在待测区域的位置坐标,即:

(2)

(2) 式的余弦相似度算法采用相同权重对选取的K个参考点位置作均值处理,获得最终的位置坐标,但实际上K个参考点的位置信息具有不同的可信度,余弦相似度大的参考点提供的位置信息将更可信.为了更有效地利用不同参考点的信息,提出根据余弦相似度的大小,赋予不同的权重值来估算待测点的位置坐标,所提出的这种方法称为加权余弦相似度算法.假设待测点N与K个参考点的余弦相似度的大小分别为S1,S2,…,SK(按余弦相似度降序排列),相似度越大,在位置估算时所作的贡献越大,权重值也越大.

余弦相似度的取值范围为从[-1,1],考虑到参考点的权重值没有负值的情况,首先把相似度转化为正数,即:

(3)

第i个参考点的权重值wi可以表示为:

(4)

式中,k为临近的参考点数目,利用不同参考点估算待测点的位置坐标,即:

(5)

从(5)式可知,加权余弦相似度算法首先考虑相似度较大的参考点,权重值的大小能更好地反映待测点与参考点间的关系.

基于加权余弦相似度的室内定位的流程分为以下步骤:

离线阶段:

1) 布置实验场景,在定位区域布置好AP.

2) 在实验区域内按照间隔为1m的间隔划分网格,每个网格的4个顶点作为离线阶段建立指纹库的参考点.

3) 基于空间因素和时间因素对RSS的影响,在每个参考点处的东、西、南、北4个方向上分别采集120 次,然后对这120次的采样值去奇异值求平均值,结合RSS平均值和参考点的位置坐标信息,构成系统的指纹数据库.

在线阶段:

1) 移动定位终端向服务器发送连接请求并定位,然后向服务器发送RSS向量.

2) 服务器接收RSS向量后通过 (5) 式的加权余弦相似度算法与离线阶段指纹库进行匹配,估算待测点的坐标,并将坐标信息发送到移动定位终端.

3) 移动定位终端获得位置坐标后,在室内地图上实时显示.

3 结果分析

为了验证算法的实际效果,比较了没有终端差异时加权余弦相似度算法与WKNN算法的精度,并且比较了存在终端差异时加权余弦相似度算法、余弦相似度算法、WKNN算法以及指纹差值法[5]的精度.实验环境为东华大学2号综合实验楼第四层的两间教室,在室内部署5个AP覆盖试验区域,如图2所示.

图2 实验环境

实验中离线阶段选取红米Note建立指纹库,指纹库主要包含采样点的位置坐标、AP的BasicServiceSetIdentifier(BSSID)和AP的RSS.在线阶段分别采用红米Note手机和酷派5216s手机在实验区域进行数据采集.图3为不存在终端差异时,采用WKNN算法和加权余弦相似度算法定位精度的对比,由图3可见在不存在终端差异时,两种算法的定位精度相近.

图4为存在终端差异时选用加权余弦相似度算法、WKNN算法定位[7]和余弦相似度算法[8]的精度对比.由图4可见存在终端差异时,通过权值对余弦相似度算法进行改进后,系统在3m内的定位精度较WKNN算法提高了3.8%.差值指纹法弱化了RSS向量和空间位置的关系,导致采用差值法时定位精度并不能够达到人们的需求.

图3 无终端差异时不同算法定位精度

图4 存在终端差异时不同算法定位精度

4 结 论

为了解决室内定位的终端差异性问题,提出了使用加权余弦相似度算法进行指纹点匹配,从而消除了由于不同终端接收信号强度不同造成的定位误差.实验结果显示,加权余弦相似度算法的使用不仅可以解决终端差异度对定位精度的影响,同时相比现有方法(余弦相似度和指纹差值法)具有更好的定位表现.

[1] Liu H,Darabi H,Banerjee P,et al.Survey of wireless indoor positioning techniques and systems [J].IEEE Transactions on Applictions and Reviews,2007,37(6):1067-1080.

[2] Shu Y,Huang Y,Zhang J,et al.Gradient-Based fingerprinting for indoor localization and tracking [J].IEEE Transactions on Industrial Electronics,2016,63(4):2424-2433.

[3] Brumitt B,Meyers B,Krumm J,et al.Easy Living:technologies for intelligent environments [J].Lecture Notes in Computer Science,2000,1927(2-3):12-29.

[4] 朱晓凤.基于核函数的特征级融合及在手部特征识别上的应用 [D].北京:北京交通大学,2009.

Zhu X F.Feature level fusion based on kernel function and its application in hand feature recognition [D].Beijing:Beijing Jiaotong University,2009.

[6] Borenovic M,Neskovic A,Budimir D.Space partitioning strategies for indoor WLAN positioning with cascade-connected ANN structures [J].International Journal of Neural Systems,2011,21(1):1-15.

[7] Youssef M,Agrawala A.Handling samples correlation in the horus system [C].Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies,2004 (2):1023-1031.

[8] 赵聪.基于位置指纹的WLAN室内定位算法研究 [D].哈尔滨:哈尔滨工业大学,2014.

Zhao C.Research on WLAN indoor location algorithm based on location fingerprint [D].Harbin:Harbin Institute of Technology,2014.

[9] Castro P,Chiu P,Kremenek T.A probabilistic room location service for wireless networked environments [C]//ACM.Ubi Comp′01 Proceedings of the 3rd international conference on Ubiquitous Computing,Atlanta:ACM,2001.

(责任编辑：包震宇)

WiFi fingerprint indoor localization based on weighted cosine similarity

Wu Yun1, Jiang Xinhua2, Qi Yanfei1, Jiang Xueqin1

(1.College of Information Science & Technology,Donghua University,Shanghai 201620,China;2.Rail Transit Division,Shanghai Aerospace Power Technology,Co.,Ltd.,Shanghai 201615,China)

Benefiting from the low cost,easy deployment,wide coverage and high precision,the WiFi based indoor positioning has attracted a lot of research attentions recently.The fingerprint location method has high location accuracy since it can combat the multipath effect.But because of the wide variety of intelligent mobile terminals,it is difficult to be compatible with different intelligent mobile devices,which reduces the universality of the positioning system.In order to overcome this shortcoming,a weighted cosine similarity algorithm was proposed.The experiments demonstrate that the proposed algorithm can effectively solve the terminal difference and improve the accuracy and universality of the indoor positioning system.

indoor positioning; terminal difference; weighted cosine similarity; WiFi

10.3969/J.ISSN.1000-5137.2017.01.021

2016-11-16

国家自然科学基金项目(61571135)

吴 赟(1976-),女,博士,副教授,主要从事无线通信中的信号处理技术研究、视频跟踪及图像处理方面的研究.E-mail:wuyun_hit@dhu.edu.cn

TN 925.93

A

1000-5137(2017)01-0124-05