Implementation and Analysis of GPSR and ALERT Protocol Techniques in AODV for MANET

Implementation and Analysis of GPSR and ALERT Protocol Techniques in AODV for MANET

Jitender Kumar

M.Tech CSE

United College of Engineering and Research Allahabad (U.P.), INDIA

Agam Verma

M.Tech CSE

United College of Engineering and Research Allahabad (U.P.), INDIA

Abstract: In past few years the world have seen a very rapid advancement and expansion in the field of mobile computing especially in mobile ad-hoc networks because of less expensiveness and large number of mobile devices [1]. MANET stands for mobile ad-hoc network is a network made up of a collection of wireless mobile nodes (or devices: mobiles, laptops, sensors) and these nodes may communicate with each other over a wireless medium to exchange necessary information [1]. MANET protocols are very important for doing some research [2]. Analysing routing algorithms and doing some efforts for making these algorithms performs much better is a wide area of research now a days. In this paper we present analysis of Ad-hoc On Demand Distance Vector Routing (AODV), a novel algorithm for the operation of such mobile ad-hoc networks [3]. AODV stands for ad-hoc on demand distance vector a very important routing scheme for mobile ad-hoc network. Main aim of AODV scheme is to reduce the number of broadcasting packets by discovering the routes on demand instead of keeping all updated route information. AODV performs transfer of packets on demand so it performs well. With the implementation of ALERT and GPSR techniques on AODV we can provide anonymity to the network. GPSR stands for greedy perimeter stateless routing, for wireless mobile networks; GPSR is a responsive and efficient routing protocol [4] that uses the positions of routers and a packets destination to make packet forwarding decisions [5]. GPSR uses greedy approach for packet forwarding decisions by using only information about immediate neighbours of corresponding router in the topology and where it seems that greedy approach cant be applied GPSR uses routing around the perimeter of the region to recover. ALERT stands for Anonymous Location-based Efficient Routing protocol, dynamically partitions the network field into zones and randomly chooses nodes in zones as intermediate relay nodes, which form a non-traceable anonymous route [6]. This paper represents an idea about implementing GPSR and ALERT techniques in AODV routing protocol and then compare the performance of those based on parameters such as throughput, packet delivery ratio, and packet delay using gnu plot.

Keywords: MANET, routing, AODV, GPSR, ALERT, protocols, comparison, ns2, gnu plot

1. INTRODUCTION

   A mobile ad hoc network named as MANET is a collection of wireless mobile nodes that dynamically establishes the network in the absence of fixed infrastructure

   [7]. One of the main and unique features of MANET is that each and every node is able to act as a router so that packets can be forwarded by finding and establishing an optimal path.

   MANET has become a most emerging technology now days because users can communicate with each other without any physical infrastructure and also there is no need to know about their geographical location [2]. In present MANET is the most important research area for researchers for establishing the efficient ad-hoc network using available different routing schemes and analyzes this network with the help of different network simulation tools such as ns2.

   In this paper we take the most important routing scheme of the MANET named AODV (Ad-hoc On-demand Distance Vector) for our research. This scheme is important because it is capable of both unicast and multicast routing [8].AODV done route establishment and packet forwarding on demand without having all updated route information. In our proposed work we implement GPSR and ALERT technique in AODV and then analyze the performance of AODV after implementing GPSR and ALERT technique using the simulation tool ns2. GPSR (Greedy Perimeter Stateless Routing) is a responsive and efficient routing protocol for mobile, wireless networks. GPSR exploits the correspondence between geographic position and connectivity in a wireless network, by using the positions of nodes to make packet forwarding decisions. ALERT (Anonymous Location-based Efficient Routing Protocol) dynamically partitions the network field into zones and randomly chooses nodes in zones as intermediate relay nodes, which form a non-traceable anonymous route.

   In particular, the section 2 describes the three protocols: AODV, GPSR and ALERT in detail, in section 3 we describes our proposed work in which we implement the techniques of GPSR and ALERT in AODV, the section 4 shows the simulation results and performance analysis based on network simulator ns2 and gun plot used to draw the comparison graph and finally section 5 describes the conclusion of the work.

