Startseite > Publikationen > Publikationen


Schindelhauer, Christian;Volbert, Klaus;Ziegler, Martin:

Geometric Spanners with Applications in Wireless Networks.

, Submitted for Publication. 2005


In this paper we investigate the relations between spanners, weak spanners, and power spanners in $REAL^ddim$ for any dimension $ddim$ and apply our results to topology control in wireless networks. For $cinREAL$, 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 $C_1$-spanner and a $C_2$-power spanner for appropriate $C_1,C_2$ depending only on $c$ but not on the graph under consideration, we show that the converse is not true: there exists a family of $c_1$-power spanners that are not weak $C$-spanners and also a family of weak $c_2$-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 $(c,delta)$-power spanners where the sum of the $delta$-th powers of the lengths has to be bounded; so $(c,2)$-power spanners coincide with the usual power spanners and $(c,1)$-power spanners are classical spanners. Interestingly, these $(c,delta)$-power spanners form a strict hierarchy where the above results still hold for any $deltageqddim$; some even hold for $delta>1$ while counter-examples exist for $deltadelta$ is not a $(C,delta)$-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.


author = {Schindelhauer, Christian and Volbert, Klaus and Ziegler, Martin},
title = {Geometric Spanners with Applications in Wireless Networks},
note = {Submitted for Publication.},
year = {2005},

BibTeX in die Zwischenablage kopieren