An Online Algorithm for Task Offloading in Heterogeneous Mobile Clouds

摘要

Mobile cloud computing is emerging as a promising approach to enrich user experiences at the mobile device end. Computation offloading in a heterogeneous mobile cloud environment has recently drawn increasing attention in research. The computation offloading decision making and tasks scheduling among heterogeneous shared resources in mobile clouds are becoming challenging problems in terms of providing global optimal task response time and energy efficiency. In this article, we address these two problems together in a heterogeneous mobile cloud environment as an optimization problem. Different from conventional distributed computing system scheduling problems, our joint offloading and scheduling optimization problem considers unique contexts of mobile clouds such as wireless network connections and mobile device mobility, which makes the problem more complex. We propose a context-aware mixed integer programming model to provide off-line optimal solutions for making the offloading decisions and scheduling the offloaded tasks among the shared computing resources in heterogeneous mobile clouds. The objective is to minimize the global task completion time (i.e., makespan). To solve the problem in real time, we further propose a deterministic online algorithm-the Online Code Offloading and Scheduling (OCOS) algorithm-based on the rent/buy problem and prove the algorithm is 2-competitive. Performance evaluation results show that the OCOS algorithm can generate schedules that have around two times shorter makespan than conventional independent task scheduling algorithms. Also, it can save around 30% more on makespan of task execution schedules than conventional offloading strategies, and scales well as the number of users grows.