文摘
基于云计算的服务已经越来越多地用于提供按需访问大量的计算请求,如数据、计算、资源等等,至关重要的是要正确地选择和合适的资源分配给一个工作负载或应用程序。提出一种新颖的在线反向拍卖方案基于在线算法分配云计算服务,可以帮助云用户和提供商建立工作流应用程序在云计算环境中。在线逆向拍卖方案包括三个部分:在线算法设计,竞争比例计算,和性能评估。在线反向基于拍卖算法云用户代理的选择最终的赢家基于Vickrey-Clarke-Groves(向量)机制(OA)和在线算法。竞争分析是应用于计算相比,该算法的竞争比离线算法。这种分析方法是重要的测量算法的性能,没有分布的假设云供应商的报价。结果证明该在线反向算法基于拍卖的是适当的机制,因为它允许云用户代理不知道未来投标作出购买决定。拍卖轮和交易成本的差异可以令人印象深刻的影响和提高提出了逆向拍卖算法的性能。
1。介绍
云计算作为一种新的计算模式,近年来迅速出现(1,2],它能够解决大规模问题产生在工业、科学、商业和工程(3]。近年来,有一些著名的商业云平台,如Amazon elastic compute cloud (EC2),微软Azure, Linode,组织一个共享资源池云用户和提供商贸易服务(4,5]。云计算的基本思想是将计算资源,如中央处理单元(CPU)、随机存取存储器(RAM),和存储服务在互联网上。云用户可以购买云计算服务的动态多变的要求。另一方面,云提供商包资源为不同类型的虚拟机和设计定价机制。然而,高度动态、无法控制和分布式网格环境的特点导致云提供商的阻碍云计算服务价格。因此,如何更好地管理云资源成为云计算的重要问题在云提供者和用户之间。
目前,当前文学经常使用固定价格方法和基于拍卖的方法来分配云计算服务。对于这两种方法,固定价格方法本质上是批评为缺乏市场效率和未能迅速适应实时供需关系变化(6]。基于拍卖算法已被证明有更多的优势7,8]。首先,固定价格算法不能反映在云资源市场供需关系的变化。自拍卖是一种灵活的市场机制,这是云资源的首选设计业务。其次,基于拍卖的方法需要全球信息,使交易更容易实现分散式结构(9]。有一系列的文献基于拍卖的算法设计在云资源市场从不同方面,实现一些新的结果10- - - - - -12]。尽管研究人员使用基于拍卖的方法取得了许多好成绩来分配云计算服务,有以下问题。(1)一次基于拍卖的方法是经常进行的,但多个轮拍卖不考虑。(2)云提供商应在完整信息的情况下使用上述基于拍卖的方法,但不是在不完全信息的情况下。例如,一个云提供商将拍卖平台从云用户没有立即回复。然后,云用户必须做出决定之前下一个云提供商的到来。
因此,它是非常重要的发现这本小说定价算法满足云计算服务的交易的性质。因为当前文学的局限性,本文提出了一种在线反向基于拍卖算法分配云计算服务使用在线算法(OA)。(1)构建一个在线反向基于拍卖的算法。基于逆向拍卖理论,云用户服务需求的要求后,云提供商采取价格收购该服务需求。在现实中,云资源分配的交易是在网上设置,云用户做出购买决定的不知道未来投标采取其他云提供商。因此,本文构造一个在线反向基于拍卖的尼森提出的算法通过使用在线算法和Ronen13]。(2)计算的竞争比。戈德堡提出的竞争分析等。14是用来计算的竞争比在线反向基于拍卖的算法的性能。竞争分析的优点是,它不需要任何假设的未来事件的分布。(3)的性能做出评估。计算的竞争比竞争分析是用来测量性能的在线反向基于拍卖算法与最优线下拍卖算法相比。
本文的主要贡献如下。首先,本文介绍了multi-round时间维度到传统的基于拍卖的方法提出一种新颖的在线反向基于拍卖算法分配云计算服务。第二,在线反向基于拍卖的算法可以帮助云用户做出购买决定,他没有对未来信息序列的云提供商。第三,拍卖服务的交易成本引入在线反向基于拍卖算法,云用户收取费用的代理拍卖服务。大量模拟实验表明,该在线反向基于拍卖的算法是有效的在云服务利用率和更好的性能在用户效用。轮拍卖和交易成本发挥重要作用的云用户代理的决定。拍卖效率可以从这两个因素得到改善。
本文组织如下。部分2介绍了相关的工作。第三节描述了反向拍卖市场。第四节介绍了小说在线反向基于拍卖的算法。第五节解释了交易策略和竞争分析。第六节介绍了模拟和总结了实验结果。结论给出了第七节。
2。相关工作
基于拍卖的算法已经应用于各个领域,如网格计算、无线网络和云计算。目的是为了分析用户和提供者如何在竞争激烈的环境。研究表明,不同类型的拍卖被认为是在算法的设计。拍卖设计的一个重要成就Vickrey-Clarke-Groves(向量)机制,这是一个通用的方法,来真实的在拍卖市场机制的建设。一切合理的近似或启发式组合拍卖VCG-based机制和有真实的特性,适用于各种类的成本最小化问题(13]。本质上的结果表明,唯一真实的拍卖算法是有效的。因此,云计算服务市场,基于拍卖的算法也是真实的如果一个云用户和云提供商没有谎报私人信息的动机。当前研究设计了一些基于拍卖算法分配云资源。最受欢迎的英式拍卖拍卖形式,组合拍卖,拍卖的两倍。例如,藤原et al。15)提出了一种组合拍卖设计云计算服务的市场机制。拍卖算法提出帮助云用户构建工作流应用程序在云计算环境中,云用户的需要组合多种类型的服务在不同的时间,每天播发或者刊登王等人。16)研究云计算服务的英语基于拍卖的算法。他们提出了一个拍卖的云计算框架。不同的设计基于拍卖的算法进行了讨论。扎曼和Grosu17)提出了两个拍卖方案为云用户分配虚拟机。他们认为,组合基于拍卖算法比固定价格更高效的算法。原因是虚拟机分配给云用户的最高估价。康等。11)提出了多部件维克瑞拍卖和片面VCG-combinatorial拍卖处理云服务分配。他们证明了这两种基于拍卖的算法是有效的方法。李等人。18)之间的谈判协议提出了一种新的实例化云用户和云提供商使用连续双向拍卖模型。他们分析和显示不同的调度策略,可以应用到真正的云资源交易。一些研究复式拍卖形式引入组合拍卖设计。例如,Tafsiri和Yousefi [12]研究了组合双基于拍卖算法,供应商的代理执行分配的虚拟机根据用户的请求的云计算。事实上,在上面的拍卖机制云提供商出售云资源和云用户将报价做出购买的决定,也就是拍卖。
近年来,一种新的拍卖模式,也就是说,反向拍卖,吸引了更多的关注。反向拍卖模型具有很高的云计算的潜力。它有别于传统的拍卖形式,云用户拍卖人,云提供商是投标人。即在反向拍卖模型中,云提供商提交投标。云用户评估的投标拍卖规则和确定最后的赢家。Roovers et al。19]研究了反向拍卖市场的设计。他们指出,反向拍卖的灵活性和能力模型和集成目前部署的价格体系的现实世界。Prodan et al。20.]扩展连续双向拍卖问题,引入了一个连续的反向拍卖,搭配了一个新颖的基于标签的投标语言和约束集。普拉萨德,饶21)使用反向拍卖设计一个云资源采购方法和显示三种可能的反向拍卖算法云资源采购。
然而,上述基于拍卖算法设计被认为是在离线情况下后宣布最终的赢家是收集所有投标。事实上,云服务提供商和用户经常做决定下不完整的信息(22]。例如,不同的云供应商在不同的时间到达和云用户需要决定是否接受每个投标报价收到,因为它不知道未来。最初是在1999年,一个在线拍卖算法提出解决这种动态网格或云资源分配问题,和作者使用了竞争分析计算竞争比例来衡量性能的在线拍卖算法(14]。竞争分析已经得到了很多认可领域的金融、经济学、和操作研究。它有别于传统的平均情况分析,侧重于假设的未来事件的分布根据一些已知的概率和试图实现平均情况性能好。许多研究人员扩展戈德堡从以下方面的工作。Hajiaghayi et al。23)被认为是一个在线的真相告诉机制基于离线魏克里模型。供应有限的商品,Lavi和尼森24)提供了一个激励兼容的在线拍卖和证明了这个拍卖有一个最优竞争力比关于收入和总社会效益。朱et al。25]研究了反向在线拍卖问题,网上基于多属性逆向拍卖算法的投标设计,取得了更好的性能。
近年来,一些研究开始设计在线拍卖算法分配的云计算服务。例如,Zhang et al。26]的框架进行真实的网上拍卖与异构云用户的需求可能会离开。他们设计了一种新颖的投标语言,云用户的异构要求被广义监管和保持一致的形式。基于这种投标语言,他们提出了一个激励兼容的在线云拍卖算法,得到了一些新的结果。施等。6)首次在线组合拍卖算法对云计算的问题。相同的结果显示,拍卖系统足够表达优化系统效率在时间域而不是在一个孤立的时间点。丁等。7]介绍了在线拍卖在网格计算资源调度网络和在线基于拍卖的算法设计。他们提出了一种新的多属性multi-round反向拍卖,准备资源用户满意度引入传统的网格资源分配问题帮助网格资源代理多属性决策下不完整的信息。
3所示。反向拍卖市场的描述
有一个反向拍卖市场,维护请求和从云用户和提供商收集投标,分别。从云的云用户代理接收到指令后用户,它计算何时以及如何分配资金购买云的云计算服务提供商。图1是反向拍卖方案的流程图,显示了参与者在市场工作。云用户提交的请求和私人信息云用户代理(标签1)。在反向拍卖市场,云用户代理搜索云提供商,以满足用户的请求,并邀请他们参与拍卖(标签2)。在云供应商报价在一个在线的方式(标签5),云用户代理报告并向用户宣布拍卖的赢家或输家(标签3)。一旦收取和支付完成(标签4),云用户和提供商建立连接和标签(6)完成交易。
在反向拍卖市场,云用户和供应商有不同的目标,策略和供需模式。这些参与者在以下简短的解释。
3.1。云用户
在反向拍卖市场,云用户的任务提交需求受到预算,价格优惠,和他的经纪人内存大小。它认为,云用户的预算 ,这意味着云用户的总资金购买云服务。用一个三个数组,每个服务 ,在哪里服务的期限,代表秘密保留价格,是最小的内存大小。云用户的目标是在总资金最大化效用在他相应的最后期限。
3.2。云用户的代理
每个云用户云用户代理或代理。在拍卖过程中,云用户代理代表了云用户宣布云资源请求。他的工作取决于用户的请求搜索云提供商可以满足用户的需求,然后邀请投标的云提供商。在游戏结束时,他选择拍卖的获胜者代表云用户。事实上,云用户代理可以被视为反向拍卖的拍卖市场。不同于上面的文献中,我们假设有交易成本当交易云资源。而不是一个圆,本文假设n轮的过期时间 。在每一轮 ,资金的分配数量的云用户用( )。,有一个固定的交易成本用云用户支付的代理。
3.3。云提供商
在反向拍卖市场,云提供商的工作是决定是否参与拍卖当收到的邀请用户代理根据自己的能力。如果他接受了这一邀请,然后他需要报价。它认为,一个云提供商提交一个定义 ,在哪里云计算和内存大小的吗提供者的估值为投标价格,这表明是可以接受的最高价格提供者提供请求的实例。 是一个云提供商的期间的时间长度想要预定一个起始时间之间的报价和结束时间 。在这里,云提供商到达不同的时间序列,这称为在线方式。
4所示。小说在线反向基于拍卖的算法
本文研究了在线预订在线拍卖问题设置。在每一轮中,面临着历史报价和当前的信息有限,云用户代理必须做出的决定不知道未来投标(16),或投标的分布函数(17]。本文旨在设计一种新型在线反向基于拍卖算法的云用户代理,进行指导云资源分配的云计算服务市场。我们使用的竞争分析来评估性能在线反向基于拍卖的算法。
定义1。在线储备拍卖定义如下:(1)在每一轮中,云提供商到来,宣布他的想法 ,其中每个是一个实数区间的 。(2)云用户代理决定购买云的云计算服务提供商如果是这样,价格和数量在打开下一个报价。(3)游戏结束时最后一个云提供商宣布竞选期间 。
定义2。在线反向基于拍卖算法的竞争比的定义如下:(1)让是用离线算法的最优效益对于任何报价序列 。(2)让在网上生成的好处用反向基于拍卖的算法对于任何报价序列 。(3)竞争比的在线反向计算基于拍卖的算法 。
定义3。在线反向的竞争分析基于拍卖的算法定义如下。它说一个在线反向基于拍卖的算法
- - - - - -如果ALG满足的利益竞争
。
在这个定义中,是在线反向的竞争比基于拍卖的算法ALG。也就是说,下确界被称为在线反向基于拍卖算法的竞争比吗ALG。另一方面,一个在线反向基于拍卖算法被认为是最好的,如果不存在另一个在线算法严格较小的竞争比。接近1的竞争比,越有利于在线反向基于拍卖的算法ALG可以获得。
接下来,我们设计一种新颖的在线反向基于拍卖算法,扩展了功名Lavi和尼森提出的算法16通过考虑到交易成本)。尽管本文认为在线反向基于拍卖算法作为向量机制,它不同于研究Lavi和尼森(16研究提出拍卖),相对于扭转在线拍卖。在网上储备拍卖市场的云计算服务,云用户代理必须考虑风险假设收购序列最高价格将会增加。因此,拟议的在线反向基于拍卖算法帮助云用户代理储备足够的资金来确保竞争的比率
,尽管出价序列呆在一个更高的价格。特别,即使云用户代理遇到最坏的情况下,购买服务的最高价格拍卖结束比赛,竞争比例不超过
。
小说在线反向基于拍卖算法如下。
让SP和规划的分别表示首选的设置和不投标。我们设计一种新颖的在线反向算法基于拍卖的云用户代理更新他的决定。鉴于
,
,
,和一个新的报价
,云用户代理作出决定按照下列规则:步骤1。集
和
。步骤2。在圆形的
,一个云提供商来呈现他的报价,也就是说,
。步骤3。在年底前t,云用户代理决定是否接受报价。如果投标值达到一个新的低,也就是说,
,和云满足的内存大小
,云用户代理的地方设置的接受报价SP,进入步骤4。否则,将拒绝在集合规划的步骤7。步骤4。云用户代理使用这样一个规则来分配云用户的原始基金,花更少的钱买服务的竞争比为常数
。也就是说,计算出交易的基金基于以下规则:
步骤5。通知获奖云提供商SP的交易价格和数量之间的时间间隔
。步骤6。集
。转到第2步。如果
,步骤7。步骤7。停止。获胜的云供应商报价SP。如果有剩余资金,那么云用户代理购买的工作或服务的最高价格
。即使在这种糟糕的情况下,竞争比例不超过
。
5。竞争分析的在线反向基于拍卖的算法
在本节中,竞争分析是用来评估在线反向基于拍卖的算法的性能。我们将在线反向基于拍卖的算法分为两种情况如下。一个是云用户代理对他的拍卖服务收取费用。另一个是云用户代理拍卖服务是免费的。
5.1。案例1:云用户代理收取费用
如果云用户代理知道所有的序列,离线最优效益可以通过离线最优算法。根据定义2,在圆 ,离线最优效益 。在线反向基于拍卖的算法 ,在哪里是交易基金。因此,竞争比用的在线反向基于拍卖的算法可以计算如下:
为了解决最优竞争比 ,我们假设剩下的基金所拥有的云用户代理后,圆的 。累计数量的云计算服务购买的云用户代理之前是 。如果 ,然后服务的总数量 。与此同时,它是显示 的范围 。在第四节,在线反向基于拍卖算法只意味着我们交易发生在新报价低于前一个。因此,它假设一些报价序列继续下滑的下界直到回合 ,然后剩下的序列的上界 。即序列 和 。为简单起见,假设 , ,和 。因此,云用户代理已经遇到这样一个糟糕的情况下,序列 和 。
基于(2),竞争比例也可以翻译成另一种形式如下:
从方程(3),我们得到
这意味着在圆的云计算服务的累积量剩下的资金有一个线性关系。因此,我们可以服务的累积量的公式分解为以下形式:
函数对剩下的基金也可分为新形式:
根据方程(3),竞争比例也可以描述如下:
用方程(5)和(6)方程(7),我们解决方程(7)在达到交易的基金 :
采取 在方程(8),我们实现这一点
当 ,云用户代理作出决定第一次报价的基础上利用方程(9);我们可以得到,
在线反向基于拍卖的算法的竞争比案例1。
当云用户代理选择在线反向基于拍卖算法来分配资金,对手将坏的序列,使他在一个坏的情况下。例如,对于任何( ),如果累计交易数量 ,然后最好的云用户代理的是花在年底前所有基金购买服务 。因此,用(8)和(10) ,我们获得 在哪里 。
求解方程(11),我们有
自 和 ,我们优化 得到最优在线反向基于拍卖算法的竞争比。对方程(12),困难是解决累积的总和。接下来,我们解决这两个累积金额和简化。因此,我们有
因为累积求和公式大于累计乘法公式相同的序列 ,也就是说, ,我们有以下关系:
我们取一阶推导(14)对,发现
因此,累积求和公式可以描述如下:
对于其他累积求和公式 ,我们有
自 ,我们设置 和获得
因此,我们得到
用(16)和(20.)(12),新的竞争比例公式是最大化的功能 如下:
的推导 关于 ,我们得到了 。因此,它是显示 会的越来越多 。他们之间有一个积极的关系。因此,虽然 和 ,的竞争比 是最大化。因为方程的复杂性(21),我们不更换 与 。竞争比的简单函数可以描述的功能 , , , , 。
从方程(22),结果表明,第一个报价是非常重要的。如果它是低于 ,然后云用户代理不做任何交易,在线反向基于拍卖的算法。因此,投标应该多 。如果我们想要得到最优竞争比,第一个报价应基于方程(22)。在线反向基于拍卖算法提出了一个想法,对手想看最严重的出价序列使云用户代理是最糟糕的情况。然后,我们平均思想引入到在线反向基于拍卖的算法来帮助云用户代理在最坏的情况下降低风险。假设云用户代理将总资金投入 ;也就是说, 。因此,我们有
求解方程(23),我们获得
5.2。案例2:云用户代理是免费的
对于这种情况,云用户代理是免费拍卖和帮助云用户选择合适的云服务价格。根据敌人的论点,我们表明,在线反向基于拍卖算法没有交易成本可以达到一个更小的竞争比。
在这种情况下,这意味着 。因此,我们可以实现交易基金案例1的类似的推导时,竞争比例 。也就是说,
当 ,云用户代理可以决定交易基金第一次报价的基础上 ,与方程(10);我们有
在线反向基于拍卖的算法的竞争比第二种情况。
在这种情况下,云用户代理使用相同的规则在线反向算法基于拍卖的价格云服务。用(25)和(26) ,对于任何( )我们获得
集 。然后,我们得到
比较方程(11)和方程(28),这表明,方程(28)是方程的特殊情况(11)当 。因此,我们简化了求解过程的在线反向基于拍卖算法的竞争比没有交易成本。基于方程(22),在线反向基于拍卖算法的竞争比没有交易成本是通过以下方程:
在第一轮的对手礼物云用户代理。如果云用户代理花不到 基金的出价,那么对手结束比赛。然后,云用户代理可能会遇到损失。即,云用户代理必须用他剩余的资金购买云计算服务的最高价格。因此,云计算用户代理也可以使用平均策略保证的竞争比 。替换 在方程(26),我们有
的竞争分析这两种情况下,重点是讨论交易成本如何影响性能的在线反向基于拍卖的算法。基于方程(22)和(29日),我们可以比较他们发现较小的竞争比。同时,关于竞争力的灵敏度分析比率在这两种情况下提出了第六节。
6。仿真和实验结果
在本节中,我们提供了一些实验结果的竞争率达到在线反向基于拍卖算法讨论了两种情况。为简单起见,我们假设竞争比和 ,分别免费和收费情况。考虑图2。显然,当我们设置 , , ,和 ,的竞争率和都是减少的增加 ,这意味着这些在线反向基于拍卖算法总是明显优于其他算法。注意,在线反向基于拍卖算法的竞争比收费情况比免费的情况。原因在于交易成本增加了云用户负担,降低其效用。一般来说,不难证明的竞争比的极限和免费和收费案件都是1.55。
图3显示在线反向基于拍卖算法使云用户管理基金,利用交易成本来实现更好的性能。在图3曲线显示的竞争比严格小于1.52。在线反向的性能曲线,基于拍卖的算法表达行为的竞争比,下界作为独立,和竞争率作为因变量。在这些轴,性能曲线的斜率向下,代表消极的下界和竞争率之间的关系。
从图3,我们发现增加将导致性能下降的在线拍卖轮反向基于拍卖的算法。具体来说,我们比较在线反向基于拍卖的不同算法的性能 。可以看出,当 , ,和 ,拍卖是15,50岁,到100年,在线反向基于拍卖算法的竞争比从1.52降低到1.48。在自然界中,拍卖轮增加云提供商之间的竞争。但是,它是低效率的云用户做出决定时,他在一个不完整的环境。
图4显示了结果的在线反向基于拍卖的算法的性能 。它发现,竞争比例函数是由交易成本。也就是说,有一个负面的竞争比和交易成本之间的关系。当从0.1到0.3,增加了交易成本的竞争比逐渐减少从1.75到1.5。许多研究不考虑交易成本。这通常是与事实相反。然而,这种成本会抵消相应的拍卖交易中获益。因此,有必要引入交易成本为云计算服务拍卖系统的设计,适合所有的参与者在拍卖市场。
我们模拟的过程在线反向基于拍卖算法(见图5),然后显示云用户代理的区别与不同的交易成本的决定。如果云用户代理已经知道所有投标序列,他可以让一个离线最优策略和获得最大的收益。然而,以在线的方式,对未来云计算用户代理不知道云供应商的报价。我们目前在线反向基于拍卖算法帮助云用户代理购买服务。即云用户代理选择获胜的云提供商根据在线反向基于拍卖算法,而投标人的报价符合要求的在线反向基于拍卖的算法。在图5绿色,蓝色的酒吧,酒吧,酒吧和棕色代表交易基金,分别 , ,和 。结果表明,当 ,交易基金中最高的 。这符合风险的想法。因为对手会让云用户代理在坏的情况下,云用户代理将购买更多的服务当第一个满足交易规则的基础上 - - - - - -威胁的基础算法。此外,相比之下,丁等。7),结果是更有益的和有意义的考虑到交易成本和交易价格。
7所示。结论
本文提出了一种新颖的在线反向拍卖方法分配云计算服务,可以帮助云用户和提供商建立工作流应用程序在云计算环境中。提出在线反向基于拍卖算法评估从自由竞争分析案例和收费情况。结果证明该反向拍卖算法是一个适当的机制,因为它允许云用户代理不知道未来投标作出购买决定。拍卖轮和交易成本的差异可以令人印象深刻的影响和提高提出了逆向拍卖算法的性能。在未来,除了云服务的价格,其他一些因素,例如,云服务和云服务质量效率,可以引入到反对拍卖市场。
数据可用性
所有的数据、模型和代码生成或使用在研究出现在提交文章。
的利益冲突
作者宣称没有利益冲突。
确认
这项研究得到了青岛社会科学项目(没有。QDSKL1801169)。