基于最大收益平衡点动态变化的云资源调度算法

张爱科，符保龙

(柳州职业技术学院，广西柳州545006)

0 引言

云计算可以看作是一种超大型的分布式计算形态，它通过对计算能力、存储能力的高度整合，为用户提供了规模空间的计算服务。在云计算的整个体系中，如何对云端的资源进行有效地管理和调度，不仅对于满足用户需求而且对于增加云端收益，都具有重要的意义［1］。

目前，对于云计算资源调度的研究有2个视角:①从提供云计算服务的供应商角度;② 从使用云计算服务的用户角度。相比较而言，更多的云计算资源调度的研究都集中于供应商的角度［2］。在云计算资源调度中如何实现节能是一个重要的研究领域，根据负载需求进行资源调度的策略一般可以通过分组分批地形式执行，分组执行期之间的间歇一般被作为节能的主要突破口［2-3］。衡量成本-收益也是一种常见的云资源调度策略，比较不同聚类方案的调度成本成为常用方法之一［4］。张水平等［5］将元胞自动机理论引入到计算资源调度之中，构造了一种基于元胞自动机改进的遗传算法。这种方法有效地解决了遗传算法过早收敛的问题，特别有利于大规模云资源的调度。刘利祥等［6］为了实现云资源的合理调度和高效分配，构造了一种多属性联合区间的调度方法，它通过各个区间对应的索引，介入保留协议，有效地实现了云资源的动态调度。谭靓亮等［7］在传统蚁群优化算法的基础上，构建了一种自适应的多态蚁群算法，实现了云资源调度的寻优方法。刘永等［8］从节能的角度出发，构建了一种基于信任驱动模式的云资源节能调度算法，有效地实现了云端虚拟机资源的初始化和合理迁移。Zhang以提高Web服务质量为目的，对于多虚拟机的CPU调度展开了研究，并基于效用最大化理论构建了一种全局调度算法，实验结果证实了这种CPU调度方法明显提高了网络应用程序的性能［9］。张伟哲［10］以云计算中的内存部署问题为研究对象，对内存资源足备的情况采用自发调节方案，对内存资源紧缺的情况采用全局调节方案，实验结果证实了这种方法对于计算密集和存储密集的任务需求都是有效的。Camillo［11］从用户的角度出发展开了研究，指出了用户获得更好云服务的前提是给定一个合适服务需求描述集合。这是因为，过多的需求描述会加重系统负担，而过少的需求描述会导致云服务质量难以满足需求。为此构建了一个基于网格中间件的需求优化器，以便为用户需求定制最合理的描述集合。Sharkh［12］提出了一个新的资源分配模型，用于解决一组云用户的请求。这个模型中比较了4种不同的资源分配方法，最终证实基于资源分布和时间优先的方法可以更好地解决群组用户的云服务请求。

从已有的研究成果可以看出，从用户需求和生产商需求来考虑云计算资源调度的方法很多，而从服务商需求的角度构建云资源调度的方法很少。本文以此为切入点，从服务商的角度出发，在不损害用户和生产商利益的前提下，引入一种最大收益模型，构建一种基于最大收益动态变化的云资源调度方法，并通过实验检验其调度性能。

1 本文算法的构建

近年来，云计算获得了飞速发展。云端资源的规模日益扩大，这也给资源调度模型的构建和资源调度算法的设计带来了越来越大的麻烦［13］。但无论云规模发展到什么程度，基于服务的角度出发去制定资源调度策略，都是符合客观实际的，这也是本文云资源调度算法设计的出发点。在云计算服务的整个过程中，可以把不同参与者归为3种角色:生产商、服务商、用户。生产商就是各种云平台的拥有者，他们拥有实际的云资源和计算处理能力。服务商是实现用户需求和生产商能力相对接的服务者，他以一定的成本从生产商手中租用云资源，又以一定的价格向用户出售云服务，以赚取中间的差价为盈利手段。用户是有实际任务要处理的需求者，通过向服务商支付相关费用获得云服务。从这三者的关系看，生产商试图提供更强大的云计算能力，以争取和更多的服务商签订订单。服务商希望自己手中掌握更强的云服务资源，以吸引更多的用户使用。用户则希望在花费相同费用的情况下，获得最佳的云服务质量。

从生产商、服务商、用户三者的地位来进行衡量现有的硬件条件日新月异。因此，生产商不断提高云计算能力是客观的、现实的;用户是云计算服务的消费者，不宜不断地提升服务收费。因此，本文在不提高用户服务费用的前提下，着重以服务商的经济性诉求出发，来构建云资源的调度模型。

