无人机配送系统中端边协同的并行任务调度算法

周博文，黄海军，徐 怡+，李学俊，高 寒，陈天翔，刘 晓，徐 佳

(1.安徽大学 计算机科学与技术学院，安徽 合肥 230601；2.中移在线服务有限公司 浙江分公司，浙江 杭州 310000；3.迪肯大学 信息技术学院，澳大利亚 吉朗 VIC 3126)

0 引言

近年来，在线购物逐渐增多，订单量也随之增加。2018年11月11日，淘宝平台全天的物流订单达到10亿，这一数据在2019年超过了12.92亿[1]。物流企业需要在规定时间内完成全部订单的配送工作。在整体配送流程中，最后一公里配送环节所占的运输时间和配送成本高达30%和50%。无人机因其灵活部署、成本低廉、高速飞行的特点，在最后一公里配送场景中具有得天独厚的优势。目前，大型物流企业，如亚马逊、京东等都已经开始尝试将无人机作为最后一公里配送的运输工具[2]。在无人机配送的整个过程中，需要不断地对无人机上传感器和摄像头捕获的数据进行处理和计算，从而保障货物安全送达。由于无人机终端的计算能力与电池容量均有限，无法高效执行此类计算密集型应用，而传统云计算环境又存在距离终端设备较远、网络带宽有限等缺点，无法满足无人机飞行过程中高实时性与数据传输需求[3]。

移动边缘计算环境通过将计算资源下沉至更靠近终端设备，使得其具有低延时、分布式、高效率等优势[4-6]，更加适用于在移动设备上部署和执行人工智能应用。与云计算不同，移动边缘计算并不是将所有原始数据直接传输到云端，而是通过边缘服务器对原始数据进行预处理、过滤和分析，充分利用边缘设备的空闲计算资源。在文献[7]中，将部分无人机视频分析任务卸载至边缘节点，节省网络带宽从而提高可扩展性。在文献[8]中，无人机可以利用周围城市范围内边缘服务器的计算资源来优化用户体验，其中提出了一个决策框架来控制任务是否卸载到无人机系统的边缘服务器中，利用马尔可夫决策优化执行时延。上述工作将边缘计算引入无人机视频分析的场景中，但目前仍然存在的问题是，即使边缘服务器的资源比终端设备丰富，相较于云服务器节点还是相对有限。当最后一公里配送场景中收货人较多，即终端设备请求较多时，单一的边缘服务器可能会超过其本身的任务负载。一旦出现任务拥塞，则无法在满足用户时间约束的情况下得到处理结果。因此，需要部署多台边缘服务器，通过任务调度协作处理无人机所请求的大量计算任务。

在MEC环境中，任务调度是一项关键技术，通过将任务分配给不同的边缘服务器进行处理，可以减少任务的响应时间，从而优化用户服务质量(Quality of Service,QoS)。当前存在很多MEC环境下任务调度的研究。文献[9]提出一种用于车辆行驶过程中的边缘计算框架，以提高车辆的计算能力，基于蚁群优化的调度算法有效地进行任务调度，优化时间延迟。文献[10]利用时分多址协议将全部或部分任务卸载到边缘服务器，基于时间约束优化终端设备能耗。文献[11]在移动边缘环境下建立了最小化系统计算开销的卸载与任务调度联合优化问题，提出了通过迭代求解两个子问题的联合优化算法(algorithm of Joint Offloading decision, Bandwidth, and Computation resource Allocation ，JOBCA)。文献[12]提出用户移动条件下的任务调度问题，并提出一种基于遗传算法的分布式资源优化算法。然而，大多数研究聚焦于在网络环境稳定的场景中进行任务调度，忽视了现实场景中网络环境往往存在波动。此外，它们没有考虑不同边缘服务器的计算负载问题。由于边缘服务器更贴近于终端用户，呈现出分布式的特点，因此各个边缘节点存在计算能力、容量、带宽等差异，需要综合考虑进行任务调度。

