For sensor networks, we can construct LDel(2)(V ), which is guaranteed
to be a planar spanner of UDel(V ), but it is di?±cult to collect the 2-hop
neighbors for every node in O(n) messages. A total communication cost of
a simple broadcast approach to collect 2-hop information is O(m) messages,
where m is the number of edges in UDG(V ) and could be as large as O(n2).
Recently, C?‡alinescu [31] proposed an approach (using O(n) messages total)
which is based on the specific connected dominating set introduced by [32].
Using this approach, we can build LDel(2) in O(n) messages, however the
constant behind it is still large. There was such an algorithm proposed in [33].
In order to reduce the total communication cost to O(n) messages, [27, 28]
do not construct LDel(2)(V ), and they extract a planar graph PLDel(V ) out
of LDel(1)(V ) instead. They provided a novel algorithm to make LDel(1)(V )
planar using linear communications after building it. The final graph still
contains UDel(V ) as a subgraph. Thus, it is a spanner of the unit-disk graph.
For detailed algorithm and proofs, refer to [27, 28].
Restricted Delaunay Graph
Gao et al [29] also proposed another structure, called a restricted Delaunay
graph RDG and showed that it has constant stretch factor properties and can
be maintained locally. A restricted Delaunay graph of a set of points in the
plane is a planar graph and contains all the Delaunay edges with length at
most 1.
Pages:
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208