基于802.11MC的室内定位及应用

背 景 介 绍

室内定位一直以来被广泛应用于多种应用场景，从日常生活的快捷导航到机器人的自动化操作都离不开室内定位的身影。目前市场上多种室内定位技术各有千秋，如图1所示，但也因为缺乏统一的技术标准，导致了室内定位平台孤岛现象严重，不利于产业生态的形成，更影响了室内定位行业的整体发展。

此外，室内定位领域痛点在于：

• 室内环境复杂，算法系统的精度易受多径效应的影响；
• 未知环境下定位困难，导致算法系统定位泛化能力差；
• 定位精度和成本难以兼顾。

低成本的定位系统精度往往无法达到商业要求，高精度的定位系统往往高度依赖于设备、基站或人力条件导致部署困难，无法实现大规模商业部署。而受限于各种室内定位技术的特点原理，现有的技术无法完全解决或只能部分解决本领域的痛点难题，造成定位系统“高精度”和“易部署”不可兼得的现象。

因此，如何研究设计一个低成本、高精度和易部署的室内定位系统，仍是目前摆在室内定位领域的业界难题和热点研究问题。

图1 基于定位精度和普及性的室内定位技术类型分类

随着IEEE 802.11-2016协议（也称为802.11MC）的精确时间测量（FTM）定位解决方案的引入，通过RTT往返时间来进行测距和定位的技术路线正在得到重视。目前提出的基于FTM的测距方案测距精度在视线环境下通常具有1-2m的偏移误差，但在802.11MC协议中，噪音不具备高斯性，精度的进一步提升存在着较大困难，进而导致定位精度无法达到米级。

本研究希望充分利用802.11MC协议的优越性，专注于使用低成本无线接入点（Access Point，AP）设备搭建室内定位系统，研究相关的算法尝试提高定位精度，在一定程度上完善并丰富国内无线网室内定位研究的理论基础，为基于FTM的无线网络室内定位技术研究提供参考和借鉴。该研究的意义除了可以推动室内定位技术的发展，助力智慧城市的建设，帮助各行各业提高运营效率减少监管成本，同时结合室内定位的室内设备行程信息，为疫情防控提供真实有效的信息支持。

---

本研究设计了一种新的单目标无线网络室内定位方案——基于极大似然估计与核密度估计的可扩展贝叶斯定位算法（Maximum Likelihood and Kernel Density Estimation - Extensible Bayesian Algorithm, MLKB），该方案的工作流程图如图2所示。

图2 MLKB系统工作流程图

MLKB 首先利用核密度估计法对 FTM 测距模块搜集的数据集进行预处理，输出各个 AP 到 STA 的测量距离，其次对室内 AP 测距结果小于 10m 的数据进行线性拟合，将纠正后的测距结果代入基于紧邻 AP 策略的线性最小二乘法，其输出作为定位算法的粗定位点输入，再设计基于极大似然估计的目标函数，赋予 AP 测距方差权重以根据测距结果的波动范围考察AP的“贡献”，最后由贝叶斯算法迭代优化目标函数得到最终的预测位置。

图3：MLKB系统框架结构

在如图3所示的系统框架结构中，测距数据预处理模块主要负责将前期的测距数据进行筛选和过滤，并基于KDE核密度估计方案选出AP到STA的某时刻的最佳测量距离，对测量距离进行线性拟合的原因是修正距离过近时AP产生的原生误差，在粗定位优化模块，我们设计了基于极大似然估计的目标函数，赋予AP测距方差权重以根据测距结果的波动范围考察AP的“贡献”，让算法优先选择测距质量高的AP，一定程度上减少了室内多径效应对测距结果带来的影响，最后由贝叶斯算法迭代优化目标函数得到最终的预测位置。

---

为了评估算法在不同室内环境下的定位性能和泛化能力，本研究分别在室内LOS，室内弱NLOS环境和室内强NLOS环境下搜集定位数据集，这三类环境可充分代表室内的大部分障碍物对信号干扰强度的场景类别，LOS环境定位数据搜集场景与室内平面图见图4，弱NLOS环境定位数据搜集场景与室内平面图见图5，强NLOS环境定位数据搜集场景与室内平面图见图6。其中对弱NLOS定义是在STA和AP之间的视线存在单一类型的障碍物阻挡（图5场景下指乒乓球桌）；对强NLOS定义是在STA和AP之间的视线存在复杂类型障碍物阻挡（图6场景下指办公桌，电脑、打印机等其他电子设备，移动的人等）。

