Section 19.2. Routing in Ad-Hoc Networks

19.2. Routing in Ad-Hoc Networks

The lack of a backbone infrastructure makes packet routing in ad-hoc networks a challenging task. A routing protocol should be able to automatically recover from any problem in a finite amount of time without human intervention. Conventional routing protocols are designed for nonmoving infrastructures and assume that routes are bidirectional, which is not always the case for ad-hoc networks. Identification of mobile terminals and correct routing of packets to and from each terminal while moving are certainly challenging.

Since the topology of an ad-hoc network is dynamic, reserving resources and sustaining QoS are difficult. In an ad-hoc medium, it may not be possible to communicate bidirectionally, so ad-hoc routing protocols should assume that links are unidirectional. The power of a wireless device is another important factor. The routing protocol also has to support node stand-by mode. Devices such as laptops are very limited in battery power; hence, the use of stand-by mode to save power is important.

19.2.1. Classification of Routing Protocols

Ad-hoc routing protocols can be classified into two broad categories:

1. Centralized versus distributed. In centralized routing protocols, the routing decision is made at a central node. In distributed routing protocols, the routing decision is made by all the network nodes. Routing protocols in most efficiently designed ad-hoc networks are distributed to increase the reliability of the network. In such cases, nodes can enter or leave the network easily, and each node can make routing decisions, using other collaborative nodes.

2. Static versus adaptive. In static routing protocols, a route of a source/destination pair does not change because of any traffic condition or link failure. In adaptive routing protocols, routes may change because of any congestion.

Whether a protocol is centralized, distributed, static, or adaptive, it can generally be categorized as either table driven or source initiated.

Table-Driven Routing Protocols

Table-driven , or proactive , routing protocols find routes to all possible destinations ahead of time. are needed. The routes are recorded in the nodes' routing tables and are updated within the predefined intervals. Proactive protocols are faster in decision making but need more time to converge to a steady state, causing problems if the topology of the network continually changes. However, maintaining routes can lead to a large overhead. Table-driven protocols require every node to maintain one or more tables to store updated routing information from every node to all other nodes. Nodes propagate updated tables all over the network such that the routing information in each table corresponds to topological changes in the network.

Source-Initiated Routing Protocols

Source-initiated , or reactive , routing protocols , are on-demand procedures and create routes only when requested to do so by source nodes. A route request initiates a route-discovery process in the network and is completed once a route is discovered . If it exists at the time of a request, a route is maintained by a route-maintenance procedure until either the destination node becomes irrelevant to the source or the route is no longer needed. On-demand protocols are more suitable for ad-hoc networks. In most cases, reactive protocols are desired. This means that the network reacts only when needed and does not broadcast information periodically. However, the control overhead of packets is smaller than for proactive protocols.