A new graph perspective on max-min fairness in Gaussian parallel channels

Marcin Wiczanowski, Holger BochearXiv 2008 · arXiv

Introduction

In modern multi-user communication systems, such as those employing Orthogonal Frequency Division Multiplexing (OFDM), efficient resource allocation is paramount. A common objective is max-min fairness, which seeks to maximize the performance of the user experiencing the worst channel conditions. While power allocation for a single user is a well-solved problem (e.g., via water-filling), the multi-user scenario introduces significant complexity. It requires solving a dual problem: a combinatorial challenge of deciding who shares which channel and for how long, and a continuous optimization challenge of determining the optimal power levels for each user.

This research introduces a novel framework that bridges these two domains by mapping channel-sharing policies to "sharing graphs." By leveraging tools from algebraic graph theory, the authors provide a unified perspective on how network topology and physical constraints interact to define fair performance.

The Sharing Graph Framework

The core innovation of this work is the sharing graph $G = (\mathcal{K}, \mathcal{E})$. In this representation, each vertex in the set $\mathcal{K}$ represents a user. An edge $(k, j) \in \mathcal{E}$ exists between two users if they share at least one parallel channel, regardless of whether they access it simultaneously or at different times within a transmission frame.

Figure 1: Three sharing graphs for K=4 users, illustrating how different channel-sharing configurations induced by matrices A result in distinct graph topologies.

As shown in Figure 1, different sharing strategies for a set of users lead to different graph structures. These structures are not merely visual aids; they are fundamental to determining the achievable fairness in the system. The authors demonstrate that the "fair" performance level is deeply tied to the spectral properties—specifically the eigenvalues—of these sharing graphs.

Theoretical Foundations and Performance Bounds

The paper draws a surprising connection between resource allocation and zero-error information theory. Specifically, it relates max-min performance to the Lovasz function ($\theta$) and the Delsarte bound, classical tools used to estimate the capacity of graphs.

By applying these graph-theoretic concepts, the authors derive "optimistic" (upper) and "pessimistic" (lower) bounds on user performance. These bounds are significant because they effectively decouple the influence of the network topology from the physical layer constraints, such as power limits and the specific shape of Quality of Service (QoS) functions (e.g., capacity or Mean Squared Error).

Figure 2: Examples of more complex sharing graphs. The different line styles (solid, dashed, dotted) represent the various parallel channels being shared among users.

A key insight from this analysis is the role of odd cycles in the sharing graph. The gap between the upper and lower performance bounds is primarily driven by the presence of these cycles. In scenarios where the graph lacks odd cycles longer than four, or when the number of users is small ($K \le 4$), these bounds become remarkably tight, providing a near-exact characterization of the optimal fair performance.

Algorithmic Approach and Results

To translate these theoretical insights into practical allocation policies, the authors employ techniques from matrix scaling theory and Non-negative Matrix Factorization (NMF). They reformulate the fair allocation problem as a bilinear program, which is significantly more computationally tractable than the original non-convex optimization problem.

The proposed algorithms (Algorithms 1, 2, and 3) were validated through extensive synthetic numerical simulations. These simulations covered various Signal-to-Noise Ratio (SNR) scenarios and graph topologies. Key results include:

  • Tight Characterization: For "non-overloaded" systems where the number of channels $N$ is at least the number of users $K$, the framework provides a precise interval for the max-min value.
  • Efficiency: The new algorithms offer a superior performance-complexity tradeoff. For instance, Algorithm 1 consistently achieved performance within 20% of the theoretical optimum while successfully avoiding the local optima that often trap traditional nonlinear solvers like BFGS.

Conclusion and Future Work

This research provides a powerful new lens through which to view multi-user resource allocation. By revealing the graph-theoretic nature of max-min fairness, it opens the door to more efficient and robust algorithms for next-generation communication networks.

Future work may extend this framework to "overloaded" scenarios ($N < K$) and explore its application in more complex network topologies, such as relay networks or ad-hoc grids. Additionally, optimizing the iterative NMF procedures for real-time hardware implementation remains an important area for further development.

Summary updated

BibTeX
@misc{wiczanowski2008new,
  author = {Marcin Wiczanowski and Holger Boche},
  title = {{A new graph perspective on max-min fairness in Gaussian parallel channels}},
  year = {2008},
  eprint = {0808.0987},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0808.0987},
}
Figure