方锦明

（义乌工商职业技术学院 机电信息分院，浙江 义乌322000）

0 引 言

Luis M.Vaquero学者在研究了20种云计算的定义后，给出了一个云计算的定义：云计算是一种大规模的易用的可访问的虚拟资源 （如硬件、平台和／或服务）池［1－4］。由此可知，虚拟性［5］在云计算中扮演了一个核心角色。然而，在云计算环境中，虚拟资源的调度问题也凸显出来。虚拟资源的调度是指，按照一定的规则合理地将用户申请的虚拟资源映射到相应的物理资源。一个好的调度器应该能够均匀地将虚拟资源映射到物理资源上，然而，由于请求的虚拟资源的差异性和物理资源的异构性，该问题是一个难解问题。

在现在的已经实现的云计算调度系统上，一般都是采用简单的策略实现。如EC2［6］使用按购买分配，VMware［7］按照CPU和内存的使用动态分配，NimBus［8］和 Eucalyptus［9］采用静态贪婪策略和随机选择，oVirt［10］采用手工分配模式，OpenNebula［11］采用需要／排序动态分配的策略。简单的调度策略来进行调度已经很难满足日益增长的云计算的规模，因此不少学者开始研究这个问题。如Ravi Iyer［12］研究了虚拟资源间对物理资源的竞争所导致的性能下降，并提出了一种有效的模型来预测这种下降并在此基础上提出了一种虚拟机管理模型；墨尔本大学的学者［13］提出了一个InterGrid系统来管理不同云系统间虚拟资源的迁移问题；国内学者田冠华等［14］提出了一种基于失效规则的资源动态提供策略，能有效提高动态提供节点资源的可靠性。

本文通过对虚拟资源调度过程的分析，将虚拟资源的调度过程抽象为具有CPU，内存，和带宽等属性的节点的匹配过程，分析了该问题的难解性，将其转换为具有负载均衡的多目标优化问题，采用多目标优化算法来对虚拟资源进行调度。与具体的虚拟资源调度的实现相比，该调度模型更能反映云计算中虚拟资源调度的复杂性，同时不同于简单的调度策略，采用多目标优化算法进行调度，能使得云计算中虚拟资源的调度更加合理。通过实验验证了本文提出的模型的合理性并验证了使用多目标优化算法求解该问题的合理性。

1 虚拟资源调度的建模

不同于网格计算等其他分布式计算平台，云计算中一个核心就是虚拟化。图1是云计算与其他分布式计算平台的差异。简单地讲，虚拟资源就是通过虚拟化技术将物理资源抽象为同一的虚拟资源。使用虚拟资源的优点有：

图1 云计算与其他分布式平台的差异

（1）可用性：在共享的分布式环境中，每个用户的需求是不一样的，在没有对资源虚拟的情况下，当一个用户占用了一个物理资源时，其他的用户只有等待，而该用户使用结束时，其他用户又不得不重新配置自己的环境。当资源被虚拟化后，不仅不同的用户可以同时使用相同的资源，而且每个用户只需配置自己的环境一次。

（2）安全性：在虚拟环境中，每个用户的程序相互隔离，当一个用户程序出现崩溃以后，不会影响到其他用户程序的运行；同时，每个用户在虚拟环境中，其权限受到限制，对用户的数据更加安全。在虚拟环境中，用户可以随时暂停，保存，恢复程序的运行。当由于配置错误等其他原因导致环境崩溃后，可以通过回滚的方式将环境恢复到正确的状态。

（3）迁移性：当由于设备更新换代或者其他原因需要将程序迁移到新的环境中时，虚拟资源的配置可以很容易迁移到其他平台上。

虚拟资源的优点导致了虚拟化技术的蓬勃发展，然而，将虚拟资源均衡地调度到物理资源上成为一个难点。因为每个用户对虚拟资源的需求不同，而且物理资源也具有差异性。本文首先对虚拟资源的调度进行建模并证明其难解性。

虚拟资源的调度是将虚拟资源合理地映射到物理资源上。在云计算的实际环境中，一个虚拟资源可以抽象为一个具有一定属性的节点。如一个具有cpu属性，内存属性和带宽属性的虚拟资源可以抽象为v（c，m，b），其中，c为cpu属性，m为内存属性，b为带宽属性。同理一个物理资源也可以抽象为p（c，m，b）。如表1所示。

表1 抽象后的虚拟资源及物理资源

