PaperlayerView exact revision on arXiv

Source-linked AI summary

Delay-Optimal Computation Task Scheduling for Mobile-Edge Computing Systems

Juan Liu, Yuyi Mao, Jun Zhang, Khaled B. Letaief

arXiv:1604.07525v3cs.ITcs.NI

TL;DR

MEC scheduling must solve a two-timescale problem that balances local execution, cloud offloading, queueing delay, and channel variation under limited device power. The paper uses a Markov-based stochastic scheduling formulation and an efficient one-dimensional search algorithm. Simulations report minimum average delay across various scenarios compared with three baseline policies.

  • Problem

    MEC scheduling must jointly decide local-versus-cloud execution across task timescales while adapting offloaded-data transmission to changing wireless channels and accounting for queued tasks.

  • Method

    The paper analyzes average delay and mobile-device power using task-buffer, local-processing, and transmission states, then solves the power-constrained problem with a one-dimensional search algorithm.

  • Results

    The proposed stochastic scheduling policy achieves the minimum average delay in various scenarios compared with local execution, cloud execution, and greedy offloading baselines.

  • Takeaways & Limitations

    The policy can exploit parallel local and cloud execution while adapting scheduling to task arrivals and wireless transmission conditions.

Abstract

from arXiv · show

Mobile-edge computing (MEC) emerges as a promising paradigm to improve the quality of computation experience for mobile devices. Nevertheless, the design of computation task scheduling policies for MEC systems inevitably encounters a challenging two-timescale stochastic optimization problem. Specifically, in the larger timescale, whether to execute a task locally at the mobile device or to offload a task to the MEC server for cloud computing should be decided, while in the smaller timescale, the transmission policy for the task input data should adapt to the channel side information. In this paper, we adopt a Markov decision process approach to handle this problem, where the computation tasks are scheduled based on the queueing state of the task buffer, the execution state of the local processing unit, as well as the state of the transmission unit. By analyzing the average delay of each task and the average power consumption at the mobile device, we formulate a power-constrained delay minimization problem, and propose an efficient one-dimensional search algorithm to find the optimal task scheduling policy. Simulation results are provided to demonstrate the capability of the proposed optimal stochastic task scheduling policy in achieving a shorter average execution delay compared to the baseline policies.

I. INTRODUCTION

MEC task scheduling must coordinate local execution, cloud offloading, and channel adaptation across two timescales while accounting for queued tasks. The paper models this problem under a power constraint and develops an optimal stochastic scheduling policy that reduces delay relative to baselines.

  • I. INTRODUCTION: MEC can improve mobile-device computation experience by offloading intensive tasks to nearby servers, reducing device energy consumption and execution delay.The motivation concerns resource-limited mobile devices running computation-intensive, delay-sensitive applications.
  • I. INTRODUCTION: The scheduling problem spans a larger timescale for local-versus-cloud execution and a smaller timescale for transmission adaptation to instantaneous wireless channels.Task execution can last across multiple channel blocks, creating a two-timescale stochastic optimization problem.
  • I. INTRODUCTION: Earlier two-timescale work minimized single-task energy and ignored queueing delay from multiple tasks, while MEC can support concurrent local and cloud execution.The paper therefore considers task buffering and parallel use of local and cloud computation resources.
  • I. INTRODUCTION: The paper analyzes average task delay and mobile-device power under a scheduling policy, formulates a power-constrained delay minimization problem, and searches for an optimal stochastic policy.The proposed solution uses an efficient one-dimensional search algorithm.

II. SYSTEM MODEL

The system consists of a resource-limited mobile device assisted by an MEC server that executes tasks on the device’s behalf. The mobile CPU and transmission unit support local execution and cloud offloading, respectively.

  • II. SYSTEM MODEL: The MEC server may be a small data center at a wireless access point and can execute mobile-device tasks through an associated virtual machine.The server assists computation-intensive and delay-sensitive applications running on the mobile device.
  • II. SYSTEM MODEL: The mobile device’s local CPU executes tasks locally, while its transmission unit sends task input data to the MEC server for cloud execution.These two device components are the system elements of particular interest.

A. Task Queueing Model

