Their algorithm
works for weighted dominating set also.
134
Chapter 5 Topology Control for Wireless Sensor Networks
The method proposed by Das et al [57, 76] contains three stages: approximating
the minimum dominating set, constructing a spanning forest of stars,
expanding the spanning forest to a spanning tree. Here the stars are formed
by connecting each dominatee node to one of its dominators. The approximation
method of MDS is essentially a distributed variation of the centralized
Chvatal??™s greedy algorithm [61] for set cover. Notice that the dominating set
problem is essentially the set cover problem which is well-studied. It is then
no surprise that the method by Das et al [57, 76] guarantees an H(??) for the
MDS problem, where H is the harmonic function and ?? is the maximum node
degree.
While the algorithm proposed by Das et al [57, 76] finds a dominating set
and then grows it to a connecting dominating set, the algorithm proposed by
Wu and Li [60, 77] takes an opposite approach. They first find a connecting
dominating set and then prune out certain redundant nodes from the CDS.
The initial CDS C contains all nodes that have at least two non-adjacent
neighbors. A node u is said to be locally redundant if it has either a neighbor
in C with larger ID which dominates all other neighbors of u, or two adjacent
neighbors with larger ID which together dominate all other neighbors of u.
Their algorithm then keeps removing all locally redundant nodes from C.
Pages:
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236