分布式环境中基于市场机制的资源自适应调价策略

丁长松，王志英，胡志刚



分布式环境中基于市场机制的资源自适应调价策略

丁长松1,2，王志英1，胡志刚3

（1. 国防科技大学计算机学院，湖南长沙 410073； 2．湖南中医药大学管理与信息工程学院，湖南长沙 410208；3．中南大学软件学院，湖南长沙 410083）

针对分布式环境中资源定价面临的资源使用率、价格、收益三者之间的冲突问题，提出一种基于市场机制的资源自适应调价策略。该策略在保障资源提供者收益前提下，通过资源价格自适应动态调整来平衡资源节点上的任务分配与资源提供者收益之间的冲突。理论分析证明了调价策略的有效性，并在此基础上设计了自适应调价算法。仿真实验采用真实分布式系统中资源节点信息作为实验节点的性能参数，在大规模网格任务中检验了自适应调价策略的性能表现。实验结果表明，基于市场机制的“自适应调价策略”在保障资源收益、均衡资源利用率的性能表现方面显著优于传统的定价策略。

分布式计算；市场机制；自适应；调价策略

1 引言

网格计算[1]和云计算[2]等网络计算平台通过整合资源提供强大的计算能力，为实时计算、可视化远程医疗、电子商务等领域中复杂的大型任务提供服务，并在服务过程中保障“非凡的服务质量”[3]。相关研究[4~6]显示，利用经济模型管理资源在促进资源公平分配、激励资源所有者和资源使用者参与交易、资源分配与资源供需变化的自适应等方面都有很好的表现。然而，作为市场机制中的核心问题之一，资源定价问题一直难以得到有效解决，其复杂性主要体现在以下2个方面：1）资源提供给其他用户使用的时间段内，到达的本地任务QoS指标，如等待时间、资源利用率等均受到不同程度的影响，网络环境下资源的动态性增加了量化这种负面影响的难度；2）市场经济环境中收益、价格以及资源分配三者之间关系的复杂性，加大了利用价格平衡资源提供者收益的难度。因此，如何通过合理的定价机制来保障资源提供者本地任务的QoS且使资源提供者获得合理收益，是一个亟待解决的问题。

本文从资源性能的真实统计特性出发，将市场经济中价格对资源使用者的影响作为价格调整的基础，引入成本价格弥补出让资源使用权带来的不利影响、利润价格增加额外收益，通过价格的自适应调整保障资源提供者得到合理的资源分配，并促使各资源节点的负载大体平衡。

2 相关工作

借用经济学理论分析市场交易中各参与方的行为、交易收益的方法已被广泛应用于计算机资源管理中，且其有效性已在诸多基于经济学理论的实际资源管理系统中得到验证。如为解决联网异构计算机的调度问题，Waldspurger等[7]设计并实现了一个面向市场调度的Spawn系统。该系统采用Vickrey拍卖机制，用户根据各自偏好，如成本最低、响应时间最小等指标，制定相应竞标策略。针对网络中多用户的带宽分配问题，文献[8]采用效用函数衡量网络用户的满意度，提出了基于网络聚合效用最大化的网络跨层映射模型，该模型求解出的最优带宽分配与各用户的支付费用情况相关。近年来出现的云计算模式由于其提出就考虑商业实现，因而经济学理论往往应用于资源分配中，如针对云虚拟机资源的分配问题，文献[9]提出了以云效用最大为资源调度目标的云虚拟机资源分配模型。

资源定价作为经济模型中资源交易各参与方关注重点，其策略直接影响到资源管理的效果。资源定价主要分为集中式和分布式2种策略。前者根据资源市场的总体供需情况对资源价格进行同步调节，如商业分配方式[10]；后者则根据资源供需情况进行单独调价，整体资源的均衡价格通过对每个资源重复调价获得。集中式定价算法收敛速度快，但价格相对固定，难以适应动态变化的网络环境，且算法复杂度相对较高。分布式定价在进行价格调节时没有考虑各个资源价格之间的相关性，因而不适应资源价格关联性较强的情况[11]，但算法复杂度相对较低。针对市场机制下网格资源调价动态变化快，资源价格的调整节奏与网格环境中资源供需关系变化难以保持相对一致的情况，文献[11]结合集中式调价算法收敛快速的优点，对分布式调价WALRAS算法[12]进行了改进，提了分布式分组调价算法。文献[13]针对异构无线网络资源管理问题，提出了基于Stackelberg博弈模型的分布式定价和资源分配算法。

