Effectiveness Of Genetic Algorithm In Reactive Protocols For MANET

Effectiveness Of Genetic Algorithm In Reactive Protocols For MANET

Arun Biradar, Dr. Ravindra C. Thool

Dept. of CSE, East West Institute of Technology, Bangalore, Karnataka, India Dept. of IT, SGGS Institute of Engineering & Technology, Nanded, Maharashtra, India

Abstract

Mobile Ad-hoc networks (MANET) consist of mobile platforms which are free to move arbitrarily. These are self-organizing and adaptive networks. These networks allow spontaneous formation and deformation of mobile networks. Shortest path problem in MANETS asks for the computation of path from source to destination node that minimizes the sum of total cost associated with the path. Several traditional algorithms like Bellman ford Algorithm, Dijkstras Algorithm are developed to find the shortest path. These algorithms are not suitable for MANETS, but are suitable onlyfor wired networks. For wireless networks, biologically inspired algorithms like Genetic Algorithm work efficiently. Genetic Algorithm techniques have been recently adopted in the networking arena to design efficient network protocols. On the other hand, multipath routing protocols have been considered far more robust than the single path routing protocols in MANETs because the topology changes in MANETs are quite frequent. A few researchers have also demonstrated the effectiveness of GA in MANETs. However, it is demonstrated only in the context of single path routing protocols. This paper aims to explore the effectiveness of GA in multipath routing protocols to improve the MANETs performance. Thorough analysis on efficiency is incorporated, demonstrating the feasibility and effectiveness of the proposed architecture.

1. Introduction

   Wireless Ad hoc networks are collection of two or more devices equipped with wireless communications and networking capability. These networks are without base stations or can also be called as infrastructure less networks.

   Mobile Ad hoc networks (MANETS) consists of mobile platforms which are free to move arbitrarily. These are self organizing and adaptive networks. These networks allow spontaneous formation and deformation of mobile networks.

   Shortest path problem in MANETS asks for the computation of path from source to destination node that minimizes the sum of total cost associated with the path. Several traditional algorithms like Bellman ford Algorithm, Dijkstras Algorithm are developed to find the shortest path. These algorithms are not suitable for MANETS, but are suitable only for wired networks.

   For wireless networks, biologically inspired algorithms like Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Evolution Algorithm (EA) can be implemented efficiently.

   Genetic Algorithm is an adaptive search algorithm based on natural evolution and genetics. Major steps involved here are generation of population of solutions, using fitness function and application of genetic operators.

   Genetic algorithm is applied with different routing protocols. The different routing protocols are Ad hoc On demand Distance Vector (AODV), Ad hoc On demand Multipath Distance Vector(AOMDV), Dynamic Source Routing(DSR), Destination Sequenced Distance Vector Routing(DSDV). Genetic Algorithm when applied with AOMDV provides the best results in terms of performance.

2. Background

   Wireless Ad-hoc Networks are a collection of two or more devices equipped with wireless communications and networking capability. These devices can communicate with other nodes that immediately within their radio range or one that is outside their radio range. For the later, the nodes should deploy an intermediate node to be the router to route the packet from the source toward the destination. The Wireless Ad-hoc Networks do not have gateway, every node can act as the gateway. Almost every wireless network nodes communicate to base-station and access points

   there by co-operating to forward packets hop by-hop. Wireless ad hoc networks can be further classified as:

   1. Mobile Ad hoc Networks (MANETs)

   2. Wireless Mesh Networks (WMNs)

   3. Wireless Sensor Networks (WSNs)

      Mobile Ad hoc networks (MANETS) consists of mobile platforms which are free to move arbitrarily. These are self organizing and adaptive networks. These networks allow spontaneous formation and deformation of mobile networks.

      A MANET is an autonomous collection of mobile users that communicate over relatively bandwidth constrained wireless links. Since the nodes are mobile, the network topology may change rapidly and unpredictably over time. The network is decentralized, where all network activity including discovering the topology and delivering messages must be executed by the nodes themselves i.e., routing functionality will be incorporated into mobile nodes.

      The set of applications for MANETs is diverse, ranging from small, static networks that are constrained by power sources, to large-scale, mobile, highly dynamic networks. The design of network protocols for these networks is a complex issue. Regardless of the application, MANETs need efficient distributed algorithms to determine network organization, link scheduling, and routing.

      These routing protocols can be divided into three categories: Proactive (table-driven), Reactive (on- demand) routing and hybrid routing protocols based on when and how the routes are discovered. In table driven routing protocols consistent and up-to-date routing information to all nodes is maintained at each node whereas in on-demand routing the routes are created only when desired by the source host. Next two sections discuss current table-driven protocols, hybrid protocols as well as on demand routing protocols.

      In Proactive routing protocols each node maintains one or more tables containing routing information to every other node in the network. All nodes update these tables so as to maintain a consistent and up-to-date view of the network. When the network topology changes the nodes propagate update messages throughout the network in order to maintain consistent and up-to-date routing information about the whole network. These routing protocols differ in the method by which the topology change information is distributed across the network and the number of necessary routing-related tables. The following sections discuss some of the existing table-driven ad hoc routing protocols. Examples DSDV, WRP.

      Reactive protocols take a lazy approach to routing. In contrast to table-driven routing protocols all up-to- date routes are not maintained at every node, instead the routes are created as and when required. When a source wants to send to a destination, it invokes the route discovery mechanisms to find the path to the destination. The route remains valid till the destination is reachable or until the route is no longer needed. This

      section discusses a few on-demand routing protocols. Examples AODV, DSR, AOMDV.

