基于混合蚁群优化的边缘计算细粒度任务调度方法

陈 刚,王志坚

(广州华商学院 数据科学学院,广州 511300)

0 引言

云计算为客户端提供了海量的可以访问的数据资源以及计算资源，因此每时每刻都有大量的用户向云平台提交任务申请，而云平台也需要根据申请来处理这些任务。面对用户申请的大规模任务，云平台原有的网络架构出现了较为严重的时延问题[1]。为此，近年来边缘计算的观点被提出来。边缘计算旨在分担云计算中心的任务处理压力，提高服务质量。然而，由于边缘计算节点的资源和计算能力都是有限的，它只能处理少量的部分任务。面对这种情况，如何合理地将任务调度给对应的边缘节点[2]，成为了新的难题问题。造成任务调度困难的原因有二个，一是边缘节点距离云计算中心的距离不同，距离越远，任务调度所耗费的时间和能耗就越多；二是不同任务所需要的计算资源是不同的，若是将小任务调度给计算能力很强的边缘节点上，将造成资源浪费;反之，边缘计算因为能力不够，将无法处理任务，服务质量受到严重限制[3]。所以如何根据任务的特征以及边缘节点的计算资源、距离，将任务合理地调度给合适的边缘计算节点至关重要。

国内外针对边缘计算的任务调度都进行相关研究。文献[4]首先将计算任务描述为一个有向无环图，然后将系统的延迟作为优化目标，并在截止期限、优先级、节点完成期限等三个约束条件下，利用改进的NSGA-Ⅱ算法求解获取了任务卸载调度方案。文献[5]以系统总开销为优化问题，并将其细化分为三个子问题，以方便求解，利用自适应遗传算法对其逐一求解，得到综合任务调度卸载方案。文献[6]以任务满意度最大化为目标，将多个任务调度到边缘服务器上配置的虚拟机上，利用深度强化学习解决了时间调度和资源分配的问题。文献[7]提出了一种基于烟花模型的调度方法，首先采用焰火视图来搜索资源，以满足任务的功能需求，然后根据任务相关性和资源对任务进行分包，最后通过构建三维空间距离来计算任务包与资源之间的匹配度。上述调度算法在时间延迟和调度能耗上都不是很理想，需要采用新型智能算法对边缘计算的任务调度进行改进与优化。

边缘计算任务调度是一个大规模且复杂的问题，单一的蚁群算法的优化能力并不能很好地应对，因此，本文将基础蚁群算法与遗传算法相结合，实现边缘计算细粒度任务高效率调度，以期为边缘计算任务调度问题提供参考和借鉴。

1 边缘计算细粒度任务调度的原理

边缘计算细粒度任务调度属于一种连续性问题，使用单一的蚁群算法进行调度，容易产生收敛速度慢，计算时间长，易于过早陷入局部最优的问题。为此，本文引入遗传算法，构建混合蚁群算法对细粒度任务调度进行优化，解决单一蚁群算法易于过早陷入局部最优的问题，提高边缘计算细粒度任务调度性能，具体描述如下。

1.1 问题描述

边缘计算任务调度是指将原本应由本地服务器或中心云端处理的任务合理地分配给网络边缘端的服务器节点，以缓解本地服务器或中心云端的任务处理压力，减少任务处理延迟[8-9]。边缘计算任务调度传统模型如图1所示，本文边缘计算细粒度任务调度模型如图2所示。本文调度模型分为底部的终端设备层和上端的边缘层。终端设备层主要包括客户端中用到的手机、平板电脑等，其中一部分会产生计算密集型任务，这些任务无法在本机设备提供的资源下完成任务，需要为其制定合理的调度策略将任务迁移到合适的地方，可以在满足任务时延要求的情况下完成任务。终端设备层的另一部分设备由没有任务处理的闲置终端用户组成。在某些时刻其CPU处于闲置状态，可以为其他CPU过载的终端用户提供计算资源。

图1 移动计算任务调度的传统模型

图2 现代移动边缘计算任务调度模型

由图2可知，每个边缘服务器都带有一个基站，其作用是接收发送过来的任务，当任务处理完成后再将处理结果通过基站发送给移动用户，完成任务调度[10]。

1.2 移动边缘计算任务调度的总体架构

