写点什么

高德网络定位之“移动 WiFi 识别”

  • 2020-03-04
  • 本文字数:3353 字

    阅读完需:约 11 分钟

高德网络定位之“移动WiFi识别”

1. 导读

随着时代的发展,近 10 年来位置产业蓬勃发展,定位能力逐渐从低精度走向高精度,从部分场景走向泛在定位。设备和场景的丰富,使得定位技术和能力也不断的优化更新。定位能力包括 GNSS、DR(航迹推算)、MM(地图匹配)、视觉定位和网络定位等。


其中网络定位是通过客户端扫描到的 WiFi 和基站信息来进行定位的一种定位方式。网络定位能力是 GNSS 定位的有力补充,在 GNSS 无法定位或者定位较慢的时候,网络定位都可以快速给出位置。网络定位能力也是高德能够深植于各类手机厂商(提供系统级网络定位能力)和 APP(出行、社交、O2O、P2P、旅游、新闻、天气等诸多领域)的原因之一。


要做到通过 WiFi 和基站来定位,我们需要通过亿级数据来挖掘出 WiFi 和基站的类型、位置、指纹等各种信息。这些信息的挖掘,历史上是通过一系列的人工经验策略来进行的,人工规则的历史局限带来了所挖掘信息较低的准召率,为了进一步提升高德网络定位能力,我们需要卸下以往的包袱,从方法上进行改变。

2. 如何定义“网络定位”

网络定位分为离线训练和在线定位两个过程:


  • 离线训练:是在用户有 GPS 位置时采集周边的 WiFi 和基站(以下统称为 AP)信息,通过对采集数据进行聚类和关联,得到两类数据产品:AP 库和指纹库;

  • 在线定位:与离线训练的过程正好相反,当用户没有 GPS 定位时,可以通过扫描到的周边 WiFi 和基站信号,结合离线训练出的 AP 库和指纹库来进行实时定位。


AP 库和指纹库这两类数据产品中:


  • 指纹库:以物理坐标位置对应的特征指纹信息为内容,这些特征指纹信息可以包括扫描到的 WiFi 或者基站的信号强度分布,采集点频次等统计信息,也可以是通过神经网络提取出的特征信息。

  • AP 库:以 WiFi 的 mac 地址或者基站的 ID(gsm 基站为 mcc_mnc_lac_cid,cdma 基站为 mcc_sid _bsid_nid )为主键,以 WiFi 或者基站的物理坐标信息(经纬度或者地理栅格坐标信息)为内容。


典型的 AP 库数据只包含挖掘出的物理坐标信息和覆盖半径,这种“点圆模型”是对 AP 发射信号的一种理想化,没有考虑任何实际场景中的信号遮挡、反射等情况,所以 AP 库大多用来进行粗略定位。而指纹库直接与位置相关,可以刻画比“点圆模型”更细致的分布信息,所以指纹库可以用来进行精细定位。



高德的指纹库主要包括特有的室内指纹和全场景指纹信息两种。

3. “网络定位”的问题

网络定位的基本思路类似聚类,假设用户手机扫描到的 AP 列表中的 AP 的位置均比较固定,则我们可以以这些 AP 位置为锚点,来确定用户位置。现实世界中,锚点(即 AP 库中的 AP)的位置通过大数据来进行挖掘,并不一定完全准确,甚至出现严重错误。


针对 WiFi 而言,移动 WiFi、克隆 WiFi、搬家 WiFi 等都可能造成 AP 位置的错误。移动 WiFi 包含手机热点,4g 移动路由器,公交车/地铁/高铁上的 WiFi 热点等,这些 WiFi 的移动属性较强,位置频繁变化,如下图所示。



如果以移动 WiFi 作为锚点,因为这些锚点的位置不固定,极可能会导致用户的定位出现极大误差。克隆 WiFi 指不同的 WiFi 设备使用了同一个 mac 地址,国内的腾达和斐讯等路由器厂商制造了大量这样的 WiFi 设备(例如大部分 mac 前缀为“c8:3a:35”的即为腾达的克隆 WiFi),克隆 WiFi 导致 AP 库中同一个 mac 地址对应的锚点位置有多个。搬家 WiFi 指某些因为搬家而发生位置变化的 WiFi,数据挖掘存在一定的滞后性,搬家后 AP 库中的位置未及时更新,也会造成定位错误。


因为大误差的 badcase 严重损害用户体验,我们必须要将这些非固定 WiFi 的属性在 AP 库中标记出来。


