云计算环境下基于遗传粒子群优化算法的DAG任务调度的研究

蒋卓材 蓝永胜 颜亮

(桂林航天工业学院 网络与信息化管理中心，广西 桂林 541004)

随着计算机软硬件和网络技术的快速发展，计算模式由分散式的计算模式，发展到利用网络技术将独立的计算资源相互连接，协同完成指定任务的网络计算模式，很多计算模式相继被提出，包括网格计算、自主计算、透明计算和云计算等[1]。由于互联网和5G技术的快速发展和部署，云计算服务吸引了人们的广泛关注并在不同场合中大范围应用。云计算采用虚拟化技术对网格计算、并行计算和分布式系统进行了改进和提升[2]，云计算将数据和计算迁移到异构的计算资源中，并通过虚拟化的技术将虚拟服务器对外统一为一个计算资源池，用户通过较低的成本购买计算服务，降低了用户的物理资源的投入和维护，提高了资源的可用性和灵活性，同时降低了用户成本。

任务调度是云计算中的一个关键环节，通过云计算调度平台将计算任务分解成若干个彼此相互联系的子任务。资源调度平台按照一定的调度策略，比如遗传算法、模拟退火算法等调度策略把各个子任务分配到云计算虚拟节点上计算，如何选择和设计一种高效调度策略达到完成时间最短，成本最小，系统利用率提升等目的成为云计算研究的重点之一。

云计算的任务调度问题实质是一类NP问题，但云计算各个子任务之间有很强的相关性和并行性，近年来一些启发式算法和智能算法，如遗传、蚁群等算法运用到云计算领域，设计云计算调度系统要充分考虑云计算资源的环境限制，云计算环境比传统分布式计算环境复杂得多， 针对云计算任务调度特点合理设计任务调度策略和调度算法，合理分配和迁移到相应资源上执行，对提高云计算平台的计算有效性和实用性都具有十分重要的意义。

1 云计算环境下DAG任务调度优化问题

1.1 云计算环境

资源的虚拟化、分布式和动态扩展是云计算的几个主要特点。云计算平台的主要结构如图1所示。用户通过特定的入口访问云计算平台，云计算平台前端模块分解用户任务，生成子任务，并根据相关参数，按照一定的调度策略把相关子任务分解到各个计算子节点进行运行，最终在子任务完成后汇总结果，并将结果返回给用户。云计算平台在系统运行过程中通过任务调度、资源优化分配、软硬件监控和故障维护等方式保证任务和平台的稳定运行。

图1 云计算主要架构

1.2 基于DAG任务调度的数学模型

云计算任务调度即为工作流调度问题，与传统的独立任务的并行执行不同，云计算各个子任务之间具有约束与依赖性，其调度本质就是把并行程序的一组相关任务按照一定调度策略分配到云资源计算节点上进行处理，并安排好每个计算节点上的执行顺序，满足用户对任务执行时间上的相关QoS约束，并获得较好的计算性能。在云计算环境中的任务调度是一类相互之间存在通信和并且相互关联的任务调度，对此类问题，本文采用有向无环图(DAG图)进行数学建模，图2中所示的9个任务的DAG图，每个子任务用一个圆圈表示，箭头表示子任务之间的通信、先后顺序、网络通信开销和约束关系，只有前驱节点完成后，后继节点才能执行。通过高效的调度策略合理调度到每个计算节点上，实现总执行时间最少。

图2 9个子任务的DAG图

2 云计算环境下的DAG任务调度数学模型

云计算平台的任务分解模块会按策略将大型任务分解为若干子任务，子任务之间符合任务运行逻辑，子任务通过DAG进行数学建模，有效的表达子任务之间的先后关系和数据依赖关系。分析DAG图的任务之间的通信量、优先关系和云计算环境下各个节点的计算能力和相互之间的通信成本，将云计算任务调度问题的数学模型(Cloud Computing Task Scheduling Model)定义为CTSM=(M,LC,L,Q,E,C)其中M表示云计算资源节点集合，L表示调度子任务集合，LC表示子任务计算成本集合，Q[n,n]表示约束关系矩阵，Qij表示任务Li和任务Lj相互之间约束关系，任务Li是任务Lj的前驱，只有任务Li完成任务Lj才能执行。E是个云计算节点的处理能力集合。C(Li,Lj)为通信成本矩阵，表示任务Li到任务Lj的通信成本。基于云计算的DAG图任务调度数学模型采用DAG图的深度遍历策略算法，计算每个子任务在计算序列中的深度值，从而获取DAG图子任务之间的约束和先后关系，满足子任务之具有的相关制约和先后执行顺序。