图4 室内 LOS 环境定位数据搜集场景

图5 室内弱 NLOS 环境定位数据搜集场景

在算法定位精度比较上，我们在室内LOS环境下搜集了11个采样点，采样点呈均匀分散分布，室内LOS环境的房间长15.6m，宽8.4m，高2.8m左右，除天花板和地板外可能产生多径效应外无其余障碍物遮挡，因此可以将主要精力放在算法各模块的定位精度验证提高上。结合FTM的测距原理和特点，本研究认为FTM定位普遍适用于如图5的室内弱NLOS环境，因此我们在相同结构但存在障碍物阻挡的室内弱NLOS环境下收集70个采样点，采样点呈均匀密集分布，以充分验证不同算法的定位效果。最后在室内强NLOS环境下收集12个采样点，采样点呈随机分散分布，以进一步验证算法在不同房间和障碍环境下的定位泛化能力。为充分保证测距结果的数据分布特征完整，本研究在每处采样点收集了100组定位数据，每组定位数据包括各个AP到STA的测量距离信息，实验验证收集100条测距数据的平均消耗时间是4-5秒。

图6 室内强 NLOS 环境定位数据搜集场景

首先我们验证各算法在室内LOS环境下（图4）的定位效果，除MLKB算法外，其余算法均结合去除离群点后的FTM平均测量距离以及最小误差平方和函数得到室内定位结果。最后得到不同算法在室内定位误差的累积分布函数如图7所示，具体定位精度指标对比如表 1所示。

图7 室内 LOS 环境下算法定位精度对比

表1 LOS 环境下各算法定位精度对比

由图表分析可得，在LOS环境且未对测量数据和算法做任何改进的情况下，除MLKB算法有接近62%的数据集达到了米级精度，其余所有算法仅有19%的数据集达到了米级精度的定位；从平均误差指标上看，算法精度效果从高到低分别为MLKB算法、贝叶斯优化算法，其次模拟退火算法和牛顿迭代法，最后是线性最小二乘法。其中贝叶斯算法，模拟退火算法和牛顿迭代法的定位效果非常接近，90%的数据达到了2米的定位精度；线性最小二乘法仅有接近57%的数据达到了2米的定位精度。再从1100条定位数据分析得到，MLKB算法最大误差属所有算法中最小，达到1.8853m，朴素贝叶斯优化最大误差略差于模拟退火算法和牛顿迭代法，最大误差可达到3.4-3.6米，而线性最小二乘法的最大定位误差则在7米之外。

接下来，为了充分验证MLKB算法在室内弱NLOS环境下（图5）的定位效果，得到在室内70个采样点下不同算法定位误差的累积分布函数如图8所示，具体定位精度指标对比如表2所示。

图8 室内弱 NLOS 环境下算法定位精度对比

表2 室内弱 NLOS 环境下各算法定位精度对比

可以发现在室内定位的弱NLOS场景下，平均定位误差相对最低的算法是MLKB算法，其次是牛顿迭代法、模拟退火算法、贝叶斯算法和线性最小二乘法。在采样点数量较多的情况下，有必要验证算法对于大部分数据的定位精度和定位稳定性，对于90%的采样点数据集，MLKB算法的定位精度能够达到2.3m以内，其余的算法精度均在3m以上。而最大误差除了线性最小二乘法达到了8m，其余算法均在5m左右并且差距较小。在米级精度的定位效果中，牛顿迭代法数据占比最高，MLKB算法没有比较明显的优势，但从定位误差标准差来看，仅MLKB算法波动最小，其余算法均超过了1m。

因此可以进一步得到的结论是，当室内环境存在着一部分干扰信号的障碍物时（如图5中的乒乓球桌和铁质支架），所有算法的定位精度都会下降，但MLKB算法的平均精度依然是所有算法中最高的，在本例中，MLKB算法和牛顿迭代法发挥了比较出色的定位效果，二者的平均误差均在1.5米以内，虽然牛顿迭代法米级精度较高，但其余指标均没有体现出优势，因此在大样本集下从平均定位精度和稳定性等方面综合考量，MLKB算法会更胜一筹。此外MLKB算法的总体数据误差控制在了两米的精度范围内，因此在室内弱障碍环境（如停车场）或者定位精度要求不太高的应用场景下可以适用。

