The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

1. Introduction.

A mobile ad hoc network (MANET) is a collection of wireless mobile nodes that form a
temporary network on the fly that operates without the support of any fixed network
infrastructure. MANETs are created dynamically and they provide special challenges beyond
those in standard data networks [1]. 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. In such networks, each mobile node operates not only as a host but also
as a router and cooperates dynamically to establish routing among them to discover "multi-hop"
paths through the network to any other node.

There are various issues related to ad hoc networks [4]. 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 Routing (DSDV) and Fisheye
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), Ad hoc On demand Distance Vector (AODV), and
Temporarily 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).

Dept. of ISE, EWIT 2010-11 Page 1

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

2. Conventional Routing Protocols.

Several protocols have been proposed for routing in a wireless environment. These
protocols can broadly be classified into two types: Proactive routing protocols 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. 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. Let us see how these protocols function in some detail.

2.1) Proactive Routing Protocol.

Motivation [5] to both improve protocol convergence and reduce traffic has led to the
development of proactive path finding algorithms that combine features of the distance vector
and link state approaches. Each node constructs a minimum spanning tree based on knowledge
of its neighbors’ minimum spanning trees and the link costs to each neighbor.

Realizations of the path finding algorithms, like the wireless routing protocol (WRP), are
able to eliminate the counting-to-infinity problem and reduce the occurrence of temporary loops,
often with less control traffic than traditional distance vector schemes.

The main disadvantage of WRP is in the fact that routing nodes constantly maintain full
routing information in each network node, which was obtained at relatively high cost in wireless
resources. Routing protocols that are based on a source initiated query/reply process have also
been introduced. Such techniques typically rely on the flooding of queries to discover a
destination. In the temporally ordered routing algorithm (TORA), the resulting route replies are
also flooded in a controlled manner to distribute routes in the form of directed acyclic graphs
(DAG’s) rooted at the destination. In contrast, protocols such as dynamic source routing (DSR)
and AODV unicast the route reply back to the querying source along a path specified by a
sequence of node addresses accumulated during the route query phase. In the case of DSR, the
node addresses are accumulated in the query packet and are returned to the source to be used for

Dept. of ISE, EWIT 2010-11 Page 2

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

source routing. AODV, on the other hand, distributes the discovered routes in the form of next
hop information stored at each node in the route.

2.2) Reactive Routing Protocol.

The 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. The on-demand discovery of routes can
result in much less traffic than standard distance vector or link state schemes, especially when
innovative route maintenance schemes are employed. However, the reliance on packet flooding
may still lead to considerable control traffic in the highly versatile wireless network
environment.

There are routing algorithms for ad hoc networks where each node belongs to two
networks, a physical and a virtual network. Routing is based on temporary addresses. A
temporary address is a concatenation of the node’s address on each one of the two networks.
Upon physical migration, a node is required to acquire a new temporary address. In order to
communicate with a node, a query phase is initiated by the source, in which the nodes that
belong to the source’s physical and virtual networks are polled about the address of the
destination.

The virtual network routing is an interesting idea. However, the dynamic assignment of
unique node addresses can be quite challenging in an ad hoc network. In particular, duplicate
addresses may arise, even if the address assignment is centrally controlled within each physical
subnet (i.e., if a physical subnet becomes partitioned). Furthermore, the routing can be far from
optimal, as it is based on hopping within virtual networks, which are determined by the sources
and the destination addresses and not by the nodes’ geographical locations.

Dept. of ISE, EWIT 2010-11 Page 3

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

3. ZRP Overview.

3.1) The ZRP.

The conventional routing protocols have significant disadvantages such as waste of
network capacity since in proactive scheme most of the routing information is never used, and in
reactive schemes a global search is carried out every time a route request is encountered at a
particular node in the network. So what is needed is a protocol that initiates the route
determination procedure on-demand, but at limited search cost. The zone routing protocol (ZRP)
provides efficient and fast discovery of routes by integrating the two radically different classes of
traditional routing protocols.

The ZRP [5] is an example of a hybrid reactive/ proactive routing protocol. On one hand,
it limits the scope of the proactive procedure only to the node’s local neighborhood. The local
routing information is referred to quite often in the operation of the ZRP, minimizing the waste
associated with the purely proactive schemes. On the other hand, the search throughout the
network, although it is global, is performed by efficiently querying selected nodes in the
network, as opposed to querying all the network nodes. The protocol identifies multiple loop-free
routes to the destination, increasing reliability and performance. Routing is flat rather than
hierarchical, reducing organizational overhead, allowing optimal routes to be discovered, and
reducing the threat of network congestion. However, the most appealing feature of the protocol
is that its behavior is adaptive, based on the current configuration of the network and the
behavior of the users.

