Ad Hoc Routing

Posted by arlene

There is an increasing list of new ideas and protocols for routing in mobile ad hoc networks. The MANET working group in the IETF publishes all significant developments and discussions by the group online in its mailing list, which is the most comprehensive source of up-to-date information on research on ad hoc routing protocols. In addition to the representative protocols in the three broad categories of routing protocols described above, it is worthwhile to look at some of the other concepts that have been applied to routing in mobile ad hoc networks.

Geographic Position Aided Routing

The fundamental problems of routing in ad hoc networks arise due to the random movements of the nodes. Such movements make topological information stale, and hence, when an on-demand routing protocol needs to find the route, it often has to flood the entire network looking for the destination. One of the ways of reducing the wastage of bandwidth in transmitting route request packets to every node in the network is to confine the search using geographical location information. Geographical positioning systems (GPS) can detect the physical location of a terminal using universal satellite-transmitted wireless signals. In recent times, GPS have become smaller, more versatile, and more cost-effective. Hence, several protocols have been proposed that assume the presence of a GPS receiver in each node and utilize the location information in routing.

An alternative concept is proposed in the Location Aided Routing (LAR) protocol, which uses location information in on-demand routing to limit the spread of request packets for route discoveries. LAR uses information such as the last known location and speed of movements of a destination to determine a REQUEST ZONE, which is defined as a restricted area within which the REQUEST packets are forwarded in order to find the destination. Two different ways of defining REQUEST ZONES have been proposed. The idea is to allow route request packets to be forwarded by only those nodes that lie within the REQUEST ZONE, specified by the source. This limits the overhead of routing packets for route discovery, which would normally be flooded over the whole network.

A related protocol that uses spatial locality based on hop counts to confine the spread of request packets was proposed by Castaneda and Das. This protocol uses the concept that once an existing route is broken, a new route can be determined within a certain distance (measured in number of hops) from the old route. The protocol confines the spread of route request packets while searching for a new route to replace one that is freshly broken. For a new route discovery where no earlier routes were on record, the protocol still uses traditional flooding. However, this query localization technique for rediscovering routes still saves routing overhead.

Stability-Based Routing

A different approach to improve the performance of routing in mobile ad hoc networks is based on using routes that are selected on the basis of their stability. The Associativity-Based Routing (ABR) protocol maintains an association stability metric that measures the duration of time for which a link has been stable. While discovering a new route, the protocol selects paths that have a high aggregate-association stability. This is done with the idea that a long-lived link is likely to be stable for a longer interval than a link that has been relatively short-lived.

`Signal Stability-Based Routing (SSR) uses signal strengths to determine stable links. It allows the discrimination between “strong” and “weak” links when a route request packet is received by a node. The request packet is forwarded by the node if it has been received over a strong link. This allows the selection of routes that are expected to be stable for a longer time.

Multipath Routing

On-demand or reactive routing protocols suffer from the disadvantage that data packets cannot be transmitted until the route discovery is completed. This delay can be significant under heavy traffic conditions when the REQUEST or the REPLY packet may take a considerable amount of time in traversing its path. This characteristic, along with the fact that each route discovery process consumes additional bandwidth for the transmission of REQUEST and REPLY packets, motivates us to find ways to reduce the frequency of route discoveries in on-demand protocols. One way of doing that is to maintain multiple alternate routes between the same source-destination pair such that when the primary route breaks, the transmission of data packets can be switched over to the next available path in the memory. Under the assumption that multiple paths do not break at the same time, which is most often true if the paths are sufficiently disjoint, the source may delay a fresh route discovery if the alternate paths are usable. As a result, many routing protocols have been designed to maintain multiple paths or routes for each pair of source and destination nodes.

The Temporally Ordered Routing Algorithm (TORA) provides multiple alternate paths by maintaining a “destination oriented” directed acyclic graph from the source. The DSR protocol also has an option of maintaining multiple routes for each destination in the route cache, so that an alternate route can be used upon failure of the primary route. Two multipath extensions of DSR were proposed by Nasipuri, Castaneda, and Das that aggressively determine multiple disjoint paths for each destination. Here, two different schemes for selecting alternative routes were considered, both benefiting from reducing the frequency of route discoveries caused by link breakages. Several other multipath routing protocols that derive benefits using the same principle have also been proposed.

Preemptive Routing

A purely reactive routing protocol typically does not avoid a multihop communication from being interrupted before the route breaks due to a link failure. Most reactive routing protocols initiate a fresh route discovery when an ERROR packet is received at the source due to a link breakage. This introduces a pause in the communication until a new route is found. The goal of preemptive routing protocols is to avoid such pauses by triggering a route discovery and switching to a new (and, it is hoped, better) route before the existing route breaks. Such protocols can be viewed as a combination of proactive and reactive routing, where the route maintenance is performed proactively but the basic routing framework is reactive.

The crucial design issue in such protocols is to detect when to initiate a preemptive route discovery to find a “better” route. The protocol proposed by Goff and colleagues uses the technique of determining this by observing when the signal strength falls below a predetermined threshold. If the wireless channel is relatively static, then this correctly detects the initiation of link failure due to increasing distance between the two nodes in the link. However, multipath fading and shadowing effects might lead to false alarms while using this technique. Alternatively, using a time-to-live parameter was proposed by Nasipuri and colleagues. In this protocol, a preemptive route discovery is initiated when a route has been in use for a predetermined threshold of time. The preemption obviously makes the route discoveries more frequent than what would be observed in a purely reactive scheme. To keep the routing overhead low, the preemptive routing protocol presented by Nasipuri and colleagues proposes the use of query localization in the preemptive searches.

Possibly related posts: (automatically generated)
Ad Hoc Routing

• Communicating with Graphic Designers
• Hybrid Routing Protocols
• Routing in Ad Hoc Networks
• Providing Support for BOOTP Clients
• Dynamic graphics on your Web site is paramount, keep in mind some technical visual design
• Proactive Routing Protocols: Destination-Sequenced Distance-Vector Routing; Optimized Link-State Routing Protocol
• Communicating with Users
• OSPF (Open Shortest Path First)
• Distinguishing Between Subjective and Objective Issues: What Exactly Does a Picture Paint? (continue...)
• Developing a plan for Managing Inbound E-mail Part 2