A Performance Analysis Of Routing Protocols In Mobile Ad-Hoc Networks

A Performance Analysis Of Routing Protocols In Mobile Ad-Hoc Networks

Manu Srivastava Parul Yadav

Department of Computer Science & Engineering Department of Computer Science & Engineering ASET, AMITY University ASET, AMITY University

Lucknow, INDIA Lucknow, INDIA

ABSTRACT

Mobile Ad hoc Networks (MANET) constitutes a group of wireless mobile nodes that transmit information without any centralized control. MANETs are infrastructure-less and are dynamic in nature that is why; they require peremptorily new set of networking approach to put through to provide efficacious and successful end-to-end communication. Therefore, an intelligent routing approach is needed in MANETs for changing network conditions such as the size of network and partitioning of network. Due to this Routing is observed as the most interesting research area in MANET. A number of different routing protocols like DSDV, AODV, DSR, ZRP etc. are developed for MANETs, and all the time when a new protocol is proposed, it attempts to provide better route establishment. Also, it is necessary for the routing protocols to ensure the quality of services to applications by giving the correct route from any source to destination within time. Therefore, it is difficult to ascertain definitely that which protocol may work best under a number of different network scenarios, such as increasing node density and traffic. This paper provides an overview and performance analysis of a wide range of routing protocols proposed to see which protocols may perform comparatively better in large networks.

Keywords

MANNET, Routing, Protocol

1. INTRODUCTION

   A Mobile Ad Hoc Network (MANET) is a collection of wireless mobile nodes constituting an

   impermanent/unstable network which has no fixed infrastructure where all the nodes configure themselves. In MANETs, changes in network topology may dynamically occur in an unpredictable manner since nodes have liberty to move anywhere arbitrarily. Routing is an important part of MANETs as it gives the better selection of paths. Thus they require efficient routing protocols for providing better communication. For any data communication packets are transmitted in store and forward manner from a source to destination with the help of intermediate nodes. Figure 1 shows the infrastructure-less mobile ad-hoc network.

   Figure 1: Infrastructure-less or Mobile Ad-hoc Network

   Data transmission in MANETs can be any day to day application such as electronic mail or any file transfer. Some other applications of MANETs include Tactical Networks such as Military communication and operations,

   Sensor Networks for Home Appliances, Emergency Services such as search and rescue operations as well as disaster recovery, Entertainment like Multi-user games, Home and Enterprise Networking such as Home/Office wireless networking (WLAN) etc.

   As MANETs provide a wide range of application, they are also having some challenges like Multicast Routing, Unicast Routing, Power-aware routing, Location-aided routing, Mobile agent based Routing, Quality of Service support, Dynamic Network Topology, Network Overhead, Scalability and Speed. Also these key challenges faced at different layers of MANETs as shown in figure 2.

   Application Layer

   Transport Layer

   Network Layer

   Physical/Link Layer

   Security

   QoS

   Routing

   Power Control

   Figure 2: Challenges of MANETs

   An emphasis in this paper is on the performance analysis of a number of routing protocols including DSDV, CGSR, WRP, AODV, DSR, CBRP, TORA, ABR, SSR, ZRP and

   ZHLS based on the comparison of their characteristics which are the key factors of these protocols.

   The Section II gives the definition and categorization of routing protocols in MANETs. In Section III, the overall and category-wise performance analysis of routing protocols is performed. In Section IV, conclusion is derived based on the analysis. And section V defines the proposed future work expected by the analysis.

2. ROUTING PROTOCOLS IN MANETS

   Routing is the process of making the selection of paths in a network along which network traffic can be send.

   Protocols are the formal set of rules or regulations which used when two or different devices communicate in the network.

   Routing protocols gives the specification that how routers communicate with each other, they widely scatter the information that enables them to select routes with the help of routing algorithms between any two nodes on a computer network. Each router contains a priori knowledge only of networks which are directly connected to it. First of all this information is shared by the routing protocol to immediate neighbours, and then throughout the network. This way, routers become aware of the topology of the network.

   A large number of protocols have been developed for ad hoc mobile networks [1]; dealing with the constraints of mobile networks like high power consumption, low bandwidth, and high error rates. As shown in Figure 3, these routing protocols may generally be categorized as Table-driven [2], On-demand [3] and Hybrid routing protocols [A]. The characteristics of each of these protocols are readily distinguishable from each other, though they are intended to serve the same network.

   Table-driven routing protocols [2], such as DSDV, CGSR, and WRP etc., make an effort to maintain uniform, up-to- date routing information from each node to every other node in the network. These protocols have requisite that every node in the network will maintain one or more tables to gather routing information, and they react favourably to changes in network topology by locomoting updates throughout the network in order to maintain a consistent network view. Source-initiated on-demand routing protocols [3], such as AODV, DSR, CBRP, TORA and ABR etc., create routes only when desired by the source node. When a node requires a route to a destination, the route discovery process is performed within the network. This process ends up when route is made available. The route maintenance procedure maintains that established route until it is no longer needed.

   Whereas, Hybrid routing protocols [4], such as ZHLS and ZRP etc., are a new generation of protocol, which combines the features of both on-demand and table driven routing protocols. Hybrid protocols aims to provide greater scalability by allowing neighbouring nodes to work simultaneously to form a kind of a major sustaining factor to decrease the route discovery problems. For example in On-demand protocols, a source initiates a route request ood when there is a need of path to destination [5].

   Ad-Hoc Routing Protocols

   Table-driven

   On-demand

   Hybrid

   DSDV WRP

   AODV

   DSR

   CBRP

   SSR ZRP ZHLS

   GGSR TORA ABR

   Figure 3: Categorization of ad hoc routing protocol