3. Working of Reactive Protocols

   This paper focuses on working of reactive protocols mainly AODV and AOMDV using the concepts of genetic algorithm.

   1. Genetic Algorithm

      A genetic algorithmic approach is presented to the SP routing problem. Computer simulations show that the GA based SP algorithm exhibits a much better quality of solution (route optimality) and a much higher rate of convergence than other algorithms. GA belong to the class of evolutionary algorithm (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover.

      A typical geneic algorithm requires: a genetic representation of the solution domain, and a fitness function to evaluate the solution domain.

      The GA operations consist of several key components: genetic representation, population initialization, fitness function, selection scheme, crossover and mutation. It is also called standard GA or SGA.

      • Genetic Representation: A routing path is encoded by a string of positive integers that represent the IDs of nodes through which the path passes.

      • Population Initialization: each chromosome corresponds to a potential solution. The initial population Q is composed of a certain number, denoted as q, of chromosomes. a certain number, denoted as q, of chromosomes.

      • Fitness Function: We should accurately evaluate the quality of a solution, which is determined by the fitness function. In this algorithm, the aim is to find the least cost path between the source and the destination.

        . Selection Scheme: Selection plays an important role in improving the average quality of the population by passing the high quality chromosomes to the next generation. The selection of chromosomes based on the fitness value.

      • Crossover and Mutation: Genetic algorithm relies on two basic genetic operators – crossover and mutation. Crossover processes the current solutions so as to find better ones.

        Mutation helps GA keep away from local optima. Chromosomes are expressed by the path structure, here a single point crossover technique to exchange partial chromosomes (sub-path) at positionally independent crossing sites between two chromosomes

      • Repair function: Both crossover and mutation may produce new chromosomes which are infeasible solutions. Therefore, we check if the paths represented

      by the new chromosomes are acyclic. If not, repair functions will be applied to eliminate the loops. Thus applying all these functions, GA is executed to get chromosome or path having lowest cost.

   2. AODV with Genetic Algorithm

      The Ad hoc On-Demand Distance Vector Routing Protocol enables dynamic, self-starting, multi-hop routing between participating mobile nodes wishing to establish and maintain an ad hoc network. The operation of the protocol has two phases: route discovery and route maintenance. In Ad-hoc routing, when a route is needed to some destination, the protocol starts route discovery. Then the source node sends route request (RREQ) message to its neighbors, if those nodes do not have any information about the destination node, then they send the message to all its neighbors and so on, if any neighbor node has the information about the destination node, the node sends route reply message to the route request message initiator.

      On the basis of this process a path is recorded in the intermediate nodes. This path identifies route and is called the reverse path. Since each node forwards route request message to all of its neighbors, more than one copy of the original route request message arrive at a node. A unique id is assigned, when a route request message is created. When a node receives the RREQ, it checks id and the address of the initiator, if it had already processed that request, it discarded that message. Node that has information about the path to the destination sends route reply message to neighbor from which it has received route request message. The neighbor does the same. Due to the reverse path, it is possible. Then the route reply (RREP) message travels back using reverse path. When a route reply message reaches the initiator the route is ready and the initiator start sending data packets. Without genetic algorithm the results are poor in terms of throughput, packet loss and delay.

      Genetic Algorithm is implemented using AODV. The results show that throughput is almost same to the AOMDV. Packet loss is little more when compared to the results of AOMDV which is given below. Average end to end delay is comparatively more when compared to AOMDV.

      Figure 1. Working of AODV

   3. AOMDV with Genetic Algorithm

      AOMDV on the other hand is a multi-path routing protocol. It is an extension to AODV and also provides two main services i.e. route discovery and maintenance. Unlike AODV, every RREP is being considered by the source node and thus multiple paths discovered in one route discovery. Being the hop-by-hop routing protocol, the intermediate nodes maintain multiple path entries in their respective routing table. As an optimization measure, by default the difference between primary and an alternate path is equal to 1 hop. The route entry table at each node also contains a list of next hop along with the corresponding hop counts. Every node maintains an advertised hop count for the destination. Advertised hop count defined as the Maximum hop count for all the paths. Route advertisements of the destination are sent using this hop count. An alternate path to the destination is accepted by a node if the hop count is less than the advertised hop count for the destination. Without genetic algorithm the results are poor in terms of throughput, packet loss and delay.

      Genetic Algorithm is implemented using AOMDV. The results show that throughput is same when compared to AODV. Packet loss is less when compared

      to AODV. Average end to delay is comparatively less when compared to AODV.

      Figure 2. Working of Genetic Algorithm

   4. Performance Metrics

      • Fitness function: F(Chi) = | f(x) |

      • Selection:

        Selection parameter = total fitness X random number

      • Crossover: bitmask=(allbitsset>>bitno)<<bitno newgene=(firstpathANDbitmask)OR(second pathAND(~bitmask))

      • Mutation:

        Bitno = 32.0 X rand( ) Bitmask = l<<bitno

      • Throughput: Throughput=(recvdSize/(stopTime- startTime))*(8/1000)

      • Packet Delivery Ratio:

        PDR = ( Number of packets received) / ( Number of packets sent)

      • Normalized Routing Overload:

        NRL = routing packets / received packets

      • Routing Overhead:

   RO = No. of routing packets for every data packet received.

4. Result Analysis:

Figure 3. Throughput with GA

Figure 4. Packet Delivery Ratio with GA

Figure 5. Normalized Routing Load with GA

Figure 6. Routing Overhead with GA

1. Conclusion

   This architecture analyses basic routing protocols with implementation of genetic algorithm. The results show that Genetic algorithm works better for reactive protocols. Hence analysis of AODV and AOMDV is done to find the performance of mobile ad hoc networks. Then Genetic algorithm based AOMDV routing protocol is designed and implemented. The outcomes infer that Genetic algorithm based AOMDV routing protocol shows better efficiency in terms of throughput, delay and packet loss. Hence Genetic algorithm based AOMDV routing protocol can be considered as best possible routing protocol for mobile ad-hoc networks.

2. References

1. Charles E. Perkins and Elizabeth M. Royer, Ad hoc on demand distance vector (AODV) routing Internet-Draft), Aug,1998.

