• search hit 8 of 15
Back to Result List

Geometric spanners with applications in wireless networks

  • In this paper we investigate the relations between spanners, weak spanners, and power spanners in for any dimension and apply our results to topology control in wireless networks. For , a c-spanner is a subgraph of the complete Euclidean graph satisfying the condition that between any two vertices there exists a path of length at most c-times their Euclidean distance. Based on this ability to approximate the complete Euclidean graph, sparse spanners have found many applications, e.g., in FPTAS, geometric searching, and radio networks. In a weak c-spanner, this path may be arbitrarily long, but must remain within a disk or sphere of radius c-times the Euclidean distance between the vertices. Finally in a c-power spanner, the total energy consumed on such a path, where the energy is given by the sum of the squares of the edge lengths on this path, must be at most c-times the square of the Euclidean distance of the direct edge or communication link. While it is known that any c-spanner is also both a weak -spanner and a -power spanner for appropriate , depending only on c but not on the graph under consideration, we show that the converse is not true: there exists a family of -power spanners that are not weak C-spanners and also a family of weak -spanners that are not C-spanners for any fixed C. However a main result of this paper reveals that any weak c-spanner is also a C-power spanner for an appropriate constant C. We further generalize the latter notion by considering -power spanners where the sum of the δth powers of the lengths has to be bounded; so ()-power spanners coincide with the usual power spanners and ()-power spanners are classical spanners. Interestingly, these ()-power spanners form a strict hierarchy where the above results still hold for any some even hold for while counter-examples exist for . We show that every self-similar curve of fractal dimension is not a -power spanner for any fixed C, in general. Finally, we consider the sparsified Yao-graph (SparsY-graph or YY) that is a well-known sparse topology for wireless networks. We prove that all SparsY-graphs are weak c-spanners for a constant c and hence they allow us to approximate energy-optimal wireless networks by a constant factor.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Christian Schindelhauer, Klaus VolbertORCiD, Martin Ziegler
DOI:https://doi.org/10.1016/j.comgeo.2006.02.001
Parent Title (English):Computational Geometry: Theory and Applications
Document Type:Article
Language:English
Year of first Publication:2007
Release Date:2022/11/25
Volume:36
Issue:3
First Page:197
Last Page:214
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