送外卖也要“黑科技”?阿里移动感知技术应用揭秘

阿里妹导读:送餐路上外卖骑手们所处的位置不仅牵动着大家的心,在本地生活的场景下,也是订单配送和调度系统的重要一环。其中骑手是否已到店取餐看似简单却难以准确观测。针对这一问题,阿里本地生活科技中心建立了基于移动感知的aBeacon系统来准确地观测骑手到店和离店行为。这一工作成果也发表在了网络系统领域的顶级会议NSDI’21上。本文将从实现原理为大家做一个简单介绍。

一  背景

作为本地生活的一个重要组成部分,外卖已经进入千千万万的家庭。相信很多小伙伴已经注意到,饿了么的每一个订单,我们都会及时向用户通知这一单现在所处的状态,比如“商户接单”,“骑手到店”,“骑手送达”等。这个实时状态的更新,不仅能让用户及时了解自己外卖到了哪里,对于整个平台的骑手调度和时间预估都有着重要意义。

而在所有的节点中,骑手到店前后的两个节点“骑手到店”和“骑手取餐”对于整个平台的价值就更为重要,主要体现在以下三个方面:

时间预估

骑手到店的时间是骑手从接单位置到商户位置的终止时间,而骑手离店的时间则是骑手从商户位置到用户位置的起始时间。掌握这些准确的时间,能给时间预估模型提供准确的标签用于模型训练。我们在APP里看到的“预估配送时间”就是这样计算出来的。同时,知道骑手在商户位置等了多长时间,我们就可以知道商户准备这一单需要多长时间,也就是商户的“出餐时间”。而掌握了准确的出餐时间,我们在给某一单找合适骑手的时候就能更加地游刃有余了。

骑手调度

当用户在外卖平台下单后,平台就会开始为这一单寻找合适的骑手来配送,这个过程就叫骑手调度。骑手调度是一个复杂的过程,需要考虑同时考虑商户,骑手和用户的位置,还要考虑骑手身上已有的单和商户正在准备的单。一个总的原则是,让更近的,更顺路的骑手去取单。如果我们知道了骑手到店的准确时间,我们就可以知道骑手在当前时刻的具体位置,并且能够预估出骑手在未来一段时间的大概位置。这就给我们的骑手调度提供了准确可靠的数据源。

超时单判责

虽然调度系统会尽力保证每一单都尽快送达,但还是会有一些情况导致少部分运单会超时,给用户带来不好的体验。为了提升调度系统的性能,减少超时单。我们首先需要知道超时的原因,从而在未来的调度中作出改进。超时的两个主要原因是“商户已出餐但骑手未到店”和“骑手已到店但商户未出餐”。在没有明确数据的情况下,这两个对立的原因往往会出现“公说公有理,婆说婆有理”的情况。如果我们能够准确获得骑手到店的时间,这一困境就会迎刃而解。

二  挑战

既然获取准确的骑手到店时间是如此重要的问题,为什么现有的方法还是无法很好的解决这个问题呢?这是因为考虑到本地生活的场景,要获得准确的骑手到店时间,面临着以下几方面的挑战:

GPS在室内的漂移

现在手机定位最常用的方法就是GPS定位。但无论是GPS,还是我们最近刚组网成功的北斗系统,其本质上都需要手机里的芯片来接收地球上方的卫星信号。但商户的位置往往是在室内,当我们在室内环境时,GPS信号会受到建筑物的遮挡,导致GPS信号微弱甚至完全失去信号。这个时候GPS的精确度就会从几米扩大到几百米甚至几公里,导致GPS信号出现漂移。因为这一漂移现象的存在,我们需要划定一个范围来判断骑手是否到达了商户。当我们用一个较小的范围时,可能会出现“骑手已到店但我们认为没到”,如果我们用一个较大的范围,那么骑手到店时间的准确性则会大打折扣。

商户在不同楼层的垂直分布

在GPS漂移之外,商户在不同楼层的垂直分布也会给骑手到店的准确判定带来困难。当商户分布在不同楼层时,即使我们通过GPS判断出骑手已经在水平方向上到达商户附近,但由于没有垂直方向的信息,我们仍然无法准确判断出骑手到店的具体时间。如今越来越多的商户都分布在商场的不同楼层,这部分订单的骑手到店时间就很难观测。虽然GPS会返回一个海拔信息,但在实际的应用中我们发现这个值往往是不够准确的。

商户环境的动态性和骑手手机的多样性

