Journal article
Localized Spanners for Ad Hoc Wireless Networks
Ad-hoc & sensor wireless networks, Vol.9(3-4), pp.305-328
01/01/2010
Abstract
We present a new efficient localized algorithm to construct, for any given quasi-unit disk graph G = (V, E) and any epsilon > 0, a (1 + epsilon)-spanner for G of maximum degree O(1) and total weight O(omega(MST)), where omega(MST) denotes the weight of a minimum spanning tree for V. We further show that similar localized techniques can be used to construct, for a given unit disk graph G = (V, E), a planar C-del(1 + epsilon)(1 + pi/2)-spanner for G of maximum degree O(1) and total weight O (omega(MST)). Here C-del denotes the stretch factor of the unit Delaunay triangulation for V. Both constructions can be completed in O(1) rounds of communication, and require each node to know its own coordinates.
Details
- Title: Subtitle
- Localized Spanners for Ad Hoc Wireless Networks
- Creators
- Mirela Damian - Villanova UniversitySriram V. Pemmaraju - Univ Iowa, Dept Comp Sci, Iowa City, IA 52246 USA
- Resource Type
- Journal article
- Publication Details
- Ad-hoc & sensor wireless networks, Vol.9(3-4), pp.305-328
- Publisher
- Old City Publishing Inc
- ISSN
- 1551-9899
- eISSN
- 1552-0633
- Number of pages
- 24
- Grant note
- CCF-0728909 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 01/01/2010
- Academic Unit
- Computer Science
- Record Identifier
- 9984259414802771
Metrics
2 Record Views