Keywords

1 Introduction

Ad hoc network is a collection of wireless mobile nodes forming a temporary network without any existing wire-line infrastructure. Communication between nodes is based on radio to radio multi-hoping.

Due to the infrastructure less (Bing Lin et al. 2000; Sarkar et al. 2008), self-configuring network property, and absence of a central governing authority, MANETFootnote 1 has wide application in industrial and commercial field involving cooperative mobile data exchange, inexpensive alternatives, or enhancement to cellular-based mobile network infrastructures. MANET has potential applications in the locations where setting of infrastructure networks is not possible. Military ad hoc networks detect and gain as much information as possible about enemy movements, explosions, and other phenomena of interest. Such kind of network also has applications in emergency disaster relief operations after natural hazards like hurricane or earthquake.

Some of the wireless traffic sensor networks monitor vehicle traffic on highways or in congested parts of a city. Wireless surveillance sensor networks may be deployed for providing security in shopping malls, parking garages, and many such other areas where direct or wired communication cannot be made.

Ad hoc networks are also characterized by frequent topology change due to mobility of nodes. Nodes may join and leave the network at any time. All nodes in such networks behave as routers and take part in discovery and maintenance of routes to the other nodes in the network. Ad hoc networks have to deal with many challenges and the one that is most important is route selection.Footnote 2 So the routing algorithm must be dynamic and must be adaptive to the frequent topology changes due to node mobility. Many algorithms have been proposed in the literature that can be used in ad hoc networks for finding routes.

The ad hoc routing protocols are divided into three categories:

Proactive routing protocol: These are also known as table-driven protocols and will actively determine the layout of the network. Through a regular exchange of network topology packets between the nodes of the network, at every single node, an absolute picture of the network is maintained.

Reactive routing protocol: These are also called on-demand routing protocols and start to set up routes on-demand. The routing protocol will try to establish such a route, whenever any node wants to initiate communication with another node to which it has no route. Unlike proactive routing protocols, reactive protocols do not generate sustained routing overhead.

Hybrid routing protocol: A hybrid routing protocol is the one that combines the best features of proactive and reactive protocols. It reduces the control overhead of proactive routing protocols and decreases the latency caused by route discovery in reactive routing protocols.

Several performance evaluations of MANET routing protocols using CBR and TCP traffic have been done in the literature (Harminder et al. 2010; Kumar et al. 2009) by considering various parameters such as mobility, network load, and pause time. Bindra et al. (2010) compared the two reactive routing protocols, ad hoc on-demand distance-vector routing (AODV) and dynamic source routing (DSR) by using group mobility model with CBR and TCP traffic sources and observed that AODV gives better performance in CBR traffic and real-time delivery of packet. DSR gives better results in TCP traffic and under restricted bandwidth condition. Also Kumar et al. (2009) investigated AODV and DSR routing protocols under random way point mobility model with CBR and TCP traffic sources. They concluded that AODV outperforms DSR in high-load and/or high-mobility situations. Jayakumar and Gopinath (2008) have observed that in dense networks of Manhattan grid model with CBR traffic, the packet delivery ratio for AODV and DSR is relatively near to one another. DSR, however, has very bad results in network latency making AODV favorable choice in more dense networks.

In this paper, we present performance comparison of two reactive routing protocols DSR, AODV and destination-sequenced distance-vector routing (DSDV) (Jayakumar and Gopinath 2008; Jeya Kumar and Rajesh 2009; Feng et al. 2009) to bring out their relative merits. Two are on-demand protocols, and they initiate their routing activities only when required. The motivation behind this comparison is to understand their internal working mechanism and bring out situations where one is preferred than the other and the other is table driven.

There are various mobility models such as random way point (Kumar et al. 2009), reference point group mobility model (RPGM) (Bindra et al. 2010), Manhattan mobility model (Jayakumar and Gopinath 2008), freeway mobility model, Gauss–Markov mobility model that have been proposed for evaluation. Many previous studies have used random way point or reference point group mobility as reference model. In this study, we will make a detailed study based on Manhattan mobility model.

2 Routing Protocols for MANETs

2.1 Dynamic Source Routing