2. Arshad, J.; Azad, M.A.; , "Performance Evaluation of Secure on-Demand Routing Protocols for Mobile Ad-hoc Networks," Sensor and Ad Hoc Communications and Networks, SECON '06. 2006 3rd Annual IEEE Communications Society on , vol.3, no., pp.971-975, 28-28 Sept. 2006.

3. Marina K Mahesh and Das Samir R Ad-hoc ondemand multipath distance vector routing Wireless Communications and Mobile Computing p.p 969-988. .2006

4. Perkins CE, Royer EM. Ad hoc on-demand distance vector routing. In Proceedings of IEEEWorkshop on Mobile Computing Systems and Applications (WMCSA), 1999.

5. Perkins CE, Belding-Royer E, Das SR. Ad hoc on- demand distance vector (AODV) routing. http://www.ietf.org/rfc/rfc3561. txt, July 2003. RFC 3561.

6. Wireless Ad-Ho networks by Lu Han, Oct 8, 2009.

7. Multi objectives GA based QOS routing protocol for Mobile Ad-Hoc networks, J Abdullah, International Journal of Grid and Distributed Computing, Vol 3, No. 4, Dec 2010.

8. Dr. Ketan Kotecha, Sonal Popat, Member IEEE, Multiobjective Genetic Algorithm based Adaptive QOS Routing in MANET.

9. C. Siva Ram Murthy and B.S. Manoj, Ad hoc Wireless Networks Architecture and protocols, Prentice Hall, 2004.

10. Tsirigos A, Haas Z. J, Multipath routing in the presence of frequent topological changes, IEEE Communications Magazine, vol. 39(11), pp. 132-138, Nov,2001.

11. C. K. Toh. Ad Hoc Mobile Wireless Networks: Protocols and Systems. Prentice Hall PTR, ISBN: 0130078174, 2002.

About Authors:

Arun Biradar has received B.E, M.Tech. in Computer Science & Engineering and Pursuing Ph.D. in Computer Science & Engineering. His main research interests are Wireless Ad-Hoc Networks and Genetic Algorithms.

Dr. Ravindra C. Thool received his Ph. D. in Electronics and Computer Engineering. He is working as a Professor and Head, Department of Information Technology, Shri Guru Gobind Singhji Institute of Engineering and Technology (SGGSIE&T), Nanded, Maharashtra, India. He is a member of IEEE, ISTE and ASABE (USA). His main research interests are Wireless Ad-Hoc Networks, Computer Networks, Genetic Algorithms and Computer Vision.