２０１３年第１１期　

文章编号：１００９—２５５２（２０１３）１１—００２９—０４　中图分类号：ＴＰ３０１．６　文献标识码：Ａ　

云计算资源调度算法的研究与实现　

余星，胡德敏，黄超　

（上海理工大学光电信息与计算机工程学院，上海２０００９３）　

摘要：在研究蚁群算法、任务分配和资源调度的基础上，提出了一种改进的蚁群资源调度算　

法。首先通过引入节点可信度机制在一定程度上增强了云计算资源的搜索能力和节点完成任务　

的成功率。然后在改进的算法中使用了信息素的局部更新机制和全局更新机制，可以有效地平　衡负载。最后通过选取合适的参数利用ＣｌｏｕｄＳｉｍ仿真工具对改进的资源调度算法进行实验测试，　

实验结果表明此算法缩短了任务的执行时间，改善了云计算资源调度的性能。　

关键词：云计算；蚁群算法；资源调度；可信度　

Ｒｅｓｅａｒｃｈ　ａｎｄ　ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　ｏｆ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　

ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　

ＹＵ　Ｘｉｎｇ．ＨＵ　Ｄｅ．ｍｉｎ，ＨＵＡＮＧ　Ｃｈａｏ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｏｐｔｉｃａｌ－Ｅｌｅｃｔｒｉｃａｌ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｈａｎｇｈａｉ　ｆｏｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｇｈ￣２０００９３，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　ｔａｓｋ　ａｌｌｏｃａｔｉｏｎ，ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｎｄ　Ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｄ　ａｎ　ｉｍｐｒｏｖｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ｒｅｓｏｕｒｃｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ａｌｇｏｒｉｔｈｍ．Ｆｉｒｓｒｔ，ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　

ｅｆｆｅｃｔｉｖｅｌｙ　ｉｍｐｒｏｖｅｄ　ｔｈｅ　ｓｅａｒｃｈ　ａｂｉｌｉｔｙ　ａｎｄ　ｓｕｃｃｅｓｓ　ｒａｔｅ　ｂｙ　ｉｎ￣ｏｄｕｃｉｎｇ　ｔｒｕｓｔ　ｖａｌｕｅ　ｍｅｃｈａｎｉｓｍ．Ｔｈｅｎ　ｔｈｅ　

ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｄ　ａ　ｇｌｏｂａｌ　ａｎｄ　ｌｏｃａｌ　ｐｈｅｒｏｍｏｎｅ　ｕｐｄａｔｉｎｇ　ｍｅｃｈａｎｉｓｍ　ｔｏ　ｒｅａｌｉｚｅ　ｌｏａｄ　ｂａｌａｎｃｅ　ａｔ　

ｅａｃｈ　ｎｏｄｅ．Ｆｉｎａｌｌｙ，ｔｈｅ　ＣｌｏｕｄＳｉｍ　ｓｉｍｕｌａｔｉｏｎ　ｔｏｏｌｓ　ｉｓ　ｕｓｅｄ　ｔｏ　ｓｉｍｕｌａｔｅ　ｔｈｅ　ｓｔｒａｔｅｇｙ　ｏｆ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ｒｅｓｏｕｒｃｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ　ｂｙ　ｃｈｏｏｓｉｎｇ　ａｐｐｒｏｐｒｉａｔｅ　ｐａｒａｍｅｔｅｒｓ．Ｔｈｅ　

ｒｅｓｕｌｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｍｐｒｏｖｅｄ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｎｄ　ｔｈｅ　ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ｏｆ　ｔａｓｋ．　

Ｋｅｙ　ｗｏｒｄｓ：ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ；ａｎｔ　ｃｏｌｏｎｙ　ａｌｇｏｒｉｔｈｍ；ｒｅｓｏｕｒｃｅｓ　ｓｃｈｅｄｕｌｉｎｇ；ｔｒｕｓｔ　ｖａｌｕｅ　

