Routing Challenges in Ad-Hoc Networks

Standard IP routing protocols (such as OSPF, IS-IS, or BGP) are engineered for wired networks characterized by static topologies, immense bandwidth, and reliable links. In these environments, the cost of routing overhead is negligible. In a Mobile Ad-Hoc Network (MANET), applying these legacy protocols would result in catastrophic failure.

MANETs are characterized by random node mobility, which causes radio links to break and reform continuously. If a Link-State protocol like OSPF were deployed, every single broken link would trigger a Link-State Advertisement (LSA) that must be flooded across the entire network to update the global topological map. The continuous movement of nodes would cause an endless tsunami of LSAs, instantly consuming 100% of the available, constrained wireless bandwidth just to maintain routing tables, leaving absolutely zero capacity for actual data payloads. Furthermore, the constant CPU cycling required to execute Dijkstra’s algorithm upon every update would drain the batteries of the mobile nodes in minutes.

To address this existential challenge, specialized MANET routing protocols were developed, categorized primarily into three families: Proactive (Table-Driven), Reactive (On-Demand), and Hybrid protocols. Each trades off latency, bandwidth overhead, and computational complexity.

1. Proactive (Table-Driven) Protocols

Proactive protocols attempt to maintain up-to-date routing information from every node to every other node in the network at all times. They operate under the philosophy of constant readiness: when an application needs to send a packet, the route must already exist in RAM, providing zero-latency transmission. The cost is the massive background signaling required to keep these tables accurate as the topology shifts.

Destination-Sequenced Distance-Vector (DSDV)

DSDV is the seminal proactive protocol, representing a direct adaptation of the classic Bellman-Ford algorithm specifically engineered to survive in MANETs.

The Counting to Infinity Problem

In classic Bellman-Ford (e.g., RIP), routers only know the distance (metric) and the next hop to a destination. If a link physically breaks, the nodes immediately adjacent to the break detect it and increment their metric to “infinity.” However, due to slow convergence, Node A might receive a stale update from Node C claiming a path to the broken destination still exists. Node A updates its table to point to C, and C points to A. They bounce packets back and forth, slowly incrementing the hop count infinitely, congesting the network in a “Routing Loop.”

Sequence Numbers: The DSDV Solution

DSDV definitively solves the Routing Loop problem by forcing strict temporal ordering. It mandates that every single route advertisement must be tagged with a Sequence Number. Crucially, only the destination node itself is permitted to generate and increment its own sequence number.

When a node receives a routing update, it obeys a rigid mathematical law: it must prefer the route possessing the highest (newest) sequence number, entirely disregarding the hop count. A route with 10 hops but a newer sequence number instantly overwrites a route with 2 hops but a stale sequence number.

When a node detects that a link to a neighbor has physically broken, it must invalidate the route. To do this without creating loops, the detecting node takes the last known sequence number for that destination, adds 1 (making it an odd number), sets the metric to infinity, and broadcasts the update. Because the sequence number is now technically “newer” than the previous even number, every node in the network that receives this update instantly accepts it, overwriting their stale tables and definitively severing the broken path globally without looping.

Pros & Cons: The advantage of DSDV is zero initial latency for data transmission. The massive disadvantage is that maintaining these tables requires periodic “Full Dump” broadcasts and frequent “Incremental” broadcasts. In highly mobile networks, the topology changes faster than these updates can propagate, resulting in the protocol consuming more bandwidth than it provides.

2. Reactive (On-Demand) Protocols

Reactive protocols abandon the concept of background readiness entirely. They operate under the philosophy of extreme conservation: routing tables are an unnecessary luxury. A route is only calculated at the exact millisecond a node actively has data to send to a specific, unknown destination.

Dynamic Source Routing (DSR)

DSR is a reactive protocol that utilizes “Source Routing,” a mechanism where the intermediate routers are entirely dumb; the sender possesses total control over the path.

Route Discovery

If Node S (Source) wishes to reach Node D (Destination), it creates a Route Request (RREQ) packet containing a unique request ID. Node S broadcasts this packet to its immediate neighbors. When an intermediate node receives the RREQ, it checks if it has seen the request ID before (to prevent broadcast storms). If it is new, the node appends its own IP address to a list inside the packet header and rebroadcasts it.

When the RREQ finally reaches Node D, the packet header contains the complete, explicit topological path it traversed (e.g., S -> A -> B -> C -> D). Node D reverses this list and sends a Route Reply (RREP) back to Node S.

Data Transmission and Heavy Overhead

When Node S receives the RREP, it caches the path. During data transmission, Node S must append this entire explicit path list into the IP header of every single data packet it sends. As Node A receives the packet, it looks at the header list, sees Node B is next, and forwards it.

Route Maintenance

If Node B moves out of range of Node C, the link breaks. Node B detects the failure when its MAC layer ACK fails. Node B generates a Route Error (RERR) packet and sends it back to Node S. Node S must then purge the broken route from its cache and initiate a completely new Route Discovery.

