A fast-csma algorithm for deadline-constrained scheduling over wireless fading channels

Sense Multiple Access (CSMA)-based scheduling algorithms have attracted extensive interest due to their throughput-optimal char-acteristics in general network topologies. However, these algo-rithms are not well-suited for serving real-time traffic under time-varying channel conditions for two reasons: (1) the mixing time of the underlying CSMA Markov Chain grows with the size of the network, which, for large networks, generates unacceptable delay for deadline-constrained traffic; (2) since the dynamic CSMA parameters are influenced by the arrival and channel state processes, the underlying CSMA Markov Chain may not converge to a steady-state under strict deadline constraints and fading channel conditions. In this paper, we attack the problem of distributed scheduling for serving real-time traffic over time-varying channels. Specifi-cally, we consider fully-connected topologies with independently fading channels (which can model cellular networks) in which flows with short-term deadline constraints and long-term drop rate requirements are served. To that end, we first characterize the maximal set of satisfiable arrival processes for this system and, then, propose a Fast-CSMA (FCSMA) policy that is shown to be optimal in supporting any real-time traffic that is within the max-imal satisfiable set. These theoretical results are further validated through simulations to demonstrate the relative efficiency of the FCSMA policy compared to some of the existing CSMA-based algorithms. I