University of Illinois Urbana-Champaign

Real-Time Scheduling in Wireless Networks

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

Content Files
DC-227 assembled.pdf

Permalink

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

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
Date of Ingest
2018-04-03T21:52:33Z
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
Genre of Resource
Technical Report
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

Report - Coordinated Science Laboratory PRIMARY