Optimal and near-optimal resource allocation algorithms for OFDMA networks

Yuan Bin Lin*, Tai Hsiang Chiu, Yu-Ted Su

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


Given the availability of multiple orthogonal channels and multimedia transmission rate requirements from multiple wireless OFDMA users, we are interested in a joint channel, power and rate assignment scheme that satisfies the given requirements with the minimum total transmit power. Algorithms for finding suboptimal and optimal solutions to sum power minimization resource allocation problems in OFDMA-based networks haven been proposed. But the complexity of finding the optimal solution is prohibitively high. We present two efficient algorithms with which each channel (subcarrier) is assigned to at most one user. The first approach, which gives near-optimal solutions, employs a dynamic programming (DP) based tree search and adopts a fair initial condition that offers every user all available channels and removes a channel from all but one user at each stage. Each removal is based on the criterion of the least total power increase. Using the DP-based solution as the initial upper bound and the partial path cost used in the DP approach as the lower bound for each visited node, we develop an efficient branch-and-bound based algorithm that guaranteed to lead to the optimal solution. The average complexities of both algorithms are evaluated and effective schemes to further reduce the required complexity are proposed. We also provide performance and complexity comparisons with other suboptimal algorithms that are modified from the existing ones.

Original languageEnglish
Article number5200968
Pages (from-to)4066-4077
Number of pages12
JournalIEEE Transactions on Wireless Communications
Issue number8
StatePublished - 1 Aug 2009


  • Branch-and-bound
  • Broadband communication
  • Dynamic programming
  • Radio resource allocation

Fingerprint Dive into the research topics of 'Optimal and near-optimal resource allocation algorithms for OFDMA networks'. Together they form a unique fingerprint.

Cite this