Mobility-aware clustering algorithms with interference constraints in wireless mesh networks

Rami Langar, Nizar Bouabdallah, Raouf BoutabaComputer Networks 2009 · DOI

TL;DR

This paper introduces a novel interference-aware routing metric (INX) and two mobility-aware clustering algorithms (OSC and DCA) for wireless mesh networks (WMNs). These innovations aim to significantly improve radio resource utilization and overall network throughput by intelligently managing user mobility and mitigating interference between wireless links.

What Problem Does This Paper Address?

Wireless Mesh Networks (WMNs) are becoming increasingly important for providing flexible and bandwidth-efficient mobile internet access. However, two key challenges hinder their efficiency: managing the mobility of users and mitigating interference between neighboring wireless links. User mobility generates signaling messages that consume scarce radio resources. Simultaneously, interference between concurrent transmissions can degrade link quality and reduce network throughput. Existing solutions often address these issues in isolation, failing to consider their interplay. This paper tackles the problem of optimizing radio resource utilization in WMNs by jointly considering user mobility and interference constraints, with the ultimate goal of maximizing network throughput and improving the efficiency of wireless infrastructure.

Methods

The authors propose two main contributions:

  • Interference-Aware Routing Metric (INX): This metric extends the widely used Expected Transmission Count (ETX) by incorporating the impact of interference from neighboring links. INX considers not only the quality of a link (via ETX) but also the number and bit rates of interfering links. This aims to select paths that minimize interference, thereby preserving network resources for future connections.
  • Mobility-Aware Clustering Algorithms:
    • Optimal Static Clustering (OSC): This approach formulates the problem of finding optimal, disjoint cluster placements as an Integer Linear Program (ILP). It aims to minimize the overall Radio Resource Utilization (RRU) cost by strategically grouping Access Points (APs) into clusters.
  • Distributed Clustering Algorithm (DCA): This algorithm offers a more dynamic and distributed solution. Clusters can overlap, and their formation is influenced by user mobility patterns and interference constraints. DCA is designed to alleviate the computational complexity of OSC and react more efficiently to network topology changes.

Datasets

Not discussed in the paper. The authors rely on simulations using ns-2 and a custom discrete-event simulator.

Key Insights and Ideas

  • Interference is a critical factor: Simply optimizing for the best individual link (like ETX) or shortest path (hop-count) can lead to suboptimal overall network performance due to inter-path interference.
  • Clustering is essential for mobility management: By grouping APs into clusters, signaling traffic related to user handoffs can be localized, significantly reducing the overhead and improving resource utilization.
  • INX offers a better trade-off: The INX metric, by considering interference, allows for better path selection that not only serves the current connection but also preserves network capacity for future connections, leading to higher overall throughput.
  • DCA provides flexibility and scalability: While OSC offers optimal solutions, its computational cost is prohibitive for large or dynamic networks. DCA, being distributed and adaptive, offers a near-optimal solution with much better scalability and responsiveness to network changes.
  • The synergy of INX and DCA is powerful: Combining the interference-aware routing of INX with the dynamic clustering of DCA yields significant improvements in RRU cost and load balancing, especially in larger and more interconnected networks.

Key Results

  • INX vs. ETX/Hop-count: In scenarios with a single active connection, ETX slightly outperforms INX. However, with multiple simultaneous connections, INX significantly improves average throughput (up to 38% over ETX and 92% over hop-count) and reduces packet loss rate by considering inter-connection interference.
  • Clustering benefits: Both OSC and DCA significantly reduce registration update costs compared to the no-clustering (WC) case.
  • OSC vs. DCA: OSC provides near-optimal RRU costs, especially when considering the trade-off between data delivery and registration update costs. However, DCA offers near-optimal performance with much faster computation times and better adaptability to network changes.
  • INX enhances clustering: Using the INX metric within clustering algorithms (OSC and DCA) leads to further improvements in RRU cost and load balancing compared to using the hop-count metric.
  • Load Balancing: DCA generally achieves better load balancing than OSC, especially when using the INX metric, due to its ability to form more, smaller clusters.

Limitations and Future Work

  • Computational complexity of OSC: The ILP formulation for OSC is computationally expensive, limiting its applicability to smaller networks or static environments.
  • Assumptions: The paper assumes a specific mobility model (random walk) and a simplified network model (e.g., disabling RTS/CTS).
  • Future Work: The authors suggest further exploration of the DCA algorithm's performance under different mobility models and network conditions. They also highlight the potential for extending their work to more complex WMN scenarios.

Summary updated

BibTeX
@article{langar2009mobility,
  author = {Rami Langar and Nizar Bouabdallah and Raouf Boutaba},
  title = {{Mobility-aware clustering algorithms with interference constraints in wireless mesh networks}},
  journal = {Computer Networks},
  year = {2009},
  doi = {10.1016/j.comnet.2008.09.012},
}
Figure