求解云计算资源调度的免疫算法

Research on Resource Scheduling Model and Algorithms of Cloud Computing

摘要: 随着信息社会的飞速发展，云计算不断渗入各界领域，成为处理海量信息数据的主要方式。任务调度问题是云计算研究的核心，其算法的效率对平台用户任务的执行效率和系统资源的使用效率起着决定性作用。本文针对云计算的资源调度问题，提出了一种基于人工免疫理论的云计算动态的任务调度算法。实验结果表明，本文提出的免疫算法能够有效提高云计算资源调度的效率。

Abstract: With the rapid development of the information society, cloud computing has been infiltrating into all walks of life, becoming the main way to deal with massive information data. Task scheduling is the core of cloud computing research, and the efficiency of its algorithm plays a decisive role in the execution efficiency of platform users’ tasks and the utilization efficiency of system resources. Aiming at the resource scheduling problem of cloud computing, this paper proposes a dynamic task scheduling algorithm based on artificial immune theory for cloud computing. The experimental results show that the immune algorithm is able to effectively improve the efficiency of cloud computing resource scheduling.

1. 引言

云计算是分布式计算、并行计算和网格计算的基础上发展而来的，是一种新兴的商业计算模式 [1]。随着信息社会的飞速发展，云计算不断渗入各界领域，成为处理海量信息数据的主要方式。而任务调度问题是云计算研究的核心，其算法的效率对平台用户任务的执行效率和系统资源的使用效率起着决定性作用。因此如何有效地进行任务调度与资源分配来满足平台对于不同用户的需求，同时使得云计算资源利用率最大化，是当前云计算领域中一个重要而又复杂的研究课题。

免疫算法理论 [2] 最早是由澳大利亚科学家Burnet提出的克隆选择理论 [3]。此后，免疫学理论 [4] 得到了迅速的发展，到了20世纪90年代，Bersini等人 [5] 最早提出免疫算法，并将免疫算法应用于解决各个领域的现实问题。Hunt等人 [6] 开始将免疫算法应用于机器学习领域。Naruaki等人 [7] 提出了自适应免疫优化算法，并将其成功应用在智能体工作域分配问题中。Coello等人 [8] 在免疫算法的基础上，提出一种多目标优化免疫算法，用于解决电力规划和智能控制等方面的问题。针对云计算领域的任务调度问题，先利用遗传算法处理虚拟机放置的组合优化问题，然后结合模糊逻辑进行多目标优化，但只考虑了静态虚拟机配置，忽视了虚拟机迁移的开销 [9]。成都电子科大团队 [10] 运用人工免疫理论的云计算平台动态任务调度算法得到不同虚拟机分配计算资源的近似最优配置，表明人工免疫调度算法具有较好实用性，但该算法针对元任务，对于现实集群中存在的大量依赖关系的任务存在较多问题。

本文基于免疫算法，对云计算任务调度问题进行研究。对随机生成的数据进行模拟实验，从执行效率和算法寻优性能这两个指标入手，改进免疫算法，得出任务调度方案。

2. 免疫算法

图1给出了免疫算法的算法框架图。具体实现步骤如下：

1) 分析问题。对任务调度所研究的问题进行研究分析，构造实验的目标函数，模拟免疫系统中抗原产生形式。设计合理的目标函数表达式。

2) 产生初始抗体群。初始种群的生成需要两个步骤：一是随机生成N个个体，二是从记忆库里随机选取m个个体组成初始群体。即初步的解集，而每个个体对应任务调度的解。

3) 抗体识别抗原。按照个体的期望繁殖力p来进行评价对前两步骤中得到的抗体逐一进行评价。

4) 形成父代群体。按照繁殖率p对初始群体进行降序排列，父代群体取其中前N个个体组成。同时将前m个个体放入记忆库里。

5) 要对抗体适应度计算判断是否满足所设定的约束，满足则结束，否则执行下一步。

6) 抗体的繁殖——新群体的产生。对第四步取得的计算结果进行分析，然后对形成的抗体群体执行选择、交叉、变异等遗传变异步骤。以此得到一个新群体。再从记忆库若干解，与新群体一起构成总群体 [3]。

7) 执行第3步。

Figure 1. Immune algorithm flowchart

图1. 免疫算法流程图

2.1. 基于免疫算法的任务调度模型

任务调度是操作系统的重要组成部分，而对于实时操作系统，任务调度直接影响其实时性能。免疫算法的任务调度属于事件驱动调度算法，即根据事件的先后以及任务的优先级安排任务的执行。图2给出了任务调度的示意图。

Figure 2. Task scheduling diagram

图2. 任务调度图

初始抗体群从两种途径取得：一是从记忆库中随机选择生成；二是在可行解的空间内随机产生。每个任务的分配方案都看作是一个长度为l的抗体(l表示虚拟机的数量)，其中抗体代表任务对虚拟机的需求指标点。

亲和力函数是用来计算抗体对抗原的识别程度。此处亲和力函数A_v为：

$A_v=\frac{1}{F_v}=\frac{1}{{\displaystyle \underset{i\in N}{\sum }{\displaystyle \underset{j\in M_i}{\sum }{w}_i{d}_{ij}{Z}_{ij}-C{\displaystyle \underset{i\in N}{\sum }\min \left({\displaystyle \underset{j\in M_i}{\sum }{Z}_{ij}-1.0}\right)}}}}$ (2-1)

其中，F_v为目标函数，在分母中插入C，意为对违反任务调度时间约束的值给予惩罚，通常取一个比较大的正数。