在此基础上，本文提出如下定义：

定义1 虚拟资源的调度是将将虚拟资源映射到物理资源上的一个方案，对应于虚拟资源vi（cvi，mvi，bvi），vi＝1，2，… ，m，和物理资源pi（cpi，mpi，bpi），pi＝ 1，2，… ，n，一个调度可以由m个物理资源组成的排列L（pi1，pi2，…，pim）来表示，此时，虚拟资源cv1被调度到物理资源pi1，虚拟资源cv2被调度到物理资源pi2等。

定理1 采用穷举算法进行求解，虚拟资源的调度是难解问题。

证明：采用穷举算法对云计算环境中的虚拟问题进行求解，则，对于v1有n个选择，v2有n个选择，…，vm有n个选择，因此对于排列L有nm种，因此该算法的时间复杂度是O（nm），由NP问题的定义知，该问题是难解问题。

2 基于NSGA II的虚拟资源调度算法

在前面讨论的基础上，本文针对虚拟资源的调度问题，提出采用多目标优化算法进行求解，下面分别介绍多目标优化算法的主要组成部分：编码、优化函数和搜索算法。

2.1 编 码

由定义1知道，虚拟资源的调度是寻找一个调度序列，设虚拟资源的编号为vi＝1，2，…，m，物理资源的编号为pi＝1，2，…，n。本文采用序列编号作为编码方式，因此对需要调度的虚拟资源进行排序设为 （v1，v2，…，vm），然后按照排序对虚拟资源进行调度，设调度序列为 （va1，va2，…，vam），其中，vai∈｛pi｝，则调度方法为，对应于vi，i＝1，2，…，m，其映射的物理资源为vai。算法中的编码方式为（va1，va2，…，vam）。

2.2 优化函数

评价一个调度算法的好坏，主要是看该算法给出的调度方法是否符合负载均衡的要求，因此本文借鉴数学上方差的思想，对资源分布的均匀性进行量化，提出了针对不同属性的均匀分布策略。

对于一个给定的编码 （va1，va2，…，vam）有：（1）cpu属性的均衡度

因此，cpu的均衡度为

同理，可得：

（2）内存属性的均衡度

（3）带宽属性的均匀性

2.3 搜索算法

本文使用NSGA II［15］对问题求解。NSGA II是多目标优化算法中的经典算法，其思想与遗传算法类似，不同的是在个体选择过程中首先按照Pareto支配的概念进行排序同时计算个体的拥挤度，然后按照非支配优先，拥挤度较小的原则选择个体。Pareto支配是指：设求解目标函数的最小值，则对于两个个体，若所有的目标有：A （B）＜＝B（A）且A不等于B，则称A （B）支配B （A），反之，则称A、B互不支配。NSGA II能一次求解多个目标，但是，非支配排序是一个非常耗时的过程，为改善算法的求解性能，受文献［16］的启发，本文提出了如下基于树的非支配求解算法来加快算法的求解速度。

首先对种群按照第一个目标进行排序，然后对每一个个体赋一个唯一的编号，设1，2，…，n。因此编号小的个体一定不会被编号大的个体所支配。然后采用二叉树构造法构建一棵非支配树。最后采用算法1获取非支配解集。

算法1：获取非支配解集

遍历树Tree获得非支配解集F

逐个将Tree及其左子树压入第一层非支配解集F1；

将F1压入F；

循环如果F中的个体数＜小于树节点个体的一半

对于Fi－1中的每一个个体p

对于pi＝p.right；pi！＝null；pi＝pi.left

若pi不被Fi中的个体所支配

将pi添加到Fi；

否则

将pi添加到集合Left；

对于每个pi属于Left

若pi不被Fi中的个体所支配

将pi添加到Fi；

若pi支配Fi中的某个个体qi

将qi添加到Left；

程序结束

算法的整体流程图如图2所示。首先随机生成包含n个基因的种群P1，同时选择交叉，变异生成下一代种群Q1；然后，将一棵空树和节点集PiUQi作为参数输入到算法1，返回一棵树，对该树按算法2进行遍历得到排序后的集合，同时对最后一个集合进行拥挤度的计算；最后按照非支配优先，拥挤度较小的原则选择个体，即：若A支配B，则选择A，若A，B互不支配，则选择拥挤度较小的那个个体。

