DR.X.

SUSAN CHRSITINA
• Unit I Ad Hoc Networks – Introduction And Routing Protocols

• Unit II Sensor Networks – Introduction & Architectures

• Unit III WSN Networking Concepts And Protocols

• Unit IV Sensor Network Security

• Unit V Sensor Network Platforms And Tools

CO NO Course Outcomes RBT-Level
C0704.1 D e s c r i b e t h e d e s i g n i s s u e s a n d c h a l l e n g e s i n A d h o c w i re l e s s s e n s o r
networks for managing the network. K2-Understand
C0704.2 Discuss various routing protocols for Adhoc wireless sensor networks to establish
communication between nodes. K3-Apply
C0704.3 Analyze the performance of various protocols in Adhoc
sensor networks to identify appropriate protocol for given application K4-Analyze

C0704.4 Discuss the challenges in designing MAC protocols, routing protocol, physical
layer, Transport protocols and network programming for wireless Adhoc
K4-Analyze
Networks to optimize network performance.

C0704.5 Explain the network architecture, sensor/mote and sensor security issues for K2-understand
designing wireless sensor networks.
C0704.6 Comprehend various network protocols and network simulation tools for K2-understand
designing Adhoc wireless networks.
Reference Book • Wired and Wireless
C. Siva Ram Murthy and B. S. Manoj, ―Ad Hoc Network
Wireless Networks Architectures and Protocols, • Infrastructure and
Prentice Hall, Infrastructure less
• What is Adhoc network
• Difference between cellular
and Adhoc
• Characteristic of Adhoc
• Advantages of Adhoc

TOPIC 1
 • Nodes are connected with the fixed
physical representation
• Nodes are communicated through AP
• Examples - GSM, UMTS and WLAN etc.

• Infrastructure less where the node is

communicated without any fixed physical
representation.

Infrastructure less
 B
A

D
E

Switching Center
+
Gateway

Base Station Mobile Node Path from C to E

5
Figure A cellular networks.
 • No preexisting infrastructure,
such as no fixed routers or access
B points
A • Each node participates in
C
routing by forwarding data
F through other nodes as required
E
to reach a destination
D
• Determination of which nodes
forward data is made
dynamically based on the
network connectivity.

Mobile Node Wireless Link Path from C to E

6
Figure. An ad hoc wireless networks
"Ad Hoc" is actually a Latin phrase that means "for this purpose.“
Definition
An adhoc network is collection of mobile nodes, which forms a temporary
network without the aid of centralized administration or Standard support
device. Node itself act as a router and host. The router are free to move
randomly and organize themselves arbitrarily. Limited transmission range.
 Cellular networks Ad-hoc wireless networks
Fixed infrastructure Not fixed infrastructure

Single hop wireless links multi -hop wireless links

Fixed routing Dynamic routing

Circuit -switched Packet -switched

High cost and time of deployment Very quick and cost-effective

Guaranteed bandwidth (designed Shared radio channel

for voice traffic) (more suitable for best-effort data traffic)
Seamless connectivity (low call drops during handoffs) Frequency path break due to
mobility
High cost of network maintenance Maintenance operations are built-in
Low complexity of mobile devices Intelligent mobile devices are required
Reuse of frequency spectrum through geographical Dynamic frequency reuse based on carrier sense
channel reuse mechanism
• Dynamically changing topology
- Network topology may change dynamically as the nodes are free to move

• Energy-constrained operation
- Nodes in ad hoc network may rely on batteries or other limited energy sources
• Peer-to-peer
- No more or less “important” nodes
• Bandwidth-constrained, variable capacity links
• Each of the nodes act as a router and as a host.
❒ Mobility causes route changes

1
• Limited physical security
• More prone to physical security threats than wired networks
• Incl. stealing mobile ad hoc devices
• Many attacks, incl. Eavesdropping, spoofing, and DoS attacks are easier
• Decentralized network control
• Eliminates single points of failure (=> better reliability)
• Scalability problems
• As networks get large
• Capable of being multi-hopped when the intended node goes out of range of network.
• Mobile nodes are characterized with less memory, power and light weight features.
• The access to channel by any node is not restricted.
• Because the network is easy to set up, it can be setup at any place.
• It has a distributed administration
• Lack of infrastructure makes the network robust in network failure.
• It is scalable. This means that network accommodates addition of more nodes.
• It is very cheap to set up since there is no wiring of nodes.
• It has adaptive computing and self -configuring capability
• It does not restrict access to channels.
 • Issues
• Applications

TOPIC 3
• Limited bandwidth:
• Wi-Fi ad hoc uses the unlicensed ISM (Industrial, Scientific, and Medical radio bands)
2.4 GHz radios.
• The limited radio band results in reduced data rate compared to wireless networks.
Adhoc - 54 Mbps
• Hence, optimal usage of bandwidth is necessary by keeping low overhead as possible.

