Section 20.3. Clustering Protocols

20.3. Clustering Protocols

Clustering protocols specify the topology of the hierarchical nonoverlapping clusters of sensor nodes. A robust clustering technique is essential for self-organizing sensor networks. An efficient clustering protocol ensures the creation of clusters with almost the same radius and cluster heads that are best positioned in the clusters. Since every node in a clustered network is connected to a cluster head, route discovery among cluster heads is sufficient to establish a feasible route in the network. For a large sensor network, clustering can simplify multihop route discovery and limit the number of transmissions compared to a flat, nonclustered network.

20.3.1. Classification of Clustering Protocols

Clustering techniques can be either centralized or decentralized . Centralized clustering algorithms require each sensor node to send its individual information, such as energy level and geographical position, to the central base station. Based on a predefined algorithm, a base station calculates the number of clusters, their sizes, and the cluster heads' positions and then provides each node with its newly assigned duty.

Given the assumption that sensor networks might consist of thousands of nodes, it is impractical , if not impossible , for a base station to collect information about every node in the network prior to route setup. Therefore, centralized clustering is not an option for large sensor networks. Since a sensor node begins a clustering process without any knowledge about its location relative to the corresponding base station, a clustering algorithm should be able to form clusters without the help of the base station and knowledge of node positioning. Although location-finder devices can also be deployed to perform this task, they are often either costly or add too much overhead on the network.

Decentralized clustering techniques create clusters without the help of any centralized base station. An energy-efficient and hierarchical clustering algorithm can be such a way whereby each sensor node becomes a cluster head with a probability of p and advertises its candidacy to nodes that are no more than k hops away from the cluster head. Given the limited transmission range of wireless sensor nodes, a hierarchical structure with an arbitrary number of levels has its limitations. As the number of hierarchical levels grows, the distance between upper-level cluster heads may increase to the point that they are no longer able to communicate with one another. The Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm and the Decentralized Energy-Efficient Cluster Propagation (DEEP) protocol are two examples of the decentralized clustering protocols and are explained next .

20.3.2. LEACH Clustering Protocol

The Low-Energy Adaptive Clustering Hierarchy (LEACH) protocol is a decentralized clustering algorithm that does not offer a complete energy-optimization solution, as it has no strategy for specifying cluster-head positioning and distribution. LEACH is an application-specific protocol architecture that aims to prolong network lifetime by periodic reclustering and change of the network topology.

LEACH is divided into rounds consisting of a clustering phase and a steady-state phase for data collection. At the start of each round, a sensor node randomly chooses a number between 0 and 1 and then compares this number to a calculated threshold called T(n) . If T(n) is larger than the chosen number, the node becomes a cluster head for the current round. The value T(n) is calculated using the following formula:

Equation 20.11

where p is the ratio of the total number of cluster heads to the total number of nodes, r is the number of rounds, and G is a set of nodes that have not been chosen as cluster heads for the last 1 /p rounds. For the first round ( r =0), T(n) is equal to p , and nodes have an equal chance to become cluster head. As r gets closer to 1 /p , T(n) increases , and nodes that have not been selected as cluster head in the last 1 /p rounds have more chance to become cluster head. After 1 /p - 1 rounds, T(n) is equal to 1, meaning that all the remaining nodes have been selected as cluster head. Thus, after 1 /p rounds, all the nodes have had a chance to become a cluster head once. Since being the cluster head puts a substantial burden on the sensor nodes, this ensures that the network has no overloaded node that runs out of energy sooner than the others.

After cluster heads are self-selected, they start to advertise their candidacy to the other sensor nodes. When it receives advertisements from more than one cluster-head candidate, a sensor node starts to make a decision about its corresponding cluster head. Each node listens to the advertisement signals and chooses the candidate whose associated signal is received with higher power. This ensures that each sensor node chooses the closest candidate as cluster head. The LEACH algorithm is distributed, as it can be accomplished by local computation and communication at each node, rather than the transmission of all the nodes' energy level and geographical position to a centralized point. However, cluster heads are chosen randomly, and there is no optimization in terms of energy consumption.

20.3.3. DEEP Clustering Protocol

The Decentralized Energy-Efficient Cluster Propagation (DEEP) protocol that establishes clusters with uniformly distributed cluster heads. This protocol balances the load among all the cluster heads by keeping the clusters' radii fairly equal. This protocol is completely decentralized, and there is no need for any location-finder device or hardware. The protocol starts with an initial cluster head and forms new cluster-head candidates gradually by controlling the relative distance between a pair of cluster heads and the circular radius of each cluster. Owing to the balanced load among cluster heads, periodic reclustering is not necessary, and operational expenses caused by frequent reclustering are therefore eliminated.

An efficient path -selection algorithm for nodes that are placed more than meters away from a cluster head is necessary in order to find the optimum two-hop or three-hop path. Although direct transmission to a cluster head can eliminate the overhead created by the route set-up packets, its efficiency is questionable, owing to the limited transmission range. In order to avoid the frequent control signal transmission and extra power consumption associated with that, a cluster head can be placed at the center of the cluster, with sensor nodes positioned closer than meters around it. In this case, cluster members can send the data packets directly to the cluster head without the need for any route set-up protocol, while efficiency has already been achieved through the choice of cluster shape and cluster size .

In order to explain the details of this algorithm, control signals and protocol parameters need to be introduced:

Control signals: (1) cluster-head declaration signal or (2) cluster-head exploration signal
Membership search signal with control parameters: declaration range ( d _r ), exploration range ( d _r ₁ , d _r ₂ ), minimum number of members ( m _n ), E _rc ₁ , and E _rc ₂ .

