Comparative Analysis of AODV, OLSR, TORA, DSR and DSDV Routing Protocols in Mobile Ad-Hoc Networks

Published Online March 2013 in MECS

• I.    INTRODUCTION

  The history of wireless networks started in the 1970s and the interest has been growing ever since. At present, the sharing of information is difficult, as the users need to perform administrative tasks and set up static, bidirectional links between the computers. This motivates the construction of temporary networks with no wires, no communication infrastructure and no administrative intervention required. Such interconnection between mobile computers is called an Ad hoc Network. Ad hoc networks are emerging as the next generation of networks

and defined as a collection of mobile nodes forming a temporary (spontaneous) network without the aid of any centralized administration or standard support services. In Latin, ad hoc literally means “for this,” further meaning “for this purpose only” and thus usually temporary. The Communication in Mobile Ad-Hoc Network (MANET) is to take place by using multi-hop paths. Nodes in the MANET share the wireless medium and the topology of the network changes erratically and dynamically. In MANET, breaking of communication link is very frequent, as nodes are free to move to anywhere. The density of nodes and the number of nodes are dependent on the applications in which we are using MANET [1]. An ad hoc network is usually thought of as a network with nodes that are relatively mobile compared to a wired network. Hence the topology of the network is much more dynamic and the changes are often unpredictable oppose to the Internet which is a wired network. This fact creates many challenging research issues, since the objectives of how routing should take place is often unclear because of the different resources like bandwidth, battery power and demands like latency.

Routing protocols is one of the challenging and interesting research areas. There are different categories of MANET routing protocol, e.g. proactive, reactive, flow-oriented, adaptive, hybrid, hierarchical, geographical, power-aware, multicast, and many other routing protocols. Each category contains different routing protocols developed according to some specific domain requirements. Mostly, proactive, reactive and hybrid protocols are of high importance due to their algorithm implementation and applications support.

In Previous literature various protocols have been compared using different parameters. In [2] two reactive protocols have been compared. In [3] Ad-Hoc On Demand Distance Vector Routing (AODV), Dynamic Source Routing (DSR) and Temporally Ordered Routing Algorithm (TORA) Protocols have been compared using packet delivery fraction and end to end delay. In [4] Proactive and Reactive protocols have been compared. In [5] AODV, DSR and Optimized link State Routing (OLSR) have been compared using packet delay, network load and throughput. In [6] AODV, DSR, Destination-Sequenced Distance-Vector (DSDV) and TORA have been compared based upon number of packets transmitted, lost, bit rate and packet delay. In [7] OLSR,

AODV and TORA have been compared using packet delivery ratio, end-to-end delay and routing overload. In previous work done, the application where these protocols can be used in the best way is not identified based upon the results of comparison. In the proposed work, five commonly used protocols i.e. Ad hoc On Demand Distance Vector Routing (AODV), Optimized link State Routing (OLSR), Temporally Ordered Routing Algorithm (TORA), Dynamic Source Routing (DSR), and Destination-Sequenced Distance-Vector Routing (DSDV) have been picked, which have not been compared yet. The comparison has been done using five parameters i.e. Throughput, Average End-to-End Delay, Average Packet Jitter, Normalized Routing Load, Routing Overhead and Packet Delivery Fraction. The most efficient routing protocol to be used for different applications has been identified based upon the results of the comparison.

Remainder of this Paper is organised as follows: Section II introduces the mobile ad-hoc network and its characteristics. Section III introduces the routing protocols. Section IV gives the overview of routing protocols used in the study. Section V presents the performance metrics used in the study. Section VI describes the simulation tool used in this study. Finally the results and conclusions are presented in section VII.

the Internet. Internet Engineering Task Force (IETF) has MANET working group (WG) that is devoted for developing IP routing protocols. Routing protocols is one of the challenging and interesting research areas.

MANETs have several salient characteristics:

• 1)    Dynamic topologies

• 2)    Bandwidth constrained, variable capacity links

• 3)    Energy-constrained operation

