[LBS] 腾讯 - 构建大规模基于wifi的室内定位系统经验分

2023-03-04 本文已影响0人 nlpming

论文标题.png

1. 摘要&引言

基于GPS的室外定位当前被广泛使用，但是很少的室内定位系统被部署和使用。本篇论文作者分享了5年的经验关于如何部署和评估一个大规模的基于wifi的室内定位系统。本系统当前在1469个商场、393个办公楼、35个医院部署覆盖了35座城市，系统每天给几百万的用户提供定位服务。作者发布了相关的数据集，包括1469个商场和一个办公楼相关的指纹数据。相关数据集可以在github中看到：https://github.com/IndoorFingerprint/IndoorFingerprintData
室内定位常使用的技术包括：wifi、蓝牙、UWB等。蓝牙、UWB定位需要专门的硬件部署，不太适合大规模的部署。所以本文考虑使用wifi进行室内定位，因为在大多数商场、办公楼等区域都会有wifi的部署，不需要额外部署专门的设备。基于Wifi的室内定位技术大致可以分为三类：angle-based（AOA）、time-based（TOA）、fingerprint-based。AOA和TOA的wifi定位技术对WIFI设备有极高的要求，AOA定位技术要求有精确的角度测量、TOA技术要求有精确的时间测量。基于指纹的定位技术包括：CSI和RSSI。CSI的获取只有某一些WIFI卡才能获取比如Inter 5300卡和Atheros AR系列卡。因此最终采用基于RSSI测量的指纹定位技术，RSSI值可以在大多数的WIFI设备上获取。

2. 指纹收集

指纹收集是非常费时费力的，人工收集指纹的方式不太适合大规模的部署室内定位系统，因此本文提出了一种基于众包的方法收集指纹数据。本文提出了一个通过两阶段的方式是的大规模的指纹收集成为可能，首先第一个阶段获取WIFI AP数据的粗略的位置，通过这种方式获取初始的指纹库数据。然后我们通过用户的反馈迭代更新我们的指纹库数据，通过这种方式获取更高质量的指纹库数据。

2.1 WIFI AP位置估计

WIFI AP的位置估计分为两个阶段：第一个阶段我们通过名称匹配的方式获取一些AP的位置，这些AP的名称通常和POI名称有一定的关联，在楼层指引的帮助下我们能够获取这些AP的较准确的物理位置。第二个阶段我们使用推测出的AP位置，去推测剩余AP的位置信息。
第一阶段：使用名称信息估计AP的位置。 为了匹配Wifi AP的名称和POI，我们采用NLP工具（Spacy，https://spacy.io/）处理AP名称，并且我们考虑名称缩写的相似性。最终我们采用Google的wide&deep模型匹配AP的名称和POI的名称。在所有的4百万的AP库能够通过名称匹配的WIFI AP占比约为19.63%。其中商场、办公楼、医院中能够通过名称匹配获取位置占比分别为：38.23%、13.50%、7.65%。为了评估名称匹配模型的准确率，人工收集8000个AP的真值，最终计算得到模型匹配的准确率为98.4%。
第二阶段：估计剩余AP的位置。 要估计剩余AP的位置，首先需要计算剩余AP与已估计位置AP的相似度。
本文首先想到的是通过计算AP之间的共现次数，来计算两个AP之间的相似度，计算公式见公式（1）。其中 $N$ 表示 $AP_x$ 和 $AP_k$ 被同一台手机扫描到的次数， $M$ 表示扫描到 $AP_x$ 或者 $AP_k$ 的次数之和。但是公式（1）中没有考虑到扫描的信号强度值，因此在公式（1）的基础之上加上了信号强度信息得到公式（2）。注意公式（2）中分子项需要对分子、分母都归一化到0-1之间。

$Prox(AP_x, AP_k) = \frac{N}{M} \qquad (1)$
$Prox(AP_x, AP_k) = \frac{\sum_{i=1}^N \frac{Mean(RSSI_{xi}, RSSI_{ki})}{|RSSI_{xi} - RSSI_{ki}|}}{M} \qquad (2)$

在估计AP的位置之前，我们首先需要估计AP的楼层信息。如果与 $AP_x$ 最相似的 $N_f$ 个AP都在同一层，则 $AP_x$ 的楼层信息可以被立马确定，否则将这个AP的楼层信息放在之后的迭代中预测。为了平衡准确率和迭代次数，论文中将 $N_f$ 的值设置为3。得到AP的楼层信息之后，AP的位置信息通过同楼层的AP位置加权得到，具体计算公式见公式（3）。当AP的位置被估计之后，则可以将这个AP加入已知位置的AP库中。

