A small node degree reduces the MAC-level contention and
interference also may help to mitigate the well-known hidden and exposed
terminal problems. Therefore, we now review some bounded degree spanners.
Notice that all of the planar structures mentioned in the previous subsection
do not have bounded node degree. An example of such node configuration is
shown in Figure 3(a) [24].
v
a
v
v1
u
vi
vi+1
a
a
2
v
n-1
n-2
v
u
(a) Unbounded Degree (b) Yao Graph
Fig. 3. (a) Node u has degree (or in-degree) n ??’ 1. (b) Illustration of Yao graph:
bound out-degree by Yao structure. Here k = 8.
Yao Graph and ?µ-graph
The Yao graph [13] with an integer parameter k ?‰? 6, denoted by ??’??’?†’ Y Gk(G), is
defined as follows. At each node u, any k equally-separated rays originated at
u define k cones. In each cone, choose the shortest edge uv among all edges
from u, if there is any, and add a directed link ??’?†’uv (as shown in Figure 3(b)).
Ties are broken arbitrarily. The resulting directed graph is called the Yao
graph. If we add the link ??’?†’vu instead of the link ??’?†’uv, the graph is denoted by
121
Yu Wang
?†???’??’ Y Gk(G), which is called the reverse of the Yao graph. Some researchers used
a similar construction named ??-graph [34, 45], the di?®erence is that, in each
cone, it chooses the edge which has the shortest projection on the angular
bisector of the cone instead of the shortest edge.
Pages:
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210