基于蜂群算法的云计算调度研究*

王 准

(广州工商学院)

基于蜂群算法的云计算调度研究*

王 准

(广州工商学院)

文章先分析了云计算任务调度的内涵，综述了蜂群算法的原理，继而通过云计算调度问题的描述，提出云计算调度的数学模型，最后通过仿真实验，证明改进的蜂群算法可以很好地改善云任务调度系统的性能，有一定的借鉴意义.

蜂群算法;改进算法;云计算;任务调度

0 引言

云计算是一种新兴技术，是由分布式计算、并行式计算以及网格计算的基础上发展而来的，亦是计算机科学商业化的体现，其实现了用户的按需付费，使得用户不但可获取高质量服务，还有效节省了费用，也减少了维护及管理问题.伴随云计算技术的进步，用户需求逐渐变化，同时服务资源也逐步增多，故而，在云任务调度中如何更好的满足用户需求以及合理利用服务资源，就成了云计算研究的重要课题.

1 云计算任务调度综述

云计算中的任务调度和旧有的分布式任务调度有某些共同点，也有本质区别.第一，云计算中的资源变化多端，任务调度的时候要实时监控资源的动态变化，但是也有一些计算资源不会变化，比如：传统的分布式的任务调度.另外，在云计算中，由于其资源类型各异，所以需要结合其不同类型来对其资源进行屏蔽，而且虚拟技术大多较为成熟.计算资源在以往的分布式子里，大多都是同构的.而且，其任务调度的目标简单，主要是对其完成时间以及任务的吞吐量等等性能指标进行分析，而云计算中的任务调度目标要最大限度的增加云服务收益.

当下有关云计算的任务调度算法的研究非常多，例如，蒲汛等人提出的则是改进离散粒子群算法的优化办法，这种算法能够按照用户不同的调度需求，在较短的时间里对云计算调度完成一定的优化；王芳等人提出了一个动态自适应蚁群算法的云计算调度的办法，这种算法在选择资源的时候按照信息素的浓度可以自适应地调节挥发因子；李依桐等人提出的是一个混合粒子群优化算法的云计算调度方法，这种算法在计算调度的时候加入遗传算法的交叉以及变异的原理同时综合爬山算法，可使种群在进化的初期阶段有很强的全局搜索性能.

目前已有的算法虽可以完成任务调度，但伴随云计算逐步走向商业化，用户对任务调度的需求更加多样.已有的云计算的调度模型大多都是针对其单方面的需求，但是对于服务商和用户的满意度不能兼顾，另外，在蜂群的算法中，没有对种群中的较优解进行利用，未结合云任务的高维特征有针对性的予以更新.

2 蜂群算法(ABC算法)原理

2.1 蜜蜂采蜜原理

蜜蜂在釆蜜的过程中，主要涉及三个关键环节，一是食物源，未被雇佣的蜜蜂以及被雇佣的蜜蜂，另外，还包括放弃食物源和为获得食物源进行的招募行为.因为，单个蜜蜂在找寻食物源的实际过程中，因为能力非常有限，所以，它会借助摇摆舞来进行招募，蜜蜂相互间能够明白其交流信息，积聚蜜蜂集体的智慧，然后找到食物源和蜂巢之间的最优路线，蜜蜂采蜜的详细工作过程如图1所示.

图1 蜜蜂采蜜工作图

2.2 ABC算法原理

在蜂群的算法中，食物源的位置代表着需要优化的一个解，在求解的时候就是找寻食物源的一个过程.初始的时候，由于食物源是随机的，所以，每个可行的解也是随机的，可以将这个过程表示为如下式子：

F(xi),xi∈RD,i∈{1,2,3,…，SN}

(1)

其中，xi是D维向量，代表食物源位置.F(xi)就是对应的目标函数值，食物源数量用SN表示.

在下一阶段，为找到最优解，蜂群将重复雇佣峰、侦查蜂以及跟随蜂三个过程，在雇佣蜂的阶段，雇佣蜂设法得到邻域内的蜜源，再将此适应度值和存储的适应度值进行比较，二者选择出最优，然后再选择可行解的最优值得适应度值，那么，雇佣蜂的寻找方式可以表示为：

Vij=xij+φij(xij-xik)

(2)

其中，Vij表示新可行解，xik是随机的临近可行解，xij是现有可行解.而φij是随机数，其值在-1到1之间，表示在可视范围内蜜蜂对其两个蜜源间的比较.k和i数值不相等，且k和j均是随机的.在跟随蜂的阶段中，雇佣蜂为了实现信息共享，可以借助跟随蜂与摇摆舞的方式来传达信息.跟随蜂在进行蜜源选择时是存在概率的，即，当收到雇佣蜂的信息，然后结合食物源的充足度，再对蜜源概率的公式进行选择，具体如下：

(3)

当食物源目标锁定后，跟随蜂会在目标食物源周围再确定一个新的食物源，这个新食物源可以适时进行更新，当雇佣峰传播的信息准确，即蜜源信息准确，那么，跟随蜂就会召集非常多的雇佣峰进行采集该蜜源，那么相反，当雇佣峰传播的信息准确度较低，蜜源不确切，那么，跟随蜂就会果断放弃此食物源，雇佣峰转为侦查蜂.因此，跟随蜂传播信息的正确与否直接关系着蜜蜂的数目以及食物源与蜜蜂数目的关系，算法收敛速度加快.另外，当跟随蜂转播信息不准确时，转化为侦查蜂后，侦查蜂随机选择食物源，所以，在一定程度上扩大了多样性，促进算法实现局部最优，随机选择的过程用以下式子表示为：

(4)

3 云计算调度问题描述

3.1 建立任务模型

目前阶段，较为典型的云计算任务调度算法大多采用Map或者Reduce的模型，也就是将一个任务划分为多个子任务，且相互独立，再将多个虚拟的资源节点作并行的计算，然后再将运行结果进行归集，进而得到最后结果.T可以用如下表示：T={Task1，Task2，…，Taskn}，即由n个元素组成的集合；Taski是云计算用户所提交的任务，可以将此表示为Taski={U.Ci,U.T,U.Ri}，其中U.Ci、U.Ti和U.Ri分别表示用户对虚拟机资源的执行费用、完成时间和可靠性的需求.

3.2 云资源的模型

4 云计算调度数学模型

4.1 建立云任务的目标函数

首先，将目标函数转化为满意度的函数，然后再利用云任务调度方案来综合其满意度，将多目标的问题转化成单目标的问题，然后再进行求解.最短等待时间的满意度在区间t1至t2，满意度的计算公式为(5).当W在区间t1至t2的时候，该文采用ε比W的方式能对区间t1至t2进行区分.同上，虚拟资源负载均衡度的满意度区间为b1至b2，满意度为计算式(6)；而经济花费的满意度区间为h1至h2，其满意度的计算式为(7).其中，3个ε为同等级的极小数.

(5)

(6)

(7)

4.2 对改进的蜂群算法进行求解

4.2.1 详细描述解的构造

假设有m个虚拟服务资源，n个云任务，主要是由虚拟服务资源对云任务进行批量的处理，那么，改进蜂群的解的描述为：

Xi=(xi1，xi2，…，xin);i=1，2，…，SN

(8)

其中，Xi是第i只蜜蜂；SN是蜜蜂的总数量；变量xij取值是取0到m-1区间所有的整数.比如：Xi=(3，2，1，2，3，1，1，3，0，0)，具体表示的含义是，十个云任务需要被处理，每个虚拟资源分别对应的云任务需要进行处理，即X1=3，就是代表第一个云任务，需要在虚拟资源为3时进行处理，以此类推，X10=0，即为第十个云任务，需要在虚拟资源为0时进行处理.

4.2.2 对解进行初始化

对解进行初始化，在进行初始化的过程中，产生的非整数解即为非可行解，但是，可以将其进行取整，这样就可以变成可能解.另外，对于位置更新的公式所产生的非可行解也可以采用这种方式来进行处理.

4.2.3 详细对位置更新的阶段进行描述

该文主要利用的ABC算法，按照上述式子(2)进行位置更新搜索，也就是对复解进行更新，进而产生一维的新解，而且每次只对此进行更新，但面临数量较多的云任务的时候，就必须要采用高维度的方式进行搜索，根据这个原理，该文对位置更新而言，一共提出了下述两种更新维数的具体方法.具体描述为：一是随机改变S1，随机取整数带入连续ABC位置更新公式中则生成位置，如式(9).二是S2突变算子，在进行高维度搜索的时候，可以借助负载较重的资源对位置进行有方向地改变.突变算子具体关系如式子(10)所示.

vij=int(xij+φij(xij-xkj))；φij∈[-1,1]

(9)

vij=(xij→int(rand[0,1]*m));xij∈Vid(max(v1j))

(10)

4.2.4 论述跟随蜂选择蜜源的策略

该文在对跟随蜂选择蜜源的策略进行分析，其方法主要是利用维度为二的方式随机进行选择，这样的话，跟随蜂就能够对蜜源进行选择，大多情况会选择适应度值较高的蜜源.蜜源选择的过程中，其数值的大小在此过程中，并不能进行具体显示，所以，较小的蜜源一样能够被跟随蜂选择到.

4.2.5 对局部进行搜索

该文在对局部进行搜索的时候，需要在跟随蜂和雇佣蜂阶段引入局部的搜索算子，这样就可以得到新解，然后再进行局部的搜索，从而能够得到Ui.

4.2.6 侦察蜂阶段

该文针对侦查蜂的行为进行了研究，在一定程度上，能够改善解的优劣性.对于侦查蜂的解能够有效降低搜索的效率，该文主要是选择维度为二的方式，随机选择蜜源，然后计算出蜜源差，进而将种群的最优解与蜜源进行交叉操作，然后产生新的解，继续进行贪婪算子的选择，从而得到最优.

5 试验结果分析

首先设本实验的虚拟机数是20，云任务数是150，侦察蜂的数目是1，跟随蜂与雇佣蜂的数目是50，迭代次数是1000次，SDABC-W的PLS=0．01，ABC是将最短的用户等待时间设为目标函数为单目标，是一种离散形式的人工蜂群算法.本次实验实现了其他不同调度算法所实现的调度优化，在优化云任务调度方面，对FCFS策略、DWLC方法、MIN-MIN算法、基本离散人工蜂群算法ABC策略、贪心等算法进行比对.在该文中，为了将等待时间定义为最短，此改进的ABC方法将目标函数定义为其等待时间最短，进而利用云任务进行调度的求解过程，此过程可以缩写为SDABC-W.详细的实验结果如图2，6种不同算法的云调度任务得出的最短的等待时间.

图2 6种调度算法比较

6 结束语

该文主要从理论等方面，在多目标的蜂群算法中，通过构建虚拟资源中的云任务进而得到最优解，即，可以得到最优的调度方案.因此，MDABC基本能够满足多目标的具体要求，可以为未来的云任务调度系统建立更好的模型，促进其发展.

[1] 王芳，李美安，段卫军．基于动态自适应蚁群算法的云计算任务调度[J]．计算机应用，2013,33(11)：3160-3162．

[2] 蒲汛，杜嘉，卢显良．基于用户优先级的云计算任务调度策略[J]．计算机工程，2013，39(8)：64-68．

[3] 李依桐，林燕．基于混合粒子群算法的云计算任务调度研究[J]．计算技术与自动化，2014，33(1)：73-77．

(责任编辑：李家云)

Research on Cloud Computing Scheduling Based on Bee Colony Algorithm

Wang Zhun

(Guangzhou Business School)

In this paper, a swarm algorithm based on cloud computing scheduling optimization method is proposed. connotation of cloud computing task scheduling is analyzed, the principle of ant colony algorithm is summarized, and then through the cloud computing scheduling problem description, a mathematical model of cloud computing scheduling is proposed, simulation results prove that the performance of improved ABC algorithm can greatly improve the cloud task scheduling system, which have certain reference significance.

Bee colony algorithm; Improved algorithm; Cloud computing; Task scheduling

2016-04-13

*2015年广东省教育厅重点平台及科研项目,青年创新人才类项目(2015KQNCX196));2016年广东省高等教育学会高职高专云计算与大数据专业委员会课题(GDYJSKT16-18)

TP3

A

1000-5617(2016)05-0025-04