A DISTRIBUTED TRUTHFUL AUCTION MECHANISM FOR TASK ALLOCATION IN MOBILE CLOUD COMPUTING
In mobile cloud computing, offloading resource demanded applications from mobile devices to remote cloud servers can alleviate the resource scarcity of mobile devices, whereas long distance communication may incur high communication latency and energy consumption. As an alternative, fortunately, recent studies show that exploiting the unused resources of the nearby mobile devices for task execution can reduce the energy consumption and communication latency. Nevertheless, it is non-trivial to encourage mobile devices to share their resources or execute tasks for others. To address this issue, we construct an auction model to facilitate the resource trading between the owner of the tasks and the mobile devices participating in task execution. Specifically, the owners of the tasks act as bidders by submitting bids to compete for the resources available at mobile devices. We design a distributed auction mechanism to fairly allocate the tasks, and determine the trading prices of the resources. Moreover, an efficient payment evaluation process is proposed to prevent against the possible dishonest activity of the seller on the payment decision, through the collaboration of the buyers. We prove that the proposed auction mechanism can achieve certain desirable properties, such as computational efficiency, individual rationality, truthfulness guarantee of the bidders, and budget balance. Simulation results validate the performance of the proposed auction mechanism. Index Terms—Mobile cloud computing, incentive mechanism, auction, truthfulness, budget balance
While mobile devices have become increasingly ubiquitous in our daily life, they are seriously constrained by limited battery capacities and computation capabilities. To alleviate resource scarcity of mobile devices, one effective way is to offload their complex or resource-demanded tasks to remote cloud through pay as you go. However, such an approach may suffer large internet delay and high energy consumption, due to long distance communication. To address this issue, recent work proposes that utilizing the unused resources of the mobile devices in the proximity can achieve better system performance. For example, communications among the nearby mobile devices through WLAN/WiFi can significantly reduce the communication latency and network congestion. Nevertheless it is non-trivial to encourage mobile devices to share their mobile resources or execute tasks for others, as these actions may incur non-negligible inconvenience to themselves, e.g., performance degradation and battery outage.
In this section, we first introduce the auction model. Then, we formulate the problem and present its desirable properties. For easy understanding. In the proposed, only a few works have been published on designing incentive schemes to incentivize mobile devices to provide their unused resources or execute tasks offloaded from others. Specifically, proposes a reputation-based economic incentive model to stimulate the mobile devices to provide services with others. Based on the rating points recorded for the devices, the winning bids can then be selected. The work in imposes a bill backlog on each mobile device. When a device’s bill backlog is larger than a threshold, it will be unable to get extra services from others. Although the fairness of mobile devices can be achieved, the mobile devices are always forced to provide services to others, which might not be appealing to many mobile devices. constructs a Stackelberg game model to capture the interaction between the owner of the tasks (i.e., buyer) and the mobile devices that participate in task execution (i.e., sellers). By appropriately allocating the tasks and determining the payments of task executions, the Stackelberg equilibrium of the game can be achieved. Although this approach can benefit both the buyer and the sellers of mobile resources, it does not capture the preference of task execution. It is worth noting that tasks executed on different mobile devices may achieve different system performances, e.g., different completion time and communication latency. Under such a circumstance, different mobile devices should get different payments for their task executions. Moreover, the model in considers only a single buyer of mobile resources, which omits the competition among multiple buyers in a general model. proposes two truthful incentive mechanisms with auctions, which however requires a centralized auctioneer to make the auction decisions. It is particularly noted that the centralized auctioneer must hold the global knowledge of the mobile cloud system, which firstly is prone to expose the privacy of mobile users, and secondly incurs high update cost because of the dynamic nature of the smartphones.
In this paper, we consider mobile task allocation problem in mobile cloud computing. To incentivize the mobile devices to participate in task execution, we construct an auction model to facilitate the resource trading between the owner of the tasks and the mobile devices. Specifically, the owners of the tasks, acted as the buyers, submit bids to compete for the resources available at the mobile devices, acted as the sellers. A distributed auction mechanism is then designed to fairly allocate the tasks, and determine the trading prices of the resources. Furthermore, an efficient payment evaluation process is proposed to prevent against the possible dishonest activity of the seller on the payment decision, through the collaboration of the buyers. We prove that the proposed auction mechanism achieves certain desirable properties, including computational efficiency, individual rationality, truthfulness guarantee of submitted bids and the sellers, and budget balance. We also validate the performance of the proposed mechanism through simulations.
 J. Paczkowski, “iPhone owners would like to replace battery,” Available: http://digitaldaily.allthingsd.com/20090821/iphone-owners-wouldlike- toreplace- battery-att, Aug. 2009.
 A. P. Miettinen, and J. K. Nurminen, “Energy efficiency of mobile clients in cloud computing,” in Proceedings of the 2nd USENIX conference on hot topics in cloud computing, pp. 1–7, Berkeley, CA, USA, 2010.
 N. Balasubramanian, “Energy consumption in mobile phones: a measurement study and implications for network applications,” in Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference (IMC) pp. 280–293, Chicago, Illinois, USA, 2009.
 M. Satyanarayanan, “Fundamental challenges in mobile computing” in Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 1–7, Philttdelphia PA, USA, 1996.
 A. Khan, M. Othman, S. Madani and S. U. Khan, “A survey of mobile cloud computing application models,” IEEE Communications Surveys & Tutorials, vol. 16, no. 1, pp. 393–413, 2014.
 A. P. Miettinen and J. K. Nurminen, “Energy efficiency of mobile clients in cloud computing,” in Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, pp. 1–7, Boston, MA, 2010.
 E. Cuervo, A. Balasubramanian, D. Cho, A. Wolman, S. Saroiu, R. Chandra, and P. Bahl, “Maui: making smartphones last longer with code offload,” in Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services (ACM MobiSys), pp. 49–62, San Francisco, CA, USA, 2010.
 B. Chun, S. Ihm, P. Maniatis, M. Naik, and A. Patti, “Clonecloud: elastic execution between mobile device and cloud,” in Proceedings of the sixth Conference on Computer Systems (EuroSys), pp. 301–314, Salzburg, Austria, 2011.
 P. Shu, F. Liu, H. Jin, M. Chen, F. Wen, Y. Qu, B. Li, “eTime: Energyefficient transmission between cloud and mobile devices,” in Proceedings of IEEE International Conference on Computer Communications (INFOCOM), pp. 195–199, Turin, 2013.
 Y. Mao, C. You, J. Zhang, K. Huang and K. B. Letaief, “A survey on mobile edge computing: the communication perspective,” IEEE Communications Surveys & Tutorials, vol. 19, no. 4, pp. 2322–2358, 2017.
 X. Chen, L. Pu, L. Gao, W. Wu and D. Wu, “Exploiting massive D2D collaboration for energy-efficient mobile edge computing,” IEEE Wireless Communications, vol. 24, no. 4, pp. 64–71, 2017.
 M. Ra, A. Sheth, L. Mummert, P. Pillai, D. Wetherall, and R. Govindan, “Odessa: enabling interactive perception applications on mobile devices,” in Proceedings of the 9th international conference on Mobile systems, applications, and services (MobiSys), pp. 43–56, NY, USA, 2011.