随后我们在图6的环境下搜集的室内强NLOS环境采样点数据集，进一步验证优化后的算法在不同的室内场景下的定位泛化效果，得到不同算法在室内定位误差的累积分布函数如图9所示，具体定位精度指标对比如表3所示。

图9 室内强 NLOS 环境下算法定位精度对比

表3 室内强 NLOS 环境下各算法定位精度对比

可以发现在室内定位的复杂真实场景下，平均定位误差相对最低的算法是贝叶斯算法，其次是MLKB算法、牛顿迭代法、模拟退火算法和线性最小二乘法。虽然MLKB算法平均误差略高于朴素贝叶斯算法，但其米级精度数据占比可以达到41%，相比原始贝叶斯算法米级精度提升17%，并且最大误差进一步减小。同时在进行多次实验后发现贝叶斯算法的定位结果也是四个算法中波动最大的，最好时最大定位误差在3.8m以内，最差时可达到12m。牛顿迭代法的运行结果相对稳定，模拟退火算法在NLOS环境下米级定位效果和牛顿迭代法类似，不及线性最小二乘法。

最后我们汇总了上述三种室内场景的实验结果，总结算法在室内环境下的综合评估结果见表4。本研究的目标是尽可能提升算法在室内环境下的定位精度，因此我们提取出不同室内环境下的平均误差和米级精度占比作为算法的重要定位精度指标，同时列出了三种场景下的总平均误差和总平均米级定位精度占比，以更加全面的评估算法的定位效果。最后我们统计了在不同场景下，各算法的平均误差和米级精度占比排名，显然平均误差越小，排名越高；米级精度占比越大，排名越高。按照排名次序分别换算成分数，如第一名5分，第二名4分，第三名3分，第四名2分和第五名1分的规则进行换算，得到最后的分数总计结果，以更加直观判断算法的定位精度优势差异。

表4 各算法重要定位精度指标综合排名对比

---

为解决第三个痛点，本研究重点讨论了基于802.11MC协议下的AP端和STA端的部署策略，通过控制成本的方式选择市场流通的高性价比AP和STA设备，将部署策略应用到基于客户端/服务端双层架构的室内定位导航系统中，在安卓端通过了真实室内场景下的定位导航部署测试，在网页端实现了设备定位数据统计分析，室内行程追溯等功能，一定程度上说明了基于802.11MC协议的室内定位系统可部署性和可应用性。

针对市场上哪些AP支持802.11MC协议的AP，我们通过网络调研和主动测量的方案，发现了目前市场上至少有12款AP支持802.11mc的FTM测距响应，部分oppo reno手机在打开热点时可支持FTM响应，从AP覆盖度而言，目前清华大学部分建筑已部署支持802.11MC协议的AP，北京大兴国际机场已全面覆盖支持802.11MC协议的AP，AP厂商多为华为公司和新华三公司。虽然目前市场上大部分AP还并不支持802.11MC协议，但可以从调研结果中发现，随着802.11mc协议逐渐走入大众视野，精确时间测量技术将在AP厂商的支持下越来越普及，未来支持FTM测量的AP设备将会逐渐被投入市场大量部署。

表5 支持 FTM 的 AP 路由器市场价格对比

在综合评估AP的市场价（表5）和原生offset（图10）后，我们选择了价格在270元左右且原始offset较小的华硕ACRH17路由器作为实验路由器，在支持FTM的48款手机终端中选择了价格在2000元的小米手机 Redmi Note9 pro作为应用开发机，注意终端价格通常不计入室内定位系统的搭建成本中，因此我们在使用3台AP的情况下，实验搭建的室内定位系统成本仅需要800元左右。

图10 不同类型的 AP 在不同频段下的 FTM 测距偏移

