Aodv Routing Protocol In Manets Computer Science Essay

Published:

A mobile ad-hoc network is a collection of mobile devices that are very dynamic, infrastructure less and can leave and join the network at any time without the assistance of a centralized structure. Within the last decade many routing protocols have been developed for MANETS and they are mainly categorized into two i.e. Proactive and Reactive protocols.

Development of ad-hoc networks can be classified into three different generations with different labels until present day when they gained the label ad-hoc networks. In 1972 there were Packet Radio Networks (PRNET) being used in conjunction with ALOHA and CSMA, in the 1980's they were improved and implemented as Survivable Adaptive Networks (SURAN) program mainly used in combat environment. In the 1990's they became commercial with the concept of notebooks and mobile phones. More research on the collection of mobile devices was done especially by the IEEE 802.11……….

Network Simulator 2 (NS2) is a discrete event simulator that was developed as part of the VINT project at the University of California in Berkeley. The simulator is mainly used for research purposes for different networks and it is event driven. It provides a substantial support to simulate different protocols like UDP, TCP, FTP and AODV. It is UNIX based and uses Tcl as its scripting language………….

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Statement of problem:

An increase in the use of portable devices with a wireless infrastructure for communication, ad hoc networking is gaining importance with the increasing number of widespread applications. MANET (Mobile Ad-hoc Network) is a collection of wireless nodes that can dynamically form a network to exchange information without using any pre-existing fixed network infrastructure, each of the mobile devices (nodes) are allowed to move freely in any direction. Since the nodes leave and join the network without notice it is a challenge to route (ensure proper sending of data (packets)) from one node to another compared to other networks such as the LAN and WAN with a stable topology designed for them. Ad hoc On-Demand Distance Vector (AODV) routing protocol is an on-demand routing algorithm that was initiated to improve routing of data in MANET, it was meant for a number of mobile nodes in a designated particular area (a hundred nodes and more). In comparison to other routing protocols for mobile ad-hoc devices (DSR, DSDV) AODV routing protocol has better characterizing features like a highly dynamic topology, the very limited resources of band width and computational power [9].

Project aims and objectives:

Design and configure 802.11 communications technology for testing.

Implement the algorithm of the routing protocol using Network Simulator 2.

C/C++ programming.

Analyzing the performance of the routing protocol under different criteria.

Scope of the project:

With recent advancement in computer and wireless communication technologies, wireless networking of advanced mobile computing devices is expected the most developing and increasingly wide spread application, much of which will involve the use of different routing protocol. The Ad hoc On Demand Distance Vector (AODV) routing procedure is to support efficient proper routing between the mobile devices under a very dynamic network where the mobile devices are allowed to live and join the network freely.

AODV is classified as an on demand routing protocol that enables mobile nodes to obtain routes rapidly for new destinations. It allows mobile nodes to act fast in case of link breakages and changes in network topology [1]. It is known for prevention of loops by using a destination sequence number for proper route maintenance [1].

Project review:

Terminologies used in AODV routing:

Originating node (source node):

A node that initiates the process of finding a route to a particular node (destination node) in an ad hoc network by broadcasting a RREQ packet to its neighbours.

Destination node:

This is a particular node requested by the source for communication or a data transfer link.

Active route:

A suitable route towards the destination identified by the routing table entry.

Broadcast:

Broadcasting means transmitting packets to the required node specified by broadcast id address.

Forwarding node:

A node that is part of an established route between the source node and destination node acting as a router.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

Forwarding route:

A route set up to send data packets from a source node to the requested destination [1].

Invalid route:

A route that is no longer being used a link for communication or data transfer due to the routing table entry comparisons between the source node and destination node.

Reverse route:

A route set up to forward a reply (RREP) packet back to the source node from the destination or from a forwarding node having a route to the destination.

Sequence number:

A particular number given to a packet (RREQ) as identification in an ad hoc network, this number constantly increases and is maintained by each originating node.

Organisation of the project:

Chapter 1

This chapter introduces the project. It defines and summarizes the purpose of MANETS and why it is preferred to use AODV routing protocol for these networks in simple words. It also explains some of the difficult terms used in this report regarding the project topic. This chapter also highlights what is discussed in each chapter for this report.

Chapter 2

