Overview of ad-hoc routing protocols
Ad-hoc networking has attracted a lot of research over the last few years. This has
led to the development of many new routing algorithms. Hong separates them into three
categories:
1. Flat ad-hoc routing
These protocols comprise those protocols that do not set up hierarchies with clusters
of nodes, special nodes acting as the head of a cluster, or different routing algorithms in
side or outside certain regions.
This category falls into two subcategories:
(I). Proactive protocols:
1. It set up tables required for routing regardless of any traffic that would
require routing functionality. DSDV is a classic member of this group .
2. Many protocols belonging to this group are based on a link-state algorithm
as known from fixed networks. Link-state algorithms flood their information
about neighbors periodically or event triggered.
3. A general advantage of proactive protocols is that they can give QoS
guarantees related to connection set-up, latency or other real-time
requirements. As long as the topology does not change too fast, the routing
tables reflect the current topology with a certain precision.
4. A big disadvantage of proactive schemes are their overheads in lightly
loaded networks. In dependent of any real communication the algorithm
continuously updates the routing tables. This generates a lot of unnecessary
traffic and drains the batteries of mobile devices.
(ii). Reactive protocols:
1. It try to avoid this problem by setting up a path between sender and receiver only
if a communication is waiting. The two most prominent members of this group are
dynamic source routing (DSR, Johnson , 1996) and ad-hoc on-demand distance
vector (AODV, Perkins, 2001a), an on-demand version of DSDV.
2. AODV acquires and maintains routes only on demand like DSR does. Both
protocols, DSR and AODV, are the leading candidates for standardization in the
IETF.
3. A clear advantage of on-demand protocols is scalability as long as there is only
light traffic and low mobility. Mobile devices can utilize longer low-power
periods as they only have to wake up for data transmission or route discovery.
4. However, these protocols also exhibit disadvantages. The initial search latency
may degrade the performance of interactive applications. Route caching, a
mechanism typically employed by on-demand protocols, proves useless in high
mobility situations as routes change too frequently.
2. Hierarchical ad-hoc rout ing
1. The motivation behind this approach is the locality property, meaning that if a
cluster can be established, nodes typically remain within a cluster, only some
change clusters. The approach basically hides all the small details in clusters
which are further away.
2. Fig below shows an ad-hoc network with interconnection to the internet via a
base station. This base station transfers data to and from the cluster heads. In this
example, one cluster head acts as head of the super cluster, routing traffic to and
from the super cluster.
Fig: Building
hierarchies in ad-
hoc networks
3. Cluster head-Gateway Switch Routing (CGSR, Chiang, 1997) is a typical
representative of hierarchical routing algorithms based on distance vector (DV)
routing (Kurose, 2003). Compared to DV protocols, the hierarchy helps to reduce
routing tables tremendously.
4. An algorithm based on the link-state (LS) principle is hierarchical state routing
(HSR, Pei, 1999). This applies the principle of clustering recursively, creating
multiple levels of clusters and clusters of clusters etc.
5. A typical hybrid hierarchical routing protocol is the zone routing protocol
(ZRP, Haas, 2001). Each node using ZRP has a predefined zone with the node as
the center. The zone comprises all other nodes with in a certain hop-limit.
6. Due to the established hierarchy, HSR and CGSR force the traffic to go through
certain nodes which may be a bottleneck and which may lead to suboptimal paths.
ZRP faces the problem of flat on-demand schemes as soon as the network size
increases as many destinations are then outside the zone.
3. Geographic-position-assisted ad-hoc routing
1. If mobile nodes know their geographical position this can be used for routing
purposes. This improves the overall performance of routing algorithms if
geographical proximity also means radio proximity.
2. One way to acquire position information is via the global positioning system
(GPS). Mauve (2001) gives an overview of several position-based ad-hoc routing
protocols.
3. GeoCast (Navas, 1997) allows messages to be sent to all nodes in a specific
region . This is done using addresses based on geographic information instead of
logical numbers.
4. The location-aided routing protocol (LAR, Ko , 2000 ) is similar to DSR, but
limits route discovery to certain geographical regions.
5. Another protocol that is based on location information is greedy perimeter
stateless routing (GPSR, Karp , 2000). The main scheme of the protocol, is that
the packets are always forwarded to the neighbor that is geographically closest to
the destination. Additional mechanisms are applied if a dead end is reached.
