Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol.

1, Issue 1, pp.022-031

PERFORMANCE EVALUATION & COMPARISON OF ROUTING PROTOCOLS FOR AD HOC WIRELESS NETWORKS
Sohan Garg1, Dolly Tyagi2
1

Department of MCA, RKGIT, Ghaziabad U.P.,

2

Research Scholar Singhania University

Abstract
The recent advances and the convergence of micro electro-mechanical systems technology, integrated circuit technologies, microprocessor hardware and nano technology, wireless communications, Ad-hoc networking routing protocols, distributed signal processing, and embedded systems have made the concept of Wireless Networks. Wireless network nodes are limited with respect to energy supply, restricted computational capacity and communication bandwidth. Most of the attention, however, has been given to the routing protocols since they might differ depending on the application and network architecture. To prolong the lifetime of the wireless network nodes, designing efficient routing protocols is critical. Even though wireless networks are primarily designed for monitoring and reporting events, since they are application dependent, a single routing protocol cannot be efficient for ad hoc wireless networks across all applications. In this chapter, we analyze the design issues of wireless networks and present a classification and comparison of routing protocols. This comparison reveals the important features that need to be taken into consideration while designing and evaluating new routing protocols for ad hoc wireless networks. Key words: AD HOC wireless network, reactive and proactive routing protocols.

Comparison between Table Driven Routing Protocols :

As we have discussed that DSDV routing protocol is modification of BF routing protocol. In DSDV there are no routing loops and this is a simple routing protocol. DSDV provides routing protocol in

comparison of BF

only a single path from

any source to the destination and selects the number of hops of the destination. one message is

shortest path which is based on the of update messages and for

DSDV provides two types

smaller than other.

The smaller update message can be used

22

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 incremental updates so that the entire routing table needs not br inefficient transmitted of for the

every change in the network topology. DSDV is requirement of the periodic the network topology.

because

update transmissions regardless of the number of changes in

In CGSR, DSDV is used as the underlying routing protocol. Routing in with table is the help of cluster heads and gateways or we can

CGSR is done

say that a cluster head

necessary in addition to the

routing table. One advantage of the CGSR is high in comparison to other routing

that the performance of the protocols is protocols.

As we know that WRP is different routing protocol from the other routing protocols. WRP each node will maintain four routing tables but there is a disadvantage

In of

WRP that when

the number of nodes in the network is more then this can lead the protocol uses the hello packet hello will packets consume for the

memory requirements. WRP routing transmission from a given node then this

bandwidth. Although, WRP uses the path finding routing advantage over creating temporary

algorithm and WRP has an problem of

other path finding algorithms that it avoids the

routing loops. The complete comparison between table driven

routing algorithms have been shown in the table 1.

DSDV PARAMETERS Loop Free Uses of Hello Messages Table required QoS Support Multiple path Multicast capability Security Sequence No used 2 No No No No Yes Yes Yes

CGSR

WRP

Yes No

Yes Yes

2 No No No No Yes

4 No Yes No No Yes

23

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 Routing Philosophy Cluster Head & Gateway Distributed Yes Yes Yes Flat No Hierarchical Yes Flat No

Table 1: Comparison between table driven routing protocols

Comparison between On-Demand Routing Protocols:

AODV uses a route discovery procedure similar to DSR; there are two differences between the two that the overhead of DSR is most important potentially larger than

that of AODV because each DSR packet must in AODV are larger packets need only

carry full routing information where as

destination address. Similarly, the route replies in DSR as

because they contain the address of every node along the route where

AODV route replies carry only the destination IP address and

sequence number. This is next hop

the reason to AODV due to remember full nodes as opposed to only information in AODV .The none of the other main

advantage of AODV is that it supports multicast and considered currently incorporate multicast

algorithms On the other

communication. and

hand AODV requires symmetric links between nodes asymmetric links, but DSR is good in this links and DSR can utilize

hence can not utilize routes with

aspect because it does not require the use of such

asymmetric links when symmetric links are not available. The advantage of DSR over other On demand routing protocols is that it use of periodic routing advertisements but they save the consumption and DSR has a multiple does not make

bandwidth and reduce the power

routes from source to destination in their cache.

Hence when a link on a destination, but

route is broken, then it can use another route to reach at

there are no additional routes to the destination in the source nodes

cache, route discovery must be reinitiated as in AODV. TORA is also a popular on-demand routing protocol which is best suited for the network which contain a lot of nodes. Like DSR, TORA also Route reconstruction is not necessary supports to the multiple routes.

