PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Spectrum Sharing in MIMO Cognitive Radio Networks via Semidefinite Programming

Ying Jun Zhang, Anthony Man-Cho So

arXiv:1006.4225v2cs.NI

TL;DR

The paper studies how an SU can maximize throughput while limiting interference to PUs when CSI on secondary-to-primary links may be complete, partial, or unavailable. It formulates all cases as homogeneous QCQPs, then obtains exact solutions for up to two primary links, near-optimal randomized solutions beyond two, and an eigenvalue-based solution with no primary-link CSI.

  • Problem

    The problem is maximizing SU throughput under primary-receiver interference limits when the SU may lack CSI on links to primary receivers.

  • Method

    The paper analyzes MIMO channel distributions and formulates three CSI scenarios as homogeneous QCQPs with deterministic or probabilistic interference constraints.

  • Results

    The SDP relaxation is exact for at most two primary links, a randomized polynomial-time method is provably near-optimal beyond two, and Scenario 3 reduces to eigenvalue-eigenvector computation.

  • Takeaways & Limitations

    The proposed formulations provide polynomial-time optimal beamforming for at most two primary links and an efficient eigenvalue-based solution when primary-link CSI is unavailable.

  • Takeaways & Limitations

    The randomized algorithm has only a worst-case performance guarantee, and better theoretical guarantees under the specific MIMO input distribution remain an open question.

Abstract

from arXiv · show

In this paper, we study the optimal secondary-link beamforming pattern that balances between the SU's throughput and the interference it causes to PUs in MIMO cognitive radio networks. In particular, we aim to maximize the throughput of the SU, while keeping the interference temperature at the primary receivers below a certain threshold. Unlike traditional MIMO systems, SUs may not have the luxury of knowing the channel state information (CSI) on the links to PUs. This presents a key challenge for a secondary transmitter to steer interference away from primary receivers. In this paper, we consider three scenarios, namely when the secondary transmitter has complete, partial, or no knowledge about the channels to the primary receivers. In particular, when complete CSI is not available, the interference-temperature constraints are to be satisfied with high probability, thus resulting in chance constraints that are typically hard to deal with. Our contribution is fourfold. First, by analyzing the distributional characteristics of MIMO channels, we propose a unified homogeneous QCQP formulation that can be applied to all three scenarios. The homogeneous QCQP formulation, though non-convex, is amenable to semidefinite programming (SDP) relaxation methods. Secondly, we show that the SDP relaxation admits no gap when the number of primary links is no larger than two. Thirdly, we propose a randomized polynomial-time algorithm for constructing a near-optimal solution to the QCQP problem when there are more than two primary links. Finally, we show that when the secondary transmitter has no CSI on the links to primary receivers, the optimal solution to the QCQP problem can be found by a simple matrix eigenvalue-eigenvector computation, which can be done much more efficiently than solving the QCQP directly.

I. INTRODUCTION

The paper addresses SU beamforming in MIMO cognitive radio networks, where secondary transmissions must improve throughput while limiting interference to primary receivers under incomplete CSI. It unifies three CSI scenarios through QCQP formulations and develops exact, near-optimal, and efficient solution methods.

  • Motivation: MIMO spatial processing lets secondary users transmit alongside primary users, but SUs must independently suppress the interference they cause.Single-antenna cognitive radio access depends on detecting spectrum holes, which limits access when primary-spectrum utilization is high.
  • CSI scenarios: The paper considers complete CSI, unknown primary-receiver beamformers, and no CSI about channels or beamformers on links to primary receivers.In the latter two scenarios, deterministic worst-case constraints can be overly stringent, motivating probabilistic interference constraints.
  • Contributions: A unified homogeneous QCQP formulation accommodates all three scenarios and both deterministic and probabilistic interference-temperature constraints.The formulation is designed to represent the different uncertainty patterns through scenario-specific quadratic constraints.
  • Contributions: SDP relaxation is exact when the number of primary users is at most two, while a randomized polynomial-time method yields a provably near-optimal solution when there are more than two.The paper also reports that the randomized solution almost achieves the optimal value numerically.
  • Contributions: With neither channel nor beamformer CSI at primary receivers, the optimal solution is obtained through a simple matrix eigenvalue-eigenvector computation.This avoids solving the QCQP directly in the third scenario.
  • Problem formulation: The beamforming objective maximizes SU throughput while keeping interference at each primary receiver below a tolerable threshold.The formulation also includes a maximum secondary transmission-power constraint and assumes relevant path losses remain approximately constant over the period of interest.

