动态队列下入侵肿瘤生长优化和BPNN的云计算任务调度新方法

范 颖 沈建京

1(郑州信息科技职业学院 河南 郑州 450008) 2(中国人民解放军战略支援部队信息工程大学 河南 郑州450008)

0 引 言

云计算是一种可以提供灵活的按需基础架构的新兴计算范例，它以平台和软件作为服务。通常有三种云模型：SaaS(软件服务)、PaaS(平台服务)和IaaS(基础架构服务)[1]。云计算调度过程是决定各种可能的工作/任务之间资源分配的概念，根据资源的最佳分配和实现良好的服务质量(Quality of Service，QoS)的需要，将这些任务分配给适当的资源[2]，而最佳资源分配加入云计算配合后，能够大幅提升QoS。在云计算中，不同的虚拟机(Virtual machines,VM)可以处理和调度来自不同用户的独立任务，以实现资源利用率的最大化。由于异构资源的不同任务特征和动态特性，任务调度被称为NP完全问题[3]。在此过程中，任务调度程序从用户接收任务并将其映射到可用资源，同时考虑任务的特征和资源的参数。因此，有效的最优任务调度算法应该通过实现资源的高效利用和最大利润以及高性能计算来考虑系统负载平衡[4]。

已有的研究已经应用了几种启发式算法来应对云计算中任务调度的挑战。文献[5]制定了任务调度模型，提出了一种基于小位置值规则的粒子群优化算法，以最大限度地降低处理成本。通过将交叉和变异嵌入的PSO算法(Embedded crossing and variation PSO,ECV-PSO)与本地研究中的PSO算法与PSO算法进行比较，结果表明PSO算法的大规模收敛速度更快，更适合云计算。文献[6]提出了一种基于蚁群优化算法的云任务调度策略，用于负载均衡，工作的主要贡献是在尝试最小化给定任务集的完成时间时平衡系统负载，并提出了与作业完成率相关的负载均衡因子，以提高负载均衡的能力。文献[7]提出了一种用于云计算中工作负载调度的单目标PSO算法。PSO算法与不同的惯性权重策略相结合，以最小化完成时间。结果表明，PSO结合线性降低的惯性重量(Linearly decreasing inertia weight,LDIW-PSO)可以获得更好的性能并改善完成时间。文献[8]为单用户工作引入一种改进的遗传算法，其中开发适应性以鼓励形成解决方案以最小化执行时间和执行成本。实验结果表明，在重载下，该算法表现出良好的性能。文献[9]提出了一种称为正交猫群优化算法(Orthogonal Taguchi based-cat swarm optimization,OTB-CSO)来最小化总任务执行时间，探索了Taguchi优化方法的局部搜索能力，通过实现最小完成时间来提高收敛速度和解决方案的质量。实验结果表明，OTB-CSO可有效优化任务调度，提高整体云计算性能。以上研究已经从各个方面为云计算中的调度问题提出了不同的方法和技术。然而，仍然迫切需要灵活的架构和调度方法，其涵盖可能对系统性能具有很大影响的重要要求。此外，一些工作不会动态地考虑任务特征和资源属性，任务等待时间这一重要绩效指标也需要得到进一步重视与优化。因此，提出了一种动态调度队列(Dynamic dispatch Queues,TSDQ)下入侵肿瘤生长优化(Invasive Tumor Growth Optimization,ITGO)结合反向传播神经网络(Back Propagation Neural Network,BPNN)的云计算任务调度新方法(TSDQ-ITGOBPNN)。其主要创新点如下：

(1) 混合启发式算法融合模拟退火算法与反向传播神经网络算法特点，对平均等待时间进行优化并使系统中的任务等待队列尽可能短；

(2) 提出的算法结合任务特性和资源能力，同时考虑搜索空间的动态特性，加快了启发算法的收敛速度并提高了解决方案的质量；

(3) 混合启发算法考虑云计算调度任务的复杂性，在兼顾云计算任务等待时间和队列长度的前提下对其进行队列管理，克服了单个启发式算法的固有局限性的同时增强了解决方案空间搜索的能力。

实验结果表明，所提动态队列下模拟退火结合反向传播神经网络算法能有效减少任务调度等待时间，提高资源利用率并增强负载平衡度。

1 背景架构

1.1 调度问题

现如今，由于云提供商要求与用户服务质量、用户优先级、服务成本等偏好之间存在巨大重叠，所以将任务调度作为云计算的一个重点方面进行了大量研究。在安排任务时应考虑用户的满意度、提供者的利润优化和其他因素。由于该过程是NP完全问题，因此，一种有效的方法不仅应该优化云用户和提供商的某些目标，还要考虑云计算环境的动态特性。