• Energy constraints: Most of the nodes rely on limited battery life. Some of the
power of the batteries is used for data transmission, data processing and for
routing packets to their destination. This is a critical issue in the design of an ad
hoc network.
• Dynamic network topology: The frequent movement of nodes compounds the
challenges of designing an ad hoc network due to frequent path breaks.
• Routing overhead: Due to the mobility of nodes within the ad hoc network, stale
routes are generated in the routing table leading to routing overhead.
• Packet loss due to transmission error: The vulnerable nature of wireless
networks often lead to frequent packet loss due to traffic collision caused by
hidden terminals, interference and frequent path breaks caused by mobility of
nodes.
• Frequent network partitions: The random movement of nodes often leads to
network partition. This affects mostly the intermediate nodes.
• Limited physical security threats: Mobile nodes are more vulnerable to attacks
within and outside network.
• Military Applications
– Establishing communication among a group of soldiers for tactical
operations
– Coordination of military object moving at high speeds such as
fleets of airplanes or ships
– Requirements: reliability, efficiency, secure communication, and
multicasting routing,
• Emergency Operations
– Search, rescue, crowd control, and commando operations
– Support real-time and fault-tolerant communication paths
• Collaborative and Distributed Computing
– Conference, distributed files sharing
– reliability of data transfer is of high importance
• Wireless Mesh Networks
• An alternate communication infrastructure for mobile or fixed nodes/users
• Provides many alternate paths for a data transfer session between a source and
destination
• Each node is connected to every other node, forming a "mesh, comprises various
wireless nodes with access points
• Each node in the network acts as a forwarding node to transfer the data.
• Since the network is decentralized, forwarding of data is possible only to the
neighboring node.
• This results in the network structure simple and easy.
• WMN makes the people connected with the Internet who work at remote
areas and operating business.
• Advantages of Wireless Mesh Networks
– High data rate, quick and low cost of deployment, enhanced services, high scalability,
easy extendability, high availability, and low cost per bit
 Wired Network

Gateway node

Transmission range
A house with rooftop transceiver Wired link to the Internet
Wireless link

Figure 5.4. Wireless mesh networks operating in a residential zone

2
Internet

Radio relay node

Multi-hop radio relay link Lamp

Wired link to the Internet Coverage area

Figure 5.5 Wireless mesh network covering a highway 27

• A collection of a large number of sensor nodes that are deployed in a particular region
• Applications:
– military, health care, home security, and environmental monitoring
• Differences with the ad hoc wireless networks:
– Mobility of nodes - Mobility of nodes is not a mandatory requirement in sensor networks
– size of network - The number of nodes in the sensor network can be much larger than ad hoc
wireless network.
– density of deployment - The density of nodes in a sensor network varies with the domain of
application.
– power constraints - The power constraints in sensor networks are much more stringent than those in
ad hoc wireless networks
– data/information fusion,
– traffic distribution- The communication traffic pattern varies with the domain of application
in sensor networks. This kind of traffic demands low bandwidth. In contrast, ad hoc
wireless networks generally carry user traffic such as digitized and packetized voice stream or
data traffic, which demands higher bandwidth.
• Medium access scheme
• Routing, Multicasting, TPC protocol
• Pricing scheme, QoS, Self-organization
• Security, Energy management
• Addressing and service discovery
• Deployment considerations
 • Adhoc wireless internet
• Routing protocol

TOPIC 4
• Ad hoc networks support efficient Internet connectivity, including mobility
management.
• Each node, have an arbitrary IP address in an ad hoc network, would require a
host route propagated to every router of the fixed network; clearly, this is an
unscalable approach.
• Mobile IP is considered as an access protocol, reduces the need for host route
dissemination.
Gate way Node
• Entry points to the wired Internet
• Owned and operated by a service provider
• keeping track of the end users, bandwidth management, load
balancing, traffic shaping, packet filtering, bandwidth fairness, and
address, service, and location discovery.
Gateways:

• Gateway nodes in the ad hoc wireless Internet are the entry points to the wired Internet.

• The major part of the service provisioning lies with the gateway nodes.

• Owned and operated by a service provider,

• Gateways perform the following tasks:

• keeping track of the end users, bandwidth management, load balancing, traffic shaping, packet
filtering, bandwidth fairness, and address, service, and location discovery.
• IP -unique 32-bit address1 which has two
parts, network identifier and host identifier,
• Traditional IP addressing is not supportive of
address mobility which is essential in
wireless Internet

• Solution : MobileIP2 is a solution

