Back to Search Start Over

Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks.

Authors :
Xiang-Yang Li
Calinescu, Gruia
Peng-Jun Wan
Yu Wang
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]

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