Paper Info
Title
Single-step creation of localized Delaunay triangulations
Abstract
A localized Delaunay triangulation owns the following interesting properties for sensor and wireless ad hoc networks: it can be built with localized information, the communication cost imposed by control information is limited, and it supports geographical routing algorithms that offer guaranteed convergence. This paper presents two localized algorithms, fast localized Delaunay triangulation 1 (FLDT1) and fast localized Delaunay triangulation 2 (FLDT2), that build a graph called planar localized Delaunay triangulation, PLDel, known to be a good spanner of the Unit Disk Graph, UDG. Our algorithms improve previous algorithms with similar theoretical bounds in the following aspects: unlike previous work, FLDT1 and FLDT2 build PLDel in a single communication step, maintaining a communication cost of O(n log n), which is within a constant of the optimal. Additionally, we show that FLDT1 is more robust than previous triangulation algorithms, because it does not require the strict UDG connectivity model to work. The small signaling cost of our algorithms allows us to improve routing performance, by efficiently using the PLDel graph instead of sparser graphs, like the Gabriel or the Relative Neighborhood graphs.
Year
DOI
Venue
2009
10.1007/s11276-007-0078-x
Wireless Networks
Keywords
DocType
Volume
Wireless communication,Routing protocols,Delaunay triangulation
Journal
15
Issue
ISSN
Citations 
7
1022-0038
5
PageRank 
References 
Authors
0.54
21
2
Name
Order
Citations
PageRank
Filipe Araujo121424.63
Luís Rodrigues21015127.25