until all known routes to a destination are

24

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 deemed invalid, and hence bandwidth can potentially be conserved because of the buildings. TORA also supports to the multicast. does not incorporate multicast into its basic as in

necessity for fewer route re Although unlike AODV, TORA

operation. Furthermore, In TORA the route rebuilding may not occur as quickly other algorithms due to the potential for oscillations during this period. ABR is also a popular On-demand routing protocol which uses the connection packet forwarding approach. The main advantage

oriented

of ABR is that like the other routing

protocols it is guaranteed to be free of packet duplicates. The reason of this is that only the best route is marked as valid while all other routes are marked as invalid. As we ABR uses the beaconing and this beaconing requirement may power consumption. ABR does not utilize the route cache. As we have discussed about ABR that the path selected by ABR are not shortest in hop count so the new algorithm SSR utilizes a routes based on the signal strength and drawback of SSR routing can not new necessarily of selecting result in know that additional

technique

location stability of nodes along the path. The

protocol is that unlike in AODV and DSR intermediate nodes

reply to route requests sent forward a destination. In DSR when a ink failure

occurs along a path, the route discovery algorithm must be invoked from the source to find a new path to the destination. No attempt is made to use partial route recovery that is to

allow intermediate nodes to attempt to rebuild the route themselves. So we can say that SSR do not specify intermediate node rebuilding. Thus it remains to be seen whether

intermediate node route rebuilding is more optimal that source node route rebuilding.

Parameters
Loop Free QoS Support Multiple path Multicast capability Security

AODV
Yes No No Yes No

DSR
Yes No Yes No No

TORA
Yes No Yes No No

ABR
Yes No No No No

SSR
Yes No No No No

25

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031
Routes are maintained in Route table Route Cache oute table Route table Route table

Routing Philosophy

Flat

Flat

Flat

Flat

Flat

Cluster Head & Gateway

No

No

No

No

No

Use of Beaconing

No

No

No

Yes

Yes

Sequence No. Used Distributed

Yes Yes

Yes Yes

Yes Yes

Yes Yes

Yes Yes

Table 2 : Comparison between On-demand routing protocols

Reactive Vs Proactive Ad hoc Routing Protocols:

Most routing protocols in mobile ad hoc networks derive from distance state algorithms. In distance vector routing, each router distance from itself to all possible table information to vector or link maintains a table containing the

destinations. Each router periodically transmits this

all its neighbour routers, and updates its own table by using the values obtained from its

received from its neighbours. Based on the comparison of the distances

neighbours for each destination, a router can decide the next hop as the shortest path from itself to the specified destination. When each router has a packet to send to some

destination, it simply forwards the packet to the decided next hop router. When the routing table is frequently updated, the algorithm speeds up the convergence to the correct path. However, the overhead in CPU time and network bandwidth for flooding routing

updates also increases. Perkins and Bhagwat [46] devised a Destination-Sequenced Distance Vector (DSDV) protocol based on the classical Bellman-Ford routing algorithm to mobile ad hoc networks. DSDV also has the feature of the to apply

distance-vector protocol

in which each node holds a routing table including the next-hop information for each possible destination. Each protocol entry has a sequence number. If a new entry is obtained, the

prefers to select the entry having the largest sequence number. If their lowest

sequence number is the same, the protocol selects the metric with the

26

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 value. Each node transmits advertisement packets using [46]. A study of performance evaluation virtually all data packets increasing sequence numbers

on DSDV shows that DSDV is able to deliver

when each node moves with relatively low speed. However,

when the mobility of each node increases, the speed at which the system converges to the correct path decreases [5]. While DSDV is a proactive protocol that always tries to maintain the information regarding network topology, Ad hoc On-demand (AODV) [55] is a reactive protocol to perform Route route needs to be found. Thus, AODV correct Vector

Distance

Discovery only when a new

does not maintain any routing information nor

transmit any periodic advertisement packets for exchanging routing tables. i.e., only when two nodes need to communicate with each other, will they forward maintain connectivity between the two nodes. routing packets to

Usually, when there is a need for

communication between two nodes, each mobile node transmits a local broadcast packet known as a hello message. Routing tables of the nodes within the neighborhood are and the support

organized for the optimization of response time to local movements of rapid response time for requests to establish a new Dynamic Source Routing (DSR)

route. AODV is similar with the

