Name
Abstract | ||
|---|---|---|
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 V \subseteq ℝd for any constant d. It can be used to upper bound the number of interfering edges. For real-world applications it can be regarded as Θ(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 × dilation and dilation × 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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/s00224-004-1124-z | Theory Comput. Syst. |
Keywords | Field | DocType |
Medium Access Control,Minimum Span Tree,Communication Link,Unit Energy,Radio Station | Radio broadcasting,Discrete mathematics,Combinatorics,Dilation (morphology),Vertex (geometry),Polynomial,Upper and lower bounds,Time complexity,Energy consumption,Mathematics,Energy minimization | Journal |
Volume | Issue | ISSN |
37 | 3 | 1432-4350 |
Citations | PageRank | References |
20 | 1.06 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Friedhelm Meyer auf der Heide | 1 | 1744 | 238.01 |
| Christian Schindelhauer | 2 | 509 | 58.02 |
| Klaus Volbert | 3 | 141 | 12.50 |
| Matthias Grünewald | 4 | 115 | 10.64 |