Learning to Optimize Resource Assignment for Task Offloading in Mobile Edge Computing

Yurong Qian, Jindan Xu, Shuhan Zhu, Wei Xu, Lisheng Fan, George K. Karagiannidis

TL;DR

This paper introduces Intelligent Branch and Bound (IBnB), a hybrid approach that accelerates resource allocation in Mobile Edge Computing (MEC). By using deep learning to predict which branches of a search tree can be safely ignored (pruned), the authors reduce computational complexity by over 80% while maintaining near-optimal performance.

What Problem Does This Paper Address?

In Mobile Edge Computing, mobile devices offload heavy computational tasks to nearby Access Points (CAPs) to save battery and reduce latency. However, deciding exactly how to assign these tasks across various subchannels is a nightmare for optimization.

Mathematically, this is a Mixed-Integer Nonlinear Programming (MINLP) problem. It involves both discrete decisions (which device uses which channel) and continuous variables (how much data to send). While the classic Branch and Bound (BnB) algorithm can find the perfect solution, it suffers from "combinatorial explosion"—as the number of devices grows, the time required to find the solution grows exponentially, making it too slow for real-time mobile networks.

Methods

The authors propose a "model-and-data-driven" hybrid called IBnB.

  1. The Foundation (BnB): The algorithm still uses the traditional tree-search structure of Branch and Bound, which ensures that the search remains grounded in the actual physics and constraints of the MEC system.
  2. The "Intelligence" (Deep Learning): Instead of manually checking every branch, the authors train a 6-layer Deep Neural Network (DNN) to act as a smart classifier. This DNN looks at the attributes of a "node" in the search tree—such as the current objective value and the level of the tree—and predicts whether that branch is likely to lead to the optimal solution.
  3. Smart Pruning: If the DNN’s output falls below a certain threshold ($\theta$), the branch is "pruned" (discarded) immediately. This prevents the algorithm from wasting time on dead ends.
  4. Adaptive Thresholding: To prevent "over-pruning" (where the AI is too aggressive and misses the best solution entirely), the authors include an adaptive mechanism. If the search finishes without finding a feasible solution, the algorithm automatically lowers the pruning threshold and tries again.

Datasets

The researchers did not use a public dataset; instead, they generated a custom dataset specifically for this problem:

  • Training Data Generation: They ran the conventional, slow BnB algorithm on various simulated MEC scenarios to find optimal paths.
  • Labels: Nodes that were part of the path to the optimal solution were labeled "1" (keep), while redundant nodes were labeled "0" (prune).
  • Simulation Environment: The data reflects a system with Rayleigh fading channels, a 10 MHz bandwidth, and devices with transmit powers between 1.0 and 1.5 Watts.

Key Insights and Ideas

  • Strategy over Solutions: Most "Learning to Optimize" papers try to train a DNN to output the final answer directly. This often fails because the DNN becomes a "black box" that can't handle new constraints. By training the DNN to learn the pruning strategy within a mathematical framework, the authors keep the best of both worlds: AI speed and algorithmic reliability.
  • The Complexity-Optimality Trade-off: The choice of the threshold $\theta$ is the "dial" for performance. A high threshold makes the algorithm lightning-fast but slightly less accurate; a low threshold is slower but more precise.
  • Generalization: Because the DNN learns the logic of the search tree rather than just mapping channel gains to offloading decisions, it demonstrates better generalization across different network scenarios.

Key Results

The numerical simulations yielded impressive efficiency gains:

  • Complexity Reduction: The IBnB approach reduced the number of searched nodes by over 80% compared to conventional BnB.
  • Near-Optimality: With a threshold of $10^{-12}$, the IBnB reached 98% of the optimal performance of the exhaustive search. Even with a more aggressive threshold of $10^{-7}$, it still achieved 80% optimality.
  • Robustness: The variance in computation time was significantly lower than standard BnB, which is crucial for "delay-sensitive" tasks where consistent performance is mandatory.

Limitations and Future Work

  • Offline Training: The DNN currently requires offline training on data generated by the slow BnB algorithm. In a rapidly changing real-world environment, the model might need a way to update itself online.
  • Initial Threshold Selection: While the adaptive thresholding works, the "first guess" for the threshold still relies on manual setting. Automating this initial choice based on real-time channel conditions could be a next step.
  • Scalability: The paper tests the system with a specific number of MDs (Mobile Devices); further research could explore how the DNN handles massive-scale IoT deployments with thousands of devices.

Summary updated

Abstract

In this paper, we consider a multiuser mobile edge computing (MEC) system, where a mixed-integer offloading strategy is used to assist the resource assignment for task offloading. Although the conventional branch and bound (BnB) approach can be applied to solve this problem, a huge burden of computational complexity arises which limits the application of BnB. To address this issue, we propose an intelligent BnB (IBnB) approach which applies deep learning (DL) to learn the pruning strategy of the BnB approach. By using this learning scheme, the structure of the BnB approach ensures near-optimal performance and meanwhile DL-based pruning strategy significantly reduces the complexity. Numerical results verify that the proposed IBnB approach achieves optimal performance with complexity reduced by over 80%.
BibTeX
@misc{qian2022learning,
  author = {Yurong Qian and Jindan Xu and Shuhan Zhu and Wei Xu and Lisheng Fan and George K. Karagiannidis},
  title = {{Learning to Optimize Resource Assignment for Task Offloading in Mobile Edge Computing}},
  year = {2022},
  eprint = {2203.09954},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.09954},
}
Figure