云计算是一种通过网络提供计算服务的模式,其主要特点是按需使用,随时扩展和按使用付费。“基础设施即服务”服务模式下,云计算基础设施软件厂商将底层资源(CPU、内存等)封装成不同形式的虚拟机,并以虚拟机的形式用户提供服务。如何合理有效地分配云资源,为云资源提供商和云计算用户带来价值收益,具有重大的经济意义。合理高效地分配云资源并制定价格策略是云计算领域的一个研究热点。以最大化社会价值量为目标分配资源和以临界点价值定价资源是两种主要的思路。其中,算法博弈论和拍卖理论为其能够研究具有“个体理性”和“激励相容”等属性的云资源分配机制提供了新思路。近年来,启发式算法确定赢者集的运用引起了广泛关注,在这一背景下,本文针对云环境下虚拟机资源分配与定价机制问题进行了研究,具体贡献如下:基于动态规划的虚拟机分配方法研究。针对离线拍卖环境下的虚拟机分配问题,我们以最大化社会价值量为目标函数,使用动态规划算法求解整体最优分配问题,并使用VCG机制对资源定价。通过理论分析证明拍卖机制能同时实现个体理性,动机相容性和计算复杂性等重要的经济属性。此外,通过大量的模拟实验来验证此方案具备良好的云资源分配效率,能为云提供商和云用户带来更高的收益。基于XOR标集的虚拟机分配问题研究。我们考虑复杂用户集,即每场拍卖下,用户为了获得资源可以提交多个投标请求,但拍卖商对每个用户最多只应允一个投标。我们引入XOR投标语言,改进了基于局部搜索算法爬山法对资源进行分配,并使用改进的VCG机制计算虚拟机资源的价格。这种机制允许用户充分的表达投标意愿,用户体验度高,模拟实验表明,这种拍卖机制能够为拍卖商带来更高的收益,同时给用户带来更高的生产效用。在线虚拟机拍卖机制中基于市场感知的分配方法研究。我们改进了基于虚拟机分配的在线拍卖机制,在机制的分配方案中考虑了高峰期和低谷期需求量的变化,使得拍卖商能动态的衡量不同时刻下用户的投标密度,更为合理的决策出赢者集,提高资源使用率,并为拍卖商带来更高的利润。我们尝试使用真实的工作量档案进行了大量的模拟实验来验证改进的在线拍卖机制的有效性。