基于移动边缘计算的任务调度算法设计

高素林，张盈希，任奕菲，冯光升

(哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨150001)

0 引言

随着互联网和智能设备的普及，人们享受着网络和智能设备带来的便捷。同时智能设备上的应用程序对于计算资源的需求越来越高,云计算的出现解决了计算资源受限的问题，却未能提供低延迟的服务[1-2]。随着移动边缘计算的兴起，智能设备将资源密集型任务迁移到移动边缘计算(Mobile Edge Computing,MEC)服务器上执行以缓解自身资源受限问题并获得低延迟的高质量服务。边缘计算从最初的薄云计算[3]演变到如今的MEC，不断地靠近用户，建立MEC服务器[4]为用户提供高质量服务。所以MEC有着边缘部署、临近用户、低时延和高带宽[5]等特点。据调查研究，预计到2030年全球的智能设备数量将达到180亿[6]。MEC服务器的计算资源相对于如此庞大数量的智能设备也变得相对有限，如何对大量的任务进行有效调度变得十分重要。

对于调度问题，早期的研究对于时延和能量的消耗考虑较少，大多是将庞大的计算任务调度到MEC服务器中执行[7]，计算资源利用率和调度的效率都比较低，导致服务质量较差。在近期的研究中，多用户场景、智能设备和服务器计算资源相对有限、任务时延要求较高等问题得到更多的关注。研究者们将任务分割[8]，考虑任务优先级、资源分配、功率调整等因素，提高了任务调度的效率和MEC服务器计算资源的利用率[9-11]。任务调度问题相关研究的主要目的是为了降低任务时延和提高服务器计算资源利用率，通过提高服务器资源利用率可将更多的任务调度到服务器上执行，从而降低智能设备的能量消耗[12-13]。

Liu等人[14]研究了在多用户场景中以任务优先级和空间限制为约束，以服务器资源利用率为优化目标的任务调度问题，提出了一种任务卸载调度器——Horae，Horae有效提高了资源利用率并且降低了所有任务的时延，但服务器和智能设备可能因此消耗更多的能量。Liu等人[15]以降低平均执行时延为优化目标使用马尔科夫决策过程来解决任务调度问题，该研究以任务调度系统的功率为约束提出了一种一维搜索算法来找到最佳任务调度策略，但时延较长的任务可能不会被调度到服务器中执行，造成智能设备消耗更多的能量。Tseng等人[16]在网关处建立了边缘计算节点，实行按需分配的资源分配策略减少了传输延迟的同时提供高性能服务，探究了如何部署边缘计算服务器以及如何将用户智能设备上的任务调度到服务器上执行从而提高服务质量，对于如何部署MEC服务器并完成任务调度有很大的借鉴意义，但是对于用户智能设备的能量消耗问题考虑得不足。Chen等人[17]研究了混合能量供应的异构MEC中的任务调度和能量管理，联合优化任务调度和能量管理以最大程度提高MEC服务器的资源利用率，文中还提出了在线任务调度和服务器能量管理算法，该算法能得到近似最大化的MEC服务器资源利用率，但更多的关注在于MEC系统集成了能量收集模块后对能量的管理。Yan等人[18]研究了在不确定运行时间和不稳定通信条件下的节能任务调度问题，将β分布的通信速率和不确定运行时间下的任务调度问题转换为一个整数规划问题并建立模型，这个模型的优化目标为最小化服务器能量消耗，最后提出EASE启发式算法来解决任务调度问题。Saleem等人[19]解决了MEC中基于移动感知的任务调度和资源分配问题，提出了一个移动感知任务调度算法，并使用遗传算法和移动感知任务调度算法来解决任务调度问题，文中更多关注智能设备的移动性，而对用户智能设备的能量消耗考虑不足。

本文对多用户场景下的任务调度问题进行研究，以时延和任务依赖性为约束条件，以智能设备最小化能量消耗为优化目标建立了优化模型，通过对优化模型进行求解得到调度策略。仿真实验结果表明算法在满足时延和任务依赖性约束的同时，有效对智能设备上的任务进行调度。算法充分利用了MEC服务器计算资源,同时更大程度地降低了智能设备整体的能量消耗，有效缓解了智能设备能量受限问题，提高了服务质量。

1 系统与计算模型

1.1 系统模型

