In other words, the open cones do
not include any edges uvi. This guarantees the algorithm does not add any
edges to node vi after vi has been processed. This approach bounds the node
degree. In [33], the authors proved that the maximum node degree of the graph
125
Yu Wang
BPS(V ) is at most 19 + ???2??
?® ??‰. For example, when ?± = ??/3, the maximum
node degree is at most 25. Note that the ordering computed by this method is
not a global ordering. Some nodes may have the same order. However, no two
neighboring nodes in LDel(2)(V ) receive the same order. Thus, after all nodes
are ordered, the algorithm will process all nodes. Observe that the algorithm
does not process two neighboring nodes at the same time. Assume that there
are two nodes, say u and v, processed at the same time. Remember that
we process a node only if it has the highest ordering among its unprocessed
neighbors. Thus, nodes u and v must receive the same order, i.e., ??u = ??v,
which is impossible in the ordering method. In [33], the authors also proved
that graph BPS(V ) is a planar t-spanner, where t = max{??
2 , ?? sin ?®
2 +1}?·Cdel.
Hereafter, we use Cdel to denote the length stretch factor of the Delaunay
triangulation. The proofs of the planar and spanner properties are much more
complex; refer to [33] for details. In addition, Algorithm 1 uses at most O(n)
messages, where each message has O(log n) bits. However, the hidden constant
could be as high as several hundreds since the method needs to collect the
2-hop information for every node.
Pages:
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218