计算机集成制造系统 第２３卷到云计算环境中的一种应用模式，可以优化运行成本和性能［２］。然而云工作流系统资源分配是 ＮＰ难问题，需要考虑系统的总体性能特别是所需费用和完成时间［３］。为了解决云工作流系统的资源分配问题，通常采用传统方法和市场导向法。传统方法采用静态分配方案，需要全局且完整的资源信息，使资源分配无法适应市场变化；市场导向法根据资源带来的价值决定价格，可以激励参与者加 入 市 场［４］。拍卖是以市场为导向的资源分配方法，是一种通过竞拍者的投标来确定资源最终 价格的市场交易模式。目前很多学者将拍卖方法应用于云计算资源分配，以及时适应市场变化、提高资源分配效率［５］。目前，在云工作流资源分配中使用拍卖方法时的资源价格固定，或者每次拍卖都是单独的反向拍卖，导致较低的资源利用率和拍卖效率，浪费拍卖的完成时间和费用。为了解决上述问题，本文首先考虑云工作流系统中任务间的关系和云资源的市场特性，基于组合反向拍卖的资源动态分配机制，将不同特性的资源组合在一起，以拍卖的形式分配给云工作流任务，从而使用户能够以低费用获得高质量的服务；其次，引入动态定价策略［３］，根据交易情况改变资源价格，使竞争力比较弱的提供商可以通过调整价格来提高竞争力。１　相关工作云环境中的资源分配已成为影响经济效益的重要因素。Ｇｏｒｌａｃｈ等［７］提出在云环境中动态提供服务的方案，虽然提高了资源分配的水平，但是并没有考虑到市场的交易情况。随后基于市场的云资源分配开始受到大量关注，Ｓｈｉ［８］提出在网格环境下使用基于市场的资源分配模型，其中包括市场交易模型、定价模型、信息传递模型和议价模型等。云工作流系统中，当大量的工作流请求云计算资源服务时，要使资源得到最优利用就必须制定合理有效的资源分配方案。Ｂｅｓｓａｉ等［９］使 用 粒 子 群 优 化 算 法 进 行 作业，并采用二进制整型规划解决在不同云提供商中选择资源的问题。Ｂｅｓｓａｉ等［１０］将一个广义联合放置模型整合到云中，用于负载均衡。Ｄａｓ等［１１］对一组具有不同特性的工作流使用静态和动态的资源分配算法，使工作流在指定的时间和成本约束下的完成率最高。计算经济学中的模型已经应用到云工作流系统资源分配中，目前常见的经济模型有商品市场模型、标价模型、议价模型等。文献［１２］提出资源分配中基于组合拍卖的定价模型，根据每个提供商的竞拍来确定资源价格。文献［１３－１４］使用拍卖来解决资源的最优价格问题，并考虑了用户预算和截止时间的限制。关于云计算资源分配即如何为云资源制定最优价格的研究已成为很多学者关注的热点问题。为了找到云市场中资源的最低价格，Ｋａｎｔｅｒｅ等［１５］建立了用户需求和价格之间的模型，提出动态定价方案来提高提供商的收益；Ｘｕ等［１６］也提出基于动态定价的收益管理框架，以最大化云计算资源提供商的收益。在最相关的文献［６］中，Ｈａｍｉｄ等提出 双目标调度策略（Ｂｉｏｂｊｅｃｔｉｖｅ　Ｓｃｈｅｄｕｌｉｎｇ　Ｓｔｒａｔｅｇｙ，ＢＯＳＳ）机制的反向拍卖为工作流任务分配资源，每个任务通过拍卖获得资源，使任务完成时间和费用最低，但资源的价格在拍卖中是固定的，一些竞争力比较弱的资源提供商几乎没有赢得拍卖的机会，从而导致资源利用率较低。本文主要研究云工作流系统资源分配，提出基于动态定价组合反向拍卖的资源分配机制，不但降低了 工 作流完 成 时间、提高了 拍卖效率，而且 通 过 资 源 价 格 的 动 态 调 整 提 高 了 资 源 利用率。２　基因序列工作流拍卖示例分析下面通过基因序列工作流 Ｅｐｉｇｅｎｏｍｉｃｓ分析对比反向拍卖和组合反向拍卖，以及组合反向拍卖中的固定价格和动态定价，并给出拍卖过程和不同拍卖类型的对比。２０个任务的 Ｅｐｉｇｅｎｏｍｉｃｓ工作流如图１所示。任务的任务量服从 Ｎ（１　０００　０００，１　０００）的 正态分布［６］。资源提供商有５个，每个资源提供商有 Ａ，Ｂ，Ｃ，Ｄ，Ｅ　５种类型的资源，资源的执行力是从２００～１　２００的等差数列，其方差是１　０００与工作流任务个数之比［６］。资源价格根 据亚马逊 云 资源价 格 设 定（Ａｍａｚｏｎ　ＥＣ２，ｈｔｔｐ：／／ａｗｓ．ａｍａｚｏｎ．ｃｏｍ／ｃｎ／ｅｃ２／ｐｒｉｃｉｎｇ／）。由于工作流中的任务之间有偏序关系，子节点的任务只有在父节点的任务完成后才可以执行。若进行固定价格的反向拍卖，则２０个任务依次进行单独拍卖即拍卖次数为２０，且价格在每一轮都保持不变；若进行固定价格的组合反向拍卖，则兄弟节点可以组合在一起拍卖（如任务２，３，４，５），拍卖次数为１７，每轮价格保持不变。动态定价的组合反向拍卖过程如下：首先单独拍卖任务１，可以提供 Ａ４９２计算机集成制造系统 第２３卷个任务的需求信息，ｎ 是一个任务组合中任务的个数。拍卖师将用户提供的需求信息整理成 Ｂｊ发送给所有参与拍卖的资源提供商。每个提供商的资源特性不同，主要资源特性包括资源种类、执行的开始时间、资源执行力、单位时间的初始价格与最低价格。单个资源竞标时，提供商将 资 源 特 性 进 行 整 合，形 成 一 个 五 元 组 Ｂｉｄ（ｔｙｐｅ，ｔｉｍｅ，ａｂｌｉｌｔｙ，ｓｐｒｉｃｅ，ｂｐｒｉｃｅ），其 中：ｔｙｐｅ 是资源的类型，ｔｉｍｅ是资源可以执行的开始时间，ａｂ－ｌｉｌｔｙ 是资源的执行力，ｓｐｒｉｃｅ是资源在单位时间的初始价格，ｂｐｒｉｃｅ 是资源 在单 位 时间的最低价格。当有组合任务的需求时，提供商会根据需求对资源进行整合，形成组合 Ｂｉｄｓｊ（Ｂｉｄｊ１，Ｂｉｄｊ２，…，Ｂｉｄｊｉ，…，Ｂｉｄｊｎ）后进行竞标。其中：Ｂｉｄｓｊ是第ｊ个组合资源的竞标，Ｂｉｄｊｉ是第ｊ个组合资源中的第ｉ 个资源竞标，ｎ 是当前组合资源中的资源个数。每个组合资源的竞标是对所包括的单个资源的组合。３．３　基于动态定价的组合反向拍卖算法基于动态定价的组合反向拍卖算法的主要思想为：对云工作流的任务按照偏序关系依次进行组合反向拍卖，每一轮拍卖通过评价标准选择出提供商中的赢家后，使用动态定价策略，使参与拍卖的每个提供商在下一轮都有赢得拍卖的机会。算法１　基于动态定价的组合反向拍卖算法。输入：任务 Ｔａｓｋｓ，资源 Ｒｅｓｏｕｒｃｅｓ。输出：资源分配方案。①以偏序关系将云工作流中ｎ个任务分配到任务列表；②分配提供商所提供的 ｍ 个资源到资源列表；③ｆｏｒ　ｉ＝１ｔｏ　ｎ　ｄｏ④　从任务列表中筛选出不同的任务类型；⑤　ｆｏｒ　ｊ＝１ｔｏ　ｍ　ｄｏ⑥　　　根 据 任 务 类 型 在 资 源 列 表 中 找 到 与 其 对 应 的 资 源类型；⑦　　　拍卖师筛选出可以提供满足这些资源类 型 的 资 源 的提供商；⑧　　　将云工作流中的任务进行组合反向拍卖；⑨　　　计算当前拍卖中任务执行的 ＴＣ（公式１）；⑩　　　选出 ＴＣ最小的提供商作为赢家；瑏瑡　　　拍卖师将赢家的资源分配给用户；瑏瑢　　　用户支付赢家；瑏瑣　Ｅｎｄ瑏瑤　提供商根据动态定价策略改变价格；瑏瑥Ｅｎｄ瑏瑦输出最优资源分配方案。首先，输入工作流中有ｎ个任务（第１行），提供商有 ｍ 个资源（第２行），筛选出不同任务类型的任务（第３～４行），拍卖师找出与这些任务类型对应的资源类型和 可 以提供这些 资 源 的 提 供 商 （第 ５～７行），将工作流中的任务进行组合反向拍卖，使筛选出的提供商参与拍卖（第８行）；然后，计算每个资源的完成时间与所需费用之积（第９行），在提供商中选出 ＴＣ 最小的作为赢家（第１０行），拍卖师将赢家提供的资源分配给用户，用户支付赢家为其提供的资源（第１１～１２行）；最后，所有提供者根据动态定价策略改变价格进行下一轮拍卖（第１４行），最终输出工作流资源分配方案（第１６行）。４　实验仿真下面首先给出实验环境与算法参数，然后设置不同的任务规模，从任务完成时间和所需成本之积ＴＣ、资源利用率 ＲＵ 和拍卖次数３方面将本文的拍卖方法和其他方法进行对比。实验采用 Ｍｙｅｃｌｉｐｓｅ编写，运行在环境为Ｉｎｔｅｌ　ｃｏｒｅ　ｉ３　３．０ＧＨｚ　ＣＰＵ，２ＧＢ内存的 ＰＣ 机。实验工作流根据基因序列工作流 Ｅｐｉｇｅｎｏｍｉｃｓ（ｈｔｔｐｓ：／／ｃｏｎｆｌｕｅｎｃｅ．ｐｅｇａｓｕｓ．ｉｓｉ．ｅｄｕ／ｄｉｓｐｌａｙ／ｐｅｇａｓｕｓ／ＷｏｒｋｆｌｏｗＧｅｎｅｒａｔｏｒ）生 成。工作流的任务个数分别设置为２０，２４，４８，且一个工作流中共存在５种类型任务，不同提供商资源的单位时间价格从０．１４～０．８４，资源降价率为１０％［６］，其他参数详见第２章。４．１　固定价格时的组合反向拍卖和反向拍卖为了比较组合反向拍卖和反向拍卖的效果，共进行３组实验，设置工作流任务个数分别为２０，２４，４８。每组实验分别使用基于固定价格反向拍卖和组合反向拍卖算法为工作流的执行进行资源分配，然后统计出每组实验的总 ＴＣ（即所有任务 ＴＣ 之和）和总拍卖次数。如图２所示，组合反向拍卖 ＴＣ 值比反向拍卖低，例如当任务数为４８时，组合反向拍卖 ＴＣ 比反向拍卖降低 ６８％。这 是由于组 合反向拍卖的工作流中，兄弟节点任务进行组合拍卖可以降低拍卖时间。通常随着任务个数的 增多，ＴＣ 值会增大。然而图２中任务个数２０和２４两个不同工作流的 ＴＣ 值相反，这是由工作流结构不同且任务个数相近所致。如图３所示，组合拍卖次数比反向拍卖少。例如当任务个数为４８时，组合反向拍卖的拍卖次数比反向拍卖降低１９％。这是由于组合反向拍卖中兄弟节点的任务可以组合在一起拍卖，从而降低了拍卖次数。４９４ 李学俊 等：基于动态定价组合反向拍卖的云工作流系统资源分配机制资源的提供商参与拍卖，提供商若输了此轮拍卖，则根据动态定价策略降低自己的资源价格，若赢了此轮拍卖，则下一轮拍卖中其资源价格将保持不变；当任务１拍卖完成后，将任务２，３，４，５组合在一起进行拍卖即组合反向拍卖，同时拥有 Ｂ，Ｃ，Ｄ，Ｅ 资源的拍卖商参与拍卖，并在此轮拍卖结束后重复上述定价策略；此后每轮拍卖以此类推。表１给出的基于动态定价的组合反向拍卖不 但简化了拍卖的流程、减少了拍卖次数，而且使提供商都有赢得拍卖的机会，提高了资源利用率。表１　不同拍卖类型对比拍卖类型时间费用／×１０１３拍卖次数资源利用率／％固定价格反向拍卖 ３．６９　 ２０　 １０．００固定价格组合反向拍卖 １．５４　 １７　 ２２．７３动态定价组合反向拍卖 ０．５８　 １７　 ６２．５０３　基于动态定价组合反向拍卖的资源分配机制下面首先介绍组合反向拍卖过程中提供商成为赢家的评价标准，然后设计适于云工作流系统的组合反向拍卖模型［３］，最后提出基于动态定价组合反向拍卖算法。３．１　评价标准赢家确定是资源分配的核心，目的是设法给用户分配最合适的资源、使得经济效益和资源利用率达到最优。拍卖赢家的确定有完成时间和所需费用之积 ＴＣ 以及资源利用率ＲＵ 两个评价标准，详见文献［６］。每次拍卖赢家的确定根据任务执行的 ＴＣｉｊ进行衡量，以评价拍卖效率和经济效益，如式（１）所示。ＴＣｉｊ ＝ （ｔｉｊ＋ｗｏｒｋｌｏａｄｉ／ａｂｉｌｉｔｙｊ）×（ｐｒｉｃｅｊ×ｗｏｒｋｌｏａｄｉ／ａｂｉｌｉｔｙｊ）。 （１）式中，等号右边由两部分（两个括号）组成，前者是任务ｉ在资源ｊ 上执行的完成时间，后者是任务ｉ在资源ｊ上执行所花费的费用。其中：ｔｉｊ表示任务ｉ 在资源ｊ上执行的开始时间，ｗｏｒｋｌｏａｄｉ表示任务ｉ 的任务量，ａｂｉｌｉｔｙｉ表示资源ｊ的执行能力，ｐｒｉｃｅｊ 表示资源ｊ单位时间的价格，ｗｏｒｋｌｏａｄｉ／ａｂｉｌｉｔｙｊ表示任务ｉ在资源ｊ 上执行所花费的时间。ＲＵ 体现资源使用的均衡，表示为被分配次数的方差，如式（２）所示。方差越小，资源越均衡，反之越不均衡。ＲＵ ＝１／Ｓ，Ｓ ＝∑ｎ１（ｎｕｍｊ－ｎｕｍ）２／ｎ。 （２）式中：Ｓ 为 每 个 提 供 商 资 源 被 分 配 次 数 的 方 差，ｎｕｍｊ 为提供商ｊ 资源被使用的次数，ｎｕｍ为所有提供商的资源被使用次数的均值，ｎ为提供商的个数。３．２　组合反向拍卖模型云工作流系统中的资源分配采用组合反向拍卖机制，可以使服务商获得更高的市场效益。本文对文献［１４］中的组合拍卖进行改进，设计了适于云工作流系统的组合反向拍卖模型。组合反向拍卖模型中首先要确定用户如何提供需求信息，以及提供商如何根据用户所提出的需求信息出售资源；其次用户需要资源为其执行任务，拍卖师负责接收用户的需求，将用户的需求整理后提供给提供商，并接收提供商的投标；最后根据评价标准（见３．１节）评估每个提供商的资源并选出赢家，将拍卖的结果返回给用户和提供商。用户的需求信息包括每个任务执行的开始时间、每种类型的任务量和任务所需资源类型。首先用户将需求信息提交给拍卖师，拍卖师将信息进行整理并将每个任 务的需 求 信 息形成一 个 三元组 Ｒ（ｓｔ，ｗｏｒｋｌｏａｄ，ｔｙｐｅ）。其 中：ｓｔ是任务执行 的 开 始时间，ｗｏｒｋｌｏａｄ 是 组 合 中 第ｉ 种 任 务 类 型 的 任 务量，ｔｙｐｅ是任务所需的资源类型。对于进行组合反向拍卖的任务，拍卖师需将所有任务整合成一个元组Ｂｊ（Ｒｊ１，Ｒｊ２，…，Ｒｊｉ，…，Ｒｊｎ），其中：Ｂｊ是第ｊ个任务组合的需求信息，Ｒｊｉ是第ｊ个任务组合中第ｉ４９３２８；修订日期：２０１６－０８－２８。Ｒｅｃｅｉｖｅｄ　２８Ｊｕｎｅ　２０１６；ａｃｃｅｐｔｅｄ　２８Ａｕｇ．２０１６．基金项目：教育部人文社会科学研究青年基金资助项目（１６ＹＪＣＺＨ０４８）；国家自然科学基金资助项目（６１６７２０３４）；安徽省教育厅自然科学研究重点资助项目（ＫＪ２０１６Ａ０２４）。Ｆｏｕｎｄａｔｉｏｎ　ｉｔｅｍｓ：Ｐｒｏｊｅｃｔ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｙｏｕｔｈ　Ｆｕｎｄ　ｆｏｒ　Ｈｕｍａｎｉｔｉｅｓ　ａｎｄ　Ｓｏｃｉａｌ　Ｓｃｉｅｎｃｅ　ｏｆ　Ｍｉｎｉｓｔｒｙｏｆ　Ｅｄｕｃａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．１６ＹＪＣＺＨ０４８），ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ，Ｃｈｉｎａ（Ｎｏ．６１６７２０３４），ａｎｄ　ｔｈｅ　Ｎａｔｕｒａｌ　ＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎ　ｏｆ　Ｅｄｕｃａｔｉｏｎ　Ｃｏｍｍｉｓｓｉｏｎ　ｏｆ　Ａｎｈｕｉ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ（Ｎｏ．ＫＪ２０１６Ａ０２４）．基于动态定价组合反向拍卖的云工作流系统资源分配机制李学俊，陈　千，刘祥俊，钟云香，徐　佳，朱二周＋（安徽大学 计算机科学与技术学院，安徽　合肥　２３０６０１）摘　要：为了引入动态定价机制、动态调整资源价格以提高资源提供商的竞争力，将动态定价组合反向拍卖方法引入云工作流资源分配中，设计了适于云工作流系统的组合反向拍卖模型，提出动态定价组合反向拍卖算法。通过基因序列工作流 Ｅｐｉｇｅｎｏｍｉｃｓ进行对比实验，结果表明固定价格时组合反向拍卖的时间费用之积和拍卖次数比反向拍卖分别平均降低６０％和１７％，组合反向拍卖中动态定价的时间费用之积比固定价格平均降低６３％，资源利用率平均提高６９％。关键词：云计算；云工作流系统；资源分配；动态定价；反向拍卖中图分类号：ＴＰ３９１　　　文献标识码：ＡＤｙｎａｍｉｃ－ｐｒｉｃｉｎｇ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ－ｂａｓｅｄ　ｒｅｓｏｕｒｃｅ　ａｌｌｏｃａｔｉｏｎｍｅｃｈａｎｉｓｍ　ｉｎ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｙｓｔｅｍＬＩ　Ｘｕｅｊｕｎ，ＣＨＥＮ　Ｑｉａｎ，ＬＩＵ　Ｘｉａｎｇｊｕｎ，ＺＨＯＮＧ　Ｙｕｎｘｉａｎｇ，ＸＵ　Ｊｉａ，ＺＨＵ　Ｅｒｚｈｏｕ＋（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈｅｆｅｉ　２３０６０１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ　ｉｓ　ａｎ　ｅｆｆｅｃｔｉｖｅ　ｍｅｔｈｏｄ　ｆｏｒ　ｒｅｓｏｕｒｃｅ　ａｌｌｏｃａｔｉｏｎ　ｏｆ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｙｓｔｅｍ．Ｂｕｔ　ｔｈｉｓ　ｍｅｔｈｏｄｃａｕｓｅｓ　ｌｏｎｇ　ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ａｎｄ　ｌｏｗ　ｅｆｆｉｃｉｅｎｃｙ　ｂｅｃａｕｓｅ　ｉｔ　ｍａｋｅｓ　ａｕｃｔｉｏｎ　ｓｅｐａｒａｔｅｌｙ．Ｂｙ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎｍｅｃｈａｎｉｓｍ，ｔｈｅ　ｂｒｏｔｈｅｒ　ｎｏｄｅｓ　ｏｆ　ｗｏｒｋｆｌｏｗ　ｔａｓｋｓ　ａｒｅ　ｃｏｍｂｉｎｅｄ　ｂｙ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ．Ｔｈｉｓ　ｂｒｉｎｇｓ　ｈｉｇｈａｕｃｔｉｏｎ　ｅｆｆｉｃｉｅｎｃｙ．Ｕｓｕａｌｌｙ　ｒｅｓｏｕｒｃｅ　ｐｒｉｃｅ　ｉｓ　ｆｉｘｅｄ　ｓｏ　ｔｈａｔ　ｗｅａｋｌｙ　ｃｏｍｐｅｔｉｔｉｖｅ　ｒｅｓｏｕｒｃｅｓ　ｐｒｏｖｉｄｅｒｓ　ａｒｅ　ｈａｒｄ　ｔｏ　ｓｅｌｌ　ｒｅ－ｓｏｕｒｃｅｓ　ａｎｄ　ｔｈｅｎ　ｒｅｓｕｌｔｓ　ｉｎ　ｌｏｗ　ｒｅｓｏｕｒｃｅ　ｕｔｉｌｉｚａｔｉｏｎ．Ｔｏ　ｉｎｔｒｏｄｕｃｅ　ｔｈｅ　ｄｙｎａｍｉｃ　ｐｒｉｃｉｎｇ　ｍｅｃｈａｎｉｓｍ　ａｎｄ　ｔｈｅ　ｄｙｎａｍｉｃｐｒｉｃｉｎｇ　ｓｔｒａｔｅｇｙ　ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｐｒｏｖｉｄｅｒｓｃｏｍｐｅｔｉｔｉｖｅ　ａｂｉｌｉｔｙ，ａ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ　ｍｏｄｅｌ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ　ｂｙｌｅａｄｉｎｇ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆ　ｄｙｎａｍｉｃ－ｐｒｉｃｉｎｇ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ　ｉｎｔｏ　ｔｈｅ　ｒｅｓｏｕｒｃｅｓ　ａｌｌｏｃａｔｉｏｎ　ｏｆ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗｓｙｓｔｅｍ，ａｎｄ　ａ　ｄｙｎａｍｉｃ－ｐｒｉｃｉｎｇ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｗｅｒｅ　ｓｉｍｕｌａｔｅｄｏｎ　Ｅｐｉｇｅｎｏｍｉｃｓ　ｗｏｒｋｆｌｏｗｓ，ａｎｄ　ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗｅｄ　ｔｈａｔ　Ｔｉｍｅ　Ｃｏｓｔ（ＴＣ）ａｎｄ　ａｕｃｔｉｏｎ　ｔｉｍｅｓ　ｏｆ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅａｕｃｔｉｏｎ　ｗｉｔｈ　ｆｉｘｅｄ　ｐｒｉｃｉｎｇ　ｗｅｒｅ　ｌｏｗｅｒ　ｔｈａｎ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ　ｂｙ　６０％ ａｎｄ　１７％ ａｖｅｒａｇｅｌｙ．Ｔｈｅ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｒｅｖｅｒｓｅａｕｃｔｉｏｎ　ＴＣ　ｏｆ　ｄｙｎａｍｉｃ　ｐｒｉｃｉｎｇ　ｗａｓ　ｌｏｗｅｒ　ｔｈａｎ　ｆｉｘｅｄ　ｐｒｉｃｉｎｇ　ｂｙ　６３％ ａｎｄ　ｒｅｓｏｕｒｃｅ　ｕｔｉｌｉｚａｔｉｏｎ　ｏｆ　ｄｙｎａｍｉｃ　ｐｒｉｃｉｎｇ　ｗａｓｈｉｇｈｅｒ　ｔｈａｎ　ｆｉｘｅｄ　ｐｒｉｃｉｎｇ　６９％ ａｖｅｒａｇｅｌｙ．Ｋｅｙｗｏｒｄｓ：ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ；ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｙｓｔｅｍ；ｒｅｓｏｕｒｃｅ　ａｌｌｏｃａｔｉｏｎ；ｄｙｎａｍｉｃ　ｐｒｉｃｉｎｇ；ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎ０　引言云计 算 是 一 种 新 兴 的 大 规 模 分 布 式 计 算 范式［１］，其通过虚拟化技术提供资源服务，采用按需付费模式提供无限的计算资源，具有较高的可靠性和较低的成本。云工作流系统是工作流管理系统应用 李学俊 等：基于动态定价组合反向拍卖的云工作流系统资源分配机制４．２　组合反向拍卖的固定价格和动态定价为了比较动态定价和固定价格，共进行３组实验，且工作流的任务个数分别为２０，２４，４８。每组实验分别使用基于固定价格的组合反向拍卖算法和基于动态定价的组合反向拍卖算法，为工作流的执行进行资源分配，然后统计出整个工作流资源分配后的ＲＵ 和总ＴＣ。动态定价的 ＴＣ 比固定价格低，如图４所示。例如当任务个数为２４时，动态定价 ＴＣ比固定价格降低６４％。这是由于组合反向拍卖中使用动态定价，为提高提供商的竞争力降低资源价格，从而 使 整 个 工 作 流 的 所 需 费 用 比 使 用 固 定 价格低。组合反向拍 卖 时 动 态 定 价 的 ＲＵ 高 于 固 定 价格，如图５所示。例如当任务个数为２０时，动态定价的ＲＵ 比固定价格提高６３％；当组合反向拍卖使用动态定价时，原本竞争力较弱的提供商可以通过降低价格 获 得 成 功 卖 出 资 源 的 机 会，从 而 提 高 了ＲＵ。通过上述实验可以看出，以 ＴＣ，ＲＵ 和拍卖次数作为评价标准，在相同的条件下，组合反向拍卖优于反向拍卖，动态定价优于固定价格。在工作流的资源分配中，相比于其他拍卖方式，本文提出的基于动态定价的组合反向拍卖工作流执行时拥有更少的完成时间和所需费用以及更高的 ＲＵ，从而提高拍卖效率，并使用户获得更优惠的资源。５　结束语本文利用经济学中拍卖的方法对云工作流进行资源分配，考虑资源的互补性、提供商的竞争性和云资源市场的动态性，提出基于动态定价的组合反向拍卖机制。云提供商通过动态调整资源价格提高了竞争力较弱的资源提供商赢得拍卖的几率，从而提高了资源利用率。同时，云工作流系统使用组合反向拍卖将满足要求的兄弟节点任务同时进行拍卖，从而降低了工作流的完成时间和所需费用，提高了拍卖效率。目前在对资源进行评估时只考虑了完成时间和所需费用，未来工作会将更多的资源因素引入评价标准中。另外，实际工作流系统中兄弟节点同时参与拍卖可能导致的拍卖失败、额外开销和价格过高等问题，也都值得深入研究。参考文献：［１］　ＢＵＹＹＡ　Ｒ，ＹＥＯ　Ｃ，ＶＥＮＵＧＯＰＡＬ　Ｓ，ｅｔ　ａｌ．Ｃｌｏｕｄ　ｃｏｍｐｕ－ｔｉｎｇ　ａｎｄ　ｅｍｅｒｇｉｎｇ　ＩＴ　ｐｌａｔｆｏｒｍｓ：ｖｉｓｉｏｎ，ｈｙｐｅ，ａｎｄ　ｒｅａｌｉｔｙ　ｆｏｒｄｅｌｉｖｅｒｉｎｇ　ｃｏｍｐｕｔｉｎｇ　ａｓ　ｔｈｅ　５ｔｈ　ｕｔｉｌｉｔｙ［Ｊ］．Ｆｕｔｕｒｅ　ＧｅｎｅｒａｔｉｏｎＣｏｍｐｕｔｅｒ　Ｓｙｓｔｅｍｓ，２００９，２５（６）：５９９－６１６．［２］　ＺＨＡＯ　Ｙｏｎｇ，ＬＩ　Ｙｏｕｆｕ，ＴＩＡＮ　Ｗｅｎｈｏｎｇ，ｅｔ　ａｌ．Ｓｃｉｅｎｔｉｆｉｃ－ｗｏｒｋｆｌｏｗ－ｍａｎａｇｅｍｅｎｔ－ａｓ－ａ－ｓｅｒｖｉｃｅ　ｉｎ　ｔｈｅ　ｃｌｏｕｄ［Ｃ］／／Ｐｒｏｃｅｅｄ－ｉｎｇｓ　ｏｆ　ｔｈｅ　２ｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｌｏｕｄ　ａｎｄ　ＧｒｅｅｎＣｏｍｐｕｔｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１２：９７－１０４．［３］　ＬＩ　Ｘｕｅｊｕｎ，ＬＩＵ　Ｘｉａｎｇｊｕｎ，ＺＨＵ　Ｅｒｚｈｏｕ．Ａｎ　ｅｆｆｉｃｉｅｎｔ　ｒｅｓｏｕｒｃｅａｌｌｏｃａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ　ｂａｓｅｄ　ｏｎ　ｄｙｎａｍｉｃ　ｐｒｉｃｉｎｇ　ｒｅｖｅｒｓｅ　ａｕｃｔｉｏｎｆｏｒ　ｃｌｏｕｄ　ｗｏｒｋｆｌｏｗ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ａｓｉａ－Ｐａｃｉｆｉｃ４９５计算机集成制造系统 第２３卷Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｂｕｓｉｎｅｓｓ　Ｐｒｏｃｅｓｓ　Ｍａｎａｇｅｍｅｎｔ．Ｂｅｒｌｉｎ，Ｇｅｒｍａ－ｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２０１５：５９－６９．［４］　ＨＵＵ　Ｔ　Ｔ，ＭＯＮＴＡＧＮＡＴ　Ｊ．Ｖｉｒｔｕａｌ　ｒｅｓｏｕｒｃｅｓ　ａｌｌｏｃａｔｉｏｎ　ｆｏｒｗｏｒｋｆｌｏｗ－ｂａｓｅｄ　ａｐｐｌｉｃａｔｉｏｎｓ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｎ　ａ　ｃｌｏｕｄ　ｉｎｆｒａｓｔｒｕｃ－ｔｕｒｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１０ｔｈ　ＩＥＥＥ／ＡＣＭ　ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｌｕｓｔｅｒ，Ｃｌｏｕｄ　ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ．Ｗａｓｈｉｎｇ－ｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１０：６１２－６１７．［５］　ＬＥＥ　Ｃ，ＷＡＮＧ　Ｐ，ＮＩＹＡＴＯ　Ｄ．Ａ　ｒｅａｌ－ｔｉｍｅ　ｇｒｏｕｐ　ａｕｃｔｉｏｎｓｙｓｔｅｍ　ｆｏｒ　ｅｆｆｉｃｉｅｎｔ　ａｌｌｏｃａｔｉｏｎ　ｏｆ　ｃｌｏｕｄ　Ｉｎｔｅｒｎｅｔ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｅｒｖｉｃｅｓ　Ｃｏｍｐｕｔｉｎｇ，２０１５，８（２）：２５１－２６８．［６］　ＦＡＲＤ　Ｈ，ＰＲＯＤＡＮ　Ｒ，ＦＡＨＲＩＮＧＥＲ　Ｔ．Ａ　ｔｒｕｔｈｆｕｌ　ｄｙｎａｍｉｃｗｏｒｋｆｌｏｗ　ｓｃｈｅｄｕｌｉｎｇ　ｍｅｃｈａｎｉｓｍ　ｆｏｒ　ｃｏｍｍｅｒｃｉａｌ　ｍｕｌｔｉ－ｃｌｏｕｄｅｎｖｉｒｏｎｍｅｎｔｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕ－ｔｅｄ　Ｓｙｓｔｅｍｓ，２０１３，２４（６）：１２０３－１２１２．［７］　ＰＡＰＡＺＯＧＬＯＵ　Ｍ，ＴＲＡＶＥＲＳＯ　Ｐ，ＤＵＳＴＤＡＲ　Ｓ，ｅｔ　ａｌ．Ｓｅｒｖｉｃｅ－ｏｒｉｅｎｔｅｄ　ｃｏｍｐｕｔｉｎｇ：ａ　ｒｅｓｅａｒｃｈ　ｒｏａｄｍａｐ［Ｊ］．Ｉｎｔｅｒｎａ－ｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｏｐｅｒａｔｉｖｅ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ，２００８，１７（２）：２２３－２５５．［８］　ＳＨＩ　Ｘｕｅｌｉｎ，ＺＨＡＯ　Ｙｉｎｇ．Ｄｙｎａｍｉｃ　ｒｅｓｏｕｒｃｅ　ｓｃｈｅｄｕｌｉｎｇ　ａｎｄｗｏｒｋｆｌｏｗ　ｍａｎａｇｅｍｅｎｔ　ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆＩｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｅｂ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ　Ｅｎｇｉ－ｎｅｅｒｉｎｇ．Ｂｅｒｌｉｎ，Ｇｅｒｍａｎｙ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２０１０：４４０－４４８．［９］　ＢＥＳＳＡＩ　Ｋ，ＹＯＵＣＥＦ　Ｓ，ＯＵＬＡＭＡＲＡ　Ａ，ｅｔ　ａｌ．Ｂｉ－ｃｒｉｔｅｒｉａｗｏｒｋｆｌｏｗ　ｔａｓｋｓ　ａｌｌｏｃａｔｉｏｎ　ａｎｄ　ｓｃｈｅｄｕｌｉｎｇ　ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇｅｎｖｉｒｏｎｍｅｎｔｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎ－ｆｅｒｅｎｃｅ　ｏｎ　Ｃｌｏｕｄ　Ｃｏｍｐｕｔｉｎｇ． Ｗａｓｈｉｎｇｔｏｎ， Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１２：６３８－６４５．［１０］　ＢＥＳＳＡＩ　Ｋ，ＹＯＵＣＥＦ　Ｓ，ＯＵＬＡＭＡＲＡ　Ａ，ｅｔ　ａｌ．Ｂｉ－ｃｒｉｔｅｒｉａｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　ｂｕｓｉｎｅｓｓ　ｐｒｏｃｅｓｓｅｓ　ｓｃｈｅｄｕｌｉｎｇ　ｉｎ　ｃｌｏｕｄ　ｅｎｖｉｒｏｎ－ｍｅｎｔｓ　ｗｉｔｈ　ｆａｉｒｎｅｓｓ　ｍｅｔｒｉｃｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　Ｉｎ－ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅｓｅａｒｃｈ　Ｃｈａｌｌｅｎｇｅｓ　ｉｎ　ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１３：１－１０．［１１］　ＤＡＳ　Ａ，ＡＤＨＩＫＡＲＹ　Ｔ，ＲＡＺＺＡＱＵＥ　Ｍ，ｅｔ　ａｌ．Ａ　ＱｏＳ　ａｎｄｐｒｏｆｉｔ　ａｗａｒｅ　ｃｌｏｕｄ　ｃｏｎｆｅｄｅｒａｔｉｏｎ　ｍｏｄｅｌ　ｆｏｒ　ＩａａＳ　ｓｅｒｖｉｃｅ　ｐｒｏ－ｖｉｄｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　８ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅｏｎ　Ｕｂｉｑｕｉｔｏｕｓ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｍａｎａｇｅｍｅｎｔ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ．Ｎｅｗ　Ｙｏｒｋ，Ｎ．Ｙ．，ＵＳＡ：ＡＣＭ，２０１４：１－７．［１２］　ＲＡＯ　Ｓ，ＰＲＡＳＡＤ　Ａ．Ａ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ａｕｃｔｉｏｎ　ｍｅｃｈａｎｉｓｍ　ｆｏｒｍｕｌｔｉｐｌｅ　ｒｅｓｏｕｒｃｅ　ｐｒｏｃｕｒｅｍｅｎｔ　ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ［Ｃ］／／Ｐｒｏ－ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１２ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓ　Ｄｅｓｉｇｎ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１２：３３７－３４４．［１３］　ＴＥＮＧ　Ｆ，ＭＡＧＯＵＬＥＳ　Ｆ．Ｒｅｓｏｕｒｃｅ　ｐｒｉｃｉｎｇ　ａｎｄ　ｅｑｕｉｌｉｂｒｉｕｍａｌｌｏｃａｔｉｏｎ　ｐｏｌｉｃｙ　ｉｎ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ１０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　ＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１０：１９５－２０２．［１４］　ＭＩＨＡＩＬＥＳＣＵ　Ｍ，ＴＥＯ　Ｙ．Ｏｎ　ｅｃｏｎｏｍｉｃ　ａｎｄ　ｃｏｍｐｕｔａｔｉｏｎａｌ－ｅｆｆｉｃｉｅｎｔ　ｒｅｓｏｕｒｃｅ　ｐｒｉｃｉｎｇ　ｉｎ　ｌａｒｇｅ　ｄｉｓｔｒｉｂｕｔｅｄ　ｓｙｓｔｅｍｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１０ｔｈ　ＩＥＥＥ／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅｏｎ　Ｃｌｕｓｔｅｒ，Ｃｌｏｕｄ　ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１０：８３８－８４３．［１５］　ＫＡＮＴＥＲＥ　Ｖ，ＤＡＳＨ　Ｄ，ＦＲＡＮＣＯＩＳ　Ｇ，ｅｔ　ａｌ．Ｏｐｔｉｍａｌｓｅｒｖｉｃｅ　ｐｒｉｃｉｎｇ　ｆｏｒ　ａ　ｃｌｏｕｄ　ｃａｃｈｅ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎＫｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１１，２３（９）：１３４５－１３５８．［１６］　ＸＵ　Ｈ，ＬＩ　Ｂ．Ｍａｘｉｍｉｚｉｎｇ　ｒｅｖｅｎｕｅ　ｗｉｔｈ　ｄｙｎａｍｉｃ　ｃｌｏｕｄ　ｐｒｉ－ｃｉｎｇ：ｔｈｅ　ｉｎｆｉｎｉｔｅ　ｈｏｒｉｚｏｎ　ｃａｓｅ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　Ｉｎ－ｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１２：２９２９－２９３３．［１７］　ＴＲＵＯＮＧ－ＨＵＵ　Ｔ，ＴＨＡＭ　Ｃ．Ａ　ｇａｍｅ－ｔｈｅｏｒｅｔｉｃ　ｍｏｄｅｌ　ｆｏｒｄｙｎａｍｉｃ　ｐｒｉｃｉｎｇ　ａｎｄ　ｃｏｍｐｅｔｉｔｉｏｎ　ａｍｏｎｇ　ｃｌｏｕｄ　ｐｒｏｖｉｄｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ／ＡＣＭ　６ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅｏｎ　Ｕｔｉｌｉｔｙ　ａｎｄ　Ｃｌｏｕｄ　Ｃｏｍｐｕｔｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ，Ｄ．Ｃ．，ＵＳＡ：ＩＥＥＥ，２０１３：２３５－２３８．作者简介：李学俊（１９７６－），男，安徽金寨人，副教授，博士，研究方向：云计算、智能软件，Ｅ－ｍａｉｌ：ｘｊｌｉ＠ａｈｕ．ｅｄｕ．ｃｎ；陈　千（１９９１－），男，安徽合肥人，硕士研究生，研究方向：工作流系统；刘祥俊（１９９０－），男，安徽六安人，硕士研究生，研究方向：云计算、工作流、组合拍卖；钟云香（１９９０－），女，安徽庐江人，硕士研究生，研究方向：多租户服务选择；徐　佳（１９９２－），男，上海人，硕士研究生，研究方向：工作流系统；　＋朱二周（１９８１－），男，安徽五河人，副教授，博士，研究方向：虚拟化、云计算，通信作者，Ｅ－ｍａｉｌ：ｅｚｚｈｕ＠ａｈｕ．ｅｄｕ．ｃｎ。４９６