A clustering scheme for hierarchical control in multi-hop wireless networks

Abstract

In this paper we present a clustering scheme to create a hier- archical control structure for multi-hop wireless networks. A cluster is de- finedas a subset of vertices, whose induced graph is connected. In addition, a cluster is required to obey certain constraints that are useful for manage- ment and scalability of the hierarchy. All these constraints cannot be met simultaneously for general graphs, but we show how such a clustering can be obtained for wireless network topologies. Finally, we present an efficient distributed implementation of our clustering algorithm for a set of wireless nodes to create the set of desired clusters. Keywords—Clustering, Ad-hoc networks, Wireless networks, Sensor net- works, Hierarchy I. INTRODUCTION APID 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 com- prising of a large number of such small devices. In the Smart Dust project at UC Berkeley (1) and the Wireless Integrated Net- work Sensors (WINS) project 1 at UCLA researchers are at- tempting to create a wireless technology, where a large number of mobile devices, with wireless communication capability, can be rapidly deployed and organized into a functional network. Hierarchical structures have been used to provide scalable so- lutions in many large networking systems that have been de- signed (2), (3). For networks composed of a large number of small, possibly mobile, wireless devices, a static manual config- uration would not be a practical solution for creating such hi- erarchies. In this paper, we focus on the mechanisms required for rapid self-assembly of a potentially large number of such de- vices. More specifically , we present the design and implementa- tion of an algorithm that can be used to organize these wireless nodes into clusters with a set of desirable properties. Typically, each cluster in the network, would select a "cluster - representative" that is responsible for cluster management — this responsibility is rotated among the capable nodes of the clus- ter for load balancing and fault tolerance.