Ad Hoc Routing Protocols

May 29 • General • 1759 Views • No Comments on Ad Hoc Routing Protocols

Ad hoc Routing Protocols are classified as follows:

Ad hoc Routing Protocol

Ad hoc Routing Protocols

A). TABLE-DRIVEN ROUTING PROTOCOLS:

This Ad hoc Routing Protocols maintain the global topology information in the form of tables at every node. These tables are updated frequently in order to maintain consistent and accurate network state information.

1.Destination Sequenced Distance-Vector Routing Protocol (DSDV):-

DSDV is an enhanced version of the distributed Bellman-Ford algorithm where each node maintains a table that contains the shortest distance and the first node on the shortest path to every other node in the network.

As it is a table-driven routing protocol (Ad hoc Routing Protocols), routes to all destinations are available at every node at all times.At regular intervals the tables are exchanged between neighbors  to keep an up-to-date view of the network topology. The table updates are of two types: i). An incremental update takes a single network data packet unit (ii). a full dump may take multiple network data packets units. Upon receiving an updated table, a node either updates its tables based on the received information or holds it for some time to select the best metric received from multiple version of same update table from different neighboring nodes.

2. Wireless Routing Protocol (WRP):-

WRP, similar to DSDV, inherits the properties of the distributed Bellman-Ford algorithm. It employs a unique method of maintaining information regarding the shortest distance to every destination node in the network and the penultimate hop node on the path to every destination node, to counter the count-to-infinity problem and to enable faster convergence,.

Consider the example, where source of route is node 1 and the destination is node 15. The route to any destination node is readily available at the source node. Let the route from node 1 to node 15 has the next node as node 2. The predecessor node of 15 corresponding to this route is node 12. The predecessor information helps WRP to converge quickly during link breaks. When a node detects a link break, it sends an update message to its neighbors with the link cost of the broken link set to ∞. After receiving the update message, all affected nodes update their minimum distances to the corresponding nodes. The node that initiated the update message then finds an alternative route, if available from its DT. This new route computed will not contain the broken link. A neighbor node, after receiving the update message, updates its routing table only if the new path is better than the previously existing path.

3. Cluster-Head Gateway Switch Routing Protocol (CGSR):-

CGSR uses a hierarchical network topology. It organizes nodes into clusters, with coordination among the members of each cluster entrusted to a special node named cluster-head. Communication between two clusters takes place through the common member nodes that are member of both the clusters. These nodes which are member of more than one cluster are called gateways.

The performance of routing is influenced by token scheduling and code scheduling that are handled at cluster-heads and gateways respectively. The cluster (hierarchical) routing protocol is used here. According to this protocol, when a node with packets to be transmitted to destination gets the token from its cluster-head, it obtains the destination cluster-head and the next hop node from the cluster member table and the routing table respectively. CGSR improves the routing performance by routing packets through the cluster-heads and gateways.

B).ON-DEMAND ROUTING PROTOCOLS:

This is one of the Ad hoc Routing Protocols, main idea in on-demand routing is to find and maintain only needed routes. The advantage is it avoids incurring the cost of maintaining routes that are not used. This approach is attractive when the network traffic is sporadic and directed mostly toward a small subset of nodes.

1.Dynamic Source Routing (DSR):-

DSR is characterized by the use of source routing i.e., sender knows the complete hop-by-hop route to the destination and routes are stored in a route cache.

When a node in ad hoc network attempts to send a data packet to a destination for which it does not already know the route, it uses a route discovery process to dynamically determine such a route. Route discovery works by flooding the network with route request/query packets. Each node rebroadcast the request unless it is destination or it has route to destination in its route cache. Such a node replies to the request with route reply packet that is routed back to the original source. If any link on a source route is broken, a route error packet is generated, which erases all entries in the route caches.

DSR makes aggressive use of source routing and route caching. With source routing, complete path information is available and routing loops can be easily detected and eliminated.

2. Ad Hoc On-demand Distance Vector (AODV):-

AODV also discovers routes on an “as needed” basis. It uses traditional routing tables, one entry per destination. Without source routing, it relies on routing table entries to propagate RREP back to the source and to route data packets to the destination. It uses destination sequence number to prevent routing loops and to determine the freshness of routing information. It is conservative in dealing with stale routes.

3. Temporally Ordered Routing Algorithm (TORA):-

TORA’s route discovery procedure computes multiple loop-free routes to the destination which constitute a destination-oriented directed acyclic graph (DAG). It employs a route maintenance procedure requiring strong inter-nodal coordination based on a link reversal concept. The basic idea behind link reversal algorithm is whenever a link failure at a node causes the node to lose all downstream links to reach the destination, a series of link reversals starting at that node can revert the DAG back to a destination-oriented state.

4. Location-Aided Routing (LAR):-

LAR utilizes the location information for improving the efficiency of routing by reducing the control overhead. It assumes the availability of the global positioning system (GPS) for obtaining the geographical position information necessary for routing. It designates two geographical regions, namely, ExpectedZone and RequestZone. The ExpectedZone is the region in which the destination node is expected to be present, given information regarding its location n I n the past and its mobility information. The RequestZone is the region within which the path-finding control packets are permitted to be propagated. LAR uses flooding but it is restricted to small geographical region.

5. Associativity-Based Routing (ABR):-

ABR protocol is a distributed Ad hoc Routing Protocols that selects routes based on the stability of the wireless links. It is a beacon-based, on-demand routing protocol (Ad hoc Routing Protocols). Each node maintains the count of its neighbors’ beacons and classifies each link as stable or unstable based on the beacon count corresponding to the neighbor node concerned.

 A source node floods RouteRequest packets throughout the network if a route is not available in its route cache. This packet carries the path it has traversed and the beacon count for the corresponding node in the path. When the 1st RouteRequest reaches the destination it waits for T time period to receive multiple RouteRequest through different paths. After T time period, destination selects the path that has the maximum proportion of stable links. If path has same proportion of stable links, the shorter of them is selected. If more than one shortest path is available, then a random path among them is selected as the path between source and destination.

6. Signal Stability-Based Adaptive Routing Protocol (SSA):-

SSA uses signal stability as the prime factor for finding stable routes. This Ad hoc Routing Protocols is beacon-based, in which the signal strength of the beacon is measured for determining link stability. This protocol consists of two parts: forwarding protocol (FP) and dynamic routing protocol (DRP). DRP maintains the routing table by interacting with the DRP processes on other hosts. FP performs the actual routing to forward a packet on its way to the destination.

 Each node maintains a table called the signal stability table (SST), which is based on the signal strengths of its neighbors’ beacons. If the attempts of forwarding a RouteRequest over the stable links fail to obtain any path to destination, the protocol floods the RouteRequest throughout the network without considering the stability of links as the forwarding criterion. The destination selects the 1st RouteRequest packet received over strong links. The destination initiates a RouteReply packet to notify the selected route to the source.

 

Tell us Your Queries, Suggestions and Feedback

Your email address will not be published.

« »