相关研究显示[14~16]，分布式环境中资源所有者出让资源使用权后，将导致本地任务的性能指标如任务反应时间、任务平均等待时间增加等问题。为了弱化其给本地任务带来的负面影响，文献[17]根据本地任务的统计特性制定定价策略，通过价格来保障资源提供者利益。针对网格计算中多QoS约束的作业调度NP难问题，文献[18]将该问题归约为多目标组合最优化问题，并提出了相应的多目标演化算法以保障网格用户的效用。针对分布式资源管理中用户的信任QoS与服务调度难以融合的问题，文献[19]通过效用函数量化服务提供者与服务请求者间信任关系，并在此基础上提出了保证多QoS的服务调度算法。

本文借鉴了分布式定价策略中“根据资源供需情况单独调价以达供需平衡”的思想，但与传统的分布式资源定价机制没有考虑资源间的相关性不同，本文将资源间的相关性体现在任务分配的博弈之中，通过市场交易中心根据资源所有者的报价与市场整体情况确定资源分配方案，资源所有者通过价格调整使分配方案与整个市场的供需关系保持一致。

3 问题描述

多资源协同服务的交易系统由资源用户、交易中心、资源代理和资源提供方4个主要实体组成。其中，资源提供方由资源集群组成，作为生产者提供资源。本文仅考虑在某时间段已被使用的资源在该时间段不能再被其他用户使用的独占型、消耗型资源，如CPU计算能力、存储能力等，并由资源代理对价格进行决策；资源用户作为消费者使用资源提供方的服务，根据使用服务的情况支付相应的费用；资源分配由交易中心决定，整个资源交易在交易中心的监管下进行；资源代理根据资源提供方的历史统计情况与市场交易情况对资源的利润价格进行自动调节。

资源提供方和资源用户通过市场交易来提供和使用资源，双方追求各自收益最大化。基于一般市场经济学中理性选择原理和曼昆经济学理论[20]，本文基于以下3点假设。

1) 资源提供方希望通过提供相同资源使用权所获得的资源利润越大越好。

2) 在使用相同服务的情况下，资源用户希望支付费用越低越好。

3) 市场希望各交易参与方满意，各资源提供方的收益大体平衡。

在上述3点假设的基础上，设资源提供方将某时间段内的资源使用权以单位时间价格提供给资源用户并获得一定的收益，其收益为

其中，为资源提供方实际出让的服务能力，即资源交易中资源的交易量。根据前面的假设可知，在提供相同服务的前提下，价格越低的资源提供方由于资源用户追求低的费用，因而其获得资源交易量越大。在为资源用户提供资源服务的时间段内可能增加“资源碎片”或可能导致该时间段内到达的本地任务QoS无法保障等情况，从而给本地任务造成一定的损失。本文采用经济学中成本加成定价模式[21]，将资源单位价格表示为单位成本和加成价格

(2)

其中，单位成本0为提供资源使用权给资源所有者带来负面影响以及为提供服务所增加的额外开销在市场环境中的货币量化，如协同服务时增加的网络通信开销成本也包含其中。0根据实际环境确定，如文献[17]针对网格计算环境采取了本地任务的概率分布特性进行计算；Δ为加成部分，根据“3C+R”定价原理中成本是定价下限约束[23]，将Δ>0作为约束条件。由加成定价模式的定价经验公式可知

(4)

根据第2点假设可知，理性的资源用户在相同服务的前提下会选择与价格低的资源提供方进行交易。因此，在资源用户的总需求确定的情况下，资源用户和资源提供方之间发生的交易量与资源价格相关。又由于在实际的资源交易场景中成本0确定，从式（4）可知资源价格随值的变化而变化。综合上述分析可得，资源的交易量与利润因子相关。基于此，本文基于资源的交易量与利润因子之间的相关性，通过调节值促使各节点负载趋于均衡。

