基于混合遗传算法的云计算任务节能调度算法

吴世山 翟健宏

摘要：云计算中主机和任务的数量都是十分庞大的，如何通过任务分配调度来减少成本开销和降低能耗是当前云计算和绿色计算领域研究的热点问题。根据云计算任务以及运行环境的特点，将云计算任务分配问题抽象为多维多背包求解问题，并采用改进的混合遗传算法对该问题进行求解。实验结果表明，改进的混合遗传算法能够在较短的时间内找到问题的优化解，并且根据该算法实现的任务分配策略能够有效地减少任务执行的成本开销和能耗。

关键词：云计算； 任务分配； 混合遗传算法； 降低成本； 节能

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2013）06-0036-05

0引言

云计算作为一种计算、存储资源的新型商业模式而出现，具有按需访问大量、潜在的远程数据、计算中心的功能。随着云计算的发展日趋成熟，相关的服务和应用正在逐年递增，云计算为之配备的服务器数量规模也在高速增长。为了达到负载均衡、降低成本以及节能的目的[1]，云计算任务分配调度已经成为当今研究的热点课题。

云计算是从网格计算的基础上发展而来，但网格计算一般用于科学研究，而云计算则更多的是面向广大用户，应用场景的不同使得两者的任务分配方法存在着非常明显的差异[2]。网格计算多是针对应用与科学研究领域，以计算密集型应用为主，更注重的是效率，比如最短时间完成任务，所以传统的网格程序性能预测模型往往只考虑程序的运行时间效率，而忽略了其他硬件方面的开销。而云计算应用范围的广泛化就决定了必须在效率和各种资源开销之间寻找一个平衡，这些开销就包括时间开销、CPU利用率、内存使用大小、I/O使用大小，为了降低成本就要使以上各种硬件资源得到充分的使用而减少任务所需主机的总数量，同时为了保证QoS（Quality of Service）必须避免出现资源征用情况的发生。

目前，许多云计算任务分配调度方法的目的主要为了减少任务的运行时间[3]，或者任务运行的利益最大化[4]，却较少地关注到任务运行所消耗的资源以及能耗。Pandey等[3]使用优化粒子群算法寻找出云计算环境下最优的资源分配策略，使得任务的执行总时间以及通信量最低；徐骁勇[5]通过对云计算资源进行调度，缩短了云计算任务的运行时间，同时也达到了降低能耗的目的；Srikantaiah[1]发现当计算机CPU和硬盘处在某一利用率时可以达到处理平均事务所消耗的能量最少，并通过调整硬件资源的利用率来达到节能的目的；Duy[6]将计算机状态分为运行、等待、休眠和关机，再结合数据中心的电源管理办法，通过将计算机在这四种状态之间互相转换来达到节能的目的，但并没有影响到计算机内部资源的利用率，而且也没有解决资源使用不充分的问题；已有的三种绿色任务调度算法是STF-OS、LTF-OS、和RT-OS算法[7]，这三种算法虽然能够达到节能的目的，但却只考虑了CPU的调度，而没有兼顾到计算机的内存、I/O和带宽等资源的整体调度，可能导致资源的不充分利用或者资源的争用，从而影响QoS。

根据云计算任务调度的特点，本文提出了一种基于混合遗传算法的云计算任务分配策略，实验表明，这种方法能够有效地降低任务运行的总能耗，降低任务成本。

1云计算任务分配模型

1.1任务分配问题的描述

假设一个数据中心包含m台主机，n个任务等待分配，{Cj，Mj，Dj，Nj}四元组分别对应第j台主机的CPU、内存、硬盘I/O、网络带宽四种资源，{ci，mi，di，ni}为第i个任务对四种资源的需求量，则四元组{Cj，Mj，Dj，Nj}即为背包问题中第j个背包容量，{ci，mi，di，ni}为第i个物品的大小，由此任务分配问题就转化为四维背包问题的求解，如何将n个任务分配到m台主机，同时保证每台计算机的资源使用率在四元组{Cj，Mj，Dj，Nj}的限定之内，这是对一个多维多背包问题的求解。

