基于MEC的无人物流车任务卸载策略

郜文灿 齐 平 束 红 蒋剑军

（铜陵学院，安徽 铜陵 244061）

一、引言

随着电商的崛起，物流行业得到了迅猛发展。仅2019年我国快递业务量就已达到635.2亿件，相比2012年骤增732%。如此巨大的配送需求给物流配送行业带来了前所未有的压力[1]。无人驾驶技术承担着革新交通运输业的重要使命，而无人化的物流配送业务则有可能成为无人驾驶技术最先落地的应用场景[2]。无人驾驶物流车运用人工智能技术，提高了物品的配送效率、准确性和安全性，并且能够有效的降低运营成本[3]，但庞大的数据传输制约着无人物流车的发展。据统计，一辆无人车运行一天产生的数据量约为4TB[4]，如果将数据均上传到云数据中心处理，必然会产生较高的时延和带宽浪费。

移动边缘计算(Mobile Edge Computing，MEC)[5]作为云计算向用户终端扩展，能够在网络边缘侧部署计算资源和服务，从而极大的降低带宽消耗与网络延迟。计算卸载技术作为MEC的关键技术，是指移动终端将部分或全部计算任务交给边缘服务器或云服务器处理的技术[6]，主要研究移动终端是否需要卸载，卸载哪些任务，卸载至何处计算等问题[7-8]。从卸载决策优化目标进行划分，当前研究主要集中在以下3个方面：1.时延优化，以获得更快的卸载响应时间和任务完成时间为目标[9-10]；2.能耗优化，以降低移动终端或整个MEC系统总体能耗为目标[11-12]；3.综合考虑能耗和时延，根据具体任务特性，兼顾优化能耗和时延为目标[13-14]。

在终端移动条件下，综合考虑时延、能耗优化问题，是当前智慧物流场景下的计算卸载技术急需解决的问题。因此，文献[15]在MEC车联网场景下，对于任务卸载过程中的能效与性能可靠性问题，提出了一种能耗最优化的卸载方案，有效地提升了系统性能。文献[16]采用层次分析法对车辆产生的安全消息进行优先级划分，再针对时延和能耗构建任务卸载模型。然而在上述研究中，一般设定车辆与路边单元(RoadSide Unit，RSU)之间的数据上传、下载速率为定值，或设为车辆行驶期间的平均数据传输速率。然而，对于在边缘服务器无线信号覆盖范围较小的小区内行驶的无人车而言，无法忽略数据传输速率的瞬时变化以及物流车位置改变对计算卸载性能的影响。

针对上述问题，本文在MEC环境下，结合工作流任务、小区无人车配送场景地图、边缘服务器无线信号覆盖范围，构建了考虑终端移动性的无人车任务卸载时间与能耗模型。在此基础上，提出了无人车移动路径规划算法、任务卸载决策与调度算法和最优配送路线算法。仿真实验结果说明通过预先规划最优配送路径和配送顺序，合理地分配计算资源，能够在用户响应时间约束下有效降低终端能耗和违约率。

二、MEC环境下小区无人车物流配送场景建模

（一）小区无人车物流配送场景

对小区无人车物流配送场景进行建模描述，图1中已标注边缘服务器、无人车出发地和目的地位置，同时使用蓝色和橙色虚线标出从出发地到目的地的两条可选路径(实际情况中可能存在多条可选路径)，移动路径定义如下：

图1 无人物流车配送场景及移动路径平面图

定义1将小区按照其地理位置划分为若干网格，移动路径由ngrid个具有偏序关系的网格位置构成，定义移动路径Path={ci|ci=(xi，yi)，i∈ngrid}。其中，ci为移动路径上第i个网格的位置坐标，由二元组(xi，yi)表示，分别其横坐标和纵坐标，且满足相邻位置坐标(xi，yi)和(xi+1，yi+1)在地理位置上相邻并可达。