• 4)    Limited physical security .

Due to the above mentioned characteristics, the routing protocols used in ordinary wired networks are not well suited for dynamic environment [3]. Fig. 1 shows Mobile Ad-hoc Network.

Figure 1: Mobile Ad- Hoc Network

• II.    MOBILE AD HOC NETWORK

MANET consists of set of wireless mobile nodes connected together to form temporary network in which the nodes are communicating with each other without centralized control [8], [2]. Mobile Ad-Hoc Networks are autonomous and decentralized wireless systems. In MANETs mobile nodes are free to move in and out of the network. Nodes are the systems or devices i.e. mobile phone, laptop, personal digital assistance, MP3 player and personal computer that are participating in the network and are mobile. When a node wants to communicate with another node, the destination node must lies within the radio range of the source node that wants to initiate the communication. The intermediate nodes within the network aid in routing the packets for the source node to the destination node. These networks are fully self organized, having the capability to work anywhere without any infrastructure. In MANETs each device need to forward traffic that is not related to its own use and therefore each device work as a router. These nodes can act as host/router or both at the same time. They can form arbitrary topologies depending on their connectivity with each other in the network. These nodes have the ability to configure themselves and because of their self configuration ability, they can be deployed urgently without the need of any infrastructure and without any geographical restrictions. Each user has the opportunity of moving freely while communicating with others. The distance between each user determines a radio contact between each other that might not be uniform. Mobile Ad Hoc Networks in an independent manner, and may lead to a larger network, as an annex to

• III.    ROUTING PROTOCOLS

Routing protocols in MANETs are classified into three different categories according to their functionality

• A.    Reactive protocols

• B.    Proactive protocols

• C.    Hybrid protocols

In Fig. 2 MANETs Routing Protocols are shown.

MANETs Routing Protocols

Reactive Protocols

AODV DSR  ACOR

Proactive Protocols

DSDV OLSR WRP

Hybrid Protocols

TORA ZRP HSLS

Figure 2: MANETs Routing Protocols

• A.    Reactive Protocols

Reactive protocols are also known as On-demand driven reactive protocols. These Protocols do not initiate route discovery by themselves, until or unless a source node request to find a route. That’s why these protocols are called reactive protocols. These protocols setup routes when demanded [9], [4]. When a node wants to communicate with another node in the network, and the source node does not have a route to the node it wants to communicate with, reactive routing protocols will establish a route for the source to destination node. Normally reactive protocols

• •    Don’t find route until demanded

• •    Uses flooding technique to propagate the query, to find the destination “On-Demand”.

• •    Do not consume bandwidth for sending information.

• •    They consume bandwidth only, when the node start transmitting the data to the destination node.

Some of the most used on demand routing protocols are DSR [10], [11], AODV [9], [7] and Admission Control enabled On demand Routing Protocol( ACOR).

• B.    Proactive Protocols

Proactive routing protocols work as the other way around as compared to Reactive routing protocols. These protocols constantly maintain update-to-date topology of the network. Every node in the network knows about the other node in advance, in other words the whole network is known to all the nodes making that network. All the routing information is usually kept in tables. Whenever there is a change in the network topology, these tables are updated according to the change. The nodes exchange topology information with each other; they can have route information any time when they needed. Some of the existing proactive routing protocols are DSDV [12], OLSR [13] and Wireless Routing Protocol (WRP).

• C.    Hybrid Protocols

Hybrid protocols exploit the strengths of both reactive and proactive protocols, and combine them together to get better results. The network is divided into zones, and use different protocols in two different zones i.e. one protocol is used within zone, and the other protocol is used between them. Zone Routing Protocol (ZRP) is the example of Hybrid Routing Protocol. ZRP uses proactive mechanism for route establishment within the nodes neighbourhood, and for communication amongst the neighbourhood it takes the advantage of reactive protocols. These local neighbourhoods are known as zones, and the protocol is named for the same reason as zone routing protocol. Each zone can have different size and each node may be within multiple overlapping zones. The size of zone is given by radius of length P, where P is number of hops to the perimeter of the zone [14]. Some of the existing hybrid protocols are ZRP [15], TORA [16] and Hazed Sighted Link State Routing Protocol (HSLS).

