基于函数约束的云任务分配的研究

聂清彬，张莉萍，霍敏霞，曹耀钦

（1.重庆邮电大学移通学院，重庆401520；2.重庆邮电大学软件工程学院，重庆400065）

基于函数约束的云任务分配的研究

聂清彬1，∗，张莉萍2，霍敏霞1，曹耀钦1

（1.重庆邮电大学移通学院，重庆401520；2.重庆邮电大学软件工程学院，重庆400065）

为了解决云环境下的资源调度问题，提出了一种改进的蚁群资源调度算法（RRLB⁃ACO），该算法在综合参考各种云计算任务调度算法的基础上，利用资源约束函数改进信息素的更新，并且通过负载均衡差函数来改进启发信息，使虚拟机经过算法多次迭代以后能够处于一种负载均衡的状态，利用CloudSim工具进行仿真测试，与标准的蚁群算法BACO、最新的ACOSA算法做仿真对比，实验结果表明RRLB⁃ACO算法在任务的执行时间、成本以及系统负载均衡方面均优于BACO算法和ACOSA算法。

云计算；资源约束；蚁群算法；任务调度；负载均衡

0 引言

云计算是将计算资源进行统一管理与统一分配的新型计算模式，根据任务的需求分配相应的资源是云计算的核心技术，云计算是把具有可伸缩的、动态的、分散的资源进行虚拟化以后以付费的方式提供给用户，用户无需关心提供服务的服务器的具体位置和分布情况，只需要提交任务给云计算中心，云计算机中心就会分配相应的资源来完成这些任务，由于云计算中的任务量巨大，每时每刻都有海量的任务提交给云计算中心，因此对于云计算系统而言，如何采用有效的资源调度算法来合理地分配资源，降低任务执行时间、成本，并且让整个云计算资源得到充分利用，提高任务执行效率成为研究的重点。

目前，云计算环境下中任务调度很多都采用Google提出的Map／Reduce的分布式编程模式，分成Map（映射）和Reduce（化简）两个阶段，在Map阶段，将用户提交的任务划分成一些小的子任务，然后分配到若干个虚拟机节点上并发地执行，执行结束并输出结果，在Reduce阶段，将Map阶段输出的结果进行汇总处理，并把最终的处理结果交付给用户，在Map／Reduce计算编程模式下，如何对分割的子任务进行高效低成本的调度是算法的关键。

很多学者提出了用改进的蚁群算法来更好地解决云环境下的任务调度，比如李建峰、彭舰［1］提出了一种带有双适应度的遗传算法（DFGA），该算法能有效缩短任务的平均完成时间，与自适应算法（AGA）进行仿真对比，算法明显优于自适应算法；魏赟、陈元元［2］提出了一种能改善任务并行性和兼顾任务串行关系的DSFACO算法，算法将用户提交的任务分成多个子任务，并根据执行先后次序放到不同优先级的调度队列中，并对处于同一调度队列中的子任务，利用最短任务的延迟时间来执行调度，在提高任务执行效率的同时，增强了调度公平性，最大程度地缩短了任务的延迟时间，实现了云环境下任务的最优分配；张浩荣、陈平华、熊建斌［3］提出了融合模拟退火算法和蚁群算法的混合算法ACOSA，该算法以最小化调度时间为目标，引入了资源和任务的匹配因子以及负载均衡度，通过改进的蚁群算法计算出任务到资源的最优解，并通过模拟退火算法对求出的解进行路径的优化以及信息素的更新，通过仿真实验，算法在调度时间、负载均衡方面都取得了良好的效果；华夏渝、郑骏、胡文心［6］提出了一种基于改进蚁群算法的计算资源分配算法，在资源调度之前，首先对可用节点的计算能力进行预测，分析线路质量、带宽的使用情况以及响应时间等因素对资源调度的影响，通过蚁群算法计算出最优的资源，该算法在符合云计算环境配置的前提下，对比以往的网格分配算法，具有更优的调度效果和更短的响应时间；史少锋、刘宴兵［7］提出一种基于动态规划模型的资源调度算法，将任务的执行时间最短作为优化目标，将虚拟机与任务的匹配看成是多阶段决策的组合优化，在一定的数量规模并且满足用户需求的前提下，减少了任务的完成时间，并且保持系统负载均衡。这些算法从不同方面优化了云计算中资源调度的过程，但是都鲜有同时考虑到通过资源约束条件以及负载均衡差来实现资源的最优调度，本文在已有的蚁群算法基础之上提出建立资源约束函数，提高虚拟机负载均衡度的改进蚁群算法（Resource Restraint，Load Balancing Ant Colony Optimization，RRLB⁃ACO）来实现对任务的分配。