Tasks arrive in discrete time and wait in a sufficiently large buffer until scheduled for local execution, cloud offloading, both, or neither. The buffer evolution tracks scheduled departures and new arrivals.

  • A. Task Queueing Model: Time is divided into equal-length slots of duration ∆, and a new task arrives at the beginning of a slot with probability α.The task buffer has sufficiently large capacity Q1 for arrived but unexecuted tasks.
  • A. Task Queueing Model: Each slot permits four scheduling decisions represented by (vL[t], vC[t]): local only, cloud only, both, or neither.The decision indicators specify whether tasks are sent to the local CPU or MEC server.
  • A. Task Queueing Model: The queue updates by removing scheduled local and cloud tasks, adding the slot’s arrival, and limiting the result by the buffer capacity.The model uses q[t+1] = min{(q[t] − vL[t] − vC[t])^+ + a[t], Q}.
  • A. Task Queueing Model: The sufficiently large buffer assumption prevents overflow, so every arrived task is eventually executed locally or by the MEC server.This is an explicit modeling assumption rather than a reported performance result.

B. Computation Model

Local and cloud computation are modeled through processing states for the mobile CPU and transmission unit. Local tasks require a fixed number of CPU slots, while cloud tasks require successful packet transmission followed by MEC execution and result feedback.

  • B. Computation Model: A local task requires N = ⌈C/(floc∆)⌉ time slots, where C is its required CPU cycles and floc is the local CPU frequency.The local CPU consumes Ploc while active and no power while idle.
  • B. Computation Model: The local CPU state cL[t] is zero when idle and otherwise records the progress of a task occupying the CPU.State cL[t] = n indicates that N − n more slots are required for completion.
  • B. Computation Model: Cloud offloading divides each task’s input into M equal-size packets of R bits and uses channel side information with on-off power control.A packet is transmitted successfully when the channel supports the required rate; otherwise the transmitter remains silent.
  • B. Computation Model: The transmission-unit state cT[t] records whether the unit is available or transmitting a task packet, and MEC execution starts after all input bits arrive.The MEC server requires Ncloud = ⌈C/(fser∆)⌉ slots, followed by constant result-feedback delay tr.

III. STOCHASTIC COMPUTATION TASK SCHEDULING AND MARKOV CHAIN MODELING

The MEC system state combines task-buffer occupancy with the execution states of the transmission unit and local CPU, defining the state space for stochastic scheduling analysis.

  • The system state is represented by τ[t] = (q[t], cT[t], cL[t]), combining queue length, transmission-unit state, and local-CPU state.

A. Stochastic Computation Task Scheduling

The scheduling policy maps each system state to probabilistic decisions about local execution and task offloading, while respecting queue availability and resource occupancy.

  • At each time slot, the device decides whether to schedule a task for local computing or offload it to the MEC server.
  • The policy parameters gkτ map each system state to decision probabilities for four possible scheduling decisions.
  • When the task buffer is empty, all scheduling probabilities are set to keep the system idle because no task is available.
  • When both the CPU and transmitter are idle, up to two tasks can start: one locally and one through computation offloading.
  • Resource occupancy restricts decisions: an idle CPU controls local execution, while an idle transmitter controls task offloading.

B. Delay and Power Analysis

The paper models scheduling as a Markov chain, derives steady-state behavior, and expresses task delay and device power by averaging over system states and execution modes.

  • The one-step transition probability χτ,τ′ describes movement between system states under a given stochastic scheduling policy.
  • The steady-state distribution {πτ} is obtained by solving a linear equation set based on the transition probabilities.
  • Average task delay combines queueing delay with processing latency, using Little’s Theorem and the task arrival rate α.
  • Cloud-processing time includes input-data transmission, MEC-server execution, and result feedback, whereas local execution lasts N time slots.
  • The channel non-outage probability β determines average transmission behavior, and average power is decomposed into local-computation and transmission components.The power expression uses Ploc and Ptx with averaged coefficients νloc and νtx.

IV. OPTIMAL COMPUTATION OFFLOADING SCHEDULING

