Analysis on Optimized Routing Protocol for Ad Hoc Networks

Analysis on Optimized Routing Protocol for Ad Hoc Networks

Kshitija Chutke

M. Tech. Scholar Department of C.S.E., JIET kshitijachutke@gmail.com

Abstract

An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. This paper evaluates some of the existing routing protocols such as Dynamic Source Routing (DSR), Ad Hoc On-Demand Distance Vector Routing (AODV), Destination Sequenced Distance-Vector (DSDV) and proposed a new protocol. An attempt has been made to compare the performance of two prominent on-demand reactive routing protocols for mobile ad hoc networks: DSR and AODV, along with the traditional proactive DSDV protocol.

These protocols involve communication overheads of route maintenance and route discovery and use single route and do not utilize multiple alternate paths and also minimize the usage of valuable resources such as bandwidth, power and processor. The nodes which do not possess enough power to carry out the data delivery process should not be used in route selection. Taking into account all these parameters, a new routing protocol has been proposed. This protocol uses the concept of virtual node and the power feature of a mobile node. The scheme establishes the multiple paths without transmitting any extra control message. A simulation model with MAC and physical layer models is used to study interlayer interactions and their performance implications. The performance differentials for the existing ones are analysed using varying network load, mobility, throughput in data delivery and network size. These simulations are carried out based on the Rice Monarch Project that has made substantial extensions to the NS-2 network simulator to run Ad hoc simulations.

1. Introduction

   In the present era, there is a huge increase in the usage of handheld devices. Indeed, laptops, mobile phones and PDAs take an important place in everyday life. Hence, the Challenge is now to make all these devices communicate with each other in order to build a network. The wireless mobile Ad hoc network (MANETs) allows the required flexibility and mobility. Ad hoc networks offer practical solution to such problems.

   In this paper the on demand reactive protocols Ad Hoc On Demand Distance Vector (AODV) and Dynamic Source Routing (DSR) is compared with the proactive protocol Destination Sequenced Distance Vector (DSDV). The On demand protocols, AODV and DSR perform better than the table-driven DSDV protocol. Although DSR and AODV share similar on-demand behaviour, the differences in the protocol mechanics can lead to significant performance differentials. Current routing protocols for MANETs suffer from certain inherent shortcomings. On the one side the proactive routings schemes like Destination Sequenced Distance Vector (DSDV) continuously update the routing tables of mobile nodes consuming large portion of the scarce network capacity for exchanging huge chunks of routing table data. This reduces the available capacity of the network for actual data communication.

   The on demand routing protocols like Ad Hoc On Demand Distance Vector and Dynamic Source Routing on the other hand launch route discovery, and require the actual communication to be delayed until the route is determined. This may not be suitable for real time data and multimedia communication applications. In all the protocols major emphasis has been on stable and shortest routes in all these while ignoring major issue of delay in response whenever break occurs. Some other areas of consideration are: (1) Most of the simulation studies use fixed environment, instead of random scenes. (ii) Reconstruction phase requires better approach in all the protocols for fast selection of new routes. (iii) Real life scenarios need to be simulated instead of predefined scenes and (iv) None of the protocols discuss the concept of power factor which can be crucial in route discovery and route repair phase.

   The current paper tries to overcome these shortcomings of AODV, DSR and DSDV routing protocols by combining them to develop a new protocol. This protocol uses the concept of power aware node during route selection and concept of virtual nodes which ensures fast selection of routes with minimal effort and faster recovery. These virtual nodes help in reconstruction phase for quick selection of new routes and power feature provides the new routes. It offers quick adaptation to

   distributed processing, dynamic linking, low processing overhead and loop freedom at all times. In the development process AODV protocol has been considered as the base protocol.

