Distributed Throughput Maximization in Wireless Mesh Networks via Pre-Partitioning

This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multi-radio Wireless Mesh Networks (WMNs). Recently, a number of distributed scheduling algorithms for wireless networks have emerged. Due to their distributed operation, these algorithms can...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2008-12, Vol.16 (6), p.1406-1419
Main Authors: Brzezinski, A., Zussman, G., Modiano, E.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Channel assignment
Channels
Distributed algorithms
Finite element method
Job shops
local pooling
matroid intersection
Maximization
Mesh networks
Network topology
Networks
Partitioning
Partitioning algorithms
Scheduling
Scheduling algorithm
Stability
Studies
Throughput
Topology
Wireless mesh networks
Wireless networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the interaction between channel assignment and distributed scheduling in multi-channel multi-radio Wireless Mesh Networks (WMNs). Recently, a number of distributed scheduling algorithms for wireless networks have emerged. Due to their distributed operation, these algorithms can achieve only a fraction of the maximum possible throughput. As an alternative to increasing the throughput fraction by designing new algorithms, 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 algorithms can achieve 100% throughput. The partitioning is based on the 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 centralized channel assignment algorithms that are based on a matroid intersection algorithm. These algorithms pre-partition a network in a manner that not only expands the capacity regions of the subnetworks but also allows distributed algorithms to achieve these capacity regions. We evaluate the performance of the algorithms via simulation and show that they significantly increase the distributedly achievable capacity region. We note that while the identified topologies are of general interference graphs, the partitioning algorithms are designed for networks with primary interference constraints.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2008.918109