改进松鼠搜索算法的云计算多目标任务调度

陈孝如，曾碧卿

(1.广州软件学院 软件工程系，广东 广州 510990；2.华南师范大学 软件学院，广东 佛山 528225)

0 引 言

近年来，为了满足大规模应用程序的计算需求，云计算凭借其计算资源的高效性和灵活性得到了大规模部署[1]。云计算提供服务的主要形式有3种，分别为：基础设施即服务(infrastructure as a service，IaaS)、平台即服务(platform as a service，PaaS)以及软件即服务(software as a service，SaaS)[2,3]。其中，IaaS可实现大规模应用程序部署，能够提供灵活和可扩展计算资源的访问[4]。然而，在IaaS云上高效且有效的执行大规模任务调度，仍然是一个亟待解决的问题[5]。

近年来，各种启发式算法被用于求解任务调度问题，取得了一定的成效[6]。然而，面对大规模计算任务时，元启发式算法的计算时间较长，由于局部搜索与全局搜索过早收敛和失衡的影响，可能会使算法陷入局部最优解。不同于传统的元启发式算法，松鼠搜索算法(squirrel search algorithm，SSA)[7]具有鲁棒性和更快的收敛速度，在处理多目标约束优化问题的同时，可对复杂的多维搜索空间进行有效地优化。由于无需特定的算法参数，SSA已被用于解决任务调度、无线通信以及经济调度等优化问题[8]。

基于上述分析，针对云计算中大规模应用程序的任务调度问题，提出一种改进SSA的云计算多目标任务调度方法，以对搜索空间进行有效的优化，合理调度多目标任务。所提方法的创新点总结如下：

(1)为了实现任务的高效调度，构建IaaS云模型，基于该模型设计多目标任务调度算法框架，并将成本和执行时间的最小化作为目标函数，从而有效地将用户任务分配给各种可用的处理单元；

(2)由于传统SSA存在容易陷入局部最优的问题，所提方法将入侵杂草优化算法(invasive weed optimization，IWO)的空间变异和扩散机制应用于SSA，并利用改进型SSA求解多目标优化问题，从而在最短时间内寻得最优调度方案。

1 相关研究

任务调度优化分为单目标优化和多目标优化。单目标优化方法只对完工时间或成本进行优化。然而，由于云计算的快速发展，需要考虑到多个服务质量(quality of service，QoS)目标，使得任务调度成为一个多目标优化问题[9]。由于用户和提供者各自具有不同的优化目标，故多目标任务优化问题较为复杂[10]。就目前的研究现状而言，针对云环境下的多目标任务调度优化问题的求解，主要采用的方法有启发式算法、分层方法以及帕累托优化等[11,12]。

文献[13]提出一种改进的非支配排序遗传算法得出Pareto最优解集，并利用模糊优选法对该解集进行选优，确定了产品开发任务调度的最优执行方案。通过两个经典多目标测试函数的求解及对比分析结果表明了改进算法的有效性和优越性。但在优化应用程序的执行时间、可靠性和负载平衡时未考虑计算资源的异构性。文献[14]提出了一种蚁群算法的测试任务并行任务调度优化方法，对测试问题进行描述并与蚁群算法结合，设计了启发函数、状态转移规则；通过依据算法流程来得到测试速度最快的任务调度序列；在任务序列多解的问题上，主要是通过提出资源均衡度的评价标准，得到最优的资源任务调度序列。然而，不同目标的结果取决于所分配权重的值，这些权重值也许不能充分代表用户的决策。此外，该方法只产生不适合多目标决策问题的解决方案。

分层方法按顺序优化任务调度目标，根据目标的重要性确定任务调度目标的优化次序，并根据目标的排序交替求解[15]。例如，文献[16]提出一种基于蚁群算法的分层调度算法，将调度过程分为预分配、粗略调度和精细调度3个步骤，对目标函数进行顺序优化。测试结果表明，使用这种新机制可以有效地减少计算时间。文献[17]提出一种基于离散粒子群算法的静态任务调度方法；求解过程中假定任务是非优先并且独立的，使用负载平衡技术提高了方法的性能。然而，该方法时效性较差，优化过程需要多次迭代，尤其是当有多个目标约束时[18]。