This chapter briefly explains the mobile adhoc networks and there characteristics. It also mentions some of the routing protocols and the difference in their algorithms in MANETs such as Dynamic Source Routing (DSR), Destination Sequenced Distance Vector (DSDV) and Ad hoc On Demand Distance Vector (AODV). It explains the algorithm of the AODV protocol, how a route or path is initiated in case a node decides to communicate with another or other nodes. It also explains some of the advantages of AODV routing protocol over other routing protocols and why it is preferred to be used in MANETS.

This chapter also shows some of the related work that is similar to my project.

Chapter 3….

Chapter 4….

CHAPTER 2

MANETS

MANET; (MOBILE AD HOC NETWORKS)

This is a group of nodes with a network that has no infrastructure but keeps changing due to the mobility of the nodes. This network is self configuring and each node is free to move independently in any direction, this often forces the nodes to change its links with other devices. This type of network has a very dynamic wireless mesh topology and uses the packet switching method to exchange data between the different nodes [9].

Characteristics of MANETS:

Dynamic topologies

Nodes are free to move arbitrarily; thus, the network topology may change randomly and rapidly at unpredictable times, and may consist of both bidirectional and unidirectional links.

Bandwidth-constrained, variable capacity links

Wireless links will continue to have significantly lower capacity than their hardwired counterparts. In addition, the realized throughput of wireless communications after accounting for the effects of multiple access, fading, noise, and interference conditions is often much less than a radio's maximum transmission rate.

Energy-constrained operation

Some or all of the nodes in a MANET may rely on batteries or other exhaustible means for their energy. For these nodes, the most important system design criteria for optimization may be energy conservation.

Limited physical security

Mobile wireless networks are generally more prone to physical security threats than are fixed-cable networks. Existing link security techniques are often applied within wireless networks to reduce security threats. As a benefit, the decentralized nature of network control in MANETs provides additional robustness against the single points of failure of more centralized approaches.

[4]

Routing protocol:

This is a certain procedure that nodes follow when they decide to route packets amongst themselves in MANET. Some of the most common routing protocols in the Ad hoc routing community are;

Destination Sequenced Distance Vector (DSDV)

DSDV is a hop-counting distance vector protocol requiring each node to periodically broadcast routing updates. The main advantage of DSDV over traditional distance vector routing protocols is that it guarantees loop freedom.

In DSDV, each node maintains a routing table that has an entry for each destination in the network. The attributes for each destination are the next hop ID, hop count metric and a sequence number which is originated by the destination node. DSDV uses both periodic and triggered routing updates. Triggered routing updates are used in addition to the periodic updates in order to propagate the routing information as quickly as possible whenever there is any topological change. The update packets include the destinations accessible from each node and the number of hops required to reach each destination along with the sequence number associated with each route [3].

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

Dynamic Source Routing (DSR)

DSR is based on source routing, where the source specifies the complete path to the destination in the packet header and each node along this path simply forwards the packet to the next hop indicated in the path. It utilizes a route cache where source routes it has learned so far are cached. Therefore, a source first checks its route cache to determine the route to the destination. If a route is found, the source uses this route. Otherwise, the source uses a route discovery protocol to discover a route. A route is sought only by a source when needed.

In route discovery, the source floods a query packet through the ad-hoc network, and the reply is returned by either the destination or another host that can complete the query from its route cache. Each query packet has a unique ID and an initially empty list. Upon reception of a query packet, if a node has already seen this ID (i.e. it is a duplicate) or if it finds its own address already recorded in the list, it discards the copy and stops flooding; otherwise, it appends its own address to the list and broadcasts the query to its neighbours. If a node can complete the query from its route cache, it may send a reply packet to the source without propagating the query packet further. Furthermore, any node participating in route discovery can learn routes from passing data packets and gather this routing information into its route cache. This route discovery protocol is similar to the Internet's Address Resolution Protocol (ARP) except that ARP requests do not propagate beyond a router [3].

Ad hoc On Demand Distance Vector; (AODV)

AODV is an on demand routing algorithm that uses particular messages in form of packets to communicate each other. These messages are known as RREQ used to find a route to a destination, RREP used for route discovery, RERR used in case of link breakages and Hello messages which are used to detect whether the neighbours of the nodes are still in range. When a particular node desires to communicate with a specific node in an ad hoc network, it broadcasts a RREQ to its neighbours, when an existing route is discovered a unicast message of an RREP packet is sent back to the source node from the destination and then data transmission begins immediately.

