在 7 月 27 日由 @百度主办、 @InfoQ 负责策划组织和实施的第 40 期百度技术沙龙活动上,百度资深软件工程师、现担任百度定位服务的技术负责人张传明和陌陌科技联合创始人兼 CTO 李志威分享了各自在定位技术方面的经验,话题涉及“构建高可用性的无线定位服务”和“陌陌手机定位技术实践”等。本文将对他们各自的分享做下简单的回顾,同时提供相关资料的下载。
主题一:构建高可用性的无线定位服务 (下载讲稿)
百度资深软件工程师、现担任百度定位服务的技术负责人张传明从“为什么需要移动定位”、“定位原理简介”、“从原理到实现”以及“现状与展望”等角度展开。首先他谈到了移动定位的三个理由:
- 使用户知道自己身在何处
- 使搜索结果更加智能
- 位置敏感信息的基础
目前的主流的定位方式有 GPS 定位、网络定位,GPS 定位精度高、精准连续定位、无服务端,但是室内不可用、耗电且初次定位慢。由于基站、WIFI 都具有全球唯一的标识,所以也能够用作定位的作用。在真正的使用中,需要根据应用场景,选用定位方法。
在百度开放的定位服务中,混合使用了不同的定位方式,对于 GPS 定位,用户可以在手机上直接调用相关的 API 即可得到 GPS 坐标和误差半径,在软件层面上通过如下的方式做优化:
- 加速可能成功的搜星
- 不做必然失败的搜星
- 预测过大误差的 GPS 结果
- GPS+ 其他传感器的智能融合
网络定位中,服务器端使用三角定位等算法,根据周围多个 AP 的角度、耗时和场强等对比 WIFI、基站数据库获得用户位置信息。由于总会有人开启 GPS 的同时扫描到基站且基站的位置总是相对固定的,那么就可以根据发射源得到采样数据并聚类出中心点。
随后他分享了集中定位中经常使用的算法:
- 对于数据聚类,百度使用的是 E-Z 算法,通过穷举所有可能的 AP 参数和采样点位置,用排除法去掉所有不靠谱的数据,使用 Query 做为排除的依据,实现良好的室内定位效果。
- 使用基于最大似然的位置估计,对于每一个 AP 的参数模型以及带 RSSI 的 AP 列表,根据概率计算出精准的位置,这种方式能够将信号强度充分利用。
- 旋转定位
- 机器学习 KNN 应用,在传统的经典三角定位中,AP 位置很难计算准确,而 RSSI=a+b*log(d) 的模型郭宇理想,通过 KNN,可以不关心原理,只关注结果,利用相似度算法对数据的特征进行统计学习。
- 机器学习决策树应用,当很难用整箱的推导得到决策模型时,构建随机的森林,挖掘大数据的潜力,进而对算法融合得到最好的策略。
同时,百度还用机器学习来解决连续定位的问题。在目前的应用中,对架构存在如下的挑战:
- 并发压力大
- 时效性高
- 容错性强
接下来他对比了工业界与学术界的差异,对于定位技术未来,他的谈到了如下的几点:
- 手机传感器应用
- 基于场景识别的定位
- 低功耗定位
- 室内定位
- 无设备定位
- 协同定位绘图
主题二:陌陌手机定位技术实践(下载讲稿)
陌陌科技联合创始人兼 CTO 李志威接下来为大家分享陌陌的定位技术实践,主要涉及“手机定位方式以及精度”、“陌陌附近搜索的架构与性能优化”和“定理位置偏移原理”等。
他对比了集中不同方式的定位技术:
- GPS 精确到 5 米,定位时间偏长
- A-GPS 精度和定位时间平衡
- 基站,在于运营商
- WIFI,快速、适用范围广,但是误差大
他提到一般系统 SDK 都会包装各种定位方式提供简单的函数,返回最终确定的坐标,又或是 SDK 提供底层获取到的各种原始数据,然后把这些数据提供到定位服务 API 来获取定位结果。但是在实际场景中,定位服务面临的一个比较棘手的问题是位置偏移,即系统调用里获取的坐标显示在系统地图上位置不正确,但是系统地图的实时位置却是正确的。由于中国采用的是 WGS-84 基础上加入随机偏移的 GCJ-02 坐标体系,所以这个问题在所难免,那么为了解决这个问题,陌陌通过如下的方式来做尝试:
- 对网络上的 Google 地图得出的原始经纬度对应的偏移量进行扫描
- 调用第三方地图 API 的接口进行修正
目前陌陌 400M 的地图数据全部放到 Java 内存中,可以实现单个服务实例每秒 1 万次的查询。
陌陌中比较著名的功能是“查找附近的人”,它的技术基础是使用 GeoHash 将原有的地图位置匹配转化成字符串大小比较的过程,因此能够使用 MySQL 等关系型数据库做实现,同时还可以用 MongoDB 的 2d 索引做更简单高效的计算。对于 MongoDB 的解决过程,李志威详细分享了背景和方案,他提到了“附近的人”的几个特性:
- 基于地理位置,热点分散
- 热点区域请求过多
- 用户坐标是变化的,索引更新频繁
- 附近搜索对多条件查询支持差
使用 MongoDB 则将位置索引作为第一个检索的索引,按查询条件一直拆分直至命中率足够高。陌陌中的 MogoDB 集群使用配置文件来描述搜索条件、区域分块等,通过 PHP/Java 提供稳定的搜索接口。
特别嘉宾
本期的沙龙我们还邀请到了北京邮电大学教授,博士生导师,智能通信、导航与微纳系统实验室主任邓中亮,邓博士在近年来一直致力于无线传感器网络、卫星导航定位、多媒体通信、微电子设计、MEMS 等研究,他在沙龙的现场也做了精彩的分享。
Open Space(开放式讨论环节)
为了促进参会者与我们每期的嘉宾以及讲师近距离交流,深入探讨在演讲过程中的疑问,本次活动依然设置了 Open Space(开放式讨论)环节。
在 Open Space 的总结环节,几位话题小组长分别对讨论的内容进行了总结。
邓中亮:我们讨论了两个问题:1. 目前的定位技术背后的技术支撑;2. 产业发展的路径,从产业的角度来考虑这些问题。
张传明:主要讨论了两类问题,第一个是开发者的问题,如何正确的使用 SDK 的接口等,第二类的是底层服务构建的问题,例如运营商的规则的探讨、室内定位、动作的判断等;
李志威:我们讨论了“附近搜索”、“热点搜索”的技术与应用技巧,还谈到了目前开源软件如 MongoDB 等的特性;
会后,一些参会者也通过新浪微博分享了他们的参会感受:
钱钤也是个好青年:地理位置偏移是 LBS 服务的硬伤之一。一种情况是国内坐标系不同程度偏移,问题体现在地图上。可通过第三方 API 做位置修正。图片的后两张概述附近搜索的基本技术原理。多条件附近搜索会加重后台服务器负担,陌陌在提高了服务器处理性能后才提高了少量服务。
一起天行健:经过李老师讲述的陌陌技术演变实践细节,终于了解附近定位的“内幕”,真心不错,很实用哈哈,这个曾经让我感到神奇的 app,今天场地有点拥挤哈,high 不起来:D
dhcn :感觉百度 LBS API 主要还是面向一些传统 GPS 定位不够有效的用户场景,它在具体的使用中它怎样和手机本地定位 API 的定位结果 merge 到一起哪?或者说它完全封装取代了那一层?
tusion2011 :干货啊,终于知道基站的地理坐标信息是如何采集的了。好东西啊,回去找论文!
有关百度技术沙龙的更多信息,可以通过新浪微博关注 @百度技术沙龙,或者关注 InfoQ 官方微信:infoqchina,InfoQ 上也总结了过往 39 期所有百度技术沙龙的演讲视频和资料等,感兴趣的读者可以直接浏览内容。
特别提示:第41 期百度技术沙龙将在8 月24 日,在北京车库咖啡举行,欢迎关注 @InfoQ 、 @百度技术沙龙获取后续的活动信息。
评论