4 自适应调价策略

资源交易中参与者根据历史情况对本次交易的结果做出期望，但由于交易是多方博弈过程，其实际结果与期望存在着差异。针对该情况，根据资源代理预期出让的服务能力0与资源提供方实际出让的服务能力之间的差距分为：1）|−0|≤0；2）0<|−0|≤1；3）1<|−0|。其中，0和1分别代表资源代理所能接受和较靠近接受的出让服务能力与期望出让服务能力之间的最大差值，0同时也是价格自适应调整终止参数。1）和2）分配结果没有达到资源代理所能接受的范围，因而需要对价格进行适当调整以使出让的服务能力满足资源代理的期望，其调价流程如图1所示。

4.1 第1调价策略

当0<|−0|≤1时，利润因子值只需进行微调。由于每次调整为使|−0|趋近于0，因而该调整可采用摸索过程（tatonnement）[22]。在调整过程中利润因子相近，2次幅度调整关系表示为，其中和分别为第次调价幅度和价格调整速率，为使每次调整后|-0|更趋近0，令，其中，为常系数，其值域为(0, 1)。该摸索过程如图2所示，通过构造李亚普诺夫能量函数的方法可证明该过程是收敛的。

4.2 第2调价策略

当1<|−0|时，利润因子值需调整的幅度较大，其调整目标依然是使|−0|趋近于0，因而该调整过程依然可采用摸索过程。与第1调价策略不同之处在于，为使|−0|能在尽量少的调整过程中接近0甚至达到|−0|≤0的范围，利润因子相近的2次幅度调整速率的系数的取值方法如下

4.3 自适应调价算法

自适应调价算法（A3PA, auto-adapted adjustment price algorithm）的伪码如图3所示。

输入：由各资源集群信息组成的队列RQ、任务申请T、资源代理承受阈值k0、k1输出：价格方案p=(p1,…, pn)Begin1) 初始化价格方案（p=null）2) 过滤掉不满足任务申请QoS约束的资源节点，并对符合条件的资源节点的利润因子λi进行初始化，计算成本价格并将价格上报给交易中心，Q=03) while Q=0 do4) 交易中心根据各资源代理报价，结合市场规则选择资源分配方案5) 计算在各资源代理所能接受的分配方案区间的任务QoS表现6) if QoS表现满足需求约束，then Q=17) end while8) while RQ<>null do9) if 存在资源代理|c−c0|≤k0 then10) 该资源代理出队列RQ，并将该代理价格加入队列p=(p1,…, pn)11) else if |c−c0|≤k1 then 12) 执行第1调价策略else13) 执行第2调价策略14)endif15) 队列RQ中的代理上报交易中心调整后的价格16)end while17) 输出p=(p1,…, pn)End

A3PA算法首先初始化价格方案，过滤不满足任务QoS约束的节点和根据历史日志计算出成本价格并对利润因子进行初始化（步骤1)和步骤2)），接下来根据任务QoS约束确定资源分配方案（步骤3)~ 步骤7)），然后资源代理队列根据交易中心的分配方案确定是否对价格进行调整以及如何调整（步骤9)~ 步骤13)）。为保证每个资源代理获得可接受的分配方案，用<>null作为循环约束条件（步骤8)~步骤16)）。理想情况为交易中心根据各资源代理初始化利润因子λ计算出的分配方案就能满足各资源代理的期望，在该情况下算法的时间复杂度为()。最坏情况为根据各资源代理初始化利润因子计算出的资源交易量没有资源代理能接受，每个节点都需要进行调价，但是需要调价的资源代理数量与时间复杂度无关，这是由于在步骤8)~步骤16)中循环约束条件只要存在资源代理对资源分配方案不满意就继续调整价格，具体的时间复杂度与所选的调整策略承受阈值0相关，A3PA算法的收敛性由调价策略1和调价策略2的收敛性保障。

5 实验结果与性能评估

5.1 仿真实验设计