本文算法的基本思路是，从经济学领域借鉴成本、收益、边际收益、边际成本等概念，不断地考察当前周期和上一周期边际收益的变化，实时捕捉能够达到最大收益的平衡点，并利用这个平衡点位置对应各个参数，指导实际的云资源调度。

1.1 收 益

在这里，我们用SY(shou yi)表示收益。当用户从服务商手中租用一定的云服务时，需要向服务上支付相关的费用，这个费用就是服务商获得的收益。这个费用的多少，是根据在服务基础上以往提供的服务质量来制定的，用户则需要根据自己的需求选择相应的服务。一般来讲，这个费用会在租用服务开始时就确定下来，并在享受云服务的整个过程中保持稳定。服务商能够提供的云服务会包括多种类型，这样才能满足不同用户的需求。为此，将这些服务(fu wu，FW)设定一个集合，其集合形式为

(1)式中，FWi表示服务商所能提供的每一项服务，i=1，2，…，n。对于公式(1)中的各种服务，被用户定制和使用的次数(ci shu，CS)对应于服务集合的次数所形成的集合如公式(2)所示。

(2)式中，CSi表示用户定制和使用某一项服务的次数，i=1，2，…，n。仍然对应于(1)式的情况，每种服务的使用都有其相关的费用，也就是服务商能从用户手中获得的费用，其集合形式如下。

设SYZ表示一个服务商在一定时期内的收益总和，则该SYZ可以用公式(4)表示。

1.2 成 本

成本(cheng ben，CB)是指服务商从生产商的手中租用云资源所付出的费用，采用CB来表示。服务商向生产商租用的FWi集合中，每一项服务对应的成本可以用CBi表示，最终形成的成本集合如下。

(5)式中，i=1，2，…，n。由公式(2)和公式(5)可以得:

(6)式中，CBZ表示服务商从生产商手中租用云服务的总花费，i=1，2，…，n。在实际当中，服务商从生产商手中租用云服务还有着不同的形式，比如按单位租用时间付费、一次性支付、竞拍型服务。从生产商的角度来看，他们也通过不断地改变服务形态增加服务的多样性，比如按照内存、CPU的品质进行服务类型的区别，或者按照服务规模的大小进行区别。在本文后续的研究中，将根据这些情况对云服务的形式进行细化设置。根据收益和成本这2个参数，可以确定服务商能获得的净收益(jing shou yi，JSY)如公式(7)所示。

这样，从服务商的角度看，云资源调度应该满足最大净收益的获得。这样，最佳的云资源调度方案也就变成了如何来获得最大净收益的方案。

1.3 最大净收益

最大净收益除了和成本、收益有关，也与服务数量和调度的资源数量直接相关，本文用虚拟机(virtual machine，VM)表示服务数量和调度的资源数量。一般来讲，净收益会随着用户的数量增加而上升，但这种上升态势不是线性的。根据边际收益的变化规律，当用户的数量不断增加、服务商需要从生产商租用虚拟机的数量也要不断增加，这样会使得云端的负载不断增加，这时净收益的上升趋势会呈现减弱的趋势。净收益几个关键因素之间的关系曲线如图1所示。

图1 净收益的变化曲线Fig.1 Changes in net income curve

从净收益的变化曲线可以看出，净收益和收益、成本、虚拟机数量、边际成本(bian ji cheng ben，BJCB)、边际收益(bian ji shou yi，BJSY)有关。其中，对于净收益影响最大的就是边际成本和边际收益。这2个因素的数学描述如公式(8)所示。

从公式(8)中可以看到，所谓边际成本，就是促成一个单位的产出增加需要增加的成本。因此，可以用成本的变化和产出变化的商来表示，也就是SY和VM的导数。对于本文的云资源调度，产出用虚拟机的数量进行表示。所谓边际收益，就是促成一个单位产出得到的收益。因此，可以用收益的变化和产出变化的商来表示，也就是CB和VM的导数。

1.4 本文的算法描述

从图1的曲线变化关系可以看出，要使得服务商的净收益最大，需要使得边际收益和边际成本相等，即满足如下的关系。

