CSMA using the Bethe Approximation: Scheduling and Utility Maximization

Se-Young Yun, Jinwoo Shin, Yung Yi

Abstract

Carrier Sense Multiple Access (CSMA) is a cornerstone of wireless networking, enabling distributed contention resolution. While it has been proven that tuning CSMA parameters can guarantee optimal scheduling and system-wide utility, traditional methods rely on Markov Chain Monte Carlo (MCMC) techniques. These "simulation-and-update" loops often suffer from exponentially slow convergence, making them poorly suited for dynamic network environments. This paper introduces a novel approach using the Bethe approximation from statistical physics to derive distributed iterative algorithms. We present the Bethe Algorithm for Stability (BAS), which achieves convergence in a single iteration, and the Bethe Utility Maximization (BUM) algorithm, which converges in polynomial time. Numerical results demonstrate that these algorithms offer high accuracy and significantly faster adaptation than existing MCMC-based schemes.

Introduction

In wireless networks, multiple links must share a common medium without causing excessive interference. CSMA provides a decentralized framework for this, where links sense the channel and transmit based on specific intensity parameters. The goal is to find parameters that ensure the network remains stable (queues do not grow infinitely) and maximizes a global utility function (ensuring fairness among users).

Historically, finding these optimal parameters required MCMC-based algorithms. These algorithms operate by observing the network's behavior over time to estimate service rates and then adjusting parameters accordingly. However, the time required for the network to reach a "stationary distribution"—known as the mixing time—can grow exponentially with the number of links. This creates a significant bottleneck, preventing networks from adapting to rapid changes in topology or traffic.

The Bethe Approximation Framework

To bypass the slow convergence of MCMC, this research reinterprets the CSMA scheduling problem through the lens of statistical physics. The network is modeled as a Markov Random Field (MRF), where nodes represent links and edges represent interference.

Instead of simulating the network to find the relationship between transmission intensities and service rates, the authors utilize the Bethe Free Energy (BFE). The BFE provides a way to approximate the partition function of the MRF, leading to a system of non-linear equations that describe the network state. By solving these equations directly, the algorithms become "mixing-independent," meaning they do not need to wait for a stochastic process to settle.

Proposed Algorithms

1. Bethe Algorithm for Stability (BAS)

The stability problem involves finding transmission intensities that satisfy a specific vector of target arrival rates. The authors discovered a remarkable property: the non-linear system derived from the Bethe approximation can be solved locally. In the BAS algorithm, a link can calculate its optimal transmission intensity in exactly one iteration of message passing, provided it knows the target rates of its immediate neighbors. This "one-shot" capability is a dramatic improvement over the thousands of iterations required by previous methods.

2. Bethe Utility Maximization (BUM)

For the broader problem of utility maximization (e.g., achieving proportional fairness), the authors developed the BUM algorithm. This is a two-phase approach:

  • Phase 1: A distributed gradient descent finds the optimal target service rates. The authors provide a critical proof that for standard $\alpha$-fair utility functions, the Bethe-approximated objective is concave, ensuring that the gradient descent reaches a global optimum.
  • Phase 2: The BAS algorithm is used to set the transmission intensities based on the rates found in Phase 1.

Performance Evaluation

The algorithms were tested on various interference topologies, including complete graphs, rings, trees, and grids.

  • Convergence Speed: In comparative simulations, the BUM algorithm typically converged within 1,000 iterations. In contrast, conventional MCMC-based schemes like JW or EJW often failed to converge even after 10,000 iterations. This represents a massive leap in responsiveness for real-time network management.
  • Accuracy: The Bethe approximation is known to be exact on tree-structured graphs. On "loopy" graphs (like grids), the empirical error remained small—usually within 20% of the target rate. This level of accuracy is generally sufficient for practical wireless applications where environmental noise and hardware variability are already present.
  • Offline Capability: A unique advantage of the Bethe approach is that it does not require active packet transmission to estimate service rates. BUM can be run as an offline algorithm to pre-calculate optimal settings before the network even begins transmitting data.

Conclusion

By applying the Bethe approximation to CSMA, this paper provides a path toward truly agile wireless networks. The transition from simulation-based MCMC to direct calculation via non-linear systems allows for polynomial-time convergence and, in the case of stability, a one-shot solution. While the approximation introduces a small error in dense, loopy topologies, the gains in speed and adaptability offer a compelling trade-off for modern, high-speed wireless communication.

Summary updated

Abstract

CSMA (Carrier Sense Multiple Access), which resolves contentions over wireless networks in a fully distributed fashion, has recently gained a lot of attentions since it has been proved that appropriate control of CSMA parameters guarantees optimality in terms of stability (i.e., scheduling) and system- wide utility (i.e., scheduling and congestion control). Most CSMA-based algorithms rely on the popular MCMC (Markov Chain Monte Carlo) technique, which enables one to find optimal CSMA parameters through iterative loops of `simulation-and-update'. However, such a simulation-based approach often becomes a major cause of exponentially slow convergence, being poorly adaptive to flow/topology changes. In this paper, we develop distributed iterative algorithms which produce approximate solutions with convergence in polynomial time for both stability and utility maximization problems. In particular, for the stability problem, the proposed distributed algorithm requires, somewhat surprisingly, only one iteration among links. Our approach is motivated by the Bethe approximation (introduced by Yedidia, Freeman and Weiss in 2005) allowing us to express approximate solutions via a certain non-linear system with polynomial size. Our polynomial convergence guarantee comes from directly solving the non-linear system in a distributed manner, rather than multiple simulation-and-update loops in existing algorithms. We provide numerical results to show that the algorithm produces highly accurate solutions and converges much faster than the prior ones.
BibTeX
@article{yun2015csma,
  author = {Se-Young Yun and Jinwoo Shin and Yung Yi},
  title = {{CSMA using the Bethe Approximation: Scheduling and Utility Maximization}},
  journal = {IEEE Trans. Information Theory},
  year = {2015},
  url = {https://openreview.net/forum?id=WAKQOQub2q},
}
Figure