2. OVERVIEW OF THREE USED PROTOCOLS: AODV, GPSR AND ALERT

   In this section we give the important details about the

   protocols which we are going to use in our research work so that one can easily understand the purpose of this research paper. The details of the three protocols are as follows:

   • AODV (Ad-hoc On-demand Distance Vector Routing): AODV routing scheme is an important scheme of mobile ad- hoc network. AODV comes under reactive protocols, in these types of protocols routes are not predefined, and routes are created on demand of the source node [9]. As being in the category of reactive protocol AODV needs to maintain only the information of the active routes. AODV maintains the route information by creating a routing table at each node. In these tables it stores routing information as destination and next hop addresses as well as the sequence number of a destination. Next to that a node also keeps a list of the precursor nodes, which route through it, to make route maintenance easier after link breakage. To prevent storing information and maintenance of routes that are not used anymore each route table entry has a lifetime. If during this time the route has not been used, the entry is discarded.

     AODV mainly operates by two important functions, first is route discovery and second is route maintenance. When a node wants to forward some packets to some destination node it needs a route so when a route is needed the protocol starts the route discovery phase. After this process the source node sends route request message to its neighbors and if the neighboring nodes do not have any information about the destination node, they broadcast the message to all their neighbors and so on. After this if any neighbor node has the information about the destination node, that node sends route reply message to the node from which it receives the route request message. On the basis of this process a path is recorded in the intermediate nodes. This path identifies the route and is called the reverse path. Since every node forwards route request message to all of its neighbors, more than one copy of the original route request message can arrive at a node. Due to this reason, a unique id is assigned with each message, when a route request message is created. When a node received the message, it will check this unique id and the address of the initiator and it discarded the message if it had already processed that request. Node that has information about the path to the destination node sends the route reply message to the neighbor from which it has received route request message. This neighbor follows the same process. Then the route reply message travels back using reverse path. When a route reply message reaches the initiato the route is ready and the initiator can start sending data packets. Thus AODV does route development and packet forwarding.

   • GPSR (Greedy Perimeter Stateless Routing): GPSR is a novel routing scheme for mobile ad-hoc networks uses the geographical positions of nodes (routers) and a packets destination address to make packet forwarding decisions [5]. GPSR is a responsive and efficient routing protocol for mobile, wireless networks. GPSR uses greedy forwarding approach to forward the packets to the nodes that are always immediate neighbors to the destination node. In those areas of the network where such a greedy forwarding path does not exist, then GPSR recovers by forwarding in perimeter mode, in which a packet traverses successively closer faces of a planar sub graph.

     The below figures shows the two approaches:-

   • ALERT (Anonymous Location-based Efficient Routing Protocol): Anonymity is the most important issue in mobile ad- hoc networks protocols because by using the anonymous protocols MANET is able to hide the network routes and identities of nodes from outside observers for securing the network [6]. But all the available anonymous protocols are very expensive and complex because of their style of implementation. So in [6] they have proposed a new anonymous protocol for MANET which provides full anonymity and less complex and less expensive. ALERT protocol works in zones and zones are created by dynamically partitioning of the network and in every zone ALERT randomly chooses the nodes as intermediate relay node [6]. All the intermediate relay nodes form a non-traceable anonymous route together. This protocol also able to hide the packet initiator/receiver among many initiators/receivers to make stronger anonymity protection for source and destination. In this manner, ALERT protocol offers anonymity protection to sources, destinations, and routes [6].

   The below figure shows the working scheme of the ALERT protocol:-

   The above figure shows the packet forwarding technique of the ALERT protocol. ALERT protocol uses hierarchical partitioning to separate source from destination. The description of ALERT process for forwarding packet as shown in the diagram above is as follows:

   There is a source and destination pair in the network, source(S) check if the destination is in the same zone where source itself then it performs vertical partition to separate form destination as shown in figure. After this source randomly selects a node very near to it in the other zone as a temporary

   destination (TD) and this node is called random forwarder (RF).After this source uses GPSR protocol to forward the packet to this randomly selected temporary destination using some relay nodes. Relay nodes are selected randomly in each zone for data forwarding and used for dynamically generating an unpredictable routing path for packet. RF then check if destination and itself are in same zone then it performs hierarchical partitioning to separate form destination and performs the same process as performed in first zone by source. This process continues until it reaches the destination zone, ZD. The shaded part in the figure shows the destination zone, ZD. The zone in which the real destination is located with some nodes is called the destination zone, ZD, because to provide anonymity so that no one cannot find the location of destination ALERT broadcast the packet to all nodes in the destination zone. Now the question arise that how a node get to know that it is in the same zone as the destination and when to stop partitioning?

   For this problem ALERT provides a formula [6] which is as follows:

   In this formula H denotes the total number of partitions in order to produce destination zone, ZD. G is the size of the entire area of the network. is the node density and k is the number of nodes in the destination zone, ZD. With the calculation of H with the help of these values (G, k, ) source S can find the location of destination zone. After finding the position of the destination zone S divides the zone horizontally if first partition is vertical or vertically if first partition is horizontal and the process of partitioning continues until H partitions are completed. The final generated zone is the desired destination zone, and its position can be retrieved accordingly.

