M.

KUMARASAMY COLLEGE OF ENGINEERING

Department of Electronics and Communication Engineering
Ad Hoc and Sensor Networks | 2018 Regulation

UNIT II – ROUTING PROTOCOLS

Syllabus Topics: Issues in designing a routing protocol – Routing protocols: Table driven – On-demand – Hybrid –
Hierarchical – Power aware – Routing protocols with efficient flooding mechanisms

PART – A (2 Mark Questions & Answers)

1. What are the issues in designing a routing protocol for ad hoc networks?
Key issues include: (1) Dynamic topology due to node mobility, (2) Limited bandwidth and energy, (3)
Absence of fixed infrastructure, (4) Security vulnerabilities, (5) Scalability with large number of nodes,
(6) Unidirectional links, and (7) Interference and hidden terminal problems.

2. Classify routing protocols in ad hoc networks.

Routing protocols in ad hoc networks are classified as: (1) Table-Driven (Proactive) – DSDV, OLSR,
WRP; (2) On-Demand (Reactive) – AODV, DSR, TORA; (3) Hybrid – ZRP; (4) Hierarchical – CGSR,
HSR; (5) Power-Aware routing protocols.

3. What is a Table-Driven (Proactive) Routing Protocol?

In table-driven routing, each node maintains up-to-date routing tables to all destinations in the network.
Routing information is periodically broadcast to keep tables consistent. Examples: DSDV
(Destination-Sequenced Distance-Vector) and OLSR (Optimized Link State Routing).

4. What is On-Demand (Reactive) Routing?

On-demand routing establishes routes only when needed. A route discovery process is initiated when a
source node wants to communicate with a destination. Routes are maintained only as long as they are
needed. Examples: AODV (Ad hoc On-demand Distance Vector) and DSR (Dynamic Source Routing).

5. Define DSDV (Destination-Sequenced Distance-Vector) protocol.

DSDV is a proactive routing protocol based on the Bellman-Ford algorithm. Each node maintains a
routing table with entries for every destination, including the destination address, next hop, metric (hop
count), and a sequence number assigned by the destination to distinguish stale routes from new ones.
Sequence numbers prevent routing loops.

6. What is AODV (Ad hoc On-Demand Distance Vector)?

AODV is a reactive routing protocol that discovers routes on demand using Route Request (RREQ) and
Route Reply (RREP) messages. It uses sequence numbers to ensure loop-freedom and freshness of
routes. Route Error (RERR) messages are used to notify about broken links. It does not maintain routes
to nodes that are not communicating.

7. What is DSR (Dynamic Source Routing)?

DSR is a reactive protocol where the complete path from source to destination is included in the packet
header (source routing). Two phases: Route Discovery (broadcasts RREQ) and Route Maintenance
(detects broken links and notifies source via Route Error). Routes are cached at each node for future
use.
8. What is the Zone Routing Protocol (ZRP)?
ZRP is a hybrid routing protocol that divides the network into zones based on a zone radius (in hops).
Within a zone, proactive routing (IARP – Intra-Zone Routing Protocol) is used. Between zones, reactive
routing (IERP – Inter-Zone Routing Protocol) is used. This reduces the overhead of pure proactive and
latency of pure reactive protocols.

9. What is OLSR (Optimized Link State Routing)?

OLSR is a proactive link-state routing protocol optimized for mobile ad hoc networks. It uses Multipoint
Relays (MPRs) to reduce the overhead of flooding. Only MPR nodes forward control messages,
reducing redundant retransmissions. Each node selects a set of MPRs from its one-hop neighbors that
cover all two-hop neighbors.

10. Define Multipoint Relay (MPR) in OLSR.

A Multipoint Relay (MPR) is a selected subset of a node's one-hop neighbors that collectively cover all
two-hop neighbors. Only MPR nodes retransmit broadcast messages, significantly reducing the number
of retransmissions compared to pure flooding. Every node selects its own MPR set independently.

11. What is TORA (Temporally Ordered Routing Algorithm)?

TORA is a highly adaptive, loop-free, distributed reactive routing protocol. It is based on the concept of
link reversal and creates a Directed Acyclic Graph (DAG) rooted at the destination. TORA uses three
phases: Route Creation, Route Maintenance, and Route Erasure. It is designed to minimize
communication overhead by localizing reactions to topological changes.

12. What are Power-Aware Routing Protocols?

Power-aware routing protocols consider the energy status of nodes when making routing decisions.
Goals include: (1) Minimizing total transmission power, (2) Maximizing network lifetime, (3) Minimizing
variance in node power levels. Examples: MTPR (Minimum Total Power Routing), MMBCR (Min-Max
Battery Cost Routing), and CMMBCR.

