PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kaiming Shen, Wei Yu

arXiv:1802.10197v2cs.IT

TL;DR

The paper addresses discrete or mixed discrete-continuous communication optimization, focusing on uplink coordinated multi-cell scheduling jointly with power control and beamforming. It develops an FP reformulation that decouples interfering links and combines distributed optimization with weighted bipartite matching. The method has provable convergence and outperforms WMMSE in utility and low-rate-user performance, while WMMSE does not explicitly handle discrete scheduling.

  • Problem

    Discrete scheduling problems cannot generally be recast as convex programs and must be optimized jointly with continuous variables such as transmit powers and beamformers.

  • Method

    The proposed FP method uses quadratic and Lagrangian dual transforms to decouple interfering links and optimize scheduling, power, and beamforming through distributed weighted bipartite matching.

  • Results

    The proposed algorithm performs better in utility than baseline power control and fixed-interference methods, with 10th-percentile user rates at least 50% higher than fixed-interference.

  • Takeaways & Limitations

    FP with weighted bipartite matching enables joint optimization of discrete scheduling and continuous communication variables, whereas WMMSE is not well equipped for discrete scheduling.

Abstract

from arXiv · show

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.

I. OVERVIEW

This paper applies fractional programming to coordinated uplink scheduling with discrete and continuous variables, avoiding relaxation-based approaches through distributed combinatorial optimization. Its framework jointly optimizes scheduling with power control or beamforming and relates FP to WMMSE.

  • Motivation: Uplink scheduling is harder than downlink scheduling because neighboring-cell scheduling decisions strongly change the interference pattern.The problem jointly involves user selection, transmit powers, and beamforming vectors.
  • Motivation: Discrete scheduling variables make the quadratic transform alone insufficient, unlike the continuous problems treated in Part I.The paper therefore addresses a mixed discrete-continuous optimization setting that generally lacks a convex reformulation.
  • FP approach: Instead of relaxing discrete variables, the method uses a Lagrangian dual transform and weighted bipartite matching to obtain efficient distributed scheduling optimization.The transform moves the fractional SINR term outside the logarithm, enabling subsequent quadratic-transform and matching steps.
  • Applications: The framework jointly optimizes uplink user scheduling and transmit power across multiple cells, with extensions to D2D and full-duplex settings.Auxiliary variables support distributed joint optimization of the discrete scheduling and continuous power variables.
  • Applications: The framework also jointly optimizes user scheduling and beamforming in MIMO networks using matching algorithms.Nearest-point projection handles discrete beamforming codebooks and discrete power control more efficiently than direct searching.
  • Relation to WMMSE: WMMSE is shown to be a particular form of FP, while the proposed FP application is designed to handle discrete scheduling variables more advantageously.The paper reviews quadratic and multidimensional complex transforms as components of the broader FP methodology.

III. LAGRANGIAN DUAL TRANSFORM

The Lagrangian dual transform reformulates weighted sums of logarithmic SINR ratios into an equivalent sum-of-ratios problem using auxiliary variables. This exposes a form that can subsequently be processed by quadratic transforms for discrete or mixed optimization.

  • Role in scheduling: The transform moves SINR outside the logarithm, allowing a subsequent quadratic transform to express optimization variables in linear terms.This role is central to applying FP to discrete scheduling problems.
  • Target problem: Weighted sum-of-logarithms objectives model communication-network weighted sum-rate maximization through ratios interpreted as SINR terms.The feasible set may contain discrete or mixed discrete-continuous variables, and the original problem has no known convex reformulation.
  • Transform: The Lagrangian dual transform converts the weighted sum-of-logarithms problem into an equivalent sum-of-ratios form.It introduces one auxiliary variable γ_m for each ratio term.
  • Equivalence: The transformed and original problems have the same optimal solutions in x and the same optimal objective values.For fixed x, the transformed objective is concave and differentiable in the auxiliary variables.
  • Equivalence: The optimal auxiliary variable satisfies γ⋆ = A_m(x)/B_m(x), so substituting it recovers the original weighted sum-of-logarithms objective exactly.This constructive characterization establishes the transform’s equivalence.

C. Constructive Derivation

