Truthful Online Combinatorial Auction-Based Mechanisms for Task Offloading in Mobile Edge Computing
Xueyi Wang, Xingwei Wang, Chen Wang, Rongfei Zeng, Lianbo Ma, Qiang He, Min Huang
Abstract
Mobile edge computation (MEC) is envisioned as a prospective approach for processing the computation-intensive and delay-sensitive tasks of smart mobile devices (SMDs) through offloading them to base stations (BSs) nearby. In fact, efficient task offloading mechanisms are crucial to accomplish an MEC system. The key challenge is to make on-spot decisions upon the arrival of each task and at the same time achieve truthfulness of each SMD. The challenge further escalates, when the unique characteristics of an MEC system, such as locality constraint, delay constraint, etc., are explicitly considered. To solve the challenge, we present a truthful online combinatorial auction-based mechanism (TOCA) for task offloading in an MEC system. Specifically, we first devise the candidate offloading scheme determination algorithm, aiming to determine the candidate offloading schemes of an SMD upon the arrival of its task. Next, we devise the winning offloading scheme selection and pricing algorithm based on the online primal-dual optimization framework, to decide the winning scheme among the SMD's candidate offloading schemes and calculate its payment. By solid theoretical analysis, we verify that TOCA achieves truthfulness, individual rationality and computational efficiency and a smaller competitive ratio. Trace-driven simulation studies validate the effectiveness and efficacy of TOCA.