假设有m个智能设备，用集合M={1,2,3,…,M}表示。每个智能设备会生成n个任务，用集合N={1,2,3,…,N}表示。这n个任务之间存在依赖性约束，即先生成的任务需先运行结束，后续的任务才能开始运行。并且每个任务均有时延要求，任务必须在特定时间内完成才不会影响整体任务的运行和用户体验。对于任务密集型任务往往需要大量的计算资源(CPU计算频率、内存和电池容量)，而由于智能设备的计算资源有限，所以需要将一部分任务密集型任务迁移到MEC服务器上运行。

假设有一台MEC服务器，它的CPU频率为fc，其他计算资源(内存、电池容量)可视为无限大。智能设备通过网络与MEC服务器建立连接后可将任务迁移到MEC服务器上运行，而MEC服务器相较于大量的来自智能设备的任务，它的CPU计算频率也相对有限。所以MEC服务器需要对这些任务进行调度，即决定这些任务是否能迁移到MEC服务上运行、何时运行。

1.2 计算模型

1.2.1 本地计算模型

任务在本地执行的时间消耗为：

任务在本地执行的能量消耗为：

1.2.2 服务器计算模型

因为视MEC服务器的能量是无限的，所以任务在MEC服务器上的能量消耗不计，只考虑任务执行的时间消耗。此时间消耗为：

1.2.3 数据传输模型

任务在传输过程中的时间消耗为：

任务在传输过程中的能量消耗为：

2 能量消耗模型与任务调度问题

2.1 任务的时延约束

2.2 任务的依赖性约束

2.3 能量消耗模型

任务调度的最小单位为单个任务，所以对于任一任务只有被调度和不被调度两种结果。任务被调度则迁移到MEC服务器上执行，反之则在智能设备上执行。任务的调度结果用am,n∈{0,1}表示，am,n=1表示任务被调度，反之则表示不被调度。如果任务被调度到MEC服务器执行，能量消耗为数据传输产生的能量消耗。如果任务不被调度到MEC服务器执行，能量消耗为本地计算产生的能量消耗。设Em,n表示智能设备m的任务n的能量消耗，则任一任务的能量消耗可以表示为：

设所有连接到任务调度系统的智能设备的整体能量消耗为E，则E可以表示为：

2.4 任务调度问题

在任务调度问题中需要确定哪个任务可以被调度到MEC服务器中执行，任务能否被调度到MEC服务器中执行取决于时延约束和任务依赖性约束，此外还需考虑智能设备的能量消耗问题。所以多用户场景下的任务调度问题可以转换为一个以任务时延和依赖性为约束条件，以最小化整体能量消耗为目标函数的优化问题：

s.t.∀m∈M,∀n∈N,

C3:am,n∈{0,1},

式中,A表示所有任务的调度决策，A={am,n|m∈M,n∈N}。约束C1是时间延迟约束,约束C2是任务依赖性约束,约束C3是对调度决策的约束。

3 问题求解与算法设计

因为智能设备持续生成任务并持续迁移到MEC服务器上执行，而任务具有时延约束需要尽快得到合理的调度。所以很难得到一个较长时间段内智能设备整体的能量消耗最小值，只能将较长的时间段分割成若干个较小的时间段，以较小时间段内的能量消耗最小值累积得到较长时间段内的近似能量消耗最小值。

3.1 优化问题求解

将较长的时间段分割至极小，即每当有任务迁移请求达到MEC服务器就对该任务进行一次调度。因为迁移到MEC服务器上执行的任务较多，所以会有一部分任务在MEC服务器中等待被执行。当新任务到达时对新任务和等待执行的任务进行调度操作(可能改变执行的顺序或之前的调度决策)。设总共进行Y次调度，每次调度后产生的能量消耗为ΔEy。

假设，新到达的任务来自智能设备m上的任务n。如果新任务不被调度，则ΔEy等于在智能设备上执行产生的能量消耗，可表示为：

如果新任务被调度且等待执行的任务调度决策没有被改变，则ΔEy等于在MEC服务执行所产生的能量消耗，可表示为：

如果新任务替换了之前被调度的任务，则ΔEy等于新任务在MEC服务器上执行产生的能量消耗加上被替换的任务回到智能设备执行产生的能量消耗，设被替换的任务来自智能设备i上的任务j，则表示为：

所有连接到MEC服务器的智能设备的整体能量消耗可看作所有操作产生的ΔEy之和，可表示为：

因此OP1可以放缩为：

针对每个任务的调度问题可以表示为：

