基于改进多目标布谷鸟搜索的资源调度算法

程 曦 宋铁成

1(四川文理学院康养产业学院 四川 达州 635000)2(重庆邮电大学通信与信息工程学院 重庆 400065)

0 引 言

云计算是一种通过网络为用户提供软件、数据库、计算、存储和安全性服务的范例。资源管理是云计算中提出的核心问题，包括资源分配、资源调度、资源发现、资源监视、资源可用性和资源定价等方面[1-2]。资源调度是从适当的物理资源中选择最佳的虚拟化资源，即对要在其中生成虚拟机(VM)的物理资源进行分类，以分配来自云设备的资源[3]。因此，在云计算环境中的基础架构即服务(IaaS)下，资源调度是一个多目标问题[4]。为此，需要一种优化算法来解决多目标问题，实现资源合理调度。

多目标优化的任务是针对一组确定的限制同时优化两个或多个冲突目标。但是，在云计算环境下，优化过程容易出现改善一个目标会导致另一个目标降级的难题。近年来，研究人员采用元启发式优化算法来处理资源调度的多目标问题[5]。Gobalakrishnan等[6]提出了一种基于遗传算法和灰狼优化算法相结合的优化技术，实现了云计算环境下负荷利用率、能耗、迁移成本和迁移时间组成的多目标函数的优化，实现了高效的任务调度，降低了时间和迁移成本，但是该算法存在求解精度低和后期收敛速度慢等问题。Agarwal 等[7]提出一种基于布谷鸟搜索的任务调度方法，该方法在可用的虚拟机之间有效地分配任务，并保持总体响应时间最小，使计算资源得到最佳的利用。Krishnadoss 等[8]提出了一种基于布谷鸟搜索算法和反向学习算法的多目标任务调度策略，该策略采用完成时间和成本作为优化问题的重要约束条件来求解任务调度的NP完全问题，实现了高性能、低成本的资源动态分配的目标。虽然布谷鸟搜索算法操作简单、通用性强，但是存在搜索速度慢、容易陷入局部最优的缺点。Srichandan等[9]通过结合遗传算法和细菌觅食算法两种生物启发式算法从经济和生态的角度方面降低了能源消耗。Abdullahi等[10]针对IaaS云计算环境下的多目标大规模任务调度优化问题，提出了一种混沌共生生物搜索算法。采用混沌优化策略生成初始种群，并用混沌序列代替基于随机序列的SOS相分量，以保证生物多样性，实现了全局收敛，但是收敛速度慢。

针对当前用于解决IaaS云计算的资源调度多目标优化算法中存在的诸多问题，提出一种基于改进多目标布谷鸟搜索的资源调度算法，通过改进随机游走策略和丢弃概率策略提高了算法的局部搜索能力和收敛速度，从而实现以最低的执行时间和成本将任务分配特定的VM中，满足云用户对云提供商的资源利用需求，减少延迟，提高资源利用率和服务质量。

1 云计算资源调度描述

云计算中的资源调度是一种多目标优化过程[11]，适用于处理器、网络、存储和VM等云资源的分发，根据云用户的需求平均分配资源，实现云资源的最佳利用，确保云计算能够以云提供商所提供的一定质量的服务来满足所有云用户的请求。资源调度(Resource Scheduling，RS)问题可以描述为：

(1)

假设存在一组任务Ti=(T1,T2,…,Tn)，云计算已将其映射到虚拟资源Vj=(V1,V2,…,Vm)上，而后被调度到物理设备中执行。则任务与资源之间的对应关系可以用矩阵表示为：

(2)

式中：xij∈{0,1}表示为第i个任务Ti与第j个资源Vj的对应关系，当xij=1时，表示任务Ti占据资源Vj，反之则没有。根据任务与资源之间的对应关系，任务Ti经过资源传递到达物理设备上执行的预期完成时间可以表示为：

(3)

同理，预期完成成本ECC可以定义为：

(4)

式中：Ci=(C1,C2,…,Cn)表示为任务成本。

根据预期完成时间ETC和预期完成成本ECC，云计算环境中资源节点完成子任务所花费的时间和成本可以计算为：

(5)

(6)

式中：t(i,j)和res(i,j)分别表示任务Ti在资源Vj的所需时间和成本;sumTime(i,j)和sumCost(i,j)分别表示任务完成的总时间和总成本。

2 改进多目标布谷鸟搜索的调度策略

当前大多数资源调度算法通过考虑不同的因素(如完成时间、执行所有用户任务的总成本、资源利用率、能耗和容错能力)进行优化，优先约束并行应用的求解时间与能耗之间的折中问题是一个双目标优化问题。这个问题的解决办法是一组帕累托点。针对大多数情况下IaaS云资源调度不够而产生的利用率低的问题，本文提出一种基于改进多目标布谷鸟搜索的资源调度算法，以完成时间和成本为优化目标，用最小的ETC和ECC矩阵将任务分配到虚拟资源上，提高资源利用率。

2.1 多目标布谷鸟搜索算法及改进措施

布谷鸟搜索算法(Cuckoo Search Algorithm，CSA)[12]是在2010年由Yang等提出的一种生物启发式智能优化算法，该算法参考了自然界中布谷鸟的寄宿繁衍行为和果蝇的莱维飞行行为，结构简单，易于实现，具有很好的全局搜索能力。鉴于CSA局限于单目标问题的优化，Yang等在2013年提出了多目标布谷鸟搜索优化(Multi-Objective Cuckoo Search Optimization，MOCSO)算法[13]，该算法可以直接求解Pareto最优解集，应用于多目标优化领域。

多目标布谷鸟搜索算法的3个基本假设是在原来CSA假设的基础上为满足k个目标的需求而做出一定的修改：

(1) 每只布谷鸟一次可产k个蛋，并随机选择一个寄生巢放置，第k个蛋即是一组解的第k个目标。

(2) 在随机选择的一组寄生巢中，最好的巢将会保留到下一代继续繁殖。

(3) 每个巢中的宿主鸟丢弃外来蛋的概率为Pa，被发现后布谷鸟选择更换一个具有k个蛋的新巢。

布谷鸟蛋的寄生巢表示搜索空间的一个解，寄生巢位置表示解的适应度值，布谷鸟搜索可以通过莱维飞行来更新t+1时刻的位置：

(7)

式中：i=1,2,…,n，Levy为莱维飞行搜索；α为步长控制量，可以引入不同解之间的差来增加算法的收敛速度。α的计算如下：

(8)

式中：α0是个常数。

MOCSO中鸟巢位置的更新由解的相似性决定的：

(9)

图1给出了多目标布谷鸟搜索算法的流程。

图1 多目标布谷鸟搜索算法流程示意图

在多目标优化过程中，其理想最优解是可以完全支配其他解的解，但在优化过程中往往获得的是多个相互妥协的解，即Pareto解。虽然MOCSO考虑了新解和旧解之间的支配关系，但是由于该算法是基于单目标算法之上的，在优化过程中缺乏对个体之间相互支配关系的考虑。除此之外，MOCSO中的游走策略虽然能够很好地保持算法的全局搜索能力和解的多样性，但是由于缩放因子r是一个随步长而改变的随机数，在搜索后期会因步长的变小而变小，使得解的多样性降低，陷入局部最优。同时，发现概率Pa为一固定值，无论解的适合度值多高，均会存在Pa概率被丢弃，这种方式会忽略较好的解，影响最终优化结果，也不适用于MOCSO。

针对上述两点，本文从丢弃频率和游走策略两个方面做适当改进。首先重新定义丢弃概率：将优化过程中产生的新解与旧解合并，按适应度大小排序；修改丢弃概率Pa，将其设定为一个区间Pa∈[Pmin,Pmax]；最后将区间[Pmin,Pmax]划分为等间距且长度与解个数相同的子集，即形成一一对应关系，最高适应度的解对应最低丢弃概率，反之对应最高丢弃概率。而丢弃概率的最大值与最小值定义为：

Pmax=max(Pmax)·(1-t/max_iter)

(10)

Pmin=max(Pmin)·(1-t/max_iter)

(11)

式中：max_iter表示最大迭代次数。

其次，针对式(9)中存在的搜索后期解空间内多样性降低的问题，提出下面的游走策略：

(12)

式中：rand是在均匀分布在[0,1]中的随机数，该策略增加了解更新方向的随机性，从而增强了解空间个体的多样性。

2.2 多目标资源调度问题

本文将完成时间和成本作为IaaS云计算环境中优化资源调度的多目标函数，利用改进的MOCSO对多目标函数进行优化。云计算资源调度的目标适应度函数是花费时间和成本的加权：

F= min(λ·sumTime+μ·sumCost)

(13)

式中：λ和μ表示加权系数。基于改进的MOCSO的多目标资源调度算法的伪代码由算法1给出。

算法1基于改进MOCSO算法的多目标资源调度算法

输入：丢弃概率Pa∈[Pmin,Pmax]，游走策略参数r，种群数量为n的初始化xi(i=1，2，…，n)，最大迭代Maxitr，目标函数Fi(x)=f(xi)。

输出：最优解Sbest。