ZRP is a routing framework composed of the proactive IntrAzone Routing Protocol

(IARP), reactive IntErzone Routing Protocol (IERP) and the Bordercast Resolution Protocol
(BRP). IARP maintains routing information for nodes that are within the routing zone of the
node. Correspondingly, IERP is a family of reactive routing protocols that offer enhanced route
discovery and route maintenance services based on local connectivity monitored by IARP. These
protocols are discussed in some detail in following sections.

Dept. of ISE, EWIT 2010-11 Page 4

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

3.2) The Notion of a Routing Zone and Intrazone Routing.

Each node is defined with a separate routing zone and zones of neighboring nodes
overlap. The routing zone has a radius r, expressed in hops. The nodes of a zone are divided into
Peripheral Nodes and Interior Nodes. An example of a routing zone (for node S) of radius two
hops is shown in Fig. 1 as follows.

K
L

C B

G D S

E A

F
H
I

Figure 1: A routing zone of radius two hops.

(Authors: Pearlman, Marc R, Haas, Zygmunt J. [5] )

For the purpose of illustration, we depict zones as circles around the node in question.
However, the zone is not a description of physical distance, but rather nodal connectivity (hops).

Note that in this example, nodes A–K are within the routing zone of the central node S.
Node L is outside S’s routing zone. Peripheral Nodes are nodes whose minimum distance to the
node in question is exactly equal to the zone radius. The remaining nodes are categorized as
interior nodes. Thus, in Fig. 1, nodes A–F are interior nodes while G–K are peripheral nodes.

Dept. of ISE, EWIT 2010-11 Page 5

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

Because each node maintains its own routing zone, the zones of neighboring nodes can heavily
overlap.
Each node is assumed to maintain routing information only to those nodes that are within
its routing zone. Because the updates are only propagated locally, the amount of update traffic
required to maintain a routing zone does not depend on the total number of network nodes
(which can be quite large). We assume that a node learns its zone through some sort of a
proactive scheme, which we refer to here as the IARP. While the performance of the ZRP
depends on the choice of IARP implementation, the study on the topic suggests that the tradeoffs
are not strongly affected by the particular choice of the proactive scheme used.

3.3) Interzone Routing and the ZRP

For Reconfigurable Wireless Networks’ the coverage of a routing zone is relatively small
compared to the size of the network. Thus, most destinations lie outside of a node’s routing zone,
and the desired routing information cannot be immediately provided by the IARP.

The IERP is responsible for reactively discovering routes to destinations located beyond a
node’s routing zone. The knowledge of the routing zone topology allows a node to efficiently
continue the propagation of a query in the more likely case that destination can be found. This is
achieved by a packet delivery service called Bordercasting. More on this in section 3.4.

The IERP operates as follows: the source node first checks whether the destination is
within its zone. (Note that a node has the information about the identity, distance to, and a route
to all the nodes in its zone.) If so, the path to the destination is known, and no further route
discovery processing is required. If the destination is not within the source’s routing zone, the
source bordercasts a route request to all its peripheral nodes. Now, in turn, all the peripheral
nodes execute the same algorithm: they check whether the destination is within their zone. If so,
a route reply is sent back to the source indicating the route to the destination. If not, the
peripheral node forwards the query to its peripheral nodes.

Dept. of ISE, EWIT 2010-11 Page 6

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

An example of this route discovery procedure is demonstrated in Fig. 2. The source node
S needs to send a packet to the destination D. To find a route within the network, S first checks
whether D is within its routing zone. If so, S knows the route to D. Otherwise S bordercasts a
query to its peripheral nodes that is S sends a query to nodes C, G, and H. Now, in turn, after
verifying that D is not in its routing zone, each one of these nodes forwards the query by
bordercasting the query to its peripheral nodes. In particular, H sends the query to B, which
recognizes D as being in its routing zone and responds to the query, indicating the forwarding
path: S–H–B–D.

C
D
E

B H S

Figure 2: An example of IERP operation

(Authors: Pearlman, Marc R, Haas, Zygmunt J. [5] )

On the downside IERP may result into heavy traffic due to the fact that the zones overlap
heavily. This is called as control traffic problem. A key feature of the routing zone is that a
node’s response to a route query contains information about that node’s entire routing zone. This
depicts that, excess route query traffic is a result of overlapping query threads (i.e., overlapping
queried routing zones). Thus, the design objective of query control mechanisms should be to
reduce the amount of route query traffic by steering threads outward from the source’s routing