that uses an address redirection
mechanism for this address
mobility issue in wireless Internet.
Routing:
• Routing is a major problem in the ad hoc wireless Internet, due to the dynamic
topological changes, the presence of gateways, multi-hop relaying, and the hybrid character of
the network.
• solution : Use separate routing protocol, for the wireless part of the ad hoc wireless Internet.
Routing protocols – Table driven protocol, on demand protocol, Hybrid network routing
protocol.
Load balancing:
• Ad hoc wireless Internet gateways experience heavy. Hence the gateways can be saturated much
earlier than other nodes in the network.
• Load balancing techniques are essential to distribute the load so as to avoid the situation where
the gateway nodes become bottleneck nodes.
• Proper Gateway selection strategies and load balancing schemes can be used for this purpose.
Pricing/billing:
• Since Internet bandwidth is expensive, it becomes very important to introduce
pricing/billing strategies for the ad hoc wireless Internet.
• Gateway is the preferred choice for charging the traffic to and from the Internet.
• A much more complex case is pricing the local traffic (traffic within the wireless part, that is, it
originated and terminated within the wireless part without passing through the gateway
nodes), where it becomes necessary to have a dedicated, secure, and lightweight pricing/billing
infrastructure installed at every node.
Provisioning of security:
• The inherent broadcast nature of the wireless medium attracts not just the mobility seekers but
also potential hackers who love to snoop on important information sent unprotected over the
air. Hence security is a prime concern in the ad hoc wireless Internet.
• Since the end users can utilize the ad hoc wireless Internet infrastructure to make e-commerce
transactions, it is important to include security mechanisms in the ad hoc wireless Internet.
 • What is Routing
• Routing protocol
• Issues in designing
routing protocol
• Hidden terminal and
Exposed problem

TOPIC 5
• Host mobility
• Dynamic topology
• Link failure / repair due to mobility

• Distributed environment
• Bandwidth constrained
• Energy constrained

Routing protocols that find a path to be followed by data packets from a source node to a destination
node
• Many factors affecting routing in MANETs:
• Models of topology
• Selection of routers
• Initiation of route requests
• Specific underlying characteristics
• E.g. application-based characteristics
• Major goals in selecting routing protocols:
• Provide the maximum possible reliability - use alternative
routes if an intermediate node fails
• Choose a route with the least cost
• E.g., minimal # of hops from source to destination
• Give the nodes the best possible response time and
throughput
• Each node in MANETs expected to serve as a router
• All execute the same routing protocol
• Protocol calculates a route
• Controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network.

• Nodes do not know the topology of their network, instead they have to discover it by their own as the topology
in the ad-hoc network is dynamic topology.

• The basic rules is that a new node whenever enters into an ad-hoc network, must announce its arrival and
presence and should also listen to similar announcement broadcasts made by other mobile nodes.
• Major goals in selecting routing protocols:
• Provide the maximum possible reliability - use alternative routes if an intermediate node fails
• Choose a route with the least cost
• E.g., minimal # of hops from source to destination
• Give the nodes the best possible response time and throughput
• Each node in MANETs expected to serve as a router
• All execute the same routing protocol
• Protocol calculates a route
Mobility:
• Ad hoc is highly dynamic due to the movement of nodes, hence
an on-going session suffers frequent path breaks.
1-4-2-6
• Disruption occurs either due to the movement of the
intermediate nodes in the path or due to the movement of
1-3-6
end nodes.
• Wired network routing protocols cannot be used in ad hoc
wireless networks because the nodes are stationary and the
path repair in wired network has slow convergence.
• Routing protocols for ad hoc wireless networks must be able to perform efficient
and effective mobility management.
Bandwidth Constraint:
• Abundant bandwidth is available in wired networks due to the advent of fiber optics

and due to the exploitation of wavelength division multiplexing (WDM) technologies.

• Wireless has less bandwidth due to the limited radio band, and hence the data rates it

can offer are much less than what a wired network can offer.

• So difficult to maintain topology information.

• Frequent change of topology causes more overhead of topology maintenance.
• So routing protocol use the bandwidth optimally by keeping the overhead as low as
possible.
Error-prone shared broadcast radio channel:
Wireless links have time varying characteristics in terms of link capacity and link-
error probability.
Resource Constraints:
Limited battery life and limited processing power
Hidden and exposed terminal problems
• The hidden terminal problem refers to the collision of packets at a receiving
node due to the simultaneous transmission of those nodes that are not within the
direct transmission range of the sender, but are within the transmission range of
the receiver.
• Collision of packets at a receiving node due to the simultaneous transmission of those nodes that are
not within the direct transmission range of the sender, but are within the transmission range of the
receiver.
• Terminal A sends data to B, terminal C cannot hear A
• Terminal C wants to send data to B, terminal C senses
a “free” medium (CS fails) and starts transmitting
Collision at B occurs, A cannot detect this collision
(CD fails) and continues with its transmission to B
• Terminal A is “hidden” from C and vice versa.
Solutions for this problem
• Medium access collision avoidance (MACA)
• Medium access collision avoidance for wireless (MACAW)
• Floor acquisition multiple access (FAMA)
• Dual busy tone multiple access (DBTMA)

