. 56
( 87 .)


tributed or joint gateways. Distributed gateways are a pair of nodes that are within direct
transmission range of each other, where each node lies in a different cluster. Together, the
two nodes can be used to route between clusters.
Cluster leaders are typically initialized through some distibuted algorithm. For in-
stance, there can be a leader election algorithm, in which the node with the highest ID

Cluster Leaders Disjoint Clusters

Clusters Gateway

Figure 10.7. Example cluster configuration.

within some area becomes the leader for that area [12]. Alternatively, weights, such as
number of neighbors, transmission range, and so on, can be used instead of the ID of the
node [2, 7]. Other algorithms take a more “first come, first elected” approach [4]. In this
method, when a node joins a network, it queries its one-hop neighbors to determine
whether it is within range of an existing cluster leader. If so, the node may choose to join
the already existing cluster. Otherwise, if there is not a nearby cluster leader, the node be-
comes a leader itself. Using this approach, during the initialization of a network, the first
node to join the network would become a cluster leader.
Once the network has been initialized and cluster leaders have been established, there
must be leader selection and revocation algorithms in place. The leader selection algo-
rithm specifies under what conditions a node should become a cluster leader. For instance,
if a node wanders to the periphery of the network, it may lose contact with all current
cluster leaders. In this case, it may become a cluster leader itself. Similarly, the network
must also have in place a cluster revocation algorithm. Without such an algorithm, there
will be a slow, continual growth in the number of leaders as more nodes wander to the net-
work perimeter and become leaders. In the worst case, without a revocation algorithm, it
would be possible for each network node to eventually become a leader. If all nodes be-
came leaders, the hierarchy would become ineffective.
There are a number of leader revocation algorithms. Most commonly, when two lead-
ers come within direct transmission range of each other, one of the leaders must give up
its leader status. The leader to give up its status may be the leader with the lowest ID [12],
or a weight-based approach may be used [2, 7]. An alternate method has been proposed in
[4], where, instead of requiring one node to become a nonleader whenever two leaders
come within transmission range, a leader gives up its leader status only when its cluster
becomes a subset of the other cluster. This approach has some beneficial properties such
as preventing a rippling effect, where one leadership change results in further network
leadership changes. Because leadership changes are expensive in terms of control over-
head and routing changes, they should be minimized overall.
There are two key benefits of utilizing clustering protocols in an ad hoc network. The
first of these is that they enable hierarchical routing. Consider the network in Figure 10.8.
Suppose a source node S wants to send packets to the destination D. The path it might dis-
cover with one of the previously discussed flat routing protocols is

S C1 G1 C2 D

Using a flat routing scheme, whenever any link along this path breaks, the route must be
repaired with a route maintenance procedure (i.e., sending a route error to the source, lo-
cal repair, route salvaging, etc.). However, with a hierarchical routing scheme, the path is
instead recorded as

S G2
C1 C2

Figure 10.8. Cluster routing example.

S C1 C2 D

The difference is that, with the hierarchical route, the path is recorded at the cluster level.
Hence, the route is recorded from cluster leader C1 to C2, and the intermediate node is not
specified. To get from C1 to C2, any gateway node connecting the two clusters can be uti-
lized. For instance, gateway G1 may be selected to route between the clusters. In the event
that G1 wanders out of transmission range of one of the clusters and can no longer serve
as a gateway, one of the other gateways (i.e., G2) can be used instead. Because of this in-
creased routing flexibility, link breaks do not necessarily result in route repairs if another
gateway node is available. Decreasing the number of route repairs decreases the amount
of control overhead generated in the network, and, consequently, increases the number of
data packets that can be delivered to the destination.
The second benefit of hierarchical protocols is that the hierarchy can be used to imple-
ment hierarchical addressing schemes. Addresses can be assigned to nodes based on their
cluster membership. For instance, in the network shown in Figure 10.9, a node z is a mem-
ber of a cluster y. In that case, its address may be y.z. If the hierarchy consisted of multiple
levels, then cluster y might in turn be within a larger cluster x. In this case, the node™s ad-
dress would be x.y.z. If the node were a member of multiple clusters, the node could have
multiple, concurrent addresses. In mobile networks, multiple addresses would be benefi-
cial because at any given time, at least one of the addresses is likely to still be valid.
As was seen in the previous example, multilevel hierarchies can be created. Multilevel
hierarchies that dynamically adjust their depth based on the network topology can further
increase the scalability of the network. In multilevel hierarchies, each cluster becomes a
node at the next-highest cluster level. Routes can be recorded up and down the hierarhical
routing tree. A route ascends the hierarchical tree only as high as needed to reach the
branch containing the destination. Multilevel hierarchical routing protocols include those
in [5, 28, 44, 52, 56].
Hierarchical routing protocols have many clear advantages. They improve route robust-
ness by increasing routing flexibility; routes that are recorded between clusters, as op-
posed to between nodes, have more routing options, and, hence, can be repaired more eas-
ily. Increasing route robustness leads to an increase in route lifetimes, thereby resulting in
fewer route reconstructions, less control traffic from route repairs, and increased data de-
livery. However, there are also disadvantages that many hierarchical routing protocols suf-
fer from. To create and maintain the clusters, many clustering protocols require periodic
overhead [1, 4, 64]. Such overhead is needed to maintain current information about clus-
ter memberships and gateway availability. To overcome this drawback, some clustering

