基于Levy飞行的人工蜂群粒子群算法的云计算任务调度方法

摘要

本发明公开了一种基于服务收益与功耗的云计算任务调度模型和基于Levy飞行的人工蜂群粒子群算法的云计算任务调度方法。针对绿色云计算的思路，提出了一种引入处理机功耗和任务调度收益的多QoS调度模型。并提出了一种基于Levy飞行的人工蜂群粒子群算法用来解决多QoS云计算任务调度的。在本发明中，在粒子群算法中引入人工蜂群局部搜索策略提高算法的局部搜索精度，并通过对全局最优值进行Levy操作来避免陷入局部最优，从而提高收敛精度。本发明所述的方法，能够有效的提高云计算任务调度收益，并能够降低用户等待时间和处理机功耗。

说明书

技术领域

本发明属于云计算技术领域，具体涉及基于Levy飞行的人工蜂群粒子群算法的云计算任 务调度方法。本算法是一种基于群体智能优化算法的任务调度方法，适用于云计算环境下QoS 任务调度。

背景技术

云计算平台为了保证服务器的可靠性通常是通过虚拟化技术将多台物理主机虚拟成一定 数量的虚拟机来处理数据，单台虚拟机处理能力娇弱，但多台虚拟机同时提供计算就可以输 出强大的计算能力。在实际的应用中，通常都会有大量的计算任务交给云计算平台进行处理， 如何高效的调度任务到不同的虚拟机处理成为影响云计算平台性能的重要影响因素。在云计 算环境下，处理机之间的性能差异和用户任务的多变，使得云计算任务调度成为一个复杂的 问题。

在商业云计算服务中，不仅要考虑用户多变的需求还要尽可能的降低服务成本并提高服 务收益。现有的调度策略通常关注的是如何对计算资源进行有效的分配和用户对任务的计算 要求，例如经典的调度算法Min-Min,其在调度时把计算量最小的任务分配给性能最好的处理 机，这样能够显著的提高系统的吞吐率但也存在负载不均衡的问题。

近几年随着商业云计算服务的广泛应用，研究人员开始关注云计算调度中的经济问题。 Rajkumar等人提出了一种基于截止时间底线和调度预算约束的调度方法，这种方法在满足两 个约束条件下，将任务分配到最早能够完成的任务的处理机上，这种调度方法能够显著提高 任务吞吐量但容易发生负载不均的情况。Kavitha等人分析了从调度完成时间、用户满意度等 方面的多种QoS目标约束的调度方法，提出针对不同应用环境下应用不同QoS调度方法。

目前在云计算任务调度方面的研究大多数从用户的角度提出的调度方法，这些方法中尽 量满足用户的需求，很少考虑到服务成本等问题。由于云数据中心通常具有很高的能耗，随 着近几年环保理念的深入，绿色数据中心成为一个趋势，尽量降低能耗成为了一个研究热点。 传统的简单调度算法很难在多种QoS目标约束调度要求下取得良好的调度效果。

发明内容

针对以上问题，本发明提出了一种基于服务收益和低功耗的云计算任务调度模型；并针 对该任务调度模型，提出了一种基于Levy飞行的人工蜂群粒子群算法的云计算任务调度方 法。此方法相对其传统的调度方法，具有更优的调度效果。

本发明实现的具体步骤如下：

1、基于服务收益和低功耗的云计算调度模型，包括如下描述：

(1)相关符号约定

为了更好的描述和分析问题，做如下假设：一个任务只能分配到一个节点上执行、任务 之间不能抢占、处理机能够处理任意类型的任务。

集合VM＝{vm₁,vm₂,…,vm_n}表示n台处理机集合，集合T＝{t₁,t₂,…,t_m}表示 m个任务集合。Budget_i表示用户对完成任务t_i的预算，即云服务提供方按时完成任务t_i获得的收入。Deadline_i是任务t_i调度完成的最晚时间，如果云计算服务商能够在Deadline_i时 间内对任务t_i完成计算，那么云计算机服务商不用支付赔偿，否则需要按照违约时间支付相 应数额的赔偿。

