TY - JOUR A1 - Schindelhauer, Christian A1 - Volbert, Klaus A1 - Ziegler, Martin T1 - Geometric spanners with applications in wireless networks JF - Computational Geometry: Theory and Applications N2 - 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. Y1 - 2007 U6 - https://doi.org/10.1016/j.comgeo.2006.02.001 VL - 36 IS - 3 SP - 197 EP - 214 ER - TY - CHAP A1 - Rührup, Stefan A1 - Schindelhauer, Christian A1 - Volbert, Klaus T1 - Performance analysis of the hierarchical layer graph for wireless networks T2 - 4th International Conference, ADHOC-NOW 2005, Cancun, Mexico, October 6-8, 2005 N2 - 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. KW - Wireless Network KW - Transmission Range KW - Topology Control KW - Leader Election KW - Unit Disk Graph Y1 - 2005 SN - 978-3-540-29132-9 SN - 978-3-540-32086-9 U6 - https://doi.org/10.1007/11561354_21 SP - 244 EP - 257 PB - Springer CY - Berlin ; Heidelberg ER - TY - JOUR A1 - Lukovszki, Tamas A1 - Schindelhauer, Christian A1 - Volbert, Klaus T1 - Resource efficient maintenance of wireless network topologies JF - Journal of Universal Computer Science N2 - 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. KW - ad hoc networks KW - topology control KW - distributed algorithms Y1 - 2006 U6 - https://doi.org/10.3217/jucs-012-09-1292 VL - 12 IS - 9 SP - 1292 EP - 1311 PB - Verlag der Technischen Universität Graz ER - TY - JOUR A1 - auf der Heide, Friedhelm Meyer A1 - Schindelhauer, Christian A1 - Volbert, Klaus A1 - Grünewald, Matthias T1 - Congestion, dilation, and energy in radio networks JF - Theory of Computing Systems N2 - 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. KW - Medium Access Control KW - Minimum Span Tree KW - Communication Link KW - Unit Energy KW - Radio Station Y1 - 2004 U6 - https://doi.org/10.1007/s00224-004-1124-z VL - 37 IS - 3 SP - 343 EP - 370 PB - Springer Nature ER -