The heuristic has
four logical stages: first the propagation of larger node ids via floodmax, second
the propagation of smaller node ids via floodmin, third the determination of
clusterheads, and fourth the linking of clusters.
353
Yadi Ma and Maggie Cheng
The first stage uses d rounds of floodmax to propagate the largest node
id in each node??™s d-neighborhood. At the conclusion of the floodmax, the
surviving node ids are the elected cluster heads in the network. The second
stage uses d rounds of floodmin to propagate the smaller node ids that have
not been overtaken, using the values that exist at each node after the first
d rounds. At the conclusion of the floodmin, each node evaluates the round??™s
WINNERs to best determine its clusterhead. At the third stage, three rules
are applied to decide the clusterheads. When the heuristic terminates, a node
either becomes a clusterhead, or is at most d hops away from its cluster head.
The value of d is an input parameter.
This scheme can precisely control the maximum number of hops from a
sensor node to its head, but the performance largely relies on the distribution
of node ids. The optimal case is when the largest node ids are spaced d
distance apart, and the worst case is when the largest node ids are located
at close proximity (one hop away from one another). When nodes with the
largest ids move or die, a large number of clusters need to be reconstructed.
Pages:
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565