云计算由包含多个物理机(Host)的大量数据中心组成。每个主机运行多个虚拟机，负责执行具有不同QoS的用户任务。云计算环境中的调度过程，如图1所示。假设N个用户提交他们的任务T1,T2,…,TN，要安排到M台虚拟机VM1,VM2,…,VMM上。本文假设任务是互相独立的，即任务之间没有优先约束，它们不是先发制人的，也不能被打断。此外，这些任务具有不同的特性，如长度、到达时间、突发时间、截止日期等。本文还假设VM在CPU速度、RAM、带宽等方面是异构的。

图1 云调度环境

云代理查询云信息服务(Cloud Information Ser-vice，CIS)提供有关执行接收任务所需服务的信息，然后在发现的服务上安排任务。要服务任务的选择取决于代理确保的多个因素和QoS要求。云信息数量庞大，给查询带来一定的困难。因此可以设计规模较小的云信息集，将同类信息进行集合，实现云信息的全面覆盖[10]。云代理是任务调度过程的主要组成部分，它调解用户和提供者之间的协商，并且还负责对特定时间和特定资源进行任务的调度决策，但是有些问题需要考虑在内。

首先，用户提交的任务加入系统中的第一个队列，并且必须等待资源的使用。因此，这扩展了系统的队列长度并增加了等待时间。但是，必须使用有效的方法而不是先到先服务(First-come-first-served,FCFS)策略来管理此队列。其次，当提供者处理任务时，许多参数可以同时被视为单目标优化或多目标，例如对资源利用有直接影响的完成时间。因此，应该在云代理中设计和实现良好的任务调度方法，不仅要满足云用户强加的QoS约束，还要在虚拟机之间进行良好的负载均衡，以提高资源利用率，最大化利润。这种方法还应具有根据云环境中动态调度要求调整调度过程的适应性。基于上述问题，本文提出的方法旨在优化特定的性能指标。特别是，本文的目标是最小化完成时间、最小化等待时间、最大化资源利用率，实现更好的负载平衡并降低所需资源的成本。

1.2 有效性衡量标准

在任务调度过程中，可以将各种时间参数作为性能衡量指标，包括所需时间(完成、等待、周转、流程、延迟等)、吞吐量、负载平衡、资源利用率等[11]。本文选取Makespan、等待时间、不平衡程度、成本以及资源利用率作为性能评价指标，具体定义如下：

(1) Makespan 该指标表示执行所有任务所花费的时间(即上一个任务的结束时间)。该指标可以按下式计算：

Makespan=maxi∈taskes{FTi}

(1)

式中：FTi表示任务i的结束时间。

(2) 等待时间 任务的等待时间是指在执行之前在队列中花费的时间。等待时间的最小值表示可以最小化等待时间以及队列长度的任务的正确/最佳顺序。

(3) 不平衡程度(Degree of Imbalance，DI) 该指标衡量各个虚拟机VM之间的不平衡。不平衡度量表示一个重要的QoS度量标准，用于显示任务的分配效率和虚拟机之间的负载平衡。DI可以按下式：

(2)

式中：Tmax、Tmin、Tavg分别是所有VM的最大、最小和平均总执行时间。

(4) 成本 成本指标表示进行任务调度过程中所花费的时间及能耗综合指标，是评价调度算法的关键因素，该指标可按下式计算：

Cost=∑ETij×CVMj

(3)

式中：ETij是VMj上任务i的执行时间；CVMj是每单位时间VMj的成本。

(5) 资源利用率(Resource Utilization Rate，RU) 资源利用率是指在云计算任务调度过程中，调度任务对各个虚拟机算力使用以及资源分配是否合理的衡量指标，可以按下式计算：

(4)

式中：TVMi是VMi完成所有任务所花费的时间；N是资源的数量。

2 算法设计

2.1 前馈型神经网络算法(BPNN)

前馈神经网络包含的算法众多，所提方法采用BP神经网络，每层神经元的状态只影响到下一层，且通过各神经元权值的不断调整以降低误差信号，直至找到最优状态。

BP神经网络的输入层数据经隐层处理后转向输出层，如果输出层实际输出与期望输出不相等，误差信号将沿原通路返回，通过各神经元权值的不断修改来降低误差信号直至达到可接受范围或指定学习次数为止[12]。

设训练样本为Xk=[xk1,xk2,…,xkm],k=1,2,…,N，N为训练样本数,η为学习效率。隐层I和输入层M间的权值向量WMI(n)第n次迭代时的关系式为：

(5)

隐层I与隐层J间的权值向量WIJ(n)第n次迭代时关系式为：

