Abstract: Mobile Ad hoc-networking (MANET) is becoming increasingly important in today’s world and a number of protocols have been developed for them. However a comparison between them is lacking to help determine an optimal one. This study addresses this issue by comparing the relative performance of four key Ad hoc routing protocols; Destination-sequenced distance vector (DSDV), Temporally ordered routing algorithm (TORA), Dynamic source routing (DSR) and Ad hoc on-demand distance vector (AODV). This study subjected the protocols to identical loads and environmental conditions and evaluate their relative performance with respect to end-to-end throughput and delay, control packet overhead and route acquisition time. From the detailed simulation results and analysis of presented, an appropriate choice of routing protocol can be made for given network context and goal.
INTRODUCTION
An Ad hoc wireless network is one that does not need any base station or wired backbone infrastructure. Communication is directly between nodes or through intermediate nodes acting as routers. In some application environments, such as battlefield communications, national crises, disaster recovery (fire, flood, earth quake) the wired network is not available and Ad hoc networks provide the only feasible means for communications and information access. Also Ad hoc network is now playing important role in civilian forums such as campus recreations, conferences, electronic classrooms etc.
Ad hoc routing has been an active research topic in the mobile and wireless area for at least a decade. As mobile and wireless technology proliferate, this area is receiving more attention and there are more industry and standards effort such as Internet engineering task force (IETF’s) MANET group, Asynchronous transfer mode (ATM) forum and a number of efforts in third-generation wireless standards. Routing protocols for Ad hoc networks can be classified into two main categories: (1) Proactive or table-driven and (2) Reactive or on-demand. In table-driven protocols each node maintains tables that store routing information. Changes in network topology trigger propagating updates throughout the network in order to maintain a consistent network view. The protocols in this area differ in the number of tables contain as well as the details of how they are updated. For example, nodes in Destination-sequenced distance vector (DSDV) algorithm maintain route information to every other node in the network. As the network status changes, full updates are exchange among all nodes. The Wireless routing protocol (WRP) localizes the updates to the immediate neighbors. And Cluster gateway switch routing (CGSR) protocol reduces the size of the tables and amount of information propagation by having each cluster of nodes elect a cluster head.
On-demand routing protocols are characterized by a path discovery mechanism that is initiated when a source needs to communicate with a destination that it does not know how to reach. The route discovery is usually in the form of query flood. The differences between on-demand protocols are in the implementation of the path discovery mechanism and optimizations of it. Dynamic source routing (DSR) uses source routing, with every packet carrying the full path information with it. Similarly, Ad hoc on-demand distance vector routing (AODV) is an on-demand version of DSDV where the path results in exchange of the portions of the routing table necessary for establishing the route. Other on-demand algorithms include temporally ordered routing algorithm (TORA) that discovers multiple paths from a source to destination and re-initiates discovery only when all of them have failed. Associativity based routing (ABR) incorporates route quality by preferring hops that have been static for a long period. Similarly, signal stability routing (SSR) prefers routes with strong received signal power.
Present research work studied the relative performance of four of these protocols (DSDV, TORA, DSR and AODV) with the aim of finding out under which network conditions a protocol is most suitable.
Destination-sequenced distance rector (DSDV): DSDV is a table-driven protocol, wherein each node maintains a routing table listing the “next hop” for each reachable destination.
Every node in DSDV periodically broadcasts its routing table with monotonically increasing even sequence number. When a node B detects that it link to a destination D has broken, it advertises the route to D with an infinite metric and a sequence number one greater than its sequence number for the route that has broken (making an odd sequence number). This cause any node ‘A’ routing packets through ‘B’ to incorporate the infinite-metric route into its routing table until node A hears a route to D with a higher sequence number.
Temporally ordered routing algorithm (TORA): TORA[1,2] is an on-demand routing protocol design to provide loop-free and multiple routes (to alleviate congestion) and yet minimize communication overhead by localizing algorithmic reaction to topological changes when possible (to conserve bandwidth and increase scalability). Moreover, it is desirable to detect network partition and delete invalid routes.
In TORA when a node needs a route to a particular destination, it broadcasts a query packet containing the address of the destination. This packet propagates through the network until it reaches either the destination or an intermediate node having a route to the destination. The recipient of the query then broadcasts an update packet listing its height with respect to the destination. As this packet propagates through the network, each node that receives the update sets it height to a value greater than the height of the neighbor from which the update was received. This has the effect of creating a series of directed links from the original sender of the query to the node that initially generated the update.
When a node discovers that a route to a destination is no longer valid, it adjusts its height so that it is a local maximum with respect to its neighbors and transmits an update packet. When a node detects a network partition, it generates a clear packet that resets routing state and removes invalid routes from the network.
Dynamic source routing (DSR): DSR[3,4] is an on-demand routing protocol wherein the source determines the ordered list of nodes through which a packet must pass while traveling to its destination. The key advantage of source routing is that intermediate nodes do not need to maintain up-to-date routing information in order to route the packets they forward, since the packets themselves already contain all the routing decisions. This fact, coupled with the on-demand nature of the protocol, eliminates the need for the periodic route advertisement and neighbor detection packets present in other protocols.
Whenever a source has a packet to transmit, it checks its route cache for a route to the destination. In case a route is not found then a route request is broadcast across the network. On receiving this request, an intermediate node without a cache route to the destination appends its address to the request packet and rebroadcast it until the request packet reaches the destination.
If any intermediate node has a cache route to the destination then it will discard the request and will send route reply back to the source. Otherwise, the destination will send a route reply to the source containing the route from the source to the destination. When the reply packet reaches the source a connection is established and all subsequent packets contain the complete route in the packet header.
If any link on a source route is broken, the source node is notified using a route error (RERR) packet. The source removes any route using the link from its cache and initiates a new route discovery if this route is still needed.
Ad hoc on-demand distance vector (AODV): AODV[5] is essentially a combination of DSR and DSDV. It borrows the basic on-demand mechanism of route Discovery and Route maintenance from DSR, plus the use of hop-by-hop routing, sequence number and periodic beacon from DSDV. When a source S needs a path to some destination D, it broadcasts a route request message enclosing the last known sequence number to that destination. The route request is broadcasted across the network until it reaches a node that has a route to the destination with the destination sequence number higher than that enclosed in the request. Each node that forwards the route request creates a reverse route for itself back to node S. when the route request reaches a node with a route to D, that node generates a route reply that contains the number of hops necessary to reach D and the sequence number for D most recently seen by the node generating the reply. Each node that participates in forwarding this reply back forward the originator of the route request (node S) creates a forward route to D. The state created in each node along the path from S to D is hop-by-hop state that is, each node remembers only the next hop and not the entire route as would be done in source routing.
In order to maintain routes, AODV normally requires that each node periodically transmit a HELLO message, with a default rate of once per second. Failure to receive three consecutive HELLO message from a neighbor is taken as an indication that the link to the neighbor in question is down.
When a link goes down, any upstream node that has recently forward packets to destination using that link is notified via an unsolicited route reply containing an infinite metric for that destination. Upon receipt of such a route reply, a node must acquire a new route to the destination using route discovery.
Simulation model: In this study used the extended version of UCB/LBNL network simulator ns-2[6] and simulate a virtual environment of 1200 * 300 m for 600 sec of simulation time. The channel data rate and transmission range set to 2 Mbps and 250 m, respectively. Each run of the simulator accepts as input a scenario file that describes the exact motion of each node and the exact time at which each change in motion or packet origination is to occur. A total of 280 different scenario files with varying network size, movement patterns and traffic loads were generated and then all four of the routing protocols were run against each of these scenario files.
Traffic and movement pattern: The nodes in the simulation move according to the ‘random way point’ model. At the start of the simulation, each node waits for a pause time, then randomly selects and moves towards a destination with a speed randomly lying between zero and some maximum speed. On reaching this destination it pauses again and repeats the above procedure till the end of the simulation. The simulations run with maximum speed of 1.5 and 20 ms-1 and pause times of 0, 10, 50, 100, 200, 300 and 600 sec. A pause time of 0 sec correspond to the continuous motion of the nodes and in a pause 600 sec the nodes are stationary. Traffic sources are constant bit rate (CBR), with sending rate of 2 packets per second, 10 CBR source and packet size of 512 bytes.
Simulation study on one or more of the four routing protocols (DSDV, AODV, TORA and DSR) has been presented in earlier works[7,8]. However present work is quite different from all of them in the input parameters and simulation objectives. Most of them did not include the extensions by CMU research group in their ns-2 simulation. Thus their simulation lacked the realistic model of radio propagation, medium access, collision and physical node mobility. These missing pieces greatly simplify the routing problem as propagation delay; capture effects, MAC-layer collision and the effects of congestion due to large packet sizes are unaccounted for.
Present findings are in close agreement of Broch et al.[8], Perkins et al.[9] and Maltz[10] as they used the same ns-2 based simulation environment.
Broch et al.[8] the original authors of the simulation model, evaluated the four ad hoc routing protocols but with an earlier version of AODV (without the query control optimizations). They used only 50 nodes with traffic loads of 4 pks/s; 10-30 CBR Source, 64 bytes packet, generating a total of 210 scenario files.
Perkins et al.[9] evaluate two of the routing protocols DSR and AODV with a fixed number of nodes for each field configuration.
Ahuja et al.[11] simulated and compared the performance of TCP over DSR, DSDV, AODV and SSA. They used a 25-node model and 250 scenario files.
The main difference between present work and the above studied works is that we simulated a more dynamic environment with varying network size (Node number 30 and 60), Rate of topology change (max speed 1.5 and 20 ms-1), generating a total of 280 scenario files. Also there are some major differences on the compared performance metrics.
RESULTS AND DISCUSSION
In order to compare the performance of the four routing protocols we evaluate them with respect to the following metrics:
Throughput or packet delivery ratio: The ratio between the number of packets sent out by the sender application and the number of packets correctly received by the corresponding peer application.
| Fig. 1a-d: | Route acquisition time for varying pause time |
Average end-to-end delay or mean overall packet latency: This implies the delay a packet suffers between leaving the sender application and arriving at the receiver application.
Routing overhead: The total number of routing packets transmitted during the simulation.
Route acquisition time: The time it takes a source node to find a route to a destination node.
The performance of each algorithm depends heavily on the simulation scenario, but there are some trends, that suggest that some algorithms are generally superior to others.
Figure 1 a-d highlight route acquisition time for varying pause time. DSDV as a proactive routing protocol with nodes having readily available route to all other destination in their routing table, performs quite predictably, having a constant route acquisition time very close to zero for all mobility rate and movement speed.
The others TORA, DSR and AODV being reactive routing protocols shows an increase in route acquisition time for increased network speed, as many packets will be in interface queue, while routing protocols try to find valid route to destination. DSR being purely on-demand, spend the most time in route finding. AODV a combination of DSDV+DSR tries to be aware of its link status with neighbors thus route acquisition time is relatively low.
Figure 2 a-d, showed the graphs for average packet delay vs pause time. From these graphs we see that the average packet delay increase for increase in network speed and number of nodes, because of packets waiting in interface queue while routing protocols try to find valid route to the destination.
| Fig. 2a-d: | Graphs representing average packet delay vs. pause time |
TORA has the worst delay characteristics because of the loss of distance information with progress. Irrespective of mobility rate and movement speed TORA is outran by the others. Also in TORA route reconstruction may not occur quickly. These leads to potential lengthy delays while waiting for new routes to be determine. DSDV as expected suffer the least delay. In DSR route recovery is fast, therefore shows a better delay performance than the other reactive protocols at low pause time (high mobility) (Fig. 2a and 2b). But in high collision traffic (high speed, low pause time) DSR control messages get loss thus eliminating its advantage of fast establishing new route. Under such situation DSR have a relatively higher delay more than AODV, but delay however decrease with increase pause time (Fig. 2c and 2d).
Figure 3 a-d showed the graphs for control overhead vs pause time. Control overhead is important because it determines the scalability of the protocol, it performance in low-bandwidth /congested environment and it efficiency in terms of consuming node battery power. From these graphs we see that control packet overhead increase for increase number of nodes, mobility rate and movement speeds. DSR showed the best performance, having a relatively lower routing overload for all cases. The overhead for DSR is fairly constant despite movement rate or load offered.
DSDV perform the worst at high movement speed and for a large number of nodes. It performance improves for small networks with low mobility rate and movement speed (Fig. 3c and 3a). TORA show a better best performance for large networks with high mobility rate and movement speed (Fig. 3b and 3d).
Figure 4 a-d showed the graphs for throughput vs pause time. Throughput describes the loss rate as seen by the transport layer. It shows the completeness and correctness of the routing protocol.
| Fig. 3a-d: | Graphs for control overhead vs. pause time |
| Table 1: | Numerical comparison of the four routing protocols |
From these graphs it can see that throughput decrease for increase in network speed and mobility rate. This is because the packet drop at such high load traffic is high. DSDV at low pause time (high mobility) performs poorly, but as pause time increase it performance increase and prove to be one of the best at high pause time (low mobility). TORA performs better at high-speed high mobility (Fig. 4c and 4d). But in other cases shows to have the worst throughput. AODV in our simulation experiment shows to have the overall best performance.
Table 1 shows a numerical comparison of the four protocols, “1” for the best up to “4” for the worst.
CONCLUSIONS
This study compared the relative performance of four key Ad hoc routing protocols DSDV, TORA, DSR and AODV and from the simulation results can summaries the suitability of each of the protocol as follows:
DSDV is most suitable for small networks where changes in the topology are limited. Also DSDV could be considered for delay constraint networks.
TORA is suitable for operation in large highly dynamic mobile network environment with dense population of nodes. The main advantage of TORA is its support for multiple routes and multicasting.
| Fig. 4a-d: | Graphs for throughput vs. pause time |
Thus TORA often serve as the underlying protocol for lightweight adaptive multicast algorithms.
DSR is suitable for networks in which the mobiles move at moderate speed. It had lowest control overhead in terms of number of control packets. This makes it suitable for bandwidth and power constraint network. However in terms of byte DSR has a significant overhead as it packets size are large carrying full routing information.
AODV in this simulation has the best all round performance. It is an improvement on DSDV and DSR and has the advantages of both of them.