The main feature of DSR is the use of source routing. That is, the sender knows the complete route from source to destination including all intermediate hops. These routes are stored in a route cache. The data packets carry the source route in the packet header. When a node in the ad hoc network attempts to send a data packet to a destination for which it does not already know the route, it uses a route discovery process to dynamically determine such a route. Route discovery works by flooding the network with route request (RREQ) packets. Each node receiving a RREQ, rebroadcasts it, unless it is the destination or it has a route to the destination in its route cache. Such a node replies to the RREQ with a route reply (RREP) packet that is routed back to the original source. RREQ and RREP packets are also source routed. The RREQ builds up the path traversed so far.

The RREP routes itself back to the source by traversing this path backwards. The route carried back by the RREP packet is cached at the source for future use.

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 this link from its cache. A new route discovery process must be initiated by the source, if this route is still needed. DSR makes very aggressive use of source routing and route caching. No special mechanism to detect routing loops is needed. Also, any forwarding node caches the source route in a packet it forwards for possible future use.

Promiscuous listening: When a node overhears a packet not addressed to itself, it checks whether the packet could be routed via itself to gain a shorter route. If so, the node sends a gratuitous RREP to the source of the route with this new, better route. Aside from this, promiscuous listening helps a node to learn different routes without directly participating in the routing process.

The DSR protocol is composed of two main mechanisms that work together to allow discovery and maintenance of source routes in MANET.

Route Discovery: When a source node S wishes to send a packet to the destination node D, it obtains a route to D. This is called route discovery. Route discovery is used only when S attempts to send a packet to D and has no information of a route to D.

Route Maintenance: When there is a change in the network topology, the existing routes can no longer be used. In such a scenario, the source S can use an alternative route to the destination D, if it knows one, or invoke route discovery. This is called route maintenance.

2.2 Ad Hoc on-Demand Distance-Vector Routing

AODV inherits the property of both DSR and DSDV protocols. It borrows the basic on-demand mechanisms of route discovery and route maintenance from DSR, plus the use of hop-by-hop routing, sequence numbers, and periodic principal of DSDV. It provides loop-free path and avoids Bellman-Ford count to infinity, and the convergence is also fast when the topology changes. RRREQ, RREP, and RERR are the message types defined by AODV. When a route to a new destination is needed, the node broadcasts a RREQ to find a route to the destination. In case of link break in an active route, a RERR message is used to notify other nodes that the link failure has occurred. AODV is a reactive protocol, and it deals with route table management.

2.3 Destination-Sequenced Distance-Vector Routing

DSDV protocol is a table-driven algorithm based on the classical Bellman-Ford routing mechanism. The improvements made to the Bellman-Ford algorithm include freedom from loops in routing tables. Every mobile node in the network maintains a routing table in which all of the possible destinations within the network and the number of hops to each destination are recorded. DSDV tags each route with a sequence number and considers a route r more favorable than r′ if r has a greater sequence number or if both have the same sequence number but as a lower metric (hop count).

Each entry is marked with a sequence number assigned by the destination node. The sequence numbers enable the mobile nodes to distinguish stale routes from new ones, thereby avoiding the formation of routing loops. Mobile nodes maintain an additional table where they store the data sent in the incremental routing information packets.

New route broadcasts contain the address of the destination, the number of hops to reach the destination, the sequence number of the information received regarding the destination, as well as a new sequence number unique to the broadcast. The route labeled with the most recent sequence number is always used. In the event that two updates have the same sequence number, the route with the smaller metric is used in order to optimize (shorten) the path. Mobiles node also keep track of the settling time of routes, or the weighted average time that routes to a destination will fluctuate before the route with the best metric is received. By delaying the broadcast of a routing update by the length of the settling time, mobiles node can reduce network traffic and optimize routes by eliminating those broadcasts that would occur if a better route was discovered in the very near future

3 Manhattan Grid Mobility Model

Fan Bai, Narayanan, and Ahmed Helmy introduced the Manhattan model to emulate the movement pattern of mobile nodes on streets (Jayakumar and Gopinath 2008). It can be useful in modeling movement in an urban area where a pervasive computing service between portable devices is provided. The scenario is composed of a number of horizontal and vertical streets. Given below is topography showing the movement of seventeen nodes for Manhattan mobility model.

  1. 1.

    Applications: It can be useful in modeling movement in an urban area where a pervasive computing service between portable devices is provided.

  2. 2.

    Important Characteristics: Maps are used in this model too. However, the map is composed of a number of horizontal and vertical streets. Each street has two lanes for each direction (north and south direction for vertical streets, east and west for horizontal streets). The mobile node is allowed to move along the grid of horizontal and vertical streets on the map. At an intersection of a horizontal and a vertical street, the mobile node can turn left and right or go straight with certain probability.