Instru_count_i表示任务t_i的计算规模即单位指令数量，Time_fini_i表示任务t_i预计完成时 间，Instru_cost_j表示虚拟机vm_j处理任务的单位指令执行成本。

Delay_costi是任务t_i的延迟单价，即云计算服务商在处理任务t_i时，如果在Deadline_i时 间之前没有完成任务，则每延迟单位时间就要向提交任务t_i的用户赔偿Delay_cost_i。

Worstline_i是任务t_i能够忍受的最大时间，即如果任务t_i在Worstline_i时还没有调度完成， 则云计算服务商向用户支付的赔偿达到上限，将不再继续支付赔偿。由于Time_fini_i是预计 任务完成时间，而Worstline_i是赔偿上限时间，因此Time_fini_i＜Worstline_i，否则任务无法调 度完成。

Energy_cost_j是处理机VM_j单位时间功耗。

(2)调度目标

用户在将任务提交给云计算服务商之前会更具自己的预算和紧急情况制定任务调度的 QoS目标约束，云计算服务商接受到用户所提交QoS约束的任务后会进行调度收益的估算， 用以判断是否接受用户提交的调度请求。

设任务t_i分配给处理机VM_j进行处理，则处理机VM_j完成任务t_i调度的计算成本如下：

$\mathrm{Comp}\_{\cos t}_j^i=\mathrm{Instru}\_{\cos t}_j\times \mathrm{Instru}\_{\mathrm{count}}_i$

其中Instru_cost_j是处理单位指令的成本，Instru_count_i是任务的单位指令数量。

处理机VM_j完成任务t_i所获得的收益为：

${\mathrm{Revenue}}_j^i={\mathrm{Budget}}_i-{\mathrm{Fine}}_j^i-\mathrm{Comp}\_{\cos t}_j^i$

其中Budget_i为用户为完成任务t_i的预算资金，是处理机VM_j因未按时完成任务t_i所 要赔偿给用户的金额。的计算公式如下：

${\mathrm{Fine}}_j^i=\left(\begin{array}{cc}0& \mathrm{Time}\_{\mathrm{fini}}_i<{\mathrm{Deadline}}_i\\ \mathrm{Delay}\_{\cos t}_i\times (\mathrm{Time}\_{\mathrm{fini}}_i-{\mathrm{Deadline}}_i)& {\mathrm{Worstline}}_i>\mathrm{Time}\_{\mathrm{fini}}_i\ge {\mathrm{Deadline}}_i\\ {\mathrm{Budget}}_i& \mathrm{Time}\_{\mathrm{fini}}_i\ge {\mathrm{Worstline}}_i\end{array}\right)$

任务t_i被分配到处理机VM_j上，执行的功耗为：

$\mathrm{Energy}\_{\mathrm{vm}}_j^i=\mathrm{Energy}\_{\cos t}_j\times \left(\frac{\mathrm{Instru}\_{\mathrm{count}}_i}{\mathrm{Power}\_{\mathrm{vm}}_j}\right)$

其中Power_vm_j表示处理机j的处理能力。

为了更好的表示目标函数，这里假设分配矩阵为X其中元素x_i,j＝1表示任务i被分配到处 理机j，否则x_i,j＝0。云服务商完成任务集合T＝{t₁,t₂,…,t_m}所获得的收益为：

$\mathrm{Revenue}=\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}({\mathrm{Revenue}}_j^i\times x_{i,j})$

云服务商调度任务T＝{t₁,t₂,…,t_m}所消耗的功耗为：

$\mathrm{Energy}=\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}(\mathrm{Energy}\_{\mathrm{vm}}_j^i\times x_{i,j})$

为了获得最大利益的同时尽量节省能源，实现绿色云计算，这里在目标调度函数上加入 了功耗信息，目标调度函数如下：

Objective＝max(Revenue-α·energy)

其中α是比率参数，用来调节功耗对收益的影响。

2、基于Levy飞行的人工蜂群粒子群算法的云计算任务调度方法，包括如下步骤：

