Subject: RE: clustering

From: Alan Amis <[email-masked]>
Date: Mon, 30 Oct 2000 18:51:51 -0500

Hi Dmitri,

At UTD we have performed a good amount of research in the area of 
clusterhead election. In our simulations nodes may be static and/or 
mobile. The main criteria for the election algorithm is that no node 
is more than d-hops away from a clusterhead, where d is a programmable 
parameter. This election algorithm is called Max-Min D-Cluster Formation 
and completes in 2d rounds of message exchange. Max-Min uses flooding 
to determine the clusterheads. A paper describing Max-Min can be found 
in the Proceeding of the IEEE INFOCOM 2000.

You are correct that there are many issues that come into play in selecting,

reselecting, or releasing a clusterhead. One as you have pointed out is
power. 
We would like to see all nodes participating in the network consume power at

roughly the same rate. Therefore, it might be necessary to invoke thresholds

governing how long a clusterhead stays a clusterhead before relinquishing
his 
leadership role, clusterheads will consume more power as they do more work. 
Once the leadership role is relinquished we need to insure that the
clusterhead 
will not be re-elected right away. Therefore, you need to instate some sort
of 
load-balancing policy to manage the re-election of clusterheads. This policy

could be based on power, time, number of messages, etc.

Regards,

Alan Amis

-----Original Message-----
From: Dmitri Deshun Perkins [mailto:[email-masked]]
Sent: Monday, October 30, 2000 2:55 PM
To: Dmitri Deshun Perkins
Cc: [email-masked]
Subject: clustering

Hello,

I have read some papers discussing the advantages offered by clustering and
hierarchical routing in static or almost static environments Intuitively, 
one would think some of these ideas may apply to MANETs especially 
environments with a large number of nodes.

However, I am curious to know how practical clustering would be in such a 
dynamic(link failures, node movement, congestion, etc) network.
Specifically, 
how would one select a clusterhead? Assuming all nodes have the ability to 
move at anytime, the clusterhead could possibly move. Does the leader
election 
algorithm elect the node that has been stationary the longest. What if this 
node has the least power? It may not be a good choice? There would seem to
be many other issues related to selecting(and reselecting) a clusterhead in
a 
highly dynamic network such as a MANET.

Your thoughts and feedback on the advantages/disadvantages surrounding
these issues would be greatly appreciated. If this discussion has already
taken place, please direct me to the-mail archives. Feel free to list any
papers that compare hierarchical versus flat routing.

Thanks for your time,
D. Perkins