11-06-2014, 11:12 AM
A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols
A Performance Comparison.pdf (Size: 175.2 KB / Downloads: 9)
Abstract
An ad hoc network is a collection of wireless mobile nodes dynamically
forming a temporary network without the use of any existing network infrastructure
or centralized administration. Due to the limited transmission range
of wireless network interfaces, multiple network "hops" may be needed for
one node to exchange data with another across the network. In recent years,
a variety of new routing protocols targeted specifically at this environment
have been developed, but little performance information on each protocol
and no realistic performance comparison between them is available. This
paper presents the results of a detailed packet-level simulation comparing
four multi-hop wireless ad hoc network routing protocols that cover a range
of design choices: DSDV, TORA, DSR, and AODV. We have extended
the ns-2 network simulator to accurately model the MAC and physical-layer
behavior of the IEEE 802.11 wireless LAN standard, including a realistic
wireless transmission channel model, and present the results of simulations
of networks of 50 mobile nodes.
Introduction
In areas in which there is little or no communication infrastructure
or the existing infrastructure is expensive or inconvenient to use,
wireless mobile users may still be able to communicate through the
formation of an ad hoc network. In such a network, each mobile node
operates not only as a host but also as a router, forwarding packets
for other mobile nodes in the network that may not be within direct
wireless transmission range of each other. Each node participates in
an ad hoc routing protocol that allows it to discover “multi-hop” paths
through the network to any other node. The idea of ad hoc networking
is sometimes also called infrastructureless networking [13], since the
mobile nodes in the network dynamically establish routing among
themselves to form their own network “on the fly.” Some examples of
the possible uses of ad hoc networking include students using laptop
computers to participate in an interactive lecture, business associates
sharing information during a meeting, soldiers relaying information
for situational awareness on the battlefield [12, 21], and emergency
disaster relief personnel coordinating efforts after a hurricane or
earthquake.
Simulation Environment
ns is a discrete event simulator developed by the University of
California at Berkeley and the VINT project [6]. While it provides
substantial support for simulating TCP and other protocols over conventional
networks, it provides no support for accurately simulating
the physical aspects of multi-hop wireless networks or the MAC protocols
needed in such environments. Berkeley has recently released
ns code that provides some support for modeling wireless LANs, but
this code cannot be used for studying multi-hop ad hoc networks as
it does not support the notion of node position; there is no spatial
diversity (all nodes are in the same collision domain), and it can only
model directly connected nodes.
Ad Hoc Network Routing Protocols Studied
In this section, we briefly describe the key features of the DSDV,
TORA, DSR, and AODV protocols studied in our simulations. We
also describe the particular parameters that we chose when implementing
each protocol.
The protocols were carefully implemented according to their specifications
published as of April 1998 and based on clarifications of
some issues from the designers of each protocol and on our own
experimentation with them. In particular, during the process of implementing
each protocol and analyzing the results from early simulation
runs, we discovered some modifications for each protocol that
improved its performance. The key improvements to each protocol
are highlighted in the respective protocol descriptions below.
Medium Access Control
The link layer of our simulator implements the complete IEEE 802.11
standard [8] Medium Access Control (MAC) protocol Distributed
Coordination Function (DCF) in order to accurately model the
contention of nodes for the wireless medium. DCF is similar to
MACA [11] and MACAW [1] and is designed to use both physical
carrier sense and virtual carrier sense mechanisms to reduce the
probability of collisions due to hidden terminals. The transmission of
each unicast packet is preceded by a Request-to-Send/Clear-to-Send
(RTS/CTS) exchange that reserves the wireless channel for transmission
of a data packet. Each correctly received unicast packet is
followed by an Acknowledgment (ACK) to the sender, which retransmits
the packet a limited number of times until this ACK is received.
Broadcast packets are sent only when virtual and physical carrier
sense indicate that the medium is clear, but they are not preceded by
an RTS/CTS and are not acknowledged by their recipients.
Implementation Decisions
IMEP must queue objects for some period of time to allow possible
aggregation with other objects, but the IMEP specification [5]
does not define this time period, and we discovered that the overall
performance of the protocol was very sensitive to the choice of this
value. After significant experimentation, we chose as the best balance
between packet overhead and routing protocol convergence, to
aggregate HELLO and ACK packets for a time uniformly chosen between
150 ms and 250 ms, and to not delay TORA routing messages
for aggregation. The reason for not delaying these messages is that
the TORA link reversal process creates short-lived routing loops that
exist from the time that the link-reversal starts until the time that all
nodes that need to be aware of the reversal receive the corresponding
UPDATE (Section 5.2). Delaying the transmission of TORA routing
messages for aggregation, coupled with any queuing delay at the
network interface, allows these routing loops to last long enough that
significant numbers of data packets are dropped.
Dynamic Source Routing (DSR)
DSR [9, 10, 2] uses source routing rather than hop-by-hop routing,
with each packet to be routed carrying in its header the complete,
ordered list of nodes through which the packet must pass. The key
advantage of source routing is that intermediate nodes do not need to
maintain up-to-date routing information in order to route the packets
they forward, since the packets themselves already contain all the
routing decisions. This fact, coupled with the on-demand nature of
the protocol, eliminates the need for the periodic route advertis
Movement Model
Nodes in the simulationmove according to a model that we call the
“random waypoint” model [10]. The movement scenario files we
used for each simulation are characterized by a pause time. Each node
begins the simulation by remaining stationary for pause time seconds.
It then selects a random destination in the 1500m ? 300m space and
moves to that destination at a speed distributed uniformly between 0
and some maximum speed. Upon reaching the destination, the node
pauses again for pause time seconds, selects another destination, and
proceeds there as previously described, repeating this behavior for
the duration of the simulation. Each simulation ran for 900 seconds
of simulated time.
Conclusions
The area of ad hoc networking has been receiving increasing attention
among researchers in recent years, as the available wireless
networking and mobile computing hardware bases are now capable
of supporting the promise of this technology. Over the past few
years, a variety of new routing protocols targeted specifically at the
ad hoc networking environment have been proposed, but little performance
information on each protocol and no detailed performance
comparison between the protocols has previously been available.