Throughput Maximization in Wireless Networks via Partitioning and Randomization

April 25, 2007
Time: 11:00am-12:00pm
Interschool Lab, Room 750 CEPSR
Speaker: Gil Zussman, Massachusetts Institute of Technology


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, scheduling algorithms that have been recently presented can 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. The first part is joint work with A. Brzezinski and E. Modiano. The second part is joint work with E. Modiano and D. Shah.

Speaker Biography

Gil Zussman received the B.A., B.Sc., and M.Sc. degrees (all summa cum laude) from the Technion - Israel Institute of Technology and from Tel Aviv University. He received the Ph.D. degree in Electrical Engineering from the Technion in 2004. Since Sep. 2004 he has been a Postdoctoral Associate in the Laboratory for Information and Decision Systems and in the Communications and Networking Research Group at MIT. His current research interests are in the area of computer networks. In particular, he is interested in the design and performance evaluation of protocols for wireless networks including ad hoc, mesh, sensor, and personal area networks. He has been a member of the Technical Program Committees of ACM Mobihoc’07, ACM Mobicom’07, IEEE INFOCOM’07, and IEEE INFOCOM’08. Gil is a recipient of the Knesset (Israeli Parliament) Award for distinguished students, the Marie Curie Outgoing International Fellowship, the Fulbright Fellowship, the IFIP Networking 2002 Best Student Paper Award, and the OPNETWORK 2002 and ACM SIGMETRICS 2006 Best Paper Awards.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University