13. What is Hierarchical Routing in ad hoc networks?

Hierarchical routing organizes nodes into clusters. Each cluster has a Cluster Head (CH) that manages
intra-cluster communication and communicates with other cluster heads via gateways. This reduces
routing overhead by limiting full topology knowledge to cluster heads. Example: CGSR (Clusterhead
Gateway Switch Routing).

14. What is Flooding and its problems in ad hoc networks?

Flooding is a simple routing mechanism where every node retransmits a received packet to all
neighbors. Problems include: (1) Broadcast storm – massive redundant packets, (2) High energy
consumption, (3) Network congestion, and (4) Duplicate packets at destination. Efficient flooding
mechanisms like MPR (OLSR) and probabilistic forwarding are used to reduce this overhead.

15. Differentiate between Proactive and Reactive Routing Protocols.

Proactive protocols maintain routes to all nodes at all times (constant overhead, low latency). Reactive
protocols establish routes only on demand (no idle overhead, higher latency for first packet). Proactive
is better for stable, small networks; Reactive is better for large, highly mobile networks with sparse
communication.

PART – B (3 × 16 Mark Questions & Answers)

Q1. Explain Table-Driven Routing Protocols in Ad Hoc Networks with suitable examples. (16
Marks)

Introduction to Table-Driven (Proactive) Routing

Table-driven routing protocols maintain consistent, up-to-date routing information at every node at all
times. Each node stores one or more routing tables and propagates updates throughout the network
whenever a topology change occurs. This ensures routes are immediately available when needed,
eliminating route discovery delay. However, they consume bandwidth and energy continuously even
when no data is being transmitted.

1. DSDV – Destination-Sequenced Distance Vector

DSDV is based on the classical Bellman-Ford distance-vector algorithm, enhanced with sequence
numbers to eliminate routing loops and count-to-infinity problems.

Key Features:
• Each node maintains a routing table with: Destination, Next Hop, Metric (hop count), Sequence
Number, Install Time.
• Sequence numbers are even for valid routes and odd for broken routes; higher sequence number
always preferred.
• Two types of updates: Full dump (entire table, sent periodically) and Incremental update (only
changed entries, sent immediately).
• Settling time mechanism delays advertising a new route to prevent instability from rapid fluctuations.
• Guarantees loop-free routing at all times through monotonically increasing sequence numbers.
DSDV Routing Table Example:
Destination Next Hop Metric Seq. Number

Node A Node B 2 A-224

Node C Node C 1 C-312

Node D Node C 2 D-198

Node E Node B 3 E-406

Limitations of DSDV:
• High overhead in highly mobile networks due to frequent table updates.
• Slow convergence when topology changes rapidly.
• Not scalable to very large networks.

2. OLSR – Optimized Link State Routing

OLSR is a proactive link-state protocol optimized for MANETs. It uses Multipoint Relays (MPRs) to
efficiently flood topology information across the network.

Key Features:
• Each node selects a set of MPRs from its one-hop neighbors that cover all two-hop neighbors.
• Only MPR nodes retransmit TC (Topology Control) messages, drastically reducing flooding
overhead.
• HELLO messages are sent periodically to discover neighbors and signal MPR selection.
• TC messages broadcast MPR selector sets to build global topology at each node.
• Shortest path routes are computed using Dijkstra's algorithm on the topology database.
• Supports multicast and multiple interfaces.
OLSR Message Types:
 Message Purpose Interval

HELLO Neighbor discovery and MPR selection 2 seconds

TC (Topology Control) Advertise MPR selector set for global topology 5 seconds

MID (Multiple Interface Decl.) Announce multiple interfaces of a node 5 seconds

HNA (Host/Network Assoc.) Announce reachable external networks 5 seconds

3. WRP – Wireless Routing Protocol

WRP maintains routing information using four tables: Distance Table, Routing Table, Link Cost Table,
and Message Retransmission List (MRL). It uses Update Messages (UMs) to share routing information.
WRP eliminates the count-to-infinity problem by enforcing the path consistency condition, where a node
only uses a neighbor as a next hop if that neighbor's predecessor is itself. This prevents loops.

Comparison of Table-Driven Protocols:

Protocol Algorithm Loop-Free? Overhead Scalability

DSDV Bellman-Ford + Seq No. Yes Medium Moderate

OLSR Link State + MPR Yes Low (MPR) Good

WRP Path Consistency Yes High Low

Q2. Explain On-Demand Routing Protocols: AODV and DSR in detail with route discovery and
maintenance. (16 Marks)

