Duality Gap Estimation and Polynomial Time Approximation for Optimal Spectrum Management

Consider a communication system whereby multiple users share a common frequency band and must choose their transmit power spectra jointly in response to physical channel conditions including the effects of interference. The goal of the users is to maximize a system-wide utility function (e.g., weigh...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2009-07, Vol.57 (7), p.2675-2689
Main Authors: LUO, Zhi-Quan, SHUZHONG ZHANG
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Asymptotic properties
Channels
Cognitive radio
Communication systems
complexity
Crosstalk
Discretization
DSL
duality
epsilon -approximation
Estimates
Exact sciences and technology
Formulations
Frequency domain analysis
Frequency estimation
Information, signal and communications theory
Interference
Lagrangian functions
Management
Mathematical analysis
Miscellaneous
Operations research
Polynomials
Radio spectrum management
Signal processing
spectrum management
Studies
sum-rate maximization
System performance
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a communication system whereby multiple users share a common frequency band and must choose their transmit power spectra jointly in response to physical channel conditions including the effects of interference. The goal of the users is to maximize a system-wide utility function (e.g., weighted sum-rate of all users), subject to individual power constraints. A popular approach to solve the discretized version of this nonconvex problem is by Lagrangian dual relaxation. Unfortunately the discretized spectrum management problem is NP-hard and its Lagrangian dual is in general not equivalent to the primal formulation due to a positive duality gap. In this paper, we use a convexity result of Lyapunov to estimate the size of duality gap for the discretized spectrum management problem and show that the duality gap vanishes asymptotically at the rate O (1/radic N ), where N is the size of the uniform discretization of the shared spectrum. If the channels are frequency flat, the duality gap estimate improves to O (1/ N ) . Moreover, when restricted to the FDMA spectrum sharing strategies, we show that the Lagrangian dual relaxation, combined with a linear programming scheme, can generate an epsiv -optimal solution for the continuous formulation of the spectrum management problem in polynomial time for any epsiv > 0 .
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2009.2016871