０　引言　

云计算是一种新型且新兴的信息技术，它由分　布式计算、网格计算、并行计算等技术发展而来，将　

大量计算、存储和软件等资源集中在一起，构成超大　

规模且高性能，可扩充性的虚拟ＩＴ资源池，再通过　服务接口像广大云用户提供以按需计费这种独特的　

商业服务模式。　合理的分配云计算资源是云计算中的重要组成　

部分之一，其效率直接影响着整个云计算产业链。　

云计算资源调度算法大致可分为三类，有的是以性　能为中心的调度策略，有的是以经济原则为中心的　

调度策略，还有的是以服务质量为中心的调度策略。　目前，有很多国内外研究人员研究蚁群算法在云计　

算资源分配中的应用，已经在很大程度上避免了单　

个节点上分配效率低和规模庞大的缺点，可以确保　

用户任务按时完成。　

１　相关研究　

目前云计算资源调度管理是云服务供应商和云　

计算研究面临的一大难题。各大云计算服务供应商　

根据各自搭建的云平台特点采用不同的调度策略，　

收稿日期：２０１３一Ｏ５—２８　基金项目：国家自然科学基金项目（６１２０２３７６）　作者简介：余星（１９８７一），男，硕士，研究方向为云计算和计算机　网络。　

一

２９—　其中广而熟知的是Ａｍａｚｏｎ云计算平台，Ｇｏｏｇｌｅ云计　

算平台和ＩＢＭ蓝云平台。　

Ａｍａｚｏｎ的调度策略是采用了不同地域收费不　同的调度分配策略，供用户选择。而性能方面主要　

由用户选择预先配置好的虚拟服务器；然后用户根　

据自己任务需求提出租用请求并在线提交。Ｇｏｏｇｌｅ　提出的ＭａｐＲｅｄｕｃｅ编程模式，是一个用于大规模数　据处理的分布式计算模型，同时也是一种高效的任　

务调度模型。ＩＢＭ云平台的资源分配与任务调度采　

用专用的资源监控代理和作业调度器来管理系统资　源调度。　另外广大云计算研究人员也对云计算资源调度　

进行深入的研究并提出很多有效的调度算法和模　型。文献［２］中李建峰等人基于ＭａｐＲｅｄｕｃｅ模型，　

提出了一种具有双适应度的遗传算法，注重作业的　

平均完成时间；文献［３］中汤小春等人提出了一种　基于元区间的分配决策算法；文献［４］中华夏渝等　

人提出一种基于蚁群优化的资源分配算法；文献　［５］中Ｘｕ等人研究了针对云计算中多个工作流的　

多ＱｏＳ调度策略，对于不同的用户考虑不同的ＱｏＳ　需求，提出一种云环境下的多作业流多ＱｏＳ约束的　

调度策略。　

本文提出了一种改进的蚁群算法，并用于云计　算资源调度中，通过引入可信度机制，局部更新信息　

素机制，全局更新信息素机制能有效的提高云计算　资源调度性能和负载均衡的性能。　

２基于蚂蚁群算法的云计算资源调度　

２．１　蚁群算法　蚁群算法是一种用来寻求最优化路径的群体智　

能算法。蚂蚁都是在事先不知道食物在何处的前提　下开始寻找食物，当某一只蚂蚁找到食物后，它会相　

应的释放一种叫做信息素（ｐｈｅｒｏｍｏｎｅ，该分泌物随　着时间的推移会慢慢的挥发消失）的分泌物吸引其　

他的蚂蚁过来觅食，这样找到食物的蚂蚁越来越多；　在此期间有些蚂蚁会另辟蹊径，如果它们搜索到的　

路径比其他蚂蚁搜索到的路径短，那么会有大量蚂　

蚁会选择这条更短的路径进行觅食；如此下来，可能　会出现一条最短路径被大多数蚂蚁重复着，由于蚁　

群算法的并发性和可扩展性，所以其很适用于云计　