The following metrics can be used to analyze the performance of any routing protocol;

End-to-end data throughput and delay: Statistical measures of data routing performance (e.g., means, variances, distributions) are important. These are the measures of a routing policy's effectiveness, how well it does its job as measured from the 'external' perspective of other policies that make use of routing.

Route Acquisition Time: A particular form of 'external' end-to-end delay measurement of particular concern with "on demand" routing algorithms. It is the time required to establish route(s) when requested.

Percentage Out-of-Order Delivery: An external measure of connectionless routing performance of particular interest to transport layer protocols such as TCP which prefer in-order delivery.

Efficiency: If data routing effectiveness is the external measure of a policy's performance, efficiency is the 'internal' measure of its effectiveness. To achieve a given level of data routing performance, two different policies can expend differing amounts of overhead, depending on their internal efficiency.

[4]

It is useful to track several ratios that illuminate the 'internal' efficiency of a protocol in doing its job (there may be others that the authors have not considered):

Average number of data bits transmitted to the data bit delivered. This can be thought of as a measure of the bit efficiency of delivering data within the network. Indirectly, it also gives the average hop count taken by data packets.

Average number of control bits transmitted/data bit delivered. This measures the bit efficiency of the protocol in expending control overhead to delivery data. Note that this should include not only the bits in the routing control packets, but also the bits in the header of the data packets. In other words, anything that is not data is control overhead, and should be counted in the control portion of the algorithm.

Average number of control and data packets transmitted/data packets delivered rather than measuring pure algorithmic efficiency in terms of bit count, this measure tries to capture a protocol's channel access efficiency, as the cost of channel access is high in contention-based link layers.

Essential parameters that should be varied include:

Network size.

This is measured with the number of nodes in the network.

Network connectivity.

This is the average number of neighbors of a node.

Topological rate of change.

The speed with which the topology of a network is changing.

Link capacity

Effective link speed measured in bits per second, after accounting for losses due to multiple access, coding, framing, etc

Fraction of unidirectional links.

How effectively does a protocol perform as a function of the presence of unidirectional links?

Traffic patterns.

How effective is a protocol in adapting to non-uniform or crowded traffic patterns?

Mobility.

What is the most appropriate model for simulating node mobility in a MANET?

Fraction and frequency of sleeping nodes.

How does a protocol perform in the presence of sleeping and awakening nodes?

AODV ROUTING PROTOCOL:

Ad hoc On Demand Distance Vector (AODV);

This is a routing protocol for mobile ad hoc networks designed to accommodate small and large networks even if the nodes in the network are as many as several thousand nodes. This routing method is reactive and the routes are created on demand i.e. nodes that do not lie on the active paths neither maintain any routing information nor participate in any periodic routing table exchange [2]. Nodes maintain routes by using two separate counters. These counters do not contain information about the whole path, only the source and the destination. [AODV junior]AODV has many great features [6]:-

Built for mobile networks

Creates routes on demand

Loop free with quick convergence

Scales well

Fits easily into the existing protocol stack

The above features currently make AODV the easiest and most widely implemented MANET protocol.

Because of the difficulty of testing an ad hoc routing protocol in a real world environment, a simulation is used so that the AODV routing protocol is tested in a variety of scenarios to analyze the performance of the routing protocol.

BASIC AODV ALGORITHM;

PATH DISCOVERY:

When there is need for a node (source node) to send data/communicate with a particular node (destination) whose data is not available in its (source) routing table entry, the process of finding a link to the destination begins. Every node maintains two separate counters; sequence number and broadcast id [2]. The source node will send a RREQ in form of packets to all its neighbouring nodes which is known as broadcasting.

This RREQ packet includes

Source address

Source sequence number ( for maintaining freshness information about the reverse route)

Broadcast id (incremented whenever source issues a new RREQ )

Destination address

Destination sequence number (for maintaining freshness of the route to the destination before it can be accepted by the source)

Hop count

