Energy-Efficient Mapping and Scheduling of Task Interaction Graphs for Code Offloading in Mobile Cloud Computing

To reduce the energy consumption in mobile devices, intricate applications are divided into several interconnected partitions like Task Interaction Graph (TIG) and are of floaded to cloud resources or nearby surrogates. Dynamic Voltage and Frequency Scaling (DVFS) is an effective technique to reduce the power consumption during mapping and scheduling stages. Most of the existing research works proposed several task scheduling solutions by considering the voltage/frequency scaling at the scheduling stage alone. But, the efficacy of these solutions can be improved by applying the DVFS in both mapping as well as scheduling stages. This research work attempts to apply DVFS in mapping as well as scheduling stages by combining both the task-resource and resource-frequency assignments in a single problem. The idea is to estimate the worst-case global slack time for each task-resource assignment, distributes it over the TIG and slowing down the execution of tasks using dynamic voltage and frequency scaling. This optimal slowdown increases the computation time of TIG without exceeding its worst-case completion time. Further, the proposed work models the code offloading as a Quadratic Assignment Problem (QAP) in Matlab-R2012b and solves it using two-level Genetic Algorithm (GA) of the global optimization toolbox. The effectiveness of the proposed model is assessed by a simulation and the results conclude that there is an average energy savings of 35% in a mobile device.

I. Introduction

The Mobile Cloud Computing (MCC) [1] enables the mobile devices to shift their computations, data processing and storage to cloud resources. This interesting feature reduces the computing resource requirements of mobile devices to run complex applications. To achieve this, static and dynamic analysis are conducted on the complex applications and are optimally partitioned into several interconnected entities like TIG [2]. The tasks in a TIG need to be mapped and scheduled over the suitable nearby/cloud resources without compromising energy and performance. Further, mapping is a process of assigning a resource to a task by matching its requirements with the capabilities of that resource. The scheduling is a process of executing the tasks over the assigned resources. Each TIG has vertices as well as edges. The vertices represent the tasks that contain sets of instructions to be executed over the mapped resources associated with a computation cost. The edges represent the data need to be transmitted between the tasks from one mapped resource to another associated with a communication cost. Since the communication cost depends on the amount of data transfered between the tasks and the bandwidth between the resources mapped to them, it is different for different task-resource mapping.