图2中，选择交叉采用锦标赛选择，两点交叉，即，随机选择两个个体，并选择其中较优的个体作为父个体p1，同样的方法选择父个体p2，然后随机生成两个交叉点c1，c2，将p1从c1到c2的基因片段与p2从c1到c2的基因片段交换，生成子个体u1，u2。变异是对每个个体每一位按照变异因子Pc进行变异，即：若随机数小于变异因子，则随机生成一个基因位替换原来的基因。算法中采用基于树的非支配排序算法进行排序，然后参照文献 ［15］计算拥挤度，即：对于每一个目标，非支配个体按照该目标排序，对于第一个和最后一个个体拥挤度为最小，其他个体则是相邻两个个体的距离倒数。

图2 算法的整体流程

3 实验及结果分析

实验的主要目的有：①验证NSGA II算法的可行性；②在不同资源数和不同资源比例下对比NSGA II与随机调度算法，静态调度算法及排序匹配算法。

3.1 实验设置及对比算法的描述

本文实验Java语言编程实现。算法的具体参数设置如下：种群个数：48，最大迭代次数：1000，交叉因子：0.9，变异因子：1／l，其中l为基因长度。本文对比了3种简单的调度算法：随机调度算法，静态调度算法和排序匹配算法。对于虚拟资源集V，物理资源集P，3种算法简述如下：

（1）随机调度算法：随机给出一个调度方案L（a1，…，am）；

（2）静态调度算法：调度方案为L （a1，… ，am），其中，ai＝i%n；

（3）排序匹配算法：该算法的主要思想是：对于一个要分配的资源，寻找与其最接近的物理资源作为分配策略。即：对于某个虚拟资源vi（cvi，mvi，bvi）和物理资源pi（cpi，mpi，bpi），pi＝1，2，… ，n，其计算公式如下：ai＝min｛pi｝，pi＝1，2，… ，n。此时有：min｛｜cpi－cvi｜＋｜mpi－mvi｜＋｜bpi－bvi｜｝。

3.2 对本文示例的求解

对第二节的实例进行求解，以验证本文模型的正确性和NSGA II求解该问题的可行性以及对比其他算法的优势。限于篇幅，表2给出了使用NSGA II算法对第二节实例求解的前8个非支配解的求解情况。从表中可以看出NSGA II可以通过一次求解获取多个不同的解。因此，本文采用3种策略来选择最终解：cpu策略、内存策略、带宽策略、均衡策略，实际使用中可以根据不同的需要进行选择。cpu策略是指：在所有解中选择cpu最均衡的解。内存和带宽策略亦类似。均衡策略是指：对于一组非支配解，选择目标函数之和最小的解。

表2 使用NSGA II求解的非支配解集分布情况

表3给出不同策略下的求解结果，注意，随机算法、静态算法和排序算法不能按照相应的策略给出不同的解。

表3 NSGA II算法对本文实例求解结果及与其他算法的对比

从表3中可以看出几种属性间相互影响，对于一个给定的问题，几乎不存在唯一最优解。同时，NSGA II给出了多个解，用户可以按照自己的要求选择不同的解，而简单的求解算法则无法达到这样的要求。简单地可以看到，NSGAII给出的解几乎全面优于其他算法。

3.3 不同资源比下的比较

为了更详细地比较NSGA II与其他算法的求解结果，了解在不同资源映射情况下NSGA II的解的情况，本文对多个资源分配进行求解。在云计算环境中，虚拟资源个数与物理资源个数比代表了资源的紧张程度。如：虚拟资源个数与物理资源个数的比例0.2，那么，此时有大量的物理资源被闲置，此种情况下，调度的均衡性变的不是非常重要；反正，若比例为1.2，则表明物理资源非常紧张，调度的好坏，直接影响着系统的均衡性和吞吐量。为全面了解算法的求解情况，本文对比例为 ［0.2－1.2］的虚拟资源调度进行求解。

实验中，随机生成个数为 ［100－1000］的物理资源，然后按照不同的比值生成虚拟资源。物理资源和虚拟资源的各个属性随机生成。CPU取值为 ［100～2000］，内存的取值为 ［10～4000］，带宽的取值为 ［1～100］。这样的资源取值可以充分代表异构的物理资源的复杂性及虚拟任务的多样性。

图3－图5显示了在均衡策略下算法运行100次后的平均结果。3张图分别表示cpu，内存和带宽的均衡性。从图中可以看出，NSGA II算法要全面优于其他算法。而随机算法和固定算法的均衡度接近，排序算法的均衡度最差。这是因为，排序算法是按照匹配度进行的，这样会导致某个匹配的机器负载较重，资源分配失去平衡性。