Protocol-control parameters are application-specific choices and can be defined prior to network deployment. DEEP forms clusters by starting with an initial cluster head that can be chosen prior to network deployment. This initial cluster head starts the cluster set-up phase by propagating cluster-head declaration signals within the range of d _r . This means that the cluster-head candidate chooses an appropriate data rate and signal output power so that it can reach nodes that are less than d _r away from the sender.

At this point, sensor nodes that receive the declaration signal accept the corresponding cluster head as a leader. They can then estimate their relative distance to the candidate by looking at the received signal's energy level. Once they know the relative distance to the cluster head, they can conserve energy by adjusting the transmission speed to the appropriate value and switching to sleep mode. Now, the initial cluster-head candidate propagates the cluster-head exploration signal within the range of d _r ₂ , as shown in Figure 20.7. All the sensor nodes in this range can listen to the exploration signal, but only nodes that have never played the role of a cluster head and verify the following inequality are chosen as new candidates:

Equation 20.12

Figure 20.7. Initial cluster head starts the advertisement process. New cluster-head candidates send the exploration signal within the range of d _r ₂ to continue the process of cluster establishment.

where E _r is the received signal energy. Note that E _rc ₁ and E _rc ₂ are fixed protocol parameters that can be precalculated and stored in the sensor-node memory, using the following formula:

Equation 20.13

and

Equation 20.14

where P _out is the constant output power of the cluster-head exploration signal, and ‰ and n are parameters that can be determined based on the environmental conditions of the deployment area. This way, any of these nodes can consider itself a candidate. This ensures that new cluster-head candidates are positioned between d _r ₁ and d _r ₂ , away from the initial cluster head.

After a new cluster-head candidate is assigned, it sends a declaration signal within the range of d _r to find new cluster members. If two candidates can hear each other's declaration signal, they are too close to each other to be considered cluster-head candidates. Therefore, one of them is eliminated through a negotiation phase. Whenever it receives a declaration signal, a cluster head informs the sender of the message, using an acknowledgment message. A cluster head that receives the acknowledgment sends a dissolution message and informs all nodes within the range of d _r about its elimination . A node that receives a declaration signal from more than one candidate chooses the candidate whose associated signal is received with a higher power.

At this point, all confirmed cluster heads propagate exploration signals and search for new cluster-head candidates. Nodes that have already been chosen as cluster head or member ignore the cluster-head exploration or declaration signals. Therefore, this advertisement process terminates automatically when all the nodes in the field belong to a cluster. At this point, the algorithm might have produced some clusters with a very small number of members. Therefore, a cluster whose total number of members is smaller than the minimum number of members, m _n , is dissolved, and all its members, including its cluster head, initiate a membership-search signal .

After this process is completed, nodes listen to the responses from the local cluster heads and choose the closest cluster head, based on the received signal power. At the end, if the timeout has been reached, a sensor node that has not received any control signal sends a membership-search signal and chooses the closest cluster head as leader. The following algorithm summarizes the core segment of the DEEP protocol.

Begin DEEP Clustering Algorithm

Initialize: Initial cluster head finds cluster members by sending "cluster-head declaration."
Initial cluster head finds new cluster-head candidates by sending "cluster-head exploration signal."
Repeat: Cluster-head candidates that are placed on the ( d _r ₁ , d _r ₂ ) ring find cluster members.
Nodes that receive more than one cluster-head declaration choose the closest cluster head, based on the received signal energy.
Cluster-head candidates that receive a cluster-head declaration signal negotiate with the sender, and one of them gets eliminated.
Confirmed cluster heads send "cluster-head exploration" signals to find new cluster-head candidates (Go to step 4).
Finalize: If the number of members in a cluster is less than m _n , all the members find new clusters by sending the membership-search signal.
At the end, a node that has not received any control signal sends the membership-search signal.

DEEP has several advantages over other clustering protocols. With DEEP, a sensor node can either select itself as a cluster head by receiving a cluster-head exploration signal or join a cluster by receiving a cluster-head declaration signal. After the execution of the protocol, all the sensor nodes are covered and belong to only one cluster. This clearly shows that this protocol is completely decentralized. In addition, for the execution of DEEP, there is no need for any location-finder hardware, such as the global positioning system (GPS) or a position-estimation protocol that puts extra overhead on sensor nodes.

DEEP can control a cluster-head distribution across the sensor network through protocol-execution methodologies. For example, cluster-head candidates should receive the cluster-head exploration signal with a certain amount of energy; if they can hear the declaration signal of each other, one of the candidates is eliminated. Communication cost is low through proper selection of protocol parameters, such as declaration range, exploration range, and minimum number of members.

With DEEP, intracluster communication is controlled by cluster heads, and nodes transmit their data directly to cluster heads. Therefore, no additional control signal is associated with route selection and maintenance inside the cluster. Also, owing to the uniform distribution of cluster heads, communication cost of a direct transmission path between a pair of neighboring cluster heads is almost identical across the sensor field. This is one of the most important protocol characteristics contributing to convenient deployment of an intercluster routing protocol.

20.3.4. Reclustering

In order to prevent overutilization of some sensor nodes, clustering technique should ensure that the cluster-head responsibility rotates among all sensor nodes. To achieve this, reclustering is performed periodically in LEACH. However, every round of reclustering requires several control-signal exchanges among self-elected cluster heads and sensor nodes. The reclustering process in DEEP is based on one small shift in the initial cluster head. When the current period of cluster setting is finished, the current initial CH chooses the nearest node that has never acted as an initial cluster head. This newly chosen initial cluster head starts the clustering process and creates a totally different cluster-head constellation.