混沌扰动w_BAPSO算法在任务调度中的应用

李信诚，徐寿伟，王重洋

（山东科技大学计算机科学与工程学院，山东青岛 266590）

0 引言

云计算是分布式计算的一种形式，给不同需求的云用户提供服务。通过互联网将用户提交的云任务发送给服务器，并在处理器的调度处理下将结果返回给云用户。随着云计算的发展，人们对于其安全性、能耗、资源管理、调度等问题进行了全方位研究。任务调度一直是云计算研究的热点话题，如何提高云环境下任务调度的效率，减小运行成本开销具有重要的研究价值。云计算管理各种虚拟化资源，使得调度成为一个关键组成部分，任务调度背后的基本思想是使任务最大限度地减少执行时间并且提高算法性能。为了在云环境中有效执行各类云任务，需要适当的任务调度策略。

随着用户数量的增加，云计算任务队列中的任务数量加剧，大幅度增加了云计算数据中心的能耗和成本；另外，在云任务提交给云服务器进行处理时，有效的任务调度算法决定云服务器的工作效率、负载均衡等。因此，为了使云服务器更好地处理用户需求、提高调度能力，在云环境中提供具有成本效益的执行算法，采取适当的任务调度策略是必要的。在云环境中如何对任务进行高效合理调度从实现系统全局最优化，是云计算研究的重点和难点。

1 相关工作

在云计算环境中，任务调度是一个NP难点问题。任务调度算法研究较多：文献［5］提出资源按需供应是云计算任务调度过程的主要目标之一，任务调度负责提高资源利用率和性能、缩短响应时间并保持整个系统平衡的方式，将任务分配给虚拟机执行。不同的任务调度顺序对调度性能影响很大，确定最适合任务的虚拟机（Virtual Machine，VM）类型集和最佳任务调度顺序并不容易。Domanal等改进PSO和CSO算法，提出一种新的任务调度和资源管理混合算法，提高了云资源利用率，降低了平均响应时间；Kumar等设计了一个具有选择最优资源决策能力的任务处理框架并提出一种粒子群优化算法，在用户定义的期限内处理虚拟机上的应用程序，改进了任务调度的时间、成本及吞吐量；Huang等提出一种任务调度器，将具有粒子群优化算法的几个离散变体用于云计算中的任务调度，实验结果证明了该方法的效率和有效性；蝙蝠算法很少应用于资源调度过程中，Pei等提出了混合蝙蝠和变量邻域搜索的算法来解决所研究的问题，并在其编码过程中实现了最优调度规则；Liu提出一种改进的蝙蝠算法，结合膜计算方式在CloudSim软件搭建仿真环境进行仿真实验，得到良好的收敛稳定性与精确性。

任务调度是一个NP-hard问题，需要使用启发式算法如粒子群优化（Particle Swarm Optimization，PSO）算法、蝙蝠优化算法（Bat Algorithm，BA）等来解决问题，为应用程序提供高效的调度算法非常重要，但以上方法都未在搜索精度和收敛速度等方面进行改进。本文提出混沌扰动的线性递减惯性权重值的混合BA-PSO算法（简称为

w

_BAPSO算法），结合带有混沌扰动的线性递减惯性权重值

w

改进了PSO算法容易陷入局部最优和BA算法收敛速度较慢的缺点，提高了任务调度的资源利用率，减少了成本和时间开销。

2 w w_BAPSO算法模型

为减少任务调度的时间和成本，提高调度算法的收敛速度和搜索精度，本文提出一种基于混沌扰动的线性递减惯性权重参数。结合蝙蝠算法和粒子群算法，克服了粒子群算法搜索精度低和蝙蝠算法收敛速度慢的缺点，有效提高了算法的收敛速度和搜索精度。

2.1 任务调度模型

云计算中分布有大量的资源和数据，具有资源差异性、异构性、动态性等特点，进行资源调度的目标是减少运行时间和成本，提高资源利用率。本文使用Fard等提出的云计算资源架构，底部到顶部为资源层、平台层和应用程序层，资源层中分布有虚拟资源和物理资源。任务调度模型如图1所示。

Fig.1 Schematic diagram of task scheduling model图1 任务调度模型

