A dominating set with minimum cardinality is
called a minimum dominating set, denoted by MDS. A connected dominating
set with minimum cardinality is denoted by minimum connected dominating
set (MCDS). A subset of vertices in a graph G is an independent set if for any
pair of vertices, there is no edge between them. It is a maximal independent
set if no more vertices can be added to it to generate a larger independent
set. It is a maximum independent set (MIS) if no other independent set has
more vertices.
4.1 Connected Dominating Set
The structure used to build virtual backbone is usually the connected dominating
set. The problem of finding a minimum CDS for a general network
is proved to be NP-complete [61]. Even for a unit disk graph, such a problem
is also NP-complete [62]. Therefore, many heuristics and approximation
algorithms have been proposed.
Centralized Methods
Guha and Khuller [63] studied approximation of the connected dominating
set problem for general graphs. They gave two di?®erent approaches, both of
which guarantee an approximation ratio of ??(H(??)), where H is the harmonic
function and ?? is the maximum node degree. Their approaches are
for general graphs and thus do not utilize the geometry structure if applied
to wireless sensor networks. One approach is to grow a spanning tree that
includes all nodes. The internal nodes of the spanning tree are selected as
the final connected dominating set.
Pages:
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233