1. Introduction

Wireless Sensor Networks (WSN) are a type of network composed of many small, isolated sensors that are distributed in a predetermined area and they communicate with each other via wireless links. A sensor, also called node or mote, is a low-cost, processing device with limited features in terms of computing capacity and energy resources because it is usually powered only with batteries or discontinuous energy sources like solar panels. Advances in the microelectronics and wireless communications make WSN applications very numerous and they are growing continuously ^[1]. There are WSN applications in many areas such as military, medical, environmental, agricultural, industrial, or smart cities’ environments among others. Some examples of current topics dealing with WSN are in health care ^[2] or smart grids ^[3]. The main purpose of those sensors is to monitor some physical variables in their environment and to send their values to a network component that collects all the information to be further processed. This last device is called the sink, gateway, or Base Station (BS). The BS is usually connected to the power grid and it usually has greater computing power, so it does not have the scarce resources of the sensors. Precisely, the power resources in the sensors constitute a limiting characteristic of the WSN as it can prevent the network from operating correctly, that is, gathering all the required information and transmitting it to the BS. Therefore, one of the main challenges of the WSN is to increase the lifetime of the network to avoid nodes depleting their batteries when accomplishing unnecessary tasks. In this sense, one of the most useful techniques is clustering, whereas traditional routing appears better suited for larger networks. A typical example of clustering is found in Figure 1. Among all the nodes, some of them are chosen to become Cluster Heads (CH). The CHs act as gatherers of data of the associated nodes, also referred to as contributing nodes. The nodes transmit their measurements to only one CH, which usually is the one that is closest to them. Then, each CH aggregates the information from its group and relays it to the BS. This technique avoids that all the nodes would have to communicate with the BS directly, which could not be affordable at long distances because they would deplete their battery much faster due to the nonlinear dependence of the power losses with the distance. Additionally, the configuration of the CHs should not be fixed and the nodes should take turns to undertake this function in order to balance the energy consumption of being a CH ^[4]. Thus, the hierarchy of CHs dynamically changes within the network.Clustering can be performed in different ways. For those in which CH sends the information directly to the BS (without relaying nodes), the clustering techniques are classified according to the activity performed by the BS. In this set, we distinguish the following clustering strategies: 

Centralized Clustering. The BS ^{[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22]}has full control about how the clustering is performed. The BS always decides which nodes are converted into CHs. For this operation, the BS needs information about all the nodes in order to choose the most appropriate ones as CHs. The most common properties used for this decision are the location of the node within the sensing area and the residual energy of each node. The first one is not always available in all the applications because nodes usually cannot afford GPS equipment or similar hardware.

• Centralized Clustering. The BS has full control about how the clustering is performed. The BS always decides which nodes are converted into CHs. For this operation, the BS needs information about all the nodes in order to choose the most appropriate ones as CHs. The most common properties used for this decision are the location of the node within the sensing area and the residual energy of each node. The first one is not always available in all the applications because nodes usually cannot afford GPS equipment or similar hardware.
• Distributed Clustering. The nodes are completely autonomous and decide by themselves if they become CH or not. This decision is supported by the properties that the node can know/estimate by itself. Then, that information is weighted by some methods that indicate whether to become CH or not. Finally, those nodes that selected themselves as CH send a message to the network so that the other nodes can join them to their clusters.

Distributed Clustering. The nodes are completely autonomous and decide by themselves if they become CH or not. This decision is supported by the properties that the node can know/estimate by itself. Then, that information is weighted by some methods that indicate whether to become CH or not. Finally, those nodes that selected themselves as CH send a message to the network so that the other nodes can join them to their clusters.

2. Result

Centralized and distributed clustering can also be subdivided into different categories depending on the method used to choose the CHs. There are stochastic approaches, geometric algorithms, methods based on fuzzy logic (Type-1 or Type-2), or techniques supported by other artificial intelligence. The most relevant stochastic and distributed algorithms is Low-Energy Adaptive Clustering Hierarchy (LEACH) ^[5]. LEACH employs a random number that is generated by each node. This number is compared with a parameter representing the probability of becoming CH. The generated value increases with the number of rounds if the sensor has not been chosen as a CH, and it is determined by a system configuration parameter (p). If the random number is greater than this value, then the node becomes a CH. An adaptation of this method is detailed in ^[6], where the nodes add different thresholds depending on the distance or the remaining energy. Other stochastic method is the Hybrid, Energy-Efficient, Distributed clustering approach for ad hoc sensor networks (HEED) ^[7], a multi-hop clustering algorithm in which the probability of being a CH depends on the residual energy. Normal nodes use the inter-cluster communication cost as a metric to decide which cluster it should join. In an Energy Efficient Clustering Scheme (EECS) ^[8], the authors propose a clustering method based on a competition among a fixed number of CH candidates. The CH candidates are selected with a probability T. This probability is set empirically in a similar way to parameter p in LEACH. Other types of approaches are those that combine stochastic and geometrical methods like Voronoi Tessellation. The work in ^[9] follows this approach for a mobile WSN in which the CH corresponds to the seeds of the cells.Clustering can also be supported by artificial intelligence. Particularly, Fuzzy Rule-Based Systems (FRBS) outstand as a convenient mechanism to decide which nodes will play the role of the CHs. The applications and research scopes that use these types of expert systems are very numerous in areas such as image classification ^[10], performance improvement in wind turbines ^[11], image fusion field ^[12], software error identification ^[13], or wireless sensor networks ^[14]. As for clustering, the work in ^[15] describes a particle optimization algorithm based on LEACH. The authors of ^[16] use a fuzzy logic Type-1 distributed algorithm with two outputs. The first output defines the sending radius of the announcement message and the second one determines whether a node will be CH or not.One of the first relevant centralized methods that employs an expert system is the Cluster-head Election using fuzzy logic (CHEF) ^[17]. The BS implements a fuzzy logic Type-1 algorithm to decide which node will be cluster head in each round. In ^[18], the BS selects the best nodes based on a fuzzy Type-2 system. The inputs of this system are the residual energy, the distance to the BS, and the number of neighbors of each node. In the proposal presented in ^[19], the BS receives information about the energy and the location of the nodes. Then, the BS decides through a simulated annealing algorithm which node configures itself as a CH. Previously, BS has removed as candidates CHs those nodes with an energy below the total average. The work in ^[20] describes another centralized method that employs a very complex technique. Specifically, it uses a convolutional neural network to determine the best CH. The authors in ^[21] present a centralized algorithm in which the BS uses artificial-intelligence as fuzzy c-means to determine the best location for the center of each cluster. The authors of ^[22]show a centralized algorithm that uses a Particle-Swarm based Optimization (PSO) for choosing the best CHs. Additionally, the BS determines the time that a CH remains active based on the residual energy of the system. Although the idea is very promising, the previous implementation is complex in real-time applications because its solution can be only achieved after the convergence of an iterative process.

The authors of this proposal^[23] present a new semi-distributed algorithm in which the base station changes the configuration of the nodes three times: at the beginning of the communication, in the first death and when only half of the sensors are alive. Centralized clustering algorithms usually allow better metrics but with more expensive hardware compared to distributed algorithms. A semi-distributed technique in which the base station modifies some aspects of the algorithms could achieve a better trade-off between cost and good metrics.