Introduction
5G networks must support a diverse array of services with conflicting requirements, ranging from ultra-reliable low-latency communications (URLLC) for autonomous systems to enhanced mobile broadband (eMBB) for high-definition streaming. To accommodate this heterogeneity, 5G introduces flexible numerology, allowing for variable subcarrier spacing (SCS) and transmission time intervals (TTIs).
This flexibility transforms resource allocation into a complex 2D packing problem. The challenge lies in scheduling different-sized resource blocks into a time-frequency grid without overlaps while strictly adhering to the latency deadlines of mission-critical services. This paper investigates the computational complexity of this task and proposes an efficient scheduling framework.
Methodology
The authors categorize services into two groups: latency-critical ($K^{(\ell)}$), which require a specific data volume within a hard deadline, and best-effort ($K^{(c)}$), which aim to maximize throughput once latency needs are met.
Complexity and Algorithm Design
The paper proves that the optimal allocation of flexible numerology is NP-hard via a reduction to the Partition Problem, meaning a perfect solution is computationally impossible for large networks in real-time. To address this, the authors developed the LP+LD algorithm, a hybrid approach that combines:
- Linear Programming (LP) Relaxation: Estimates the value of block assignments by treating binary variables as continuous.
- Lagrangian Duality (LD): Relaxes non-overlapping constraints into penalty-based multipliers to guide the search in the dual space.
By integrating insights from both methods, the LP+LD algorithm employs a greedy strategy to pack the grid efficiently, achieving a complexity of $O(|B||K| \log (|B||K|))$, which is suitable for real-world base station schedulers.
Performance Evaluation
The proposed framework was evaluated using simulations aligned with 3GPP Release 15 standards, featuring various multipath channel profiles and four distinct block shapes (SCS ranging from 15 kHz to 60 kHz).
Key Findings
- Superiority of Flexibility: As shown in the results, fixed-numerology schemes (like those used in LTE) often fail to find feasible schedules when latency requirements are strict (e.g., $\tau = 0.25$ ms). In contrast, the flexible approach maintains high throughput by dynamically adjusting block shapes.
- Near-Optimality: The LP+LD algorithm consistently performs within 10% of the global optimum while significantly reducing computational overhead compared to standard integer programming solvers.
- Optimal Shapes: Blocks with 0.25ms-30kHz (Shape 2) were found to be particularly effective, offering a robust balance between meeting deadlines and maintaining spectral efficiency against channel fading.
Conclusion and Future Work
Flexible numerology is essential for the co-existence of heterogeneous 5G services. The proposed LP+LD algorithm provides a scalable, near-optimal solution for real-time scheduling. Future research will focus on modeling inter-numerology interference—the noise generated between adjacent subbands with different SCS—and optimizing the signaling overhead required to communicate these dynamic configurations to user equipment.
Summary updated