3.3 Forest Approach
The LEACH approach has a random process that makes it have no control
over the number of clusterheads and the sizes of clusters in each round; the
Max-Min D-Cluster has the limitation that the performance relies on the
distribution of node IDs. Having observed the limitations of the two schemes,
we propose a new clustering scheme Forest, which outperforms the above two
schemes in these two aspects, and is more energy e?±cient in data transmission.
In the Forest Approach, clusters are formed in two stages. First, we compute
a Minimum Dominating Set (MDS) of the sensor network using the
distributed implementation of a greedy algorithm from [18]. At the end of
the first stage, some nodes are elected dominators, others are non-dominators
located at most one hop away from dominators; dominators are 1, 2, or 3
hops away from each other. The dominators form a virtual graph with link
cost equal to the number of hops between each other. In the second stage, a
distributed algorithm will run on the virtual graph to form super clusters.
At the beginning of the second stage, all the black nodes are clusterheads,
and the level of the clusters is zero. To meet the size requirement, clusters
are further joined or split through multiple rounds (splitting is rarely used at
the beginning of the second stage, except in extremely dense networks). At
each round, the nodes in each cluster collaboratively select a minimum weight
outgoing edge and try to merge with the cluster at the other end of the edge.
Pages:
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566