The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 4
Back to Result List

Congestion, dilation, and energy in radio networks

  • 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 ⫅ ℝ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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Friedhelm Meyer auf der Heide, Christian Schindelhauer, Klaus VolbertORCiD, Matthias Grünewald
DOI:https://doi.org/10.1007/s00224-004-1124-z
Parent Title (English):Theory of Computing Systems
Publisher:Springer Nature
Document Type:Article
Language:English
Year of first Publication:2004
Release Date:2022/12/02
Tag:Communication Link; Medium Access Control; Minimum Span Tree; Radio Station; Unit Energy
Volume:37
Issue:3
First Page:343
Last Page:370
Institutes:Fakultät Informatik und Mathematik
Publication:Externe Publikationen
research focus:Information und Kommunikation
Licence (German):Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG