论文部分内容阅读
云计算是继分布式计算、网格计算和对等计算之后的一种新型的通过互联网提供服务的计算模式，其主要特点是按需使用、随时扩展和按使用付费。云提供者将底层计算资源(CPU、内存和存储等)配置成不同类型的虚拟机(Virtual Machine，VM)实例，并以VM实例的形式提供给云用户使用。然而，云计算资源的海量性、异构性和动态性等特点使得云计算资源分配变得更加复杂。如何合理而有效地将云计算资源分配给云用户达到社会效益最大化成为当前云计算研究领域的一个热点和难点。
许多云提供者采用基于固定价格的机制来分配云资源，但是这些机制均属于静态的定价机制，因此，它们是经济无效的。相反，基于拍卖的云资源分配机制是经济有效的，属于动态的定价机制。拍卖能够根据资源的供需关系动态地形成均衡的市场价格，能够应对参与者多种多样的利益冲突，能够使参与者做出独立的决定。另外，在基于拍卖的云资源分配机制中，胜标确定问题(Winner Determination Problem，WDP)通常是一个NP难问题，具有较高的计算复杂度。由于启发式算法具有直观、简单易行和速度快等特点，并且在处理大规模的问题实例时能够在一个合理的时间范围内获得比较满意的解。因此，本文采用启发式算法来求解云资源分配过程中的WDP。
针对IaaS(Infrastructure as a Service)类型服务，研究了拍卖理论在云资源分配领域中的应用，根据不同的应用场景分别将反向拍卖、组合拍卖、组合双向拍卖和团购拍卖引入到云资源分配机制中，分别设计了三种启发式算法(贪心启发算法、多目标粒子群优化算法和自适应差分进化算法)来求解云资源分配过程中的WDP，以期获得更佳的资源分配效果。本文的主要研究内容如下:
基于多属性反向Vickrey拍卖的云资源分配机制。在云市场中，云用户在采购云计算资源来完成任务时，无法充分了解云提供者的可靠性。为了解决这一问题，考虑云提供者多方面属性的可靠性(云资源提供量的可靠性和提供服务质量(QualityofService，QoS)指标值的可靠性)，设计一种新颖的信誉方案来计算云提供者的综合信誉。为了有利于云提供者充分发挥各自竞争的优势，充分满足云用户多样化的个性需求，设计了一种基于多属性反向Vickrey拍卖的云资源分配(Multi-Attribute Reverse Vickrey Auction-based Cloud Resource Allocation，MARVA-CRA)机制。该机制在确定胜标云提供者时，不仅考虑价格属性，而且也考虑非价格属性，例如云资源的提供量、QoS指标(例如响应时间、可用性等)以及云提供者的综合信誉，通过综合评价云提供者的多种属性来确定胜标的云提供者。同时，还考虑到云提供者实际提供的计算资源数量和QoS指标值可能与承诺的不符。为了弥补由于云提供者的违约而给云用户所带来的损失，提出了一种惩罚机制来减少支付给云提供者的费用，从而保证云用户的效用不会受到损失。实验结果表明，本文所提出的信誉方案可以有效地确定云提供者的可靠性。同时，MARVA-CRA机制，不仅可以保证云提供者真实地报价，而且也有效地避免了云用户的效用因云提供者的违约而受到损失。
基于组合拍卖的云资源分配机制。现有的基于组合拍卖的云资源分配机制存在以下不足:(1)云提供者未考虑云用户的实际需求，预先定义提供的VM实例的类型及相应类型VM实例的数量，从而导致了云提供者的资源利用率较低。(2)现有的基于贪心启发算法的分配机制在计算标书密度时没有合理地处理异构VM实例在资源构成和价格上的巨大差异，从而导致资源分配机制性能较差。(3)在资源分配和定价过程中忽略了VM实例的保留价格，可能会造成云提供者的效用降低。针对以上问题，提出了两种基于组合拍卖的云资源分配机制，即基于Vickrey-Clarke-Groves的云资源分配(Vickrey-Clarke-Groves based Cloud Resource Allocation，VCG-CRA)机制和基于贪心启发算法的云资源分配(Greedy Heuristic Algorithm based Cloud Resource Allocation， GHA-CRA)机制。实验结果表明，VCG-CRA机制可以获得最大的社会效益，但是时间复杂度较高，不适用于实际应用场景。而GHA-CRA机制不仅可以保证所获得的社会效益非常接近于VCG-CRA机制所获得的社会效益，而且执行时间较短。
基于组合双向拍卖和信誉感知的云资源分配机制。为了能够营造一个健康的云市场环境，不仅要追求社会效益最大化，而且要鼓励参与者的诚信，提出了一种基于组合双向拍卖和信誉感知的云资源分配(Combinatorial Double Auction-based and Reputation-Aware Cloud Resource Allocation，CDARA-CRA)机制。在该机制中，为了解决参与者之间信息不对称而导致的交易中不诚实行为的问题，首先，设计了一种信誉方案来计算参与者的信誉。然后，设计了一个基于随机森林的价格预测算法来获得合理的云用户的报价和云提供者的要价。在此基础上，将云资源分配问题归纳为一个多目标优化问题，不仅考虑两个冲突的目标(最大化社会效益和最大化总的期望信誉)，而且允许一个云用户的请求可以由一个云提供者单独满足或多个云提供者共同满足。最后，为了解决该机制中的WDP，设计了一种基于改进的多目标粒子群优化算法的胜标确定机制来获得该问题的近似最优帕累托解集，并利用逼近于理想解的排序技术(Technique for Order Performance by Similarity to Ideal Solution，TOPSIS)来选择最佳的折衷解。实验结果表明，该机制是可行并且有效的，不仅改善了社会效益，而且提高了总的期望信誉。
基于团购拍卖的动态云资源配置与分配机制。为了使云提供者能够聚合更多的云用户需求而从中获利，同时使云用户能够以比自己单独购买时更低的价格购买所需要的云计算资源，提出了一种基于团购拍卖的动态云资源配置与分配(Group-Buying Auction-based Dynamic Cloud Resource Provisioning and Allocation，GBA-DCRPA)机制。该机制不需要云提供者预先配置各种类型的VM实例，允许云提供者根据云用户的实际需求动态地配置各种类型的VM实例。为了使该机制更加适合实际的云环境，该机制考虑云市场中存在多个支持团购策略的云提供者，并且允许云用户的需求可以由一个云提供者单独满足或多个云提供者共同满足。另外，为了解决该机制中的WDP，提出了一种基于自适应的差分进化算法的胜标确定机制来计算该问题的近似最优解。实验结果表明，该机制可以改善社会效益、提高云提供者的资源利用率以及改善了任务完成数。
许多云提供者采用基于固定价格的机制来分配云资源，但是这些机制均属于静态的定价机制，因此，它们是经济无效的。相反，基于拍卖的云资源分配机制是经济有效的，属于动态的定价机制。拍卖能够根据资源的供需关系动态地形成均衡的市场价格，能够应对参与者多种多样的利益冲突，能够使参与者做出独立的决定。另外，在基于拍卖的云资源分配机制中，胜标确定问题(Winner Determination Problem，WDP)通常是一个NP难问题，具有较高的计算复杂度。由于启发式算法具有直观、简单易行和速度快等特点，并且在处理大规模的问题实例时能够在一个合理的时间范围内获得比较满意的解。因此，本文采用启发式算法来求解云资源分配过程中的WDP。
针对IaaS(Infrastructure as a Service)类型服务，研究了拍卖理论在云资源分配领域中的应用，根据不同的应用场景分别将反向拍卖、组合拍卖、组合双向拍卖和团购拍卖引入到云资源分配机制中，分别设计了三种启发式算法(贪心启发算法、多目标粒子群优化算法和自适应差分进化算法)来求解云资源分配过程中的WDP，以期获得更佳的资源分配效果。本文的主要研究内容如下:
基于多属性反向Vickrey拍卖的云资源分配机制。在云市场中，云用户在采购云计算资源来完成任务时，无法充分了解云提供者的可靠性。为了解决这一问题，考虑云提供者多方面属性的可靠性(云资源提供量的可靠性和提供服务质量(QualityofService，QoS)指标值的可靠性)，设计一种新颖的信誉方案来计算云提供者的综合信誉。为了有利于云提供者充分发挥各自竞争的优势，充分满足云用户多样化的个性需求，设计了一种基于多属性反向Vickrey拍卖的云资源分配(Multi-Attribute Reverse Vickrey Auction-based Cloud Resource Allocation，MARVA-CRA)机制。该机制在确定胜标云提供者时，不仅考虑价格属性，而且也考虑非价格属性，例如云资源的提供量、QoS指标(例如响应时间、可用性等)以及云提供者的综合信誉，通过综合评价云提供者的多种属性来确定胜标的云提供者。同时，还考虑到云提供者实际提供的计算资源数量和QoS指标值可能与承诺的不符。为了弥补由于云提供者的违约而给云用户所带来的损失，提出了一种惩罚机制来减少支付给云提供者的费用，从而保证云用户的效用不会受到损失。实验结果表明，本文所提出的信誉方案可以有效地确定云提供者的可靠性。同时，MARVA-CRA机制，不仅可以保证云提供者真实地报价，而且也有效地避免了云用户的效用因云提供者的违约而受到损失。
基于组合拍卖的云资源分配机制。现有的基于组合拍卖的云资源分配机制存在以下不足:(1)云提供者未考虑云用户的实际需求，预先定义提供的VM实例的类型及相应类型VM实例的数量，从而导致了云提供者的资源利用率较低。(2)现有的基于贪心启发算法的分配机制在计算标书密度时没有合理地处理异构VM实例在资源构成和价格上的巨大差异，从而导致资源分配机制性能较差。(3)在资源分配和定价过程中忽略了VM实例的保留价格，可能会造成云提供者的效用降低。针对以上问题，提出了两种基于组合拍卖的云资源分配机制，即基于Vickrey-Clarke-Groves的云资源分配(Vickrey-Clarke-Groves based Cloud Resource Allocation，VCG-CRA)机制和基于贪心启发算法的云资源分配(Greedy Heuristic Algorithm based Cloud Resource Allocation， GHA-CRA)机制。实验结果表明，VCG-CRA机制可以获得最大的社会效益，但是时间复杂度较高，不适用于实际应用场景。而GHA-CRA机制不仅可以保证所获得的社会效益非常接近于VCG-CRA机制所获得的社会效益，而且执行时间较短。
基于组合双向拍卖和信誉感知的云资源分配机制。为了能够营造一个健康的云市场环境，不仅要追求社会效益最大化，而且要鼓励参与者的诚信，提出了一种基于组合双向拍卖和信誉感知的云资源分配(Combinatorial Double Auction-based and Reputation-Aware Cloud Resource Allocation，CDARA-CRA)机制。在该机制中，为了解决参与者之间信息不对称而导致的交易中不诚实行为的问题，首先，设计了一种信誉方案来计算参与者的信誉。然后，设计了一个基于随机森林的价格预测算法来获得合理的云用户的报价和云提供者的要价。在此基础上，将云资源分配问题归纳为一个多目标优化问题，不仅考虑两个冲突的目标(最大化社会效益和最大化总的期望信誉)，而且允许一个云用户的请求可以由一个云提供者单独满足或多个云提供者共同满足。最后，为了解决该机制中的WDP，设计了一种基于改进的多目标粒子群优化算法的胜标确定机制来获得该问题的近似最优帕累托解集，并利用逼近于理想解的排序技术(Technique for Order Performance by Similarity to Ideal Solution，TOPSIS)来选择最佳的折衷解。实验结果表明，该机制是可行并且有效的，不仅改善了社会效益，而且提高了总的期望信誉。
基于团购拍卖的动态云资源配置与分配机制。为了使云提供者能够聚合更多的云用户需求而从中获利，同时使云用户能够以比自己单独购买时更低的价格购买所需要的云计算资源，提出了一种基于团购拍卖的动态云资源配置与分配(Group-Buying Auction-based Dynamic Cloud Resource Provisioning and Allocation，GBA-DCRPA)机制。该机制不需要云提供者预先配置各种类型的VM实例，允许云提供者根据云用户的实际需求动态地配置各种类型的VM实例。为了使该机制更加适合实际的云环境，该机制考虑云市场中存在多个支持团购策略的云提供者，并且允许云用户的需求可以由一个云提供者单独满足或多个云提供者共同满足。另外，为了解决该机制中的WDP，提出了一种基于自适应的差分进化算法的胜标确定机制来计算该问题的近似最优解。实验结果表明，该机制可以改善社会效益、提高云提供者的资源利用率以及改善了任务完成数。