22-06-2012, 12:46 PM
Minimum Bandwidth Reservations for Periodic Streams in Wireless Real-Time Systems
INTRODUCTION
WIRELESS embedded real-time systems are becoming
prevalent with the continuous increase in streaming
applications such as video/audio communications, industrial
automation, networked and embedded control systems,
and wireless sensor and actuator networks. This has
called for research efforts to enhance the support of
timeliness and Quality of Service (QoS) in wirelessly
networked embedded environments. Wireless networks
are inherently broadcast and media-shared. Contentionbased
media accesses such as CSMA are nondeterministic
and thus incapable of providing predictable QoS support to
periodic communications often found in wireless real-time
systems. Moreover, multiple nodes are active simultaneously
and continuously sense and contend for the shared
media, leading to excessive energy consumption.
RELATED WORK
Scheduling and schedulability analysis have been extensively
studied in previous work, particularly for processing
resources. In networking environments, reservation-based
mechanisms are becoming highly prominent in supporting
latency-critical and energy-aware traffic. In this section, we
discuss existing protocol standards and techniques related
to resource and channel access reservations.
Traffic Model
We consider a set of wireless nodes with applications on
each node generating one or more periodic real-time
streams. Nodes connect wirelessly to a common BS to
access an external network. We denote the set of periodic
streams generated by a node as S ¼ fS1; . . . ; Sng. Each
stream Si periodically generates a certain number (worst
case or average case) of bytes (called a datagram) for a given
period pi for transmission. The datagram generated at the
beginning of the jth period of Si for transmission is denoted
as Ji;j. Wireless channel conditions are time-varying and
error-prone.
MODEL TRANSFORMATION
To approach the MBR problem, we first transform the
scheduling model M ¼ ðS ¼ fSign
1;B ¼ ðSP; SIÞ;AÞ of the
MBR problem to another scheduling modelM0 ¼ ðS0;B0;A0Þ,
where the stream set S0 extends S by adding a sleep stream;
the scheduling policy A0 extends A by assigning the sleep
stream the highest priority; and B0 represents the dedicated
resource allocation for S0. We show that the two scheduling
models are schedulably equivalent, i.e., M is schedulable if
and only if M0 is schedulable. As a corollary, we show that
the MBR problem in M is a dual of the maximum execution
time problem of the sleep stream in M0.
INTRODUCTION
WIRELESS embedded real-time systems are becoming
prevalent with the continuous increase in streaming
applications such as video/audio communications, industrial
automation, networked and embedded control systems,
and wireless sensor and actuator networks. This has
called for research efforts to enhance the support of
timeliness and Quality of Service (QoS) in wirelessly
networked embedded environments. Wireless networks
are inherently broadcast and media-shared. Contentionbased
media accesses such as CSMA are nondeterministic
and thus incapable of providing predictable QoS support to
periodic communications often found in wireless real-time
systems. Moreover, multiple nodes are active simultaneously
and continuously sense and contend for the shared
media, leading to excessive energy consumption.
RELATED WORK
Scheduling and schedulability analysis have been extensively
studied in previous work, particularly for processing
resources. In networking environments, reservation-based
mechanisms are becoming highly prominent in supporting
latency-critical and energy-aware traffic. In this section, we
discuss existing protocol standards and techniques related
to resource and channel access reservations.
Traffic Model
We consider a set of wireless nodes with applications on
each node generating one or more periodic real-time
streams. Nodes connect wirelessly to a common BS to
access an external network. We denote the set of periodic
streams generated by a node as S ¼ fS1; . . . ; Sng. Each
stream Si periodically generates a certain number (worst
case or average case) of bytes (called a datagram) for a given
period pi for transmission. The datagram generated at the
beginning of the jth period of Si for transmission is denoted
as Ji;j. Wireless channel conditions are time-varying and
error-prone.
MODEL TRANSFORMATION
To approach the MBR problem, we first transform the
scheduling model M ¼ ðS ¼ fSign
1;B ¼ ðSP; SIÞ;AÞ of the
MBR problem to another scheduling modelM0 ¼ ðS0;B0;A0Þ,
where the stream set S0 extends S by adding a sleep stream;
the scheduling policy A0 extends A by assigning the sleep
stream the highest priority; and B0 represents the dedicated
resource allocation for S0. We show that the two scheduling
models are schedulably equivalent, i.e., M is schedulable if
and only if M0 is schedulable. As a corollary, we show that
the MBR problem in M is a dual of the maximum execution
time problem of the sleep stream in M0.