Topic Five
Ad-hoc Networks
Introduction
There are currently two variations of mobile wireless networks infrastructured and
infrastructureless networks.
The infrastructured networks, also known as Cellular network, have fixed and wired gateways.
They have fixed base stations that are connected to other base stations through wires. The
transmission range of a base station constitutes a cell. All the mobile nodes lying within this cell
connects to and communicates with the nearest bridge (base station). A hand off occurs as
mobile host travels out of range of one Base Station and into the range of another and thus,
mobile host is able to continue communication seamlessly throughout the network. Example of
this type includes office wireless local area networks (WLANs).
The other type of network, Infrastructureless network, is known as Mobile Ad NETwork
(MANET). These networks have no fixed routers. All nodes are capable of movement and can
be connected dynamically in arbitrary manner. The responsibilities for organizing and
controlling the network are distributed among the terminals themselves. The entire network is
mobile, and the individual terminals are allowed to move at will relative to each other. In this
type of network, some pairs of terminals may not be able to communicate directly to with each
other and relaying of some messages is required so that they are delivered to their destinations.
The nodes of these networks also function as routers, which discover and maintain routes to
other nodes in the networks. The nodes may be located in or on airplanes, ships, trucks, cars,
perhaps even on people or very small devices.
The chief difference between ad hoc networks and infrastructure networks is that there is no centralized
entity within an ad hoc network. There are no base stations or mobile switching centers in an ad hoc
network.
Page 1
5.1. Ad-hoc Networks
Ad Hoc network is a collection of wireless mobile hosts forming a temporary network without
the aid of any centralized administration, in which individual nodes cooperate by forwarding
packets to each other to allow nodes to communicate beyond direct wireless transmission range.
Figure 5.1: Ad Hoc Network
The interest in wireless ad hoc networks stems from of their well-known advantages for certain
types of applications. Since, there is no fixed infrastructure, a wireless ad hoc network can be
deployed quickly. Thus, such networks can be used in situations where either there is no other
wireless communication infrastructure present or where such infrastructure cannot be used
because of security, cost, or safety reasons.
Ad-hoc networks were mainly used for military applications. Since then, they have become increasingly
more popular within the computing industry. Applications include emergency search and rescue
operations, deployment of sensors, conferences, exhibitions, virtual classrooms and operations in
environments where construction of infrastructure is difficult or expensive. Ad-hoc networks can be
rapidly deployed because of the lack of infrastructure.
5.2. Characteristics of MANET
Dynamic Topologies: Since nodes are free to move arbitrarily, the network topology may
change randomly and rapidly at unpredictable times. The links may be unidirectional or
bidirectional.
Bandwidth constrained, variable capacity links: Wireless links have significantly lower
capacity than their hardwired counterparts. Also, due to multiple access, fading, noise, and
interference conditions etc. the wireless links have low throughput.
Page 2
Energy constrained operation: Some or all of the nodes in a MANET may rely on batteries. In
this scenario, the most important system design criteria for optimization may be energy
conservation.
Limited physical security: Mobile wireless networks are generally more prone to physical
security threats than are fixed- cable nets. The increased possibility of eavesdropping, spoofing,
and denial-of-service attacks should be carefully considered. Existing link security techniques
are often applied within wireless networks to reduce security threats. As a benefit, the
decentralized nature of network control in MANET provides additional robustness against the
single points of failure of more centralized approaches.
5.3. Routing Protocols
Routing is a process of exchanging information from one station to other stations of the network.
Routing protocols of mobile ad-hoc network tend to need different approaches from existing
Internet protocols because of dynamic topology change, mobile host, distributed environment,
less bandwidth, less battery power.
Why Routing Protocols are the main issue In Ad Hoc networks
Routing support for mobile hosts is presently being formulated as mobile IP technology when the
mobile agent moves from its home network to a foreign (visited) network, the mobile agent tells
a home agent on the home network to which foreign agent their packets should be forwarded. In
addition, the mobile agent registers itself with that foreign agent on the foreign network. Thus,
the home agent forwards all packets intended for the mobile agent to the foreign agent, which
sends them to the mobile agent on the foreign network. When the mobile agent returns to its
original network, it informs both agents (home and foreign) that the original configuration has
been restored. No one on the outside networks need to know that the mobile agent moved.
But in Ad Hoc networks there is no concept of home agent as it itself may be moving.
Supporting Mobile IP from host mobility requires address management, protocol interoperability
enhancements and the like, but core network functions such as hop by hop routing still presently
rely upon preexisting routing protocols operating within the fixed network. In contrast, the goal
of mobile ad hoc networking is to extend mobility into the realm of autonomous, mobile,
wireless domains, where a set of nodes, which may be combined routers and hosts, themselves
form the network routing infrastructure in an ad hoc fashion. Hence, the need to study special
routing algorithms to support this dynamic topology environment. Routing protocols for mobile
Page 3
ad-hoc networks have to face the challenge of frequently changing topology, low transmission
power and asymmetric links.
A number of routing protocols have been suggested for ad-hoc networks. These protocols can be
classified into two main categories:
1. Table driven routing protocols (proactive schemes)
2. Source initiated on demand routing protocols (reactive schemes)
Figure 5.2: Categorization of ad hoc routing protocols.
5.3.1. Table Driven Routing Protocols
Table-driven routing protocols attempt to maintain consistent, up-to-date routing information
from each node to every other node in the network. These protocols require each node to
maintain one or more tables to store routing information, and they respond to changes in network
topology by propagating updates throughout the network in order to maintain a consistent
network view. The areas in which they differ are the number of necessary routing-related tables
and the methods by which changes in network structure are broadcast.
Some of the table driven routing protocols are Destination Sequenced Distance Vector Routing
protocols (DSDV), Clusterhead Gateway Switching Routing Protocol (CGSR), Hierarchical
State Routing (HSR), and Wireless Routing Protocol (WRP) etc.
Destination Sequenced Distance Vector Routing Algorithm
Page 4
The Destination Sequenced Distance Vector (DSDV) Routing Algorithm is based on the idea of the
Distributed Bellman Ford (DBF) Routing Algorithm with certain improvements. The primary concern
with using a Distributed Bellman Ford algorithm in Ad Hoc environment is its susceptibility towards
forming routing loops and counting to infinity problem. DSDV guarantees loop free paths at all instants.
Each node maintains a routing table, which contains entries for all the nodes in the network.
Each entry consists of:
the destination's address
the number of hops required reaching the destination (hop count)
the sequence number as stamped by the destination.
Whenever a node B comes up, it broadcasts a beacon message ("I am alive message") stamping it
with a locally maintained sequence number. The nodes in its neighborhood listen to this message
and update the information for this node. If the nodes do not have any previous entry for this
node B, they simply enter B's address in their routing table, together with hop count and the
sequence number as broadcasted by B. If the nodes had previous entry for B, then sequence
number of broadcasted information is compared to the sequence number stored in the node for
destination B. If the message received has a higher sequence number, then this means that the
node B has propagated a new information about its location so the entry must be updated in
accordance with the new information received. The information with a newer sequence number
is definitely new as the node B itself stamps sequence number.
The new information that a node receives is scheduled for broadcasting to its neighbors so that
they can know about the changes in topology. The neighboring nodes also follow the same rule
i.e. updating the information when information about a node with a newer sequence number is
received. The metrics for routes chosen from the newly received broadcast information are each
incremented by one hop. So, the new information is updated gradually at all nodes and they now
know the next hop node in order to correctly route the packet to destination B. B also generates
the new information with a newer sequence number when it sees that it is moving. By moving, it
is meant that B observes that there is a change in topology because it's neighbors are changing,
may be due to it's motion or other nodes (neighbors) motion. And it comes to know that the
neighbors are changing since it receives new beacon messages or does not receive beacon
messages from its current neighbors.
The information is broadcasted periodically to neighbors. It could be advertised when
specifically asked for or when there is a significant change in topology. Thus, it is both 'event
driven' and 'time driven'.
Page 5
Clusterhead Gateway Switch Routing
The Clusterhead Gateway Switch Routing (CGSR) protocol differs from the previous protocol in
the type of addressing and network organization scheme employed. Instead of a flat network,
CGSR is a clustered multi hop mobile wireless network with several heuristic routing schemes.
In that by having a cluster head controlling a group of ad hoc nodes, a framework for code
separation (among clusters), channel access, routing, and bandwidth allocation can be achieved.
A cluster head selection algorithm is utilized to elect a node as the cluster head using a
distributed algorithm within the cluster. The disadvantage of having a cluster head scheme is that
frequent cluster head changes can adversely affect routing protocol performance since nodes are
busy in cluster head selection rather than packet relaying.
Hence, instead of invoking cluster head reselection every time the cluster membership changes, a
Least Cluster Change (LCC) clustering algorithm is introduced. Using LCC, cluster heads only
change when two cluster heads come into contact, or when a node moves out of contact of all
other cluster heads.
CGSR uses DSDV as the underlying routing scheme, and hence has much of the same overhead
as DSDV. However, it modifies DSDV by using a hierarchical cluster-head-to-gateway routing
approach to route traffic from source to destination. Gateway nodes are nodes that are within
communication range of two or more cluster heads. A packet sent by a node is first routed to its
cluster head, and then the packet is routed from the cluster head to a gateway to another cluster
head, and so on until the cluster head of the destination node is reached. The packet is then
transmitted to the destination. Figure 5.3 illustrates an example of this routing scheme. Using this
method, each node must keep a cluster member table where it stores the destination cluster head
for each mobile node in the network. Each node periodically using the DSDV algorithm
broadcasts these cluster member tables. Nodes update their cluster member tables on reception of
such a table from a neighbor. In addition to the cluster member table, each node must also
maintain a routing table, which is used to determine the next hop in order to reach the
destination. On receiving a packet, a node will consult its cluster member table and routing table
to determine the nearest cluster head along the route to the destination. Next, the node will check
its routing table to determine the next hop used to reach the selected cluster head. It then
transmits the packet to this node.
Page 6
Figure 5.3:-CGSR: routing from node 1 to node 8.
Page 7
5.3.2. Source Initiated On Demand Routing:
A different approach from table-driven routing is source-initiated on demand routing. This type
of routing creates routes only when desired by the source node. When a node requires a route to
a destination, it initiates a route discovery process within the network. This process is completed
once a route is found or all possible route permutations have been examined. Once a route has
been established, it is maintained by a route maintenance procedure until either the destination
becomes inaccessible along every path from the source or until the route is no longer desired.
The source initiated on-demand routing protocols are Ad Hoc On-Demand Distance Vector
Routing (AODV), Dynamic Source Routing (DSR), and Temporally Ordered Routing Algorithm
(TORA). There are many others routing protocols available. Zone Routing Protocol (ZRP) is the
hybrid routing protocol.
Ad Hoc On Demand Distance Vector Routing (AODV)
The Ad Hoc On Demand Distance Vector (AODV) routing protocol builds on the DSDV
algorithm previously described. AODV is an improvement on DSDV because it typically
minimizes the number of required broadcasts by creating routes on a demand basis, as opposed
to maintaining a complete list of routes as in the DSDV algorithm. AODV classify as a pure on-
demand route acquisition system, since nodes that are not on a selected path do not maintain
routing information or participate in routing table exchanges.
When a source node desires to send a message to some destination node and does not already
have a valid route to that destination, it initiates a path discovery process to locate the other node.
It broadcasts a route request (RREQ) packet to its neighbors, which then forward the request to
their neighbors, and so on, until either the destination or an intermediate node with a fresh
enough routes to the destination is located. Figure 5.4(a) illustrates the propagation of the
broadcast RREQs across the network. AODV utilizes destination sequence numbers to ensure all
routes are loop free and contain the most recent route information. Each node maintains its own
sequence number, as well as a broadcast ID. The broadcast ID is incremented for every RREQ
the node initiates, and together with the node’s IP address, uniquely identifies an RREQ. Along
with its own sequence number and the broadcast ID, the source node includes in the RREQ the
most recent sequence number it has for the destination. Intermediate nodes can reply to the
RREQ only if they have a route to the destination whose corresponding destination sequence
number is greater than or equal to that contained in the RREQ.
Page 8
During the process of forwarding the RREQ, intermediate nodes record in their route tables the
address of the neighbor from which the first copy of the broadcast packet is received, thereby
establishing a reverse path. If additional copies of the same RREQ are later received, these
packets are discarded.
Once the RREQ reaches the destination or an intermediate node with a fresh enough route, the
destination intermediate node responds by unicasting a route reply (RREP) packet back to the
neighbor from which it first received the RREQ(Fig.5.4 b). As the RREP is routed back along
the reverse path, nodes along this path set up forward route entries in their route tables which
point to the node from which the RREP came. These forward route entries indicate the active
forward route. Associated with each route entry is a route timer that will cause the deletion of the
entry if it is not used within the specified lifetime. Because the RREP is forwarded along the path
established by the RREQ, AODV only supports the use of symmetric links. Routes are
maintained as follows. If a source node moves, it is able to reinitiate the route discovery protocol
to find a new route to the destination. If a node along the route moves, its upstream neighbor
notices the move and propagates a link failure notification message (an RREP with infinite
metric) to each of its active upstream neighbors to inform them of the erasure of that part of the
route. These nodes in turn propagate the link failure notification to their upstream neighbors, and
so on until the source node is reached. The source node may then choose to reinitiate route
discovery for that destination if a route is still desired.
An additional aspect of the protocol is the use of hello messages, periodic local broadcasts by a
node to inform each mobile node of other nodes in its neighborhood. Hello messages can be used
to maintain the local connectivity of a node. However, the use of hello messages is not required.
Nodes listen for retransmission of data packets to ensure that the next hop is still within reach. If
such a retransmission is not heard, the node may use any one of a number of techniques,
including the reception of hello messages, to determine whether the next hop is within
communication range. The hello messages may list the other nodes from which a mobile has
heard, thereby yielding greater knowledge of network connectivity.
Page 9
Figure 5.4: AODV routing protocol
Dynamic Source Routing Protocol (DSR)
The Dynamic Source Routing (DSR) protocol presented in is an on-demand routing protocol that
is based on the concept of source routing. Mobile nodes are required to maintain route caches
that contain the source routes of which the mobile is aware. Entries in the route cache are
continually updated as new routes are learned.
The protocol consists of two major phases: route discovery and route maintenance. When a
mobile node has a packet to send to some destination, it first consults its route cache to determine
whether it already has a route to the destination. If it has an unexpired route to the destination, it
will use this route to send the packet. On the other hand, if the node does not have such a route, it
initiates route discovery by broadcasting a route request packet. This route request contains the
address of the destination, along with the source node’s address and a unique identification
number. Each node receiving the packet checks whether it knows of a route to the destination. If
it does not, it adds its own address to the route record of the packet and then forwards the packet
along its outgoing links. To limit the number of route requests propagated on the outgoing links
of a node, a mobile only forwards the route request if the mobile has not yet seen the request and
if the mobile’s address does not already appear in the route record.
A route reply is generated when the route request reaches either the destination itself, or an
intermediate node, which contains in its route cache an unexpired route to the destination. By the
time the packet reaches either the destination or such an intermediate node, it contains a route
record yielding the sequence of hops taken. Figure 5.5 (a) illustrates the formation of the route
record as the route request propagates through the network. If the node generating the route reply
is the destination, it places the route record contained in the route request into the route reply. If
the responding node is an intermediate node, it will append its cached route to the route record
and then generate the route reply. To return the route reply, the responding node must have a
route to the initiator. If it has a route to the initiator in its route cache, it may use that route.
Otherwise, if symmetric links are supported, the node may reverse the route in the route record.
Page 10
If symmetric links are not supported, the node may initiate its own route discovery and
piggyback the route reply on the new route request. Figure 5.4 (b) shows the transmission of the
route reply with its associated route record back to the source node.
Route maintenance is accomplished through the use of route error packets and
acknowledgments. Route error packets are generated at a node when the data link layer
encounters a fatal transmission problem. When a route error packet is received, the hop in error
is removed from the node’s route cache and all routes containing the hop are truncated at that
point. In addition to route error messages, acknowledgments are used to verify the correct
operation of the route links. Such acknowledgments include passive acknowledgments, where a
mobile is able to hear the next hop forwarding the packet along the route.
Figure 5.5: DSR routing protocol
Page 11
One tradeoff between source routing and distance vector routing is the handling of partitioned
networks. Under dynamic source routing, if a host wishes to communicate with an unreachable
host, then though the rate at which route request are made will be reduced by a back off
mechanism but the protocol continues to make periodic efforts to find a route to the unreachable
host, consuming some network resources. Under distance vector routing, with the assumption
that routes have had time to converge once the host become unreachable, no network resources
are used trying to send packets to unreachable host, as none of the host in the sender's partition of
the network has a routing table entry for the destination.
Comparison
Parameters On Demand Table Driven
Availability of routing Available Always available
Information when needed regardless of need
Routing philosophy Flat Mostly flat, except
CGSR
Periodic route updates Not required Required
Coping with mobility Use localized Inform other nodes
route to achieve a
discovery consistent routing
table
Greater than that of on
Signaling traffic Grows with
generated increasing demand routing
mobility
Table 5.1: comparison of on demand and table driven routing with different parameters
5.3.3 Hybrid Scheme
Zone Routing Protocol (ZRP)
Proactive routing uses excess bandwidth to maintain routing information, while reactive routing
involves long route request delays. Reactive routing also inefficiently floods the entire network
Page 12
for route determination. The Zone Routing Protocol (ZRP) aims to address the problems by
combining the best properties of both approaches. ZRP can be classed as a hybrid
reactive/proactive routing protocol.
In an ad-hoc network, it can be assumed that the largest part of the traffic is directed to nearby
nodes. Therefore, ZRP reduces the proactive scope to a zone centered on each node. In a limited
zone, the maintenance of routing information is easier. Further, the amount of routing
information that is never used is minimized. Still, nodes farther away can be reached with
reactive routing. Since all nodes proactively store local routing information, route requests can
be more efficiently performed without querying all the network nodes.
• AODV –unicast route discovery
• RREQ (route request) is broadcast
• Sequence Number:
– Source SN: freshness on reverse route to source
– Destination SN: freshness on route to destination
• RREQ message
– <bcast_id, dest_ip, dest_seqno, src_seqno, hop_count>
• RREP (route reply) is unicast back
– From destination if necessary
– From intermediate node if that node has a recent route
1. Node S needs a route to D
2. Create a route request (RREQ)
Page 13
• Enters D’ s IP address, sequence number, S’s IP address, sequence number
• Broadcasts RREQ to neighbors
3. Node A receives RREQ
• Makes reverse route entry for S
• Dest= S, nexthop= S, hopcount= 1
• It has no route to D, so it broadcasts RREQ
4. Node C receives RREQ
• Makes reverse route entry for S
• Dest= S, nexthop= A, hopcount= 2
• It has route to D && seq# for route D > seq# in RREQ
• Creates a route reply (RREP)
• Enters D ’ s IP address, sequence number, S’ s IP address, hopcount
• Unicasts RREP to A
[Link] A receives RREP
• UnicastsRREP to S
• Makes forward route entry to D
• Dest= D, nexthop= C hopcount= 2
[Link] S receives RREP
• Makes forward route entry to D
• Dest= D, nexthop= A hopcount= 3
• Sends data packets on route to D
DSDV An Example
Page 14
• In this example node X moves from its first position where it is a neighbor of node B to a
new position where it is a neighbor of node E.
• Routing Tables at Node A prior to Node X’s migration
Destination Next Hop Cost Sequence
Number
A A 0 666
B B 1 403
C C 1 102
D C 2 549
E C 2 440
X B 2 331
• The sequence number entry indicates the last sequence number received from that
destination.
• When Node X moves, it would generate a new route update that is sent to Node E.
Page 15
• Node E would propagate this to Node C, which in turn propagates this to the other
nodes.
• Note: In the interim many intermediate changes would have occurred (e.g. Node B
detects that the link to Node X is broken) and this would trigger other route updates.
• Thus, sequence numbers associated with other destinations would have changed as well.
Page 16