蚁群算法是1992年Marco Dorigo在博士论文里提出的一种在图中寻找最优路径的算法，它模拟蚂蚁群体搜寻食物的过程，寻觅食物过程中，在其经过的每一条路经上遗留下一种信息，叫信息素（pheromone），这些路径上已经留下的信息素的浓度大小对后续蚂蚁选择自己下一步走哪条路径具有很大的影响。一般情况下，某一条路径的信息浓度越高，后续蚂蚁选择其作为下一条路径的概率也就越大，那么路径上留下的信息素也就越多，这样大量的蚂蚁选择该路径的行为就体现出蚁群的整体运动机制。该算法求解精度高且易与其他方法结合，能在海量的解空间中最大限度地寻找全局最优解，特别是解决组合优化问题方面，根据状态转移概率来搜索解的空间，结合信息素的更新，找到最优解。

1 资源约束负载均衡调度模型的建立

1.1 虚拟机的选择

在云环境中，将n个分别独立的子任务分配到m个虚拟机上并行执行（m＜n），虚拟机表示为νm＝｛νm1，νm2，…，νmm｝，子任务表示为t＝｛t1，t2，…，tn｝，每个子任务只能在一个虚拟机上运行。结合蚁群算法公式（1）计算出任务ti被分配到虚拟机νmj的概率值

其中，τij（t）表示在t时刻路径（i，j）上的信息素浓度，ηij（t）表示在t时刻路径（i，j）上的启发信息，α为期望启发因子，表示蚂蚁在任务调度过程中的启发信息对任务选择的相对重要程度；β为信息素启发因子，表示路径上的残留信息素浓度对任务选择的影响程度；tabuk（k＝1，2，…，n），记录蚂蚁已经走过的城市，被访问过的城市会加入禁忌表；allowedk表示第k只蚂蚁允许访问的下一个城市的节点，是禁忌表之外蚂蚁还没走过的城市，设置蚂蚁的迭代次数为nc，最大迭代次数为ncmax。

1.2 资源约束函数

在对云计算机中资源选择过程中，每个虚拟机完成任务的性能决定了被选择的概率，当前资源与任务分配的方案用I表示。对任务选择哪一个虚拟机来执行的几种因素主要考虑如下：

1）预计执行时间νtij表示任务ti在虚拟机νmj预计执行时间。

2）预计执行成本νcij表示任务ti在虚拟机νmj预计执行成本。

3）网络带宽νbij表示预计任务ti在虚拟机νmj执行使用的网络带宽。

4）虚拟机νdij表示预计任务ti在虚拟机νmj执行产生的延迟。

5）虚拟机νfij表示预计任务tj在虚拟机νmj执行任务产生的故障概率。

则资源约束函数res（Iij）可表示为

其中，a，b，c，d，e为5个约束条件的权重，νtmax，vcmax，vdmax，vbmax，vfmax为其边界条件，不同的云环境会有不同的取值。

1.3 负载均衡差函数

在实际云环境中，由于云计算资源存在动态性和异构性，每个虚拟机的网络带宽、计算能力、内存大小等差异较大，单位时间内执行任务的负载有较大差别，有的虚拟机性能较差，有的虚拟机性能明显更好，这样更容易造成大量任务聚集到一部分性能高的虚拟机上执行，而且容易造成等待的任务增多，同时另外性能较差的虚拟机资源却处于闲置的状态，使得整个云计算中的虚拟机负载不均衡，资源利用率很低。为了解决这个问题，本文提出建立负载均衡差函数来改变虚拟机启发信息，通过改进启发信息可以让闲置的虚拟机分配更多的任务，为分配过多任务的虚拟机减轻负载，使系统的负载始终保持均衡状态。

