PaperlayerView exact revision on arXiv

Source-linked AI summary

Lyapunov-guided Deep Reinforcement Learning for Stable Online Computation Offloading in Mobile-Edge Computing Networks

Suzhi Bi, Liang Huang, Hui Wang, Ying-Jun Angela Zhang

arXiv:2010.01370v3cs.NI

TL;DR

The paper studies online computation offloading in multi-user MEC networks with stochastic channels and task arrivals, seeking high data-processing capability under long-term queue stability and power constraints. It proposes LyDROO, which uses Lyapunov optimization to create per-frame problems and combines model-based optimization with DRL to solve them. Simulations report optimal computation performance with stabilized queues and low execution latency, while the analysis identifies assumptions and access-scheme boundaries for the current design.

  • Problem

    Joint binary offloading and resource allocation are computationally difficult, while existing DRL methods generally lack long-term queue-stability and average-power guarantees.

  • Method

    LyDROO applies Lyapunov optimization to decouple the stochastic problem into per-frame MINLPs and uses an actor-critic framework combining DRL with analytical resource allocation.

  • Results

    LyDROO achieves optimal computation performance while stabilizing system queues, converging to similar queue-length and rate performance as LyCD after around t = 7,500.

  • Takeaways & Limitations

    The framework provides an online approach for constrained computation offloading with low execution latency and applicability to partial offloading and other multiple-access methods when resource allocation is efficiently solved.

  • Takeaways & Limitations

    The convergence proof relies on i.i.d. task data arrivals, and the current model assumes block-fading channels; other multiple-access schemes require efficient resource allocation algorithms.

Abstract

from arXiv · show

Opportunistic computation offloading is an effective method to improve the computation performance of mobile-edge computing (MEC) networks under dynamic edge environment. In this paper, we consider a multi-user MEC network with time-varying wireless channels and stochastic user task data arrivals in sequential time frames. In particular, we aim to design an online computation offloading algorithm to maximize the network data processing capability subject to the long-term data queue stability and average power constraints. The online algorithm is practical in the sense that the decisions for each time frame are made without the assumption of knowing future channel conditions and data arrivals. We formulate the problem as a multi-stage stochastic mixed integer non-linear programming (MINLP) problem that jointly determines the binary offloading (each user computes the task either locally or at the edge server) and system resource allocation decisions in sequential time frames. To address the coupling in the decisions of different time frames, we propose a novel framework, named LyDROO, that combines the advantages of Lyapunov optimization and deep reinforcement learning (DRL). Specifically, LyDROO first applies Lyapunov optimization to decouple the multi-stage stochastic MINLP into deterministic per-frame MINLP subproblems. By doing so, it guarantees to satisfy all the long-term constraints by solving the per-frame subproblems that are much smaller in size. Then, LyDROO integrates model-based optimization and model-free DRL to solve the per-frame MINLP problems with low computational complexity. Simulation results show that under various network setups, the proposed LyDROO achieves optimal computation performance while stabilizing all queues in the system. Besides, it induces very low execution latency that is particularly suitable for real-time implementation in fast fading environments.

I. INTRODUCTION

The paper addresses online computation offloading in multi-user MEC networks, where joint binary offloading and resource allocation are computationally difficult and long-term stability constraints must be maintained under random environments. LyDROO combines Lyapunov optimization with DRL to solve these constrained decisions online with low complexity.

  • A. Motivations and Summary of Contributions: Joint binary offloading and resource allocation form a computationally difficult MINLP, especially as the number of users increases.Existing approaches reduce complexity through heuristics, decomposition, or binary-variable relaxations, but may sacrifice solution quality.
  • A. Motivations and Summary of Contributions: Most existing DRL-based offloading methods do not directly impose long-term queue stability and average power constraints.They instead use per-frame penalty terms, while Lyapunov optimization provides theoretical long-term stability guarantees through per-frame deterministic subproblems.
  • A. Motivations and Summary of Contributions: The proposed online design targets optimal computation performance under random fading channels and task arrivals without requiring future channel or arrival realizations.The framework is intended for real-time decisions in fast-varying MEC environments.
  • A. Motivations and Summary of Contributions: LyDROO decouples the multi-stage stochastic MINLP into per-frame deterministic problems, then combines model-based optimization with model-free DRL.Its actor learns binary offloading actions, while its critic analytically solves the continuous resource allocation problem for more accurate action evaluation.
  • A. Motivations and Summary of Contributions: LyDROO uses noisy order-preserving quantization to balance exploration and exploitation while reducing computational complexity during training.The quantization parameter adapts during training, and simulations report fast convergence to optimal computation rate while satisfying long-term stability constraints.