s.t.∀m∈M,∀n∈N,

C3:am,n∈{0,1}。

3.2 实时调度算法

该问题中每次只对一个新到的任务进行调度，复杂度相对较低。因为等待执行的任务都是被调度过的，所以它们的相对顺序不会被改变。新到的任务只能被插入到队伍列(队列中间或队列末尾)或替换其中某个等待执行的任务。而等待执行的队列中只有队尾的一部分任务可以被替换或被“插队”，因为队伍前的任务即将被执行或有极大的可能性被再次调度后不满足时延要求，因此找到可行解并找到最优解的复杂度并不高，可以将新到的任务从队列末尾依次往前“插队”找出所有可行解，并在可行解中选择最优解后完成调度。为了充分利用时间资源，如果存在多个相同的最优解，则选择靠近队列头部的调度方式。

实时调度算法可表示为：对于新到的任务x和等待队列K。

① 将x放置到队列末尾，检查x的约束条件是否满足，若满足则记录下该可行解；

② 针对队列中的任务k从队列尾部至队列头部依次向前重复步骤③和步骤④，直至步骤③和步骤④均未得到可行解；

③ 尝试将x插入到k之前，如果x和k及k以后的所有任务均满足时延约束和依赖性约束，则记录该可行解；

④ 尝试将x替换k，如果x和k及k以后的所有任务均满足时延约束和依赖性约束，则记录下该可行解；

⑤ 如果有可行解则选择其中的最优解，如果存在多个最优解则选择最后获得的最优解，如果不存在可行解则新到的任务x不被调度。

3.3 遗传算法

因此OP1可以放缩为所有较小时间段内的最优解之和：

因此较小时间段内的调度问题可以表示为：

s.t.∀m∈Mx,∀n∈Nx,

C3:am,n∈{0,1}。

对于调度策略Ax，Ax={am,n|m∈Mx,n∈Nx}，Ax是一串由0或1组成的二进制编码，将此编码作为遗传算法的基因编码，使用对应调度策略的能量消耗的倒数作为个体的适应值，即可使用遗传算法对该问题进行求解。

4 实验

仿真实验模拟了20台智能设备与一台MEC服务器。智能设备以一定的速率和概率生成任务，这些任务的工作量、时延要求是不一样的，但是在合理的范围内。为了更逼真地模拟真实场景，实验中存在许多随机因素(任务生成的概率、任务工作量和任务时延要求)，所以每次实验是唯一的、不可重复的，因此同时使用遗传算法和实时调度算法分别进行调度以对比两种算法的性能。实验中各参数设置如表1所示，参数设置参考文献[9]。

表1 实验的参数设置

4.1 任务到达速率对算法性能的影响

该实验将探究在不同的任务到达速率的情况下遗传算法和实时调度算法的性能。该实验在合理的范围内随机生成了200个任务，使用不同的速率到达MEC服务器。共进行7组实验，每组实验仅到达速率不同。通过控制任务到达的时间间隔实现不同的到达速率，如时间间隔为50 ms则表示每秒到达20个任务。实验结果如图1所示，随着任务到达速率的降低，经过两个算法进行调度后能量消耗均有所降低，意味着更多的任务被调度到MEC服务器上执行。当任务到达速率较高时，大量的任务竞争MEC服务器计算资源。而MEC服务器计算资源较为有限，所以很多任务不能被调度，造成了更多的能量消耗。当任务到达速率较低时则相反。

图1 不同任务到达速率对算法性能的影响

由图1可以看出，实时调度算法的性能优于遗传算法。遗传算法优化的是较小时间段内到达的所有任务，而实时调度算法优化的是每个任务到达后的调度操作，更大程度地提高了计算资源的利用率和调度效率，使得更多的任务被调度。此外实时调度算法在不用任务达到速率情况下的性能仍受响应时间的影响，如图2所示,图中的平均响应时间为所有响应时间之和与响应次数之比。

图2 不同任务到达速率对算法响应时间的影响

由图2可以看出，随着任务到达速率降低，两个算法的平均响应时间均降低。因为单位时间到达的任务数量减少了，算法调度的复杂度有所减低使得平均响应速率降低。而当任务到达速率较高时遗传算法的性能受到很大影响，因为遗传算法每次调度的任务数量较多，算法复杂度较高，导致平均响应时间较高，从而导致了对时延要求较高的任务错过了有效时间。而实时调度算法的平均响应时间受任务到达速率的影响较小，当任务到达速率降低至一定程度后两个算法拥有相同的平均响应时间。