为了克服聚合和分层方法的缺点，提出了基于帕累托的优化方法，以解决多目标任务调度问题。帕累托方法为优化问题的目标找到了几个最优的折衷方案。使用帕累托支配的概念来为个体分配适应度。帕累托方法不需要将多个目标转化为单目标公式，并在一个单一的过程中产生多个权衡解决方案。文献[19]提出了工作流任务调度问题的多目标遗传算法，在考虑任务优先级的同时还兼顾了云计算中的任务能耗。使任务的完工时间和成本达到最小化。采用遗传算法解决了完工时间、成本和能耗之间的帕累托最优权衡问题，仿真结果表明了该方法的有效性。同样，文献[20]基于包括车辆云、路边小云和集中式云三层体系结构，提出一种混合自适应粒子群优化(hybrid adaptive particle swarm optimization，HAPSO)算法资源分配和任务优化调度算法，可以有效地满足来自道路用户的大量任务请求，同时保持改进的服务质量。结果表明，对于多目标优化调度问题，HAPSO的收敛速度比标准粒子群优化和自适应粒子群优化更具优势。然而，在帕累托任务调度方法中，由于帕累托优势是一个偏序，很难为下一代选择合适的个体。因此，如果选择算子不能保持足够的多样性，所得到的解可能无法覆盖整个帕累托前沿，则在开发多目标任务调度有效分配个体适应度的同时保持对整个优化方案的有效估计，仍是一个具有挑战性的研究课题。

Jain M提出了SSA[21]，该算法模仿了飞松鼠的动态跳跃策略和特征，对于优化问题的最优搜索具有易于实现的优点，并且不易陷入局部最优。其数学模型主要包括食物和捕食者的位置，整个优化过程包括夏季和冬季两个阶段。然而，与其它智能进化算法相似，SSA也存在收敛精度低、收敛速度慢等缺点。根据SSA，全局搜索能力的单冬搜索方法不够，使得算法容易陷入局部最优。此外，随机夏季搜索方法降低了收敛速度，收敛精度也降低[22]。为了提高算法的收敛精度和收敛速度，提出了一种改进的松鼠搜索算法(improved squirrel search algorithm，ISSA)，包括跳跃搜索法和渐进搜索法。当松鼠与捕食者相遇时，将“逃逸”和“死亡”操作引入跳跃搜索方法，将“突变”操作引入渐进搜索方法。在优化过程中，ISSA还通过线性回归选择策略选择合适的搜索方法。

2 系统模型与问题建模

2.1 IaaS云模型

(1)

2.2 多目标调度的目标函数

(2)

只考虑一个实例序列和一个定价方案，其中实例序列类型是计算密集型的。则任务调度 (ET,C) 的目标函数为

minf=(ET,cost)e

(3)

2.3 调度算法框架

在整个调度过程中，如果计算资源(包括CPU和存储系统)无法满足用户的任务需求，则可以通过任务管理器进行采集和处理任务数据。任务管理器具有接受和管理任务的功能，需要向调度器提供数据。任务管理器将通过成本、存储和时间限制进行工作分配，并且通过全局资源管理系统对分配的资源进行了标记。整个调度算法是在云计算平台中进行，兼容不同的物理服务器[23]。同时，可以访问本地服务器资源管理(local server resource management，LRM)，每个LRM都支持许多虚拟机。IaaS云环境下的任务调度算法结构如图1所示。

图1 IaaS云环境下的任务调度

云计算系统由多个数据中心组成，这些数据中心可以通过使用来自世界各地的互联网进行访问，每个数据中心都有许多计算、存储以及其它的资源。在每个服务器集群中，处理单元通过高带宽连接网络。在所提调度模型中，有效地将用户任务分配给各种可用的处理单元，以优化用户成本和时间。

3 改进型松鼠搜索算法

