留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向海量智能终端的云定位系统设计与实现

张传明 杨玲玲 刘敏 李伟 贾海禄 蒋方胜 李成洲

张传明, 杨玲玲, 刘敏, 李伟, 贾海禄, 蒋方胜, 李成洲. 面向海量智能终端的云定位系统设计与实现[J]. 武汉大学学报 ( 信息科学版), 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
引用本文: 张传明, 杨玲玲, 刘敏, 李伟, 贾海禄, 蒋方胜, 李成洲. 面向海量智能终端的云定位系统设计与实现[J]. 武汉大学学报 ( 信息科学版), 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
ZHANG Chuanming, YANG Lingling, LIU Min, LI Wei, JIA Hailu, JIANG Fangsheng, LI Chengzhou. Design and Implementation of Cloud Positioning System for Massive Intelligent Terminals[J]. Geomatics and Information Science of Wuhan University, 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
Citation: ZHANG Chuanming, YANG Lingling, LIU Min, LI Wei, JIA Hailu, JIANG Fangsheng, LI Chengzhou. Design and Implementation of Cloud Positioning System for Massive Intelligent Terminals[J]. Geomatics and Information Science of Wuhan University, 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249

面向海量智能终端的云定位系统设计与实现

doi: 10.13203/j.whugis20210249
基金项目: 

国家重点研发计划 2016YFB0501801

详细信息
    作者简介:

    张传明,博士,主要从事地理信息系统研究与应用。zhangchuanming@baidu.com

  • 中图分类号: P208

Design and Implementation of Cloud Positioning System for Massive Intelligent Terminals

Funds: 

The National Key Research and Development Program of China 2016YFB0501801

More Information
图(8) / 表(1)
计量
  • 文章访问数:  366
  • HTML全文浏览量:  107
  • PDF下载量:  47
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-12-01
  • 刊出日期:  2021-12-05

面向海量智能终端的云定位系统设计与实现

doi: 10.13203/j.whugis20210249
    基金项目:

    国家重点研发计划 2016YFB0501801

    作者简介:

    张传明,博士,主要从事地理信息系统研究与应用。zhangchuanming@baidu.com

  • 中图分类号: P208

摘要: 随着移动设备和低成本定位传感器的普及,移动终端的普适定位能力成为刚需。为了构建一个普适可用的云定位系统,需要在智能终端应用各类定位传感器获取信号并将其在定位数据库中进行查找、计算,实现对位置的获取。针对智能手机设备和位置服务应用(location based service, LBS)场景,基于主流云计算网络架构,探讨并解决了层次化云定位能力、开发者低成本接入、设备容错能力和分布式服务等工程化关键问题,设计并搭建了面向海量智能终端的大规模云定位系统。测试结果表明,该系统能够支撑每日千亿次请求的访问处理能力,提供面向亿级大众用户的定位服务。

English Abstract

