Scheduling and Channel Assignment of Backhaul Traffic in Infrastructure Wireless Mesh Networks with Near-Minimal Delay and Jitter

Algorithms to provision backhaul traffic flows in an infrastructure Wireless Mesh Network (WMN) with near minimal delay and jitter and near-perfect QoS are described. The WMN consists of Base-Stations with multiple radio transceivers for backhauling, and one or more Gateway BSs. It has recently been established in theory that a recursive fair stochastic matrix decomposition algorithm can be used to schedule all provisioned backhaul traffic flows between BSs without primary conflicts. However, no extensive simulation results were reported and the practical application of the theory was not demonstrated. To demonstrate the theory, extensive simulations of an essentially saturated 64-node hexagonal WMN supporting backhaul traffic flows are reported. Upward and downward traffic distribution trees are provisioned in the WMN to carry backhaul traffic to and from the Internet through the Gateway BSs. Background point-to-point traffic flows are added between BSs to essentially saturate the WMN. The traffic flows are scheduled using the stochastic matrix decomposition theory, to yield a sequence of permutations for a TDMA/OFDMA scheduling frame. Each permutation is colored to assign orthogonal OFDMA radio channels to the active radio edges. Two greedy graph coloring algorithms are examined, the greedy-linear and greedy-random algorithms. The network is then extensively simulated, and the end-to-end delay, jitter and queue sizes for all backhaul traffic flows are recorded. Extensive simulations demonstrate experimentally that backhaul traffic flows can be delivered with near-minimal delay and jitter and near-perfect QoS under reasonable assumptions on wireless link quality.