Bipartite Graph Based Dynamic Spectrum Allocation for Wireless Mesh Networks

The capacity of a wireless mesh network can be improved by equipping mesh nodes with multi-radios tuned to non-overlapping channels. By letting these nodes utilize the available spectrum opportunistically, we can increase the utilization of the available bandwidth in the spectrum space. The key problem is how to allocate the spectrum to these multi-radio nodes, especially when they are heterogeneous with diverse transmission types and bandwidth. Most of current work has been based on the conflict-graph model and given solutions that focused on either increasing bandwidth utilization or minimizing starvation. In this paper, we propose a new bipartite-graph based model and design an channel allocation algorithm that considers both bandwidth utilization and starvation problems. Our solution is based on using augmenting path to find a matching in the bipartite-graph and can minimize starvation and then maximize the bandwidth utilization. The simulations demonstrate that our algorithm can reduce the starvation ratio and improve the bandwidth utilization, compared with previous conflict-graph based algorithms.