While((t

基于莱维飞行随机生成一个解；

评估解的适合度Fi；

if (Fi是Pareto 最优)

从n个巢中随机选择一个j巢；

评估j巢的K个解；

if (Fi>Fj) then

将Fi替换Fj；

end if

end if

丢弃部分适合度低的巢，通过莱维飞行在新位置建造新巢；保留最好的巢，留给下一代；

对当前解进行排序并找到当前最佳的Pareto最优；

t←t+1；

end while

返回最优解Sbest；

3 实验与结果分析

为了评价本文算法的性能，使用CloudSim3.0仿真软件进行测试实验，并在相同条件下与基于布谷鸟多目标优化(MOCSO)、基于简化群多目标优化(MOSSO)[14]、基于粒子群多目标优化(MOPSO)[15]和基于蚁群多目标优化算法(MOACO)[16]的任务调度方法相比。采用完成时间、成本和利用率三个性能评价指标评估本文方法的性能。表1给出了仿真实验运行环境的详细信息。

表1 实验运行环境的详细信息

3.1 数据集及评价指标

本文采用HPC2N、NASA Ames iPCS / 860和SDSC三个工作负载档案集[17]进行测试，这些档案集提供了CloudSim工具认可的标准工作负载格式(.swf)。HPC2N数据集包括527 371个任务的统计数据，NASA包括14 794个任务的统计数据，SDSC包括73 496个任务的统计数据。在云计算环境中，这些数据集用于评估算法的性能。

为了对比本文算法与其他启发式资源调度优化算法的测试结果，采用完成时间、成本、资源利用率三个指标来评进行价。下面给出三个指标的数学定义。

资源调度的完成时间是通过VM上所有任务映射的完成时间来确定执行的最大完成时间：

(14)

式中：ti表示任务Ti的完成时间。

成本表示针对资源使用或利用率产生的总金额， VM的成本根据云提供商所确定的大量时间和VM的描述而有所不同。下面给出用于计算完成特定VM任务的成本：

(15)

式中：Ci表示单位时间内资源i的使用成本；resourcei表示资源i。

利用率是指数据中心主映射有效利用的资源量：

(16)

3.2 结果分析

利用多目标资源调度的完成时间、成本和资源利用率三个指标评估提出的改进MOCSO在IaaS云计算环境中的优化性能。图2给出了不同资源调度算法在HPC2N、NASA和SDCS三个工作负载数据集测试的完成时间。

图2 不同资源调度算法在三个数据集上的完成时间

测试过程中使用200～2 000范围内各种数量的任务进行仿真。将三种云计算资源调度算法用于与提出的改进MOCSO进行比较。可以看出，随着任务数量的增加，资源调度算法的完成时间会增加。结果表明，相比于标准MOCSO，改进的MOCSO的完成时间有所降低，同时还可以看出，本文算法的效果比其他三种对比算法要好。

图3给出了不同资源调度算法在HPC2N、NASA和SDCS三个工作负载数据集测试的成本。 可以看出，随着任务数量的增加，资源调度算法的成本也随之增加。本文算法计算出的成本低于其他四种算法， 该结果表明提出的改进MOCSO在云计算环境中支持云用户减少开支。

图3 不同资源调度算法在三个数据集上的成本

图4给出了不同资源调度算法在HPC2N、NASA和SDCS三个工作负载数据集测试的资源利用率。 可以明显看出，随着任务数量的增加，资源调度算法的资源利用率下降。与其他四种算法相比，本文算法在资源利用率上具有一定的优势。

图4 不同资源调度算法在三个数据集上的利用率

仿真结果和分析结果表明，提出的改进MOCSO在完成时间、成本、利用率方面提供了更好的质量结果，相较于标准MOCSO有了不错的提升。进一步阐明了改进MOCSO非常适合IaaS云计算环境中的ETC和ECC矩阵。从性能评估可以看出，改进MOCSO可能是一种强大的搜索和优化技术，足以解决IaaS云计算环境中资源调度的多目标问题。

4 结 语

本文提出一种基于改进多目标布谷鸟搜索的资源调度算法，用于解决IaaS云计算环境中资源调度的多目标问题。该算法在多目标布谷鸟搜索算法的基础上，为了提高优化算法的局部搜索能力和收敛速度，在随机游走和丢弃概率两个地方做出了一定的改进。本文算法用最小的ETC和ECC矩阵将任务分配到虚拟资源上，以最大限度地减少完成时间和成本，解决IaaS云资源因为调度不够而导致利用率低的问题。实验结果表明，与其他算法相比，本文算法在评估指标上提供了更好的质量结果。