<<

. 53
( 87 .)



>>


standing, developing, and deploying a broad base of MANET technology. One promising
area of future work is engineering improvements in extending network and wireless inter-
face design to improve system effectiveness. This is also a problem area for other wire-
less, mobile Internet efforts and is not limited to routing issues.
Overall, significant progress in the area of MANET technology has been realized in re-
cent years. After years of research and development, we are now seeing a growing sense
of widespread, practical applications for this technology along with the more esoteric vi-
sions. We anticipate further proliferative growth of wireless network systems at the edge
of the Internet infrastructure and, therefore, more requirements for adaptive, flexible, and
robust operational concepts in the next decade. As our daily lives and our societies begin
teeming with wireless devices, everywhere and in everything, adaptive network technolo-
gies will further enable the envisioned, invisible computing world.


REFERENCES

1. M. Weiser, “The Computer for the Twenty-First Century,” Scientific American, pp. 94“10, Sep-
tember 1991.
2. M. S. Corson, S. Batsell, and J. Macker, “Architectural Considerations for Mobile Mesh Net-
working,” in Proceedings IEEE MILCOM 96.
3. J. P. Macker and M. S. Corson, “Mobile Ad Hoc Networking: Routing Protocol Performance Is-
sues and Evaluation Considerations,” Internet RFC 2501, Jan 1999.
4. M. S. Corson, J. P. Macker, G. Cirincione, “Internet-Based Mobile Ad Hoc Networking,” IEEE
Internet Computing, 3, 4, July/August 1999.
5. J. P. Macker, V. Park, and M. S. Corson, “Mobile and Wireless Internet Service: Putting the
Pieces Together,” IEEE Communications Magazine, June 2001.
6. P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,™™ IEEE Transactions on Infor-
mation Theory, IT-46, 2, pp. 388“404, March 2000.
7. C. Perkins et al., Ad Hoc Networking, Addison-Wesley, 2001.
8. Partial list of protocol implementations, http://www.wikipedia.org/wiki/Ad_hoc_protocols_im-
plementations.
9. The Network Simulator ns-2, http://www.isi.edu/nsnam/ns/.
10. Qualnet Simulator, http://www.scalable-networks.com/.
11. OPNET Simulator, http://www.opnet.com/.
12. ETSI STC-RES10 Committee. Radio equipment and systems: HIPERLAN type 1, functional
specifications ETS 300-652, ETSI, June 1996
13. A. Ephremides, J. E. Wieselthier, and D. J. Baker, “A Design Concept for Reliable Mobile Ra-
dio Networks with Frequency Hopping Signaling,” Proceedings of IEEE. 75, 56“73, January
1987.
14. R. Kahn et al., “Advances in Packet Radio Technology,” Proceedings of the IEEE 66,
1468“1496, November 1978.
15. B. Bellur and R. G. Ogier, “A Reliable, Efficient Topology Broadcast Protocol for Dynamic
Networks,” Proceedings IEEE INFOCOM ˜99, New York, March 1999.
16. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum, and L. Viennot, “Optimized Link
State Routing Protocol,” IEEE INMIC 2001.
17. D. B. Johnson, D. A. Maltz, and J. Broch, “DSR: The Dynamic Source Routing Protocol for
Multihop Wireless Ad Hoc Networks,” in Ad Hoc Networking, C. E. Perkins (Ed.), pp. 139“172,
Addison-Wesley, 2001.
273
REFERENCES


18. C. E. Perkins and E. M. Royer, “The Ad Hoc On-Demand Distance-Vector Protocol (AODV),”
in Ad Hoc Networking, C. E. Perkins (Ed.), pp. 173“219, Addison-Wesley, 2001.
19. Z. Haas and M. Pearlman, “Zone Routing Protocol (ZRP): A Framework for Routing in Hybrid
Ad Hoc Networks,” in Ad Hoc Networking, C. E. Perkins (Ed.), pp. 221“253, Addison-Wesley,
2001.
CHAPTER 10




ROUTING APPROACHES IN
MOBILE AD HOC NETWORKS

ELIZABETH M. BELDING-ROYER




10.1 INTRODUCTION

Routing in ad hoc networks has become a popular research topic. Dating back to the early
1980s, there have been a large number of routing protocols designed for multihop ad hoc
networks. These protocols cover a wide range of design choices and approaches, from sim-
ple modifications of Internet protocols, to more complex multilevel hierarchical schemes.
Many of these routing protocols have been designed based on similar sets of assump-
tions. For instance, most routing protocols assume that all nodes have homogeneous re-
sources and capabilities. This includes the transmission ranges of the nodes. Also, bidirec-
tional links are often assumed. In some instances, protocols have mechanisms for
determining whether links are bidirectional. In these cases, the protocols will then elimi-
nate unidirectional links from consideration for routing. In other instances, protocols can
actually utilize these unidirectional links, whereas other protocols simply assume all links
are bidirectional. Finally, although the ultimate end goal of a protocol may be operation in
large networks, most protocols are typically designed for moderately sized networks of 10
to 100 nodes.
Before describing the types of approaches and example protocols, it is important to ex-
plain the developmental goals for an ad hoc routing protocol so that the design choices of
the protocols can be better understood. As has already been stated in previous chapters,
the defining characteristics of ad hoc networks include resource-poor devices, limited
bandwidth, high error rates, and a continually changing topology. Among the available re-
sources, battery power is typically the most constraining. Hence, the following are typical
design goals for ad hoc network routing protocols:

