一种室内定位免采集室内店铺Wi-Fi指纹填充算法
以下内容转载自腾讯位置服务的文章《一种室内定位免采集室内店铺Wi-Fi指纹填充算法》
作者：腾讯位置服务
链接：https://segmentfault.com/a/1190000022847510
来源：segmentfault
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
对于目前最主流的室内Wi-Fi指纹定位技术而言，采集Wi-Fi指纹的覆盖度和新鲜度是决定定位精度最重要的因素。受到成本和导航需求等因素的限制，腾讯地图定位平台目前提供的室内定位服务只对商场的走廊部分采集了指纹信息。对于面积更大的商场店铺，目前很难人工采集Wi-Fi指纹。本文介绍了我们如何利用过去积累的定位日志数据，实现了室内店铺Wi-Fi指纹的自动填充，并用于室内定位服务，从而提升了我们室内定位服务的覆盖度和服务质量。
一、问题背景
在室内环境中，由于建筑对信号的遮挡，GPS信号非常微弱甚至探测不到，无法用于定位服务。而随着Wi-Fi技术的普及和广泛部署，基于Wi-Fi指纹的定位技术目前已经成为室内最普适、最基础的定位解决方案。然而，对于Wi-Fi指纹定位技术而言，采集指纹的覆盖度和新鲜度是决定定位精度的最重要的因素。
图1. 北京欧美汇购物中心某层人工采集Wi-Fi指纹覆盖示意图
目前，腾讯地图定位平台对国内的主要商场都提供了基于Wi-Fi指纹的室内定位服务。然而，受到指纹采集成本和导航需求等因素的限制，目前指纹采集主要集中在商场走廊区域。图1展示了在北京欧美汇购物中心某一层中我们采集的Wi-Fi指纹的覆盖情况。从图中我们可以看到，对于商场内主要的走廊区域，我们都进行了指纹的采集。然而，对于范围更大的店铺部分，目前采集Wi-Fi指纹的流程很难覆盖到。这种指纹覆盖不全的情况会导致我们无法在整个商场内保证定位质量的一致性。当有用户在店铺内发起定位请求时，由于店铺内缺失Wi-Fi指纹信息，理想的情况是恰好在店铺门口采集的Wi-Fi指纹与用户请求定位时扫描到的Wi-Fi信息比较类似，将用户定位在店铺门口。然而，更糟糕的一种情况则是如图2展示的那样，我们将用户定位在了一个离店铺较远的位置，严重降低了用户的定位体验。
图2. 用户在店铺中发出定位请求，实际定位结果偏移了44米
对于这种情况，最为直接的解决方案是在店铺内也采集指纹信息，做到整个商场内指纹采集全覆盖。然而，由于店铺的面积远远大于商场内走廊区域的面积，采集店铺指纹会导致成本成倍增加。同时，由于店铺装修、搬迁以及店内Wi-Fi设备更换更为频繁，要想保证店铺指纹的准确性，店铺指纹的更新也需要更加的频繁。这些因素导致了在目前的技术条件下，无法人工地对店铺指纹进行采集。因此，我们要寻求别的方式来对商场内的店铺指纹进行填充，并将其用于我们的定位服务。
二、店铺Wi-Fi指纹的自动化填充
目前，腾讯地图定位平台的室内定位服务覆盖了全国的三千多个主要商场，每天有上亿次定位请求发生在这些商场中，并且有上千万次定位请求是在手机连接了Wi-Fi热点的情况下发出。如果一个用户发出定位请求时连接的Wi-Fi热点是店铺内的热点，那么该用户发出定位请求时所在的真实位置很有可能就在该店铺中。此时，该用户请求定位时上传的Wi-Fi扫描信息就有机会被用于建立店铺指纹。 然而，想要利用用户连接热点时请求定位的日志记录来建立店铺指纹，有一些挑战需要解决：
- 用户连接的Wi-Fi热点是否在店铺中？在哪个店铺中？
- 如何确保连接了热点的定位请求就一定是在对应的店铺中发出的？
针对第一个问题，我们根据每个Wi-Fi热点的名称、店铺的名称、从历史定位日志中挖掘出的每个Wi-Fi的位置以及其它的一些信息，尝试把每个Wi-Fi热点都和一个店铺关联起来，建立了Wi-Fi和店铺之间的映射关系库，为我们后续用定位日志数据来填充店铺指纹提供了良好的数据基础。
针对第二个问题，我们根据定位请求中扫描到的店铺内Wi-Fi热点的信号强度信息对定位日志进行清洗，保留下来那些信号强度较强的请求数据，从而尽可能保证每个用于店铺指纹填充的请求日志都是在对应的店铺内产生的。最后我们采用最近一个月的日志数据对店铺指纹进行填充，并且定期更新。通过这种方式，我们既保证了店铺指纹的自动化填充，同时也确保了店铺指纹的新鲜度——即使店铺发生变化或者迁移，我们的指纹数据也能够及时适应。
三、约束式定位
在填充了店铺指纹之后，我们还需要将店铺指纹用于我们的定位服务，填补人工采集的Wi-Fi指纹没有覆盖到的区域。然而，店铺Wi-Fi指纹和人工采集的走廊区域的Wi-Fi指纹存在很大的差异，导致二者无法直接融合。
首先，不同来源的指纹的新鲜度不同。店铺Wi-Fi指纹来自定位日志，能够每天自动更新，时刻保持最新鲜的状态。但是，人工采集指纹的周期一般都在一年左右。因此，走廊区域的指纹信息会随着时间逐渐老化，与实际请求时扫描到的Wi-Fi列表的匹配度会逐渐下降。这两种指纹信息同时用于位置计算时，会由于新鲜度差异导致指纹匹配度存在bias。
其次，不同获取方式得到的指纹可靠性不同。人工采集的Wi-Fi指纹具有十分明确的真实位置的标注，可信度较高；而自动填充的店铺Wi-Fi指纹，即使加入了数据清洗策略，也只能保证大部分指纹数据数据来源于店铺中，整体数据中存在一定比例的噪声数据。
图3. 基于网格Wi-Fi指纹的定位过程：选择最相似的几个网格计算最终位置
除此之外，人工采集的Wi-Fi指纹所代表的区域大小和店铺指纹所代表的区域大小也有很大的不同。人工采集Wi-Fi指纹时会将定位区域以网格的形式进行划分，每个网格具有相同的大小，然后采集每个网格的Wi-Fi指纹。在实际定位过程中，如图3所示，我们会选择一个或几个Wi-Fi指纹和采集到的Wi-Fi列表最相似的网格来确定目标位置。然而，店铺Wi-Fi指纹表述的是整个店铺的特征。一个店铺比一个网格一般要大很多，并且不同店铺的大小和形状也不相同。
受上述因素的影响，我们无法将人工采集的网格指纹和自动填充的店铺指纹直接对等地融合在一起提供位置服务。同时，考虑到店铺指纹的可靠性较低以及覆盖范围过大，店铺指纹如果最终参与到位置计算中有可能会造成较大偏移。因此，我们最终采取了基于排序的约束式定位。图4展示了我们目前版本约束式定位的整体流程。
图4. 基于店铺填充Wi-Fi指纹的约束式定位示意图
首先，我们建立了一个排序模型来判断目标发出请求的位置是在店铺内还是在有人工采集指纹覆盖的走廊内。我们根据人工采集的网格指纹和自动填充的店铺指纹中出现的Wi-Fi、每个Wi-Fi对应的信号强度等信息，对每个网格和店铺都提取出了一个41维的特征向量。基于特征向量，我们训练了一个XGBoost树模型作为我们的排序模型，来对店铺和网格进行排序，判断用户发出定位请求的实际区域。
图5. 将最终定位结果约束在店铺附近
然后，基于不同排序结果，我们采用了不同的定位策略。如果我们判断出目前发出请求的位置更可能是在人工采集过指纹的网格中，那么我们采用已有的定位流程，根据网格内的指纹特征，选择最相似的1个或几个网格来计算目标的位置。如果我们判断出目标发出定位请求的位置更可能是在某个店铺中，那么我们会找到店铺周围的那些网格，如图5所示，用这些网格来最终确定目标的位置，从而将定位结果约束在目标最可能存在店铺门口，以免产生过大的定位偏移。
最终，在上述策略下，对于因店铺指纹缺失导致定位结果偏离实际位置过远的情况，我们能够将50%的请求重新约束在正确范围内进行定位，大大减少了大偏移定位结果的数量。而对于原有系统能够正确定位的情况，我们最多也只会对其中2%的定位请求造成错误约束，不会对现有的定位性能和其它相关服务造成负面影响。
四、小结
随着定位服务质量的提升，越来越多的用户开始使用我们的室内定位服务，同时也对定位精度提出了更高的要求。然而，受系统搭建成本的限制，我们人工采集室内指纹无法真正覆盖室内的所有区域。店铺指纹的缺失已经成为限制室内定位服务质量进一步提升的关键。在本文中，我们利用了团队过去积累下来的定位数据的优势，在不增加成本的情况下，自动化地填充了一部分店铺指纹，并用于定位服务，提高了可定位区域的范围，大大提升了用户定位体验。未来，我们会不断优化用于指纹填充的数据质量，同时结合更多的数据来源，提高数据准确度的同时也为更多的店铺进行指纹填充，从而提供一个更加全面和精准的定位体验，也为更上层的应用服务提供一个可靠的基础位置信息服务。
目前室内图产品为腾讯位置服务特色付费产品，如感兴趣可点击了解，欢迎大家体验~
