An ad-hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route

Routing

Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...

 packets between computing devices in a mobile ad hoc network

Mobile ad hoc network

A mobile ad-hoc network is a self-configuring infrastructureless network of mobile devices connected by wireless links. ad hoc is Latin and means "for this purpose"....

 .

In ad-hoc networks, nodes are not familiar with the topology of their networks; instead, they have to discover it.The basic idea is that a new node may announce its presence and should listen for announcements broadcast by its neighbors.Each node learns about nodes nearby and how to reach them, and may announce that it, too, can reach them.

Note that in a wider sense, ad hoc protocol can also be used literally, that is, to mean an improvised and often impromptu protocol established for a specific purpose.

The following is a list of some ad hoc network routing protocols.

Pro-active (table-driven) routing

This type of protocols maintains fresh lists of destinations and their routes by periodically distributing routing tables throughout the network.
The main disadvantages of such algorithms are:

1. Respective amount of data for maintenance.
2. Slow reaction on restructuring and failures.

Examples of pro-active algorithms are:

• Babel
  Babel (protocol)
  The Babel routing protocol is a distance-vector routing protocol for Internet Protocol packet-switched networks that is designed to be robust and efficient on both wireless mesh networks and wired networks....
  
  , a protocol inspired by DSDV with faster convergence and ETX link quality estimation. Free implementation available.
• B.A.T.M.A.N.
  B.A.T.M.A.N.
  The Better Approach To Mobile Adhoc Networking, or B.A.T.M.A.N., is a routing protocol which is currently under development by the “Freifunk”-Community and intended to replace OLSR....
  
   – Better approach to mobile adhoc networking. RFC Draft: http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00
• DSDV
  Destination-Sequenced Distance Vector routing
  Destination-Sequenced Distance-Vector Routing is a table-driven routing scheme for ad hoc mobile networks based on the Bellman-Ford algorithm. It was developed by C. Perkins and P.Bhagwat in 1994. The main contribution of the algorithm was to solve the routing loop problem...
  
   (Highly Dynamic Destination-Sequenced Distance Vector routing protocol) – C. E. PERKINS, P. BHAGWAT Highly Dynamic Destination-Sequenced Distance Vector (DSDV) for Mobile Computers Proc. of the SIGCOMM 1994 Conference on Communications Architectures, Protocols and Applications, Aug 1994, pp 234–244.
• HSR
  Hierarchical state routing
  Hierarchical state routing , proposed in Scalable Routing Strategies for Ad Hoc Wireless Networks by Iwata et al. , is a typical example of a hierarchical routing protocol....
  
   (Hierarchical State Routing protocol) – Guangyu Pei and Mario Gerla and Xiaoyan Hong AND Ching-Chuan Chiang, A Wireless Hierarchical Routing Protocol with Group Mobility, IEEE WCNC'99, New Orleans, USA, September 1999. http://wiki.uni.lu/secan-lab/Hieracical+State+Routing.html
• IARP
  IARP
  International Aging Research Portfolio is a non-profit, open-access knowledge management system incorporating grants, publications, conferences in natural and social & behavioral sciences. In addition to the advanced search and visual trend analysis tools the system includes a directory of...
  
   (Intrazone Routing Protocol/pro-active part of the ZRP) – ZYGMUNT J. HAAS, MARC R. PEARLMAN, PRINCE SAMAR The Intrazone Routing Protocol (IARP) for Ad Hoc Networks, Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-zone-iarp, work in progress, July 2002.
