Weighted coloring based channel assignment for WLANs

Suman Banerjee, Arunesh Mishra, Suman Banerjee 0001, William A. ArbaughACM Sigmobile Mob. Comput. Commun. rev 2005 · DOI

TL;DR

This paper tackles the challenge of efficiently assigning radio channels to Access Points (APs) in dense Wi-Fi networks. They introduce a novel "weighted graph coloring" approach that accounts for realistic interference scenarios and client distribution, leading to significantly better channel reuse and reduced interference compared to existing methods.

What Problem Does This Paper Address?

As Wi-Fi networks become denser, with more Access Points (APs) packed into buildings, managing radio channel assignments becomes critical. The standard approach relies on assigning non-overlapping channels (like 1, 6, and 11 in the 2.4 GHz band) to nearby APs to minimize interference. However, this approach is inefficient because it doesn't fully utilize the available spectrum and can lead to performance degradation when APs are very close or when clients are affected by interference even if the APs themselves aren't directly interfering. Existing methods like Least Congested Channel Search (LCCS) are often static and don't adapt well to dynamic client distributions or the nuanced interference patterns in real-world environments. This paper addresses the need for a more dynamic, intelligent, and efficient channel assignment strategy that maximizes spectrum reuse while minimizing user-perceived interference.

Methods

The core innovation is a weighted graph coloring formulation.

  • Graph Representation: APs are represented as vertices in a graph, and an edge exists between two APs if their interference regions overlap.
  • Weighted Edges: Unlike traditional graph coloring, edges are weighted. The weight signifies the importance of assigning different channels to the connected APs, primarily based on the number of clients affected by potential interference.
  • I-factor: The authors introduce an "I-factor" to quantify the interference between adjacent channels. This allows them to model and exploit partially overlapping channels, going beyond the strict non-overlapping constraint.
  • Objective Functions: They define three objective functions to minimize:
  • $L_{max}$: Minimizing the maximum interference experienced by any user.
  • $L_{sum}$: Minimizing the total interference experienced by all users.
  • $L_{num}$: Minimizing the number of conflicting AP pairs.
  • Distributed Algorithms: Two distributed algorithms, Hminmax and Hsum, are proposed to solve this weighted graph coloring problem.
  • Hminmax: A greedy, non-cooperative algorithm that focuses on minimizing the local $L_{max}$ for each AP. It's suitable for heterogeneous networks.
  • Hsum: An improved algorithm that also considers $L_{sum}$ and requires some AP coordination (via IAPP protocol) to achieve better overall network performance without compromising $L_{max}$.
  • Site-Report: A mechanism for APs to collaboratively build the overlap graph by having clients perform passive scans and report nearby APs.

Datasets

Not explicitly discussed as "datasets" in the traditional machine learning sense. The evaluation relies on:

  • Extensive Simulations: The authors simulated various network topologies and densities, including scenarios with 100 APs and a maximum degree of 20 in the overlap graph.
  • In-building Wireless Testbed: A real-world testbed with 20 IEEE 802.11b APs distributed across two floors was used to validate the algorithms.

Key Insights and Ideas

  • Partial Overlap is Key: The most significant insight is that allowing APs to use partially overlapping channels, rather than strictly non-overlapping ones, can dramatically improve spectrum reuse and reduce interference, especially in dense environments.
  • Client Distribution Matters: Channel assignment should not solely focus on AP interference but must consider the impact on end-users and their distribution. Weights based on affected clients are crucial.
  • Distributed Algorithms are Scalable: The proposed distributed algorithms (Hminmax, Hsum) are designed to be scalable and adaptable to dynamic network conditions, unlike static RF site surveys.
  • Hsum's Cooperative Advantage: While Hminmax offers good performance, Hsum's ability to leverage limited AP coordination leads to superior results, particularly in reducing overall interference ($L_{sum}$).

Key Results

  • Significant Interference Reduction: The proposed techniques achieve up to 45.5% reduction in interference for sparse topologies and 56% for dense topologies when using only non-overlapping channels.
  • Overlapping Channels Boost Performance: When allowing partially overlapping channels, an additional 42% reduction in interference was observed on average for moderately sized networks.
  • Improved User Throughput: The reduction in interference directly translates to better user throughput, as demonstrated by a simple two-AP scenario where increasing the overlap weight (more users in the interfering region) significantly decreased throughput.
  • Hsum Outperforms Hminmax: Hsum consistently performed better than Hminmax, especially in minimizing the $L_{sum}$ metric, due to its cooperative nature.
  • Scalability: The algorithms showed good scalability, with Hminmax converging in about 2 rounds and Hsum in about 4 rounds of optimization steps.
  • Real-world Validation: Experiments on a wireless testbed confirmed the simulation results, showing substantial improvements over the LCCS algorithm. For instance, ADJ-minmax (Hminmax with overlapping channels) reduced user interference by 40% compared to LCCS.

Limitations and Future Work

  • NP-Hardness: The weighted graph coloring problem is NP-hard, meaning optimal solutions are computationally expensive for large networks. The proposed algorithms are heuristics that aim for good, near-optimal solutions.
  • Asymmetric Interference: The paper acknowledges that coexisting 802.11b and 802.11g APs can create asymmetric interference, which would require a directed overlap graph. This is left as future work.
  • Implementation Details: While the algorithms are described, full implementation details for specific protocols like IAPP are outside the scope of this paper.
  • Physical Layer Effects: While the testbed captured some physical effects, more complex modeling of path loss and multi-path effects could be explored.
  • Client Behavior: The assumption of clients associating with the strongest signal is a simplification; more complex client behavior could be modeled.

Summary updated

BibTeX
@article{banerjee2005weighted,
  author = {Suman Banerjee and Arunesh Mishra and Suman Banerjee and William A. Arbaugh},
  title = {{Weighted coloring based channel assignment for WLANs}},
  journal = {ACM Sigmobile Mob. Comput. Commun. rev},
  year = {2005},
  doi = {10.1145/1094549.1094554},
}
Figure