Performance Comparison of AODV, DSR, DSDV and OLSR MANET Routing Protocols

Performance Comparison of AODV, DSR, DSDV and OLSR MANET Routing Protocols

Akshay Shankar, Lavanya Chelle Information Science Engineering RNS Institute of Technology Bangalore, India

Abstract- A Mobile Ad-hoc Network (MANET) is a collection of arbitrarily moving wireless mobile nodes that are infrastructure-less, self-organized and self-configurable. They can function even in rapidly changing topologies. Due to this highly dynamic environment, routing in MANET is a difficult, yet crucial task. Over the last decade, various routing protocols have been proposed for the mobile ad-hoc network and some of the most important among these are AODV, DSR, DSDV and OLSR. This research paper gives the overview of these routing protocols and their comparative analysis based on similar environment conditions. We evaluate their performance based on Packet Delivery Ratio, Throughput and Average end-to-end delay. The simulation results dictated that OLSR and DSDV perform best in networks where nodes were less mobile and densely populated. AODV was suitable for networks with more number of nodes. DSR performed well in networks with low mobility rate and a lower traffic density.

KeywordsMANET; AODV; DSR; DSDV; OLSR

1. INTRODUCTION

   The cause for the requirement of efficient and swift communication between wireless devices is due to their rapid development and demand by the general population. This has also created an increased appeal for wireless networks as they are inexpensive and are open-ended.

   Mobile Ad-hoc Network (MANET) was created for this purpose. Unlike wired networks, MANETs are void of any kind of infrastructure support, including switches or cables. This causes the network topology to change very rapidly as the number of nodes, the location of these nodes and the metric, all vary a greatly within a short amount of time. Additionally, this variation requires MANETs to be self- configuring and adaptable in order to maintain a consistent data transmission speed. Furthermore, the limited transmission range of mobile devices is overcome by utilizing intermediate nodes as routers for other nodes. [4]

   These characteristics of MANETs renders interior routing protocols, like Distance-vector and Link-state, inefficient due to high storage requirement and loop formation, respectively. [3] In their stead, ad hoc routing protocols were developed specifically for MANETs, which include AODV, DSDV, DSR, ZRP, TORA etc.

   MANETs are useful in various application areas such as: Communication in the battlefields, institutions and colleges, military areas, disaster recovery areas, law and order maintenance, traffic control areas, medical field, conferences and convocations.

   In this paper we compare Destination Sequenced Distance Vector (DSDV), Ad-hoc On-demand Distance Vector (AODV), Optimized Link State Routing (OLSR) and Dynamic Source Routing (DSR) and analyze the Packet Delivery Ratio, Throughput and Average end-to-end delay of each of these.

2. RELATED WORK

   Rajeev Paulus, et al [9] analyzed the performance of AODV, DSR, OLSR, ZRP. They used QualNet version 6.1 and evaluated the performance of these protocols to compare parameters viz., throughput, packet delivery ratio (PDR), average end to end delay and average jitter. They concluded that ZRP has lower throughput and lower PDR than others, with varying pause time and maximum speed. The performance of AODV was best for all performance metrics. DSR throughput and packet delivery ratio was better than OLSR and ZRP. OLSR shows the worst performance for average jitter and average end-to-end delay with the varying pause time. DSR shows the worst performance for average jitter and average end-to-end delay.

   Anuj K. Gupta, et al [8] compared AODV, DSDV and TORA using Network Simulator 2 (NS-2). They analyzed various performance parameters such as packet delivery fraction, or throughput, and end-to-end delay. They observed that for constant model, AODV outperforms DSDV and TORA. Though TORA performed better at high mobility, it had lower throughput in other cases. AODV in their simulation shows to have the best overall performance. DSR outperforms the other protocols in terms of overhead. TORAs performance is not very competitive with the distance vector and on-demand protocols.

   Samba Sesay, et al [7] surveyed DSDV, DSR, TORA and AODV using extended version of UCB/LBNL network simulator ns-2 to simulate a virtual environment of 1200 * 300 m for 600 sec. They analyzed the throughput, average end-to-end or mean overall packet latency, packet delivery ratio, route acquisition time and routing overhead. DSR showed the best performance having a relatively lower routing overload for all cases. DSDV performed the worst at high movement speed and for a large number of nodes. TORA showed a better best performance for large networks with high mobility rate and movement speed.

   Charles E. Perkins, et al [6] analyzed the performance of DSR and AODV, two prominent on-demand routing protocols for ad hoc networks using ns-2 network simulator. They took parameters such as normalized routing load, normalized MAC load, average end-to-end delay and packet delivery ratio for the analysis. MAC load is a measure of

   effective utilization of the wireless medium by data traffic. The poor delay and throughput performances of DSR are mainly attributed to aggressive use of caching, and lack of any mechanism to expire stale routes or to determine the freshness of routes when multiple choices are available.

   Josh Broch, et al [5] examined the performances of DSDV, TORA, DSR and AODV using ns network simulator. They compared parameters like packet delivery, routing overhead, path optimality and lower speed of node movement. TORA, although the worst performer in their experiments in terms of routing packet overhead, still delivered over 90% of the packets in scenarios with 10 or 20 sources. AODV performs almost as well as DSR at all mobility rates and movement speeds and accomplishes its goal of eliminating source routing overhead.