张传明, 杨玲玲, 刘敏, 李伟, 贾海禄, 蒋方胜, 李成洲. 面向海量智能终端的云定位系统设计与实现[J]. 武汉大学学报 ( 信息科学版), 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
引用本文: 张传明, 杨玲玲, 刘敏, 李伟, 贾海禄, 蒋方胜, 李成洲. 面向海量智能终端的云定位系统设计与实现[J]. 武汉大学学报 ( 信息科学版), 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
ZHANG Chuanming, YANG Lingling, LIU Min, LI Wei, JIA Hailu, JIANG Fangsheng, LI Chengzhou. Design and Implementation of Cloud Positioning System for Massive Intelligent Terminals[J]. Geomatics and Information Science of Wuhan University, 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
Citation: ZHANG Chuanming, YANG Lingling, LIU Min, LI Wei, JIA Hailu, JIANG Fangsheng, LI Chengzhou. Design and Implementation of Cloud Positioning System for Massive Intelligent Terminals[J]. Geomatics and Information Science of Wuhan University, 2021, 46(12): 1872-1880. doi: 10.13203/j.whugis20210249
  • 定位能力是支撑基于位置的服务(location based service,LBS)的基础能力,精准的定位能力在各类导航、地点推荐等应用中起到了至关重要的作用。因此,定位能力的准确性与健壮性是两大基本问题。准确性是指定位结果应当和设备真实位置尽可能接近,健壮性则是指在各种复杂场景下(网络不畅、无线信号不佳、并发用户多)依然能提供稳定的定位服务。

    广泛使用的全球导航卫星系统(global navigation satellite system,GNSS)使得全球数十亿用户可以享受低成本、高精度的连续定位服务,基本解决了室外应用的问题[1]。但由于其固有的定位原理[2],使得它有两个难以克服的问题:(1)初次定位慢;(2)室内无法发挥作用。这影响了LBS应用的体验感。现实中,部分场景对定位精度的需求并不苛刻,如天气预报、周边地点推荐等,精度在楼宇级、街区级乃至在城市级都是可以接受的。云定位恰恰是解决这类场景的有效手段,它能够和GNSS形成有效的互补[3]

    云定位能够有效利用网络传输信号进行定位,由于在云端进行信号数据库的维护,由此得名。随着智能手机的普及,近年来涌现了一些针对云定位的研究[3-5],但多数研究未涉及面向大规模大众化应用的实践。在实际工程中,针对多样且海量的智能设备构建一套普适可用的云定位平台所涉及到的技术依赖非常复杂。为了保证定位精度,需要实现多种定位算法并且构建大规模定位数据库和合适的融合定位算法,在服务接入方面也需要最小化LBS应用开发者的开发成本,还需要构建大规模分布式服务,以应对流量波动,保持服务的健壮性。

    本文探讨了上述相关基础能力的构建,包括基站定位、无线局域网(wireless local area network,WLAN)定位、网络互通协议(interworking protocol,IP)定位、云-端协同融合定位等,同时在工程实现层面上也讨论了相关的技术原理与工程化手段。运用上述思想,笔者进行了工程化设计与开发,测试结果表明,本文介绍的云定位系统可以支撑海量设备的普适定位请求,实现与GNSS的有效互补,满足LBS应用的定位需求,提升LBS应用的体验。

    • GNSS有着精度高、连续性好的突出优势,但也存在初始定位慢以及室内无法使用的问题。而在另一方面,只要终端设备具有扫描或接入网络的能力,即可感知到周围的网络信号,此外,普通智能手机还可以获取丰富的运动传感器数据。这些数据与GNSS形成良好的互补,更普遍精准地推算设备位置,如图 1所示。根据主流手机的硬件参数,智能手机可获取到的用于定位的信号,除了GNSS外,还包括两类[5]:(1)绝对定位信号源,以基站、WLAN、蓝牙三者为主;(2)相对定位信号源、惯性传感器(加速度计、陀螺仪、重力计)、磁力计。

      图  1  各种信号覆盖人类活动范围

      Figure 1.  Signals Covering the Area of Human Activities

      绝对信号源所涉及的信号均具有很好的局部唯一性。例如,对于全球任何一个基站,都可以通过移动国家码(mobile country code,MCC)、移动网络码(mobile network code,MNC)、位置区码(location area code,LAC)、小区编码(CELLID)来唯一标识它。对于WLAN接入点设备(即接入点(access point,AP)、无线路由器)和蓝牙信标也是如此,根据相关约定,所有的无线接入点都有一个唯一的媒体存取控制位址(media access control address,MAC)地址。这就意味着设备如果能扫描到上述几类绝对信号源发出的信号,说明当前设备必然在这些信号对应的发射设备的附近。如果设备仅有一个且位置已知,只需将发射设备位置作为定位结果,其最大定位误差便不会超过信号辐射范围。如果设备有多个,那么基于三角定位的原理,精度还可以更高[6]

      从绝对信号源的信号编码唯一性定位原理可知,只需要采集并构建一个无线信号数据库,即可根据客户端扫描到的信号通过查询的方式来确定该信号源在数据库中的位置,并实现对设备位置的推算。但困难在于,全球的基站、WLAN等主流信号源个数已达数亿,导致数据库的大小远远超过终端的存储能力,并且这个数据库还在时刻变化更新。因此,个体设备无法在本地实现信号位置的查询和定位。

      因此,更可行的方法是在服务端维护一套信号位置数据库,并且通过客户端扫描定位依据、发送请求到服务端、服务端进行定位查询、解算出设备位置最终返回给用户来解决这一问题。这就是云定位的基本流程。

    • 基于服务端定位原理,本文提出了基于客户端-服务端(client-server,C-S)架构的云定位服务,整体架构如图 2所示。在这套架构下,客户端不必关注服务端的实现原理,服务端实际使用分布式计算来实现服务架构,便于平行扩充,响应快速波动的请求。

      图  2  网络定位架构图

      Figure 2.  Architecture of Network Location System

      在云定位系统架构中,客户端一方面通过扫描定位依据,请求服务端得到绝对定位结果,另一方面结合GNSS信号,并融合网络定位结果和惯性传感器(inertial measurement unit,IMU)计算出更精准的位置。而服务端主要作用是解决两个问题:(1)定位的健壮性(成功率、响应速度)问题;(2)定位的准确率问题。

    • 根据软件工程的设计原则,一个复杂的业务应当尽量拆解细致,各能力解耦,可以分别优化而不受影响[7]。而在实际业务中,漏斗式的层次定位更重要的作用在于能够减少精细化定位算法的调用次数,实现整体性能的最大化,提升系统可用性。基于上述考虑,本文构建了层次化的云定位能力,将一个完整的复杂定位流程逐层分解,各环节相互配合,最终完成一次云定位的解算。层次化定位的整体框架如图 3所示。

      图  3  层次化定位架构图

      Figure 3.  Hierarchical Cloud Positioning Architecture

    • 粗略定位,顾名思义是定位解算的计算量较小、准确率稍低,但是可以最大限度减少后续算法的工作量。主要的粗略定位包括基站单点定位、WLAN三角定位、IP定位这3类算法。

    • 基站定位本身是业内很成熟的定位方法,但从民用智能终端的可用性角度,普适的基站定位很难做到100 m以内的精度。其主要原因包括两点:(1)基站部署密度还不够,而基站定位精度和基站密度是正相关的,这就导致了无法广泛地满足实验室里的高精度条件;(2)智能手机操作系统和智能手机厂商对基站定位的支持度并不高,包括并未普遍放开多基站编码(ID)的返回,以及刷新用户连接基站时更新速度低,这样就导致了相当数量的手机设备只能获取到单个基站的ID,且时效性并不高。基于上述原因,基站定位可以用于返回百米量级精度的用户位置,但是由于通信信号覆盖非常广阔[8],因此基站定位依然是最关键的粗略定位手段之一。

      构建基站定位数据库的方法包括两类,第一类方法是通过室外采集标签数据(带有真实GNSS位置)来构建,但该方法无法获取室内深处或仅覆盖地下区域的基站位置,因此还需使用第二类方法做补充,即同一设备上若能同时扫描到WLAN与基站信号,则在有WLAN定位数据库的前提下,可以用WLAN定位的结果近似作为基站位置的标签,通过空间聚类的方法计算出基站最有可能的位置。

    • 由于大部分城市区域都有WLAN信号,因此WLAN定位也是一种非常普遍的定位方法,尽管主流的WLAN定位方法是指纹定位[5],但从工程实现的角度,指纹定位依然有着不小的代价,其计算代价与指纹库的数量呈正相关。因此,十分有必要在指纹匹配的前期使用一种简化的定位方式,减小精细化指纹匹配的搜索空间。

      三角定位就是一种化繁为简的定位方式,基本原理如图 4所示。根据目标点与信号源之间位置关系计算方法的不同,又分为基于到达方向角(angle of arrival,AoA)、基于达到时间(time of arrival,ToA)、基于到达时间差(time difference of arrival,TDoA)[6]的三角定位。但普通民用手机受操作系统的限制,很难获得AoA、ToA、TDoA观测值,因此这类基于经典三角定位方法无法在普通智能终端的定位中得到推广。而由于操作系统对于WLAN信号强度的友好度高,基于信号强度的(received signal strength,RSS)的WLAN三角定位相对可行,它利用WLAN信号在空间传输过程中的能量衰减特性,计算出目标点到信号源之间的距离(如对数-距离衰减模型),进而推算目标点的位置。

      图  4  三角定位原理示意图

      Figure 4.  Triangular Positioning Principle

      但其中仍有3个影响着定位精度的关键问题难以彻底解决:

      1)很多定位场景出现在室内,且最为常见也是使用最多的一种无线信号源WLAN也多半部署在室内,室内的环境通常比较复杂,存在各种障碍物(墙壁的遮挡、人流的影响等),使得无线信号发生各种反射、衍射,即多路径效应,不再符合理想状态下的传播模型,导致根据设备收到的周围WLAN的信号强度来推算两者的距离就会过远,进而据此推算的定位坐标也就不准。例如,目标点与某AP之间有人流通过,且不同时间段人流情况也不尽相同,那么在不同时间段目标点接收到同一AP的信号强度也会不一样,同样导致了定位结果的误差。

      2)由于不同移动设备感知信号的能力差异较大,会导致在同一位置、同一时间的两个设备扫描同一AP的WLAN信号强度也不一样,同一个传播模型无法适用于所有的设备。

      3)信号源的真实位置往往无法准确获得,即便是人工采集数据也很难直接标记出信号源的坐标。一般是通过有位置标注的信号采集点数据反推信号源坐标。例如,可以利用人工标注得到某个AP的一系列信号采集点 < (xy),s > ,(xy)为信号采集的真实位置,s代表此处接收到该AP的信号强度。通过AP的采集点,根据信号传播模型反过来计算AP的位置,从而导致与1)和2)相同的情况,信号的实际传播情况与理论上的传播模型不相符,最终无法精准推算AP的位置。

      上面3个影响定位精度的关键问题决定了三角定位是一种高性能(只需要进行几何计算即可)、低精度(10 m量级)的定位算法,但毋庸置疑其是一种可行的粗略定位方法,其精度比单点基站定位高了一个量级,可以有效地降低后续精细化定位的搜索空间。

    • 由于网络请求必然会产生一个IP地址,而IP地址的分配受运营商的规划影响,存在一定的规律性,因此基于IP地址的定位也得到了一定的研究[9]。目前的IP地址主要分为移动类IP(2G/3G/4G/5G接入互联网)和宽带类IP(宽带/WLAN接入互联网)。

      移动类IP主要是手机端用的2G/3G/4G类IP,由于移动类IP地点变化的频率比较高,还伴随着漫游等场景,因此基于移动类IP的精准定位非常困难。而对于宽带类IP,大部分分布于公司、学校、住宅小区等室内场所,且稳定性很好,存在定位的可能性。从技术上可以实现精准(百米量级)的单IP定位,从而弥补当前移动定位的不足,为广大个人电脑、非智能手机系统、封闭式手机系统的用户提供更为完善、精准和稳定的定位服务,提升用户体验。尤其是第六代互联网协议(IPV6)系统,IP地址更加精细化,所映射的物理空间位置更加精准。

    • 目前实际使用较多的是指纹匹配法。最早的指纹定位方法是微软研究院在2000年设计的雷达(RADAR)算法[10]。RADAR算法提出了将WLAN信号作为位置指纹实现定位的新思路,并设计了指纹定位方法的原型。其后,有相当多的室内定位系统都是基于RADAR原型进行不同方面的算法改进和性能提升。其中较著名的是文献[11]提出的Horus系统[11]。近20 a来,指纹定位的方法越来越流行,所采用的指纹信息也涵盖了射频识别、移动通信、调频广播等多种多样的无线网络信号,以及背景声音、地磁场、光照、图像等丰富多彩的环境感知信息。

      指纹定位的本质是将待定位的定位信号指纹与指纹库中的指纹进行比对,找到最接近的多个候选指纹,并基于它们的位置来推算定位结果,关键步骤是两个定位指纹的相似度计算。

      本文用MAC地址和信号强度的二元组来代表一个信号,不同信号用“|”来分隔,在某商场能得到的WLAN信号指纹如下:

      {b4b36265ea16;-58;|062512859186;-61;|c6b36265ea16;-61;|d6b36265ea16;-63;|c6b36265ec1e;-66;|d6b36265ec1e;-67;}

      计算两条指纹的相似度,主流的做法是首先将两条指纹扫描到的相同AP的信号强度作为向量,有多少个共同AP则就构造多少维向量;然后,针对这两个向量计算余弦相似度。假设两次信号测量结果指纹1和指纹2,它们共同的MAC地址仅有2个,这两条指纹在这两个MAC地址上的信号强度分别为s11s21(指纹1的测量结果)以及s12s22(指纹2的测量结果),则余弦相似度的计算方法为:

      (s11s21+s12s22)|f1||f2|

      其中,

      $$\begin{array}{l} |{f_{\rm{1}}}| = \sqrt {{s_{{\rm{11}}}} \cdot {s_{{\rm{11}}}} + {s_{{\rm{12}}}} \cdot {s_{{\rm{12}}}}} \\ |{f_{\rm{2}}}| = \sqrt {{s_{{\rm{21}}}} \cdot {s_{{\rm{21}}}} + {s_{{\rm{22}}}} \cdot {s_{{\rm{22}}}}} \end{array}$$

      在上述计算中,每个AP在余弦相似度计算中是等权的,但这在很多时候并不符合实际情况。辐射范围较小的AP,信号强度可以在短距离内有很大的变化,因此其区分度更大,蕴含的信息量也更大。基于这样的出发点,从匹配度优化的角度还可以引入排序学习的机制,学习出每个AP的匹配权重[12]

      即使如此,由于不可避免的硬件差异和信号随机波动,依然会导致在同一位置的不同设备感知同一无线信号源,其获取到的信号强度也可能是不同的。但因为LBS产品特性的限制,需要在尽可能短的时间内扫描到定位依据,否则位置的时效性便无法保障。因此,其信号波动性会对定位质量产生不可忽略的影响。在实际工程中还需要通过一些方式来消除这样的影响,后文还会进行进一步的介绍。

    • 为了提高匹配的精度和效率,云平台在进行指纹匹配之前要对智能终端上传的观测数据进行检核,该过程包括两部分:(1)判断无线信号采集是否充分;(2)依据定位方式对观测数据进行预处理。关于无线信号采集是否充分的判断,即检核无线信号采集是否满足一定的密度要求(同一采集单元获取的WLAN/蓝牙信号数等),云平台会根据这项指标选择不同的定位方式,采集充分时以指纹匹配为主,采集不充分时以三角定位解算为主。

      不同的定位方式对成功率和精度均有不同的侧重。举例来说,GNSS精度高但在室内的精度很差,而网络定位的精度则仅对信号丰富度敏感,室内外差异不大。因此当获得无线信号后,需要有一个融合定位的投票机制来确定最终的定位结果。

    • 比较简单的实现方式是先确定场景,然后基于不同场景用规则制定所用的算法。由于手机传感器能观测到的信号强度依赖于智能手机操作系统,典型的场景判断方法包括如下几种。

      1)基于室内外判断的融合策略。室内外主要基于以下几个特征:(1)GNSS的信号强度。同时能观测到的卫星数量越多、信噪比越好、卫星形态越均匀(精度因子值是一种可行的量化手段),则室外的可能性越大。(2)WLAN信号的强度。WLAN信号强度越强,则室内的可能性越大。

      基于上述判断,当判断为室外时更信任GNSS结果,当倾向于遮挡或者室内时则更信任云定位结果。

      2)基于无线信号丰富度的融合策略。当判断为室内时,依然需要有进一步的判断,以确定定位的方法。由于三角定位的泛化能力较好,避免了指纹稀疏导致的体验,因此当信号源个数较多(如同一时刻扫描到的WLAN信号源超过一定数量)时可以考虑使用指纹定位方法,反之则使用三角定位方法。

    • 在多定位算法融合这一领域,集成学习是一个很有价值的思想。它本身不是一个具体的机器学习模型,而是一类融合框架的统称,通过构建并结合多个算法来完成学习任务[13]

      在多定位算法融合场景中,除了应用常规的集成学习算法外,还可以根据定位算法的特点对集成算法框架进行深度的定制设计,如定位点所在的区域(室内、室外、楼层等)是一个启发因子,可以对融合策略有决定性的影响,又如每个基础定位算法(GNSS、WLAN三角定位、WLAN指纹定位、基站定位)自身也可以通过概率模型给出对其定位结果置信度的估计,这种定位置信度也可以作为融合的重要特征。集成策略也可以使用强化学习得到,通过初步推算云定位结果和GNSS观测值的偏差作为强化信号,迭代提升集成算法的精度。

    • 从支撑普适LBS应用的角度,需要减少LBS开发者的开发成本。按照传统的C-S架构,有大量的细节需要开发者处理,首先是搭建云定位服务端,该工作成本巨大,其数据采集成本是普通开发者难以承担的。其次是在客户端要获取定位依据,需要对操作系统、定位原理有深入的了解。再次是在算力上,需要基于请求分布考虑不同区域的计算资源调配,并应对请求量随出行高峰剧烈变化等运行维护问题。上述问题在实际工程中严重制约了LBS应用的构建效率。因此,需要有统一、易于接入的客户端插件包,嵌入宿主程序,实现即插即用的定位能力,即SDK(software development kit)接入方式。SDK即软件开发工具包,通过把各种基础能力封装成开发接口,大大提升了构建应用的效率。SDK封装了实现细节,在内部通过网络连接的方式与服务端交互,因此在SDK内部需要考虑网络传输的安全性。在安全性方面最大的威胁是各类网络劫持,这可能导致传输内容泄露或篡改。在传输过程中,可以通过域名解析服务代理和加密传输的方式来规避域名解析劫持以及传输劫持[14],而在服务端获取了客户端传输的结果后,可以通过请求内容签名校验的方式验证获取到的请求内容与原始(客户端发起的)请求的一致性。上述多种机制并用,有效解决了传输过程中的信息一致性,以保证传输的安全。

      在构建SDK时,还需考虑通过账号体系等控制开发者对于定位能力的使用频次与精度,进而构建面向开发者的商业模式。由于SDK的更新升级往往是独立于宿主程序的,因此在自我修复机制方面需要考虑C-S协同的热修复机制,使SDK在发现问题时可以修复问题,最小化客户端升级成本,确保宿主程序的稳定性。

    • 当构建大范围的定位服务时,最大的困难并不是算法本身,而是针对各种异常情况的处理。最主要的容错场景包括信号源位置变更、信号强度差异过大等。

    • 如前文介绍,信号强度在定位算法中起到了关键作用,但不同设备对于同一位置同一信号的敏感度不同,这样导致观测到的信号强度存在不可忽略的差异。因此需要对观测数据进行相应的预处理,包括过滤与纠正。

      过滤工作,是指采用指纹匹配定位时,要在满足匹配所需最小信号数的前提下,剔除信号最弱的若干观测数据,避免这些观测值的波动带来的负影响;采用三角定位时,要考虑信号过弱而不再满足信号传播模型的情况,对这些信号予以剔除以保证定位精度。

      纠正工作,是指主动对不正常的信号强度进行修正。为了兼顾简单和有效,通常使用线性变换来拟合特定设备指纹信号强度的偏差。即假设指纹库信号强度=k×某设备信号强度+ b,求解kb。求解过程是先计算出某设备发出的若干请求指纹和指纹库中对应的最佳匹配指纹,并假设两两位置相同,而后基于匹配中共现的AP,计算出若干组信号强度差,最后用关联分析的方法分析出设备和指纹库中对于同一AP的信号强度关联关系。这种方式可以有效减小基于信号强度的测距误差,用以提高定位精度。

    • 无线信号能够用于云定位的本质假设是信号源的位置固定。如果违背该假设,则会引入误差甚至导致严重错误。信号源位置的变更主要出现在连人带设备搬迁的情况,如WLAN的AP随楼内人员搬迁导致的定位错误。这类问题可以通过动态社区发现[15]、关联分析的方法来解决。如基于AP在大范围(城市级)定位请求中的共现关系构建一个带权图,如共现频繁则权值更大,基于该图进行聚簇分析,一旦某些AP所属的簇发生了变化,则表明该AP所属的物理位置发生了变更,此时需要剔除该AP或者重新对AP位置进行采集、标记。上述场景的一种极端情况就是便携式热点或者移动基站,即信号源的位置始终在变化,这种情况也可以通过同样手段进行检测和处理。

    • 对于大规模的定位服务,一般使用分布式的架构来保证性能,主要是出于多个原因的考虑。第一是请求量增大,单机的处理能力无法处理海量并发请求;第二是大范围的信号数据库无法在单机内存中进行存储;第三是为了尽量使逻辑上不同的业务环节(如粗略定位、精细定位)分配于不同服务器,以确保彼此的稳定性不受影响,专机专用也便于运维。图 5为分布式云定位服务器的整体架构。

      图  5  分布式定位服务集群示意图

      Figure 5.  Distributed Location Service Cluster

      分布式结构的引入使得系统之间的耦合度降低,可以独立开发、独立部署、独立测试,系统与系统边界清晰,开发效率和服务能力都得到了提升。

      客户端请求到达服务器后,首先经过的是前端服务器,前端服务器主要使用超文本传输协议(hyper text transfer protocal,HTTP)来接入流量。接入流量后,最重要的职责就是调度,即定位请求到来时,选择负载较小的节点去处理,使得各个节点的压力都尽量平均。负载均衡的方法包括轮询法、加权轮询法、随机法、加权随机法、源地址哈希法、最小连接法等。

      通过负载均衡算法确定连接的目标后端服务器后,通过远程过程调用(remote procedure call,RPC)的方式向后端服务器发起请求,后端服务器具有粗略定位、精细化定位、融合定位等能力,彼此之间也通过RPC进行连接。在后端服务器中,广泛使用内存数据库、流式计算实现快速请求响应和数据传输。

      分布式定位服务的最新形态是虚拟化的定位平台,即基于云存储、弹性计算等技术,在这种计算框架下,已经不需要关注物理主机的概念,拥有的计算资源可以无限、平滑地扩展。这样的平台不仅仅可以在集群压力增大时自动扩容,加快运维效率,在集群闲置的低谷时期,也可以动态调配其他计算任务,避免计算资源过多闲置。

    • 需要说明的是,即使运用了分布式手段,由于集群数量是有限的,所以整个集群的响应能力依然是有限的。为了确保集群的稳定性,云定位服务需要拥有自动化降级能力。本文设计的自动降级计算的技术架构如图 6所示。

      图  6  自适应降级原理示意图

      Figure 6.  Adaptive Degradation Principle

      当线上计算资源充裕时,自适应降级架构可不起作用,即完全按需提供服务。但资源紧张时就会启动降级预案。首先通过预估模型判断请求的重要性,判断价值的原则是预估请求定位结果与设备既有定位结果的差异,如差异较大(最极端的情况下就是首次定位),则认为此次请求重要性较高,因此使用完整的定位流程进行定位。当差异较小,则使用较为粗略的定位流程进行定位(比如仅使用三角定位),如几乎无差异,则可直接丢弃流量,即服务端主动拒绝定位。上述流量分配机制配合失败重试限制,可以在超出集群设计压力的情况下,有效确保服务的整体可用性,避免雪崩类事故发生。

    • 笔者所在团队对上述系统框架设计思路进行了工程化实现,系统采用分布式架构,在北京、苏州、南京、广州进行区域中心部署,由前端服务器集群、应用服务器集群和数据存储服务器集群组成。服务器均使用CentOS Linux操作系统,前端服务器采用Lighttpd和Nginx,应用服务器使用C++开发服务,数据服务器采用远程数据服务(remote dictionary server,Redis)和分布式文件系统(hadoop distributed file system,HDFS)作为存储服务。云定位平台的模块架构图如图 7所示。

      图  7  定位服务模块架构图

      Figure 7.  Module Architecture of Location Service

      为了验证分布式云定位系统的服务能力,在上述每个区域集群分别进行请求压力测试,基于网络定位系统日志统计确定云定位日处理最大峰值,每个集群的安全容量测试均持续50 min以上。可以看出,随着压力测试的开始,每秒响应次数迅速增加(见图 8),最终测试结果如表 1所示。

      图  8  压力测试时每秒响应次数趋势图

      Figure 8.  Trend of Queries per Second During Load Testing

      表 1  云定位系统的请求响应能力测试

      Table 1.  Request Response Capability Test of CloudPositioning System

      集群 响应能力/(万次∙min-1) CPU利用率/%
      广州 2 430 63.58
      苏州 1 950 62.24
      北京 2 208 59.45
      南京 1 524 61.63
      整体 8 112 61.76

      表 1数据可知,在压力测试中,中央处理器(central processing unit,CPU)利用率始终在70%以内,在负载正常的条件下,每秒响应次数折合的每日处理能力达到1 000亿次以上,能够有效支撑大规模协同精密定位应用。

    • 随着LBS应用的发展,为了保障连续、普适的移动设备定位能力,构建云定位系统的必要性已经显而易见。本文介绍了云定位系统的整体架构、层次化云定位算法的组成和对于开发者和运维工程师更加友好的高可用性设计。基于本文所述的设计,笔者所在团队构建了面向海量智能终端的定位服务开放平台,得到了数十万开发者的应用,产生了良好的行业价值。展望未来,随着5G与边缘计算的兴起,传输效率越来越高,云和端的分工界限也会越来越模糊。从定位的系统性角度,未来的定位将会是云定位系统与终端高精度GNSS能力的深度融合,这些工作能进一步降低成本,提升定位的精准度和连续性,也将是后续研究的重点。

参考文献 (15)

目录

    /

    返回文章
    返回