AUCTION-BASED RESOURCE ALLOCATION FOR SHARING CLOUDLETS IN MOBILE CLOUD COMPUTING
Driven by pervasive mobile devices and ubiquitous wireless communication networks, mobile cloud computing emerges as an appealing paradigm to accommodate demands for running power-hungry or computation-intensive applications over resource-constrained mobile devices. Cloudlets that move available resources closer to the network edge offer a promising architecture to support real-time applications, such as online gaming and speech recognition. To stimulate service provisioning by cloudlets, it is essential to design an incentive mechanism that charges mobile devices and rewards cloudlets. Although auction has been considered as a promising form for incentive, it is challenging to design an auction mechanism that holds certain desirable properties for the cloudlet scenario. In this paper, we propose an incentive-compatible auction mechanism (ICAM) for the resource trading between mobile devices as service users (buyers) and cloudlets as service providers (sellers). ICAM can effectively allocate cloudlets to satisfy the service demands of mobile devices and determine the pricing. Both theoretical analysis and numerical results show that ICAM guarantees desired properties with respect to individual rationality, budget balance, truthfulness (incentive compatibility) for both buyers and sellers, and computational efficiency.
Index Terms—Mobile cloud computing, cloudlet, truthful double auction, incentive design.
The past decade has witnessed an explosive growth of wireless communication networks, where a variety of smart mobile devices offer a plethora of applications. Nonetheless, the energy and resource constraints of mobile devices still limit the support of power-hungry or computation-intensive applications, even with the rapid progress of hardware technologies. In the mean time, cloud computing is achieving great success in empowering end users with rich experience by leveraging resource virtualization and sharing. Extending the success of cloud computing to the mobile domain, mobile cloud computing (MCC) creates a new appealing paradigm. There have been many popular cloud-based mobile applications, e.g., deployed in Apple iCloud and Amazon Silk. By offloading power-hungry or computation-intensive tasks to clouds, MCC is expected to relax the local constraints of mobile devices in storage, energy, and networking. Three typical MCC architectures are reviewed in, including the traditional centralized cloud, the recently emerged cloudlet, and the peer-based ad hoc mobile cloud. The ad hoc mobile cloud is a user-centric model which pools together a crowd of neighboring mobile devices for resource sharing. The other two larger-scale cloud architectures are illustrated in The centralized cloud hosts shared resources in remote data centers and acts as an agent between the original content providers and mobile devices. To access resources at the data centers, mobile devices often need to go through the backbone network. The long latency incurred to access the centralized cloud can be intolerable for interactive applications such as online gaming and speech recognition. Even with the acceleration of network speeds, the network resources will remain insufficient in a fairly long period to accommodate the soaring traffic demands. On the other hand, a cloudlet is a trusted, resource-rich, Internet-connected computer or a cluster of computers, which can be utilized by mobile devices via a high-speed wireless local area network (WLAN). With such geographically distributed cloudlets, the close physical proximity can enable smoother interactions with the low one-hop communication latency. Thus, cloudlets offer an economical solution which can take advantage of content distribution close to the network edge.
In this section, we give a brief review on related works in two groups, i.e., the incentive mechanisms specifically for mobile cloud computing in the networking literature, and more general auction mechanisms in the economics literature. As a promising paradigm, mobile cloud computing has attracted considerable research attention and efforts. There have been a number of studies addressing various aspects of MCC, such as virtual machine migration, service enhancement with MCC, and emerging applications with MCC. However, the research on incentive design for MCC is limited. In, cloud resources are categorized into several groups (e.g., processing, storage, and communications). Then, the resource allocation problem is formulated as a combinatorial auction with substitutable and complementary commodities. This combinatorial auction mechanism is not applicable for the cloudlet architecture since its key problem is the allocation of M resources of G groups in one MCC service provider to N users. In contrast, our system model with cloudlets focuses on distinct valuations of cloudlets to mobile users. we also consider computational efficiency and budget balance, which are critical to an auction mechanism. Although auction theory has been widely studied in the economics literature, the existing auction mechanisms cannot be directly applied to the cloudlet scenario, since they fail to fully satisfy the required properties stated in Section I. One of the most well-known auction mechanisms is the truthful Vickrey- Clarke-Groves (VCG) auction. In, Parkes et al. propose a Vickrey-based double auction, which achieves individual rationality and budget balance. The assignment between buyers and sellers is determined to maximize social welfare (system efficiency), while the player’s utility equals the incremental contribution to the overall system, i.e., the difference between the social welfare with and without a player’s participation. However, the well-known result in reveals that it is impossible to design a truthful, efficient, and budget-balanced double auction, even putting individual rationality aside. Therefore, the Vickrey-based double auction in is only fairly efficient and fairly truthful.
In this paper, we focus on a promising paradigm of MCC with cloudlets that provide resources to nearby mobile devices. Due to spatial locations of cloudlets and their distinct capabilities or hosted resources, the cloudlets offer heterogeneous valuations toward mobile devices. The mobile users can acquire services from different cloudlets to maximize their utilities. To improve resource utilization of cloudlets, we have proposed a double auction mechanism ICAM, which coordinates the resource trading between mobile devices as service users (buyers) and cloudlets as service providers (sellers). ICAM can effectively allocate the cloudlets’ resources among mobile users to satisfy their service demands, while maintaining the desirable properties, including computational efficiency, individual rationality, budget balance, and truthfulness for both buyers and sellers. We have provided rigorous proof on these properties of ICAM and confirmed the analysis with extensive simulation results.
 H. Dinh, C. Lee, D. Niyato, and P. Wang, “A survey of mobile cloud computing: Architecture, applications, and approaches,” Wireless Communications and Mobile Computing, vol. 13, pp. 1587–1611, 2013.
 N. Fernando, S. W. Loke, and W. Rahayu, “Mobile cloud computing: A survey,” Future Generation Computer Systems, vol. 29, pp. 84–106, 2013.
 Apple Inc., “Apple iCloud,” https://www.icloud.com/.
 Amazon.com, “Amazon Silk,” http://amazonsilk.wordpress.com/.  S. Abolfazli, Z. Sanaei, E. Ahmed, A. Gani, and R. Buyya, “Cloudbased augmentation for mobile devices: Motivation, taxonomies, and open challenges,” IEEE Communications Surveys & Tutorials, vol. 16, no. 1, pp. 337–368, 2014.
 F. Liu, P. Shu, H. Jin, L. Ding, J. Yu, D. Niu, and B. Li, “Gearing resource-poor mobile devices with powerful clouds: Architectures, challenges, and applications,” IEEE Wireless Communications, vol. 20, no. 3, pp. 14–22, Jun. 2013.
 Z. Liu, Y. Feng, and B. Li, “Socialize spontaneously with mobile applications,” in Proc. IEEE INFOCOM, 2012, pp. 1942–1950.
 M. Satyanarayanan, P. Bahl, R. Caceres, and N. Davies, “The case for VM-based cloudlets in mobile computing,” IEEE Pervasive Computing, vol. 8, no. 4, pp. 14–23, 2009.
 D. Huang, T. Xing, and H. Wu, “Mobile cloud computing service models: A user-centric approach,” IEEE Communications Surveys & Tutorials, vol. 27, no. 5, pp. 6–11, 2013.
 V. Krishna, Auction Theory, 2nd ed. Academic Press, Aug. 2009.
 Y. Zhang, C. Lee, D. Niyato, and P. Wang, “Auction approaches for resource allocation in wireless systems: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, no. 3, pp. 1020–1041, 2013