1.2任务分配问题的数学模型

背包问题是一种组合优化的NP完全问题[8]。问题可以描述为：给定n个物品，每种物品都有自己的重量和价格，第i个物品的重量为wi，价格为vi，在限定的总重量c内，应该如何选择，才能使得物品的总价格最高。其数学模型可表示为：

max∑ni=1vixi（1）

s.t∑ni=1wixi≤c

xi=0或1；i=1，2，…，n（2）

其中， xi表示物品是否被选装入：

xi=0，物品i不装入

1，物品i装入

多维多背包问题是背包问题的一类子集[9]，其中表示背包容量和物品大小的变量有多维表示，而且物品放入的背包可有多个选择[10]，在任务分配问题中可用主机的各种硬件资源{Cj，Mj，Dj，Nj}表示为背包问题中第j个背包容量，每个任务对各种硬件资源的需求量{ci，mi，di，ni}表示为第i个物品的大小，则任务分配问题的数学模型可表示为：

max∑ni=1∑mj=1vixij（3）

s.t∑ni=1∑mj=1cixij≤Cj

∑ni=1∑mj=1mixij≤Mj

∑ni=1∑mj=1dixij≤Dj

∑ni=1∑mj=1nixij≤Nj

xij=0或1；i=1，2，…，n；j=1，2，…，m（4）

其中，{Cj，Mj，Dj，Nj}表示第{Cj，Mj，Dj，Nj}台主机的CPU、内存、硬盘I/O以及网络带宽四个维度的容量，xij表示第i个任务是否被分配至第{Cj，Mj，Dj，Nj}台主机，用公式表示如下：

xij=0，任务i不分配至第j台主机

1，任务i分配至第j台主机（5）

2混合遗传算法

遗传算法是计算机科学人工智能领域中用于解决最优化的一种搜索启发式算法，是进化算法的一类分支。这种启发式的研究思路通常用来生成有用的解决方案来优化和搜索问题。进化算法最初是借鉴了进化生物学中的一些现象而衍生发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。而鉴于基本的遗传算法存在着局部搜索能力差以及容易产生早熟现象的缺点，结合云计算任务分配问题的特点，本文采用了遗传和贪心相结合的混合遗传算法，该算法克服了基本遗传算法局部搜索能力差以及容易产生早熟现象的缺点[11]。

2.1遗传算法的基因编码

传统的遗传算法基因编码方式多采用二进制编码，考虑任务分配问题可转化为0/1规划问题的特点，可以将问题的解直接映射成一个m×n的矩阵，以此作为遗传算法的基因编码，这种方法存在的缺点是基因长度为m×n，当问题规模较大时不利于搜索问题的优化解。

因为任务分配问题中，一个任务只能分配到一台主机，二进制编码中将会存在大量的冗余，所以本文中直接采用整数编码的方式，问题的解可表示为X={x1，x2，…，xn}，（xi∈{0，1，2，…，n}），例如将第i个任务分配至第j台主机，则xi=j，当xi=0时，则表示没有多余的资源可以执行第i个任务，任务未被分配。

采用整数基因编码方式优化解的搜索空间为O（mn），而采用二进制编码方式的搜索空间为O（2mn），当问题规模较大时，采用整数编码的遗传算法搜索空间要远小于采用二进制编码的搜索空间。

2.2修正种群个体

种群的个体在经过交叉和变异之后都会产生新的个体，但是这个个体不一定是可行解，所以要将种群中的不可行解修正为可行解，并且为了加快算法收敛的速度，要将可以优化的可行解进一步优化。在这里采用贪心算法实现这一功能，其算法流程如图1所示。

2.3目标函数与适应度函数

为了达到节能的目的，采用计算耗能作为目标函数，主机的能耗可表示为：

