Int. J. Communications, Network and System Sciences, 2010, 3, 289-293
doi:10.4236/ijcns.2010.33037 blished Online March 2010 (http://www.SciRP.org/journal/ijcns/).
Pu
A Mobile Ad-Hoc Routing Algorithm with Comparative
Study of Earlier Proposed Algorithms
Pawan Kumar Verma, Tarun Gupta, Nitin Rakesh, Nitin Nitin
Department of C SE & IT, Jay pee Uni versi ty of Information Tech nology, Wakna gh at, I ndia
Received December 10, 2009; revised January 12, 2010; accepted Febru a r y 16, 2010
Abstract
A mobile ad-hoc network is an autonomous collection of mobile nodes that communicate over bandwidth
constrained wireless links. Due to nodal mobility, the network topology may change rapidly and unpredicta-
bly over time. The routing protocols meant for wired network cannot be used for mobile ad-hoc network be-
cause of mobility of network. A number of routing protocols like Destination-Sequenced Distance-Vector
(DSDV), Ad-Hoc On-Demand Distance Vector (AODV), Dynamic Source Routing (DSR), and Temporally
Ordered Routing Algorithm have been implemented. The ad-hoc routing protocols can be divided into two
classes; Table-Driven and On-Demand. This paper examines two routing protocols for mobile ad-hoc net-
works—the Destination Sequenced Distance Vector (DSDV), the table-driven protocol and the Ad-Hoc On-
Demand Distance Vector routing (AODV), an on-demand protocol and propose an algorithm that facilitates
efficient routing of the packet and failure recovery mechanism.
Keywords: AODV, DSDV, Relative Performance
1. Introduction and Motivation
Wireless networks are the current field of research as it
provides new advancement to the field of mobile net-
work and reliable data transfer. They provide a mecha-
nism to share the information and services via electronic
medium without any geographical constraints. As the
medium is wireless there is no distance limitations pre-
sent and the network do not need much maintenance as
no physical medium is involved in the actual transmis-
sion. Wireless networks can be categorized
as-infrastructured network and infrastructure less (ad-hoc)
networks. Infrastructured network consists of a network
with fixed and wired gateways. A mobile host searches
for a bridge in the network in its defined communication
radius, if it goes out of the range of the network the
search for new base station starts and the communication
is established. The approach is called as handoff.
In contrast to infrastructure-based networks, in ad-hoc
networks all nodes are mobile and can be connected dy-
namically in an arbitrary manner. All nodes of these
networks behave as routers and take part in discovery
and maintenance of routes to other nodes in the network.
Ad-hoc networks are very useful in emergency search-
and-rescue operations, meetings or conventions in which
persons wish to quickly share information, and data ac-
quisition operations in inhospitable terrain. Routing pro-
tocols for mobile ad-hoc networks can be classified into
two main categories: Proactive or table driven routing
protocols and reactive or on-demand routing protocols.
In proactive protocols, every node maintains the network
topology information in the form of routing tables by
periodically exchanging routing information. They in-
clude the Destination Sequenced.
Distance Vector (DSDV) [1], the Wireless Routing
Protocol (WRP) [2], Source-Tree Adaptive Routing
(STAR) [3] and Cluster-head Gateway Switch Routing
Protocol (CGSR) [4]. On the other hand, reactive proto-
cols obtain routes only on demand, which include the
Dynamic Source Routing (DSR) protocol [5], the Ad-hoc
On-demand Distance Vector (AODV) protocol [6], the
Temporally Ordered Routing Algorithm (TORA) [7],
and the Associati vi t y Based R out i n g (AB R) protocol [8] .
The rest of the paper is organized as follows: Section 2
presents an overview of the two main categories of mo-
bile ad-hoc routing protocols and Section 3 presents a
general comparison of the table-driven and on-demand
routing protocols. Section 4 provides an overview and
general comparison of the routing protocols used in the
study. In Section 5, we propose routing algorithm with
better performance and failure recovery. Finally, Section
6 concludes the paper and describes the future work of

P. K. VERMA ET AL. 290
our paper. Section 7 lists the references used by our re-
search paper.
2. Routing Protocols for Mobile Ad-Hoc
Network
In Routing, protocols for mobile ad-hoc networks can be
classified into two main categories:
 Proactive or ta ble-dri ven ro uting protocol s and
 Reactive or on-demand routing protocols.
2.1. Table-Driven Routing Protocol
In table-driven routing protocols, each node maintains
one or more tables containing routing information to
every other node in the network. All nodes update these
tables to maintain a consistent and up-to-date view of the
network. When the network topology changes the nodes
propagate update messages throughout the network in
order to maintain consistent and up-to-date routing in-
formation about the whole network.
 Dynamic Destination Sequenced Distance Vector
Routing Prot ocol (DSDV)
 The Wireless Routi ng Protocol ( WRP)
 Clusterhead Gateway Switch Routing Protocol (CG-
SR)
 Global State Rout ing
 Fisheye State Routing
 Hierarchical State Routing
 Zone-Based Hierarchical Link St ate R outing Prot ocol
2.2. On Demand Routing Protocols
These protocols take a lazy approach to routing. In con-
trast to table-driven routing protocols not all up-to-date
routes are maintained at every node, instead the routes
are created as and when required. When a source wants
to send to a destination, it invokes the route discovery
mechanisms to find the path to the destination. Th e route
remains valid until the destination is reachable or until
the route is no longer needed.
 Ad-hoc On-demand Distance Vector Routing (AO-
DV)
 Dynamic Sour ce R out ing Protocol (DSR)
 Temporall y Ordered Routing Algorithm (TORA)
 Associativity Based Routing(ARB)
 Cluster B a sed R out i ng Protocol
3. Comparison of Table-Driven and
On-Demand Routing Protocols
The table-driven ad-hoc routing approach is similar to
the connectionless approach of forwarding packets, with
no regard to when and how frequently such routes are
desired. It relies on an underlying routing table update
mechanism that involves the constant propagation of
routing information. This is not the case, however, for
on-demand routing protocols. When a node using an on-
demand protocol desires a route to a new destination, it
will have to wait until such a route can b e discovered . On
the other hand, because routing information is constantly
propagated and maintained in table-driven routing pro-
tocols, a route to every other node in the ad-hoc network
is always available, regardless of whether or not it is
needed. This featu re, although useful for datag ram traffic,
incurs substantial signaling traffic and power consump-
tion. Since both bandwidth and battery power are scarce
resources in mobile computers, this becomes a serious
limitation. Table 1 lists some of the basic differences
between the two categories of mobile ad-hoc routing
protocols.
4. Overview of DSDV and AODV
As each protocol has its own merits and demerits, none
of them can be claimed as absolutely better than others.
Two mobile ad-hoc routing protocols—the Destination
Sequenced Distance Vector (DSDV), the table-driven
protocol and the Ad-Hoc On-Demand Distance Vector
routing (AODV), an On-Demand protocol are selected
for study.
4.1. Destination-Sequenced Distance Vector
(DSDV)
The Destination-Sequenced Distance-Vector (DSDV)
Table 1. Comparison of table-driven and on-demand rout-
ing protocol.
Parameters Table-Driven On-Demand
Route AvailabilityAlways available
irrespective of need Computed when needed
Routing philosophyFlat, except for
CGSR Flat, except for CBRP
Periodic updatesAlways required Not required
Handling mobilityUpdates occur at
regular intervals Use localized route discovery
Control traffic
generated Usually higher th an
on-demand Increases with mobility of active routes
Storage
requirements Higher than
on-demand
Depends on the number
of routes maintained or
needed
Delay Small as routes are
predetermined High as routes are Computed when needed
Scalability Usually up to 100
nodes Usually higher than table driven

P. K. VERMA ET AL. 291
Routing Algorithm is based on the idea of the classical
Bellman-Ford Routing Algorithm with certain improve-
ments. Every mobile station maintains a routing table
that lists all available destinations, the nu mber of hops to
reach the destination and the sequence number assigned
by the destination node. The sequence number is used to
distinguish stale routes from new ones and thus avoid the
formation of loops. The stations periodically transmit
their routing tables to their immediate neighbors. A sta-
tion also transmits its routing table if a significant change
has occurred in its table from the last update sent. There-
fore, the update is both time-driven and event-driven.
The routing table updates can be sent in two ways: a “full
dump” or an incremental update. A full dump sends the
full routing table to the neighbors and could span many
packets whereas in an incremental update only those
entries from the routing table are sent that has a metric
change since the last update and it must fit in a packet. If
there is space in the incremental update packet then those
entries may be included whose sequence number has
changed. When the network is relatively stable, incre-
mental updates are sent to avoid extra traffic and full
dump are relatively infrequent. In a fast-changing net-
work, incremental packets can grow big so full dumps
will be more frequent. Each route update packet, in ad di-
tion to the routing table information, also contains a
unique sequence number assigned by the transmitter. The
route labeled with the highest (i.e. most recent) sequence
number is used. If two routes have the same sequence
number then the route with the best metric (i.e. shortest
route) is used. Based on the history, the stations esti mate
the settling time of routes. The stations delay the trans-
mission of a routing update by settling time to eliminate
those updates that would occur if a better route were
found very soon.
4.2. Ad-Hoc On-Demand Distance Vector
Routing (AODV)
Ad-hoc On-Demand Distance Vector Routing (AODV)
is an improvement on the DSDV algorithm discussed in
previous section. AODV minimizes the number of broa-
dcasts by creating routes on-demand as opposed to
DSDV that maintains the list of all the routes. To find a
path to the destination, the source broadcasts a route re-
quest packet. The neighbors in turn broadcast the packet
to their neighbors until it reaches an intermediate node
that has recent route information about the destination or
until it reaches the destination (Figure 1(a)). A node
discards a route request packet that it has already seen.
The route request packet uses sequence numbers to en-
sure that the routes are loop free and to make sure that if
the intermediate nodes reply to route requests, they reply
with the latest information on ly.
When a node forwards a route request packet to its
neighbors, it also records in its tables the node from
which the first copy of the request came. This informa-
tion is used to construct the reverse path for the route
reply packet. AODV uses only symmetric links because
the route reply packet follows the reverse path of route
request packet. As the route reply packet traverses back
to the source (Figure 1(b)), the nodes along the path
enter the forward route into their tables.
If the source moves then it can reinitiate route discov-
ery to the destination. If one of the intermediate nodes
moves then they moved nodes neighbor realizes the link
failure and sends a link failure notification to its up-
stream neighbors and so on till it reaches the source upon
which the source can reinitiate route discovery if needed.
Source
Destination
(a)
Source
Destination
(b)
Figure 1. (a) Propagation of Route Request Packet (RREQ),
(b) Path taken by the Route Reply (RREP) Packet.
Table 2. AODV v/s DSDV.
Parameter DSDV AODV
Routing structureFlat Flat
Frequency of
updates Periodic and as
needed As required
Critical nodes No No
Loop-free Yes Yes
Multicasting
capability No Yes
Routing metric Shortest path Fastest and shortest path
Utilizes sequence no.Yes Yes
Time complexityO(Diameter of
network) O( 2* Di ameter of network)
Communication
Complexity O(Number of nodes
in n/w) O(Number of nodes in n/w)
Advantages Small delays Adaptable to highly
dynamic topology
Disadvantage Large overhead Large delays
C opyright © 2010 SciRes. IJCNS

P. K. VERMA ET AL. 292
5. Proposed Routing Algorithm
The proposed algorithm involves the computation of
efficiency of the given route based on the network his-
torical results and the maintenance of previous route in-
formation from source to the current node to handle any
failure recovery during the transmission. Other than this
the information of the various nodes connected and their
distance from the destination is computed and updated
after every cycle. Every node in the routing path is as-
signed a unique sequence number, which is checked after
every movement to prevent any loops during the trans-
mission procedure. At every node, a scheduling algo-
rithm is applied based on the priorities of the data pack-
ets receiving the nodes. Information contained/processed
at every node-
 Sequence Number: A unique number assigned to
every node for its identification in the network. The
unique ID is also used to prevent any l oops i n the net wor k.
The loop in the network are prevented by checking the
current node sequence number with the previous node
sequence number, if found smaller the routing is moving
in a backward direction or will suffer from loop. The uni-
que number is assigned to every node from source to des-
tination.
 Neighbor Node Table: The table is maintained at
every node that contains the information about every
neighbor node in the network with respect to the current
node. The search technique searches for the entire con-
nected node in the network and store/update the neighbor
node table accordingly. The sequence number of every
neighbor node is stored in the table. The distance of every
neighbor node from the destination is computed and
stored in the table to facilitate shortest path search.
 Path Information: The path information contains the
path trace from the souse node to the current node i.e. the
actual routing map with the sequence number stored in
the path information. E.g. suppose a route start from a
source node with sequence number 1 and move through 3,
6, 7 to the node with sequence number 9 then the path
information for the node number becomes 1367
9. This path trace helps to know the whole prorogated
path from source to destination, which facilitates back-
tracking. The backtracking is needed when any of the
network route fails, in this case the path information can
be used to backtrack i.e. moving back in the network and
selecting any other opt i mal path.
 Efficiency Factor (EF): This efficiency factor is
computed based on the historical records. The network
efficiency of the route is monitored every time it sends a
data packet through the node. If the route transmits the
data packet efficiently, the value of EF increases and vice
versa. This factor helps to select the most optimal path as
the node for which the EF will be high will result in reli-
able and speedy data transfer.
 Data Packet Buffer: At every node, a buffer is
maintained to store the receiving data packets to be
transmitted to the destination node. The storing of data
packet in the node buffer prevents any packet loss and
reduces the network traffic.
 Scheduling of Data Packet: A node buffer may re-
ceive more than one data packet for routing it to the des-
tination. The selection of the data packet is made in ac-
cordance with the priority of the data packets received
and the packets are arranged in order of their priorities in
the buffer.
When the data packet progress from source to destina-
tion the information maintained is viewed. The n ext node
in the network is sele ct ed on the basis-
 Availability of path: The next node selected must be
free to transmit the packet or the buffer of the node
should be empty. All the nodes connected are viewed for
the buffer position and the one, which is vacant or less
busy, is selected.
 Distance from Destination: The Neighbor Node Ta-
ble available at each node is examined for the node with
minimum distance from the destination. The node with
minimum distance is selected.
 Efficiency Factor: The efficiency factor computed at
every node that provides the information about the net-
work reliability is looked upon and the node with highest
efficiency factor EF is selected.
Based on the commutative result of all the above-de-
scribed parameters the packet is transmitted to the next
node with the condition that the current distance should
be less than the distance from the next node. If in case
the network path fails the packet is transmitted back to
the previous node in the path information and any other
path is selected. If there are multiple data packets at any
node the scheduling of data packets is done to prevent
any collision and data loss. The scheduling is done ac-
cording to the priority of the data packets. The proposed
algorithm provides an efficient way to transmit data over
the wireless network reliably and with failure recovery
mechanism.
Table 3 prescribed in the below gives the sequential
flow of the routing steps. This algorithm described in-
volves reliable data packet transfer through the best pos-
sible path and minimum time latency.
6. Conclusions and Future Works
Each earlier proposed protocol has their own merits and
demerits, none of them can be claimed as absolutely bet-
ter than others can. This paper compared the two ad-hoc
routing protocols: AODV an on-demand routing protocol,
and DSDV a table-driven protocol and proposed a better
routing algorithm with historical monitoring of the net-
work and failure recovery to facilitate reliable transmis-
sion of data packet over the wireless network.

P. K. VERMA ET AL. 293
Table 3. Proposed algorithm.
Steps Task Performed
1
- Every node assigned a unique sequence ID;
- Neighbour Node Table containing distance from
destination;
- Path Information is updated;
- Efficiency Factor (E.F.) computed based on
historical network Efficiency.
2 The data packed to be sent is selected based on the
Scheduling algorithm based on the prioritization.
3
After the packet selection the network is computed on
the basis of-
- Neighbour node table
- Each neighbour distance from destination.
- Efficiency Factor(E.F.)
The above factors are examined and the next node is
selected accordingly.
4 If the network route is efficient the algorithm proceed in
forward direction, else the Path Information is used to
reverse the path.
5 If data packet reaches Destination Node then algorithm
terminates else continue, from step 3.
The future aspect of the system involves the im-
provement of the scheduling algorithm that facilitates
more efficient scheduling of data packets using a data
buffer at every node. This will prevent any jam in the
network and improve network traffic. The efficiency
factor can be computed more precisely to have excellent
results during the packet transmission.
7. References
[1] C. E. Perkins and P. Bhagwat, “Highly dynamic destina-
tion-sequenced distance-vector routing (DSDV) for mo-
bile computers,” In Proceedings of ACM SIGCOMM, pp.
234–244, August 1994.
[2] S. Murhty and J. J. Garcia-Luna-Aceves, “An efficient
routing protocol for wireless networks,” ACM Mobile
Networks and Applications Journal, Special Issue on
Routing in Mobile Communication Networks, Vol. 1, No.
2, pp. 183–197, October 1996.
[3] J. J. Garcia-Luna-Aceves and M. Spohn, “Source-tree
routing in wireless networks,” In Proceedings of IEEE
ICNP, pp. 273–282, October 1999.
[4] C. C. Chiang, H. K. Wu, W. Liu, and M. Gerla, “Routing
in clustered multi-hop mobile wireless networks with
fading channel,” In Proceedings of IEEE SICON, pp.
197–211, April, 1997.
[5] D. B. Johnson and D. A. Malta, “Dynamic source routing
in ad hoc wireless networks,” Mobile Computing, Klu-
wer Academic Publishers, Vol. 353, pp. 153–181, 1996.
[6] T.-W. Chen, J. T. Tsai, and M. Gerla, “QoS routing per-
formance in multihop, multimedia, wireless networks,”
IEEE 6th ICUPC Record, pp. 557–561, October 1997.
[7] V. D. Park and M. S. Corson, “A highly adaptive distrib-
uted routing algorithm for mobile wireless networks,” In
Proceedings of IEEE INFOCOM 1997, pp. 1405–1413,
April 1997.
[8] C. K. Toh, “Associativity-based routing for ad hoc mo-
bile networks,” Wireless Personal Communications, Vol.
4, No. 2, pp. 1–36, March 1997.
[9] M. G. Kaosar, M. Hafiz, M. A. Tarek, R. Shel tami, a nd A.
S. H. Mahmoud, “Simulation-based comparative study of
on demand routing protocols for MANET,” International
Conference on Wireless Networking and Mobile Computing
(ICWNMC’05), Chennai, India, Vol. 1, pp. 201–206, 28–
30 December 2005.
[10] K. Takanashi, T. Kato, S. Itoh, A. Sugata, F. Kojima, and
M. Fujise, “Combining AODV ad hoc routing and con-
ventional IP routing over wireless and wired links,” Pro-
ceedings of Communication Systems and Networks, 2005.
[11] Technical report. http://www.cs.umu.se/education/exami-
na/Rapporter/KrishnaGorantala.pdf.
[12] Technical report. http://en.wikipedia.org/wiki/DSDV.
[13] T. Yang, M. Ikeda, G. De Marco, and L. Barolli, “Per-
formance behavior of AODV, DSR and DSDV protocols
for different radio models in ad-hoc sensor networks,”
2007 International Conference on Paralled Processing
Workshops, 10–14 September 2007.
[14] E. M. Royer and C. K. Toh, “A review of current routing
protocols for ad hoc mobile wireless networks,” IEEE
Personal Communications Magazine, pp. 46–55, April
1999.
[15] C. E. Perkins and E. M. Royer, “Ad hoc on-demand dis-
tance vector routing,” Proceedings of IEEE Workshop on
Mobile Computing Systems and Applications, pp. 90–
100, February 1999.
[16] Technical report. http://en.wikipedia.org/wiki/AODV.
[17] G. D. Nguyen and S. Kompella “Optimization of trans-
mission schedules in captured-based wireless networks”.
[18] Z. Zhang, S. Moola, and E. K. P. Chong, “Approximate
stochastic dynamic programming for opportunistic fair
scheduling in wireless networks,” Proceedings of the 47th
IEEE Conference on Decision and Control Cancun,
Mexico, 9–11 December 2008.
[19] G. Forman and J. Zahorjan, “The challenges of mobile
computing,” IEEE computer, Vol. 27, No. 4, April 2001.