In [83], they further improved the approximation
ratio to 1.35 ln n which is the best known ratio.
Recently, many proposed clustering algorithms [79, 84??“90] also considered
di?®erent weights as a priority criterion to decide whether a node will be a
clusterhead. Notice, the ultimate goal of the majority protocols is still to minimize
the size of the cluster (or backbone), not the total weight of the cluster
(or backbone). For example, methods in [79, 86, 89] considered the stability
or mobility of each node as the weight. In [85], a combined weight metric
was considered in their clustering algorithm; it takes into account several system
parameters like the node-degree, transmission power, mobility and the
battery power of the nodes. Most of these proposed weighted clustering algorithms
applied the simple greedy algorithms where the nodes with highest
priority (lowest cost) become clusterheads. For example, the cluster method
in [85] selects a node with the lowest cost among its unchosen neighbors to
serve as a clusterhead. These greedy heuristics work well in practice, but
Wang et al [91] showed that they may generate a backbone with a high cost
compared with the optimum. Some of these methods [87, 88] are randomized
algorithms and nodes become clusterheads randomly with a weighted election
probability. In [84], Turgut proposed a genetic algorithm to optimize cluster
processing. None of these cluster methods guarantee any approximation ratio
of the weighted cluster compared with the optimum.
Pages:
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241