<<

. 55
( 87 .)



>>

to inform it of the break.
Other characteristics that distinguish DSR from other reactive routing protocols in-
clude the fact that DSR™s route cache entries need not have lifetimes. Once a route is
placed in the route cache, it can remain there until it breaks. However, timeouts, capacity
limits, and cache-replacement policies have been shown to improve DSR™s performance


RREP:S,A,E,G ,D
RREQ:S,A RREQ:S,A,E E
E RREP:S,A,E,G ,D
A
A G
G RREP:S,A,E,G ,D
RREQ:S
RREQ:S,A,E,G RREP:S,A,E,G
S
S
D
D
B
B
RREQ:S RREP:S,B,H,D
H
H RREP:S,B,H,D
RREQ:S,B,H
RREQ:S,B RREP:S,B,H,D

(a) RREQ Broadcast (b) RREP Propagation

Figure 10.3. DSR route discovery.
285
10.4 GEOGRAPHICAL APPROACHES


[20]. Additionally, DSR nodes have the option of promiscuous listening, whereby nodes
can receive and process data and control packets that are not addressed, at the MAC layer,
to themselves. Through promiscuous listening, nodes can utilize the source routes carried
in both DSR control messages and data packets to gratuitously learn routing information
for other network destinations. Finally, to reduce the overhead of carrying source routes in
data packets, DSR also allows flow state to be established in intermediate nodes. This
flow state effectively allows hop-by-hop forwarding with the same source-based route
control as provided by the source route [21].
For a detailed study of the performance of AODV and DSR, as well as an explanation
of how the protocol differences result in performance differentials, the reader is referred
to [16].


10.4 GEOGRAPHICAL APPROACHES

Geographical approaches build on the proactive or reactive techniques previously de-
scribed and in addition incorporate geographical information to aid in routing [3, 25, 33,
58, 59]. This geographical information can be in the form of actual geographic coordi-
nates [as obtained through the global positioning system (GPS)], or can be obtained
through reference points on some fixed coordinate system. The use of geolocation infor-
mation can prevent network-wide searches for destinations, as either control packets or
data packets can be sent in the general direction of the destination if the recent geographi-
cal coordinates for that destination are known. This reduces the control overhead generat-
ed in the network; however, all nodes must have continual access to their geographical
coordinates for these approaches to be useful. The following describes one such geo-
graphical routing approach.

10.4.1 Location-Aided Routing
The Location-Aided Routing (LAR) protocol [25] is a reactive routing protocol that uti-
lizes geographical coordinates to direct route request messages to the previously known
location of the destination. The protocol defines two areas: the expected zone and the re-
quest zone. The expected zone is the area in which the destination is most likely to be dis-
covered. To calculate this area, the source must know a previous location of the destina-
tion at time t0, as well as an estimate of the velocity, v, at which the destination was
traveling at t0. If the current time is t1, the expected zone can be calculated as a circle of
radius v(t1 “ t0) centered at D. The request zone is the area in which the route request for
the destination should propagate. In order to have the greatest probability of finding the
destination, the request zone is defined to be the smallest rectangle that contains both the
expected zone and the source node. Figure 10.4 illustrates an example expected and re-
quest zone.
The basic route discovery procedure of LAR is similar to that of other reactive routing
protocols. When a source needs a route to a destination, it creates a route request (RREQ)
message for that destination. If the source recently had a route to the destination, then the
source calculates the expected zone and the request zone, and places the coordinates of
the request zone boundary into the RREQ message. If the source does not have any previ-
ous information about the destination, then it is unable to calculate the expected and re-
quest zones. In this case, the algorithm defaults to basic flooding.
286 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS


(X D + r, Y D + r)
(X S , Y D + r)



r
D
Expected Zone
D'


RequestZone
S
(X D + r, Y S )
(X S , Y S )

Figure 10.4. LAR expected and request zone.


