基于余弦相似性的指纹匹配算法在WIFI室内定位上的应用

转自：http://mogu.io/consin_similarity_indoor_positioning-73

1、引言

"求孤的坐标…"

"谁看到月明了？"

"独嘉坐在哪里，我TT登陆不了！"

"有人看到我的土豪金了么？"

"有谁看到我的手机了么，白色经典版vivo音乐手机~~"

随着蘑菇街人员越来越多，业务交互越来越频繁，以及新大楼的投入使用，经常出现找人找不到、移动设备忘记丢在哪里的情况；对于充满时尚和科技元素的蘑菇街，我们怎么能容忍"通讯基本靠吼，找人基本靠走"的尴尬局面？

幸好幸好，有崇尚科技改变生活的工程师蓝狐君、语鬼君以及无所不能的大子腾。

胡乱说了这么多，顿时感觉萌萌哒，那么下面开始吧。

2、WIFI定位原理及实现

我们在研究的过程中，先后采用了两种定位方法，三角定位法和指纹数据匹配定位法。

2.1、三角定位法

三角定位原理非常简单，GPS系统采用的基本原理也是三角定位法。即三点可以确定一个点。该方法分为两个阶段:

2.1.1 基于RSSI的测距

该方法的理论基础是:无线电信号强度随着传播距离的增加而衰减¹，无线电传播距离与信号强度的关系。在大量实践的基础上可以得出，接收信号强度log-normal(对数-常态)分布模型，可以通过信号在传播过程中的衰减计算出传播距离。
 (1)
其中Pl(d)为在距离d位置接收到的信号功率(单位dBm),Pl(d0)为距离为参考距离d0位置接收到的信号功率，一般取1m。n为信号衰减因子,为均值为0的高斯随机变量。接收端的信号强度:
 (2)
基于实际情况及室内环境的因素，我们一般通过(1),(2)式进一步将RSSI定位模型简化为如下公式:
 (3)
通过对(3)式演化，我们得到了通过RSSI值算出距离的公式:
 (4)
由公式(4)，我们可以根据信号强度RSSI计算出距离d。通过距离d可以简单计算出一个范围。

2.1.2 定位

我们通过上面的测距，就可以测得三个不同位置的AP的RSSI，然后通过无线传输损耗模型计算出对应的距离d，然后以这三个位置为圆心，以d为半径画圆，所得三个圆的交点即为要求的坐标点；如图1:

图1 三角定位图
已知A(x1,y1)到D(x,y)的距离为d1,B(x2,y2)到D的距离为d2,C(x3,y3)到D的距离为d3，我们可以得出:
 (5)
由公式(5)，我们可以推导出点D的坐标(x,y)。
然而上面只是一种理想的模型，在实际情况中，我们不可能这么理想，我们可能会遇到以下各种情况:
a)、只有一个AP热点信号;

图2 一个AP
b)、有两个AP热点信号;

图3 两个圆交叉

图4 两个圆相离
c)、三个AP热点信号;

图5 三个圆交叉

图6 三个圆相离
d)、以及其他更加复杂的情况等。

通过对以上分析，假设我们在X(x,y)点能够获取到n个AP信号AP1(x1,y2),AP2(x2,y2),AP3(x3,y3)…APn(xn,yn)建立如下模型:
 (6)
由式(6)可以得出线性方程组:
 (7)
式(7)通过解线性方程组就可以求得X点的坐标。

在通过RSSI测距的实践中，由于室内环境部署复杂，信号干扰大，通过这种方法得到的结果经常偏差较大。于是，我们又采用了下面的算法。

2.2 基于指纹数据库及余弦相似性的定位算法

由于室内环境复杂，Wifi信号具有很强的时变性²，如图7

图7 不同时间采集的WIFI信号强度

上图中是不同时间采集到的同一AP的WIFI信号强度，由图中可以看出，WIFI的信号强度随着时间，以及环境的不同，在时刻变化着，所以，无线信号衰减模型难以准确的表现出距离与信号强度的关系。而基于指纹数据库的匹配定位方法就具有很好的鲁棒性。

