ABSTRACT
CONTENTS 12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
12.1.1 Main Objectives and Design Challenges of Clustering in WSNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
12.2 Classification of Clustering Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 12.2.1 Clustering Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 12.2.2 Taxonomy of Clustering Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
12.3 Probabilistic Clustering Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 12.3.1 Popular Probabilistic Clustering Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
12.3.1.1 Low Energy Adaptive Clustering Hierarchy (LEACH) . . . . . . . 333 12.3.1.2 Energy-Efficient Hierarchical Clustering (EEHC) . . . . . . . . . . . . 335 12.3.1.3 Hybrid Energy-Efficient Distributed Clustering (HEED) . . . . 336
12.3.2 Extensions and Other Similar Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 12.4 Nonprobabilistic Clustering Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341
12.4.1 Node Proximity and Graph-Based Clustering Protocols . . . . . . . . . . . . . . . . 342 12.4.2 Weight-Based Clustering Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 12.4.3 Biologically Inspired Clustering Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
12.5 Clustering Algorithms for Reactive Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 12.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
The use of wireless sensor networks (WSNs) has grown enormously in the last decade, pointing out the crucial need for scalable and energy-efficient routing and data gathering and aggregation protocols in corresponding large-scale environments. Hierarchical clustering protocols (as opposed to direct single-tier communication schemes) have extensively been used toward the above directions. Moreover, they can greatly contribute to overall system scalability, lifetime, and energy efficiency. In this chapter the state of the art in corresponding hierarchical clustering approaches for large-scaleWSN environments is presented. The need for clustering in WSNs is first motivated and a brief description of the implied hierarchical network pattern is given. The basic advantages, objectives, and design challenges are also briefly explored. A set of appropriate taxonomy parameters as well as a global classification scheme is then introduced. In the main body of the chapter, the most significant of the existing WSN clustering algorithms are concisely presented and commented according to the previously stated parameters and classification scheme. The chapter is concluded by stating some general remarks as well as some open research issues in the field.