为检验本文提出的分布式环境中自适应定价策略（A3PS, auto-adapted adjustment price strategy）的性能表现，基于GridSim搭建了一个分布式系统。实验中各站点性能参数配置采用Grid’5000[23]在2015年4月22日的实际配置，详细信息如表1所示。任务负载采用Lublin-Feitelson模型生成。考虑到任务由Lublin-Feitelson模型随机生成，实验数据采用每次实验重复10次后的平均结果。

表1 模拟网格系统的数据信息

模拟实验将A3PS策略与在资源定价中广泛应用的招投标/合同网模型（TCM, tender/contract-net model）[24]和商品市场模型（CMM, commodity market model）[25]的性能表现进行比较。

5.2 性能分析与比较

5.2.1 性能比较

表2 模拟实验结果

表2中数据显示，TCM策略的任务完成时间最长，而A3PS策略的任务完成时间最短，其原因在于TCM策略中资源价格由资源所有者指定，其定价机制相对固定，导致资源用户选择资源时具有随机性，选择的资源不一定是最合适的资源。然而，A3PS策略其价格中成本价格部分就蕴含着本地任务对资源的使用情况，而理性的资源使用者都倾向于选择价格低的资源，因此其任务完成时间最短。TCM模型的最大反映出各资源利用率情况相差很大，这正是由于TCM模型中资源用户一旦选择了某个资源提供方后就不会考虑其他资源情况的这一缺陷所致，而A3PS策略的最小体现了其有使资源负载趋向平衡的能力，分析原因还是在于A3PS策略的定价考虑了成本价格且利润价格与市场整体利润平衡时的资源提供方才停止调价，而资源用户将任务放在价格较低的资源节点上运行，价格低的资源节点其本地任务相对较少，因而起到了平衡资源节点负载作用。

表2中数据显示，3种策略的总收益和总利润之间的差距都较大。导致这一现象的原因在于实验中设置的费用预算较大，在进行任务分配时费用预算对分配策略影响不大。实验中发现如果将费用预算减少，3种策略的总收益差距会减小。造成总利润之间的差距较大的原因是，A3PS策略在成本价格较低的资源节点上分配的任务多，因而其利润相对高，根据定价策略可知，成本价格与资源节点原有负载相关，即成本价格低的节点其负载较低，通过A3PS策略把资源用户的任务更多地分配到负载较低的节点中，这也与A3PS策略值最小相符合。

实验中发现，A3PS策略的资源节点总调价次数明显高于其他策略，正是由于该策略具有自适应调价的灵活性，根据市场供需情况采用自动调价，使收益符合各自预期。

5.2.2 参数分析

上述检验A3PS策略实验中，当0<|−0|≤1时，采取第1调价策略时||=0.1；当1<|−0|时，初始=1.2，接纳阈值0=0.025。为进一步研究不同参数情况下调价策略对资源节点以及任务QoS指标的影响，对策略中参数采取了不同的取值。表3中1、2分别为0<|−0|≤1时，||和1<|−0|中的取值。

表3 模拟实验结果

综合上述实验结果可以得出：调价函数和接纳阈值对系统的调节次数有很大的影响，接纳阈值相同的情况下调价函数的变化对各资源的总收益与任务完成时间没有明显影响，资源的总收益和任务完成时间、调价次数与接受阈值相关，而且接受阈值越小调价次数越多，收益越大，这表示资源提供者对分配策略的要求比较苛刻，表明资源分配方案与价格调整函数关系不大，只要资源提供方的接纳分配策略范围|−0|<0确定，其资源分配方案就能确定。

6 结束语

如何合理地对资源定价是基于市场机制进行资源管理的一个核心问题。本文在保障本地节点利益并尊重市场规律的前提下，对资源提供方出让的使用权进行价格确定，在该定价过程中资源代理利用市场对价格的反应，通过对价格进行自适应调整，使市场中资源分配方案符合资源代理所设置的资源分配接纳区间，以此来保障资源提供方的收益，并建立了资源自适应市场变化的定价策略。对GridSim进行了改进与扩展，并在此平台上对提出的自适应定价策略进行的仿真实验结果表明，本文提出的定价策略不但保障了资源提供方的收益，而且能使各资源节点的资源负载趋于平衡。下一步工作将主要集中研究资源提供者不同偏好以及多QoS约束下保障价格的定价机制与价格调整函数的优化。

