A Clustering Scheme for Hierarchical Routing in Wireless Networks
Suman Banerjee, Samir Khuller · University Libraries (University of Maryland) · 2000
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. 1 Introduction Rapid advances in hardware design have greatly reduced cost, size and the power requirements of network elements. As a consequence, it is now possible to envision networks comprising of a large number of such small devices. In the Smart Dust project at UC Berkeley [Ka 99] and the Wireless Integrated Network Sensors (WINS) project at UCLA [WINS] researchers are attempting to create this technology, wher...