Genetic Zone Routing Protocol (GZRP) is a new hybrid multipath routing protocol for MANETs which is an extension of ZRP by using Genetic Algorithm (GA). GZRP uses GA on IERP and BRP parts of ZRP to provide a limited set of alternative routes to the destination in order to load balance the network and robustness during node/link failure during the route discovery process. GZRP is studied for its performance compared to AOMDV, another multipath routing protocol extended from AODV, a source routing protocol. The performance analysis is made using GloMoSim 2.03. The results of the comparison are produced in this paper.
Keywords: MANET, Routing, ZRP, Genetic Algorithm, GZRP, Load Balancing, AOMDV, AODV.
A Mobile Ad hoc NETwork (MANET)  is a connectivity of network formed due to cooperation between the mobile nodes dynamically and instantaneously without depending on any of the fixed infrastructure like base stations. There are many challenges related to MANETs . Some examples of the possible uses of ad hoc networking [3-4] include students using laptop computers to participate in an interactive lecture, business associates sharing information during a meeting, soldiers relaying information for situational awareness on the battlefield, and emergency disaster relief personnel coordinating efforts after a hurricane or earthquake. There are various issues related to ad hoc networks [5-6]. Several protocols have been proposed for routing in such an environment. These protocols can broadly be classified into two types: proactive and reactive routing protocols. Proactive or table-driven protocols try to maintain routes to all the nodes in the network at all times by broadcasting routing updates in the network. Examples are Destination Sequenced Distance Vector (DSDV) , Optimized Link State Routing (OLSR), Wireless Routing Protocol (WRP) and Fishey State Routing (FSR). On the other hand, reactive or on-demand protocols attempt to find a route to the destination, only when the source has a packet to send to the destination. Examples are Dynamic Source Routing (DSR), Adhoc Ondemand Distance Vector (AODV), and Temporally Ordered Routing Algorithm (TORA). In between the above two extremes, there are the hybrid protocols. The Zone Routing Protocol (ZRP)  is a hybrid protocol. ZRP is a routing framework composed of the proactive Intrazone Routing Protocol (IARP), reactive Interzone Routing Protocol (IERP) , and the Bordercast Resolution Protocol (BRP) . There are studies [13-16] related to ZRP which prove that its performance is better compared to either table-driven or on-demand protocols. Authors of this paper have also made a considerable performance study on ZRP whose results are presented in [17-20].
Get your grade
or your money back
using our Essay Writing Service!
Genetic Algorithms  perform much better with uneven conditions because of their population based approach spreading search throughout the possible alternatives. A large amount of work [21-30] has been done on the application of genetic algorithms or evolutionary algorithms to communications networks. Investigators have applied GAs to the shortest path (SP) routing problem [22-23]. C.W. Ahn et al  have proposed a GA approach for SP routing problem. It employs the variable length chromosomes. The crossover operation exchanges partial chromosomes (partial routes) at partially independent crossing sites and the mutation operation maintains the generic diversity of the population. A repair function is used to cure the infeasible solutions due to crossover. The authors of the paper proposed a protocol called Genetic Zone Routing Protocol (GZRP) , which utilizes the new GA suggested in  with little changes and is proved to be fast compared to other GA-based methods. In our approach, the proposed routing protocol maintains a limited number of alternative routes which are frequently used in order to reduce communication overhead and end-to-end delay in routes while having better delivery of packets. We generate alternative routes by GA with genetic operators based on topological information of the network. These alternative routes generated by GA are use for distributing the packets in multiple paths in order to load balance the network and the paths can also be used for fault tolerance.
This paper is organized as follows: Section 2 provides the details and working of the protocol proposed by the authors, called Genetic Zone Routing Protocol (GZRP). Section 3 discusses the brief idea of AOMDV protocol. The experimental procedure including the evaluation methodology and environment used for the simulation are given in Section 4, and in Section 5, we present the results of the experimented simulations. Finally, Section 6 proposes the conclusions.
Always on Time
Marked to Standard
Genetic Zone Routing Protocol (GZRP) is proposed  by the authors of this paper which is a multipath extension of Zone Routing Protocol (ZRP) adopting the concept of Genetic Algorithm (GA). Some of the performance evaluations on GZRP are done in [33-35]. The principle of GZRP is explained hereunder: GZRP makes use of IARP, similar to ZRP, to verify whether intended destination is within the routing zone of the source node. If the route to the destination is available in its routing table, it makes of the same route and forwards the packets to the destination. And, if the route to the destination is not within its reach, it applies route discovery process using its sub-protocols, IERP and BRP. IERP makes use of Route Request (RREQ) and Route Reply (RREP) packets in the route discovery process. The RREQ packets are bordercasted in to the network. In turn, these packets are further bordercasted from the border nodes. Every border node searches for the destination node within its routing table. When a route to the destination is found, the Route Reply (RREP) packets are sent back to the source node. The GZRP makes use of GA at each border node and generates possible alternative paths which may be optimal or sub-optimal. These alternative paths are stored at the border nodes for two basic reasons: (a) they can utilize these routes as the alternative routes in case of the existing route fails or node fails (Fault Tolerance) (b) they can distribute the packets on multiple alternative routes to reduce the congestion and as well to balance the network (load balancing). At each border node, instead of bordercasting the RREQ packets on a primary path alone, they can be bordercasted on many routes. Even though, GA produces many possible alternative paths, we make use of limited number of alternative routes which are either optimal or near optimal. The architecture of the GZRP is shown in Fig.1.
Figure 1. Architecture of Genetic Zone Routing Protocol
While using GA in computing the shortest path or near shortest paths, it includes the process like crossover and mutation to produce the new routes. The main advantage of the GZRP is that it limits the control overhead as it does not rediscover the routes when the route fails. It makes use of readily available routes which are generated using GA.
Routing Table of a Border Nodes
The routing table consists of the entries including destination, route, frequency, and metric. The default metric used throughout the work is hop count. The destination entry indicates the destination node of packets. For each destination, we have a set of alternative routes. A route entry is a list of node IDs along the route. The frequency entry specifies the number of packets sent to the destination by the route.
Robustness: fault tolerance
Fault tolerance is essential in actual routing algorithms. It will take care of route maintenance. The routing algorithms must be robust for packet loss caused by instability of the network such as congestion and node/link failure. The GZRP reduces this problem by providing a set of alternative routes to a border node. The next best available alternative route at the border node is used for forwarding the packets. This gives robustness for the network and also reduces the control overhead that may occur in the network due to rediscovery of the routes.
This frequency field in the routing table will be useful in order to load balance the network. This reduces the load on a single route by distributing the packet delivery through the available alternative routes. The first route to the destination in the list is considered as the default route. In initial state, the routing table is empty. When a packet is generated at a node, a default route is generated by the IARP routing framework and will be inserted in to the routing table. This not only reduces the end-to-end delay but also helps in reducing the overhead. Further, delivery of the packets will be done more efficiently.
The Protocol AOMDV is a multipath extension of existing reactive routing protocol AODV. The working of AOMDV protocol is hereunder. RREQ propagation from the source towards the destination establishes multiple reverse paths both at intermediate nodes as well as the destination. Multiple RREPs traverse these reverse paths back to form multiple forward paths to the destination at the source and intermediate nodes. Note that AOMDV also provides intermediate nodes with alternate paths as they are found to be useful in reducing route discovery frequency. The core of the AOMDV protocol lies in ensuring that multiple paths discovered are loop-free and disjoint, and in efficiently finding such paths using a flood-based route discovery. AOMDV route update rules, applied locally at each node, play a key role in maintaining loop-freedom and disjointness properties. AOMDV relies as much as possible on the routing information already available in the underlying AODV protocol, thereby limiting the overhead incurred in discovering multiple paths. In particular, it does not employ any special control packets. In fact, extra RREPs and RERRs for multipath discovery and maintenance along with a few extra fields in routing control packets (i.e., RREQs, RREPs, and RERRs) constitute the only additional overhead in AOMDV relative to AODV.
This Essay is
a Student's Work
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
A. Evaluation Methodology
The simulator used for evaluation of the protocols is GloMoSim (Global Mobile Information System Simulator) . The aim of this simulation study is to evaluate both the protocols, AOMDV and GZRP, for their performance on the factors like percentage of packet loss, route discovery frequency and the average delay.
B. Parameter used in the Simulation Model
The parameters used for modeling the simulation to evaluate the protocol are summarized in Table I and Table II lists the parameters used for GA. No data was collected for the first 10 seconds to avoid measurements before intra-zone route discovery process stabilized.
In this section, an analysis is made on the achieved results due to the performance evaluation of AOMDV and GZRP with respect to percentage of packet loss, packet delivery frequency and average delay. The zero seconds of pause time imply that nodes are in continuous motion without any pause whereas the 900 seconds of pause time imply that nodes are in stationary as the simulation is run for 900 seconds.
Fig. 2 indicates the results of the simulation made for the influence of mobility on AOMDV and GZRP protocols to check the percentage loss of packets. It is observed that due to the load balancing the network, there much less packet loss in GZRP, in general, and better performed with respect to AOMDV, in particular. The overall improvement of 4% is seen in GZRP compared to AOMDV.
Fig. 3 shows the effect of mobility on the route discovery frequency of both the protocols, AOMDV and GZRP respectively. Due to the readily availability of the routes which are generated by GA module of GZRP, there is much less need for rediscovery of the routes. The results indicate that GZRP shows an improved result of 4% compared to AOMDV in route discovery frequency. This is a considerable improvement over AOMDV.
Finally, Fig.3 represents the variation of average delay over mobility for AOMDV and GZRP protocols. There is an improvement of nearly 6% of GZRP over AOMDV protocol. It can be inferred that GZRP is delivering the packets using multiple alternative routes because of which there is a much less average delay of GZRP compared to AOMDV.
In this paper, we have presented the performance evaluation of Genetic Zone Routing Protocol (GZRP) and Adhoc Ondemand Multipath Distance Vector (AOMDV) Routing Protocols. GZRP is an extension to the Zone Routing Protocol (ZRP) with the use of genetic algorithm (GA). GZRP shows slight improvement of around 5% over AOMDV on the average. The studies are made on various factors like percentage of packet loss, packet delivery frequency and average delay. The results indicate that GZRP is well balanced protocol compared to AOMDV. Its load balancing nature and fault tolerance nature provided a set of alternative routes without requiring for more route discoveries.