Request To Send (RTS) from A to B

CTS from B to A
Data Send from A to B
DATA frame from A to B
ACK from B to A.
• Inability of a node which is blocked due to transmission by a nearby transmitting node to
transmit to another node.
• When a node is prevented from sending packets to other nodes because of a neighboring
transmitter is known as the exposed node problem.

• B sends to A, C wants to send to another terminal D not A

or B
• C senses the carrier and detects that the carrier is busy.
• C postpones its transmission until it detects the medium
as being idle again
• But A is outside radio range of C, waiting is not necessary
• C is “exposed” to B

Hidden terminals cause collisions, where as Exposed

terminals causes’ unnecessary delay.
 • Characteristics of an
Ideal Routing Protocol
• Classification
• Comparison reactive
and proactive protocol

TOPIC 6
1. It must be fully distributed, Distributed routing is more fault tolerant than centralized routing, which involves
the risk of single point of failure.
2. It must be adaptive to frequent topology changes caused by the mobility of nodes.
3. Route computation and maintenance must involve a minimum number of nodes. Each node in the network
must have quick access to routes, that is, minimum connection setup time is desired.
4. It must be localized, as global state maintenance involves a huge state propagation control overhead.
5. It must be loop-free and free from stale routes.
6. The number of packet collisions must be kept to a minimum by limiting the number of broadcasts made by
each node. The transmissions should be reliable to reduce message loss and to prevent the occurrence of stale
routes.
7. It must converge to optimal routes once the network topology becomes stable. The convergence must be
quick.
8. It must optimally use scarce resources such as bandwidth, computing power, memory, and battery
power.
9. Every node in the network should try to store information regarding the stable local topology only.
Frequent changes in local topology, and changes in the topology of parts of the network with which the
node does not have any traffic correspondence, must not in any way affect the node, that is, changes in
remote parts of the network must not cause updates in the topology information maintained by the node.
10. It should be able to provide a certain level of quality of service (QoS) as demanded by the applications,
and should also offer support for time-sensitive traffic.
The routing protocols for ad hoc wireless networks can be broadly classified into four categories
based on
• • Routing information update mechanism
• • Use of temporal information for routing
• • Routing topology
• • Utilization of specific resources
• Types of routing protocols:
1) Proactive Table Driven protocols
• Keep routes ready at all times
• When a packet needs to be forwarded, the route is already known
• Example: distance vector routing protocols (more below)
2) Reactive (= on-demand) protocols
• Route determination on demand
• Determine a route only when there is a packet to send
• Examples: flooding routing algorithms, ad hoc on-demand distance vector
(AODV), temporarily ordered routing algorithm (TORA) (more below)

• Proactive vs. reactive

• In proactive: a route available immediately
• In reactive: (1) a significant delay
(2) significant traffic of control msgs
(searching for a route)
 Proactive Reactive
Nodes continuously evaluate and Nodes evaluate and update routes only
update routes when they are needed

Periodic route-update packets Route update when necessary

Route from each node to every other Routes from Source to Destination
node in the network only
Routes are ready to use Routes constructed when needed,
instantaneously higher connection setup delay
Large routing tables Small or No routing tables
Large amount of Overhead Minimum overhead
Ad Hoc Routing Protocols Overview

Ad hoc Routing Protocols

Table Driven Hybrid Source-Initiated

(Proactive) On-demand Driven
(Reactive)
ZRP

CGSR DSDV WRP

AODV DSR TORA ABR SSR
• Routing Protocol:
• Table-driven (proactive)
• Source-initiated on-demand (reactive)
• Hybrid

• Routing Algorithm
• Link-State algorithm:
• Each node maintains a view of the network topology
• Distance-Vector algorithm:
• Every node maintains the distance of each destination
• Like the shortest-path computation method
• Each node maintains a view of the network topology with a cost for each link
• Periodically broadcast link costs to its outgoing links to all other nodes such as
flooding
 A

link costs
F

H
B

C
G
D
• known also as Distributed Bellman-Ford or RIP (Routing Information Protocol)
• Every node maintains a routing table
• all available destinations
• the next node to reach to destination
• the number of hops to reach the destination

• Periodically send table to all neighbors to maintain topology

 1 2
A B C
Dest. Next Metric … Dest. Next Metric … Dest. Next Metric …
A A 0 A A 1 A B 3
B B 1 B B 0 B B 2
C B 3 C C 2 C C 0
 B broadcasts the new routing
information to his neighbors

Routing table
is updated (A, 1) (A, 1)
(B, 0) (B, 0)
(C, 1) (C, 1)

1 1
A B C
Dest. Next Metric … Dest. Next Metric … Dest. Next Metric …
A A 0 A A 1 A B 3 2
B B 1 B B 0 B B 1
C B 3 2 C C 1 C C 0
 broadcasts to update