Introduction to On-Demand (Reactive) Routing

On-demand routing protocols do not maintain routing tables continuously. Routes are discovered only
when a source node wishes to communicate with a destination. This eliminates the overhead of periodic
route updates, making it suitable for large, highly mobile networks with sporadic communication
patterns.

1. AODV – Ad hoc On-Demand Distance Vector

AODV combines features of DSR and DSDV. It uses on-demand route discovery like DSR but maintains
only next-hop routing (not full source routes). Sequence numbers ensure loop-freedom and freshness.

AODV Control Messages:

Message Direction Purpose

RREQ (Route Request) Source → Broadcast Initiates route discovery; flooded through network

RREP (Route Reply) Destination → Source (unicast) Provides a valid route back to source

RERR (Route Error) Intermediate node → Source Notifies about a broken link

RREP-ACK Neighbor → Sender of RREP Confirms bidirectional link for RREP

Route Discovery Process:

• Step 1: Source node S broadcasts a RREQ packet containing: Source ID, Destination ID, Source
Seq No., Dest Seq No., Broadcast ID, Hop Count.
• Step 2: Each intermediate node checks if it has a valid route (with higher/equal dest seq no.) to the
destination.
• Step 3: If yes, it unicasts a RREP back towards the source; if not, it rebroadcasts the RREQ after
incrementing hop count.
• Step 4: Duplicate RREQs (same source + broadcast ID) are discarded to prevent loops.
 • Step 5: Destination (or intermediate node with valid route) sends RREP back along the reverse
path.
• Step 6: Each node along the path sets up a forward route entry and reverse route entry with a
lifetime timer.
Route Maintenance:
• Each route entry has an expiry timer; unused routes are deleted after timeout.
• If a link breaks while transmitting, the node sends a RERR message upstream toward source.
• RERR lists all destinations now unreachable due to the broken link.
• Source may initiate a new RREQ upon receiving RERR if it still needs the route.
• Local repair: intermediate node may try to repair a broken route locally by issuing a new RREQ.
AODV Features Summary:
• Loop-free routing guaranteed by destination sequence numbers.
• Only active routes are maintained – saves memory and energy.
• Supports both unicast and multicast routing (MAODV extension).
• Scales better than proactive protocols in large, sparse networks.

2. DSR – Dynamic Source Routing

DSR uses source routing – the complete path (list of intermediate nodes) is embedded in every data
packet header. This eliminates the need for nodes to maintain up-to-date routing tables. DSR has two
main mechanisms: Route Discovery and Route Maintenance.

Route Discovery:
• Source S initiates a RREQ packet containing the source address, destination address, request ID,
and an initially empty Route Record.
• Each intermediate node appends its own address to the Route Record before rebroadcasting.
• Duplicate RREQs (same source + request ID) are discarded.
• When the RREQ reaches destination D (or a node with a cached route to D), a RREP is sent back.
• RREP carries the complete route (copied from RREQ's Route Record) back to source.
• Source stores the discovered route in its Route Cache and uses it for subsequent packets.
Route Maintenance:
• Each forwarding node is responsible for confirming delivery to the next hop (via link-layer ACK or
passive ACK).
• If a link failure is detected, a Route Error (RERR) packet is sent back to the source.
• Source removes the broken route from its cache and uses an alternate cached route or initiates new
Route Discovery.
• Salvaging: when a node detects a broken link, it may use its own cache to reroute the packet.
Route Caching:
Every node maintains a Route Cache of recently discovered routes. Routes overheard from other
packets (promiscuous mode) are also cached. This significantly reduces the number of Route Discovery
floods. However, stale cache entries can cause problems if routes are not invalidated promptly after link
failures.

AODV vs DSR Comparison:

Feature AODV DSR

Routing Info in Packet No (only next-hop) Yes (full source route)

Route Cache No Yes (aggressive caching)

Loop Freedom Sequence numbers Source routing (inherently loop-free)

 Overhead per Packet Low (only next hop) High (full path in header)

Route Maintenance RERR + local repair RERR + cache-based salvaging

Scalability Better for large nets Better for small/medium nets

Q3. Explain Hybrid Routing (ZRP), Hierarchical Routing, Power-Aware Routing, and Efficient
Flooding Mechanisms in Ad Hoc Networks. (16 Marks)

1. ZRP – Zone Routing Protocol (Hybrid)

ZRP is a hybrid protocol that combines the advantages of proactive and reactive protocols. It defines a
routing zone around each node based on a zone radius (in hops). Within the zone, proactive routing is
used for fast route lookup. Outside the zone, reactive route discovery is used.

ZRP Components:
Component Type Role

IARP (Intra-Zone Routing Protocol) Proactive Maintains routes within the routing zone

IERP (Inter-Zone Routing Protocol) Reactive Discovers routes to nodes outside the zone

BRP (Bordercast Resolution Protocol) Support Efficiently forwards IERP queries to zone borders

How ZRP Works:

• Each node maintains a routing zone of radius r hops (e.g., r = 2 means all nodes within 2 hops).
• Intra-zone routing: proactive protocol (IARP) maintains routes to all nodes within the zone.
• Inter-zone routing: when destination is outside the zone, IERP issues a query (like RREQ) to border
nodes.
• BRP optimizes inter-zone queries by directing them only to zone perimeter nodes (bordercasting).
• ZRP reduces overhead vs pure proactive and reduces latency vs pure reactive; performance
depends on zone radius r.

2. Hierarchical Routing
Hierarchical routing organizes nodes into a multi-level hierarchy (clusters). This reduces the routing
table size and control overhead for large networks.

CGSR – Clusterhead Gateway Switch Routing:

• Nodes are organized into clusters; each cluster has a Cluster Head (CH) elected using LCA (Lowest
ID Clustering Algorithm).
• Intra-cluster routing: members route through the Cluster Head.
• Inter-cluster routing: CHs communicate via gateway nodes (members of multiple clusters).
• Each node maintains a Cluster Member Table (CMT) and uses DSDV for actual packet forwarding.
• Limitation: Frequent CH changes in high-mobility scenarios cause excessive overhead.
HSR – Hierarchical State Routing:
• Multi-level clustering: nodes at level 1 form clusters, cluster heads form level-2 clusters, and so on.
• At each level, nodes only need topology information for their local cluster.
• Long-distance routing uses aggregated topology at higher levels, reducing table size.
• Highly scalable for very large networks.

3. Power-Aware Routing Protocols

Power-aware routing extends network lifetime by incorporating energy considerations into routing
decisions. Simply minimizing hop count can drain certain nodes quickly; power-aware protocols
distribute energy consumption more evenly.
 Objectives of Power-Aware Routing:
• Minimize total transmission power: Select routes that consume the least total energy.
• Maximize node lifetime: Avoid routing through nodes with low remaining battery.
• Minimize variance in battery levels: Balance energy drain across all nodes.
• Minimize maximum node cost: Protect the bottleneck node with least energy.
Key Protocols:
Protocol Strategy Metric Used

MTPR (Min Total Power Routing) Minimize sum of transmission powers on path Transmission power per link

MMBCR (Min-Max Battery Cost Routing)Maximize lifetime of weakest node on path Inverse of remaining battery

CMMBCR Hybrid: uses MTPR if all nodes > threshold, else MMBCR Combined energy metric

PARO (Power Aware Routing Opt.)Reduces transmission power using relay nodes Relay placement metric

4. Routing Protocols with Efficient Flooding Mechanisms

Pure flooding (every node rebroadcasts every packet) is simple but generates massive redundancy
(broadcast storm problem). Efficient flooding mechanisms reduce overhead while ensuring full
coverage.

Problems with Pure Flooding:

• Broadcast Storm: Exponential growth in retransmissions with network size.
• Duplicate Packets: Each node receives the same packet multiple times.
• Collisions: Simultaneous broadcasts cause packet collisions.
• Energy Waste: Nodes consume energy for redundant transmissions.
Efficient Flooding Techniques:
Technique Mechanism Advantage

MPR Flooding (OLSR) Only MPR-selected nodes rebroadcast Minimum retransmissions with full coverage

Probabilistic Flooding Node rebroadcasts with probability p Simple; reduces redundancy

Counter-Based Rebroadcast only if received count < threshold Adapts to local density

Distance-Based Rebroadcast only if additional coverage > d Geometry-aware reduction

Location-Based (Geo Flooding) Forward only toward destination region Directional, energy-efficient

Gossip Protocol Node forwards to random subset of neighbors Low overhead; eventual delivery

Summary – Routing Protocol Classification:

Type Examples Best For Main Advantage

Table-Driven DSDV, OLSR, WRP Small, stable networks No route discovery delay

On-Demand AODV, DSR, TORA Large, mobile networks Low idle overhead

Hybrid ZRP Medium-scale networks Balances overhead and latency

Hierarchical CGSR, HSR Very large networks Scalable routing

Power-Aware MTPR, MMBCR, CMMBCR Energy-constrained networks Maximizes network lifetime

— End of Unit II Question Bank —

M. Kumarasamy College of Engineering | Curriculum and Syllabus 2018 Regulation