Performance Comparison Of AODV, DSR And Cluster Based Routings In Mobile Ad Hoc Networks

Performance Comparison Of AODV, DSR And Cluster Based Routings In Mobile Ad Hoc Networks

Abstract

MANETs based on flat routing schemes cannot perform well when the network size increases, especially in face of node mobility as well, due to link and processing overhead. With cluster structure, the processing and spreading of routing information are restricted to partial mobile nodes in the network. Hence, cluster-based routing should be able to provide better scalability solutions for MANETs compared to flat routing schemes. Cluster based Routing Protocol (CBRP), maintains 1-hop and 2-hop neighbour information tables which are updated after every hello message interval. Besides explicit Hello messages, we propose utilization of data packets and routing packets for updating information tables at each mobile node so that the information tables can be updated more frequently when a mobile node receives packets from others. This addition is named as Modified-CBRP. Simulation results show that Modified-CBRP can achieve satisfying routing performance and outperforms CBRP and other flat routing schemes (DSR and AODV).

Keywords: AODV, DSR, CBRP, routing

1. Introduction

   Mobile Ad Hoc Networks (MANETs), without any fixed infrastructures, allow mobile terminals to set up a temporary network for instant communication. Hence, MANETs bear great application potential in these scenarios, including disaster and emergency relief, mobile conferencing, battle field communication, and so on. The infrastructureless and dynamic nature of MANET requires efficient routing protocols to form routing paths and a number of ad hoc routing protocols have been proposed. Ad hoc routing protocols can be divided into flat and hierarchical routing. AODV [4] and DSR [5] are two widely used flat ad hoc routing protocols. It has been shown that flat routing cannot perform well for a large-scale MANET. Hierarchical routing is one solution to solve the scalability problem

   in MANET. CBRP [6][8] is a cluster-based hierarchical ad hoc routing protocol which is included in the internet draft. The rest of the paper is organized as follows: The AODV routing protocol Description is summarized in section 2. The DSR routing protocol Description is summarized in section 3. The CBRP & modified-CBRP routing protocol Description is summarized in section 4.The simulation environment and performance metrics are described in Section 5.

2. AODV ROUTING PROTOCOL DESCRIPTION

   Ad hoc On Demand Distance Vector (AODV) [1][2][3][4] is a reactive routing protocol which initiates a route discovery process only when it has data packets to send and it does not know any route to the destination node, that is, route discovery in AODV is on-demand. AODV uses sequence numbers maintained at each destination to determine freshness of routing information and to avoid the routing loops that may occur during the routing calculation process. All routing packets carry these sequence numbers.

   1. Route Discovery Process

      During a route discovery process, the source node broadcasts a route request (RREQ) packet to its neighbors. If any of the neighbors has a route to the destination, it replies to the query with a route reply packet. Otherwise, the neighbors rebroadcast the route query packet. Finally, some query packets reach to the destination.

      Fig. 1 shows the initiation of route discovery process from source node S to destination node D. At that time, a reply packet is produced and transmitted tracing back the route traversed by the query packet as shown in Fig. 2.

      Figure 1.Source node S initiates the path discovery process [3].

      Figure 2.A RREP packet is sent back to the source [3]

   2. AODV Route Message Generation

      The route maintenance process in AODV is very simple. When the link in the path between node S and node D breaks the upstream node that is affected by the break generates and broadcasts a RERR message. The RERR message eventually ends up in source node S. After receiving the RERR message, node S will generate a new RREQ message.

   3. AODV Route Maintenance Process

      Finally, if adjacent node already has a route to destination node D, it will generate a RREP message and if adjacent node do not have route in its route cache it will re-broadcast the RREQ from source node S to destination node D. Fig. 3 shows the AODV Route Maintenance process.

      Figure 3. AODV Route Maintenance by using Link Failure Notification Message [3]