针对上述问题，本文针对无人机物流场景构建了渐进式任务调度模型，并基于移动边缘计算环境设计了端边协同的并行任务处理框架。同时，针对上述模型和框架对现有的移动边缘计算中的调度算法进行优化和改进，改进后的调度算法除了能够在端边协同的并行任务处理框架下充分降低任务的时延，还考虑了边缘服务器和终端设备之间的网络波动情况，以及边缘服务器自身的计算负载，相比传统的调度算法具有良好的稳定性。

1 端边协同的并行任务调度模型

1.1 渐进式任务调度模型

在传统云计算环境中，无人机需要将拍摄的全部视频流数据上传到云服务器进行处理，最后将结果反馈到终端设备上。但是由于传输时延较高，可能存在不可知的网络波动，无法满足收货场景中复杂任务的实时性要求。本文基于移动边缘计算环境提出了渐进式任务调度模型。复杂任务的传输和处理流程建模如图1所示。

无人机将拍摄的视频流逐帧处理，首先采用基于YOLO-V3tiny的目标检测算法[13]，快速筛选出含有人的视频帧，并采用图像分割算法去除冗余信息，将其中包含人的部分提取出来。上述流程称为视频流在无人机上的预处理过程。通过对视频帧的初步筛选，可以大大降低数据的冗余度，减少任务的数据传输量和处理时间。最后，采用姿势识别[14]和人脸识别(网址参考：https://github.com/ageitgey/face_recognition/)对包含人的图片进行进一步识别，以定位目标收货人。而由于姿势识别和人脸识别是资源密集型的计算任务，需要将其卸载到边缘服务器上执行。考虑到不同边缘服务器的计算负载以及未知的网络波动，需要做出合理的调度决策。

本文基于移动边缘计算环境提出的渐进式任务调度模型，可以不断地将无人机中已经预处理完成的任务按照一定的调度算法调度到指定的边缘服务器执行。虽然边缘服务器具备更多的计算资源，可以执行复杂的深度学习算法，但是相对于云服务器，边缘服务器的计算资源有限，不能同时处理全部任务，后到的任务需要在就绪队列中等待。等到边缘服务器有足够的计算资源时，队列中的任务才能再进入边缘服务器执行。

在实际的无人机送货场景中，无人机首先对拍摄的视频流进行预处理。这些计算任务在经过预处理后按照一定的调度算法调度到边缘服务器中执行，经过姿势识别和人脸识别确认和定位目标收货人，并将信息实时反馈给无人机。

1.2 端边协同的并行任务处理框架

为了降低任务处理时延，提高无人机的配送效率，本文基于1.1节提出的渐进式任务调度模型，构建了一个基于端边协同的并行任务处理框架，如图2所示。这里的“并行”主要体现在以下两方面：

(1) 多边缘服务器并行处理任务 相比于传统的串行计算架构，多个边缘服务器能够并行处理来自无人机的计算任务。在实际的收货场景中，一旦出现了收货人，在某一小段视频流的连续的若干帧中都能够通过人脸识别算法判断出收货人。根据并行任务处理的特点，由这若干帧所形成的任务就会被卸载调度到就近的若干边缘服务器中。从整个网络环境来看，多个任务在若干边缘服务器中并行执行，相比多个任务只在单个边缘服务器中执行具有更高的系统效率，边缘服务器之间的协同计算也能够充分降低任务的处理时延。

(2)多个任务在边缘服务器内并行处理 虽然边缘服务器的计算资源有限，但是可以在考虑任务负载的前提下，在同一边缘设备内并行处理多个计算任务。在传统的串行任务计算架构中，边缘设备虽然只需保证其计算资源大于所有任务的最大负载，但并不是所有的任务都能达到边缘设备的最大负载，这将导致计算资源剩余、利用率不高的问题。而将这些任务并行处理，虽然可能会降低每个任务的处理速率，但是基本不会出现计算资源剩余，从而能够大大提高计算资源的利用率，任务处理速率自然也会随之提高，整个端边协同的并行任务处理框架就能够有效地降低时延，提高定位收货人的速度。

1.3 任务处理时延建模

根据1.1节中设计的渐进式任务调度模型和1.2节中构建的端边协同的任务处理框架，下面给出任务处理总时延的计算方式，并对一些量进行定义和说明。

根据1.2节提出的端边协同的并行任务处理框架，考虑在无人机最后一公里配送场景中，有m架无人机Ui,i∈[1,m]，以及n台边缘服务器Ej,j∈[1,n]。假设在给定视频帧数的情况下，整个端边协同的并行任务处理框架中将产生N个任务。现在考虑这些任务中的第t个任务(t∈[1,N])。需要通过定义一些指标及其计算方式，来度量该任务处理总时延。根据1.1节中介绍的渐进式任务调度模型，一个计算任务的执行总时间主要由以下5部分构成：任务在无人机中的预处理所花费的时间Tuav、任务预处理完成在发送队列中等待到卸载所经过的时间Toffload、任务的传输时延Ttrans、任务卸载到边缘服务器进入就绪队列后的等待时间Tready以及任务在边缘服务器执行的时间Tedge。于是，第t个任务的处理总时延为：

(1)

(2)

式中:Ft表示任务t所包含的图片对应的原始视频帧的数据大小,它是根据原始视频的分辨率换算成像素，然后按照每个像素3通道，每像素每通道1字节的方式进行计算;fuav表示无人机的处理速率。

同理，在式(1)中，第t个任务在边缘服务器执行的时间也需要按照类似的公式计算：

(3)

式中：Ct表示任务t的计算量；fedge表示边缘服务器的处理速率。

在式(1)中，第t个任务的传输时延具体表示如下：

(4)

式中：dt表示第t个任务的数据大小，即原始视频帧经过预处理后所得图片的数据大小；B表示带宽。

2 基于最短响应时间优先改进的任务调度算法

为了满足无人机最后一公里配送场景的实时性需求，第1章给出了渐进式任务调度模型，设计了端边协同的并行任务处理框架。然而，多边缘服务器的协同与多任务并行处理带来了新的挑战，增加了网络的不确定性。因此，传统的移动边缘计算环境中的任务调度算法可能因为网络的波动而变得不稳定。为此，本文参考移动边缘计算环境中SSLF调度算法[15]，并针对该算法优化了预计响应时间的更新策略，设计了改进后的α-SSLF调度算法。

(5)

SSLF调度算法每次在进行任务调度时会查找卸载该任务的无人机Ui，根据表P中的向量Pi，找到预计响应时间最小的边缘服务器Ej，将任务调度到该边缘服务器上。

然而，在实际的网络环境中，因为一些不确定的因素会导致网络的波动，频繁的、剧烈的网络波动会破坏SSLF调度算法的稳定性。为了防止极个别任务的处理时延过大或者过小而导致表T频繁地更新，本文引入参数α，在更新预计响应时间的同时兼顾表T中原来的预计响应时间。

(6)

式中α是一个给定的值，α∈[0,1)。当α=0时，表示直接根据当前已经完成的任务的响应时间更新预计响应时间，这与传统的SSLF调度算法一致。α越小，表示新的预计响应时间受当前已经完成的任务的响应时间影响越大，而受原来的预计响应时间影响越小；α越大，则反之。

改进后的预计响应时间更新策略如下：

算法1改进后的预计响应时间更新策略。

输入:预计响应时间表P，当前任务t，参数α;

输出:更新后的预计响应时间表P。

1 Tresp=当前任务t的响应时间

2 Ui当前任务所属的无人机

3 Ej=当前任务调度到的边缘服务器

5 returnP

与SSLF调度算法一样，α-SSLF调度算法每次也按照相同的规则找到向量Ti，进而找到预计完成时间最小的边缘服务器并将任务调度到该边缘服务器上。与SSLF调度算法不同的是，α-SSLF调度算法在更新和维护表P时，需要按照式(6)进行更新。改进后的α-SSLF调度算法如下所示：

算法2改进后的α-SSLF调度算法。

输入:预计响应时间表P，当前任务t;

输出: 当前任务调度到的边缘服务器Ej。

1 Ui=当前任务t所属的无人机

2 j=find_min_index(Pi)

3 returnEj

新引入的参数α既反映了网络的实时性，又保证了调度算法的稳定性。改进后的预计响应时间更新策略兼顾了预计响应时间表P原来的值，避免了因突然的、剧烈的网络波动而引起的表P的频繁更新，使得α-SSLF调度算法相比于传统的SSLF调度算法具有更好的稳定性。实际上，当网络状况不佳且持续了一段时间时，传统的SSLF调度算法和α-SSLF调度算法的更新策略都可以让表P的相应数值增大，进而迫使调度算法改变调度策略。而当网络状况不佳仅只有一瞬间时，传统的SSLF调度算法会立刻改变调度策略，而α-SSLF调度算法并不会立刻改变调度策略，而是可能会再等待一小段时间确认当前网络状况是突然的波动还是持续的不佳。因此，改进后的α-SSLF调度算法具有很好的稳定性，可以避免因网络的短暂波动作出错误的调度决策。

3 实验和结果分析

本文提出的基于端边协同的并行任务处理框架能够充分降低任务的处理时延。通过改进SSLF算法，综合考虑了网络波动的影响，可以在无人机最后一公里配送场景中找到最优的任务调度方案。本章首先描述了实验的仿真环境和参数设置，然后对比了传统的串行任务处理框架和本文提出的基于端边协同的并行任务处理框架在任务处理时延方面的优劣，证明了并行任务处理架构在任务处理时延方面的优越性。最后，在端边协同的并行任务处理框架中，对比了传统的SSLF调度算法和改进的α-SSLF调度算法，从任务处理平均时延和最大时延两个方面进行了综合评价。实验证明，当参数α取得合适的值时，本文提出的α-SSLF调度算法可以取得显著的效果。

3.1 实验环境及参数设置

本文仿真实验均运行于PyCharm 2020.1 Version，Python3.6环境。硬件参数为IntelCorei5-6200 2.40 GHz CPU，12 GB RAM。实验所采用的视频流通过大疆无人机在安徽大学校园内拍摄，并且指定其分辨率分别为360 p、480 p、720 p和1 080 p。针对每一种分辨率的视频流，截取其100帧、200帧、300帧和400帧分别作为仿真实验中无人机的输入。根据第2章提出的α-SSLF调度算法，α的取值集合为{0,0.25,0.375,0.5,0.625,0.75}。仿真实验的网络环境为100 Mbps带宽，实时的数据率为小于100 Mbps，并且服从正态分布的随机值[16]。

3.2 实验结果与分析

为了证明本文提出的渐进式任务调度模型和端边协同的并行任务处理框架可以充分降低时延，提高无人机配送效率，本节首先对比了传统的串行任务处理架构和端边协同的并行任务处理架构在任务处理总时延方面的优劣，证明了并行任务处理架构在任务处理时延方面的优越性。本节还对比了传统的SSLF调度算法和改进的α-SSLF调度算法。结果表明，参数α取得一定的值时，改进的α-SSLF调度算法在降低任务处理时延的同时，可以有效地防止短暂的网络波动带来的影响。

第一部分实验按照视频流的分辨率分组，并采用传统的SSLF调度算法，对比在视频帧数不断增大的情况下，传统的串行任务处理框架和本文提出的端边协同的并行任务处理框架的优劣。该部分实验针对单架无人机Ui,i∈[1,m]，测量其从开始预处理一段给定长度的连续视频帧到周围所有边缘服务器{Ej|j∈[1,n]}都处理完因其产生的任务所经过的总时间，将之作为该部分实验的评价指标。根据传统的串行任务处理框架的特点，该部分实验设置整个移动边缘计算环境只有一台边缘设备，并且不支持多任务的并行执行。而根据本文提出的端边协同的并行任务处理框架的特点，该部分实验设置移动边缘计算环境中存在4台边缘设备，且其中2台边缘设备的最大负载为同时执行4个计算任务，另外2台边缘设备的最大负载为同时执行3个计算任务。

实验结果如图3所示，可以看到，本文提出的端边协同的并行任务处理框架在不同帧数和不同清晰度的情况下，效果均优于传统的串行任务处理框架，可以减少约20%左右的处理时延。分辨率较小的360 p因其原始视频帧数据量小，最终两种计算架构的处理总时延相差并不大，总时延平均相差14.38%。而分辨率较大的1 080 p因其原始视频帧数据量庞大，基于端边协同的并行任务处理框架的优势更为明显，总时延平均相差33.91%。因此，相比于传统的任务并行计算架构，本文提出的基于端边协同的并行任务处理框架能够有效地降低一段视频流产生的任务处理总时延，并且视频流的帧数和分辨率越高时，效果越明显。

第二部分实验探究α的取值对本文提出的改进的α-SSLF调度算法在端边协同的并行任务处理架构中对任务处理时延的影响。实验首先给定视频流的帧数为100，改变视频流的分辨率，对比α不同取值下的任务处理时延的优劣；其次给定视频流的分辨率为1 080 p，改变视频流的帧数，对比α不同取值下的任务处理时延的优劣。

实验需要用到所有任务处理总时延的最大值和所有任务处理总时延的平均值两个评价指标。根据木桶效应，一段给定长度的连续的视频帧的处理时延很大程度上取决于其产生的所有计算任务中处理时延最大的任务。因此，所有计算任务的最大处理时延是一个有价值的评价指标。而在实际的无人机最后一公里配送场景中，并不是所有的任务最终都能够识别到收货人姿势，进而校验其人脸。换言之，很大一部分计算任务因为没能识别出收货人的姿势而被丢弃。因此，所有计算任务的平均处理时延也同样重要，这更能够反映出整个系统的任务执行效率。

当视频流的帧数不变时(均为100帧)，改变视频流的分辨率，在α取不同值时平均任务处理总时延和最大任务处理总时延如图4所示。仅从平均任务处理总时延来看，当α=0.5时，平均任务处理总时延较优。仅从最大任务处理总时延来看，当α=0.5时，最大任务处理总时延较优。虽然平均任务处理总时延和最大任务处理总时延并不只有一个最优点，但综合两种指标来看，当α=0.5时，对于不同分辨率的视频流都能有较好的降低时延的效果。

从任务处理总时延的平均值的大小来看，α取不同值时，其极差大约在10～50 ms。同理，从任务处理总时延的最大值的大小来看，α取不同值时，其极差大约在10～20 ms。在实际的无人机最后一公里收货场景中，对收货人的快速定位是整个系统所要实现的首要目标。在一个计算任务中，平均能够优化10～50 ms的处理时延，最大的处理时延也能优化10～20 ms，这对需要执行大量计算任务的整个系统来说至关重要。这不仅能够提升用户的收货体验，还能够提高整个端边协同的系统工作效率。

当视频流的分辨率不变时(均为 1 080 p)，改变视频流的帧数，在α取不同值时任务平均处理总时延和最大处理总时延如图5所示。仅从平均任务处理总时延来看，当α=0.5时，平均任务处理总时延普遍较优；仅从最大任务处理总时延来看，虽然当α=0.5时，最大任务处理总时延在少数情况下并不是最优的；综合两种指标来看，当α=0.5时，对于不同帧数的视频流都能有较好的降低时延的效果。

综上所述，本文提出的基于端边协同的多边缘服务器并行任务处理框架在处理时延上优于传统的串行任务处理框架，在此基础上采用改进后的SSLF调度算法在α=0.5时可以在确保算法稳定的前提下充分降低任务处理时延，提高无人机配送效率。

4 结束语

本文研究了基于MEC的无人机最后一公里配送场景中复杂任务的调度问题，构建了端边协同的并行任务处理框架来模拟任务调度的执行过程，包括计算负载、传输时延等。考虑到网络波动的问题，根据已有的最短响应时延优先(SSLF)调度算法，优化了响应时延的更新策略，解决了因网络波动而产生的调度算法不稳定的问题，可以大大减少任务的响应时间，提高无人机配送的效率。本文在仿真的端边协同的并行任务处理框架上进行了实验，结果表明改进后的α-SSLF算法可以有效降低任务的平均响应时间，具有良好的稳定性，提高整个无人机最后一公里配送系统的效率。

本文初步提出了基于端边协同的并行任务处理架构，后续还将在此基础上进一步优化该系统架构。未来将加入更多的调度算法进行对比，并对其中效果不好的调度算法进行优化和改进。另外，对于无人机配送场景中可能产生的其他实际问题也会进一步展开研究。