Computer Science Colloquium, 2007-2008

Gil Zussman
Columbia University
July 9, 2008

Title: Throughput Maximization in Wireless Networks via Partitioning and Randomization
 

Abstract:

A major challenge in the design of wireless networks is the need for distributed scheduling algorithms that will efficiently share the common spectrum. Due to the distributed operation, such algorithms usually achieve only a fraction of the maximum throughput. We present two distributed scheduling frameworks that guarantee maximum throughput. The first framework is based on deterministic algorithms and is designed for Wireless Mesh Networks (WMNs). We show that the multi-channel multi-radio capability of WMNs can enable the partitioning of the network into subnetworks in which simple deterministic distributed scheduling algorithms achieve 100% throughput. Using the recently introduced notion of Local Pooling, we characterize such subnetworks.

Then, channel assignment algorithms that partition a network into such subnetworks are presented. The second framework uses randomized algorithms and is designed for general wireless networks. It is based on a combination of a distributed randomized matching algorithm and an algorithm that compares and merges successive matching solutions. The comparison can be done by a deterministic algorithm or by randomized gossip algorithms. We show that although the comparison may be inaccurate, the framework attains 100% throughput. It is shown that the complexities of our algorithms, that achieve 100% throughput, are comparable to those of algorithms that achieve 50% throughput.

 


Benny Pinkas