PaperlayerView exact revision on arXiv

Source-linked AI summary

Coordinated Beamforming for Multiuser MISO Interference Channel under Rate Outage Constraints

Wei-Chiang Li, Tsung-Hui Chang, Che Lin, Chong-Yung Chi

arXiv:1108.4475v4cs.ITmath.IT

TL;DR

Rate-outage constraints make utility-maximizing coordinated beamforming difficult, while exhaustive search scales exponentially with the number of transmitter-receiver pairs. The paper proposes centralized and distributed successive convex approximation methods using semidefinite relaxation and first-order approximations. The centralized method is near the exhaustive-search result in the reported comparisons, and the distributed method can approach its centralized counterpart in some settings.

  • Problem

    How to maximize system utility under rate-outage and individual-power constraints is difficult because the outage constraints are nonconvex and exhaustive search scales exponentially with the number of transmitter-receiver pairs.

    Source: §I · p. 3, §II · p. 6

  • Method

    The paper develops centralized SCA using semidefinite relaxation and first-order approximations, plus round-robin distributed SCA using local CDI and limited message exchange.

    Source: §I · p. 3, §IV · p. 14

  • Results

    The centralized SCA achieves almost the exhaustive-search average sum rate at 0 and 10 dB and remains within 2% of it at 20 dB; its rate tuple converges along the Pareto boundary for all considered utility functions.

    Source: §V · p. 19

  • Takeaways & Limitations

    The proposed algorithms yield near-optimal performance with lower complexity than the methods reported in, [23].

    Source: §I · p. 3

    The stationary-point result for the SDR is conditional on problem (20) yielding a rank-one beamforming solution.

    Source: §VI · p. 22

Abstract

from arXiv · show

This paper studies the coordinated beamforming design problem for the multiple-input single-output (MISO) interference channel, assuming only channel distribution information (CDI) at the transmitters. Under a given requirement on the rate outage probability for receivers, we aim to maximize the system utility (e.g., the weighted sum rate, weighted geometric mean rate, and the weighed harmonic mean rate) subject to the rate outage constraints and individual power constraints. The outage constraints, however, lead to a complicated, nonconvex structure for the considered beamforming design problem and make the optimization problem difficult to handle. {Although} this nonconvex optimization problem can be solved in an exhaustive search manner, this brute-force approach is only feasible when the number of transmitter-receiver pairs is small. For a system with a large number of transmitter-receiver pairs, computationally efficient alternatives are necessary. The focus of this paper is hence on the design of such efficient approximation methods. In particular, by employing semidefinite relaxation (SDR) and first-order approximation techniques, we propose an efficient successive convex approximation (SCA) algorithm that provides high-quality approximate beamforming solutions via solving a sequence of convex approximation problems. The solution thus obtained is further shown to be a stationary point for the SDR of the original outage constrained beamforming design problem. {Furthermore}, we propose a distributed SCA algorithm where each transmitter optimizes its own beamformer using local CDI and information obtained from limited message exchange with the other transmitters. Our simulation results demonstrate that the proposed SCA algorithm and its distributed counterpart indeed converge, and near-optimal performance can be achieved for all the considered system utilities.

EDICS: SAM-BEAM, MSP-APPL, MSP-CODR, SPC-APPL

The work acknowledges its funding support and notes an earlier presentation at IEEE ICASSP 2011.

EDICS: SAM-BEAM, MSP-APPL, MSP-CODR, SPC-APPL

  • The work was supported by two National Science Council grants and was partly presented at IEEE ICASSP in Prague in May 2011.The listed grants are NSC 99-2221-E-007-052-MY3 and NSC 101-2218-E-011-043.Source: EDICS: SAM-BEAM, MSP-APPL, MSP-CODR,… · p. 1

I. INTRODUCTION

The paper addresses coordinated beamforming for MISO interference channels, where interference coordination requires less information sharing than network MIMO. It develops outage-constrained utility-maximizing algorithms using transmitter CDI.