定义2小区无人车物流配送场景地图可表示为二维数组。如图2所示，数组元素用于表示地图中网格点的通行状态。数值0表示该网格存在永久性建筑或障碍物(如楼房、绿化带等)，无法通过，数值1表示该网格可以正常通行。

图2 小区无人车物流配送场景地图构建方法

（二）工作流任务模型

本文通过加权有向无环图 （DirectedAcyclic Graph，DAG）对MEC环境下无人车物流配送工作流中任务执行的先后依赖关系进行描述。其中，无人车物流配送工作流、云服务器、边缘服务器、移动终端和无线信号覆盖模型分别定义如下：

定义3工作流任务可采用一个加权有向无环图（W，E）表示，W为任务集合，E为工作流任务间的依赖关系。其中W={wi|wi=(INi，OUTi，li)}，wi为工作流任务中第i个任务，INi为任务wi的输入数据量，OUTi为任务wi的输出数据量，li为任务负载；E={(wpre，wsucc)|wpre，wsucc∈W}， 其中wpre为前驱任务，wsucc为后继任务。

定义4移动设备（MobileDevice，MD）可表示为一个五元组，MD=(fmd，Pmd，Locmd，nload，v)，其中fmd和Pmd分别表示MD的计算能力和能耗；Pmd=(pidle，pexec，ptra，prec)，分别表示MD的空闲功率、任务执行功率、数据发送功率和接收功率；Locmd表示MD的位置坐标，v表示其速度（米/秒）；nload表示MD的最大承载能力，即MD每次回到小区物流配送服务站最多可以装载nload件货物。

定义5云服务器（CloudServer，CS）可表示为一个二元组，CS= (fcs，Rcs)，其中fcs表示CS的计算能力，Rcc表示CS的数据发送和接收速率。

定义6边缘服务器（EdgeServer，ES）可表示为一个四元组，ES=(fes，Res，BWes，Loces)，其中fes表示ES的计算能力，Res表示数据发送和接收速率，BWes，为传输带宽，Loces为位置坐标。

定义7MD与ES之间的瞬时数据传输速率为：

其 中fSNR(dES，MD)为 传 输 信 噪 比[11]，dES，MD为MD和ES之间的距离，dmax为两者之间的最大通信距离。受信噪比的影响，对于不同ES，应通过dES，MD计算MD与各ES之间的瞬时数据传输速率。为简化模型，本文假定MD在同一网格内移动时，与同一ES进行通信的数据瞬时传输速率不变。

三、无人车任务卸载模型

设定无人车的初始位置为小区物流配送服务站，当用户发出配送服务请求时，如图3(a)所示，无人车应尽可能多的装载货物(设nload为4)，再将货物分别送至各用户指定位置，若此时配送任务没有完成，还需返回小区物流配送服务站继续装载、配送货物，直至任务完成。

配送过程中存在两方面问题：（1）如图3(b)所示，当无人车的出发地和目的地确定时，应结合当前可选移动路径以及无人车的移动速度，计算各可选路径在任务响应时间约束下的最少终端能耗，进而选择终端能耗最小的最优路径行驶；（2）如图3(c)所示，当存在多个用户的配送请求时，应结合最优路径选择算法，确定服务的先后顺序，得到最优配送路线。本节针对确定起止点的路径构建任务卸载能耗模型，该模型由云服务器能耗模型、移动设备能耗模型和边缘服务器能耗模型三部分构成。

图3 无人物流车配送路径规划

（一）云服务器能耗模型

当计算任务卸载至云服务器时，MD能耗由三部分组成：1）数据发送能耗；2）数据回传接收能耗；3）整个过程中空闲等待能耗。设卸载至云端执行的任务数量为ncs，则将任务卸载至云端时，终端的总执行时间和总能耗可由式(2)计算：

在移动路径预先规划的情况下，设（Startx，Starty）为MD初始网格的位置坐标，网格边长为len米，则在Tcs时间内MD通过的网格数gridcs为[(V×Tcs)/len]。因而，任务执行完毕后MD位置(Endx，Endy)可更新为(Startx，Starty)之后第gridcs个邻接网格位置(若任务执行过程中，已到达目的地则MD位置不再改变)。

