, where is the
number of hops to the perimeter of the zone.
This document describes and analyzes the Zone Routing Protocol or ZRP for Mobile Ad-Hoc Networks (MANETs). The basics of MANET and the implications on routing in particular are briefly covered in Section 2 to provide an introduction to the problems resulting from a rapidly changing topology without a fixed router.
As we will see in Section 3, ZRP, in contrast to other MANET routing protocols, utilizes a hybrid pro-active/re-active approach to maintain valid routing tables without too much overhead. Furthermore, ZRP does not provide a single protocol, but rather outlines a routing framework suitable for inclusion and extension of other existing protocols.
In describing the protocol, we will consider some specific examples in order to visualize how ZRP's characteristics influence it's performance (Section 4).
Section 5 analyzes the performance of the ZRP as well as discusses various scenarios, and in Section 6 the information provided in this document is briefly summarized.
A Mobile Ad-Hoc Network (MANET) is a decentralized network of autonomous mobile nodes able to communicate with each other over wireless links. Due to the mobility of the nodes, the topology of the network may rapidly be changing, making it impossible to use conventional routing tables maintained at fixed points (routers). Instead, each node is required to determine the best route to a given destination node by itself.
Given their dynamic nature, route discovery in a MANET differs significantly from the more or less static routes in wired networks: Not all nodes in a MANET necessarily have the same capabilities. Two nodes, even if they are direct neighbors, may differ with respect to signal strength, available power, reliability etc.
These differences require much more complicated and particularly more active distributed algorithms in order to maintain an accurate picture of the networks topology, while at the same time providing scalability for potentially large (and ever-growing) networks. At the same time, route discovery must not use up the majority of the often limited bandwidth available to todays mobile devices.
Furthermore, it is important to point out an important difference to conventional routing approaches: In wired networks, each link is bi-directional. If a node A can send packets to a node B, we know that node B can send packets back to node A, and a reverse path can be entered. This is not necessarily the case in a wireless network, where the physical location and the individual power resources have great influence upon a nodes transmission capacity and signal strength.
MANET routing protocols are IP based and may use unicast, multicast or hybrid approaches and should allow for interaction with standard wired IP services rather than being regarded as a completely separate entity.
A detailed yet not overly complex overview of the various aspects of Mobile Ad-Hoc Networking is given in [7].
The IETF MANET Working Group has researched and developed a number of protocols for mobile ad-hoc networks, which have been described in [8], [9], [10], [11] and [12]. These protocols can generally be categorized into two groups: pro-active and re-active protocols.
Pro-active protocols follow an approach similar to the one used in wired routing protocols. By continuously evaluating the known and attempting to discover new routes, they try to maintain the most up-to-date map of the network. This allows them to efficiently forward packets, as the route is known at the time when the packet arrives at the node.
Pro-active or table-driven protocols, in order to maintain the constantly changing network graph due to new, moving or failing nodes, require continuous updates, which may consume large amounts of bandwidth - clearly a disadvantage in the wireless world, where bandwidth is often sparse. Even worse so, much of the accumulated routing information is never used, since routes may exist only for very limited periods of time.
The family of Distance-Vector protocols, including Destination-Sequenced
Distance-Vector Routing ([13]), fall into the category of pro-active
protocols.
In contrast, reactive protocols determine the proper route only when required, that is, when a packet needs to be forwarded. In this instance, the node floods the network with a route-request and builds the route on demand from the responses it receives. This technique does not require constant broadcasts and discovery, but on the other hand causes delays since the routes are not already available. Additionally, the flooding of the network may lead to additional control traffic, again putting strain on the limited bandwidth.
These reactive (or on-demand) protocols include Dynamic Source Routing (DSR) [9] and Ad-hoc On demand Distance Vector Routing (AODV) [8], as well as the classical flooding algorithms. [1]
As explained above, both a purely pro-active or purely reactive approach to implement a routing protocol for a MANET have their disadvantages. The Zone Routing Protocol, or ZRP, as described in this document combines the advantages of both into a hybrid scheme, taking advantage of pro-active discovery within a node's local neighborhood, and using a reactive protocol for communication between these neighborhoods.
In a MANET, it can safely be assumed that the most communication takes place between nodes close to each other. Changes in the topology are most important in the vicinity of a node - the addition or the removal of a node on the other side of the network has only limited impact on the local neighborhoods.
As mentioned earlier, the ZRP is not so much a distinct protocol as it
provides a framework for other protocols.
The separation of a nodes local neighborhood from the global topology of the
entire network allows for applying different approaches - and thus taking
advantage of each technique's features for a given situation.
These local neighborhoods are called zones (hence the name); each node
may be within multiple overlapping zones, and each zone may be of a different
size.
The ``size'' of a zone is not determined by geographical measurement, as one
might expect, but is given by a radius of length , where is the
number of hops to the perimeter of the zone.
By dividing the network into overlapping, variable-size zones, ZRP avoids a hierarchical map of the network and the overhead involved in maintaining this map. Instead, the network may be regarded as flat, and route optimization is possible if overlapping zones are detected.
While the idea of zones often seems to imply similarities with cellular phone
services, it is important to point out that each node has it's own zone, and
does not rely on fixed nodes (which would be impossible in MANETs).
Figure 1 shows an example routing zone with 
.
Note that in this example node A has multiple routes to node F, including one
that has a hopcount of 
.
Since it also has a route with 
, F still belongs to A's zone.
Node G is out of A's zone,
The nodes on the perimeter of the zone (i.e. with a hopcount 
) are
referred to as peripheral nodes (marked gray), nodes with 
are
interior nodes.
Obviously a node needs to first know about it's neighbors before it can construct a routing zone and determine it's peripheral nodes. In order to learn about it's direct neighbors, a node may use the media access control (MAC) protocols directly. Alternatively, it may require a Neighbor Discovery Protocol (NDP). Again, we see that ZRP, as a framework, does not strictly specify the protocol used but allows for local independent implementations.
Such a Neighbor Discovery Protocol typically relies on the transmission of ``hello'' beacons by each node. If a node receives a response to such a message, it may note that it has a direct point-to-point connection with this neighbor. The NDP is free to select nodes on various criteria, such as signal strength or frequency/delay of beacons etc. Once the local routing information has been collected, the node periodically broadcasts discovery messages in order to keep it's map of neighbors up to date. In doing so, it is assumed that these ``link-layer (neighbor) unicasts are delivered reliably and in-sequence.''[1]
If the MAC layer of the nodes does not allow for such a NDP, the Intrazone Routing Protocol must provide the possibility of direct neighbor discovery. This protocol is responsible for determining the routes to the peripheral nodes and is commonly a pro-active protocol. The Intrazone Routing Protocol, or IARP, is described in more detail in in Section 3.1.
Communication between the different zones is guarded by the Interzone Routing
Protocol, or IERP, and provides routing capabilities among peripheral nodes
only.
That is, if a node encounters a packet with a destination outside it's own
zone - i.e. it does not have a valid route for this packet - it forwards it
to it's peripheral nodes, which maintain routing information for the
neighboring zones, so that they can make a decision of where to forward the
packet to.
Through the use of a bordercast algorithm rather than flooding all peripheral
nodes, these queries become more efficient.
The Interzone Routing Protocol and the Bordercast Resolution Protocol are
presented in Sections 3.2 and 3.3.
As we can see, the Zone Routing Protocol consists of several components, which only together provide the full routing benefit to ZRP. Each component works independently of the other and they may use different technologies in order to maximize efficiency in their particular area. For example, a reactive protocol such as AODV might be used as the IARP, while the IERP is most commonly a pro-active protocol such as OLSR [14].
Figure 2, as adapted from [1], illustrates the
different protocols and their interactions.
Even though the hybrid nature of the ZRP seems to indicate that it is a hierarchical protocol, it is important to point out that the ZRP is in fact a flat protocol. In a hierarchical network architecture, two different protocols are maintained for communication among (a) each individual cluster's nodes and (b) the different clusters. The main difference here is that in the ZRP there is a one-to-one correspondence between nodes and routing zones, causing overlapping zones maintained by each individual nodes (see [1] for details).
Since ZRP assumes that local neighbor discovery is implemented on the
link-layer and is provided by the NDP, the first protocol to be part of ZRP is
the Intrazone Routing Protocol, or IARP.
This protocol is used by a node to communicate with the interior nodes of it's
zone and as such is limited by the zones radius (the number of hops
from the node to it's peripheral nodes).
Since the local neighborhood of a node may rapidly be changing, and since changes in the local topology are likely to have a bigger impact on a nodes routing behavior than a change on the other end of the network, the IARP is a pro-active, table-driven protocol.
The node continuously needs to update the routing information in order to determine the peripheral nodes as well as maintain a map of which nodes can be reached locally. The IARP allows for local route optimization through the removal of redundant routes and the shortening of routes if a route with fewer hops has been detected, as well as bypassing link-failures through multiple (local) hops, thus leveraging global propagation.
As mentioned earlier, it is possible that a node A can broadcast messages to a
node B, but that node B, due to limitations in it's signal-strength (caused by
interference, for example) or low transmission power, can not reach node A.
Therefor, it is important for the IARP to provide support for unidirectional
links among the local nodes.
Due to it's pro-active nature, local route discovery is very efficient and routes to local destinations are immediately available. In order to not overutilize the available bandwidth resources, the IARP - as the name suggests - is restricted to routing within the zone, which is why it is referred to as a ``limited scope pro-active routing protocol''[3].
Global route discovery, communication with nodes in a different zone, is done
by guiding the route queries to the peripheral nodes instead of flooding all
local nodes.
In order to adopt a traditional pro-active link state protocol for use as the
IARP in the ZRP, the scope of the protocol needs to be limited to the size of
the zone .
This may be implemented by adding a Time To Live (TTL) to the route discovery
requests, initialized to 
, and decremented by each node until it
reaches 
(when it is discarded).
In Figure 1, uninterrupted lines indicate the areas where the IARP is used to provide routing between the nodes. The Intrazone Routing Protocol including an example implementation (a Timer Based Link State IARP) is described in more detail in [3].
As the global reactive routing component of the ZRP, the Interzone Routing Protocol, or IERP, takes advantage of the known local topology of a node's zone and, using a reactive approach enables communication with nodes in other zones.
Route queries within the IERP are issued on demand, that is only when a request for a route is made. The delay caused by the route discovery (in contrast to IARP, where the route is immediately available) is minimized through the use of bordercasting, an approach in which the node does not submit the query to all local nodes, but only to it's peripheral nodes. Furthermore, a node does not send a query back to the nodes the request came from, even if they are peripheral nodes (as explained in Section 3.3, Figure 5).
In order to convert an existing reactive routing protocol for use as the IERP
in the ZRP, it is necessary to disable pro-active updates for local routes,
since this functionality is provided by the IARP.
Furthermore, the IERP needs to be able to take advantage of the local routing
information provided by the IARP, as well as change the way route discovery is
handled:
Instead of flooding a route request to all nodes, it should instead use the
Bordercast Resolution Protocol (BRP) to only initiate route requests with
peripheral nodes.
In Figure 1, dotted lines indicate the areas where the IERP is used to provide routing between the zones. The Interzone Routing Protocol including an example implementation (Reactive Source Routing) is described in more detail in [4].
The Bordercast Resolution Protocol, or BRP, is used in the ZRP to direct the route requests initiated by the global reactive IERP to the peripheral nodes, thus removing redundant queries and maximizing efficiency. In doing so, it utilizes the map provided by the local pro-active IARP to construct a bordercast tree. Unlike IARP and IERP, it is not so much a routing protocol, as it is packet delivery service.
The BRP keeps track of which nodes a query has been delivered to, so that it can prune the bordercast tree of nodes that have already received (and relayed) the query. When a node receives a query packet for a node that does not lie within it's local routing zone, it constructs a bordercast tree so that it can forward the packet to it's neighbors. These nodes, upon receiving the packet, reconstruct the bordercast tree so that they can determine whether or not it belongs to the tree of the sending node. If it does not, it continues to process the request and determines if the destination lies within it's routing zone and taking the appropriate action, upon which the nodes within this zone are marked as covered.
In order to detect when a routing zone they belong to has been queried, two levels of Query Detection are provided by BPR. As they relay the queries to the peripheral nodes, the nodes detect the query and notes which zones have been covered. This is referred to as the first level of Query Detection, or QD1.
Secondly, in networks that use a single broadcast channel, a node can determine this information by listening to the traffic broadcast among other nodes. This approach is referred to as QD2. Figure 3 shows node A bordercasting a query to the peripheral nodes D and F. Nodes B and C, as they relay the query, note that node A's zone has been queried (QD1). In single-channel networks, node E can listen to the traffic and come to the same conclusion using QD2.
Simply detecting that a given node has already been covered, however, is not
enough.
The protocol needs to drop packets that would be sent to already covered
nodes.
This is done using Early Termination or ET, which obviously relies on
Query Detection, as well as Loopback Termination or TL (in which routes
that loop back into the querying nodes zone are eliminated, since these nodes
can be reached locally using IARP).
In order to further eliminate unnecessary broadcasting, the BRP may implement
Selective Bordercasting.
In this approach, a node needs to know network topology information for an
extended zone of size 
.
Given this knowledge, a node can further eliminate peripheral nodes from its list of bordercast recipients, if the outer peripheral nodes overlap. Figure 4 shows an example of how node A is able to remove node C from its bordercasting spanning tree, since nodes G and H can be reached through nodes B and D respectively.
In the context of ZRP, the BRP can be seen as the glue which ties together the IARP and the IERP in order to take full advantage of the pro-active and reactive components where they are best used.
The Bordercast Resolution Protocol, including the implementation is described in more detail in [5].
In order to better understand how the different components of the ZRP work together and how routing is done using this approach, we will consider a few examples. Several scenarios are possible, among them stationary nodes in a dense network, mobile nodes moving in different directions with and without stable and/or stationary fixpoints and stationary or moving networks with instable or frequently changing nodes. In these examples, a node is considered stationary, if it does not move relative to the other nodes (even though it may be moving into the same direction). A stable node is one that broadcasts with a constant signal and does not undergo power fluctuations.
In Figure 5, node A needs to send a packet to node H. Since node H is not within it's zone, it constructs a bordercast tree spanning its peripheral nodes C, E and F, and sends the query to its local neighbors B and D. Both B and D note that H is not within their zone they in turn construct a bordercast tree. Note that they only include peripheral nodes of theirs that have not been covered previously.
That is, node B will not include node D, even though it is a peripheral node for B's zone. Similarly, node D's tree will not include node B. Node D then forwards the request to node F, which determines that node H lies within its routing zone, and replies with the correct route.
Let us extend the network from Figure 1 to span a few more nodes. An example situation of such a stationary network, where the number of nodes and their position does not change frequently might be a number of people attending a conference, communicating with each other. This example lends itself to show the basics of ZRP, so we will investigate it in more detail.
Figure 6 shows the network graph; the radius of each
node's zone is still .
Again, as before, the peripheral nodes for node A are marked gray.
In this example, node A has to send a packet to node U.
Node A uses the IARP to determine of node U is within its zone. Since IARP is pro-active, the information that U is in this routing zone is readily available, and node A initiates a route request using IERP. As explained in Section 3.3, IERP now utilizes BRP to bordercast the request: It is not flooded to each of the nodes in A's zone, but only to B, D, E, F, H and J, the peripheral nodes, which in turn search their routing tables for the destination.
Node H does not find U in its routing table and thus bordercasts the request to its peripheral nodes. Figure 7 shows node H's routing zone.
Through the use of BPR, the bordercast tree of node H does not contain nodes F or A: these branches have been pruned, since these nodes have already been covered. Node H broadcasts the route query to nodes M and N. Some of the peripheral nodes of node N's zone are also peripheral nodes of node U's zone - an example of how zones can (and frequently do) overlap. In Figure 8, the peripheral nodes for both node U and node N are shaded.
Now node N bordercasts the query to nodes R and S (nodes M and H are already marked as covered), which in turn reply with the correct route, as they both know U to be within their local zone.
In this example, we will see how ZRP deals with link-failures and link-opti-mization, since moving nodes will constantly have to update their network map, as nodes that used to be within their zone move out of transmission range. For simplicity, let us consider a much smaller initial network. In Figure 9, the arrows indicate the direction in which the nodes are traveling. As we observe node A, we mark its peripheral nodes gray.
As nodes D and B move further away from each other, they lose their connection, just as nodes C and E. However, node E moves closer and is able to establish a point-to-point connection with nodes A and D. Similarly, node F moves closer and is able to establish connections with nodes E and A. These changes are reflected in Figure 10.
In this example, it is interesting to point out that node D remains a peripheral node for A's zone, even though the local route from A to D changes. This change shows the need for a pro-active IERP: the changes in the networks topology like will have taken place within a short period of time. Nodes connected to E only need to add an additional peripheral node (F), as E maintains it's connection to node D. However, were a node connected to E request a route to C, the IERP would need to initiate a new route request, as C no longer is within the querying node's zone and the route needs to go through D.
In order to maximize performance of the ZRP, we need to minimize the amount of control traffic that is sent. Thus, we wish to maintain an overview of the networks topology that is as accurate as possible (at any given time - thus minimizing delays caused by route discovery requests), while at the same time requiring sending as little packages as possible.
Given the hybrid nature of the ZRP, this goal can be reduced to finding the
correct - i.e. optimal - size of the routing zone radius for the
given network - which may vary from case to case, depending on the
circumstances.
For example, in a stationary network as considered in Section
4.2, it would be possible to increase to a larger
number, without too much of a penalty: in this situation, the position or the
number of available nodes changes infrequently, so that, given a larger
routing zone radius, the nodes could take advantage of the comparably static
and immediately available, since pro-actively maintained, routes.
The example in Section 4.3 on the other hand would not benefit
from large zones: the cost of maintaining the ever-changing local routes is
too high, particularly since most of the routes are so short-lived that they
are never used.
Instead, a zone radius of 
would be beneficial, to ensure that
the zones overlap enough to allow for route-re-dundancy.
Note, however, that reducing
effectively turns the ZRP
into a completely reactive protocol, obsoleting the advantages gained from its
hybrid nature: all routing is done on-demand (using IERP), as no node is able
to contact another node using IARP.
The results of [16] showed that the IARP traffic grows with the
number of nodes in a given zone, while increased mobility of a the nodes
increases IERP traffic: as nodes move, the routes between zones break and
need to be ``re-discovered''.
Increasing the number 
of nodes in the global network has only limited
effect on the amount of pro-active traffic, since pro-active IARP updates are
local to a zone.
In general, it can be stated that ``larger zones provide more efficient
queries, which compensates for the IARP maintenance cost''([2]).
A more detailed analysis of ZRPs general performance can be found on [16] and [17].
In this section, we will show how BRP can minimize the number of broadcasts significantly. First let us consider a network as shown in Figure 11.
The first 8 nodes connected to the node in the middle should be seen as that node's peripheral nodes (that is, interior nodes are not shown in this example), the 8 nodes on the outside as the peripheral nodes of the extended zone. As we can see, the total number of queries if no BRP would be used would sum up to be 40!
Now we introduce selective bordercasting. A large number of broadcasts can be avoided, since many of the zones overlap and peripheral nodes connect to the same nodes in the extended zone. As Figure 12 shows, the number has been brought down to 16, a decrease of over 50%!
The tremendous advantage of using Selective Broadcasting in the IERP is visualized in Figure 13, as adopted from [16], [17] and others.
The Zone Routing Protocol (ZRP) provides a hybrid routing framework, in which each node maintains local routes within its zone in a pro-active manner, while interzone communication is performed in a reactive manner. In order to improve performance of the reactive IERP and avoid having to rely on flooding all neighboring nodes, thus risking exhausting the available bandwidth, it makes use of a bordercasting protocol.
It is important to note that all of the components of the ZRP provide the necessary flexibility optimal for nodes in a MANET:
, according
to its signal strength, transmission power, velocity etc.
In contrast to other MANET routing protocols, ZRP, as mentioned above, provides a hybrid approach, a framework of protocols. Thus, it does not directly conflict or compete with any of the protocols described in [8], [9], [10], [11] and [12], but is able to take advantage of each of those protocols strengths, depending on the situation, requirements and implementation.
Also, ZRP is more suitable than other protocols for large networks spanning
diverse mobility patterns by providing the benefits of both reactive and
pro-active routing in a flat network that takes advantage of a
near-hierarchical approach.
The Zone Routing Protocol is formally described by the Mobile Ad-Hoc Networks (MANET) Working Group in an IETF Internet Draft to expire in January 2003 ([1]). Its components IARP, IERP and BRP are described in the IETF Internet Drafts [3], [4] and [5] respectively.
![\includegraphics[width=0.5\textwidth]{simple-example.eps}](img4.png)
![\includegraphics[width=1.0\textwidth]{zrp-arch.eps}](img9.png)
![\includegraphics[width=0.4\textwidth]{query-detection.eps}](img12.png)
![\includegraphics[width=0.5\textwidth]{sbc.eps}](img14.png)
![\includegraphics[width=0.5\textwidth]{brp-example.eps}](img15.png)
![\includegraphics[width=0.5\textwidth]{example-begin.eps}](img16.png)
![\includegraphics[width=0.5\textwidth]{example-periphh.eps}](img17.png)
![\includegraphics[width=0.5\textwidth]{example-overlap.eps}](img18.png)
![\includegraphics[width=0.5\textwidth]{example-small.eps}](img19.png)
![\includegraphics[width=0.5\textwidth]{example-small2.eps}](img20.png)
![\includegraphics[width=0.4\textwidth]{flooding.eps}](img24.png)
![\includegraphics[width=0.4\textwidth]{bordercasting.eps}](img25.png)
![\includegraphics[width=1.0\textwidth]{IERP-traffic.eps}](img26.png)