tables of C, B, A with
new entry for D

(A, 1) (A, 2)
(B, 0) (B, 1)
(C, 1) (C, 0)
(D, 2) (D, 1) (D, 0)

1 1 1
A B C D
Dest. Next Metric … Dest. Next Metric … Dest. Next Metric …
A A 0 A A 1 A B 2
B B 1 B B 0 B B 1
C B 2 C C 1 C C 0
D B 3 D C 2 D D 1
 1 1 1
A B C D
Dest. Next Metric … Dest.c Next Metric … Dest. Next Metric …
… … … … … … … … …
D B 3 D C 2 D B
D 1
 (D, 2) (D, 2)

1 1 1
A B C D
Dest. Next Metric … Dest. Next Metric … Dest. Next Metric …
… … … … … … … … …
D B 3 D C 2 D B 3
 (D,5)

(D,4) (D,4)

(D,3)

(D,2) (D,2)

1 1 1
A B C D
Dest. Next Metric … Dest.c Next Metric … Dest. Next Metric …
… … … … … … … … …
D B 3, 5, … D C 2, 4, 6… D B 3, 5, …
• DV not suited for ad-hoc networks!
• Loops
• Count to Infinity

• New Solution -> DSDV Protocol

 • Destination-Sequenced
Distance-Vector
Routing (DSDV)

TOPIC 7
• “Table-driven” because:
• Each node maintains table(s) with routing information for every other nodes in the network
• When the topology changes, updates are propagated throughout the network.
• Routing information is generally flooded in the whole network.
• Whenever a node requires a path to a destination, it runs an appropriate path-finding
algorithm on the topology information it maintains.
Examples of table-driven routing protocols are:
Destination Sequenced Distance Vector routing (DSDV)
Cluster-head Gateway Switch routing (CGSR)
Wireless Routing Protocol (WRP)
• Based on the Bellman-Ford algorithm
• Each mobile node maintains a routing table
• In terms of number of hops to each destination

• Routing table updates are periodically transmitted

• Each entry in the table is marked by a sequence number
• Helps to distinguish stale routes from new ones, and thereby avoiding loops

• To minimize the routing updates, variable sized update packets are used
• Depending on the number of topological changes
Broken node distance is ∞
 DSDV- Table updates
The table updates are of two types: incremental updates and full dumps

Full dump
q Large packet that contains all routing information available at a node.
q IT require several Network Protocol Data Units (NPDUs) to be transferred if the routing table is
large.
q Full dump packets are transmitted infrequently if the node only experiences occasional movement.
q A full dump is done either when the local topology changes significantly or when an incremental
update requires more than a single NDPU
Incremental routing
q An incremental update requires a single network data packet unit
q Smaller packet contains only the information that has changed since the latest full dump was sent
out by the node.
q Incremental packets only consume a fraction of the network resources compared to a full dump.
Advantages
• The availability of routes to all destinations at all times implies that much less delay is involved in
the route setup process.
• The mechanism of incremental updates with sequence number tags makes the existing wired
network protocols adaptable to ad hoc wireless networks. Hence, an existing wired network
protocol can be applied to ad hoc wireless networks with many fewer modifications.
• The updates are propagated throughout the network in order to maintain an up-to-date view of
the network topology at all the nodes.

Disadvantages
• The updates due to broken links lead to a heavy control overhead during high mobility. Even a
small network with high mobility or a large network with low mobility can completely block the
available bandwidth. Hence, this protocol suffers from excessive control overhead that is
proportional to the number of nodes in the network and therefore is not scalable in ad hoc
wireless networks, which have limited bandwidth and whose topologies are highly dynamic.
• Another disadvantage of DSDV is that in order to obtain information about a particular destination
node, a node has to wait for a table update message initiated by the same destination node. This
delay could result in stale routing information at nodes.
 DSDV (Route Advertisements)

• Advertise to each neighbor own routing information

– Destination Address
– Metric = Number of Hops to Destination
– Destination Sequence Number
• Rules to set sequence number information
– On each advertisement increase own destination sequence number (use only even
numbers)
– If a node is no more reachable (timeout) increase sequence number of this node by 1
(odd sequence number) and set metric = 
 DSDV (Route Selection)

• Update information is compared to own routing table

– 1. Select route with higher destination sequence number
(This ensure to use always newest information from
destination)
– 2. Select the route with better metric when sequence
numbers are equal.
 • Cluster-head Gateway
Switch Routing (CGSR)

TOPIC 8
Cluster-head Gateway Switch Routing (CGSR)

• Cluster-head gateway switch routing (CGSR) –

a clustered multi-hop routing, heuristic
• MANET divided into clusters
– For each cluster, a cluster-head (CH) elected
• By a distributed CH selection algorithm
» It modifies DSDV by using a hierarchical CH to route traffic

