李远征，佟国香

(上海理工大学 光电信息与计算机工程学院，上海200093)



云环境中基于混合和声算法的资源调度方案

李远征，佟国香

(上海理工大学 光电信息与计算机工程学院，上海200093)

随着信息技术的日趋成熟，任务、资源也呈几何倍数增长，对资源调度效率的要求不断提高，如何提高资源调度效率也成为了当前研究的热点。为此，文中针对调度策略提出了一种混合和声算法，加入遗传算法交叉操作和动态PAR方法，扩大基本和声算法的搜索范围并防止其陷入局部最优，以达到最短时间跨度的目的。通过Cloudsim云仿真平台进行仿真实验，实验结果表明，该算法明显减少了任务平均完成时间，有效提高了资源调度效率。

云计算; 资源调度; 和声算法; 遗传交叉操作; Cloudsim

LI Yuanzheng, TONG Guoxiang

(School of Photoelectric Information and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

云计算通过虚拟化技术[1-3]，将异构的硬件软件资源整合成云资源池，根据用户需求进行调度及分配，但由于云计算资源具有开放、异构、并行、海量数据及用户等特点，如何高效地进行资源调度是云计算发展过程中必须解决的关键问题[4-7]。

传统的调度方法如包括OLB、轮循调度算法、Min-Min算法、MCT算法、禁忌搜索等,这些方法具有原理简单、易实现的特点,但处理大规模复杂问题时性能不佳[8]。为此，本文提出一种混合和声算法资源调度的方案，并利用Cloudsim云仿真平台和其他算法加以比较，来证明本方案的可行性。

1 云资源调度模型

1.1 虚拟机资源描述

虚拟机资源集合VM={vm1, vm2, vm3, …,vmn}，其中各虚拟机可以统一表示为VMi={vmid,mips,size,ram,bw,pesNumber}。其中，vmid、mips、size、ram、bw、pesNumber分别表示虚拟机ID、每秒百万条指令、存储空间大小、内存空间大小、带宽和核数。

1.2 用户任务描述

设云环境中有用户任务集合中有n个任务:Task={task1, task2, task3,…. taskn}，其中，每个任务可简单统一表示为taski={Length,Filesize,Outputsize}。其中Length表示其任务长度，Filesize表示为输入任务文件大小，Outputsize表示输出文件大小。

1.3 调度过程描述

图1 云环境下任务资源调度模型

云计算中资源调度可分为两部分：第一部分为任务与虚拟机之间的分配调度；第二部分为虚拟机与主机之间的匹配。本文所解决的是第一部分的分配策略，即用户任务与虚拟资源的调度策略。

2 混合和声算法

和声搜索算法(Harmony Search, HS)算法首先由韩国学者 Geem 等人于 2001年提出的一种现代启发式算法。[9]和声算法通过模拟音乐家即兴创作不断调整尝试来达到最美和声的过程进行寻优。

虽然基本的和声搜索算法(HS)具有优秀的优化性能，但是其利用步长微调的策略不能有效的调节解向量的结构，容易陷入局部最优。为此，本文在和声算法的基础上加入了遗传算法的交叉操作，同时提出了一种动态调节PAR的方法。

2.1 遗传算法交叉操作的加入

遗传算法(GA)作为经典的启发式算法，已被广泛应用[10]，交叉更是其核心部分，为提高和声记忆库中解的多样性，本文将这个步骤加入和声算法。其基本操作原理为，当 rand

2.2 动态参数PAR的设计

基因调整概率PAR是和声搜索算法中的重要参数，一般来说，当PAR值较小时，算法的局部搜索能力比较强。[11]反之，当PAR较大时，算法具有较大的搜索范围。所以，本文所使用的PAR设计方案为

(1)

混合和声算法的步骤可以归纳为以下几步：

步骤1 对混合和声算法需要使用的参数进行初始化。主要参数包括问题的维数N，每一维参数N的取值范围[xL,xH] ，和声记忆库的范围HMS，记忆库取值概率HMCR，微调步长bw，音调微调概率PAR;

步骤2 和声记忆库初始化。和声记忆库存储了HMS个和声初始解，用矩阵HM表示如下

(2)

步骤3 生成新的和声向量。新的和声向量即为新的解向量，新解的产生规则如下

(3)

(4)

步骤4 更新和声记忆库。

步骤5 重复步骤3和步骤4，直到满足条件或者满足迭代次数。

具体实现过程如图2所示。

图2 混合和声算法流程图

3 混合和声算法的应用

和声算法和其他启发式算法一样，对于不同问题所采用的编码方式以及适应度函数都有所不同。本文采用实数编码方式进行编码，并将该和声组合适应度函数的值放到每个和声组合最后一位，执行任务的时间跨度作为适应度函数进行设计。

3.1 编码规则设计

图3 第i组和声序列

以图3为例，该数组表示和声库中的第i组和声序列。每个框中的数字代表第i个任务对应的虚拟机编号，即第1个任务由5号虚拟机处理，第2个任务由3号虚拟机处理，第3个任务由2号虚拟机处理，以此类推。此外，最后一列数组数值Fit(i)表示该和声序列的适应度值。

3.2 适应度函数设计

在云模型中，因为云资源调度能耗等问题都与任务处理完成时间有着直接的联系，所以本方法以调度处理时间为适应度函数来进行调度策略的研究。VM[i]表示第i个虚拟机资源，task[j]表示第j个任务。那么第j个任务在第i个虚拟机上运行的时间用式(5)表示

Tij→(VM[i],task[j])

(5)

适应度函数可以写作

(6)

4 仿真实验

因为构建实际的云平台成本高、效率低，所为简化云平台的建设与测试过程，澳大利亚墨尔本大学云计算与分布式系统实验室开发了CloudSim仿真软件。本方案采用云仿真平台Cloudsim对混合和声算法进行验证。

为符合实际情况，本实验设置了不同大小的虚拟机、任务以及多种带宽。具体实验参数如表1所示。

表1 实验平台参数

表2 混合和声算法参数设置

本实验分别在相同虚拟机个数以及相同任务个数两种情况下进行。

实验1 设定虚拟机个数为5，任务数量分别为10,20,30,40,50,60,70,80,90,100。分别使用混合和声算法(HHS)和蚁群算法(ACO)进行对比。由图4可以明显的看到随着任务个数的增加，混合和声算法花费的时间不仅一直小于蚁群算法，并且随着任务数量的增加，两种算法的运行时间差越来越大。

图4 不同任务个数各调度方法所需时间

图5 不同虚拟机个数各调度方法所需时间

实验2 设定任务数量为100个，虚拟机的数量分别为6,7,8,9,10,11,12,13,14,15。由图5发现，随着虚拟机个数的增加，混合和声算法和蚁群算法运行时间均有所浮动，但混合和声算法调度策略花费的时间还是要远小于蚁群算法。

5 结束语

本文提出一种混合和声调度算法，通过实验证明该算法可缩短时间跨度，提高调度效率。但本文仅是采用了运行时间这一适应度函数进行约束，在实际应用中影响分配效率的因素还有很多，下一步工作是结合多种约束条件进行算法的应用与研究。

[1] 储雅,马廷淮,赵立成.云计算资源调度:策略与算法[J].计算机科学,2013(11):8-13.

[2] 李舰锋,彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用,2011, 31(1):184-186．

[3] Mahdavi M, Fesanghary M, Damangir E. An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics and Computation,2007,188(2):1567-1579.

[4] Tang M,Pan S. A hybrid genetic algorithm for the energy-efficient virtual machine placement problem in data centers[J].Neural Processing Letters, 2014,41(2):211-221.[5] Beloglazov A,Abawajy J,Buyya R.Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J].Future Generation Computer Systems,2012,28(5):755-768.

