A performance study of energy minimization for interleaved and localized FDMA

Lei You, Lei Lei, Di Yuan

TL;DR

This paper tackles the challenge of minimizing battery consumption for mobile users in LTE-style uplink transmissions (SC-FDMA). The researchers prove that while power optimization for localized channel allocation is notoriously difficult (NP-hard), the interleaved approach is actually solvable in polynomial time, and they provide a matching-based algorithm to find the global optimum.

What Problem Does This Paper Address?

In modern wireless communications, specifically the uplink of 3GPP-LTE, devices use 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 get a contiguous block of adjacent channels.
  2. Interleaved (IFDMA): Users get channels spread out equidistantly across the spectrum.

Previous research established that finding the absolute minimum power allocation for LFDMA is "NP-hard"—meaning it's computationally impractical to find the perfect solution as the number of users grows. This paper asks: Is the interleaved version (IFDMA) just as hard? And how does the energy efficiency of the two methods compare when both are pushed to their mathematical limits?

Methods

The authors introduce the Minimal Power Channel Allocation (MPCA) algorithm. Their approach relies on a clever mathematical mapping:

  • Problem Reduction: They prove that for any given "channel block" in IFDMA, the task of assigning users to specific slots within that block can be modeled as a maximum weight perfect matching problem in a bipartite graph.
  • The Solver: By using the classic Kuhn-Munkres (KM) algorithm, they can find the optimal user-to-channel permutation in $O(M^3)$ time (where $M$ is the number of users).
  • Global Search: Since the total number of possible channel blocks is limited ($O(N^3)$), the algorithm iterates through these blocks, running the KM algorithm for each, to find the global power minimum.
  • Complexity: The total computational cost is $O(M^3N^4)$, which is polynomial. This is a significant theoretical win over the exponential complexity often required for NP-hard problems.

Datasets

The study uses a simulated environment based on standard LTE parameters rather than a static dataset. Key simulation settings include:

  • Environment: 1000m cell radius with a 2 GHz carrier frequency.
  • Channel Model: Rayleigh fading with log-normal shadowing (8 dB standard deviation) and the COST-231-HATA path loss model.
  • Configuration: 10 users sharing 64 channels (180 KHz bandwidth each).
  • Demand: User data requirements ranging from 400 Kbps to 3000 Kbps.

Key Insights and Ideas

  • The Complexity Gap: The most striking insight is the disparity in computational complexity. IFDMA’s equidistant structure creates a mathematical symmetry that allows for efficient global optimization, whereas LFDMA’s contiguous requirement breaks this symmetry, leading to NP-hardness.
  • The Permutation Trick: In IFDMA, once a channel block is chosen, the relative positions of users are fixed across all sub-blocks. This means the optimizer only needs to find the best permutation of users, which is exactly what bipartite matching excels at.
  • Generality: The MPCA algorithm doesn't rely on a specific "rate vs. power" formula. As long as the rate function is monotonic (more power equals more data), the algorithm holds, making it applicable to various modulation and coding schemes.

Key Results

  • Solvability: The paper successfully proves that the Min-Power problem for IFDMA is polynomial-time solvable.
  • Capacity Limits: LFDMA significantly outperforms IFDMA in terms of maximum supported demand. LFDMA could support nearly 2500 Kbps per user, while IFDMA hit a "feasibility wall" at approximately 1400 Kbps.
  • Energy Efficiency: When both schemes can satisfy the demand, LFDMA is slightly more power-efficient than IFDMA.
  • The Trade-off: While LFDMA is more efficient and has higher capacity, IFDMA is easier to optimize perfectly and generally offers a better Peak-to-Average Power Ratio (PAPR), which is easier on hardware amplifiers.

Limitations and Future Work

The authors acknowledge a few constraints in their model:

  • Uniform Allocation: The study assumes all users are allocated the same number of channels ($c$). In real-world scenarios, users with higher demands might need more channels than those with lower demands.
  • Static Scenarios: The simulation assumes a snapshot in time. Future work could explore how these algorithms perform in highly mobile environments where channel gains change rapidly.
  • Hybrid Approaches: Given that LFDMA has better capacity but IFDMA is easier to optimize, a hybrid scheme that switches modes based on network load could be a promising area for exploration.

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},
}

Loading related content...

Figure