关键词：
一 背景
作为本地生活的一个重要组成部分，外卖已经进入千千万万的家庭。相信很多小伙伴已经注意到，饿了么的每一个订单，我们都会及时向用户通知这一单现在所处的状态，比如“商户接单”，“骑手到店”，“骑手送达”等。这个实时状态的更新，不仅能让用户及时了解自己外卖到了哪里，对于整个平台的骑手调度和时间预估都有着重要意义。
而在所有的节点中，骑手到店前后的两个节点“骑手到店”和“骑手取餐”对于整个平台的价值就更为重要，主要体现在以下三个方面：
时间预估
骑手到店的时间是骑手从接单位置到商户位置的终止时间，而骑手离店的时间则是骑手从商户位置到用户位置的起始时间。掌握这些准确的时间，能给时间预估模型提供准确的标签用于模型训练。我们在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信号，从而来判断手机是否到达了特定位置。
基于这样的感知技术，我们建立了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设备同样的可靠性。
部署与运行
在小规模测试后，从2018年1月开始，如图2所示，我们在上海的12000余家商户里部署了aBeacon设备。我们用一份包含“部署在哪里”、“怎么固定”、“如何绑定”等问题的部署手册来指导业务经理进行部署。在运行过程中，我们通过后台收集的数据，可以对所有设备进行实时监控，所有设备被分类为“健康”、“部署错误”、“下线”等状态。我们针对不同的设备还可以采取不同的维护措施，比如针对“部署错误”的设备进行重新部署。
另一个很重要的问题是系统安全和隐私保护，这也是我们在aBeacon设备的定制过程中作出的重要改进之一。因为传统的iBeacon协议是固定ID的明文广播，可能导致系统的安全性漏洞。比如：
- 未授权的用户可能通过战争驾驶（wardriving）[2] 的方法来反推出Beacon设备的位置，并用于其他目的。
- 恶意攻击者可能通过在异地复制已有Beacon设备的蓝牙广播，向系统中注入错误的位置数据。
针对这一问题，我们在自主定制的设备中对蓝牙广播进行加密，通过一种TOTP[3]的加密算法，让所有aBeacon设备广播的ID内容定时进行变更，而ID和设备位置的映射关系存在只有授权用户可以访问服务器。这样极大地提高了系统的安全性。
四 效果
为了评估aBeacon系统给整个配送过程带来的效果，我们采用了“超时率”这一总体指标作为指标。我们用上海未部署aBeacon设备的一万多家商户作为参照，来评估部署了aBeacon设备的商户在部署前后超时率的变化。通过对比我们发现，在总体上，通过一年的运行，aBeacon系统可以将超时率降低0.24%，这使得我们每年可以减少超过7余万超时配送订单。
同时我们还发现，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........
本文为阿里云原创内容，未经允许不得转载。
对话李飞飞，揭秘国际体育赛事风“云”背后的黑科技
...科学家李飞飞为我们揭秘国际体育赛事风“云”背后的黑科技。Qÿ 查看详情
java黑科技实现原理揭秘
高并发架构消息队列搜索引擎缓存分库分表读写分离设计高并发系统高并发架构部分内容缓存：Redis高可用：高并发系统设计：分布式系统分布式业务系统，就是把原来用Java开发的一个大块系统，给拆分成多... 查看详情
北京冬奥黑科技;揭秘虎年春晚硬核科技;全球首款ar隐形眼镜问世;索尼3d显示技术路径曝光...
...家开工大吉，虎年顺利！北京冬奥从开幕式就黑科技曝了！这一次的北京冬奥会，从开幕式就直接火了！首先是从冰立方中破冰而出并随着音乐冉冉升起的奥运五环。事实上，整个冰雪五环就是个巨大的LED... 查看详情
iphonex黑科技大揭秘，这几大摄像功能是要上天！
北京时间9月13日凌晨1点，苹果在美国召开了2017年秋季新品发布会今年是iPhone诞生10周年，iPhone已经三年没有大变样了，因而今年的关注度也是异常的高，各种爆料也是轰炸刷屏了一整年，这次发布会自然也是万众瞩目。这场亮... 查看详情
阿里根据截图查到泄露者,用的什么黑科技？(数字盲水印)
https://stgod.com/1482本文分为五个部分，第一部分综述；第二部分频域数字盲水印制作原理介绍；第三部分盲水印攻击性实验；第四部分总结；第五部分附录（源代码）。一、综述本文提供的一种实现“阿里通过肉眼无法识别的标... 查看详情
从量子加密到机器学习，盘点2015阿里云开放的黑科技
http://www.csdn.net/article/2015-12-18/2826512摘要：因为云计算应用的不断深入。以及对大数据处理需求的不断扩大，用户要求功能丰富、性能强大、高可用性的产品，云计算厂商们也推陈出新，不断地推出新产品，本文就盘点了业内翘... 查看详情
大繁至简，首度揭秘阿里云飞天洛神系统
参考技术A摘要：洛神是阿里云飞天中负责虚拟网络的系统，她为阿里云客户提供了丰富的网络产品，如VPC、SLB等。同时，她也是ECS，RDS，OSS，NAS等100多个云产品的网络基础设施。她还支撑了阿里巴巴集团和蚂蚁金服集团众多业... 查看详情
阿里云专家带你揭秘云计算数据底座——对象存储
...取、存储、处理、应用数据，是一整套方法论，也要有一整套的工具。对象存储因云而生，是面向各种计算应用的存储资源池，提供弹性的服务化能力。随着各行业数字化的蓬勃发展和企业数字化的转型，数... 查看详情
阿里云ai编辑部获ccbn创新奖，传媒行业解决方案背后的黑科技
简介：视频云驱动智媒创新5月27日，CCBN（第二十八届中国国际广播电视信息网络展览会）在北京隆重召开，在本次的“CCBN年度创新奖”评选中，阿里云视频云凭借AI编辑部的传媒行业专业解决方案获得CCBN... 查看详情
直播app全量混淆和瘦身技术揭秘
...淆技术是对抗逆向攻击最有效的方式之一。本直播会分享阿里聚安全带来的APP全量混淆技术 查看详情
[codevs2800]送外卖
[codevs2800]送外卖试题描述有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次）... 查看详情
堪称一绝，阿里技术人都用的nginx笔记手册，应用到架构齐全
有人调侃我们说：程序员不如送外卖。送外卖是搬运食物，自己是搬运代码，都不产出新的东西……透支体力，又消耗健康，可替代性极强，30岁之后就要面临被优化的危险……想跳槽，但是更高的平... 查看详情
区间dp-送外卖
Whenwearefocusingonsolvingproblems,weusuallyprefertostayinfrontofcomputersratherthangooutforlunch.Atthistime,wemaycallforfooddelivery.Supposethereare N peoplelivinginastraightstreetthatisjus 查看详情
百度再出lens黑科技！用paddlemobile实现类人眼视觉ai能力
你知道吗？人类有70%的信息获取来自于视觉。但目前存在两个问题：①人眼本身只能看到物理世界，无法看到其背后复杂的信息世界；②人类的记忆力有限，视野有限，于是会出现看了就忘、视野窄等各种问题。科幻片里常见这... 查看详情
程序人生干了三年程序员，我决定兼职送外卖
目 录为什么去送外卖送外卖经历过程送外卖收入状况一些趣事的分享停止送外卖原因送外卖心得感受 写在最后为什么去送外卖当时我的手机只有64GB，但实在太多东西不想清理掉，就想换个最新款的小米手机，256... 查看详情
codevs2800送外卖
题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），... 查看详情
[codevs2800]送外卖
题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），... 查看详情
codevs2800送外卖
题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），... 查看详情