ExOR - Extremely Opportunistic Routing: Difference between revisions

From
Jump to navigation Jump to search
Line 29: Line 29:


=== Selecting a Forwarding Set ===
=== Selecting a Forwarding Set ===

A Forwarding Set is a list of all potential forwarding nodes. Each node of the network creates such a list to decide where it should send its data packets.
Therefor it first identifies the shortest path to the destination, breaking ties between equally short paths using information
from the delivery ratio matrix. The priority in this list is given as the first node in this path is the highest priority candidate.
This set of nodes is cached until there is any update from the Delivery-Ratio matrix. In this way the process guarantees, that it will adept to all changes within the network.


=== Sending Acknowledgements ===
=== Sending Acknowledgements ===

Revision as of 14:16, 26 July 2007

Description

Extremely Opportunistic Routing is a Routing algorithm that takes advantage of the characteristics of wireless networks. Therefor ExOR determines the path as the packet moves through the network instead of choosing a single route ahead of time. Through this improvement the performance in wireless networks will increase significantly.

Implementation

What is neccesary to implement such a routing protocol?

First the standard MAC Protocol has to be modified. And in second every node needs a Delivery-Ratio-Matrix to decide which node would be the best receiver.

Modified MAC Protocol

The standard MAC Protocol is used to define the format for data transmission. Therefor its frame has several partitions.

Mac-protocol.jpg

The ExOR algorithm needs to improve the current MAC - Protocol as it changes the single destination and acknowledgement partition into a n-slot partition. E.G. the network where ExOR will be implemented needs a 3 candidate list, there will be 3 destination slots and 3 acknowledgement slots like it is shown in the picture.

Delivery - Ratio MAtrix

The Delivery - Ratio Matrix consists of transmission rates between each node in the network. Consequently every node owns such a matrix. All Values are updated in a specific period of time through a link-state-flooding scheme. Though it is possible to keep up with changes within the network.

The 3 important Stages

Selecting a Forwarding Set

A Forwarding Set is a list of all potential forwarding nodes. Each node of the network creates such a list to decide where it should send its data packets. Therefor it first identifies the shortest path to the destination, breaking ties between equally short paths using information from the delivery ratio matrix. The priority in this list is given as the first node in this path is the highest priority candidate. This set of nodes is cached until there is any update from the Delivery-Ratio matrix. In this way the process guarantees, that it will adept to all changes within the network.

Sending Acknowledgements

Decision

Performance

In comparison to many well-known Routing - algorithms like OSPF,DSR,AODV Opportunistic routing generally performs better than the a margin of 55%. Depending on how large the network is there are improvements of up to 65%. In generell the greatest benefit out of ExOR is its ability to skip intermediate hops.

Number of Transmissions per node pair
Number of used nodes in correlation with distance

The first graphic shows how ExOR reduces the number of Transmissions in a network.

Problems

See also

External Links

hotnets-exor

Multi-Channel-Opportunistic Routing

SAR HU ExOR Solutions