基于动态遗传算法的云计算任务节能调度策略研究

钟潇柔　翟健宏

摘 要：云计算的飞速发展造成了许多大型数据中心的建立，海量的数据中心会消耗巨大的电力能源，导致操作成本以及二氧化碳排放量的升高。为了解决这一问题，本文提出了一种基于遗传算法的新型多目标动态调度算法，将任务的执行时间及数据中心的能耗作为优化目标，充分考虑云环境的动态性，根据任务长度以及资源计算能力将任务分配给资源。本文将该算法与一些著名的云调度模型进行对比，实验结果证明，本文提出的多目标动态遗传算法可以有效利用于云环境，并在减少任务执行时间和能耗方面具有一定优势。

关键字：云计算；任务调度；节能；遗传算法

中图分类号：TP391.41 文献标识号：A 文章编码：2095-2163（2015）03-

Energy-efficient Cloud Task Scheduling Research based on Dynamic Genetic Algorithm

ZHONG Xiaorou， ZHAI Jianhong

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： The rapid development of cloud computing has led to the establishment of large-scale data centers. Such data centers consume enormous amounts of electric energy results in high operating cost and carbon dioxide emissions. With the aid of traditional genetic algorithm， the paper presents a new multi-objective dynamic scheduling algorithm， which considers cloud environment dynamics and reduces total execution time and power consumption. The new algorithm assigns the jobs to the resources according to the job length and resources capacities. After that， the paper evaluates this algorithm with some famous cloud scheduling algorithm， and the experiments show the efficiency of the proposed approach in terms of execution time， power consumption in cloud environment.

Key words： Cloud Computing Scheduling； Energy-efficient； Genetic Algorithm

0 引 言

云计算是分布式计算、网格计算、效用计算和自主计算发展融合的技术研究成果[1]。在云计算中，用户不必感知服务处于基础设施的哪一部分，只需通过云基础设施范式来使用服务并支付相关服务的费用。云基础设施即根据“按需付费”的原则向用户提供共享的资源及服务。

调度算法主要用来减少任务的执行时间以及执行消耗[2]。具体来说，算法中的调度旨在处理如何将资源合理分配给任务的问题。一个好的调度算法应该考虑到系统的负载平衡以及可用资源的总执行时间。调度器则应根据任务长度以及资源计算能力来为任务分配资源[3]。

近年来，在云任务调度领域，一些智能方法的使用引起了多方的高度关注。其中，遗传

算法就是一个著名的人工智能方法。传统的遗传算法模拟生物进化的过程，由一系列染色体组成的种群开始，通过选择、交叉、变异操作，逐步选择适应度高的个体以求得最优解[4]。基于此，本文充分考虑任务的动态特点[5]，并设定多个优化目标，提出了一种新型的多目标动态遗传算法调度策略， 同时运用了CloudSim-3.0仿真工具，切通过与CloudSim自带调度算法的对照比较，验证了本文所提出的算法在动态环境中的有效性。

1 模型建立

1.1 任务期望完成时间模型

通过分析CloudSim自带的样例程序可得，CloudSim默认一个任务所需的执行时间等于任务的指令长度除以处理该任务的虚拟机的执行速度。

根据上述结论，定义一个矩阵time[i][j]，表示任务j在虚拟机i上所需的执行时间，显然time[i][j]=MI[j]/MIPS[i]。在初始化矩阵time前，首先将任务按照MI的大小降序排列，而将虚拟机按MIPS的大小升序排列，重新排序后矩阵time的行号和任务id不再一一对应，列号和虚拟机id的对应关系也随之改变。初始化后，矩阵time的每一行、每一列的元素值都是降序排列的，而后即以time为一个优化目标做遗传选择。这一方式的最终结果表明：任务越复杂，利用更快的虚拟机进行处理的需求就越发明确，以解决复杂任务造成的瓶颈，从而降低所有任务的总执行时间。

1.2 基础设施能耗模型

近年来，一些研究工作[6]表明服务器的能量消耗和CPU利用率之间可准确表述为一种线性关系。不同类型的处理器，线性关系也有所不同。设当前动态环境中有 台虚拟机，运行时间是离散的且可以分割为N个时间块，每个时间块是1秒，当前总能耗设为 ， 为第j台虚拟机的当前状态，则：

（1）

（2）

其中， 是虚拟机处于空闲状态时的最小能耗， 是负载处于峰值时的最大能耗，Utilization则指虚拟机当前的资源利用率。资源提供者会根据物理机的总能耗实行付费。该基础设施的总能耗计算如下所示：

（3）

其中， 是时间序列。主机的资源计算能力以及虚拟机的资源利用率的特征则由CPU性能而决定并优化。

1.3 动态性能模型

