01-02-2013, 11:06 AM
A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks
A Review of Current Routing.pdf (Size: 109.99 KB / Downloads: 15)
Abstract
An ad hoc mobile network is a collection of mobile nodes that are dynamically and arbitrarily located in such a manner that the interconnections
between nodes are capable of changing on a continual basis. In order to facilitate communication within the network, a routing protocol is used
to discover routes between nodes. The primary goal of such an ad hoc network routing protocol is correct and efficient route establishment
between a pair of nodes so that messages may be delivered in a timely manner. Route construction should be done with a minimum of overhead
and bandwidth consumption. This article examines routing protocols for ad hoc networks and evaluates these protocols based on a given set of
parameters. The article provides an overview of eight different protocols by presenting their characteristics and functionality, and then provides a
comparison and discussion of their respective merits and drawbacks.
INTRODUCTION
The second type of mobile wireless network is the infrastructureless
mobile network, commonly known as an ad hoc
network. Infrastructureless networks have no fixed routers; all
nodes are capable of movement and can be connected dynamically
in an arbitrary manner. Nodes of these networks function
as routers which discover and maintain routes to other nodes
in the network. Example applications of ad hoc networks are
emergency search-and-rescue operations, meetings or conventions
in which persons wish to quickly share information, and
data acquisition operations in inhospitable terrain.
This article examines routing protocols designed for these
ad hoc networks by first describing the operation of each of
the protocols and then comparing their various characteristics.
The remainder of the article is organized as follows.
The next section presents a discussion of two subdivisions of
ad hoc routing protocols. Another section discusses current
table-driven protocols, while a later section describes those
protocols which are classified as on-demand. The article
then presents qualitative comparisons of table-driven protocols,
followed by demand-driven protocols, and finally a general
comparison of table-driven and on-demand protocols.
Applications and challenges facing ad hoc mobile wireless
networks are discussed; and finally, the last section concludes
the article.
Existing Ad Hoc Routing Protocols
Since the advent of Defense Advanced Research Projects
Agency (DARPA) packet radio networks in the early 1970s
[1], numerous protocols have been developed for ad hoc
mobile networks. Such protocols must deal with the typical
limitations of these networks, which include high power
consumption, low bandwidth, and high error rates. As
shown in Fig. 1, these routing protocols may generally be
categorized as:
• Table-driven
• Source-initiated (demand-driven)
Solid lines in this figure represent direct descendants, while
dotted lines depict logical descendants. Despite being designed
for the same type of underlying network, the characteristics of
each of these protocols are quite distinct. The following sections
describe the protocols and categorize them according to
their characteristics.
Table-Driven Routing Protocols
Table-driven routing protocols attempt to maintain consistent,
up-to-date routing information from each node to every other
node in the network. These protocols require each node to
maintain one or more tables to store routing information, and
they respond to changes in network topology by propagating
updates throughout the network in order to maintain a consistent
network view. The areas in which they differ are the
number of necessary routing-related tables and the methods
by which changes in network structure are broadcast. The following
sections discuss some of the existing table-driven ad
hoc routing protocols.
Source-Initiated On-Demand Routing
A different approach from table-driven routing is source-initiated
on-demand routing. This type of routing creates routes
only when desired by the source node. When a node requires
a route to a destination, it initiates a route discovery process
within the network. This process is completed once a route is
found or all possible route permutations have been examined.
Once a route has been established, it is maintained by a route
maintenance procedure until either the destination becomes
inaccessible along every path from the source or until the
route is no longer desired.
Temporally Ordered Routing Algorithm
The Temporally
Ordered Routing Algorithm (TORA) is a highly adaptive
loop-free distributed routing algorithm based on the concept
of link reversal [10]. TORA is proposed to operate in a highly
dynamic mobile networking environment. It is source-initiated
and provides multiple routes for any desired
source/destination pair. The key design concept of TORA is
the localization of control messages to a very small set of
nodes near the occurrence of a topological change. To
accomplish this, nodes need to maintain routing information
about adjacent (one-hop) nodes. The protocol performs three
basic functions:
• Route creation
• Route maintenance
• Route erasure
During the route creation and maintenance phases,
nodes use a “height” metric to establish a directed acyclic
graph (DAG) rooted at the destination. Thereafter, links
are assigned a direction (upstream or downstream) based
on the relative height metric of neighboring nodes, as
shown in Fig. 5a. This process of establishing a DAG is
similar to the query/reply process proposed in Lightweight
Mobile Routing (LMR) [11]. In times of node mobility the
DAG route is broken, and route maintenance is necessary
to reestablish a DAG rooted at the same destination.
Comparisons
The following sections provide comparisons of the previously
described routing algorithms. The next section compares
table-driven protocols, and another section compares ondemand
protocols. A later section presents a discussion of
the two classes of algorithms. In Tables 1 and 2, time complexity
is defined as the number of steps needed to perform a
protocol operation, and communication complexity is the
number of messages needed to perform a protocol operation
[11, 14]. Also, the values for these metrics represent worstcase
behavior.
Table-Driven Protocols
The discussion here is based on Table 1. As stated earlier,
DSDV routing is essentially a modification of the basic Bellman-
Ford routing algorithm. The modifications include the
guarantee of loop-free routes and a simple route update
protocol. While only providing one path to any given destination,
DSDV selects the shortest path based on the number
of hops to the destination. DSDV provides two types of
update messages, one of which is significantly smaller than
the other. The smaller update message can be used for
incremental updates so that the entire routing table need
not be transmitted for every change in network topology.
However, DSDV is inefficient because of the requirement
of periodic update transmissions, regardless of the number
of changes in the network topology.
Conclusion
In this article we provide descriptions of several routing
schemes proposed for ad hoc mobile networks. We also
provide a classification of these schemes according to the
routing strategy (i.e., table-driven and on-demand). We
have presented a comparison of these two categories of
routing protocols, highlighting their features, differences,
and characteristics. Finally, we have identified possible
applications and challenges facing ad hoc mobile wireless
networks. While it is not clear that any particular algorithm
or class of algorithm is the best for all scenarios, each protocol
has definite advantages and disadvantages, and is well
suited for certain situations.