List of ad hoc routing protocols

From Wikipedia, the free encyclopedia
  (Redirected from Ad hoc protocol list)
Jump to: navigation, search
This article may require copy editing for grammar, style, cohesion, tone, or spelling. You can assist by editing it. (September 2011)

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.

Contents

[edit] 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
  • HSLS The hazy-sighted link-state algorithm. This algorithm is based on empirical and theoretical studies to limit link-state traffic while achieving practical link mobility. It avoids the message flooding of DSR, OLSR and AODV by growing the range of the link-state updates two fold for each two fold expansion of time. It has a practical large network in place at CuWIN.
  • 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

[edit] 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:

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

[edit] 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.

[edit] 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.

[edit] 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:

[edit] 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.

[edit] 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.

[edit] 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.

[edit] 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.

[edit] 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

[edit] 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.

[edit] 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:

Retrieved from "http://en.wikipedia.org/w/index.php?title=List_of_ad_hoc_routing_protocols&oldid=472856238"
Personal tools
Namespaces
Variants
Actions
Navigation
Interaction
Toolbox
Print/export
Languages