The unit disk graph (UDG) is a widely employed model for the study of wireless networks. In this model, wireless nodes are represented by points in the plane and there is an edge between two points if and only if their Euclidean distance is at most one. A hop spanner for the UDG is a spanning subgraph @math such that for every edge @math in the UDG the topological shortest path between @math and @math in @math has a constant number of edges. The hop stretch factor of @math is the maximum number of edges of these paths. A hop spanner is plane (i.e. embedded planar) if its edges do not cross each other. The problem of constructing hop spanners for the UDG has received considerable attention in both computational geometry and wireless ad hoc networks. Despite this attention, there has not been significant progress on getting hop spanners that (i) are plane, and (ii) have low hop stretch factor. Previous constructions either do not ensure the planarity or have high hop stretch factor. The only construction that satisfies both conditions is due to Catusse, Chepoi, and Vax e s (2010); their plane hop spanner has hop stretch factor at most 449. Our main result is a simple algorithm that constructs a plane hop spanner for the UDG. In addition to the simplicity, the hop stretch factor of the constructed spanner is at most 341. Even though the algorithm itself is simple, its analysis is rather involved. Several results on the plane geometry are established in the course of the proof. These results are of independent interest.
Alzoubi al @cite_6 proposed a distributed algorithm for the construction of a hop spanner for the UDG. Their algorithm integrates the connected dominating set and the local Delaunay graph of @cite_17 to form a backbone for the spanner. Although the backbone is plane, the entire spanner is not. The hop stretch factor of this spanner is at most @math (around @math as estimated in @cite_7 ).
@cite_7 @cite_6 @cite_17
1983502795 2809995963 1766136887 1574233320
We propose a new geometric spanner for static wireless ad hoc networks, which can be constructed efficiently in a localized manner. It integrates the connected dominating set and the local Delaunay graph to form a backbone of the wireless network. Priori arts showed that both structures can be constructed locally with bounded communication costs. This new spanner has these following attractive properties: 1) the backbone is a planar graph, 2) the node degree of the backbone is bounded from above by a positive constant, 3) it is a spanner for both hops and length, 4) it can be constructed locally and is easy to maintain when the nodes move around, and 5) moreover, the communication cost of each node is bounded by a constant. Simulation results are also presented for studying its practical performance. An (α,β)-spanner of an n-vertex graph G = (V,E) is a subgraph H of G satisfying that dist(u, v, H) ≤ α·dist(u, v, G) + β for every pair (u, v) ∈ V ×V, where dist(u,v,G′) denotes the distance between u and v in G′ ⊆ G. It is known that for every integer k ≥ 1, every graph G has a polynomially constructible (2k − 1,0)-spanner of size O(n 1 + 1 k ). This size-stretch bound is essentially optimal by the girth conjecture. Yet, it is important to note that any argument based on the girth only applies to adjacent vertices. It is therefore intriguing to ask if one can “bypass” the conjecture by settling for a multiplicative stretch of 2k − 1 only for neighboring vertex pairs, while maintaining a strictly better multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of k-hybrid spanners, in which non neighboring vertex pairs enjoy a multiplicative k stretch and the neighboring vertex pairs enjoy a multiplicative (2k − 1) stretch (hence, tight by the conjecture). We show that for every unweighted n-vertex graph G, there is a (polynomially constructible) k-hybrid spanner with O(k 2 ·n 1 + 1 k ) edges. This should be compared against the current best (α,β) spanner construction of [5] that obtains (k,k − 1) stretch with O(k ·n 1 + 1 k ) edges. An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs S ×V for a given subset of vertices S ⊆ V referred to here as sources. Spanners in which the distances in S ×V are bounded are referred to as sourcewise spanners. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more). The simplest model of a wireless network graph is the Unit Disk Graph (UDG): an edge exists in UDG if the Euclidean distance between its endpoints is ≤ 1. The problem of constructing planar spanners of Unit Disk Graphs with respect to the Euclidean distance has received considerable attention from researchers in computational geometry and ad-hoc wireless networks. In this paper, we present an algorithm that, given a set X of terminals in the plane, constructs a planar hop spanner with constant stretch factor for the Unit Disk Graph defined by X. Our algorithm improves on previous constructions in the sense that (i) it ensures the planarity of the whole spanner while previous algorithms ensure only the planarity of a backbone subgraph; (ii) the hop stretch factor of our spanner is significantly smaller. Let G(V, E) be an undirected weighted graph with |V| = n, and |E| = m. A t-spanner of the graph G(V, E) is a sub-graph G(V, ES) such that the distance between any pair of vertices in the spanner is at most t times the distance between the two in the given graph. A 1963 girth conjecture of Erdos implies that Ω(n1+1 k) edges are required in the worst case for any (2k - 1)-spanner, which has been proved for k = 1, 2, 3, 5. There exist polynomial time algorithms that can construct spanners with the size that matches this conjectured lower bound, and the best known algorithm takes O(mn1 k) expected running time. In this paper, we present an extremely simple linear time randomized algorithm that constructs (2k - 1)-spanner of size matching the conjectured lower bound. Our algorithm requires local information for computing a spanner, and thus can be adapted suitably to obtain efficient distributed and parallel algorithms.