Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Communication Cost
delaunay triangulation
Local Algorithm
Planar Graph
Satisfiability
Topology Control
Wireless Ad Hoc Network
Shortest Path
Unit Disk Graph
Subscribe
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/s1103600644695,Mobile Networks and Applications,Yu
Edit
Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks
(
Citations: 22
)
BibTex

RIS

RefWorks
Download
Yu Wang
,
Xiangyang Li
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 2hop 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 tspanner (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 2hop 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. 161175, 2006
DOI:
10.1007/s1103600644695
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
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: Energyefficient topology control in coop...
...To improve the efficiency of geographic routing, which means to shorten the routes, some denser graphs, e.g., planar tspanners 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 tspanners 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 tspanner of UDG, which plugs in the work of Li et al. [33] and whose construction needs 2hop neighborhood information of nodes...
Yan Sun
,
et al.
An EdgeConstrained 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 boundeddegree 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.
VisibilityGraphBased ShortestPath 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 Cui
,
et al.
On the Dilation of Delaunay Triangulations of Points in Convex Positio...
References
(38)
Routing with Guaranteed Delivery in Ad Hoc Wireless Networks
(
Citations: 15
)
Prosenjit Bose
,
Pat Morin
,
Ivan Stojmenović
,
Jorge Urrutia
Journal:
Wireless Networks  WINET
, vol. 7, no. 6, pp. 609616, 2001
Distributed Spanners with Bounded Degree for Wireless Ad Hoc Networks
(
Citations: 24
)
Yu Wang
,
Xiangyang Li
,
Ophir Frieder
Journal:
International Journal of Foundations of Computer Science  IJFCS
, vol. 14, no. 2, pp. 183200, 2003
Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks
(
Citations: 82
)
Xiangyang Li
,
Gruia Calinescu
,
Pengjun Wan
,
Yu Wang
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 14, no. 10, pp. 10351047, 2003
Constructing Plane Spanners of Bounded Degree and Low Weight
(
Citations: 41
)
Prosenjit Bose
,
Joachim Gudmundsson
,
Michiel H. M. Smid
Conference:
European Symposium on Algorithms  ESA
, pp. 234246, 2002
FaultTolerant and 3Dimensional Distributed Topology Control Algorithms in Wireless Multihop Networks
(
Citations: 113
)
Mohsen Bahramgiri
,
Mohammad Taghi Hajiaghayi
,
Vahab S. Mirrokni
Journal:
Wireless Networks  WINET
, vol. 12, no. 2, pp. 179188, 2006
Sort by:
Citations
(22)
Survey of local algorithms
(
Citations: 14
)
Jukka Suomela
Published in 2012.
Hemoglobin A1c as a tool for the diagnosis of type 2 diabetes in 208 premenopausal women with polycystic ovary syndrome
Line Velling Magnussen
,
Hanne Mumm
,
Marianne Andersen
,
Dorte Glintborg
Journal:
Fertility and Sterility  FERT STERIL
, vol. 96, no. 5, pp. 12751280, 2011
Cooperative energy spanners: Energyefficient topology control in cooperative ad hoc networks
Ying Zhu
,
Minsu Huang
,
Siyuan Chen
,
Yu Wang
Conference:
IEEE INFOCOM  INFOCOM
, pp. 231235, 2011
A novel family of geometric planar graphs for wireless ad hoc networks
Xu Li
,
Nathalie Mitton
,
Isabelle SimplotRyl
,
David SimplotRyl
Conference:
IEEE INFOCOM  INFOCOM
, pp. 19341942, 2011
P02464  The philosophical underpinnings of the CognitiveBehavioural approach to depression
S. Varga
Journal:
European Psychiatry  EUR PSYCHIAT
, vol. 26, pp. 10601060, 2011