Dept. of ISE, EWIT 2010-11 Page 7

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

zone and away from each other. This problem is addressed primarily through appropriate
mechanisms of query detection and query termination.

3.4) Bordercasting Routing Protocol (BRP)

The construction of a routing zone requires a node to first know who its neighbors are. A
neighbor is defined as a node that can communicate directly with the node which is one hop
away. Identification of a node’s neighbors may be provided directly by the Media Access
Control (MAC) protocols. In other cases, neighbor discovery may be implemented through a
MAC-level Neighbor Discovery Protocol (NDP).

The fact that the topology of the local zone of each node is known can be used to reduce
traffic when global route discovery is needed. Instead of broadcasting packets, ZRP uses a
concept called bordercasting. Bordercasting utilizes the topology information provided by IARP
to direct query request to the border of the zone. Bordercasting could be implemented through
network layer unicasting or multicasting of messages to the peripheral nodes which prevents
non-peripheral nodes from accessing the bordercasted messages. In this case, bordercast packet
delivery service is provided by the Bordercast Resolution Protocol (BRP). Route updates are
triggered by NDP, which notifies IARP when the neighbor table is updated. IERP uses the
routing table of IARP to respond to route queries. IERP forwards queries with BRP. BRP uses
the routing table of IARP to guide route queries away from the query source.

Dept. of ISE, EWIT 2010-11 Page 8

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

4. Genetic Zone Routing Protocol.

4.1 Genetic algorithm Approach.

Genetic Algorithms perform much better with rugged landscapes because of their
population based approach spreading “probes” throughout the search space. In the study we
preferred genetic algorithm as the optimization algorithm because of the confidence that it would
work due to its robustness. Note that one of the big advantages of genetic algorithms is the
ability to parallelize them on a large scale by spreading the evaluations across different
machines.

A large amount of work has been done on the application of genetic algorithms or
evolutionary algorithms to communications networks. Investigators have applied GAs to the
shortest path routing problem [6], multicast routing problem [7-9]. A simple genetic algorithm
consists of the following steps:

i. Initial Population: Generate random population of n chromosomes (suitable solutions

for the problem, in this case ‘routes’)
ii. Fitness: Evaluate the fitness f(x) of each chromosome x in the population.
iii. New population: Create a new population by repeating following steps until the new
population is complete.

Dept. of ISE, EWIT 2010-11 Page 9

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

a. Selection: Select two parent chromosomes from a population according to their

fitness (the better fitness, the bigger chance to be selected)
b. Crossover: With a crossover probability cross over the parents to form a new
offspring (children). If no crossover was performed, offspring is an exact copy of
parents.
c. Mutation: With a mutation probability mutate new offspring at each locus
(position in chromosome).
d. Accepting: Place new offspring in a new population.
iv. Replace: Use new generated population for a further run of algorithm.

v. Test: If the end condition is satisfied, stop, and return the best solution in current
population.
vi. Loop: Go to step (ii).

4.2 Application of Genetic Algorithm to ZRP.

Genetic Zone Routing Protocol (GZRP) is an extension of ZRP adopting the concept of
Genetic Algorithm (GA). The idea of using GA leads to finding multiple shortest (near shortest
some times) paths to provide load balancing and tolerance in the networks. Any on-demand
routing protocol uses route discovery and route maintenance procedures for finding the path to
the destination which in turn return a single shortest path to the destination. In any case, if that
route fails and/or congestion occurs and that route leads to the delays or packet losses, then
rediscovery of the new shortest path is required. This causes unnecessary wastage of network
resources and also wastage of time. ZRP is a hybrid protocol which has the hands on routes if the
destination is within the routing zone. However, the actual problem comes when the destination
is outside the zone. In this case, it makes use of route discovery with IERP and BRP. This route
discovery goes with border nodes between the zones.

In this study, GA has been applied at the border nodes in order to find the alternative
routes. Instead of rediscovering the path to the destination every time on failure of the existing
path due to link/node failure and/or congestion occurrence, the border node will apply GA by

Dept. of ISE, EWIT 2010-11 Page 10

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

making use of topological database available with that node to find alternative routes that may be
shortest or near shortest paths.

4.2.1) Routing Table at border node

