Remember that a Gabriel graph is a planar power spanner. To reduce the
total communication cost, Song et al [46] proposed a new method by applying
the ordered Yao structures on a Gabriel graph to bound node degree. The idea
is similar with the above method in [33]. The major di?®erences are in [46]:
(1) they only use one-hop information instead of two-hop information, which
reduces communication cost significantly; (2) they use a Gabriel graph instead
of the localized Delaunay triangulation, which makes the localized method
much simpler and more e?±cient.
The algorithm is as follows. First, each node self-constructs the Gabriel
graph GG locally. Let NGG(u) be the neighbor??™s set of node u in GG. Then,
each node u decides its order ?? locally using the same method in [33]. After
that, all nodes self-form the final topology based on local order ?? as follows.
Initially, all nodes are marked with White color, i.e., unprocessed. Let
NOY GG(u) be the set of neighbors of u in the final topology, which is initialized
as NGG(u). If node u is unprocessed (marked White), and it has the
largest order ??[u] among all its White neighbors in NGG(u), it divides its
transmission range (which is a unit disk centered at the node u) into k equalsized
cones, keeps one nearest White neighbor v ??? NOY GG(u) (if available)
in each cone and deletes others. Node u marks itself Black, i.e., processed,
and notifies all nodes in NGG(u) of the deleted edges through a broadcasting
message UpdateN.
Pages:
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219