– Gateway nodes are bridges connecting cluster heads

• Frequent changes of CHs affect the performance

Gateway Node

Cluster Head 7 1
0
Internal (non-
cluster) Node 9
8
Cluster Head Gateway Switch Routing (CGSR)
n CGSR scenario - routing from Node 1 to Node 12:
n Packet sent by Node 1 is first routed to its CH (2)
n The packet is routed from CH (2) to gateway (4) connecting to CH of
another cluster (5)
n Packet routed from gateway (4) to the next CH (5)
n …
n Packet routed from gateway (10) to CH of destination cluster (11)
n Packet routed to destination node (12)
6
12
5

11
10
4 7

1
9
8 Gateway Node
3
Cluster Head

Internal (non-
cluster) Node
Advantages and Disadvantages

• CGSR is a hierarchical routing scheme which enables partial coordination between

nodes by electing cluster-heads. Hence, better bandwidth utilization is possible.
• It is easy to implement priority scheduling schemes with token scheduling and
gateway code scheduling.
The main disadvantages of CGSR are
• increase in path length and instability in the system at high mobility when the rate of
change of cluster-heads is high. In order to avoid gateway conflicts, more resources
(such as additional interfaces) are required.
• The power consumption at the cluster-head node is also a matter of concern because
the battery-draining rate at the cluster-head is higher than that at a normal node.
This could lead to frequent changes in the cluster-head, which may result in multiple
path breaks.
 • Dynamic Source
Routing (DSR)

TOPIC 9
• Source-initiated on-demand routing - the 2nd category (“family”) of routing protocols
• Unlike the table-driven routing protocols, on-demand routing protocols execute
the path-finding process and exchange routing information only when a path is
required by a node to communicate with a destination.

• This family of protocols includes:

1) Ad hoc On-Demand Distance Vector (AODV)
2) Dynamic Source Routing (DSR)
3) Temporary Ordered Routing Algorithm (TORA)
4) Associativity Based Routing (ABR)
5) Signal Stability Routing (SSR)
 • Routing only when needed
• Source floods the network with a route
0 request packet when a route is required to
query(0)
reply(0) a destination
1 query(0) • Flood is propagated outwards from the
source
query(0)
3 • Pure flooding = every node transmits the
reply(0) request only once
query(0)
2
query(0) • Destination replies to request
• Reply uses reversed path of route request
4
query(0) • sets up the forward path
reply(0) query(0)
5 • Two key protocols: DSR and AODV
• Advantages:
¡ eliminate periodic updates
¡ adaptive to network dynamics
• Disadvantages:
¡ high flood-search overhead with
lmobility, distributed traffic
¡ high route acquisition latency
A SUMMARY OF DSR
Entirely on-demand, potentially zero control message overhead
Trivially loop-free with source routing
Conceptually supports unidirectional links as well as
bidirectional links

High packet delays/jitters associated with on-demand routing

Space overhead in packets and route caches
Promiscuous mode operations consume excessive amount of
power
• When a host has a packet to send, it first consults its route cache.
• If there is an unexpired route, then it will use it.

• Otherwise, a route discovery will be performed

• Route Discovery:
• Initiates by broadcasting a route request packet.
• Source node S floods Route Request (RREQ)
• Route request message contains
• Address of the destination,
• Source node's address and
• Unique identification number.
• Each node appends own identifier(Sequence number) when forwarding
RREQ Entries in the route cache are continually updated as new
routes are learned.
• Source Node broadcast RouteRequest packet
• Each Intermediate node do the following steps:
• If request received before  discard
• If node ID is listed in request  discard
• If Route to the destination is available send RouteReply to the source node with full
path
• Otherwise  append node ID and rebroadcast
• When destination is reached  return RouteReply with full path
• Intermediate nodes cache all paths they overhear
• Source node caches all paths received and choose Shortest Path
 S-B
S-B-E
S E
B
D
S-B S-B-C
S C
S-A-G-F
S-B-C F
S
A
G S-A-G
S-A

RouteRequest Dropped
 B-E-D E-D
S-B-E-D
S-B-E-D
E
S-B-E-D B
D
S-B-E-D
S C
S-A-G-F-D
S-A-G-F-D
F
F-D
S-A-G-F-D
A
S-A-G-F-D
A-G-F-D G
S-A-G-F-D G-F-D
• Triggered when a link breaks between two nodes along the path
from the Source to the destination
• Node who discover the break send a RouteError to inform the
source node about the broken link
• Source Node
• erase the route from the cache, and
• Use another cached routes, Or
• Request a new Route
 RouteError
E
RouteError B
D
S-B-E-D
S C
S-A-G-F-D
F