When a node receives the RREQ, it processes it as described in the previous sections
with the following exception. The node first determines whether it lies in the request zone
defined in the RREQ. Because every node knows its current geographical coordinates, it
can easily make this determination. If the node does not lie within the request zone, then it
does not process the packet. Otherwise, if it does lie within the request zone, it processes
the packet and either rebroadcasts it or sends a reply, depending on whether it has a cur-
rent route to the destination.
The size of the request zone is a trade-off between control overhead and probability of
finding the destination. A small request zone runs the risk of not including the area in
which the destination is currently located. It is also possible that, although the destination
may lie within the request zone, the path between the source and the destination may not
be completely contained within this zone. In this case, a route to the destination will not
be discovered. On the other hand, if the request zone is too large, the control overhead sav-
ings will be minimal.
In addition to the previously described approach, LAR also defines a second method
for determining the request zone. Instead of calculating a rectangular area, the source
places its distance from the previous location of the destination, along with the coordi-
nates of the destination™s previous location, in the RREQ. When neighboring nodes re-
ceive the RREQ, they calculate their distance from the destination (DISTi) and then com-
pare that value with the source™s distance as reported in the RREQ (DISTS). For some
parameter , if DISTS + DISTi, then the node i processes the request. When it for-
wards the request, the node replaces DISTS in the RREQ with its distance DISTi. On the
other hand, if DISTS + < DISTi, the node discards the RREQ. In practical implementa-
tions, typically equals 0. By using this approach, the nodes are forcing the RREQ to
make forward progress to the estimate of the destination™s location.
In both approaches, the RREQ is prevented from flooding the entire network because it
is restricted to areas that are likely to be en route to the destination. This results in a re-
duction in both bandwidth and processing overhead.


10.5 HYBRID APPROACHES

The characteristics of proactive and reactive routing protocols can be integrated in various
ways to form hybrid networking protocols. Hybrid networking protocols may exhibit
287
10.5 HYBRID APPROACHES


proactive behavior given a certain set of circumstances, while exhibiting reactive behavior
given a different set of circumstances. These protocols allow for flexibility based on the
characteristics of the network. Hybrid approaches include the Zone Routing Protocol [41]
and the Distance Routing Effect Algorithm for Mobility [3].

10.5.1 Zone Routing Protocol
The Zone Routing Protocol (ZRP) [41] integrates both proactive and reactive routing
components into a single protocol. Around each node, ZRP defines a zone whose radius is
measured in terms of hops. Each node utilizes proactive routing within its zone and reac-
tive routing outside of its zone. Hence, a given node knows the identity of and a route to
all nodes within its zone. When the node has data packets for a particular destination, it
checks its routing table for a route. If the destination lies within the zone, a route will ex-
ist in the route table. Otherwise, if the destination is not within the zone, a search to find a
route to that destination is needed. Figure 10.5 illustrates the zone concept. In this figure,
the zone radius is two hops.
For intrazone routing, ZRP defines the Intrazone Routing Protocol (IARP). IARP is a
link-state protocol that maintains up-to-date information about all nodes within the zone.
For any given node X, X™s peripheral nodes are defined to be those nodes whose minimum
distance to X is the zone radius. In Figure 10.5, S™s peripheral nodes are nodes A, B, C, and
D. These peripheral nodes are important for reactive route discovery. ZRP utilizes the In-
terzone Routing Protocol (IERP) for discovering routes to destinations outside of the
zone. For route discovery, the notion of bordercasting is introduced. Once a source node
determines the destination is not within its zone, the source bordercasts a query message
to its peripheral nodes. During the bordercast, the query message is relayed toward these
peripheral nodes using trees constructed within the intrazone topology. After receiving the
message, the peripheral nodes, in turn, check whether the destination lies within their
zone. If the destination is not located, the peripheral nodes in turn bordercast the query
message to their peripheral nodes. This process continues until either the destination is lo-
cated, or until the entire network is searched. Once a node discovers the destination, it uni-
casts a reply message to the source node.
Figure 10.6 illustrates an example of the bordercast discovery procedure. In the figure,
node S performs a query for the destination X. By using the IARP, it learns that X is not
within its zone. It bordercasts the query message to its peripheral nodes. In the figure, the


Periphery
Nodes

D S's zone radius
B
S A
C

Figure 10.5. ZRP zone radius.
288 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS




D
E B
G X
F S A
C F

Figure 10.6. Example ZRP route discovery.