在云计算实际环境中，影响负载的因素有虚拟机CPU的使用率r_cpu，内存的使用率r_mem，网络带宽的利用率r_bw。因此虚拟机νmj的负载公式表示为

其中，w1＋w2＋w3＝1，w1，w2，w3分别表示CPU，内存，带宽的权值。则整个云计算系统的平均负载为

则整个云计算中心服务器负载均衡标准差Lij表示为

利用Lij结合公式（1）得到

根据公式（7）计算任务ti选择虚拟机νmj并比较每种选择方案所产生的Lij值。Lij值越小，说明任务ti选择虚拟机νmj对系统所产生的负载使得整个云计算的平均负载率越均衡，虚拟机νmj被分配到任务的概率也就越大；反之，虚拟机νmj被分配到任务的概率也就越小。经过算法多次迭代以后，改进后的算法最终能实现云计算中心虚拟机的负载平衡。

1.4 初始化信息素和启发信息

在蚁群算法中，信息素τij（t）和启发函数ηij（t）是最重要的参数，由于云计算的动态性和异构性，本文通过虚拟机的计算能力、网络带宽、虚拟机内存等对启发函数和信息素进行初始化：

其中，νm_memj表示虚拟机内存，νm_bwj表示虚拟机νmj网络带宽，νm_mipsj处理器运算速度，νm_numj表示虚拟机νmj的处理器数量。

通过轮盘赌算法计算任务选择虚拟机的概率，首先利用概率转移公式（1）计算得到任务ti选择到虚拟机νmj上执行的概率，最后用轮盘赌注法来确定某一个任务在哪一个虚拟机上执行。每一个任务到虚拟机上的执行概率就等同于赌盘上的每一个扇区，扇区面积越大，该扇区被指针选中的概率也就越大，任务分配到该虚拟机的概率值对应每个分区的大小，则任务分配到该虚拟机的转移概率值越大，更有可能被选中来执行下一个任务。在本文中选择资源和路径的过程就是寻找满足式（3）以及最小res（Iij）和最小Lij的过程。

1.5 信息素的更新

当蚂蚁将任务分配到虚拟机上以后，随着迭代次数的增加，原有的信息素就会随之增加，如果不对路径上残留的信息素进行更新，算法将会陷入局部收敛的状态，因此在每只蚂蚁完成任务分配时，就利用式（10）进行信息素更新：

其中，ρ是信息挥发因子，表示信息素在单位时间内的挥发程度，1－ρ表示信息素浓度残留程度，ρ∈（0，1］，如果ρ越大，说明信息素挥发越快，则过去搜索过的路径对现在的选择影响也就越小，Δτij表示信息素浓度的增量，信息素增量Δτij用资源约束函数Δτij定义。改进的信息素更新由局部更新和全局更新组成。

1）当一只蚂蚁通过路径搜索时，也就是任务被分配到某一个虚拟机上，找到了相应的分配方案以后，路径上所有的虚拟机都将进行一次局部信息素更新，此时Δτij定义如下：

其中，D1表示常量，res（Iki）表示第i只蚂蚁在第k次迭代中为用户搜索到的分配方案。

2）当所有蚂蚁完成路径搜索时，找到本次迭代中最优的路径，然后对路径上的所有虚拟机进行全局信息素更新，此时Δτij定义如下：

其中，MIN（res（Iki））表示在第k次迭代中蚂蚁为用户搜索到的最优的分配方案，D2为常量。

1.6 算法流程

第1步：初始化云计算机中所有虚拟机的信息素的值，信息素启发因子α和挥发因子ρ，期望启发因子β，蚂蚁个数m，设置迭代次数nc以及最大迭代次数ncmax。

第2步：将蚂蚁随机地分配到虚拟机上。

第3步：计算任务到资源的负载均衡差Lij作为启发信息，计算任务到资源的约束函数res（Iij），并根据公式（1）计算每个虚拟机被选中的概率，通过轮盘赌算法确定被最终执行任务的虚拟机。

第4步：如果完成本次任务分配，根据公式（11）进行局部信息素的更新，否则跳转到步骤2。

第5步：如果所有蚂蚁完成了本次任务的分配，根据分配情况找出本次任务分配的最优的分配方案，根据公式（12），通过本次的最优解进行全局信息素更新。

