PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yuyi Mao, Jun Zhang, Khaled B. Letaief

arXiv:1701.05055v1cs.IT

TL;DR

MEC can reduce the latency and energy burden of computation-intensive tasks, but multiple-task systems require jointly choosing the offloading order and transmit powers. The paper uses alternating minimization with flow-shop scheduling and convex optimization, achieving near-optimal delay and substantial device-energy savings, especially when radio and computational resources are balanced.

  • Problem

    The paper addresses joint offloading scheduling and transmit-power allocation for multiple independent tasks to reduce execution delay and device energy consumption in MEC systems.

  • Method

    Alternating minimization combines flow-shop scheduling for the offloading order with convex optimization for transmit-power allocation.

  • Results

    The algorithm achieves near-optimal execution delay with substantial device-energy savings; 78% of device energy consumption is saved for fser = 1 GHz with η = 100 sec · J−1.

  • Takeaways & Limitations

    Scheduling matters most when radio and computational resources are relatively balanced, while suitable weighting can reduce energy without sacrificing optimal delay performance.

Abstract

from arXiv · show

Mobile-edge computing (MEC) has emerged as a prominent technique to provide mobile services with high computation requirement, by migrating the computation-intensive tasks from the mobile devices to the nearby MEC servers. To reduce the execution latency and device energy consumption, in this paper, we jointly optimize task offloading scheduling and transmit power allocation for MEC systems with multiple independent tasks. A low-complexity sub-optimal algorithm is proposed to minimize the weighted sum of the execution delay and device energy consumption based on alternating minimization. Specifically, given the transmit power allocation, the optimal task offloading scheduling, i.e., to determine the order of offloading, is obtained with the help of flow shop scheduling theory. Besides, the optimal transmit power allocation with a given task offloading scheduling decision will be determined using convex optimization techniques. Simulation results show that task offloading scheduling is more critical when the available radio and computational resources in MEC systems are relatively balanced. In addition, it is shown that the proposed algorithm achieves near-optimal execution delay along with a substantial device energy saving.

I. INTRODUCTION

The paper studies joint offloading scheduling and transmit-power allocation for multiple independent tasks in a single-user MEC system. It proposes alternating minimization, combining flow-shop scheduling and convex optimization, to reduce delay and device energy consumption.

  • MEC moves computation-intensive tasks from resource-limited mobile devices to nearby servers, targeting lower latency and device energy consumption.
  • The system considers multiple independent tasks, with one task offloaded at a time and tasks executed sequentially at the MEC server.
  • The proposed low-complexity algorithm alternates between optimal offloading scheduling via flow-shop scheduling theory and transmit-power allocation via convex optimization.
  • Task offloading scheduling is most critical when radio and computational resources are relatively balanced.
  • The MEC system comprises a mobile device communicating wirelessly with a nearby MEC server that executes tasks on the device’s behalf.
  • All tasks are assumed to be offloaded because the mobile device has very limited computational capability.

B. Task Offloading and Mobile-Edge Execution Model

The task model represents each task by its input-data size and computational workload, while offloading follows a chosen permutation and MEC execution follows the same order.

  • The offloading schedule σ is a permutation of task indices, where Tσi is the ith task transmitted to the MEC server.
  • A single-antenna mobile device transmits the input data of only one computation task at each time.
  • The task transmission rate depends on transmit power and channel parameters including path loss, reference distance, and receiver noise spectral density.
  • The single-core MEC server executes offloaded tasks sequentially using first-come-first-serve, so execution order matches offloading order.
  • The optimization targets a weighted sum of execution delay and device energy consumption by jointly designing scheduling and transmit power.

III. PROBLEM FORMULATION

The formulation couples task readiness, sequential MEC execution, and transmission energy in a joint scheduling and power-allocation problem. Because it is an MINLP, exhaustive search is impractical and motivates a low-complexity alternative.

  • Execution of each task waits until its input data is ready at the MEC server and the server CPU is available.
  • A task’s completion time depends on both its input-data transmission completion and the completion time of the previously executed task.
  • The formulation uses recursive completion-time expressions to represent sequential task execution.
  • Device energy consumption for offloading is modeled as transmit energy and is independent of the task offloading schedule.
  • The optimization minimizes the weighted delay-energy objective subject to valid permutations and non-negative peak-limited transmit powers.
  • 20! ≈ 2.43 × 10^18 permutations arise for N = 20, making exhaustive search practically infeasible.

IV. SUB-OPTIMAL JOINT TASK OFFLOADING SCHEDULING AND TRANSMIT POWER ALLOCATION

The proposed sub-optimal method alternately optimizes task offloading scheduling and transmit power allocation to address the joint problem with lower complexity.

  • The algorithm optimizes task offloading scheduling and transmit power allocation alternately.

A. Optimal Task Offloading Scheduling

