云计算中TSP问题求解服务的定价机制

摘要：

旅行商问题(TSP)是一个典型的路径优化问题,在城市交通规划、物流运输、通信网络设置等领域都存在类似的问题和应用.但是,TSP问题的求解是NP难的,当问题规模很大时,必须借助大规模并行计算环境,例如云计算平台,以较大的计算开销来获得可行解.以TSP问题为具体实例,研究云计算服务的定价机制.一般情况下,定价机制要满足公平、灵活、动态、自适应.从公平合理角度来看,影响计算服务定价的因素主要有两方面:一是求解问题的难度,包括计算时间复杂性、空间复杂性、输入输出数据规模等；二是求解服务质量,即服务契约,包括可以作为服务等级协定指标的求解精度、响应时间、资源要求等.由此,提出了一种新的云计算中的服务定价机制:CloudPricing.该机制给出了服务定价的一般和具体原则,并给出了相应的定价公式.针对TSP问题求解,进行了具体的定价实例分析,这对云计算中NP难问题求解服务的定价有参考意义.

关键词：云计算、TSP问题、求解服务、定价机制、服务等级协定

所属期刊栏目：38

分类号：TP1;TP3

资助基金：863项目2007AA01Z425;973计划课题2007CB316502;国家自然基金项目90718015;NSFC-微软亚洲研究院联合资助项目60970155;教育部博士点基金项目20090072110035;上海市优秀学科带头人计划项目10XD1404400;高效能服务器和存储技术国家重点实验室开放基金项目2009HSSA06

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：194-199