The Value of Cooperation: Minimizing User Costs in Multi-Broker Mobile Cloud Computing Networks

摘要

We study the problem of user cost minimization in mobile cloud computing (MCC) networks. We consider a MCC model where multiple brokers assign cloud resources to mobile users. The model is characterized by an heterogeneous cloud architecture (which includes a public cloud and a cloudlet) and by the heterogeneous pricing strategies of cloud service providers. In this setting, we investigate two classes of cloud reservation strategies, i.e., a competitive strategy, and a compete-then-cooperate strategy as a performance bound. We first study a purely competitive scenario where brokers compete to reserve computing resources from remote public clouds (which are affected by long delays) and from local cloudlets (which have limited computational resources but short delays). We provide theoretical results demonstrating the existence of disagreement points (i.e., the equilibrium reservation strategy that no broker has incentive to deviate unilaterally from) and convergence of the best-response strategies of the brokers to disagreement points. We then consider the scenario in which brokers agree to cooperate in exchange for a lower average cost of resources. We formulate a cooperative problem where the objective is to minimize the total average price of all brokers, under the constraint that no broker should pay a price higher than the disagreement price (i.e., the competitive price). We design new globally optimal solution algorithm to solve the resulting non-convex cooperative problem, based on a combination of the branch and bound framework and of advanced convex relaxation techniques. The resulting optimal solution provides a lower bound on the achievable user cost without complete collusion among brokers. Compared with pure competition, we found that (i) noticeable cooperative gains can be achieved over pure competition in markets with a few brokers only, and (ii) the cooperative gain is only marginal in crowded markets, i.e., with a high number of brokers, hence there is no clear incentive for brokers to cooperate.