A Performance Study of Energy Minimization for Interleaved and Localized FDMA

Lei You, Lei Lei, Di Yuan

Abstract

Optimal channel allocation is a key performance engineering aspect in single-carrier frequency-division multiple access (SC-FDMA). It is of significance to consider minimum sum power (Min-Power), subject to meeting specified user's demand, since mobile users typically employ battery-powered handsets. In this paper, we prove that Min-Power is polynomial-time solvable for interleaved SC-FDMA (IFDMA). Then we propose a channel allocation algorithm for IFDMA, which is guaranteed to achieve global optimum in polynomial time. We numerically compare the proposed algorithm with optimal localized SC-FDMA (LFDMA) for Min-Power. The results show that LFDMA outperforms IFDMA in the maximal supported user demand. When the user demand can be satisfied in both LFDMA and IFDMA, LFDMA performs slightly better than IFDMA. However, Min-Power is polynomial-time solvable for IFDMA whereas it is not for LFDMA.

Introduction

In modern wireless communications, specifically the uplink of 3GPP-LTE, devices utilize Single-Carrier Frequency-Division Multiple Access (SC-FDMA). Because mobile handsets are battery-powered, minimizing the total transmission power required to meet a user's data demand is a critical engineering goal.

There are two primary ways to assign frequency channels to users:

  1. Localized (LFDMA): Users are assigned a contiguous block of adjacent channels.
  2. Interleaved (IFDMA): Users are assigned channels spread out equidistantly across the spectrum.

Previous research established that finding the absolute minimum power allocation for LFDMA is "NP-hard," making it computationally impractical for large networks. This paper investigates whether the interleaved version (IFDMA) is similarly complex and compares the energy efficiency of both methods when pushed to their mathematical limits.

Methodology: The MPCA Algorithm

The authors introduce the Minimal Power Channel Allocation (MPCA) algorithm for IFDMA. The core innovation is a mathematical mapping that reduces the allocation problem to a graph theory problem.

Bipartite matching model for user-to-order mapping in IFDMA.

For any given channel block in IFDMA, the task of assigning users to specific slots can be modeled as a maximum weight perfect matching problem in a bipartite graph. By utilizing the Kuhn-Munkres (KM) algorithm, the optimal user-to-channel permutation can be found in $O(M^3)$ time (where $M$ is the number of users). Since the total number of possible channel blocks is limited, the global power minimum can be found in polynomial time—a significant theoretical win over the exponential complexity required for LFDMA.

Simulation and Results

The study simulated an LTE environment with 10 users sharing 64 channels, utilizing Rayleigh fading and the COST-231-HATA path loss model. User data requirements ranged from 400 Kbps to 3000 Kbps.

Capacity and Efficiency Limits

The results highlight a striking disparity in performance. LFDMA significantly outperforms IFDMA in terms of maximum supported demand.

Comparison of maximal supported user demand between LFDMA and IFDMA.

As illustrated in the findings, LFDMA could support nearly 2500 Kbps per user, while IFDMA hit a "feasibility wall" at approximately 1400 Kbps. Furthermore, when both schemes were able to satisfy the demand, LFDMA was found to be slightly more power-efficient than IFDMA.

Conclusion

While LFDMA is more efficient and offers higher capacity, IFDMA is easier to optimize perfectly due to its mathematical symmetry. Additionally, IFDMA generally offers a better Peak-to-Average Power Ratio (PAPR), which is beneficial for hardware amplifiers. Future work may explore hybrid schemes that switch modes based on network load to leverage the strengths of both allocation strategies.

Summary updated

Abstract

Optimal channel allocation is a key performance engineering aspect in single-carrier frequency-division multiple access (SC-FDMA). It is of significance to consider minimum sum power (Min-Power), subject to meeting specified user's demand, since mobile users typically employ battery-powered handsets. In this paper, we prove that Min-Power is polynomial-time solvable for interleaved SC-FDMA (IFDMA). Then we propose a channel allocation algorithm for IFDMA, which is guaranteed to achieve global optimum in polynomial time. We numerically compare the proposed algorithm with optimal localized SC-FDMA (LFDMA) for Min-Power. The results show that LFDMA outperforms IFDMA in the maximal supported user demand. When the user demand can be satisfied in both LFDMA and IFDMA, LFDMA performs slightly better than IFDMA. However Min- Power is polynomial-time solvable for IFDMA whereas it is not for LFDMA.
BibTeX
@inproceedings{you2014performance,
  author = {Lei You and Lei Lei and Di Yuan},
  title = {{A Performance Study of Energy Minimization for Interleaved and Localized FDMA}},
  booktitle = {CAMAD},
  year = {2014},
  url = {https://openreview.net/forum?id=Ht12cDtF5Y},
}
Figure