云计算市场中激励相容的实时拍卖系统设计

摘要

随着云计算的广泛应用,关于云计算资源分配算法研究—如何让云资源提供商有效地将云资源分配给潜在的云用户—引起了学界的广泛关注。拍卖式的资源定价方法,由于能够有效的反映用户的供求关系,在最近一些关于云市场的资源分配算法研究中被广泛地采用。然而,通过对已有的云计算市场中拍卖式的资源分配与定价算法的调查研究,我们发现目前的算法设计中往往有以下的一些通病:(1)无法实时的反映资源供求关系的动态变化;(2)无法表达进而满足用户对于云资源的多样化需求;(3)容易受用户欺骗行为的影响。
　　针对以上提到的这些问题,本文对云计算市场中如何对云资源进行动态有效的分配的问题进行了深入地研究,并设计了第一个针对多种不同用户需求的实时云资源拍卖系统。该系统很好地满足了以下一系列的设计需求:(1)满足实时性,使得卖家能够根据变化的供求关系灵活地对资源进行有效的配置;(2)支持用户需求的多样性,使得不同种类的买家(用户)能够有效地反映自己对于云资源的不同需求;(3)保证激励相容性,使得该实时拍卖系统能够有效防止用户的欺骗策略。具体地说,我们首先提出了一个新颖的拍卖语言,可以将各种各样的用户需求转化为有着简单而统一形式的拍卖请求。在该拍卖语言的基础上,我们设计了一个激励相容的实时拍卖算法,COCA。除了保证激励相容性,我们还通过理论分析证明了COCA可以获得很好的资源分配效率下界。此外,我们还对COCA算法在其他一些重要性能指标下的性能做了全面的讨论。最后,实验结果表明了COCA算法能够在一般情况下获得良好的资源分配效率。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景

1.2 云计算中动态资源分配方法研究现状

1.3 研究意义与研究内容

1.4 论文结构

2 拍卖模型与拍卖语言设计

2.1 云计算市场中的实时拍卖模型设计

2.2 针对不同用户需求的拍卖语言设计

2.3 拍卖算法的性能标准

3 拍卖算法设计：激励相容性的保证

3.1 云市场中激励相容性拍卖算法设计面临的挑战

3.2 保证激励相容性的算法设计准则

3.3 COCA：激励相容的实时拍卖算法设计

3.4 COCA激励相容性的证明

4 拍卖算法设计：资源分配效率竞争比率的保证

4.1 针对单一用户类型的竞争比率分析

4.2 针对混合用户类型的竞争比率分析

5 针对COCA算法的多方面性能分析

5.1 针对COCA算法的计算复杂度分析

5.2 针对其他用户策略性行为的分析

6 实验仿真

6.1 参数设定

6.2 实验结果

6.3 实验总结

7 总结

致谢

参考文献

附录1 部分定理的详细证明

附录2 攻读学位期间的主要成果和奖励