C. Distribution of rk

The distribution analysis shows that primary-receiver beamformers can often be modeled as isotropically distributed normalized complex Gaussian vectors. This result follows from unitary-invariance properties and supports later chance-constraint reformulations.

  • Beamformer representation: The receiver beamformer is represented through a random Hermitian matrix W_k acting on the relevant channel column while preserving unit norm.The construction includes distinct forms of W_k for MF, ZF, and MMSE reception.
  • Definitions: A normalized complex Gaussian vector is an isotropically distributed unit vector, uniformly distributed over the complex unit sphere.This rotational symmetry is the key distributional property used in the beamformer analysis.
  • Channel assumptions: The analysis models channel columns using normalized complex Gaussian vectors and assumes independent complex Gaussian entries for the other channel columns.These assumptions are justified by independent links and by primary precoders being determined by primary-system channels.
  • Distribution result: The primary receiver beamformer r_k has the same distribution as a normalized complex Gaussian vector when W_k is unitarily invariant.The result follows by decomposing W_k with an isotropically distributed unitary factor and using rotational invariance.
  • Receiver models: The distribution result applies to matched-filter, zero-forcing, and minimum-mean-squared-error receivers.For these receivers, the corresponding W_k matrices are unitarily invariant.

III. OPTIMAL BEAMFORMING AS HOMOGENEOUS QCQP

The paper reduces optimal SU beamforming to homogeneous QCQP by eliminating the receive beamformer: for any transmit beamformer, the optimal receiver is an MMSE receiver and the objective becomes quadratic.

  • QCQP reduction: All three optimal SU beamforming scenarios can be formulated as quadratically constrained quadratic programs.The reduction begins by exploiting the structure of the optimal receive beamforming solution.
  • Receiver optimization: For a fixed secondary transmit beamformer, the receive beamformer maximizing SU SINR is the MMSE receiver.Because the receive vector appears only in the objective, it can be optimized conditionally on the transmit vector.
  • Transmit-only formulation: Eliminating the receive beamformer replaces the SINR objective with a quadratic form in the secondary transmit beamformer.This produces the transmit-only optimization structure used in the subsequent QCQP formulations.

A. Homogeneous QCQP Formulation in Scenario 1

Scenario-specific uncertainty is converted into quadratic constraints, yielding homogeneous QCQPs whose constraints depend on available CSI and interference-outage tolerance. The distribution of primary beamformers enables the probabilistic constraints in Scenario 2.

  • Scenario 1: In Scenario 1, perfect knowledge of H^H_k,S r_k permits direct quadratic interference constraints in the transmit beamformer.The optimal secondary receive beamformer has already been eliminated before this scenario-specific formulation.
  • Scenario 1: The Scenario 1 problem is a homogeneous QCQP because its objective and inequality constraints are quadratic without linear terms.The matrices H^H_k,S H_k,S are Hermitian positive semidefinite.
  • Chance constraints: When primary-receiver beamformers are unknown, probabilistic interference constraints require the interference threshold to hold with probability at least 1−δ_k.The formulation exploits the distribution of r_k rather than enforcing every possible realization.
  • Chance constraints: The chance-constraint derivation uses a normalized complex Gaussian vector and distributional identities involving chi-square, beta, and F-distributed random variables.These identities convert the probabilistic conditions into deterministic quadratic constraints.
  • Scenario 2: After rewriting the chance constraints, the Scenario 2 transmit beamformer is found by solving the resulting QCQP.The paper notes that δ_k=0 recovers the worst-case constraint formulation.

C. Homogeneous QCQP Formulation and Closed-Form Solution in Scenario 3

Scenario 3 models interference constraints probabilistically because the secondary transmitter lacks both the primary beamformers and channels. MIMO channel distribution results convert these chance constraints into a homogeneous QCQP, with a small outage probability permitting transmission.

  • 1) Homogeneous QCQP:: Scenario 3 assumes the secondary transmitter knows neither the channels to primary receivers nor their beamformers, so interference constraints are probabilistic.
  • 1) Homogeneous QCQP:: Conditioned on the primary beamforming vector, the interference term is a zero-mean complex Gaussian variable whose variance depends on the secondary beamforming vector norm.
  • 1) Homogeneous QCQP:: The squared interference magnitude follows an exponential distribution with parameter determined by the secondary beamforming-vector norm.
  • 1) Homogeneous QCQP:: This distributional result holds whenever the primary beamforming vector has unit length, regardless of its distribution.
  • 1) Homogeneous QCQP:: The chance constraints can therefore be rewritten in deterministic quadratic form for the secondary beamforming vector.
  • 1) Homogeneous QCQP:: Under worst-case constraints with zero outage probability, the only feasible secondary transmission is zero.
  • 1) Homogeneous QCQP:: Allowing a small outage probability permits the secondary link to transmit over the primary system’s spectrum.
  • 1) Homogeneous QCQP:: The Scenario 3 optimum is obtained by solving the resulting QCQP after combining the chance-constraint reformulation with the power constraint.