3. ANALYSIS

   1. Performance Analysis of Table-Driven Routing Protocols

      Destination-Sequenced Distance-Vector Routing (DSDV) routing [6], is introduced essentially by performing modifications to the basic Bellman- Ford routing algorithm [7]. DSDV is a simple route update protocol and ensures the loop-free routes [8]. DSDV takes the shortest path as a choice to the destination among several routes depending on the hop count to the given destination. However, DSDV lacks ability when periodic update transmissions are required [9], disregarding the number of changes occured in the network topology. Cluster-head Gateway Switch Routing (CGSR) [10] involves basic facts and principles of DSDV routing protocol that is why, it also has same overhead as in DSDV. CGSR performs routing on cluster

      heads and gateways. A cluster head table is logically inevitable in addition to the routing table. The Wireless Routing Protocol (WRP) [11] is distinct from the other protocols in various ways. Each node in WRP maintains four routing tables and ensures loop freedom [12]. This may require substantial amount of memory, especially when there are larger number of nodes in the network. WRP protocol needs to send hello messages if no recent packet transmissions are performed from a given node. They consume bandwidth but do not allow a node to enter sleep mode. However, although it belongs to the class of path-finding algorithms, WRP is advantageous for other path-finding algorithms because it stay clear to the problem of creating temporary routing loops and it also avoids the count-to-infinity problem [13]. Table 1 below gives the performance analysis:

      CHARCTERISTICS	DSDV	CGSR	WRP
      Time complexity	O(d)	O(d)	O(h)

      Communication complexity	O(x = N)	O(x = N)	O(x = N)
      Nature of Routing	Flat	Hierarchical	Flat
      Routing standard	Shortest Path	Shortest Path	Shortest Path
      Update transmissions often-ness	At regular intervals and when required	At regular intervals	At regular intervals and when required
      Use of sequence numbers	Yes	Yes	Yes
      Use of hello messages	Yes	No	Yes
      Loop-free	Yes	Yes	Yes, but not immediate
      Critical nodes	No	Yes (cluster head)	No
      Multicast capability	No	No*	No
      Tables required	Two	Two	Four
      Updates transmitted to	Neighbours	Neighbours and cluster head	Neighbours
      Where: N = Number of nodes in the network d = Diameter of Network h = Routing tree dimension x = Influence of topological change on the number of nodes * CGSR does not support multicasting; but it uses separate protocol which provides multicast capability.

      Table 1

   2. Performance Analysis of On-Demand Routing Protocols

      Ad Hoc On-Demand Distance Vector (AODV) routing protocol [14], utilizes a route discovery procedure as in DSR; however, they have little important dissimilarity. It is

      noteworthy that the overhead of Dynamic Source Routing (DSR) protocol [15], is potentially larger than that of AODV since each DSR packet must carry full routing information, whereas in AODV packets required only to contain the destination address. DSR returns the larger route replies because it contains the address of each node along the route, but AODV route replies have only the

      destination IP address and sequence number. As DSR contains the full routes, it requires more memory unlike AODV. If any link failure occurs in the network, DSR send a unicast packet to the source giving the information about the broken link where as AODV broadcast the Route error message to all its neighbors as it is possible that the reverse path from the problematic node to the source has timed out. The DSR algorithm is proposed for networks in which the nodes move at less speed with respect to packet transmission latency [16]. Route recovery is faster in DSR than most of the other on-demand protocols. On the other hand, Temporally Ordered Routing Algorithm (TORA)

      [17] is based on the concept of link reversal that is proposed for highly dynamic networks with large number of mobile nodes. TORA is advantageous because it provides multiple routes to destination from the source node. Multiple routes are feasible only in TORA and DSR for a single source and destination pair. As a distinction to AODV [18], availability of multicast operation lacks in TORA, but TORA uses Lightweight Adaptive Multicast Algorithm (LAM) [14], to associate the multicasting in it [19].

      Whereas, Associativity-Based Routing (ABR) [20] is based on nodes associativity and a new metric known as associativity degree is used and square ups the broadcast

      and point-to-point routing. It uses to forward the packets using connection-oriented approach. It has one distinct feature that it uses associativity ticks which are required only to create routes depending on the stability of nodes and therefore ABR stresses on the longevity of the routes created. ABR also guarantees that it does not send duplicate packets. Reason behind is that only the best route is considered in effect and rest of all possible routes used to be inactive.

      The Signal Stability Routing (SSR) [21] algorithm is analytically derived from ABR. The choice of routes depends on the strength of the signal and location permanence of nodes through the path. In AODV and DSR [22], nodes between source and destination may respond to requests of routes unlike in SSR. This is the one major drawback of SSR.

      Cluster Based Routing Protocol (CBRP) [23] is an on- demand routing protocol, in which nodes are divided into clusters and thus it minimizes the control overhead as it is spread into the network. CBRP is different from other on- demand routing protocols. This protocol suffers from temporary invalid routes as the destination nodes travel from one cluster to another. Therefore, CBRP is convenient when the size of network is moderate having slow mobility. Table 2 below gives the performance analysis:

      CHARCTERISTICS	AODV	DSR	TORA	ABR	SSR	CBRP
      Time complexity (start)	O(2d)	O(2d)	O(2d)	O(d + z)	O(d + z)	O(2d)
      Time complexity (after failure)	O(2d)	O(2d)	O(2d)	O(l + z)	O(l + z)	O(2B)
      Communication complexity (start)	O(2N)	O(2N)	O(2N)	O(N + y)	O(N + y)	O(2x)
      Communication complexity (after failure)	O(2N)	O(2N)	O(2x)	O(x + y)	O(x + y)	O(2A)
      Nature of Routing	Flat	Flat	Flat	Flat	Flat	Hierarchical
      Use of route cache/table expiration timers	Yes	No	No	No	No	Yes
      Multicast capability	Yes	No	No	No	No	Yes
      Existence of Multiple routes	No	Yes	Yes	No	No	No

      Loop-free	Yes	Yes	Yes	Yes	Yes	Yes
      rocedure to Route reconfiguration	Delete Route & Inform source	Delete Route & Inform source	Backtrack link to repair route	Confined broadcast query to nodes	Delete Route & Inform source	Delete Route then SN & local route repair
      Routing standard	Recently made Shortest path	Shortest path	Shortest path	Resulting from Shortest path	Resulting from Stable path	First available route (first fit)
      Where: N = Number of nodes in the network d = Diameter of Network l = Diameter of the network section which is influenced x = Influence of topological change on the number of nodes y = Exact number of nodes creating the directed path at transit of REPLY packet z = Diameter of the directed path at transit of REPLY packet A= number of affected nodes B= diameter of the affected area

      Table 2

   3. Performance Analysis of Hybrid Routing Protocols

      In the Zone Routing Protocol (ZRP) [24], the whole network is split up into overlapping zones which may be of different variable sizes [25]. It makes the use of table driven protocols to search the zone neighbors by transmitting hello messages as well as on-demand protocols for routing purposes among different zones. Routes are only created when desired. Each node is confined to zone size defined by the node itself and zone size can be the number of hops to the zone perimeter. Although ZRP is not readily distinguishable from all other protocols, it furnishes the framework for other protocols [26]. Zone-based

      hierarchical link state (ZHLS) [27] routing protocol uses hierarchical structure. In ZHLS, the network is split up into non-overlapping zones unlike ZRP, and every node contains a node ID and a zone ID, which is determined by GPS. However, ZRP has more overhead because zones overlap heavily. Table 3 below gives the performance analysis:

      CHARCTERISTICS	ZRP	ZHLS
      Time Complexity(RD)	Intra: O(l)/ Inter: O(2D)	Intra: O(l)/ Inter: O(D)
      Nature of Routing	Flat	Hierarchical
      Multiple routes	No	Yes, if more than one virtual link exists
      Routing standard	Shortest Path	Shortest Path or next available virtual link
      Procedure to Route reconfiguration	Route repair at point of failure and Inform source	Location request
      Where: RD = Route discovery I = Periodic update interval D= Diameter of a zone

      Table 3

   4. Performance Analysis of Table- Driven, On-Demand, And Hybrid Routing Protocols

      In general, on-demand (reactive) protocols are more efficient than table driven (proactive) ones. On demand protocols reduce control overhead and power consumption since routes are only established when required. On the other hand, table driven protocols need periodic route updates to retain possession of current and consistent information; also they keep information of multiple routes which may or may not be used that increases the routing overheads. Table driven routing protocols are better in providing quality of service than on-demand protocols. As routing information is continually keeps updating in the

      table driven protocols, routes are always available up-to- date to every destination and, hence end- to- end delay can be reduced. In on-demand protocols, when source node needs to communicate, it waits until the route is discovered and after that communication takes place. This type of delay in route discovery and communication will be unpleasant for real-time communications. Another class of unicast routing protocols that can be identified as that of hybrid protocols which combines both proactive (table driven) and reactive (on demand) approaches and collectively utilizes the advantages of these two categories of routing protocols. Table 4 below gives the performance analysis:

      CHRACTERISTICS	TABLE-DRIVEN		ON-DEMAND			HYBRID
      Availability of routing Information	Always available regardless of need		Available on need			Depends on the location of the destination
      Routing philosophy	Mostly flat, CGSR	except for	Flat			Mostly hierarchical
      Requirement of periodic route updates	Yes		No			Yes, between zones or gateways
      Mobility dealing	Nodes keep routing table	consistent	Route localized	discovery	is	Usually more than one path
      						may be available. Single point
      						of failures are reduced by
      						working as a group.
      Delay level	Small routes are		Higher than proactive			For local destinations
      	predetermined					small.
      						Inter-zone may be as
      						large as
      						reactive protocols
      Scalability level	Usually up to 100 nodes.		Source routing protocols up to			Designed for up to 1000 or
      			Few hundred nodes. Point-			more nodes
      			to-point
      			may scale higher. Also
      			depends on the level of traffic
      			and the levels of multi- hopping
      Rise of Signalling traffic	Raises when mobility of active routes increase		Larger than on- demand routing			Mostly, lower than proactive and reactive
      Quality of service	Less support to QoS, rest take the shortest path		Mainly shortest path as the QoS metric			No

      Storage requirements	High	Depends on the number of routes kept or required. Usually	Each cluster or zone may become
      			as large as proactive
      		lower than proactive
      		protocols	protocols if clusters are big

      Table 4

      The overall above analysis brings out that, as DSDV broadcasts frequent routing updates, takes more bandwidth. AODV has less overhead and more bandwidth because there is no need to maintain routing tables in it, that is why, it is better than DSDV. Performance of DSR is observed very poor in larger networks, as it shows extreme high delays in delivering packets. The performance of AODV was very good in all network sizes, even though the routing overhead is higher than in DSR. It has also been observed that performance of TORA is quite good in delivery of packets by selecting better routes with the use of acyclic graph. It can also be assumed that DSDV performs better in smaller networks only. It has also been observed that AODV performs better in dense mediums and with faster speeds.

      The analysis also brings out that ZRP and CBRP are two very exciting protocols that divide the whole network into several zones/clusters. CBRP makes an effort to reduce the control overheads spread into the network by splitting the network into clusters. In extremely mobile networks, CBRP may receive fairly large amount of processing overheads at the time of formation and maintenance of cluster. This protocol suffers from temporary invalid routes because the destination nodes travel into different cluster. Therefore, this protocol is appropriate only for medium size networks having less mobility.