When any node receives a RREQ it checks for the sequence number and broadcast id for the RREQ, if it has already received a RREQ with the same broad cast id and sequence number it will ignore the RREQ otherwise if it had not yet received the RREQ it will broadcast it again to its neighbours after increasing its hop count [2]. Each intermediate node keeps the following information:

Destination IP address

Source IP address

Broadcast id

Expiration time for reverse path route entry

Source sequence number.

REVERSE PATH SETUP:

While the RREQ is still in its broadcast transit it traces its path by taking records till the source. Each node keeps track of its neighbours by taking the address of the node that originated the request and a RREQ id number [5]. The reverse path entries are given time to locate the destination required by the source node.

FORWARD PATH SETUP:

When the RREQ packet reaches node that has an entry to the required destination node by the source it checks whether the route is current by comparing the destination sequence number of the RREQ to the one in its route table entry [2]

If the sequence number for destination is greater than the one its route table entry it does not use this route to respond to the RREQ. If the sequence number for the destination is equal to the one in its route table entry but with a smaller hop count, or greater the node unicasts a RREP packet the node where the RREQ originated.

If the node is the destination it checks whether the RREQ was received over a bidirectional link [2]. A RREP contains the following information:

Source address

Destination address

Destination sequence number

Hop count

Life time

When a RREP packet is sent back to the source node following the reverse path it notifies the nodes in the reverse path that the forward path has been confirmed. The nodes in the reverse path will update their time out information for their route table entries to the source and destination.

When the source receives a RREP it begins the data transmission and can later update its routing information it comes up with a better route [2].

Figure (1): A possible path for a route reply RREP if A wishes to find a route to J [8].

Figure (1) illustrates an AODV route lookup session. Node A wishes to initiate traffic to node J for which it has no route, A broadcasts a RREQ which is flooded to all nodes in the network. When this request is forwarded to J from H, J generates a RREP. This RREP is then unicasted back to A using the cached entries in nodes H, G and D [8].

Because movement of the nodes there is dynamic changes in the links, link breaks usually occur in an active route. The node in the direction towards the source of the break broadcasts a route error (RERR) packet containing a list of all destinations which are now unreachable due to the loss of the link. The RERR is propagated back to the source node and once received the source may reinitiate path discovery if it still needs the route.

Flow chart diagram showing the Algorithm of AODV routing protocol (node processing an incoming message);

Figure (2): Shows the action of AODV when processing an incoming message [5].

EXPECTED RESULTS:

PERFORMANCE AND ANALYSIS

Network Simulator 2 [NS-2] is an event driven open source software. This simulator is targeted at network research over wired and wireless networks. This simulator is used as a basis for AODV implementation, certain assumptions and simplifications can be made in a simulation that are not valid in a real world scenario, which makes it important to implement the protocol once the simulation is complete [7].

Routing protocols are vital for the proper functioning of the ad hoc networks. AODV algorithm always chooses a route based on the metrics, the smallest number of hops to the destination, this might not be the most significant route when there is congestion in the network and may cause the packet drop rate, packet end to end delay or routing over head to be increased. Performance metrics used in AODV routing protocols [3], [9];

Throughput

Ratio of packets delivered to the total number of packets sent.

Average end to end delay

This is time taken for the packets to reach the destination. This is the average overall delay for a packet to traverse from a source node to a destination node.

Routing overhead

The number of packets delivered to the total number of packets sent.

Normalized routing load

This is the number of routing control packets per data packet delivered at the destination.

Round Trip Time (RTT): Time difference between the receipt of the acknowledgement from the destination node to the source node and the time of transmission of the original packet at the source node

Average number of nodes receiving packets: Sum of numbers of all the intermediate nodes receiving packets sent by all the source nodes divided by the number of received packets at all the destination nodes.

Average number of nodes forwarding packets:

Sum of numbers of all the intermediate nodes forwarding packets sent by all the source nodes divided by the number of received packets at all the destination nodes.

Delays between current and other node: 

Shows the end-to-end delays (in seconds) between the current node (sender) and the other node (receiver).

Number of data packets dropped:

The number of data packets dropped at any given node. This is an important parameter because if the number of dropped packets increases, the throughput decreases.

Basing on the above metrics under effects of different load conditions [3] the performance of the routing protocol will be analyzed. Some of the effects

Pause time