3. DSR ROUTING PROTOCOL DESCRIPTION

   The Dynamic Source Routing (DSR) [1][2][3][5] protocol is also reactive routing protocol but is based on source routing. In the source routing, a source determines the perfect sequence of nodes with which it propagate a packet towards the destination. The list of intermediate nodes for routing is explicitly stored in the packet's header. In DSR, every mobile node needs to maintain a route cache where it caches source routes. When a source node wants to send a packet to some other intermediate node, it first checks its route cache for a source route to the destination for successful delivery of data packets. In this case if a route is found, the source node uses this route to propagate the data packet otherwise it initiates the route discovery process. Route discovery and route maintenance are the two main features of the DSR protocol.

   1. Route Discovery Process

      For route discovery, the source node starts by broadcasting a route request packet that can be received by all neighbor nodes within its wireless transmission range. The route request contains the address of the destination host, referred to as the target of the route discovery, the source's address, a route record field and a unique identification number (Figure 4). During the route discovery process, the route record field is used to contain the sequence of hops which already taken. At start, all senders initiate the route record as a list with a single node containing itself. The next intermediate node attaches itself to the list and so on. Each route request packet also contains a unique identification

      number called as request_id which is a simple counter increased whenever a new route request packet is being sent by the source node. So each route request packet can be uniquely identified through its initiator's address and request_id. When a node receives a route request packet, it is important to process the request in the following given order. This way we can make sure that no loops will occur during the broadcasting of the packets.

      Figure 4. Building of the record during route discovery in DSR[3]

      A route reply is sent back either if the request packet reaches the destination node itself, or if the request reaches an intermediate node which has an active route4 to the destination in its route cache. The route record field in the request packet indicates the sequence of hops which was considered. If the destination node generating the route reply, it just takes the route record field of the route request and puts it into the route reply. If the responding node is an intermediate node, it attaches the cached route to the route record and then generates the route reply (Figure 5).

      Sending back route replies can be processedwith two different ways: DSR may use symmetric links. In the case of symmetric links, the node generating the route reply just uses the reverse route of the route record. When using asymmetric links, the node needs to initiate its own route discovery process and back the route reply on the new route request.

      Figure 5. Propagation of the route reply in DSR[3]

   2. Route Maintenance Process

      Route Maintenance Phase takes the responsibility of detecting broken links and making route recovery. When a mobile node notices that it cannot send packets to the next node in route, a route error (RERR) message will be generated and sent back to the source node along the first part of the route. If a certain node holding the RERR message can find an alternative route from its RC to substitute the failed link, local link repairing will be made. Otherwise, after the RERR message arrives at source node, a new Route Setup Phase will be initiated.