移动边缘计算是一种新型移动通信网络技术，在移动网络边缘提供网络环境，将网络大量的任务进行缓存，该技术可以处理比较复杂的网络边缘任务，移动边缘计算具有较好的任务计算能力，可以分析、处理海量网络任务。该移动边缘计算节点在地理位置方面与信息源比较接近，用户发送请求时，网络能快速响应用户的请求，极大地减小了响应的时延，使网络中的数据传输网和核心网络不会发生网络拥塞，移动边缘计算技术还可以实时获取各大网络基站ID、用户的网络数据、用户请求等信息，对网络中的链路可进行有效的感知自适应，为用户在网络边缘处部署位置应用，从而提升网络用户的服务质量。本文采用的基于移动边缘计算总体组成结构如图3所示。

图3 基于移动边缘计算任务调度的总体结构

1.3 细粒度任务调度的原理

移动边缘计算是将网络控制、数据处理和相关存储迁移到网络边缘，为覆盖范围内的移动用户提供较好的密集型计算服务。任务调度方法就是要实现基站与用户之间的互动，在用户密集且流动性大的情况下实现任务合理分配，其多基站协同合作的示意图如图4所示。

图4 移动边缘云服务器任务调度示意图

移动边缘计算任务调度质量取决于边缘基站计算资源的分配。要想实现边缘服务器中的资源公平合理的分配，就要对智能边缘基站进行研究。边缘计算节点为基站调度任务时，主要考虑两个性能指标，分别为数据传输速率和任务执行能耗。通过任务分类合理化的方式提高数据传输速率，将优先级高的任务调度到边缘基站中，优化资源调度程序。除此之外，基站的能耗是一定有的，应在提供能量一定的前提下，让基站能源的总消耗小于所有任务执行任务结束时的总和。

2 边缘计算细粒度任务调度的设计

2.1 假设条件设置

粒度指的是根据项目模块划分的细致程度区分的标准，一个边缘计算任务调度模块划分得越多，每个子模块越小，负责的工作越细致，即所属认为的粒度越细，因此在调度细粒度任务时的难度和能耗比较于粗粒度任务调度更高。通常来说，在细粒度任务调度时，其可以根据自身的需要选择合适的边缘节点进行卸载，但是如何选择合适的边缘节点成为细粒度任务调度时的关键问题[11]。按照以往的调度方案，会选择能耗最少或者延迟时间最短作为目标，选择距离最短的边缘节点进行任务调度。然而，这种调度方案并没有将边缘节点的资源容量考虑在内，会发生任务拥塞问题，导致任务调度失败，而与此同时，边缘网络中有可能存在部分边缘服务器节点闲置的状态，造成了计算资源的浪费[12]。针对上述问题，在任务资源调度前，需要作出几项假设条件。

假设条件1：任务调度时不能只考虑一个边缘节点作为调度对象；

假设条件2：边缘节点的计算资源存在能源耗尽的情况；

假设条件3：边缘网络拓扑已知，且拓扑中每个服务器节点与本地服务器、中心云端的距离是已知的；

假设条件4：每个任务对计算资源的需求都是已知且存在差异的；

假设条件5：边缘节点内部数个虚拟机工作模式为并行；

假设条件6：任务调度过程中为连续执行，不存在间断执行；

假设条件7：任务传输信道的信息是已知的。

2.2 任务调度顺序设计

任务调度器可以获取任务调度的优先级，即完成任务调度顺序设计工作[13]。任务调度器对任务的排序规则是通过计算任务的优先指数，然后从大到小的顺序排列待调度任务[14]。优先指数计算公式如下：

(1)

式中，Si代表细粒度任务i的优先指数；Ai代表细粒度任务i的饱和度；di代表相对权重比；α代表平衡指数；bi代表细粒度任务i执行的截止时刻；ci代表细粒度任务i执行的开始时刻；wi代表细粒度任务i执行价值；W代表细粒度任务总价值；ti代表细粒度任务i执行最长耗时；n代表细粒度任务数量。

基于计算出来的任务优先指数[15]，设计出任务调度顺序方案。

2.3 边缘服务器性能特征分析

边缘服务器受到其自身硬件资源的影响，其计算资源性能具有不同的特征，这就直接影响了对任务的处理能力[16]。为此，通过了解边缘服务器性能特征对于细粒度任务调度至关重要，为调度可靠性和成功率判断提供了重要依据。边缘服务器的性能可以通过静态指标和动态指标两类指标表示，考虑到静态指标对边缘计算细粒度任务调度性能的影响更高，因此，本文重点分析了边缘服务器静态指标。

静态指标表示服务器硬件资源情况的基本性能指标，其主要包括CPU中央处理单元的CPU频率、计算能力等、存储设备的任务数据量、任务达到率等。根据静态指标能够直接明确边缘服务器性能，为细粒度任务调度中边缘服务器节点的选择提供了重要的参考[17]。