4. CONCLUSION

   In this paper, an effort has been made to concentrate on the comparative performance analysis of various Table-Driven, On-demand and Hybrid routing protocols on the basis of above mentioned performance metrics. The performance of routing protocols is almost invariably appraised as a function of mobility rate and speed disregarding the network size. It is observed by the analysis that all the protocols work well in distributed medium where mobility and traffic is low but not in dense medium.

   As a conclusion, AODV routing protocol is comparatively worthy of being chosen for general mobile ad-hoc networks as it takes less bandwidth and lower overhead because it doesnt keep any routing tables at nodes. AODV is a favourable routing protocol in different ways, like:

   • Routes are created by On-demand basis and destination sequence numbers are used to search the latest route to the destination.

   • It prefers the least congested route instead of the shortest route.

   • The connection set up delay is less.

   • Ability to adapt highly dynamic topologies, so that it can respond to the topological changes very quickly which affects the active routes.

5. FUTURE WORK

   Few efficiency enhancements can make AODV a highly efficacious routing protocol for larger networks, which are:

   • For broadcast medium there is a requirement that nodes should have to detect the broadcasts of each other node.

   • Route maintenance technique can be improved.

   The focus of the analysis is on these issues in the future research work and need and effort to propose a routing protocol in Ad Hoc networks which can perform best when mobility and traffic increases by confronting these core issues of secure and power aware/energy efficient routing.

