Dynamic Spectrum Management: Complexity and Duality
Dynamic Spectrum Management: Complexity and Duality
复制标题
DOI：
10.1109/jstsp.2007.914876
复制
发表时间：
2008-02-01
影响因子：
7.5
通讯作者：
Zhang, Shuzhong
中科院分区：
文献类型：
--
作者：
Luo, Zhi-Quan (Tom);Zhang, Shuzhong
考虑一个通信系统，其中多个用户共享一个公共频带，并且必须响应于物理信道条件动态地选择它们的发射功率谱密度。由于同信道干扰，每个用户可达到的数据速率不仅取决于其自身的功率谱密度，而且还取决于系统中其他用户的功率谱密度。给定任何信道条件并假设高斯信令，我们考虑联合确定所有用户的功率谱密度的问题，以便最大化系统范围的效用函数（例如，所有用户的加权和速率），服从单独的功率约束。对于这个非凸问题的离散化版本，我们通过建立各种实际设置下的NP-硬度来表征其计算复杂性，并确定在多项式时间内可解的问题的子类。此外，我们考虑了这个非凸问题的拉格朗日对偶松弛。利用泛函分析中的李雅普诺夫定理，我们严格证明了Yu和Lui（2006）首次发现的一个结果，即连续（Lebesgue积分）公式存在零对偶间隙。此外，我们表明，离散配方的对偶间隙渐近消失的离散化的大小减少到零。
Consider a communication system whereby multiple users share a common frequency band and must choose their transmit power spectral densities dynamically in response to physical channel conditions. Due to co-channel interference, the achievable data rate of each user depends on not only the power spectral density of its own, but also those of others in the system. Given any channel condition and assuming Gaussian signaling, we consider the problem to jointly determine all users' power spectral densities so as to maximize a system-wide utility function (e.g., weighted sum-rate of all users), subject to individual power constraints. For the discretized version of this nonconvex problem, we characterize its computational complexity by establishing the NP-hardness under various practical settings, and identify subclasses of the problem that are solvable in polynomial time. Moreover, we consider the Lagrangian dual relaxation of this nonconvex problem. Using the Lyapunov theorem in functional analysis, we rigorously prove a result first discovered by Yu and Lui (2006) that there is a zero duality gap for the continuous (Lebesgue integral) formulation. Moreover, we show that the duality gap for the discrete formulation vanishes asymptotically as the size of discretization decreases to zero.