Towards truthful auction mechanisms for task assignment in mobile device clouds

Abstract

Despite the increased capabilities of mobile devices, resource-demanded mobile applications still transcend what can be accomplished on a single device. As such, mobile device cloud (MDC), an environment that enables computation-intensive tasks to be performed among a set of nearby mobile devices, offers a promising architecture to support real-time mobile applications. To stimulate mobile devices to execute tasks for others, it is essential to design an incentive mechanism that appropriately charges the owners of the tasks, acted as the buyers, and rewards the mobile devices, acted as the sellers. In this paper, we propose two truthful auction mechanisms for two different task models, heterogeneous and homogeneous task models, which assume the different and the same resource requirements of the tasks, respectively. Specifically, for heterogeneous task model, we propose an efficient heuristic winning bids determination algorithm to allocate the tasks, and decide the payment of each seller for its winning bids. For homogeneous task model, we design an optimal winning bid determination algorithm, and propose a Vickrey-Clarke-Groves (VCG) based auction mechanism to determine the payment of each bid. Both theoretical analysis and simulations show that the proposed auction mechanisms achieve several desirable properties such as individual rationality, truthfulness and computational efficiency.