2. Background Description of DSDV, DSR and AODV Routing

   Protocols

   1. DSDV Routing Protocol

      An ad hoc network is a collection of mobile nodes forming an instant network without fixed topology. In such a network, each node acts as both router and host simultaneously, and can move out or join in the network freely. The instantly created network does not have any base infrastructures as used in the conventional networks, but it is compatible with the conventional networks. DSDV is a modification of the conventional Bellman-Ford routing algorithm. It addresses the drawbacks related to the poor looping properties of RIP in the face of broken links. The modification adapted in DSDV makes it a more suitable routing protocol for ad hoc networks. This paper reviews the DSDV protocol, and analyses the properties of DSDV when it is used for ad hoc networks routing.

      This protocol requires each mobile station to advertise, to each of its current neighbours, its own routing table (for instance, by broadcasting its entries). The entries in this list may change fairly dynamically over time, so the advertisement must be made often enough to ensure that every mobile computer can almost always locate every other mobile computer of the collection. . In addition, each mobile computer agrees to relay data packets to other computers upon request. This agreement places a premium on the ability to determine the shortest number of hops for a route to a destination we would like to avoid unnecessarily disturbing mobile hosts if they are in sleep mode. In this way a mobile computer may exchange data with any other mobile computer in the group even if the target of the data is not within range for direct communication. All the computers inter operating to create data paths between themselves broadcast the necessary data periodically, say once every few seconds. The data broadcast beach mobile computer will contain its new sequence number and the following information for each new route:

      • The destination's address.

      • The number of hops required to reach the destination.

      • The sequence number of the information received regarding that destination, as originally stamped by the destination.

        Fig1. Example of Ad Hoc Network

        The transmitted routing tables will also contain the hardware address, and (if appropriate) the network address, of the mobile computer transmitting them, within the headers of the packet. The routing table will also include a sequence number created by the transmitter. Routes with more recent sequence numbers are always preferred as the basis for making forwarding decisions, but not necessarily advertised. Of the paths with the same sequence number, those with the smallest metric will be used. By the natural way in which the routing tables are propagated, the sequence number is sent to all mobile computers, which may each decide to maintain a routing entry for that originating mobile computer. Routes received in broadcasts are also advertised by the receiver when it subsequently broadcasts its routing.

   2. DSR Routing Protocol

      An ad hoc network is a collection of wireless mobile hosts forming a temporary network without the aid of any established infrastructure or centralized administration. In such an environment, it may be necessary for one mobile host to enlist the aid of other hosts in forwarding a packet to its destination, due to the limited range of each mobile hosts wireless transmissions. The protocol for routing in ad hoc networks that uses dynamic source routing. The protocol adapts quickly to routing changes when host movement is frequent, yet requires little or no overhead during periods in which hosts move less frequently. Based on results from a packet-level simulation of mobile hosts operating in an ad hoc network, the protocol performs well over a variety of environmental conditions such as host density and movement rates. For all but the highest rates of host movement simulated, the overhead of the protocol is quite low, falling to just 1% of total data packets transmitted

      for moderate movement rates in a network of 24 mobile hosts. In all cases, the difference in length between the routes used and the optimal route lengths is negligible, and in most cases, route lengths are on average within a factor of 1.01 of optimal.

      DSR protocol is composed by two ondemand mechanisms, which are requested only when two nodes want to communicate with each other. Route Discovery and Route Maintenance are built to behave according to changes in the routes in use, adjusting themselves when needed. Along with those mechanisms, DSR allows multiple routes to any destination, thus can lead easily to load balancing or increase robustness. Route Discovery is the mechanism by which a node S (Source) wishing to send a packet to a Destination node D obtains a source route to D. Route Discovery is used only when S attempts to send a packet to D and does not already know a route to D.

      The source first has to check in its Route Cache if it knows a suitable route for the destination. If no route is found, it will have to start a route discovery protocol to find a route to the destination.

      • Route discovery

      • Route Maintenance

      • Route Optimizations

      • Complete use of route cache

        Fig2: Simple Ad Hoc Network of three wireless mobiles.

        The route discovery itself consists on a chain of locally broadcasted Route Request (RREQ). The broadcasting occurs until one of the broadcasted RREQ reaches either the destination node or a node who knows a route to that destination. When a node receives a RREQ, it checks in its Route Request Table if the same RREQ has already been received. In that case, the packet is discarded. Route Maintenance is the mechanism by which node S is able to detect, while using a source route to D, if the network topology has changed such that it can no

        longer use its route to D because a link along the route no longer works. When Route Maintenance indicates a source route is broken, S can attempt to use any other route it happens to know to D, or can invoke Route Discovery again to find a new route for subsequent packets to D. Route Maintenance for this route is used only when S is actually sending packets to D. Each node is responsible for its own links, i.e. each node must confirm that data can flow over the link from that node to the next hop. This information can be provided by an acknowledgement from different sources.

        Fig3: Ad Hoc Network Illustrating Route Cache.

   3. AODV Routing Protocol

      This builds the DSDV and the improvement is on minimizing the number of required broadcasts by creating routes on an ondemand basis, as opposed to maintaining a complete list of routes as in DSDV. A path discovery is initiated when a route to a destination does not exist. Broadcast is used for route request. Link failure notification is sent to the upstream neighbours and this algorithm requires symmetric links. Ad hoc on demand distance vector, as the name suggests is a routing protocol designed to build routes between nodes only when demanded by source nodes. Routes are maintained as long as they are needed by the sources.

      Sequence numbers are used in order to maintain the routes up to date. Routes are built using route request/reply messages. When a source node wishes to communicate with a destination for which it does not have a route, it broadcasts a route request

      (RREQ) packet across the network. A node receiving the packet updates the information about the source node and sets backward pointers to the source node in the route tables. A node will then unicast a route reply (RREP) if it is the destination or if it has a route to the destination with a greater or equal sequence number to that of the RREQ message. Otherwise the node rebroadcasts the RREQ packet. If it has already been processed it is then being discarded. When a RREP propagates back to the source, nodes set up forward pointers to the destination. Once the source node receives the RREP which includes the sequence number of the destination and the hop count to reach it, data packets can be sent to the destination using the forward route entries of the intermediate nodes. If a

      RREP is received later with a greater or equal sequence number and shorter hop count, the better route can be used. Timeouts are used in order to keep the routes active for certain periods of time. In the case a link breaks while a route is active, the node upstream of the breakage will propagate a route error (RERR) message to the source node to inform that the destination is unreachable. The source node can then reinitiate RREQ if desired. Additionally sequence numbers are used in order to maintain the freshness of routing information and loop avoidance.

