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

Pricing Mechanism of TSP Solving Service in Cloud Computing

作　　者：曾栩鸿[1] 曾国荪[2] 

机构地区：[1]同济大学计算机科学与技术系,上海200092 [2]国家高性能计算机工程技术中心同济分中心,上海201804

出　　处：《计算机科学》2011年第12期194-199,共6页Computer Science

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

摘　　要：旅行商问题(TSP)是一个典型的路径优化问题,在城市交通规划、物流运输、通信网络设置等领域都存在类似的问题和应用。但是,TSP问题的求解是NP难的,当问题规模很大时,必须借助大规模并行计算环境,例如云计算平台,以较大的计算开销来获得可行解。以TSP问题为具体实例,研究云计算服务的定价机制。一般情况下,定价机制要满足公平、灵活、动态、自适应。从公平合理角度来看,影响计算服务定价的因素主要有两方面:一是求解问题的难度,包括计算时间复杂性、空间复杂性、输入输出数据规模等;二是求解服务质量,即服务契约,包括可以作为服务等级协定指标的求解精度、响应时间、资源要求等。由此,提出了一种新的云计算中的服务定价机制:CloudPricing。该机制给出了服务定价的一般和具体原则,并给出了相应的定价公式。针对TSP问题求解,进行了具体的定价实例分析,这对云计算中NP难问题求解服务的定价有参考意义。The traveling salesman problem（TSP） is a typical path optimization problem which has similar problems and applications in urban transportation planning, logistic transport and communication network settings. However,TSP is a NP hard problem. When problem scale is very large, large scale parallel computing environment such as cloud computing platform is needed. In this paper, we illustrated cloud service pricing mechanism with TSP. Generally, pricing mechanism should be fair, flexible, dynamic and flexible. To be fair and reasonable, there are two main aspects to be considered when pricing a service. One is the difficulty of solving the problem including time complexity, space complexity and quantity of data the application input and output. The other is the quality of service including precision of the result, re- sponse time and whether the service is provided in peak time or not which can be served for Service Level Agreemenl between service provider and customer. Next, we proposed principles of pricing the service and pricing formula. Finally, a case study aiming at pricing solving TSP service was given, which has a reference value for pricing NP hard problem in cloud computing environment.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]