cluster y
cluster x

Figure 10.9. Hierarchical addressing.

approaches have opted for a more on-demand approach, such that clusters are only creat-
ed when needed [18]. This can eliminate a significant fraction of the overhead in networks
with low traffic demands. Other disadvantages include the centralization of routes
through cluster leaders. If the cluster leaders can be selected solely from nodes with
greater resources, than this centralization is likely to be beneficial. However, in networks
without specialized, high-power nodes, centralizing routes unfairly taxes leader nodes,
and is likely to result in premature depletion of their batteries. Protocols that utilize cluster
leaders for the establishment of routes but that do not actually require cluster leaders to
participate on the routes can eliminate this unfair burden. Finally, the cluster leader“gate-
way“cluster leader routing requirement can result in the use of nonshortest paths.


10.7.1 Multipath Routing
The majority of routing protocols previously described utilize route tables for storing
routing information. In such tables, there is one next-hop entry for each destination. Al-
though in the IP route table it is only possible to store one route entry for each destination,
it is possible in the routing protocol to create a route cache, in which multiple routing en-
tries per destination can be maintained. In the event that the path in use to some destina-
tion breaks or becomes otherwise unusable, an alternate route in the route cache can be
utilized instead. When alternate routes are available, route discoveries can be saved, and
control overhead can be reduced.
There are numerous proposals for multipath routing. The vast majority of these study
multipath routing with on-demand routing approaches. The DSR protocol utilizes route
caches for maintaining multiple paths to each destination. In [20], various caching strate-
gies and cache configurations are analyzed.
Other proposals investigate modifications to existing protocols to add multipath
routing capability. For instance, the Ad Hoc On-Demand Multipath Distance Vector
(AOMDV) routing protocol is described in [36]. In AOMDV multiple routing entries are
stored per destination, and there is one lifetime value associated with all the routing en-
tries for a destination. Hence, all the routing possibilities are refreshed or expire at the
same time. Also, the emphasis in AOMDV is on finding multiple routes that are link dis-
joint, implying that the routes do not share any common links.
Another approach is taken in AODV-BR [29], which proposes back-up paths for rout-
ing around link breaks in active routes. When a link break in an active route occurs, the
node closer to the source sends an error message to the source, and also broadcasts the
data packet to its neighbors. The packet indicates in the data header that the link has
broken and that the packet is in need of alternate routing. When the neighboring nodes
receive the packet, they forward it to the destination if they have a route for that desti-
There are additional proposals that describe new protocols to handle multipath routing
[30, 39, 50]. One of these, the Split Multipath Routing (SMR) protocol [30], operates sim-
ilarly to the reactive protocols described in Section 10.3; however, the protocol makes the
following modifications. To obtain maximal node disjoint paths, intermediate nodes are
not allowed to respond to route requests. Further, route requests and route replies contain
entire routing paths. Intermediate nodes forward the first route request they receive, and

only rebroadcast subsequent ones if the requests arrive from different neighbors and have
not traveled further from the source than the first route request received. When the desti-
nation receives the request, it responds to the first request, and then waits a time interval
to receive additional requests. At the end of the time interval, it responds to the request
that traveled the route most disjoint from the original request received. The protocol can
be easily configured so that the destination responds to more than two requests.
Finally, [42] investigates the impact of alternate path routing on ad hoc routing proto-
cols, particularly focusing on load balancing and the concurrent utilization of multiple
routes. In particular, it studies the impact of route coupling in ad hoc networks with only a
single available channel. Route coupling occurs when two routes have nodes or links in
common. The authors discover that, while alternate routes enable a reduction in end-to-
end delay, the route coupling results in an underutilization of network resources, thereby
preventing alternate path routing from achieving significant performance improvements.

