The message overhead will be Pn in this phase. After that, when a node
decides which cluster to join, it will inform the clusterhead which will then
broadcast the transmission schedule of all its children. The message overhead
during this phase will be n. The total message overhead will be (Pn + n) in
each round.
In Max-Min, each node propagates node ids for 2d rounds to elect clusterheads.
A converge-cast is then initiated to inform the clusterheads of their
children. Since no node is more than d hops away from its clusterhead, the
converge-cast will be at most d rounds of messages. Altogether, the total message
overhead will be 3dn.
In Forest, during the stage of computing a MDS, each node keeps exchanging
its state information within its 2-hop neighborhood. This would require
each node to broadcast its own information to its one-hop neighbors and relay
information for all its one-hop neighbors. This amounts to (n(??+1)) messages
per round ([18]). After the MDS algorithm terminates, the black nodes form
a virtual graph, then we run the clustering algorithm on the virtual graph.
356
Chpater 14 Performance Comparison of Clustering Schemes
Each ???join??? will take as many as five steps if it is a cluster with level > 0,
or two steps if it is a cluster of level = 0. For a graph of |V | nodes and |E|
edges, the number of messages used is 5|V | log2 |V | + 2|E| ([19]). Therefore
the message overhead in the second phase is 5|V | log2 |V | + 6|E|, where |V |
is the number of black nodes and |E| is the number of edges on the virtual
graph, and each of the |E| virtual edges is at most three wireless hops.
Pages:
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570