• IV. OVERVIEW OF PROTOCOLS

• A.    Optimized Link State Routing Protocol (OLSR)

Optimized Link State Protocol (OLSR) [13] is a proactive routing protocol, all nodes have route table that contains routing information of every node in the network. Thus the routes are always immediately available when needed. OLSR is an optimization version of a pure link state protocol. Hence the topological changes cause the flooding of the topological information to all available nodes in the network. OLSR protocol uses Multipoint Relays (MPR) to reduce the possible overhead in the network. The Fig. 3, illustrates the MPR utilization in packet transmission.

The idea of MPR is to reduce flooding of broadcasts by reducing the same broadcast in some regions in the network, and to provide the shortest path. OLSR uses the following control messages: Hello and Topology Control (TC). Hello messages are used for finding the information about the link status and the neighbour nodes. TC messages are used for broadcasting information about own advertised neighbours which includes at least the MPR Selector list. OLSR may optimize the reactivity to topological changes by reducing the maximum time interval for periodic control message transmission. OLSR has also Multiple Interface Design (MID) to allow the nodes for having multiple OLSR interface addresses and provide the external routing information giving the possibility for routing to the external addresses. Based on this information, nodes in the ad hoc network can act as gateways to another possible network. Furthermore, as OLSR continuously maintains routes to all destinations in the network, the protocol is beneficial for traffic patterns where a large subset of nodes are communicating with another large subset of nodes in which the source, destination pairs are changing over time.

Figure 3: Packet Transmission using MPR

• B.    Ad hoc On Demand Distance Vector Routing Protocol (AODV)

AODV [9] is an enhancement of Destination-Sequenced Distance-Vector (DSDV) routing protocol. Each node maintains a route table contains routing information but does not necessarily maintain routes to every node in the network and tremendously minimize the requirement of system wide broadcasts.

• 1.    Route Discovery

• 2.    Forward Path Setting

• 3.    Route Maintenance

When a source node wants to transmit the packet to its destination, the entries in the route table are checked to ensure whether there is a current route to that destination node or not. If route exists there, the packet is forwarded to the appropriate next hop toward the destination. If it is not there, the route discovery process is initiated to locate the destination. The source node broadcasts a control message RREQ with its IP address, Route Request ID (RREQ ID), and the sequence number of the source and destination. While, the RREQ ID and the IP (Internet Protocol) address is used to uniquely identify each request, the sequence numbers are used to determine the timeliness of each packet. To minimize network wide broadcasts of RREQ, the source node uses an expanding ring search technique. The Fig. 4 illustrates the route discovery process by broadcasting RREQ. The RREQ receiving node set the backward pointer to the source node and generates a Route Reply (RREP) unicast packet with a lifetime, sent back to the source if it is the destination or contains a route to the destination i.e. intermediate node. An intermediate node set up a reverse route entry with lifetime for the source node in its route table to process the RREQ and forwards a RREP to the source. When the RREP reaches the source node, it means a route from source to the destination has been established and the source node can begin the data transmission. If the RREQ is lost during transmission, the source node again starts broadcast using route discovery mechanism.

When an intermediate node receives RREQ from the source, it checks route table for valid route from source to its destination. If it is, copies its known sequence number for the destination into the Destination Sequence number field in the RREP message and RREP sent back to the source along the reverse path. If not, the intermediate node updates the forward route entry with preceding node into the precursor list and forwards the RREQ to its neighbour node.

A route which is discovered between a source node and destination node is maintained as long as the source node needed it. If the source node moves during an active session, it can reinitiate route discovery mechanism to establish a new route to destination. When either destination or intermediate node moves, the node upstream of the break initiates Route Error (RERR) message to the affected active upstream nodes. Consequently, these nodes propagate the RERR to their predecessor nodes. This process continues until the source node is reached. When RERR is received by the source node, it can either stop sending the data or reinitiate the route discovery mechanism by sending a new RREQ message if the route is still needed.