2) Closed-Form Solution:

In Scenario 3, the beamforming problem reduces to a largest-eigenvalue computation, avoiding direct QCQP solution. For Scenarios 1 and 2, SDP relaxation replaces the rank-one constraint and provides a convex polynomial-time problem whose rank-one recovery determines exactness.

  • 2) Closed-Form Solution:: Scenario 3 reduces to finding the largest eigenvalue of a matrix and its associated eigenvector.
  • 2) Closed-Form Solution:: The optimal Scenario 3 beamformer is a scalar multiple of the eigenvector associated with that largest eigenvalue.
  • 2) Closed-Form Solution:: This eigenvalue-eigenvector computation eliminates the need to solve a QCQP in Scenario 3.
  • IV. SDP RELAXATION: Scenarios 1 and 2 require solving homogeneous QCQPs with quadratic interference and power constraints.
  • IV. SDP RELAXATION: The QCQP is NP-hard in general because it maximizes a convex function over an intersection of ellipsoids.
  • IV. SDP RELAXATION: Introducing X = t_St_S^H and dropping rank(X) = 1 yields an SDP with trace constraints replacing the original quadratic constraints.
  • IV. SDP RELAXATION: SDPs are convex and polynomial-time solvable, while a rank-one optimal SDP solution can be converted into an optimal QCQP solution.
  • IV. SDP RELAXATION: The SDP and its dual satisfy Slater conditions, enabling complementary-condition analysis of optimal primal and dual solutions.

V. OPTIMAL RANK-ONE SOLUTION WHEN K ≤2

When the number of primary links is at most two, SDP relaxation solves the homogeneous QCQP exactly. Polynomial-time rank-one decomposition constructs an optimal beamformer from an SDP solution.

  • When K ≤ 2, the SDP relaxation has no gap from the homogeneous QCQP and an optimal rank-one solution can be found in polynomial time.
  • The exact-solution algorithms recover rank-one matrices from an optimal SDP solution using a polynomial-time decomposition theorem.
  • For K = 1, selecting and scaling a decomposition vector yields a rank-one matrix satisfying the SDP constraints.
  • The construction preserves feasibility by maintaining the quadratic constraint and transmit-power bounds of the SDP solution.
  • Complementary conditions certify optimality after the rank-one feasible solution is constructed.
  • The resulting rank-one matrix is optimal for the SDP, and its vector factor is optimal for the original QCQP.
  • Algorithm 1 supplies the polynomial-time rank-one decomposition procedure used by the recovery argument.
  • The decomposition and extracted beamformer can be computed in polynomial time from the optimal SDP solution.

B. Optimal Rank-One Solution when K = 2

For K = 2, rank-one recovery handles cases with either non-binding or binding SDP constraints. In both cases, the recovered beamformer is feasible, optimal, and computable in polynomial time.

  • B. Optimal Rank-One Solution when K = 2: For K = 2, the SDP has three quadratic constraints: two primary-link constraints and one transmit-power constraint.
  • B. Optimal Rank-One Solution when K = 2: If at least one SDP constraint is non-binding, complementary conditions set its dual multiplier to zero and support rank-one recovery.
  • B. Optimal Rank-One Solution when K = 2: Scaling a suitable decomposition vector produces a rank-one solution that satisfies the relevant quadratic constraints.
  • B. Optimal Rank-One Solution when K = 2: If all SDP constraints bind, the recovered rank-one vector can simultaneously satisfy both primary-link constraints and the transmit-power constraint.
  • B. Optimal Rank-One Solution when K = 2: Complementary conditions establish that the recovered rank-one matrix is optimal for the SDP.
  • B. Optimal Rank-One Solution when K = 2: The corresponding beamformer is optimal for the QCQP and can be computed in polynomial time.

VI. RANK-ONE SOLUTION WHEN K ≥3

