So d(u) represents how many neighbors are not ordered so far.
If node u finds that d(u) ?‰¤ 5 and ??u = 0, it goes to Step 2 (a).
When node u finds that d(u) = 0 and ??u > 0, it can go to step 3.
3. Build structures based on local order ?? as follows: (Initialize all nodes
unprocessed)
a) If an unprocessed node u has the highest local order in its unprocessed
neighbors Nu in LDel(2)(V ), let k be the number of processed
neighbors of u in LDel(2)(V ) (at most 5 since graph LDel(2)(V ) is
planar). Assume that v1, v2, . . . , vk be the processed neighbors of u in
LDel(2)(V ). Node u divides its transmission range into k open sectors
cut by the rays from u to these processed neighbors. Then divide each
sector into a minimum number of open cones of degree at most ?± with
?± ?‰¤ ??/3. For each cone, let s1, s2, . . . , sm be the ordered unprocessed
neighbors of u in NLDel(2) (u). For this cone, node u first adds an edge
usi, where si is the nearest neighbor among s1, s2, . . . , sm. Node u
then tells s1, s2, . . . , sm to add all the edges sjsj+1, 1 ?‰¤ j < m. Node
u marks itself processed, and tells all nodes in NLDel(2) (u) that it is
processed.
b) If an unprocessed node v receives a message for adding edge vv??? from
its neighbor u, it adds edge vv???.
4. When all nodes are processed, the final network topology is denoted by
BPS(V ).
Notice that in the algorithm we use open sectors, which means that in the
algorithm we do not consider adding the edges on the boundaries (any edge
involved previously processed neighbors).
Pages:
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217