Tree T(u) is constructed
recursively. The algorithm is as follows. First, construct the graph ??’??’?†’ Y Gk(V ).
Each node u will have a set of in-coming nodes I(u) = {v | ??’?†’vu ??? ??’??’?†’ Y Gk(V )}.
For each node u, use the following method (called Tree(u,I(u))) to build tree
T(u). First, node u chooses k equal-sized cones centered at u: C1(u), C2(u),
. . . , Ck(u) to partition the unit disk centered at u. Node u finds the nearest
node yi ??? I(u) in Ci(u), for 1 ?‰¤ i ?‰¤ k, if there is any. Link ??’?†’ yiu is added
to T(u) and yi is removed from I(u). For each cone Ci(u), if I(u) ??© Ci(u) is
not empty, recursively call Tree(yi,I(u) ??© Ci(u)) and add the created edges
to T(u). Figure 4 (a) illustrates a directed star centered at u in ??’??’?†’ Y Gk(V ) and
Figure 4 (b) shows the directed tree T(u) constructed to replace the star with
k = 8. The union of all trees T(u) is called the sink structure ??’??’?†’ Y G??—k(V ).
Notice that node u constructs the tree T(u) and then broadcasts the structure
of T(u) to all nodes in T(u). Since the total number of edges in the Yao
structure is at most k ?· n, where k is the number of cones divided, the total
number of edges of T(u) of all nodes u is also at most k ?· n. Thus, the total
communication cost of broadcasting the T(u) to all its neighbors is still at
most k ?· n.
u u
(a) (b)
Fig. 4. (a) Star - links toward to u. (b) Directed tree T(u) sinked at u.
Pages:
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213