在静态环境中，资源以及任务是事先可预知的。而在动态环境中，资源和任务可能随时增减。因此，提前设计固定的性能指标并不适用于动态环境，为此动态CloudSim可用计算单元（compute unit）来衡量虚拟机资源。不同的主机的计算单元可以提供不同数量的计算能力。本动态模型使用指数分布模拟性能改变，用户根据每小时发生的状态变化平均数给出一个速率参数来决定下一个性能改变来临的时间间隔。由指数分布决定的性能改变是随机且无记忆性的，因为对任意随机参数T都遵循如下关系：

（4）

概率密度函数如下：

（5）

其中，λ是单位时间单元内发生状态变化的次数。

2 多适应度的动态遗传调度算法

2.1 染色体编码与解码

染色体用来定义遗传算法尝试解决问题的各种可能答案。本课题采用资源--任务的间接编码方式。染色体的长度为任务的数量，染色体中的每个基因的取值为该位置号对应的任务分配到资源上的具体编号。设有M个用户，N个资源，第t个用户提交的任务数量为：cloudletNum（t）。则任务的总数量CloudletNum为：

（6）

综上可知，根据任务顺序对这些任务进行编号，即第i个用户提交的第j个Cloudlet的序号m为：

（7）

2.2 适应度函数

在遗传算法中，适应度函数用于评价个体的优劣程度，根据适应度对个体进行选择，可以保证适应性能较好的个体将有更多的可能繁殖后代，即使优良特性得以遗传。本课题考虑两个优化目标：任务的完成时间和基础设施的能量消耗，故设定适应度函数如下：

设当前种群集合为 ，种群中每个染色体 代表一种可行的调度方案，基于该调度方案执行所有任务所需的时间为 ， 可根据具体调度方案依照时间矩阵 求得。为此当前种群中全部染色体所需的完成任务的总时间函数可表述为：

（8）

当前种群中，第i个染色体的适应度函数为：

（9）

根据1.2提出的能耗模型计算可得到能耗矩阵EEC。具体计算则如式（10）和（11）所示：

（10）

（11）

其中， 表示任务分配序列为x的染色体对应的基础施设能量消耗， 表示种群总能耗。故染色体x的能耗适应度函数为：

（12）

综合考虑时间消耗以及能量消耗，本研究提出加权的双适应度改进遗传算法，加权双适应度函数如下：

（13）

其中， 和 分别为时间消耗和能量消耗的权重，且 。

2.3初始种群生成

设种群规模为SCALE，任务总数为m，资源数为N，则种群初始化可描述为：由系统随机产生SCALE个染色体，染色体长度为m，基因的取值范围[1，N]，可在此范围中随机取值。

为了符合云计算环境的动态特点，还需做出如下改进：

（1）服务器的增减：计算节点离开，则资源状态不可用，从染色体中删除该资源占用的基因位；计算节点加入，状态由不可用变为可用，在当前染色体中加入新的基因位。

（2）新任务的加入：在当前任务调度完成，占用主机资源执行，有新任务加入时，采用继承思想调度策略。继承思想是指当函数从 转变为 时，函数 收敛得到的最优种群pop-1将保留下来作为函数 的初始种群进行动态寻优，从而得到新的最优种群pop-2。

2.4 选择、交叉和变异算子

选择算子是遗传算法对个体适应度的评价方式，也是实现种群优良基因继承的基本方式，具体方法是：分别计算种群中每一个体的适应度，选出适应度较高的个体遗传至子类。

Srinivas[7]等人提出了一种自适应遗传算法（Adaptive GA，AGA），该算法可根据种群的进化情况来动态地调整交叉概率Pc和变异概率Pm，以达到克服过早收敛及加快搜索速度的目的，根据其原理，建立表达式如下：

（14）

其中， 、 、 、 是（0，1）区间的常数，具体取值根据实际情况而定， 为群体中最大适应度值， 为每代群体平均适应度值， 为要交叉的两条个体中较大的适应度值，f为要变异个体的适应度值，分别计算每两条个体的 和 ，并用其中较大值作为最终的 。交叉算子具体步骤如下：

Step 1：将m条个体两两分成[m/2]组，作为交叉父代；

Step 2：根据公式（14）确定最终的交叉概率 ；

Step 3：对于每一组交叉父代，分别产生一个随机数 ，0< <1；

Step 4：若 ：子代个体用父代个体代替

Step 5：若 ：

Step 6：在[0，m]区间产生随机数 作为交叉位置，m为染色体长度；

Step 7：根据遗传交叉算子计算产生后代；

Step 8：重复step3-7，直到遍历所有染色体组。

由于采用浮点数编码而非二进制编码，交换之后，还需消除其中重复的基因，避免生成无效染色体，具体方法如下：查找新生成的任务序列中是否有重复的元素，若有，则用还未在该顺序表中出现的任务序号替换重复出现的第一个位置元素。

变异运算，指个体染色体编码串中某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。为避免产生无效染色体，本课题采用插入变异算子，即在当前染色体中选取两个基因座，并将其中的一个基因座插入到另一个基因座之后或之前。

2.5 再选择策略

