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

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.