算环境下的资源调度　。　２．２信息素初始化　

本文是用虚拟机的硬件资源来衡量一个节点的　信息素，其中，ｍ是ＣＰＵ的个数，Ｐ是处理能力，ｒ是　

内存容量，ｈ是外存容量，ｂ是带宽，这些用来测量节　点的信息素，初始化节点各硬件的信息素。　

一３０一　ＣＰＵ的信息素：　

（Ｏ）：　－１００％　（１）　。　ｍｏ。，‘０　内存的信息素：　

．ｒ　（Ｏ）＝　・１００％　（２）　ｔ－Ｏ　外存的信息素：　

Ｌ　Ｔｉｈ（０）＝　・１００％　（３）　‘０　带宽的信息素：　Ｌ　（０）＝　・１００％　（４）　ｕ０　节点ｉ的信息素是上面各个信息素的加权和，　如公式（５）所示：　

（０）＝ａＴｉ，（０）＋６ｒ　（０）＋ｃ下ｆＪｌ（０）＋ｄｒ　（０）　

（５）　其中，ａ＋ｂ＋ｃ＋ｄ＝１。　

２．３可信度机制　本文引入了节点的可信度评价机制，可信度越　

高的节点，表示节点执行任务的成功率越高，在分配　

任务时可以优先分配给可信度高的节点。用公式衡　量节点的可信度：　

＝　／　（６）　为节点的可信度，　为节点实际完成任务总　

数，　为节点接受的任务总数，当　和　相同时，　可信度为１，这时资源节点完成任务的成功率是最　

高的。　２．４信息素更新机制　当一个新任务被分到计算节点时，ＣＰＵ，内存等　的利用率会增加，同时资源的信息素也会随之减少。　

利用局部更新机制更新节点的信息素浓度：　

（ｔ１）＝　ｉ（ｔ）一Ａｒ　（ｔ），０＜Ａ＜１　（７）　其中，７－　（　）表示在ｔ时刻ｉ节点的信息浓度，７－　（ｔ　）　在ｔｌ时刻任务分配到ｉ节点上的信息浓度，Ａ是调　

节因子。　有效节点上的任务随着时间的推移会越来越　少，负载减轻，当计算节点完成任务后，根据全局更　新机制更新节点的信息素得到的信息素浓度为：　

７－ｉ（ｔ１）＝ｐｒｉ（ｔ１）＋ｔｏｔ　（８）　

其中，Ｐ为信息素的持久性，ｔ为任务运算量，在任务　执行成功时∞为奖励因子或者惩罚因子。任务执　行成功时的奖励因子　为０．５，任务执行失败时的　

惩罚因子∞为一０．５。　

２．５路径选择机制　蚂蚁在搜寻目标节点过程中，根据各条路径上　

信息素浓度大小决定蚂蚁下一跳节点，蚂蚁总是向　着路径上信息浓度相对较大的方向移动。蚂蚁ｋ　

（ｋ＝１，２，…，ｍ）在运动过程中根据各条路径上信息　

素浓度决定其移动方向。在ｔ时刻，蚂蚁ｋ选择下　

一跳节点的概率Ｐ　（ｔ）为：　

ｒ　７－　（ｔ）　（ｔ）　．　，，　，　

Ｐ　（　）：』——　：—　丽’　∈口　。　。ｄ　（９）　

ｔＯ　ｏｔｈｅｒｗｉｓｅ　

其中，ａｌｌｏｗｅｄ　＝｛０，ｌ，２，…，ｎ｝为蚂蚁ｊ｝下一跳节　

点；．ｒ　（ｔ）是ｉ节点在ｔ时刻的信息素浓度；ｓ是ｉ的　

邻居节点，　是节点ｋ的固有属性，即启发因子，参　

数　和　为调节因子，　小收敛速度较快，ＪＢ小收敛　速度慢。　

２．６适应度函数　本文随机产生权系数，使得每只使用不同的权　