The constructive derivation develops the Lagrangian dual transform by introducing auxiliary ratio variables, exploiting convexity and strong duality, and recovering an equivalent formulation.

  • Auxiliary-variable reformulation: The derivation introduces γ_m variables to replace each ratio inside the logarithm, creating an outer optimization over x and an inner optimization over γ.The inner problem fixes x and optimizes the auxiliary variables subject to the ratio constraints.
  • Dual construction: Because the inner optimization is convex in γ, strong duality permits an equivalent dual formulation with multipliers λ_m.The Lagrangian is formed for each inequality constraint, and the dual problem is equivalent to the primal inner problem.
  • Stationarity: The saddle-point first-order condition determines the relationship between γ⋆_m and λ⋆_m through the derivative of the Lagrangian.The derivation imposes ∂L/∂γ_m = 0 and uses the resulting condition together with the known inner optimum.
  • Equivalent formulation: Substituting the resulting expressions for the auxiliary and dual variables yields the transformed terms A_m(x) + B_m(x).The transformed expression is then combined with the outer maximization over x.
  • Extension: The same Lagrangian-dual procedure can be extended to the multidimensional complex case, although the paper omits the derivation details for Theorem 4.This extension is stated as a remark rather than developed constructively in the supplied passage.

IV. JOINT UPLINK SCHEDULING AND POWER CONTROL

The paper formulates coordinated uplink scheduling and power control as a discrete-continuous FP problem, using coupled transforms and per-cell updates to obtain a convergent distributed algorithm.

  • Problem formulation: Coordinated uplink scheduling selects users and transmit powers across cells, but each scheduling choice strongly affects neighboring-cell interference and the objective is nonconvex in power.In the SISO setting, at most one user is scheduled per cell, making the problem jointly discrete and continuous.
  • Implicit scheduling by power control: Power-control formulations can suffer premature turning-off: a link deactivated early may never reactivate because the local gradient discourages it.The issue follows from the highly nonconvex objective and sensitivity to initialization.
  • Problem formulation: Naive per-cell alternating updates lack guaranteed convergence because changing a scheduled user can drastically change the interference pattern.The paper identifies this instability as a central obstacle to independently optimizing scheduling and power.
  • FP approach: The proposed method combines the Lagrangian dual and quadratic transforms to decouple per-cell scheduling and power updates while preserving convergence.Quadratic transformation alone is insufficient; the combined reformulation enables individual updates of scheduling and power.
  • FP approach: With auxiliary variables fixed, each cell can determine its scheduled user and optimized power independently, then select the user maximizing the reformulated objective.The resulting scheduling criterion has a utility-minus-penalty structure that accounts for both local gain and interference imposed on neighboring cells.
  • Convergence and complexity: Algorithm 1 converges with a monotonically nondecreasing weighted sum rate, although the discrete scheduling subproblem remains difficult to optimize globally.The paper states that even with power fixed, finding the optimal scheduling assignment is NP-hard.
  • Practical scope: Obtaining CSI for all users and including all users in scheduling can be prohibitively costly, motivating a two-stage strategy that first narrows the candidate set.The refinement stage applies Algorithm 1 to the reduced set to lower runtime and CSI-acquisition costs.

D. Simulation Results

The proposed coordinated uplink scheduling and power-control method is evaluated against power-control and fixed-interference baselines using proportional-fairness simulations and user-rate distributions.

  • Simulation Setup: The simulation uses a 7-cell wrapped-around network with 84 uniformly placed users and strongest-BS association.Users have a maximum transmit PSD of −47dBm/Hz, with −169dBm/Hz background noise over 10MHz bandwidth.
  • Simulation Setup: User priority weights are updated as reciprocals of long-term average rates to maximize the proportional-fairness log-utility.The utility is computed using long-term average user rates expressed in Mbps.
  • Baselines: The power-control baseline treats unscheduled users as having zero power, turning scheduling into a highly nonconvex global power-control problem.The WMMSE algorithm is used for this baseline in the simulation.
  • Baselines: The fixed-interference baseline alternates per-cell weighted-rate scheduling with scheduled-user power updates until convergence or a fixed iteration limit.Scheduling assumes the interference pattern from the previous iteration.
  • Results: The proposed method achieves at least 50% higher 10th-percentile user rate than the fixed-interference method.It also provides much better utility than both baselines while maintaining low overall complexity.