一些室内定位的方法通过收集特定环境的声音指纹,光指纹或者磁场强度指纹来建立指纹库,然后通过指纹对比来判断手机所处的位置。理论上如果我们能够采集商户环境的指纹,并和骑手手机收到的信号进行比对,就可以判断骑手是否已经到达商户。但由于商户环境的动态性,比如装修改造和人来人往带来的实时扰动,我们很难建立一个稳定的指纹库来进行比对。同时,由于声光磁的指纹收集受到手机硬件的影响,骑手手机的多样性也对指纹库的建立带来很大挑战。

基于Wi-Fi的方法的局限性

随着越来越多的室内环境有Wi-Fi信号的覆盖,基于Wi-Fi信号的室内定位也得到了充分研究。但基于Wi-Fi方法也有两个局限性:一是持续的Wi-Fi扫描会带来极大的能耗负担,这对于工作极度依赖手机的骑手很不友好;二是出于隐私保护等原因,iOS系统只支持获取当前连接的Wi-Fi信息,而不支持获取Wi-Fi扫描的列表,但骑手在取餐过程中很少连接商户的Wi-Fi。这两个原因导致了基于Wi-Fi的定位方法无法适用于骑手到店的场景。

三  解决方案

当我们把骑手到店观测问题抽象出来,可以发现这是移动感知(Mobile Sensing)领域经典的“室内定位(Indoor Localization)”或者“存在监测(Presence Detection)”的问题。移动感知是指利用移动设备上的网络信号或声光电磁等传感器信号对用户的位置,行为,场景等进行感知的技术。手机上的计步功能,以及智能手表提供的心率监测和睡眠监测等功能,都是移动感知技术在生活中的具体应用。近些年来,随着移动设备的升级,研究者们也在探索移动感知的新应用,比如用Wi-Fi信号感知键盘敲击和老人摔倒,用手机话筒来检测醉驾,用新的传感器来感知用户的情绪和压力状态等。

这些研究也给我们的到店观测问题提供了很多思路,比如基于Wi-Fi的室内定位,基于特定光信号和声信号的定位方法等。但是通过上面的讨论我们可以看出,这些方法都难以很好地解决骑手到店观测问题。针对这一情况,我们设计并部署了aBeacon系统,一个基于蓝牙信号的移动感知系统,来解决骑手到店观测的问题。其实基于蓝牙的移动感知并不是一个全新的技术,苹果公司在2013年提出基于蓝牙的iBeacon协议用于移动感知[1],2016年蓝牙5.0中的新特征(更低功耗,更大范围)真正让蓝牙感知技术得以落地。蓝牙移动感知的原理就是通过在特定位置部署一些持续发送蓝牙信号的Beacon设备,同时手机进行持续的扫描来感知周围的蓝牙Beacon信号,从而来判断手机是否到达了特定位置。

图1  aBeacon系统原理图



基于这样的感知技术,我们建立了aBeacon系统,如图1所示,系统由三部分组成:部署在商户的蓝牙Beacon硬件、骑手APP内的蓝牙监听模块和平台服务器上的后端模块。在骑手配送过程中,APP上的蓝牙监听模块会持续监听周围的蓝牙Beacon信号,当骑手到达商户附近(比如10米范围内)时,手机会监听到该商户内的蓝牙Beacon信号,并把该数据和当前时间戳上传到服务器,服务器通过和预置的Beacon地图进行比对,就可以得到该骑手到达该商户的准确时间。在Beacon硬件方面,我们采用了自主定制的硬件,在降低成本的同时保证了蓝牙广播的质量,同时引入了加密技术来保护商户的位置隐私。在手机监听模块方面,我们通过设计一个动态监听模块,在保证到店判断能力的前提下降低了能耗。

对比前面提到的几个挑战,我们可以发现,因为蓝牙信号自身的特性,Beacon信号在室内环境的传播仅限于几米到几十米的范围(相信大家使用蓝牙耳机和鼠标都有类似的感受),因此基于蓝牙的到店判断不会出现GPS那样几百米的误差,可以极大提高骑手到店观测的准确性。同时,因为蓝牙信号的穿墙能力较差,因此只有当骑手到达商户所在的楼层时才会接收到蓝牙信号,这样就避免了商户楼层带来的影响。此外,我们通过标准化的部署流程,使得Beacon硬件部署在商户的骑手取餐处的上方,避免了商户内动态环境的改变对信号的影响。蓝牙协议的标准化和手机硬件的成熟化也降低了骑手手机硬件对到店观测的影响。此外,因为蓝牙监听属于非连接通信,骑手使用蓝牙耳机的功能也不会受到影响。最后,和Wi-Fi相比,蓝牙监听的功耗也很低,我们的实验证明,Beacon监听每天只会给骑手手机带来3%的额外功耗负担。