应用程序层是连接用户和云计算平台的载体，通过互联网将用户与云服务器进行互联。云用户在应用程序层产生服务需求，提交云任务请求后生成云任务列表。在云任务列表中，将任务分为较小的子任务提交给平台层。平台层提供开发、测试、部署软件以及管理功能，在平台层中主要分布有云服务调度服务器、资源管理模块以及任务调度模块。当云任务列表到达云服务调度服务器后，通过资源管理模块分配相应的资源用以执行，通过任务调度模块执行任务调度算法。在云计算服务器的处理下，经过合理的调度算法和调度策略将云任务分配到资源层。资源层提供基础设施，是平台层和应用层进行任务调度及资源处理的基础。资源层包括物理资源和虚拟资源。物理资源就是分布在不同空间的物理机、服务器等硬件设施；虚拟资源由虚拟化技术形成的资源池组成。在资源层中，分布有大量的物理机和虚拟机，云任务被分配到对应的虚拟机上执行，消耗物理资源并将结果返回给平台层中的云服务器，最终将任务执行结果反馈给应用程序层，用户得到任务执行结果。

2.2 w_BAPSO算法

在粒子群迭代过程中，使用式（1）、式（2）对速度和位置进行更新：

其中，

w

为惯性权重，表示粒子继承当前速度的程度；

c

、

c

是学习因子，

c

表示“自我认知”，代表粒子自我学习的能力，

c

表示“社会认知”，代表粒子向全局最优学习的能力，

c

、

c

∈[0，2]，通常情况下

c

=

c

=2；

r

和

r

是分布在［0，1］之间的随机数。在

w

_BAPSO算法的迭代过程中，加入带有logistics混沌扰动的线性递减的惯性权重参数。在粒子群算法迭代初期，较大的惯性权重有助于全局搜索，避免陷入局部最优。在粒子群算法迭代后期，较小的惯性权重有助于局部搜索，在局部中搜索出全局最优解。为了更好地平衡算法的全局搜索以及局部搜索能力，Shi提出了线性递减惯性权重策略：

其中，

w

是第t次迭代中惯性权重的值，

w

是惯性权重的最大值，

w

是惯性权重的最小值，

iter

是当前的迭代次数，

T

是迭代总次数，惯性权重随迭代次数线性递减。在非线性递减的惯性权重基础上，添加一个Logistics混沌扰动项

At

∈[0，0.1]，其公式如下：

其中

μ

为控制参量，当

μ

=4，0≤

At

≤1时，Logistics处于完全混沌状态，可以利用其混沌特性进行迭代搜索。

增添扰动项非线性递减的惯性权重具有随机性，有效改进了粒子群的搜索能力和搜索范围。通过引入Logistics混沌扰动项产生混沌变量，在每一次迭代过程中对当前的速度公式进行扰动，提高了算法跳出局部最优解的处理能力。

蝙蝠算法是一种新型的群体智能优化算法，每个蝙蝠个体有相应的适应度，蝙蝠群通过调整频率、脉冲发射率和响度，在解空间中搜素最优蝙蝠个体。蝙蝠脉冲的响度

A

(

i

)和脉冲速率

R

(

i

)随着迭代过程不断更新，脉冲响度从最大值不断减小，同时脉冲速率从初始值开始逐渐增大。

在此基础上，结合BA算法对PSO算法进行改进。

然后判断脉冲速率

R

(

i

)和随机数

Rand

(0，1)的大小。（1）若

Rand

(0，1)＞

R

，则从当前解附近形成一个局部解，使用式（9）生成当前位置，产生一个局部新解。此过程可以克服粒子群算法陷入局部最优的缺陷，产生随机解便于粒子扩大搜索范围，更好地搜索全局最优解。

（2）若

Rand

(0，1)＜

R

且此时粒子的适应度值小于最佳位置的适应度值，则保留当前位置，使用式（10）更新粒子的位置，并使用式（6）、式（7）增大

R

，缩小

A

，重新排序，找到最优解

gbest。

（3）否则使用式（11）更新其位置：

本文提出的

w

_BAPSO算法流程如图2所示。

Fig.2 Flow of w_BAPSO algorithm图2 w_BAPSO算法流程

3 应用实验

采用Cloudsim仿真平台，将

w

_BAPSO算法在云计算任务调度中进行仿真实验验证，通过设置不同规模任务数量对实验结果进行比较。实验结果表明本文提出的

w

_BAPSO算法在云计算任务调度中有较好性能，提高了收敛速度，减少了任务调度过程中的时间和成本。

3.1 w_BAPSO算法的适应度函数

任务

i

在虚拟机

j

上的执行时间用

ETC

(

i

，

j

)表示，

ETC

(

i

，

j

)的计算公式如式（12）所示，其中

task_length

表示任务

i

的长度，

vm_cpu

表示虚拟机

j

的运行速度。

任务调度过程的总执行时间计算如式（13）、式（14）所示：

其中，

x

表示任务

task

与虚拟机

vm

的分配关系。当

x

=1时，表示任务

task

在虚拟机

vm

上执行，否则

x

=0。

Time

（

j

）表示虚拟机