B. Problem Formulation

The problem formulation seeks an online policy that maximizes weighted computation rate while enforcing data queue stability and average power constraints. It models per-frame offloading and resource allocation decisions without knowledge of future channel and task-arrival realizations.

  • B. Problem Formulation: The objective is to maximize the long-term average weighted sum computation rate under data queue stability and average power constraints.The formulation uses fixed user weights and represents the task as a multi-stage stochastic MINLP.
  • B. Problem Formulation: Each time frame requires online optimization of task offloading and resource allocation using only the current frame’s information.Future realizations of random channel conditions and data arrivals are not assumed to be known.
  • B. Problem Formulation: The formulation includes offloading-time, data-causality, average-power, and data-queue-stability constraints.The average power constraint uses user-specific power thresholds, while queue stability remains difficult under stochastic channels and arrivals.
  • B. Problem Formulation: Although the paper highlights a linear utility function, the framework can also handle suitable non-decreasing concave utilities when the resource allocation subproblem is efficiently solvable.Examples include α-fairness and proportional-fairness utilities.

III. LYAPUNOV-BASED DECOUPLING OF THE MULTI-STAGE MINLP

Lyapunov optimization converts the multi-stage stochastic MINLP into deterministic per-frame problems using data and virtual energy queues. Drift-plus-penalty control then balances computation performance with queue stability and average power constraints.

  • Virtual Queue Construction: Virtual energy queues track power consumption against the average-power thresholds, so their stability implies satisfaction of the power constraints.Each queue has energy arrivals proportional to consumption and a fixed service rate proportional to the power threshold.
  • Lyapunov Control: The combined backlog Z(t) contains both data queues Q(t) and virtual energy queues Y(t), enabling joint queue control.The Lyapunov function and drift are defined over this total queue backlog.
  • Per-Frame Optimization: At each frame, the algorithm observes queue backlogs and chooses offloading and resource-allocation actions that minimize an upper bound on drift-plus-penalty.Removing action-independent terms yields the deterministic per-frame optimization objective.
  • Per-Frame Optimization: The per-frame subproblem uses current queue states and controls computation-rate rewards while penalizing users with excessive average-power usage.The penalty weight V scales the performance term in the drift-plus-penalty objective.
  • Constraint Satisfaction: Solving the per-frame subproblems satisfies the original long-term constraints because the per-frame queue constraints are equivalent to the corresponding constraints in the multi-stage problem.The equivalence follows because exactly one term is nonzero at the optimum.

IV. LYAPUNOV-GUIDED DRL FOR ONLINE COMPUTATION OFFLOADING

LyDROO reduces online offloading complexity by using DRL to generate candidate binary actions while convex optimization evaluates resource allocation for each candidate. Its actor module maps observed channels and queues to feasible actions through adaptive quantization.

  • Problem Reduction: Fixing the binary offloading decision makes the resource-allocation problem convex, reducing each per-frame problem to action search plus efficient allocation.The optimal allocation value G is used to evaluate each offloading decision.
  • Problem Reduction: DRL learns a policy mapping the current observation ξt to an optimal binary offloading action without enumerating all 2^N possibilities.Enumeration becomes impractical even for moderate user counts, such as N = 10.
  • Algorithm Architecture: LyDROO repeatedly executes actor, critic, policy-update, and queueing modules while interacting with time-varying channels and queues.The modules operate sequentially and iteratively in each time frame.
  • Actor Module: The actor DNN maps observation ξt to a relaxed offloading vector ˆxt in [0,1]^N, which is quantized into feasible binary actions.The observation includes system information used to construct candidate actions.
  • Actor Module: NOP quantization generates Mt candidate actions by combining order-preserving quantization with noisy sigmoid-transformed outputs.The method can generate any Mt ≤ 2^N candidate actions and adds noise to support exploration.

2) Critic Module:

The critic module evaluates candidate binary offloading actions using model-based resource optimization rather than a model-free critic network. An adaptive candidate count balances solution quality against computation time.

  • Critic Module: LyDROO analytically solves the optimal resource-allocation problem to evaluate each candidate binary offloading action.This model-based evaluation provides accurate action values for selecting the best candidate.
  • Critic Module: Model-based action evaluation supports more robust and faster DRL convergence than relying on a model-free DNN critic.The comparison concerns the critic's evaluation mechanism within the actor-critic structure.
  • Adaptive Candidate Set: Evaluating all Mt candidates improves solution performance but increases computation time, creating a performance-complexity trade-off.The critic computes the resource-allocation value Mt times before selecting the best action.
  • Adaptive Candidate Set: The candidate count Mt is adapted over time because a small candidate set becomes sufficient as the actor DNN approaches the optimal policy.The procedure starts with M1 = 2^N and updates Mt every δM frames.
  • Policy Update: The policy is trained from recent state-action samples in replay memory using periodic minibatch updates and Adam optimization.Training begins after more than q/2 samples are collected and occurs every δT time slots.

