06-08-2014, 02:39 PM
Classification of Ad Hoc Routing Protocols
[attachment=66662]
Abstract
Mobile ad hoc networks (MANET) are networks which
routing is based on multi-hop routing from a source to a
destination node or nodes. These networks have quite a
many constrains because of uncertainty of radio interface
and its limitations e.g. in available bandwidth. Also
some terminals have limitations concerning battery
energy in use.
There are numerous applicable protocols for ad hoc
networks, but one confusing problem is the vast number
of separate protocols. Each of these protocols is designed
to perform its task as well as it is possible according to
its design criteria. The protocol to be chosen must cover
all states of a specified network and never is allowed to
consume too much network resources by protocol
overhead traffic.
This seminar paper deals with a classification of ad hoc
routing protocols and also presents some specified
protocols according to that classification. Presented
protocols are selected according to an entity formed by
this paper and related papers to be published by
Networking Laboratory of HUT. The emphasis of this
paper is not to present protocols in detail but to present
main features of wide variety of different protocols and
evaluate their suitability and tradeoffs
Introduction
Ad hoc network is a multi-hop wireless network, which
consists of number of mobile nodes. These nodes
generate traffic to be forwarded to some other nodes or a
group of nodes. Due to a dynamic nature of ad hoc
networks, traditional fixed network routing protocols are
not viable. Based on that reason several proposals for
routing protocols has been presented.
Ad hoc radio networks have various implementation
areas. Some areas to be mentioned are military,
emergency, conferencing and sensor applications. Each
of these application areas has their specific requirements
for routing protocols. For example in military
applications low probability of detection and interception
is a key factor such is routing efficiency during fading
and disturbed radio channel conditions. At sensor
applications low or minimum energy consumption is a
precondition for an autonomous operation. In conference
A Taxonomy for Routing Protocols
Because of multiple and diverse ad hoc protocols there is
an obvious need for a general taxonomy to classify
protocols considered. Traditional classification is to
divide protocols to table-driven and to source-initiated
on-demand driven protocols [1].
Table-driven routing protocols try to maintain consistent,
up-to-date routing information from each node to every
other node. Network nodes maintain one or many tables
for routing information. Nodes respond to network
topology changes by propagating route updates
throughout the network to maintain a consistent network
view.
Source-initiated on-demand protocols create routes only
when these routes are needed. The need is initiated by
the source, as the name suggests. 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. After that there is a route
maintenance procedure to keep up the valid routes and to
remove the invalid routes.
Communication Model
Protocols can be divided according to communications
model to protocols that are designed for multi-channel
or single-channel communications. Multi-channel
protocols are routing protocols generally used in TDMA
or CDMA-based networks. They combine channel
assignment and routing functionality. That kind of
protocol is e.g. Clusterhead Gateway Switched Routing
(CGSR) [4].
Single -channel protocols presume one shared media to
be used. They are generally CSMA/CA-oriented, but
they have a wide diversity in which extend they rely on
specific link-layer behaviors.
Overview of selected Protocols
There are unicast, single channel protocols, which are
uniform or non-uniform. Uniform protocols are divided
to topology-based protocols, in where nodes are aware of
the topology information of all other nodes in the
network or to destination-based protocols, in where
nodes only know the preferred next hop to a destination.
One protocol to belong to that topology-based class is
GSR (Global State Routing) and the other is DSR
(Destination Source Routing). One main difference
between these protocols is the scheduling method. GSR
is a proactive protocol, which will all the time have the
information needed for routing. DSR is on its behalf a
reactive protocol, which will obtain needed information
only on demand.
Multichannel Protocols
The main distinct feature for multichannel protocols is
the ability to support different communications channels.
Some nodes may have access to more than one physical
medium or a node may be allowed to change the channel
during routing operation.
Multichannel protocols may also be divided at the same
way as single channel protocols to different subclasses.
They can be treated as uniform or non-uniform as is the
case with the two protocols presented in here. The two
protocols appearing here is CGSR (Clusterhead Gateway
Switch Routing) protocol and quite an exceptional
protocol called Epidemic. CGSR is a non-uniform
hierarchical protocol, which is based to forming clusters
among nodes and selecting a cluster head to control
routing to outside the cluster area. Epidemic is a uniform
Applicability of different Protocols
Different kind of ad hoc routing protocols are suitable
for different kind of network structures and node
behaviors. When evaluating protocols one needs some
appropriate classification also for the features of
performance metrics.
The critical features for ad hoc networks can be
classified according to Subbaro [19] to following
quantitative and qualitative features. Quantitative
features are:
- Network settling time, which is the time for a
network to reach a stable state and be able to
send its first message reliably.
- Network join time, which is the time for an
entering node or group of nodes to become
integrated into the ad hoc network.
- Network depart time , which is the time
required for the ad hoc network to recognize the
loss of one or more nodes, and reorganize itself
to manage lacking links.
- Network recovery time, which is the time for a
network to recover after a condition that
dictates reorganization of the network.
- Frequency of updates, which is the number of
control packets or overhead bytes inside packets
to be sent in a given time to maintain proper
network operation. This means also same as
overhead.
- Memory required, which is the storage space
required for routing tables and other
management tables.
- Network scalability number, which is the
number of nodes that a network can scale to and
still preserve communications.
Dynamic Networks
Dynamic networks are the main challenge, because we
are able to manage with many large different networks,
as is the case with the Internet. But when we have same
problems in dynamic environments, there is vast number
of trade-offs to consider. If we want the route acquisition
time to be modest we should prefer table-based i.e.
proactive protocols, but when using proactive protocols
with dynamic networks, there is a burden of too many
and too frequent update messages.
With dynamic networks we obviously have to apply
reactive protocols and admit some kind of increase in
route acquisition time and also we have to accept that in
case of route interrupt it will take some time to reestablish
a connection. The use of unidirectional links
comes at stage in that situation. If we have remaining
unidirectional link towards receiving node, it makes no
sense to interrupt the whole connection if we still can use
that route for voice stream to one direction. At the same
time a route acquisition process could be started and a
new route should be taken in use when it is operational
Conclusion
As it can be seen, there is vast number of different kinds
of protocols. Only minority of the presented protocols
will attain a technical or commercial success, one would
forecast. Each of these protocols has some common
goals. Every protocol has the ability of distributed
routing calculations and every protocol try to manage the
consequences caused by mobility of nodes. But the
means are such different as they can be.
The presented taxonomy of routing protocols is a
meaningful attempt to clarify the vast field of ad hoc
routing protocols. It is so because it tries to reveal the
main design and implementation principles behind
protocols. The taxonomy is a little bit complicated and it
is not always an easy task to classify a protocol
according to that taxonomy, but the meaning of
classifying is try to get some rough basis for protocol’s
performance evaluation. It should be assumed that same
kinds of protocols behave quite the same way in
simulations.
When comparing the simulation result of presented
protocols, there is a little difficult situation to reach a
common understanding about the results. This is because
of every simulation has been conducted according to
different premises. One question arises if there should be
a common framework for tests and simulations. That
definition could be a part of e.g. RFC 2501, which
concentrates to routing performance issues and
evaluation of protocols