Fractional Programming for Communication Systems-Part II: Uplink Scheduling via Matching

Kaiming Shen, Wei Yu

Introduction

Optimizing multi-cell wireless networks involves a complex balancing act: base stations must simultaneously decide which users to schedule, determine their optimal transmit power, and design beamforming vectors to maximize overall network performance. This task is particularly daunting in the uplink—where users transmit to base stations—due to the dynamic and highly coupled nature of inter-cell interference. This paper introduces a novel framework based on Fractional Programming (FP) that successfully decouples these variables, enabling exact discrete scheduling through weighted bipartite matching and delivering significant performance boosts for cell-edge users.

In modern cellular networks, interference management is the primary bottleneck for spectral efficiency. While downlink interference originates from a small number of fixed base stations, uplink interference is generated by the users themselves. Consequently, the interference seen by a base station depends entirely on which specific users are active in neighboring cells at any given moment.

Comparison of interference patterns in (a) uplink and (b) downlink multicell networks.

Mathematically, maximizing the network sum rate involves optimizing the logarithm of the Signal-to-Interference-plus-Noise Ratio (SINR). This results in a non-convex problem that mixes continuous variables (power, beamforming) with discrete variables (user selection). Traditional approaches often rely on continuous relaxations of the scheduling variables. However, these heuristics frequently suffer from a "premature turning-off" problem, where users experiencing high initial interference are permanently assigned zero power by the algorithm, even if favorable scheduling in neighboring cells would have later cleared their path.

Decoupling via Fractional Programming

To overcome these limitations without resorting to problematic relaxations, the authors propose a two-stage transformation within the FP framework:

  1. Lagrangian Dual Transform: This technique reformulates the logarithmic rate function, effectively moving the SINR ratio outside the logarithm by introducing auxiliary variables.
  2. Quadratic Transform: This step decouples the numerator (signal) and denominator (interference plus noise) of the SINR fraction.

By applying these transforms, the global optimization problem is decomposed into per-cell subproblems. Once decoupled, the discrete scheduling decisions can be solved exactly using weighted bipartite matching. This allows the network to match users to available data streams efficiently using combinatorial algorithms like the Hungarian method, avoiding the pitfalls of gradient-based relaxations.

Performance Gains and Scalability

The proposed FP method was evaluated against standard baselines, including the Weighted Minimum Mean-Square-Error (WMMSE) algorithm and fixed-interference heuristics. Simulations in a 7-cell environment demonstrated that the FP approach significantly improves the experience of the most disadvantaged users.

Cumulative distribution of data rates, showing the FP method's superiority, particularly for low-rate (cell-edge) users.

As shown in the data rate distribution, the FP method provides a substantial "shift to the right," particularly at the lower end of the spectrum. The 10th-percentile users—typically those at the cell edge—saw data rate improvements of over 50%. Furthermore, the FP framework scales more effectively than WMMSE. While WMMSE complexity grows quadratically with the total number of users in the network, the FP method's per-cell decomposition leads to a more manageable linear-quadratic complexity, making it better suited for dense, high-capacity deployments.

Conclusion

By moving away from continuous relaxations and leveraging the decoupling power of Fractional Programming, this work provides a robust solution for the joint scheduling and power control problem in uplink networks. The ability to maintain a "memory" of link quality through auxiliary variables prevents the premature exclusion of users and ensures a more equitable and efficient distribution of network resources. Future research will explore extending this framework to more complex scenarios, such as full-duplex communications and networks with imperfect channel state information.

Summary updated

Abstract

This two-part paper develops novel methodologies for using fractional programming (FP) techniques to design and optimize communication systems. Part I of this paper proposes a new quadratic transform for FP and treats its application for continuous optimization problems. In this Part II of the paper, we study discrete problems, such as those involving user scheduling, which are considerably more difficult to solve. Unlike the continuous problems, discrete or mixed discrete-continuous problems normally cannot be recast as convex problems. In contrast to the common heuristic of relaxing the discrete variables, this work reformulates the original problem in an FP form amenable to distributed combinatorial optimization. The paper illustrates this methodology by tackling the important and challenging problem of uplink coordinated multi-cell user scheduling in wireless cellular systems. Uplink scheduling is more challenging than downlink scheduling, because uplink user scheduling decisions significantly affect the interference pattern in nearby cells. Further, the discrete scheduling variable needs to be optimized jointly with continuous variables such as transmit power levels and beamformers. The main idea of the proposed FP approach is to decouple the interaction among the interfering links, thereby permitting a distributed and joint optimization of the discrete and continuous variables with provable convergence. The paper shows that the well-known weighted minimum mean-square-error (WMMSE) algorithm can also be derived from a particular use of FP; but our proposed FP-based method significantly outperforms WMMSE when discrete user scheduling variables are involved, both in term of run-time efficiency and optimizing results.
BibTeX
@article{shen2018fractional,
  author = {Kaiming Shen and Wei Yu},
  title = {{Fractional Programming for Communication Systems-Part II: Uplink Scheduling via Matching}},
  journal = {IEEE Trans. Signal Process.},
  year = {2018},
  doi = {10.1109/tsp.2018.2812748},
}
Figure