25-07-2012, 03:32 PM
Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks
Multi-Radio, Multi-Hop Wireless Mesh Networks.pdf (Size: 315.72 KB / Downloads: 19)
ABSTRACT
We present a new metric for routing in multi-radio, multihop
wireless networks. We focus on wireless networks with
stationary nodes, such as community wireless networks.
The goal of the metric is to choose a high-throughput path
between a source and a destination. Our metric assigns
weights to individual links based on the Expected Transmission
Time (ETT) of a packet over the link. The ETT
is a function of the loss rate and the bandwidth of the link.
The individual link weights are combined into a path metric
called Weighted Cumulative ETT (WCETT) that explicitly
accounts for the interference among links that use the same
channel. The WCETT metric is incorporated into a routing
protocol that we call Multi-Radio Link-Quality Source
Routing.
INTRODUCTION
Routing in ad-hoc wireless networks has been an active
area of research for many years. Much of the original work
in the area was motivated by mobile application environments,
such as battlefield ad-hoc networks. The primary focus in such environments is to provide scalable routing in
the presence of mobile nodes.
Recently, interesting commercial applications of multi-hop
wireless networks have emerged. One example of such applications
is “community wireless networks” [6, 37, 35, 27].
Several companies [31, 34] are field-testing wireless networks
to provide broadband Internet access to communities that
previously did not have such access.
WHY A NEW ROUTING METRIC?
Much prior research [43, 4, 24, 13, 18, 20] has recognized
the shortcomings of shortest-path routing in multi-hop wireless
networks. In this section, we will focus on the ETX
(Expected Transmission Count) routing metric proposed by
De Couto et al. [15]. Section 7 discusses other related work.
The work of De Couto et al. shares our goal of using inexpensive,
commodity hardware to build and deploy multi-hop
wireless networks. They also use a similar indoor testbed environment
with stationary nodes for evaluation. Although
ETX does very well in homogeneous single-radio environments,
as we will show it does not perform as well in environments
with different data rates or multiple radios. We
will first review the definition of ETX and then discuss its
performance.
The ETX metric measures the expected number of transmissions,
including retransmissions, needed to send a unicast
packet across a link. The derivation of ETX starts with
measurements of the underlying packet loss probability in
both the forward and reverse directions; denoted by pf and
pr, respectively; and then calculates the expected number
of transmissions.
Computing Path Metric
In keeping with the design goals, MR-LQSR assigns a
weight to each link that is equal to the expected amount
of time it would take to successfully transmit a packet of
some fixed size S on that link. This time depends on the
link bandwidth and loss rate. For now, let us assume that
given a link i from node x to node y, we know how to calculate
the expected transmission time (ETT) of the packet
on this link. We denote this value by ETTi. (We describe
the calculation of ETT in the next subsection.) The next
question is how to combine the individual ETT link weights
of hops along a path into a metric that reflects the overall
“goodness” of the path.
Computing ETT
We define the ETT of a link as a “bandwidth-adjusted
ETX.” In other words, we start with the ETX (number of
expected transmissions) and multiply by the link bandwidth
to obtain the time spent in transmitting the packet. We can
formalize this as follows. Let S denote the size of the packet
(for example, 1024 bytes) and B the bandwidth (raw data
rate) of the link. Then:
Note that this definition of ETT does not incorporate
backoff time spent waiting for the radio channel; it only
reflects the time spent actually using the channel. In Appendix
A, we consider an alternative definition that includes
backoff time.
Discussion
In the derivation of ETT we did not explicitly consider
the impact of contention due to traffic from nearby nodes.
The contending traffic affects the link in two ways. First,
it may increase the packet loss rate due to collisions, and
second it reduces the available bandwidth.
In our derivation, we assumed that packet loss rate is an
independent parameter. This is in keeping with the models
developed in [10, 8]. In reality, it might be dependent on
the channel utilization. In our implementation, we continuously
measure the channel loss rate and update the ETT
value accordingly. Thus, we automatically account for any
changes in the loss rate due to channel utilization.
IMPLEMENTATION
We have implemented our MR-LQSR protocol (the LQSR
routing protocol plus theWCETT metric) in an ad-hoc routing
framework that we call theMesh Connectivity Layer (MCL).
Architecturally, MCL is a loadable Windows driver. It implements
a virtual network adapter, so that to the rest of
the system the ad-hoc network appears as an additional (virtual)
network link. Under the covers, MCL routes packets
using the LQSR protocol. We have implemented a variety
of link-quality metrics for LQSR, including WCETT and
ETX, and basic shortest-path routing. In this section, we
briefly review our architecture and implementation to provide
background for understanding the performance results.
More architectural and implementation details are available
in [16].
Band and Channel Assignment
One of the assumptions we made in designing our routing
metric is that the channels used by the multiple radios
are non-interfering. We performed a series of tests to verify
that this was indeed the case for the bands and channels we
use in our testbed environment. These tests were performed
using three dual-radio nodes from our testbed, namely 201,
204, and 205. See Figure 3. Nodes 201 and 204 were always
the senders, and 205 was always the receiver. Our
methodology was to first measure the TCP throughput between
each of the senders and the receiver alone, and then
simultaneously with both senders operating. If the transfers
are truly non-interfering, we would expect the throughputs
to be essentially the same whether run independently or simultaneously.
RELATED WORK
Several researchers have studied the problem of capacity
reduction in multi-hop wireless networks [21, 25] from a theoretical
perspective. In [29, 21], the authors show that observed
capacity is far below the theoretical optimum, using
evidence from deployed multi-hop 802.11 wireless meshes.
They observe that throughput degrades quickly as the number
of hops increases. One reason is that the 802.11 MAC
is inherently unfair and it can stall the flow of packets over
multiple hops. Another reason is that these networks use
only a small portion of the spectrum and a single radio for
transmitting and receiving packets.
CONCLUSION
We have shown that when nodes are equipped with multiple
heterogenous radios, it is important to select channeldiverse
paths in addition to accounting for the loss rate and
bandwidth of individual links. We have implemented a routing
protocol MR-LQSR (Multi-Radio Link-Quality Source
Routing) with a new metric WCETT (Weighted Cumulative
Expected Transmission Time) to accomplish this task,
and compared its performance to other routing metrics in
a multi-radio testbed. Our results show that WCETT outperforms
previously-proposed metrics.