The fast evolution of electronic technologies has foretold a promising and fancy future for wireless sensor network applications. Distinguished from typical wireless network, wireless sensor networks face problems of stringent limited energy, poor dynamic links, and large quantity of nodes. These unique characteristics have created a large research field and inspired enormous innovative ideas....[ Read more ]

The fast evolution of electronic technologies has foretold a promising and fancy future for wireless sensor network applications. Distinguished from typical wireless network, wireless sensor networks face problems of stringent limited energy, poor dynamic links, and large quantity of nodes. These unique characteristics have created a large research field and inspired enormous innovative ideas.

Many applications in wireless sensor networks (WSNs) significantly benefit from organizing nodes into groups, called clusters, because clustering could provide a convenient structure for the design of data aggregation, routing and topology control algorithms. Clustering has been widely studied in computer science literature. Recently, the most popular works on clustering are within the scope of wireless ad hoc networks, mainly targeting at generating stable clusters in a complicated environment with mobile nodes. Most of these research focus on nodes’ reachability and route stability, without much concern about critical design restrictions of wireless sensor networks, such as energy efficiency and energy balance which could help to extend the life time of wireless sensor networks.

By classifying sensor network applications into two categories - periodical monitoring applications and event detection applications, we propose two general clustering frameworks, K-hop static clustering and dynamic clustering correspondingly. We tackle three critical problems. First, it is straightforward that the size of clusters should vary according to diverse applications. It is essential to provide a general clustering framework which could provide tailored cluster size. Second, we observe that unbalanced clusters would dramatically decrease the network lifetime. We design an Evenly Distributed Clustering (EDC) algorithm. Constrained by the maximum cluster size K, EDC distributes clusters uniformly and minimizes the number of clusters. Third, clustering framework is inevitable to introduce some overhead. Particularly for infrequent event detection applications, the maintenance cost is comparably high due to the dynamic behaviors of wireless sensor networks. A dynamic clustering scheme is proposed to generate clusters on demand without maintaining clustering structure across the network. Energy-efficient and energy-balanced dynamic clustering (EEDC) and evenly distributed dynamic clustering (EDDC) algorithms are designed and comprehensively discussed under various scenarios.

Keywords: Wireless Sensor Networks, Clustering, K-hop Clustering, Evenly Distributed Clustering, Dynamic Clustering