（二）移动终端能耗模型

当任务在MD执行时，其终端能耗为任务在MD的执行能耗。设在MD上执行的任务数量为nmd，则终端的总执行时间和总能耗可由式(3)计算：

（三）边缘服务器能耗模型

如图4所示，当任务卸载至边缘服务器时，MD能耗由任务所需数据的发送能耗、回传数据的接收能耗以及在发送、接收、执行期间MD的空闲等待能耗组成。数据发送阶段，MD的位置由坐标(TraXstart，TraYstart)移动至坐标(TraXend，TraYend)；在回传数据接收阶段，MD的位置从坐标(RecXstart，RecYstart)移动到坐标(RecXend，RecYend)。然而，如图4(b)所示，由于MD和ES之间的瞬时数据传输速率与距离相关，在数据发送或回传阶段，当MD离开当前ES的无线信号覆盖范围时(d|ES，MD|＞dmax)，任务将无法卸载至ES，需在本地或卸载至云端执行。

图4 边缘服务器计算卸载模型

设卸载至边缘侧执行的任务数量为nes，则将任务卸载至边缘侧时，终端的总执行时间Tes和总能耗Ees分别为：

四、工作流卸载决策及其调度算法

根据工作流任务的执行先后依赖关系对其优先等级进行划分，相同优先级任务可并行处理。设任务最大优先级为N，优先级序列为LV={lv1，lv2，…，lvN}，对于其中第i级可并行任务lvi(设第i级可并行任务的任务总数为mi)，使用任务执行矩阵对其进行描述，如式(5)所示：

（一）基于最优路径的卸载决策及调度算法

最优路径是指在满足任务时间约束的条件下，终端能耗最低的路径。在小区无人车物流配送场景下，当无人车出发地和目的地确定时，需要在两地之间的多条路径中找出最优路径，并依此得到卸载决策和任务调度方案。本文使用遗传算法设计基于最优路径的无人车任务调度算法(TaskSchedulingAlgorithmBasedontheOptimalPath，TSABOP)。TSABOP算法首先对染色体进行解码，再结合无人车的移动路径得到各任务调度序列(如将任务卸载至边缘服务器则根据各边缘服务器位置及其无线信号覆盖范围，找出边缘侧无线信号最优的候选边缘服务器进行卸载)，最后通过适应度函数对各任务调度序列进行评价。

（二）无人车最优配送路线算法

本节基于遗传算法设计了无人车最优配送路线算法（OptimalServiceSequenceofDriverlessLogistics DistributionVehicle，OSS-DV)。

设请求配送货物的用户数量为ndist，按时间排列的配送请求位置序列为由于无人车最多能够装载nload个货物，因此以序号1，2，...，nload表示nload个用户，Eij表示无人车从用户i到用户j的最优能耗(由算法1计算，当无人车早于用户指定时间到达配送位置时，应加上无人车等待期间的终端空闲能耗)；tij表示无人车从用户i到用户j所花费的时间；xij∈{0，1}为决策变量；Ti表示无人车到达用户i的时刻，应落在时间范围[Tui-ε，Tui+ε]内，Tui为用户i指定的服务时间，Eear和Elate分别表示无人车提前到达和延后到达的惩罚值，因而该问题的目标函数f为：

式(7)右侧第一项为不考虑时间约束下的能耗；第二项为无人车到达时间早于Tui-ε时，等待时间的惩罚值；第三项为无人车晚于Tui+ε时，迟到时间的惩罚值。

五、仿真实验与分析

本文通过在MatlabR2017b环境下进行仿真实验以检验算法性能，所有实验结果均采用10次实验的平均值。