4. Cluster-Based Routing Protocol (CBRP)

   Hierarchical routing protocols are used to reduce routing space, thus decrease flooding traffic and improve network performance. A typical way to establish hierarchy in MANET is to group mobile nodes near to each other to form explicit clusters, and assign different roles to the nodes, such as cluster head (CH), cluster member (CM) and cluster gateway (CGW). A cluster-based routing scheme consists of two parts: Clustering Algorithm and Routing Algorithm. In CBRP, the Clustering Algorithm is based on Least CH Change (LCC) and Lowest-id [6][11][12]. For LCC, initially, all nodes are in undecided state, after exchanging Hello messages, the nodes with smallest IP addresses in its neighbourhood are elected as CHs. Other nodes still in undecided state will send out another Hello messages. If a CH receives a Hello message from node k, it will give a reply and nominate k as his CM. Once a cluster is formed, the CH will have a routing table to store the information of its CMs. Cluster changes occur in two conditions: (1) two CHs

   move into each others transmission range, or (2) a CM move out of his CHs transmission range. The MNs in CBRP exchange Hello messages periodically. So each MN can keep updated information from its neighbours. Routing Algorithm for CBRP is similar to DSR, except: (1) when a source node needs to propose a Route Setup Phase, the RREQ message is first unicast to the source nodes CH instead of broadcasting to all neighbouring nodes. The source nodes CH will broadcast this RREQ only to its adjacent CHs through CGW. The CHs receiving this RREQ message still only rebroadcast this RREQ message to their adjacent CHs through CGW, until the RREQ arrives at the destination nodes cluster. In short, flooding traffic only goes through the high-level MNs, such as CHs and CGWs in this case, and thus, network resources can be greatly saved, (2) For RREP, IP loose source routing [6][7] is used to shorten routing path and save CHs from heavy transmission load.

   Figure 6. Cluster topology

   Figure 7. Route discovery and building of route record [7,4,10,11]

   Figure 8. Route reply, reversed loose source route [11,10,4,7] and actual source route [11,10,12,9,7]

   For example, as shown in Fig. 8, n7 and n11 are S and D of a communication pair respectively. When n11 receives a RREQ packet originated from n7, indicating this RREQ has travelled through CHs n4 and n10, n11 will return a RREP to n7 by traversing the CHs listed in the received RREQ with reverse order. Then, the reversed loose source route for the RREP packet to travel from n11 to n7 is [n11, n10, n4, n7], where n10 and n4.are listed as Traversed Cluster IDs in the RREPs header. As the RREP travels back, the strict source route, which will be utilized for the data forwarding, is computed based on the mechanisms addressed above and recorded in the Route record list in RREPs header. Then n7 can obtain the actual source route, [n11, n10, n12, n9, n7], where (n11, n10, n12, n9) is stored as the Route record list in RREPs header, once it receives the RREP.

   1. Information Table Updates Using Routing Packets and Data Packets

      The correctness and accuracy of information tables are quite important because they can reflect the real- time underlying network topology, which is the basis for clustering, routing and data delivery. Besides the explicit Hello messages, Modified-CBRP utilizes data packets and routing packets for updating information tables at each mobile node so that the information tables can be updated more frequently as a by product when a mobile node receives packets from others. There are two solutions to utilize the data packets or routing packets to update the information tables:

      • In Modified-CBRP, a mobile node attaches its cluster-related information, including its cluster status, node degree and CIDs in an outgoing data packet or routing packet, and this information may travel up to two hops. Hence, the information about this mobile node in its neighbours information tables can be

        updated when its neighbours receive or overhear such a packet. This update can be achieved at low cost because a mobile node adds only several bytes in the header of its outgoing packets to include the corresponding information.

      • When an IM detects the link breakage between itself and its downstream mobile node along an active path, it deletes the entry corresponding to the downstream node from its 1-hop neighbour table, and all entries with the downstream node as the next hop from its 2-hop neighbour table. When a RERR message, indicating a broken link along an active path, travels back to S of the path, each mobile node, receiving or overhearing the message, will check whether its 2-hop NT includes an entry, with the upstream node of the broken link indicated in the RERR as the

   node ID and the downstream node as the

   next hop or vice versa. If true, it will delete the corresponding entries from its 2-hop NT. Hence, the link break information can help to update information tables at a mobile node without adding any additional information to the RERR packet.

5. SIMULATION ENVIRONMENT

   1. Simulation Model

      The Glomosim [9][10] simulator is used for simulating the performance of four routing schemes: CBRP, AODV and DSR. Glomosim can simulate the physical, MAC and data link layer of a multihop wireless network. The distributed coordination function (DCF) of IEEE 802.11 for wireless LANs is utilized as the MAC layer. Lucents WaveLAN is used as the radio model, which is a shared-media radio with a nominal bit rate of 2Mbps and a nominal transmission range of 250 m.

      1. Simulation Parameters

         TABLE I

         PARAMETERS VALUES FOR AODV, DSR, CBRP SIMULATION

         Parameters	Values
         Simulation time	200 s
         Number of mobile nodes, N	50
         Simulation area	1,000 m * 1,000 m
         Transmission range for mobile nodes	250 m
         Movement model	Random Waypoint
         Pause time for mobile nodes	50.0 s
         Max. Speed for mobile nodes, vmax	10.0 m/s
         Speed for mobile nodes	0vmax
         Traffic pairs, nt	10,15,20,25
         Data Traffic Rate for each source	4 packets/second

      2. Performance Metrics

         Three performance metrics which are Packet Delivery Fraction (PDF), Average End-to-End Delay and Normalized Routing Load (NRL) have been considered:

         Packet delivery fraction: The fraction of all the received data packets successfully at the destinations over the number of data packets sent by the CBR sources is known as Packet delivery raction.

         Average End to end delay: The average time from the beginning of a packet transmission at a source node until packet delivery to a destination. This includes all possible delays caused by buffering during route discovery latency, queuing at the interface queue, retransmission delays at the MAC, and propagation and transfer times of data packets. Calculate the send(S) time (t) and receive (R) time (T) and average it.

         Normalized Routing Load: The normalized routing load is defined as the fraction of all routing control packets sent by all nodes over the number of received data packets at the destination nodes.

