In other words, they call any planar graph containing UDel(V ) a restricted
Delaunay graph. They described a distributed algorithm to construct
an RDG such that at the end of the algorithm, each node u maintains a set
of edges E(u) incident to u. Those edges E(u) satisfy that (1) each edge in
E(u) has length at most one unit; (2) the edges are consistent, i.e., an edge
uv ??? E(u) if and only if uv ??? E(v); (3) the graph obtained is planar; (4) The
graph UDel(V ) is in the union of all edges E(u).
120
Chapter 5 Topology Control for Wireless Sensor Networks
The algorithm works as follows. First, each node u acquires the position
of its 1-hop neighbors N1(u) and computes the Delaunay triangulation
Del(N1(u)) on N1(u), including u itself. In the second step, each node u sends
Del(N1(u)) to all of its neighbors. Let E(u) = {uv | uv ??? Del(N1(u))}. For
each edge uv ??? E(u), and for each w ??? N1(u), if u and v are in N1(w) and
uv 6??? Del(N1(u)), then node u deletes edge uv from E(u).
When the above steps are finished, the resulting edges E(u) satisfy the four
properties listed above. However, unlike the local Delaunay triangulation, the
computation cost and communication cost of each node needed to obtain E(u)
is not optimal within a small constant factor.
2.2 Bounded-Degree Spanners
Besides the sparseness and spanner properties, it is also desirable that the
node degree in the constructed topology is small and bounded from above
by a constant.
Pages:
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209