j

的运行时间。最大完成时间

Makespan

计算如下：

使用Cost(

i

，

j

)表示云任务

i

在虚拟机

j

上运行的成本，Cost(

i

，

j

)的计算公式如下：

其中，

P

、

P

、

P

分别表示虚拟机内存外存、带宽的运行成本。使用

total Cost

表示所有虚拟机的运行总成本：

本文的适应度函数使用多目标优化方案，使用

total-Time、Makespan、total Cost

设计目标函数，并对目标函数按照式（18）-（20）进行归一化处理：

3.2 实验环境及算法参数设置

本文使用计算机仿真通用平台CloudSim进行实验验证。CloudSim是澳大利亚墨尔本大学和Gridbus项目组共同推出的云计算仿真软件，本实验采用CloudSim 3.0版本。计算机采用Windows10操作系统，8GB内存，Core i7处理器。将本文提出的算法分别与标准粒子群优化（PSO）算法、改进后的粒子群优化算法（AIW-PSO）、标准蝙蝠算法（BA）进行对比实验。为进一步比较本文提出算法的性能，设置云任务数量分别为50、200，对比指标为算法的适应度值、收敛情况、最大完成时间Makespan、任务平均完成时间及任务平均成本。

CloudSim平台中虚拟机、主机、任务的参数设置如表1所示。

Table1 Parameter settings表1 参数设置

3.3 实验结果对比

设置两组数据进行对比实验，当云任务数量为50和200时，测试

w

_BAPSO算法在云计算资源调度中的性能，分别比较两种任务规模下4种算法的收敛速度、执行云任务的平均成本、平均时间以及虚拟机的最大完成时间。任务调度在云计算中的收敛情况如图3所示，不同规模任务级条件下算法的收敛情况有所不同。由图3可知，当任务规模较小时，本文提出的

w

_BAPSO算法在80次迭代时收敛，产生最小的适应度值，约为0.31，而其他几个算法收敛程度较为缓慢，且具有陷入局部最优的过程，一直处于不断迭代中，其中PSO表现出的性能最差，收敛精度较低。当任务规模较大时，

w

_BAPSO和AIW_PSO算法都表现出较好的性能，但

w

_BAPSO算法收敛速度更快，寻优能力更强；而PSO和BA算法在迭代后期仍未找到全局最优解，收敛效果较差。因此，本文提出的

w

_BAPSO算法应用于云计算任务调度过程中，具有较快的收敛速度和搜索精度。

Fig.3 Convergence of the algorithm under different number of tasks图3 不同任务数量下算法的收敛情况

4种算法在不同任务规模下的最大完成时间如图4所示。当任务规模较大时，最大完成时间

Makespan

都有不同程度的提高。从图中可以看出，不论任务规模大小，

w

_BAPSO算法的

Makespan

都处于较小值，因此可以得出

w

_BAPSO算法在执行任务调度过程中最大完成时间较小，有效提高了虚拟机的利用率和任务调度性能。

Fig.4 Makespan of the algorithm under different number of tasks图4 不同任务数量下算法的最大完成时间

4种算法在不同任务规模下的平均完成时间如图5所示。从图中可以看出，当任务规模较小时，4种算法的任务平均完成时间较为一致，但

w

_BAPSO算法的任务平均完成时间较小，为226ms；当任务规模较大时，任务的平均完成时间差异比较明显，但

w

_BAPSO算法依旧有着最少的时间，为1 026ms。也就是说，在不同规模的任务调度过程中，

w

_BAPSO算法的调度时间最小，耗时最短，能以较快的速度收敛到全局最优值，产生最佳调度方案。不同任务规模下几种算法进行任务调度的成本如图6所示。当任务规模为50时，4种算法都维持在较小成本；当任务规模增大时，PSO算法成本较大，

w

_BAPSO算法成本相对较小。因此，本文提出的

w

_BAPSO算法在解决任务调度问题中具有较小的成本。

Fig.5 Averagecompletion timeof thealgorithm under different number of tasks图5 不同任务数量下算法的平均完成时间

Fig.6 Averagecost of thealgorithm under different number of tasks图6 不同任务数量下算法的平均花费

4 结语

为克服粒子群算法和蝙蝠算法缺点，本文提出了混沌扰动

w

_BAPSO算法，将其用于云计算任务调度过程，有效避免了粒子群算法陷入局部最优和蝙蝠算法收敛速度慢的缺陷。实验结果证明，

w

_BAPSO算法具有收敛速度快且搜索精度高的优点，调度成本小，最大完成时间短。后续研究工作中要进一步改善算法的收敛速度和寻优精度，更好地适应大规模云计算任务调度。