总体来说,aBeacon系统的主要贡献在于将蓝牙感知的技术真正应用到骑手到店观测的问题中,并解决了一系列实际应用中的挑战,比如能耗,可靠性,隐私保护等,并且从理论层面上对系统的成本和效用进行分析,从而指导今后大规模感知系统的落地。

在系统的设计中,我们考虑了下面的一些指标:

成本

成本是我们上线一个商业化的系统所必须考虑的因素之一。aBeacon系统的成本包括两部分:aBeacon设备的硬件成本,和大规模部署的成本。在硬件成本方面,我们通过对硬件的定制来降低成本。在部署成本方面,我们通过简化硬件部署的流程,从而在业务经理的帮助下降低部署成本。

寿命

出于易用性的考虑,我们的aBeacon硬件采用了电池供电的方式。这样电池的容量就成为了限制系统寿命的主要因素。但在两年的运行之后,我们发现除了电池的寿命,环境变化也是影响系统寿命的重要因素。

可靠性

可靠性是指在所有的骑手到店行为中,有多大比例可以被aBeacon系统观测到。在实际中,可靠性受到包括部署质量,商户环境,骑手手机等诸多因素的影响。

效用

骑手到店观测给整个系统提供了更准确的数据,它带来的效用是基础但难以直接衡量的,因此我们采用超时率这一衡量整个调度系统的指标来评估aBeacon的效用。

在系统的设计过程中,我们首先量化了上面的四个指标,然后建立这四个指标和我们要优化的终极目标——aBeacon带来的累积收益——之间的量化关系。因此,我们可以在这个量化关系的指导下对各个因素进行权衡。

在这样的设计思路的指导下,aBeacon系统的部署和运行主要包含了两个主要环节:

设计与测试

基于成本和设计自由度的考虑,我们选择自主定制aBeacon设备,同时自主定制还能让我们嵌入隐私保护等其他功能。在大规模的部署前,我们挑选了几个商场进行小规模的测试。在测试中,我们将自主定制的aBeacon设备和另一种商用的Beacon设备同时部署在商户里。通过对比测试,我们发现采用自主定制的aBeacon设备可以在压缩成本的同时达到和商用Beacon设备同样的可靠性。

图2  aBeacon设备在上海的部署

部署与运行

在小规模测试后,从2018年1月开始,如图2所示,我们在上海的12000余家商户里部署了aBeacon设备。我们用一份包含“部署在哪里”、“怎么固定”、“如何绑定”等问题的部署手册来指导业务经理进行部署。在运行过程中,我们通过后台收集的数据,可以对所有设备进行实时监控,所有设备被分类为“健康”、“部署错误”、“下线”等状态。我们针对不同的设备还可以采取不同的维护措施,比如针对“部署错误”的设备进行重新部署。

另一个很重要的问题是系统安全和隐私保护,这也是我们在aBeacon设备的定制过程中作出的重要改进之一。因为传统的iBeacon协议是固定ID的明文广播,可能导致系统的安全性漏洞。比如:

  • 未授权的用户可能通过战争驾驶(wardriving)[2] 的方法来反推出Beacon设备的位置,并用于其他目的。


  • 恶意攻击者可能通过在异地复制已有Beacon设备的蓝牙广播,向系统中注入错误的位置数据。


针对这一问题,我们在自主定制的设备中对蓝牙广播进行加密,通过一种TOTP[3]的加密算法,让所有aBeacon设备广播的ID内容定时进行变更,而ID和设备位置的映射关系存在只有授权用户可以访问服务器。这样极大地提高了系统的安全性。

四  效果

为了评估aBeacon系统给整个配送过程带来的效果,我们采用了“超时率”这一总体指标作为指标。我们用上海未部署aBeacon设备的一万多家商户作为参照,来评估部署了aBeacon设备的商户在部署前后超时率的变化。通过对比我们发现,在总体上,通过一年的运行,aBeacon系统可以将超时率降低0.24%,这使得我们每年可以减少超过7余万超时配送订单。

图3  aBeacon系统在不同楼层和不同地区的效用