3. PROPOSED WORK

   In the proposed work two different strategies are implemented on AODV protocol but the process is same when the connection is required it broadcasts a request for connection to the other nodes present in the network but the difference is in the path made between source and destination. First strategy is based on the GPSR protocol in which links created between two nodes on the basis of distance between the nodes. The nodes having short distance to create a path from source to destination are chosen on the basis of formula given by:-

   Distance= (xi – xj )2 + (yi – yj )2

   The second strategy is based on the ALERT protocol in which the links are created on the basis of their location in the region defined as well as the distance those nodes are chosen who have short distance to create a path from source to destination.

   First strategy based on GPSR protocol:-

   The first strategy based on the GPSR protocol implemented on AODV protocol is that the distance is calculated between every node in the network after that a

   range is set to compare with the distance between every node. The distance should be less than the range set.

   After that the links are created between different nodes whose distance is less than the set range. To make a link between two different nodes in the network a comparison is made between the distance of two nodes and the range. After this comparison a link is created only if there is no next hope of the current node.

   Finally using these different links made for the short distance a final link is created from source to destination by traversing the different links from source till the destination is reached. In this way a path is created using GPSR technique for AODV protocol.

   In this scheme we use greedy forwarding approach of GPSR technique with AODV. The working of this scheme is shown in below figures:-

   In this very first step of our proposed scheme, for transferring the packet from source to destination each and every node of the network creates a link between their closest neighbors and calculates the distance between them. In the figure d1, d2, d3, d4, d5, d6, represents the distance between nodes connecting the link between them.

   In the second step the distance of each link is compared with the range, R, which is predefined by the programmer. Those links which have larger distance value than the range will be discarded and those links are maintained which have distance value less than the range.

   Finally, the packet starts to reach the destination through available links. First it tries a link to reach the destination if it cant get the destination then it tries for another available link to reach the destination. Thus the final path is created to transfer the packet to the destination.

   Second strategy based on ALERT protocol:-

   The second strategy is based on ALERT technique implemented on AODV. In this strategy, we take MANETs most important protocol AODV and we apply the ALERT protocol techniques on AODV for providing anonymity to the AODV protocol so that the route of packet forwarding cannot be determined and also location of the source and destination cannot be determined by the attacker. Thus using this strategy we can make AODV more secure.

   This strategy works as follows:-

   As given that we are using AODV so as its nature it broadcast the path request message to all the nodes in the network and from which node it receives the response it establishes the path with them and transfer the packet to them. But in our case we apply the ALERT technique in AODV for anonymity protection, for this as in ALERT it partitions the network ito zones according to the formula

   but in our strategy we fix the zone partition value to four, means it partitions the network into four zones (zone1, zone2, zone3, and zone4). In very first step it divides the network into four zones (zone1, zone2, zone3, and zone4).

   We also define a new variable in our strategy which is distance between each node, we fix this value to a number (in our case it is 200). In the second step it finds that the neighbors of the source and destination are located in which zone out of four defined zone, for finding zone location in network to check for node in zone we fix the value of upper-

   left and lower right value of each zone. After finding each neighbor location in zones it calculates the distance of each neighbor from destination and finally selects those nodes which have distance value less than the fixed value (which is 200 in our case) as well as the node should fall in some region out of four regions. After the selection of nodes source node multicast the packets to all neighbors of the destination and which neighbors have minimum distance value creates the final path form source to destination. So because of multicasting and nodes being in different zones the actual location of destination cannot be determined by the attacker. Thus AODV can provide anonymity with the use of ALERT technique.

