Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

2.3 CLUSTERING-BASED BACKBONES

Clustering is one of the commonly used backbones to organize the network in a hierarchical architecture. It is used to partition nodes of the network into groups (clusters) in which CHs dominate the other nodes in the clusters. Clustering provides spatial reuse of the bandwidth which is a limited resource in wireless sensor networks. Moreover, clustering provides a hierarchical architecture for efficient routing. Existing solutions for clustering usually consists of two phases: clustering construction and clustering maintenance. In the first phase, nodes are chosen to act as coordinators of the clusters (CHs). A CH and some of its neighbors form a cluster. After clustering construction, clustering maintenance is required to reorganize the clusters due to node mobility and node failure.

There are different cluster structures. Clusterheads may or may not be allowed to be neighbors, and other nodes may or may not be always connected to a CH. For example, nodes in LEACH (low-energy adaptive clustering hierarchy) protocol proposed by Heinzelman et al. (2000) randomly decide whether or not to become CHs. The parameter used in decision making is the percentage of desired CHs in the network. Sensors that decide to become CHs broadcast their decision. Each node reports to the CH with the highest signal strength, and thus clusters correspond to Voronoi diagrams of CHs. A CH allocates a timeslot for each of its cluster members for reporting aggregation data. ...