基于任务可分割性的多用户依赖性任务调度策略研究

［张伟 师宝康 刘甫琴］

1 引言

边缘计算作为解决5G 通信网络uRLLC 场景时延过长的杀手锏，它让用户的部分任务卸载到边缘服务器端处理，在一定程度上提升了用户的感知水平。但是边缘服务器的计算存储能力相较于云中心更小，为了优化计算存储资源的利用率，研究用户的任务调度很有必要。目前边缘网络资源管理没有考虑卸载任务存在多用户竞争的因素，从而造成边缘计算资源和传输资源在处理任务时产生的时延具有不确定性的问题。随着用户的增多，任务传输时延和计算时延受到多用户竞争的影响，如何合理调度任务是提高系统性能的关键问题。当前关于任务调度存在三大主要问题：（1）目前研究用户任务调度的研究不少，但是大多数侧重于独立任务[1～3]，也就是认为用户的任务是一个整体，独立用户在服务器与用户调度之间是联合调度的。但在现实中，移动终端通常会将任务分割成多个子任务，任务直接存在时间处理上的依赖关系。（2）目前研究忽视高等级用户的任务动态到达的问题[4,5]，也就是当高等级用户的任务需要插队处理时，如何将高等级用户子任务插入到执行链表队列中，从而满足现实依赖性任务细粒度调度的动态性需求。（3）目前研究没有考虑共享服务器在处理任务时资源的动态变化问题，静态任务调度[6,7]或在线任务调度[8～10]往往导致任务处理时延过大，无法满足用户需求。

为了解决上面3 个问题，本文研究多用户多MEC 服务器场景下，根据任务的依赖关系构建拓扑图和服务器的实际负载，分别计算任务在移动终端和在MEC 服务器上的计算时间，以执行时延最小为目标来执行任务的卸载策略。主要步骤包括：

（1）考虑到用户任务存在依赖性，因此，本文将用户的任务划分割成子任务并形成任务队列，采用强化学习来最大化所获得的累积奖励，将子任务分配到合适的服务器中。增强学习用于动态环境的资源调度策略，以应对服务器计算资源存在变化的时候，处理器发生变化，从而解决由于时延发生变化的问题。

（2）当有新任务出现时，根据任务调度的优先级（用户级别、任务属性、最晚完成时间）采用链表依赖性任务在线滑动调度的方式结合已调度任务的执行时间冗余为新到达的任务寻找合适的执行槽位，当所有任务调度完成时，将每一个任务节点的执行时间设置为最早完成时间，以保证任务的时延需求。

因此，本文在整个系统时延最低目标的基础上，以任务的依赖关系、时延约束以及整个系统的负载均衡为约束，结合任务调度优先级形成灵活的、自适应的任务调度策略，从而实现任务平均响应时延最低。

2 基于任务可分割性的多用户依赖性任务调度策略

2.1 系统模型

随着移动终端的智能化，移动终端能够实现越来越多复杂的应用。当移动终端执行某个应用时，将一个任务拆分成多个子任务，图1 左边1 号终端将任务拆分成7 个子任务。图1 右边时任务调度结果和执行顺序，子任务1 必须在移动终端执行，1 号边缘节点执行子任务2，4，而2号边缘节点执行子任务3，5，6，最后，2 号边缘节点将结果反馈到1 号边缘节点，1 号边缘节点执行结束后将最终结果反馈到1 号终端。系统模型图如图1 所示。

图1 系统模型图

由于本文变量较多，在构建网络模型和计算模型之前，本文将相关的变量以列表的形式给出，具体如表1 所示。

表1 相关变量解释

2.2 网络模型

本文考虑的是移动边缘计算的服务协同问题，图1 显示系统模型，1 号终端在执行某应用时，首先是将该应用的任务进行分割，分割完毕之后，需要对任务进行是否卸载的决策；然后要考虑如何将子任务卸载到哪些服务器的问题；最后还要考虑子任务动态调度的问题，也就是考虑任务的执行方式以及任务调度的优先级。为了对用户任务调度更好的描述，本文用集合N={0,1,2,…,n,…,M}表示移动终端设备、MEC 边缘服务器集合，统一看成为处理单元。其中N={0}表示移动终端。n 代表第n 个边缘服务器，M代表处理能力资源总数。

