转自:http://mogu.io/consin_similarity_indoor_positioning-73
1、引言
"求孤的坐标…"
"谁看到月明了?"
"独嘉坐在哪里,我TT登陆不了!"
"有人看到我的土豪金了么?"
"有谁看到我的手机了么,白色经典版vivo音乐手机~~"
随着蘑菇街人员越来越多,业务交互越来越频繁,以及新大楼的投入使用,经常出现找人找不到、移动设备忘记丢在哪里的情况;对于充满时尚和科技元素的蘑菇街,我们怎么能容忍"通讯基本靠吼,找人基本靠走"的尴尬局面?
幸好幸好,有崇尚科技改变生活的工程师蓝狐君、语鬼君以及无所不能的大子腾。
胡乱说了这么多,顿时感觉萌萌哒,那么下面开始吧。
2、WIFI定位原理及实现
我们在研究的过程中,先后采用了两种定位方法,三角定位法和指纹数据匹配定位法。
2.1、三角定位法
三角定位原理非常简单,GPS系统采用的基本原理也是三角定位法。即三点可以确定一个点。该方法分为两个阶段:
2.1.1 基于RSSI的测距
该方法的理论基础是:无线电信号强度随着传播距离的增加而衰减1,无线电传播距离与信号强度的关系。在大量实践的基础上可以得出,接收信号强度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信号具有很强的时变性2,如图7
图7 不同时间采集的WIFI信号强度
上图中是不同时间采集到的同一AP的WIFI信号强度,由图中可以看出,WIFI的信号强度随着时间,以及环境的不同,在时刻变化着,所以,无线信号衰减模型难以准确的表现出距离与信号强度的关系。而基于指纹数据库的匹配定位方法就具有很好的鲁棒性。
指纹数据匹配算法主要也有两个阶段:
2.2.1 训练阶段
训练阶段主要是建立一个坐标点与WIFI信号强度向量的映射关系,从而建立一个指纹库(radio map)3训练阶段中,我们通过脚本采集不同位置的信号并发送到服务端。
通过脚本在每个位置上每隔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
相关推荐
主要介绍了Java基于余弦方法实现的计算相似度算法,简单说明了余弦相似性的概念、原理并结合实例形式分析了java实现余弦相似性算法的相关操作技巧,需要的朋友可以参考下
基于 MR的无线优化方法在无线网络中正逐步推厂应用,而其中位置指纹定位算法可应用在2G/3G通信网络的无线优化中。分析比较了几种不同的定位算法优劣性 ,并就其中位置指纹定位的优化算法作了优化改进,使用余弦距离...
改进的SIFT结合余弦相似度的人脸匹配算法
Moviebox:基于内容的机器学习推荐系统利用tf-idf和余弦相似性算法
TF-IDF算法的优点是简单快速,结果比较符合实际情况
正弦余弦算法(SCA)代码以及详解 。正弦余弦算法(SCA)是 Mirjalili于2016年提出的一种新型的群体智能优化算法,该算法结构简单、参数较少且易于实现,它的搜索过程主要受正弦和余弦函数的影响。
余弦相似度算法
一种新的优化算法,正余弦优化算法。提出了一种新的基于种群的优化算法
改进后的OPTICS聚类算法matlab代码,将原来的欧氏距离改为余弦距离的倒数,适用于文本聚类。
C#源码,演示字符串相似度 编辑距离 余弦相似性 SimHash算法
一种应用于指纹识别系统的指纹图像压缩算法.pdf 一种彩色图像水印方法的抗攻击性能.pdf 一种简单有效的彩色图像数字水印算法.pdf 压缩域上人脸识别的研究.pdf 基于DCT变换的信息隐藏算法研究.pdf 基于DCT变换的图像...
python实现正余弦优化算法Sine Cosine Algorithm(SCA)
BERTScore利用来自BERT的预训练上下文嵌入,并通过余弦相似性匹配候选和参考句子中的单词
为解决人脸表情识别任务中存在的类内表情...经过大量的实验和分析,该算法在RAF-DB人脸表情数据集上的准确率达到了83.196%,效果优于Softmax损失函数和Island损失函数,所提算法在人脸表情识别任务中具有较高的优越性。
得到标准向量前提下二者的转化公式,并在此基础上定义一种与欧氏距离意义相近关系紧密的余弦距离,使原有基于欧氏距离的K-means改进方法可通过余弦距离迁移到基于余弦相似度的K-means算法中。在此基础上理论推导出...
余弦相似度算法文本相似度算法的对比及python实现五种常见的相似度算法:余弦相似度(cosine_similarity)、jaccard相似度、编辑距离(Levenshtein)、MinHash、SimHash + 海明距离。
余弦相似度,又称为余弦相似性,是通过计算两个向量的夹角余弦值, 来评估他们的相似度。 余弦相似度将向量根据坐标值,绘制到向量空间中,如常见的二维空间。 余弦相似度衡量的是2个向量间的夹角大小,通过夹角的...
为解决目前已有的图像匹配算法不适用于对实时性要求很强的应用,提出了PLS(Partial Least Squares)与余弦定理相结合的并行化图像匹配算法。该算法在CUDA架构下,对图像矩阵分块,分块后每个小块图像存入共享存储器...
基于离散余弦包变换的语音压缩算法基于离散余弦包变换的语音压缩算法