Table 1 is a routing table generated at border node with BRP. 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, there are 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. This field will be useful in order to load
balance the network. This reduces the load on a single route by equally distributing the
packet delivery through the available alternative routes. The first route to the destination
in the list is considered 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.

Table 1: Routing table at border node with BRP

( Authors: P. Sateesh Kumar, S. Ramachandram [11] )

Destination Route Frequency Metric

7-3-5 7000
5 7-2-6-5 2000 Hop Count
7-3-2-6-5 1000
4-9-8 20000
8 4-5-8 18000 Hop Count
4-5-9-8 12000
... … … …

4.2.2) Encoding Method

The first step in GA is to encode the elements of chromosomes. A chromosome
(routing path) of the GA consists of sequences of positive integers that represent the IDs

Dept. of ISE, EWIT 2010-11 Page 11

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

of nodes through which a route path passes. Each locus of the chromosome represents an
order of a node (indicated by the gene of the locus) in a routing path. The gene (node) of
the first locus is always reserved for the source node. It never needs more than N
number of nodes in a network to form a routing path. Hence, the maximum size of a
chromosome length can be N. A chromosome encodes the problem by listing up node
IDs from its source node to destination node based on topological information (routing
table of IARP part of that node) of the network. An example of chromosome encoding is
given below:

S B1 B2 -------- Bk-1 Bk D

Where,
S is the Source node
D is the Destination node
Bi is the ith Border node in the routing path
k is the route size ( excluding D)

4.2.3) Initial Population.

Population consists of the number of chromosomes. One of the issues in selecting
the initial population of chromosomes is its size. A larger population is quite useful but it
demands excessive costs in terms of both memory and time. The population size is
needed to increase exponentially with the complexity of the problem (i.e. length of the
chromosome) in order to generate good solution. Recent studies have shown, however,
that satisfactory results can be obtained with a much smaller population size. Further, the
literature suggested that random initialization method can be adopted in order to generate
the new population.

4.2.4) Fitness Function.

Dept. of ISE, EWIT 2010-11 Page 12

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

Fitness calculation is most crucial in the GA operation. The fitness function of

GAs is generally the objective function that requires to be optimized. The fitness function
has a higher value when the fitness characteristic of the chromosome is better than others.
The fitness function in the shortest path routing problem is obvious because the shortest
path computation amounts to finding the minimal cost path.

The underlying topology of multi-hop networks can be specified by the directed

graph G=(N,A), where N is a set of nodes (vertices) and A is a set of its links (arcs and
edges). There is a cost Cij associated with each link (i,j). The costs are specified by the
cost matrix C=[Cij], where Cij denotes a cost of transmitting a packet on link (i,j). Source
and destination nodes are denoted by S and D, respectively. Each link has the link
connection indicator denoted by Iij, which plays the role of a chromosome map (masking)
providing information on whether the link from node i to node j is included in a routing
path or not.

It can be defined as follows:

Ii,j = { 1, if the link from node i to node j exists

0, otherwise

The objective function can be formulated as,

D
D
n n Ci,j ∙ Ii,j
∑( ) ∑
i=S
(
i=S k
k
)i ≠i

Subject to the condition that the path between source and destination can have
no loops only when,

{
D D 1, if i=S
∑ ( ) ∑ (nk )
n
k Ii,j
-1 if i=D
i=S ,
i≠i
I
i= Si,j
i ≠i
, = 0, otherwise

Dept. of ISE, EWIT 2010-11 Page 13

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

And,

{
D
≤ 1, if i≠D
∑ ( nk )
i=S ,
i≠i
=Ii,j 0 if i=S

4.2.5) Selection.
The selection (reproduction) operator is intended to improve the average quality
of the population by giving the high-quality chromosomes a better chance to get copied
into the next generation. There are many techniques like roulette wheel selection,
stochastic remainder selection, tournament selection and truncation selection for selecting
the chromosomes for next generation. However, the proposed GA technique employs the
roulette wheel selection which is most widely used. In this technique, two chromosomes
are selected based on the probability. However, the same chromosome should not be
picked twice as a parent.

4.2.6) Crossover.
Crossover examines the current solution in order to find the better ones.
Physically, crossover in the shortest path routing problem plays the role of exchanging
each partial route of two chosen chromosomes in such a manner that the offspring
produced by the crossover represents only one route. This dictates selection of one-point
crossover as a good candidate scheme for the proposed GA. One partial route connects
the source node to an intermediate node and the other partial route connects the
intermediate node to the destination node.

But the mechanism of the crossover is not the same as that of the conventional
one-point crossover. In the proposed scheme, two chromosomes chosen for crossover
should have at least one common gene except for the source and destination nodes, but
there is no requirement that they be located at the same locus. That is, the crossover does
not depend on the position of nodes in routing paths.

Dept. of ISE, EWIT 2010-11 Page 14

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

Before crossover,

S B1 B2 B4 B5 D

S B2 B3 B5 B6 B7 D

After crossover,

S B1 B2 B3 B5 B6 B7 D

S B2 B4 B5 D

It is possible that loops are formed during crossover. A simple counter measure
must be taken in this regard. Repair and penalty functions are the usual counter measures.

4.2.7) Mutation.
The population undergoes mutation by an actual change or flipping of one of the
genes of the candidate chromosomes, thereby keeping away from local optima.
Physically, it generates an alternative partial-route from the mutation node to the
destination node in the proposed GA. A topological information database is utilized for
the purpose. Of course, mutation may induce a subtle bias. However, the bias can be
ignored.

