31-01-2013, 10:38 AM
Opportunistic Routing in Multi-radio Multi-channel Multi-hop Wireless Networks
Opportunistic Routing.pdf (Size: 175.6 KB / Downloads: 19)
Abstract
Two major factors that limit the throughput in
multi-hop wireless networks are the unreliability of wireless
transmissions and co-channel interference. One promising technique
that combats lossy wireless transmissions is opportunistic
routing (OR). OR involves multiple forwarding candidates to
relay packets by taking advantage of the broadcast nature and
spacial diversity of the wireless medium. Furthermore, recent
advances in multi-radio multi-channel transmission technology
allows more concurrent transmissions in the network, and shows
the potential of substantially improving the system capacity.
However, the performance of OR in multi-radio multi-channel
multi-hop networks is still unknown, and the methodology of
studying the performance of traditional routing (TR) can not be
directly applied to OR. In this paper, we present our research
on computing an end-to-end throughput bound of OR in multiradio
multi-channel multi-hop wireless networks. We formulate
the capacity of OR as a linear programming (LP) problem which
jointly solves the radio-channel assignment and transmission
scheduling. Leveraging our analytical model, we gain the following
insights into OR: 1) OR can achieve better performance
than TR under different radio/channel configurations, however,
in particular scenarios, TR is more preferable than OR; 2) OR
can achieve comparable or even better performance than TR
by using less radio resource; 3) for OR, the throughput gained
from increasing the number of potential forwarding candidates
becomes marginal.
INTRODUCTION
Multi-hop wireless networks have attracted increasing attention
in recent years owing to its easy deployment and
wide range of applications. Two major factors that limit the
throughput in multi-hop wireless networks are the unreliability
of wireless transmissions and co-channel interference. One
promising network-MAC cross-layer design to improve the
wireless network throughput is opportunistic routing (OR)
[1]–[7], which involves multiple forwarding candidates at
each hop, and the actual forwarder is selected after packet
transmission according to the instant link reachability and
availability. It is quite different from the traditional routing
(TR) that only one pre-selected next-hop node is involved
to forward packets at each hop. It has been shown that
OR achieves much higher throughput than TR in multi-hop
wireless networks [1], [4], [7]. Furthermore, with the spur
of modern wireless technologies, another way to improve
system throughput is to allow more concurrent transmissions
by installing multiple radio interfaces on one node with each
radio tuned to a different orthogonal channel [8]–[10].
SYSTEM MODEL AND OPPORTUNISTIC ROUTING
PRIMER
We consider a multi-hop wireless network with N nodes.
Each node ni (1 ≤ i ≤ N) is equipped with one or more
wireless interface cards, referred to as radios in this work.
Denote the number of radios in each node ni as ti (i =
1...N ). Assume K orthogonal channels are available in the
network without any inter-channel interference. We consider
the system with channel switching capability, such that a radio
can dynamically switch across different channels. We assume
there is no performance gain to assign the same channel to the
different radios on the same node. For simplicity, we assume
each node ni transmits at the same data rate Ri among all
its radios and channels. We also assume half-duplex on each
radio, that is, a radio can not transmit and receive packets
at the same time. There is a unified transmission range RT
and interference range RI for the whole network. Typically,
RI > RT . Two nodes, ni and nj , can communicate with
each other if the Euclidean distance dij between them is less
than RT and they are operated on the same channel.
Opportunistic Routing Primer
Different from TR, OR basically runs in such a way that
for each local packet forwarding, a set of next-hop forwarding
candidates are selected at the network layer and one of them
is chosen as the actual relay at the MAC layer according to
their instantaneous availability and reachability at the time
of transmission. We introduce the concept of opportunistic
module for OR. A subset
of the one-hop neighbors will be selected as forwarding
candidates. Only the forwarding candidates will help forward
the packet. To avoid packet duplication, only one of the
forwarding candidates becomes the actual forwarder of each
packet. There is a forwarding priority among these forwarding
candidates to decide who should forward the packet if multiple
forwarding candidates correctly receive the same packet. We
use an ordered set Fi, the forwarding candidate sequence,
which is one permutation of the forwarding candidates, to
represent the forwarding priority.
Simulation of Random Networks
In this subsection, we investigate the throughput bound of
OR and TR in multi-radio multi-channel multi-hop networks
and compare the results with that in single-radio singlechannel
systems. In the simulation, we randomly deploy 12
nodes in a rectangle area of 200 units × 300 units. We select
node n1 at the left corner of the network as the destination,
then calculate the throughput bound from other nodes to the
destination using the LP formulations in Fig. 2. Therefore,
there are 11 different source-destination pairs considered in
the evaluation. In all the simulations, we assume the packet
reception ratio is inversely proportional to the distance with
gasussian random variation, which simulates the log-normal
fading and two-ray path loss model. The interference range
RI = 2RT . The transmission range RT is set as 100 units. The
performance metric is the normalized end-to-end throughput
bound (by assuming the transmission rate is unit one).
CONCLUSIONS AND FUTURE WORK
In this paper, we proposed a unified framework to compute
the throughput bound of opportunistic routing between two
end nodes in multi-radio multi-channel multi-hop wireless
networks. Our model accurately captures the unique property
of OR that throughput can take place from a transmitter
to any one of its forwarding candidates at any instant. Our
methodology can be used to calculate the end-to-end throughput
bound of OR and TR in multi-radio multi-channel multihop
wireless networks, as well as to study the OR behaviors
(such as candidate selection and prioritization).