第6步：判定当前迭代次数是否达到最大迭代次数，如果是，结束算法流程，如果没有，跳转到步骤2继续执行。

2 仿真实验结果与分析

利用云计算仿真平台CloudSim 3.0验证算法RRLB⁃ACO的有效性与可行性，利用CloudSim里面的Cloudlet、DataCenter、VM等类来模拟云系统中真实环境和资源，创建虚拟机以及任务，并重写Cloudlet，DataCenterBroker类来构造RRLB⁃ACO算法，模拟云计算的真实环境，并在基于同样配置和参数设置的条件下与标准的蚁群算法以及文献［3］中的云计算中改进任务调度算法ACOSA进行对比。

在本实验中，对CloudSim模拟器参数进行设置，设置数据中心为20个，每个数据中心设置10个虚拟机，虚拟机性能参数设置为500～2 000 MIPS，内存为512～2 048 MB，带宽为5 000～10 000 b／s，任务指令长度为300～3 600 MI（Million Instruction），任务数量为100～400个，虚拟机单位时间运行所消耗成本rcu（νmj）值为25，最大迭代次数ncmax为50次，在资源中心执行时间共享和空间共享的策略，调度算法中的参数设置为：α＝1，β＝2，ρ＝0．01。

CloudSim仿真步骤如下：

1）初始化CloudSim包。

2）创建数据中心。

3）创建数据代理中心。

4）创建虚拟机。

5）创建云任务。

6）调用任务调度策略，分配任务到虚拟机。

7）启动仿真。

8）仿真结束后分析结果。

实验中在同等条件下将标准的蚁群算法BACO、文献［3］中的ACOSA算法和本文的RRLB⁃ACO算法进行试验仿真，对比任务的执行时间、成本以及虚拟机的负载率状况，具体实验数据如图1～3所示，图中任务执行成本单位为美元（），执行时间单位为秒。实验结果分析如下：

从图1可以看出，在任务数量在100左右的时候，三者算法执行任务时间差别不大，随着任务数量的增加，BACO和ACOSA算法对比，ACOSA算法执行时间比BACO算法短。同等条件下，RRLB⁃ACO算法使任务执行时间最短。任务在选择虚拟机的过程中，算法中的资源约束函数总是通过算法对比选择出执行当前任务时间相对较短的虚拟机，有更好地发现解的能力，提高资源利用率，对缩短任务执行时间发挥有效作用。

图1 任务执行时间比较Fig.1 Comparison of task execution time

从图2可以看出，当任务量在200以内时，3个算法执行成本差别不大，随着任务数量的增加，执行同样多数量的任务，BACO算法执行费用最高，ACOSA算法执行成本比BACO降低了一些，RRLB⁃ACO算法的执行成本比ACOSA降低35%左右，说明通过资源约束函数res（Iij）中的成本约束、网络带宽约束、执行时间约束等函数，算法总能在目前可选的虚拟机中选择出与当前任务匹配并且执行成本相对较低的虚拟机来执行任务，从而达到降低任务执行成本的目的。

图2 任务执行成本比较Fig.2 Comparison of task execution costing

图3反映了虚拟机的负载均衡度的对比，从图中可以看出，标准的蚁群算法BACO负载均衡度是最低的，说明负载极不平衡，ACOSA算法负载有所改进，RRLB⁃ACO算法相比前面两种算法将负载均衡度提高了0.3左右，使云计算资源系统负载一直维持在一个相对均衡的状态，说明通过成本函数改进以后的蚁群算法通过多次迭代以后，使得整个系统的负载均衡度提高，再与图1、图2的任务执行时间、成本对比分析，RRLB⁃ACO算法所产生的任务执行时间短，负载均衡度高，充分说明了云系统的负载均衡度越高，虚拟机的利用率就越高，以后用户提交的任务的执行时间也就越短。

图3 负载均衡率比较Fig.3 Comparison of load balancing rate

3 结束语

本文提出了基于资源的约束函数，负载均衡差的改进蚁群优化算法RRLB⁃ACO，用来改进云计算中的资源调度，实验结果表明，RRLB⁃ACO算法性能明显优于ACOSA和BACO，有效优化了资源的调度，降低执行时间和成本，提高了系统执行任务效率，让云计算系统始终保持在一个负载均衡的状态。