3. Proposed New Protocol

   The proposed new protocol takes care of on demand routing and also power features along with a new concept of virtual nodes. It is dynamic and supports multi hop routing between participating mobile nodes wishing to establish and maintain an ad hoc network. Virtual nodes are nodes at the one hop distance from its neighbour and are in active state based on power status. These virtual nodes help in reconstruction phase for fast selection of new routes. Each route table of a node has an entry for its power status (which is measured in terms of Critical, Danger and Active state) and number of Virtual node attached to it. Status of Virtual node depends upon two major factors as power status and life time of a node. Power status is a field having range from 1-10 with three tags. Active range is 7-10, critical is 4-6 1-3 is danger level. Life time is determined by the control packet. These fields are updated with each data packet forward and with each beaconing via HELLO packet. HELLO packets are beaconing packets which transmit status of the node to all its neighbours. Same process is repeated in route phase. DSDV, DSR and AODV on the other hand require additional control to construct and maintain alternate routes. The additional control messages increases overhead and thus reduces performance of the protocol. The proposed scheme with minor modifications in packet formats and in route achieves the desired results. This new protocol has been designed for use in networks in which all the nodes can trust each other, and there are no malicious intruder nodes.

   There are three phases in the scheme as Route Construction, Route Repair and Route Erasure. Route Construction is starting phase of the scheme, it creates and establishes route initially. In this requests are made in the form of request packet, replies are received as reply packet and using route reply packets, route is established. Route repair phase deals with situation, when a route break occurs. In case of link failures or other situations when a break in routes occurs, this phase is

   invoked. Route repair involves transmission of error packets and reconstruction of new route. In the proposed protocol, major changes have been done in this phase as compared to the base protocol used. Route recovery involves (a) finding virtual nodes and power status. (b) Invalidate route erasures (c) Listing affected destination (d) Valid route update and (e) Finding a new route. Last phase is route erasure process which is the phase invoked when data transmission is over; this requires releasing of route for next transmission. This process makes the network available for future transmission.

   The proposed protocol has highest percentage of packet delivered in all cases compared with other protocols. The new protocol achieves the target of better management of route repairs and thus reliable routes. It does not use cache concept as in DSR which creates overhead in route maintenance. It does not use height calculation and generation of directed acyclic graph. It has been designed to be robust to changes.