I. INTRODUCTION

  • Network MIMO requires base stations to share all CSI and user data, whereas interference coordination shares CSI to coordinate transmission strategies.The paper focuses on coordinated beamforming within the interference-coordination approach.Source: §I · p. 2
  • With single-user detection, transmit beamforming is Pareto optimal, but optimizing beamformers for common system utilities is NP-hard in general.The cited utilities include weighted sum rate, geometric mean rate, and harmonic mean rate.Source: §I · p. 2
  • Outage-constrained Pareto-boundary search in prior work has complexity that grows exponentially with the number of transmitter-receiver pairs.The paper contrasts this with efficient beamforming algorithms that had considered power minimization rather than rate-utility maximization.Source: §I · p. 3
  • The proposed SCA design targets system-utility maximization under rate-outage and individual-power constraints using transmitter CDI.The paper also proposes a distributed round-robin SCA algorithm using local CDI and limited message exchange.Source: §I · p. 3

II. SIGNAL MODEL AND PROBLEM STATEMENT

The paper models a K-user MISO interference channel with beamforming and channel distribution information at transmitters. It seeks utility-maximizing rates subject to outage and individual-power constraints.

II. SIGNAL MODEL AND PROBLEM STATEMENT

  • Each transmitter has Nt antennas, each receiver has one antenna, and transmitter i uses beamformer w_i for its information signal.Receivers use single-user detection, treating cross-link interference as noise.Source: §II · p. 4
  • Channels are block-faded, and transmitters know channel distributions rather than instantaneous CSI; each channel vector is modeled as zero-mean complex Gaussian with known covariance.A rate is in outage when it exceeds the instantaneous capacity, with its probability bounded by the receiver's requirement.Source: §II · pp. 4–5
  • The design maximizes a predefined system utility over beamformers subject to receiver outage requirements and individual power constraints.The utility captures throughput-fairness tradeoffs and can represent weighted sum, geometric mean, harmonic mean, or minimum rate.Source: §II · pp. 5–6
  • Exhaustive search over cross-link interference levels scales exponentially with K(K − 1), making the described method viable only for small K.For K = 3 and M = 10, the example requires searching 10^6 rate tuples.Source: §II · p. 6

III. PROPOSED CONVEX APPROXIMATION METHOD

The outage probability can be written in closed form, but the resulting design constraints remain complicated and nonconvex. The section therefore turns to convex approximation for efficient solution.

III. PROPOSED CONVEX APPROXIMATION METHOD

  • The outage probability is expressed in closed form, allowing the outage-constrained problem to be rewritten.The rewritten formulation uses ρ_i = 1 − ϵ_i.Source: §III · p. 6
  • Despite the closed-form outage probability, the constraints remain complicated and nonconvex, motivating a convex approximation method.The stated goal is an efficient approximation algorithm for near-optimal solutions for any number of transmitter-receiver pairs.Source: §III · p. 6

A. Convex Approximation Formulation

The formulation combines semidefinite relaxation with restrictive first-order approximations to obtain a convex problem for outage-constrained beamforming. It can yield rank-one beamformers when K ≤ 3, while for larger systems rank-one solutions are not guaranteed.

A. Convex Approximation Formulation

  • First-order lower bounds approximate two remaining nonconvex constraints, producing a convex optimization problem that standard solvers can solve.The lower bounds are formed at a feasible point; the resulting solution may over-satisfy an outage constraint, with tighter rates obtainable by line search.Source: A. Convex Approximation Formulation · pp. 8–9
  • The reformulation uses SDR to replace beamforming vectors with positive semidefinite matrices of arbitrary rank, then restrictively approximates constraints to obtain a convex problem.The restrictive approximation preserves feasibility for the original problem.Source: A. Convex Approximation Formulation · pp. 7, 9
  • If the convex approximation is feasible and K ≤ 3, it has an optimal solution whose beamforming matrices are rank one.This permits recovery of rank-one beamforming vectors feasible for the original problem.Source: A. Convex Approximation Formulation · pp. 9–10
  • For K > 3, rank-one optimality is not assured; Gaussian randomization can approximate a beamforming solution, whose utility is no greater than the tight-rate utility.K ≤ 3 is sufficient, not necessary, for rank-one optimality; simulations nevertheless found rank-one solutions for the tested instances.Source: A. Convex Approximation Formulation · p. 10