3. ROUTING PROTOCOLS

   Routing protocols for Mobile Ad-hoc networks can be subdivided into 2 types: Proactive and Reactive routing.

   1. PROACTIVE ROUTING

      Proactive routing or Table-Driven routing protocols allow all nodes to disseminate continuous and periodic updates throughout the network topology, which helps each node in obtaining a view of the entire network and in maintaining route consistency. As the nodes maintain tables to store these updates, the decisions that are taken with regard to the forwarding of a packet are immediate.

      1. DESTINATION SEQUENCED DISTANCE VECTOR (DSDV)

         DSDV is an upgradation of the classic Bellman-Ford routing algorithm, as it solves the count-to-infinity problem. Each node in the network maintains a periodically updated routing table. It has the following fields:

         <destination, next hop, metric, sequence number, install time>

         Metric specifies the hop count. Sequence numbers are generated from the destination node and it ensures route freshness. Install time helps determine when to delete stale routes.

         Packets transmission can be done in two methods. A full dump, in which the packet will carry all the routing information and an Incremental, in which it will carry only that information which has changed since the last full dump. During a full dump, the data packet broadcasted by the node contains the following information for each new route:

         • The destination IP address

         • The hop count required to reach the destination

         • The new sequence number generatedby the destination

           When destination node receives the data packet, it compares the sequence number of the received packet with its corresponding entry in the routing table. The sequence number is updated, if the new sequence number is larger. But if the new sequence number is equal to the one in the routing table, then the metric is compared and the smallest one is chosen. The routing table is updated. Subsequently, the receiver increments the metric by 1 and the sequence number by 2, before rebroadcasting the packet to its neighbors.

           Whenever a broken link is discovered the data packet will contain an infinity metric and an odd sequence number, which helps solve the count-to-infinity problem. [10] [14]

      2. OPTIMIZED LINK STATE ROUTING (OLSR)

         Optimized Link State Routing (OLSR) is a proactive non- uniform protocol that is based on the Link State Routing (LSR) protocol. In the actual LSR protocol, every node propagated its link state information to every other node. This greatly increased redundancy. [1] In the OLSR, this redundancy was curtailed by reducing the number of nodes that can re-transmit information. In OLSR, periodic messages are used to update the topological information of the nodes in the network. The routes to the destination are immediately available at each node. Instead of flooding, Multipoint Relay (MPR) nodes are used for packet re- transmission. MPRs of a node are the set of its neighbor nodes, which are selected to retransmit the packets generated by it. These MPRs are selected among the one hop neighbors that are bi-directionally linked to the node.

         OLSR uses two types of control messages. They include Hello and Topology Control (TC) message. Hello message is used to get the information about the link status and the node's neighbors. Whereas, TC messages are used for broadcasting information. Each Hello message contains a list of addresses of bi-directionally linked neighbor nodes. Every node in the network has a topological table in which it maintains the topological information obtained from the TC messages. MPR node information is also included in TC messages. Based on these information, routing table is fabricated. If there is any change in subsequently received information, the table is re-created.

         Additionally, OLSR does not require sequenced delivery of messages, as a sequence number is given to all the messages. Therefore, on the delivery of messages, the recipient can know the most recent message even if the messages are re-ordered during the transmission. [2]

   2. REACTIVE ROUTING

      Reactive routing protocols create routes on demand. They do not transmit periodical signals, like proactive protocols, but compute and discover routes as and when they are required. This makes it more suitable for ad-hoc networks, since the nodes in these networks are always fluctuating. These protocols utilize the flooding technique to find routes.

      1. AD-HOC ON DEMAND DISTANCE VECTOR (AODV)

         Ad-hoc On Demand Distance Vector Routing (AODV) is a reactive unicast routing protocol. It is a confluence of both DSDV and DSR. It uses an on-demand approach for finding routes, which means that a route is established only when it is required by a source node. Whenever a source node needs a route to a destination node, it generates a Route Request (RREQ) packet and floods it to all of its neighboring nodes. It contains the source address, destination address, source and destination sequence numbers, broadcast ID and the hop count. Sequence numbers are maintained to determine the most recent routing information and to prevent routing loops. Broadcast ID keeps count of the number of times the source initiated a path discovery process. Source address, along with broadcast ID, forms a unique pair which is used by nodes in order to locate redundant RREQ packets. A node that receives RREQ, either sends a Route Reply (RREP) back to

         the source, if it is the destination node, or increases the hop count of the RREQ packet and re-broadcasts it. Every node that receives the RREQ, and is not the destination node, will maintain a reverse path for the traversal of the RREP packet, as long as the RREQ packet is present in the network. The RREP packet contains destination address, source address, destination sequence number, hop count and Time to Live (TTL). If a link is broken, then the node broadcasts it by sending a Route Error (RERR) packet to the source node. Upon reception, it re-initiates the path discovery process.

         AODV stores one entry per destination, and the routing table entries will expire if not used frequently. Another distinguishing feature of AODV is that, it can provide unicast, multicast and broadcast communication. [11] [12]

      2. DYNAMIC SOURCE ROUTING (DSR)

   Dynamic source routing (DSR) is a self-maintaining reactive unicast routing protocol for ad-hoc wireless networks. DSR uses source routing algorithm. A Dynamic Source Routing network can configure and organize itself independently. The protocol can also function with cellular telephone systems and mobile networks.

   The two major phases in DSR are the route discovery phase and the route maintenance phase. Route discovery phase is initiated, when a node needs a route to another node. Here, the node which is seeking a route is called source node, and the node to which it is seeking a route to, is called the destination node. The route discovery phase is based on flooding. The source node generates RREQ (route request) packet, which contains addresses of both the source and the destination and a unique number to identify the request, and it is flooded throughout the network. Each node that receives this packet appends its own address into the packet header. At the same time, whenever RREQ reaches either the destination or a node that knows a route to the destination, a RREP (route reply) packet, which contains the addresses of nodes that the RREQ has traversed, is sent in reverse route. Source node might receive many RREP signals. It chooses the route with the shortest distance, and the rest of the routes are cached. If a selected route gets disconnected, then a route from cache can used as a substitute to speed up the process.

   Each RREQ packets has a unique identifier. Once a RREQ packet has been processed by a node, it will discard any other RREQ packets that bears the same identifier. This helps in avoiding duplication, and reducing the space required for caching. In route maintenance phase, the protocol detects if the topology of the network has changed, and decides whether an alternative route is to be used or to initiate another the route discovery protocol. When there is a link disconnection, a RERR (route error) packet is sent backward to the source. The nodes through which this packet is traversing should remove all routes containing the broken link from their route caches. After receiving the RERR packet, the source node initiates a route discovery operation. [13]