4. Performance Metrics

   Three important performance metrics are evaluated:

   1. Packet delivery fraction

      The ratio of the data packets delivered to the destinations to those generated by the CBR sources.

   2. Average end-to-end delay of data packets

      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.

   3. Normalized routing load

      The number of routing packets transmitted per data packet delivered at the destination. Each hop-wise transmission of a routing packet is counted as one transmission.

5. Simulation Results

   1. Performance comparison of the protocols

      First, an attempt was made to compare all the 3 protocols under the same simulation environment. For all the simulations, the same movement models were used, the number of traffic sources was fixed at 20, the maximum speed of the nodes was set to 20m/s and the pause time was varied as 0s, 10s, 20s, 40s and 100s.

      Figures 4 and 5 highlight the relative performance of the three routing protocols. All of the protocols deliver a greater percentage of the originated data packets when there is little node mobility (i.e., at

      large pause time), converging to 100% delivery when there is no node motion.

      1. Packet delivery Comparison

         The On-demand protocols, DSR and AODV performed particularly well, delivering over 85%of the data packets regardless of mobility rate.

      2. Average End-End Packet delivery

      The average end-to-end delay of packet delivery was higher in DSDV as compared to both DSR and AODV. In summary, both the On-demand routing protocols, AODV and DSR outperformed.

   2. Varying Mobility and Number of Sources to see the performance difference between DSR and AODV

Fig4: Packet Delivery

Now, again simulations were carried out with the number of traffic sources as 10, 20, 30 and

40. The pause time was varied as 0 (high mobility), 10, 20, 40,100 (no mobility) and the packets were sent at a rate of 4 packets/sec.

B.1 Packet delivery Comparison

The packet delivery fractions for DSR and AODV are similar with 10 sources (Fig. 3a).

However, with 20, and 30 sources, AODV outperforms DSR by about 15 percent (Fig. 3b and 3c) at lower pause times (higher mobility).

Fig5: Packet Delivery

Here we can see the comparison between two packet delivery sessions are done. (Fig4 and Fig5).

1. Conclusions

   This paper compared the performance of DSDV, AODV and DSR routing protocols for ad hoc networks using ns-2 simulations. Unfortunately, the new protocol simulations

   couldnt be successfully carried out. DSDV uses the proactive table-driven routing strategy while both AODV and DSR use the reactive On-demand routing strategy. Both AODV and DSR perform better under high mobility simulations than DSDV. High mobility results in frequent link failures and the overhead involved in updating all the nodes with the new routing information as in DSDV is much more than that involved AODV and DSR, where the routes are created as and when required. DSR and AODV both use on-demand route discovery, but with different routing mechanics. In particular, DSR uses source routing and route caches, and does not depend on any periodic or timer-based activities. DSR exploits caching aggressively and maintains multiple routes per destination.

   AODV, on the other hand, uses routing tables, one route per destination, and destination sequence numbers, a mechanism to prevent loops and to determine freshness of routes. The general observation from the simulation is that for application-oriented metrics such as packet delivery fraction and delay AODV, outperforms DSR in more stressful situations (i.e., smaller number of nodes and lower load and/or mobility), with widening performance gaps with increasing stress(e.g., more load, higher mobility). DSR, however, consistently generates less routing load than AODV. The poor performances of DSR are mainly attributed to aggressive use of caching, and lack of any mechanism to expire stale routes or determine the freshness of routes when multiple choices are available. Aggressive catching, however, seems to help DSR at low loads and also keeps its routing load down. Future Work In the future, extensive complex simulations could be carried out for the proposed new protocol, in order to gain a more in depth performance analysis of the ad hoc routing protocols.

2. Future Work

   In the future, extensive complex simulations could be carried out for the proposed new protocol, in order to gain a more in depth performance analysis of the ad hoc routing protocols.

3. References

[1]. Saurabh Rastogi Optimizing routing protocols for Ad Hoc Network.

[2]. Guoyou He Destination Sequenced Distance Vector.

[3]. David B. Johnson, David A. Maltz Dynamic Source Routing in Ad Hoc wireless network. [4]. J. Broch, D.A. Maltz, D.B.Johnson, Y-C. Hu and J. Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols.

[5]. Samir R. Das, Charles E. Perkins, Elizabeth M. Royer. Performance comparison of Two On- demand Routing Protocols for Ad Hoc Networks.