Routing in Ad Hoc Networks of Mobile Hosts
MECH 590: Directed Studies with Dr. Gerard McLean
B. Cameron Lesiuk
December 2, 1998
Department of Mechanical Engineering
University of Victoria, Victoria, BC, Canada
Preamble:
This report was written in partial fulfillment of a MECH 590 Directed Studies course with my supervisor, Dr. Ged McLean. This report was written in Frame Builder and later translated into HTML form.
Click here to return to my home page.
This paper presents an overview of ad hoc routing principles and how these differ from conventional routing. Four proposed ad hoc routing protocols, DSDV, TORA, DSR, and Virtual Subnets, are presented and commented on. Finally, several other ad hoc routing protocols are briefly introduced, highlighting their novel concepts or optimizations over the four main routing protocols presented earlier in the paper.
Figure 1.1: Simple network with three nodes.
Figure 1.2: Network with eight nodes connected by four separate links.
Figure 1.3: Ad hoc network of three wireless mobile hosts.
Figure 1.4: Ad hoc network with four wireless nodes.
Figure 1.5: Ad hoc network with a one-way link.
Figure 2.1: An example of the routing procedure in DSDV.
Figure 2.2: A node receiving three update packets.
Figure 3.1: Generation of an ordered graph in TORA.
Figure 3.2: TORA protocol reaction to node mobility.
Figure 4.1: A packet being source routed from node 9 to node 5.
Figure 5.1: Physical and virtual subnets in an ad hoc network.
Figure 6.1: Multi-point relay versus conventional broadcasting.
This report investigates routing protocols for ad hoc networks of mobile hosts. There are numerous different routing protocols presently proposed for ad hoc networks. Unfortunately, few have been extensively simulated, let alone implemented in an actual ad hoc environment. Consequently, independent commentary is rare for many of the protocols discussed in this paper.
This report focuses on a few key protocols which illustrate the underlying philosophies of ad hoc protocols. Favor is given to mature protocols which have been independently implemented and tested. Subsequently, several other ad hoc routing protocols are briefly introduced, highlighting their novel concepts or optimizations over the main routing protocols presented.
A quantitative analysis and comparison of protocol performance is not provided in this paper. Each protocol performs differently when coupled with different MAC and physical layer technologies. Consequently, an analysis and comparison of protocol performance is only valid within the context of a single implementation, and different protocols may be optimal for different implementations. Furthermore, few quantitative performance comparisons have been reported in the literature, and the ones that have been reported are far from comprehensive.
The remainder of this introduction presents the background required to understand ad hoc routing protocols. Section 1.1 provides relevant background and terminology used in this report. Section 1.2 discusses the attributes and unique characteristics of ad hoc networks.
A network is a collection of two or more computing devices connected by a communication medium. Figure 1.1 shows a simple network with three computing devices. When a computing device wishes to send information to another device, it may do so by transmitting the information along a shared communication medium.
In this paper, any computing device actively participating in a network is called a node. Nodes are connected by a communication medium or link. Nodes exchange information over links in discrete blocks called packets.
In Figure 1.1, any node can communicate with any other node along the single shared link. In this case, no special steps are needed for any two nodes in the network to exchange information. If, however, nodes in a network do not share a common link, this no longer holds true. Figure 1.2 shows a network where different nodes share different links.
Figure 1.2: Network with eight nodes connected by four separate links.
For example, in Figure 1.2, for node 1 to send a packet to node 8, the packet must first be sent to node 3. Node 3 must subsequently be willing and able to forward the packet on to node 8. The links and nodes a packet traverses along its journey from source to destination is called the packet’s path.
Whenever a packet is transmitted from one node to another, it is said to have made a hop. In the above example, a packet sent from node 1 to node 3 requires one hop, whereas a packet sent from node 1 to node 8 requires two hops (one hop from node 1 to node 3, and a second hop from node 3 to node 8).
In the above example, the various nodes along the packet’s path from node 1 to node 8 must cooperate in order to make the information exchange successful. This cooperation process is called routing.
Routing in conventional network technologies, such as the Internet Protocol (IP) [1] or ATM [8], is simplified by designing the link topology in a predictable (usually hierarchical) manner. The topology of a network is the way in which nodes are connected to each other. In these networks, the routing protocol can take advantage of the topology structure, resulting in a simplified routing algorithm.
Conventional networks tend to change infrequently, relaxing the burden on the routing protocol to return to a stable state in response to a topology change. The process of returning to a stable state after a topology change is called convergence. The time required for a routing protocol to converge is called its convergence time. As will be seen in later sections, many routing protocols (in both ad hoc and conventional networks) can form temporary routing loops when the topology changes. These routing loops may persist until the routing protocol converges.
An ad hoc network is a collection of mobile nodes forming a temporary network without the aid of any centralized administration or standard support services regularly available on conventional networks. In this paper, it is assumed the mobile hosts use wireless RF transceivers as their network interface, although many of the same principles will apply to infra-red and wire based networks. Some form of routing protocol is necessary in these ad hoc networks since two hosts wishing to exchange packets may not be able to communicate directly.
For example, Figure 1.3 illustrates an ad hoc network with three wireless mobile hosts. Node 3 is not within the range of node 1’s wireless transmitter (indicated by the circle around node 1) and vice versa. If node 1 and node 3 wish to exchange packets, they must enlist the services of node 2 to forward packets for them, since node 2 is within the range overlap between node 1 and node 3.
The situation in Figure 1.3 becomes more complicated with the addition of more nodes. The addition of just one node, as illustrated in Figure 1.4, results in multiple paths existing between nodes 1 and 3; packets may travel the path 1 - 2 - 3, 1 - 4 - 3, or even 1 - 4 - 2 - 3. An ad hoc routing protocol must be able to decide on a single "best" path between any two nodes.
Another situation unique to wireless networks is illustrated in Figure 1.5. In this example, node 1 has a large enough range to transmit packets directly to node 3. However, node 3 has a much smaller range and must enlist the help of node 2 in order to return packets to node 1. This makes the link between node 1 and node 3 appear as a one-way or unidirectional link. Most conventional routing protocols require bidirectional links.
Another problem with wireless network interfaces is they typically operate at significantly slower bit rates than their wire-based counterparts. Frequent flooding of packets throughout the network, a mechanism many protocols require, can consume significant portions of the available network bandwidth. Ad hoc routing protocols must minimize bandwidth overhead at the same time as they enable proper routing to take place.
Finally, ad hoc networks must deal with frequent changes in topology. By their very nature, mobile nodes tend to "wander around", changing their network location and link status on a regular basis. Furthermore, new nodes may unexpectedly join the network or existing nodes may leave or be turned off. Ad hoc routing protocols must minimize the time required to converge after these topology changes. A low convergence time is more critical in ad hoc networks because temporary routing loops can result in packets being transmitted in circles, further consuming valuable bandwidth.
For the purposes of this report, an ad hoc routing protocol is considered to fill the space between two network extremes. At one extreme, the network topology is changing so rapidly the only feasible routing mechanism is for every packet to be flooded throughout the network. At the other extreme, the network topology is sufficiently permanent and static as to permit the use of conventional routing mechanisms such as those employed in the Internet. Ad hoc networks are networks which lack the support structure and permanency of traditional networks, yet change sufficiently slowly as to permit the use of a routing protocol to optimize transmission bandwidth.
Destination-Sequenced Distance-Vector Routing (DSDV) [16] is an adaption of a conventional routing protocol to ad hoc networks. DSDV is based on the Routing Information Protocol (RIP) [9], used in parts of the Internet. Consequently, DSDV only makes use of bidirectional links. DSDV is one of the earlier ad hoc routing protocols developed.
In DSDV, packets are routed between nodes of an ad hoc network using routing tables stored at each node. Each routing table, at each node, contains a list of the addresses of every other node in the network. Along with each node’s address, the table contains the address of the next hop for a packet to take in order to reach the node.
Figure 2.1 illustrates the routing procedure in DSDV. In this example, a packet is being sent from node 1 to node 3 (node 3 is not shown). From node 1, the next hop for the packet is node 4 (Figure 2.1 a). When node 4 receives the packet, it looks up the destination address (node 3) in its routing table (Figure 2.1 b). Node 4 then transmits the packet to the next hop as specified in the table, in this case node 5 (Figure 2.1 c). This procedure is repeated as required until the packet finally reaches its destination.
The bulk of the DSDV protocol does not involve routing at all. Rather, the crux of DSDV is the generation and maintenance of the routing tables. Every time the network topology changes, the routing table in every node needs to be updated. As one might expect, this is no trivial task. The situation is further complicated by the fact that, when routing tables are out of sync (i.e. the routing protocol has not converged), routing loops may form.
To facilitate routing table maintenance, several additional pieces of information are stored in the routing tables. In addition to the destination address and next hop address, routing tables maintain the route metric and the route sequence number.
Periodically, or immediately when network topology changes are detected, each node will broadcast a routing table update packet. The update packet starts out with a metric of one. This signifies to each receiving neighbor they are one hop away from the node. The neighbors will increment this metric (in this case, to two) and then retransmit the update packet. This process repeats itself until every node in the network has received a copy of the update packet with a corresponding metric. If a node receives duplicate update packets, the node will only pay attention to the update packet with the smallest metric and ignore the rest.
To distinguish stale update packets from valid ones, each update packet is tagged by the original node with a sequence number. The sequence number is a monotonically increasing number which uniquely identifies each update packet from a given node. Consequently, if a node receives an update packet from another node, the sequence number must be equal to or greater than the sequence number already in the routing table; otherwise the update packet is stale and ignored. If the sequence number matches the sequence number in the routing table, then the metric is compared and updated as previously discussed.
Each time an update packet is forwarded, the packet not only contains the address of the eventual destination, but it also contains the address of the transmitting node. The address of the transmitting node is entered into the routing table as the next hop (unless the packet is ignored, of course). Figure 2.2 illustrates how a node processes an update packet under varying conditions. Note update packets with higher sequence numbers are always entered into the routing table, regardless of whether they have a higher metric or not.
Each node must periodically transmit its entire routing table to its neighbors using update packets. The neighbors will update their tables based on this information, if required. Likewise each node will listen to its neighbors update packets and update its own routing table.
Mobile nodes cause broken links as they move from place to place. The broken link may be detected by the communication hardware, or it may be inferred if no broadcasts have been received for a while from a former neighbor. A broken link is described as having a metric of infinity. Since this qualifies as a substantial route change, the detecting node will broadcast an update message for the lost destination. This update message will have a new sequence number and a metric of infinity. This will essentially cause the routing table entries for the lost node to be flushed from the network. Routes to the lost node will be established again when the lost node sends out its next broadcast.
To avoid nodes and their neighbors generating conflicting sequence numbers when the topology changes, nodes only generate even sequence numbers for themselves, and neighbors responding to link changes only generate odd sequence numbers.
DSDV contains substantially more procedures for handling different network layer addresses, dealing with non-mobile base stations, and damping fluctuations caused by topology changes. However, the details of these procedures are deemed beyond the scope of this report. For more information, refer to [16].
DSDV is based on a conventional routing protocol, RIP, adapted for use in ad hoc networks. Routing is achieved by using routing tables maintained by each node. The bulk of the complexity in DSDV is in generating and maintaining these routing tables.
DSDV requires nodes to periodically transmit routing table update packets, regardless of network traffic. These update packets are broadcast throughout the network so every node in the network knows how to reach every other node. As the number of nodes in the network grows , the size of the routing tables and the bandwidth required to update them also grows. This overhead is DSDV’s main weakness, as Broch et al. [5] found in their simulations of 50-node networks. Furthermore, whenever the topology changes, DSDV is unstable until update packets propagate throughout the network. Broch found DSDV to have the most trouble (of four protocols analyzed) in dealing with high rates of node mobility.
Temporally-Ordered Routing Algorithm (TORA) [15] is a distributed routing protocol based on a "link reversal" algorithm. It is designed to discover routes on demand, provide multiple routes to a destination, establish routes quickly, and minimize communication overhead by localizing the reaction to topological changes when possible. Route optimality (shortest-path routing) is considered of secondary importance, and longer routes are often used to avoid the overhead of discovering newer routes. It is also not necessary (nor desirable) to maintain routes between every source/destination pair at all times.
The actions taken by TORA can be described in terms of water flowing downhill towards a destination node through a network of tubes that model the routing state of the network. The tubes represent links between nodes in the network, the junctions of the tubes represent the nodes, and the water in the tubes represents the packets flowing towards the destination. Each node has a height with respect to the destination that is computed by the routing protocol. If a tube between two nodes becomes blocked such that water can no longer flow through it, the height of the nodes are set to a height greater than that of any neighboring nodes, such that water will now flow back out of the blocked tube and find an alternate path to the destination.
At each node in the network, a logically separate copy of TORA is run for each destination. When a node needs a route to a particular destination, it broadcasts a route query packet containing the address of the destination. This packet propagates through the network until it reaches either the destination, or an intermediate node having a route to the destination. The recipient of the query packet then broadcasts an update packet listing its height with respect to the destination (if the recipient is the destination, this height is 0). As this packet propagates back through the network, each node that receives the update sets its height to a value greater than the height of the neighbor from which the update was received. This has the effect of creating a series of directed links from the original sender of the query to the node that initially generated the update. An example of this process is illustrated in Figure 3.1.
When a node discovers that a route to a destination is no longer valid, it adjusts its height so that it is a local maximum with respect to its neighbors and transmits an update packet. This process is illustrated in Figure 3.2.
When a node detects a network partition, where a part of the network is physically separated from the destination, the node generates a clear packet that resets the routing state and removes invalid routes from the network.
TORA sits as a routing layer above another, network level protocol called the Internet MANET Encapsulation Protocol (IMEP) [6]. IMEP is designed to support the operation of many routing algorithms, network control protocols or other upper layer protocols intended for use in mobile ad hoc networks. The protocol incorporates mechanisms for supporting link status and neighbor connectivity sensing, control packet aggregation and encapsulation, one-hop neighbor broadcast reliability, multipoint relaying, network-layer address resolution, and provides hooks for interrouter authentication procedures.
TORA is one of the largest and most complicated protocols presented in this paper. In terms of memory requirements, each node must maintain a structure describing the node’s height as well as the status of all connected links per connection supported by the network [15]. In terms of CPU and bandwidth requirements, each node must be in constant coordination with neighboring nodes in order to detect topology changes and converge. As was found with DSDV, routing loops can occur while the network is reacting to a change in topology [5] [15].
TORA is designed to carry IP traffic over wireless links in an ad hoc network. Based on simulation results [5] [14], it is best suited to large, densely packed arrays of nodes with very low node mobility (although Broch [5] calls into question the validity of Park and Corson’s simulations in [14] supporting this claim). Of the two papers reporting simulation results, only the one by Broch et al. [5] actually simulates node mobility. Broch found TORA to be encumbered by its layering on top of IMEP, and found IMEP caused considerable congestion when TORA was trying to converge in response to node mobility. This resulted in TORA requiring between one to two orders of magnitude more routing overhead than other ad hoc routing protocols investigated by Broch in [5].
Dynamic Source Routing (DSR) [12] [2] is designed to allow nodes to dynamically discover a source route across multiple network hops to any destination in the ad hoc network. When using source routing, each packet to be routed carries in its header the complete, ordered list of nodes through which the packet must pass. A key advantage of source routing is that intermediate hops do not need to maintain routing information in order to route the packets they receive, since the packets themselves already contain all necessary routing information. An example of a packet moving through an ad hoc network with source routing is illustrated in Figure 4.1.
Figure 4.1: A packet being source routed from node 9 to node 5.
Unlike every other protocol presented in this paper, DSR does not require the periodic transmission of router advertisements or link status packets, reducing the overhead of DSR. In addition, DSR has been designed to compute correct routes in the presence of unidirectional links.
Source routing is a routing technique in which the sender of a packet determines the complete sequence of nodes through which to forward the packet. The sender explicitly lists this path in the packet’s header, identifying each forwarding hop by the address of the next node to which to transmit the packet on its way to the destination host.
DSR is broken down into three functional components: routing, route discovery and route maintenance. Routing has already been described and is relatively trivial. Route discovery is the mechanism by which a node wishing to send a packet to a destination obtains a path to the destination. Route maintenance is the mechanism by which a node detects a break in its source route and obtains a corrected route.
To perform route discovery, the source node broadcasts a route request packet with a recorded source route listing only itself. Each node that hears the route request forwards the request (if appropriate), adding its own address to the recorded source route in the packet. The route request packet propagates hop-by-hop outward from the source node until either the destination node is found or until another node is found that can supply a route to the target.
Nodes forward route requests if they are not the destination node and they are not already listed as a hop in the route. In addition, each node maintains a cache of recently received route requests and does not propagate any copies of a route request packet after the first.
All source routes learned by a node are kept (memory permitting) in a route cache, which is used to further reduce the cost of route discovery. A node may learn of routes from virtually any packet the node forwards or overhears. When a node wishes to send a packet, it examines its own route cache and performs route discovery only if no suitable source route is found.
Further, when a node receives a route request for which it has a route in its cache, it does not propagate the route request, but instead returns a route reply to the source node. The route reply contains the full concatenation of the recorded route from the source, and the cached route leading to the destination.
Naturally, if a route request packet reaches the destination node, the destination node returns a route reply packet to the source node with the full source to destination path listed.
Conventional routing protocols integrate route discovery with route maintenance by continuously sending periodic routing updates. If the status of a link or node changes, the periodic updates will eventually reflect the change to all other nodes, presumably resulting in the computation of new routes. However, using route discovery, there are no periodic messages of any kind from any of the mobile nodes. Instead, while a route is in use, the route maintenance procedure monitors the operation of the route and informs the sender of any routing errors.
If a node along the path of a packet detects an error, the node returns a route error packet to the sender. The route error packet contains the addresses of the nodes at both ends of the hop in error. When a route error packet is received or overheard, the hop in error is removed from any route caches and all routes which contain this hop must be truncated at that point.
There are many methods of returning a route error packet to the sender. The easiest of these, which is only applicable in networks which only use bidirectional links, is to simply reverse the route contained in the packet from the original host. If unidirectional links are used in the network, the DSR protocol presents several alternative methods of returning route error packets to the sender.
Route maintenance can also be performed using end-to-end acknowledgments rather than the hop-by-hop acknowledgments described above. As long as some route exists by which the two end hosts can communicate, route maintenance is possible. In this case, existing transport or application level replies or acknowledgments from the original destination, or explicitly requested network level acknowledgments, may be used to indicate the status of the node’s route to the other node.
Two sources of bandwidth overhead in DSR are route discovery and route maintenance. These occur when new routes need to be discovered or when the network topology changes [2] [12]. However, this overhead can be reduced by employing intelligent caching techniques in each node, at the expense of memory and CPU resources. The remaining source of bandwidth overhead is the required source route header included in every packet. This overhead cannot be reduced by techniques outlined in the DSR literature.
DSR simulation results have been reported in numerous papers, [5], [12], and [4] to name a few. In [5], Broch et al. found DSR to perform the best of four protocols simulated in their scenarios. Unfortunately, Broch only simulated networks of 50 nodes; as node count increases, the detrimental effects of route discovery and maintenance can be expected to grow.
The virtual subnet protocol (VS) [18] [19] breaks up a large body of nodes into smaller logical groups called subnets. It then applies a hierarchical addressing scheme to these subnets. A novel routing scheme is then employed to enable broadcasting within subnets and limited broadcasting between subnets. The virtual subnet addressing scheme is somewhat reminiscent of that used in ATM [8].
In this method, network nodes are assigned addresses depending on their current physical connectivity. Assume the network is segmented into physical subnets (the distinction between physical and virtual subnets will be clarified shortly; for the moment assume that physical subnets cover a local area) each containing mobile nodes. Each node in the network is assigned a unique address constructed of two parts: one part is a subnet address allocated to the entire subnet (subnet_id), and the other part is an address which is unique within the node’s subnet (node_id). In this paper, this address is written as subnet_id.node_id (e.g.: 12.2, 5.3).
Each node in this topology is affiliated with nodes whose address differs only in one digit; that is, node x1.x0 is affiliated with nodes x1.x0’ and x1’.x0 Thus, every node is affiliated with every node within its subnet, as well as one node in every other subnet. These cross-linked affiliations are the building blocks of the ad hoc network. Figure 5.1 illustrates a network arranged in this fashion.
Figure 5.1: Physical and virtual subnets in an ad hoc network.
Each node in the network is affiliated with a physical subnet (the local nodes all sharing the same subnet_id) and a virtual subnet (the nodes all sharing the same node_id). Nodes which are members of a physical subnet (subnet_id) are within close proximity in a local geographic area. Nodes which are members of a virtual subnet (node_id) form a regional network (i.e., beyond a local area). Figure 5.1 illustrates an example of an ad hoc network with physical subnets (in shaded areas) and virtual subnets. Note all nodes within a physical subnet have the same subnet_id, while all nodes within a virtual subnet have the same node_id.
A node becomes a member of a physical subnet by acquiring the first available address (with the lowest node_id) in that subnet. Once a node becomes affiliated with a specific physical subnet, it automatically becomes a member of a virtual subnet defined by the node_ID in its address. As long as a node remains within "hearing" distance of its subnet neighbors, it will keep its current physical subnet affiliation and its address.
When a node moves to a new location where it cannot establish a connection with its previous physical subnet’s members, it will drop its previous address and join a new physical subnet.
In the simple case where the destination node is within two hops of the source node, packets traverse one network address digit at a time in fixed order. For example, when the source node address is 12.15 and the destination node address is 9.17, the packet would follow the route: 12.15 to 12.17 to 9.17. In this case, routing requires at most two hops.
In general, the network will be arranged such that more than two hops are necessary from source to destination. In this case the routing is performed in two phases. In the first phase, routing is performed only in the physical subnet. Packets are routed to the node belonging to the same virtual subnet as the destination. Using the same example as above, phase one consists of routing packets from 12.15 to 12.17.
In phase two, packets are routed between virtual subnets. The papers describing virtual subnets by Sharony [18] [19] become especially sketchy at this stage of the protocol. The papers call for adjustments of transmission frequencies, transmission power, and/or directional antennae to facilitate logical network connections. It must be assumed that all nodes are capable of reaching neighboring physical subnets when required to do so. However, the papers do not describe how subnets become aware of, and plot routes through, neighboring subnets to facilitate multi-hop routing.
The VS protocol, as currently specified, can best be described as a method to optimize throughput when multiple frequencies and/or spatial reuse is possible, on the condition that nodes are close together relative to their transmitter range. Virtual subnets have been analyzed using queueing theory, but no actual simulations or implementations have been studied. Furthermore, there are apparent holes in the proposed routing mechanism regarding forwarding of packets between subnets.
Various routing protocols exist other than those presented in previous sections. For the most part, these routing protocols offer improvements to the protocols already discussed. This sections highlights the improvements or novel applications these protocols offer without repeating concepts presented in previous sections.
Ad Hoc On-Demand Distance Vector (AODV) [17] routing is essentially a combination of both DSR and DSDV. It borrows the basic on-demand mechanism of route discovery and route maintenance from DSR, plus the use of hop-by-hop routing, sequence numbers, and periodic update packets from DSDV.
The main benefit of AODV over DSR is the source route does not need to be included with each packet. This results in a reduction of routing protocol overhead. Unfortunately, AODV requires periodic updates which, based on simulations by Broch [5], consume more bandwidth than is saved from not including source route information in the packets.
Signal stability based adaptive routing (SSA) [3] is a variant of the AODV protocol to take advantage of information available at the link level. Both the signal quality of links and link congestion are taken into consideration when finding routes. It is assumed links with strong signals will change state less frequently. By favoring these strong signal links in route discovery, it is hoped routes will survive longer and the number of route discovery operations will be reduced. Link signal strength is measured when the nodes transmit periodic hello packets.
One important difference of SSA from AODV or DSR is that paths with strong signal links are favored over optimal paths. While this may make routes longer, it is hoped discovered routes will survive longer.
The cluster based routing protocol (CBRP) [11] is a variation of the DSR protocol. CBRP groups nodes located physically close together into clusters. Each cluster elects a cluster head. The cluster head maintains complete knowledge of cluster membership and inter-cluster members (called gateways) which have access to neighboring clusters.
The main difference between DSR and CBRP is during the route discovery operation. DSR floods route query packets throughout the entire network. CBRP takes advantage of its cluster structure to limit the scope of route query flooding. In CBRP, only the cluster heads (and corresponding gateways) are flooded with query packets, reducing the bandwidth required by the route discovery mechanism.
Unfortunately, CBRP depends on nodes transmitting periodic hello packets; a large part of the gains made by DSR are because DSR does not require periodic packets of any kind.
Optimized Link State Routing (OLSR) [10] is a link state routing protocol. OLSR is an adaption of conventional routing protocols to work in an ad hoc network on top of IMEP [6].
The novel attribute of OLSR is its ability to track and use multi-point relays. The idea of multi-point relays is to minimize the flooding of broadcast messages in the network by reducing/optimizing duplicate re-transmissions in the same region. Each node in the network selects a set of nodes in its neighborhood who will re-transmit its broadcast packets. This set of selected neighbor nodes is called the multi-point relays of that node. Each node selects its multi-point relay set in a manner to cover all the nodes that are two hops away from it. The neighbors which are not in the multi-point relay set still receive and process broadcast packets but do not re-transmit them. Figure 6.1 illustrates an example of multi-point relay versus regular broadcasting in a network of 10 nodes.
Figure 6.1: Multi-point relay versus conventional broadcasting. In this example, conventional broadcasting (a) requires 10 transmissions of the packet; multi-point relay broadcasting (b) only requires 3 (the routes taken by broadcast packets are shown by darker lines).
When a node needs to route a packet, it first checks to see if the destination node is within its zone. If it is, the node knows exactly how to route to the destination. Otherwise, a route search similar to DSR is employed. However, to reduce redundant route search broadcasts, nodes only transmit route query packets to the border nodes (called bordercasting). When the border nodes receive the search query packet, they repeat the process for their own zones.
Because ZRP only employs proactive network management in a local zone, overhead is reduced over protocols like DSDV. When route discovery procedures are employed as in DSR, overhead is reduced by limiting the query packet broadcasts to border nodes.
This paper presents an overview of ad hoc routing principles and how these differ from conventional routing. Four proposed ad hoc routing protocols, DSDV, TORA, DSR, and Virtual Subnets, are presented and commented on. Finally, several other ad hoc routing protocols are briefly introduced, highlighting their novel concepts or optimizations over the four main routing protocols presented earlier in the paper.
It is currently impossible to quantitatively compare and contrast most ad hoc routing protocols. For the most part, simulations of protocols have been done independent of one another and results cannot be compared. Furthermore, implementations of protocols in actual wireless ad hoc networks are largely nonexistent or proprietary. In order to begin filtering out inferior protocols and highlight the superior concepts, significant simulation work needs to be done in a coordinated, consistent fashion.
[1] "Internet Protocol," RFC 791, Information Sciences Institute, September 1981.
[2] Josh Broch, David Johnson, David Maltz, The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks, Internet Draft, draft-ietf-manet-dsr-00.txt, March 13, 1998. Work in progress.
[3] Rohit Dube, Cynthia Rais, Kuang-Yeh Wang, Satish Tripathi, Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks, IEEE Personal Communications, February, 1997.
[4] David Johnsom, David Maltz, Protocols for Adaptive Wireless and Mobile Networking, IEEE Personal Communications, Volume 3 Issue 1, February, 1996.
[5] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, Jorjeta Jetcheva, A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols, Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ‘98), October 25, 1998.
[6] S. Corson, S. Papademetriou, P. Papadopoulos, V. Park, A. Qayyum, An Internet MANET Encapsulation Protocol (IMEP) Specification, Internet Draft, draft-ietf-manet-imep-spec-01.txt, August 7, 1998. Work in progress.
[7] Z. Haas, M. Pearlman, The Zone Routing Protocol (ZRP) for Ad Hoc Networks, Internet Draft, draft-ietf-manet-zone-zrp-01.txt, August, 1998. Work in progress.
[8] Harry J. R. Dutton, Peter Lenhard, Asynchronous Transfer Mode, Prentice Hall, 1995.
[9] C. Hedrick, Routing Information Protocol, RFC 1058, June, 1988.
[10] P. Jacquet, P. Muhlethaler, A. Qayyum, Optimized Link State Routing Protocol, Internet Draft, draft-ietf-manet-olsr-00.txt, November 18, 1998. Work in progress.
[11] M. Jiang, J. Li, Y. C. Tay, Cluster Based Routing Protocol (CBRP) Functional Specification, Internet Draft, draft-ietf-manet-cbrp-spec-00.txt, August, 1998. Work in progress.
[12] David Johnson, Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Kluwer Academic Publishers, 1996.
[13] David B. Johnson, Routing in Ad Hoc Networks of Mobile Hosts, Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, December, 1994.
[14] V. Park, S. Corson, A Performance Comparison of TORA and Ideal Link State Routing, Proceedings of IEEE Symposium on Computers and Communication ‘98, June, 1998.
[15] V. Park, S. Corson, Temporally-Ordered Routing Algorithm (TORA) Version 1 Functional Specification, Internet Draft, draft-ietf-manet-tora-spec-01.txt, August 7, 1998. Work in progress.
[16] Charles E. Perkins, Pravin Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers, Proceedings of the SIGCOMM ‘94 Conference on Communications, Architectures, Protocols and Applications, pp 234-244, August, 1994
[17] Charles Perkins, Elizabeth Royer, Ad Hoc On Demand Distance Vector (AODV) Routing, Internet Draft, draft-ietf-manet-aodv-02.txt, November 20, 1998. Work in progress.
[18] Jacob Sharony, A Mobile Radio Network Architecture with Dynamically Changing Topology Using Virtual Subnets, Proceedings of ICC ‘96, pp 807-812, 1996.
[19] Jacob Sharony, An Architecture for Mobile Radio Networks with Dynamically Changing Topology Using Virtual Subnets, Mobile Networks and Applications 1, pp 75-86, 1996.
address Each node in a network has a unique identifier called the node’s address. This address is used in routing to determine where packets should be sent.
ad hoc For the scope of this paper, ad hoc means unplanned and/or established for one specific reason or occasion.
ad hoc network A network which is formed without apriori knowledge or planning. Nodes belonging to an ad hoc network do not share any central authority or support structure.
Asynchronous Transfer Mode A circuit switched networking technology used largely in the telephony industry. In ATM, nodes are arranged in a hierarchical manner according to strict policies. Routing in ATM takes advantage of this hierarchical network topology to perform quick and efficient source routing.
ATM See Asynchronous Transfer Mode.
base station In this paper, a base station is a stationary node participating in an ad hoc network.
broadcast A packet which is broadcast is received by every and all nodes within transmission range of the sender.
communication medium See medium.
convergence The point at which a routing protocol has stabilized and is generally ready to route packets through the network. When a routing protocol has not yet converged, loops may form. See loop.
convergence time The time required for a routing protocol to converge.
flooding See broadcast.
hop Each time a packet is transmitted, it is said to have performed one hop. Multi-hop networks require nodes in the network to enlist the aid of neighboring nodes to forward packets towards a destination node.
host See node.
IP See Internet Protocol.
Internet Protocol A packet switched network protocol as defined by the Internet Engineering Task Force (IETF). For more information, see http://www.ietf.org.
link A communication channel by which a node can send packets to another node.
loop Some protocols, when they have not converged, can set up routing loops. A loop is formed when two nodes do not agree on the shortest path to a destination. For example, suppose node A routes a packet to node B, but B subsequently routes the packet back to A. In this example, the packet will be routed between nodes A and B ad infinitem, or until their routing logic is synchronized and the routing protocol converges.
MAC This network layer sits between the physical layer and the network layer. It is usually thought of as part of the data link layer.
medium Synonymous with communication medium or link. See link.
metric The suitability of a given packet or route. Typically, the metric is the number of hops to a destination node. However, other forms of measure could be employed to determine a route metric such as link congestion or link stability.
mobile host See mobile node.
mobile node A node which is willing and able to physically move location, resulting in network topology changes.
network partition See partition.
on-demand routing A process by which a route between two nodes is unknown and unresolved until the moment the route is required.
partition Sometimes, in an ad hoc network, the network can break appart and groups of nodes can be out of range of other groups of nodes. When this happens, the network is said to be partitioned. Each group is called a network partition.
router A node willing to forward and route packets on behalf of other nodes. In ad hoc networks, typically every node acts as a router.
routing loop See loop.
source routing In source routing, a node wishing to send a packet will completely describe the path the packet should take to its destination. In some networks, such as ATM, source routing is accomplished based on a complete knowledge of the network topology. In ad hoc networks, source routing usually requires special route discovery procedures.
topology The graph representing node positions and their links to other nodes. The topology is said to change when links change state (are either created or destroyed) or nodes change state (appear, disappear, or move).
