Applying Yao structure on UDG(V ) to bound node degree is a very natural
idea. Hereafter, we use ??’??’?†’ Y Gk(V ) to denote ??’??’?†’ Y Gk(UDG(V )). The Yao graph
??’??’?†’ Y Gk(V ) has length stretch factor 1
1??’2 sin ??
k
. Thus, its power stretch factor is
no more than ( 1
1??’2 sin ??
k
)??. Li et al [24] proved a stronger result: the power
stretch factor of the Yao graph ??’??’?†’ Y Gk(V ) is at most 1
1??’(2 sin ??
k )?? .
Li et al [35] also proposed to apply the Yao structure on top of the Gabriel
graph structure (the resulting graph is denoted by ??’??’??’?†’ Y GGk(V )), and apply the
Gabriel graph structure on top of the Yao structure (the resulting graph is
denoted by ??’??’??’?†’ GY Gk(V )). These structures are sparser than the Yao structure
and the Gabriel graph structure and they still have a constant bounded power
stretch factor. These two structures are connected graphs if the UDG is connected,
which can be proved by showing that RNG is a subgraph of both
structures. A similar idea is proposed in the two-phased approach by Wattenhofer
et al [36] which consists of a variation of the ??-graph followed by a
variation of the Gabriel graph.
Li et al [37] proposed a structure that is similar to the Yao structure for
topology control. Each node u finds a power pu,?® such that in every cone
of degree ?± surrounding u, there is some node that u can reach with power
pu,?®. Then the graph G?® contains all edges uv such that u can communicate
with v using power pu,?®.
Pages:
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211