## Keywords (9)

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
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
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »

## Citation Context (12)

• ...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 Zhu, et 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 Sun, et 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. Kanj, et 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 Tan, et 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]...

Sort by:

## Citations (22)

### Survey of local algorithms(Citations: 14)

Published in 2012.

### Hemoglobin A1c as a tool for the diagnosis of type 2 diabetes in 208 premenopausal women with polycystic ovary syndrome

Journal: Fertility and Sterility - FERT STERIL , vol. 96, no. 5, pp. 1275-1280, 2011

### Cooperative energy spanners: Energy-efficient topology control in cooperative ad hoc networks

Conference: IEEE INFOCOM - INFOCOM , pp. 231-235, 2011

### A novel family of geometric planar graphs for wireless ad hoc networks

Conference: IEEE INFOCOM - INFOCOM , pp. 1934-1942, 2011

### P02-464 - The philosophical underpinnings of the Cognitive-Behavioural approach to depression

Journal: European Psychiatry - EUR PSYCHIAT , vol. 26, pp. 1060-1060, 2011