用集合V={1，2，…，i，…，Q}表示任务集合，其中i 代表第i 个任务，Q 代表任务总数。

用集合U={1，2，…，j，…，P}表示用户集合，其中j 代表第j 个用户，P 代表用户总数。

2.3 通信模型

一旦移动终端执行卸载策略，任务卸载需要考虑任务的传输速率和任务在无线侧的传输时间。假设无线侧上传链路信道的带宽B，高斯白噪音功率；手机终端发射功率G，信道增益参数，假设基站带宽足够并且带宽平均分给该基站的移动用户，得到数据平均传输速率：

其中信道增益参数Hi与上传链路的信道衰落因子h以及终端传输任务起始到结束的平均距离有关。

基于传输速率，得到任务在无线侧的传输时延false：

2.4 计算模型

如果任务选择在本地处理任务，那么基于本地计算能力所产生的时延为：

f υ表示终端处理任务i 所需要的计算资源（也就是终端CPU 芯片的时钟频率，单位是赫兹），Ci表示服务器处理任务i 所需要的计算资源（也就是服务器是CPU 芯片的时钟频率，单位是赫兹），表示终端处理任务i 所需要的时延。如果终端处理任务i 所需要的时延大于业务要求的最大容忍时延那么需要进行部分卸载。变量的任务卸载比例，表示为：

考虑边缘服务器协同的场景，那么一旦卸载或者全部卸载，都满足：

卸载到边缘计算节点，其产生的时延为：

那么，任务i 完成的总时间为：

本文不考虑不考虑有包交互、有线传输时间的时延和子任务处理完回传到终端侧的时延。正如前面所述，我们在任务卸载之前，已经将任务划拆分成多个子任务，每个子任务是可以在不同设备上执行的。因此，本文通过公式8 计算协同服务器中哪一台服务器执行子任务的总时间最大作为任务卸载处理时间。

一旦子任务i 被放置到第n 个处理器时，需要区分前驱子任务和后驱子任务。因此，服务器的选择不仅仅需要依据子任务完成的时延进行资源调度，还要考虑到当前服务器的任务队列，也就是考虑每一个服务器的时间槽最早开始执行的位置。本文按照间隔的大小将服务器的处理器分割成多个槽位，子任务i 在多个边缘服务器内选择合适的槽位进行任务处理，服务器处理时间调度模型如图2 所示。

本文还是以图1 的任务为例，子任务在可选的边缘服务器和时间槽的占用情况，最终选择了2 个服务器节点，那么我们在服务器n 的总时延就是：

公式11 的最后三个公式是指任务分配到服务器n 时，任务i 所需要的CPU 计算资源、存储计算资源和带宽资源都不能大于服务器最大值。

上述情况时没有考虑到动态任务的到达情况，一旦有高用户等级的任务进来，本文采用滑动窗口的方式微调任务节点的时间，将动态到达的任务插入链表队列中，减少调度的开销。

在静态情况下用户的任务资源配置过程，上一个用户任务配置如图2 所示，任务已经分配给两个边缘服务器。这时，有多个VIP 用户将任务卸载到这两个服务器。当有多个VIP 用户的任务动态到达时，上一个用户的任务执行开始时间将会是发生变化的。如果能够调整上述已经安排好时间槽的子任务执行时间，那么VIP 用户很有可能通过“插队”将任务插入执行链表之中。

首先，结合任务的最大时延需求确定已经安排槽位的任务最早允许执行和最晚允许执行的时间，用户执行任务的最早和最晚时间示意图如图3 所示。

图3 用户执行任务的最早和最晚时间