[1] FOSTER I, KESSELMAN C. The grid: blueprint for a new computing infrastructure, second edition [M]. Singapore: Elsevier Inc. 2004.

[2] LUO J Z, JIN J H, SONG A B, et al. Cloud computing: architecture and key technologies [J]. Journal on Communications, 2011,32(7): 3-21.

[3] FOSTER I. What is the Grid? a three point checklist [J]. GRID Today, 2002, 1(6): 20-27.

[4] BUYYA R. Economic-based distributed resource management and scheduling for grid computing[D]. Monash University, Australia, 2002.

[5] SANDHOLM T. Making markets and democtacy work: a story of incentives and computing[C]//The International Joint Conference on Artificial Intelligence (IJCAI-03), c2003: 1649-1671.

[6] 曹鸿强, 肖侬, 卢锡城, 等. 一种基于市场机制的计算网格资源分配方法[J]. 计算机研究与发展, 2002, 39(8): 913-916

CAO H Q, XIAO N, LU X C, et al. A market-based approach to allocate resources for computational grids [J]. Journal of Computer Research and Development, 2002, 8(39): 913-916.

[7] WALDSPURGER C, HOGG T, HUBERMAN B, et al. Spawan: a distributed computation economy [J]. IEEE Transactions on Software Engineering, 1992, 18(2): 103-117.

[8] 李世勇, 杨冬, 秦雅娟, 等.基于效用最大化的网络跨层映射[J].软件学报,2011,22(8):1855-1871.

LI S Y, YANG D, QIN Y J, et al. Network cross-layer mapping based in utility maximization[J]. Journal of Softeware, 2011, 22(8): 1855-1871.

[9] 师雪霖,徐恪.云虚拟机资源分配的效用最大化模型[J]. 计算机学报, 2013,36(2): 252-262.

SHI X L, XU K. Utility maximiztion model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2): 252-262.

[10] KENYON C, CHELIOTIS G. Grid resource commercialization: economic engineering and delivery scenarios grid resource management: state of the art and research issues [M]. Kluwer, 2003.

[11] 翁楚良, 陆鑫达. 一种基于市场机制的网格资源调价算法[J]. 计算机研究与发展, 2004, 41(7): 1151-1156.

WENG C L, LU X D. A pricing algorithm for market-based resource management on grid computing systems[J]. Jouranl of Computer Research and Development, 2004, 7(41): 1151-1156.

[12] CHENG J Q, WELLMAN M P. The WALRAS algorithm: a convergent distributed implementation of general equilibrium outcomes [J]. Computational Economics, 1998, 12(1): 1-24.

[13] 姜永, 陈山枝, 胡博. 异构无线网络中基于Stackelberg博弈的分布式定价和资源分配算法[J].通信学报, 2013, 34(1): 61-68.

JIANG Y, CHEN S Z, HU B. Stackelberg games – based distributed algorithm of pricing and resource allocation in heterogeneous wireless netwotks[J]. Journal on Communications, 2013, 34(1): 61-68.

[14] SMITH W, FOSTER I, TAYLOR V. Scheduling with advanced reservations[C]//14th International Parallel and Distributed Processing Symposium(IPDPS 2000), c2000: 127-132.

[15] CAO J F. Zimmermann. Queue scheduling and advance reservations with COSY[C]//18th International conference on Parallel and Distributed Processing Symposium, c2004: 63a.

[16] HEINE F, HOVESTADT M, KAO O, et al. On the impact of reservations from the Grid on planning-based resource management[C]//International Conference on Computational Science-(ICCS 2005). c2005: 155-162.

[17] 丁长松, 王志英, 胡志刚. 基于效用驱动的网格资源协同预留策略[J]. 通信学报, 2014, 35(3): 101-107.

DING C S, WANG Z Y, HU Z G. Utility-driven based co-allocation resource reservation strategy in computational grid[J]. Journal on Communications, 2014, 35(3): 101-107.