历史上,高德是通过一系列简单的人工规则对这些 WiFi 的属性进行分类的。例如,通过采集点覆盖范围较大来判定移动 WiFi,通过 mac 前缀来判定克隆 WiFi 等。人工规则的缺点是准召率不高,训练分类模型就成了一个自然的选择。


鉴于 badcase 中最严重的问题是移动 WiFi 的准召率不高,下面我们就尝试使用监督学习的方法来进行“移动 WiFi 识别”。

4. 如何实现“移动 Wifi 识别”

4.1 样本提取

AP 库中的 WiFi 数量十分庞大,如果我们在 AP 库中随机抽取样本进行人工标注,那大部分标注的结果可能是人工规则判定正确的样本,为了尽可能低成本获取有效的标注样本,我们借鉴主动学习的思路,不断抽取模糊样本进行标注,快速迭代使得模型稳定。


我们根据人工规则的判定结果提取了一批确定性较高的样本,使用人工强特征训练第一版模型,之后将第一版模型的预测结果与线上人工规则的结果进行全量比较,提取出模糊样本进行人工标注。在标注样本的过程中发现问题,持续特征工程,不断迭代模型。


这里模糊样本的定义包含三种:预测结果与上一版模型的结果不同,预测概率值在 0.5 附近,预测结果在不同训练周期内存在波动(例如昨天识别是移动 WiFi,今天识别是非移动)。

4.2 特征提取

4.2.1 移动 WiFi vs 克隆/搬家 WiFi

第一版模型中,我们使用了一些采集聚集程度相关的特征。


名称描述
ratioX聚簇寻找中心点,中心点向外X米圆形范围内的定位点占总定位数的比例
areaSqare定位点覆盖的矩形围栏范围的面积


模型迭代过程中,我们遇到的第一个问题是移动 WiFi 与克隆 WiFi 或搬家 WiFi 比较容易混淆。下面几幅图分别画出了固定 WiFi、移动 WiFi、克隆 WiFi、搬家 WiFi 的定位点散布的实例。




可以看到,如果仅仅使用定位点的聚集程度来分类,那克隆 WiFi 和搬家 WiFi 的定位点也比较分散,极易与移动 WiFi 混淆。所以我们先使用聚簇算法,将采集点局部聚集的点集合成不同的簇,在每个簇中计算定位点的散布程度,再将所有簇的散布程度求平均值等,获取平均意义上的聚集程度。

4.2.2 多维度提取特征

为了进一步提升分类的准召率,我们不仅从定位点的聚集维度来提取特征,还增加了信号强度、关联特征、IP 特征、时间特征等,以下进行简要介绍:


  • 信号强度信息:(和上节中的聚集特征一起,统称为采集特征)移动设备与非移动设备采集点的信号强度在去除设备差异性之后,分布存在差异性。

  • 关联特征:关联信息是指当设备扫描到的一次 WiFi 列表中,列表中所有 WiFi 两两之间就算产生了一次关联(或称邻居)关系,统计 WiFi 周边关联的 WiFi 和基站信息,可以描述出 WiFi 的移动属性。

  • IP 特征:固网 IP 和移动网的 IP 存在一定隔离,移动 WiFi 设备的上游一般是通过基站连接的移动网,固定 WiFi 设备的上游一般是通过 ADSL 等连接的固网。

  • 时间特征:固定 WiFi 一般是长时间连接电源的,而移动 WiFi 一般是临时在某些地方和时间短暂出现的。

4.2.3 聚合特征

在 AP 库中,存在一部分 WiFi 定位信息不够充分,即使是人工标注也存在着非常大的不确定性,这些定位信息不够充分的 WiFi,我们称之为“弱信息 WiFi”。


对于这类 WiFi,我们只有通过 ssid 和 mac 前缀来进行辅助判断。因为 ssid 中包含了一些诸如“iPhone”、“个人热点”、“oppo”、“shouqiyueche”(首汽约车)、“往返免费”、“tp-link”等能够表明设备属性的信息。另一方面,mac 前缀(mac 信息的前半部分)代表了厂商信息。基于这些辅助信息,我们可以在其他信息不够充分的情况下辅助推测 WiFi 的类别属性。


我们将基础特征(采集特征、关联特征、IP 特征、时间特征)中较为重要的 TOP_N 维特征按照 ssid 和 mac 前缀进行聚合,聚合函数为中位数(median)和总体标准差(stddev)。这样,聚合特征体现了一类 WiFi 共有的特征,针对弱信息 WiFi,我们就可以通过集体的特征来推测出个体的属性。


5. 应用场景