6. ACKNOWLEDGMENTS

   I would like to give special thanks to my college faculty and friends to help me to understand the difficult concept of Mobile Ad-Hoc networks and for providing necessary information related in this area.

7. REFERENCES

1. J. Jubin and J. Tornow, The DARPA Packet Radio Network Protocols, Proc. IEEE, vol. 75, no. 1, 1987, pp. 2132.

2. Charles E. Perkins, Ad Hoc Networking, Addision Wesley, 2001.

3. Tseng Y.C., Shen C.C, and Chen W.T., Mobile ip and ad hoc networks: An integration and implementation

   experience, Technical report, Dept. of Comput. Sci. and Inf. Eng., Nat. Chiao Tung Univ., Hsinchu,, Taiwan, 2003.

4. C. Siva Ram Murthy and B.S. Manoj, Ad Hoc Wireless Networks Architectures and Protocol, volume ISBN: 81-297-0945-7. Pearson Education, first Indian reprint, 2005 edition, 2005.

5. D. B. Johnson, D. A. Maltz, Y.-C. Hu, and J. G. Jetcheva, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR), February 2002.

6. C. E. Perkins and P. Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, Comp. Commun. Rev., Oct. 1994, pp. 23444.

7. L. R. Ford Jr. and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, 1962.

8. R.E. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957.

