It was proved in [37] that, if ?± ?‰¤ 5??
6 and the UDG
is connected, then graph G?® is a connected graph. On the other hand, if
?± > 5??
6 , they showed that the connectivity of G?® is not guaranteed by giving
some counter-examples [37].
Note that although the directed graphs ??’??’?†’ Y Gk(V ), ??’??’??’?†’ GY Gk(V ) and ??’??’??’?†’ Y GGk(V )
have a bounded power stretch factor and a bounded out-degree k for each
node, some nodes may have very large in-degrees. The node configuration
given in Figure 3(a) will result in a very large in-degree for node u. Bounded
out-degree gives us advantages when we apply several routing algorithms.
However, unbounded in-degree at node u will often cause large overhead at u.
Therefore it is often imperative to construct a sparse network topology such
that both the in-degree and the out-degree are bounded by a constant while
it is still power-e?±cient.
Sink Structure
Arya et al [7] gave an ingenious technique to generate a bounded degree
graph with constant length stretch factor. In [24], Li et al applied the same
technique to construct a sparse network topology with a bounded degree and
a bounded power stretch factor from ??’??’?†’ Y Gk(V ). The technique is to replace the
122
Chapter 5 Topology Control for Wireless Sensor Networks
directed star consisting of all links toward a node u in ??’??’?†’ Y Gk(V ) by a directed
tree T(u) of a bounded degree with u as the sink.
Pages:
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212