Tsinghua Science and Technology


cloud computing, coalition formation, combinatorial auction, ant colony algorithm, communication cost


In this paper, we present a novel, dynamic collaboration cloud platform in which a Combinatorial Auction (CA)-based market model enables the platform to run effectively. The platform can facilitate expense reduction and improve the scalability of the cloud, which is divided into three layers: The user-layer receives requests from end-users, the auction-layer matches the requests with the cloud services provided by the Cloud Service Provider (CSP), and the CSP-layer forms a coalition to improve serving ability to satisfy complex requirements of users. In fact, the aim of the coalition formation is to find suitable partners for a particular CSP. However, identifying a suitable combination of partners to form the coalition is an NP-hard problem. Hence, we propose approximation algorithms for the coalition formation. The Breadth Traversal Algorithm (BTA) and Revised Ant Colony Algorithm (RACA) are proposed to form a coalition when bidding for a single cloud service in the auction. The experimental results show that RACA outperforms the BTA in bid price. Other experiments were conducted to evaluate the impact of the communication cost on coalition formation and to assess the impact of iteration times for the optimal bidding price. In addition, the performance of the market model was compared to the existing CA-based model in terms of economic efficiency.


Tsinghua University Press