基于离散和声搜索的云计算任务调度研究

姜 凯

(聊城大学 东昌学院 ，山东 聊城 252000)

基于离散和声搜索的云计算任务调度研究

姜 凯

(聊城大学 东昌学院 ，山东 聊城 252000)

云计算任务调度是云计算最重要的问题之一。为解决云计算调度问题，提出一种基于改进和声搜索的调度算法。该算法采用离散形式编码，以总的任务完成时间为优化目标，并对标准和声搜索算法中新和声产生方式进行了改进。最后，在CloudSim平台上进行了仿真实验。实验结果表明，新提出的算法具有较好的调度性能。

云计算；任务调度；离散和声搜索算法

0 引言

云计算的概念自2007年提出以来，迅速受到产业界和学术界的高度关注。以Google、Amazon、IBM和微软为代表的IT巨头纷纷推出自己的云计算产品。与此同时，许多国际学术会议也将云计算作为重要的讨论话题。作为一种成功的商业计算服务模式，云计算能够将计算任务分布在大量由计算机构成的资源池上，使得用户能够通过按需租用的方式获取其提供的计算力、存储空间和信息服务[1]。这些虚拟计算资源通常是一些大型服务器集群，包括计算服务器、存储服务器和宽带资源等[2]。当用户需要使用某些资源时，可以动态地向云计算系统提出申请，以支持各种应用程序的运转。在收到任务请求后，系统调度中心要及时分配资源。通常情况下，云计算的用户数量非常大，且系统本身是动态的、异构的。因此，如何设计一个高效的任务调度算法，既能够满足用户的要求，又使得运行成本最小，成为云计算系统的核心问题之一。

云计算任务调度本质上是一个组合优化问题。对于该类问题，很多研究学者采用启发式方法进行求解，取得了不错的结果。文献[3]利用离散粒子群结合模拟退火算法解决云调度问题，以降低总的综合执行成本为目标，提出一种混合算法，取得了不错的结果。文献[4]则将遗传算法和蚁群优化算法结合起来，提出一种基于多群智能算法的云计算任务调度策略。而文献[5]则提出一种多目标优化调度策略，试图同时满足多个资源调度优化目标。

和声搜索算法(Harmony Search，HS)是新近提出的一种启发式优化算法。该算法的结构比较简单，而且容易实现，在多维函数优化、车间调度等问题中取得了较好的结果，已经成为智能优化算法领域的又一个研究热点。

目前，和声搜索算法还没有被应用到云计算任务调度问题。因此，本文尝试将改进的和声搜索算法应用于云计算任务调度问题，并通过实验来验证该算法调度性能。

1 云计算任务调度问题的数学模型

