Joint Task Offloading Scheduling and Transmit Power Allocation for Mobile-Edge Computing Systems

Yuyi Mao, Jun Zhang, Khaled Ben Letaief

Introduction

Mobile-Edge Computing (MEC) has emerged as a vital technology for resource-constrained devices, such as smartphones and IoT sensors, by allowing them to offload computationally intensive tasks to nearby servers. However, real-world implementations often face physical constraints: devices may only be able to upload one task at a time, and servers may process tasks sequentially. This creates a "pipelining" challenge where the order of tasks and the power used for transmission significantly impact both battery life and execution speed.

What Problem Does This Paper Address?

Most existing research assumes infinite network bandwidth or parallel server processing. In reality, resources are limited, leading to potential idle time for either the network or the server. For instance, sending a large data task first might leave the server idle while waiting for the upload to finish. Conversely, a small task with high computational requirements might leave the network idle while the server processes it.

System model of a mobile-edge computing (MEC) system with sequential task offloading and execution.

The authors aim to find the "Goldilocks" zone—the optimal sequence of tasks and the corresponding transmit power allocation—to minimize a weighted sum of total execution latency and device energy consumption. This is formulated as a Mixed Integer Nonlinear Programming (MINLP) problem, which is traditionally difficult to solve due to its combination of discrete scheduling choices and continuous power variables.

Methodology

To tackle the MINLP problem, the authors developed an Alternating Minimization approach that decomposes the challenge into two manageable sub-problems:

  1. Optimal Scheduling: By fixing the transmit power, the task ordering problem is mapped to a classical two-machine flow shop scheduling problem. The authors demonstrate that Johnson’s Algorithm can find the mathematically optimal sequence in $O(N \log N)$ time.
  2. Optimal Power Allocation: By fixing the task sequence, the authors use a change-of-variables technique to transform the non-convex power allocation problem into a convex optimization problem, solvable using standard numerical methods.

The algorithm iterates between these two steps until convergence, providing a low-complexity solution suitable for real-time mobile applications.

Key Insights: The Flow Shop Analogy

A primary insight of this work is treating the MEC system as a factory pipeline. The wireless transmitter acts as "Machine 1," and the MEC server CPU acts as "Machine 2." Because transmission and execution can occur in parallel (the server can process Task 1 while the device uploads Task 2), the system functions as a pipeline.

The authors found that scheduling is most critical when radio and computational resources are balanced. If one resource is significantly faster than the other, it becomes a permanent bottleneck, and the order of tasks matters less. Additionally, the optimal strategy often involves "front-loading" power—using higher transmit power for the first few tasks to minimize initial server idle time.

Key Results

Numerical simulations show that the proposed joint optimization offers significant performance gains over baseline methods:

  • Latency Reduction: In balanced resource scenarios, the optimal scheduling algorithm reduced execution delay by approximately 6.1% compared to random task ordering.
  • Energy Efficiency: The joint optimization achieved massive energy savings. In specific simulations ($f_{ser} = 1$ GHz), the algorithm saved 78% of device energy compared to maximum power transmission, without increasing latency.
  • Convergence: The alternating minimization typically converges in just a few iterations, ensuring high efficiency.
Comparison of execution delay between random and optimal task offloading scheduling across different resource ratios.

Conclusion and Future Work

This paper demonstrates that joint optimization of task sequencing and power allocation can significantly enhance the efficiency of MEC systems. While the current model focuses on a single-user scenario with independent tasks, it provides a robust foundation for future research. Potential extensions include multi-user environments with interference, tasks with complex dependencies (Directed Acyclic Graphs), and flexible "partial offloading" where devices decide between local and edge execution based on real-time channel conditions.

Summary updated

BibTeX
@inproceedings{mao2017joint,
  author = {Yuyi Mao and Jun Zhang and Khaled Ben Letaief},
  title = {{Joint Task Offloading Scheduling and Transmit Power Allocation for Mobile-Edge Computing Systems}},
  booktitle = {WCNC},
  year = {2017},
  doi = {10.1109/wcnc.2017.7925615},
}
Figure