Before mutation,

Mutation node.

S B2 B4 B5 D

After mutation,

S B2 B1 B3 D

Depending on the mutation point, a gene from the chosen chromosome is selected
(node B2). One of the nodes, connected directly to the node at mutation point, is chosen
randomly as the first node of the alternative partial route.

Dept. of ISE, EWIT 2010-11 Page 15

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

4.2.8) Repair Function.

As mentioned earlier, crossover may generate infeasible chromosomes that violate
the constraints of generating loops in the routing paths. It must be noted that none of the
chromosomes of the initial population or after the mutation is infeasible because when
once a node is chosen, it is excluded from the candidate nodes forming the rest of the
path.

5. Experimental procedure.

5.1 Evaluation Methodology.

The simulator used for evaluation of the protocols is GloMoSim (Global Mobile
Information System Simulator) [10]. Our aim of simulation study is to investigate the impact of
node mobility on the performance of both the protocols, ZRP and GZRP. The metrics used for
evaluation are (i) Packet Delivery Ratio (PDR), (ii) Total Overhead (iii) Average end-to-end
Delay. Packet delivery ratio is important as it describes the loss rate that will be seen by the
transport protocols, which in turn affects the maximum throughput that the network can support.
This metric characterizes both the completeness and correctness of the routing protocol. Control
Overhead is an important metric for measuring scalability of a protocol, the degree to which it
will function in congested or low-bandwidth environments, and its efficiency in terms of
consuming node battery power. Average end-to-end delay is important as it describes quality of
link establishment and the ability of forwarding of the packets to the intended nodes.

The parameters used in the simulation model are summarized in following tables. Table-
2 summarizes the parameters used for GA and Table-3 summarizes the parameters used for
modeling the simulation to evaluate the protocol. No data was collected for the first 10 seconds
to avoid measurements before intrazone route discovery process stabilized. The network
interface is modeled after IEEE 802.11 product.

Dept. of ISE, EWIT 2010-11 Page 16

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

Table 3: Parameters of simulation.