同时我们还发现,aBeacon系统在不同楼层和不同的地区体现出较大的差异性。如图3所示,部署在B2层和4/5层的设备可以带来更大的效用,这其实也印证了我们前面的分析,骑手在这些楼层商户的准确到店时间更难观测,通过部署aBeacon设备,我们可以在这些商户取得更大的效用。

迄今为止,aBeacon系统为上海超过10万骑手提供准确的到店观测分析,通过不断优化骑手配送流程,每年可减少超过7余万超时配送订单,为超过700万的用户人群提供更优质服务。

五  讨论与发现

作为一篇介绍移动感知技术大规模应用的文章,我们在系统设计和部署过程中的发现希望能给后来者的工作带来更多启发。总的来说,我们的发现包括以下两个方面:

(1)    系统可靠性。在移动感知领域,研究者们为我们带来了很多新的想法。但这些想法在实际落地的过程中都会遇到可靠性的问题,我们用aBeacon系统的部署过程说明了,即使是用蓝牙信号进行存在感知这样一个简单的应用,系统的可靠性也会受到硬件设备的部署和用户手机硬件等诸多因素的影响。因此在以后的研究中,我们需要在系统设计的过程中更多地考虑这些因素,让系统就有更强的鲁棒性。

(2)    aBeacon系统的局限之一就是我们还需要部署和维护硬件设备,在后来的工作中,我们仍在探索采用已有的终端设备作为虚拟的aBeacon设备用以辅助骑手的定位。基于此,我们正在开展aBeacon+系统的研究工作,解决一些相关的问题,比如终端设备自身定位,以及隐私保护等。

六  总结

基于aBeacon系统,阿里本地生活科技中心的论文“From Conception to Retirement : a Lifetime Story of a 3-Year-Old Operational Wireless Beacon System in the Wild” 被计算机网络系统领域的顶级会议NSDI’21收录。作为首篇基于本地生活场景的系统论文,这也代表了阿里本地生活科技中心在移动感知方面的工作得到了来自网络系统领域顶级会议的认可。在落地应用后,通过获取更准确的骑手到店和离店时间,该系统为全国超过10万骑手提供准确的到店观测分析,通过不断优化骑手配送流程,每年可减少超过7余万超时配送订单,为超过700万的用户人群提供优质服务。未来,在阿里巴巴本地生活和新零售的业务布局下,我们还会持续加强相关领域的研究,将更多前沿技术投入到更多场景的运营分析中,发挥出更多作用,用技术服务用户。

参考文献

[1] Apple Inc. iBeacon. https://developer.apple.com/ibeacon/ , 2020
[2] Wikipedia, Wardriving, https://en.wikipedia.org/wiki/Wardriving, 2020
[3] Wikipedia. Time-based one-time password, https://en.wikipedia.org/wiki/Time-based_One-time_Password_algorithm , 2020.
阿里技术
阿里技术

分享阿里巴巴的技术创新、实战案例、经验总结,内容同步于微信公众号“阿里技术”。

专栏二维码
产业感知移动感知技术Beacon蓝牙
相关数据
感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

调度技术

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源,如线程、进程或数据流;也可以指硬件资源,如处理器、网络连接或扩展卡。 进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态,允许多位用户有效地同时共享系统资源,或达到指定的服务质量。 see planning for more details

室内定位技术

在室内环境无法使用卫星定位时,使用室内定位技术作为卫星定位的辅助定位,解决卫星信号到达地面时较弱、不能穿透建筑物的问题。最终定位物体当前所处的位置。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

阿里巴巴机构

阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的18人于1999年在浙江杭州创立的公司。 阿里巴巴集团经营多项业务,另外也从关联公司的业务和服务中取得经营商业生态系统上的支援。业务和关联公司的业务包括:淘宝网、天猫、聚划算、全球速卖通、阿里巴巴国际交易市场、1688、阿里妈妈、阿里云、蚂蚁金服、菜鸟网络等。 2014年9月19日,阿里巴巴集团在纽约证券交易所正式挂牌上市,股票代码“BABA”,创始人和董事局主席为马云。 2018年7月19日,全球同步《财富》世界500强排行榜发布,阿里巴巴集团排名300位。2018年12月,阿里巴巴入围2018世界品牌500强。

https://www.alibabagroup.com/
相关技术
量化技术

深度学习中的量化是指,用低位宽数字的神经网络近似使用了浮点数的神经网络的过程。

暂无评论
暂无评论~