First of all one should know WMN specific and main problems witch routing is influenced by:
So, it's time to enumerate different ways and algorithms of solving ploblems mentioned above:
| Protocol |
Idea |
Type |
Metrics |
Year |
| Dynamic Source Routing (DSR) |
"On demand" protocol (without periodic packetes). The basic version of DSR uses explicit "source routing", in which each data packet sent carries in its header the complete, ordered list of nodes through which the packet will pass. Node transmits a "Route Request" as a single local broadcast packet and Each Route Request contains a record listing the address of each intermediate node through which this particular copy of the Route Request has been forwarded. Then routing path is calculated using information from the list of nodes extracted from returned "Route Request" packets. Each node stores a set of routes to the particular node and rediscover them only in case of all routes crash |
Reactive, topology based |
HOP |
2002 |
| Ad hoc On-demand Distance Vector (AODV) |
"On demand" protocol with only active routes maintaining. It uses a simple requet-reply mechanism with signals link breaks for the discovery of routes. Every routing information has a timeout and a sequence number. This ensures freedom of routing loops and avoids "counting to infinity". The data packets are buffered during the route discovery. The source node broadcasts a "Route Request" with several flags, sequence numbers of originator and destination, hopcount. The hopfield contains the distance to the originator. When a node receives a "Route Request", it processes as follows: if this packet was already breceived it is discarded, the hopcount is incremented by 1, personal routes to the source and previous hop are updated, if node is a destination it generates a "Route Reply" otherwise broadcasts a packet. Protocol can do a local repair in case of link failure has happened |
Reactive, topology based |
HOP |
2003 |
| Radio Aware Optimized Link State Routing (RA-OLSR) |
Uses the classical shortest path algorithm based on the hopcount metric. The key consept of OLSR is an optimized broadcast mechanism. Each node select multipoint relays (MPRs) among its neighbors in such a way that 2-hop neighdors receive broadcast messages even if only the MPRs rebroadcast the messages. The forwarding of broadcast messages can significantrly reduce their number. Each node periodically broadcasts hello messages for local topology detection. Every node broadcasts its link stat information through the whole OLSR network by topology control (TC) messages |
Proactive, topology based |
HOP |
1998 |
| Topology Broadcast based on Reverse-Path Forwarding (TBRPF) |
Provides hop-by-hop routing along shortest paths to each destination. Each node running TBRPF computes a source tree (providing paths to all reachable nodes) based on partial topology information stored in its topology table, using a modification of Dijkstra's algorithm. To minimize overhead, each node reports only part of its source tree to neighbors. TBRPF uses a combination of periodic and differential updates to keep all neighbors informed of the reported part of its source tree. Each node also has the option to report additional topology information (up to the full topology), to provide improved robustness in highly mobile networks. TBRPF performs neighbor discovery using "differential" HELLO messages which report only changes in the status of neighbors. This results in HELLO messages that are much smaller than those of other link-state routing protocols such as OSPF |
Proactive, topology based |
|
2004 |
| Open Shortest Path First in Mobile Ad-hoc Networks (OSPF-MANET) |
The advantage of OSPF-MANET is the easy integration of WMNs and MANETs into existing wired OSPF networks. Similarto OLSR the flooding of link state advertisements will be reduced. It concentrates on connected dominating sets (CDS) for the reduction of rebroadcasts |
Proactive, topology based |
|
|
| Fisheye State Routing (FSR) |
It uses "fisheye" concept for a reduction of broadcast messages. The node closer to a node N receive topology information more frequently than faraway nodes. This is done by incrementing the TTL of the mesages for each flood until the maximum value before it continues with the initial, small value |
Proactive, topology based |
|
2000 |
| Hybrid Wireless Mesh Protocol (HWMP) |
HWMP is the default routing protocol for meas networks. THe foundation of HWMP is an adaptation of the reactive routing protocol AODV to layer 2 and to radio-aware metrics. A mesh portal (provides a connection to the outside of the mesh) can be configured to periodically broadcast announcements, which sets up a tree tha allows proactive routing towards this mesh portal. The reactive part follows the general concepts of AODV. It uses the distance vector method and the well-known route discovery process with route request and route reply |
Hybrid, topology based |
ARM |
2006 |
| Greedy Perimeter Stateless Routing (GPSR) |
Packets are forwarded based on the geographical positions of the forwarding node, its neighbors, and the destination. The packet is sent to the neighbor closest to the destination. However, the simple forwarding algorithm may get stuck in a local minimum and cannot reach the destination although a path to the destination exists. Face routing is usually used as a fallback strategy in such a case. The network graph is logically segmented into faces, where the considered links do not cross each other |
Position based |
|
2000 |
| Multi-Radio Link-Quality Source Routing (MR-LQSR) |
This protocol is evolution of DSR. In WMN some degradation in throughput might be expected over five or six hops. MR-LQSR assigns a weight to each link, which is the expected amount of time it would take to successfully transmit a packet of some fixed size on that link. This time depends on the transmission rate of the link and the loss rate. So the path mwtric in MR-LQSR tries to balance the trade-off between throughput and delay |
|
WCETT |
|
Nobody can imagine routing protocol without any metric, thus below there is a set of metrics used:
| Metric |
Idea |
| Hop Count (HOP) |
Provides minimum hop-count routing |
| Per-Hop Round Trip Time (RTT) |
Based on measuring the round trip delay seen by unicast probes between neighboring nodes |
| Per-hop Packet Pair Delay (PktPair) |
Based on measuring the delay between a pair of back-to-back probes to a neighboring node |
| Expected Transmission Count (ETX) |
Estimates the number of retransmissions needed to send unicast packets by measuring the loss rate of broadto send unicast packets by measuring the loss ratcast packets between pairs of neighboring nodes |
| Weighted Cumulative Expected Transmission Time (WCETT) |
It's like ETX multiply by the link bandwidth to obtain the time spent in transmitting the packet |
| Airtime routing metric (ARM) |
It's a default metric. It reflects the amount of channel resources consumed for transmitting a frame over a particular link |