Worst Case Mobility in Ad Hoc Networks

Christian Schindelhauer, Tamás Lukovszki, Stefan Rührup, Klaus Volbert


We investigate distributed algorithms for mobile ad hoc networks for moving radio stations 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 vmax of the radio station, while in the vehicular model we assume a maximum acceleration amax of the points.
Our goal is to maintain persistent routes with nice network properties like hop-distance, energy-consumption, congestions 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 networks needs to adopt changes, i.e. update routing tables, change directory entrees, etc.
We present distributed algorithms based on a gird clustering technique and a high-dimensional representation of the dynamical start situation. 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.