A
G
• Promiscuous mode, intermediate nodes learns about routes breaks
• During network partition, if the destination is in different partition a backoff algorithm is
used to prevent frequent RouteRequest broadcast
• Scalability - since the source need to add the IDs of all nodes
along the path to the destination which increase the overhead
in every data packet sent
• No Local repair of the broken link -When a link is broken
RouteError packets need to go all the way to the source to
inform it about the problem
• Intermediate node can use outdated routes stored in their cache
• Stale cache information could result to inconsistence during
route reconstruction
• Poor Performance as Mobility increases-As mobility increases
more links are broken hence more route reconstructions is
needed
• Uses a reactive approach which eliminates the need to periodically
flood the network with table updatemessages
• Route is established only when required
• Reduce control overhead
• Route maintenance mechanism does not locally repair a broken link
• Stale route cache information could result in inconsistencies during route
construction phase
• Connection set up delay is higher
• Performance degrades rapidly with increasing mobility
• Routing overhead is more & directly proportional to path length
• Each host maintains a route cache which contains all routes it has learnt.
• Source Routing:
• routes are denoted with complete information (each hop is registered)
• Two major parts:

• route discovery
• route maintenance
Dynamic Source Routing

§ The protocol consists of two major phases: Route

Discovery, Route Maintenance
§ When a mobile node has a packet to send to some
destination, it first consults its route cache to check whether
it has a route to that destination
§ If it is an un-expired route, it will use this route
§ If the node does not have 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 address
Dynamic Source Routing – cont. 1

§ Each node receiving the packet checks to see whether it

has a route to the destination. If it does not, it adds its
own address to the route record of the packet and
forwards it.
§ A route reply is generated when the request reaches
either the destination itself or an intermediate node that
contains in its route cache an un-expired route to that
destination.
§ If the node generating the route reply is the destination, it
places the the route record contained in the route request
into the route reply.
Dynamic Source Routing – cont.
Creation of Route Record in DSR
Hop1 Hop2 77 Hop3 Hop4

<1> 2 <1,2> <1,3,5,7>

5 <1,3,5>
Source 11 <1>
8 Destination
33 <1,3>
<1> <1,4,6>
6
44 <1,4>

(a) Building Record Route During Route Discovery

7
2
5
Source 1
8 Destination
3
<1,4,6> <1,4,6>
6
4
<1,4,6>

(b) Propagation of Route Reply with the Route Record

 message containing path information is sent back to the
source either by
• the destination, or
• intermediate nodes that have a route to the destination
• Reverse the order of the route record, and include it in Route Reply.
• Unicast, source routing

• Each node maintains a which records routes it has

learned and overheard over time
Route Discovery
B Initiator ID
A-B-D-G
A-B-D-G G Initiator seq#
A-B-D-G
A-B Target ID
A D A-B-D
Partial route

A
A-C-E

A E H A-B-C
A-C-E
Route Request (RREQ)
A-C-E
C A-C A-B-C
F Route Reply (RREP)
Route Discovery: at source A
A need to send to G

Lookup Cache for route A to G

Start Route no
Buffer Route
Discovery found?
packet
Protocol

Continue
yes
normal
wait

yes Write route in

processing
packet header

Route Packet
Discovery in
buffer?
Send
finished no packet to
don
next-hop
e
Route Discovery: At an intermediate node

Accept route <src,id> in

yes Discard
request recently
route
packet seen
request
requests list?

no
Host’s
address yes Discard
already in route
patrial request
route
Append no
myAddr to no myAdd
partial route
r=targ
et
yes
Store <src,id>
in list Send route
reply packet

Broadcast packet
done
 message containing path information is sent back to the
source either by
• the destination, or
• intermediate nodes that have a route to the destination
• Reverse the order of the route record, and include it in Route Reply.
• Unicast, source routing

• Each node maintains a which records routes it has

learned and overheard over time
• Route maintenance performed only while route is in use
• Error detection:
• Monitors the validity of existing routes by passively listening to data packets
transmitted at neighboring nodes
• Lower level acknowledgements

• When problem detected, send packet to original sender to

perform new route discovery
• Host detects the error and the host it was attempting;
 B
RERR
RERR G

D
G
A

Route Cache (A)

G: A, B, D, G H
G: A, C, E, H, G E
F: B, C, F

C
F
 • Ad hoc On–Demand
Distance Vector Routing
(AODV)

TOPIC 10
 AD HOC ON–DEMAND DISTANCE VECTOR ROUTING (AODV)

• Improvement on DSDV, - minimizes the number of broadcasts by creating routes on demand

basis i.e AODV, a route is established only when it is required by a source node for transmitting
data packets.

• In AODV, the source node and intermediate nodes store the next-hop information
corresponding to each flow for data packet transmission.

• Nodes that are not in a selected path do not maintain routing information or participate in
routing table exchanges
 AD HOC ON–DEMAND DISTANCE VECTOR ROUTING (AODV).
