In [91],Wang et al first studied how to approximate the minimum weighted
connected dominating set problem using distributed algorithms. They first
showed that many classical greedy methods [57,61,66,85,90,92] may produce
dominating sets with arbitrarily larger weight than the optimum solution.
Then they proposed a new distributed method of constructing a dominating
set whose total cost is comparable with the optimum solution. Their method
first constructs a maximal independent set (MIS) using node weight as selection
criterion. Then for each node v in MIS, they run a local greedy set
cover method (like in [57, 61, 92]) on local neighborhood N2(v) to find some
nodes GRDYv to cover all one-hop neighbors of v. If GRDYv has a total cost
smaller than v, then they use GRDYv to replace v, which will further reduce
the cost of MIS. In [91], Wang et al proved that their algorithm constructs
137
Yu Wang
a dominating set whose total cost is no more than min(18 logDelta, 4?? + 1)
times the optimum for networks modelled by UDG. Here ?? is the maximum
ratio of costs of two adjacent wireless nodes and ?? is the maximum node
degree in the communication graph. The second step of weighted connected
dominating set formation is to find some connectors (also called gateways)
among all the dominatees to connect the dominators. Their new connector
selection method for a weighted connected dominating set is similar to those
in [32, 66, 81].
Pages:
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242