抗体之间的亲和力函数是用来计算抗体之间的相似程度。当两个抗体中的编码超过R位相同时，表示这两种抗体近似“相同”，否则表示不同。在此处，排序不作考虑，因此得到抗体与抗体之间的亲和度亲和力函数S_v,s为：

$S_{v,s}=\frac{k_{v,s}}{L}$ (2-2)

其中，k_v,s表示抗体v与抗体s中位数相同的部分；L则表示抗体的长度。

抗体浓度表示的是群体中相似抗体所占全部抗体的比例，将设其为C_v：

$C_v=\frac{1}{N}{\displaystyle \underset{i\in N}{\sum }{S}_{v,s}}$ (2-3)

其中，N表示抗体总数；当 $S_{v,s}>T$ (T是事先设置的阈值)时， $S_{v,s}=1$ ；当 $S_{v,s}$ 为其他值时， $S_{v,s}=0$。

繁殖概率是由抗体与抗原之间的亲和力A_v和抗体浓度C_v两部分一起决定，此处设函数为p：

$p=\alpha \frac{A_v}{{\displaystyle \sum A_v}}+\left(1-\alpha \right)\frac{C_v}{{\displaystyle \sum C_v}}$ (2-4)

其中， $\alpha$ 为已知常数。

由(2-4)式可见，个体适应度、个体浓度均与期望繁殖率成正比。如此一来，在鼓励适应度高的个体同时，又可以一定程度上抑制浓度高的个体，由此确保所得个体具有多样性。

为了避免算法在抑制高浓度个体的时候导致与抗原亲和度最高的个体由于自身浓度过高受到抑制从而丢失。因此考虑在每次更新记忆库时，先将这样的个体存入记忆库中，然后按照期望繁殖率将其他优秀个体存入记忆库。

2.2. 任务调度模型求解

现在假设有n个未完成的任务，需要在有m个可用的虚拟机的云端上执行，需要通过免疫算法将n个任务合理分配到m个可用虚拟机上运行，使得完成所有任务所耗费的时间MT最短。假设 ${\text{Case}}_i$ 表示第i ( $i=1,2,\cdots ,n$ )个需要完成的任务， ${\text{Machine}}_j$ 表示第j ( $j=1,2,\cdots ,m$ )个可用的虚拟机，GT是一个 $n\times m$ 的二维矩阵，这个矩阵表示每个任务在相应的可用虚拟机上执行时所花费的时间，其中 $G{T}_{ij}$ 表示在 ${\text{Machine}}_j$ 上执行完 ${\text{Case}}_i$ 所需要的时间。

3. 实验仿真结果与分析

为验证免疫算法的对任务调度具有可行性，本实验选取随机数据，进行仿真模拟实验。

3.1. 实验假设

1) 本实验目标为计算任务时间的需求即任务最小完成时间，因此仅将完成任务的时间长短作为唯一考量。

2) 本实验仅考虑任务的大小和任务调度的难度，不考虑能耗以及其他因素带来的影响。

3.2. 初始条件

1) 随机生成了31个任务(Case)数据，每个数据为二维向量，意在表示任务的两个参数：任务的大小和任务调度的难度。

2) 考虑实验需要，随机生成6台虚拟机(Machine)，将CPU容量和内存大小作为虚拟机的两个参数，默认硬盘大小一致且满足实验需要。

3) 根据任务调度的模型，按照上述免疫算法的基本流程进行求解，设置如下参数：将种群规模(sizepop)设为60，记忆库容量(overbest)设为15，迭代次数(max)设为100，变异概率(pumtation)设为0.4，交叉概率(pcross)设为0.5，虚拟机数(length)设为6，多样性评价参数(assessment)设为0.95。

3.3. 终止条件

1) 迭代次数达到最大化(本实验迭代次数最高为120)。

2) 连续20代完成任务的总时间基本不变，认为算法基本收敛，求得任务调度方案以及总时间。

3.4. 实验结果分析

相对于原始人工免疫算法，改进后的人工免疫算法有效避免了易陷入局部最优等难题，全局的搜索能力更强。我们通过一定的限制选择了6个虚拟机，把25任务按最优结果分配到6个虚拟机上工作，使得时间最短，6个虚拟机同时工作，在处理任务上就可以多个任务同时进行，因为每个任务所要求的虚拟机配置不同，通过免疫算法的任务最优的分配给虚拟机，最终结果如图3所示。

Figure 3. Diagram of experimental results

图3. 实验结果图

通过图3我们可以得到，这些任务通过免疫算法分配的时候不是每个虚拟机都会得到任务，他是根据最优和最合适的算法原理去把任务分配给虚拟机的，所以我们可以看到最终结果是，有一些虚拟机被分配了多个任务，但是有一个虚拟机没有分配到任务。免疫算法在应用资源调度的时候不是追求平均，而是最优。

随着迭代次数的增加，平均适应度值逐渐接近最优适应度值，并且收敛速度极快，由该算法在20代的时候就收敛，即产生满足要求的最优解所用时间较短。图3表示任务随着迭代次数的增加而减少并最终收敛趋于平稳，就是说在进行实验时，能够是每个任务所分配的虚拟机是最佳，而且整个任务调度过程所需的时间是最短。这说明了实验的可行性。

4. 结论

为了更好地对任务进行调配，本文对免疫算法进行了改进，使其能够更好地调度任务，所需的时间最少，调度最优。提出了一种基于人工免疫理论的云计算动态的任务调度算法.免疫算法对任务调度具有可行性。

参考文献