为从直观的数值上比较各个算法的均衡度，表4给出了各个算法在不同资源比下的各个均衡度的平均值及NSGA II相比其他算法的均衡度提高的倍数。从表中可以看出，在均衡策略下，NSGA II各个数值都要优于其他算法的结果。

表4 各个算法的平均值及NSGA II相对于其他算法提高的倍数

4 结束语

本文对云计算环境下的虚拟资源调度问题进行了建模，提出将虚拟资源和物理资源抽象为具有一定属性的节点的匹配过程。采用NSGA II算法对该问题进行求解，同时改进了NSGA II的非支配排序过程。最后通过实验对比了NSGA II算法和其他3种基于简单策略的调度算法。实验表明，NSGA II可以用来求解云计算环境下的虚拟资源调度问题，一次求解给出多个候选解，为用户采用不同的调度策略进行调度提供了可能性。同时，实验中给出了在均衡策略下与其他3种简单的调度算法的对比，结果表明，本文提出的基于NSGA II的调度算法能进行更好地调度。

［1］Armbrust Michael，Fox Armando，Griffith Rean，et al.A view of cloud computing ［J］.Communications of the ACM，2010，53 （4）：50－58.

［2］WANG Jiajun，LU Zhihui，WU Jie，et al.Cloud computing technology development analysis and applications discussion［J］.Computer Engineering and Design，2010，31 （20）：4405－4409（in Chinese）.［王佳隽，吕智慧，吴杰，等.云计算计算发展分析及其应用探讨 ［J］.计算机工程与设计，2010，31 （20）：4405－4409.］

［3］Amazon.Amazon EC2 ［EB／OL］.http：／／www.amazon.com／ec2，2011.

［4］Luis M Vaquero，Luis Rodero Merino，Juan Caceres，et al.A break in the clouds：Towards a cloud definition ［J］.ACM Sigcomm，2009，39 （1）：50－55.

［5］Mendel Rosenblum，Tal Carfinkel.Virtual machine monitors：Current technology and future trends computer ［J］.Computer，2005，38 （5）：39－47.

［6］Ostermann Simon，Iosup Alexandria，Yigitbasi Nezih，et al.A performance analysis of EC2cloud computing services for scientific computing ［J］.Cloud Computing，2010，34 （4）：115－131.

［7］VMware Inc.VMware VCloud initiative ［EB／OL］.http：／／www.vmware.com／technology／cloud－computing.html，2011.

［8］WANG Lizhe，Laszewski Von Gregor.Scientific cloud computing：Early definition and experience［C］.Dalian：10th IEEE International Conference on High Performance Computing and Communications，2008：825－830.

［9］Nurmi Daniel，Wolski Rich，Grzegorczyk Chris.The eucalyptus open－source cloud－computing system ［C］. Washington：IEEE Computer Society，2009：1－8.

［10］Redhet Inc.oVirt.［EB／OL］.http：／／ovirt.org，2011.

［11］Borja Sotomayor，Rubén S Montero，Ignacio M Llorente，et al.Virtual infrastructure management in private and hybrid clouds［J］.Internet Computing IEEE，2009，13 （5）：14－22.

［12］Ravi Iyer，Ramesh Illikkal，Omesh Tickoo，et al.VM3：Measuring modeling and managing VM shared resources ［J］.Computer Networks，2009，53 （17）：2873－2887.

［13］Alexandre Di Costanzo，Marcos Dias De Assuncao，Rajkumar Buyya.Harnessing cloud technologies for a virtualized ［J］.Distributed Computing Infrastructure，2009，13 （5）：24－33.

［14］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing ［J］.Chinese Journal of Computer，2010，33 （10）：1859－1872 （in Chinese）［田冠华，孟丹，詹剑锋.云计算环境下基于失效规则的资源动态提供策略 ［J］.计算机学报，2010，33 （10）：1859－1872.］

［15］LI Hui，ZHANG Qingfu.Multiobjective optimization problems with complicated pareto sets MOEA／D and NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2009，13（2）：284－302.

［16］SHI Chuan，YAN Zhenyu，SHI Zhongzhi，et al.A fast multi－objective evolutionary algorithm based on a tree structure［J］.Applied Soft Computing，2010，10 （2）：468－480.