(6)

输出层P与隐层J间的权值向量WJP(n)第n次迭代时关系式为：

(7)

迭代后的实际输出为：Yk(n)=[yk1(n),yk2(n),…,ykp(n)]，期望输出为：dk=[dk1,dk2,…,dkp]，k=1,2,…,N[13]。BPNN算法详细流程如图2所示。

图2 BPNN算法详细流程

2.2 入侵肿瘤生长优化(ITGO)

ITGO是一种基于群智能的启发式优化算法，该算法通过模拟肿瘤细胞周围的微环境，对所需问题进行求解和计算[14]。在细胞种群中，由外到内分别是入侵细胞、生长细胞、休眠细胞和死亡细胞。其中，当细胞种群陷入局部最优解时，可通过入侵细胞的Levy飞行，跳出局部最优解；当前范围内搜索更优解由生长细胞负责。

4类细胞在解空间中的具体表现为：

(1) 入侵细胞。入侵细胞具有极强的搜索能力，能通过Levy飞行跳出局部最优解[15]。当细胞种群陷入局部最优解时，可通过入侵细胞的Levy飞行，找到营养液浓度更高的位置，并引导种群向该浓度更高的地方移动，从而跳出局部最优解：

Icelli,j(t+1)=Icelli,j(t)+α·Levy(s)

(8)

(9)

Levy(s)～|s|-1-v1

(10)

(11)

(12)

(13)

式(11)-式(13)为基于蒙特卡罗的步长选择。式(8)中：t为当前迭代次数；Icelli,j(t+1)为当前的入侵细胞；α是步长控制参数；Levy(s)是Levy飞行的步长分布。式(9)中T为算法最大迭代次数。

(2) 生长细胞。生长细胞位于入侵细胞内层，休眠细胞外层，承担了绝大部分的搜索工作，主要负责在当前范围内搜索更优解。

(3) 休眠细胞。休眠细胞位于生长细胞内层，死亡细胞外层。休眠细胞搜索能力极低，当周围的营养液浓度过低时，部分细胞会由于营养成分不足而进入休眠状态，直到周围的营养液浓度再次发生变化。

(4) 死亡细胞。在优化过程中，不执行任何检索操作，不占据任何计算资源，当达到一定的细胞周期之后，将释放占据的计算空间。

2.3 任务调度

云计算环境的增长速度非常迅速，任务调度被认为是必须解决的挑战之一。由于任务的特征、云提供商的要求、用户的偏好以及要解决的优化问题的类型多样，有效的任务调度方法是一个长期存在的问题。

各混合算法间的主要区别在于调整任务权重的方法和适应度计算模型。所提方法的主要目的是使用WTO-PSO算法以增强BPNN的收敛性能，并提高搜索能力和方案质量，其中采用SA算法来优化惯性权重这一影响BPNN性能的关键参数，动态调整该参数，可提高BPNN的搜索能力。此外，在分析问题的动态特征基础上，所提方案包括任务特征和资源容量。

因此，本文使用基于BPNN算法的有效算法来优化平均等待时间并使系统中的任务等待队列尽可能短。如图3所示，在任务等待队列中，任务根据其到达时间排队。通过计算所有可能的任务序列等待时间以获得时间的最佳序列，选取其中的最小值并返回，即可以获得最小等待时间和减少队列长度的任务的正确顺序。缩小等待时间和减少队列任务可以有效降低分摊到每个任务队列的压力，有利于实现负载均衡，负载均衡又可以提高对动态特征的分析和处理[16]。

图3 本文提出的方法模型

为了优化等待时间，定义式(12)为该问题的目标函数。因此，给出了用于计算PSO算法中每个粒子的解的适应度函数，并且在式(15)和式(16)中检验了解决方案以找到所考虑问题的最优解。

objectivefunction=minimize{WT}

(14)

Fitness=minTWi

(15)

任务TWT的总等待时间可以表示如下：

(16)

式中：WTTaski是任务TWT的等待时间；n是队列中的任务数。

该算法从初始化部分开始，该部分包括生成具有随机位置和速度的群。然后在每次迭代中连续更新速度、位置、局部最佳和全局最佳解。当满足终止标准时，该过程结束：超过迭代次数或获得最佳解决方案。本文使用SA算法来优化惯性权重，以加速BPNN向最优解的收敛。模拟退火方法的伪代码如下：

Pseudo-code of Simulated Annealing(SA)

1. S0=Generate_initial_solution()

2. Sbest=S0

3. Temperature=Initialize_Temp()

4. repeat

5. repeat

6. Temperature=calculate_temperature()

7. Snew=Create_neighbor_solution(S0)