在云计算环境下，用户是以按需租用的形式使用系统资源的。一般来说，在保证资源得到充分利用的前提下，任务处理时间越短越好，这样用户需要支付的费用就越少，得到的服务质量也就越高。在云计算系统中，用户数量大大多于虚拟计算资源数，如果没有合理的调度方案，很容易产生死锁，造成系统利用率低下。为便于分析问题，将云计算调度问题抽象为将n个相互独立的子任务，分配到m个可用计算资源(即虚拟机)上执行(m

(1)

云计算调度算法的任务是设法找到一个调度方案X，使得总任务完成时间最小。

2 基于离散和声搜索的云计算任务调度算法

2.1 基本和声搜索算法

和声搜索算法是Geem等人受音乐家创作过程的启发，于2001年提出的一种元启发式全局优化算法。在该算法中，解空间中的每个解为一个“和声” ，它实际上是一个N维的实数矢量。算法首先产生一个规模为HMS的初始种群，称为初始的和声记忆库(Harmony Memory，HM)。初始种群以随机的方式产生，产生的所有初始和声组成和声记忆库；接着，和声搜索算法根据记忆考虑、微调扰动、随机选择这三个规则产生一个新的候选解xnew，然后将xnew与HM内的最差解进行比较，如果新解优于最差解，则进行替换，用这种方式来不断更新和声记忆库。算法不断进行迭代，直至达到指定的最大迭代次数。

2.2 云计算任务调度算法的实现

和其他启发式算法一样，和声搜索算法也是问题依赖的。基本和声搜索算法采用连续编码方式，不能直接用于解决离散优化问题。因此，为解决云计算任务调度问题，必须对基本和声搜索算法从和声编码、适应度函数定义、算子设计等多个方面进行改进，使之适合云计算任务调度问题。

2.2.1 和声编码及其初始化

由于云计算调度本身是离散优化问题，为简化计算过程，新算法采用“任务-虚拟机”间接离散编码方式，即一个和声的编码长度为子任务个数，每一位编码的位置代表对应的子任务，每一位编码的数值代表分配的虚拟机编号。

假设要将n个子任务分配到m个虚拟机上执行，则n个子任务依次编号为0～n-1，m个虚拟机编号依次为0～m-1。如果用长度为n的数组Xi表示一个和声，则满足i∈[0,n-1]且Xi∈[0,m-1]。

例如，要将6个子任务(T0,T1,T2,T3,T4,T5)分配到4个虚拟机(V0,V1,V2,V3)上执行，如果某个个体编码为[2,1,0,3,2,3]，则表示子任务T2分配给虚拟机V0，子任务T1分配给虚拟机V1，子任务T0和T4分配给虚拟机V2，子任务T3和T5分配给虚拟机V3。在此基础上，很容易就可以求出总任务完成时间。

和声库的规模为HMS，算法在初始化时，首先按照上述规律随机生成一个长度为n的和声，然后重复进行HMS次，得到一个HMS×n矩阵，组成初始和声记忆库。

2.2.2 适应度函数

适应度函数是优化的目标，和声搜索算法正是以适应度函数为目标函数，在解空间中不断迭代寻找最优解，并以此为依据来对种群中的个体进行评价。因此，适应度函数的选择对于利用好和声搜索算法至关重要。考虑到计算的复杂性，新算法以公式(1)作为适应度函数。

2.2.3 新和声的产生

产生新和声这一步骤类似于遗传算法的选择、交叉和变异操作，是算法的核心，主要目的是产生新的和声个体，使得种群向着适应度函数值更优的方向进化。由于本算法采用离散的编码，因此要对基本和声搜索算法进行改进，采用如下方法来产生一个新的和声向量xnew：

(1)基于记忆考虑和随机选择规则，算法首先在[0,1]之间产生一个随机数τ1，如果τ1

(2)按照微调扰动和随机选择规则，在[0,1]之间产生一个随机数τ2，如果τ2

(2)

(3)

上述两公式中，PAR是算法的声音调微调概率，也是一个预设的参数，τ3和τ4是[0,1]之间的随机数。

2.2.4 和声记忆库的更新

产生新和声后，算法随后要更新和声记忆库。更新和声记忆库的依据是适应度函数值的优劣，即如果产生的新和声xnew所对应的函数值优于原来和声记忆库中函数值最差的和声xw所对应的适应度值,则用新的和声xnew替换xw，否则不再替换。

综上所述，新提出的离散和声搜索调度算法(记作DHS算法)的步骤如下：

Step1：算法参数初始化。设置和声记忆库的大小HMS、和声记忆库考虑概率HMCR、声音调微调概率PAR以及最大迭代次数NI等参数。

Step2：初始化和声记忆库。按照2.2.1节的方法产生初始和声记忆库，并使用公式(1)计算每个和声的适应度函数值。

Step3：产生新的和声。对和声记忆库中的每一个和声，利用2.2.3节提出的记忆考虑、微调扰动、随机选择规则产生新和声xnew。

Step4：和声记忆库更新。将新产生的解xnew与HM内的最差解进行比较，如果新解优于最差解，则进行替换。

Step5：判断是否终止。若当前迭代次数达到NI则终止；否则转向Step3继续执行。

3 仿真实验分析

通过仿真实验评价和分析本文提出的和声搜索算法DHS的调度性能。实验在墨尔本大学开发的云计算仿真平台CloudSim3.0.3上进行。在实验时，首先对DataCenterBoker类进行扩展，在该类中添加自己编写的DHS调度算法的方法，该方法能够实现DHS算法功能，从而完成对DHS调度算法的模拟。编程时使用的编程语言为Java，开发环境为Eclipse4.4.2和JDK1.8。实验在CPU 为3.4 GHz、内存为4 GB、安装Windows 7操作系统的主机上进行。由于云计算本身是处于动态和异构环境下的，为了充分验证算法的性能，本文设计了如下实验。

实验中设置的虚拟机数为10，随机产生50、100、500、1 000、1 500和2 000个任务进行调度，旨在考察不同规模情况下新算法DHS的调度性能。其中，每个虚拟机的CPU数量、内存大小、MIPS、网络带宽等指标由MATLAB随机生成。为保证实验具有可比性，前一轮实验产生的任务要包含在后一轮实验的任务当中。对比算法采用轮询调度算法(RR)和Min-Min算法。为尽可能减少误差，保证实验结果的准确性，每次实验连续运行20次，取平均值作为实验数据。实验得到的各种算法的总任务完成时间如图1所示。

图1 不同任务数量下总任务完成时间

从图1可以看出，在任务规模不大的情况下，由于各个任务出现资源竞争的可能性较小，发生冲突的概率也较小，因此各个算法所得到的总任务完成时间差别不大。但是，随着任务数量不断增大，各个任务出现资源竞争的情况显著增多，调度的复杂度也急剧升高。这时，新提出的DHS算法显著优于其他算法，其调度所需要的总的任务完成时间在三种算法中是最少的。这主要是因为DHS算法具有良好的全局搜索能力，通过不断迭代，使种群朝着适应度值更优的方向进化。这说明，本文提出的DHS算法是可行的，能够在一定程度上处理不同规模的云计算调度问题。

4 结论

一个好的任务调度算法能够显著提高云计算系统的性能。本文在基本和声搜索算法的基础上，从编码方式、新和声产生方式等方面对其进行了改进，提出一种基于离散和声搜索的云计算任务调度算法DHS。最后进行了仿真实验。实验表明，新提出的DHS算法在处理大规模任务时的性能显著优于轮询、Min-Min等经典算法。

[1] 王波,张晓磊.基于粒子群遗传算法的云计算任务调度研究[J].计算机工程与应用,2015,51(6):84-88.

[2] 刘鹏.云计算[M] .北京：电子工业出版社，2011.

[3] 赵轩,蔚承建,王开，等.离散PSO结合模拟退火算法解决云调度问题[J] .微电子学与计算机,2013,30(5):137-140.

[4] 陈海燕.基于多群智能算法的云计算任务调度策略[J].计算机科学,2014,41(6A):83-86.

[5] 徐忠胜,沈苏彬.一种云计算资源的多目标优化的调度方法[J].微型机与应用,2015,34(13):17-20.

Study on task scheduling in cloud computing based on discrete harmony search

Jiang Kai

(Dongchang College, Liaocheng University,Liaocheng 252000, China)

Task scheduling is one of the most important issues in cloud computing. In order to solve the problem of cloud computing scheduling, a scheduling algorithm based on improved harmony search is proposed. The new algorithm uses the discrete form of encoding and employs the total task completion time as the optimization objective. At the same time, a new harmony generation method is introduced in the proposed algorithm. Finally, a simulation experiment is carried out on the CloudSim platform. Experimental results show that the new algorithm has better scheduling performance.

cloud computing; task scheduling; discrete harmony search

TP393

A

1674- 7720(2016)03- 0021- 03

姜凯．基于离散和声搜索的云计算任务调度研究[J] .微型机与应用，2016，35(3)：21- 23.

2015-11-05)

姜凯(1986-)，男，硕士，助教，主要研究方向：智能优化、云计算。