[6] 吴国芳.云环境中基于布谷鸟搜索算法的多目标任务调度方案[J].计算机应用研究,2015,9(9):2674-2677.

[7] Calheiros R N，Ranjan R，Beloglazov A,et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice & Experience,2011,41(1):23-50

[8] 李锋华.基于蚁群算法的云计算资源负载均衡调度算法研究[D].昆明:云南大学,2013．

[9] 刘晓茜.云计算数据中心结构及其调度机制研究[D].合肥：中国科学技术大学,2011.

[10] Andrew J Younge,Gregor Von Laszewski,Wang Lizhe,et al.Efficient resource management for cloud computing environments[C].Noven:International Conference on Green Computing,2010.

[11] Calheiros R N,Ranjan R,Beloglazov A，et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice & Experience,2010,41(1):23-50.

[12] 李若平.学习型和声搜索算法及其在0_1背包问题中的应用[J].控制与决策，2013,28(2):205-210.

Resource Scheduling Based on Hybrid Harmony Search Algorithm in Cloud Environment

The exponential growth of tasks and resources in the information industry asks for more efficient resource scheduling. In this paper, we presents a hybrid algorithm harmony scheduling algorithm by combining the crossover of genetic algorithm and the dynamic PAR method to expand the search range of basic harmony search algorithm and preventing falling into local optimum, thus achieving the shortest time. Cloudsim simulation shows this algorithm can significantly reduce the average schedule time.

cloud computing; resource scheduling; crossover of genetic algorithm; harmony search; Cloudsim

2016- 01- 05

李远征(1990-)，男，硕士研究生。研究方向：启发式算法等。

10.16180/j.cnki.issn1007-7820.2016.10.015

TP391

A

1007-7820(2016)10-051-04