Ad hoc routing protocols

The world of ad hoc protocols is evolving very fast and new drafts pop-up all the time. Sadly, drafts are removed and not archived within six months if they are not maintained. This creates a huge problem if you try to get a view of what has done within the field during the latest years. In order to hopefully not reinvent the wheel I tried to compile a list () of the existing protocols.

This section begin with a brief description of how the AODV algorithm work to give a quick introduction to an ad hoc protocol. This is also the protocol we used in the testbed.

Brief description of the AODV algorithm

As many ad hoc routing protocols an AODV-node informs its neighbours about its own existence by constantly sending ``hello messages'' at a defined interval. This enables all nodes to know the status about their neighbours, i.e. if they gone down or moved out of reach.

To resolve a route to another node in the network AODV floods its neighbours with a route request(RREQ). A RREQ contain the senders address, the address of the sought node and the last sequence number received from that node if there exist one. The receiving node checks if it has a route to the specified node. If a route exists and the sequence-number for this is higher than the supplied a new route is found. The node replies to the requesting by sending a route reply (RREP). If on the other hand a route does not exist the receiving node sends a RREQ itself to try to find a route for the requesting node.

If the original node does not receive an answer within a time-limit the node can deduce that the sought node are unreachable. Since the request was sent to all neighbours the node may end up with several routes but they are easily separated by the sequence numbers. nodes along the route keep their routing tables updated as long as traffic flows along the route. If not, the nodes will discard the routing entries after a specified time. To be sure that the route still exists, the sender has to keep the route alive by periodically sending packets. All nodes along the route are responsible for the upstream links which means that a broken link will be discovered by the closest node. This node signal the broken link by sending an error message (RRERR) downstream so that the using nodes can start to search for a new route.

AODV is a pretty simple routing-scheme. It has low overhead and supports multicast, but requires symmetric links. The on-demand structure makes it along with DSR very power efficient as stated by [113].

List of protocols

This is an attempt to assemble a list containing most of the ad hoc protocols found on the Net. It became clear that there were many protocols but no survey over them all. Since drafts are removed from IETF when they are not continually supported I have collected abstracts from drafts I have come across in order to create a small reference. This can be found the Appendix  .

The protocols are sorted based on the type of routing they use. The classic pro-active type updates the routingtables on a regular basis compared to the reactive where they only are updated when requested. The reactive type is very popular in ad hoc networks since they adapt fast which is a key feature. Then there is the hierarchical type which usually combine two or more strategies to create several routing-layers. Routing based on geographical information have also been used but usually requires extra equipment compared to the other protocols. Last of the unicast-protocols' are the power-aware that optimize usage of the power stored in the nodes. And last there are two sections with multicast protocols.

Pro-active: (Table-driven)
CGSR	Clusterhead Gateway Switch Routing protocol [23]
DBF	Distributed Bellman-Ford routing protocol [21]
DSDV	Distance Source Distance Vector routing protocol [19]
DTDV	Higly Dynamic Destination-Sequenced Distance Vector routing protocol [6]
HSLS	Hazy Sighted Link State routing protocol [62]
HSR	Hierarchical State Routing protocol
LCA	Linked Cluster Architecture [60]
MMBDP	Mobile Mesh Border Discovery Protocol [63] ()
MMLDP	Mobile Mesh Link Discovery Protocol  [64] ()
MMRP	Mobile Mesh Routing Protocol [65] ()
OLSR	Optimized Link State Routing Protocol [39] ()
STAR	Source Tree Adaptive routing protocol [9] ()
TBRPF	Topology Broadcast based on Reverse-Path Forwarding routing protocol [40] ()
WRP	Wireless Routing Protocol [22]

Reactive: (On-demand)
ABR	Associativity Based Routing protocol [31] ()
AODV	Ad hoc On Demand Distance Vector routing protocol [4] ()
BSR	Backup Source Routing protocol [32]
DSR	Dynamic Source Routing protocol [41] ()
DSRFLOW	Flow State in the Dynamic Source Routing protocol [43] ()
FORP	Flow Oriented Routing Protocol [34]
LMR	Lightweight Mobile Routing protocol [29]
LUNAR	Lightweight Underlay Network Ad hoc Routing [3] ()
RDMAR	Relative-Distance Micro-discovery Ad hoc Routing protocol [10]
SSR	Signal Stability Routing protocol [33]
TORA	Temporally-Ordered Routing Algorithm routing protocol [28] ()

Hierarchical:
CBRP	Cluster Based Routing Protocol [8] ()
CEDAR	Core Extraction Distributed Ad hoc Routing [51] ()
DDR	Distributed Dynamic Routing Algorithm [35]
GSR	Global State Routing protocol [17]
FSR	Fisheye State Routing protocol [38] ()
HARP	Hybrid Ad Hoc Routing Protocol [36]
HSR	Host Specific Routing protocol [18] ()
LANMAR	Landmark Routing Protocol for Large Scale Networks [7] ()
ZRP	Zone Routing Protocol protocol [24] ()
BRP	Bordercast Resolution Protocol [25] ()
IARP	Intrazone Routing Protocol [26] ()
IERP	Interzone Routing Protocol [27] ()

Geographical:
DREAM	Distance Routing Effect Algorithm for Mobility [44]
GLS(Grid)	Geographic Location Service [46]
LAR	Location-Aided Routing protocol [45]
ZHLS	Zone-Based Hierarchical Link State Routing [61]

Power aware:
ISAIAH	Infra-Structure Aodv for Infrastructured Ad Hoc networks [5]
PARO	Power-Aware Routing Optimization Protocol [37]
PAMAS	PAMAS-Power Aware Multi Access Protocol with Signaling Ad Hoc Networks [52]

Multicast:
ABAM	On-Demand Associativity-Based Multicast [53]
ADMR	Adaptive Demand-Driven Multicast Routing protocol [47] ()
AMRIS	Ad hoc Multicast Routing protocol utilising Increasing id-numbers [13]
AMRoute	Ad hoc Multicast Routing Protocol [12]
CAMP	Core-Assisted Mesh Protocol [14]
CBM	Content Based Multicast [15]
DDM	Differential Destination Multicast [20] ()
FGMP	Forwarding Group Multicast Protocol [54]
LAM	Lightweight Adaptive Multicast protocol [16]
DSR-MB	Simple Protocol for Multicast and Broadcast using DSR [42] ()
MAODV	Multicast Ad hoc On-Demand Distance Vector routing [50] ()
MCEDAR	Multicast CEDAR [55]
MZR	Multicast Zone Routing protocol [48] ()
ODMRP	On-Demand Multicast Routing Protocol [11]
SRMP	Source Routing-based Multicast Protocol [49] ()

Geograpical Multicast (Geocasting):
LBM	Location Based Multicast [56]
GeoGRID	Geographical GRID (see GLS) [57]
GeoTORA	Geographical TORA (see TORA) [58]
MRGR	Mesh-Based Geocast Routing [59]