Real-Time Scheduling in Wireless Networks

Raghunathan, Vivek; Cao, Min; Kumar, P.R.

Permalink

https://hdl.handle.net/2142/99600 Copy

Description

Title

Real-Time Scheduling in Wireless Networks

Author(s)

• Raghunathan, Vivek
• Cao, Min
• Kumar, P.R.

Issue Date

2007-03

Keyword(s)

• Real-time
• Wireless networks
• Loss
• Opportunistic scheduling
• Dynamic
• Programming

Abstract

"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."

Publisher

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

Series/Report Name or Number

Coordinated Science Laboratory Report no. DC-227

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/99600

Sponsor(s)/Grant Number(s)

• NSF / CCR-0325716 and CNS 05-19535
• DARPA/AFOSR / F49620-02-1-0325
• DARPA / N00014-0-1-1-0576 and N66001-06-C-2021
• Oakridge-Battelle / 239 DOE BATT 4000044522
• AFOSR / F49620-02-1-0217

Owning Collections