Startseite > Publikationen > Publikationen


Meyer auf der Heide, Friedhelm;Schindelhauer, Christian;Volbert, Klaus;Grünewald, Matthias:

Congestion, Dilation, and Energy in Radio Networks.

Theory of Computing Systems 37(3): S. 343-370, Mai 2004


We investigate the problem of path selection in radio networks for a given static set of $n$ sites in two- and three-dimensional space. For static point-to-point communication we define measures for congestion, dilation, and energy consumption that take interferences among communication links into account.

We show that energy-optimal path selection for radio networks can be computed in polynomial time. Then we introduce the diversity $g(V)$ of a set $Vsubseteq REAL^ddim$ for any constant $ddim$. It can be used to upper bound the number of interfering edges. For real-world applications it can be regarded as $Theta(log n)$. A main result is that a $c$-spanner construction as a communication network allows one to approximate the congestion-optimal path system by a factor of $O(g(V)^2)$.

Furthermore, we show that there are vertex sets where only one of the performance parameters congestion, dilation, and energy can be optimized at a time. We show trade-offs lower bounding congestion $times$ dilation and dilation $times$ energy. The trade-off between congestion and dilation increases with switching from two-dimensional to three-dimensional space. For congestion and energy the situation is even worse. It is only possible to find a reasonable approximation for either congestion or energy minimization, while the other parameter is at least a polynomial factor worse than in the optimal network.




author = {Meyer auf der Heide, Friedhelm and Schindelhauer, Christian and Volbert, Klaus and Gr{\"u}newald, Matthias},
title = {Congestion, Dilation, and Energy in Radio Networks},
journal = {Theory of Computing Systems},
volume = {37},
number = {3},
pages = {343-370},
month = may,
year = {2004},

BibTeX in die Zwischenablage kopieren