V. JOINT UPLINK SCHEDULING AND BEAMFORMING

The paper extends coordinated multi-cell uplink optimization to jointly schedule users and optimize transmit beamformers in a MIMO network.

  • Problem Scope: The MIMO formulation jointly optimizes uplink user schedules, transmit beamformers, and power across multiple cells to maximize network utility.This generalizes the earlier uplink scheduling and power-control problem by adding beamformer optimization.

A. Problem Formulation

The MIMO uplink problem jointly selects users and beamformers across data streams, then uses FP reformulation to obtain distributed per-cell matching updates with convergence guarantees.

  • A. Problem Formulation: Each BS may schedule up to M users, represented by scheduling variables s and beamformers V across its M data streams.The formulation defines users by associated BS and includes power constraints and weighted sum-rate maximization.
  • A. Problem Formulation: Multiple scheduled users create both cross-cell and same-cell interference, making the MIMO problem harder than the SISO case.The additional same-cell interference arises because several users can be scheduled at each BS.
  • B. FP Reformulation and Weighted Bipartite Matching: FP reformulation applies a multidimensional Lagrangian dual transform and quadratic-transform machinery to the joint scheduling and beamforming objective.The reformulated problem introduces auxiliary variables for each data stream while retaining the original power constraints.
  • B. FP Reformulation and Weighted Bipartite Matching: For fixed primal variables, each auxiliary γ update equals the resulting uplink SINR in its data stream.The γ subproblem is convex and can be solved efficiently by setting its derivative to zero.
  • B. FP Reformulation and Weighted Bipartite Matching: The auxiliary y variables are updated explicitly, with each optimal y equal to a scaled MMSE receiver.These updates precede the joint optimization of scheduling and beamforming variables.
  • B. FP Reformulation and Weighted Bipartite Matching: FP decouples scheduling by cell, making each scheduling update a weighted bipartite matching between users and data streams.Matching weights are analytically determined, and negative-weight edges can be removed because assigning them would decrease the reformulated objective.
  • B. FP Reformulation and Weighted Bipartite Matching: Matching can be solved in O((K + M)^3), or O((K + M)^2) with finite-precision weights, using established algorithms such as Hungarian or auction methods.The iterative algorithm updates auxiliary variables, γ, and scheduling-beamforming variables until the reformulated objective converges.
  • B. FP Reformulation and Weighted Bipartite Matching: Algorithm 2 converges with nondecreasing weighted sum rate, while its fixed-scheduling limit is a stationary point with respect to beamformers.The paper notes that optimizing the scheduling variable exactly for fixed beamformers is already NP-hard.

C. Discrete Beamforming

For codebook-constrained beamforming, the paper replaces exhaustive discrete search with nearest-point projection of the relaxed FP beamformer while preserving optimality for the reformulated objective.

  • Codebook-Constrained Beamforming: The discrete beamforming setting restricts each transmit beamformer to a finite codebook while retaining its power constraint.Each codebook element is a possible beamforming vector.
  • Codebook-Constrained Beamforming: For a scheduled user and data stream, the best codebook beamformer is selected by searching over the available beamforming vectors.The resulting utility weights are then used in the same weighted matching process.
  • Efficient Discrete Update: Nearest-point projection reduces discrete beamformer optimization from O(|V|) search to O(log |V|) complexity.The reduction exploits the concave quadratic structure of the reformulated objective and can be implemented with a k-d tree.
  • Efficient Discrete Update: The relaxed beamformer is obtained without the codebook constraint, then projected to the closest codebook vector for each data stream.This projection is equivalent to the direct discrete optimization of the reformulated objective, rather than merely a heuristic rounding step.
  • Efficient Discrete Update: The nearest-point projection is realized with average O(log |V|) insertion, search, and deletion operations in a preconstructed k-d tree.The same argument yields one-dimensional bisection search for discrete power control in the SISO case.

D. Simulation Results