• Linked Cluster Architecture|LCA (Linked Cluster Architecture) – M. GERLA, J. T. TSAI Multicluster, Mobile, Multimedia Radio Network ACM Wireless Networks, VOl 1, No.3, 1995, pp. 255–265
• WAR (Witness Aided Routing) – Aron, I.D. and Gupta, S., 1999, “A Witness-Aided Routing Protocol for Mobile Ad Hoc Networks with Unidirectional Links”, Proc. of the First International Conference on Mobile Data Access, p.24-33.
• OLSR
  Optimized link state routing protocol
  The Optimized Link State Routing Protocol is an IP routing protocol optimized for mobile ad-hoc networks, which can also be used on other wireless ad-hoc networks. OLSR is a proactive link-state routing protocol, which uses hello and topology control messages to discover and then disseminate...
  
   Optimized Link State Routing Protocol RFC 3626: http://tools.ietf.org/html/rfc3626

Reactive (on-demand) routing

This type of protocols finds a route on demand by flooding the network with Route Request packets. The main disadvantages of such algorithms are:

1. High latency time in route finding.
2. Excessive flooding can lead to network clogging.

Examples of reactive algorithms are:

• SENCAST – P. Appavoo and K. Khedo, SENCAST: A Scalable Protocol for Unicasting and Multicasting in a Large Ad hoc Emergency Network, International Journal of Computer Science and Network Security, Vol.8 No.2, February 2008
• Reliable Ad hoc On-demand Distance Vector Routing Protocol – Sandhya Khurana, Neelima Gupta, Nagender Aneja, http://doi.ieeecomputersociety.org/10.1109/ICNICONSMCL.2006.183
• Ant-based Routing Algorithm for Mobile Ad Hoc Networks – Mesut Günes et al., ARA – the ant-colony based routing algorithm for manets, In Stephan Olariu, editor, Proceedings of the 2002 ICPP Workshop on Ad Hoc Networks (IWAHN 2002), pages 79–85, IEEE Computer Society Press, August 2002, http://www.adhoc-nets.de
• Admission Control enabled On demand Routing (ACOR) – N. Kettaf, A. Abouaissa, T. Vuduong and P. Lorenz, http://tools.ietf.org/html/draft-kettaf-manet-acor, July 2006, (Work in progress)]
• Ariadne – Y. Chu, A. Perrig, D. Johnson, Ariadne: A Secure On-Demand Routing Protocol for Ad Hoc Networks, Proc. ACM Conf. Mobile Computing and Networking (MobiCom), 2002. http://sparrow.ece.cmu.edu/~adrian/projects/secure-routing/ariadne.pdf
• Associativity-Based Routing – CHAI-KEONG TOH: A Novel Distributed Routing Protocol To Support Ad hoc Mobile Computing, Proc. IEEE 15th Annual International Phoenix Conference on Computers and Communications, IEEE IPCCC 1996, 27 March-29, Phoenix, AZ, USA, pp. 480–486 / CHAI-KEONG TOH: Long-lived Ad Hoc Routing based on the Concept of Associativity, Internet Draft, March 1999, Expired, http://tools.ietf.org/html/draft-ietf-manet-longlived-adhoc-routing – US PATENT 5,987,011 http://www.patentstorm.us/patents/5987011.html
• Ad hoc On-demand Distance Vector(AODV) – C. PERKINS, E.ROYER AND S. DAS Ad hoc On-demand Distance Vector (AODV) Routing, RFC 3561
• Ad hoc On-demand Routing Protocol (AORP) – A. Reeve: Resilient Real-time Communications Across Meshed Networks Under Adverse Conditions, Proc. 1st SEAS DTC Technical Conference, 2006, http://www.seasdtc.com/downloads/pdf/conf_material_06/communications_and_control/cc001.pdf
• Ad hoc On-demand Multipath Distance Vector – M. Marina, S. Das: On-demand Multipath Distance Vector Routing in Ad Hoc Networks, Proceedings of the 2001 IEEE International Conference on Network Protocols (ICNP), pages 14—23, IEEE Computer Society Press, 2001.
• Backup Source Routing – SONG GUO, OLIVER W. YANG Performance of Backup Source Routing (BSR) in mobile ad hoc networks p 440-444, Proc. 2002 IEEE Wireless Networking Conference
• Dynamic Source Routing
  Dynamic Source Routing
  'Dynamic Source Routing' is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting computer requests one...
  
   – DAVID JOHNSON, DAVID MALTZ, YIH-CHUN HU: The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks for IPv4, RFC 4728 / DAVID B. JOHNSON, DAVID A. MALTZ: Dynamic Source Routing in Ad Hoc Wireless Networks, Mobile Computing, Thomasz Imielinski and Hank Korth (Editors), Vol. 353, Chapter 5, pp. 153–181, Kluwer Academic Publishers, 1996
