An Ad hoc mobile network is a collection of mobile nodes that are capable of changing on a continual basis. In order to facilitate communication within a network, a routing protocol is used to discover routes between nodes. The primary goal of an ad hoc network routing protocol is to establish correct and efficient route between two nodes so that message may be delivered in time. In this research we have studied the performance of three routing protocols (DSDV, DSR and AODV) and evaluated its performance based on a given set of parameters. Here we presented the characteristics and functionality of all three protocols and the comparison.
PDF Abstract XML References Citation
How to cite this article
With recent technological advancements, the wireless and mobile computing devices such as laptops have become increasingly widespread and popular in everyday business and personal life. Often mobile user may meet under circumstances where there is no fixed infrastructure to enable communication among them. In such cases they can form a Mobile Ad hoc Network (MANET) to communicate with each other. A MANET is a collection of wireless mobile host forming a temporary network with out the aid of any centralized administration. Ad hoc network form self organizing architecture that are rapidly deployable and that are adaptable to propagation condition and to the network traffic and mobility patterns of the network nodes. The most distinguishing characteristics of ad hoc network are the absence of fixed infrastructure. Other characteristics include multihop routing and relatively changing topology. Many Routing Protocols[2-5] are proposed for MANET have been proposed in the literature.
The high mobility, low bandwidth, and limited computing capability of mobile hosts make the design of routing protocols more challenging. The protocols must be able to keep up with the drastically and unpredictably changing network topology, with minimized message exchanges, in an efficient way.
The routing protocols may be categorized as proactive, on-demand, and hybrid, according to the way the mobile hosts exchange routing information. The proactive protocols, such as DSDV and Source Tree Adaptive Routing (STAR), periodically disseminate routing information among all the hosts in the network, so that every host has the up-to-date information for all possible routes. On-demand routing protocols, such as AODV and Dynamic Source Routing (DSR), operate on a need basis, discover and maintain only active routes that are currently used for delivering data packets. Hybrid routing protocols, such as Zone Routing Protocol (ZRP), maintain a virtual routing infrastructure, apply proactive routing mechanisms in certain regions of a network and on-demand routing in the rest of the network.
Ad hoc networks are too complex to allow analytical study for explicit performance expressions. We use the means of simulation to evaluate the routing approaches numerically and gather data to estimate their characteristics. We study the performance of DSDV, DSR and AODV in a wide range of network contexts with varied network size, mobility, and traffic load. This study subjected the protocols to identical loads and environmental conditions and evaluates 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, an appropriate choice of routing protocol can be made for given network context and goal. This analysis also provides guidelines to improve the performance of these protocols.
Several simulation-based performance comparisons have been done for ad hoc routing protocols in the recent years. Das et al. evaluated performance of ad hoc routing protocols based on the number of conversations per mobile node using Maryland Routing Simulator (MaRS). The performance comparison of two on-demand routing protocols: DSR and AODV is presented, using NS-2 (Network Simulator) for the simulation. The pause time and the offered traffic load are taken as parameters. Jiang and Gavcia-Luna-Aceves showed that, Glo-MoSim is used for the performance study of the STAR, AODV and DSR routing protocols, taking the pause time as the parameter. The simulating the same protocol in different simulators may produce differences in the results. The performance of two location-based routing protocols for ad hoc networks is investigated by using NS-2 and the effect of average moving speed in different scenarios is presented by Camp et al.. Present study is to comprehensively investigate the characteristics DSDV, DSR and AODV protocols. In addition to identifying the suitable network contexts for each approach, we explore the causes for performance degradation.
ROUTING PROTOCOLS FOR MANET
Destination Sequenced Distance Vector Routing: DSDV is a table Driven or Proactive Algorithm based on the classical Bellman-Ford Or Routing Information protocol (RIP) routing mechanism. The improvement made to the Bellman-Ford algorithm includes freedom from loops in routing tables by using the concept sequence number. DSDV is a hop-by-hop distance vector routing protocol. Each node has a routing table that for all reachable destination stores the next hop and number of hops for that destination. Like Distance Vector, DSDV requires that each node periodically broadcast routing updates. The sequence number shows the freshness of a route and routes with higher sequence number are favourable. For routes with the equal sequence number, the one with the smallest distance metric is chosen.
Assume that node B receives routing information from E about a route to node G. Let S(B) and S(E) denote the sequence number for node G as stored at node B, and as sent by node E with its routing table to node B, respectively. Node B takes the following Steps:
If S(B) > S(E), then B ignores the routing information received from E.
If S(B) = S(E) and cost of going through E is smaller than the route know to B, then B sets E as the next hop node to G.
If S(B) < S(E), then B sets E as the next hop node to G and S(B) is updated to equal S(E).
Each time a host sends an update to its neighbors, its current sequence number is incremented and included in the update. The sequence number is disseminated throughout a network via update messages. DSDV requires each host to periodically advertise its own routing table to its neighbors. Updates are triggered when significant new routing information is available. Routes received in broadcasts are used to update the routing table. The receiver adds an increment to the metric of each received route before updating.
To avoid periodic updates, which generate large amount of network traffic, DSDV supports full dump and incremental dump. The full dump carries all available routing information and the incremental dump that carries the information that has changed since the last dump.
Dynamic Source Routing: Dynamic Source Routing belongs to the class of reactive (ondemand) routing protocol based n the concept of source routing. This protocol allows nodes to dynamically discover a source route across multiple network hops to any destination. Source routing means that each packet in its header carries the complete ordered list of nodes through which the packet must pass. DSR has no periodic routing messages, thereby reduces the network bandwidth overhead, conserving battery power and avoiding large routing updates throughout the ad hoc network. The protocol consists of two major phases: Route Discovery and Route Maintenance.
When a mobile node wants to send a packet to its destination, it checks its route cache whether it has any route to the destination. If it has an unexpired route, it will use this route to send packet to the destination. Otherwise, it will initiate a route discovery procedure by broadcasting a route request (RREQ). Each node hears the route request packet, checks whether it knows the route to the destination. If it does not, it adds its own address to the route record of the packet and forwards the packet along its outgoing links. To limit the number of route request propagated on a outgoing links of a node, a mobile only forward if the request has not seen by the node and if the nodes address already does not appear in the route record.
A route reply is generated when either the route request reaches the destination itself or an intermediate node which contain in its route cache an unexpired route to destination. If the node generating the route reply is the destination, it places the route record contained in the route request into the route reply. If the responding node is the intermediate node, it will append its cached route to the route record and then generate the route reply. To return the route reply, the responding node must have a route to the initiator.
Ad hoc On Demand Distance Vector (AODV) protocol:
AODV routing protocol is also based upon distance vector, and uses destination sequence numbers to determine the freshness of routes. It operates in the on-demand fashion, as opposed to the proactive way of the DSDV protocol. AODV requires hosts to maintain only active routes. An active route is a route used to forward at least one packet within the past active timeout period. When a host needs to reach a destination and does not have an active route, it broadcasts a route request (RREQ), which is flooded in the network. A route can be determined when RREQ is received either by the destination itself or by an intermediate host with an active route to that destination. A route reply (RREP) is unicast back to the originator of RREQ to establish the route. Each host that receives RREQ caches a route back to the originator of the request, so that RREP can be sent back. Every route expires after a predetermined period of time. Sending a packet via a route will reset the associated expiry time. It uses HELLO messages to determine the connectivity among the neighbours.
Features of this protocol include loop-freedom and that link breakages cause immediate notification to be sent to the affected set of nodes. AODV also supports multicast routing and avoids the Bellman-Ford counting-to-infinity problem. The use of destination sequence number ensures the freshness of the route.
The performances of the routing protocols are studied with the help of the network simulator software NS-2. In NS-2 the initial network topology is generated with random position of the node. Upon receiving the various simulation input parameter such as number of nodes (n), Simulation Area (A), Speed (S), Pause time (tp) and simulation time (T), mobility is initiated. The node positions are updated and the shortest path and the number of hops required to reach the destination are computed. Based on the number of active connections (mc) and their respective data rate, the packets are routed to the required destination. The trace file containing the status of the nodes (receive, send) and links (failure, connectivity), types of packets (control, data, acknowledgment) and average hop count is then generated and the process goes on till the simulation time is over. The performance parameter such as throughput, overhead and delay of the simulated mobile network are then computed.
The simulation procedure in NS-2 can be described as shown in Fig. 1.
The Scenario file describes the movement pattern of the nodes. The communication file describes the traffic in the network. These files are used for the simulation and as a result a trace file is generated as output. Prior to the simulation the parameters that are going to be traced during the simulation must be selected. The trace file can be scanned and analyzed for various parameters that we want to measure.
This can be used as data for plots with for instance Gnuplot. The trace file can also be used to visualize the simulation run with either Ad hockey or Network animator.
The simulation of the mobile network has been carried out on 800 MHZ Pentium III processor, 40 GB Hard Disk capacity and Red Hat Linux ver 6.2 operating system with the parameter specification shown in Table 1.
Performance metrics: The following four quantitative metrics are used to assess the performance:
|Packet delivery ratio: The ratio of the data delivered to the destinations (i.e., throughput) to the data sent out by the sources.
|Average end-to-end delay: The average time it takes for a packet to reach the destination. It includes all possible delays in the source and each intermediate host, caused by routing discovery, queuing at the interface queue, transmission at the MAC layer, etc. Only successfully delivered packets are counted.
|Normalized Protocol Load: The routing load per unit data successfully delivered to the destination. The routing load is measured as the number of protocol messages transmitted hop-wise (i.e., the transmission on each hop is counted once). A unit data can be a byte or a packet.
Simulation setup : To comprehensively measure the performance of a protocol, various network contexts are considered. The following parameters are varied in the simulation.
|Host Mobility is determined by the maximum speed (with 10 sec pause time).
|Traffic Load is the number of the CBR connections.
|Network Size is measured as the number of mobile hosts. Since the simulation field is fixed, the network size also measures the density of mobile hosts.
The parameter that we use for simulation is offered network load. The offered network load is the actually applied to the network. This can be categorized by three different parameters-Packet size, number of connections and the rate with which we are sending the packet. Here we investigate how the protocol behaves when the load and mobility increases. We have used three different offered load cases, 10 packets sec-1; 15 packets sec-1 and 20 packets sec-1. The packet size is held constant at 512 bytes and the number of flows at 15.
RESULTS AND DISCUSSION
Fraction of received packets: The study states that only at 5 packets sec-1, both AODV and DSR are rather constant, the fraction of received packets is only decreasing slightly when mobility increases (Fig. 2). At 10 packets sec-1 we can see that fraction received packets is decreasing much faster when the mobility factor is greater than 2. At 15 packets sec-1 and 20 packets sec-1 both AODV and DSR are dropping a large number of packets. At the highest mobility rate of 20 packets sec-1 only 50 to 60% of the sent packets are received.
The reason is more packets in the air and congestion in the buffer. At data rates of 15 packets sec-1 and 20 packets sec-1, AODV shows better performance than DSR. At these rates these protocols are dropping a large fraction of packets even at a mobility factor of 0. DSR will have much larger byte overhead than AODV at higher data rates. The reason for this is source route in each packet. This also increases the load on the network and causes more packets to be dropped. So AODV gets more packets through the network. DSDV is dropping a large fraction of packets already at lowest rate 5 packets sec-1.
|Fraction of received packets
It must be noted that the increase in dropped packets is not as large for DSDV as AODV and DSR. At the highest rate, DSDV is almost as good as DSR.
End-to-End delay: The delay is also affected by high rate of CBR packets (Fig. 3). The buffer comes full quicker, so the packets have to stay in buffer for much longer period of time before they sent. This can clearly be seen at highest rate 20 packets sec-1. DSR have much lower delay compared to AODV. The difference between AODV and DSR is very apparent at the rate of 10 packets sec-1.
DSDV has lowest delay of them all. The high delay at the mobility factor of 0-1 and the data rate of 20 packets sec-1, DSDV is due to extremely high data rate and the low mobility.
High data rate will fill up the buffers quickly and low mobility means that already found routes are valid for a much longer time period. This means that the route can be used for more packets. Even the packets that have stayed in the buffer for a long time have a chance to get through. When mobility increases more routes will become invalid and new request are necessary. While the request is propagating the network in search of new route, buffer will get full and packets are dropped.
For DSDV, the average delay at highest data rate will actually be lower than at the rate of 15 packets sec-1. At the rate of 15 packets sec-1 and 20 packets sec-1, when mobility starts to get so high that the topology changes frequently, only 40-60% of the packets gets through the network. These topology changes means that the protocol needs more time to converge before the packets can be sent.
End-to-end throughput: At low CBR rates the throughput of DSR and AODV is unaffected of the mobility (Fig. 4 ), it stays constant at 2.5 kbits sec-1. At highest CBR rate, the throughputs will decreases when the mobility increases. This can already be seen at CBR rate 10 packets sec-1 is however very small. At 15 packets sec-1 and 20 packets sec-1 the throughput decreases very much for all protocols. This is however an effect from the large fraction of dropped packets. The results of AODV are slightly better than for DSR. DSR have much larger byte overhead than AODV at higher data rates. This also increases the load on the network and causes more packets to be dropped. Thus a AODV will have better through put at high data rates. DSDV drops a large fraction of packets already at the rate of 5 packets sec-1. The throughput decreases more and more as the rate increases.
Overhead: The simulation shows that the byte overhead of DSR is much larger than AODV even at low data rates and the difference become larger when the CBR rate increases. At CBR rate of 20 packets sec-1, the byte overhead for DSR is more than double of AODV. The reason for larger byte overhead for DSR is of course the source route in each packet. The amount of control information in DSDV is not affected to great extent by the data rate for the CBR packets. The number of control packets is actually smaller when the data rate is 20 packets sec-1. The reason for this is high data rate causes more collisions, which means that some of the update messages are dropped.
Those lost update messages are not received by any nodes and cannot triggers new update message. When the mobility increases more and more packets will be dropped. At the highest data rate, many update messages are dropped.
The simulation shows that there is a need for a special routing protocol, when the mobility increases. AODV and DSR have exhibited a good performance in high mobility also. DSR is based on source routing, which means that byte overhead in each packet can affect the total byte overhead in the network drastically when the load offered and size of the network increases. In this situation the hop-by-hop based routing protocol like AODV is more desirable. One advantage with source routing is that during route discovery operation it learns more routes. Source routing is however is not desirable in ordinary forwarding of data packets because of larger byte overhead. A combination of AODV and DSR can be used for better result. The performance of the protocols differs slightly based on different network loads.
DSDV are more suitable for small networks where changes in the topology are limited. Also DSDV could be considered for delay constraint network. DSR is suitable for networks in which the nodes 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 its packet size is large carrying full route. AODV in the simulation has the best all round performance. It is the improvement on DSDV and DSR and has the advantage of both of them.
- Corson, M.S., J.P. Marker and G.H. Cirincione, 1999. Internet based mobile Ad hoc networking. IEEE Internet Compt., 3: 63-70.
- Perkins, C.E. and P. Bhagwat, 1994. Highly dynamic Destination Sequenced Distance-Vector routing (DSDV) for mobile computers. Proceedings of the ACM Conference on Communication Architecture, Protocols and Applications, August 31-September 2, 1994, London, UK., pp: 234-244.
- Garcia-Luna-Aceves, J.J. and M. Spohn, 1999. Source-tree routing in wireless networks. Proceedings of the 7th International Conference on Network Protocols, Oct. 31-Nov. 3, Washington, DC., USA., pp: 273-282.
- Jiang, H. and J.J. Garcia-Luna-Aceves, 2001. Performance comparison of three routing protocols for ad hoc networks. Proceedings of the 10th International Conference on Computer Communications and Networks, October 15-17, 2001, Scottsdale, AZ., USA., pp: 547-554.
- Das, S.R., C.E. Perkins, E.M. Royer and M.K. Marina, 2001. Performance comparison of two on-demand routing protocols for ad hoc networks. Proceedings of the IEEE Personal Communications Magazine Special Issue on Ad hoc Networking, February 2001, USA., pp: 16-28.
- Zeng, X., R. Bagrodia and M. Gerla, 1998. GloMoSim: A library for parallel simulation of large-scale wireless networks. Proceedings of the 12th Workshop on Parallel and Distributed Simulation, May 26-29, 1998, Banff, Alta, Canada, USA., pp: 154-161.
- Camp, T., J. Boleng, B. Williams, L. Wilcox and W. Navidi, 2002. Performance Comparison of two location based routing protocols for ad hoc networks. Proceedings of the Infocom 21st Annual Joint Conference of the IEEE Computer and Communications Societies, 2002, IEEE Xplore, pp: 1678-1687.