• The major difference between AODV and other on-demand routing protocol is that it uses a
destination sequence number ( DestSeqNum) to determine an up-to-date path to the
destination.

• Destination sequence numbers are used to ensure that routes are loop free and has the most
recent route information. A node updates its path information only if the DestSeqNum of the
current packet received is greater than the last DestSeqNum stored at the node.

• AODV utilizes routing tables to store routing information.

• The routing table stores: destination next-hop destination hop count life time
addr addr sequence
 AD HOC ON–DEMAND DISTANCE VECTOR ROUTING (AODV).

The AODV routing procedure

• If a node wants to send a packet to some destination. At first, it checks its routing table to
determine whether it has a current route to the destination or not.

=>If yes, it forwards the packet to next hop node of the route.

=>If no, it initiates a route discovery process

• A source node initiates a path discovery process to locate the other intermediate nodes (and
the destination), by broadcasting a Route Request (RREQ) packet to its neighbors
 AD HOC ON–DEMAND DISTANCE VECTOR ROUTING (AODV).

The Route discovery process:

• A source node initiates a path discovery process to locate the other intermediate nodes (and the destination), by
broadcasting a Route Request (RREQ) packet to its neighbors. Broadcasting is done via flooding.

• The neighbors in turn forward the request to their neighbors and so on until either an intermediate node with
valid (fresh enough) route or destination is located

• Each node maintains its own sequence number and broadcast ID (incremented with every RREQ the node
initiates)

• Broadcast ID and source IP address form a unique identifier for the RREQ.

• DestSeqNum indicates the freshness of the route that is accepted by the source.
 AD HOC ON–DEMAND DISTANCE VECTOR ROUTING (AODV).

RREQ packet format

• source identifier (SrcID),
Type Reserved Hop Count
• destination identifier (DestID),
Broadcast ID
• source sequence number (SrcSeqNum),
Destination IP Address(ID)
• destination sequence number (DestSeqNum),
Destination Sequence Number
• broadcast identifier (BcastID), Source IP Address (ID)
• time to live (TTL) field. Source Sequence Number
Time Stamp
• Source sends RREQ (which includes sequence number for the destination) along with
its own sequence number and broadcast ID

• The intermediate node reply to RREQ only if

sequence number of destination <= sequence number in the current RREQ

• When a node broadcasts a RREQ, a reverse path towards the source is created

• Route reply uses the reverse path when RREQ is forwarded

1 Node S broadcasts RREQ to its neighbors. B

RREQ{D, D’seq, S, S’seq, 0}

S A

C
2 Node A rebroadcasts RREQ to all its neighbors. 3. Since, node C known a route to D, Node C creates a RREP
packet and unicasts RREP to A. Set forward path in node C’s
routing table.
4. Node A creates a RREP packet and unicasts RREP to S.
Set forward path in node A’s routing table. B

A’s Routing table

S A dest nexthop hopcount
D C 2
RREP{D, D’seq, S, S’seq, 2} D

C’s Routing table

dest nexthop hopcount
D D 1
4. Set forward path in node S’s routing table.

A’s Routing table

dest nexthop hopcount B
D C 2

S A

S’s Routing table D

dest nexthop hopcount C

D A 3
C’s Routing table
dest nexthop hopcount
D D 1
Route maintenance in AODV (Path broken due to host mobility)

1. If intermediate nodes or the destination move.

The next hop links break.
Routing tables are updated for the link failures.
All active neighbors are informed by RouteError (REER) packet.

2. When a source node receives an RRER, it can reinitiate the route

discovery process.

3. It can be also dealt with by a local fix scheme.

 Illustration of route maintenance in AODV
• Assume link between C and D breaks.
• Node C invalidates route to D in route table.
• When a node cannot forward a packet towards a destination, it generates a RERR
message; increments sequence number for destination; includes this incremented
destination sequence number in the RERR message
• Node C creates REER packet and sends to its upstream neighbors. (Route Error)
• Node A sends RRER to S.
• When a source receives the RERR, it initiates a new route discovery process for the
destination using sequence number equal or greater than the destination sequence
number in RERR message
• Node S rediscovers route if still needed. B

RERR
S A
Periodic Hello messages are used to ensure the links exist RERR
A link failure occurs when no hello message are exchanged D
for a timeout interval (the time to live (TTL) field.)
Failure to receive MAC-level acknowledgement can also be C
interpreted as a link failure
 On-demand routing protocol – AODV (cont.)
• Advantage:
– The routes are established on demand and the destination
sequence number can find the latest route to the destination.
• Disadvantage:
– The intermediate nodes can lead to inconsistent routes if the
source sequence number is very old.
• The periodic beaconing leads to unnecessary bandwidth
consumption. (When a link breaks, which is determined by
observing the periodical beacons or through link-level
acknowledgments, the end nodes (i.e., source and destination
nodes) are notified. )