接下来是室内导航应用场景演示，我们启动WifiRttScanT APP，进行真实场景下的室内导航测试，测试过程快照如图11（左）所示。首先用户点击“开始导航”按钮，软件将自动选择用户设备的实时定位坐标为起点，用户在APP上点击一处位置作为本次导航目的地（终点），若误选可以继续点击地图上其他位置更新目的地，直到用户确认目的地无误后，点击“确认导航”按钮，软件进入导航页面，用户跟随导航路径前进，过程中伴随语音和界面文字提示，用于告知用户当前设备定位点所在的后续路段描述信息，同时会周期性刷新设备定位点周围的AP信息，若用户偏离导航路径（当路线偏移距离超过阈值时），软件将重新自动规划新的合法路径，直到用户到达目的地，本次导航结束。

在网页端用户设备的室内行程追溯功能的主要展示页面如图11（右）所示，只要登录管理员账户就可以查询普通用户的设备定位信息，当用户登录后即进入网站主页，可以查看注册用户数，建筑覆盖数，部署AP数，上线时间，建筑设备流统计监测等信息，假设需要查询某一用户在某天内经过了哪些建筑或者建筑内行程轨迹，只需要按照步骤进入“用户室内轨迹追溯”模态框页面，选择某一普通用户，选择该用户的特定设备，选择该设备的定位活跃日期和该日期下经过的特定建筑，即可筛选出用户的室内行程轨迹。因此我们对客户端和服务端系统进行了部署联调演示，一定程度上证明了基于 802.11MC 协议的 Wi-Fi 室内定位的可部署性和可应用性。

图11 室内定位导航（图左）与室内行程追溯（图右）应用场景演示

---

总 结 与 展 望

为解决室内定位领域的痛点，本研究考虑到无线局域网在室内已得到广泛部署的先天优势，期望在无线网络技术领域中结合802.11MC协议的精确时间测量技术原理来进一步提升精度并降低成本。研究提出了一套单目标网络定位解决方案MLKB，该方案对AP的测距数据进行了采集并对FTM测量米级精度效果进行了验证，结果表明在室内LOS环境下，测量距离的偏移误差有接近50%的数据结果在米级精度以内。将最终的测距结果数据集进行核密度估计优化以及线性拟合纠正，其效果优于去除离群点后的平均或中值测量距离，数据优势占比73.5%。并且基于加权最小二乘法思想设计了基于极大似然估计的目标函数，用于筛选周围测距质量较高的AP，并对定位算法正式迭代前的目标函数、初始点选择、迭代范围与次数等选取进行了研究与优化，一定程度上减少了室内多径效应的影响。

随着的802.11mc协议的普及，本研究提出的MLKB算法将可以在具有FTM测量功能的AP设备的室内定位系统中广泛运用。在现有研究的基础上，未来还可以继续开展的研究工作主要包括：1）优化筛选高质量AP的评估函数，提高不同环境下的筛选泛化能力；2）优化MLKB算法的线性拟合函数，降低由于AP型号不同导致的原始测距误差偏移对定位精度的影响；3）进一步提升用户体验，实现室内定位点的平滑移动，通过高并发环境下的系统定位测试；4）若需要尽可能满足实时性，未来可通过多线程或是降低测量次数的办法提升时间上的性能，将算法实时性问题进一步优化提升，以扩大需求应用场景。相信在不远的未来，当市场上绝大多数AP都支持802.11MC协议时，基于精确时间测量技术的WI-FI室内定位一定会在众多室内定位技术中脱颖而出并大放异彩，推动基于位置的服务不断向前发展。

---

【参考文献】

[1] 唐翔宇, 张千里等. 基于精确时间测量的无线网络室内定位系统研究 [J]. 计算机学报, 2022(3).

[2] Horn B. Doubling the accuracy of indoor location: Frequency diversity[M]. Preprints, 2020

[3] 中国移动通信有限公司研究院. 室内定位生态发展白皮书[EB/OL]. 2020. https://131152

99.s21i.faiusr.com/61/1/ABUIABA9GAAgltKCjgYoutiahwQ.pdf.

[4] 钱志鸿, 孙大洋, LENG V. 无线网络定位综述[J]. 计算机学报, 2016, 39(6): 1237-1256.

---

END

精彩推荐

互联网中的自治域飞地

2022全球互联网路由前缀疑似劫持事件分析

钓鱼网站特征分析

原文始发于微信公众号（风眼实验室）：基于802.11MC的室内定位及应用