Achieving Both High Capacity and Low Delay via CSMA-Like Algorithms: A Virtual Multi-Channel Approach

Prof. Xiaojun LIN
Purdue University, USA
Wednesday, 5 September, 2012
2:30 - 3:30 pm
Room 833, Ho Sin Hang Engineering Building The Chinese University of Hong Kong

Link scheduling is one of the central problems for the design of high-performance wireless networks. As physical-layer coding and transmission techniques continue to advance, efficient network-level scheduling algorithms are in even greater need to manage interference and maximize spatial reuse. Such scheduling algorithms must attain not only high throughput, but also low delay. Further, for large wireless networks, they must incur low complexity and are easy to implement. Unfortunately, existing algorithms in the literature are often only able to attain a subset of these goals at the cost of others. For example, the max-weight algorithm can achieve the full capacity with reasonably low delay, but may incur prohibitively high complexity. Approximation algorithms such as greedy heuristics incur much lower complexity, but can only guarantee a small fraction of the optimal capacity. Recently, a class of CSMA algorithms has received a significant amount of interest in the literature. They are particularly attractive because they incur low computation complexity and communication overhead, and can be shown to achieve the optimal capacity under certain assumptions. However, it has also been observed that CSMA algorithms suffer the starvation problem and incur large delay that may grow exponentially with the network size. 

Can we design scheduling algorithms that simultaneously attain high capacity and low delay without the cost of high complexity? In this talk, we answer this question affirmatively by proposing a new CSMA-like algorithm, called Virtual-Multi-Channel (VMC-) CSMA. VMC-CSMA can dramatically reduce delay without sacrificing the high throughput and low complexity of CSMA. The key idea of VMC-CSMA to avoid the starvation problem is to use multiple virtual channels that emulate a multi-channel system and to compute a good set of feasible schedules simultaneously (without constantly switching/re-computing schedules). Under the protocol interference model and a single-hop utility-maximization setting, we show that VMC-CSMA can approach arbitrarily close to the optimal total system utility, with both the number of virtual channels and the computation complexity increasing logarithmically with the network size. The VMC-CSMA algorithm inherits the distributed nature of CSMA algorithms. Further, once the algorithm converges to the steady-state, both the packet delay and the head-of-line (HOL) waiting time at each link can be tightly bounded. Our simulation results confirm that the proposed VMC-CSMA algorithm indeed achieves both high throughput and low delay. Further, it can quickly adapt to network changes. We will conclude the talk with a discussion of the potential opportunities and challenges to generalize the key idea of VMC-CSMA to more sophisticated physical-layer models, e.g., with the use of network coding and MIMO.



Xiaojun Lin received his B.S. from Zhongshan University, Guangzhou, China, in 1994, and his M.S. and Ph.D. degrees from Purdue University, West Lafayette, Indiana, in 2000 and 2005, respectively. He is currently an Associate Professor of Electrical and Computer Engineering at Purdue University. 

Dr. Lin's research interests are in the analysis, control and optimization of large and complex wireless and wireline networks.  He received the IEEE INFOCOM 2008 best paper award and 2005 best paper of the year award from Journal of Communications and Networks.  His paper was also one of two runner-up papers for the best-paper award at IEEE INFOCOM 2005. He received the NSF CAREER award in 2007. He was the Workshop co-chair for IEEE GLOBECOM 2007, the Panel co-chair for WICON 2008, the TPC co-chair for ACM MobiHoc 2009, and Mini-conference co-chair for IEEE INFOCOM 2012. He is currently serving as an Area Editor for (Elsevier) Computer Networks journal, and has served as a Guest Editor for (Elsevier) Ad Hoc Networks journal.