Scheduling links for heavy traffic on interfering routes in wireless mesh networks

Fabio R. J. Vieira, José Ferreira de Rezende, Valmir Carneiro Barbosa, Serge Fdida

Abstract

Efficient scheduling in Wireless Mesh Networks (WMNs) is often hampered by signal interference and finite node buffer space. This paper evaluates Scheduling by Edge Reversal (SER) and introduces a novel enhancement, SER with Advancement (SERA), designed to maximize throughput under heavy traffic conditions without causing buffer overflows.

Introduction

In TDMA-based Wireless Mesh Networks, scheduling simultaneous transmissions is a complex task that must account for signal interference. While many algorithms focus on maximizing network utilization, they often ignore the physical constraint of finite buffer space. If a node is scheduled to transmit to a neighbor whose buffer is full, the network stalls. This research investigates scheduling strategies that guarantee zero buffer overflows while maximizing packet delivery rates on pre-determined routes under heavy traffic conditions.

Methodology: From Routes to Interference Graphs

The proposed approach transforms directed routing paths into an undirected interference graph, where edges represent potential wireless interference between links. This transformation allows the scheduling problem to be treated as a graph-coloring or orientation problem.

Figure 1: (a) Three routing paths and (b) the resulting interference graph where edges denote interference between links.

The study compares two primary scheduling heuristics:

  • Scheduling by Edge Reversal (SER): This baseline method uses acyclic orientations of the interference graph. Nodes acting as "sinks" (having no outgoing edges) are scheduled to transmit, after which their edges are reversed. This creates a rigid, interleaved schedule that naturally respects a buffer size of one but limits overall capacity due to its strict alternation.
  • SER with Advancement (SERA): SERA improves upon the baseline by relaxing strict interleaving. It dynamically tracks buffer availability and "advances" transmissions whenever a node has a packet and the receiver has space. This opportunistic approach breaks strict coloring rules to utilize otherwise idle time slots while still guaranteeing zero buffer overflows.

Experimental Evaluation

The algorithms were evaluated using 1,600 simulated network topologies with sizes ranging from 60 to 120 nodes. The maximum node degree ($Δ$), representing network density and interference, was varied across 4, 8, 16, and 32 to observe its impact on performance.

Key Results

  • Throughput Performance: SERA consistently outperformed the baseline SER algorithm by a factor of 2 to 4 across all tested network densities and sizes.
  • Initialization and Numbering: The initial state of the graph significantly impacts performance. The authors found that a Breadth-First (BF) numbering scheme, which prioritizes starting traffic at the path origins, yielded better throughput than Depth-First numbering.
  • Buffer Utilization: Interestingly, increasing the buffer size ($B > 1$) did not significantly improve SERA's average performance. The majority of throughput gains were achieved by allowing single-packet transmissions to occur out of strict alternating order, rather than by hoarding multiple packets at intermediate nodes.
  • Interference and Density: Throughput exhibited a non-monotonic relationship with network density. While increasing density initially provides more routing options, high interference levels ($Δ = 32$) eventually overwhelm scheduling opportunities, leading to a drop in throughput.

Conclusion

The SERA algorithm demonstrates that opportunistic scheduling, which prioritizes buffer availability over strict interleaving, can significantly enhance the capacity of Wireless Mesh Networks. While the algorithm's complexity in determining scheduling periods remains a challenge for real-time implementation, it provides a robust framework for high-throughput, overflow-free communication in constrained environments. Future work will focus on establishing tighter mathematical upper bounds for throughput and optimizing initial graph orientations.

Summary updated

BibTeX
@article{vieira2012scheduling,
  author = {Fabio R. J. Vieira and José Ferreira de Rezende and Valmir Carneiro Barbosa and Serge Fdida},
  title = {{Scheduling links for heavy traffic on interfering routes in wireless mesh networks}},
  journal = {Computer Networks},
  year = {2012},
  doi = {10.1016/j.comnet.2012.01.011},
}
Figure