29-01-2013, 02:31 PM
Distributed Opportunistic Scheduling in Multihop Wireless Ad Hoc Networks
[attachment=48738]
Abstract
In this paper, we introduce a framework for distributed
opportunistic scheduling in multihop wireless ad hoc networks.
With the proposed framework, one can take a scheduling
algorithm originally designed for infrastructure-based wireless
networks and adapt it to multihop ad hoc networks. The
framework includes a wireless link state estimation mechanism,
a medium access control (MAC) protocols and a MAC load
control mechanism. The proposed link state estimation mechanism
accounts for the latest results of packet transmissions on
each wireless link. To improve robustness and provide service
isolation during channel errors, the MAC protocol should not
make any packet retransmissions but only report the transmission
result to the scheduler. We modify IEEE 802.11 to fulfill these
requirements. The MAC load control mechanism improves the
system robustness. With link state information and the modified
IEEE 802.11 MAC, we use BGFS-EBA, an opportunistic
scheduling algorithm for infrastructured wireless networks, as
an example to demonstrate how such an algorithm is converted
into its distributed version within the proposed framework. The
simulation results show that our proposed method can provide
robust outcome fairness in the presence of channel errors.
INTRODUCTION
A wireless ad hoc network consists of a number of nodes
communicating with each other on wireless links without
infrastructure support. A multihop ad hoc network is an ad
hoc network in which the packets of a traffic flow are relayed
by one or more intermediate nodes before they reach the destination.
To support different types of multimedia applications,
providing various quality of service (QoS) guarantees for multihop
flows is an important issue in wireless ad hoc networks.
In this paper, we focus on the issue of providing robust service
isolation and outcome fairness through opportunistic packet
scheduling.
Some recent work [1], [2], [3] have been proposed for
fair packet scheduling in wireless ad hoc networks. In the
rest of this section, we first survey the related work on error
compensation and opportunistic scheduling in multihop ad hoc
networks. Then, we describe the problem we are facing and
our major contributions on resolving it.
Related Work
In [4], a fair scheduling algorithm, namely, TBCP (Timestamp
Based Compensation Protocol), is proposed to account
for channel errors. By employing a TDMA1-based system,
TBCP is designed to adapt the start-time fair queueing (SFQ)
scheme [5] into the ad hoc environment. Nodes exchange their
service tags among two-hop neighbors at the beginning of each
frame. The time slot allocation is decided based on the service
tags. A flow experiencing channel errors will be compensated
automatically since a packet which has been sent unsuccessfully
tends to have a smaller service tag and a higher priority.
Although collisions among neighboring nodes are inevitable
since they do not have exactly the same information, TBCP
does not handle collisions due to conflicts in the transmission
schedules computed by different nodes. TBCP does not utilize
the link status information to improve performance.
Our Contributions and Organization of the Paper
To the best of our knowledge, none of the previous work
takes error compensation, link status estimation and fair
scheduling into consideration simultaneously for distributed
scheduling in multihop ad hoc networks. In this work, we propose
a framework, named “Robust Opportunistic Scheduling
for Ad Hoc Networks” (ROSA), with which a scheduling algorithm
originally designed for infrastructured wireless networks
can be adapted to multihop ad hoc networks. The adapted
algorithm performs distributed scheduling opportunistically by
utilizing the link status information provided by ROSA. We
also improve the robustness of the system by limiting the
traffic load at the MAC layer.
The rest of the paper is organized as follows. Section II describes
the system model and the assumptions used throughout
the paper. Section III describes the ROSA framework in detail.
Section IV presents the performance results through simulation
in ns-2 [13]. We conclude our work in Section V.
SYSTEM MODEL AND ASSUMPTIONS
We consider a multihop wireless ad hoc network. Nodes
communicate over the same channel. A node cannot transmit
and receive packets simultaneously. A collision happens when
a receiver is in the transmission ranges of multiple transmitters.
Wireless links are error-prone and the occurrences of channel
errors are not negligible.
Instead of using static flow weights, the QoS requirement
of an end-to-end flow specifies the desired service rate. An
admission control mechanism is used to grant the desired QoS
requirements. The desired service rate is propagated to all the
intermediate nodes along the path. This may be accomplished
by piggy-backing the desired rate on each packet of the flow.
For ease of presentation, we assume that a contention-based
MAC scheme is used, although this is not a requirement of
ROSA. Since the packet transmission schedule is computed
at each node locally based on incomplete and conflicting
network information, collisions are inevitable. However, with
the admission control mechanism no flow shall offer a traffic
load above the admitted service rate. We assume that the
collision rates are statistically stable and predictable [14]
SIMULATION RESULTS AND DISCUSSION
The simulation is performed with ns-2, in which the proposed
link status estimation mechanism, ROSA-MAC protocol,
and the OBGSA scheduling algorithm are all implemented.
Link errors are caused by channel fading. A practical
ns-2 extension for the well-known Ricean fading model is
used [16]. The capacity of the wireless channel used in the
simulation is 2 Mbps or 256 KBps. Table I lists the ROSA
parameters used in the simulation.
CONCLUSION
In this paper, we present the ROSA framework for distributed
opportunistic scheduling in multihop wireless ad hoc
networks. The framework includes a link status estimation
mechanism, the MAC protocol and a MAC load control
mechanism. We use BGFS-EBA as an example and adapt
it to ad hoc networks within the ROSA framework. The
simulation results show that the adapted algorithm increases
the system throughput and provides robust outcome fairness
in the presence of channel errors. In the future, we shall adapt
other scheduling algorithms designed for infrastructure-based
wireless networks by transforming them to the distributed
algorithms for to multihop ad hoc networks under the ROSA
framework.
[attachment=48738]
Abstract
In this paper, we introduce a framework for distributed
opportunistic scheduling in multihop wireless ad hoc networks.
With the proposed framework, one can take a scheduling
algorithm originally designed for infrastructure-based wireless
networks and adapt it to multihop ad hoc networks. The
framework includes a wireless link state estimation mechanism,
a medium access control (MAC) protocols and a MAC load
control mechanism. The proposed link state estimation mechanism
accounts for the latest results of packet transmissions on
each wireless link. To improve robustness and provide service
isolation during channel errors, the MAC protocol should not
make any packet retransmissions but only report the transmission
result to the scheduler. We modify IEEE 802.11 to fulfill these
requirements. The MAC load control mechanism improves the
system robustness. With link state information and the modified
IEEE 802.11 MAC, we use BGFS-EBA, an opportunistic
scheduling algorithm for infrastructured wireless networks, as
an example to demonstrate how such an algorithm is converted
into its distributed version within the proposed framework. The
simulation results show that our proposed method can provide
robust outcome fairness in the presence of channel errors.
INTRODUCTION
A wireless ad hoc network consists of a number of nodes
communicating with each other on wireless links without
infrastructure support. A multihop ad hoc network is an ad
hoc network in which the packets of a traffic flow are relayed
by one or more intermediate nodes before they reach the destination.
To support different types of multimedia applications,
providing various quality of service (QoS) guarantees for multihop
flows is an important issue in wireless ad hoc networks.
In this paper, we focus on the issue of providing robust service
isolation and outcome fairness through opportunistic packet
scheduling.
Some recent work [1], [2], [3] have been proposed for
fair packet scheduling in wireless ad hoc networks. In the
rest of this section, we first survey the related work on error
compensation and opportunistic scheduling in multihop ad hoc
networks. Then, we describe the problem we are facing and
our major contributions on resolving it.
Related Work
In [4], a fair scheduling algorithm, namely, TBCP (Timestamp
Based Compensation Protocol), is proposed to account
for channel errors. By employing a TDMA1-based system,
TBCP is designed to adapt the start-time fair queueing (SFQ)
scheme [5] into the ad hoc environment. Nodes exchange their
service tags among two-hop neighbors at the beginning of each
frame. The time slot allocation is decided based on the service
tags. A flow experiencing channel errors will be compensated
automatically since a packet which has been sent unsuccessfully
tends to have a smaller service tag and a higher priority.
Although collisions among neighboring nodes are inevitable
since they do not have exactly the same information, TBCP
does not handle collisions due to conflicts in the transmission
schedules computed by different nodes. TBCP does not utilize
the link status information to improve performance.
Our Contributions and Organization of the Paper
To the best of our knowledge, none of the previous work
takes error compensation, link status estimation and fair
scheduling into consideration simultaneously for distributed
scheduling in multihop ad hoc networks. In this work, we propose
a framework, named “Robust Opportunistic Scheduling
for Ad Hoc Networks” (ROSA), with which a scheduling algorithm
originally designed for infrastructured wireless networks
can be adapted to multihop ad hoc networks. The adapted
algorithm performs distributed scheduling opportunistically by
utilizing the link status information provided by ROSA. We
also improve the robustness of the system by limiting the
traffic load at the MAC layer.
The rest of the paper is organized as follows. Section II describes
the system model and the assumptions used throughout
the paper. Section III describes the ROSA framework in detail.
Section IV presents the performance results through simulation
in ns-2 [13]. We conclude our work in Section V.
SYSTEM MODEL AND ASSUMPTIONS
We consider a multihop wireless ad hoc network. Nodes
communicate over the same channel. A node cannot transmit
and receive packets simultaneously. A collision happens when
a receiver is in the transmission ranges of multiple transmitters.
Wireless links are error-prone and the occurrences of channel
errors are not negligible.
Instead of using static flow weights, the QoS requirement
of an end-to-end flow specifies the desired service rate. An
admission control mechanism is used to grant the desired QoS
requirements. The desired service rate is propagated to all the
intermediate nodes along the path. This may be accomplished
by piggy-backing the desired rate on each packet of the flow.
For ease of presentation, we assume that a contention-based
MAC scheme is used, although this is not a requirement of
ROSA. Since the packet transmission schedule is computed
at each node locally based on incomplete and conflicting
network information, collisions are inevitable. However, with
the admission control mechanism no flow shall offer a traffic
load above the admitted service rate. We assume that the
collision rates are statistically stable and predictable [14]
SIMULATION RESULTS AND DISCUSSION
The simulation is performed with ns-2, in which the proposed
link status estimation mechanism, ROSA-MAC protocol,
and the OBGSA scheduling algorithm are all implemented.
Link errors are caused by channel fading. A practical
ns-2 extension for the well-known Ricean fading model is
used [16]. The capacity of the wireless channel used in the
simulation is 2 Mbps or 256 KBps. Table I lists the ROSA
parameters used in the simulation.
CONCLUSION
In this paper, we present the ROSA framework for distributed
opportunistic scheduling in multihop wireless ad hoc
networks. The framework includes a link status estimation
mechanism, the MAC protocol and a MAC load control
mechanism. We use BGFS-EBA as an example and adapt
it to ad hoc networks within the ROSA framework. The
simulation results show that the adapted algorithm increases
the system throughput and provides robust outcome fairness
in the presence of channel errors. In the future, we shall adapt
other scheduling algorithms designed for infrastructure-based
wireless networks by transforming them to the distributed
algorithms for to multihop ad hoc networks under the ROSA
framework.