List of ad hoc routing protocols

Last updated

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.

Contents

In ad hoc networks, nodes are not familiar with the topology of their networks. Instead, they have to discover it: typically, a new node announces its presence and listens for announcements broadcast by its neighbors. Each node learns about others 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, 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.

Table-driven (proactive) 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 proactive algorithms are:

On-demand (reactive) routing

This type of protocol 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 on-demand algorithms are:

Hybrid (both proactive and reactive) routing

This type of protocol combines the advantages of proactive and 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 of one or the other method requires predetermination for typical cases. The main disadvantages of such algorithms are:

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

Examples of hybrid algorithms are:

Hierarchical routing protocols

With this type of protocol the choice of proactive and of reactive routing depends on the hierarchic level in which 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:

See also

Related Research Articles

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the other being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

Wireless mesh network

A wireless mesh network (WMN) is a communications network made up of radio nodes organized in a mesh topology. It can also be a form of wireless ad hoc network.

Optimized Link State Routing Protocol IP routing protocol optimized for mobile ad hoc networks

The Optimized Link State Routing Protocol (OLSR) 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 (TC) messages to discover and then disseminate link state information throughout the mobile ad hoc network. Individual nodes use this topology information to compute next hop destinations for all nodes in the network using shortest hop forwarding paths.

Ad hoc On-Demand Distance Vector (AODV) Routing is a routing protocol for mobile ad hoc networks (MANETs) and other wireless ad hoc networks. It was jointly developed on July 2003 in Nokia Research Center, University of California, Santa Barbara and University of Cincinnati by C. Perkins, E. Belding-Royer and S. Das.

Zone Routing Protocol, or ZRP is a hybrid Wireless Networking routing protocol that uses both proactive and reactive routing protocols when sending information over the network. ZRP was designed to speed up delivery and reduce processing overhead by selecting the most efficient type of protocol to use throughout the route.

Dynamic Source Routing (DSR) is a routing protocol for wireless mesh networks. It is similar to AODV in that it forms a route on-demand when a transmitting node requests one. However, it uses source routing instead of relying on the routing table at each intermediate device.

The OrderOne MANET Routing Protocol is an algorithm for computers communicating by digital radio in a mesh network to find each other, and send messages to each other along a reasonably efficient path. It was designed for, and promoted as working with wireless mesh networks.

The Hazy-Sighted Link State Routing Protocol (HSLS) 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. Its network overhead is theoretically optimal, utilizing both proactive and reactive link-state routing to limit network updates in space and time. Its inventors believe it is a more efficient protocol to route wired networks as well. HSLS was invented by researchers at BBN Technologies.

Delay-tolerant networking (DTN) is an approach to computer network architecture that seeks to address the technical issues in heterogeneous networks that may lack continuous network connectivity. Examples of such networks are those operating in mobile or extreme terrestrial environments, or planned networks in space.

Destination-Sequenced Distance-Vector Routing (DSDV) 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. Each entry in the routing table contains a sequence number, the sequence numbers are generally even if a link is present; else, an odd number is used. The number is generated by the destination, and the emitter needs to send out the next update with this number. Routing information is distributed between nodes by sending full dumps infrequently and smaller incremental updates more frequently.

In wireless networking, On-Demand Multicast Routing Protocol is a protocol for routing multicast and unicast traffic throughout Ad hoc wireless mesh networks.

6LoWPAN is an acronym of IPv6 over Low-Power Wireless Personal Area Networks. 6LoWPAN is the name of a concluded working group in the Internet area of the IETF.

A wireless ad hoc network (WANET) or mobile ad hoc network (MANET) is a decentralized type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points in wireless networks. Instead, each node participates in routing by forwarding data for other nodes, so the determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.

The Multipath On-demand Routing (MOR) protocol is a protocol to connect nodes in wireless sensor networks. It is an ad hoc routing protocol which is reactive or on-demand, meaning that it establishes routes as needed. The advantage of this approach is obvious if only a few routes are needed, since the routing overhead is less compared to the proactive approach of establishing routes whether or not they are needed. The disadvantage of on-demand establishment of routes is that connections take more time if the route needs to be established.

B.A.T.M.A.N. Routing protocol for multi-hop mobile ad hoc networks

The Better Approach to Mobile Ad-hoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR).