275
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.
276 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS


Minimal control overhead. Control messaging consumes bandwidth, processing
resources, and battery power to both transmit and receive a message. Because
bandwidth is at a premium, routing protocols should not send more than the min-
imum number of control messages they need for operation, and should be de-
signed so that this number is relatively small. While transmitting is roughly twice
as power consuming as receiving [26], both operations are still power consumers
for the mobile devices. Hence, reducing control messaging also helps to conserve
battery power.
Minimal processing overhead. Algorithms that are computationally complex re-
quire significant processing cycles in devices. Because the processing cycles cause
the mobile device to use resources, more battery power is consumed. Protocols that
are lightweight and require a minimum of processing from the mobile device re-
serve battery power for more user-oriented tasks and extend the overall battery life-
time.
Multihop routing capability. Because the wireless transmission range of mobile
nodes is often limited, sources and destinations may typically not be within direct
transmission range of each other. Hence, the routing protocol must be able to dis-
cover multihop routes between sources and destinations so that communication be-
tween those nodes is possible.
Dynamic topology maintenance. Once a route is established, it is likely that some
link in the route will break due to node movement. In order for a source to commu-
nicate with a destination, a viable routing path must be maintained, even while the
intermediate nodes, or even the source or destination nodes, are moving. Further,
because link breaks on ad hoc networks are common, link breaks must be handled
quickly with a minimum of associated overhead.
Loop prevention. Routing loops occur when some node along a path selects a next
hop to the destination is also a node that occurred earlier in the path. When a routing
loop exists, data and control packets may traverse the path multiple times until ei-
ther the path is fixed and the loop is eliminated, or until the time to live (TTL) of the
packet reaches zero. Because bandwidth is scarce and packet processing and for-
warding is expensive, routing loops are extremely wasteful of resources and are
detrimental to the network. Even a transitory routing loop will have a negative im-
pact on the network. Hence, loops should be avoided at all times.

With these goals in mind, numerous routing protocols have been developed for ad hoc
networks. There are far too many proposed routing protocols than can be discussed in this
chapter. This chapter describes the characteristics of classes of routing approaches, and
then describes the operation of particular routing protocols within those classes. The rout-
ing protocols that are described are selected for a number of reasons. They may be popu-
lar choices for routing-related research among the ad hoc community; they may, at the
time of this writing, be under consideration by the Mobile Ad Hoc Networks (MANET)
Working Group [34] of the IETF for standardization; or, they may simply be good, illus-
trative examples of their particular class of protocol. This chapter does not make compar-
isons regarding the discussed protocols. There have been many published studies compar-
ing the performance of ad hoc routing protocols in a variety of scenarios. The interested
reader should see [8, 15, 16, 23, 32, 53] for comparisons of some of the discussed proto-
cols. Further, the citations for the protocols themselves often contain an evaluation of the
277
10.2 PROACTIVE APPROACHES


protocol, and sometimes a comparison with other ad hoc routing protocols. Finally, a
high-level description of each protocol is presented. Consequently, many operational de-
tails have been omitted. Additional details of each protocol can be found in its respective
citation.


10.2 PROACTIVE APPROACHES

The proactive routing approaches designed for ad hoc networks are derived from the tradi-
tional distance vector [35] and link state [38] protocols developed for use in the wireline
Internet. The primary characteristic of proactive approaches is that each node in the net-
work maintains a route to every other node in the network at all times. Route creation and
maintenance is accomplished through some combination of periodic and event-triggered
routing updates. Periodic updates consist of routing information exchanges between
nodes at set time intervals. The updates occur at specific intervals, regardless of the mo-
bility and traffic characteristics of the network. Event-triggered updates, on the other
hand, are transmitted whenever some event, such as a link addition or removal, occurs.
The mobility rate directly impacts the frequency of event-triggered updates because link
changes are more likely to occur as mobility increases.
Proactive approaches have the advantage that routes are available the moment they are
needed. Because each node consistently maintains an up-to-date route to every other node
in the network, a source can simply check its routing table when it has data packets to
send to some destination and begin packet transmission. However, the primary disadvan-
tage of these protocols is that the control overhead can be significant in large networks or
in networks with rapidly moving nodes. Further, the amount of routing state maintained at
each node scales as O(n), where n is the number of nodes in the network. Proactive proto-
cols tend to perform well in networks where there is a significant number of data sessions
within the network. In these networks, the overhead of maintaining each of the paths is
justified because many of these paths are utilized.