其次，结合新到达用户的子任务调度优先级（VIP 等级和任务类型），对子任务的时间槽位进行灵活调整，采用滑动窗口的方式将已分配的任务最晚时间为原则，对最新到达的子任务插入链表中，充分利用服务器的任务资源，节省调度开销。任务滑动处理后的任务队列示意图如图4所示。

图4 任务滑动处理后的任务队列

最后，将新到达用户的子任务调度优先级（VIP 等级和任务类型）与图3 空白位置的时间槽进行判断，如果上述的时间槽满足子任务处理时延的要求，那么就将其放进空白的时间槽进行处理，否则，再寻找合适的时间槽，不断迭代，直到找到合适的时间槽为止。

3 实验分析

3.1 实验目的

为了验证本文提出的算法，将本文算法与传统的任务调度方法（随机调度）进行未超时任务比例以及任务平均处理时间这两项性能的比较，验证本文算法的依赖性任务调度能够在一定程度上降低任务的平均时延。由于子任务之间存在竞争关系，因此边缘计算节点的处理能力和存储能力是一个动态变化的过程。本文重点验证在处理器数量变化与未超时任务比例和处理器数量变化与任务平均处理时延的变化，以此说明本文算法更加使用动态场景。

3.2 实验仿真与分析

为了评估动态场景下系统的调度策略，实现多用户依赖性任务的自适应调度，本文在中山联通5G 试验网中进行测试，通过模拟多用户的任务请求，以期验证该方法在多用户依赖性任务调度的可靠性。每次测试都是在固定其余参数的情况下，更改其中一个参数。比如，在边缘节点处理器数量固定的情况下，随着任务动态到达数量的变化，计算出不同任务状态下的未超时任务比例与任务平均处理时延；或者在固定任务达到数量的情况下，随着边缘节点处理器数量的变化，计算出不同任务状态下的未超时任务比例与任务平均处理时延。未超时任务比例随着处理器数量的变化关系以及任务平均处理时间随着处理器数量的变化关系分别如图5 和图6 所示。

图5 未超时任务比例随着处理器数量的变化关系图

图5 和图6 展示在随机达到任务数量（任务数量为200）的情况下，处理器数量从5 变化到25 过程中，未超时任务比例和任务平均处理时间随着处理器的变化情况。

随着处理器数量的增多，未超时任务比例的差距越来越大，而任务平均处理时间的差距越来越小。未超时任务比例随着任务数量的变化关系和任务平均处理时间随着任务数量的变化关系分别如图7 和图8 表示。由图7 和图8可知，本文的算法较随机调度的算法性能高，这是因为在每一轮调度过程中，本文算法以任务的依赖关系、时延约束以及整个系统的负载均衡为约束，通过优化服务器任务调度优先级，能够在一定程度降低用户将任务卸载时传输和处理任务时延的不确定性。

在处理器数量（处理器数量为20）确定的情况下，不同算法在任务数量增多的情况下，未超时任务比例和任务平均处理时间的变化情况。随着任务数量的增多，任务平均处理时间的差距越来越大，而为超时任务比例在每一轮的调度中比随机调度算法小得多。由此可知，本文的算法以任务的依赖关系和时延为约束，结合任务调度优先级形成灵活的、自适应的任务调度策略，根据任务数量的变化自适应调整卸载策略，从而降低任务处理时延的不确定性。

图7 未超时任务比例随着任务数量的变化关系图

图8 任务平均处理时间随着任务数量的变化关系图

4 结束语

本文提出一种基于任务可分个性的多用户依赖性任务调度策略。该策略以任务依赖关系，将子任务形成任务队列后，采用增强学习将任务分配到合适的服务器中，解决多用户依赖性的任务调度问题；其次，当新任务出现时，结合子任务调度的优先级，采用链表依赖性任务在线滑动调度的方式实现新到达任务的槽位安排，在保证任务时延需求下提升VIP 用户满意度。相比于传统的随机调度算法，本文的任务调度算法具有更强的移植性以及扩展性。