Each nonclusterhead
node decides which node to be its clusterhead for this round
based on the received signal strength of the advertisements. It then informs
the clusterhead that it will join the cluster. When the clusterhead receives
all the messages, it will broadcast a schedule telling each node in the cluster
when to transmit data. Only during data transmission phase can nodes send
data to the clusterhead. When all the data has been received, the clusterhead
will compress the data into a single stream and send it to the base station.
After a specified period of time, the next round begins with the set-up phase
and goes on as described above.
This scheme has relatively low message overhead, and is energy e?±cient,
as we will see in the simulation. However, it only has a loose control over the
percentage of clusterheads: it guarantees that within every 1
P rounds, every
node has a chance to be a clusterhead, but it has no tight control over the
number of clusterheads and the distance from a sensor to its head in each
round.
3.2 Max-Min D-Cluster Formation
[2] used the concept of minimum d-hop dominating set to construct clusters.
It is proved that the minimum d-hop dominating set problem is NP-complete.
[2] presented a heuristic to form d-clusters in a wireless ad hoc network where
each sensor node is at most d hops away from its cluster head. Clusters are
formed by di?®using node identities along the wireless links.
Pages:
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564