B. Successive Convex Approximation (SCA)

The SCA algorithm repeatedly solves a convex approximation centered on the previous iteration's solution. The corresponding utility is nondecreasing across iterations.

B. Successive Convex Approximation (SCA)

  • Each iteration updates the approximation point using the previous convex problem's beamforming matrices and corresponding achievable rates, then solves a new convex problem.The rates used for the next approximation are tightened rates, no less than the rates returned directly by the previous convex problem.Source: B. Successive Convex Approximation (SCA) · pp. 10–11
  • The previous iteration's beamforming matrices and tight rates form a feasible point for the next convex approximation.This feasibility supports the monotonic utility guarantee.Source: B. Successive Convex Approximation (SCA) · p. 11
  • The utility of the tight-rate tuple is nondecreasing across SCA iterations.The stated inequality is U(˜R1[n], . . . , ˜RK[n]) ≥ U(˜R1[n −1], . . . , ˜RK[n −1]) for all n ≥ 1.Source: B. Successive Convex Approximation (SCA) · p. 11

C. Convergence Analysis

Under a differentiable, strictly increasing utility, the SCA utility sequence converges, and its limit points are stationary for problem (8). With the additional constraints (9), those points are also stationary for problem (6).

C. Convergence Analysis

  • The utility sequence is nondecreasing and converges under the stated utility assumptions and individual power constraints.Theorem 1 assumes the utility is differentiable and strictly increasing in each rate.Source: C. Convergence Analysis · p. 11
  • Every limit point of the SCA iterates satisfies the KKT conditions of problem (8) and is therefore stationary.The proof uses inner approximations that are tight at the current iterate and asymptotically tight.Source: C. Convergence Analysis · pp. 11–13
  • With constraints (9) added to problem (6), a stationary point of problem (8) is also stationary for the constrained problem (6).The paper states this follows by examining equivalence of the two problems’ KKT conditions.Source: C. Convergence Analysis · pp. 11, 14
  • Approximation accuracy depends on the initial point, because the SCA algorithm guarantees only a stationary point.The paper suggests maximum-ratio transmission as one possible initialization.Source: C. Convergence Analysis · p. 14

IV. DISTRIBUTED IMPLEMENTATION

The distributed SCA algorithm updates transmitters in round-robin fashion using local channel distribution information and exchanged messages. Under the stated utility conditions, its utility sequence converges and its limit points are stationary.

  • Algorithm 2 updates transmitters in round-robin Gauss-Seidel order, with each optimizing its own beamformer using local CDI and exchanged information.Source: §IV · p. 14
  • Each transmitter's subproblem accounts for all users' outage constraints; SDR and first-order approximations produce a convex subproblem.Source: §IV · p. 15
  • For differentiable utilities strictly increasing in each rate, the utility sequence converges to a common value across transmitters, and every limit point is stationary for problems (8) and (6) with constraints (9).Source: §IV · p. 16
  • Each transmitter sends K real values to the other K−1 transmitters per round, yielding K²(K−1)N real values total.Source: §IV · p. 17
  • For K ≤ 6 and Nt = 8, Algorithm 2 can converge in fewer than 15 rounds, but iterative updates may increase transmission delay versus centralized schemes.Source: §IV · p. 17

V. SIMULATION RESULTS

Simulations compare the centralized SCA algorithm with exhaustive search and heuristic baselines, then assess convergence and distributed performance across system sizes and rate utilities.

Simulation setup

  • Simulations use 10% outage requirements by default, unit power limits, randomly generated channel covariance matrices, and MRT initialization.Algorithm 1 stops when utility improvement falls below 1% of the previous iteration’s utility.Source: §V · pp. 17–18