6. Simulation Results and observations

   Figure 9. Packet delivery ratio

   Figure 10. Routing overhead

   Figure 11. Average end-to-end delay

7. Conclusions

In this simulation work, the routing protocols: AODV, DSR, CBRP and modified-CBRP are evaluated for the application oriented performance metrics like packet delivery fraction, average end-to-end delay, and normalized routing load. DSR performs the worst. Packet delivery ratio of CBRP is better than DSR and Modified-CBRP exhibits better than AODV. As the traffic load increases cluster based routing gives reduced overhead compared to flat routing because the number of nodes involved in flooding of route request packet are minimized. AODV has less average end-to- end delay.

REFERENCES

1. S. R. Das, C. E. Perkins, and E. M. Royer, Performance Comparison of Two On-Demand Routing Protocols for Ad Hoc Networks, IEEE Personal Communications Magazine, Vol. 8, No. 1, February 2001, pp.16-29.

2. J. Broch, D. A. Maltz, D. B. Johnson et.al., A Performance Comparison of Multi-Hop Wireless Network Routing Protocols, Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom98), October 25-30, 1998, USA,pp.25-30.

3. David Oliver Jorg, Performance Comparison of MANET Routing Protocols In Different Network Sizes, Computer Networks and Distributed Systems, University of Berne,Switzerland,2003.

4. C. E. Perkins, E. M. Royer, and S. R. Das, Ad Hoc On- Demand Distance Vector (AODV)Routing, Internet Draft, draft-ietf- manet- aodv-10.txt, work in progress, 2002

5. D.B. Johnson, D.A. Maltz, and J. Broch, DSR: The Dynamic SourceRouting Protocol for Multi-Hop Wireless Ad Hoc Networks, Ad HocNetworking, pp. 139172, 2001.

6. M. Jiang, J. Li, and Y.C. Tay, Cluster Based Routing Protocol, draftietf-manet-cbrp-spec-01, Internet Draft, IETF, Aug. 1999.

7. Jane Y. Yu, Peter H. J. Chong, and Mingyang Zhang, Performance of Efficient CBRP in Mobile Ad Hoc Networks (MANETS),IEEE, 2008

8. N. S. Yadav and R. P. Yadav, Source routing in MANETs, International journal of recent trends in engg. Issue 1, Vol. 1, may 2009

9. M. Takai, L. Bajaj, R, Ahuja, R. Bagrodia and M. Gerla, GloMoSim:A Scalable Network Simulation Environment, echnical report 990027,UCLA, Computer Science Department, 1999.

10. A tutorial on Glomosim by Thomas Nilsson

11. J. Y. Yu and P. H. J. Chong, "A survey of clustering schemes for mobile ad hoc networks," Communications Surveys & Tutorials, IEEE, vol. 7, pp.32-48, 2005.

12. Azzedine Boukerche, Simulation-Based Performance Comparisons of Routing Protocols for Mobile Ad Hoc Networks, The Society for Modeling and Simulation International, Vol.78, Issue 7, July 2002