Using hierarchical agglomerative clustering in wireless sensor networks: An energy-efficient and flexible approach

In wireless sensor networks (WSNs), hierarchical network structures have the advantage of providing scalable and resource efficient solutions. To find an efficient way to generate clusters, this paper adapts the well-understood hierarchical agglomerative clustering (HAC) algorithm by proposing a distributed HAC (DHAC) algorithm. With simple six-step clustering, DHAC provides a bottom-up clustering approach by grouping similar nodes together before the cluster head (CH) is selected. DHAC can accommodate both quantitative and qualitative information types in clustering, while offering flexible combinations using four commonly used HAC algorithm methods, SLINK, CLINK, UPGMA, and WPGMA. With automatic CH rotation and re-scheduling, DHAC avoids reclustering and achieves Uniform energy dissipation through the whole network. Simulation results in the NS-2 platform demonstrate the longer network lifetime of the DHAC than the better-known clustering protocols, LEACH and LEACH-C. (C) 2009 Elsevier B.V. All rights reserved.