INFOCOM 2003Return to Main MenuAn Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks Seema Bandyopadhyay and Edward J. Coyle School of Electrical and Computer Engineering Purdue University West Lafayette, IN, USA {seema, coyle}@ecn.purdue.edu Abstract— A wireless network consisting of a large number of small sensors with low-power transceivers can be an effective tool for gathering data in a variety of environments. The data collected by each sensor is communicated through the network to a single processing center that uses all reported data to determine characteristics of the environment or detect an event. The communication or message passing process must be designed to conserve the limited energy resources of the sensors. Clustering sensors into groups, so that sensors communicate information only to clusterheads and then the clusterheads communicate the aggregated information to the processing center, may save energy. In this paper, we propose a distributed, randomized clustering algorithm to organize the sensors in a wireless sensor network into clusters. We then extend this algorithm to generate a hierarchy of clusterheads and observe that the energy savings increase with the number of levels in the hierarchy. Results in stochastic geometry are used to derive solutions for the values of parameters of our algorithm that minimize the total energy spent in the network when all sensors report data through the clusterheads to the processing center. Keywords- Sensor Networks; Clustering Methods; Voronoi Tessellations; Algorithms. I. INTRODUCTION Recent advances in wireless communications and microelectro-mechanical systems have motivated the development of extremely small, low-cost sensors that possess sensing, signal processing and wireless communication capabilities. These sensors can be deployed at a cost much lower than traditional wired sensor systems. The Smart Dust Project at University of California, Berkeley [14, 15, 16] and WINS Project at UCLA [1, 17], are two of the research projects attempting to build such low-cost and extremely small (approximately 1 cubic millimeter) sensors. An ad-hoc wireless network of large numbers of such inexpensive but less reliable and accurate sensors can be used in a wide variety of commercial and military applications. These include target tracking, security, environmental monitoring, system control, etc. To keep the cost and size of these sensors small, they are equipped with small batteries that can store at most 1 Joule [12]. This puts significant constraints on the power available for communications, thus limiting both the transmission range and the data rate. A sensor in such a network can therefore communicate directly only with other sensors that are within a small distance. To enable communication between sensors not within each other’s communication range, the sensors form a multi-hop communication network. Sensors in these multi-hop networks detect events and then communicate the collected information to a central location where parameters characterizing these events are estimated. The cost of transmitting a bit is higher than a computation [1] and hence it may be advantageous to organize the sensors into clusters. In the clustered environment, the data gathered by the sensors is communicated to the data processing center through a hierarchy of clusterheads. The processing center determines the final estimates of the parameters in question using the information communicated by the clusterheads. The data processing center can be a specialized device or just one of these sensors itself. Since the sensors are now communicating data over smaller distances in the clustered environment, the energy spent in the network will be much lower than the energy spent when every sensor communicates directly to the information processing center. Many clustering algorithms in various contexts have been proposed [2-7, 23-28]. These algorithms are mostly heuristic in nature and aim at generating the minimum number of clusters such that any node in any cluster is at most d hops away from the clusterhead. Most of these algorithms have a time complexity of )(nO , where n is the total number of nodes. Many of them also demand time synchronization among the nodes, which makes them suitable only for networks with a small number of sensors. The Max-Min d-Cluster Algorithm [5] generates d-hop clusters with a run-time of )(dO rounds. But this algorithm does not ensure that the energy used in communicating information to the information center is minimized. The clustering algorithm proposed in [7] aims at maximizing the network lifetime, but it assumes that each node is aware of the whole network topology, which is usually impossible for wireless sensor networks which have a large number of nodes. Many of these clustering algorithms [23, 26, 27, 28] are specifically designed with an objective of generating stable clusters in environments with mobile nodes. But in a typical wireless sensor network, the sensors’ locations are fixed and 0-7803-7753-2/03/$17.00 (C) 2003 IEEE IEEE INFOCOM 2003the instability of clusters due to mobility of sensors is not an issue. For wireless sensor networks with a large number of energy-constrained sensors, it is very important to design a fast algorithm to organize sensors in clusters to minimize the energy used to communicate information from all nodes to the processing center. In this paper, we propose a fast, randomized, distributed algorithm for organizing the sensors in a wireless sensor network in a hierarchy of clusters with an objective of minimizing the energy spent in communicating the information to the information processing center. We have used results in stochastic geometry to derive values of parameters for the algorithm that minimize the energy spent in the network of sensors. II. RELATED WORK Various issues in the design of wireless sensor networks − design of low-power signal processing architectures, low-power sensing interfaces, energy efficient wireless media access control and routing protocols [3, 6, 20], low-power security protocols and key management architectures [29-30], localization systems [21, 22], etc. − have been areas of extensive research in recent years. Gupta and Kumar have analyzed the capacity of wireless ad hoc networks [18] and derived the critical power at which a node in a wireless ad hoc network should communicate to form a