CSMA algorithms have recently received significant interests in the literature for designing wireless control algorithms. CSMA algorithms incur low complexity and can achieve the optimal capacity under certain assumptions. However, CSMA algorithms suffer the starvation problem and incur large delay that may grow exponentially with the network size. In this paper, our goal is to develop a new algorithm that can provably achieve high throughput utility and low delay with low complexity. Towards this end, we propose a new CSMA-like algorithm, called Virtual-Multi-Channel (VMC-) CSMA, that can dramatically reduce delay. The key idea of VMC-CSMA to avoid the starvation problem is to use multiple virtual channels (which emulate a multi-channel system) and compute a good set of feasible schedules simultaneously (without constantly switching/re-computing schedules). Under the protocol interference model and a singlehop utility-maximization setting, VMC-CSMA can approach arbitrarily close-to-optimal system utility with both the number of virtual channels and the computation complexity increasing logarithmically with the network size. Further, once VMC-CSMA converges to the steady-state, we can show that under certain assumptions on the utility functions and the topology, both the expected packet delay and the tail distribution of the HOL (headof- line) waiting time at each link can be bounded independently of the network size. Our simulation results confirm that VMCCSMA algorithms indeed achieve both high throughput utility and low delay with low-complexity operations.
Carrier sence multiple access (CSMA), utility maximization, distributed scheduling, Markov chain, starvation, virtual multiple channels.
Date of this Version