ALCOMFT-TR-03-125

Christian Schindelhauer, Tamás Lukovszki, Stefan Rührup and Klaus Volbert
Worst Case Mobility in Ad Hoc Networks
Paderborn. Work package 2. December 2003.

Abstract: We investigate distributed algorithms for mobile ad hoc networks for moving radio stations with adjustable transmission power in a worst case scenario. We consider two models to find a reasonable restriction on the worst-case mobility. In the pedestrian model we assume a maximum speed v_max of the radio stations, while in the vehicular model we assume a maximum acceleration a_max of the points. Our goal is to maintain persistent routes with nice communication network properties like hop-distance, energy-consumption, congestion and number of interferences. A route is persistent, if we can guarantee that all edges of this route can be uphold for a given time span \Delta, which is a parameter denoting the minimum time the mobile network needs to adopt changes, i.e. update routing tables, change directory entries, etc. This \Delta can be used as the length of an update interval for a proactive routing scheme. We extend some known notions such as transmission range, interferences, spanner, power spanner and congestion to both mobility models and introduce a new parameter called crowdedness that states a lower bound on the number of radio interferences. Then we prove that a mobile spanner hosts a path system that polylogarithmically approximates the optimal congestion. We present distributed algorithms based on a grid clustering technique and a high-dimensional representation of the dynamical start situation which construct mobile spanners with low congestion, low interference number, low energy-consumption, and low degree. We measure the optimality of the output of our algorithm by comparing it with the optimal choice of persistent routes under the same circumstances with respect to pedestrian or vehicular worst-case movements. Finally, we present solutions for dynamic position information management under our mobility mode

Postscript file: ALCOMFT-TR-03-125.ps.gz (146 kb).