Files in this item

FilesDescriptionFormat

application/pdf

application/pdfDC-227 assembled.pdf (202kB)
(no description provided)PDF

Description

Title:Real-Time Scheduling in Wireless Networks
Author(s):Raghunathan, Vivek; Cao, Min; Kumar, P.R.
Subject(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.
Issue Date:2007-03
Publisher:Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Series/Report:Coordinated Science Laboratory Report no. DC-227
Genre:Technical Report
Type:Text
Language:English
URI:http://hdl.handle.net/2142/99600
Sponsor: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
Date Available in IDEALS:2018-04-03


This item appears in the following Collection(s)

Item Statistics