List of ad hoc routing protocols

An ad-hoc routing protocol is a convention, or standard, that controls how nodes decide which way to route packets between computing devices in a mobile ad hoc network .

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, a protocol inspired by DSDV with faster convergence and ETX link quality estimation. Free implementation available.
• B.A.T.M.A.N. – Better approach to mobile adhoc networking. RFC Draft: http://tools.ietf.org/html/draft-wunderlich-openmesh-manet-routing-00
• DSDV (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 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 (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 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 – 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 – 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 – 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

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 (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 [1]
• ZRP (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 (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.

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 ${\alpha} \geq 2$ is the attenuation factor or path loss exponent, which depends on the transmission medium. When α = 2 (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 (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: <http://puma-adhoc.cvs.sourceforge.net/puma-adhoc/Puma/>.
• 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 (Geocasting)

• 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 (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 with inexpensive computers to form self-organizing radio-based network systems:

• 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
  • CUWiN implementation of HSLS 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/