导语:本篇文章分享了腾讯定位团队5年来在室内定位领域的探索和解决方案，讨论了学界和工业界基于Wi-Fi的室内定位技术研究差异。室内定位研究走过十几年研究历程，还未产生被业界普遍接受的实用系统。本文亦希望带来各界对室内定位技术的重新思考，希望更多业界团队进入这个领域，让室内定位在不久的将来像室外GPS一样服务公众！
近日，第28届MobiCom公布了论文接收名单，其中腾讯定位团队论文《Experience: Pushing Indoor Localization from Laboratory to the Wild》成功入选，并且荣获Mobicom组委会“BEST COMMUNITY PAPER AWARD RUNNER-UP奖项”，该奖项主要对工作实际效果和社会影响力贡献角度进行评选，每年仅有3篇论文入选。这是腾讯以第一单位首次于该会议发表论文，这项工作是与中科院软件所团队、美国麻省大学团队合作开展的。
论文分享了腾讯定位团队5年来在大规模室内定位上的探索和经验，该系统已经在国内超过30个城市，1500家商场部署。论文主要描述了腾讯基于Wi-Fi的室内定位的实践经验。第一，大规模室内定位无需人工参与收集指纹。人工收集指纹是之前基于指纹的室内定位系统无法从实验室走向大规模部署的一个关键原因。第二，巧妙利用室内Wi-Fi名和室内物理地点的关联性来获取部分Wi-Fi AP的位置信息，这些无需人工收集的信息被有效利用来初始化定位系统。第三，在大规模的实际部署中发现了一些有趣的问题并提出了新颖的解决方案，例如：很多商场具有中空结构，室内外的边界判断等。希望这些真实环境中遇到的实际问题对其它室内定位系统的部署具有非常强的借鉴意义。
MobiCom（Annual International Conference on Mobile Computing and Networking）是ACM SIGMobile旗下无线网络和移动计算系统领域最负盛名的世界顶级学术会议，也是中国计算机学会推荐的A类国际会议跟清华计算机学科群推荐的A类会议，在所有的计算机国际会议排名中都被列在最高等级。会议每年接受两轮投稿，本次会议共有314篇投稿，其中56篇文章被接收，录取率仅为17.8%。组委会设立的BEST COMMUNITY PAPER AWARD仅有3篇文章入选，比例仅为0.95%。
背景知识
大家日常生活中经常听到GPS和北斗定位，可能会认为定位就是由卫星系统来提供的。但实际生活中由于室内环境/建筑物遮挡无法收到卫星信号，GPS定位无法在室内使用。正因为此，室内定位一直是学术界跟工业界共同的难题！
图1
图2
论文解读
论文题目：Experience: Pushing Indoor Localization from Laboratory to the Wild
论文作者：Jiazhi Ni, Fusang Zhang, Jie Xiong , Qiang Huang, Zhaoxin Chang , Junqi Ma , BinBin Xie, Pengsen Wang , Guangyu Bian , Xin Li , Chang Liu
主要内容：定位技术已经成为我们日常生活中不可或缺的一部分，比如基于GPS的定位服务被广泛用于车辆导航和追踪。尽管在过去二十年中学术界和工业界都做出了巨大的努力，仍然没有一种定位系统能在室内被广泛使用。经过系统性的深入研究，我们发现要实现可扩展的大规模室内定位，最可行的方法是利用现有基础设施，这使得Wi-Fi在跟其他的无线定位技术包括红外、蓝牙、RFID、ZigBee等的竞争中脱颖而出，成为室内定位最有前景的选择。在这篇文章中，我们利用超过400万第三方部署的WiFi AP，通过WiFi信号的共现特征和SSID名称特征进行大规模WiFi AP位置发现。构建城市规模的 WiFi 信号库，融合海量人流定位请求特征、信号分布特征等，对终端用户提供位置服务。系统部署于腾讯地图定位中心覆盖全国 35 个城市，在垂直行业包括京东配送、 美团外卖、滴滴打车、快手等位置服务需求应用中提供了 WiFi 网络定位服务，日均定位请求超过 1600 亿次。
1.Wi-Fi 定位方法的选择
自Wi-Fi从1998年诞生以来，Wi-Fi定位在学术界一直是研究热点，时至今日，大量基于Wi-Fi的室内定位系统可以被分为三类：基于指纹的定位，基于AoA的定位，以及基于ToF的定位。指纹定位由于收集指纹需要耗费大量的人力，一直没有得到大规模的部署跟使用。最近几年学术界对定位的研究聚焦在AoA定位和ToF定位上，但是我们发现在广泛部署的Wi-Fi AP上，能拿到获取信号AoA和ToF的信息的AP数量是极少的。所以要让Wi-Fi定位被大规模广泛部署使用，指纹定位是唯一的可行选择，当然前提是要解决人工收集指纹耗费大量人力这个困扰学术界跟工业界多年的问题。
2. WiFi AP位置估计
在定位系统的初始化阶段，我们设计对大量的第三方Wi-Fi AP 进行粗定位。首先采用基于机器学习的Wi-Fi名和物理位置匹配的方法获得部分AP的位置，这个匹配方法基于一个有趣的现象，即许多兴趣点（POI），如商店、餐馆和咖啡店，都部署了自己的Wi-Fi AP，并且AP的名字与商店相关（比如商场中的Starbucks用SB_Wi-Fi命名他们的AP）。因此，系统可以在建筑平面图的帮助下用AP名推断AP的物理位置。用此方法在获取到部分AP的物理位置后，我们提出了一个全新的基于大数据的方法去获取大量其它AP的物理位置。该方法利用终端用户的手机给系统提供的大量AP list 来获取AP与AP之间物理位置接近的信息。通过大量的物理位置接近信息，我们设计公式量化AP之间的距离，从而用已知AP的位置来获取另外一部分AP的位置。此方法在实际应用中兼具低开销和高性能。
3.Wi-Fi指纹收集
指纹收集需要耗费大量人力一直是阻碍基于指纹的定位系统被大规模部署的根本原因。我们提出一种无需任何人工参与的指纹数据库构建方法。由于此方法系统不需要人工去采集位置信息，这个方法的核心就在于如何把我们通过终端用户收集到的信号强度跟准确的物理位置信息联系起来。如图3 所示，该方法由两个模块组成：初始化模块和基于用户反馈的更新模块。其中初始化模块主要是将物理位置和对应指纹进行关联，指纹的物理位置信息是利用终端用户报告的Wi-Fi AP的位置和AP的信号强度(RSSI)进行加权计算，作为指纹的初始位置信息；指纹更新模块是基于大量用户的反馈评分来进行指纹迭代。需要指出的是，在系统中，我们不仅把传统的Wi-Fi信号强度作为指纹，也引入了海量用户请求数量作为指纹，因为在不同物理位置的用户定位请求的数量也会截然不同。
图3
4.基于排序模型的指纹定位
传统的基于指纹的室内定位系统依赖于信号强度（RSSI），其基本原理是每一个位置能够收到的多个Wi-Fi AP 的信号强度信息，多个AP的RSSI组合是具有高度特异性的。系统在数据库中寻找与观测到的RSSI组合相似度最高的物理位置作为定位结果。系统采用了多特征的排序学习模型，特种中包括了传统RSSI信号特征以及用户定位请求的统计量，我们方法的处理流程如图4所示。
图4
5.真实大规模场景下的定位挑战
在过去的几年中，我们遇到了许多真实大规模场景中面临的极具挑战性的问题，这里分享两个我们的解决办法与思考。
a. 室内外边界判断
室内室外边界检测是精确定位的关键。当用户进入购物中心后，如果仍然使用GPS进行定位，则会出现较大的定位误差。已有的工作大部分使用光传感器和气压计来进行区分室内室外，但适用场景有限，容易受到环境温度等因素影响。我们提出了一种基于GPS和Wi-Fi信号强度分布进行室内/室外检测的方法，其基本原理是Wi-Fi信号的强度分布在室内跟室外的时候会有很大差异，室内明显大于室外，同样GPS信号的强度分布是室外大于室内。基于该性质，系统可以对室内室外边界进行高精确的判断（准确度高于99%）。
图5
b. 中空区域定位
另一个在定位过程中遇到的挑战是很多商场的中空区域，如图6所示，这个中空的结构会导致楼层识别错误。大部分用户对楼层定位错误的容忍度远低于对定位误差的容忍度。针对此问题，我们提出了一个新颖的解决办法，如图7所示，当没有中空区域时，WiFi AP的信号强度会呈现一个高斯分布，但是在中空区域附近的AP信号强度分布呈现两个高斯分布的叠加，具有两个峰值。利用这个性质可以有效的探测中空区域的存在，然后进一步解决中空区域附近的楼层定位不准问题。
图6
图7
5.大规模系统验证
我们选择了购物中心、办公楼和医院三类大规模真实室内场景评估了系统性能。其中商场的平均定位精度在5.1m左右，办公楼在6.82m左右，医院在7m左右。图8展示了选取的购物中心一楼的平面图及发现的大量第三方WiFi AP位置。我们也对比了系统在不同商场、不同品牌的手机上的表现（见图9、10），更多的实验细节参见我们的论文。值得一提的是，我们完全不需要人工收集指纹的定位系统和苹果系统利用人工收集指纹的定位系统的定位精度类似，充分说明了我们系统的有效性。
图8
左图9 右图10
总结
本篇论文总体介绍了利用WiFi信号进行大规模室内定位的方法，向学术界和工业界第一次展示了腾讯在WiFi大规模室内定位商用的实践经验，希望这项工作可以帮助研究者重新思考室内定位技术，推动现实中室内定位系统的部署与普及。
小福利
腾讯地图平台部-定位技术中心，目前推出网络RTK服务了，现在正在免费公测中，点此申领一个免费公测账号~
↓↓↓ 点击“阅读原文”，查看本次获奖论文详细内容
