基于免疫算法的云计算任务调度算法

吕计英

（西山煤电集团信息中心，山西 太原 030053）

云计算不仅要面向大量的用户群，还要处理海量任务与数据，因此任务调度就成为了云计算中的重点与难点。现有的常见任务调度算法有3种：FIFO调度算法、公平调度算法（Fair Scheduler）和计算能力调度算法（Capacity Scheduler）。它们都存在一些不足：FIFO调度算法会忽略不同用户的不同作业需求，使交互性的用户作业长期处于等待状态，影响系统效率；公平调度算法会造成计算资源的部分浪费，影响资源利用效率；计算能力调度算法容易使作业处于长期等待状态，陷入局部最优。为了解决这些算法的不足，一些借鉴遗传算法、蚁群算法等智能算法的云环境任务调度算法相继被提出。基于改进的蚁群算法的云环境任务调度算法[1]，避免了蚁群优化算法陷入局部最优，缩短了任务平均运行时间，提高了资源利用效率。针对云计算的编程模型框架，提出了一种具有双适应度的遗传算法的任务调度算法[2]，不仅能够快速确定完成所有任务的时间，而且还能保证该调度策略的任务平均完成时间也较短。这增加了问题搜索空间，避免了局部最优。

本文利用免疫算法中的克隆选择算法，将其应用于云计算环境中的任务调度问题。根据抗体与抗原之间亲和力的大小，获取优秀抗体，并对抗体进行不同程度的变异，最终找出优秀的抗体种群，得出问题的最优解。通过仿真实验，验证其算法的有效性，并能够快速确定任务调度最优策略，提高了系统的整体性能与资源利用效率。

1 基于克隆选择算法的云计算调度算法的设计

1.1 云计算的任务调度

目前，云计算环境大多采用Google公司提出的Map-Reduce编程模型，它是一种并行编程模式，非常适于产生和处理大规模的数据集。在Map-Reduce计算框架模型中，主要分为Map阶段和Reduce阶段。Map阶段：将用户提交的较大的作业拆分成若干个较小的任务，然后分配给多个任务服务器（Task Tracker）并行执行，输出处理后的中间数据；Reduce阶段：将Map阶段处理后的中间数据进行汇总分析处理，输出最终结果。

1.2 基于免疫算法的云计算任务调度算法

针对云计算环境中的任务调度问题，利用免疫算法中的克隆选择算法，可以确定使总任务执行时间和任务平均执行时间都较短的任务调度策略，提高系统效率和资源利用率，满足用户的使用需求。

1.2.1 抗体的编码与解码

假设有p个作业（job），n个任务服务器node（计算资源），第t个作业被拆分为的任务（task）的数量为：taskNum（t），然后再对这些任务进行编号。假设抗体基因序列的长度为10，每个基因位的取值为1～5，随机产生下面一个抗体基因序列：{3，2，4，5，2，1，4，3，1，5}，这个抗体基因序列代表第 1 个 task 在第3个node上执行，第2个task在第2个node上执行，……，第10个task在第5个node上执行。如上述抗体基因序列解码为：

Node1：{6，9}；Node2：{2，5}；Node3：{1，8}；Node4：{3，8}；Node5：{4，10}。

1.2.2 初始抗体种群生成

若初始抗体种群规模为S，作业个数为J，任务个数为m，任务服务器（计算资源）的个数为n，则抗体的种群初始化描述如下：系统随机产生S个抗体，抗体基因序列的长度为m，每个基因位的取值在任务服务器个数的范围内随机选取，即在[1，n]中随机选择。

1.2.3 克隆选择

克隆选则是根据抗体与抗原之间的亲和力大小，从抗体种群中选取优秀抗体进行克隆，增加优秀抗体的浓度，并通过不断的变异进化找到最优抗体（问题的最优解）。因此，亲和力的计算显得尤为重要，它关系到算法的收敛速度以及解的优劣性。

对于云环境的作业调度，一个最主要的性能指标就是全部作业的完成时间，另外还需考虑作业的平均完成时间。在保证所有作业完成时间最短的基础上，还应该满足作业的平均完成时间也最短。

在云环境下，基于免疫算法的任务调度算法的流程如下：

第一，初始化抗体种群：随机产生规模为S的初始抗体种群Ag.

第二，For每一代种群do

{

计算种群中每个抗体的亲和力，根据亲和力大小，选择出N个优秀抗体组成临时抗体种群Ag*N；

对临时抗体种群Ag*N进行不同规模的克隆增殖，生成增殖种群Agp；

对种群中亲和力较低的抗体进行不同程度的基因重组，完成变异操作，生成目标种群Ag′N；

引入随机抗体进入目标种群，丰富抗体种类，变陷入局部最优；

}

第三，直到满足算法结束条件。

第四，从抗体种群中选择出亲和力最高的抗体，确定最佳的任务调度方案。

2 仿真实验及结果分析

由于云计算可以看作是一个特殊的网格环境，所以本文用Gridsim来模拟一个云计算的局部环境。在相同情况下，分别用遗传算法和克隆选择算法进行比较。

初始条件：作业（job）个数为 10，任务（task）个数为 20，任务服务器node（计算资源）的个数为5，初始抗体种群规模为50.

算法终止条件：①到达最大进化代数（这里取最大进化代数为100）；②连续20代总任务完成时间和任务平均完成都没有变化时，认为算法基本收敛，算法结束。

图1 总任务完成时间比较

从图1、图2中可以看出，在进化初期，克隆选择算法的收敛速度要明显快于遗传算法的，并且通过克隆选择算法得出的总任务的完成时间和任务平均完成时间均要小于遗传得出的。另外，在进化后期，虽然2种算法都达到了一种基本收敛，但是克隆选择算法收敛迭代次数以及总任务完成时间和任务平均完成时间均小于遗传算法的，说明了其算法的优良性与有效性。

图2 任务平均完成时间比较

3 结束语

本文借鉴了免疫算法中的克隆选择算法，并应用到云计算环境的任务调度中。克隆选择算法可以解决云计算环境中的任务调度问题，能够确定较优的任务调度策略，提高了系统效率与资源利用率，是一种有效的任务调度算法。

[1]王永贵，韩瑞莲.基于改进蚁群算法的云环境任务调度研究[J].计算机测量与控制，2011，19（5）：1203-1206.

[2]李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）：184-186.