在图1中，BJCB0对应的位置可以看作是净收益平衡的初始位置。这时，如果服务商承接的用户需求又有增加，总收益会加大，对应地收益曲线也会向上增加，相应地虚拟机数量也会增加，这样边际成本和边际收益的平衡点也会向右移动到BJCB1的位置，对应的收益也会从SY0增加到SY1，虚拟机数量也会从VM0增加到VM1，如果服务商承接的用户需求有所减少，总收益会减少，对应地收益曲线也会向下下降，相应地虚拟机数量也会减少，这样，边际成本和边际收益的平衡点也会向左移动到BJCB2的位置，对应的收益也会从SY0减少到SY2，虚拟机数量也会从VM0减少到VM2。可见，最大收益的平衡点会随着服务商承接业务数量的多少而动态变化，而相应的云资源调度方案也可以根据动态平衡点的位置来确定，方案的调整方向也可以根据动态平衡点的变化方向来调整。

本文算法的基本思路是，从经济学领域借鉴成本、收益、边际收益、边际成本等概念，不断地考察当前周期和上一周期边际收益的变化，实时捕捉能够达到最大收益的平衡点，并利用这个平衡点位置对应的各个参数，指导实际的云资源调度。

据此，构建基于最大收益平衡点动态变化的云资源调度算法，具体操作步骤如下。

步骤1 为上一时间周期的虚拟机数量、上周期收益、上周期成本、上周期边际成本、上周期边际收益、本周期的虚拟机数量、本周期收益、本周期成本、本周期边际成本、本周期边际收益分别开辟寄存器。

步骤2 启动程序，计算当前周期相对上一周期的负载变化和收益变化。

步骤3 判断此时边际收益和边际成本的关系，如果BJSY＞BJCB，增加虚拟机的数量，重新比较边际收益和边际成本;如果BJSY＜BJCB，减少虚拟机的数量，重新比较边际收益和边际成本。

步骤4 判断边际收益和边际成本的差值，如果差值大于事先设定的阈值T，重复执行步骤3;如果差值小于事先设定的阈值T，认为边际收益和边际成本相等，到达最大收益新的平衡点。

步骤5 将最大收益平衡点位置对应的各个参数，作为指导云资源实际调度的数据。

2 实验结果与分析

为了验证基于最大收益平衡点动态变化的云资源调度算法的有效性，本文通过仿真实验来验证其性能。仿真平台选择了澳大利亚墨尔本大学推出的CloudSim云端仿真器［3］。此仿真平台的特点是不但可以自由设置虚拟机的各种资源配置(如CPU、内存、带宽)，还具备虚拟化引擎和可编程能力。为了便于直观地比较本文方法和其它方法的性能情况，选取了服务水平驱动调度方法(service level agreement，SLA)作为对比方法。在这里，之所以选择SLA方法作为比对方法，是因为SLA方法本身就是协调服务商和用户需求的方法，而本文方法的前提在于保证用户需求得到满足的前提下提高服务商的效益，那么在用户需求得到同等保障的条件下，SLA方法和本文方法哪个能够给服务商提供更大的效益，也就可以说明哪种方法更加合理。

仿真实验设定的实验条件如下。

1)每个云节点含有30个调度节点，这些调度节点的硬件资源配置是CPU的主频为4 GHz，内存大小为4 GB，硬盘大小为2 TB。

2)每个调度节点含有50个虚拟机节点，虚拟机节点的硬件资源配置是CPU的主频为2 GHz，内存大小为1 GB，硬盘大小为500 GB，带宽为100 MHz。

3)要处理的用户需求数据量以模拟北京奥运会举办期间的门户网站的数据量为准(从2008年8月8日到2008年8月24日不断变化)。

4)服务商能够提供的服务类型分为大、中、小3种，分别包括500条指令、1 000条质量、2 000条指令。

5)虚拟机的初始设定为10个，可以根据需求不断进行调整，但上限不能超过调度节点下属的50个节点。

6)虚拟机的收费标准，按照总体收费标准为0.1 MYM，按照CPU 收费标准为0.33 MYM，按照内存大小收费标准为0.33 MYM，按照带宽收费标准为0.33 MYM。

相应的实验参数配置情况如表1所示。

表1 实验参数配置Tab.1 Experimental parameters configuration

按照上述设置，利用北京奥运会举办期间的门户网站的模拟数据量，分别执行服务驱动方法和本文方法的云资源调度方法，实验结果如图2 -图4所示。

图2 2种方法随着负载变化的虚拟机数量变化Fig.2 Number of virtual machines changes as the load in two methods

从图2 -图4的实验结果可以看出以下几点。

1)随着负载数量的动态变化，基于服务驱动的调度方法和本文提出的方法都会动态地调整虚拟机配置的数量，但本文方法所需要的虚拟机数量总是少于服务驱动的调度方法，这说明本文方法可以有效地节省云资源。

2)本文方法的响应时间都比服务驱动的调度方法响应时间快，无论是大型服务、中型服务还是小型服务。