SSA是模拟飞行松鼠为躲避捕食者、寻找捕食的最佳地点以及以较小的代价进行捕食的滑翔行为。飞行松鼠的觅食策略灵活多变，这可以帮助飞行松鼠以最佳的方式应对食物资源。相比于其它搜索优化算法，SSA对搜索空间要求较少，且搜索效率较高，但在优化过程中也存在易陷入局部最优解，收敛速度较慢的问题。

3.1 松鼠搜索算法

松鼠是一种多样的树栖和夜间活动的啮齿动物，其类似降落伞的薄膜特别适合滑翔。其滑翔搜索能力可以帮助其躲避捕食者、寻找捕食的最佳地点和以较小的代价进行捕食。松鼠可以通过展示动态觅食行为来优化食物资源的利用[24]。

在温暖的秋天，由于橡树籽数量多，且能够满足松鼠在秋天的营养需要，当它们发现橡树籽后，会立即食用。在满足了每天的能量需求后，开始寻找冬天的最佳食物来源；而在冬季，森林中树叶的脱落增加了被捕食的风险，因此它们变得不活跃，但不冬眠。由于较低的温度会导致更高的营养需求，储存山核桃仁将有助于它们在极端天气条件下维持能量需求，从而提高存活概率。因此，根据营养需要，有选择地吃一些坚果，而将其它坚果储存起来，这使得两种坚果得到了充分利用。到冬季末，松鼠又活跃起来了开始觅食。如此循环往复，一直延续到松鼠生命的结束。在这个过程中，它们通过改变位置来探索不同的森林区域。SSA的寻优流程如图2所示。

图2 SSA的流程

为了简化数学模型，需要考虑以下假设[25]：

(1)森林里有n只会飞的松鼠，假设树上只有一只会飞的松鼠；

(2)每只松鼠都独立地寻找食物，并通过表现出动态的觅食行为来优化现有食物资源的利用；

(3)在森林中，只有3种树可供选择，如普通树、橡树(橡树籽的来源)和山核桃树(山核桃仁的来源)；

(4)假设森林区域由k橡树和一棵山核桃树组成。

在SSA中，对于d维优化问题，每个松鼠的位置可以用一个d维向量来表示

Xi=[xi1,xi2,…,xij,…,xid],i=1,2,…,nxij=xmin+δ(0,1)·(xmax-xmin),j=1,2,…,d

(4)

式中：xmax和xmin分别是飞行松鼠位置的上下限，δ(0,1) 是[0,1]范围内的均匀分布随机数。

根据用户定义的适应度函数，计算出每只飞鼠所在地的适应度值f(Xi)， 对应的值描述了可供搜索的食物源的质量，即最佳食物源(山核桃树)、正常食物源(橡树)和无食物源(普通树)。

3.2 引入空间变异与扩散机制

SSA算法在优化过程中不可避免地陷入局部最优解，收敛速度较慢。因此，受IWO的启发，将空间变异和扩散行为结合到SSA中，提出了一种ISSA。

第i只飞行的松鼠在一定范围内选择树Ni上降落，以确保在该范围内找到最佳食物来源，这个过程被称为空间变异。Ni的个数由IWO算法中的生长和再生思想决定

(5)

式中：dmax和dmin分别是空间变化的最大和最小数量。f(·) 是适应度函数，fmax、fmin分别是f(·) 的最大值和最小值。

然后，由正态分布的空间扩散产生Ni随机位置，平均值为第i只飞行松鼠的当前位置，标准差为σt， 其中σt的值根据迭代次数确定为

(6)

式中：σinitial为初始标准差，σfinal为最终标准差，t为当前迭代次数，tmax为最大迭代次数，n为非线性调和指数，常取3。

由上可知，空间扩散产生的新Ni位置可以表示为

(7)

式中：N(0,1) 是标准正态分布随机数。

对随机生成的Ni适应度函数值进行排序，选择适应度函数值最小的位置作为第i只飞行松鼠的当前新位置。式(7)描述了ISSA的基本特征，即早期强调全局搜索，后期强调局部搜索。

