A Clustering Scheme for Hierarchical Routing in Wireless Networks

Abstract

In this paper we present a clustering scheme to create hierarchies for wireless networks. A cluster is defined as a subset of vertices, whose induced graph is connected. In addition, a cluster is required to obey certain constraints that are useful for hierarchical routing. While all these constraints cannot be met simultaneously for general graphs, we show how for wireless network topologies, such a clustering can be obtained. We also present simulation results from a distributed implementation of this scheme to demonstrate its convergence and stability properties.