w=pT≤PT

其中，T为主机的运行时间，p为主机运行的实际功率，p为主机的额定功率，一般情况下都会满足p≤P，但在文中修正种群个体的过程中会保证各运行主机的硬件资源得到充分的利用，在这种情况下p≈P，所以选取目标函数为：

minW≈∑mj=1PjTj（6）

其中，Pj为第j台主机的额定功率，Tj为第j台主机的运行时间，由于云计算中一台主机可以运行多个任务，所以Tj为第j台主机上最长任务的执行时间，当主机未被分配任何任务时，则处于休眠状态，休眠状态下的主机耗电量为0。个体适应度函数选取目标函数的倒数：

2.4选择与遗传操作

遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。本文中选择算子采用轮盘赌选择方法，设种群中共有N个个体，个体xi被选中遗传到下一代的概率为：

p（Xi）=fitness（Xi）∑Nj=1fitness（Xj）（8）

个体杂交方式采用单点杂交方式，其主要过程如下：

（1）在染色体上随机选择一个交换点；

（2）确定是在交换点前面部分或者后面部分的基因进行交换；

（3）根据上述原则将两父本的染色体基因进行交换重组，从而形成新的个体。

2.5算法流程

改进后的混合遗传算法流程如下：

（1）初始化。 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体Population（t）；

（2）修正个体。使用贪心算法对个体进行优化和修正；

（3）个体评价。计算Population（t）中各个个体的适应度值；

（4）选择运算。将选择算子作用于群体；

（5）交叉运算。将交叉算子作用于群体；

（6）变异运算。将变异算子作用于群体，并通过以上运算得到下一代群体Population（t+1）；

（7） 终止条件。判断t≦T：t←t+1转到步骤（2）；t>T：终止输出解。

3算法仿真与结果分析

本文使用CloudSim[12]模拟了大规模云计算数据中心，并对基于混合遗传算法的任务分配策略进行了仿真和测试。实验中模拟了一个包含1 000台主机的与计算数据中心，对1 000个任务分配问题进行了仿真。1 000台主机和1 000个任务的数据为随机生成，为有利于仿真，数据完全按照CloudSim中主机和任务的量化标准生成。

3.1算法正确性验证

虽然任务分配问题是NP完全问题，在问题规模较大时得到最优解是非常困难的，但在问题规模较小时还是可以得到最优解的。为了验证算法的正确性，选取任务和主机都较少的情况进行验证，实验选取的3个任务、5台主机的任务分配问题进行验证，任务数据和主机数据如表1和表2所示，任务分配的结果如表3所示。

由表3可以看出，所有3个任务全部分配给了第三台主机。从表2可以看出第4台主机能耗较低，但其计算能力较弱，如果将任务全部分配给第四台主机就会出现资源争用的情况，降低程序运行的效率，为避免出现这种情况就必须开启其他主机，这样却会使能耗大大增加；第二台主机也能够完成三个任务的计算，但其功率相比第三台主机要大，完成任务所需的能耗更大，所以算法将三个任务全部分配给第三台主机是能耗最优的选择。

3.2算法收敛效果比较

为了验证改进的混合遗传算法在解决任务分配问题是否具有更好的性能，将其与基本的遗传算法和贪心算法做了比较，实验结果如图2所示。

图2中三条线分别为混合遗传算法、基本遗传算法和贪心算法计算所得优化解，因为本文中目标函数为能耗最低，所以值越低，说明该值越接近最优解。从图2中可以看出，混合遗传算法搜索优化解的结果要远优于贪心算法和基本的遗传算法。贪心算法虽然开始时搜索局部优化解的速度较快，但其对全局优化解的搜索能力却比较差，基本遗传算法搜索全局优化解的能力要比贪心算法强，但其搜索局部优化解的能力较弱，所以向最优解收敛的速度较慢，而混合遗传算法则结合了基本遗传算法和贪心算法的优点，其收敛速度较快。在实验中使用50个任务，1 000台主机，混合遗传算法种群进化1 000代的耗时为2.7s，基本遗传算法耗时1.8s，贪心算法为0.3s，算法执行时间有所增加，但仍在可以接受的范围内。