With fixed transmit powers, task offloading scheduling is formulated as a two-machine flow shop problem and solved optimally using Johnson’s Algorithm.

  • Flow-shop formulation: The flow-shop formulation minimizes the makespan of all N tasks.
  • Flow-shop formulation: For a given transmit power vector p, the scheduling problem is an F2|(perm), (pmtn)|Cmax flow-shop problem.
  • Flow-shop formulation: Each independent task is processed sequentially by the mobile-device transmitter and MEC server, modeled as machines M1 and M2.Jobs follow the same order on both machines, without preemption, while each machine processes one job at a time.
  • Johnson’s Algorithm: Johnson’s Algorithm partitions tasks into F and G, ordering F by ascending transmission-time values and G by descending MEC execution-time values.
  • Johnson’s Algorithm: Using Quicksort, the scheduling algorithm has complexity O(N log N).Its main computational overhead comes from sorting the two task subsets.

B. Optimal Transmit Power Allocation

For a fixed offloading order, transmit-power allocation is reformulated through auxiliary variables so that a convex optimization problem yields the optimal allocation numerically.

  • Problem reformulation: Given a task offloading schedule, transmit power affects both execution delay and device energy consumption.
  • Problem reformulation: Auxiliary variables ˜tσ are introduced to replace the recursive completion-time expressions in the fixed-schedule problem.The resulting formulation is a relaxed version of P1 given σ.
  • Problem reformulation: The relaxation is tight, so an optimal solution of P2 is also optimal for P1 under the given schedule.
  • Convex transformation: P2 is non-convex, but the substitution ξσi = 1/R(pσi) transforms it into P3, a convex optimization problem.
  • Convex transformation: The optimal transmit power allocation can be obtained numerically with convex optimization solvers such as CVX.
  • Power-allocation structure: The optimal power allocation is non-increasing along the task order because earlier completion times affect all subsequent tasks.

C. The Alternating Minimization Algorithm

The proposed joint algorithm alternates between optimal scheduling and optimal fixed-schedule power allocation, repeatedly updating both decisions.

  • Alternating minimization: The algorithm updates the task offloading schedule and transmit power vector in an alternating manner.
  • Alternating minimization: Algorithm 1 supplies the optimal schedule for the current power vector, while P3 supplies the optimal power allocation for the current schedule.
  • Algorithm 2: Algorithm 2 initializes power and scheduling decisions, then iterates these updates until convergence tolerance or the iteration limit is reached.

V. SIMULATION RESULTS

The simulations evaluate scheduling effects and the proposed joint algorithm under uniformly distributed task sizes and workloads with a 1 GHz MEC server.

  • Simulation setup: The simulations assume uniformly distributed task input sizes and workloads, with davg = 1 kbits and cavg = 797.5 cycles/bit.
  • Simulation setup: The MEC server CPU speed is set to fser = 1 GHz.
  • Evaluation focus: The evaluation first investigates optimal task offloading scheduling’s impact on delay, then evaluates the joint scheduling and power-allocation algorithm.

A. Impact of The Optimal Task Offloading Scheduling

Execution delay rises with task count, while optimal offloading scheduling consistently outperforms random scheduling, especially when radio and computational resources are balanced.

  • Execution delay increases linearly with the number of computation tasks.
  • Higher transmission rates reduce execution delay, but gains shrink after the computational resource becomes the bottleneck.Increasing the rate from 0.63 to 1.25 Mbps yields a significant reduction, whereas further doubling produces a smaller reduction.
  • The optimal task offloading schedule outperforms random scheduling in every evaluated case.

B. Joint Task Offloading Scheduling and Transmit Power Allocation

The proposed algorithm improves the weighted objective while exposing a tradeoff between device energy consumption and execution delay. Increasing the weighting factor can substantially reduce energy consumption without sacrificing optimal delay once computation becomes limiting.

  • The proposed algorithm significantly improves the P1 objective over random scheduling with maximum transmit power.Its performance advantage becomes more pronounced as η increases because the benchmark power allocation is non-adaptive to η.
  • Device energy consumption decreases while execution delay increases with η.
  • 78% of device energy consumption is saved at η = 100 sec · J−1 for fser = 1 GHz.The reported saving occurs while the proposed algorithm retains optimal delay performance with a suitable η.
  • Beyond a transmission-energy threshold, additional energy does not improve delay performance.When computation limits delay, energy can be reduced without losing optimal delay; at sufficiently large η, radio resources become the constraint.

VI. CONCLUSIONS

The paper jointly optimizes task offloading scheduling and transmit power allocation for MEC systems with multiple independent tasks. Its low-complexity algorithm combines flow shop scheduling and convex optimization to achieve near-optimal delay with substantial energy reduction.

  • The paper jointly investigates task offloading scheduling and transmit power allocation for MEC systems with multiple independent tasks.
  • A low-complexity sub-optimal algorithm minimizes the weighted sum of execution delay and device energy consumption using flow shop scheduling and convex optimization.
  • Scheduling delivers the most noticeable delay improvement when radio and computational resources are relatively balanced.
  • The proposed algorithm achieves near-optimal delay together with a large reduction in device energy consumption.
Loading 1701.05055v1…