protocol, which will be explained with more details in

the following sections, in terms of the nature of on-demand. However, while DSR is based on source routing, AODV is dependent upon dynamically establishing route table entries at intermediate nodes. The proactive ad hoc routing protocols approach is similar to the of forwarding packets, with no regard to when desired. It relies on an underlying connectionless approach

and how frequently such routes are

routing table update mechanism that involves the

constant propagation of routing information. This is not the case, however, for reactive routing protocols. When a node using a reactive protocol desires a route to a new destination, it will have to wait until such a route can be discovered. On other hand, because routing information is constantly propagated proactive routing protocols, a route to every other available, regardless of whether or datagram traffic, incurs and maintained the in

node in the ad hoc network is always

not it is needed. This feature, although useful for

substantial signaling traffic and power consumption. Since

27

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 both bandwidth and battery power are scarce resources in mobile computers, becomes a serious limitation. Another consideration is whether a flat or hierarchical addressing scheme should be used. All of the protocols considered here, except for CGSR, use a flat addressing scheme. protocols by this

The numerical comparison of reactive and proactive ad hoc routing

assuming five routing protocols which are DSDV, AODV, DSR, TORA, ABR has been shown in the following table 3, and here 1 is for the best up to 5 is for the worst and the comparison of the characteristics of source-initiated on demand ad hoc routing protocols and proactive protocols has been shown in the table 4:

METRICS Scalability Delay Routing Overhead Packet Drop Route Acquisition time Throughput Adaptability to dynamic environment Bandwidth conservation Energy Conservation Optimal Path

DSDV 5 1 5 5 1 3 5 5 5 1

AODV 2 4 2 1 2 1 2 1 2 1

DSR 3 2 1 2 4 2 4 2 1 1

TORA 1 5 3 3 3 4 1 2 3 3

ABR 1 3 2 1 3 1 1 2 3 2

Table 3: Numerical comparison of the reactive and proactive routing protocols

28

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031
PERFORMANCE PARAMETERS
Time Complexity (Route Construction) Time Complexity (post failure) Communication Complexity (Initialization) Communication Complexity (post failure) Routing Philosophy Loop-free Multicast Capability Beaconing Requirements Multiple Route possibilities Routes maintained in Utilizes route cache/table expiration timers

AODV
O(2d) O(2d) O(2N) O(2N) Flat Yes Yes No No Route Table Yes

DSR
O(2d) O(2d) O(2N) O(2N) Flat Yes No No Yes Route Cache No

TORA
O(2d) O(2d) O(2N) O(2x) Flat Yes No** No Yes Route Table No

ABR
O(d + z) O(/ + d) O(N + y) O(x + y) Flat Yes No Yes No Route Table No

DSDV
O(d) O(d) O(x=N) O(x=N) Flat Yes No No No Route Table Yes

Erase route; notify Erase route; notify reversal; route Link Localized broadcast Erase route; notify
Route reconfiguration methodology

source Freshest & Shortest

Routing metric

source Shortest path

repair

query

source

path

Associativity & Shortest Shortest path Shortest path path

Table 4: Characteristics comparison of the reactive and proactive routing protocols Where N= Number of nodes in the network, d= Network Diameter h= Height of the routing tree, x= No. of nodes affected by a topological l=Diameter of the affected network segment y= Total number of nodes forming the directed path where the REPLY z= Diameter of the directed path where the REPLY packet transits * packet transits Cache hit change

References:
1. A. James Freebersyser, B. Leiner, A DoD perspective on mobile ad hoc networks, in: Charles E. Perkin (Ed.), Ad hoc Networking, Addison Wesley Reading, May 2001, pp.29-51.