在处理大数据时，遗传算法庞大的种群规模以及较高的迭代循环次数均将造成极大的内存和时间消耗。所以，选择遗传算法用于调度实现时，其研究重心就是尽可能地减少迭代次数，并尽可能快地达到最优解。基于此一目的，本文将采用再选择策略，即将选择运算得到的种群和交叉变异得到的种群，各自选择最优秀的那一半个体进行组合，从而得到一个新的种群，如此即保证了优秀个体在交叉变异后流失数量的降低。具体执行步骤如下：

Step 1：选择运算得到的种群1和交叉变异得到的种群2分为两组；

Step 2：计算每一个体的适应度值；

Step 3：对种群1使用冒泡排序法得到适应度值由大到小的排列；

Step 4：对种群2使用冒泡排序法得到适应度值由大到小的排列；

Step 5：在种群1和种群2中各自择取最优的一半，组成优势种群。

3 实验结果分析

本研究采用CloudSim-3.0仿真工具。CloudSim-3.0仿真机制默认“先绑定，再执行”的一套流程：在仿真准备阶段，用户向数据中心代理提交环境配置信息（HOST配置、VM配置、Cloudlet配置等）以及Cloudlet调度策略等信息，并由数据中心代理按照用户要求的调度策略提前将云任务绑定到相应的虚拟机，而后各个虚拟机统一开始执行云任务。

CloudSim仿真时默认的Cloudlet分配策略是顺序分配，这种方法尽量保证了每个虚拟机运行相同数量的任务即平摊负载，但却未能考虑到任务的需求及虚拟机之间的差别。而贪心算法则考虑到了虚拟机以及任务之间的差异，为此通过优化负载平衡以达到减小任务执行时间的目的。本组实验配置环境信息具体表述如1所示。

表1 实验环境配置

Tab.1 experiment configuration

数据中心 物理机配置 虚拟机配置

CPU 2 000MIPs 500-2 000MIPs

RAM 2 048MB 2 048MB

STORAGE 100 000MB 10 000MB

BANDWIDTH 500-1 000M 500-1 000M

调度策略 TimeShared SpaceShared

任务配置 单核CPU，长度5 000-25 000MI

任务数量 {10，100，200，300，，400，500，600，700，800，900，1 000}

虚拟机数量 50

数据中心数量 1

主机数量 20

图1是数量分别为{100，200，300，400，500，600，700，800，900，1 000}的十组实验的对比结果，横轴为任务集序号，纵轴为总执行时间。由图1可以看出，贪心算法和本课题提出的多适应度动态遗传算法要显著优于顺序调度方法，且随着任务数量的增加，本课题提出的多适应度动态遗传算法在减少执行时间方面的优势则愈加明显。

图2为基于三种调度算法的基础设施能耗对比结果。由图2可以看出，在三种算法中，本课题提出的DGA算法消耗的能量普遍最小，且随着任务数量的增多，其节能优势也愈加突出。

图1 执行时间对比结果

Fig.1 Execution time comparison

图2 能量消耗对比结果

Fig.2 Power consumption comparison

4 结束语

为了解决动态云环境中节能调度的问题，本文提出了一种多适应度的动态节能的改进遗传调度算法，该算法充分考虑云环境的动态性，并综合设定了任务的执行时间以及基础设施的能量消耗多个优化目标。实验表明本文的调度算法可有效应用于云计算环境，并在减少任务执行时间以及能耗方面具有相当优势，并且该优势还将随着任务数量的增加而更加突显。

参考文献：

[1] ARMBRUSTM， FOX A， GRIFFITHR， etal. Above the Clouds： A Berkeley view of cloud computing. http：//www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-28.pdf . 2010.

[2] Buyya R， Beloglazov A， Abawajy J. Energy-efficient management of data center resources for cloud computing： A vision， architectural elements， and open challenges[C]//Proc of the 2010 Int Conf on Parallel and Distributed Processing Techniques and Applications， Las Vegas， USA： PDPTA， 2010：1-12.

[3] MEZMAZ M， MELAB N， KESSACI Y， et al. A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J]. Journal of Parallel and Distributed Computing， 2011，71（11）：1497-1508.

[4] AII S， SAIT S M， BENTON M S T. GSA： Scheduling and allocation using Genetic Algorithm[C]// Proc.EURO-DAC '94， Grenoble， France： IEEE Computer Society， 1994： 84-89.

[5] LI K. Performance analysis of power-aware Task scheduling algorithms on multiprocessor computers with dynamic voltage and speed[J].IEEE Trans on Parallel and Distributed Systems，2008，19（11）：1484-1497.

[6] KUSIC D， KEPHART J O， HANSON J E， et al. Power and performance management of virtualized computing environments via lookahead control[J]. Cluster Computing ，2009， 12（1）：1-15.

[7] SRINVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in Genetic Algorithm for the electrical districting problem[J]. Annals of Operations Research，2003（121）：33-35.