Figure 4: AODV Route Discovery Process

• C.    Temporally-Ordered Routing Algorithm Protocol (TORA)

Temporally-Ordered Routing Algorithm (TORA) [16], [6] is a hybrid, distributed, highly adaptive routing protocol which is also known as link reversal protocol. TORA uses an arbitrary height metric to establish a direct acyclic graph (DAG) and the length of the route that physically (DAG) rooted at the destination. Consequently, multiple routes often exist for a given destination but none of them are necessarily the shortest route. Instead of using the shortest path for computing the routes, the TORA algorithm maintains the direction of the next destination to forward the packets. Thus a source node maintains one or more downstream. TORA reduces the control messages in the network by having the nodes to query for a path only when it needs to send a packet to a destination. In TORA three steps are involved in establishing a network.

• •     Creating the routes from source to destination,

• •     Maintaining the routes

• •     Erasing invalid routes.

Initially to create a route, the source node broadcasts a QUERY packet to its neighbours. This QUERY is rebroadcasted through the network until it reaches the destination or an intermediate node that has a route to the destination. The recipient of the QUERY packet then broadcasts the UPDATE packet which lists its height with respect to the destination. When this packet propagates in the network, each node that receives the UPDATE packet sets its height to a value greater than the height of the neighbour from which the UPDATE was received. This has the effect of creating a series of directed links from the original sender of the QUERY packet to the node that initially generated the UPDATE packet. When a node discovers that the route to a destination is no longer valid; it will adjust its height so that it will be a local maximum with respect to its neighbours and then transmits an UPDATE packet. If the node has no neighbours of finite height with respect to the destination, then the node will attempt to discover a new route. As shown in Fig. 5, node 6 does not propagate QUERY from node 5 as it has already seen and propagated QUERY message from node 4 and the source may have received a UPDATE each from node 2, it retains                     that                     height.

Figure 5: Route Creation in TORA

When a node detects a network partition, it will generate a CLEAR packet that results in reset of routing over the ad hoc network. The establishment of the route is based on the DAG mechanism thus ensuring that all the routes are loop free. Packets move from the source node having the highest height to the destination node with the lowest height like top-down approach.

• D.    Dynamic Source Routing (DSR)

This is an on-demand routing protocol based on source routing concept. In DSR mobile nodes stores source routes in it caches for which mobile device are aware. When new routes are learned by nodes entries of cache is updated for these new routes. DSR uses no periodic routing messages (e.g. no router advertisements), thereby reducing network bandwidth, conserving battery power and avoiding routing updates through ad-hoc network. Instead DSR relies on support from Medium Access Control (MAC) layer (MAC layer should inform routing protocol about link failures).

Working of this protocol can be divided in two parts.

• (a)    Route discovery

• (b)    Route maintenance.

Route Discovery: When a mobile node need to send any packet it first consults with its route cache that whether it already have a route for destination. If an unexpired route is present it sends the packet using this route. But if node does not have such route it initiates broadcasting of route request packet. This route request message contains the address of the destination, along with the source node's address and a unique identification number. Each node that receive that packet check it cache to know whether a route for this destination exists or not. If route does not exists it adds it own information to the packet and send it to outgoing link. To limit the number of route requests propagated on the outgoing links of a node, a mobile only forwards the route request if the request has not yet been seen by the mobile and if the mobile's address has not already appeared in the route record. A reply packet is generated when request packet either reach to destination node or it reach to an intermediate node who have unexpired route for destination in its cache. By the time the packet reaches either the destination or such an intermediate node, it contains a route record yielding the sequence of hops taken [17], [11]. As seen in Fig. 6, when a source node S wants to send packet to destination D, it initiated route discovery mechanism in which Source node S broadcasts a ROUTE REQUEST packet which in controlled manner is flooded through the network and answered in the form of ROUTE REPLY packet by destination node or from the node which has the route to destination.

