They showed that this algorithm works well in practice when the nodes are
distributed uniformly and randomly, although no theoretical analysis is given
by them either for the worst case or for the average approximation ratio.
However, it was shown by Alzoubi et al [69] that the approximation ratio of
this algorithm could be as large as n
2 .
Stojmenovic et al [59] proposed several synchronized distributed constructions
of a connecting dominating set. In their algorithms, the connecting dominating
set consists of two types of nodes: clusterhead and border-nodes (also
called gateway or connectors elsewhere). The clusterhead nodes are just a
maximal independent set, which is constructed as follows. At each step, all
white nodes which have the lowest rank among all white neighbors are colored
black, and the white neighbors are colored gray. The ranks of the white nodes
are updated if necessary. Here, the following rankings of a node are used in
various methods: the ID only [72, 73], the ordered pair of degree and ID [78],
and an ordered pair of degree and location [59]. After the clusterhead nodes
are selected, border-nodes are selected to connect them. A node is a bordernode
if it is not a clusterhead and there are at least two clusterheads within its
2-hop neighborhood. It was shown by [69] that the worst case approximation
ratio of this method is also n
2 , although it works well in practice.
Clustering with Geometry Property
Notice that none of the above algorithm utilizes the geometry property of
the underlying unit disk graph.
Pages:
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237