ISSA的伪代码如算法1所示。

算法1：ISSA的伪代码。

Begin

定义输入参数：εg是随机滑行距离；R是[0,1]范围内的随机数；Gc是滑动常数，常取1.9；Pd为捕食者存在概率。

(1) 生成n只飞行松鼠的随机位置：

Xi=[xi1,xi2,…,xid],i=1,2,…,n

(2) 评估每只飞行松鼠的位置是否适合。

(3) 通过空间变化和扩散进行重新定位：

(4) 根据它们的适应值， 按升序排列飞行松鼠的位置。

(5) 上报山核桃树、 橡树和普通树上的飞行松鼠。

(6) 随机选择一些在正常树上的飞行松鼠向山核桃树移动， 其余的向橡树移动。

(7) While 不满足停止条件

(8) Fort=1 ton1(在橡树上向山核桃树飞去的松鼠总数)

(9) ifR1≥Pd

(12) end

(13) end

(14) Fort=1 ton2(在正常树上向橡树移动的飞行松鼠的总数)

(15) ifR2≥Pd

(18) end

(19) end

(20) Fort=1 ton3(在普通树上向山核桃树移动的飞行松鼠总数)

(21) ifR3≥Pd

(24) end

(25) end

(27) 使用更新季节常数Smin的最小值:

(28) 通过空间变化和扩散进行重新定位：

(29) 松鼠在山核桃树上的位置是最终的最优解。

End

4 仿真及分析

4.1 仿真设置

CloudSim仿真工具包支持模拟云计算场景，支持大规模计算环境的建模和仿真，可为数据中心、物理主机、云服务代理和调度系统提供建模支持，因此，在IaaS云环境下使用CloudSim 3.0.3仿真工具包实现所提方法的调度方案。在实验中，一个IaaS云提供商拥有一个数据中心、两个主机和20个不同配置的虚拟机。数据中心和主机的配置见表1。虚拟机(virtual machine，VM)配置基于当前amazonec2产品，见表2，虚拟机的处理能力(即工作负载参数)见表3。

此外，ISSA算法的参数见表4。

4.2 性能指标

将完工时间、成本(财务成本)、超体积作为性能指标。ET是虚拟机最晚的完成时间，最小ET意味着用户在执行任务时要付出适度的成本，因为云服务中用户通常是按每小时的虚拟机使用量收费的。成本是从IaaS云提供商租赁VMs获得的。

表1 IssA云环境的参数设置

表2 虚拟机的配置与类型

表3 工作负载参数

表4 ISSA算法的参数设置

ET也称为总执行时间，是执行任务集合时使用的所有VMs最新完成时间，表示如下

(8)

成本是VMs成本与ET的乘积之和，四舍五入得最接近的整数表示为

(9)

超体积(hypervolume，HV)指标是通过计算得到非支配解决方案和参考点之间目标函数的空间体积，通过提供解集收敛性和多样性之间的关系获得的，是衡量多目标优化方法求解质量的一种综合指标，计算如下

(10)

为了获得HV值，每个方法在所有工作负载实例上独立运行30次，并将每个算法获得的30次运行的解合并成一个参考集，然后，在参考集上选取非支配解，形成帕累托前沿(pareto front，PF)，剔除由真PF支配的结果。将制造周期和成本标准化，使用参考点(1.1,1.1)计算HV值，该值越大，说明解决方案与参考点的相对空间体积越大，解的质量越高。

4.3 调度性能对比及分析

为了验证所提方法在成本和时间方面的性能，将其与文献[17]、文献[19]和文献[21]中的方法进行对比分析。其中文献[17]提出一种基于PSO算法的静态任务调度方法，求解过程中假定任务是非优先并且独立的，使用负载平衡技术提高了方法的性能。文献[19]采用遗传算法(genetic algorithm，GA)算法解决了完工时间、成本和能耗之间的帕累托最优权衡问题，在考虑任务优先级的同时还兼顾了云计算中的任务能耗，使任务的完工时间和成本达到最小化。文献[21]提出了SSA算法，模仿了飞松鼠的动态跳跃策略和特征，对于优化问题的最优搜索具有易于实现的优点。

