the destination node verifies the signature of the source node and then sends a digitally
signed route reply packet (REP) back to the source. The REP travels the same path as the
RDP, and the same signing procedure is performed by intermediate nodes. Because the
destination must sign the REP message, only the destination is allowed to respond to the
10.7 OTHER TECHNIQUES
RDP. Also, because RDP messages are signed at each hop and do not contain a hop count
or a source route, malicious nodes have no opportunity to intentionally redirect traffic.
The Secure Routing Protocol (SRP)  is another approach to secure routing that is
based on the assumption of the existence of a security association between the source and
destination node. To initiate communication, the two nodes negotiate a shared secret key.
A message authentication code (MAC) is used to ensure that the reply message is not
modified en route to the source node. Only the destination can respond to route query
messages, and the source is assured that the destination was reached because the shared
key is used as input to the MAC computation.
Like SRP, Ariadne assumes that all pairs of communicating nodes have secret MAC
keys . Each pair of nodes maintains two keys, one for each direction of communica-
tion. Ariadne is utilizes symmetric cryptographic primitives and is based on the DSR rout-
ing protocol and the TESLA broadcast authentication protocol . Ariadne has the prop-
erties that source and destination nodes can authenticate each other due to the secret keys,
and that the source node can authenticate each entry on the path returned in the route re-
ply. In addition, a one-way function is utilized so that no intermediate node can remove a
previous node in the source route contained in route request and reply messages.
The Security Aware Routing (SAR) protocol described in  relies on trust levels to
provide security. Nodes form a trust hierarchy whereby each node is assigned a specific
trust level. Designed to run over a reactive routing protocol such as AODV or DSR, route
request and reply messages are assigned a security level by the source node. Only nodes
with at least the indicated level of security can process and forward the control messages.
Hence, SAR discovers routes in which all nodes along the path meet the desired level of
Finally, a mechanism for securing the AODV protocol is presented in . The proto-
col, SAODV utilizes digital signatures and hash chains for securing AODV control mes-
sages. The digital signatures are utilized to authenticate the nonmutable fields of the con-
trol messages, whereas the hash chains are used to secure the hop count information. The
approach assumes the nodes have access to a key management system so that the nodes
can obtain the public keys of the other nodes within the network.
10.7.3.2 Intrusion Detection and Monitoring Schemes. Intrusion detection is a
mechanism widely used in wired networks to detect malicious invaders and trigger an ap-
propriate response. Intrusion detection in ad hoc networks is somewhat less straightfor-
ward because membership in the network is open to virtually any user. Hence, it is diffi-
cult to detect when a user is actually a malicious intruder. Nevertheless, intrusion
detection techniques can be employed in ad hoc networks to detect misbehaving nodes,
particularly in networks in which the membership is well defined. Such networks include
military networks and collaborative networks comprised of a team of individuals.
An intrusion detection and response mechanism is presented in . It uses the coop-
erative statistical anomaly detection model to protect against attacks on routing protocols
or other wireless applications and services. Each intrusion detection system (IDS) agent
runs independently and monitors local activities. Intrusions are detected from local traces,
and responses are subsequently initiated. If an anomaly is detected in the local data, or if
the evidence is inconclusive and a broader search is warranted, neighboring IDS agents
cooperate to participate in global intrusion detection actions.
Another approach taken by a handful of protocols is to monitor node behavior to detect
misbehaving nodes. Node misbehavior can come in many forms; however, a common ac-
296 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS
tion to monitor is whether a node en route to a destination forwards data packets that it re-
ceives for that destination. For instance, the monitoring system described in  uses nodes
called watchdogs to monitor the forwarding of data packets by intermediate nodes. After a
node transmits a data packet, it promiscuously listens to determine whether the next hop
along the path forwards the data packet to its next hop. For this functionality to work, a node
must know the identity of the node two hops further along the path. In addition to the watch-
dog, network nodes also run a pathrater module to determine the reliability of paths. Nodes
maintain ratings for other network nodes and, hence, select paths with the highest aggregate
rating. The watchdog system is used to maintain the rating for neighboring nodes.
A similar monitoring system is described in . This approach incorporates a trust man-
ager and reputation system with a path manager to detect misbehaving or nonconforming
nodes and exclude them from routing. The difference with this approach is that nodes prop-
agate information about detected misbehaving nodes so that those nodes can be excluded
from participation in the network. When a node receives such a message indicating the mis-
behavior of another node, the node must be able to authenticate the source of that message.
This prevents denial of service attacks by malicious nodes against other, benign nodes.
As has been shown in this chapter, there exists a vast variety of routing protocols designed
specifically for ad hoc mobile networks. These networks create a hostile routing environ-
ment due to the mobility of the nodes and the resulting ephemeral nature of the network
links. However, significant strides have been made toward the development of robust rout-
ing protocols that can deliver high percentages of traffic, even in dynamic environments.
It is likely that there does not exist a single routing protocol that can solve the needs of
every conceivable ad hoc network scenario. Rather, the selection of a routing protocol for
a given network is likely to be dependent upon the dominating characteristics of that net-
work. Hence, certain routing protocols are likely to perform best in networks of one set of
characteristics, while others will perform better in networks with a differing set of charac-
teristics. More work is needed to identify the sets of characteristics that promote the opti-
mum behavior of each individual protocol and class of protocols.
This work is largely based on a tutorial on mobile ad hoc networks created jointly by the
author and Sung-Ju Lee of Hewlett-Packard Laboratories. The author would like to thank
Thomas Clausen, Zygmunt Haas, Yih-Chun Hu, Sung-Ju Lee, Richard Ogier, Marc Pearl-
man, Prince Samar, and Fred Templin for their insightful comments and contributions to
the protocol descriptions in this chapter.
1. D. J. Baker and A. Ephremides. â€śThe Architectural Organization of a Mobile Radio Network
via a Distributed Algorithm,â€ť IEEE Transactions on Communications, 29(11), 1694â€“1701, No-
2. S. Basagni. â€śDistributed Clustering for Ad Hoc Networks,â€ť in Proceedings of the 1999 Interna-
tional Symposium on Parallel Architectures, Algorithms, and Networks, pp. 310â€“315, June
3. S. Basagni, I. Chlamtac, V. Syrotiuk, and B. Woodward. â€śA Distance Routing Effect Algorithm
for Mobility (DREAM),â€ť in Proceedings of the 4th Annual ACM/IEEE International Conference
on Mobile Computing and Networking (MobiCom), pp. 76â€“84, Dallas, TX, October 1998.
4. E. M. Belding-Royer. â€śHierarchical Routing in Ad hoc Mobile Networks.â€ť Wireless Communi-
cations and Mobile Computing, 2002.
5. E. M. Belding-Royer. â€śMulti-Level Hierarchies for Scalable Ad Hoc Routing.â€ť Wireless Net-
6. B. Bellur, R. G. Ogier, and F. L. Templin. â€śTopology Broadcast Based on Reverse-Path For-
warding (TBRPF).â€ť IETF Internet Draft, draft-ietf-manet-tbrpf- 01.txt, (work in progress),
7. C. Bettstetter and R. Krausser. â€śScenario-Based Stability Analysis of the Distributed Mobility-
Adaptive Clustering (DMAC) Algorithm,â€ť in Proceedings of the 2nd Annual Symposium on Mo-
bile Ad hoc Networking and Computing, Long Beach, California, October 2001.
8. J. Broch, D. A. Maltz, D. Johnson, Y.-C. Hu, and J. Jetcheva. â€śA Performance Comparison of
Multi-Hop Wireless Ad Hoc Network Routing Protocols,â€ť in Proceedings of the 4th Annual
ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), pp.
85â€“97, Dallas, Texas, October 1998.
9. S. Buchegger and J.-Y. L. Boudec. Nodes Bearing Grudges: â€śTowards Routing Security, Fair-
ness, and Robustness in Mobile Ad Hoc Networks,â€ť in Proceedings of the Tenth Euromicro
Workshop on Parallel, Distributed and Network-based Processing, pp. 403â€“410, Canary Is-
lands, Spain, IEEE Computer Society, January 2002.
10. R. Castaneda and S. R. Das. â€śQuery Localization Techniques for On-demand Routing Protocols
in Ad Hoc Networks,â€ť in Proceedings of the 5th Annual ACM/IEEE International Conference on
Mobile Computing and Networking (MobiCom), pp. 186â€“194, Seattle, August 1999.
11. J.-H. Chang and L. Tassiulas. â€śEnergy Conserving Routing in Wireless Ad-Hoc Networks,â€ť in
Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pp. 22â€“31,
Tel Aviv, Israel, March 2000.
12. C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla. â€śRouting in Clustered Multihop, Mobile Wire-
less Networks with Fading Channel,â€ť in Proceedings of IEEE Singapore International Confer-
ence on Networks (SICON), pp. 197â€“211, April 1997.
13. C.-F. Chiasserini and R. R. Rao. â€śRouting Protocols to Maximize Battery Efficiency,â€ť in Pro-
ceedings of IEEE MILCOM, Los Angeles, CA, October 2000.
14. T. Clausen, P. Jacquet, A. Laouiti, P. Muhlethaler, A. Qayyum, and L. Viennot. â€śOptimized Link
State Routing Protocol,â€ť in Proceedings of IEEE INMIC, Lahore, Pakistan, December 2001.
15. S. R. Das, R. Castaneda, and J. Yan. â€śComparative Performance Evaluation of Routing Proto-
cols for Mobile, Ad Hoc Networks,â€ť in Proceedings of the 7th International Conference on
Computer Communications and Networks, pp. 153â€“161, Lafayette, LA, October 1998.
16. S. R. Das, C. E. Perkins, and E.M. Royer. â€śPerformance Comparison of Two Ondemand Rout-
ing Protocols for Ad Hoc Networks,â€ť in Proceedings of the IEEE Conference on Computer
Communications (INFOCOM), pp. 3â€“12, Tel Aviv, Israel, March 2000.
17. T. A. ElBatt, S. V. Krishnamurthy, D. Connors, and S. Dao. â€śPower Management for Through-
put Enhancement in Wireless Ad Hoc Networks,â€ť in Proceedings of the IEEE International
Conference on Communications (ICC), pp. 1503â€“ 1513, New Orleans, LA, June 2000.
18. M. Gerla, T. Kwon, and G. Pei. â€śOn Demand Routing in Large Ad Hoc Wireless Networks with
Passive Clustering,â€ť in Proceedings of the IEEE Wireless Communications and Networking
Conference (WCNC), Spetember 2000.
298 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS
19. Z. J. Haas and M. R. Pearlman. â€śThe Performance of Query Control Schemes for the Zone
Routing Protocol.â€ť ACM/IEEE Transactions on Networking, 9(4), 427â€“ 438, August 2001.
20. Y.-C. Hu and D. B. Johnson. â€śCaching Strategies in On-Demand Routing Protocols for Wireless
Ad Hoc Networks,â€ť in Proceedings of the Sixth Annual IEEE/ACM International Conference on
Mobile Computing and Networking (MobiCom 2000), pp. 231â€“242, Boston, MA, August 2000.
21. Y.-C. Hu and D. B. Johnson. â€śImplicit Source Routing in On-Demand Ad Hoc Network Rout-
ing,â€ť in Proceedings of the Second Symposium on Mobile Ad Hoc Networking and Computing
(MobiHoc 2001), pp.1â€“10, Oct. 2001.
22. Y.-C. Hu, D. B. Johnson, and A. Perrig. â€śAriadne: A Secure On-Demand Routing Protocol for
Ad Hoc Networks,â€ť in Proceedings of the 8th ACM International Conference on Mobile Com-
puting and Networking (Mobicom), Atlanta, GA, September 2002.
23. P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark. â€śScenario-based Per-
formance Analysis of Routing Protocols for Mobile Ad-Hoc Networks,â€ť in Proceedings of the
5th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom),
pp. 195â€“206, Seattle, WA, August 1999.
24. D. B. Johnson and D. A. Maltz. â€śDynamic Source Routing in Ad Hoc Wireless Networks,â€ť in T.
Imielinski and H. Korth (Eds.), Mobile Computing, pp. 153â€“181. Kluwer Academic Publishers,
25. Y.-B. Ko and N. H. Vaidya. â€śLocation-Aided Routing (LAR) in Mobile Ad Hoc Networks,â€ť in
Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and Net-
working (MobiCom), pp. 66â€“75, Dallas, Texas, October 1998.
26. R. Kravets and P. Krishnan. â€śApplication-Driven PowerManagement for Mobile Communica-
tion.â€ť Wireless Networks, 6(4), 263â€“277, 2000.
27. A. Laouiti, A. Qayyum, and L. Viennot. â€śMultipoint Relaying: An Efficient Technique for
Flooding in Mobile Wireless Networks,â€ť in Proceedings of the 35th Annual Hawaii Internation-
al Conference on System Sciences (HICSSâ€™ 2002), Waikoloa, HI, January 2002.
28. G. S. Lauer. â€śPacket-Radio Routing,â€ť in M. Steenstrup (Ed.), Routing in Communications Net-
works. Prentice-Hall, 1995.
29. S.-J. Lee and M. Gerla. â€śAODV-BR: Backup Routing in Ad Hoc Networks,â€ť in Proceedings of
the Wireless Communications and Networking Conference (WCNC), Chicago, IL, September
30. S.-J. Lee and M. Gerla. â€śSplit Multipath Routing with Maximally Disjoint Paths in Ad Hoc
Networks,â€ť in Proceedings of the IEEE International Conference on Communications (ICC),
pp. 3201â€“3205, Helsinki, Finland, June 2001.
31. S.-J. Lee, E. M. Royer, and C. E. Perkins. â€śAd Hoc Routing Protocol Scalability.â€ť International
Journal on Network Management, 2002.
32. S.-J. Lee, C.-K. Toh, and M. Gerla. â€śA Simulation Study of Table-Driven and On-Demand
Routing Protocols for Mobile Ad-Hoc Networks.â€ť IEEE Network, 13(4), 48â€“54, July/August
33. J. Li, J. Jannotti, D. S. J. D. Couto, D. R. Karger, and R. Morris. â€śA Scalable Location Service
for Geographic Ad hoc Routing,â€ť in Proceedings of the 6th ACM/IEEE International Confer-
ence on Mobile Computing and Networking (MobiCom), pp. 120â€“130, Boston, MA, August
34. J. Macker and M. S. Corson. Internet Engineering Task Force (IETF) Mobile Ad Hoc Networks
(MANET) Working Group Charter. http://www.ietf.org/html.charters/manet-charter.html.
35. G. S. Malkin and M. E. Steenstrup. â€śDistance-Vector Routing,â€ť in M. Steenstrup (Ed.), Routing
in Communications Networks, pp. 83â€“98. Prentice-Hall, 1995.
36. M. Marina and S. Das. â€śOn-demand Multipath Distance Vector Routing in Ad Hoc Networks,â€ť
in Proceedings of the International Conference on Network Protocols (ICNP), Riverside, CA,
37. S. Marti, T. J. Giuli, K. Lai, and M. Baker. â€śMitigating Routing Misbehavior in Mobile Ad Hoc
Networks,â€ť in Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile
Computing and Networking, pp. 255â€“265, 2000.
38. J. Moy. â€śLink-State Routing,â€ť in M. Steenstrup (Ed.), Routing in Communications Networks,
pp. 135â€“157. Prentice-Hall, 1995.
39. A. Nasipuri and S. Das. â€śOn-DemandMultipath Routing for Mobilc Ad Hoc Networks,â€ť in Pro-
ceedings of the IEEE Conference on Computer Communications and Networks (ICCCN), pp.
64â€“70, Boston, MA, October 1999.
40. P. Papadimitratos and Z. Haas. â€śSecure Routing for Mobile Ad Hoc Networks,â€ť in Proceedings
of the SCS Communication Networks and Distributed Systems Modeling and Simulation Con-
ference (CNDS 2002), San Antonio, Texas, January 2000.
41. M. R. Pearlman and Z. J. Haas. â€śDetermining the Optimal Configuration for the Zone Routing
Protocol.â€ť IEEE Journal on Selected Areas in Communications, 17(8), 1395â€“1414, August
42. M. R. Pearlman, Z. J. Haas, P. Sholander, and S. S. Tabrizi. â€śOn the Impact of Alternate Path
Routing for Load Balancing in Mobile Ad Hoc Networks,â€ť in Proceedings of the 1st Annual
Workshop on Mobile and Ad hoc Networking and Computer (MobiHOC)), pp. 3â€“10, Boston,
43. G. Pei, M. Gerla, and X. Hong. LANMAR: â€śLandmark Routing for Large Scale Wireless Ad
Hoc Networks with Group Mobility,â€ť in Proceedings of the 1st Annual Workshop on Mobile and
Ad hoc Networking and Computer (MobiHOC), pp. 11â€“18, Boston, MA, August 2000.
44. G. Pei, M. Gerla, X. Hong, and C.-C. Chiang. â€śA Wireless Hierarchical Routing Protocol with
Group Mobility,â€ť in Proceedings of IEEE Wireless Communications and Networking Confer-
ence (WCNC), pp. 1538â€“1542, New Orleans, September 1999.
45. C. E. Perkins, E. M. Belding-Royer, and S. R. Das. â€śAd Hoc On-Demand Distance Vector
(AODV) Routing.â€ť IETF Internet Draft, draft-ietf-manet-aodv-10.txt, March 2002. (Work in
46. C. E. Perkins and P. Bhagwat. â€śHighly Dynamic Destination-Sequenced Distance-Vector Rout-
ing (DSDV) for Mobile Computers,â€ť SIGCOMM â€™94: Computer Communications Review,
24(4), 234â€“244, October 1994.
47. C. E. Perkins and E. M. Royer. â€śAd-Hoc On-Demand Distance Vector Routing,â€ť in Proceedings
of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp. 90â€“100, New
Orleans, February 1999.
48. C. E. Perkins and E. M. Royer. â€śThe Ad Hoc On-Demand Distance Vector Protocol,â€ť in C. E.
Perkins (Ed.), Ad Hoc Networking, pp. 173â€“219. Addison-Wesley, 2000.
49. A. Perrig, R. Canetti, D. Song, and J. Tygar. â€śEfficient and Secure Source Authentication for
Multicast,â€ť in Proceedings of the Network and Distributed System Security Symposium (NDSS),
San Diego, February 2001.
50. J. Raju and J. Garcia-Luna-Aceves. â€śA New Approach to On-Demand Loop- Free Multipath
Routing,â€ť in Proceedings of the IEEE Conference on Computer Communications and Networks
(ICCCN), pp. 522â€“527, Boston, October 1999.
51. R. Ramanathan and R. Rosales-Hain. â€śTopology Control of Multihop Wireless Networks Using
Transmit Power Adjustment,â€ť in Proceedings of the IEEE Conference on Computer Communi-
cations (INFOCOM), pp. 404â€“413, Tel Aviv, Israel, March 2000.
52. R. Ramanathan and M. Steenstrup. â€śHierarchically-organized,Multihop Mobile Wireless Net-
works for Quality-of-Service Support.â€ť ACM/Baltzer Mobile Networks and Applications, 3(1),
53. E. M. Royer and C.-K. Toh. â€śA Review of Current Routing Protocols for Ad-Hoc Mobile Net-
works.â€ť IEEE Personal Communications, 6(2), 46â€“55, April 1999.
54. P. Samar, M. R. Pearlman, and Z. J. Haas. â€śHybrid Routing: The Pursuit of an Adaptable and
300 ROUTING APPROACHES IN MOBILE AD HOC NETWORKS