Energy-Delay Tradeoff in Helper-Assisted NOMA-MEC Systems: A Four-Sided Matching Algorithm

Mengmeng Ren, Long Yang, Hai Jiang, Jian Chen, Yuchen ZhouIEEE Trans. Communications 2023 · DOI · OpenReview

TL;DR

This paper tackles the challenge of optimizing resource allocation in mobile edge computing (MEC) systems that use Non-Orthogonal Multiple Access (NOMA) and employ "helpers" (e.g., nearby devices) to assist. They introduce a novel algorithm that balances energy consumption and task completion delay by modeling the problem as a complex four-sided matching game, achieving near-optimal performance with significantly reduced complexity.

What Problem Does This Paper Address?

Modern mobile devices are increasingly tasked with handling complex computations for applications like AI and IoT. While mobile cloud computing (MCC) offers a solution by offloading tasks to distant servers, it often incurs significant delays. Mobile Edge Computing (MEC) addresses this by bringing computation closer to users, deploying servers at the network edge. This paper further enhances MEC by incorporating "helpers" – other devices in proximity – to assist with task offloading and computation, especially when users have limited resources.

The core challenge lies in efficiently allocating limited resources (bandwidth, power, computation) among users, helpers, and MEC servers to achieve a desirable balance between minimizing energy consumption and reducing task completion delay. This is particularly difficult in NOMA systems, where multiple users can share the same resources, leading to complex interference management. The authors aim to optimize this by minimizing the maximum energy-delay tradeoff experienced by any user, ensuring a degree of fairness.

Methods

The authors tackle this complex optimization problem through a multi-stage approach:

  1. Problem Formulation: They define a novel "energy-delay tradeoff" metric as a weighted sum of energy consumption and delay. The problem is formulated as a mixed-integer nonlinear programming (MINLP) problem to minimize the maximum of this metric across all users.
  2. Decoupling and Reformulation: Due to the MINLP's complexity, they decouple it into two subproblems:
  3. PATACRA (Power Allocation, Task Assignment, and Computation Resource Allocation): This subproblem deals with continuous variables and is solved using an Iterative Parametric Convex Approximation (IPCA) algorithm. IPCA iteratively approximates non-convex parts of the problem with convex functions, allowing for efficient solutions.
  4. DUARA (Discrete User Association and RB Assignment): This subproblem deals with discrete variables (user-server/helper association, resource block assignment).
  5. Four-Sided Matching: The DUARA problem is then modeled as a four-sided matching problem. This is a novel approach where users, resource blocks (RBs), MEC helpers, and MEC servers are matched. They propose a Four-Sided UE-RB-Helper-Server Matching (FS-URHSM) algorithm to solve this. This algorithm uses sequential swap and leaving/joining operations to find a stable matching that optimizes the overall utility (derived from the PATACRA solution).

Datasets

Not discussed in the paper. The authors use simulated data for evaluation.

Key Insights and Ideas

  • Helper-Assisted NOMA is Promising: Integrating helpers into NOMA-MEC systems can significantly improve performance by leveraging spare resources and reducing user burden.
  • Four-Sided Matching for Resource Allocation: Modeling the complex resource allocation problem as a four-sided matching game (UEs, RBs, Helpers, Servers) is a novel and effective approach to handle the interdependencies.
  • IPCA for Non-Convex Optimization: The proposed IPCA algorithm effectively handles the non-convexity inherent in MEC resource allocation problems, offering a more efficient alternative to existing methods.
  • Min-Max Fairness is Achievable: The proposed FS-URHSM algorithm successfully achieves a near-optimal solution while ensuring that the worst-case energy-delay tradeoff among users is minimized, promoting fairness.
  • Tradeoff Between Complexity and Performance: The FS-URHSM algorithm achieves near-optimal performance with significantly lower computational complexity compared to exhaustive search methods.

Key Results

  • The proposed IPCA algorithm converges within approximately 5 iterations, demonstrating its efficiency and insensitivity to data size and weight factors.
  • The IPCA algorithm shows a performance improvement (lower mEDT gap) compared to an alternative optimization (AO) algorithm, achieving normalized gaps of around 23.8% and 15.3% for different data sizes.
  • The FS-URHSM algorithm achieves near-optimal performance, with normalized mEDT gaps of approximately 0.5% and 2.9% compared to an exhaustive search approach (ES-IPCA) for different system configurations.
  • The FS-URHSM algorithm outperforms other schemes (FDMA/TDMA with/without helpers) in terms of the energy-delay tradeoff, especially for systems with strict delay requirements.
  • The algorithm demonstrates good user fairness, with individual user EDTs being relatively consistent.

Limitations and Future Work

  • Complexity of Four-Sided Matching: While significantly better than exhaustive search, the FS-URHSM algorithm still has a worst-case complexity that grows with the number of users, helpers, servers, and RBs.
  • Assumptions: The paper relies on several assumptions, such as perfect SIC (Successive Interference Cancellation) and negligible result downloading time, which might not hold in all real-world scenarios.
  • Future Work: The authors suggest extending the work to consider more complex scenarios, such as imperfect CSI (Channel State Information) and dynamic environments. Further research could also explore different fairness metrics beyond min-max.

Summary updated

Abstract

This paper designs a helper-assisted resource allocation strategy in non-orthogonal multiple access (NOMA)-enabled mobile edge computing (MEC) systems, in order to guarantee the quality of service (QoS) of the energy/delay-sensitive user equipments (UEs). To achieve a tradeoff between the energy consumption and the delay, we introduce a novel performance metric, called \emph{energy-delay tradeoff}, which is defined as the weighted sum of energy consumption and delay. The joint optimization of user association, resource block (RB) assignment, power allocation, task assignment, and computation resource allocation is formulated as a mixed-integer nonlinear programming problem with the aim of minimizing the maximal energy-delay tradeoff. Due to the non-convexity of the formulated problem with coupled and 0-1 variables, this problem cannot be directly solved with polynomial complexity. To tackle this challenge, we first decouple the formulated problem into a power allocation, task assignment and computation resource allocation (PATACRA) subproblem. Then, with the solution obtained from the PATACRA subproblem, we equivalently reformulate the original problem as a discrete user association and RB assignment (DUARA) problem. For the PATACRA subproblem, an iterative parametric convex approximation (IPCA) algorithm is proposed. Then, based on the solution obtained from the PATACRA subproblem, we first model the DUARA problem as a four-sided matching problem, and then propose a low-complexity four-sided UE-RB-helper-server matching (FS-URHSM) algorithm. Theoretical analysis demonstrates that the proposed algorithms are guaranteed to converge to stable solutions with polynomial complexity. Finally, simulation results are provided to show the superior performance of our proposed algorithm in terms of the energy consumption and the delay.
BibTeX
@article{ren2023energy,
  author = {Mengmeng Ren and Long Yang and Hai Jiang and Jian Chen and Yuchen Zhou},
  title = {{Energy-Delay Tradeoff in Helper-Assisted NOMA-MEC Systems: A Four-Sided Matching Algorithm}},
  journal = {IEEE Trans. Communications},
  year = {2023},
  doi = {10.1109/tcomm.2023.3349166},
}
Figure