Subject: clustering

From: Dmitri Deshun Perkins <[email-masked]>
Date: Mon, 30 Oct 2000 15:55:14 -0500 (EST)

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

---

From: Chip Elliott <[email-masked]>
Date: Mon, 30 Oct 2000 16:38:51 -0500

Hi Dmitri,

At BBN we've done several clustered (hierarchical)
mobile ad hoc networks and have some experience with
how they behave in (a) simulated radio environments,
and (b) actual experiments. The largest real experiment
to date involved about 65 radios in vehicles and
took place out in the Arizona desert in an area of
fairly large hills.

In our networks, all nodes move, and so yes, the
clusterhead may certainly move. Note that it's not such
a great idea to drive your algorithms towards selecting
stationary nodes, if all the other nodes are moving!
What you'd like is some kind of network stability,
so as to hold down the control traffic and # of failed routes,
which means that your clusters should map onto the
underlying structure of the moving radios, if possible.
This is vaguely like trying to select working sets
for paged memory systems...

Most of our networks involve vehicle-based radios,
which generally do not need to worry about power. However
we're still interested in picking clusterheads that
require minimal power in order to communicate with their
members, so as to maximize the overall spatial reuse.
(If everyone whispers, you can get a lot more people in
a room talking at once.) Some of our work, particularly
the power-based DARPA work led by Jason Redi, has had
an explicit goal of power minimization to save battery life.

Choosing good clusterheads is in general as much art as
science, as one is always trying to predict the future:
eg, which node of these N will be the best clusterhead over
the next 10 minutes. That's a hard problem when all the
nodes are moving through some kind of terrain and RF interference
with unpredictable traffic loads!

We've documented some aspects of our networking
protocols and algorithms in papers, typically at MILCOM.
Here's a link you can chase down to find out about
our support for IP multicast routing:

http://www.argreenhouse.com/society/TacCom/papers98/13_03i.pdf

For general background info on our work, and for specific
articles on Jason's power-conservation work, check out:

http://www.jasonredi.com/

Cheers,

Chip Elliott
BBN Technologies

---

From: Joe Macker <[email-masked]>
Date: Mon, 30 Oct 2000 17:10:37 -0500

>highly dynamic network such as a MANET.

These are good questions.

Going back aways if you have not read them see below.. (I assume you may 
have already seen these as they good fundamental pieces of work in this 
area. although there is other work as well)

Special issue of the Proceedings of the IEEE on packet radio networks, vol. 
75, no. 1, Jan. 1987. ...paper by Ephremides et al. uses a backbone of 
clusterheads and gateways. Using simple selection criteria of node number 
ordering.

Another reference, more recent, is ``Multicluster, mobile, multimedia radio 
network,'' by M. Gerla and J. T.-C. Tsai, in Wireless Networks vol. 1, no. 
3, 1995, pp. 255-265.

Both these papers had election algorithms running, with some analysis of 
different techniques.  I believe the results from these previous studies, 
opted for simpler lowest ID clusterhead election schemes, as opposed to 
more complex metric election schemes.

>papers that compare hierarchical versus flat routing.

In general, to address you broader question, I think hierarchical vs. flat 
discussions might need to be quite subjective.  As any flat algorithm has a 
scaling limit, it is obvious that hierarchical can help when that limit is 
reached.  Flat algorithms can have very different scaling limits and 
conditional behaviors.  We would like to understand those limits better so 
more knowledge of individual algorithms would help.

Another argument against clusters, often discussed,  is can overly 
concentrate traffic in dense networks.  CBRP used such clusters to improve 
flooding of control, but not for data forwarding, an interesting hybrid 
with a potential benefit of avoiding some traffic concentration 
problems.  We also used a hybrid approach like that for a NRL mobile 
networking project in the mid-90s that worked reasonably well (more of a 
MAC/subnet layer approach).

Hope these tidbits help,

Joe

---

From: Zygmunt Haas <[email-masked]>
Date: Mon, 30 Oct 2000 18:11:37 -0500 (EST)

Dimitri,

May want to take a look at:

Z.J. Haas and S. Tabrizi, "On Some Challenges and Design Choices in Ad-Hoc
Communications,"IEEE MILCOM'98, Bedford, MA, October 18-21, 1998 