Parameter Value [11] )
( Authors: P. Sateesh Kumar, S. Ramachandram
Simulation time 900 Sec.
Number of experimented
Tabletrials 5
2: Parameters used for GA
( Authors: P. Sateesh Kumar, S. Ramachandram
2 [11] )
Network coverage area 1500 X 300 m
Number of nodes 50
Routing zone radius 2
Model: Random Way Point Pause Time:
0s, 100s, . . . . .900s.
Mobility model Minimum Speed: 1 m/s.
Maximum Speed: 20 m/s.
Parameter Value
Crossover Rate Node
60% Placement: Random.
Crossover Point Source:
RandomlyCBRselected 2 point crossover.
Mutation Rate 0.5 %
Number of sources: 10
Traffic
Mutation Point Chromosome size / 2
Rate: 1 packet/sec.
Population Size 2 times the number of nodes.
Selection Technique Packet size:
Roulette 512method
wheel bytes.
MACSize of alternative routes in 802.11
3
the routing table
Bandwidth 2 Mbps.
Transmission range 200 m.

5.2 Results Analysis.

This section provides the comparative study of both ZRP and GZRP for different
evaluation strategies like PDR, Total Overhead and Average end-to-end delay at different
mobility conditions of the nodes.

Dept. of ISE, EWIT 2010-11 Page 17

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

As shown in Figure 3, the change in PDR for GZRP is almost similar to ZRP for different
mobility conditions. Still, there is an improvement nearly 5% in all the mobility conditions. This
improvement is seen due to availability of alternative routes even in the link/node failures.

The effect of average end-to-end delay on the mobility of the nodes is shown in Figure 4.
The results show that delay factor is very much reduced as the pause time is less (high mobility).
At a very high mobility condition, GZRP gives almost 20% to 30% better results compared to
ZRP. The reason behind the results may be due to reduction is congestion due to load balancing
of the network. This is a good improvement. But, as the mobility of the nodes comes to a stable
condition, both the protocols behave like the same. The delay incurred was almost same. This
may be due to less or no usage of the alternative routes in the lower mobility conditions.

The Figure 5 shows the effect of control overhead on the mobility of the nodes. There is
an improvement in the reduction of control overhead in the network due to GZRP as high as 35%
and as low as 15%. This is a very good result compared to ZRP. GZRP has utilized the
advantage of availability of alternative routes. This reduced the control overhead due to
rediscovery of the new routes whenever there is a need. Even at the high mobility conditions, the
results are proved to be good and there is a considerable reduction in control overhead of around
35%. At lower mobility conditions or when the nodes are not moving, there is improvement of
15% of reduction in control overhead.

Dept. of ISE, EWIT 2010-11 Page 18

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

Figure 3: Packet Delivery Ratio for ZRP and GZRP

( Authors: P. Sateesh Kumar S. Ramachandram [11] )

Figure 4:End-to-End Delay for ZRP and GZRP

( Authors: P. Sateesh Kumar S. Ramachandram [11] )

Dept. of ISE, EWIT 2010-11 Page 19

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

Figure 5:Control Overhead for ZRP and GZRP

( Authors: P. Sateesh Kumar S. Ramachandram [11] )

6. Conclusion.

In this paper, we have proposed an extension to the Zone Routing Protocol with the use
of genetic algorithm. We have called this new routing protocol as Genetic Routing Protocol
(GZRP). GZRP is more efficient compared to ZRP as it reduces considerably the average end-to-
end delay and control overhead. The results show that there is a reduction at the maximum in
delay by 30% and in control overhead by 35%. The results are proved to be interesting. This
protoco1 uses Genetic Algorithmic approach to find a limited set of alternative routes in order to
load balance the network. These alternative routes are more efficiently used by GZRP to work in
congestion situations and also at the node/link failure times.

Dept. of ISE, EWIT 2010-11 Page 20

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

7. References.

[1] R. Ramanathan and J. Redi, "A brief overview of ad hoc networks: challenges and
directions", IEEE Communications Magazine, 40(2): 20 - 2,2002
[2] Schiller, J H; Mobile Communications, Pearson Education, India, 2001
[3] Willium Stalings; Wireless communications and Networks. Prentice Hall, New Jersey,
2000
[4] Elizabeth, Royer, Chai-Keong, roh: "A Review of Current Routing Protocols for Ad hoc
Mobile Wireless Networks", IEEE Personal Communications, April 1999.
[5] Pearlman, Marc R, Hass, Zygmunt J; "Determining the Optimal Configuration for the
Zone Routing Protocol", IEEE Journal on Selected Areas in Communications, Vol 17,
No.8, August 1999
[6] M. Munemoto, Y. Takai, and Y. Sato, “ A migration scheme for the genetic adaptive
routing algorithm”, in Proc. IEEE Int. Conf. Systems, Man, and Cybernetics, 1998,
pp2774-2779.
[7] J. Inagaki, M. Haseyama, and H. Kitajima, “A genetic algorithm for determining multiple
routes and its applications”, in Proc. IEEE Int. Symp. Circuits and Systems, 1999, pp.
137-140.
[8] Y. Leung, G. Li, and Z.B. Xu, “A genetic algorithm for the multiple destination routing
problems”, IEEE Trans. [Link]., vol. 2, pp. 150-161, Nov. 1998.
[9] Z. Xiawei, C. Changjia, and Z. Gang, “A genetic algorithm for multicasting routing
problem”, Proc. Int. Conf. Communication Technology (WCC-ICCT 2000), 2000, pp.
1248-1253.
[10] GloMoSim: "Global Mobile Information Systems Simulation Library" available at
[Link]

Dept. of ISE, EWIT 2010-11 Page 21

The Performance Evaluation of Genetic Zone Routing Protocol for MANETs

[11] P. Sateesh Kumar, S Ramchandram, “The Performance Evaluation of Genetic Zone

Routing Protocol for MANETs”, Journal of Theoretical and Applied Information
Technology, 2005-2008.

Dept. of ISE, EWIT 2010-11 Page 22