Mobility

Bit rate

Number of traffic generators [9]

Related work.

Performance Comparison of AODV, DSDV and I-DSDV Routing Protocols in MANETS

This work was done in University Putra Malaysia in the Department of Communication Technology and Network. The project mainly concentrated on performance of three routing protocols AODV, DSDV and I-DSDV using NS2. They managed to grasp the major difference between AODV and DSDV since one is reactive and the other is proactive as detailed above. They compared DSDV and I-DSDV algorithm by reconstructing the scheme of messaging for their invalid routes and through simulation they discovered that I DSDV reduces the number of dropped data packets with little increased over head at higher rates of node mobility but still could not compete with AODV in higher node speed and number of nodes. There experimental results were based on various number of nodes, different pause times with constant number of nodes,speed and different node speed.

Performance Analysis and Comparison of Ad hoc Routing Protocols.

This project was under Mobile Computing and was done by the Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County. Different routing protocols for MANETS were studied in this project namely DSR, AODV, DSDV and CEDAR (Core Extraction Distributed Ad-Hoc routing) which is mainly used for high bandwidth. They used NS2 for their simulations and the performance of the different routing protocols were compared qualitatively and quantitavely. Simulations were done with a Random Way point model in a rectangular field. They used pause times, random destinations, various sizes for mobile node movement and randomly selected speed that is uniformly distributed. In this project I am mainly interested in their analysis for the AODV routing protocol and the conclusion they came up with.

An Implementation Study of the AODV routing protocol.

This study was done by Elizabeth M. Royer from the Department of Electrical and Computer Engineering, University of California Santa Barbara and Charles E. Perkins Communications System Laboratory Nokia Research Centre. In this study they focused on the implementation of the AODV routing protocol. They also mentioned the purpose of simulating routing protocols with different metrics and criteria before it is implemented in the real world. The paper highlighted there recent work in the past and the necessary changes of implementing the routing protocol. My interest in this study was the operation of the AODV routing protocol which was mainly focused on the unicast and multicast operations of the protocol.

AODV Jr AND AODV SIMPLIFIED

This paper was written from the National Institute of Standards and Technology, Gaithersburg, Maryland USA. AODVjr is a simplified version of AODV protocol in such a way that some items are removed from the AODV protocol its self like sequence number, hop count and Hello messages etc. The result showed that AODVjr performs as well as AODV and describes other positive effects of a smaller protocol specification. In relation to my report it has simulation and results of the AODV protocol which for the analysis of the AODV protocol its self for my report.

A COMPARISON OF IMPROVED AODV ROUTING PROTOCOL BASED ON IEEE 802.11 AND IEEE 802.15.4

This project was done executed from the Department of Information and Telecommunication Engineering Korea Aerospace University. The significance of the project was to show the performance of Improved AODV (I-AODV) using QualNet as the simulator. For I-AODV if a node finds a new shortest routing path it resets the routing path to the shorter one even before the expiry time of the longer path. This is done in the process of sending packets. The performance of the routing protocol was implemented and analyzed by QualNet. Their use of different software and IEEE 802.11 communication technology got me interested because the communication technology relates with my hardware model design and I would relate my performance comparisons with theirs.

Design Routing Protocol Performance Comparison in NS2 with AODV comparing to DSR as Example.

This project was done by Yinfei Pan Department of Computer Science SUNY Binghamton. This document mainly helps new users of NS2 software dealing with wireless networks and their routing protocols. It provides some simple and understandable trace file formats and TCL (Tool Command Language) codes that are used by the software for simulation and analysis which make the simulation software more practical. In relation to my work it shows some analysis of two routing protocols used in MANETS which are AODV and DSR. I focused more on their work regarding AODV and how they managed to evaluate its performance under different criteria.

Performance Analysis of MANET Routing Protocols in the Presence of Self-Similar Traffic.

This project was done by Ahmed Al-Maashri and Mohamed Ould-Khaoua form the Department of Electrical and Computer Engneering, Sultan Qaboos University in Oman. This project explains in brief some of the famous routing protocols in MANETS which are DSDV, OLSR and AODV.It also focuses on the analysis of their performance. They concluded that different routing protocols can behave in different ways under different criterias basing on the traffic whether Self similar or Bursty.