4) Queueing Module:

The queueing module executes the selected offloading and resource-allocation action, updates data and energy queues, and feeds the resulting state into the next iteration. The full loop progressively improves the actor policy and can extend to concave utility objectives.

  • Queueing Module: After selecting xt, LyDROO obtains its associated optimal resource allocation yt and executes the joint action {xt, yt}.This action processes the users' task data in the current frame.
  • Online Procedure: Algorithm 1 initializes random DNN parameters, empty replay memory, zero data queues, zero energy queues, and M1 = 2^N.It then repeats the online procedure over time frames t = 1, 2, ..., K.
  • Queueing Module: The queueing module updates data and energy queues at the beginning of the next time frame using the queue-update equations.The next observation is then supplied to the DNN for a new actor iteration.
  • Online Procedure: The actor DNN learns from the best and most recent state-action pairs, causing its policy to gradually approximate the optimal mapping for the per-frame problem.The main computational cost is solving the optimal resource-allocation problems for candidate actions.
  • Extension: The LyDROO framework can extend to non-decreasing concave utility functions because the corresponding per-frame resource-allocation problem is convex.The paper notes that the detailed analysis is omitted.

B. Low-complexity Optimal Resource Allocation Algorithm

The resource-allocation problem is decomposed by offloading mode, solved through a dual formulation, and recovered using bisection and a linear program. Closed-form solutions simplify local computation and transmission decisions.

  • Problem decomposition: The weighted resource-allocation problem separates into independent local-computation problems for users in M0 and an offloading subproblem for users in M1.For a local-computing user, the closed-form solution implies faster computation when Qj(t) is larger or Yj(t) is smaller.
  • Dual formulation: The M1 offloading subproblem is handled with a partial Lagrangian and dual function using dual variable µ.The formulation exploits the separable structure of the offloading users’ resource-allocation problem.
  • Offloading allocation: The optimal transmission time increases linearly with offloaded data under a fixed optimal communication rate li(µ).The rate li(µ) is treated as a fixed parameter for a given µ.
  • Algorithm output: The resulting optimal resource allocation combines the local-computation solution and recovered offloading variables to solve (P4).The procedure is summarized as a primal-dual algorithm in Algorithm 2.

A. Computational Complexity

LyDROO’s per-frame action generation dominates its execution cost, while policy updates occur infrequently and in parallel. Its bounded per-frame optimization gap supports queue stability, power compliance, and an O(1/V)–O(V) rate-delay tradeoff.

  • Computational complexity: Offloading action generation runs every time frame, whereas policy updates run infrequently and in parallel with task offloading and local computation.The complexity analysis therefore focuses on action generation.
  • Computational complexity: Algorithm 2 reduces the resource-allocation LP from 4N variables to N variables, lowering complexity especially for large N.LyDROO executes Algorithm 2 Mt times per time frame when generating an offloading action.
  • Computational complexity: A small Mt, such as less than 5 when N = 30, suffices to generate an optimal offloading action after learning converges.The adaptive procedure gradually reduces Mt during learning.
  • Convergence performance: Under the stated feasibility and Slater-condition assumptions, a per-frame optimality gap C yields strongly stable queues and satisfies the average power constraint with probability 1.The guarantee applies when LyDROO stays within C of the per-frame subproblem minimum.
  • Convergence performance: Increasing V improves the computation objective proportionally to 1/V while increasing queue length, and therefore processing delay, proportionally to V.A smaller C provides both higher rate and lower delay performance.

VI. SIMULATION RESULTS