4. PERFORMANCE ANALYSIS BASED ON SIMULATION RESULTS In this section we describe the simulation setup for our proposed work and analyze the obtained results. We also make a comparison chart between AODV with the technique of GPSR and AODV with the technique of ALERT for different parameters such as throughput, packet delivery ratio,

   and packet delay.

   There are many simulators available for simulation work. For our work we use the simulator NS2. NS2 stands for network simulator version2. We use ns2 because it is easy to use and open source for research work. NS2 provides substantial support for simulation of TCP/UDP, routing, and multicast protocols over wired and wireless (local and satellite) networks [10]. In [10] the author Marc Greis provides complete detailed description of ns2 for all type of users of ns2, the person who is aware of ns2 or unaware may easily learn from [10] how to work on ns2. So we use ns2 for our work so that one can easily understand this paper.

   After the simulation process the next step is to prepare the comparison graph for throughput, packet delivery ratio, and packet delay for this we use gnu plot which is a command-line program that can be used to generate 2D or 3D plots of functions, data and data fits. Gnu plot can produce outputs in many formats including Portable Network Graphics (PNG), Encapsulated PostScript (EPS), Scalable Vector Graphics (SVG), JPEG and many others. It can also produce LaTeX code that can be included directly in LaTeX document.

   In our simulation we make comparison between AODV with the technique of GPSR and AODV with the technique of ALERT for different number of nodes such as in our work we do simulation for 50 nodes and 60 nodes and for 70 nodes. We compare both techniques on the basis of the results of their throughput, packet delivery ratio, and packet delay.

   The simulation scenario for our work is as follows:

   Table I. Simulation Setup

   	For 50 nodes	For 60 nodes	For 70 nodes
   Routing Protocol	AODV	AODV	AODV
   Simulation Area	900×900	900×900	900×900
   Simulation Time	10 seconds	10 seconds	10 seconds
   MAC Layer Protocol	IEEE 802.11	IEEE 802.11	IEEE 802.11
   Traffic Type	CBR(UDP)	CBR(UDP)	CBR(UDP)

   • Simulation results for packet delay for 50,60 and 70 nodes:-

     well in the desired network. We analyze both techniques for 50 nodes and 60 nodes and for 70 nodes and as shown in above figures the results comes out that when we implement the ALERT technique in AODV then the result of Throughput ,packet delivery ratio and packet delay is better then, when we implement the technique of GPSR in AODV.

     The simulation results shows above tells that ALERT- AODV is better than the GPSR-AODV. But the important note is that the ALERT technique performs better when the network is divided into different regions and GPSR performs well when network is determined as a geographic region.

     So conclusion is that both techniques may be used with AODV for different purposes. In future work one can analyze these techniques for a wide network by increasing the number of nodes greater than 150 or more and also for varying pause time.

   • Simulation results for packet delivery ratio for 50,60 and 70 nodes:-

   • Simulation results for throughput for 50,60 and 70 nodes:-

5. CONCLUSION OF THE WORK

   As we have discussed yet about the two new approaches for implementing the most important routing technique of the mobile ad-hoc network, AODV, both techniques performs

6. ACKNOWLEDGMENT

   A number of people have made this paper possible. In particular I wish to thank my best friend, Mr. Agam Verma, for providing much needed help and support and my teachers for their guidance and displaying inconceivable patience and my family and friends for constantly asking me when I would finish my thesis and lastly my mother for teaching me never to give up on any endeavor.

7. REFERENCES

1. An Overview of Mobile Ad Hoc Networks: Applications and Challenges, Jeroen Hoebeke, Ingrid Moerman, Bart Dhoedt and Piet Demeester, Session 4.

2. MANET: Vulnerabilities, challenges, Attacks, Application, Priyanka Goyal, Vinti Parmar, Rahul Rishi, IJCEM International Journal of Computational Engineering & Management, Vol. 11, January 2011.

3. Ad-hoc On-Demand Distance Vector Routing, Charles E. Perkins, Sun Microsystems Laboratories, Advanced Development Group

   ,Menlo Park,CA, Elizabeth M. Royer, Dept. of Electrical and Computer Engineering, University of California, Santa Barbara, CA.

4. http://www.cs.cmu.edu/~./bkarp/gpsr/gpsr.html.

5. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks, Brad Karp,Harvard University / ACIRI, H. T. Kung, Harvard University, MobiCom 2000.

6. ALERT: An Anonymous Location-Based Efficient Routing Protocol in MANETs, Lianyu Zhao, Haiying Shen, IEEE transactions on mobile computing, vol. 12, no. 6, june 2013.

7. C.Sivaram murthy, B.S.Manoj, Adhoc wireless networks:Architectures, and protocols, Pearson Education, 2004.

8. http://moment.cs.ucsb.edu/AODV/aodv.html.

9. Performance Comparisons of Routing Protocols in Mobile Ad hoc Networks, International Journal of Wireless & Mobile Networks (IJWMN) Vol. 3, No. 1, February 2011.

10. http://www.isi.edu/nsnam/ns/