除了提升网络定位能力,移动 WiFi 的识别还有更多用武之地,例如手机热点的识别,室内外的判断,建筑物和 POI 级别的定位等等。其中一个例子就是判断当前设备所连接的 WiFi 是否为移动热点(如 4g 路由器,手机热点等),在视频类的 APP 中,可以通过判别当前用户连接的 WiFi 是否为移动热点,从而控制是否进行视频的自动播放或缓存,给予用户提示性信息。

6. 小结

最终我们使用随机森林来训练分类模型,经过特征选择和模型参数调整之后,最终得到的模型,移动 WiFi 的准召率均优于 99.8%。高德网络定位的精度也因此得到了较大提升,尾部大误差 badcase 降低了 18%左右。


网络定位作为一种低功耗的定位手段,不仅在 GNSS 无法触达的地区(例如地铁、室内等场景)为普通用户带来辅助的定位信息,而且在某些急救和寻人的场景中发挥了重要的作用。未来,随着 5G 通信技术的开展,将迎来更加精准的网络定位能力。


2020-03-04 14:482095

评论

发布
暂无评论
发现更多内容

6月优质更文活动结果已出炉,快来看看有没有你

InfoQ写作社区官方

热门活动 6 月 优质更文活动

如何使用 Flink SQL 探索 GitHub 数据集|Flink-Learning 实战营

Apache Flink

大数据 flink 实时计算

零样本视频生成无压力,基于飞桨框架实现Text2Video-Zero核心代码及依赖库

飞桨PaddlePaddle

人工智能 百度 paddle 飞桨 百度飞桨

看这个视频,4万人学会云上部署 Stable Diffusion

Serverless Devs

云计算 Serverless 函数计算FC

如何用极狐GitLab 为 iOS App 创建自动化CI/CD?详细教程来了

极狐GitLab

ios DevOps gitlab 自动化 CI/CD

表格检测识别技术面临的挑战和发展趋势

合合技术团队

人工智能 表格识别 表格检测

边缘云特点、应用实践和发展趋势浅析

天翼云开发者社区

边缘云

【TiDB v7.1.0】资源管控调研及评测

TiDB 社区干货传送门

7.x 实践

Gartner®DevOps 平台魔力象限出炉,GitLab 获评「领导者」!

极狐GitLab

gitlab 安全 开放平台 开源贡献者 领导者象限

MySQL中字符串查询效率大比拼

不在线第一只蜗牛

数据库 sql

LED租赁屏市场

Dylan

活动 广告 方案 设备 LED显示屏

关于 3.0 和 2.0 的数据文件差异以及性能优化思路

爱倒腾的程序员

TICDC 数据同步至 MySQL初体验

TiDB 社区干货传送门

迁移

Flink CDC 2.4 正式发布,新增 Vitess 数据源,PostgreSQL 和 SQL Server CDC 连接器支持增量快照,升级 Debezium 版本

Apache Flink

flink

南通市属于几线城市?本地有正规等保测评机构吗?

行云管家

等级保护 等保测评 南通

linux自动化运维工具用哪款好?理由是什么?

行云管家

Linux IT运维 自动化运维

程序员搞开发的时候,心态真的不稳

伤感汤姆布利柏

WEB系统安全之开源软件风险使用评估

天翼云开发者社区

开源 Web

TIDB v7.1 reource control资源管控特性体验贴

TiDB 社区干货传送门

版本测评 7.x 实践

基于群组实现从 Azure AD 到极狐GitLab 的单点登录

极狐GitLab

统一身份认证 IdP 单点登录 用户同步 配置群组同步

实现淘宝母婴订单实时查询和可视化|Flink-Learning实战营

Apache Flink

大数据 flink

数字先锋|云上医院长什么样?宁夏固原中医医院带你一探究竟!

天翼云开发者社区

云计算

从零开始初识机器学习 | 京东云技术团队

京东科技开发者

人工智能 机器学习 企业号 6 月 PK 榜

微服务之道:8个原则,打造高效的微服务体系

不在线第一只蜗牛

微服务 微服务架构

火山引擎A/B测试推出智能流量调优实验,助力汽车行业破局营销困境

字节跳动数据平台

你说搞开发的很累,那做什么工作不累?

树上有只程序猿

证书管理:从手工到平台化

vivo互联网技术

运维自动化 运维开发 证书管理

高考成绩都出来了,你的秒杀系统如何了?

冰河

并发编程 多线程 高并发 协程 秒杀系统

记一次Native memory leak排查过程 | 京东云技术团队

京东科技开发者

native 企业号 6 月 PK 榜 memory leak

高德网络定位之“移动WiFi识别”_文化 & 方法_高德技术_InfoQ精选文章