Distributed throughput maximization in wireless mesh networks - a partitioning approach

This paper considers the interaction between channel as-signment and distributed scheduling in multi-channel multi-radio Wireless Mesh Networks (WMNs). Recently, a num-ber of distributed scheduling algorithms for wireless net-works have emerged. Due to their distributed operation, these algorithms can achieve only a fraction of the max-imum possible throughput. As an alternative to increas-ing the throughput fraction by designing new algorithms, in this paper we present a novel approach that takes advantage of the inherent multi-radio capability of WMNs. We show that this capability can enable partitioning of the network into subnetworks in which simple distributed scheduling al-gorithms can achieve 100 % throughput. The partitioning is based on the recently introduced notion of Local Pooling. Using this notion, we characterize topologies in which 100% throughput can be achieved distributedly. These topologies are used in order to develop a number of channel assign-ment algorithms that are based on a matroid intersection algorithm. These algorithms partition a network in a man-ner that not only expands the capacity regions of the subnet-works but also allows distributed algorithms to achieve these capacity regions. Finally, we evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region