4. PERFORMANCE METRICS

   We consider the following three performance metrics to compare the four routing protocols.

   1. Average end-to-end delay: It is defined as the average time taken by the data packets to be transmitted from the source to the destination across the MANET. It includes transmission delay, propagation delay, processing delay and queuing delay. Measured in milliseconds (ms).

   2. Throughput: It is the rate of transmission of data packets in unit time.

   3. Packet Delivery Ratio (PDR): It is the ratio of number of packets delivered to the destination to the number of packets generated at the source.

5. SIMULATION PARAMETERS

   Parameter	Values
   Simulator	ns-3.25
   MAC Protocol	IEEE 802.11
   Simulation Area	500x2000m
   Mobile Nodes	20, 60, 100
   Node Speed	20 m/s
   Pause Time	0, 10, 30, 50, 70, 100 seconds
   Mobility Model	Random Waypoint
   Packet Size	64 byte
   Rate of Transmission of Packets	4 Packets per Second
   Routing Protocols	AODV, DSR, DSDV, OLSR
   Traffic Sources	Constant Bit Rate
   Simulation Time	200 seconds

6. SIMULATION RESULTS AND DISCUSSIONS

   In this Section, we compare the capabilities of the four routing protocols studied in this paper. The simulation results are shown in the following section in the form of line graphs. The routing protocols AODV, DSR, DSDV and OLSR are compared based on the above mentioned performance metrics, as a function of pause time and using different number of sources.

   1. THROUGHPUT

      Figures 1 to 3 give the throughput of the routing protocols with varying number of sources. Throughput increases when there is good connectivity between nodes. We found that AODV has the best overall performance. The performance of DSR increased with increase in pause time, but decreased when the number of nodes were more. OLSR performed best in the presence of heavy traffic. Throughput of DSDV declined with increased number of nodes.

      Fig. 1. Throughput (20 Nodes)

      Fig. 2. Throughput (60 Nodes)

      Fig. 3. Throughput (100 Nodes)

   2. AVERAGE END-TO-END DELAY

      Figures 4 to 6 provide the average end-to-end delays. Smaller delays indicate better performance. It was found to be less with respect to proactive routing protocols, than reactive ones as route acquisition is performed beforehand. OLSR had the least delay during all scenarios, even less than that of DSDV. AODV and DSR provided similar delays with less number of nodes, but as the number of nodes increased AODV out-performed DSR.

      Fig. 4. Average end-to-end delay (20 Nodes)

      Fig. 5. Average end-to-end delay (60 Nodes)

      Fig. 6. Average end-to-end delay (100 Nodes)

   3. PACKET DELIVERY RATIO (PDR)

   Figures 7 to 9 give PDR of the routing protocols. PDR directly measures the reliability of a network. It also provides the loss in data packets in a network. DSR performed well when pause time and traffic was high. AODV and OLSR had almost similar PDR throughout the experiment. PDR of DSDV was found to be consistently lower than other protocols.

   Fig. 7. Packet Delivery Ratio (20 Nodes)

   Fig. 8. Packet Delivery Ratio (60 Nodes)

   Fig. 9. Packet Delivery Ratio (100 Nodes)

