Academic
Publications
Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks

Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks,10.1007/s11036-006-4469-5,Mobile Networks and Applications,Yu

Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks   (Citations: 22)
BibTex | RIS | RefWorks Download
We propose a novel localized algorithm that constructs a bounded degree and planar spanner for wireless ad hoc networks modeled by unit disk graph (UDG). Every node only has to know its 2-hop neighbors to find the edges in this new structure. Our method applies the Yao structure on the local Delaunay graph [1] in an ordering that are computed locally. This new structure has the following attractive properties: (1) it is a planar graph; (2) its node degree is bounded from above by a positive constant $$19+\lceil\frac{2\pi}{\alpha}\rceil$$ ; (3) it is a t-spanner (given any two nodes u and v, there is a path connecting them in the structure such that its length is no more than $$t\leq {\rm max}\{\frac{\pi}{2},\pi {\rm sin}\frac{\alpha}{2}+1\} $$ Cdel times of the shortest path in the unit disk graph); (4) it can be constructed locally and is easy to maintain when the nodes move around; (5) moreover, we show that the total communication cost is O(n log n) bits, where n is the number of wireless nodes, and the computation cost of each node is at most O(d log d), where d is its 2-hop neighbors in the original unit disk graph. Here Cdel is the spanning ratio of the Delaunay triangulation, which is at most $$\frac{4\sqrt{3}}{9}\pi$$ . And the adjustable parameter α satisfies 0 < α ≤ π/3.
Journal: Mobile Networks and Applications - MONET , vol. 11, no. 2, pp. 161-175, 2006
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...On the other hand, several localized geometrical structures [7]‐ [9] have been proposed to be used as underlying network topologies...
    • ...Such problem has been studied in traditional topology control algorithms (without CC) [7]‐[9], [16], [17]...
    • ...the energy consumption of the least energy cost path in �� . Several geometric structures [7]‐[9] have been proved to be energy spanners...

    Ying Zhuet al. Cooperative energy spanners: Energy-efficient topology control in coop...

    • ...To improve the efficiency of geographic routing, which means to shorten the routes, some denser graphs, e.g., planar t-spanners 2 of UDG [33], [34], [35], are proposed as...
    • ...Recently, many researchers [33], [34], [35], [36] focus on the construction of denser graphs, e.g., planar t-spanners of UDG, as the underlying graphs, which makes the GFG routing much more efficient with shorter routes...
    • ...To prevent from keeping two graphs in our simulations, each node keeps only one planar graph as the underlying graph for both greedy and face routing, which is the same as several other simulation studies [33], [34], [35]...
    • ...Wang and Li [35] propose a bounded degree planar t-spanner of UDG, which plugs in the work of Li et al. [33] and whose construction needs 2-hop neighborhood information of nodes...

    Yan Sunet al. An Edge-Constrained Localized Delaunay Graph for Geographic Routing in...

    • ...In such applications plane spanners are used as the underlying topologies for efficient unicasting, multicasting, and broadcasting (see [4,5,10,14,15,17,19])...
    • ...Many of the algorithms mentioned above (among others) can be modified to construct bounded-degree plane spanners of UDGs [3,4,11,12] (see also [19])...

    Iyad A. Kanjet al. Improved Local Algorithms for Spanner Construction

    • ...(This assumption is needed only in this section.) To avoid pathologic network topologies (e.g., one in which a node has O(N ) degree), we employ an alternative planarization algorithm developed by Wang and Li [20] that guarantees a bounded degree χ for every node...

    Guang Tanet al. Visibility-Graph-Based Shortest-Path Geographic Routing in Sensor Netw...

    • ...Spanners are fundamental to wireless distributed systems because they represent topologies that can be used for efficient unicasting, multicasting,and/or broadcasting (see [4, 5, 11, 14, 16, 18], to name a few)...
    • ...For these applications, spanners are typically required to be planar because planarity is useful for efficient routing [4, 5, 11, 14, 18]...
    • ...As a matter of fact, many spanner constructions in the literature rely on extracting subgraphs of the Delaunay graph (see for example [4, 11, 15, 16, 18])...
    • ...factor of the Delaunay graph Cdel [4, 11, 15, 16, 18]...

    Shiliang Cuiet al. On the Dilation of Delaunay Triangulations of Points in Convex Positio...

Sort by: