徐浙君,陈善雄

(1.浙江邮电职业技术学院,浙江 绍兴 312000; 2.西南大学 计算机与信息科学学院,重庆 400715)

基于膜计算和蚁群算法的融合算法在云计算资源调度中的研究

徐浙君1,陈善雄2

(1.浙江邮电职业技术学院,浙江 绍兴 312000; 2.西南大学 计算机与信息科学学院,重庆 400715)

针对云计算下的资源调度的问题,提出将蚁群算法的个体与云计算中的可行性资源调度进行对应,首先对云计算资源调度进行描述,其次针对蚁群算法的路径选择引入了平衡因子,对信息素进行了局部研究和全局研究,将蚁群个体引入到膜计算中,通过膜内运算和膜间运算,提高了算法的局部和全局收敛的能力,最后在云计算资源分配中,引入匹配表概念,将云计算任务和资源进行匹配,融合后的算法提高了算法的整体性能;仿真实验说明在网络消耗,成本消耗,能量消耗上有了明显的降低,提高了资源分配效率。

蚁群算法;膜计算;平衡因子;信息素;匹配表

0 引言

自从云计算概念被提出来之后,有关云计算的方面的资源利用就成为了众多系统供应商以及学者研究的对象,云计算的本质是一种集成了分布式计算,网格计算和网络技术的互联网概念,由于云计算中资源取决于用户执行任务的效率,网络的成本消耗和时间消耗等等约束条件,如何能够更好的满足这些约束条件进行云计算资源调度成为目前的研究方向[1-2]。国内外学者研究如下,文献[3-4]提出了在云计算中使用粒子群算法进行云计算资源调度,仿真实验说明改进的粒子群算法能够有效的提高云计算下的资源分配效率,降低消耗的时间；文献[5-7]提出了将改进的蚁群算法运用到云计算资源调度中,通过蚂蚁个体的运动来描述云计算中的资源调度,仿真实验表明该算法的总任务完成时间较短,具有较好的寻优能力,并且能够实现负载均衡,是一种有效的资源调度算法；文献[8]提出在云计算资源算法中引入布谷鸟算法,并对布谷鸟算法进行改进,使得改进后的算法收敛精度提高,能够有效的提高云计算环境下的资源分配效率。

本文在云计算的资源调度中引入蚁群算法,将蚁群算法中的蚁群个体与云计算中的可行性资源调度进行对应,针对蚁群算法的不足进行改进,同时引入膜计算,使得改进后的粒子群算法和蚁群算法组成的融合算法在云计算的资源调度中节省了资源分配时间,提高了资源分配效率。

1 云计算资源调度描述

云系统中有n个任务的集合T={T1,T2,…Tn},资源节点集合G={G1,G2…Gn},前面描述了粒子群算法中一个粒子的位置就是一个可行解,因此任务Ti在资源Gj上完成,则粒子k的位置表示为Xk={x1,x2,…xi,…xn},其中xi表示任务i分配到资源为xi,因此Xk是一个可行的分配方案。本文采用文献[11]描述的云计算资源调度模型, 综合云计算中的各种条件,设置资源调度的约束函数表示为:

(1)

式中,Delay表示网络延迟,Time表示执行时间,Source表示网络消耗资源,A,B,C分别表示各自约束条件的权重。云计算分配的资源就是需要找到满足函数最小值,从而使得云计算资源分配的成本,时间和网络消耗都达到一个尽可能的最优值。

2 基本算法介绍

2.1 膜计算概述

膜计算是一种从生物细胞生成的启发上得到来的算法,其概念是由欧洲科学院提出的,膜计算的本质主要模仿细胞在进行变换过程中的细胞内和细胞间之间的变换而抽象出来的一种计算模型。膜结构如图1所示。

膜计算表示如下:

(2)

其中：V是输入内容,T是输出内容,μ表示膜结构,wx表示膜内对象,Rx表示膜内规则,ρx表示内部执行顺序。膜算法具有的特点是:

(1)膜中的各个区域都是单独,相互时间没有直接联系,膜内进行各自的计算,膜内的交流仅仅发生在相邻的区域,这样可以加速产生局部最优解。

(2)膜计算能够有效的避免局部计算陷入最优,可以结合其他智能算法提高算法精度。

2.2 蚁群算法

蚁群算法是一种在模拟大自然中的蚂蚁寻找食物的智能算法,蚂蚁能够寻找到食物主要依靠前面蚂蚁所留下的信息素从而能够指引前进,蚂蚁个体所经历过的路径上的分泌的信息素越多,这样引导后续的蚂蚁走该条路径上概率就越大,路径概率的选择和信息素更新选择如下:

(3)

(4)

3 改进的蚁群算法

3.1 蚁群算法的不足

在蚁群算法的初始阶段存在一定数量的随机路径(主要是路径长度相对短的路径),算法初始阶段蚂蚁个体会随机的选择的几条路径来进行寻找食物,通过在这些路径上遗留下的信息素来引导后续的蚂蚁前进,但是信息素的分布浓度与路径的长度存在一定的关系,路径越长信息素浓度越低,反之信息素浓度越高,信息素的变换效果直接影响到后续蚂蚁的路径选择,需要注意的是蚂蚁个体在每次遍历之后,无论是最好的路径还是最差的路径,都会留下一定的信息素,因此,最差的路径都会得到一定的信息素累计,这样就会造成对后续蚂蚁的影响,而出现无效的搜索,延迟了最优蚂蚁个体所经过的路径的产生。

3.2 针对选择路径的改进-平衡因子

蚁群算法中的蚂蚁个体在前进的路径的选择上需要考虑信息素的浓度的大小,这样的选择有可能会出现最优路径会被忽视,而陷入局部最优路径的选择中,其实在蚁群算法中的各个路径上的相关信息素之间的差异并不大,为了尽可能的降低这种风险,在概率转移规则中增加一个平衡因子来降低在搜索过程中的陷入局部最优解的影响,如果当前蚂蚁寻找最短路径的时候,就赋予该蚂蚁个体高因子值,反之,则应该赋予该蚂蚁个体低因子值.设置平衡因子如下:

(5)

式中,lmax和lmin分别代表蚂蚁个体在当前迭代中所在路径中长度的最大值和最小值,l(α)表示蚂蚁个体所走的路径的长度,A(i,j)表示在迭代中的路径i→j的集合。设定蚂蚁的总个数M,蚂蚁选择的其他经过点的数目为cad,本次迭代中经过路径i→j的蚂蚁个数为A(i,j),算法伪码如表下所示。

表1 引入平衡因子算法伪码

因此,通过上面的平衡因子的选择得到目标的选择的概率如下:

(6)

(7)

3.3 信息素优化

前述中已经描述了蚁群算法中的信息素是一个决定后续蚂蚁是否前进选择的重要的参考,对其信息素本身而言,本文进行2个方面的优化:

(1)局部信息素优化。

在进行选择路径的过程中,蚂蚁个体每经过一条路径之后,就会对路径上的所有的信息素进行更新,这就是所谓的局部更新,在局部信息素更新中,蚂蚁所走的路径上的信息素是按照一定的比例挥发消失,因此减低了该路径对于其他的蚂蚁的吸引,从而提高了算法的迭代空间,在目前大部分的蚁群算法中,局部信息素的挥发因子是一个固定的常量,这样的设置对于很多路径上的信息素的挥发没有说服力,因此本文在局部的信息素的更新上引入动态信息素挥发因子,该因子主要是可以用来动态的描述在信息素在不同情况下的挥发的变化情况。

(8)

(2)全局信息素更新。

当所有的蚂蚁都进行完成第一次遍历之后,假设有k只蚂蚁通过路径i→j,按照在迭代过程中的每只蚂蚁走过的路径对这k只蚂蚁进行排序,按照从小到大的顺序存储这些蚂蚁走过的路径长度,记做list[k],因此信息素的更新如下:

(9)

在公式中,wr表示第r只蚂蚁所经过的路径上的信息量的更新程度,当list[r]值比较小的时候,第r只蚂蚁走过的路径小于其他蚂蚁的路径长度,则wr取正值,当全局更新信息素的时候,该只蚂蚁会增大路径上的信息量。当list[r]值比较大的时候,第r只蚂蚁走过的路径大于其他蚂蚁的路径长度,则wr取负值,该只蚂蚁在全局信息素会降低。

4 基于膜计算和蚁群算法的融合算法在云计算资源调度

4.1 设定匹配表

为了更好的适应云计算下的资源的调度,而资源的分配对应不同的节点完成的任务,特别是在云计算中涉及的资源种类比较繁多,相同类型的任务能够获得相同的资源进行处理,在对应的任务和资源之间,加入一个匹配表。这样可以更加有效的匹配云计算下的任务和资源。在匹配表中,每一个云计算的任务通过匹配表找到对应的节点序列,在节点序列中按照节点使用频率的高低进行排列，通常优先级高的会被选中。因此蚂蚁个体在寻找出发节点的时候，如果蚂蚁个体对应的云计算任务对应的节点在匹配表中存在,则选择节点强度最大的节点为初始节点, 否则选随机节点为初始节点。当最后查找到需要的节点时候,将该节点添加到匹配表中。

4.2 基于膜计算和蚁群算法的融合算法的云计算资源调度

4.2.1 算法融合

蚁群算法的缺点是容易陷入局部最优，根据云计算中资源分配的要求，蚁群算法显然在一定程度上无法能够更好的分配云计算的资源，膜计算的优点在于能够通过膜内运算和膜间运算，合理的避免产生局部最优的可能。因此两种算法的融合可以很好的提高蚁群算法的效率，从而确定最优解。进而可以有效的获得云计算中的资源分配效率。

4.2.2 编码规则

4.2.3 算法内容描述

图1描述的膜结构中情况，以其中的某一个膜为例，5当作主膜,膜6,7,8当作辅助膜。主膜是提高蚁群算法个体的全局最优能力,同时接受来自其他膜中传递过来的优异的蚂蚁个体,从而进一步保证能够进行全局最优，辅助膜主要是针对蚁群算法的搜索空间进行局部搜索,为主膜提供局部最优解。

步骤1:辅助膜6内在进行迭代的时候,根据蚂蚁个体对应的适应度的优劣进行从小到大的排序,从中选择优秀的蚂蚁个体到主膜中。转换规则如下:

(10)

步骤2:辅助膜7中按照公式改进的信息素和概率选择更新蚁群个体,迭代中按照从小到大进行排序,将最差的蚁群个体重新进行初始化操作,再次进行排序。

(11)

步骤3:辅助膜8中的的蚂蚁个体按照蚂蚁算法的步骤进行,迭代更新的结果进行从小到大的排序,如同上面的步骤一样送入到主膜中。

(12)

步骤4:按照公式(6),(7)计算主膜中的蚂蚁个体。通过前述的步骤,将从辅助膜中传递的蚁群个体进行排序。按照如下的规则进行排序。

(13)

步骤5:如果达到最大迭代次数,则退出迭代,最优的蚂蚁个体即是最佳云计算资源分配方案,否则继续执行步骤2。

(14)

算法流程如图2所示。

图2 算法流程

5 实验与分析

为了验证本文算法具有的有效性和可行性,本文采用Cloudsim平台来模拟云计算环境,在平台中对DataCenterBroker类,Cloudlet类,CloudCoordinator类进行了重写,初始化蚁群算法和膜计算的各个相应的参数,同时设置最大迭代次数。

文献[9]和文献[10]是关于云计算资源调度中较新的研究算法,将本文的算法与这两种算法进行云计算的资源比较,从节点能量消耗,时间消耗和带宽消耗上进行比较,设定虚拟任务为1 000个,虚拟资源为100个,从图3～5中发现,本文算法在能量消耗,完成时间方面和成本消耗方面低于其他的云计算调度算法,在能量消耗方面,时间消耗和带宽消耗相比于其他两种算法平均降低了7.12%,10.18%和6.21%,本文算法能够有效的降低了能量消耗,能够有效的降低云计算中的资源调度所带来的能量消耗的问题。