An "older" paper, but still has "some" truth in it ....

Zygmunt.
===-=-====
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas                    tel: +1-607-255-3454
Wireless Networks Laboratory		                  
School of Electrical Engineering         fax: +1-607-255-9072 
Cornell University
323 Frank Rhodes Hall			 e-mail: [email-masked]
Ithaca, NY 14853			 
U.S.A                             http://www.ee.cornell.edu/~haas/wnl.html
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

---

From: Stefano Basagni <[email-masked]>
Date: Mon, 30 Oct 2000 17:30:17 -0600 (CST)

Hi Dmitri,

  here are my two cents ;-) which have a more computer science flavor. 

  A generalization of the algorithms proposed in the 80s by Ephremides
et al. and more recently by Mario Gerla e la sua banda ;-) (more than
the 1995 paper I consider more informative a paper published in JSAC in
1997), has been considered in several papers scattered in several
conferences. (See the bibtex entries below.) The generalization consists
of assigning to each node a generic weight that can be computed in
different way, that may change in time, etc. This weight is intended to
express the suitability of a node for the role of clusterhead. The first
papers on this subject aim at defining a) clustering properties that
have to be satisfied given the specific characteristics of ad hoc nets,
b) a distributed solution that minimize bandwidth usage and energy
consumption at each node, c) a study of both the time and message
complexity of this distributed solution.
 
  The approach in these papers is to determine in a distributed way a
maximal weight independent set (the clusterheads) which is also dominant
(every non-clusterhead node has a clusterhead as neighbor). Of course
this is not the only possible approach, and there have been several
approaches basically based on not considering the independence of the
clusterheads and build a "spine," i.e., a (minimum) connected dominating
set (the clusterheads).

  There is also an "hybrid" solution in which the indipendence property
is partially released in the sense that up to 1 < k <= n clusterheads are
allowed to be neighbors.

  In our approach (the former), it is clear that the determination of
the weight is very important. This is quite an open issue. The only
paper I know about it is being published in the proceedings of Globecom
2000, and the authors are Sajal K. Das, Damla Turgut et. al.   

  Finally, I have heard rumors that in a book soon-to-be released by
Wiley's and Sons ("Ad hoc networks," C. Perkins Ed.) there is a whole
chapter about clustering for ad hoc nets (Martha Steenstrup is the
author).

  Hope this helps, cheers, St.

@article{1,
  author      = "Basagni, S.",
  title       = "A Distributed Algorithm for Finding a Maximal Weighted
                 Independent Set in Wireless Networks",
  journal     = "Telecommunication Systems, Special Issue on Mobile
                 Computing and Wireless Networks",
  editor      = "Stojmenovic, I.",
  year        =  2000,
  note        = "To appear"
}

@inproceedings{2,
  author       = "Basagni, S.",
  title        = "Distributed and Mobility-Adaptive Clustering for
                  Multimedia Support in Multi-Hop Wireless Networks",
  booktitle    = "Proceedings of the IEEE $50$th International
                  Vehicular Technology Conference, VTC 1999-Fall",
  volume       = 2,
  pages        = "889--893",
  address      = "Amsterdam, The Netherlands",
  month        = "September 19--22",
  year         = 1999
}

@inproceedings{3,
  author       = "Basagni, S.",
  title        = "Distributed Clustering for Ad Hoc Networks",
  booktitle    = "Proceedings of the 1999 International Symposium on
                  Parallel Architectures, Algorithms, and Networks
                  ({I-SPAN'99})",
  editor       = "Zomaya, A. Y. and Hsu, D. F. and Ibarra, O. and
                  Origuchi, S. and Nassimi, D. and Palis, M.",
  publisher    = "IEEE Computer Society",
  pages        = "310--315",
  address      = "Perth/Fremantle, Australia",
  month        = "June 23--25",
  year         = 1999
}

--
Stefano Basagni, Ph.D.          Assistant Professor of Computer Science
Center for Advanced Telecommunications Systems and Services     (CATSS)
The University of Texas at Dallas MS EC31          Richardson, TX 75080
Tel. 972 883 2216 ~~~ Fax 972 883 6204 ~~~ E-mail: [email-masked]