Startseite > Publikationen > Publikationen


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

Worst Case Mobility in Ad Hoc Networks.

In: Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03), 2003


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 models.





author = {Schindelhauer, Christian and Lukovszki, Tamás and R{\"u}hrup, Stefan and Volbert, Klaus},
title = {Worst Case Mobility in Ad Hoc Networks},
booktitle = {Proc. of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA03)},
year = {2003},

BibTeX in die Zwischenablage kopieren