Cluster Maintenance in Mobile Ad-hoc Networks

The main contribution of this paper is to propose a new cluster maintenance algorithm and a companion cluster initialization algorithm based on a number of interesting and novel properties of diameter-2 graphs. The initialization algorithm naturally blends into cluster maintenance, showing the unity between these two operations. We refer to our algorithms as tree-based since they depend on a spanning tree maintained at various nodes. Unlike the vast majority of published clustering algorithms, our algorithms are cluster-centric, as opposed to node-centric, and work in the presence of node mobility. Extensive simulation results have shown the effectiveness of our algorithms when compared to other clustering schemes proposed in the literature.Lan Wang received his B.S. and M.S. degrees in computer science from Harbin Engineering University, China in 1992 and 1995, respectively. From 1995 to 1999, he worked as a software engineer at the System Engineering Research Institute of CSSC, Beijing, China. He is currently a PhD student at the Computer Science Department of Old Dominion University.Stephan Olariu received the M.Sc. and Ph.D. degrees in computer science from McGill University, Montreal, Canada in 1983 and 1986, respectively. In 1986 he joined the Computer Science Department at Old Dominion University where he is now a full professor. He has published extensively in various journals, book chapters, and conference proceedings. His research interests include wireless networks and mobile computing, parallel and distributed systems, performance evaluation, and medical image processing. Prof. Olariu serves on the editorial board of several archival journals including IEEE Transactions on Parallel and Distributed Systems, Journal of Parallel and Distributed Computing, International Journal of Foundations of Computer Science, Journal of Supercomputing, International Journal of Computer Mathematics, VLSI Design, and Parallel Algorithms and Applications.