2.4 任务调度方案设计

在上述各研究成果的基础上，本章节基于混合蚁群优化设计细粒度任务调度方案，该部分分为目标函数构建，约束条件设置[18]以及混合蚁群优化算法求解三部分。

2.4.1 目标函数构建

细粒度任务调度旨在解决任务调度所需要的能量(能耗)以及任务调度所需要的时间(时延)两个问题。针对这两个问题，本研究中设置的目标函数为多目标函数[19]。函数描述如下：

minY=y1∪y2

(2)

式中，minY代表综合目标最小值；y1代表细粒度任务调度能耗；y2代表细粒度任务调度时延；Qi(1)、Ti(1)代表任务i在本地处理时的能耗、时延；Pi代表调度决策因子，当等于0时，认为任务i在本地处理，当等于1时，任务i执行调度处理；qij代表边缘服务器分配因子，当等于0时，任务i没有被分配给边缘服务器j进行调度，当等于1时，任务i被分配给边缘服务器j进行调度。Qi(2)、Ti(2)代表任务i在边缘节点上处理的能耗、时延；m代表边缘服务器数量[20]。

2.4.2 约束条件设置

为上述多目标函数设置的约束条件如下。

约束条件1：细粒度任务调度时延y2小于任务最迟截止处理时间(最大时延限值)。

约束条件2：边缘服务器性能约束，主要指的是1.4部分的静态指标。

约束条件3：任务只能调度到一个边缘服务器处理，即细粒度任务调度只能在一个边缘服务器j上完成。

3 混合蚁群算法完成细粒度任务调度实现

虽然基础蚁群算法具有并行计算、扩展能力好和较好全局搜索能力等优点，但当达到一定迭代次数后，会出现解趋于一致现象，使得基础蚁群算法呈现收敛速度慢和容易陷入局部最优解的缺点。本文提出的混合蚁群算法采用了遗传算法对数据特征进行预选择，一定程度上克服了基础蚁群算法的上述缺点，可以进一步解决该问题，提高基础蚁群算法的性能，对其初始解的选择方法和信息素更新策略进行改进。

混合蚁群算法是在原有蚁群算法的基础上结合遗传算法，以弥补基础蚁群算法存在的缺陷[21]。本文先利用遗传算法求出多目标函数的初始解，并将其转换为蚁群算法的初始路径信息素分布，最后再执行蚁群算法寻优程序，完成进行任务调度方案求解[22]。针对前面章节描述的目标函数，设置相应的约束条件后，将遗传算法与基础蚁群算法相结合构成混合蚁群算法，求出最优解，即任务调度方案。具体过程如图5(a)和图5(b)所示：

图5 混合蚁群优化算法求解任务调度流程

针对于图5(a)，可以按照下面的步骤与文字进行详细描述。

步骤1：初始化蚁群算法，并设置相关参数；

步骤2：对边缘计算细粒度任务调度问题进行编码处理；

步骤3：定义适应度函数；

步骤4：初始化种群；

步骤5：种群个体解码；

步骤6：计算种群个体的适应度函数值，筛选出优良父代个体；

步骤7：执行遗传算法的操作，得到新一代群体；

步骤8：将新一代群体与父代个体进行优劣替换；

步骤9：得到最终子代个体(多目标函数的初始解)；

步骤10：判断当前的进化代数是否位于最小和最大进化代数之间，且连续进化停滞代数的进化率大于等于最小进化率，若满足上述条件，则进入下一步；否则返回步骤6；

步骤11：将初始解转换为蚁群算法的路径信息素值分布；

至此完成第一部分的多目标函数求解。为了避免使用基础蚁群算法陷入局部最优，因此引入蚁群算法执行边缘计算细粒度任务调度寻优程序，具体流程如图5(b)，可以按照下面的步骤与文字进行详细描述。

步骤1：将m只蚂蚁(任务)任意放置在n个边缘服务器节点上；

步骤2：计算每只蚂蚁的t时刻的转移概率；

步骤3：根据转移概率选择下一个边缘计算细粒度任务调度的边缘服务器节点；

步骤4：更新被选边缘服务器节点的信息素，并将该节点加入到禁忌表中；

步骤5：当每一只蚂蚁均找到一个边缘服务器节点方案后，更新边缘服务器节点的信息素；

步骤6：更新全局信息，清空禁忌表；

步骤7：判断是否达到最大循环次数[23]，若是，输出边缘计算细粒度任务调度方案；否则，回到步骤1，直至达到最大循环次数。至此完成基于混合蚁群优化的边缘计算细粒度任务调度。