8. if(Fitness(Snew)

9. Sbest=Snew

10. else if(rand()

11. S0=Snew

12. end if

13. until thermal equilibrium is reached

14. decrease Temperature according with the annealing schedule;

15. until stopping criterion is met

16. return Sbest

在此过程中，生成初始S0并将温度设置为初始温度。在满足某个停止标准之前执行迭代。在每个步骤中，SA考虑当前解S0的一些相邻解Snew，并且以一定的概率决定在移动到Snew或保持在S0之间。如果新解决方案(Snew)与当前解决方案(S0)相比具有更好的适应性，则将被接受。但是，如果新解决方案比当前解决方案更差，则以一定的概率驳回。一旦达到热平衡，就根据退火时间表降低温度。模拟退火算法的主要优点是其强大的局部搜索能力，避免陷入局部最优解。

3 实验及分析

本文进行了几个不同参数设置的实验，以评估本文的工作效率。因此，为了客观地评估所提算法的性能，本文将提出的算法TSDQ-ITGOBPNN与文献[5-6,9]中提出的ECV-PSO、LDIW-PSO以及OTB-CSO算法进行了比较。评估使用来自并行工作负载存档(PWA)[7]中可用实际系统生成的工作负载数据的合成和实际数据集完成的。主要对比在完成时间、不平衡程度、资源利用率和成本等方面的性能。

3.1 模拟环境及参数设置

为了评估所提方法TSDQ-ITGOBPNN的有效性，在CloudSim上实现了性能评估和与其他算法的比较。该模拟器允许建模和模拟可扩展云，并在受控环境中测试开发的应用程序服务的性能。CloudSim工具包支持云系统组件的建模，例如:云数据中心、用户、虚拟机和资源配置策略。Cloudsim提供了多种功能，例如使用不同的方案生成不同的工作负载，并根据自定义配置执行稳健的测试。资源参数如表1所示。

表1 资源参数

3.2 平均等待与完成时间对比

此模拟的目的是在任务等待队列中找到最佳的最小等待时间序列。为了说明这种情况，本文提供了一个简单的例子。本文假设用户提交了3个独立的任务，由提供者处理，并且最初存储在等待时间队列中。在该模拟中，进行了6次实验，其中在这些实验中每个任务的突发时间已经改变。

图4所示为所提算法与ECV-PSO、LDIW-PSO、OTB-CSO算法的对比结果。可以看出所提算法可以有效地克服OTB-CSO的缺点并提供优化的解决方案，通过最小化在队列中花费的任务等待时间，减少队列长度并使其尽可能短，提高了管理任务等待队列的速度和效率。

图4 不同算法平均等待时间对比

在这种模拟中，高性能计算中心北部的标准格式化工作负载称为日志，用于生成不同的工作负载。图5中，对于不同数量的任务，在平均完成时间方面对性能进行了比较。得到的结果表明，所提算法TSDQ-ITGOBPNN的完成时间比其他算法更好，增长更慢。可以看出，所提算法在执行所有任务上花费的时间更少，并且在解决方案的质量和收敛速度方面优于LDIW-PSO和RIW-PSO；当搜索空间扩大时，LDIW-PSO和RIW-PSO都显示出更高的稳定性。但在LDIW-PSO和RIW-PSO算法的情况下，找到改进的最优解的可能性变得更大。TSDQ-ITGOBPNN算法显示出良好的收敛特性，特别是当任务数量增加时，完成时间显著减少。这是因为基于两个阶段的动态队列和模糊逻辑，TSDQ-ITGOBPNN算法通过考虑任务长度和VM能力(如CPU速度、占用率、RAM和带宽)将任务分配给最合适的资源，有助于在更短的时间内找到最佳的映射和完成任务。此外，在搜索最优值的每次迭代中，算法评估返回的解决方案以选择最优解。由于虚拟机状态或虚拟机的占用率是所提算法的输入参数之一，所有这些都使得TSDQ-ITGOBPNN不仅能够做出最佳决策，而且还能够为其分配最合适的资源。即使收到任务，也要尽可能保持资源的繁忙，这样才能通过增加任务执行时间的方式有效地减少完成时间。

图5 具有不同任务数的平均完成时间对比

3.3 平均执行成本对比

图6给出了在相同条件下各种任务调度算法的平均完成时间和执行成本，可以看出本文算法的平均执行成本最小。结果同时表明，所提出的算法不仅优化了完成时间而且优化了执行成本，并解决了两个相互冲突的目标。在所提算法中，以任务执行花费最少时间并且不忽略诸如资源利用和执行成本的其他度量的方式来选择资源。因为目标是在更好的执行时间和低成本之间找到折衷方案，可以尽可能多地使用具有较低处理器容量的资源，同时获得较好的解决方案。所提算法具有动态优化资源分配、缩短执行时间和降低执行成本的灵活性。

图6 对比不同算法的平均执行成本

3.4 不平衡程度对比

图7绘制了所提算法与ECV-PSO、LDIW-PSO、OTB-CSO在平均不平衡程度与任务数量方面的比较。实验结果表明，基于动态队列的两种任务调度算法具有明显的效率优势，并且对所有数据集表现出近似相同的性能。TSDQ-ITGOBPNN显示出极好的能力来确定资源之间的最佳负载平衡，从而防止完成时间变得过大并避免VM的不平衡工作负载。这意味着资源具有最佳负载量；任一负载不至于繁忙，且其他负载在任何特定时间闲置或不使用。因此，最佳和良好的负载平衡可以得到最高的资源利用率。

图7 对比不同算法的平均失衡度(DI)

3.5 平均资源利用率与不同任务数成本对比

图8显示了所提算法与ECV-PSO、LDIW-PSO、OTB-CSO的平均资源利用率。资源利用率是一项重要的性能指标，因为它不仅代表资源的利用率，而且显示资源在执行任务时忙于哪个级别。结果表明TSDQ-ITGOBPNN的资源利用率保持在较高水平，与ECV-PSO、LDIW-PSO以及OTB-CSO相比，它具有最佳的资源利用率。提出的算法和这些算法之间的差异是显著的，并证明了基于动态调度队列的算法的有效性。因此，TSDQ-ITGOBPNN可以灵活地分析、探索和调度存储在动态队列中的任务集，以执行更智能的调度决策。此外，TSDQ-ITGOBPNN还可以在调度任务的过程中实现资源的良好利用，保持较高的资源占用率。实际上，TSDQ-ITGOBPNN算法使资源尽可能繁忙并使用所有可能的资源能力。资源利用率指标正在显著增长，因为服务提供商希望通过租用有限数量的资源来获得最大利润。

图8 不同算法的平均资源利用率对比

图9为TSDQ-ITGOBPNN与ECV-PSO、LDIW-PSO、OTB-CSO不同任务数之间的成本比较。此度量标准显示用户需要向服务提供商支付的资源利用总量。例如，在此模拟中，本文假设资源的5 000 MIPS计算能力的成本是每单位时间10美元。仿真结果表明，当任务数量增加时，TSDQ-ITGOBPNN表现更好，成本更低。基于所提出的调度策略，TSDQ-ITGOBPNN显示出了将传入请求分发到异构VM的更好的灵活性，例如，它能够确定执行每个任务的最合适的VM，以便在考虑其他QoS要求的同时最小化成本。TSDQ-ITGOBPNN算法基于Mamdani推理系统和定义的规则动态地考虑任务长度和资源处理器容量。当所提算法计算函数适应度时，它考虑任务和资源属性，例如：资源的任务长度和CPU功率。因此，最佳适应性意味着TSDQ-ITGOBPNN算法选择并使用具有较高计算能力的VM，如果具有较低计算能力的VM不能为任务提供良好结果或给出非最佳解决方案，那么将影响结果的准确性。综上，TSDQ-ITGOBPNN算法可以在成本方面有效地实现良好的性能。

图9 具有不同任务数的成本对比

实验表明，所提算法的特性不仅适用于合成任务，也适用于实际任务。它是一种智能体系结构，可以获得最优解，并在所考虑的性能指标方面实现更好的全局收敛能力。

4 结 语

任务调度是云计算中最具挑战性的问题之一，在整个云计算设施的效率中起着重要作用。任务调度的目标是通过优化执行时间、成本、资源利用率、负载平衡度等指标将任务映射到要执行的最合适资源。提出的动态调度队列和混合启发式算法的任务调度优化方法能快速有效确定不同情况下的最佳调度方案，以保证较高的调度效率与最佳的稳定性。通过使用CloudSim仿真器和来自Parallel Workload Archive(PWA)的实际系统的合成和实际数据集的大量实验，验证了所提出工作的优越性。TSDQ-ITGOBPNN在最小化等待时间和队列长度、减少完成时间、最大化资源利用率、最小化执行成本和改善负载平衡方面取得了良好的性能。

实验结果证明了本文提出的算法的有效性，与其他现有的调度算法相比，特别是在高维问题中，具有更优异的性能。下一步可以通过整合其他优化算法和技术来增强所提算法的稳健性，并考虑更多的QoS参数如任务的优先级，允许在队列之间迁移任务，考虑能量消费和虚拟机迁移的概念等。