For more than two primary links, the SDP relaxation may lack a rank-one optimum and the QCQP is generally NP-hard, so the paper constructs feasible near-optimal solutions by randomization. The resulting algorithm is polynomial-time and achieves a provable fraction of the QCQP optimum.

  • When K ≥3, an optimal SDP solution may have no rank-one form, while the QCQP is NP-hard in general.This prevents polynomial-time extraction of an optimal QCQP solution from the SDP in general.
  • Algorithm 2 decomposes an optimal SDP solution, diagonalizes its objective matrix, samples random unit-modulus phases, and outputs a feasible QCQP vector.The procedure takes X∗ as input and returns a feasible solution t.
  • The SDP admits an optimal solution with rank at most K + 1, and the relevant quadratic forms have rank bounded by µ.These rank bounds support the randomized construction and its analysis.
  • Theorem 2 establishes that the randomized output is well defined and feasible for the QCQP.Its feasibility follows from the normalization and probabilistic bounds established in the theorem’s proof.
  • The returned objective value is at least 1/α times the QCQP optimum, with the guarantee derived from concentration bounds and the SDP upper bound.The theorem compares the randomized solution with the SDP relaxation, whose objective upper-bounds the QCQP optimum.
  • Scenario 3 remains efficiently solvable by a matrix eigenvalue-eigenvector computation regardless of the number of primary links, whereas Scenarios 1 and 2 require approximation when K > 2.The approximate solution is reported to be nearly optimal most of the time.

VII. NUMERICAL SIMULATIONS

Simulations evaluate the proposed beamforming methods under Rayleigh fading and compare exact, randomized, and SDP-relaxed solutions across networks with two and four primary links. The randomized method closely matches the SDP upper bound, while SINR improves with interference tolerance and allowable outage probability.

  • The simulations use four antennas per station, Rayleigh fading, path-loss exponent 4, and 50000 independent runs per plotted point.Unless otherwise stated, the outage probability δk is 1% in Scenarios 2 and 3.
  • For two primary links, the optimal beamforming solution can be found in polynomial time.The experiment uses specified transmitter- and receiver-side link distances for the two primary links.
  • SINR increases with tolerable interference, while additional channel information yields higher SINR especially when the interference threshold is low.The SINR gap between information scenarios narrows as the tolerable interference increases.
  • With four primary links, polynomial-time methods in Scenarios 1 and 2 produce approximate rather than exact solutions.The randomized algorithm is used for Scenarios 1 and 2, while Scenario 3 uses an eigenvalue-eigenvector computation.
  • Higher allowable outage probability enables higher secondary-link SINR in both Scenarios 2 and 3.This tradeoff is evaluated at fixed interference tolerance in the corresponding figures.
  • The randomized algorithm’s achieved SINR almost overlaps the SDP relaxation’s upper bound for the four-primary-link case.The SDP optimum is used as an upper bound on maximum achievable SINR.

C. A Grid Network with 9 Primary Links

A nine-primary-link grid experiment averages SINR over random secondary-link placements. The randomized algorithm remains close to the SDP upper bound, while full CSI provides substantially higher SINR when interference tolerance is small.

  • The nine primary links form a 70-by-40 meter grid, all links are 10 meters long, and the secondary link is randomly placed.Each plotted point averages 20000 independent secondary-link placements.
  • For nine primary links, Algorithm 2 achieves SINR that almost overlaps the SDP upper bound.The comparison treats the SDP optimum as an upper bound on the optimal value.
  • Full CSI produces much higher SINR than partial or no CSI, especially when the interference tolerance is small.Without full CSI, the paper uses the schemes developed for Scenarios 2 and 3.

VIII. CONCLUSIONS AND DISCUSSIONS

The paper unifies beamforming across channel-knowledge scenarios, with exact polynomial-time solutions in some cases and randomized near-optimal solutions when primary links exceed two. It also identifies practical performance and multi-secondary-link limitations.

  • The unified QCQP covers complete, partial, and no channel knowledge, including deterministic and probabilistic interference-temperature constraints.
  • When primary users number no more than two, SDP relaxation has no gap and yields a polynomial-time optimal beamforming solution.
  • When primary users exceed two, randomized polynomial-time construction provides a provably near-optimal QCQP solution from an optimal SDP solution.
  • The randomized algorithm's worst-case guarantee can differ from practical performance because MIMO inputs follow a specific distribution.The paper suggests probabilistic analysis could provide better theoretical guarantees.
  • The proposed beamforming methods can support multiple secondary links through MAC coordination that permits only one secondary link to transmit at a time.Without MAC, secondary links interfere with one another and the optimal beamforming problem becomes more challenging.
Loading 1006.4225v2…