Regarding whether or not location information is used, this latter survey considers the special case of using a mobile agent (a program that travels across the nodes to perform tasks based on environmental conditions in an autonomous way) and where the BS can move within the network to collect data from sensor nodes. Location-based routing is also included under this type, but it could be included under the network structure category as done in other surveys.
Under the Reliable Routing category, protocols are classified depending upon their inclusion of QoS support or multiple paths to balance the load and tolerate path failures.
To sum up, most of the routing algorithms proposed in the literature can be classified in flat network, hierarchical and location-based, either using single-hop or multihop communication.
In flat network routing, all nodes have the same responsibility and every node has all information, so that the user can send a query to any node to obtain information. We must note that it is not possible to use a global addressing scheme due to the huge number of nodes in the network. This fact makes classical IP-based routing inadequate. Therefore, the routing is data-centric, i.e., it is totally dependent on naming of desired data.
2.4.1. Hierarchical Routing Protocols
Heinzelman et al. [
56] proposed the first hierarchical routing protocol referred to as LEACH (Low Energy Adaptive Clustering Hierarchy). LEACH proposes a random rotation method to select the node with maximum energy level as the CH, and so uniformly distribute the energy load among the sensors in the network. CHs send advertisement messages to the whole WSN using CSMA. Each sensor node joins the cluster from which it receives the strongest signal. Next, CH schedules TDMA slots for each member in the cluster to send data to it. CH uses aggregation techniques to combine the data received from sensor nodes to save energy and bandwidth, and then this aggregated information is forwarded directly to the BS, i.e., using only one hop, as shown in
Figure 3.
Figure 3. Different hierarchical routing strategies (BS base station, L leader, CH cluster head).
The single-hop transmission is the simplest method, but usually it is not suitable for large networks, where multiple-hop transmission should be employed. In this case, data follows a multiple-hop route across several CHs towards the BS, and so it is essential to use an energy-aware routing protocol that avoids unnecessary transmissions and the overload in the nodes close to the BS.
Clustering enhances energy efficiency in several ways: (i) it reduces the communication range within the cluster and so less transmission power is necessary, (ii) data reduction techniques can be performed by the CH, (iii) energy-intensive operations such as coordination or data reduction are only carried out by the CH, (iv) it enables the powering-off of some nodes, typically after sending data to the CH. On the other hand, hierarchical routing also improves network scalability by maintaining a hierarchical topology in the network.
LEACH is still the most important and most used basic routing algorithm for WSNs. After 18 years of existence, much attention is still devoted to LEACH by the research community working in the area of routing in WSN. This itself shows its relevancy. In several recent works [
141,
142,
143], the authors survey, classify and analyze different versions or improvements of LEACH, also using multihop transmission.
Manjeshwar and Agrawal [
144] proposed another popular cluster-based routing algorithm referred to as Threshold-sensitive Energy-Efficient sensor Network (TEEN) [
144] that has been designed for time critical applications. TEEN combines the architecture based on clustering with the use of a data-centric mechanism. Adaptive Periodic TEEN (APTEEN) [
145] is an enhancement of TEEN where CH broadcasts relevant parameters to the cluster members such as threshold values, TDMA schedule, and maximum time between consecutive reports.
Another interesting cluster-based routing protocol is Hybrid Energy-Efficient Distributed (HEED) [
146], where CH election is triggered in given intervals and it is based mainly on residual energy and other parameters as the number of neighbors or the distance to them. A survey recently published by Ullah [
147] focus on HEED-based protocols.
Since the relevancy of cluster-based routing, it is common to speak indistinctly of cluster-based and hierarchical routing, but strictly speaking, other types of hierarchical structures have been proposed in the literature. Recently, Chan et al. [
148] survey and compare both LEACH-based clustering and these other hierarchical structures, classified into the following categories: (a) chain-based, (b) tree-based, (c) grid-based, and (d) area-based, also represented in the
Figure 3.
In chain-based hierarchical routing, the WSN is divided into chains; and a leader is chosen for every chain. Every node sends the data to the next node until the leader is reached. The main drawbacks are the delays suffered by the farthest nodes in long chains, the overload of the nodes close to the leader and the connectivity loss in a sub-chain when a node fails. The most relevant chain-based algorithm is PEGASIS (Power-Efficient Gathering in Sensor Information Systems) [
149], where the leaders are rotated for energy reasons, and they send the aggregated data to the sink.
In tree-based routing algorithms, a sink tree is created and there is a single path between each node and the sink. Unlike the chain-based case, there are no leaders, and a parent node can receive data from several children (or leaves), unlike the previous case, a node (parent) can have several children that send data to it, enabling the possibility of aggregation. The main drawbacks are similar to the chain-based case, i.e., the delays suffered by the farthest nodes in long trees, the overload of the nodes close to the sink and the connectivity loss in branches connected to a parent that fails. The most relevant tree-based algorithm is PEDAP (Power-Efficient Data gathering and Aggregation Protocol) [
150] that uses the optimum sink tree based on data volume and transmission distance.
In grid-based algorithms, the whole network is split into many grids (similar to clusters), based on the geographical location of the nodes. The leader selected for every grid is the responsible for routing the data through other leaders until reaching the sink, i.e., using multihop transmission. Each node only needs to know the location information about the leader of the grid. The most important proposal of this type is Two-tier data dissemination (TTDD) [
151], where the mobile sink use flooding to send a data request to source nodes.
In area-based mechanisms, the entire network is divided into multiple variable-sized areas. The BS also transmits a data request to the closest nodes that they forward via flooding until the data source is reached, which will send the data to the sink. A typical area-based algorithm is Line-based data dissemination (LBDD) [
152], where a line of leaders is selected to split the whole network in two areas. The nodes send data to the closest leader on the line, and the leaders on the line store data from nodes and serve requests from sink if possible, and if not, send the request up and down the line. A little improvement was proposed in Ring Routing [
153], using a ring instead of a line.
In Figure 4, we show the most relevant algorithms of each type.
Figure 4. Classification of hierarchical routing strategies.
The main problems related to cluster-based routing are the cluster formation, the selection of CH in each cluster and the relay node placement. In addition to the classic approaches to address them, these problems have been object of optimization in hundreds of works in last years, and they are clearly one of the most active research areas presently. To solve this problem, the researchers have appealed to optimization (Swarm Intelligence Algorithms) and methodological approaches such as fuzzy logic or metaheuristic. The survey in [
154] studies hierarchical energy-efficient routing protocols based on classical and swarm intelligence approaches.
However, the subsequent survey in [
155] focuses on methodological approaches in cluster-based multihop routing protocols that are classified into four categories: classical approaches, fuzzy-based approaches, metaheuristic-based approaches and hybrid metaheuristic- and fuzzy-based approaches.
The very recent survey by Manuel et al. [
156] is much more complete and the classification considers both swarm intelligence algorithms: ant colony optimization (ACO), artificial bee colony optimization (ABCO), fuzzy logic (FL), genetic algorithm (GA), whale algorithm (WA), or particle swarm optimization (PSO) and methodological approaches (fuzzy-based and metaheuristic-based approaches). See
Figure 5 reproduced from this complete survey.
Figure 5. Classification of clustering-based routing protocols reproduced from Manuel et al. [
156].
A review of the recent literature on these topics shows rapidly the high level of research activity in this area. The work in [
157] studies the adoption of sink mobility to avoid the hot spot problem (CHs close to the BS). The mobile sink moves within the network and communicate directly with CHs without the need for routing. The ACO algorithm is studied for finding an optimal trajectory for the mobile sink. In [
158] a special clustering method called Energy Centers searching using PSO (EC-PSO) is proposed for clustering and CH selection. In [
159] a firefly algorithm is developed for selecting the CH optimally. Ezhilarasi and Krishnaveni [
160] propose the evolutionary multipath energy-efficient routing protocol (EMEER) using a cuckoo search algorithm to optimally select the CH considering energy efficiency. Recently, Alghamdi [
161] proposes an optimal CH selection by considering energy, delay, distance, and security using a new algorithm that hybridizes the concept of dragon fly and firefly algorithms. Additionally, recently, the Optimized QoS-based Clustering with Multipath Routing Protocol (OQoS-CMRP) has been proposed [
162] by applying the Modified Particle Swarm Optimization to form clusters and select CHs.
Ref. [
163] introduces an algorithm that uses fuzzy logic for cluster construction and CH selection, and ACO for inter-cluster routing to mitigate the hot spot problem and extend network lifetime. In [
164] an interesting PSO-based unequal and fault tolerant clustering protocol (PSO-UFC) is presented. In [
165] the authors use a cuckoo optimization algorithm (COA) for clustering and selection of optimal CHs, considering four criteria such as the remaining energy of nodes, distance to the base station, within-cluster distances, and between cluster distances. In [
166] a multihop LEACH protocol is optimized by means of an ACO algorithm, using a CH close to the BS. Other recent works that propose LEACH optimizations are the proposal in [
167] using a Fuzzy C-means clustering (FCM) Algorithm, the work in [
168] that uses a PSO algorithm or the optimization made in [
169] by means of a Genetic Algorithm. Another interesting work is that of Jain and Goel [
170] where fuzzy sets and fuzzy decision rules have been used for intelligent selection of CHs and to setup multihop routes to BS.
Although LEACH is the preferred protocol for using as basis for optimization, other cluster-based protocols are also used. Therefore, several improvements of PEGASIS has been recently proposed. In [
171] an Enhanced PEGASIS (EPEGASIS) protocol is proposed to mitigate the problem of hot spots from four directions. The work in [
172] combines PEGASIS with Hamilton Loop algorithm, through a mixture of single-hop and multihop mechanisms, inserting a mobile agent node that is responsible for receiving and merging packets from the CHs. The authors in [
173] also combines PEGASIS with a genetic algorithm to build the chain instead of the greedy algorithm.
The problem of CH selection in APTEEN using artificial intelligence has also attracted the interest of researchers in recent years: using PSO [
174], a combination of genetic algorithms and fruit fly optimization algorithm [
175], or ACO [
176,
177].