10.2.1 Destination-Sequenced Distance Vector Routing
The Destination-Sequenced Distance Vector (DSDV) routing protocol [46] is a distance
vector protocol that implements a number of customizations to make its operation more
suitable for ad hoc mobile networks. DSDV utilizes per-node sequence numbers to avoid
the counting to infinity problem common in many distance vector protocols. A node incre-
ments its sequence number whenever there is a change in its local neighborhood (i.e., a
link addition or removal). When given a choice between two routes to a destination, a
node always selects the route with the greatest destination sequence number. This ensures
utilization of the most recent information.
Because DSDV is a proactive protocol, each node maintains a route to every other
node in the network. The routing table contains the following information for each entry:
destination IP address, destination sequence number, next-hop IP address, hop count, and
install time. DSDV utilizes both periodic and event-triggered routing table updates. Every
time interval, each node broadcasts to its neighbors its current sequence number, along
with any routing table updates. The routing table updates are of the form:

< destination IP address, destination sequence number, hopcount >
278 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS


After receiving an update message, the neighboring nodes utilize this information to
compute their routing table entries using an iterative distance vector approach [35]. In ad-
dition to periodic updates, DSDV also utilizes event-triggered updates to announce impor-
tant link changes, such as link removals. Such event-triggered updates ensure timely dis-
covery of routing path changes.
As stated previously, if a node learns two distinct paths to a destination, the node se-
lects the path with the greatest associated destination sequence number. This ensures the
utilization of the most recent routing information for that destination. When given the
choice between two paths with equal destination sequence numbers, the node selects the
path with the shortest hop count. On the other hand, if all metrics are equivalent, then the
choice between routes is arbitrary.
DSDV implements two primary optimizations to improve performance in mobile net-
works. The first is that it defines two types of updates: full and incremental. Full up-
dates are transmissions of a node™s entire routing table. Because the size of these updates
scales with the size of the network, these updates are performed relatively infrequently.
To reduce processing overhead and bandwidth consumption, incremental updates are
transmitted more frequently. Incremental updates include only those routing table entries
that have changed size since the last full update. Once the number of routing changes
becomes too great to fit into a single NPDU, a full update is transmitted during the next
update period.
Finally, DSDV also implements a mechanism to damp routing fluctuations. Due to the
unsynchronized nature of the periodic updates, routing updates for a given destination can
propagate along different paths at different rates. To prevent a node from announcing a
routing path change for a given destination while another, better, update for that destina-
tion is still en route, DSDV requires nodes to wait a settling time before announcing a new
route with a higher metric for a destination. The settling time is the average time to get all
the updated advertisements for a route. In this way, the node can be sure to receive all
routing path changes for a destination before propagating any of those changes. This re-
duces bandwidth utilization and power consumption by neighboring nodes.

10.2.2 Optimized Link State Routing
The Optimized Link State Routing (OLSR) protocol [14] is a variation of traditional link
state routing, modified for improved operation in ad hoc networks. The key feature of
OLSR is its use of multipoint relays (MPRs) to reduce the overhead of network floods and
the size of link state updates. Each node computes its MPRs from its set of neighbors. The
MPR set is selected such that when a node broadcasts a message, the retransmission of
that message by the MPR set will ensure that the message is received by each of its two-
hop neighbors. Hence, whenever a node broadcasts a message, only those neighbors in its
MPR set rebroadcast the message. Other neighbors that are not in the MPR set process the
message but do not rebroadcast it. Further, when exchanging link state routing informa-
tion, a node only lists its connections to those neighbors that have selected it as an MPR.
That set of neighbors is termed the MPR Selectors.
The MPR set for a given node is the set of neighbors that covers the two-hop neighbor-
hood of the node, as shown in Figure 10.1. Nodes learn their set of two-hop neighbors
through the periodic exchange of Hello messages. Each node periodically transmits a Hel-
lo message that contains a list of all neighbors. Associated with each neighbor is an at-
tribute indicating the directionality of the link to that neighbor. The node is labeled sym-
279
10.2 PROACTIVE APPROACHES




S




Figure 10.1. Multipoint relays.



metric if the link to the neighbor is bidirectional, or asymmetric if a Hello has been re-
ceived from that node but the link has not been confirmed as bidirectional. When a node
receives this Hello message from each of its neighbors, it obtains complete knowledge of
its two-hop neighbor set at that point in time. Further, if its own address is listed in the
Hello message, it knows the link with that neighbor is bidirectional. It can then update the
status of that neighbor to be symmetric.

<<

. 53
( 87 .)



>>