AP位置估计.png

在商场、办公楼、医院三个场景下被估计出位置的AP占比分别为：91.10%，91.40%，86.87%。为了评估AP位置估计的准确率，我们人工收集8000个AP位置真值，最终误差估计的中位数在三个环境中分别为：5.16米、8.65米、23.61米。

2.2 指纹收集

指纹收集过程分为两步：初始化阶段和更新阶段；指纹的两个重要组成部分是：位置（Location）和这个位置相关的特征（unique features associated with this location）。传统的基于wifi的指纹仅仅使用AP的信号强度作为唯一的特征，本文中加入了位置的请求次数作为额外的特征。

室内指纹收集.png

位置指纹初始化： 本文采用基于迭代的方式更新指纹数据，首先通过众包的方式初始化指纹库数据，然后通过用户的反馈删除那些不正确的指纹数据。每次请求的时候，根据用户手机接收到的AP及其信号强度我们可以粗略估计用户的位置，具体计算公式见公式（4）。我们能够通过众包的方式很快的收集到很多的指纹数据。1469个商场平均需要花费6.6天的时间收集到87.4%位置的指纹数据。剩下的位置用户很少到访，因此对于定位服务影响不大。

粗略用户位置.png

位置指纹更新： 通过指纹的初始化可以获取很多指纹数据，但是可能不是很正确。因此本文继续通过大量的用户反馈修正初始指纹库数据。通过一些奖励机制获取用户反馈，比如给用户发一些优惠券等。大约可以获取5%的用户反馈，反馈的形式就是让用户给系统定位结果进行打分（1~5分）。只有当我们接收的用户得分与之前的得分相等或者更高的时候，我们才更新我们的指纹库数据，否则我们使用最新的AP数据获取位置的最新指纹数据。对于商场场景平均经历6天的时间，所有的指纹库数据都会获得5分的评分。

3. 数据处理

3.1 基于多特征的定位

本文的指纹定位使用的特征包括：RSSI和请求次数特征。为了计算数据库中网格的RSSI列表和在线收集的RSSI列表相似度，我们首先要定位两个列表的共同AP，然后计算RSSI列表相似度。计算的指标包括：euclidean distance, rank distance, distribute distance, reverse-pair rate。 如果共同的AP数量少于3，则这个网格将排除不考虑。本文还引入了请求次数作为另外一个指纹特征，请求次数特征能够告诉我们当用户发起定位的时候哪个位置更受欢迎。作者发现发起定位请求的地方大多数在某个POI的入口，比如饭店的入口。
为了比较好的将两种特征结合起来，我们使用熟知的LambdaRank模型。LambdaRank模型将网格的特征作为输入，对网格进行排序，排在最前面的网格就是最终估计的位置。本文将用户反馈的数据训练LambdaRank模型。

指纹定位过程.png

3.2 现实世界中的挑战

室内外边界检测： 边界检测对于精确定位至关重要，比如当一个用户进入到一个商场，如果仍然使用GPS服务，则会产生较大的定位误差。目前常用的方法是使用智能手机的传感器比如亮度和大气压传感器，用来判别室内外。本文仅仅使用GPS和WiFi的信号强度分布用于室内外的判别，其基本原理是：WIFI在室内外信号强度分布有明显差异，室内环境强于室外环境，然而GPS信号强度在室外环境强于室内环境。下图5展示了室内外WiFi和GPS信号强度分布，作者在不同的位置收集了WiFi和GPS信号强度分布训练了室内外判别模，模型获得的准确率为98.7%。

室内外WiFi和GPS信号强度分布.png

建筑中的中空区域： 在中空区域（例如电梯口或者室内桥）中，我们发现会出现大量的楼层识别错误。并且我们发现在中空区域边缘的AP信号强度分布出现了两个波峰，而其他区域的AP信号强度分布没有这样的表现，只出现一个波峰。最终在楼层定位的时候，我们将中空区域的AP删除因为引入它们将产生较大误差。

商场中的中空区域.png

AP信号强度分布（中空区域vs其他区域）.png

4. 大规模系统实验

4.1 商场定位

