摘要：云计算任务调度是云计算最重要的问题之一。为解决云计算调度问题，提出一种基于改进和声搜索的调度算法。该算法采用离散形式编码，以总的任务完成时间为优化目标，并对标准和声搜索算法中新和声产生方式进行了改进。最后，在CloudSim平台上进行了仿真实验。实验结果表明，新提出的算法具有较好的调度性能。
0引言
云计算的概念自2007年提出以来，迅速受到产业界和学术界的高度关注。以Google、Amazon、IBM和微软为代表的IT巨头纷纷推出自己的云计算产品。与此同时，许多国际学术会议也将云计算作为重要的讨论话题。作为一种成功的商业计算服务模式，云计算能够将计算任务分布在大量由计算机构成的资源池上，使得用户能够通过按需租用的方式获取其提供的计算力、存储空间和信息服务［1］。这些虚拟计算资源通常是一些大型服务器集群，包括计算服务器、存储服务器和宽带资源等［2］。当用户需要使用某些资源时，可以动态地向云计算系统提出申请，以支持各种应用程序的运转。在收到任务请求后，系统调度中心要及时分配资源。通常情况下，云计算的用户数量非常大，且系统本身是动态的、异构的。因此，如何设计一个高效的任务调度算法，既能够满足用户的要求，又使得运行成本最小，成为云计算系统的核心问题之一。
云计算任务调度本质上是一个组合优化问题。对于该类问题，很多研究学者采用启发式方法进行求解，取得了不错的结果。文献［3］利用离散粒子群结合模拟退火算法解决云调度问题，以降低总的综合执行成本为目标，提出一种混合算法，取得了不错的结果。文献［4］则将遗传算法和蚁群优化算法结合起来，提出一种基于多群智能算法的云计算任务调度策略。而文献［5］则提出一种多目标优化调度策略，试图同时满足多个资源调度优化目标。
和声搜索算法(Harmony Search，HS)是新近提出的一种启发式优化算法。该算法的结构比较简单，而且容易实现，在多维函数优化、车间调度等问题中取得了较好的结果，已经成为智能优化算法领域的又一个研究热点。
目前，和声搜索算法还没有被应用到云计算任务调度问题。因此，本文尝试将改进的和声搜索算法应用于云计算任务调度问题，并通过实验来验证该算法调度性能。
1云计算任务调度问题的数学模型
在云计算环境下，用户是以按需租用的形式使用系统资源的。一般来说，在保证资源得到充分利用的前提下，任务处理时间越短越好，这样用户需要支付的费用就越少，得到的服务质量也就越高。在云计算系统中，用户数量大大多于虚拟计算资源数，如果没有合理的调度方案，很容易产生死锁，造成系统利用率低下。为便于分析问题，将云计算调度问题抽象为将n个相互独立的子任务，分配到m个可用计算资源（即虚拟机）上执行（m<n），调度的目标是得到一个尽可能小的总任务完成时间。云计算任务调度的数学模型描述：（1）用tj(j=1,2,…,n)表示第j个需要调度的子任务，n为任务数，各个子任务间是相互独立的；（2）用vmi(i=1,2,…,m)表示第i个虚拟机，m为虚拟机数；（3）规定每个子任务只能分配且仅分配给一个虚拟机并执行；（4）用time(tj,vmi)表示任务tj在虚拟机vmi上的执行时间。那么对于一个给定的调度方案X，总任务完成时间应该为：
云计算调度算法的任务是设法找到一个调度方案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<HMCR，则xnew(j)在HM内的记忆空间产生；否则，按照初始化时的规则随机产生。其中，HMCR为和声记忆库考虑概率，是预设的一个参数；xnew(j)为xnew的第j维。
（2）按照微调扰动和随机选择规则，在［0,1］之间产生一个随机数τ2，如果τ2<PAR,则xnew(j)按照公式（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）和MinMin算法。为尽可能减少误差，保证实验结果的准确性，每次实验连续运行20次，取平均值作为实验数据。实验得到的各种算法的总任务完成时间如图1所示。
从图1可以看出，在任务规模不大的情况下，由于各个任务出现资源竞争的可能性较小，发生冲突的概率也较小，因此各个算法所得到的总任务完成时间差别不大。但是，随着任务数量不断增大，各个任务出现资源竞争的情况显著增多，调度的复杂度也急剧升高。这时，新提出的DHS算法显著优于其他算法，其调度所需要的总的任务完成时间在三种算法中是最少的。这主要是因为DHS算法具有良好的全局搜索能力，通过不断迭代，使种群朝着适应度值更优的方向进化。这说明，本文提出的DHS算法是可行的，能够在一定程度上处理不同规模的云计算调度问题。
4结论
一个好的任务调度算法能够显著提高云计算系统的性能。本文在基本和声搜索算法的基础上，从编码方式、新和声产生方式等方面对其进行了改进，提出一种基于离散和声搜索的云计算任务调度算法DHS。最后进行了仿真实验。实验表明，新提出的DHS算法在处理大规模任务时的性能显著优于轮询、MinMin等经典算法。
参考文献
［1］ 王波,张晓磊.基于粒子群遗传算法的云计算任务调度研究［J］.计算机工程与应用,2015,51(6):8488.
［2］ 刘鹏.云计算［M］ .北京：电子工业出版社，2011.
［3］ 赵轩,蔚承建,王开，等.离散PSO结合模拟退火算法解决云调度问题［J］ .微电子学与计算机,2013,30(5):137140.
［4］ 陈海燕.基于多群智能算法的云计算任务调度策略［J］.计算机科学,2014,41(6A):8386.
［5］ 徐忠胜,沈苏彬.一种云计算资源的多目标优化的调度方法［J］.微型机与应用,2015,34(13):1720.