欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:153 2730 2358
邮箱:910330594@QQ.COM

Q Q:
910330594
网址:http://www.17winner.com
工作时间:
9:00-24:00  

博士论文
当前位置:首页 > 博士论文
基于动态定价组合反向拍卖的云工作流系统资源分配机制
来源:一起赢论文网     日期:2018-01-28     浏览数:422     【 字体:

 计算机集成制造系统 第23卷到云计算环境中的一种应用模式,可以优化运行成本和性能[2]。然而云工作流系统资源分配是 NP难问题,需要考虑系统的总体性能特别是所需费用和完成时间[3]。为了解决云工作流系统的资源分配问题,通常采用传统方法和市场导向法。传统方法采用静态分配方案,需要全局且完整的资源信息,使资源分配无法适应市场变化;市场导向法根据资源带来的价值决定价格,可以激励参与者加 场[4]。拍卖是以市场为导向的资源分配方法,是一种通过竞拍者的投标来确定资源最终 价格的市场交易模式。目前很多学者将拍卖方法应用于云计算资源分配,以及时适应市场变化、提高资源分配效率[5]。目前,在云工作流资源分配中使用拍卖方法时的资源价格固定,或者每次拍卖都是单独的反向拍卖,导致较低的资源利用率和拍卖效率,浪费拍卖的完成时间和费用。为了解决上述问题,本文首先考虑云工作流系统中任务间的关系和云资源的市场特性,基于组合反向拍卖的资源动态分配机制,将不同特性的资源组合在一起,以拍卖的形式分配给云工作流任务,从而使用户能够以低费用获得高质量的服务;其次,引入动态定价策略[3],根据交易情况改变资源价格,使竞争力比较弱的提供商可以通过调整价格来提高竞争力。1 相关工作云环境中的资源分配已成为影响经济效益的重要因素。Gorlach等[7]提出在云环境中动态提供服务的方案,虽然提高了资源分配的水平,但是并没有考虑到市场的交易情况。随后基于市场的云资源分配开始受到大量关注,Shi[8]提出在网格环境下使用基于市场的资源分配模型,其中包括市场交易模型、定价模型、信息传递模型和议价模型等。云工作流系统中,当大量的工作流请求云计算资源服务时,要使资源得到最优利用就必须制定合理有效的资源分配方案。Bessai等[9]使 作业,并采用二进制整型规划解决在不同云提供商中选择资源的问题。Bessai等[10]将一个广义联合放置模型整合到云中,用于负载均衡。Das等[11]对一组具有不同特性的工作流使用静态和动态的资源分配算法,使工作流在指定的时间和成本约束下的完成率最高。计算经济学中的模型已经应用到云工作流系统资源分配中,目前常见的经济模型有商品市场模型、标价模型、议价模型等。文献[12]提出资源分配中基于组合拍卖的定价模型,根据每个提供商的竞拍来确定资源价格。文献[13-14]使用拍卖来解决资源的最优价格问题,并考虑了用户预算和截止时间的限制。关于云计算资源分配即如何为云资源制定最优价格的研究已成为很多学者关注的热点问题。为了找到云市场中资源的最低价格,Kantere等[15]建立了用户需求和价格之间的模型,提出动态定价方案来提高提供商的收益;Xu等[16]也提出基于动态定价的收益管理框架,以最大化云计算资源提供商的收益。在最相关的文献[6]中,Hamid等提出 双目标调度策略(Biobjective Scheduling Strategy,BOSS)机制的反向拍卖为工作流任务分配资源,每个任务通过拍卖获得资源,使任务完成时间和费用最低,但资源的价格在拍卖中是固定的,一些竞争力比较弱的资源提供商几乎没有赢得拍卖的机会,从而导致资源利用率较低。本文主要研究云工作流系统资源分配,提出基于动态定价组合反向拍卖的资源分配机制,不但降低了 作流完 时间、提高了 拍卖效率,而且 利用率。2 基因序列工作流拍卖示例分析下面通过基因序列工作流 Epigenomics分析对比反向拍卖和组合反向拍卖,以及组合反向拍卖中的固定价格和动态定价,并给出拍卖过程和不同拍卖类型的对比。20个任务的 Epigenomics工作流如图1所示。任务的任务量服从 N(1 000 000,1 000)的 正态分布[6]。资源提供商有5个,每个资源提供商有 A,B,C,D,E 5种类型的资源,资源的执行力是从200~1 200的等差数列,其方差是1 000与工作流任务个数之比[6]。资源价格根 据亚马逊 资源价 定(Amazon EC2,http://aws.amazon.com/cn/ec2/pricing/)。由于工作流中的任务之间有偏序关系,子节点的任务只有在父节点的任务完成后才可以执行。若进行固定价格的反向拍卖,则20个任务依次进行单独拍卖即拍卖次数为20,且价格在每一轮都保持不变;若进行固定价格的组合反向拍卖,则兄弟节点可以组合在一起拍卖(如任务2,3,4,5),拍卖次数为17,每轮价格保持不变。动态定价的组合反向拍卖过程如下:首先单独拍卖任务1,可以提供 A492计算机集成制造系统 第23卷个任务的需求信息,n 是一个任务组合中任务的个数。拍卖师将用户提供的需求信息整理成 Bj发送给所有参与拍卖的资源提供商。每个提供商的资源特性不同,主要资源特性包括资源种类、执行的开始时间、资源执行力、单位时间的初始价格与最低价格。单个资源竞标时,提供商将 合,形 Bid(type,time,ablilty,sprice,bprice),其 中:type 是资源的类型,time是资源可以执行的开始时间,ab-lilty 是资源的执行力,sprice是资源在单位时间的初始价格,bprice 是资源 在单 时间的最低价格。当有组合任务的需求时,提供商会根据需求对资源进行整合,形成组合 Bidsj(Bidj1,Bidj2,…,Bidji,…,Bidjn)后进行竞标。其中:Bidsj是第j个组合资源的竞标,Bidji是第j个组合资源中的第i 个资源竞标,n 是当前组合资源中的资源个数。每个组合资源的竞标是对所包括的单个资源的组合。3.3 基于动态定价的组合反向拍卖算法基于动态定价的组合反向拍卖算法的主要思想为:对云工作流的任务按照偏序关系依次进行组合反向拍卖,每一轮拍卖通过评价标准选择出提供商中的赢家后,使用动态定价策略,使参与拍卖的每个提供商在下一轮都有赢得拍卖的机会。算法1 基于动态定价的组合反向拍卖算法。输入:任务 Tasks,资源 Resources。输出:资源分配方案。①以偏序关系将云工作流中n个任务分配到任务列表;②分配提供商所提供的 m 个资源到资源列表;③for i=1to n do④ 从任务列表中筛选出不同的任务类型;⑤ for j=1to m do⑥   根 据 任 务 类 型 在 资 源 列 表 中 找 到 与 其 对 应 的 资 源类型;⑦   拍卖师筛选出可以提供满足这些资源类 型 的 资 源 的提供商;⑧   将云工作流中的任务进行组合反向拍卖;⑨   计算当前拍卖中任务执行的 TC(公式1);⑩   选出 TC最小的提供商作为赢家;瑏瑡   拍卖师将赢家的资源分配给用户;瑏瑢   用户支付赢家;瑏瑣 End瑏瑤 提供商根据动态定价策略改变价格;瑏瑥End瑏瑦输出最优资源分配方案。首先,输入工作流中有n个任务(第1行),提供商有 m 个资源(第2行),筛选出不同任务类型的任务(第3~4行),拍卖师找出与这些任务类型对应的资源类型和 可 以提供这些 资 源 的 提 供 商 (第 5~7行),将工作流中的任务进行组合反向拍卖,使筛选出的提供商参与拍卖(第8行);然后,计算每个资源的完成时间与所需费用之积(第9行),在提供商中选出 TC 最小的作为赢家(第10行),拍卖师将赢家提供的资源分配给用户,用户支付赢家为其提供的资源(第11~12行);最后,所有提供者根据动态定价策略改变价格进行下一轮拍卖(第14行),最终输出工作流资源分配方案(第16行)。4 实验仿真下面首先给出实验环境与算法参数,然后设置不同的任务规模,从任务完成时间和所需成本之积TC、资源利用率 RU 和拍卖次数3方面将本文的拍卖方法和其他方法进行对比。实验采用 Myeclipse编写,运行在环境为Intel core i3 3.0GHz CPU,2GB内存的 PC 机。实验工作流根据基因序列工作流 Epigenomics(https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator)生 成。工作流的任务个数分别设置为20,24,48,且一个工作流中共存在5种类型任务,不同提供商资源的单位时间价格从0.14~0.84,资源降价率为10%[6],其他参数详见第2章。4.1 固定价格时的组合反向拍卖和反向拍卖为了比较组合反向拍卖和反向拍卖的效果,共进行3组实验,设置工作流任务个数分别为20,24,48。每组实验分别使用基于固定价格反向拍卖和组合反向拍卖算法为工作流的执行进行资源分配,然后统计出每组实验的总 TC(即所有任务 TC 之和)和总拍卖次数。如图2所示,组合反向拍卖 TC 值比反向拍卖低,例如当任务数为48时,组合反向拍卖 TC 比反向拍卖降低 68%。这 是由于组 合反向拍卖的工作流中,兄弟节点任务进行组合拍卖可以降低拍卖时间。通常随着任务个数的 增多,TC 值会增大。然而图2中任务个数20和24两个不同工作流的 TC 值相反,这是由工作流结构不同且任务个数相近所致。如图3所示,组合拍卖次数比反向拍卖少。例如当任务个数为48时,组合反向拍卖的拍卖次数比反向拍卖降低19%。这是由于组合反向拍卖中兄弟节点的任务可以组合在一起拍卖,从而降低了拍卖次数。494 李学俊 等:基于动态定价组合反向拍卖的云工作流系统资源分配机制资源的提供商参与拍卖,提供商若输了此轮拍卖,则根据动态定价策略降低自己的资源价格,若赢了此轮拍卖,则下一轮拍卖中其资源价格将保持不变;当任务1拍卖完成后,将任务2,3,4,5组合在一起进行拍卖即组合反向拍卖,同时拥有 B,C,D,E 资源的拍卖商参与拍卖,并在此轮拍卖结束后重复上述定价策略;此后每轮拍卖以此类推。表1给出的基于动态定价的组合反向拍卖不 但简化了拍卖的流程、减少了拍卖次数,而且使提供商都有赢得拍卖的机会,提高了资源利用率。表1 不同拍卖类型对比拍卖类型时间费用/×1013拍卖次数资源利用率/%固定价格反向拍卖 3.69  20  10.00固定价格组合反向拍卖 1.54  17  22.73动态定价组合反向拍卖 0.58  17  62.503 基于动态定价组合反向拍卖的资源分配机制下面首先介绍组合反向拍卖过程中提供商成为赢家的评价标准,然后设计适于云工作流系统的组合反向拍卖模型[3],最后提出基于动态定价组合反向拍卖算法。3.1 评价标准赢家确定是资源分配的核心,目的是设法给用户分配最合适的资源、使得经济效益和资源利用率达到最优。拍卖赢家的确定有完成时间和所需费用之积 TC 以及资源利用率RU 两个评价标准,详见文献[6]。每次拍卖赢家的确定根据任务执行的 TCij进行衡量,以评价拍卖效率和经济效益,如式(1)所示。TCij = (tij+workloadi/abilityj)×(pricej×workloadi/abilityj)。 (1)式中,等号右边由两部分(两个括号)组成,前者是任务i在资源j 上执行的完成时间,后者是任务i在资源j上执行所花费的费用。其中:tij表示任务i 在资源j上执行的开始时间,workloadi表示任务i 的任务量,abilityi表示资源j的执行能力,pricej 表示资源j单位时间的价格,workloadi/abilityj表示任务i在资源j 上执行所花费的时间。RU 体现资源使用的均衡,表示为被分配次数的方差,如式(2)所示。方差越小,资源越均衡,反之越不均衡。RU =1/S,S =∑n1(numj-num)2/n。 (2)式中:S 为 每 个 提 供 商 资 源 被 分 配 次 数 的 方 差,numj 为提供商j 资源被使用的次数,num为所有提供商的资源被使用次数的均值,n为提供商的个数。3.2 组合反向拍卖模型云工作流系统中的资源分配采用组合反向拍卖机制,可以使服务商获得更高的市场效益。本文对文献[14]中的组合拍卖进行改进,设计了适于云工作流系统的组合反向拍卖模型。组合反向拍卖模型中首先要确定用户如何提供需求信息,以及提供商如何根据用户所提出的需求信息出售资源;其次用户需要资源为其执行任务,拍卖师负责接收用户的需求,将用户的需求整理后提供给提供商,并接收提供商的投标;最后根据评价标准(见3.1节)评估每个提供商的资源并选出赢家,将拍卖的结果返回给用户和提供商。用户的需求信息包括每个任务执行的开始时间、每种类型的任务量和任务所需资源类型。首先用户将需求信息提交给拍卖师,拍卖师将信息进行整理并将每个任 务的需 求 信 息形成一 个 三元组 R(st,workload,type)。其 中:st是任务执行 的 开 始时间,workload 是 组 合 中 第i 种 任 务 类 型 的 任 务量,type是任务所需的资源类型。对于进行组合反向拍卖的任务,拍卖师需将所有任务整合成一个元组Bj(Rj1,Rj2,…,Rji,…,Rjn),其中:Bj是第j个任务组合的需求信息,Rji是第j个任务组合中第i49328;修订日期:2016-08-28。Received 28June 2016;accepted 28Aug.2016.基金项目:教育部人文社会科学研究青年基金资助项目(16YJCZH048);国家自然科学基金资助项目(61672034);安徽省教育厅自然科学研究重点资助项目(KJ2016A024)。Foundation items:Project supported by the Youth Fund for Humanities and Social Science of Ministryof Education,China(No.16YJCZH048),the National Natural Science Foundation,China(No.61672034),and the Natural ScienceFoundation of Education Commission of Anhui Province,China(No.KJ2016A024).基于动态定价组合反向拍卖的云工作流系统资源分配机制李学俊,陈 千,刘祥俊,钟云香,徐 佳,朱二周+(安徽大学 计算机科学与技术学院,安徽 合肥 230601)摘 要:为了引入动态定价机制、动态调整资源价格以提高资源提供商的竞争力,将动态定价组合反向拍卖方法引入云工作流资源分配中,设计了适于云工作流系统的组合反向拍卖模型,提出动态定价组合反向拍卖算法。通过基因序列工作流 Epigenomics进行对比实验,结果表明固定价格时组合反向拍卖的时间费用之积和拍卖次数比反向拍卖分别平均降低60%和17%,组合反向拍卖中动态定价的时间费用之积比固定价格平均降低63%,资源利用率平均提高69%。关键词:云计算;云工作流系统;资源分配;动态定价;反向拍卖中图分类号:TP391   文献标识码:ADynamic-pricing combinatorial reverse auction-based resource allocationmechanism in cloud workflow systemLI Xuejun,CHEN Qian,LIU Xiangjun,ZHONG Yunxiang,XU Jia,ZHU Erzhou+(School of Computer Science and Technology,Anhui University,Hefei 230601,China)Abstract:Reverse auction is an effective method for resource allocation of cloud workflow system.But this methodcauses long execution time and low efficiency because it makes auction separately.By combinatorial reverse auctionmechanism,the brother nodes of workflow tasks are combined by combinatorial reverse auction.This brings highauction efficiency.Usually resource price is fixed so that weakly competitive resources providers are hard to sell re-sources and then results in low resource utilization.To introduce the dynamic pricing mechanism and the dynamicpricing strategy for improving providerscompetitive ability,a combinatorial reverse auction model was presented byleading the method of dynamic-pricing combinatorial reverse auction into the resources allocation of cloud workflowsystem,and a dynamic-pricing combinatorial reverse auction algorithm was proposed.Experiments were simulatedon Epigenomics workflows,and the results showed that Time Cost(TC)and auction times of combinatorial reverseauction with fixed pricing were lower than reverse auction by 60% and 17% averagely.The combinatorial reverseauction TC of dynamic pricing was lower than fixed pricing by 63% and resource utilization of dynamic pricing washigher than fixed pricing 69% averagely.Keywords:cloud computing;cloud workflow system;resource allocation;dynamic pricing;reverse auction0 引言云计 算 是 一 种 新 兴 的 大 规 模 分 布 式 计 算 范式[1],其通过虚拟化技术提供资源服务,采用按需付费模式提供无限的计算资源,具有较高的可靠性和较低的成本。云工作流系统是工作流管理系统应用 李学俊 等:基于动态定价组合反向拍卖的云工作流系统资源分配机制4.2 组合反向拍卖的固定价格和动态定价为了比较动态定价和固定价格,共进行3组实验,且工作流的任务个数分别为20,24,48。每组实验分别使用基于固定价格的组合反向拍卖算法和基于动态定价的组合反向拍卖算法,为工作流的执行进行资源分配,然后统计出整个工作流资源分配后的RU 和总TC。动态定价的 TC 比固定价格低,如图4所示。例如当任务个数为24时,动态定价 TC比固定价格降低64%。这是由于组合反向拍卖中使用动态定价,为提高提供商的竞争力降低资源价格,从而 使 整 个 工 作 流 的 所 需 费 用 比 使 用 固 定 价格低。组合反向拍 卖 时 动 态 定 价 的 RU 高 于 固 定 价格,如图5所示。例如当任务个数为20时,动态定价的RU 比固定价格提高63%;当组合反向拍卖使用动态定价时,原本竞争力较弱的提供商可以通过降低价格 获 得 成 功 卖 出 资 源 的 机 会,从 而 提 高 了RU。通过上述实验可以看出,以 TC,RU 和拍卖次数作为评价标准,在相同的条件下,组合反向拍卖优于反向拍卖,动态定价优于固定价格。在工作流的资源分配中,相比于其他拍卖方式,本文提出的基于动态定价的组合反向拍卖工作流执行时拥有更少的完成时间和所需费用以及更高的 RU,从而提高拍卖效率,并使用户获得更优惠的资源。5 结束语本文利用经济学中拍卖的方法对云工作流进行资源分配,考虑资源的互补性、提供商的竞争性和云资源市场的动态性,提出基于动态定价的组合反向拍卖机制。云提供商通过动态调整资源价格提高了竞争力较弱的资源提供商赢得拍卖的几率,从而提高了资源利用率。同时,云工作流系统使用组合反向拍卖将满足要求的兄弟节点任务同时进行拍卖,从而降低了工作流的完成时间和所需费用,提高了拍卖效率。目前在对资源进行评估时只考虑了完成时间和所需费用,未来工作会将更多的资源因素引入评价标准中。另外,实际工作流系统中兄弟节点同时参与拍卖可能导致的拍卖失败、额外开销和价格过高等问题,也都值得深入研究。参考文献:[1] BUYYA R,YEO C,VENUGOPAL S,et al.Cloud compu-ting and emerging IT platforms:vision,hype,and reality fordelivering computing as the 5th utility[J].Future GenerationComputer Systems,2009,25(6):599-616.[2] ZHAO Yong,LI Youfu,TIAN Wenhong,et al.Scientific-workflow-management-as-a-service in the cloud[C]//Proceed-ings of the 2nd International Conference on Cloud and GreenComputing.Washington,D.C.,USA:IEEE,2012:97-104.[3] LI Xuejun,LIU Xiangjun,ZHU Erzhou.An efficient resourceallocation mechanism based on dynamic pricing reverse auctionfor cloud workflow systems[C]//Proceedings of Asia-Pacific495计算机集成制造系统 第23卷Conference on Business Process Management.Berlin,Germa-ny:Springer-Verlag,2015:59-69.[4] HUU T T,MONTAGNAT J.Virtual resources allocation forworkflow-based applications distribution on a cloud infrastruc-ture[C]//Proceedings of the 10th IEEE/ACM InternationalConference on Cluster,Cloud and Grid Computing.Washing-ton,D.C.,USA:IEEE,2010:612-617.[5] LEE C,WANG P,NIYATO D.A real-time group auctionsystem for efficient allocation of cloud Internet applications[J].IEEE Transactions on Services Computing,2015,8(2):251-268.[6] FARD H,PRODAN R,FAHRINGER T.A truthful dynamicworkflow scheduling mechanism for commercial multi-cloudenvironments[J].IEEE Transactions on Parallel and Distribu-ted Systems,2013,24(6):1203-1212.[7] PAPAZOGLOU M,TRAVERSO P,DUSTDAR S,et al.Service-oriented computing:a research roadmap[J].Interna-tional Journal of Cooperative Information Systems,2008,17(2):223-255.[8] SHI Xuelin,ZHAO Ying.Dynamic resource scheduling andworkflow management in cloud computing[C]//Proceedings ofInternational Conference on Web Information Systems Engi-neering.Berlin,Germany:Springer-Verlag,2010:440-448.[9] BESSAI K,YOUCEF S,OULAMARA A,et al.Bi-criteriaworkflow tasks allocation and scheduling in cloud computingenvironments[C]//Proceedings of the 5th International Con-ference on Cloud Computing. Washington, D.C.,USA:IEEE,2012:638-645.[10] BESSAI K,YOUCEF S,OULAMARA A,et al.Bi-criteriastrategies for business processes scheduling in cloud environ-ments with fairness metrics[C]//Proceedings of the 7th In-ternational Conference on Research Challenges in InformationScience.Washington,D.C.,USA:IEEE,2013:1-10.[11] DAS A,ADHIKARY T,RAZZAQUE M,et al.A QoS andprofit aware cloud confederation model for IaaS service pro-viders[C]//Proceedings of the 8th International Conferenceon Ubiquitous Information Management and Communication.New York,N.Y.,USA:ACM,2014:1-7.[12] RAO S,PRASAD A.A combinatorial auction mechanism formultiple resource procurement in cloud computing[C]//Pro-ceedings of the 12th International Conference on IntelligentSystems Design and Applications.Washington,D.C.,USA:IEEE,2012:337-344.[13] TENG F,MAGOULES F.Resource pricing and equilibriumallocation policy in cloud computing[C]//Proceedings of the10th International Conference on Computer and InformationTechnology.Washington,D.C.,USA:IEEE,2010:195-202.[14] MIHAILESCU M,TEO Y.On economic and computational-efficient resource pricing in large distributed systems[C]//Proceedings of the 10th IEEE/ACM International Conferenceon Cluster,Cloud and Grid Computing.Washington,D.C.,USA:IEEE,2010:838-843.[15] KANTERE V,DASH D,FRANCOIS G,et al.Optimalservice pricing for a cloud cache[J].IEEE Transactions onKnowledge and Data Engineering,2011,23(9):1345-1358.[16] XU H,LI B.Maximizing revenue with dynamic cloud pri-cing:the infinite horizon case[C]//Proceedings of IEEE In-ternational Conference on Communications.Washington,D.C.,USA:IEEE,2012:2929-2933.[17] TRUONG-HUU T,THAM C.A game-theoretic model fordynamic pricing and competition among cloud providers[C]//Proceedings of the IEEE/ACM 6th International Conferenceon Utility and Cloud Computing.Washington,D.C.,USA:IEEE,2013:235-238.作者简介:李学俊(1976-),男,安徽金寨人,副教授,博士,研究方向:云计算、智能软件,E-mail:xjli@ahu.edu.cn;陈 千(1991-),男,安徽合肥人,硕士研究生,研究方向:工作流系统;刘祥俊(1990-),男,安徽六安人,硕士研究生,研究方向:云计算、工作流、组合拍卖;钟云香(1990-),女,安徽庐江人,硕士研究生,研究方向:多租户服务选择;徐 佳(1992-),男,上海人,硕士研究生,研究方向:工作流系统; +朱二周(1981-),男,安徽五河人,副教授,博士,研究方向:虚拟化、云计算,通信作者,E-mail:ezzhu@ahu.edu.cn。496

[返回]
上一篇:基于深度信念网络的供应链柔性提升研究
下一篇:基于博弈的业务流程动态任务分配方法