Routing in delay-tolerant networking concerns itself with the ability to transport, or route, data from a source to a destination, which is a fundamental ability all communication networks must have. Delay- and disruption-tolerant networks (DTNs) are characterized by their lack of connectivity, resulting in a lack of instantaneous end-to-end paths. In these challenging environments, popular ad hoc routing protocols such as AODV and DSR fail to establish routes. This is due to these protocols trying to first establish a complete route and then, after the route has been established, forward the actual data. However, when instantaneous end-to-end paths are difficult or impossible to establish, routing protocols must take to a "store and forward" approach, where data is incrementally moved and stored throughout the network in hopes that it will eventually reach its destination. A common technique used to maximize the probability of a message being successfully transferred is to replicate many copies of the message in hopes that one will succeed in reaching its destination.

Vehicular Reactive Routing protocol (VRR) is a reactive routing protocol with geographical features which is specifically designed for Wireless Access for the Vehicular Environment (WAVE) standard in Vehicular ad hoc Networks (VANETs). The protocol takes advantages of the multichannel scheme defined in WAVE and uses the Control Channel (CCH) for signalling, and relies on one of the multiple Service Channels (SCHs) for payload data dissemination.

IEEE 802.11s is a wireless local area network (WLAN) standard and an IEEE 802.11 amendment for mesh networking, defining how wireless devices can interconnect to create a wireless LAN mesh network, which may be used for relatively fixed topologies and wireless ad hoc networks. The IEEE 802.11s task group drew upon volunteers from university and industry to provide specifications and possible design solutions for wireless mesh networking. As a standard, the document was iterated and revised many times prior to finalization.

The Hybrid Wireless Mesh Protocol (HWMP), part of IEEE 802.11s, is a basic routing protocol for a wireless mesh network. It is based on AODV and tree-based routing. It relies on a Peer Link Management protocol by which each Mesh Point discovers and tracks neighboring nodes. If any of these are connected to a wired backhaul, there is no need for HWMP, which selects paths from those assembled by compiling all mesh point peers into one composite map.

A mobile wireless sensor network (MWSN) can simply be defined as a wireless sensor network (WSN) in which the sensor nodes are mobile. MWSNs are a smaller, emerging field of research in contrast to their well-established predecessor. MWSNs are much more versatile than static sensor networks as they can be deployed in any scenario and cope with rapid topology changes. However, many of their applications are similar, such as environment monitoring or surveillance. Commonly, the nodes consist of a radio transceiver and a microcontroller powered by a battery, as well as some kind of sensor for detecting light, heat, humidity, temperature, etc.

References

[8]

  1. Chai Keong Toh Ad Hoc Mobile Wireless Networks, Prentice Hall Publishers, 2002. ISBN   978-0-13-007817-9
  2. C. Perkins, E. Royer and S. Das: Ad hoc On-demand Distance Vector (AODV) Routing, RFC 3561
  3. David Johnson, David Maltz, Yih-Chun Hu: The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks for IPv4, RFC 4728
  4. Johnson, David B.; Maltz, David A. (1996). "Dynamic Source Routing in Ad Hoc Wireless Networks". Mobile Computing. The Kluwer International Series in Engineering and Computer Science. Vol. 353. pp. 153–181. doi:10.1007/978-0-585-29603-6_5. ISBN   978-0-7923-9697-0.
  5. Djenouri, Djamel; Badache, Nadjib (2009). "On eliminating packet droppers in MANET: A modular solution". Ad Hoc Networks. 7 (6): 1243–1258. doi:10.1016/j.adhoc.2008.11.003.
  6. {B. S. Manoj, R. Ananthapadmanabha and C. S. R. Murthy, "Link life based routing protocol for ad hoc wireless networks," Proceedings Tenth International Conference on Computer Communications and Networks (Cat. No.01EX495), Scottsdale, AZ, USA, 2001, pp. 573-576, doi : 10.1109/ICCCN.2001.956324.}
  7. 1 2 Joa-Ng, M.; i-Tai Lu (1999). "A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks". IEEE Journal on Selected Areas in Communications. 17 (8): 1415–1425. doi:10.1109/49.779923.
  8. C. Siva Ram Murthy and B. S. Manoj, ``Ad hoc Wireless Networks: Architectures and Protocols," Prentice Hall PTR, New Jersey, May 2004.

Further reading