[18] 张伟哲, 胡铭曾, 张宏莉, 等. 多QoS约束网格作业调度问题的多目标演化算法[J]. 计算机研究与发展, 2006, 43(11): 1855-1862.

ZHANG W Z, HU M Z, ZHANG H L, et al. A multiobjective evolutionary algorithm for grid job scheduling of multi-QoS constraints [J]. Journal of Computer Research and development, 2006, 43(11): 1855-1862.

[19] 张伟哲, 方滨兴, 胡铭曾, 等. 基于信任QoS增强的计算服务调度算法[J]. 计算机学报, 2006, 29(7): 1157-1166.

ZHANG W Z, FANG B X, HU M Z, et al. A trust-QoS enhanced grid service scheduling [J]. Chinese Journal of Computers, 2006, 29(7): 1157-1166.

[20] MANKIW N G. Teaching the principles of economics [J]. Eastern Economic Journal, 1998, 24(4): 519-524.

[21] 骆品亮.定价策略[M]. 上海:上海财经大学出版社, 2013. 19-22. LUO P L. Pricing strategy. Shanghai: Shanghai University of Finance and Economics Press, 2013. 19-22.

[22] VARIAN H R. Microeconomic analysis[M]. New York: W.W. Norton & Company, 1992.

[23] MediaWiki. Grid5000: Home[EB/OL]. https://www.grid5000.fr/ mediawiki/index.php/Grid5000:Home.

[24] SMITH R, DAVIS R. The contract net protocol: high level communication and control in a distributed problem solver [J]. IEEE Transactions on Computers, 1980, 29(12): 1104-1113.

[25] MCKNIGHT L W, BOROUMAND J. Pricing internet service: approaches and challenges [J]. IEEE Computer, 2000, 33(2): 128-129.

Self-adaptive price adjustment strategy based on market mechanism in distributed environment

DING Chang-song1,2, WANG Zhi-ying1, HU Zhi-gang3

(1. College of Computer, National University of Defense Technology, Changsha 410073, China; 2. School of Management and Information Engineering, Hunan University of Chinese Medicine, Changsha 410208, China; 3. School of Software, Central South University, Changsha 410083, China)

To solve the resource pricing problem of the collision among resource utilization, price and benefits in distributed computing environments, a self-adaptive pricing strategy of resource services based on market mechanism was proposed. On the premise of the local resource benefits, this adaptive pricing strategy guaranteed the resource to self-adapt the price dynamically so as to balance the collision between the assigned tasks on the resource node and the benefits of the resource provider. The theoretical analysis proved the effectiveness of the pricing strategy, and the algorithm of the pricing strategy was designed. Resources node information in the real distributed systems was used as the performance parameters of experimental node in the simulation experiments, and the performance of the adaptive pricing strategy was tested in a large-scale grid mission. Experimental results show that, compared with the traditional pricing strategies, the adaptive pricing strategy based on market mechanism has vastly superior performance on the resource benefits and the balance of resource utilization.

distributed computing, market mechanism, self-adaptive, price adjustment strategy

TP393

A

10.11959/j.issn.1000-436x.2016027

2015-05-20；

2016-01-05

国家自然科学基金资助项目（No.81573985）；湖南省科技厅基金资助项目（No.2011RS4025, No.2013GK3143）；湖南省教育厅优秀青年基金资助项目（No.13B079）

The National Natural Science Foundation of China (No.81573985),The Science and Technology Projects Fund of Hunan Province (No.2011RS4025, No.2013GK3143), Scientific Research Fund for Outstanding Young Teachers of Hunan Provincial Education Department (No.13B079)

丁长松（1975-），男，湖南汉寿人，湖南中医药大学副教授、硕士生导师，主要研究方向为云计算、中医药信息化。

王志英（1956-），男，山西长治人，国防科技大学教授、博士生导师，主要研究方向为计算机系统结构。

胡志刚（1963-），男，山西孝义人，中南大学教授、博士生导师，主要研究方向为网络并行计算、嵌入式系统、网络安全。