Route Maintenance: Route Maintenance is a mechanism by which a packet sender S detects if the network topology has changed so that it can no longer uses its route to destination D. This might happens when a host listed in a source node, move out of wireless transmission range or is turned off making the route unusable. A failed link is detected by either actively monitoring acknowledgments or passively by running in promiscuous mode, overhearing that packet is forwarded by neighbouring node. As seen in Fig. 6, the failed link is notified to the source node S with ROUTE ERROR packet. The source node s can use any other known route to Destination D or the process of route discovery is initiated again to find new route to destination [18].

S    B    C D

Route

Discovery

Route

Maintenance

Broadcast ROUTE REQUEST

ROUTE REPLY

Data Sent

Data Sent

S

S, B

S, B, C

S, B

S, B, C

S, B, C,D

S, (B), C, D

S, B,( c), D

S, B, C, (D)

Forwarding fails

ROUTE

ERROR

C moves away

B-C

Dead

Figure 6: DSR Route Discovery and Route Maintenance

• E.    Destination-Sequenced Distance-Vector Routing (DSDV)

DSDV [12] is also unicast, table driven, proactive MANET protocol used for routing based on BellmanFord algorithm with improved routing mechanisms to obtain good performance [19]. It is an enhancement to distance vector routing for ad-hoc networks. DSDV is basically a distance vector with small adjustments to make it better suited for ad-hoc networks. These adjustments consist of triggered updates that will take care of topology changes in the time between broad casts.

Every node consists of two routing tables that are forwarding packets and advertised packets (incremental routing packets) to obtain imminent routing information probability to suit best metric

DSDV routing table entry contains information about next hop destination address, a complete cost metric of destination routing path and sequence number. Destination creates a sequence number in DSDV for distinguish between stale and fresh routes to avoiding loops.

Periodic updates of routing tables occur by every node which contains routing information of neighbours. If significant change had been done from the previous update a new routing table is transmitted by a node as event triggered style.

DSDV is more efficient then link state algorithm due to less computation and storage space, however this algorithm might cause short and long lived loops since nodes selects next hop in distributed fashion that can be incorrect due to stale routes. Modification made in the algorithm reduces some looping problems by explicitly implementing inter-nodal coordination protocol for nodes.

The routing information is mainly done through multicasting or broadcasting in a periodical packet updates when change in the topology is detected. DSDV requires every node to advertise its routing table to its every current neighbour time to time based on approximation such that every node always locate other node in the network when required. In wireless networks broadcasting has limited range because of wireless medium physical characteristics as compared to wired networks. Every broadcast data contains a sequence number with the following information [19]:

• •    Destination address.

• •    Number of hops towards destination (route metric).

• •    Sequence number originally allocated by destination.

• •    Next hop address

In this a sequence number is used to tag each route. In the routes that contain fresh sequence numbers provides basis in forwarding decisions since it has enhanced metric. Source node has always multiple routes towards same destination with fresh sequence number and enhanced metric, with previous sequence number and worst metric. A route with higher sequence number is more favourable than a route with lower sequence number. However, if two routes have the same sequence number, the route with fewer hops is more favourable.

In case of route failure, its hop number is set to infinity and its sequence number is increased to an odd number where even numbers are reserved only to connected paths.

To reduce the amount of information in each packet there are two type of message are defined: Full and incremental dump [19]. The full dump carries all the available routing information and incremental dump carries the information that has changed since last dump.

• V. PERFORMANCE METRICS

• •    Average  End-to-End  Delay:  This metric

represents average end-to-end delay. It indicates how long it took for a packet to travel from the source to the application layer of the destination. It includes all possible delay caused by buffering during route discovery latency, transmission delays at the MAC, queuing at interface queue, and propagation and transfer time. It is measured in seconds [20], [2].

• •    Packet Delivery Ratio: Packet delivery ratio is calculated by dividing the number of packets received by the destination through the number of packets originated by the application layer of the source (i.e. CBR source). It specifies the packet loss rate, which limits the maximum throughput of the network [20], [2].