9. C.E. Perkins, T.J. Watson, Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers, in: ACM SIGCOMM_94 Conference on Communications Architectures, London, UK, 1994.

10. C.-C. Chiang, Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel, Proc. IEEE SICON 97, Apr. 1997, pp. 197211.

11. 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. 18397.

12. S. Murthy J.J. Garcia-Luna-Aceves, A routing protocol for packet radio networks, in: Proceedings of the First Annual ACM International Conference on Mobile Computing and Networking, Berkeley, CA, 1995, pp. 86 95.

13. A. S. Tanenbaum, Computer Networks, 3rd ed., Ch. 5, Englewood Cliffs, NJ: Prentice Hall, 1996, pp. 35758.

14. C. E. Perkins and E. M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proc. 2nd IEEE Wksp. Mobile Comp. Sys. And Apps, Feb. 1999, pp. 90100.

15. D. B. Johnson and D. A. Maltz, Dynamic Source Routing in Ad-Hoc Wireless Networks, Mobile

    Computing, T. Imielinski and H. Korth, Eds., Kluwer, 1996, pp. 15381.

16. V. D. Park and M. S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proc. INFOCOM 97, Apr. 1997.

17. M. S. Corson and A. Ephremide, A Distributed Routing Algorithm for Mobile Wireless Networks, ACM/Baltzer Wireless Networks J., vol. 1, no. 1, Feb. 1995, pp. 6181.

18. C. E. Perkins and E. M. Royer, Ad Hoc on Demand Distance Vector (AODV) routing, IETF Internet draft, draft-ietf-manet-aodv-02.txt, Nov. 1998 (work in progress).

19. L. Ji and M. S. Corson, A Lightweight Adaptive Multicast Algorithm, Proc. GLOBECOM 98, Nov. 1998, pp. 103642.

20. C-K. Toh, A Novel Distributed Routing Protocol to Support Ad-Hoc Mobile Computing, Proc. 1996 IEEE 15th Annual Intl. Phoenix Conf. Comp. and Commun. Mar. 1996, pp. 48086.

21. R. Dube et al., Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks, IEEE Pers. Commun., Feb. 1997, pp. 3645.

22. A. Kush and S. Taneja, A Survey of Routing Protocols in Mobile Ad-hoc Networks, International Journal of Innovation, Management and Technology, Vol. 1, No. 3, 2010 pp 279-285.

23. M. Jiang, J. Ji, Y.C. Tay, Cluster based routing protocol, Internet Draft, draft-ietf-manet-cbrp-spec-01.txt, work in progress, 1999.

24. Z.J. Hass, R. Pearlman, Zone routing protocol for ad- hoc networks, Internet Draft, draft-ietf-manet-zrp-02.txt, work in progress, 1999.

25. Hass, Z.J.; Pearlman, M.R., Zone Routing Protocol (ZRP) for ad-hoc networks, July 2002

26. Schaumann, J., Analysis of the zone routing protocol, July 2002

27. M. Joa-Ng, I.-T. Lu, A peer-to-peer zone-based two- level link state routing for mobile ad hoc networks, IEEE Journal on Selected Areas in Communications 17 (8) (1999) 14151425.