PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning for Task Offloading in Mobile Edge Computing Systems

Ming Tang, Vincent W. S. Wong

arXiv:2005.02459v1cs.NI

TL;DR

The paper addresses decentralized offloading when unknown, time-varying edge loads affect delays and task drops. It formulates a queued offloading problem for non-divisible, delay-sensitive tasks and proposes model-free distributed DRL, achieving substantially lower drop ratios and delays than benchmark methods.

  • Problem

    Unknown edge-load dynamics make decentralized decisions difficult when devices must choose whether to offload and which edge node to use for non-divisible, delay-sensitive tasks.

  • Method

    A model-free distributed DRL algorithm uses local observations and incorporates LSTM, dueling DQN, and double-DQN techniques.

  • Results

    86.4%-95.4% fewer dropped tasks and 18.0%-30.1% lower average delay were obtained than existing algorithms in simulations with 50 mobile devices and five edge nodes.

  • Takeaways & Limitations

    The algorithm handles unknown edge-load dynamics and time-varying task environments while enabling decentralized offloading from local information.

  • Takeaways & Limitations

    The system assumes a small time-slot duration and constant transmission capacity, and models future cost under time-varying environments and other devices’ decisions.

Abstract

from arXiv · show

In mobile edge computing systems, an edge node may have a high load when a large number of mobile devices offload their tasks to it. Those offloaded tasks may experience large processing delay or even be dropped when their deadlines expire. Due to the uncertain load dynamics at the edge nodes, it is challenging for each device to determine its offloading decision (i.e., whether to offload or not, and which edge node it should offload its task to) in a decentralized manner. In this work, we consider non-divisible and delay-sensitive tasks as well as edge load dynamics, and formulate a task offloading problem to minimize the expected long-term cost. We propose a model-free deep reinforcement learning-based distributed algorithm, where each device can determine its offloading decision without knowing the task models and offloading decision of other devices. To improve the estimation of the long-term cost in the algorithm, we incorporate the long short-term memory (LSTM), dueling deep Q-network (DQN), and double-DQN techniques. Simulation results with 50 mobile devices and five edge nodes show that the proposed algorithm can reduce the ratio of dropped tasks and average task delay by 86.4%-95.4% and 18.0%-30.1%, respectively, when compared with several existing algorithms.

1 INTRODUCTION

The paper formulates decentralized task offloading under uncertain, time-varying edge loads and proposes a model-free DRL solution for non-divisible, delay-sensitive tasks.

  • Background and motivation: High edge-node load can increase processing delay and cause deadline-expired tasks to be dropped.
  • Background and motivation: Distributed offloading is challenging because each device lacks prior knowledge of other devices’ task models, decisions, and resulting edge loads.
  • Problem formulation: The proposed formulation combines non-divisible tasks, queuing systems, and processing or transmission that may continue across multiple time slots.
  • Solution approach: The model-free distributed DRL algorithm uses local information without requiring other devices’ task models or offloading decisions.
  • Performance evaluation: 86.4%-95.4% fewer dropped tasks and 18.0%-30.1% lower average delay were achieved versus existing algorithms with 50 devices and five edge nodes.

2 SYSTEM MODEL

The MEC system contains mobile devices and edge nodes, with devices able to offload computational tasks to edge nodes during finite-duration time slots.

  • System model: The system includes edge nodes N = {1, 2, . . . , N} and mobile devices M = {1, 2, . . . , M}.
  • System model: Each episode comprises time slots T = {1, . . . , T}, each lasting ∆ seconds.
  • System model: Mobile devices can offload computational tasks to edge nodes for processing, alongside the modeled mobile-device and edge-node components.

2.1 Mobile Device Model

Each mobile device manages newly arriving tasks through local computation or transmission queues, selecting whether and where to offload while modeling queue-dependent completion or dropping times.

  • Queueing and arrivals: A device assumes at most one new task arrival per time slot and places each arriving task in a computation or transmission queue.The slot duration can be set small, such as ∆ = 0.1 second.
  • Task model: Each arriving task receives a unique positive index km(t), while km(t) = 0 represents no new task arrival.
  • Task model: Task size λm(t) is selected from a discrete set Λ or set to zero when no task arrives, and tasks require processing density ρm.
  • Task offloading decision: For an offloaded task, the device selects one edge node, represented by binary variables ym,n(t) and vector ym(t).
  • Computation and transmission queues: The computation and transmission queues track waiting and completion-or-dropping time slots using queue capacities, deadlines, and prior tasks’ completion times.
  • Transmission queue: Transmission capacity is assumed constant to characterize edge-node load-level dynamics.

2.2 Edge Node Model

Each edge node maintains one queue per mobile device, and active queues share the node’s processing capacity equally. Queue evolution and task completion times account for arrivals, service, processing, and deadline-based dropping under uncertain future load.

  • Queues at Edge Nodes: Each edge node maintains M queues, with one queue corresponding to each mobile device.An offloaded task enters its corresponding edge-node queue at the beginning of the next time slot after complete reception.
  • Queues at Edge Nodes: Active queues are those receiving a task during the slot or remaining non-empty from the previous slot.The number of active queues at node n is represented by |B_n(t)|.
  • Task Processing: Active queues equally share each edge node’s processing capacity under a generalized processor sharing model.The model can be approximated by practical fair queuing algorithms.
  • Queue Dynamics: Queue length equals its previous value plus arrivals minus bits processed or dropped during the current time slot.The update uses the number of dropped bits e^edge_m,n(t) together with arrivals and service.
  • Task Processing or Dropping: A task’s completion time is the slot when it is processed or dropped, but that time remains unknown until the outcome occurs.The processing-start slot is constrained by queue placement and earlier tasks’ processing or dropping.

