Recently, several algorithms were proposed
with a constant worst case approximation ratio by taking advantage of the
geometry properties of the underlying graph. These methods typically use two
messages similar to IamDominator and IamDominatee, and typically have the
135
Yu Wang
following procedures: a white node claims itself to be a dominator if it has the
smallest ID among all of its white neighbors, if there are any, and broadcasts
IamDominator to its 1-hop neighbors. A white node receiving IamDominator
message marks itself as dominatee and broadcasts IamDominatee to its 1-hop
neighbors. The set of dominators generated by the above method is actually a
maximal independent set. Here, we assume that each node knows the IDs of all
its 1-hop neighbors, which can be achieved by asking each node to broadcast
its ID to its 1-hop neighbors initially. This approach to constructing MIS is
well-known. For example, Stojmenovic et al [59] also used this method to
compute the MIS.
The second step of backbone formation is to find some connectors (also
called gateways) among all the dominatees to connect the dominators. Then
the connectors and the dominators form a connected dominating set. Recently,
Wan, et al [80] proposed a communication e?±cient algorithm to find connectors
based on the fact that there are only a constant number of dominators
within k-hops of any node. The following observation is a basis of several algorithms
for CDS.
Pages:
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238