10.7.2 Energy-Conserving Protocols
All of the routing protocols previously described in this chapter were designed with the
characteristics of a mobile environment in mind. Hence, each protocol attempts to reduce
control overhead and processing requirements so as to minimize power utilization. How-
ever, there is a set of ad hoc routing protocols that have been designed with the specific
goal of further minimizing energy consumption. These protocols take a variety of ap-
proaches toward energy efficiency, including powering down unutilized nodes, load bal-
ancing, and dynamic transmission power adjustment.
The Geographical Adaptive Fidelity (GAF) algorithm [61] is an example of an energy-
conservaing protocol that powers down unutilized nodes. GAF is able to identify routing-
equivalent nodes in a network so that unnecessary nodes can be turned off. GAF nodes
utilize location information, such as that provided through GPS, to create a virtual grid.
All nodes within a given grid square are equivalent with respect to routing functionality.
Nodes in the grid square can therefore coordinate to determine the sleep duration for each
node. The nodes can be coordinated such that load balancing aids in the overall energy
utilization of each node; each node takes a turn forwarding data packets.
Routing based on overall energy cost and remaining battery lifetimes is performed by
the Battery Energy Efficient (BEE) protocol [13]. This protocol assigns to each route a
cost function that takes into account both energy cost and battery lifetime. When a source
initiates a data stream, it evaluates the cost function for all the possible loop-free routes to
the destination. It selects the route that minimizes the cost function. Similar to this work,
[11] describes an approach that balances path selection and energy consumption rates
among the network nodes in proportion to the available energy reserves of the nodes.
A number of protocols dynamically adapt node transmission ranges to reduce overall
power consumption. For instance, the approach described in [17] computes the power cost
along the discovered paths from the source to the destination. The path with the minimum
such cost is selected. The network nodes use a power management scheme such that nodes
are grouped into clusters, and each node transmits at the minimum power level to reach
each of the nodes in the cluster. Along these same lines, the protocol proposed in [51] dy-
namically adjusts node transmit powers to maintain a connected topology using minimum
power. Nodes in dense portions of the network decrease their transmission power to reach
fewer nodes, whereas nodes in remote areas of the network increase their transmission pow-
er to become more fully connected. It should be noted, however, that increasing the number

of hops in a path has the drawback of increasing the likelihood of a link break in that path.
This can result in an increase in control overhead due to the additional route repairs.
In addition to routing protocols, there is a wide range of research on power-efficient
MAC protocols and transport layer protocols. For instance, the Power-Aware Multiple Ac-
cess Protocol with Signalling (PAMAS) [57] utilizes information gleaned from RTS/CTS
exchanges to turn off nodes when they are not receiving packets. Because the RTS and
CTS messages contain the length of an upcoming data packet, nodes receiving this mes-
sage that are not the sender or receiver of the data packet can safely turn off their inter-
faces while the data packet is being transmitted.

10.7.3 Security-Aware Protocols
The open nature of wireless communication and the portability of mobile devices creates a
challenge for securing mobile networks. In contrast to wired networks, intruders do not
need to compromise network hosts to gain access to the network; malicious nodes need only
be within transmission range of a node in order to participate in and overhear network traf-
fic. Although securing ad hoc networks is a challenge, it is a necessary component for ad
hoc networks to be universally deployed. Recent ad hoc network security research has ad-
dressed a wide range of security topics, from secure routing to intrusion detection and mon-
itoring. In this section, a sampling of approaches from these two areas is highlighted. Secure Routing. When performing an on-demand route discovery such as
those described in Section 10.3, there are a number of possible attacks. Malicious nodes
can lie about the existence of paths and can modify the information in routing messages to
influence path selection. Further, a source node has no method for determining whether a
path actually exists when it receives a route reply. However, in nearly every application
scenario a user would like to be assured that his or her data traffic is actually reaching its
intended destination. To address this issue, a number of secure routing protocols have
been developed. Some of these protocols attempt to secure existing routing protocols,
such as those described in Section 10.3. Others are new routing protocols that have been
designed with the primary goal of security.
An example of this latter type of protocol is the Authenticated Routing for Ad Hoc
Networks (ARAN) Protocol [55]. ARAN is based on certificates and assumes that all net-
work nodes can obtain a certificate from a trusted certificate server before joining the ad
hoc network. The certificate contains the public key of the node. ARAN utilizes a route
discovery procedure similar to AODV A source node S generates a Route Discovery Pack-
et (RDP) for a destination. The RDP is signed with the source™s private key and contains
its certificate. When a neighbor A receives the RDP message, it verifies the signature of
the source by extracting S™s public key from its certificate, and then sets up a reverse path
back to the source node. The node then signs the contents of the message, appends its own
certificate, and broadcasts the message to its neighbors. When A™s neighbor B receives the
message, it validates A™s signature, and then replaces this signature with its own signature
(the signature of the source node is retained). The packet continues to be rebroadcast in


. 56
( 87 .)