RELIABLE CLUSTERING TECHNIQUES FOR LARGE, MOBILE PACKET RADIO NETWORKS.

The authors have proposed a model for studying the problem of clustering in large, mobile packet radio networks (PRNET). It is a dynamic graph model in which the nodes and links fail very often. They have discussed in detail the various objectives that a general clustering algrithm may be required to fulfill and have chosen a subset of these objectives and shown how they are relevant to the PRNET environment. Three algorithms for cluster creation have been proposed each satisfying a different set of objectives. Wherever possible polynomial bounds on the objectives are derived. The authors have also discussed overlapping clusters and how the proposed algorithms can be modified to obtain them. The concept of physical redundancy has been introduced and its use in the creation of reliable clusters is described. Finally, they have given algorithms for the maintenance of clusters, i. e. , maintaining the structure of the hierarchical clustering tree when failures occur.