4 仿真测试与分析

4.1 仿真测试参数设置

在Intel Corei7 CPU@2.80 GHz，NVIDIA Ge G Force GTX1050Ti 和8GB RAM 配置的工作站中进行调度仿真测试。

目标工作站在图2的调度模型中完成细粒度任务调度，此次测试的应用场景为某地区的交通视频监控。使用边缘计算可以让服务器能够在网络边缘完成对视频流的采集、压缩、存储、检测、显示以及最终的控制等整个监控流程，同时可以解决核心网压力过大无法对其及时转发而造成不连续等问题。

考虑到移动性是边缘计算服务器的固有属性。当用户在小区间切换时，可能会导致服务器的切换，而且不同服务器的属性与配置也存在差异，因此本文通过边缘计算系统与归属位置寄存器的配合实现移动性管理。

具体测试参数如表1所示。

表1 仿真试验参数表

4.2 细粒度任务优先指数计算

按照公式(1)计算100个细粒度任务的优先指数，并组成任务调度队列。其中，前20个任务的优先指数如表2所示。

4.3 混合蚁群算法参数设置

在表1所示的参数下，利用文章提出的混合蚁群算法对1 000个细粒度任务进行调度，测试其收敛性能。该测试通过适应度函数最优值体现，适应度函数越快达到最低点，表明算法性能更好，测试结果如图6所示。

图6 算法收敛速度测试

由图6可知，本文方法适应度函数值在迭代次数为200次时达到最低点，即此时本文方法实现收敛。表明本文方法细粒度任务调度能力较强，能够有效提高细粒度任务调度的可靠性。此时混合蚁群算法的参数情况如表3所示。

表2 前20个细粒度任务优先指数表

表3 混合蚁群算法参数表

4.4 结果分析

4.4.1 能耗和时延分析

相同仿真测试条件下，利用基于改进 NSGA-Ⅱ的调度方法、基于自适应遗传算法的调度方法、基于DRL的调度方法、基于烟花模型的调度方法求解调度方案，并与本文的混合蚁群优化算法做比较，然后同时模拟运行5个任务调度方案，将100个任务调度给10个边缘服务器节点，统计其调度的能耗以及时延。结果如图7和图8所示。

图7 任务调度的能耗

图8 任务调度的时延

由图7可知，在同一基站带宽下，本文方法的任务调度能耗更低，最高调度能耗为基站带宽1.4 kHz时的150 kWh，本文方法调度能耗更低的原因是在调度过程中利用混合蚁群算法根据转移概率选择下一个任务调度的边缘服务器节点，减少了选择带宽时干扰因素的影响。

由图8可知，在前传链路速率一致时，本文方法的细粒度任务调度时延更小，最高时延为5 s，其主要原因是本文方法利用遗传算法优化了蚁群算法，提高了算法的调度性能，避免陷入局部最优。因此，综合图7和图8中可以看出，与其他4种调度方法相比，混合蚁群任务调度能耗和时延均要更小，这也说明本文的调度方法表现更好，所求出的调度方案更为合理。

4.4.2 用户碰撞概率测试

为了进一步验证本文方法的有效性，以不同数量的竞争用户碰撞的概率为测试指标，测试五种方法的冲突概率，如图9所示。

图9 用户碰撞概率测试

由图9可知，五种方法的冲突概率随着用户数量的增加而增加，其主要原因是随着用户数量的增加，用户选择同样的子载波的概率变得更高，因此提高了用户冲突概率。而本文方法在五种方法中，用户冲突概率更低，最高用户冲突概率为0.27%，本文方法用户冲突概率较低的原因是在求解目标函数时，设定了细粒度任务只能调度到一个边缘服务器上处理的约束条件，降低了用户数量增加对边缘服务器带宽造成的影响，减少了用户冲突。同时，当发生较高概率的用户碰撞时，可以增加子信道带宽来减少多用户之间的碰撞概率。通过增加子信道带宽，为任务调度带来了足够大的竞争空间，可以为用户提供更多的选择机会，去选择不同的竞争子载波，从而提供更好的完成细粒度任务调度。

5 结束语

边缘计算支持在网络边缘提供低延迟服务，以缓解中心服务器的压力。然而，边缘服务器上计算资源的有限容量给调度应用程序任务带来了巨大挑战。针对上述问题，本文将遗传算法与蚁群算法相结合，通过混合算法实现边缘计算细粒度任务调度。仿真测试结果证明了其有效性，求出的调度方案更为合理。下一步研究中，将针对不同类型的任务调度、任务卸载等问题进行分析，以提高本文方法的综合性能。