After clustering, one dominator node can be connected to
many dominatees. However, it is well-known that a dominatee node can only
be connected to at most five dominators in the unit disk graph model. Generally,
it was shown in [66, 80] that for each node (dominator or dominatee),
there are at most a constant number ?„“k < (2k+1)2 of dominators that are at
most k units away. Let V irtG be the graph connecting all pairs of dominators
within at most three hops. As shown in [66], V irtG is connected. Then it is
natural to form a connected dominating set by finding connectors to connect
any pair of dominators if they are connected in V irtG. This strategy is also
adopted by [80]. Notice that, in the approach by Stojmenovic et al [59], they
set any dominatee node as the connector if there are two dominators within
its 2-hop neighborhood. This approach is very pessimistic and results in a
very large number of connectors in the worst case [69]. Instead, Alzoubi et
al [32] suggested looking for only one unique shortest path to connect any
two dominators that are at most three hops away. Wang and Li [66] and Wan
et al [80] discussed in detail some approaches to optimize the communication
cost and the memory cost.
In [32, 66, 81], they proved the number of connectors found by their algorithms
is at most ?„“3 times the minimum and the size of the connected
dominating set found is within a small constant factor of the minimum.
Pages:
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239