7. CONCLUSION

In this paper we illustrate the performance of four routing protocols (AODV, DSR, OLSR and DSDV). We have used the latest simulation environment NS 3 and evaluated the routing protocols based on pause time and network density. The pause time is varied from 0 to 100 seconds and the number of nodes from 20 to 100 in a fixed topography of 500×2000 meters. The performance criterion used in this paper, packet delivery ratio, throughput and average end-to- end delay, are critical in assessing any routing protocol.

Our simulations led us to conclude that OLSR and DSDV are best suited for networks with high density and low latency, as the average end-to-end delay was significantly lower than other protocols and the throughput did not decrease with increase in number of nodes. AODV had the best overall performance, and is suitable for networks with more number of nodes. Whereas, DSR is fitting for networks with low mobility rate and a lower traffic density.

REFERENCES

1. P. J. and T. C. , "Optimized Link State Routing (OLSR)," RFC, 2003.

2. Shubhi and P. Shukla, "Comparative Analysis of Distance Vector Routing & Link State Protocols," International Journal of Innovative Research in Computer and Communication Engineering, vol. 3, no. 10, p. 9533, 2015.

3. Aarti and Dr. S. S. Tyagi, "Study of MANET: Characteristics, Challenges, Application and Security Attacks," International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 5, p. 252, 2013.

4. J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu and J. Jetcheva, "A performance comparison of multi-hop wireless ad hoc network routing protocols," in MobiCom '98 Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, New York NY, 1998.

5. C. E. Perkins, S. R. Das, E. M. Royer and M. K. Marina, "Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks," IEEE Personal Communications, vol. 8, no. 1, pp. 16-28, 2001.

6. S. Sesay, Z. Yang, B. Qi and J. He, "Simulation Comparison of Four Wireless Ad hoc Routing Protocols," Information Technology Journal 3 (3), pp. 219-226, 2004.

7. A. K. Gupta, H. Sadawarti and A. K. Verma, "Performance analysis of AODV, DSR & TORA Routing Protocols," IACSIT International Journal of Engineering and Technology, vol. 2, no. 2, April 2010.

8. R. Paulus, P. D. Kumar, P. C. Philips and A. Kumar, "Performance Analysis of Various Ad Hoc Routing Protocols in MANET using Variation in Pause Time and Mobility Speed," International Journal of Computer Applications, vol. 73, no. 8, July 2013.

9. C. E. Perkins and P. Bhagwat, "Highly dynamic Destination- Sequenced Distance-Vector routing (DSDV) for mobile computers," in SIGCOMM '94 Proceedings of the conference on Communications architectures, protocols and applications, New York, NY, USA, 1994.

10. E. M. Royer and C. E. Perkins, "Multicast operation of the ad- hoc on-demand distance vector routing protocol," in MobiCom '99 Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, New York, 1999.

11. C. E. Perkins and E. M. Royer, in WMCSA '99 Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, Washington DC, 1999.

12. D. B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," in Mobile Computing, Springer US, 2001.

13. C. E. Perkins, Ad Hoc Networking, Addison Wesley Professional, 2001.

14. C. A. E. B. and P. J. , "Link state routing in wireless ad-hoc networks," in MILCOM'03 Proceedings of the 2003 IEEE conference on Military communications, Washington DC, 2003.