4.2 任务工作量对算法性能的影响

工作量决定任务执行需要的时间，从而对调度决定造成影响，该实验探究不同工作量情况下两个算法的性能。该实验中生成了200个相同工作量的任务，这200个任务其余的参数均在合理范围内随机生成。任务以相同的速率到达MEC服务器，到达速率选取为5个/s，由上一个实验可知再次到达速率下两个算法的性能同样好。共进行10组实验，每组实验中的任务除工作量外均相同。实验结果如图3所示。

图3 不同工作量对算法性能的影响

由图3可知，随着任务工作量的增加，两个算法所对应的能量消耗与工作量之比均上升，即算法性能降低。当工作量足够小时，两个算法的性能达到最佳。因为工作量足够小，任务所需的计算资源少，所有的任务都被调度到MEC服务器上执行。随着任务工作量的增加算法性能迅速下降，性能下降速率逐渐降低，而当工作量达到一定值时两个算法性能均达到最差，因为任务工作量过大，对计算资源的需求很高，所以绝大部分的任务没有被调度。随着任务工作量逐渐增加，任务对计算资源的需求也随之增加，任务之间对计算资源的竞争更加激烈，而后激烈程度逐渐降低，所以算法性能降低的速度先快后慢。

由图3可以看出，实时调度算法的性能优于遗传算法的性能，性能下降的速率也较低于遗传算法。因为实时调度算法提高了对计算资源的利用率，使得更多的任务被调度到MEC服务器上执行。

4.3 任务时延要求对算法性能的影响

任务时延要求决定了任务是否应该被先执行，也影响着调度决策。任务时延要求为除去任务执行所必需的时间(以任务本地执行的时间为必需时间)外可等待的、延迟的时间。该实验将探究不同的任务时延要求对算法性能的影响，实验生成了200个任务有相同时延要求的任务，这200个任务其余参数均在合理范围内随机生成，以5个/s的速率到达MEC服务器。共设计10组实验，每组数据除时延要求外均相同，实验结果如图4所示。

图4 不同时延要求对算法性能的影响

由图4可以看出，任务时延要求对遗传算法的影响较小，但是能量消耗总体呈现下降趋势。而实时调度算法受任务时延要求的影响较大，能量消耗总体呈现上升趋势，但是上升幅度较小。任务时延要求的时间越长，被调度的可能性越高，所以遗传算法的能量消耗总体呈现下降趋势。任务时延要求的时间越长相对于先到达的任务是有优势的，大部分任务被调度。但是会导致等待执行队列逐渐变长，这对后到的任务并不有利，甚至导致一部分任务不被调度，所以遗传算法的性能提升较小。因为等待执行队列过长，实时调度算法可利用的资源减少了，所以算法的性能反而有所下降。但是总体来看实时调度算法的性能仍然优于遗传算法。当任务时延要求的时间增大到某个数值(图4中A点)时所有的任务都能被调度，所以两个算法的能量消耗会稳定在某个值。

4.4 实验分析

本节探究了多种因素对算法性能的影响，从实验结果可看出实时调度算法在高并发和高时延要求情况仍能保存良好的性能，且始终优于遗传算法，主要有以下两个原因：一是实时调度算法的复杂度比遗传算法复杂度低，每增加一个任务，遗传算法增加的处理步骤是实时调度算法的几十倍，使得有些任务没能被及时处理而错过了有效调度时间；二是实时调度算法对计算资源的利用率更高，实时调度算法通过“插队”和“替换”方式更大程度地利用计算资源，提高计算资源的效用。

5 结束语

本文研究了MEC中多用户场景下的任务调度问题，分析了有效解决任务调度问题的必要性。通过分析场景特性建立任务调度问题的优化模型，并依据任务调度的实时性将该优化问题分别放缩至两个较小规模的优化问题。使用遗传算法和实时调度算法进行求解得到任务调度策略。通过仿真实验，验证了实时调度算法的可行性，测试了多种环境下算法的性能优势。实时调度算法在有效实现任务调度、保障服务质量的同时降低了智能设备整体的能量消耗，即使在高并发和高时延要求等情况下仍能保持良好的性能。在未来的研究中，拟考虑更大规模(任务数量更多、智能设备更多、MEC服务器数量更多)的任务调度问题，在大规模场景下继续完善优化模型及算法。