29

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 2. J. Macker and S. Corson, Mobile Ad hoc Networks (MANET), IETF WG Charter.,http://www.ietf.org/html.charters/manetCarter.html,1997. 3. IEEE Computer Society LAN MAN Standards Committee,Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, IEEE Std. 802.11, 1997, pp. 11-97. 4. M.S. Corson, J.P. Maker, J.H. Ernicione Internet based mobile ad hoc networking, IEEE Internet Computing, 3 (4), 1999, pp. 63-70. 5. E. M. Royer and C. K. Toh, A review of current routing protocols for ad hoc mobile wireless networks, IEEE Personal Communications Magazine, April 1999, pp. 46-55. 6. I. Chlamtac and A. Lerner, Link allocation in mobile radio networks with noisy channel, In IEEE INFOCOM, Bar Harbour. www.openu.ac.il/Personal_sites/anat-lerner.html, FL, April 1986. 7. I. Chlamtac and A. Lerner, Fair algorithms for maximal link activiation in multi-hop radio networks, IEEE Transactions on Communications COM-3, Issue-7, Vol. 35, 1987, pp. 739746. 8. A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou. A Multi radio unification protocol for IEEE 802.11 wireless networks. networks, (BroadNets), 2004. 9. C. Perkins, Ad hoc Networking, Chapter 4, Addison-Wesley, December 2000. 10. C. Siva Ram Murthy and B.S. Manoj, Ad hoc Wireless Networks Architecture and Protocols, Prentice Hall, 2004. 11. M.S. Corson, S. Batsel and J. Macker, Architecture consideration for mobile mesh networking, Conference Proceeding, IEEE, Vol.1, 12. 21-24 Oct. 1996, pp. 225-229. In IEEE International conference on broadband

P. Merlin and A. Segall, A fail safe distributed routing protocol, IEEE

Transactions on Communications, COM-27 (9), Sep. 1979, pp. 1280-1287. 13. J.M. Jaffe and P.H. Moss, A responsive distributed routing algorithm for computer

networks, IEEE Transactions on Communications, COM-30 (7): July 1982, pp. 1758-1762. 14. J.J. Garcia Aceves,Distributed routing algorithm using internidal coordination, Proc. IEEE INFOCOM, New Orleans, LA, 1998, pp.85-96. 15. E.M. Gafni and D. P. Bertsekas, Distributed algorithm for generating loop-free routes in networks with frequently changing topology,

IEEE Transactions on Communications, Vol. Com-29, no. 1, Jan. 1981, pp. 11-18.

30

Dr. Sohan Garg, Dolly Tyagi / International Journal of Engineering Research and Applications (IJERA) www.ijera.com Vol. 1, Issue 1, pp.022-031 16. M. S. Corson and A. Ephremides, A distributed routing algorithm for mobile wireless networks, ACM Journal for Wireless Networks, Feb. 1995, pp. 61-81. 17 . C.E. Perkins and P. Bhagwat, Highly dynamic destination sequenced distance

vector routing (DSDV) for mobile computers, ACM SIGCOMM, Vol.24, no.4, Oct.1994, pp. 234-244. 18. S. Murthy and J.J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, ACM Mobile Networks and App. J., Special issue on Routing in Mobile communication Networks, Oct. 1996, pp. 183-187. 19. J.M. McQuillan, I. Richer, E. Rosen, The new routing algorithm for ARPANET, IEEE Transaction of Communication Vol. 28, Issue 5, May 1980, pp. 711-719. 20. D.B. Johnson, D. A. Maltz and Y.C. Hu., The dynamic source routing protocol for mobile ad hoc networks (DSR), IETF Mobile Ad hoc Networks Working Group, Internet Draft, 16 Apr. 2003. 21. C. Bettstetter and C. Wagner. (March 2002), The Spatial Node Distribution of the RandomWaypoint Mobility Model. In Proceedings of the German Workshop on Mobile Ad hoc Networks (WMAN), pages 4158, Ulm, Germany. 22.C. Bettstetter, (2001), Mobility modeling in wireless networks: Categorization, smooth movement, and border effects, ACM Mob. Comput. Commun. Rev., vol. 5, no. 3, pp. 5566. 23. C. Bettstetter, (Sept. 2001),Smooth is better than sharp: a random mobility model for simulation of wireless networks, in Proc. 4th ACM Int. Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM), Rome, pp. 1927. 24. C. Bettstetter, G. Resta, and P. Santi, (2003), The node distribution of the random waypoint mobility model for wireless ad hoc networks, IEEE Trans. Mobile Computing, vol. 2, no. 3, pp. 257269 25.C. Bettstetter, H. Hartenstein, and X. Perez-Costa. (September 2002), Stochastic Properties of the Random Waypoint Mobility Model: Epoch Length, Direction Distribution and Cell Change Rate. In Proceedings of the ACM International Workshop on Modeling, Analysis, and Simulation of Wireless and Mobile Systems (MSWIM), pages 714, Atlanta, GA. 26.C. Bettstetter. (July 2001), Smooth is Better than Sharp: A Random Mobility Model for Simulation of Wireless Networks. In Proceedings of the ACM International Workshop.

31