In each cone, node u checks whether
there are some Black nodes in NSY GG(u) within the same cone:
i. Yes. Node u keeps the closest Black neighbor v ??? NSY GG(u)
among them and deletes all the other links in the cone;
ii. No. Node u keeps a closest White neighbor v ??? NSY GG(u) (if
available) among them and deletes all the other links in the cone.
After processing all k cones, node u marks itself Black, i.e., processed,
then notifies each deleted neighboring node v in GG by a
broadcasting message UpdateN.
b) Once aWhite node v receives the message UpdateN from a neighbor
u in GG, it checks whether it itself is in the nodes set for deleting: if
so, it deletes the sending node u from NSY GG(v), otherwise, marks u
as BLACK in its local list NSY GG(v).
c) Once a Black node v receives the message UpdateN from a neighbor
belonging to NSY GG(v), it checks whether it itself is in the nodes
set for deleting: if so, it deletes the sending node u from NSY GG(v),
otherwise, marks u as BLACK in its local list NSY GG(v).
3. When all nodes are processed, all selected edges {uv|v ??? NSY GG(u)} form
the final network topology, denoted by SY aoGG.
Algorithm 2 further reduces the communication cost during constructing
a degree-bounded planar power spanner to 3n messages, because it does not
demand the local ordering before construction. It also reduces the degree
bound to k, and keeps all other nice properties, except that the theoretical
power stretch factor is relaxed to
???2
??
1??’(2???2 sin ??
k )?? , where k > 8 is an adjustable
parameter.
Pages:
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221