30-10-2012, 04:59 PM
Opportunistic Routing for Interactive Traffic in Wireless Networks
Opportunistic Routing.pdf (Size: 219.11 KB / Downloads: 21)
Abstract
To take advantage of the broadcast nature of wireless
communication, a number of opportunistic routing techniques
have recently been proposed. In order to manage the extra
signaling overhead associated with operation of the opportunistic
routing, these schemes work in terms of ‘batches’ consisting
of multiple packets. While these opportunistic techniques can
dramatically improve the system performance, use of batches
means that they are best suited to UDP traffic. In the Internet and
wireless networks, however, the vast majority of the traffic is interactive1
(e.g., up to 80-90% is TCP). To support interactive traffic
opportunistically and efficiently, we introduce a novel scheme
called RIPPLE. In the RIPPLE scheme, an expedited multihop
transmission opportunity mechanism ensures low signaling
overhead and eliminates re-ordering, and a two-way packet
aggregation technique further reduces overhead. We implement
the RIPPLE and related schemes2 in NS-2 and compare their
performance for long- and short-lived TCP transfers and VoIP
traffic over a wide range of network conditions, including varied
wireless channel states, levels of regular and hidden collisions,
and geographic locations of stations derived from measurement
studies (i.e., the Wigle and Roofnet topologies), etc. Our results
show that the RIPPLE scheme consistently delivers 100% – 300%
performance gains over other approaches.
INTRODUCTION
Wireless communication is inherently broadcast in nature.
A unicast transmission can be heard not only by the target
receiver, but also by every other station in the neighborhood
of the transmitter. Indeed, these stations (called forwarders
hereafter) typically decode all transmissions they hear and
then drop transmissions for which they are not the intended
recipients. To take advantage of this broadcast property, it is
appealing to let forwarders help relay overheard traffic. This
can be expected to yield significant performance gains when,
for example, the link between the sender and the receiver is
poor, but the links between the forwarders and the sender, and
the links between the forwarders and the receiver are good.
This idea is often referred to as opportunistic routing in the
literature (e.g., [14] [7] [8] [25]).
Comparison
In the context of opportunistic routing, the receiver R is
able to hear from the sender S but the link quality between
them is normally low. The link quality between the sender
S and the forwarders in F and that between the forwarders
in F and the receiver R is normally high. Thus, a properly
designed opportunistic routing scheme should be able to seize
the opportunities when a transmission from S is directly heard
by R, or by high priority forwarders that are close to R, so
as to reduce the number of transmissions needed to forward
packets, and thereby improving system efficiency.
However, this performance gain is often not achieved when
using the preExOR and MCExOR schemes for supporting
interactive traffic such as TCP and VoIP. There are two reasons
for this inefficiency: signaling overhead and packet reordering.
THE RIPPLE SCHEME
The Main Idea
For opportunistic routing protocols (as discussed in the
previous section), performance for supporting interactive flows
is mainly affected by two key issues: packet re-ordering and
the per packet signaling overhead. In the RIPPLE scheme,
these two issues are resolved in the following manner.
1) Resolving Re-ordering: The cause of packet re-ordering,
as introduced in the last section, is the time difference between
transmissions of new packets by the sender, and transmissions
of old packets by the forwarders. To solve this issue, we
do not let the forwarders cache any heard frames while still
letting them help forward transmissions (This is thus an idea
similar to that proposed in [22] for next generation mobile
ad-hoc networks). That is, we design an atomic operation
between the sender and the receiver within which re-ordering
can be completely eliminated. We call this kind of operation
a multi-hop transmission opportunity4 (mTXOP) and describe
the details in the following steps.
EVALUATION
We implemented the RIPPLE and related schemes (namely
predetermined routing, shortest path routing, preExOR,
MCExOR and a 802.11n-like single-hop packet aggregation
scheme called AFR[17]) in NS-2. All results presented are
averages over multiple runs. Due to packet re-ordering and
signaling issues introduced in Section II, the performance of
the preExOR and MCExOR schemes is always worse that with
predetermined routing schemes, and so we do not introduce
their results in this section.
To evaluate performance when the channel is error prone
and both intra-path and inter-path collisions happen (see
Section III Remark (3)). We use a combination of frame and
bit error models.
Short-lived TCP Transfers: Web Traffic
In this section, we present results for short TCP transfers
which mimic realistic web traffic ([21]). Web traffic consists of
ON/OFF periods. During the ON time, a web user visits some
web pages, whilst in the OFF time, the user is reading what
he/she just downloaded. To run the simulations in a realistic
manner, traffic generated in ON periods should be Long-Range
Dependent, i.e., resembles the aggregation of many ON-OFF
senders with heavy-tailed ON periods. In this paper, a transfer
sized with a Pareto distribution with mean 80KB and shape
parameter 1.5, is used when the traffic is in ON time. While
during the OFF periods, no traffic is generated. The length of
the OFF periods follows an exponential distribution with mean
duration of one second.
CONCLUSIONS AND FUTURE WORK
In this paper, we introduced a novel scheme called RIPPLE.
In the RIPPLE scheme, an expedited multi-hop transmission
opportunity mechanism ensures low signaling overhead and
eliminates re-ordering, and a two-way packet aggregation technique
further reduces overhead. We implement the RIPPLE
and related schemes in NS-2 and compare their performance
for long/short TCP transfers and VoIP over a wide range of
network conditions, including varied wireless channel states,
levels of regular/hidden collisions, and geographic locations of
stations derived from measurement studies (i.e., the Wigle and
Roofnet topologies), etc. Our results show that the RIPPLE
scheme consistently delivers 100% – 300% performance gains
over other approaches.