百度技术沙龙第 40 期回顾:定位技术解析与应用开发实战(含资料下载)

  • 水羽哲

2013 年 7 月 30 日

话题:百度语言 & 开发

在 7 月 27 日由@百度主办、@InfoQ负责策划组织和实施的第 40 期百度技术沙龙活动上,百度资深软件工程师、现担任百度定位服务的技术负责人张传明和陌陌科技联合创始人兼 CTO 李志威分享了各自在定位技术方面的经验,话题涉及“构建高可用性的无线定位服务”和“陌陌手机定位技术实践”等。本文将对他们各自的分享做下简单的回顾,同时提供相关资料的下载。

主题一:构建高可用性的无线定位服务 (下载讲稿

百度资深软件工程师、现担任百度定位服务的技术负责人张传明从“为什么需要移动定位”、“定位原理简介”、“从原理到实现”以及“现状与展望”等角度展开。首先他谈到了移动定位的三个理由:

  1. 使用户知道自己身在何处
  2. 使搜索结果更加智能
  3. 位置敏感信息的基础

目前的主流的定位方式有 GPS 定位、网络定位,GPS 定位精度高、精准连续定位、无服务端,但是室内不可用、耗电且初次定位慢。由于基站、WIFI 都具有全球唯一的标识,所以也能够用作定位的作用。在真正的使用中,需要根据应用场景,选用定位方法。

在百度开放的定位服务中,混合使用了不同的定位方式,对于 GPS 定位,用户可以在手机上直接调用相关的 API 即可得到 GPS 坐标和误差半径,在软件层面上通过如下的方式做优化:

  1. 加速可能成功的搜星
  2. 不做必然失败的搜星
  3. 预测过大误差的 GPS 结果
  4. GPS+ 其他传感器的智能融合

网络定位中,服务器端使用三角定位等算法,根据周围多个 AP 的角度、耗时和场强等对比 WIFI、基站数据库获得用户位置信息。由于总会有人开启 GPS 的同时扫描到基站且基站的位置总是相对固定的,那么就可以根据发射源得到采样数据并聚类出中心点。

随后他分享了集中定位中经常使用的算法:

  1. 对于数据聚类,百度使用的是 E-Z 算法,通过穷举所有可能的 AP 参数和采样点位置,用排除法去掉所有不靠谱的数据,使用 Query 做为排除的依据,实现良好的室内定位效果。
  2. 使用基于最大似然的位置估计,对于每一个 AP 的参数模型以及带 RSSI 的 AP 列表,根据概率计算出精准的位置,这种方式能够将信号强度充分利用。
  3. 旋转定位
  4. 机器学习 KNN 应用,在传统的经典三角定位中,AP 位置很难计算准确,而 RSSI=a+b*log(d) 的模型郭宇理想,通过 KNN,可以不关心原理,只关注结果,利用相似度算法对数据的特征进行统计学习。
  5. 机器学习决策树应用,当很难用整箱的推导得到决策模型时,构建随机的森林,挖掘大数据的潜力,进而对算法融合得到最好的策略。

同时,百度还用机器学习来解决连续定位的问题。在目前的应用中,对架构存在如下的挑战:

  1. 并发压力大
  2. 时效性高
  3. 容错性强

接下来他对比了工业界与学术界的差异,对于定位技术未来,他的谈到了如下的几点:

  1. 手机传感器应用
  2. 基于场景识别的定位
  3. 低功耗定位
  4. 室内定位
  5. 无设备定位
  6. 协同定位绘图

主题二:陌陌手机定位技术实践(下载讲稿

陌陌科技联合创始人兼 CTO 李志威接下来为大家分享陌陌的定位技术实践,主要涉及“手机定位方式以及精度”、“陌陌附近搜索的架构与性能优化”和“定理位置偏移原理”等。

他对比了集中不同方式的定位技术:

  1. GPS 精确到 5 米,定位时间偏长
  2. A-GPS 精度和定位时间平衡
  3. 基站,在于运营商
  4. WIFI,快速、适用范围广,但是误差大

他提到一般系统 SDK 都会包装各种定位方式提供简单的函数,返回最终确定的坐标,又或是 SDK 提供底层获取到的各种原始数据,然后把这些数据提供到定位服务 API 来获取定位结果。但是在实际场景中,定位服务面临的一个比较棘手的问题是位置偏移,即系统调用里获取的坐标显示在系统地图上位置不正确,但是系统地图的实时位置却是正确的。由于中国采用的是 WGS-84 基础上加入随机偏移的 GCJ-02 坐标体系,所以这个问题在所难免,那么为了解决这个问题,陌陌通过如下的方式来做尝试:

  1. 对网络上的 Google 地图得出的原始经纬度对应的偏移量进行扫描
  2. 调用第三方地图 API 的接口进行修正

目前陌陌 400M 的地图数据全部放到 Java 内存中,可以实现单个服务实例每秒 1 万次的查询。

陌陌中比较著名的功能是“查找附近的人”,它的技术基础是使用 GeoHash 将原有的地图位置匹配转化成字符串大小比较的过程,因此能够使用 MySQL 等关系型数据库做实现,同时还可以用 MongoDB 的 2d 索引做更简单高效的计算。对于 MongoDB 的解决过程,李志威详细分享了背景和方案,他提到了“附近的人”的几个特性:

  1. 基于地理位置,热点分散
  2. 热点区域请求过多
  3. 用户坐标是变化的,索引更新频繁
  4. 附近搜索对多条件查询支持差

使用 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@百度技术沙龙获取后续的活动信息。

百度语言 & 开发