3.3仿真结果分析

CloudSim提供了资源的监测、主机到虚拟机以及虚拟机到任务的映射功能[13]，并且提供了能耗的仿真和计算模块，可以方便地模拟主机或者虚拟机的能耗，而且能够根据任务运行所占的资源量和所用时间给出任务执行所耗费的成本。

实验模拟云计算数据中心包含1 000台主机，任务数量从0到1 000不等，分别对随机任务分配算法、CloudSim能量感知任务分配算法[14]及基于混合遗传算法的任务分配算法的能耗和任务执行成本做了对比。对比结果如图3和图4所示，从图3和图4的对比结果可以看出，基于混合遗传算法的任务分配方式能够大大降低任务执行的总能耗，并且由于充分利用了计算机的硬件资源，避免了运行主机的空闲资源浪费，所以大幅降低了任务执行总成本，在任务总量越多时节能和节约成本的效果越明显。图 3不同任务分配算法能耗比较

4结束语

本文使用基于混合遗传算法对云计算数据中心任务分配策略进行了优化，优化后的任务分配策略能够有效地减少任务运行的总能耗，减少任务运行的成本。这种任务分配策略在解决云计算的任务调度、负载均衡、节能减排、成本最小化等问题时有着良好的应用价值。

参考文献：

[1]SRIKANTAIAH S， KANSAL A， ZHAO Feng. Energy aware consolidation for cloud computing[C]//HotPower'08 Proceedings of the 2008 Conference on Power aware Computing and Systems，2008：10.

[2]陈全，邓倩妮.云计算及其关键技术[J].计算机应用， 2009，（9）：2562-2568.

[3]PANDEY S，WU L，GURU M S，et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//IEEE International Conference on Advanced Information Networking and Applications，2010：400-407.

[4]CAO Qi，WEI Zhibo，GONG Wenmao. An optimized algorithm for task scheduling based on activity based costing in cloud computing[C]//Bioinformatics and Biomedical Engineering，2009：1-3.

[5]徐骁勇，潘郁，凌晨.云计算环境下资源的节能调度[J]. 计算机应用， 2012.32（7）：1913-1915.

[6]DUY T V，SATO Y， INOGUCHI Y. Performance evaluation of a Green Scheduling Algorithm for energy savings in Cloud computing[C]//IEEE International Symposium on Parallel &Distributed Processing， Workshops and Phd Forum，2010：1-8.

[7]王永贵，张伟，韩瑞莲.云环境下绿色任务调度策略[J].北京：计算机工程与应用， 2012：1-6.

[8]AKBAR M M， ERIC G， MANNING， et al. Heuristic solutions for the mltiple-choice multi-dimension knapsack problem[C]// Proceeding ICCS '01 Proceedings of the International Conference on Computational Science-Part II， 2001： 659-668.

[9]PUCHINGER J， GUNTHER R. RAIDL， et al. The multidimensional knapsack problem： structure and algorithms[J]. INFORMS Journal on Computing， 2010： 250-265.

[10]MARTELLO S，TOTH P. Knapsack Problems[M]. New York，，Springer-Verlag，2004：221-240.

[11]李晓萌， 戴光明， 石红玉. 解决多维0/1背包问题的遗传算法综述[J]. 电脑开发与应用， 2006，1：4-8.

[12]CloudSim a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software—Practice & Experience archive，2011：23-50.

[13]GARG S K，BUYYANETWORK R. CloudSim modeling parallel applications in cloud simulations[C]//IEEE International Conference on Utility and Cloud Computing，2011：105-113.

[14]BELOGLAZOV A， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation： Practice and Experience， 2012： 1397-1420.