系数来计算各自的适应度值。本文所求的云计算资　源调度问题可以用下面的函数求适应度值：　

Ｆ（ｔ）＝Ａ１・Ｆ　（ｔ）＋Ａ２・　（ｔ）＋Ａ３・．ｒ　（ｔ）＋　

Ａ４厶（ｔ）　（１０）　其中，　（ｔ）表示节点ｉ在ｔ时刻执行任务时最大完　

工时间，周期（虚拟机的最大完工时间），　（￡）表示　

ｔ时刻某一虚拟机节点　的可信度丁　（ｔ）表示节点ｉ　

在￡时刻的信息素浓度，　（ｔ）表示ｔ时刻节点ｉ的当　

前负载量。　

３　资源调度算法描述　

根据以上描述，改进的蚁群算法在云计算资源　

调度中应用的步骤如下：　

①初始化各节点信息素。　②向Ｍａｓｔｅｒ节点提交ｚ个任务，并预定资源分　

配的时间。　￣Ｍａｓｔｅｒ节点发送ｒｔ（ｎ≤Ｚ）只蚂蚁；并把每只　蚂蚁ｋ的初始出发节点置于其路径节点集中。　

④根据公式（６）计算每个节点的可信度值。　⑤根据公式（１Ｏ）计算每只蚂蚁的适应度值。　

⑥每只蚂蚁ｋ根据公式（９）按概率Ｐ　（ｔ）选择　

下一跳节点，并按公式（７）更新每个节点的信息素　

浓度。　⑦若某只蚂蚁的当前适应度函数由于其历史适　

应度度值，则记录当前适应度为该蚂蚁的历史最优　适应度，同时记录其对应的历史最优节点；若在　

Ｍａｓｔｅｒ节点预定时间内没找到最优虚拟机节点，搜　

索失败。　⑧向每只蚂蚁的最优虚拟机节点分配任务，如　

果任务执行成功按公式（８）更新节点的信息素浓　度；如果任务执行失败除了按公式（７）更新节点的　信息素浓度外，与此同时根据公式（８）同步更新节　点的可信度值，失败的任务由Ｍａｓｔｅｒ节点转移到其　

它的节点完成。　（￣）Ｍａｓｔｅｒ节点取下一批任务，重复步骤③一⑧，　

直到所有任务都完成。　

４　实验仿真与结果　

为了验证改进的蚁群算法在云计算资源调度应　用中的正确性和有效性，本文在开源云计算仿真平　

台ＣｌｏｕｄＳｉｍ上实现了仿真，并且与ＣｌｏｕｄＳｉｍ中现有　

的最优时间调度算法以及标准蚁群算法进行了比　较，对实验结果进行了分析。算法中的ａ，ｂ，ｃ，ｄ分　

别表示了虚拟机的ＣＰＵ，内存，外存及带宽的重要　

性，分别设为０．４，０．２，０．２，０．２。调剂因子Ａ　为　

０．５，信息素持久性因子Ｐ取０．２，Ｍａｓｔｅｒ节点预定搜　索时间设为２秒。在算法仿真过程中，本文采用了　

表１所示的任务参数和表２所示的虚拟机属性。　表１任务参数　

ＶＭＩＤ　ＩＭＡＧＥＳＩＺＥ　ＭＥＭＯＲＹ　ＣＰＵ　ＢＡＮＤＷｒｒＨ　

Ｃｌｏｕｄｌｅｔ　ＩＤ为０，ｌ，２，３，４，５的任务执行过程中　

分别调用ＶＭＩＤ为２，ｌ，３，１，１，０的虚拟机来完成任　

务计算，如表３所示。　表３实验１改进算法的资源调度　

Ｃｌｏｕｄｌｅｔ　ＩＤ为０，ｌ，２，３，４，５的任务在执行过程　

中分别调用ＶＭＩＤ为１，０，２，３，１，０的虚拟机来完成　

任务计算，如表４所示。　

一

３１—