Back to Search
Start Over
Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks.
- Source :
-
IEEE Transactions on Parallel & Distributed Systems . Oct2003, Vol. 14 Issue 10, p1035-1048. 13p. 4 Black and White Photographs, 8 Diagrams, 4 Charts. - Publication Year :
- 2003
-
Abstract
- Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RNG) or Gabriel graph (GG) is used as such planar structure. However, it is well-known that the spanning ratios of these two graphs are not bounded by any constant (even for uniform randomly distributed points). Bose et al. [11] recently developed a localized routing protocol that guarantees that the distance traveled by the packets is within a constant factor of the minimum if Delaunay triangulation of all wireless nodes is used, in addition, to guarantee the delivery of the packets. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we model the network as a unit-disk graph (UDG), in which a link uv exists only if the distance uv is at most the maximum transmission range. In this paper, we present a novel localized networking protocol that constructs a planar 2.5-spanner of UDG, called the localized Delaunay triangulation (LDEL), as network topology. It contains all edges that are both in the unit-disk graph and the Delaunay triangulation of all nodes. The total communication cost of our networking protocol is O(n log n) bits, which is within a constant factor of the optimum to construct any structure in a distributed manner. Our experiments show that the delivery rates of some of the existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. Our simulations also show that the traveled distance of the packets is significantly less when the FACE routing algorithm is applied on LDEL, rather than applied on GG. [ABSTRACT FROM AUTHOR]
- Subjects :
- *WIRELESS communications
*COMPUTER network protocols
*SENSOR networks
Subjects
Details
- Language :
- English
- ISSN :
- 10459219
- Volume :
- 14
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Parallel & Distributed Systems
- Publication Type :
- Academic Journal
- Accession number :
- 11146344
- Full Text :
- https://doi.org/10.1109/TPDS.2003.1239871