On Tractability Aspects of Optimal Resource Allocation in OFDMA Systems

被引:24
作者
Yuan, Di [1 ]
Joung, Jingon [2 ]
Ho, Chin Keong [2 ]
Sun, Sumei [3 ]
机构
[1] Linkoping Univ, Dept Sci & Technol, Linkoping, Sweden
[2] ASTAR, Inst Infocomm Res, Singapore, Singapore
[3] ASTAR, Inst Infocomm Res, Dept Modulat & Coding, Singapore, Singapore
基金
瑞典研究理事会;
关键词
Orthogonal frequency-division multiple access (OFDMA); resource allocation; tractability; POWER-CONTROL; MULTIUSER OFDM; ALGORITHMS;
D O I
10.1109/TVT.2012.2225854
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Joint channel and rate allocation with power minimization in orthogonal frequency-division multiple access (OFDMA) has attracted extensive attention. Most of the research has dealt with the development of suboptimal but low-complexity algorithms. In this paper, the contributions comprise new insights from revisiting tractability aspects of computing the optimum solution. Previous complexity analyses have been limited by assumptions of fixed power on each subcarrier or power-rate functions that locally grow arbitrarily fast. The analysis under the former assumption does not generalize to problem tractability with variable power, whereas the latter assumption prohibits the result from being applicable to well-behaved power-rate functions. As the first contribution, we overcome the previous limitations by rigorously proving the problem's NP-hardness for the representative logarithmic rate function. Next, we extend the proof to reach a much stronger result, namely, that the problem remains NP-hard, even if the channels allocated to each user are restricted to be a consecutive block with given size. We also prove that, under these restrictions, there is a special case with polynomial-time tractability. Then, we treat the problem class where the channels can be partitioned into an arbitrarily large but constant number of groups, each having uniform gain for every individual user. For this problem class, we present a polynomial-time algorithm and provide its optimality guarantee. In addition, we prove that the recognition of this class is polynomial-time solvable.
引用
收藏
页码:863 / 873
页数:11
相关论文
共 23 条