(1)对处理机进行编号，载入任务，设置任务矩阵、处理机性能矩阵、处理机功耗矩阵和 处理机成本矩阵，任务矩阵中存储各个任务的计算量，处理机矩阵存储各个处理机的处理能 力，处理机功耗矩阵存储处理机的功率，处理机成本矩阵中存储处理机单位处理成本；其中任 务计算量和处理机处理能力均用MIPS(Million Instructions Per Second,每秒处理的百万级的 机器语言指令)表示。

(2)初始化种群：设粒子P＝{x₁,x₂,…,x_n},其n是待调度的任务数量,x₁,x₂,…,x_n代表分配 的处理机机编号。以此方式初始化粒子群中的各个粒子。每个粒子代表一种分配方案，对各 个粒子代表的分配方案带入发明内容1中的目标调度函数中计算收益，找出收益最大的粒子 为全局最优值，各个粒子自身为粒子的局部最优值。

(3)对每个粒子进行速度和位置利用如下公式进行更新

v_i(t+1)＝v_i(t)+c₁·r₁(p_i(t)-x_i(t))+c₂·r₂·(p_g(t)-x_i(t))

x_i(t+1)＝x_i(t)+v_i(t+1)

其中t表示第t次迭代，同理t+1表示t的下一次迭代，c₁和c₂是粒子的加速度常数，通常 取值范围是[0,2]，r₁和r₂是[0,1]之间的随机数，p_i表示第i个粒子的局部最优位置，p_g表示 粒子群的全局最优位置。公式(2.6)是速度限制，防止粒子在运动过程中飞出解空间。k和j是 随机数，且k∈[1,N],j∈[1,D]，k≠j；是[-1,1]之间的随机数。

(4)对步骤(3)进行迭代，在迭代过程中，如果全局最优值位置连续10次没有更新，则采 用如下公式在全局最优值附近进行搜索：

$x^{t+1}=x^t+\alpha \oplus \mathrm{Levy}\left(\beta \right)$

其中α是单位步长，其值与求解问题范围有关，在这里我们把α赋值为粒子维度的随机 数：

$x^{t+1}=x^t+\mathrm{random}\left(\mathrm{size}\left(D\right)\right)\oplus \mathrm{Levy}\left(\beta \right)$

公式中表示矩阵的内积运算。

(5)迭代次数达到最大迭代次数时，停止迭代，全局最优值p_g就是最优任务调度方案，按 照此方案将任务分配给不同的处理机进行处理。

附图说明

图1本发明的流程图；

图2本发明方法和其它方法任务调度所需时间对比；

图3本发明方法和其它方法任务调度单位时间收益对比；

图4本发明方法和其它方法任务调度所需功耗对比；

具体实施方式

1、基于服务收益和低功耗的云计算调度模型，包括如下描述：

(1)相关符号约定

为了更好的描述和分析问题，做如下假设：一个任务只能分配到一个节点上执行、任务 之间不能抢占、处理机能够处理任意类型的任务。

集合VM＝{vm₁,vm₂,…,vm_n}表示n台处理机集合，集合T＝{t₁,t₂,…,t_m}表示 m个任务集合。Budget_i表示用户对完成任务t_i的预算，即云服务提供方按时完成任务t_i获得的收入。Deadline_i是任务t_i调度完成的最晚时间，如果云计算服务商能够在Deadline_i时 间内对任务t_i完成计算，那么云计算机服务商不用支付赔偿，否则需要按照违约时间支付相 应数额的赔偿。

Instru_count_i表示任务t_i的计算规模即单位指令数量，Time_fini_i表示任务t_i预计完成时 间，Instru_cost_j表示虚拟机vm_j处理任务的单位指令执行成本。

Delay_costi是任务t_i的延迟单价，即云计算服务商在处理任务t_i时，如果在Deadline_i时 间之前没有完成任务，则每延迟单位时间就要向提交任务t_i的用户赔偿Delay_cost_i。

Worstline_i是任务t_i能够忍受的最大时间，即如果任务t_i在Worstline_i时还没有调度完成， 则云计算服务商向用户支付的赔偿达到上限，将不再继续支付赔偿。由于Time_fini_i是预计 任务完成时间，而Worstline_i是赔偿上限时间，因此Time_fini_i＜Worstline_i，否则任务无法调 度完成。