为了确保不同方法之间的公平比较，工作负载实例的初始生态系统(总体)、生成数、停止条件和硬件资源都是相同的。并且NASA Ames iPSC/860是一些标准格式的工作负载，用于评估分布式系统的性能，而Uniform是合成工作负载。

4.3.1 不同并行任务种类下的执行时间和成本

对于所有测试的工作负载实例，将所提方法获得最佳结果所耗费的执行时间(以秒为单位)与文献[17]、文献[19]和文献[21]进行比较，结果如图3所示。

图3 执行时间的对比结果

从图3可以看出，对于所有测试的工作负载实例，所提方法的执行时间均少于其它对比方法。所提方法利用改进ISSA能够在较短的计算时间内获得更高质量的解决方案，优于文献[21]中传统的SSA。文献[17]和文献[19]分别使用GA和PSO算法，虽能够在一定程度上缩短执行时间，但随着任务数量的增加，算法处理效率不高，导致执行时间较长。由此可验证所提方法是求解多目标任务调度优化问题的有效方法。

此外，由5000个大小的工作负载实例的非支配解决方案如图4所示。

由图4可知，无论在NASA标准或是Uniform标准下，所提方法的性能明显优于其它对比方法。如图4(a)所示，在NASA标准下，所提方法的显著性能归功于其底层SSA算法的全局收敛性，并且引入空间变异与扩散机制，从而使其能够获得更好的收敛性，有效地处理大的搜索空间，因此，其对于成本的控制优于其它文献所提方法；其中，文献[17]所提方法由于缺乏全局搜索能力，因此其性能相对较差；而文献[21]和文献[19]所提方法则处于中等水平。在Uniform标准下，如图4(b)所示，文献[17]的GA和文献[19]的PSO算法在处理多目标调度问题，处理效率一般，且全局收敛性有待提高；文献[21]方法与所提方法性能较为接近，但所提方法凭借其变异与扩散机制带来的更好的收敛性，具有更好的性能，因此略优于文献[21]所提方法。

4.3.2 不同任务数量下的HV指标提升

对于不同任务数量，几种方法在HV指标方面的对比结果见表5。

从表5中可以看出，对于所有工作负载实例，相比文献[17]、文献[19]和文献[21]提出的方法，所提方法的HV值有显著提高。在不同的工作负载下，所提方法的HV值比文献[21]的SSA算法提高了16.32%～35.51%，而相比文献[19]的PSO算法性能提升了37.75%～63.89%，与文献[17]中的GA相比，提高了94.40%～120.24%。由此可见，所提方法具有较好的收敛性和解决方案的多样性，从而得到全局最优解决方案，完成多目标任务调度，实现成本和执行时间最小化。

图4 非支配解决方案的对比

表5 不同任务数量的HV指标对比结果

5 结束语

针对云环境中多目标任务调度优化所存在的收敛慢且易陷入局部最优的问题，提出一种改进SSA的云计算多目标任务调度方法。基于IaaS云模型，设计了多目标任务调度算法框架，并且将成本和执行时间的最小化作为目标函数，利用ISSA进行问题求解，其中引入空间变异与扩散机制改进传统的SSA。此外，在CloudSim模拟器工具包中，使用NASA标准工作负载和Uniform合成工作负载对所提方法进行实验验证，结果表明，所提方法的成本、执行时间和HV均少于其它对比方法，以NASA为例，当任务数量为5000时，其执行时间和HV分别是32.12 s和21.50，并且当执行时间达到2500 s时，所提方法快速收敛，且成本仅约为10元。

所提方法具有较大的服务质量提升空间，可以对其进行扩展，以处理对可靠性和安全性需求较高的大型负载实例。此外，实验仅考虑了NASA和Uniform两种工作实例，后续工作中将考虑更多实例类型，以提高所提方法的普适性。