3)随着负载的动态变化，本文方法的收益始终比基于服务驱动的方法收益大，这符合服务商的实际需求。从整个模拟过程来看，本文方法的收益比基于服务驱动的调度方法收益率提高9.81%。

图3 2种方法的3种服务类型的响应时间对比Fig.3 Response time of three types of service of the two methods

图4 2种方法随着负载变化的收益变化Fig.4 Income changes as the load in two methods

3 结束语

为了有效地解决云资源调度问题，本文提出了一种基于最大收益平衡点动态变化的调度方法。这种方法从服务商的角度出发，以节省资源并追求最大收益为调度的优化目的，通过边际成本和边际收益的平衡点随着负载的变化而动态更新当前的调度方案。通过在CloudSim平台下的仿真实验表明，本文方法比基于服务驱动的方法具有更好的性能，本文方法响应时间快、所需虚拟机数量少、所获得的收益大。

［1］孙大为，常桂然，李凤云，等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法［J］.电子学报，2011，8(2):1824-1831.SUN Dawei，CHANG Guiran，LI Fengyun，et al.Optimizing Multi-Dimensional QoS Cloud Resource Scheduling by Immune Clonal with Preference［J］.Acta Electronica Sinica，2011，8(2):1824-1831.

［2］许波，赵超，祝衍军，等.云计算中虚拟机资源调度多目标优化［J］.系统仿真学报，2014，26(3):592-595.XU Bo，ZHAO Chao，ZHU Yanjun，et al.Virtual Machine Resource Scheduling Multi-objective Optimization in Cloud Computing［J］.Journal of System Simulation，2014，26(3):592-595.

［3］CALHEIROS R N，RANJAN R，BELOGLAZOY A，et al.CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Practice and Experience，2011，41(1):23-50.

［4］BELOGLAZOV A，ABAWAJY J，BUYYA R.Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing［J］.Future Generation Computer Systems，2012，28(5):755-768.

［5］张水平，邬海艳.基于元胞自动机遗传算法的云资源调度［J］.计算机工程，2012，38(11):11-13.ZHANG Shuiping，WU Haiyan.Cloud Resource Schedule Based on Cellular Automata Genetic Algorithm［J］.Computer Engineering，2012，38(6):11-13.

［6］刘利祥，张健，赵岩，等.基于区间划分的云资源调度方法［J］.华中科技大学学报:自然科学版，2012，40:170-174.LIU Lixiang，ZHANG Jian，ZHAO yan，et al.The cloud resource scheduling method based on interval differentiate［J］.Journal of huazhong university of science and technology:natural science edition，2012，40(2):170-174.

［7］谭靓亮，曾哲明，王耀华.多态蚁群算法优化的云资源调度策略研究［J］.信息通信，2013，126(4):11-13.TAN Jingliang，CENG Zheming，WANG Yaohua.Polymorphic ant colony algorithm to optimize the cloud resource scheduling strategy research［J］.Journal of information and communications，2013，126(4):11-13.

［8］刘永.云计算环境下虚拟机资源调度策略研究［D］.山东:山东师范大学，2012.LI Yong.Virtual Machine Resource Scheduling Strategy Research in Cloud Computing Environment［D］.Shandong:Shandong Normal University，2012.

［9］ZHANG Weizhe，HE Hui，CHEN Gui，et al.Multiple virtual machines resource scheduling for cloud computing［J］. Applied Mathematics ＆ Information Sciences，2013，7(5):2089-2096.

［10］张伟哲，张宏莉，张迪，等.云计算平台中多虚拟机内存协同优化策略研究［J］.计算机学报，2011，12(15):2265-2277.ZHANG Weizhe，ZHANG Hongli，ZHANG Di，et al.Memory Cooperation Optimization Strategies of Multiple Virtual Machines in Cloud Computing Environment［J］.Chinese Journal of Computers，2011，12(15):2265-2277.

［11］CAMILLO Frederic，CARON Eddy.Resource management architecture for fair scheduling of optional computations［C］//Proceedings 8th International Conference on P2P，Parallel，Grid，Cloud and Internet Computing.Paris.France:IEEE Conference Publications，2013:113-120.

［12］ABU Sharkh Mohamed，QUAD Abdeikader，SHAML A.A resource scheduling model for cloud computing data centers［C］//9th International Wireless Communications and Mobile Computing Conference.Sardinia.Italy:IEEE Conference publications，2013:213-218.

［13］YU Yu，GUO Zhongwen .Sensor data compression based on MapReduce［J］.Journal of China Universities of Posts and Telecom，2014，21(1):60-66.