指纹数据匹配算法主要也有两个阶段:

2.2.1 训练阶段

训练阶段主要是建立一个坐标点与WIFI信号强度向量的映射关系，从而建立一个指纹库(radio map)³训练阶段中，我们通过脚本采集不同位置的信号并发送到服务端。

通过脚本在每个位置上每隔5s采集一次数据，总共采集100次数据，并将数据上传到服务器上。

采集后，我们对每个指纹特征采用AP的RSSI均值，即
 (8)
即对同一个AP采集的多次数据取平均值，以此建立指纹数据库。

2.2.2 定位阶段

定位阶段的主要工作是根据一定的匹配算法，将接收到的AP的RSSI向量与数据库中的值进行匹配，找到一个最合适的值返回坐标。常用得匹配算法有NN,KNN,神经网络等，经过综合考虑，我们决定采用余弦相似性来进行匹配。

余弦相似性是通过测量两个向量内积空间的夹角的余弦值来判定两个向量之间的相似程度。余弦值越接近1，其夹角越接近0，表示两个向量越相似。如图8

图8 余弦相似性
两个向量间的余弦值可以根据欧几里得点积和量级公式推导:
 (9)
由式(9)以及理论，我们可以得出:
 (10)
通过以上理论基础，我们对客户端采集到的AP的信号强度值作为一个向量然后与指纹数据库中的数据计算余弦相似性，得到的值越接近1，代表越相似。

3、测试结果

3.1 测试环境

测试在蘑菇大楼8楼北区进行，8楼分布图如下所示

图9 蘑菇街办公楼8层平面分布图

我们总共采集了56个点，每个点每5秒钟扫描一次，总共扫描100次。以此数据作为样本，经过处理后建立指纹数据库。

3.2 测试结果

我们在北区随机选择了10个点进行测试进行了测试，测试效果图如下:

图10 测试效果图

测试数据如下:

表1 测试结果

| 编号 | 实际坐标 | 测试结果 | 误差(m) |
| :---: | :---: | :---: | :---: |
| 1 | (175,1232) | (175,1232) | 　0 |
| 2 | (240,1165) | (240,1165) | 　0 |
| 3 | (175,1075) | (175,1075) | 　0 |
| 4 | (110,1008) | (110,1008) | 　0 |
| 5 | (175,918)) | (175,918) | 　0 |
| 6 | (110,851) | (110,851) | 　0 |
| 7 | (175,761) | (110,761) | 　1.35 |
| 8 | (110,604) | (110,604) | 　0 |
| 9 | (315,604) | (315,537) | 　1.21 |
| 10 | (175,537) | (240,537) | 　1.35 |

从测试的结果来看，准确率较高，偏差几乎在一个座位的偏移(大致在1.3m左右)，与客户端采集到的数据不准确有关，在后期的优化处理中可以减少或避免此类事件的发生。

4、后记

由于时间的仓促，算法没有进行过优化，能够达到这样的效果已经相当满意。后续打算将该功能集成到蘑菇街即将开源出去的企业级内部通讯工具TeamTalk中去，大家就可以方便快捷的定位出对方的具体坐标。
后续还想对该算法进行优化，客户端采集数据的时候，需要进行多次采集，并使用卡尔曼滤波 (Kalman Filter),去除一些干扰信息。服务端在进行计算的时候采用贝叶斯公式，通过计算位置目标的后验概率分布，来进行定位。
另外需要解决的一个问题是，我们目前采集信号使用的是MAC OS提供的API，该API在采集信号的时候有一定的缓存，缓存时间大概10s左右。
在本次研究的过程中感谢羽漠，独嘉帮忙写测试客户端。

5、参考文献

1 刘尚合, 原 亮, 褚 杰. 电磁仿生学——电磁防护研究的新领域[J]. 自然杂志, 2009

2 J. Bardwell. Converting Signal Strength Percentage to dBm Values. White Paper, 2002.

3 林以明，罗海勇，李锦Tao，赵方．基于动态Radio Map的粒子滤波室内无线定位算法．计算机研究与发展，2010