本文提出的室内定位系统部署在1469个商场中，所有的WiFi AP都是第三方部署的。并且作者发布了商场的指纹库数据，数据采集是基于5mx5m的网格。室内定位系统每天可以收到8810万的定位请求。本文提出的定位系统获得了4.56的评分基于41500个投票结果，投票的时间范围是从2020年1月到2022年3月。为了评估模型的效果作者手动收集4个商场的groundtruth，包括大中小各种类型的商场。并且选择一个大型和一个中型的商场，跟苹果比较室内的定位结果。最终总共收集了31140个参考点进行定位评估，其中大商场包括20300个，中型商场5230个，小型和特殊形状的商场分别2510个和3100个。并且对比了不同系列的Iphone手机和不同品牌的Android手机，商场定位效果如图9所示。
从下图9可以看出，在大型和中型的商场本文提出的室内定位系统可以获得6.12米和6.43米中等误差定位精度。本文提出的系统获得了与苹果通过人工收集指纹方式（苹果室内定位：https://register.apple.com/resources/indoor/Apple-Indoor-Maps-Program.pdf）差不多的定位精度。在小型和特定形状的商场，苹果没有指纹采集的情况下，定位效果显著下降但是本文提出的室内定位系统没有出现显著的下降。

本文室内定位系统与iPhone手机定位效果对比.png
下图10展示了不同品牌手机的定位效果对比，从下图可以看出不同品牌的手机定位效果没有显著的差异。

不同品牌手机的定位结果.png
AP位置估计： 在4个商场中通过名称匹配的方式，分别可以获取1592，288，101和176个AP的位置，分别各自占比52.8%，51.33%，47.64%，39.82%，将这种AP使用绿色点表示。进一步通过近似估计的方案，可以估计出1251，237，84和230个AP的位置，把这些AP标记为红色。最终有位置的AP的占比分别为94.38%，93.58%，87.26%，91.85%，还有一些没有估计出位置的AP标记为灰色。

不同类型商场的平面图.png

中空区域的处理： 通过使用本文提出的中空区域处理策略，楼层定位准确率有了显著的提升：55.63% -> 98.92%, 56.12% -> 99.31%, 56.75% -> 99.53%, 53.82% -> 98.25%。对应四个商场楼层识别混淆矩阵如下图11所示。

楼层识别混淆矩阵.png

AP物理位置改变： 在我们长期对两个大型商场评估的过程中，我们发现经过一年大约19.1%的AP会发生移动，如果不更新指纹库数据的话会导致很大的定位误差。通过我们提出的用户反馈的指纹库更新策略，能够很好的解决这样的问题。从下图12可以看出如果长期不更新指纹库数据，会导致非常大的定位误差。

指纹库更新对定位效果的影响.png

多路径效应影响： 本文对工作日和非工作日，不同时间段的定位误差做了一个详细的对比分析。从图13我们可以发现，对于不同时间段工作日和非工作日定位误差差距不是很大。

不同时间段的定位误差.png

4.2 办公楼定位

虽然本文的定位系统在商场获得了比较好的定位精度（平均约6.82米），但是在办公楼定位精度较差。主要的原因还是办公楼的AP部署比较稀疏，为了进一步提高定位精度，本文在办公楼定位结合了wifi定位和IMU传感器数据。一般来说信号强度的采集频率很低在0.0167Hz ~ 0.5Hz之间，但是IMU数据的采集频率一般在100Hz左右。利用加速度计、陀螺仪和地磁器的传感器数据和PDR算法，可以大致估计用户的行走速度、方向和位移。为了测试融合后的模型效果，本文测试了10条不同的轨迹，长度范围从50米到150米。50个志愿者分别去走这10条轨迹，最终的整体表现如图15a所示。从图15a我们可以看到使用IMU数据，中位数误差从9.13米下降到3.79米。并且作者也测试了不同RSSI采集频率对定位误差的影响，从图15b我们可以看出中位数误差大概在7.37米，4.76米，3.79米，3.26米和2.55米，分别对应不同的采样频率。

办公楼定位：结合wifi指纹和IMU数据.png

4.3 医院定位

医院定位和商场定位有很大的不同之处：医院部署的AP一般比较少，并且大部分AP都不能通过名字和POI进行关联。但是医院通常会有一些收银台，并且还有自助打印机供患者打印检查报告。为了保证更好的支付和服务通常会部署WIFI ap在附近。最终医院的中位数定位误差在11.85米。

某个医院第一层平面图.png

5.结论

应用和服务： 本文的室内定位系统可以提供基于位置的广告、打车、外卖服务。但是在停车场这种场景下，如何提供室内定位服务具有很大的挑战，因为Wifi AP部署的非常少。使用方式： 本文提出的室内定位系统，提出了三种方式使用定位服务：包括App, SDK, Web RESTful API。

参考资料

论文：Experience: Pushing Indoor Localization from Laboratory to the Wild
https://dl.acm.org/doi/pdf/10.1145/3495243.3560546
犀牛鸟硬核 | 腾讯大出行团队论文入选MobiCom2022！
https://www.withzz.com/article/208148f9397f/