The simulations compare the proposed coordinated uplink method with WMMSE and fixed-interference benchmarks in a 7-cell MIMO network. Coordinating user schedules and beamformers is reported as crucial to network performance.

  • The evaluation uses a 7-cell wrapped-around network with 84 users, 2 antennas per user, and 4 antennas per base station.Users are associated with the base station providing the strongest channel, and proportional-fair weights are updated from long-term average rates.
  • The benchmarks are WMMSE and a fixed-interference heuristic, alongside the proposed FP-based scheduling and beamforming method.WMMSE implicitly schedules users through nonzero beamformers, while the fixed-interference method alternates beamforming and scheduling under fixed neighboring-cell interference.
  • The proposed method is reported to have a significant advantage over the two baselines in the user-rate comparison shown in Fig. 4.Fig. 4 compares cumulative distribution functions of user rates across the methods.
  • Coordinating user schedules and beamformers is crucial to network performance.

VI. CONNECTION WITH WMMSE

The paper connects WMMSE to FP, showing that WMMSE arises from a particular FP reformulation but does not explicitly decouple discrete scheduling variables. The proposed FP formulation instead enables distributed scheduling through weighted bipartite matching.

  • The FP and WMMSE approaches share a quadratic-transform foundation, but they apply the transform differently to obtain distinct reformulations.The paper presents multiple ways to apply the multidimensional quadratic transform to the relevant ratios.
  • WMMSE can be derived by iteratively updating FP auxiliary variables, beamformers, and receivers for a fixed scheduling variable.The resulting beamformer procedure is exactly the WMMSE algorithm for optimal beamforming.
  • The alternative reformulation does not decouple scheduling variables across cells, preventing an explicit distributed optimization of user schedules.Its scheduling is implicit because WMMSE optimizes beamformers for all users rather than directly solving the scheduling problem.
  • The proposed FP reformulation uses weighted bipartite matching to optimize the discrete scheduling variable explicitly.This contrasts with WMMSE's implicit scheduling through beamformer optimization.

B. Complexity Comparison

The complexity comparison shows that Algorithm 2 has communication complexity independent of the number of users, while WMMSE generally communicates with every user. With finite-precision matching weights, Algorithm 2 is overall more computationally efficient than WMMSE.

  • Communication Complexity: Algorithm 2 has communication complexity O(M^2B^2 + MNB^2), independent of the number of users K.Each base station collects scheduling, beamformer, and receiver information except γ for each base-station and stream pair.
  • Communication Complexity: WMMSE has communication complexity O(MKB^2 + NKB^2), which is generally higher because K is normally much greater than M.WMMSE collects beamformer, γ, and receiver information for every user in the network.
  • Computational Complexity: With the classic Hungarian algorithm, Algorithm 2 can be more computationally complex when the number of users K is large.The comparison assumes fixed M and N and K much greater than both.
  • Computational Complexity: Reducing weighted bipartite matching from O(K^3) to O(K^2) under finite-precision weights makes Algorithm 2 computationally more efficient than WMMSE overall.The improved matching complexity changes the computational comparison in favor of Algorithm 2.
  • Implication: The paper positions the FP-based approach as a distributed method for jointly optimizing discrete schedules and continuous communication variables.The complexity comparison is part of a broader FP formulation using matching for scheduling.

APPENDIX A PROOFS OF PROPOSITIONS 1 AND 2

The proof establishes convergence by showing that each auxiliary-variable and primal-variable update does not decrease the weighted sum-rate objective. Boundedness then implies convergence to a local optimum of the reformulated problem.

  • Lemma 1 bounds the original objective below by the first FP reformulation, with equality when γ satisfies its update equation.This supports the auxiliary-variable update used in the convergence chain.
  • Lemma 2 bounds the first reformulation below by the second FP reformulation, with equality when Y satisfies its update equation.This provides the second equality step in the proof.
  • Each iteration updates γ, Y, scheduling, and beamformers to maximize the relevant reformulated objective while holding the other variables fixed.The proof attributes the successive inequalities to the two lemmas and the maximizing updates.
  • The weighted sum-rate objective is monotonically nondecreasing after each iteration and is bounded above, so the algorithm converges.At convergence, the algorithm reaches a local optimum of the reformulated problem.
  • For a fixed scheduling variable s, the converged solution is a stationary point of the original objective with respect to the beamformers V.The proof distinguishes this stationary-point result from the local optimum of the reformulated problem.
Loading 1802.10197v2…