Real-Time Scheduling in Wireless Networks

We study a canonical real-time scheduling problem for time-slotted collocated wireless networks serving users with diverse real-time requirements and wireless loss patterns arising from fading. We study two traffic patterns: periodic arrivals with deadline equal to period, and renewal arrivals, in which a new packet from a user arrives when the current one leaves. Wireless channel conditions are modelled as Bernoulli losses. For periodic arrivals, we prove that the optimal policy that minimizes the expected number of deadline misses has a strong property: it only switches between users on arrivals, successful completions or deadline expiry. When users have similar periods, this optimal policy is a linear switching curve characterized by a single number. Our result explicitly captures the trade-off between two competing aspects of the problem: the real-time tendency to schedule users in earliest-deadline-first (EDF) order, and the wireless tendency to exploit multi-user diversity by scheduling users with good channel conditions first. When users have similar channels, a common occurrence, we establish the optimality of EDF. For renewal arrivals, the optimal policy continues to have a switching structure, although not necessarily characterized by a single parameter. It schedules the user most likely to complete when it also has the earlier deadline. When the "better" user has a later deadline, it is scheduled till a worse user's deadline gets "close'", and then the worse user is scheduled till expiry. Our results for periodic arrivals are strong and significant. They reduce the search space for optimal wireless real-time scheduling policies by an exponential order of magnitude. They establish optimality of "virtual-deadline-first" policies, where each user's deadline is modified to take channel quality into account. Policies in this class are easy to implement in a distributed manner.NSF / CCR-0325716 and CNS 05-19535DARPA/AFOSR / F49620-02-1-0325DARPA / N00014-0-1-1-0576 and N66001-06-C-2021Oakridge-Battelle / 239 DOE BATT 4000044522AFOSR / F49620-02-1-0217Ope