云计算数学建模对DAG图采用深度遍历策略其深度值为

(1)

通过深度值计算，获取子任务约束和先后关系，构建计算节点和资源关系矩阵“MLm×n”,m为计算资源数量，其中n为深度值。

通过高效合理的调度策略，在满足计算节点和资源关系矩阵MLm×n，考虑节点计算能力和网络开销等综合因素的前提下，使得完成任务时间最少。

基于云计算机DAG图T(S)计算模型如

(2)

(3)

因此基于DAG图的云计算任务调度数学模型可以构建为min{T(S)}，其中

T(S)=max{FT(l,m)|l∈L,m∈M}。

(4)

3 云计算环境下DAG任务调度模型的遗传粒子群混合算法

3.1 基于DAG云计算任务算法混合策略

遗传算法(Genetic Algorithm)是模拟达尔文生物进化的自然选择和遗传的特点，通过数学建模的方法自然搜索寻找最优解的算法[3]。算法从最初一个种群开始，通过度量函数，对个体进行编码(编码后的个体变量又称为染色体)和适应度评价计算，不同的个体构成一个种群，通过遗传算法进行运算，对染色体进行重组、变异，产生新的染色体，通过不断的选择、交叉和变异等迭代运算，在种群中找到相对最优解。GA算法具有较强的全局搜索性能，可以整个群体空间进行搜索。并且算法具有并行性的特点，适合用在云环境下DAG数学模型环境下的任务调度，所以把GA算法引入云计算任务调度，作为任务调度的基础性算法。

遗传算法从问题解的解集开始搜索，区别于传统算法从单个初始值开始迭代求解，因此具有很强的全局搜索能力，但同时容易出现早收敛，而达不到全局最优。

粒子群(PSO)算法模拟动物觅食行为特征的群体智能全局随机搜索算法，在算法中单个动物视为一个粒子，每一个粒子由速度决定他的方向和位置，并同最优粒子进行对比，通过不断迭代计算，而在种群中找到最优解[4]。GA算法具有很好的全局和局部搜索能力，但易产生早熟收敛情况，且搜索效率低、收敛慢[5]，粒子群算法搜索效率高，但算法不稳定容易陷入局部最优，结合二者优点，将粒子群算法和思想引入遗传算法中，如图3所示，将粒子群搜索作为遗传算法的变异算子[6]。

把粒子群算法作用于变异的过程，其实是有条件的打破遗传算法的局部最优解的过程。对选择的个体进行变异，完成一次全局的寻优，重新生成新的染色体个体，更新种群的基因信息，有条件的接受新个体解，从而是种群引入新个体的过程。算法保持了群体的多样性，计算过程中爬山能力增强有效地避免了早熟现象。

图3 基于遗传粒子群算法的混合策略图

3.2 云计算环境下基于遗传粒子群算法的DAG任务调度算法设计

算法根据云计算数学模型，先通过等深度DAG算法分解成资源与任务关系矩阵，采用二维二进制染色体编码机制对染色体进行编码，编码体现了云计算任务调度的逻辑合法性，然后通过遗传粒子群算法对种群进行全局寻优生成新种群，并通过不断迭代运算，输出最优调度解。

3.2.1 染色体编码设计

染色体的编码方式有很多种，本文根据云计算DAG任务调度的特点采用二进制矩阵直接编码的方式定义二维矩阵“资源-任务”矩阵MLm×n来描述染色体编码结构。矩阵中的每一基因列表示被调度任务和资源节点之间的映射关系，通过二维二进制矩阵表示一个合法的云计算DAG任务调度序列，也是任务调度的一个合法解。

以图2中的DAG图为例，假设计算资源节点数为4,可以产生多个二维染色体矩阵,例如图4为一个染色体编码矩阵结构：

图4 资源和任务调度染色体编码矩阵

3.2.2 遗传算法的选择算子和交叉算子设计

本文通过轮盘选择算子，既按一定比例保留适应度函数结果中最优解，从而保存下一代群体的优良个体解不丢失，染色体s被选中的概率为

(5)

通过上面选择算子可以看出，适应度值越高，在种群中被选择的概率越高，从而在进化过程中，使得优秀的遗传基因得以保留，又可以容纳部分劣解，从而保持遗传的多样性和随机性。

根据云计算DAG任务调度的特点设计交叉算子，云计算子任务之间有较强的相互依赖关系，设计交叉算子不能破坏二维矩阵“资源-任务”矩阵MLm×n之间的约束关系，本文采用不同个体染色体二维矩阵列等深度交换运算的策略进行交叉运行，交换不同染色体的等深度基因从而形成新的染色体个体，保留MLm×n的约束关系，新生成的染色体矩阵为一个合法的DAG任务调度解。

