Stefan Rührup

Research Interests

Geographic Routing in Wireless Networks

Geographic routing (also called position-based routing) uses positioning capabilites (e.g. GPS 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.

Alternative Planarization Methods

For planarization 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.

Beaconless Geographic Routing

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 Networks

Highly mobile networks with low node density are only sporadically 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 Schindelhauer: DT-DYMO: Delay-tolerant Dynamic MANET On-demand Routing, 3rd IEEE International Workshop on Wireless Mesh and Ad Hoc Networks (WiMAN'09), June 2009.

Network Simulation

Simulation with OMNet++

For the simulation of wireless networks we use OMNet++, a public-source simulation environment. 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).

OMNett++ screenshot

Simulation of the Cell-based Geographic Forwarding Protocol [PDF], a geographic routing algorithm based on implicit clustering, with OMNet++

Simulation with SAHNE

SAHNE (Simulation Environment for 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.

Simulating directional communication with SAHNE