@article{SchindelhauerVolbertZiegler, author = {Schindelhauer, Christian and Volbert, Klaus and Ziegler, Martin}, title = {Geometric spanners with applications in wireless networks}, series = {Computational Geometry: Theory and Applications}, volume = {36}, journal = {Computational Geometry: Theory and Applications}, number = {3}, doi = {10.1016/j.comgeo.2006.02.001}, pages = {197 -- 214}, abstract = {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.}, language = {en} } @inproceedings{RuehrupSchindelhauerVolbert, author = {R{\"u}hrup, Stefan and Schindelhauer, Christian and Volbert, Klaus}, title = {Performance analysis of the hierarchical layer graph for wireless networks}, series = {4th International Conference, ADHOC-NOW 2005, Cancun, Mexico, October 6-8, 2005}, booktitle = {4th International Conference, ADHOC-NOW 2005, Cancun, Mexico, October 6-8, 2005}, publisher = {Springer}, address = {Berlin ; Heidelberg}, isbn = {978-3-540-29132-9}, doi = {10.1007/11561354_21}, pages = {244 -- 257}, abstract = {The Hierarchical Layer Graph (HL graph) is a promising network topology for wireless networks with variable transmission ranges. It was introduced and analyzed by Meyer auf der Heide et al. 2004. In this paper we present a distributed, localized and resource-efficient algorithm for constructing this graph. The qualtiy of the HL graph depends on the domination radius and the publication radius, which affect the amount of interference in the network. These parameters also determine whether the HL graph is a c-spanner, which implies an energy-efficient topology. We investigate the performance on randomly distributed node sets and show that the restrictions on these parameters derived from a worst case analysis are not so tight using realistic settings. Here, we present the results of our extensive experimental evaluation, measuring congestion, dilation and energy. Congestion includes the load that is induced by interfering edges. We distinguish between congestion and realistic congestion where we also take the signal-to-interference ratio into account. Our experiments show that the HL graph contains energy-efficient paths as well as paths with a few number of hops while preserving a low congestion.}, language = {en} } @article{LukovszkiSchindelhauerVolbert, author = {Lukovszki, Tamas and Schindelhauer, Christian and Volbert, Klaus}, title = {Resource efficient maintenance of wireless network topologies}, series = {Journal of Universal Computer Science}, volume = {12}, journal = {Journal of Universal Computer Science}, number = {9}, publisher = {Verlag der Technischen Universit{\"a}t Graz}, doi = {10.3217/jucs-012-09-1292}, pages = {1292 -- 1311}, abstract = {Multiple hop routing in mobile ad hoc networks can minimize energy consumption and increase data throughput. Yet, the problem of radio interferences remain. However if the routes are restricted to a basic network based on local neighborhoods, these interferences can be reduced such that standard routing algorithms can be applied. We compare different network topologies for these basic networks, i.e. the Yao-graph (aka. Θ-graph) and some also known related models, which will be called the SymmYgraph (aka. YS-graph), the SparsY-graph (aka. YY-graph) and the BoundY-graph. Further, we present a promising network topology called the HL-graph (based on Hierarchical Layers). We compare these topologies regarding degree, spanner-properties, and communication features. We investigate how these network topologies bound the number of (uni- and bidirectional) interferences and whether these basic networks provide energy-optimal or congestion-minimal routing. Then, we compare the ability of these topologies to handle dynamic changes of the network when radio stations appear and disappear. For this we measure the number of involved radio stations and present distributed algorithms for repairing the network structure.}, language = {en} } @article{aufderHeideSchindelhauerVolbertetal., author = {auf der Heide, Friedhelm Meyer and Schindelhauer, Christian and Volbert, Klaus and Gr{\"u}newald, Matthias}, title = {Congestion, dilation, and energy in radio networks}, series = {Theory of Computing Systems}, volume = {37}, journal = {Theory of Computing Systems}, number = {3}, publisher = {Springer Nature}, doi = {10.1007/s00224-004-1124-z}, pages = {343 -- 370}, 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 ⫅ ℝ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.}, language = {en} }