Pros & Cons: DSR drastically reduces background control traffic, preserving battery life when the network is idle. However, it introduces significant initial latency (delay) when setting up a new route. Furthermore, as the network scales and paths reach 10-20 hops, appending 20 IP addresses to every single data packet creates massive byte overhead, severely degrading actual throughput.

Ad-hoc On-Demand Distance Vector (AODV)

AODV represents an architectural evolution, combining the on-demand discovery mechanism of DSR with the hop-by-hop tracking and sequence numbers of DSDV. It is currently the foundation for many modern mesh networking standards, including Zigbee.

Hop-by-Hop Tracking (Eliminating Source Routing)

Unlike DSR, AODV completely rejects Source Routing. It refuses to append lists of IPs to packets. Instead, during the Route Discovery phase, as the RREQ propagates outward, each intermediate node dynamically creates a temporary “Reverse Pointer” in its local RAM, pointing back to the neighbor from which it received the first copy of the RREQ.

When the Destination node generates the RREP, the packet does not need a map; it simply follows the Reverse Pointers hop-by-hop back to the source. As the RREP travels backward, it leaves a trail of “Forward Pointers” in the RAM of the intermediate nodes, pointing toward the destination.

During data transmission, the source merely puts the Destination IP in the packet header. The intermediate nodes consult their Forward Pointers to route the packet blindly to the next hop. This ensures the packet header size remains constant and tiny, regardless of how large the network scales.

Sequence Numbers and Freshness

AODV utilizes Destination Sequence Numbers to guarantee loop freedom. Furthermore, intermediate nodes are permitted to reply to a RREQ if they have a cached route to the destination. However, they are only allowed to reply if their cached route’s sequence number is greater than or equal to the sequence number demanded in the RREQ, ensuring that stale cached routes are never injected into the network.

3. Hybrid Routing Protocols

Hybrid protocols attempt to fuse the zero-latency benefits of Proactive routing with the low-overhead benefits of Reactive routing by partitioning the network based on distance.

Zone Routing Protocol (ZRP)

ZRP divides the entire network into overlapping geographic or topological “Routing Zones.” A zone is not defined by physical distance, but by a strict hop-count radius centered around every individual node. If the radius is set to 2 hops, every node within 2 hops belongs to that central node’s zone.

Intra-Zone Routing (Proactive)

Within a node’s defined radius, ZRP utilizes a strict Proactive protocol (such as IARP, an adaptation of DSDV). Every node constantly exchanges updates with its immediate neighbors. Consequently, every node possesses a perfect, zero-latency routing map of its entire local zone. If a node needs to send data to a neighbor two blocks away, transmission is instantaneous.

Inter-Zone Routing (Reactive)

For communication with nodes outside the local zone, proactive updates would cause too much overhead. Therefore, ZRP utilizes a Reactive protocol (like IERP, similar to AODV). However, it vastly optimizes the Route Discovery process.

Instead of blindly broadcasting the RREQ to every single node in the network, ZRP utilizes “Bordercasting.” The source node unicasts the RREQ explicitly to its Peripheral Nodes—the nodes residing on the absolute outermost edge of its zone (exactly 2 hops away). These peripheral nodes then check their own proactive zones. If the destination is not found, they bordercast to their peripheral nodes. This targeted querying drastically reduces the flood of control packets across the global network backbone, making ZRP highly scalable.

Multicast Routing in MANETs

Standard routing is Unicast (Point-to-Point). Multicast is Point-to-Multipoint, delivering the identical data stream to a specific, dynamic group of receiving nodes simultaneously. In wired networks, this is achieved by building a rigid Spanning Tree (like PIM-SM). In a MANET, rigid trees shatter instantly as nodes move.

On-Demand Multicast Routing Protocol (ODMRP)

ODMRP is a reactive multicast protocol engineered specifically to survive hyper-dynamic topologies. It Abandons the concept of a fragile Multicast Tree entirely, instead opting to build an overlapping, highly redundant “Forwarding Mesh.”

Mechanism: Building the Mesh

When a multicast source has data to send, it periodically floods a Join Query across the network. Nodes that are subscribed to the multicast group and wish to receive the data reply by broadcasting a Join Reply.

As the Join Reply travels back toward the source, every intermediate node that forwards the reply mathematically flags itself as a member of the “Forwarding Group.” Because the replies take multiple paths back to the source, the Forwarding Group naturally forms a thick, overlapping web of nodes connecting the source to the receivers.

Redundancy over Efficiency

Instead of forcing data down a single, optimized branch of a tree, ODMRP requires all nodes in the Forwarding Group to use localized flooding to propagate the multicast data. While this consumes more bandwidth than a perfect tree, the architectural benefit is monumental.

Because it uses a mesh providing multiple redundant paths, ODMRP is immensely robust against link breakages. In a highly mobile MANET, if a critical branch node on a tree moves out of range, the entire downstream sub-tree is violently disconnected and data is lost until a new tree is calculated. In ODMRP, if a node in the mesh moves, the data simply propagates through the remaining, overlapping paths in the Forwarding Group. The data still reaches the destination seamlessly without requiring immediate, panicked route recalculation, guaranteeing reliable delivery in hostile environments.