They constructed a counter example to show
that Y Sk(V ) may have large stretch factor.
2.3 Bounded-Degree Planar Spanners
The structures discussed so far either have bounded degree, or are planar, or
are spanners, but none of the structures has all these three properties together.
We then review one recent result [33] that can construct a bounded degree planar
spanner in a localized manner. Their method rigorously combines localized
Delaunay triangulation LDel(2)(V ) and the ordered Yao structure [45].
Algorithm 1 Construct Bounded-Degree Planar Spanner
124
Chapter 5 Topology Control for Wireless Sensor Networks
1. First, compute the planar localized Delaunay triangulation LDel(2)(V )
(using the method in [31] to collect the location information of N2(u)), so
that every node u knows all its neighbors NLDel(2) (u) and its node degree
d(u) in LDel(2)(V ). Assume a synchronized method is used to collect
NLDel(2) (u) for every node u.
2. Build a local order ?? of V as follows: (Every node u initializes ??u = 0,
i.e., unordered.)
a) If node u has ??u = 0 and d(u) ?‰¤ 5, then u queries each node v, from
its unordered neighbors, the current degree d(v). If node u has the
smallest ID among all unordered neighbors v with d(v) ?‰¤ 5, node u
sets
??u = max{??v | v ??? NLDel(2) (u)} + 1,
and broadcasts ??u to its neighbors NLDel(2) (u).
b) If node u receives a message from its neighbor v saying that ??v = k,
it updates its d(u) = d(u) ??’ 1 and also updates the order ??v stored
locally.
Pages:
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216