18-06-2012, 03:34 PM
Minimum Bandwidth Reservations for Periodic Streams in Wireless Real-Time Systems
[attachment=24741]
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.
Network Access Model
We briefly discuss the concept of reservation-based channel
access model (which corresponds to the single time slot
periodic partition model introduced in [3]) since it forms the
basis for the problem we intend to solve. Such a mechanism
uses resource reservations to ensure contention-free accesses.
This is achieved through a central authority at a BS
that regulates the channel accesses of individual nodes.
Here, the BS takes control of the channel and starts polling
each of the nodes in a predetermined order (e.g., roundrobin).
Upon reception of a polling frame, a node gains
access to the channel. The HCCA mode defined in the IEEE
802.11e standard [2] is an example of a protocol which
adopts the reservation-based channel access approach to
enhance the QoS support for real-time applications in
wireless environments.
Problem Definition and Objectives
Each client node requests its desired bandwidth reservation
from the BS and the normalized bandwidth (i.e., the ratio of
SP to the given SI) of a node should be minimum as long as
all real-time streams meet their deadlines. Minimizing the
reserved bandwidth ensures that a node has the maximum
amount of sleep time, thereby minimizing the energy
consumption of its wireless network card. From the
perspective of the BS, the normalized bandwidth of each
node should be minimum as well so that the BS’s throughput
is maximized and the maximum amount of bandwidth is
available for potential future reservation requests of other
nodes. Therefore, the problem and objective can be stated as:
Generic Framework
In this section, we develop a generic algorithmic framework
(Algorithm 1) to solve the MET problem, based on an
augmented time-demand analysis. In the following description,
we distinguish between the finished portion and the
unfinished portion of execution before a given deadline. This
concept allows us to conservatively reduce the sleep time of
the sleep stream to approach its minimum value, assuming
that the reduced sleep time (equal to the unfinished portion)
is solely utilized by the job missing its deadline. To compute
the finished/unfinished portions of a job, we define a
generic time-demand function at every job release event
point.
[attachment=24741]
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.
Network Access Model
We briefly discuss the concept of reservation-based channel
access model (which corresponds to the single time slot
periodic partition model introduced in [3]) since it forms the
basis for the problem we intend to solve. Such a mechanism
uses resource reservations to ensure contention-free accesses.
This is achieved through a central authority at a BS
that regulates the channel accesses of individual nodes.
Here, the BS takes control of the channel and starts polling
each of the nodes in a predetermined order (e.g., roundrobin).
Upon reception of a polling frame, a node gains
access to the channel. The HCCA mode defined in the IEEE
802.11e standard [2] is an example of a protocol which
adopts the reservation-based channel access approach to
enhance the QoS support for real-time applications in
wireless environments.
Problem Definition and Objectives
Each client node requests its desired bandwidth reservation
from the BS and the normalized bandwidth (i.e., the ratio of
SP to the given SI) of a node should be minimum as long as
all real-time streams meet their deadlines. Minimizing the
reserved bandwidth ensures that a node has the maximum
amount of sleep time, thereby minimizing the energy
consumption of its wireless network card. From the
perspective of the BS, the normalized bandwidth of each
node should be minimum as well so that the BS’s throughput
is maximized and the maximum amount of bandwidth is
available for potential future reservation requests of other
nodes. Therefore, the problem and objective can be stated as:
Generic Framework
In this section, we develop a generic algorithmic framework
(Algorithm 1) to solve the MET problem, based on an
augmented time-demand analysis. In the following description,
we distinguish between the finished portion and the
unfinished portion of execution before a given deadline. This
concept allows us to conservatively reduce the sleep time of
the sleep stream to approach its minimum value, assuming
that the reduced sleep time (equal to the unfinished portion)
is solely utilized by the job missing its deadline. To compute
the finished/unfinished portions of a job, we define a
generic time-demand function at every job release event
point.