• Flow State in the Dynamic Source Routing
  DSRFLOW
  DSRFLOW, the Flow-State extensions to Dynamic Source Routing , are a set of extensions that provide all of the benefits of source routing, without most of the per-packet overhead that is associated with source routing. It works by allowing most packets to be sent without a source route header, thus...
  
   – YIH-CHUN HU, DAVID B. JOHNSON, DAVID A. MALTZ Flow State in the Dynamic Source Routing Protocol Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-dsrflow, work in progress, June 2001.
• Dynamic NIx-Vector Routing – Young J. Lee and George F. Riley, Dynamic NIx-Vector Routing for Mobile Ad Hoc Networks. Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC 2005), New Orleans, Mar. 13 – 17, 2005.
• DYnamic Manet On-demand Routing
  DYMO
  The DYMO routing protocol is successor to the popular Ad hoc On-Demand Distance Vector Routing protocol and shares many of its benefits. It is, however, slightly easier to implement and designed with future enhancements in mind....
  
   – I. Chakeres AND C. Perkins: Dynamic MANET On-demand Routing Protocol (DYMO), Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-dymo, work in progress, June 2008. RFC 4728

Endaira: It is on demand source routing protocol and it is designed to address the hidden channel attack in ariadne.

Flow-oriented routing

This type of protocols finds a route on demand by following present flows. One option is to unicast consecutively when forwarding data while promoting a new link. The main disadvantages of such algorithms are:

1. Takes long time when exploring new routes without a prior knowledge.
2. May refer to entitative existing traffic to compensate for missing knowledge on routes.

Examples of flow oriented algorithms are:

• FR and PR, E. Gafni, D. Bertsekas: Distributed Algorithms for Generating Loop-free Routes in Networks with Frequently Changing Topology, IEEE Transactions on Communication, Vol. 29, No. 1, Jan, 1981, pp.11–15. - The first Link Reversal Routing (LRR) algorithms.
• IERP (Interzone Routing Protocol/reactive part of the ZRP) – ZYGMUNT J. HAAS, MARC R. PEARLMAN, PRINCE SAMAR The Interzone Routing Protocol (IERP) for Ad Hoc Networks, Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-zone-ierp, work in progress, July 2002.
• LUNAR
  Lunar
  Lunar may refer to:*Relating to the Moon*Lunar , a series of console video games*Lunar distance *Lunar calendar...
  
   (Lightweight Underlay Network Ad hoc Routing) – CHRISTIAN TSCHUDIN AND RICHARD GOLD Lightweight Underlay Network Ad hoc Routing (LUNAR), http://cn.cs.unibas.ch/projects/lunar/
• RDMAR (Relative-Distance Micro-discovery Ad hoc Routing protocol) – G. AGGELOU, R. TAFAZOLLI Relative Distance Micro-discovery Ad Hoc Routing (RDMAR) protocol Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-rdmar, work in progress, September 1999.
• SSR (Signal Stability Routing protocol) – R. DUBE, C. D. RAIS, K. WANG, AND S. K. TRIPATHI Signal Stability based adaptive routing (SSR alt SSA) for ad hoc mobile networks, IEEE Personal Communication, Feb. 1997.

Hybrid (both pro-active and reactive) routing

This type of protocols combines the advantages of proactive and of reactive routing. The routing is initially established with some proactively prospected routes and then serves the demand from additionally activated nodes through reactive flooding. The choice for one or the other method requires predetermination for typical cases. The main disadvantages of such algorithms are:

1. Advantage depends on number of Mathavan nodes activated.
2. Reaction to traffic demand depends on gradient of traffic volume.

Examples of hybrid algorithms are:

• HRPLS (Hybrid Routing Protocol for Large Scale Mobile Ad Hoc Networks with Mobile Backbones) – Ashish Pandey, Md. Nasir Ahmed, Nilesh Kumar, P. Gupta: A Hybrid Routing Scheme for Mobile Ad Hoc Networks with Mobile Backbones, IEEE International Conference on High Performance Computing, HIPC 2006, pp. 411–423, Dec 2006.
• HWMP (Hybrid Wireless Mesh Protocol) – default mandatory routing protocol for 802.11s. HWMP is inspired by a combination of AODV (RFC 3561[2] ) and tree-based proactive routing. Guenael Strutt: HWMP Specification Update. The Working Group for WLAN Standards of the Institute of Electrical and Electronics Engineers. 14 November 2006 https://mentor.ieee.org/802.11/dcn/06/11-06-1800-00-000s-hwmp-specification-update.ppt
• ZRP
  Zone Routing Protocol
  Zone Routing Protocol or ZRP was the first hybrid routing protocol with both a proactive and a reactive routing component. ZRP was proposed to reduce the control overhead of proactive routing protocols and decrease the latency caused by route discovery in reactive routing protocols...
  
   (Zone Routing Protocol) – ZYGMUNT J. HAAS, MARC R. PEARLMAN, PRINCE SAMAR The Zone Routing Protocol (ZRP) for Ad Hoc Networks, Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-zone-zrp, work in progress, July 2002. ZRP uses IARP as pro-active and IERP as reactive component.

Hierarchical routing protocols

With this type of protocols the choice of proactive and of reactive routing depends on the hierarchic level where a node resides. The routing is initially established with some proactively prospected routes and then serves the demand from additionally activated nodes through reactive flooding on the lower levels. The choice for one or the other method requires proper attributation for respective levels. The main disadvantages of such algorithms are:

1. Advantage depends on depth of nesting and addressing scheme.
2. Reaction to traffic demand depends on meshing parameters.

Examples of hierarchical routing algorithms are:

• CBRP (Cluster Based Routing Protocol) – M. JIANG, J. LI, Y. C. TAY Cluster Based Routing Protocol (CBRP) Functional Specification Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-cbrp-spec, work in progress, June 1999.
• CEDAR
  Cedar
  Cedrus is a genus of coniferous trees in the plant family Pinaceae. They are native to the mountains of the western Himalaya and the Mediterranean region, occurring at altitudes of 1,500–3,200 m in the Himalaya and 1,000–2,200 m in the Mediterranean.-Description:Cedars are trees up to...
  
   (Core Extraction Distributed Ad hoc Routing) – RAGHUPATHY SIVAKUMAR, PRASUN SINHA, VADUVUR BHARGHAVAN Core Extraction Distributed Ad hoc Routing (CEDAR) Specification, Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-cedar-spec; PRASUN SINHA, RAGHUPATHY SIVAKUMAR, VADUVUR BHARGHAVAN CEDAR: A Core-Extraction Distributed Ad Hoc Routing Algorithm, The 18th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM '99 New York, NY, USA, pp. 202–209 IEEE, March 1999