Thus, the Manhattan mobility model is also expected to have high spatial dependence and high temporal dependence. It too imposes geographic restrictions on node mobility. However, it differs from the freeway model in giving a node some freedom to change its direction. Most of the mobility models mentioned above are parameterized, e.g., SDR and ADR are some of the parameters used in RPGM, while maps are important parameters in the freeway and Manhattan models. There are other prevalent mobility models: Gauss–Markov mobility model, random walk mobility model, etc. (Ariyakhajorn 2006) (Fig. 1).

Fig. 1
figure 1

Topography showing the movement of nodes for Manhattan mobility model

Full size image

4 Simulation Environment

Traffic models: Random traffic connections of CBR and TCP can be set up between mobile nodes using a traffic-scenario generator script. This traffic generator script is available under ~ns/indep-utils/cmu-scen-gen and is called cbrgen.tcl. It can be used to create CBR and TCP traffic connections between wireless mobile nodes. So the command line looks like the following:

  • ns cbrgen.tcl [-type cbr|tcp] [-nn nodes] [-seed seed] [-mc connections] [-rate rate]

For the simulations carried out, traffic models were generated for 50 nodes with CBR traffic sources, with maximum connections of 10 or 40 at a rate of 4 packets per sec, and the packet size is 512 bytes.

Mobility model: The movement of nodes in the Manhattan grid mobility model is generated by the software called Mobility Generator which is based on a frame work called IMPORTANT (Impact of Mobility Patterns on Routing in Ad hoc NeTwork, from University of Southern California).

Implementation: We have used network simulator (NS)-2 in our evaluation. The NS-2 is a discrete event driven simulatorFootnote 3 (Altman and Jimenez 2012) developed at UC Berkeley. We have used Red Hat Linux environment with version NS-2.34 of network simulator. NS-2 is suitable for designing new protocols, comparing different protocols and traffic evaluations. It is an object-oriented simulation written in C++, with an OTcl interpreter as a frontend. NS uses two languages because simulator got to deal with two things: (1) detailed simulation of protocols which require a system programming language which can efficiently manipulate bytes, packet headers, and implement algorithms, (2) research involving slightly varying parameters or quickly exploring a number of scenarios.

Nam is the basic visualization tool used for ns-2 simulations. Using Java program, we analyze the trace file generated, and using MS Excel, we draw the graph.

We have used four traffic patterns with varying number of sources for each type of traffic (TCP and CBR). The goal of our simulation is to evaluate the performance differences of these two on-demand routing protocols. The type of traffic (CBR and TCP) and the maximum number of sources are generated by inbuilt tool of NS2 (M Greis 2010). The parameters used for carrying out simulation are given in the Table 1.

Table 1 Simulation parameters for Manhattan grid mobility model
Full size table

Performance Metrics: RFC2501 (Corson and Macker 1999) describe a number of quantitative metrics that can be used for evaluating the performance of MANET routing protocols. We have used the following metrics for evaluating the performance of two on-demand reactive routing protocols (AODV and DSR):

Packet Delivery Fraction: It is the ratio of data packets delivered to the destination to those generated by the sources. It is calculated by dividing the number of packet received by destination through the number packet originated from source.

$$ {\text{PDF}} = \left( {{ \Pr }/{\text{Ps}}} \right)* 100 $$

where Pr is total packet received and Ps is the total packet sent.

Routing Overhead: It is the total number of control or routing (RTR) packets generated by routing protocol during the simulation. All packets sent or forwarded at network layer is considered routing overhead.

$$ {\text{Overhead}} = {\text{Number}}\;{\text{of}}\;{\text{RTR}}\;{\text{packets}} $$

Normalized Routing Load: 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.

$$ {\text{NRL}} = {\text{Routing}}\;{\text{Packet}}/{\text{Received}}\;{\text{Packets}} $$

Average End-to-End Delay (second): This includes all possible delay caused by buffering during route discovery latency, queuing at the interface queue, retransmission delay at the MAC, propagation, and transfer time. It is defined as the time taken for a data packet to be transmitted across an MANET from source to destination.

$$ {\text{D }} = \, \left( {{\text{Tr }}{-}{\text{Ts}}} \right) $$

