hoceedings
ofthe
2004
IEEE
International
Conference
on
Networking,
Sensing
&
Control
Taipei,
Taiwan,
March
21-23,
2004
Ad
Hoc Network
Routing
Victor
0.
K.
Li
Department
of
Electrical
&
Electronic
Engineering
University
of
Hong
Kong
Hong
Kong,
China
vli@eee.hku.hk
Abstract
-
An
ad hoc network is composed
of
nodes that
may move arbitrarily and without the suppon of a
stationary infrastructure. The dynamic nature
of
ad hoc
networh makes it very challenging
to
realize routing and
deliver data packets efficiently. This article discusses the
challenges
of
ad hoc network routing, surveys existing
routing algorithms, and provides a comparison
of
these
algorithms.
Keywords:
ad hoc, routing, proactive, reactive,
comparison.
1
Introduction
An
ad hoc network, also known
as
a multi-hop
packet radio network, is composed of nodes that may
move arbitrarily and without the support of a stationary
infrastructure. Research in such networks is initiated
in
the Defense Advanced Research Projects Agency
(DARPA) packet radio network
[l].
They may be used in
emergency search-and-rescue operations, battle field
operations and data acquisition
in
inhospitable terrain.
This article surveys routing protocols designed for ad hoc
networks and compares them.
2
Ad
Hoc
Network Routing
To
design a good routing scheme for ad hoc
networks, we must consider the following issues:
2.1
The scalability
of
the protocol with network
size
The size of an ad hoc network may be quite large
in
many applications such as communications in battle fields
and disaster search-and-rescue operations. As there is no
wired infrastructure to serve as a backbone, the same
bandwidth is used to find and maintain routes as well as to
transmit data.
As
its size grows, the amount of
information required to
be
transmitted and to he
maintained by each node in an ad hoc network grows
exponentially.
2.2
Frequent topological changes
A mobile ad hoc network is
an
autonomous system
of nodes connected by wireless links, and nodes may
move randomly and organize themselves arbitrarily. The
topology
of
the network may change rapidly and
Zhenxin
Lu
Department
of
Electrical
&
Electronic Engineering
University
of
Hong
Kong
Hong Kong,
China
zxlu8eee.hku.hk
unpredictably. When the current route is unusable, a new
one must be re-established.
2.3
Unidirectional
Links
An ad hoc network may he composed of different
kinds of devices, each with its own transmission
characteristics.
In
addition, the same device may have
different transmission ranges due to power constraints.
So,
if node A can transmit to node
B,
one can not assume that
node
B
can transmit to node A. Interference may also
introduce unidirectional links.
2.4
Power
supply
A5 in other mobile networks, nodes
in
an ad hoc
network are powered by battery.
So
power conservation
and balancing should be considered in addition to traffic
load balancing and transmission efficiency.
2.5
Key characteristics
of
an
ad
hoc
network include
large number of users, user mobility and the need to
support multimedia communications. Frequently changing
topology makes it challenging foran ad hoc network to
support
QoS.
Service
and
quality
of
service
(QoS)
support
Many routing protocols for ad hoc networks have
been proposed. Generally, they can be categorized into
three types: proactive (label switch), reactive
(on
demand),
and intra-zone proactive with inter-zone reactive
3
Proactive Routing Protocols
Proactive routing protocols require each node to
maintain one or more tables to store up-todate routing
information to every other node in the network.
Examples include:
3.1
Wireless Routing Protocol (WRP)
Wireless Routing Protocol
(WRP)
[Z]
is a loopfree
table-driven algorithm.
In
this protocol, each node in the
network maintains four tables:
Distance table
*
Routing table
0-7803-8193-9/04/$17.00 02004
IEEE
100