Geographic Routing in Wireless
Geographic routing (also called position-based routing) uses
receiver) for routing packets. It is based on the assumptions that the
nodes can determine their own positions, know the positions of the
neighbors and that the source knows the position of the destination.
With this information a node can forward a message to the neighboring
node that minimizes the distance to the destination. This local
decision strategy is called greedy forwarding. This strategy
fails, if the routed packet gets stuck in a local minimum. In this case
a recovery strategy is applied to find a way out of the dead
end. Known recovery strategies guide the packet around this region
by traversing the edges along the incident face of the communication
graph. Such strategies require a planarization (i.e. the local
construction of a plane subgraph) in order to prevent routing loops.
several subgraph constructions have been proposed like neighborhood
graphs or delaunay triangulations. Unfortunately, the planarization
removes edges even if no critical intersection is existing. We propose
a reactive planarization method that removes crossing edges on demand
while preserving structural properties of the network graph.
- Hannes Frey, Stefan Rührup: Paving the Way Towards Reactive Planar
Spanner Construction in Wireless Networks. KiVS, March 2009.
The assumption that the positions of the neighbors is known to the
forwarding node can be fulfilled by a periodic exchange of beacon
messages. But this overhead can be avoided: The so-called beaconless routing algorithms work
without knowing the neighborhood. The basic idea of beaconless greedy
forwarding is as follows: The forwarding node broadcasts the message
(locally) and then a competition among the neighbors begins, where the
best located node may respond first and take over the message. After
that the other neighbors remain silent. While beaconless greedy
protocols are well-established, we propose a beaconless recovery scheme
and prove its efficiency theoretically and in simulations.
- Hanna Kalosha, Amiya Nayak, Stefan Rührup,
Ivan Stojmenović: Select-and-Protest-based
Beaconless Georouting with Guaranteed Delivery in Wireless Sensor
Networks, IEEE INFOCOM, April 2008.
Delay-tolerant Routing in Mobile Ad hoc
Highly mobile networks with low node density are only
connected and require a routing scheme that is capable of storing
packets and forwarding them once a link becomes available. We
investigate ad hoc routing with delay-tolerant networking extentions
such as a store-carry-forward mechanism and delivery probability
estimation. Our extension of the established DYMO protocol is able to
deliver messages even if links are only temporarily available.
- Christian Kretschmer, Stefan Rührup, Christian
Delay-tolerant Dynamic MANET On-demand Routing, 3rd IEEE
International Workshop on Wireless Mesh and Ad Hoc Networks (WiMAN'09),
For the simulation of wireless networks we use OMNet++, a public-source
With OMNet++ we have
simulated position-based routing and delay-tolerant routing protocols
using an IEEE 802.11 MAC
layer (provided by the Mobility Framework or the INET Framework).
Simulation of the Cell-based Geographic Forwarding Protocol [PDF
], a geographic routing algorithm
based on implicit clustering, with OMNet++
Simulation with SAHNE
mobile Ad Hoc Networks) was develped as part of
the Mobile Ad-hoc Networks research project
at University of Paderborn. In this project we investigated topology
control algorithms for directional communication. SAHNE was designed to
provide efficient simulation of directional propagation models and
large scale ad hoc networks.
communication with SAHNE