［1］李建峰，彭舰.云计算环境下基于改进遗传算法的任务调度算法［J］.计算机应用，2011，31（1）：184⁃187.

［2］魏赟，陈元元.基于改进蚁群算法的云计算任务调度模型［J］.计算机工程，2015，41（1）：12⁃16.

［3］张浩荣，陈平华，熊建斌.基于蚁群模拟退火算法云环境任务调度［J］.广东工业大学学报，2014，31（3）：77⁃82.

［4］张焕青，张学平，等.基于负载均衡蚁群优化算法的云计算任务调度［J］.微电子学与计算机，2015，5（5）：31⁃40.

［5］左利云，左利锋.云计算中基于预先分类的调度优化算法［J］.计算机工程与设计，2012，33（4）：1357⁃1361.

［6］华夏渝，郑骏，胡文心.基于云计算环境的蚁群优化计算资源分配算法［J］.华东师范大学学报（自然科学版），2010，2（1）：127⁃134.

［7］史少锋，刘宴兵.基于动态规划的云计算任务调度研究［J］.重庆邮电大学学报（自然科学版），2012，6（1）：687⁃692.

［8］林伟伟，齐德昱.云计算资源调度研究综述［J］.计算机科学，2012，39（10）：1⁃6.

［9］张水平，邬海艳.基于细胞自动机遗传算法的云资源调度［J］.计算机工程，2012，38（6）：11⁃13.

［10］刘卫宁，靳洪兵，刘波.基于改进量子遗传算法的云计算资源调度［J］.计算机应用，2013，33（8）：2151⁃2153.

［11］卓涛，詹颖.改进人工蜂群算法的云计算资源调度模型［J］.微电子与计算机，2014，31（7）：147⁃150.

［12］Dinh H T，Lee C，Niyato D，et al.A survey of mobile cloud compu⁃ting：architecture，applications，and approaches［J］.Wireless Com⁃munications and Mobile Computing，2013，13（18）：1587⁃1611.

［13］Garg S K，Versteeg S，Buyya R.A framework for ranking of cloud computing services［J］.Future Generation Computer Systems，2013，29（4）：1012⁃1023.

［14］Venkata Krishna P.Honey bee behavior inspired load balancing of tasks in cloud computing environments ［J］.Applied Soft Computing，2013，13（5）：2292⁃2303.

［15］Yuan H，Li C，Du M.Optimal virtual machine resources scheduling based on improved particle swarm optimization in cloud computing［J］.Journal of Software，2014，9（3）：705⁃708.

［16］Armbrust M，Fox A，Griffith R，et al.A view of cloud computing［J］.Communication of the ACM，2010，53（4）：50⁃58.

Research on cloud task allocation based on constraint of function

NIE Qing⁃bin1，ZHANG Li⁃ping2，HUO Min⁃xia1，CAO Yao⁃qin1
（1.College of Mobile Communication，Chongqing University of Posts and Telecommunications，Chongqing 401520，China；2.College of Software Engineering，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

In order to solve the problem of resource scheduling in cloud environment，an improved ant colony resource scheduling optimization algorithm（RRLB⁃ACO）is proposed.Based on a variety of cloud computing task scheduling algorithms，a resource con⁃straint function is used to improve the update of information elements in this algorithm，and the heuristic information is improved by load balancing function，which enable the virtual machine to be in a state of load balance after many iterations of algorithm.The sim⁃ulation test is carried out using the CloudSim tool，and compared with the standard BACO algorithm and the latest ACOSA algo⁃rithm.The results show that the RRLB⁃ACO algorithm performs better in task execution time，cost and system load balancing.

cloud computing；resource restraint；ant colony optimization；task scheduling；load balancing

TP393

A

10．3969／j．issn．1007⁃791X．2015．05．012

1007⁃791X（2015）05⁃0453⁃05

2015⁃07⁃15 基金项目：重庆市前沿与应用基础研究计划一般资助项目（cstc2014jcyjA40049，cstc2015jcyjA30001）；重庆市教委科学技术研究资助项目（KJ130527）

∗聂清彬（1982⁃），男，四川资中人，硕士，讲师，主要研究方向为云计算与物联网，Email：270104318＠qq.com。