• FSR (Fisheye State Routing protocol) – MARIO GERLA, GUANGYU PEI, XIAOYAN HONG, TSU-WEI CHEN Fisheye State Routing Protocol (FSR) for Ad Hoc Networks Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-fsr, work in progress, June 2001. (see http://wiki.uni.lu/secan-lab/Fisheye+State+Routing.html)

Backpressure Routing

This type of routing does not pre-compute paths. It chooses next-hops dynamically as a packet is in progress toward its destination. These decisions are based on congestion gradients of neighbor nodes. When this type of routing is used together with max-weight link scheduling, the algorithm is throughput-optimal. See further discussion here: Backpressure Routing

Backpressure Routing

This article describes backpressure routing forqueueing networks. It shows how the algorithm is derived and how its optimality is establishedusing concepts of Lyapunov drift....

.

Host Specific Routing protocols

This type of protocols requires thorough administration to tailor the routing to a certain network layout and a distinct flow strategy. The main disadvantages of such algorithms are:

1. Advantage depends on quality of administration addressing scheme.
2. Proper reaction to changes in topology demands reconsidering all parametrizing.

• LANMAR (Landmark Routing Protocol for Large Scale Networks) – MARIO GERLA, XIAOYAN HONG, LI MA, GUANGYU PEI Landmark Routing Protocol (LANMAR) Internet Draft, http://tools.ietf.org/html/draft-ietf-manet-lanmar-05, work in progress, June 2001.

Power-aware routing protocols

Energy required to transmit a signal is approximately proportional to d, where d is the distance and is the attenuation factor or path loss exponent, which depends on the transmission medium.
When (which is the optimal case), transmitting a signal half the distance requires one fourth of the energy and if there is a node in the middle willing to spend another fourth of its energy for the second half, data would be transmitted for half of the energy than through a direct transmission – a fact that follows directly from the inverse square law of physics.

The main disadvantages of such algorithms are:

1. This method induces a delay for each transmission.
2. No relevance for energy network powered transmission operated via sufficient repeater infrastructure.

Multicast routing

• MRMP
  MRMP
  MRMP is a power-aware multicast protocol designed for large-scale mobile ad hoc networks, in which nodes may be with high mobility....
  
   (Maximum-Residual Multicast Protocol) – Pi-Cheng Hsiu and Tei-Wei Kuo: "A Maximum-Residual Multicast Protocol for Large-Scale Mobile Ad Hoc Networks", IEEE Transactions on Mobile Computing, 2009 Available from: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4796204
• EraMobile (Epidemic-based Reliable and Adaptive Multicast) – Zulkuf Genc and Oznur Ozkasap: "EraMobile: Epidemic-based Reliable and Adaptive Multicast for MANETs", In Proc. of the Wireless Communications and Networking Conference (WCNC), Hong Kong, China, March 2007. Available from: http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=4224245&arnumber=4225046&count=810&index=800
• PUMA (Protocol for Unified Multicasting Through Announcements) – Vaishampayan, Ravindra. and Garcia-Luna-Aceves, J.J.: " Efficient and Robust Multicast Routing in Mobile Ad Hoc Networks", In 2004 IEEE International Conference on Mobile Ad hoc and Sensor Systems, pages 304- 313, Fort Lauderdale, FL, October 2004. Available from: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1392169. A NS-2 implementation by Sidney Doria is available in: .
• AMRIS (Ad hoc Multicast Routing protocol utilizing Increasing id-numberS) – Chun Wei Wu and Yong Chiang Tay: "AMRIS: A Multicast Protocol for Ad Hoc Wireless Networks", In Proc. of the IEEE Military Communications Conference (MILCOM), pages 25 – 29, Atlantic City, NJ, November 1999.
• LAM (Lightweight Adaptive Multicast) – Lusheng Ji and M. Scott Corson: "A Lightweight Adaptive Multicast Algorithm", In Proc. of the IEEE Global Telecommunications Conference (Globecom), pages 1036 – 1042, Sydney, Australia, November 1998.

Geographical multicast protocols (Geocast

Geocast

Geocast refers to the delivery of information to a group of destinations in a network identified by their geographical locations. It is a specialized form of multicast addressing used by some routing protocols for mobile ad hoc networks....

ing)

• MOBICAST (Mobile Just-in-time Multicasting) – Q. Huang, C. Lu and G-C. Roman, Mobicast: Just-in-time multicast for sensor networks under spatiotemporal constraints, Lecture Notes in Computer Science, Vol 2634, pages 442–457
• Abiding Geocast / Stored Geocast
  Abiding Geocast / Stored Geocast
  Abiding Geocast is a time stable geocast scheme used in ad hoc networks or in cellular networks. Messages are delivered to all nodes that are inside a destination region within a certain period of time...
  
   (Time Stable Geocasting) – C. Maihöfer, T. Leinmüller, E. Schoch: Abiding Geocast: Time-Stable Geocast for Ad Hoc Networks, Second ACM International Workshop on Vehicular Ad Hoc Networks (VANET 2005), Cologne, Germany, September 2, 2005

Other protocol classes

• IMEP (Internet Manet Encapsulation Protocol) – M. S. CORSON, S. PAPADEMETRIOU, P. PAPADOPOULOS, V. PARK, A. QAYYUM INTERNET MANET ENCAPSULATION PROTOCOL (IMEP) SPECIFICATION, Internet Draft http://tools.ietf.org/html/draft-ietf-manet-imep-spec
• W2LAN (Wireless to LAN Protocol) – W2LAN: protocol that transforms a 802.11 mobile Ad hoc network (MANET) into an Ethernet LAN, CIIT2004, International Conference on Communications, Internet & Information Technology, pp. 317–320, ISBN 0-88986-445-4.

External links

This is a list of existing definitions or even implementations of Ad hoc network routing protocols.
These are links to code that can combine inexpensive commercial radios

WIFI

WIFI is a radio station broadcasting a brokered format. Licensed to Florence, New Jersey, USA, the station is currently operated by Florence Broadcasting Partners, LLC.This station was previously owned by Real Life Broadcasting...

 with inexpensive computers to form self-organizing radio-based network systems

Manet

-MANET as an abbreviation:*MANET is a mobile ad hoc network, a self-configuring mobile wireless network.*MANET database or Molecular Ancestry Network, bioinformatics database-People with the surname Manet:*Édouard Manet, a 19th-century French painter....

:

• AODV
  • Ad hoc Support Library and AODV-UIUC, http://aslib.sourceforge.net
  • UoB-JAdhoc – Java based multi-platform implementation, http://www.aodv.org
  • UoBWinAODV – Microsoft Windows based implementation, http://www.aodv.org
• DSR
  • DSR-UU, http://core.it.uu.se/adhoc
  • picoNet – DSR implementation, http://piconet.sourceforge.net/
  • Monarch implementation of DSR, http://www.monarch.cs.rice.edu/dsr-impl.html
  • UC Boulder implementation of DSR, http://pecolab.colorado.edu/DSR.html
• OLSR
• MAODDP
  • On-Demand Routing in Mobile Ad Hoc Network,gesj.internet-academy.org.ge/download.php?id=1634.pdf&t=1

• MISC
  • Authenticated Routing for Ad Hoc Networks (ARAN) (based on Ad Hoc Support Library) http://prisms.cs.umass.edu/arand/
  • ResNet - AORP implementation, http://www.seasdtc.com/events/2010_conference/downloads/pdf/communications_and_control/a13_%28cc022%29.pdf
  • babeld, the reference implementation of Babel
    Babel (protocol)
    The Babel routing protocol is a distance-vector routing protocol for Internet Protocol packet-switched networks that is designed to be robust and efficient on both wireless mesh networks and wired networks....
    
    
  • CUWiN implementation of HSLS
    Hazy Sighted Link State Routing Protocol
    The Hazy-Sighted Link State Routing Protocol is a wireless mesh network routing protocol being developed by the CUWiN Foundation. This is an algorithm allowing computers communicating via digital radio in a mesh network to forward messages to computers that are out of reach of direct radio contact...
    
    for NetBSD http://cuwireless.net/download
  • DYMO, http://sourceforge.net/projects/dymoum/
  • LQSR, http://research.microsoft.com/mesh/
  • LUNAR http://cn.cs.unibas.ch/projects/lunar/