Energy_cost_j是处理机VM_j单位时间功耗。

(2)调度目标

用户在将任务提交给云计算服务商之前会更具自己的预算和紧急情况制定任务调度的 QoS目标约束，云计算服务商接受到用户所提交QoS约束的任务后会进行调度收益的估算， 用以判断是否接受用户提交的调度请求。

设任务t_i分配给处理机VM_j进行处理，则处理机VM_j完成任务t_i调度的计算成本如下：

$\mathrm{Comp}\_{\cos t}_j^i=\mathrm{Instru}\_{\cos t}_j\times \mathrm{Instru}\_{\mathrm{count}}_i$

其中Instru_cost_j是处理单位指令的成本，Instru_count_i是任务的单位指令数量。

处理机VM_j完成任务t_i所获得的收益为：

${\mathrm{Revenue}}_j^i={\mathrm{Budget}}_i-{\mathrm{Fine}}_j^i-\mathrm{Comp}\_{\cos t}_j^i$

其中Budget_i为用户为完成任务t_i的预算资金，是处理机VM_j因未按时完成任务t_i所 要赔偿给用户的金额。的计算公式如下：

${\mathrm{Fine}}_j^i=\left(\begin{array}{cc}0& \mathrm{Time}\_{\mathrm{fini}}_i<{\mathrm{Deadline}}_i\\ \mathrm{Delay}\_{\cos t}_i\times (\mathrm{Time}\_{\mathrm{fini}}_i-{\mathrm{Deadline}}_i)& {\mathrm{Worstline}}_i>\mathrm{Time}\_{\mathrm{fini}}_i\ge {\mathrm{Deadline}}_i\\ {\mathrm{Budget}}_i& \mathrm{Time}\_{\mathrm{fini}}_i\ge {\mathrm{Worstline}}_i\end{array}\right)$

任务t_i被分配到处理机VM_j上，执行的功耗为：

$\mathrm{Energy}\_{\mathrm{vm}}_j^i=\mathrm{Energy}\_{\cos t}_j\times \left(\frac{\mathrm{Instru}\_{\mathrm{count}}_i}{\mathrm{Power}\_{\mathrm{vm}}_j}\right)$

其中Power_vm_j表示处理机j的处理能力。

为了更好的表示目标函数，这里假设分配矩阵为X其中元素x_i,j＝1表示任务i被分配到处 理机j，否则x_i,j＝0。云服务商完成任务集合T＝{t₁,t₂,…,t_m}所获得的收益为：

$\mathrm{Revenue}=\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}({\mathrm{Revenue}}_j^i\times x_{i,j})$

云服务商调度任务T＝{t₁,t₂,…,t_m}所消耗的功耗为：

$\mathrm{Energy}=\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}(\mathrm{Energy}\_{\mathrm{vm}}_j^i\times x_{i,j})$

为了获得最大利益的同时尽量节省能源，实现绿色云计算，这里在目标调度函数上加入 了功耗信息，目标调度函数如下：

Objective＝max(Revenue-α·energy)

其中α是比率参数，用来调节功耗对收益的影响。

2、基于Levy飞行的人工蜂群粒子群算法的云计算任务调度方法，包括如下步骤：

(1)对处理机进行编号，载入任务，设置任务矩阵、处理机性能矩阵、处理机功耗矩阵和 处理机成本矩阵，任务矩阵中存储各个任务的计算量，处理机矩阵存储各个处理机的处理能 力，处理机功耗矩阵存储处理机的功率，处理机成本矩阵中存储处理机单位处理成本；其中任 务计算量和处理机处理能力均用MIPS(Million Instructions Per Second,每秒处理的百万级的 机器语言指令)表示。

(2)初始化种群：设粒子P＝{x₁,x₂,…,x_n},其n是待调度的任务数量,x₁,x₂,…,x_n代表分配 的处理机机编号。以此方式初始化粒子群中的各个粒子。每个粒子代表一种分配方案，对各 个粒子代表的分配方案带入发明内容1中的目标调度函数中计算收益，找出收益最大的粒子 为全局最优值，各个粒子自身为粒子的局部最优值。