• •    Normalized Routing load: It is defined as Number of routing packets “transmitted” per data packet “delivered” at destination. Each hop-wise transmission of a routing is counted as one transmission. It is the sum of all control packet sent by all node in network to discover and maintain route. [2].

• •    Throughput: It is the ratio of total amount of data which reaches the receiver from sender to the time it takes for receiver to receive the last packet. It is represented in bits per seconds [5].

• •    Packet Jitter: It is the variation in the delay of received packets. At the sender they are evenly spaced intervals, but due to traffic congestion, improper queuing or configuration errors they come at unequal intervals.

• VI.    SIMULATION TOOL

The tool used for simulation is NS-2 which is highly preferred by research communities. The network simulator version 2 (NS-2) is a package of tools that simulates behaviour of networks. It is a discrete event network simulator developed at UC Berkeley that focuses on the simulation of IP networks on the packet level. It can simulate both wired and wireless network. Wireless network research in the last years is often based on simulation. Ns-2 is a widely used wireless network simulation tool for this purpose [21]

It uses three types of files namely Tool Command Language file (.tcl), Trace file (.tr) and Network Animator file (.nam). Tool command language file (.tcl) has subsets of commands which are written into it for simulation. While simulator runs on .tcl, simulation trace file (.tr) and animation file (.nam) are created during the session. Trace file (.tr) is used to trace the whole process and Network Animator file (.nam) is used to visualize the behaviour of network protocols and traffic the model.

• VII.    RESULTS & CONCLUSIONS

For comparing the performance of all the five protocols, two scenarios have been taken. First scenario is low mobility and low traffic and second scenario is high mobility and high traffic.

Table I. Low Mobility and Low Traffic

	AODV	OLSR	TORA	DSR	DSDV
Jitter(sec)	3.73	0.39	0.59	58.91	0.39
Average Delay(sec)	39.84	6.29	9.74	673.65	8.43
Throughput (bps)	251.37	177.15	230.88	244.54	237.09
Normalized Routing load	0.003	0.007	0.020	0.005	0.001
Packet Delivery Fraction	0.9200	0.6483	0.8450	0.893	0.8660

Table II. High Mobility and High Traffic

	AODV	OLSR	TORA	DSR	DSDV
Jitter(sec)	226.5	5.53	698.8	649.9	9.09
Average Delay(sec)	2706.3	2597.2	3796	2786.7	2602.19
Throughput (bps)	149.92	231.15	233.8	146.4	338.72
Normalized Routing load	0.027	0.032	0.045	0.025	0.005
Packet Delivery fraction	0.0360	0.0342	0.0843	0.0545	0.471

By observing the table I and II, it is found that AODV has maximum throughput under low traffic and DSDV has maximum throughput under high traffic. As network becomes dense OLSR, DSR and DSDV perform well in terms of Throughput than AODV and TORA. TORA performs well in dense networks in terms of packet delivery fraction but at the same time Normalized Routing load of TORA is maximum among all the protocols in both the networks. DSDV has least Normalized Routing load in both low and high traffic. OLSR and DSDV give the least Jitter and Average Delay in both networks

Low delay and low jitter are mainly required in voice applications (i.e. Voice over Internet Protocol (VOIP)) and real time applications (i.e. real time multi player games in mobile ad hoc environment), so OLSR and DSDV can be used there. The least the value of Normalized Routing load, least will be the wasted portion of BW that is used for exchange of routing message between nodes and more will be the BW available for transferring data between nodes. The applications like voice and video conferencing need more BW, so in this case DSDV can be used. The applications like video telephony, web games, etc. require high throughput, so in this case AODV can be used under low mobility and low traffic and DSDV can be used under high mobility and high traffic. There is high mobility of users and network nodes at the time of emergency and military operations. We have observed that as the mobility increases there is an improvement in the throughput of OLSR, DSR and DSDV. So these three protocols can be used in emergency and military applications.