3.2.3 遗传算法变异算子的优化策略

(6)

式中：由于云计算DAG任务调度具有相互约束性，变异过程迁移不同列等深度的基因，保证变异后的染色体个体为合法调度序列，w是惯性因子；c1、c2为加速系数，合理设计取值范围可以加快收敛但又不陷入局部最优[7]。rand为介于[0,1]之间的随机数。为了解决粒子群在种群空间的搜索力度，每个粒子的速度被限制在±Vmax范围内。

3.2.4 云计算环境下基于遗传粒子群算法的DAG任务调度算法设计

下面给出混合遗传和粒子群优化算法的设计过程。

步骤1：初始化算法的基本参数，包括GA算法的种群数量N、选择算子、交叉算子等，并初始化PSO算法的粒子群变异概率、权重w、c1和c2因子等参数。

步骤2：染色体的编码形式采用二维矩阵RLm×n编码方式, 每个染色体就是一个合法的DAG任务调度解。令t=0,k=0。

步骤3：根据DAG图采用深度遍历策略初始化种群, 其中有N个个体:s1t,s2t,...,sNt。

步骤4：计算染色体群体中每个个体的适应值f(s1t),f(s2t)...f(sNt)。

步骤5：选择算子通过概率PRi公式：

通过公式可以看出，在整个种群中个体的适应度值的占比越大，越可能被选择参与迭代寻优。

步骤6：对被选择的个体根据交叉概率，进行二维二进制矩阵交叉运算。

步骤7：粒子群的变异计算 。

步骤7.1：生成0～1之间的随机数randi,i=1,2...,N, 如果有randi

步骤7.3：将变异后的染色体个体纳入种群中。

步骤8：如果t

步骤9：染色体解码，输出最优解，终止算法。

4 云仿真平台结果测试及分析

根据云计算任务调度的特点，选择CloudStack工具进行试验平台搭建，CloudStack是具有开源、高可用性和扩展性的一个开源云计算解决方案[8]。为了验证算法有效性，对比遗传算法和本算法进行仿真结果比较，本文采用40、80、160个不同轻重负载子任务根据DAG图进行任务调度。最大的迭代进化代数设计为400次。模拟实验输出对比结果如表1。

表1 仿真实验数据结果

表1为不同负载和计算资源节点下完成时间和找到最优解的迭代次数，从试验数据可以看出：

①当任务个数固定时，随着计算资源个数的增加，云计算完成计算任务的时间和收敛时的进化代数成下降趋势，而得到最优解的最大进化代数也提前。

②当计算资源个数固定，随着任务个数的增加，云计算完成计算任务的时间呈上升趋势，当子任务个数成倍增加，完成时间和收敛进化代数并不成倍增加，体现了算法的优化过程。

③通过模拟仿真结果可以看出，优化后的算法在完成时间和收敛时的进化代数上都有明显的提升和优化。

④从算法性能对比可以看出，优化后的算法对比原遗传算法能在较短的进化代数上接近最优解，并且在较少的计算时间上接近最优解。

分析优化后的算法在性能上有明显提升的原因，在于GA算法具有的高效全局和局部搜索能力，但同时GA算法在搜索计算过程中，容易出现染色体种群中某个个体适应值过大，造成个体适应值大大超过了种群的平均适应值， GA算法选择算子无法选择其他染色体，导致种群多样性降低，使得算法过早收敛，无法输出最优解。为了解决早熟收敛的问题，利用PSO算法搜索效率高，容易找到局部最优解的特点，引入PSO作为变异算子有条件的接受劣解，在染色体种群中保持染色体的多样性，一定程度上减少GA算法本身容易出现的早熟收敛情况，使得优化后的GA算法有效提高了云计算的任务调度性能。

5 结语

通过实验可以看出，云计算环境下基于遗传粒子群算法的DAG任务调度算法优化后算法相较于原遗传算法在完成时间和收敛后的迭代数量上有明显的优势，在遗传算法中，根据云计算DAG任务调度的特点，使用粒子群算法作为变异过程的基础性算法，有限度的接受不同基因的合法解，跳出GA算法的早熟收敛，并有效克服粒子群算法易陷入局部最优的问题。

现实的云计算环境中，很多虚拟云计算节点因为网络问题或者虚拟资源问题存在退出计算资源池的情况，就需要实时监控云计算虚拟计算节点的状态信息，进行动态任务再调度。本文只可考虑了静态负载的调度，资源的动态调度是将进一步研究的方向。