  Despite the rich literature on scheduling algorithms for wireless networks,
algorithms that can provide deadline guarantees on packet delivery for general
traffic and interference models are very limited. In this paper, we study the
problem of scheduling real-time traffic under a conflict-graph interference
model with unreliable links due to channel fading. Packets that are not
successfully delivered within their deadlines are of no value. We consider
traffic (packet arrival and deadline) and fading (link reliability) processes
that evolve as an unknown finite-state Markov chain. The performance metric is
efficiency ratio which is the fraction of packets of each link which are
delivered within their deadlines compared to that under the optimal (unknown)
policy. We first show a conversion result that shows classical non-real-time
scheduling algorithms can be ported to the real-time setting and yield a
constant efficiency ratio, in particular, Max-Weight Scheduling (MWS) yields an
efficiency ratio of 1/2. We then propose randomized algorithms that achieve
efficiency ratios strictly higher than 1/2, by carefully randomizing over the
maximal schedules. We further propose low-complexity and myopic distributed
randomized algorithms, and characterize their efficiency ratio. Simulation
results are presented that verify that randomized algorithms outperform
classical algorithms such as MWS and GMS.
