TL;DR
This paper tackles the challenge of minimizing data transmission time in uplink multi-subcarrier NOMA (Non-Orthogonal Multiple Access) systems, crucial for latency-sensitive applications like federated learning. They introduce a novel joint optimization framework for power allocation, user pairing, and scheduling, proving its NP-hardness and proposing both optimal and heuristic algorithms to achieve significant reductions in completion time compared to existing methods.
What Problem Does This Paper Address?
In modern wireless communication, especially for emerging applications like mobile edge computing and federated learning, minimizing data transmission latency is paramount. These applications often involve numerous devices needing to send data to a central base station (BS) within strict time constraints. Traditional NOMA systems, while offering spectral efficiency gains, face challenges in optimizing for maximum completion time, particularly in multi-subcarrier scenarios. Existing research often simplifies these systems (e.g., single-subcarrier) or makes impractical assumptions about packet transmission. This paper addresses the need for a comprehensive approach to optimize uplink multi-subcarrier NOMA systems by jointly considering power allocation, user pairing, and scheduling to minimize the maximum completion time across all devices.
Methods
The authors propose a framework for optimizing maximum completion time in uplink multi-subcarrier NOMA systems. Key methodological contributions include:
- Problem Formulation: They formulate the problem as minimizing the maximum completion time ($C_{max}$) by jointly optimizing power allocation, user pairing, and subcarrier scheduling.
- NP-Hardness Proof: They prove that this joint optimization problem is NP-hard, necessitating the development of efficient algorithms.
- Optimal Power Allocation for Pairs: For a single NOMA pair (two users sharing a subcarrier), they derive an optimal power allocation scheme to minimize their individual completion time, considering different decoding orders.
- Optimal Algorithm for Special Case (K=2M): When the number of users ($K$) is twice the number of subcarriers ($M$), they propose an optimal algorithm based on maximum weight matching and binary search to find the best user pairings.
- Heuristic Algorithm for General Case (K>2M): For the more general scenario where $K > 2M$, they propose a two-step heuristic algorithm: first, pairing users to minimize total completion time, and second, scheduling these pairs using a longest-processing-time-first (LPT) approach.
- Federated Learning Application: They demonstrate the practical applicability of their scheme by applying it to data aggregation in wireless federated learning.
Datasets
Not discussed in the paper. The paper uses simulated data for evaluation.
Key Insights and Ideas
- Joint Optimization is Crucial: The paper highlights that optimizing power allocation, user pairing, and scheduling simultaneously is essential for achieving significant improvements in maximum completion time, rather than optimizing them in isolation.
- NOMA's Latency Advantage: Despite the complexity, NOMA, when optimally managed, can substantially reduce transmission times compared to OMA (Orthogonal Multiple Access), especially in scenarios with many users and limited subcarriers.
- Decoding Order Matters: The order in which users' packets are decoded within a NOMA pair significantly impacts their completion time, and the paper provides a method to determine the optimal order.
- Federated Learning Synergy: The proposed NOMA optimization scheme shows strong potential for accelerating federated learning by reducing the communication rounds needed to achieve a target accuracy.
Key Results
- Significant Completion Time Reduction: In simulations, the proposed NOMA-LPT algorithm reduced completion times by up to 53.3% compared to OMA-LPT and other NOMA schemes for the $K=2M$ case. For the general $K>2M$ case, NOMA-LPT reduced completion times by up to 18.3% compared to OMA-LPT.
- Federated Learning Performance: In a simulated federated learning scenario, NOMA achieved shorter transmission times (up to 44.6% reduction) for the same communication rounds and accuracy compared to OMA. It also achieved the same accuracy with significantly less transmission time.
- Optimal Solution for K=2M: The paper presents an optimal algorithm for the $K=2M$ case, demonstrating its effectiveness.
Limitations and Future Work
- NP-Hardness: The inherent NP-hardness of the general problem means that optimal solutions for large-scale systems are computationally intractable, necessitating the use of heuristic algorithms.
- Assumptions: The paper assumes constant channel gains within a transmission round and a fixed packet size. Real-world scenarios might involve more dynamic conditions.
- Future Work: The authors suggest exploring more advanced scheduling algorithms and considering additional system constraints or objectives, such as energy efficiency, in future research. They also imply that extending this to more complex NOMA scenarios (e.g., more than two users per subcarrier) would be a valuable direction.
Summary updated