3 TASK OFFLOADING PROBLEM IN MEC

The task-offloading problem models each device as choosing actions from locally observed state information to minimize expected discounted long-term cost. The formulation captures task delay or deadline-drop penalties while accounting for other devices and time-varying system conditions.

  • State: At each slot, a device observes its task, queue information, and edge-node load history before selecting an action.The load-history matrix records the number of active queues at each edge node over the previous T_step slots.
  • Action: An action determines whether a task uses local computation or transmission and, for offloading, which edge node receives it.The device action space is A = {0, 1}^{1+N}.
  • Cost: A processed task incurs its delay, whereas a dropped task incurs a constant penalty C.Task delay is measured in time slots from arrival until processing or dropping.
  • Objective: Each device seeks a policy mapping states to actions that minimizes expected discounted long-term cost.The expectation includes time-varying arrivals, task requirements, and other devices’ offloading decisions.
  • Solution Approach: A DRL-based algorithm learns the mapping from state-action pairs to expected long-term cost despite unknown edge-load dynamics.The proposed approach is distributed and uses information available to each device through local observation.

4 DRL-BASED OFFLOADING ALGORITHM

The proposed distributed DRL algorithm lets each mobile device map observed state-action pairs to Q-values and choose the action with minimum expected long-term cost. Its neural network combines LSTM-based load-dynamics learning with dueling-DQN components, while edge nodes assist with training from device experience.

  • Distributed DRL algorithm: Each mobile device uses a neural network to map state-action pairs to Q-values and selects the action with minimum expected long-term cost.The mapping supports decentralized offloading decisions without requiring other devices’ offloading decisions.
  • Neural network architecture: The six-layer network comprises input, LSTM, two fully connected, advantage-and-value, and output layers.The network parameter vector contains the adjustable connection weights and neuron biases used during DRL training.
  • LSTM layer: The LSTM processes T step sequences of edge-load observations to learn load-level dynamics across time slots.Each LSTM unit receives one row of the load-history matrix, and sequential connections track variations over time.
  • Q-value estimation: The fully connected layers combine ordinary state information with learned load dynamics to produce action Q-values.These layers use neurons with rectified linear unit activations.
  • Dueling-DQN layer: The advantage-and-value and output layers implement dueling-DQN by separately learning state-value and action-advantage values before determining each action’s Q-value.The resulting Q-value combines the state-value with the action’s advantage relative to the average advantage across actions.
  • Distributed training: Edge nodes train device-specific networks using stored experience tuples containing state, action, cost, and next state.Each device is assigned an assisting edge node, whose replay memory supports training of evaluation and target networks.

5 PERFORMANCE EVALUATION

The proposed DRL-based algorithm is evaluated against no offloading, random offloading, PGOA, and ULOOF across episodes and varied system parameters. It consistently reduces dropped-task ratios and average delay, especially under high edge loads or delay-sensitive tasks.

  • Performance and Convergence: After around 350 episodes, the proposed algorithm converges to a dropped-task ratio of 0.02 and average delay of 0.52 second.Compared with benchmark methods, it reduces the dropped-task ratio by 86.4%−95.4% and average delay by 18.0%−30.1%.
  • Task Arrival Probability: As task arrival probability increases from 0.1 to 0.5, the proposed algorithm keeps the dropped-task ratio below 0.2, while benchmark ratios exceed 0.5.For moderate arrival probabilities of 0.3−0.8, the reduction is at least 13.3%; its average delay increases by 26.1% from probability 0.1 to 0.4, versus at least 34.5% for benchmarks.
  • Task Deadline: At a 0.6-second deadline, the proposed algorithm reduces the dropped-task ratio by 65.8%−79.3% versus benchmark methods and reaches below 0.01 above 1.4 seconds.Its converged average delay is around 0.54 second, compared with around 0.84 second for ULOOF and more than 0.96 second for other methods.
  • Task Density: At task density 0.5 Gigacycles per Mbits, the proposed algorithm reduces the dropped-task ratio by 41.4%−74.1% versus benchmarks, although average delays are similar.From density 0.05 to 0.25 Gigacycles per Mbits, both metrics increase less dramatically for the proposed algorithm than for benchmark methods.
  • System Processing Capacities and Device Scale: With 150 mobile devices, the proposed algorithm achieves a dropped-task ratio 53.4%−76.6% lower than benchmarks and average delay 9.0% lower than PGOA and ULOOF.At 3.5 GHz mobile-device capacity, it reaches a dropped-task ratio of 0.007 and average delay 31.4% and 29.4% below PGOA and ULOOF, respectively; at 15 GHz edge-node capacity, reductions are at least 57.0% and 9.4%.

6 CONCLUSION

The study addresses decentralized offloading for non-divisible, delay-sensitive tasks under unknown and time-varying edge-node loads. Its distributed algorithm reduces dropped-task ratios and average delay, especially for delay-sensitive tasks or high edge-node loads.

  • The distributed algorithm enables decentralized offloading decisions for non-divisible, delay-sensitive tasks under unknown edge-load dynamics.It also handles time-varying environments, including new task arrivals and changing computational requirements.
  • The algorithm reduces dropped-task ratios and average delay compared with several benchmark methods.The reported benefit is especially significant when tasks are delay-sensitive or edge-node loads are high.
  • Future cooperative learning could accelerate DRL training and improve performance by sharing trained neural networks across mobile devices.
Loading 2005.02459v1…