(3)对每个粒子进行速度和位置利用如下公式进行更新

v_i(t+1)＝v_i(t)+c₁·r₁(p_i(t)-x_i(t))+c₂·r₂·(p_g(t)-x_i(t))

x_i(t+1)＝x_i(t)+v_i(t+1)

其中t表示第t次迭代，同理t+1表示t的下一次迭代，c₁和c₂是粒子的加速度常数，通常 取值范围是[0,2]，r₁和r₂是[0,1]之间的随机数，p_i表示第i个粒子的局部最优位置，p_g表示 粒子群的全局最优位置。公式(2.6)是速度限制，防止粒子在运动过程中飞出解空间。k和j是 随机数，且k∈[1,N],j∈[1,D]，k≠j；是[-1,1]之间的随机数。

(4)对步骤(3)进行迭代，在迭代过程中，如果全局最优值位置连续10次没有更新，则采 用如下公式在全局最优值附近进行搜索：

$x^{t+1}=x^t+\alpha \oplus \mathrm{Levy}\left(\beta \right)$

其中α是单位步长，其值与求解问题范围有关，在这里我们把α赋值为粒子维度的随机 数：

$x^{t+1}=x^t+\mathrm{random}\left(\mathrm{size}\left(D\right)\right)\oplus \mathrm{Levy}\left(\beta \right)$

公式中表示矩阵的内积运算。

因此一个更有意义的随机步长s的公式为：

$s=\mathrm{random}\left(\mathrm{size}\left(D\right)\right)\oplus \mathrm{Levy}\left(\beta \right)~0.01\frac{\mu }{{\left|v\right|}^{1/\beta }}(x_j^i-{\mathrm{gbest}}^t)$

其中size(D)是问题维度，μ和v可用从如下分布中获得

$\mu ~N(0,{\sigma }_{\mu }^2),v~N(0,{\sigma }_v^2)$

其中

${\sigma }_u={\left\{\frac{\Gamma (1+\beta )\sin \left(\frac{\mathrm{\pi \beta }}{2}\right)}{\Gamma \left[\left(\frac{1+\beta }{2}\right)\right]{\beta 2}^{(\beta -1)/2}}\right\}}^{1/\beta },{\sigma }_v=1$

上面公式中，β取值是[0,2]之间的随机数。

(5)迭代次数达到最大迭代次数时，停止迭代，全局最优值p_g就是最优任务调度方案， 按照此方案将任务分配给不同的处理机进行处理。

本发明效果可以通过以下仿真实验进一步说明。

(1)仿真环境:

本发明的仿真环境是在CPU主频3.8GHz的AMD A10-5800K、8G内存、Windows 7专 业版的环境下，使用CloudSim仿真器进行仿真实验。实验中算法的种群规模设置为50，最 大迭代次数设置为200，算法运行50次求取平均值。

(2)实验内容:

为了本发明算法的性能，在实验中通过本发明算法与遗传算法(GA)、标准粒子群算法 (PSO)、引入混合蛙跳搜索策略的人工蜂群粒子群算法(ABCSFL-PSO)三种算法进行对比实验。 为了更加准确的说明本文发明的算法在基于服务收益和低功耗的云计算模型上的调度能力， 通过调度完成所有任务的耗时、单位时间收益和处理机功耗这三个方面进行对比实验。

(3)实验结果分析:

图2是4种算法调度完成所有数量的任务所需时间的柱形图，从图中可以看出，本发明 的LFABC-PSO算法耗时在不同任务数量的情况下均最少。图3是4种算法在不同任务数量 情况下的单位时间收益，本发明的LFABC-PSO算法收益最高。图4展示了4种算法在调度 完所有任务的功耗，从图中可以看出本发明的LFABC-PSO算法调度完所有任务的功耗最低。

以上实验充分证明了，本发明的LFABC-PSO算法在云计算任务调度问题中具有比其他 算法更优的调度能力。