Distributionally Robust Optimization for Computation Offloading in Aerial Access Networks

Guanwang Jiang, Ziye Jia, Lijun He, Chao Dong, Qihui Wu, Zhu HanarXiv 2024 · OpenReview

TL;DR

This paper tackles the challenge of optimizing computation offloading in aerial access networks (AANs) when task data sizes are uncertain. They propose a novel "distributionally robust optimization" (DRO) approach that leverages historical data to model uncertainty, leading to a more practical and efficient algorithm (MDRLOA) that outperforms existing methods in reducing latency and energy consumption.

What Problem Does This Paper Address?

The increasing demand for data offloading and computation, especially in remote areas, poses a significant challenge for ensuring Quality of Service (QoS). Aerial Access Networks (AANs), utilizing drones (UAVs) and high-altitude platforms (HAPs), offer a promising solution due to their flexibility and low latency. Integrating Multi-Access Edge Computing (MEC) onto these aerial platforms further enhances their capabilities. However, a critical hurdle is the uncertainty surrounding the data sizes of tasks. Traditional optimization methods struggle with this uncertainty, either requiring precise probability distributions (stochastic optimization) or leading to overly conservative solutions (robust optimization). This paper aims to bridge this gap by developing an optimization framework that robustly handles uncertain task data sizes in AAN-MEC systems, specifically focusing on minimizing system latency.

Methods

The core of this paper lies in its application of Distributionally Robust Optimization (DRO). Instead of assuming known probability distributions, DRO constructs "uncertainty sets" based on historical data to characterize the possible distributions of uncertain task sizes. This allows for a more data-driven and less assumption-heavy approach.

The authors formulate a distributionally robust optimization problem to minimize the worst-case expected system latency. Recognizing that this problem is NP-hard, they employ a relaxation technique, transforming the mixed-integer minimax problem into a linear programming problem. This leads to the development of their proposed MEC-based distributionally robust latency optimization algorithm (MDRLOA). MDRLOA involves solving a series of sub-problems (P1-P4) that iteratively determine the optimal task offloading decisions and probability distributions under uncertainty. The algorithm utilizes a branch-and-bound approach to recover integer solutions from relaxed continuous variables.

Datasets

Not discussed in the paper. The paper relies on simulated data for evaluation, with parameters set based on typical values for AAN-MEC systems.

Key Insights and Ideas

  • DRO for Practical Uncertainty: The paper highlights the practical advantage of DRO in scenarios with unknown probability distributions, making it more applicable than traditional stochastic or robust optimization methods for real-world AAN-MEC deployments.
  • Balancing Latency and Energy: MDRLOA demonstrates a superior ability to balance system latency reduction with energy consumption minimization, a crucial trade-off in resource-constrained aerial networks.
  • Impact of Tolerance Value: The study reveals that a larger "tolerance value" (epsilon, ε) in the uncertainty set, while increasing conservativeness and robustness, also leads to higher system latency. This underscores the importance of carefully tuning this parameter.
  • Resource Scaling: Simulation results show that increasing HAP and UAV quotas (computing resources) directly leads to lower system latency, as expected, but MDRLOA provides a robust way to manage these resources under uncertainty.

Key Results

Simulations demonstrate that MDRLOA significantly outperforms existing methods:

  • System Latency: MDRLOA achieves approximately 18.8% lower system latency on average compared to a baseline "DO" (Deterministic Optimization) approach.
  • Energy Consumption: MDRLOA saves about 6.9% energy on average compared to a "RO" (Robust Optimization) approach, indicating it's less conservative while still being robust.
  • Robustness: The paper claims MDRLOA exhibits higher robustness compared to DO, meaning it performs better across a wider range of task data size variations.

Limitations and Future Work

  • Computational Complexity: While MDRLOA is designed to be efficient, the paper acknowledges that the computational complexity of solving the optimization problems (P2 and P4) can still be significant, especially with a large number of users and constraints.
  • Parameter Tuning: The performance of MDRLOA is influenced by the choice of the tolerance value (ε) for the uncertainty set. Finding the optimal ε for different scenarios might require further investigation.
  • Future Work: The authors suggest that future research could explore dynamic environments, more complex network topologies, and the integration of other performance metrics beyond latency and energy consumption.

Summary updated

Abstract

With the rapid increment of multiple users for data offloading and computation, it is challenging to guarantee the quality of service (QoS) in remote areas. To deal with the challenge, it is promising to combine aerial access networks (AANs) with multi-access edge computing (MEC) equipments to provide computation services with high QoS. However, as for uncertain data sizes of tasks, it is intractable to optimize the offloading decisions and the aerial resources. Hence, in this paper, we consider the AAN to provide MEC services for uncertain tasks. Specifically, we construct the uncertainty sets based on historical data to characterize the possible probability distribution of the uncertain tasks. Then, based on the constructed uncertainty sets, we formulate a distributionally robust optimization problem to minimize the system delay. Next,we relax the problem and reformulate it into a linear programming problem. Accordingly, we design a MEC-based distributionally robust latency optimization algorithm. Finally, simulation results reveal that the proposed algorithm achieves a superior balance between reducing system latency and minimizing energy consumption, as compared to other benchmark mechanisms in the existing literature.
BibTeX
@misc{jiang2024distributionally,
  author = {Guanwang Jiang and Ziye Jia and Lijun He and Chao Dong and Qihui Wu and Zhu Han},
  title = {{Distributionally Robust Optimization for Computation Offloading in Aerial Access Networks}},
  year = {2024},
  eprint = {2408.02037},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.02037},
}
Figure