It
was also shown in [32, 66, 81] that the constructed CDS is a sparse spanner
in terms of both hops and length with factors 3 and 6, meanwhile CDS has a
bounded node degree max(?„“3, 5 + ?„“2). See [81] for detailed proofs.
4.2 Low-Weight Connected Dominating Set
All of the above methods try to minimize the number of clusterheads, i.e., the
number of nodes in the backbone. However, in many applications of wireless
sensor networks, minimizing the size of the backbone is not su?±cient. For
136
Chapter 5 Topology Control for Wireless Sensor Networks
example, di?®erent sensor nodes may have di?®erent costs for serving as a clusterhead,
due to device di?®erences, power capacities, and information loads to
be processed. Therefore, in this subsection, we assume that each wireless node
u has a generic cost (or weight) c(u). The cost may also represent the fitness
or priority of each node to be a clusterhead. The lower cost means higher
priority. Then a connected dominating set C is called a weighted connected
dominating set (WCDS). A subset C of V is a minimum weighted connected
dominating set (MWCDS) if C is a WCDS with minimum total cost. It is
clear that MWCDS is an NP-hard problem. Guha and Khuller [82] studied
centralized algorithms for a weighted minimum connected dominating set in
general graphs; by combining a weighted set cover approximation algorithm
and a node-weighted Steiner tree approximation algorithm they achieve approximation
ratio 3 ln n.
Pages:
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240