图3 3种算法的能量消耗比较

图4 3种算法的时间消耗比较

图5 3种算法的网络消耗带宽比较

6 结束语

针对云计算的资源调度的问题,本文引入了膜计算和蚁群算法,首先对蚁群算法中的路径与信息素的匹配进行改进,其次针对信息素所处状态的不同进行局部更新和全局更新,最后将蚁群个体融入到膜计算中,融合后的算法提高了算法效率,CloudSim实验说明本文算法能够有效的提高云计算的资源分配效率,节省时间和降低能量消耗.

[1] 李 乔.云计算研究现状综述[J].计算机科学,2011,38(4):32-36.

[2] 葛 新.基于云计算集群扩展中的调度问题研究[D].合肥:中国科学技术大学,2011.

[3] 蔡 琪,单冬红,赵伟艇.改进粒子群算法的云计算环境资源优化调度[J].辽宁工程技术大学学报(自然科学版),2015,35(1):93-96.

[4] 周丽娟,王春影.基于粒子群优化算法的云计算资源调度策略研究[J].计算机科学,2015,42(6):279-283.

[5] 张焕青,张学平,王海涛,等.基于负载均衡蚁群优化算法的云计算任务调度[J].微电子学与计算机,2015,32(5):31-35.

[6] 王常芳,徐文忠.一种用于云计算资源调度的双向蚁群优化算法[J].计算机测量与控制,2015,23(8):2861-2863.

[7] 蒋 华,张乐乾,王 鑫.基于多维评价模型及改进蚁群优化算法的云计算资源调度策略[J].计算机测量与控制,2015,23(7):2559-2562.

[8] 叶华乔,丁善婷.基于改进的布谷鸟算法在云计算资源的研究[J],计算机测量与控制,2014,22(12):4150-4154.

[9] 赵宏伟,李圣普.基于粒子群算法和RBF神经网络的云计算资源调度方法研究[J].计算机科学,2016,43(3):113-116.

[10] 嵇可可.基于动态趋势预测蚁群算法的云计算资源调度优化研究[J].科技通报,2016,32(1):187-190.

[11] 宁 彬,谷 琼,吴 钊.基于膜计算的蝙蝠算法在云计算资源调度的研究[J].计算机应用研究,2015,32(3):830-83.

Research of Fusion Algorithm Based on Membrane Computing and Ant Colony Algorithm in Cloud Computing Resource Scheduling

Xu Zhejun1, Chen Shanxiong2

(1.Zhejiang Technical College of Posts&telecom,Shaoxing 312000,China; 2.College of Computer and Information Science,Southwest Universtiy,Chongqing 400715,China)

Aiming at the issue of resource scheduling in cloud computing, this paper proposes to correspond individuals in ant colony algorithm with feasibility resource scheduling in cloud computing. Firstly, it describes resource scheduling in cloud computing and then aiming at the path choice of ant colony, balancing factor is introduced for global research into pheromone, and individual ants are introduced into the calculation of membrane. The membrane computing and membrane operations have improved the ability of local and global convergence. Finally, in resource allocation of cloud computing, the concept of matching table is introduced to match tasks and resources in cloud computing. The integrated algorithm has improved the entire performance of the algorithm, and simulation platform experiment shows that it has reduce the network consumption, cost consumption and energy consumption as well as the resource allocation efficiency.

ant colony algorithm; membrane computing; balancing factor; pheromone; matching table

2016-06-29；

2016-08-17。

国家自然基金项目(61303227)。

徐浙君(1980-),男,讲师，硕士,主要从事数据挖掘和云计算方向的研究。

1671-4598(2017)01-0127-04

10.16526/j.cnki.11-4762/tp.2017.01.036

TP3

A