dotted circle represents the radius of S™s zone. The peripheral nodes, in turn, check their
zone, and after not finding the destination, bordercast the query message to their peripher-
al nodes. The solid circles in the figure represent the forward propagation of the query
messages to each node™s peripheral nodes (i.e., the circles do not enclose nodes that have
already received the query). Hence, only the portion of each node™s zone that have not
been previously traversed by the query message is shown. Eventually, node G discovers X
within its zone, and then unicasts a reply back to node S.
To improve query efficiency, a random query processing delay can be used as an effec-
tive query control mechanism. By waiting a random interval between query reception and
query forwarding, the chance of collisions during forwarding is reduced and, therefore,
the effectiveness of the protocol is improved. In addition, ZRP defines other optimizations
to reduce the messaging and processing overhead [19]. In particular, these include early
termination of queries by preventing a query from propagating into a zone that has al-
ready been searched for a destination.
Recently, a new version of ZRP, ZRPv2, has been introduced [54]. ZRPv2 differs from
the original ZRP in the manner in which bordercasting is performed. In both versions, route
discovery is initiated with the query source node constructing a bordercast tree to its un-
covered peripheral nodes. An uncovered node is one that does not belong to the routing zone
of a node that already has received the query. The node then forwards the query message to
its bordercast tree neighbors. When these neighbors receive the query message, rather than
forwarding the message to the query source™s downstream peripheral nodes (as in the orig-
inal ZRP), they each construct bordercast trees to their own uncovered peripheral nodes,
and forward the route query to their bordercast tree neighbors. Each node that receives a
route query follows the above procedure until the destination, or a node possessing a fresh
route to the destination, is reached. At that point a route reply is unicast back to the source.
Performing bordercasting on a hop-by-hop basis yields a uniform and, thus, simpler,
protocol implementation. Also, the need for maintaining an extended routing zone is elim-
inated.


10.6 CLUSTERING AND HIERARCHICAL ROUTING

IP addresses are hierarchical in that they identify the location of the end device within the
global Internet. Routing protocols in the Internet take advantage of this hierarchy when
determining routes between networks. Ad hoc networks, on the other hand, are not neces-
sarily able to take advantage of a hierarchy based on IP addresses. Nodes joining an ad
289
10.6 CLUSTERING AND HIERARCHICAL ROUTING


hoc network are likely to have pre-assigned IP addresses from other networks. Hence, the
nodes form a hodgepodge of addresses, and hierarchical routing based on addresses is not
necessarily possible.
However, flat routing, as performed by the previously discussed protocols, has a num-
ber of disadvantages. The primary disadvantage is that it is not scalable. In the worst case,
a node must maintain a routing table entry for every other node in the network, and the
amount of information exchanged to create these routing table entries is O(n2), where n is
the number of nodes in the network.
To increase the scalability of the ad hoc network, hierarchical, or clustering, protocols
can be utilized. Hierarchical protocols place nodes into groups, often called clusters.
These groupings may be based on a number of criteria, but most commonly they are based
on either location [1, 2, 4, 5] or functionality [43, 60].
There have been numerous hierarchical routing protocols developed that take a variety
of approaches toward clustering. In this section, a survey of the characteristics and algo-
rithms for clustering is given; individual protocols are not examined.
The physical properties of the clusters vary between clustering protocols. As shown in
Figure 10.7, clusters can be either overlapping or completely disjoint. Further, a one-level
hierarchy can be created, or recursive multilevel hierarchies are also possible. Finally, con-
trol within a cluster can be held by a cluster leader, or the cluster can be completely dis-
tributed with no cluster leader. In networks in which cluster leaders exist, these leaders
typically process control packets on behalf of their member nodes. It is also possible for
cluster leaders to form a routing backbone within the network [4, 12]. This can be a desir-
able property if the cluster leaders are preselected as nodes with greater resources than
nonleader nodes.
Figure 10.7 illustrates an example cluster topology with cluster leaders. The cluster
boundaries are based on the transmission range of the cluster leaders. All nodes within a
cluster must be within direct transmission range of the cluster leader. In this example,
cluster boundaries are allowed to overlap. Nodes that are located within the boundaries of
multiple clusters are called gateways. These nodes serve as routers between the two clus-
ters. With many clustering protocols, it is also possible for pairs of nodes to serve as dis-

<<

. 55
( 87 .)



>>