Startseite > Publikationen > Publikationen


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

Energy, Congestion and Dilation in Radio Networks.

In: Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures, Winnipeg, Manitoba, Canada, 10. - 13. Aug. 2002


We investigate the problem of path selection in radio networks for a given set of sites in two-dimensional space. For some given static point-to-point communication demand we define measures for congestion, energy consumption and dilation that take interferences between 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 of a set $Vsubseteq REAL^2$. It can be used to upperbound the number of interfering edges. For real-world applications it can be regarded as $Theta(log n)$. A main result of the paper is that a $t$-spanner construction as a communication network allows to approximate the congestion optimal communication network by a factor of $O(g(V)^2)$. Furthermore, we show that there are vertex sets where only one of the performance parameters congestion, energy and dilation can be optimized at a time. We show trade-offs lowerbounding congestion $times$ delay and delay $times$ energy. 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 = {Gr{\"u}newald, Matthias and Meyer auf der Heide, Friedhelm and Schindelhauer, Christian and Volbert, Klaus},
title = {Energy, Congestion and Dilation in Radio Networks},
booktitle = {Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures},
address = {Winnipeg, Manitoba, Canada},
month = {10~-~13~} # aug,
year = {2002},

BibTeX in die Zwischenablage kopieren