The paper formulates power-constrained delay minimization and transforms the non-convex problem into linear programs indexed by a scalar parameter, enabling one-dimensional search for the optimal policy.

  • The optimization minimizes average task delay subject to an average power constraint at the mobile device.
  • The formulation includes an average power constraint, balance equations, and nonnegative decision variables.
  • Occupation measures xkτ represent the probability of being in state τ while decision k is selected.
  • Algorithm 1 solves the linear program over a grid of η values and selects the minimum optimized delay, yielding x∗ and the optimal scheduling policy.
  • For a fixed η, the non-convex problem reduces to a linear program, after which a one-dimensional search identifies η∗.

V. SIMULATION RESULTS

Simulations compare three baseline scheduling policies with the proposed optimal policy as task arrival rates vary. The optimal policy achieves the minimum average delay and largest stable region by exploiting parallel local and cloud execution.

  • Simulation setup: Simulations assume 500 Kbits per task, M = 1, R = L, and the listed system parameters.The settings include Δ = 20 ms, B = 5 MHz, Ptx = 1 W, β = 0.4, N = 17, and tc = 3.5.
  • Compared policies: The comparison includes local execution, cloud execution, greedy offloading, and the proposed optimal scheduling policy.Local and cloud policies execute all tasks locally or remotely, while greedy offloading uses whichever local CPU or transmission unit is idle.
  • Evaluation metrics: Average delay and local-execution proportion are evaluated against the average computation task arrival rate α.The metrics are shown in Fig. 2 and Fig. 3, respectively.
  • Observed trends: The local, cloud, and optimal policies increase their average delays and local-execution proportions as α increases, whereas greedy offloading schedules fewer tasks locally.For greedy offloading, local execution decreases with α because cloud execution is faster, with tc = 3.5 < N = 17.
  • Optimal-policy behavior: When α ≤ 0.12, the optimal policy executes no tasks locally; beyond α = 0.12, it increasingly uses local execution alongside cloud execution.At higher arrival rates, parallel local and cloud execution adapts to the increased task arrival rate.
  • Main result: The optimal policy achieves the minimum average delay and largest stable region among the evaluated policies.The stable region accommodates the maximum task arrival rate α in the reported scenarios.

VI. CONCLUSIONS

The paper concludes that its stochastic scheduling policy incorporates the different timescales of task execution and channel fading. It reports minimum average delay across various scenarios and identifies broader MEC systems as future work.

  • Contribution: The proposed stochastic computation task scheduling policy incorporates different timescales in task execution and channel fading.The policy is designed for MEC systems.
  • Optimization: An efficient one-dimensional search algorithm finds the optimal task scheduling policy using average delay and mobile-device power analysis.The optimization is based on the analyzed average delay and average power consumption.
  • Results: The proposed policy achieves the minimum average delay in various scenarios compared to three baseline policies.The conclusion reports this as the principal simulation finding.
  • Future work: Future investigation could extend the work to more general MEC systems.This is the stated future-work direction.

A. The State Transition Probabilities of the Markov Chain

The Markov chain models state transitions by jointly considering task scheduling decisions, task arrivals, and channel states. Transition rules vary according to whether the local CPU and transmission unit are idle or busy.

  • Transition model: The Markov-chain transition probabilities jointly account for scheduling decisions, task arrivals, and channel states.The state-transition analysis is organized into four cases.
  • Case I: both units idle: When both the local CPU and transmission unit are idle, up to four scheduling decisions can be selected when at least two tasks await processing.When the buffer is empty, transitions are driven by whether a new task arrives.
  • Case II: transmission busy: When the transmission unit is busy and the local CPU is idle, a new task can be scheduled for local execution while offloading continues.For a non-empty buffer, the scheduling policy and resulting transitions depend on task arrivals and successful packet delivery.
  • Case III: local CPU busy: When the local CPU is busy and the transmission unit is idle, offloading decisions are made probabilistically while local execution proceeds.The transition probabilities include task arrivals, successful packet delivery, and the evolving transmission state.
  • Case IV: both units busy: When both units are busy, four transitions combine task arrivals, successful packet delivery, and the next channel state.If destination states coincide in special cases, their transition probabilities are combined.
  • Power coefficients: Power coefficients are derived for each system state from the stochastic scheduling policy, including local execution and transmission activity.An empty task buffer consumes no execution or offloading power.
Loading 1604.07525v3…