Example 1

  • For K = 2, SCA nearly matches exhaustive search for weighted sum and harmonic mean rates, with a sum-rate gap within 2% at 1/σ2 = 20 dB.The comparison averages 500 randomly generated channel covariance sets.Source: Figure 1 · p. 18, §V · p. 19
  • Across the considered utility functions, SCA approaches the Pareto boundary and then converges along it to the corresponding optimal rate tuple, including with asymmetric priorities.The asymmetric-priority case follows a similar convergence pattern.Source: §V · p. 19, Figure 2 · p. 19

Example 2

  • For K = Nt = 4, SCA outperforms MRT especially above 5 dB; in the K = 4, Nt = 8 setting, it outperforms both MRT and ZF.For 1/σ2 ≤ 5 dB in the first setting, SCA and MRT have comparable sum-rate performance.Source: §V · p. 20, Figure 3 · p. 20
  • SCA’s weighted geometric and harmonic mean rates saturate at high 1/σ2, which the authors suggest may reflect fairness becoming more prominent in interference-dominated conditions.The authors contrast this behavior with weighted sum-rate performance.Source: §V · p. 21, Figure 4 · p. 21

Example 3

  • For Nt = 8, K = 4, distributed SCA performs similarly to centralized SCA in almost all 30 tested instances within 10 rounds; a gap appears near full loading.For Nt = 12, K = 6, the distributed algorithm again converges to the centralized solution.Source: §V · p. 21, Figure 5 · p. 22

VI. CONCLUSIONS

The paper presents centralized and distributed SCA algorithms for rate-outage-constrained coordinated beamforming. Simulations report near-optimal centralized performance for K = 2 and distributed performance comparable to the centralized method in most tested cases.

Contributions

  • The centralized SCA algorithm combines SDR and first-order approximations, and its stationary-point guarantee holds provided problem (20) yields a rank-one beamforming solution.It iteratively solves convex problem (20).Source: §VI · p. 22
  • The distributed SCA algorithm uses local CDI and limited inter-transmitter messages in round-robin updates, with a stationary-point guarantee conditional on problem (36) yielding rank one.The algorithm produces approximate beamforming solutions.Source: §VI · p. 22

Simulation conclusions

  • Simulations show near-optimal centralized performance for K = 2, significant gains over MRT and ZF, and distributed performance comparable to centralized SCA within 10 rounds for most instances.The conclusion reports the distributed comparison for most problem instances.Source: §VI · p. 22

APPENDIX A

Appendix A establishes convergence properties used to support the centralized SCA algorithm’s analysis, including vanishing approximation residuals and bounds derived through Taylor expansions.

APPENDIX A

  • If a surrogate error stayed bounded away from zero, the utility would diverge; the proof therefore rules out that behavior.The argument uses the utility relation in (22).Source: Appendix A · p. 23
  • The residual between the exponential term and its first-order surrogate tends to zero as iterations increase.This is the limit stated in (A.7).Source: Appendix A · p. 23
  • Second-order Taylor expansions and bounded iterates establish the stated inequalities (31) and (32).The expansions are taken at the preceding iterate for exponential and logarithmic expressions.Source: Appendix A · pp. 23–24

APPENDIX B

Appendix B proves convergence and stationarity properties for the distributed SCA algorithm, while Appendix C establishes the inter-round convergence relations used in that proof.

APPENDIX B

  • The distributed algorithm’s utility sequence is nondecreasing and bounded, so it converges as rounds and transmitter updates proceed.The argument compares updated achievable rates with the previous surrogate rates.Source: Appendix B · p. 24

APPENDIX C

  • Appendix C establishes that the distributed algorithm’s surrogate rates converge across consecutive transmitter updates and successive rounds.The rate differences in (A.13e) tend to zero.Source: Appendix B · p. 26, Appendix C · p. 28

APPENDIX B

  • Bounded primal-dual iterates and asymptotically tight inner approximations support the conclusion that limit points satisfy the KKT conditions of problem (8).The proof passes the KKT conditions of problem (36) to a convergent subsequence.Source: Appendix B · pp. 26–27
Loading 1108.4475v4…