基于改进人工蜂群算法的云任务调度

吴 傲， 陈宏伟

(湖北工业大学计算机学院， 湖北 武汉 430068)

云计算技术作为一种全新的计算模式，对于用户来讲具有成本低廉，使用即时，操作简单，计算高效等特点，因而受到业界的大量关注，目前已经成为计算机领域热门的研究方向。随着越来越大的用户需求，云环境下的资源分配问题成为一个急需考虑的问题，用户日益增长的资源需求和云服务资源的高效分配之间的矛盾是目前云计算资源调度下最关键的问题。在云计算资源调度系统中，用户可以采取租用的形式按需获取供应商提供的计算力、信息服务以及存储空间[1]，由于在实际使用中，云计算资源调度系统面对的用户群体十分巨大，而且任务类型极其复杂，在资源的调度过程中需要一个合理高效且低成本的分配方案。对于云计算任务调度。文献[2]提出了一种基于改进粒子群的云计算任务调度策略，从负载均衡的角度和任务完成的总时间的角度这两个方面来对资源调度任务进行优化。

人工蜂群算法(artificial bee colony argorithm,ABC)于2005年由土耳其教授Karaboga基于蜜蜂种群采蜜机制而提出的一种蜂群算法[3-4]。由于BCO算法参数多，而ABC算法参数较少，易于实现，因此有关ABC算法的研究居多。

博弈论是数学基础理论的一个分支方向，其包含博弈者本身、博弈者策略集合、信息、收益和纳什均衡等五大因素。目前的研究已有将博弈论用于云环境下的资源调度问题中。Osorio等[5]简要描述了当前云资源分配策略，并且首次提出有关云资源分配框架。Hassan等[6]提出了用博弈论的方法来解决云环境下有关资源分配的管理问题，他们得出了合作博弈比非合作博弈的博弈模型更适合云环境的结论。

1 相关技术介绍

1.1 人工蜂群算法模型

在ABC算法中，蜂群包含3个小种群，分别为雇佣蜂(也称为引领蜂)，跟随蜂和侦察蜂[7]。算法原理是将蜜蜂种群寻找食物源的过程数学化为寻优求解的过程。原ABC算法步骤如下：

1)：由式子(1)初始化种群，含有N个具有D维变量的解

Xi,j=Xmin,j+Rand(0,1)·(Xmax,j-Xmin,j)

(1)

式(1)中i=1,2，…，N，j=1,2,…,D。Xmax,j为搜索解空间的上限，Xmin,j为搜索解空间的下限。Rand(0,1)为区间[0,1]内的随机数。每个解Xi(i=1,2,…,N)用一个D维向量来表示，D是待优化目标问题参数个数。

2)引领蜂根据式(2)对食物源进行邻域搜索，并产生候选解，计算候选解的适应度值。基于贪婪选择原理挑选较好的食物源(解)，保留适应度值最高的食物源。

Vi,j=Xi,j+ri,j(Xi,j-Xk,j)

(2)

其中，j=1,2,….,D，k=1,2,…,N，Xk,j，Xi,j为解空间内的随机解，且k≠j，ri,j为[-1,1]区间内的一个随机数，若Vi,j函数值优于Xi,j，则前者取代后者。

3)跟随蜂根据公式(3)计算食物源的适应度值，根据公式(4)计算得出食物源位置被选择的概率值。基于上述最优食物源,根据式(2)展开二次邻域搜索。再计算得出新解的适应度值，根据贪婪选择策略保留最优解。

(3)

(4)

式(4)中：Pi表示为第i个食物源由跟随蜂选取的概率fiti为其对应的适应度值。fi为该解的目标函值，等同于待优化问题的函数值。

4)若某个解Xi在有限次循环(定义为Limit_time)之后并没有得到提高，引领蜂必须放弃该较差的食物源，且引领蜂更改职责称为侦察蜂，按照式(5)产生随机新解。若多次循环后食物源没有被放弃，则该食物源为最佳蜜源(即该解为问题最优解)。

Xi,j=Xmin,j+Rand(0,1)·(Xmax,j-Xmin,j)

(5)

其中，Xmin,j为目前得到的第j维最小值；Xmax,j为得到的第j维最大值。Rand(0,1)为[0,1]区间内的随机数。通过以上种群内互相协作结合的方式，蜜源会不断地优于上一代，在经过多次迭代后，达到算法所预设的次数或者达到精度范围内的所需解。以此达到求最优解的过程。

1.2 基于博弈论的云计算资源调度模型

在资源调度系统中，首要保证系统资源高效利用和用户最小等待，此时就需要采用资源调度算法将任务合理的分配给不同的服务器节点，提升处理效率和用户满意度[11]。用户任务用Ti表示，则m个任务可表示为T={T1,T2,…,Tm}。系统中的服务器节点为VMi，则n个服务器节点可表示为V={VM1,VM2,…,VMn}，对于任意的节点VMj。

采用如下定义描述该模型，调度任务定义如下：

Ti={Lenth,Filesize,Cost}

式中:Lenth为任务长度；Filesize为任务文件大小；Cost为任务花费。

节点模型如下：

VMj={CPU，Memory，Bandwidth，Cost}

虚拟节点考虑因素分别为CPU、内存大小、网络带宽以及调度收益成本。云计算资源调度拓扑结构见图1。

图 1 云计算资源调度结构图

结合非合作博弈理论，构建基于非合作博弈的调度模型，博弈模型可以用一个五元组表示，模型定义如下

G={Time,ω,C,(Sp(t)),(P(t)p)}

下面给出非合作博弈模型和相关的表达式[8]。

1)资源调度时间耗费 在资源调度系统中，Ti表示第i个任务，VMj表示第j个节点，因此任务Ti在节点上VMj会对应一个时间耗费，用Time(Ti→VMj)来表示。那么对于一个完整的执行序列K必然对应一个总时间耗费Time，如

(6)

式中，m表示任务数量，n表示服务器节点数量。

2)资源调度节点负载均衡 节点负载均衡同样是纳入考虑的重要因素，用ω表示,即

(7)

式中，VMlj表示节点VMj负载，aVMlj表示节点的平均负载，ω值越小说明系统负载均衡度越好，此时效率越高。

3)资源调度中用户任务需求花费 另一个重要因素是任务花费，用C表示用户支付费用，如

式中：Ccpuj,Cramj,Cbwj为悉尼节点的特征量。分别代表节点cpu花费成本，内存花费成本，网络带宽花费成本。该式体现了资源调度服务按需付费的原则，合理地将任务分配到不同的计算节点上，使用户以最低的成本来达到目的。

4)效用函数 在博弈中，对于某个特定的策略序列，该序列下的单位调度成本的倒数为效用函数，用于衡量该调度的效用：

5)目标函数 资源调度系统的最大目的为保持各个节点之间公平均衡调度的前提下实现系统最低调度成本和最大化总效用。定义表述目标函数如：

1.3 基于Nash均衡算法求解

Nash均衡点在非合作博弈下具有以下几个特点，任何博弈参与者在单独改变行动策略的前提下都不会增加效用函数，因此利用Nash均衡求解能得到云计算资源调度的最优调度序列[8-9]。

定理1：在任务m的需求非合作博弈中，假如不同的任务最佳反应函数Oi(S-i)满足如下条件：

1)对于任务q的调度策略Sq(∀q≠i)，Oi(S-i)是Sq的可微函数；

则此次任务Ti的非合作博弈必定存在Nash均衡点。

此外，∀S=(s1，s2，…，sm)，根据文中定义可知S为策略空间，定义Ks=(O1(S-1)，O2(S-2)，…，Om(S-m))，于是有

由拉式中值定理可知：

2 仿真实验结果分析

实验环境：Inter i7-8086k CPU 4.0GHZ；系统平台为Windows7操作系统；软件为MATLAB2018，Cloudsim3.0仿真平台。本文实验使用谷歌Cluster trance数据作为参考。表1收集了谷歌集群5天内的各项参数变化。

表1 节点中心部分参数

本实验将经典的群智能优化算法的ACO算法(蚁群优化算法)，PSO算法(粒子群优化算法)和本文结合博弈论的改进ABC算法(后文统一用BG-ABC算法作描述)做对比，并从多个角度比较分析两个算法在实际运用中的不同点。实验结果见图2、图3。

图 2 任务完成总时间对比图

图 3 节点间负载均衡值ω对比图

由图2可知，对于资源调度任务完成总时间，BG-ABC算法较PSO算法和ACO算法具有更高的速度，PSO算法和ACO算法相差不大。由图3可知，采用BG-ABC算法的云计算资源调度系统，其系统的负载均衡度值相较于PSO和ACO算法更小，说明其系统负载均衡度更好，相关公式参见式(2-7)。

为进一步验证改进算法的高效性，这里增加实验，使用Schaffer测试函数来验证，理论上最优解为0，即当实验结果越接近0表示越精确。Schaffer函数具体表达式如下：

实验对比见图4。实验结果表明，BG-ABC算法在测试函数求最优值上具有高效性和精准性，精确度高于ACO算法和ABC算法。

图 4 Schaffer函数寻优结果对比

3 结束语

本文提出了基于博弈论的云计算资源调度优化模型，并以人工蜂群算法为前提。该模型考虑了调度时间，节点间负载均衡度，资源调度花费，效用函数和目标函数。将改进后的GB-ABC和传统PSO算法、ACO算法同时运用在资源调度下，并对实验结果进行对比，同时利用测试函数进一步证明BG-ABC算法的有效性。结果表明，BG-ABC算法较同类型的其他算法效果更佳。