Simulations show that LyDROO closely matches near-optimal computation performance while stabilizing queues and satisfying power constraints across network conditions, with low execution latency.

  • Per-frame optimization: LyDROO reaches about 0.96 moving-window objective ratio, with a median near 0.98 and over 75% of cases above 0.94.These results indicate a small optimality gap for the per-frame subproblem.
  • Convergence: For λi = 3 Mbps, LyDROO stabilizes data queues and converges to LyCD-like queue and rate performance after about t = 7,500.Its computation-rate gap from LyCD remains below 5% for t ≤ 3,000.
  • Parameter impact: Across the considered λi and γi settings, LyDROO maintains stable queues, satisfies average power constraints, and achieves optimal computation-rate performance.The Myopic scheme becomes unstable or loses computation rate under heavier workloads and more stringent power constraints.
  • Lyapunov control parameter: For V ∈ [1, 1000], LyDROO and LyCD achieve similar stable-queue, below-threshold-power, and optimal-rate performance.Increasing V reduces queue length and power consumption when V ≤ 40, but all three quantities increase when V > 40 as offloading becomes unfair.
  • Network size: LyDROO maintains stable task queues up to λi ≤ 3.2 Mbps for N = 10, λi ≤ 2.4 Mbps for N = 20, and λi ≤ 2 Mbps for N = 30.The stable capacity region shrinks as the number of WDs increases.

VII. CONCLUSIONS AND DISCUSSIONS

The paper concludes that LyDROO achieves optimal computation performance while satisfying long-term constraints, with low online complexity and latency. It also discusses extensions and scope limitations involving arrival processes, channel variation, result downloading, and access methods.

  • Conclusions: LyDROO achieves optimal computation rate performance while satisfying all long-term constraints in theory and simulations.It also converges within a relatively small number of iterations and generates online actions with low computational complexity.
  • Extensions: LyDROO can be extended from binary to partial computation offloading for tasks consisting of multiple independent subtasks.Binary variables can represent which subtask subset is offloaded while continuous resources are jointly optimized.
  • Arrival processes: The convergence proof relies on an i.i.d. task-data-arrival assumption, although similar [O(1/V ), O(V )] guarantees are indicated for broader processes.The paper evaluates LyDROO under non-i.i.d. Markov modulated ON-OFF arrivals with equal long-term average arrival rates.
  • Channel variation: The block-fading assumption may be adapted to small within-frame channel variations using an SNR margin ρ ≥1, trading spectrum efficiency for robustness.A larger ρ increases robustness against channel variation but lowers spectrum efficiency.
  • Scope and implementation: The study neglects computation-result downloading delay, although this delay can be incorporated by modifying the resource-allocation time constraint.The adjustment does not affect the overall LyDROO algorithm design.
  • Multiple access: LyDROO is also applicable to FDMA, CDMA, OFDMA, and NOMA if the critic module can quickly obtain optimal wireless resource allocation.The paper coordinates multiple WDs using TDMA and identifies efficient allocation under other access methods as the technical challenge.

APPENDIX A PROOF OF PROPOSITION 1

The proposition’s proof analyzes a strictly concave objective over feasible time allocations. The optimum is therefore determined by an interior stationary point when feasible, or otherwise by the boundary.

  • Concavity: The objective Ω(τ_i) is strictly concave over the feasible set τ_i ≥ r_i,O.This makes the derivative Ω′(τ_i) decreasing and limits the candidate minimizers.
  • Optimality condition: The optimum is attained at the boundary r_i,O or at the stationary point v1 satisfying Ω′(v1) = 0.The applicable point depends on whether the stationary point lies within the feasible set.
  • Lambert-W solution: The stationary point is obtained using the Lambert-W function and its monotonicity on the relevant domain.The proof uses W(x) ∈ [−1, 0] and the fact that W(x) increases for x ≥ −1/e.
  • Boundary case: When the stationary condition is infeasible, concavity implies that the optimum occurs at the boundary (τ_i)∗ = r_i,O.The proof compares v1 with the lower feasible bound r_i,O.

APPENDIX B PROOF OF THEOREM 1

The theorem proof combines an auxiliary stationary policy with Lyapunov drift bounds to establish computation performance and queue stability. Telescoping sums then yield the long-term power and stability guarantees.

  • Auxiliary policy: The proof introduces lemmas providing an ω-only policy satisfying the required inequalities and linking rate-stable virtual queues to average-power feasibility.The policy is used because it is independent of the queue backlog.
  • Performance bound: Summing the drift inequality over time and taking limits establishes the computation-performance bound in Theorem 1.The argument uses iterated expectations, telescoping sums, and division by KV.
  • Stability argument: The Slater-condition policy is substituted into the drift bound to derive the virtual-queue bound required for stability.The proof then uses nonnegative virtual queues to complete the corresponding theorem statement.
  • Guarantees: All data and virtual queues are strongly stable, so data queues are rate stable and the average-power constraint holds with probability 1.This implication completes the proof of the theorem’s stability and power claims.
Loading 2010.01370v3…