18-08-2012, 04:56 PM
Comparison of Routing Metrics for Static Multi-Hop Wireless Networks
1metrics.pdf (Size: 310 KB / Downloads: 19)
ABSTRACT
Routing protocols for wireless ad hoc networks have traditionally
focused on finding paths with minimum hop count.
However, such paths can include slow or lossy links, leading
to poor throughput. A routing algorithm can select better
paths by explicitly taking the quality of the wireless links
into account. In this paper, we conduct a detailed, empirical
evaluation of the performance of three link-quality metrics—
ETX, per-hop RTT, and per-hop packet pair—and compare
them against minimum hop count. We study these metrics
using a DSR-based routing protocol running in a wireless
testbed. We find that the ETX metric has the best performance
when all nodes are stationary. We also find that
the per-hop RTT and per-hop packet-pair metrics perform
poorly due to self-interference. Interestingly, the hop-count
metric outperforms all of the link-quality metrics in a scenario
where the sender is mobile.
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.
LINK QUALITY METRICS
We consider three wireless link quality metrics in this paper.
We also support minimum hop-count routing by defining
a “HOP” metric. Each of these metrics represents a
different notion of what constitutes good link quality. In
Section 7, we will discuss other link quality metrics that we
have not included in this study. The process of link discovery
(i.e. neighbor discovery) is a separate issue, which we
will discuss in in Section 3.
Hop Count (HOP)
This metric provides minimum hop-count routing. Link
quality for this metric is a binary concept; either the link
exists or it doesn’t.
The primary advantage of this metric is its simplicity.
Once the topology is known, it is easy to compute and minimize
the hop count between a source and a destination.
Moreover, computing the hop count requires no additional
measurements, unlike the other metrics we will describe in
this section.
The primary disadvantage of this metric is that it does
not take packet loss or bandwidth into account. It has been
shown [9] that a route that minimizes the hop count does not
necessarily maximize the throughput of a flow. For example,
a two-hop path over reliable or fast links can exhibit better
performance than a one-hop path over a lossy or slow link.
The HOP metric, however, will prefer the one-hop path.
Per-hop Round Trip Time (RTT)
This metric is based on measuring the round trip delay
seen by unicast probes between neighboring nodes. Adya
et al. [1] proposed this metric. To calculate RTT, a node
sends a probe packet carrying a timestamp to each of its
neighbors every 500 milliseconds. Each neighbor immediately
responds to the probe with a probe acknowledgment,
echoing the timestamp. This enables the sending node to
measure round trip time to each of its neighbors. The node
keeps an exponentially weighted moving average of the RTT
samples to each of its neighbors. Our implementation gives
10% weight to the current sample while calculating the average.
If a probe or a probe response packet is lost, the average
is increased by 20% to reflect this loss. Similar penalty is
taken if loss of a data packet is detected on the link. We
also increase the average if we detect a loss of data packet.
The routing algorithm selects the path with the least total
sum of RTTs.
Expected Transmission Count (ETX)
This metric estimates the number of retransmissions needed
to send unicast packets by measuring the loss rate of broadcast
packets between pairs of neighboring nodes. De Couto
et al. [9] proposed ETX. To compute ETX, each node broadcasts
a probe packet every second. The probe contains the
count of probes received from each neighboring node in the
previous 10 seconds. Based on these probes, a node can
calculate the loss rate of probes on the links to and from
its neighbors. Since the 802.11 MAC does not retransmit
broadcast packets, these counts allow the sender to estimate
the number of times the 802.11 ARQ mechanism will
retransmit a unicast packet.
RELATED WORK
There is a large body literature comparing the performance
of various ad hoc routing protocols. Most of this
work is simulation-based and the ad hoc routing protocols
studied all minimize hop-count. Furthermore, many of these
studies focus on scenarios that involve significant node mobility.
For example, Broch et al. [7] compared the performance
of DSDV [23], TORA [22], DSR [15], and AODV [24]
via simulations.
CONCLUSIONS
We have examined the performance of three candidate
link-quality metrics for ad hoc routing and compared them
to minimum hop-count routing. Our results are based on
several months of experiments using a 23-node static ad hoc
network in an office environment. The results show that
with stationary nodes the ETX metric significantly outperforms
hop-count. The RTT and PktPair metrics perform
poorly because they are load-sensitive and hence suffer from
self-interference. However, in a mobile scenario hop-count
performs better because it reacts more quickly to fast topology
change.