where Tr is receiving time and Ts is sending time.

5 Result and Discussion

5.1 Packet Delivery Fraction

In case of CBR traffic, AODV performs well and delivers almost 80 % packets irrespective of high and low load. DSDV delivers around 70 % irrespective of load. It declines slightly with the increasing speed in case of both AODV and DSDV. DSR uses source routing and also caches some routing entries. It is observed that such caching provides a significant benefit up to a certain extent. But at high loads and increasing speed, the PDF declines as shown in Fig. 2.

Fig. 2
figure 2

PDF versus speed (CBR Traffic)

Full size image

For TCP traffic, it is investigated that DSDV performs better than AODV in high or low network load. PDF ratio is nearly 100 % when number of sources is low, the PDF ratio for AODV and DSR is comparable as shown in Fig. 3. Under high load conditions (say 30 sources), when mobility is low, DSR shows better PDF than AODV. This is because DSR uses caching; hence, it is more likely to find a route in cache and perform the route discovery less frequently than with AODV. With the increase in speed, the routes change more frequently and there is a strong need of finding new routes in DSR as well. Over all, the packet delivery fraction is around (87–99 %) in TCP traffic which is better than CBR which is around (30–90 %).

Fig. 3
figure 3

PDF versus speed (TCP Traffic)

Full size image

5.2 Routing Overhead

In case of CBR traffic, the routing load of DSDV is almost similar in high or low network load at all speeds and is low as compared to other two routing protocols as shown in Fig. 4. AODV is comparable at low network traffic, but with more mobility nodes the routing overhead also increases. AODV and DSDV outperforms DSR irrespective of the network load and speed of nodes. Simulation results show that mobility and load affects the performance of AODV and DSR differently. In the presence of high mobility, link failures can happen very frequently. Link failure triggers new route discoveries in AODV since it has almost one route per destination in its routing table. The reaction of DSR to link failures in comparison is mild and causes route discovery less often. The reason is the abundance of cached routes at each node. Thus, the route discovery is delayed in DSR until all cached routes fail. But with high mobility, chances of the caches being stale are quite high in DSR. Eventually when a route discovery is initiated, the large numbers of replies received in response are associated with high overhead. Hence, the cache staleness and high overhead together result in significant degradation in performance of DSR in high-mobility scenarios.

Fig. 4
figure 4

Routing overhead versus speed (CBR Traffic)

Full size image

In TCP traffic, DSDV gives lower routing overheads than AODV at all speeds as shown in Fig. 5. AODV performs better at low network load, but the routing overhead increases at high speed.

Fig. 5
figure 5

Routing overhead versus speed (TCP Traffic)

Full size image

Performance of DSR deteriorates with increasing speed. When nodes are moving fast, there is higher rate of disconnections, which produces more route errors and frequent needs for re-initialization of route discovery process. At high load and at high speeds, performance of DSDV is slightly better than AODV. Over all, the routing overhead in TCP traffic is low as compared to CBR traffic.

5.3 Normalized Routing Load

In case of CBR traffic, AODV and DSDV perform better than DSR irrespective of the network load and speed of nodes as shown in Fig. 6. DSR at low network load substantially increases with increase in speed.

Fig. 6
figure 6

Normalized routing load versus speed (CBR Traffic)

Full size image

In TCP traffic also, AODV and DSDV outperforms DSR irrespective of network load and speed of nodes as shown in Fig. 7. Normalized routing load of AODV and DSDV is comparable. At high network load, performance of DSR is less as compared to low network load. NRL in CBR traffic is high as compared to TCP traffic.

Fig. 7
figure 7

Normalized routing load versus speed (TCP Traffic)

Full size image

5.4 Average End-to-End Delay

In CBR traffic, average delay of AODV is very low as compared to DSR and DSDV as shown in Fig. 8. The delay of DSR has a significant order of magnitude difference. This is highly undesirable for delay-sensitive applications.

Fig. 8
figure 8

E-E delay versus speed (CBR Traffic)

Full size image

In case of TCP traffic, performance of AODV and DSDV is comparable and both outperform DSR in high or low network load conditions and at all speeds as shown in Fig. 9. Over all, AODV is the best choices for real-time delivery of packet in both types of traffic. The average delay in TCP traffic is low as compared to CBR traffic.

Fig. 9
figure 9

E-E delay versus speed (TCP Traffic)

Full size image