实验参数设置如下：无人车的最大承载能力为6，计算能力为1GHz，执行功率为0.5W，数据发送时功率为0.5W，数据接收时功率为0.05W，空闲功率为0.02W，Eear和Elate分别取0.1和0.15，移动速度为1m/s[2]，无人车与云端的数据传输速率为5Mb/s，与边缘侧的数据瞬时传输速率由两者之间的通信距离决定[11][12]。边缘服务器数量为10，其位置在小区内呈均匀分布，计算能力介于[2GHz～5GHz]之间，云服务器的计算能力为8GHz[12]。设定小区无人车物流配送场景为800m*600m的长方形区域，小区路径预先给定，网格大小设定为1m*1m。设定用户位置随机生成，用户配送请求时间间隔服从指数分布[17]；无人车工作流任务DAG图随机生成，任务计算量介于1～5GHz之间，发送和回传数据量介于1～15Mb之间[18]，用户响应时间约束为该任务在1.4GHz虚拟机上平均执行时间的2倍[19]。

（一）任务卸载模型的有效性

1.路径选择对算法性能的影响

工作流任务数量为50，Path1～Path8分别表示两点间随机选择的8条路径，实验结果如图5所示。

图5 不同移动路径下的终端能耗比较

由图可见，当选择不同路径时，终端能耗也不相同。对比最小能耗路径Path3和最大能耗路径Path7，Path7所需能耗增加了152.3%，可见TSABOP算法规划最优路径的必要性。

2.配送路线对算法性能的影响

本实验在不同任务数情况下，从终端能耗、违约率和任务完工时间三个方面考察不同配送路线对算法性能的影响。相关实验参数设置如下：ε为30s，每条路径的工作流任务数量变化范围为[10，100]，任务完成后无人车才可进入下一条配送路径。TimeSequence(两点间最优路径由TSABOP算法计算，配送路线按照用户请求时间)、ShortestPath(两点间路径选取最短路径，配送路线按照用户请求时间)和Optimal Sequence(OSS-DV算法得到的最优配送路线)为3种无人车配送策略，实验结果如图6所示。

图6 不同配送路线算法的性能比较

由图可见，Timesequence策略相比OptimalSequence策略的终端能耗提高了17.6%，违约率提高38.9%，说明不同配送顺序对算法性能具有较大影响，而本文提出的OSS-DV算法结合移动路径，即考虑了用户配送时间要求，又考虑了任务在云端、边缘服务器以及移动设备上的执行效益，能够在响应执行时间约束下有效降低终端能耗和违约率。

（二）不同任务数情况下的算法性能比较

本实验在不同任务数下，对OSS-DV算法和其它3种任务卸载策略进行比较。实验参数设置为：每条路径的工作流任务量为50，对比策略包括Only-Cloud、Only-Edge和LoPRTC[20](其中Only-Cloud、Only-Edge分别指工作流任务全部在云端或边缘侧执行)，对比策略选取路径为两点间最短路径，配送路线按照用户请求时间，实验结果如图7所示。

图7 不同任务数下算法的比较

由图7(a)和图7(c)可见，本文提出的OSS-DV算法的违约率比LoPRTC算法降低50.1%，任务完工时间减少25.3%，而终端能耗降低41.3%，说明OSSDV算法通过合理规划移动路径，优化任务卸载决策，和其他3种算法相比能够大幅降低终端能耗和违约率，有效提升无人车配送效率。

六、结语

本文在小区无人车物流配送场景下，将终端移动性纳入计算卸载模型，根据移动终端的实时位置、移动速率、边缘服务器位置、边缘服务器无线信号覆盖范围以及小区地图构建了无人车任务卸载模型，设计了工作流任务优先级划分算法和边缘侧卸载优化算法，并在此基础上使用遗传算法设计基于最优路径的无人车任务调度算法和无人车最优配送路线算法以计算最优路径和配送路线。仿真实验结果说明本文提出的TSABOP算法和OSS-DV算法能够在响应时间约束下，有效降低终端能耗和配送违约率。由于本文只考虑了单个无人车的物流配送场景，下一步工作将研究多个无人车的协作问题。