Heterogeneity consideration in wireless sensor networks routing algorithms: a review

Abstract

Wireless sensor networks (WSNs) are resource-constrained networks with limited battery power, computation abilities and communication capabilities at the sensor node level. A long-standing need in the area is to reduce energy consumption of the WSN nodes and to extend the network lifetime, along with improving the network reliability and the network quality. Energy-efficient routing protocols can improve the WSN performance, and the algorithms have been explored widely by the researchers. In the majority of the work, sensor nodes have been considered homogeneous in their configuration and capabilities. However, in practical scenarios and with the advent of an era of connected devices, called “Internet of Things,” consideration of node heterogeneity in WSN has become inevitable. Nodes’ heterogeneity can be exploited constructively in WSN routing algorithms. In the literature, many different heterogeneous WSN scenarios (e.g., energy, computation, link heterogeneities) have been considered and the routing algorithms have been proposed for performance improvement in such scenarios. This paper focuses on the routing concepts for diverse heterogeneous WSNs scenarios and covers the state of the art in the area. The clustering-based approaches for routing decisions are extensively covered under different heterogeneous WSN scenarios. Along with presenting a comprehensive review of the routing algorithms under different varieties of heterogeneous WSNs, the paper also discusses the effects and interdependencies of different heterogeneities in routing decisions and unveils new research directions in the area.

1 Introduction

The technological advancements in the energy-efficient low-cost sensors, electronic circuits and radio frequency (RF) communication modules along with Internet of Things (IoT) evolution have revived the interest in wireless sensor network (WSN) research and applications. WSN is a collection of wirelessly connected tiny sensor nodes, deployed in the region of interest. The nodes capture some physical phenomena and send the information to the sink/base-station (BS) for processing and decision making. The IoT envisions networked and connected things/devices for improvement in human life and surroundings [1]. The IOT technology is based on the evolution of networked devices, and it considers WSN deployment for complex and demanding applications [2]. WSN has numerous applications in a variety of application domains, e.g., defense, environment, health, home and industrial applications [3, 4].

WSN nodes are constrained in resources (energy, computation abilities, communication capabilities, etc.) and for optimum resource utilization they require specialized techniques for networking and information sharing. Development of energy-efficient algorithms for improving the network lifespan is a challenge in self-organizing, self-healing and multi-hopped WSNs. Algorithmic techniques have been developed for various WSN functional dimensions, e.g., WSN routing [5,6,7,8,9,10] (considering the optimum path for a packet to go from a source node to the sink); node placement [11, 12] (positioning of the nodes to improve the network coverage, connectivity, lifetime and load balancing); localization [13, 14] (finding location information of the nodes in the WSN); data aggregation [15] (an efficient combining of related/duplicate information generated from the nodes).

As communication activities consume the maximum share of a node’s energy (in comparison with sensing and computation) during its operations [4], the routing algorithm becomes an important and critical aspect of WSN. The major challenge in WSN routing algorithms is to prolong the lifetime of the WSN, while maintaining reliable data communication in the network. The design of a routing algorithm for a WSN can be affected by many factors [5,6,7], e.g., node/link heterogeneity, energy efficiency with accuracy, node deployment, network scalability, fault tolerance, data aggregation/fusion, network dynamics, data reporting model, coverage, connectivity and quality of service. Based on various attributes, like network structure, communication model, topology and reliability, the routing algorithms have been classified into many categories, e.g., flat, hierarchical, negotiation based, location based, query based, mobile agent based, QoS (Quality of Service) based and multipath based.

A majority of WSN routing algorithms consider that all the nodes (except sink) are homogeneous, i.e., the nodes are equal in configuration and capabilities. However, in practical scenarios, a WSN may consist of heterogeneous nodes with different configuration and capabilities. Due to the disparities in nodes’ resources, the routing protocols designed for homogeneous WSNs may not perform optimally in heterogeneous scenarios; this makes the consideration of heterogeneity in WSN routing algorithms a crucial research challenge. Based on the nodes’ disparities in energy resources, computation capabilities, and communication link properties, the majority of the routing algorithms for heterogeneous WSNs have been categorized into energy, computation/computational and link heterogeneities, respectively [16, 17]. Zhou et al. [18] consider an energy and computational heterogeneity based network model and indicate that the homogeneous WSN can be regarded as a special case of heterogeneous WSN. Yarvis et al. [19] focus on resource heterogeneity (energy and link) in ad hoc sensor networks and show that an intelligent exploitation of heterogeneity (e.g., optimum number and placement of heterogeneous resources) can improve the average delivery rate and the WSN lifetime. Due to the diverse topics and voluminous work in the area, the general reviews on routing algorithms for WSNs [5,6,7,8,9,10] do not put WSN heterogeneity aspects in center stage. In comparison with the earlier reviews on the routing algorithms for heterogeneous WSNs [16, 17, 20, 21], our work provides a wider coverage in the specific domain, covers the state of the art and looks at new possibilities in the area.

The main contribution of this paper is to present a review of the most pertinent literature and the latest advancements in the energy-efficient routing protocols for heterogeneous WSNs. The node architecture and WSN heterogeneity relationship has been discussed to uncover many possible heterogeneous scenarios in the area. The most impactful concepts and the recent work in routing algorithms under all three heterogeneous WSN categories (energy, link and computation) have been discussed in detail. The clustering-based routing approaches are covered extensively with description of cluster head selection and cluster management aspects. The computational heterogeneity section also covers the routing algorithms for traffic heterogeneous scenarios, which is relatively less explored area. Routing algorithms for the WSNs with multiple heterogeneities and other heterogeneous scenarios (e.g., application heterogeneity, mobile relay nodes) have also been considered. The energy harvesting WSNs, with disparities in the nodes’ harvested energies due to varying environmental conditions, pose unique challenges in routing decisions. An introduction to the routing techniques under such scenarios is also included. Further, the interdependencies of different heterogeneities and their effects on the performance of the routing algorithms have been discussed, along with future research direction in the area.

This paper is organized as follows: In Sect. 2, the different types of heterogeneities in WSNs are presented in reference to the WSN node architecture. In Sect. 3, a review of routing protocols for diverse heterogeneous WSN environments is presented. The routing techniques are discussed chronologically under different scenarios, viz. energy, link, computation and other heterogeneous scenarios. An introduction to the routing algorithms for energy harvesting WSNs is also included in this section as a special case of WSN heterogeneity. Section 4 discusses interdependencies and future research directions in the area. Finally, the article is concluded in Sect. 5.

2 Heterogeneities in WSN based on sensor node architecture

A node in WSN generally comprises of four essential modules, viz. sensor/sensing module, computing/computation/processing module, communication module and power module (Fig. 1a–d). Further, the node may have few additional modules, e.g., location finding module, mobilizer and energy generation/harvesting module. In the sensor module, a sensor senses some physical phenomena and produces a corresponding output signal. If the output signal is analog, then an analog-to-digital converter (ADC) is used to convert the analog signal into a digital signal, which can be processed by the computing module. Depending on the application, the sensor module may have a single sensor or multiple sensors. The computation module has processor to process the information and memory to store the data and algorithms. This intelligent module also controls the other modules like sensor module and communication module. The communication module consists of radio frequency (RF) transceiver to communicate with the other nodes/sink in the WSN. The power module (supported by batteries) feeds all the other modules, and it can be supported by an energy generation/harvesting system, e.g., solar panels.

Fig. 1

WSN node architecture: (a) power module, (b) sensor module, (c) computing module and (d) communication module

The differences in the configuration and capabilities of these modules in different nodes of a WSN can lead to diverse heterogeneous scenarios. The network (shape, size and node density) along with MAC (Media Access Control) and routing protocols are some of the factors affecting heterogeneity benefits in WSNs [19]. The differences in the energy levels of different WSN nodes, e.g., disparities in nodes’ power modules (Fig. 1a), can result in energy heterogeneity. As an example of energy heterogeneous WSN scenario, Intel deploys two types of sensor nodes (few line-powered and remaining battery-powered) in a fabrication plant to reduce the installation cost and complexity [22]. The disparities in nodes’ computing modules and communication modules (communication links) can lead to computational/computation heterogeneity and link heterogeneity, respectively (Fig. 1c, d). The disparities in sensor modules (Fig. 1b) may be needed to fulfill the dissimilar node-level sensing requirements in heterogeneous sensing applications. Further, WSN applications may require few nodes to be equipped with additional module/modules (e.g., location finding module, mobilizer and different/additional sensors), which may lead to disparity in functional behavior and/or energy consumption pattern. Wang et al. [23] show that the presence of few nodes with better capabilities (in terms of sensing and transmission ranges) can reduce the total number of required nodes without compromising the coverage and the broadcast reachability. In ideal scenario, the disparities in configurations, capabilities and/or functionalities of any module can create heterogeneity of some form and exploiting such heterogeneous scenario is a major research challenge in heterogeneous WSNs. Further, the interdependencies of different modules play a critical role in overall system performance improvement, e.g., addition of new module (e.g., additional sensors, location finding module) in a node can change its energy consumption pattern and the additional data generated through the module may further require additional computation and communication resources. The WSN routing algorithm design aims for a constructive exploitation of such heterogeneous scenarios. The routing techniques for heterogeneous WSNs are presented in the following sections.

3 Routing algorithms for heterogeneous WSNs

Most of the early routing algorithms proposed for WSNs assume that all the nodes are homogeneous in resources and capabilities. However, the assumption may not hold true in practical scenarios, e.g., a new node added to existing WSN may have more residual energy in comparison with the existing nodes in the network. The routing protocols, which help in selecting the optimum paths for data communication in WSNs, can be benefitted by the heterogeneity consideration (in terms of heterogeneity type, positioning and quantity of heterogeneous nodes) with improvement in WSN lifetime, reliability and quality.

The majority of the routing algorithms for heterogeneous WSNs have been categorized based on one of the three heterogeneities (i.e., energy, link, or computation). Figure 2 shows different heterogeneous scenarios along with the key factors (in terms of heterogeneity) generally considered in routing algorithm design. In an energy heterogeneous scenario, the nodes may be of different types based on their initial energy levels, e.g., two-level, three-level and multi-level. In two-level energy heterogeneous WSN, the initial energy of each node belongs to one of the two energy levels. In multi-level energy heterogeneous scenario, the initial energy of each node falls into one of the multiple energy levels or in more realistic scenarios each node may have a different random initial energy. The routing algorithms in such scenarios try to allocate energy-intensive operations to the energy-rich nodes, which balances the network energy drainage pattern and improves the network lifetime. The routing algorithms for WSNs with energy heterogeneity are discussed in Sect. 3.1. In link heterogeneity, the nodes have different communication link properties, e.g., few nodes with long-range communication capabilities or nodes with multiple radios. The disparities in communication capabilities and environmental factors can create asymmetric links, e.g., in a unidirectional scenario, node A can communicate its information to node B, but node B does not have communication capabilities to communicate its information to the node A. The routing algorithms for homogeneous WSN generally do not optimized for asymmetric link scenario. The two general approaches to tackle asymmetric links are either to avoid the asymmetric link or to create a reverse path for both way communications. The link heterogeneity has been exploited in WSNs and majorly in wireless ad hoc networks for improving network reliability and network delay. The routing algorithms for WSN with link heterogeneity are discussed in Sect. 3.2. In computational/computation heterogeneity, the nodes have different computation capabilities, e.g., nodes with different hardware platforms. The WSN operations, which require higher computation, can be shifted to computationally powerful nodes. The in-network processing can reduce the network traffic and it can improve network lifetime, delay and localized decision making. The routing algorithms for WSN with computational heterogeneity are discussed in Sect. 3.3. The scenario with disparities in the data traffic generation rate, called traffic heterogeneity, has also been considered under computation heterogeneity. There are many other heterogeneous scenarios like the presence of few mobile relay nodes, cooperation in heterogeneous overlapped multiple WSNs and sensing diversity maximization. A discussion on such relatively pristine areas is presented in Sect. 3.4. The energy harvesting WSNs, a special case of energy heterogeneous WSNs, can help in achieving the WSN sustainability goal. Such networks pose unique routing challenges, which are introduced in Sect. 3.5.

Fig. 2

Types of WSN heterogeneities with the key influencing factors for routing algorithm design

3.1 Routing algorithms for WSNs with energy heterogeneity

Disparities in nodes’ energy levels create energy heterogeneity in WSN. The presence of few nodes with additional battery power (e.g., line-powered nodes) is the main causes of WSN energy heterogeneity. The energy heterogeneous scenarios can be further categorized based on the energy level (generally initial energy) of each sensor node, which falls into one of the two levels, three levels or multiple/random levels. Generally, the routing algorithms designed for homogeneous WSNs do not take advantage of the additional energy of heterogeneous nodes (Fig. 3a). The routing algorithms can achieve better performance (e.g., improved network lifetime) by considering energy-rich nodes for energy-hogging operations, e.g., data aggregation, long-range communication and cluster head (CH) role. Figure 3b depicts the network lifetime improvement in a hierarchical heterogeneous WSN by giving a higher priority to the energy-rich nodes during cluster head selection. In this section, the routing algorithms for energy heterogeneous WSNs have been discussed. Few of the algorithms are similar in operations and consider minor improvements in cluster head election step to improve the energy efficiency; these are being considered for a broader picture.

Fig. 3

Cluster head selection in energy heterogeneous hierarchical WSN: a without preference to energy-rich nodes and b with preference to energy-rich nodes

The majority of the routing algorithms proposed for the heterogeneous WSNs are based on some improvements in the well-known homogeneous WSN routing algorithms deployed in heterogeneous scenarios. For example, LEACH (Low-Energy Adaptive Clustering Hierarchy) [24, 25] is one such algorithm, which serves as the cornerstone for development of other improved algorithms [26, 27]. It is a hierarchical, probabilistic, distributed, one-hop protocol, which rotates randomly the cluster heads role to evenly spread the network energy load among the sensors and further improves the energy efficiency by performing data aggregation at cluster head level. LEACH performs its operations in rounds, where each round has two phases, viz. setup phase and steady-state phase. During the setup phase, cluster heads are selected based on a stochastic algorithm and clusters are formed for the current round. The stochastic algorithm ensures that each node gets a fair opportunity to become a cluster head in the long run. During the steady-state phase, data are transferred from the nodes to the base station via their corresponding cluster head. In [25], Heinzelman et al. also discuss an energy heterogeneous scenario and express that energy-rich nodes should be considered more often for the cluster head role in comparison with the normal node. They suggest considering of nodes’ energy level relative to the remaining aggregate energy of the network in the probability of becoming a cluster head. However, the approach requires a global knowledge of nodes energy in such scenario and the performance of the approach is not evaluated in the paper. Mhatre and Rosenberg [28] analyze clustering-based WSNs for the optimum number of cluster heads and the required energy (battery) of nodes with consideration of the optimum communication mode (single-hop or multi-hop) between the member nodes and the cluster heads. In [29], they discuss the overall network cost in homogeneous and heterogeneous scenarios with consideration of energy-hardware tradeoff, i.e., tradeoff between lower hardware cost of the sensor network (achieved in the heterogeneous network scenario) and the uniform energy drainage (achieved in the homogeneous network scenario). They consider a heterogeneous scenario with an introduction of few more powerful nodes (based on hardware and battery cost). They compare the cost of homogeneity and heterogeneity in single-hop and multi-hop scenarios. For multi-hop scenario, they propose M-LEACH, which is based on the LEACH with in-cluster multi-hop routing. The in-cluster multi-hop approach is found to be more energy-efficient (in comparison with LEACH-like single-hop in-cluster approach) for the large propagation loss exponent and for the large-sized regions. Further, it is found that the heterogeneous networks become more cost-effective for increase in the relative cost of the hardware in comparison with battery cost.

In the early work, Duarte-Melo and Liu [30] consider clustering-based clock-driven (periodic reporting) energy heterogeneous WSN scenario with sensor nodes having different battery powers. It considers more powerful nodes (fewer in number) overlaid with a layer of normal nodes. The more powerful nodes take part in cluster heads selection process and the normal nodes report their data to their respective cluster head, which can further communicate with the sink node (collector). The approach can improve network lifetime; however, this approach may cause a normal node to die first if that is far away from the overlay nodes.

Smaragdakis et al. [31] propose Stable Election Protocol (SEP), which is based on a constructive energy heterogeneity consideration in LEACH protocol. They assume that a percentage of the nodes in the WSN are equipped with more energy (advanced nodes) than the remaining normal nodes. They observe that heterogeneous-oblivious protocols (e.g., LEACH) are very sensitive in such heterogeneous scenario and it can go to unstable operation at sooner stage. SEP shows an improvement in the stability period (period of the WSN lifetime until all the nodes are alive) by considering the weighted cluster head election probabilities based on the relative initial energy of the nodes.

Paruchuri et al. [32] present Energy Aware Random Asynchronous Wakeup (RAW-E), a distributed, randomized, scalable, cross-layer power management and routing algorithm for energy efficiency and balanced load distribution in heterogeneous WSN. In the approach, the nodes consider neighboring nodes’ energy level for deciding their active and sleeping periods. The energy-rich nodes remain active for a longer period in comparison with lower energy neighboring nodes. The packets are forwarded, using a greedy geographical routing approach, to an active neighbor which is closest to the destination. The approach shows improvement on its earlier variant (RAW [33]). The algorithm assumes that the locations of nodes are available; however, in practical scenario localization techniques may cost additional energy overheads.

Qing et al. [34] propose Distributed Energy-Efficient Clustering (DEEC) algorithm, which considers multi-level energy heterogeneous WSNs, where the cluster heads election probability is based on the ratio between the node’s residual energy and the average energy. The total energy and an estimate of network lifetime are known to the nodes initially. The information is used by the node to compute the average probability at the beginning of a new epoch. Further, the nodes consider different round numbers in the rotating epoch (the number of rounds for a node to again become eligible for cluster head) based on the node’s initial and residual energy to give powerful nodes (high initial and residual energy) more chances of becoming cluster head. With consideration of the initial energy and residual energy at the same time, DEEC performs better than SEP and it performs well in multi-level heterogeneous scenarios.

Kumar et al. [35] propose Energy Efficient Heterogeneous Clustered (EEHC) scheme for three-level energy heterogeneous scenario, with consideration of advanced nodes (having more energy than a normal node) and supernodes (more energy than an advanced node) along with normal nodes. The approach utilizes weighted cluster heads’ election probabilities based on the initial energy of the node relative to that of other nodes in the network. The EEHC extends the network lifetime over LEACH along with improved reliability.

Saini and Sharma [36] propose Enhanced Distributed Energy Efficient Clustering (E-DEEC) protocol with consideration of the advanced nodes and the supernodes along with normal nodes. The cluster formation is similar to the DEEC algorithm. Based on simulation results, the algorithm shows improvement in the network lifetime and the number of packets delivered in comparison with SEP algorithm.

Han [37] proposes LEACH-HPR, an energy-efficient routing algorithm with three types of energy heterogeneous nodes. The cluster setup phase considers the nodes’ remaining energy based timer approach for a balanced distribution of cluster head associated energy load. The assistant cluster head nodes (set of stronger candidate nodes under the cluster head) are introduced to assist the cluster head in information collection, information fusion and task assignment. Further, it applies a multi-hop data communication approach between the cluster heads and the base station to reduce (cluster head far away from the base station) and balance (cluster head close to the base station) the energy consumption. The inter-cluster routing utilizes a minimum spanning tree-based approach. LEACH-HPR shows efficiency in reducing and balancing energy consumption (in comparison with LEACH) and hence improves the WSN lifetime.

The Hybrid Energy Efficient Distributed (HEED) [38] protocol considers the residual energy as a primary and the network communication characteristics (based on node degree, neighbors’ distances) as secondary parameters for cluster head selection in homogeneous hierarchical WSN for network lifetime improvement. Kour and Sharma [39] consider an energy heterogeneous scenario and propose Heterogeneous-Hybrid Energy Efficient Distributed (H-HEED) protocol. They consider various scenarios with the presence of nodes with different energy levels, e.g., two-level, three-level and multi-level. The cluster head selection in H-HEED is based on HEED-like approach. Based on simulations, H-HEED shows improvement in terms of network lifetime (maximum in case of multi-level approach) over HEED protocol.

Singh et al. [40] propose HEED MultiLevel with Fuzzy Logic (HEEDML-FL), which considers five different variants based on five different levels of nodes’ energy heterogeneity. It considers the cluster head selection parameters (residual energy and node density) based on HEED protocol. Further, it utilizes a fuzzy logic implementation with two additional parameters, the average energy of the neighbors and the node to sink distance, along with the residual energy and node density during cluster heads selection. The approach shows improvement (in terms of network lifetime, throughput, average delay, etc.) over HEED and its multi-level variants.

Alla et al. [41] propose Hierarchical Adaptive Balanced energy efficient Routing Protocol (HABRP), which considers few high-energy gateway nodes along with clustering-based routing approach. The gateway nodes help in reducing the energy consumption of cluster heads; however, introducing the gateway selection algorithm in setup phase will increase the overheads. For cluster head selection, they consider weighted optimal probabilities for normal and advanced nodes based on the ratio of the node’s initial energy and the initial energy of normal node. HABRP claims improved performance (a prolonged stability period and a shortened instability period) in comparison with LEACH and SEP in heterogeneous as well as homogeneous environments.

Kumar et al. [42] propose Energy Efficient Clustering and Data Aggregation (EECDA) protocol for heterogeneous WSNs. They consider three types of energy heterogeneous nodes (normal, advanced and super), and the cluster head selection is based on weighted probabilities with the weights proportional to the node’s initial energy and inversely proportional to the initial energy of normal node. To further improve the performance, they consider energy residue of selected cluster heads and normal nodes during associating normal nodes with selected cluster heads. Based on simulation results, EECDA performs better in terms of network lifetime, stability and energy efficiency in comparison with existing protocols (e.g., LEACH).

Katiyar et al. [43] consider an idea of minimum reachability power (MRP) for cluster head selection in energy heterogeneous WSNs. During the cluster setup phase, in response to the base station’s beacon message, all the nodes calculate their minimum power requirements to reach the base station and send the information along with their residual energy to the base station. Then the base station broadcasts total remaining energy in the network and the total reciprocal of minimum reachability power (TRMRP), which helps nodes in calculating their probability of becoming cluster head. The protocol claims improved network lifetime and stability period in comparison with the LEACH protocol. However, as the MRP discovery is done only once during the network lifetime, the self-healing and self-organizing characteristics of the protocol are questionable.

Alla and Ezzati [44] propose Coverage and Connectivity Preserving Routing Protocol (CCPRP) for heterogeneous WSNs with consideration of coverage, connectivity and energy balancing in hierarchically clustered environment. The gateway nodes are introduced as additional concentration nodes to balance the load and to minimize the multi-hop paths length. The gateway node selection is based on the remaining energy of node and its distance to the gateways’ optimal location. The cluster head selection is based on nodes’ residual energy, network coverage contribution and distance to the optimal location of gateways. The algorithm shows improved performance, in terms of network lifetime, over LEACH and its variant.

Kashaf et al. [45] propose Threshold-sensitive Stable Election Protocol (TSEP) for a WSN with three levels of energy heterogeneous nodes. The cluster head selection mechanism is inspired from the SEP-based approach. It considers a reactive approach (similar to the TEEN protocol [46]), where the data are transmitted based on some threshold values. For example, nodes keep on sensing the environmental attribute set continuously (periodically) and transmit the data only when attribute set fulfills the hard threshold value. Next time they transmit the data only when the attribute set changes its value more than the soft threshold. Consideration of these threshold values reduces the network data transmission requirements drastically; however, the sink/user cannot ascertain the nodes failure as it may think that nodes are not transmitting due to not meeting their threshold requirements. Simulation results show that TSEP performs better (in terms of stability period and network lifetime) than LEACH, SEP and TEEN.

Zhen et al. [47] propose an Efficient and Dynamic Clustering Scheme (EDCS) for multi-level energy heterogeneous hierarchical WSN. The algorithm estimates average network energy and considers this estimated energy along with residual energy during the cluster head election. The non-cluster head node considers distances to the cluster heads and their residual energies while choosing his cluster head. Based on simulation results, the work shows improved network lifetime and data delivery in comparison with LEACH, SEP, DEEC, etc.

Javid et al. [48] propose Enhanced Developed Distributed Energy Efficient Clustering (EDDEEC) scheme for heterogeneous WSNs, which considers dynamic changes in the probability of cluster head election to balance the nodes energies in the E-DEEC like three-level energy heterogeneous scenario. It considers that the repeated cluster head selection of supernodes and advance nodes (in multiple rounds) will cause their residual energies to be of same level as that of the normal nodes. To avoid over penalization of supernodes and advance nodes in such scenario, they propose that all the nodes will have a same CH selection probability once the advance nodes and the supernodes have same energy levels (called absolute residual energy level) as that of the normal nodes. EDDEEC shows improvements over DEEC and related algorithms in terms of network lifetime, stability period and packet delivery.

Long and Li [49] propose LEACH Region Divided Algorithm (LRDA) with partitioning of the WSN area into different sized smaller regions based on energy consumption and number of hops. The cluster head selection is based on nodes’ energy and the cluster heads can use multi-hop communication to forward their information to the base station in the energy heterogeneous sensor network. The areas near to the base station are smaller to retain some energy for data forwarding. The simulation results show improvement in terms of network lifetime and throughput in comparison with LEACH protocol; however, it is difficult to create and maintain optimal sized partitions in a practical large-scale WSN deployment.

Yadav and Jain [50] propose Critical Hybrid Adaptive Threshold Sensitive Election Protocol (CHATSEP), a clustering-based approach for reactive networks based on TSEP-like approach with special characteristics like “criticality aware transmission” and “adaptive nature.” The criticality aware transmission step gives maximum data transmission priority to the network-specified sensed information. The adaptive nature step keeps base station dynamically aware of nodes’ status in the network if the nodes are not transmitting due to the threshold requirements of reactive network. Although the problem in TSEP algorithm related to non-availability of dead nodes status at the base station is resolved by adaptive nature step, it introduces extra overhead. The CHATSEP performs better than LEACH, SEP and TSEP in terms of network lifetime.

Kumar et al. [51] propose Multihop Energy Efficient Protocol (MEEP) for two-level energy heterogeneous WSN. The cluster head selection is based on SEP-like weighted probabilities, except for normal nodes where it explicitly considers node’s initial and residual energies. If the advanced node has not been selected as a cluster head and it is closer (in comparison with base station) to a normal node selected as a cluster head, it can relay the cluster head (normal node) data to the base station. A sleep state is also proposed to avoid transmission of uncompressed data directly to base station. MEEP, by utilizing the concepts of clustering and multi-hop communication, shows improvement over SEP protocol in terms of network lifetime, stable region and network throughput.

Maurya and Daniel [52] propose a region-based static clustering technique and a hybrid routing approach for better coverage and energy efficiency in the WSN. The network area is divided into five fixed non-overlapping regions with base station located at the center of the field and central region. The normal nodes are deployed in the central region, and they send their data directly to the base station. The energy-rich supernodes are deployed into remaining four regions and they send their data to their region-specific cluster head, which forwards the consolidated information to the base station. The cluster head selection is based on fuzzy logic-based approach with consideration of node’s distance to the base station, residual energy and load. The approach shows improvement in network lifetime and throughput; however, in practical scenarios it is difficult to select fixed regions with a selective type of node deployment.

Gu et al. [53] propose Energy and Coverage-aware Distributed Clustering (ECDC) protocol with consideration of energy and coverage. The coverage importance cost metrics is calculated for different coverage scenarios to identify the nodes which are critical for coverage requirements. In point coverage scenario, where few specific points in the region require coverage attention, the nodes with exclusive coverage over higher number of such critical points are considered critical. In area coverage scenario, where every point in the region needs to be covered, the nodes with less number of neighbors are more critical. The nodes with higher energies and not critical for coverage requirements are preferred for cluster head role. ECDC shows improved results, in terms of network lifetime and coverage, over previous protocols (e.g., LEACH, HEED).

Wang et al. [54] propose Stochastic Election of Appropriate Range Cluster Heads (SEARCH), a semi-centralized stochastic election based routing approach for heterogeneous WSNs. It modulates the cluster head selection of the nodes based on their positions, type, residual energy and cluster head energy dissipation, e.g., boosting the cluster head selection threshold for a favorably positioned node. SEARCH assures lower time, cost and optimum number of cluster heads for each round. It shows improvement in WSN lifetime (extending the life of half-alive nodes surviving) in comparison with LEACH, SEP and DEEC.

Deniz et al. [55] propose Adaptive Disjoint Path Vector (ADPV) algorithm for two-tiered fault-tolerant heterogeneous WSNs with the presence of few resource-rich nodes (supernodes). The protocol focuses on securing supernode connectivity, where the sensor node’s transmission power is adjusted dynamically in the presence of node failure. At initialization, ADPV computes alternative routes in the network. Whenever the network loses k-vertex supernode connectivity (each node connected to a supernode via k vertex disjoint paths), it activates the restoration phase which utilizes the alternative routes (computed at initialization) and accordingly adjusts the sensor nodes’ transmission ranges. A consideration of the nodes residual battery power levels prolongs the k-vertex supernode connectivity and the restoration approach improves reliability of the sensor network in link failure situations. However, the adaptation of the topological changes may be difficult to achieve in changing network conditions.

Tekkalmaz and Korpeoglu [56] propose Power Source Aware Backbone based Routing (PSABR), which considers mains-powered nodes along with the battery-powered nodes. It is a tree-based distributed approach with a backbone routing structure mainly consisting of mains-powered nodes (and few battery-powered nodes if needed). The mains-powered nodes are assigned to the resource-intensive tasks (e.g., long-range communication and computation intensive jobs like data aggregation) to reduce the energy consumption of battery-powered nodes. PSABR shows significant improvement in the network lifetime over shortest path routing algorithm (based on minimum-hop distance-based path selection). However, the improvement is intuitive, as the mains-powered nodes are not battery-constrained, and the approach may be difficult to implement in practical scenarios with limited/no availability of mains-powered nodes.

Jia et al. [57] propose a Dynamic Cluster Head Selection Method (DCHSM), which considers balancing of network energy consumption based on the energy heterogeneity and the redundant nodes. The area to be monitored is divided into clusters using Voronoi diagram, and the redundant nodes are selected as cluster head nodes of the first kind. The presence of redundant nodes does not affect the network coverage and the redundant nodes’ perception (sensing) function can be switched-off to reduce the energy consumption during the WSN operations. After death of the redundant nodes, another cluster head selection mechanism (survival time estimation algorithm) is utilized based on the ratio of the remaining energy and the average energy of the remaining nodes in the network. The proposed mechanism shows improvement in network lifetime, and the stability period over protocols like LEACH, DEEC; however, the consideration of two different types of mechanisms for cluster head selection can increase the overhead. Enhanced Dynamic Cluster Head Selection Method (EDCHSM) [58] also considers a similar approach.

Aslam et al. [59] propose two energy-efficient path planning routing methods for heterogeneous WSNs with three types of energy heterogeneous nodes. Both the algorithms, Two-Hop heterogeneity-aware Centralized Energy Efficient Clustering (THCEEC) and Advanced heterogeneity-aware Centralized Energy Efficient Clustering (ACEEC) consider a region-based network model, i.e., the network is divided into multiple regions. The algorithms consider centralized (base station controlled) cluster head election approach based on multiple parameters like initial energy, residual energy, distance to the base station and regional flag. In comparison with ACEEC, which considers single-hop inter-cluster communication, the THCEEC can utilize two-hop inter-cluster communication for better energy efficiency. The proposed methods show improvement (in terms of throughput and network lifetime) in comparison with conventional protocol like LEACH, SEP, and DEEC.

Chithra and Kumari [60] propose Energy Efficient Concentric Circular Clustering Protocol (EECCCP) for three-level energy heterogeneous WSN. The circular area is divided into concentric zones, where normal nodes and supernodes are deployed in the zones nearest and the farthest to the sink, respectively. The advance nodes are deployed in the region between the two zones. The normal nodes and the supernodes send their data directly to the sink and the advance nodes use clustering-based approach. The cluster head selection is based on node’s residual energy and average energy of the network. EECCCP shows improvement, in terms of network lifetime and throughput, over SEP, DEEC, etc. However, for supernodes, which are farther from the sink, the direct transmission might not be a good choice and in real-life application scenarios the opportunity of deterministic deployment of nodes may not be available.

Mittal et al. [61] propose Stable Energy Efficient Clustering Protocol (SEECP), a reactive protocol with threshold condition-based sensors data transmission (similar to TEEN [46]). A predetermined number of cluster heads are selected deterministically based on residual energies of the nodes. It considers dual-hop cluster head to base station communication to minimize the transmission energy of distant cluster heads not lying within an optimum proximity area to the base station. SEECP shows improved performance, in terms of stability period and energy variance, over LEACH, SEP, etc. Similar to the threshold-based selective data transmission approach, Diwakaran et al. [62] considers node’s data transmission only if it differs from the data transmitted by other neighboring nodes. The selective data transmission from the sensor nodes reduces network energy consumption and enhances the network lifetime.

Naranjo et al. [63] propose Prolong-SEP (P-SEP), a routing protocol to prolong the stable period of fog-supported heterogeneous hierarchical WSN. P-SEP considers that normal nodes are deployed randomly and the energy-rich advanced nodes are deployed at predetermined locations. It makes a fully distributed and suitable election of cluster heads based on node’s type specific weighted probabilities with consideration of average nodes energy of current round, advanced nodes initial energy, etc. P-SEP shows improvements over SEP and related algorithms in terms of stability period and packet transmission rate. However, the deterministic placement of advanced node may not be suitable in some scenarios as it requires accessibility of the application deployment area.

Yang et al. [64] propose UCR-H, an unequal cluster-based routing scheme for three-level energy heterogeneous WSNs, to avoid energy hole problem. For example, the cluster heads to the base station multi-hopped communication puts extra relay traffic load on the cluster heads nearer to the base station; therefore, the nodes around the base station depletes their energy faster, leading to the energy hole problem in the area. In the approach, the WSN field is partitioned into an optimal number of equal-sized rectangular units. The approach optimizes the number of clusters in each unit, the cluster sizes (based on the node type of the cluster head) and the round threshold (to avoid excessive penalty for higher level nodes). It considers a LEACH-like cluster head selection mechanism; and the cluster heads farther from the base station also choose a routing head from the cluster heads of the neighboring unit nearer to the base station. UCR-H mitigates the energy hole problem and shows improvement in terms of network lifetime over its predecessors like EDDEEC.

Tanwar et al. [65] propose learning automata-based multi-level heterogeneous routing (LA-MHR) for energy heterogeneous WSNs with five node types. S-model learning automata (SLA) is used for cluster head selection with consideration of node’s distance to the BS and number (normalized) of working nodes. Another SLA is used for prioritizing the CHs (spectrum allocation) based on remaining energy. LA-MHR shows improved lifetime and stability over E-SEP (enhanced SEP for three tier scenario) and other algorithms.

Borujeni et al. [66] propose FECR and FEAR algorithms for fog-supported and two-level energy heterogeneous WSN. The CH selection is based on probability function considering node’s initial energy and current energy. The CHs send their data to the nearest fog node (energy-rich nodes deployed/fixed at the network edges), which further process and route (using FECR and FEAR) the data collaboratively before sending it to the cloud. The FECR uses a PEGASIS-based approach and the FEAR uses an Ant Colony Optimization based approach. The approaches show improved energy efficiency and network lifetime over P-SEP.

Table 1 summarizes the routing algorithms for energy heterogeneous WSNs and highlights the key points.

Table 1 A qualitative overview of the routing algorithms for energy heterogeneous WSNs

3.2 Routing algorithms for WSNs with link heterogeneity

The disparities in communication capabilities (e.g., bandwidth, number of channels, communication range and antenna properties) of the sensor nodes are the main cause of link heterogeneity. The link heterogeneity is majorly exploited in ad hoc networks. The quality of received radio signal, measured in terms of received signal strength indicator (RSSI), can be affected by many factors [67], e.g., the node’s antenna height, the type of antenna and environmental temperature. The environmental properties, transceiver characteristics and asymmetric interference may lead to asymmetric links (e.g., link unidirectionality). The unidirectional link requires a multi-hop reverse path for acknowledgement messages; this makes a bidirectional link a better choice. Batmaz et al. [68] consider a sensor network with the presence of unidirectional links induced by transmission power heterogeneity (link asymmetry due to unequal transmission ranges). They show that the reverse path length has a significant impact on WSN lifetime in the presence of the unidirectional links and the reverse path with one relay node is a near optimal solution.

A link heterogeneity scenario is shown in Fig. 4, where few nodes have long-range communication capabilities. In Fig. 4a, the node capable of a longer transmission range has been ignored, which leads to a multi-hopped communication involving a number of nodes. Due to the involvement of a number of nodes, the communication in Fig. 4a will be slower (i.e., higher network transmission delay) with a higher probability of communication link failure. In Fig. 4b, the node with higher transmission range is considered, which reduces the number of hops required for the communication and it can also improve network reliability and transmission delay.

Fig. 4

Route selection in heterogeneous link scenario a ignoring high transmission range link and b utilizing high transmission range link

Jin et al. [69] propose an Energy-Efficient m-Coverage and n-Connectivity Routing (EECCR) algorithm with consideration of border effects in heterogeneous WSNs. An area is considered m-covered, if each point in the area is covered by at least m sensor nodes. The network is considered n-connected, when each of its node pair is connected by at least n mutually independent communication paths. The border effect distinguishes the network properties of the nodes based on their closeness to the network boundary. The work considers heterogeneous nodes, with different sensing range and radio range, deployed randomly in a circular region. In the setup phase, nodes scheduling sets are formed to fulfill coverage and connectivity requirements. During the data transmission phase, each scheduling set operates periodically to balance and cut down the nodes’ energy consumption and hence improves the WSN lifetime. The algorithmic overhead is quite high during scheduling-set formation in setup phase, although a back-off timer-based scheme has been proposed to reduce it.

Alizai et al. [70] exploits short-term stable long-range bursty links to improve the routing performance in terms of overall transmission. The short-term link estimation, based on overhearing neighboring nodes’ data packets, identifies the reliable periods for bursty links with better routing progress over the long-term stable links. They enhanced a routing algorithms (Collection Tree Protocol on TinyOS environment) to consider these active bursty links for data transmission. The approach falls back to regular path approach on failure of bursty links. The testbed evaluation shows that the proposed approach improves the data transmission with reasonable overhead. As the bursty links are not reliable in long runs, the approach can only improve (and cannot replace) the routing mechanism with regular reliable link.

The asymmetric links in a WSN can degrade the performance of routing protocols meant for homogeneous WSNs. The two general approaches to handle the problem are, either to avoid the use of long-range asymmetric links or to consider the extra capabilities of the high-power nodes in a constructive manner. Li et al. [71] propose a Tier-based Routing Framework (TRIF) to handle the asymmetric link problem in an ad hoc network environment while ensuring efficient utilization of high-power nodes with long transmission range capabilities. It enables the source to find an on-the-fly symmetric path to the destination and considers an optimal transmission power over each link for maintaining reliability and energy efficiency. To determine the optimum power level for a symmetric link, the sender sends a sequence of the route request packet, each with a different transmission power level (i.e., a different tier) and in a descending order of power levels. The receiver responds to the request only if its own tier is greater than the request packet’s tier. Further, it does not require any MAC layer changes for its deployment. TRIF outperforms well-known ad hoc routing protocols (AODV [72] and DSR [73]) in terms of packet delivery fraction, average end-to-end delay and normalized routing overhead in the presence of asymmetric links.

Romdhani et al. [74] propose MUlti-RAnge convergecast routing protocol (MURA) for asymmetric link environment. It takes benefit of the large transmission ranges to collect data while avoiding redundant messages and reducing the hop count from source nodes to the sink node. In TRIF, a message is sent with several levels of transmission range to avoid asymmetric links. MURA sends only one message for this purpose; however, it requires the neighborhood knowledge. MURA provides a high delivery ratio, a lower hop count, and a low duplication ratio compared to the TRIF protocol.

Li et al. [75] propose a routing approach combined with scheduling, channel assignment and power control for multi-power multi-radio WSNs. They consider nodes with one or more radios and the nodes can choose an optimum transmitted power level from a set of levels, where each level has a corresponding transmission range and interference range. They propose a distributed routing algorithm based on random walk and extend the algorithm to get benefitted by the concurrent transmissions in multipath scenario. The simulation result shows improved performance in terms of network delay.

Chen et al. [76] propose Probabilistic routing protocol for Heterogeneous sensor networks (ProHet), a distributed probabilistic routing protocol to consider the issues related to asymmetric links, reliability and scalability. The algorithm works in two parts, viz. the preparation part and the routing part. The preparation part creates a bidirectional routing abstraction by discovering neighbor relationships and determining a reverse path for the asymmetric link. The routing phase includes a probabilistic approach for selection of forwarding nodes followed by forwarding of messages and sending of acknowledgements. ProHet works in a distributed manner with low overhead and assured delivery rate to handle asymmetric links; however, it does not give emphasis on energy consumption and hotspot-related aspects.

In [77] Chen et al. propose reverse path (RP) protocol, a general framework to deal with asymmetric links. Based on the reverse path approach (with up to three hops of reverse routing path length), they propose two routing algorithms, viz. LayHet and EgyHet. The LayHet optimizes the number of broadcasts from the sender and the receivers forwarding probabilities. It manages layer numbers in the preparation part and in routing part messages are broadcasted an optimum number of times from the sender and further forwarded by the receivers with a probability based on the link states with neighbors. The EgyHet is energy-efficient variant of LayHet, which considers the remaining energy of nodes while message forwarding. The LayHet and EgyHet are proactive algorithms and outperform existing protocol (e.g., ProHet) in terms of delivery rate, average hops and overheads.

Guidoni et al. [78] propose RouT, a routing protocol for heterogeneous WSNs, based on logical topology selection. They consider two types of sensor nodes based on hardware capabilities (in terms of communication reach); L-sensors nodes and a small number of H-sensors nodes with higher hardware capabilities over L-sensors nodes. The work considers the creation of multiple logical topologies (to cater different application-specific requirements) within the same physical topology. During the routing phase, an appropriate logical topology is selected keeping in mind the tradeoff between communication latency and energy consumed in routing. The algorithm shows that application-specific topology selection in routing can help in achieving different application requirements. They also found that the presence of 10% network nodes with high wireless communication skills can ensure strict requirements regarding latency routing data.

Hong et al. [79] propose a Clustering-tree Topology control algorithm based on the Energy Forecast (CTEF), which considers energy and link heterogeneity in hierarchical heterogeneous WSN. The cluster head selection considers a cost function (based on the energy, link characteristic and packet loss rate) and the distances among the cluster heads. The energy, distance and link quality are also considered by non-cluster head nodes while choosing their cluster head. To further decrease the load on the cluster heads, relay nodes are selected from the non-cluster head (member) nodes for multi-hop communication-based data transmission. The CTEF shows improvement in terms of network lifetime and throughput in comparison with LEACH, EDFCM and EDCS.

Table 2 summarizes the routing algorithms for WSNs with link heterogeneity and highlights the key points.

Table 2 A qualitative overview of the routing algorithms for WSNs with link heterogeneity

3.3 Routing algorithms for WSNs with computational heterogeneity

Disparities in nodes’ computational resources (computation power, processor architecture, storage, etc.) are the main cause of computational heterogeneities. The heterogeneity is generally considered as a hindrance to a smooth application deployment and operations; and there is an incorrect perception that platform heterogeneity mitigation is a better option than exploiting it. Contrary to this incorrect perception, the heterogeneity can be exploited by in-network migration of computation hungry tasks (data aggregation/compression, cryptographic operations, etc.) to the competent resource-rich nodes in the network. Also, the in-network processing can reduce the effective number of bits to be communicated across the network and hence it can reduce the network energy consumption.

Reinhardt et al. [80] exploit platform heterogeneity, by transferring resource-intensive processing tasks to the other computationally powerful nodes within the sensor network, for improving the network’s energy efficiency. They consider six different sensor platforms and analyzed their energy requirements for computational and communication (wireless) operations. A sink node rooted routing tree protocol (Collection Tree Protocol) is utilized (i.e., it’s not novel), where the data are recursively forwarded until it reaches the destination. The task migration is triggered intelligently on meeting a condition that the energy requirement for communication and remote processing of the task is lesser than the local processing energy requirement. They consider representative scenarios for evaluation to prove that an intelligent exploitation of computationally heterogeneous devices can improve the WSN lifetime.

Figure 5 shows a scenario with constructive consideration of computational (e.g., platform) heterogeneity. The connecting lines between the nodes show the flow of data and the line thickness represents data volume. Figure 5a shows a high volume of data communicating across the network through normal nodes, where normal nodes do not have required in-network data processing capabilities. Figure 5b shows a reduction in effective data communicated across the WSN by utilizing high-performance node for in-network data processing. The approach could be helpful in low-latency control-decision/actuation scenarios based on in-network and edge-level information processing (Fog Computing [81]).

Fig. 5

Exploiting computational heterogeneity: a ignoring computationally powerful node and b exploiting computationally powerful nodes for improving energy efficiency of the network

Consideration of heterogeneity in node-level data/traffic generation rate is another interesting concept. The situation may arise due to nodes with heterogeneous sensing/actuating/platform requirements. Wang [82] discusses the need of traffic analysis and modeling in WSN for designing improved routing algorithms, sensor deployment strategies and fault/security management techniques, etc. A few routing algorithms for WSNs with heterogeneous traffic scenarios have been discussed in the following section.

Xiaoya et al. [83] propose Residual Energy and Energy Consumption Rate (REECR) based routing protocol for heterogeneous hierarchical WSN. The algorithm prefers nodes with high residual energy and slow energy consumption rate for cluster head selection instead of stochastic election and periodical rotation-based LEACH-like approach. The protocol shows better energy efficiency and energy balancing abilities in the heterogeneous scenario in comparison with LEACH protocol. However, the results are based on the number of rounds (WSN lifetime) comparison and the packet delivery-related aspects have not been covered.

Li et al. [84] propose Zone-based REECR (ZREECR) to improve the balancing of nodes’ energy consumption in the heterogeneous WSN. To avoid unbalanced and high energy consumption scenarios in REECR, like adjacent nodes or nodes located near the edges selected as cluster head, a zone-based approach is proposed. The WSN area is divided into different sized zones (based on distance and orientation from the base station) acting as static clusters with REECR-like cluster head selection approach. ZREECR shows improvement in stable region; however, the energy efficiency is deteriorated in comparison with REECR.

Zhou et al. [18] propose Energy Dissipation Forecast and Clustering Management (EDFCM) protocol, an energy-efficient and reliable clustering-based method for LEACH-type protocols considering energy and computation heterogeneous scenario. They present a mathematical model for the heterogeneous WSN with a function to obtain the optimum number of cluster heads. The EDFCM considers nodes’ remaining energy and rate of energy consumption in the cluster head selection process. EDFCM shows improvements over LEACH, SEP and DEEC in terms of stability period and effective messages transmitted to the base station.

Wei et al. [85] propose Energy Efficient Clustering with Traffic load consideration (EECT) for a heterogeneous hierarchical WSN scenario, where different nodes have different initial energy and different traffic load contributions. They consider both the nodes’ traffic load contribution and the residual energy during the cluster head selection. The nodes with higher residual energy and lesser traffic load are preferred for the cluster head role during the setup phase. During organizing clusters, the algorithm considers the distance between the cluster heads and their member nodes, and it also balances the energy usage of the clusters by limiting the ratio of the total cluster energy and the total cluster traffic load. The algorithm improves the stability period (in comparison with DEEC, EEHC) and performs well in scalable scenarios; however, the single-hop cluster head to base station communication in large WSN may not be an energy-efficient choice.

Barcelo et al. [86] present a multi-tree-based routing approach to manage application-specific multiple heterogeneous traffic requirements in the same WSN. They consider three different traffic scenarios in WSN, viz. event detection, critical monitoring and non-critical monitoring. The event detection scenario considers an isolated traffic pattern and it concentrates on reducing the network delay. The non-critical monitoring scenario considers a periodic traffic pattern and it concentrates on reducing the energy consumption. The critical monitoring concentrates on network reliability and its traffic pattern generally varies according to the application. The multi-tree algorithm is based on a gradient routing approach, where pilot messages are transmitted to calculate certain node’s metrics (heights) for each different traffic scenarios. Then multiple routing trees are formed, where each tree considers a specific type of traffic by utilizing its corresponding metric/heights at node level. They propose three tree-based schemes, viz. minimum delay tree, minimum consumption tree and maximum reliability tree, which consider the three different traffic scenarios to focus on delay, energy consumption and reliability, respectively. Also, the performance of the proposed approach is evaluated in a habitat monitoring application having fourteen Crossbow IRIS sensor nodes. It is shown that traffic-aware optimized trees can be constructed to cater different application-specific requirements; however, the fault tolerance and scalability aspects have not been emphasized.

In [87], Sharma et al. analyze the performance of a hierarchical-clustered algorithm (LEACH) in the presence of few traffic heterogeneous nodes. It is shown that an increase in the data generation rate of traffic heterogeneous nodes can significantly deteriorate the network stability period. It is also shown that adding few traffic heterogeneous nodes with high traffic generation rate can deteriorate the stability period; however, a further increase in the percentage of the traffic heterogeneous nodes does not affect the stability period significantly. They also propose an energy-efficient traffic-aware routing algorithm for such scenario. The proposed routing algorithm tries to avoid high traffic nodes for the cluster head role. The algorithm shows improvement in the stability period in traffic heterogeneous scenario (in comparison with LEACH); however, it does not consider aspects related to the packet delivery and the energy heterogeneity.

Al-Kiyumi et al. [88] propose Distributed Energy-aware Fuzzy Logic based routing algorithm (DEFL) for improving energy efficiency and energy balancing in a WSN with heterogeneities in node’s initial energy and energy consumption rate. A shortest path routing approach (based on Bellman-Ford algorithm) is considered to find out the minimum cost route. To calculate link cost, DEFL considers fuzzy logic approach based on nodes’ transmission energy, residual energy and energy drain rate (influenced by the traffic needs). The higher residual energy, lower transmission energy and lower drain rate are favorable conditions for relay decisions. DEFL shows improved results, in terms of network lifetime and energy balancing, over minimum total energy and other methods.

3.4 Routing algorithms for other heterogeneous WSN scenarios

This section considers the routing algorithms for WSNs with multiple heterogeneities and other scenarios, e.g., presence of relay/mobile nodes and application heterogeneity. Consideration of a few relay nodes, along with their optimized placement [89], can improve the WSN lifetime. Node placement techniques have been considered to fulfill a variety of objectives, e.g., improving network connectivity, coverage, network lifetime, data fidelity, load balancing and node failure tolerance [11, 12]. Mobility consideration in WSN routing is another emerging area with many challenges associated with network connectivity, coverage, topology, sleep-scheduling, synchronization, mobility overheads and energy cost. A few cases, focusing on heterogeneity aspects, are considered in this paper. Wang et al. [90] consider few energy-rich mobile relay nodes in a WSN with large number of static energy-limited nodes. The relay nodes and the static nodes are having same communication range and sensing abilities; however, the relay nodes can move dynamically to ease the burden of the high traffic zone. They propose a joint mobility and routing protocol for network lifetime improvement. It is shown that in an ideal case, even a single energy-rich mobile node can extend WSN lifetime by four times. It is found that the mobile relay-based approach is more efficient than majority of the static energy-provisioning methods. The mobile sink is another energy-efficient approach. Further, the mobile relay node may be beneficial in the event-based WSNs with non-uniform traffic load distribution.

Wang et al. [91] propose a Mobile sink-based improved algorithm for Stable Election (MSE), a SEP-based routing algorithm for heterogeneous WSNs with consideration of a mobile sink node. A mobile sink can avoid hot spot problem (with fixed sink node) and it can improve network latency, energy efficiency and network lifetime. A SEP-like simulation environment is considered; however, the sink is mobile with a trajectory along the central line of node deployment area. Based on simulation results, the MSE shows improvement in network lifetime and packet delivery in comparison with LEACH and SEP protocols. However, the proposed static trajectory of sink movement is difficult to achieve in practical deployments and it might not be suitable with frequent node failure and topology changing scenarios.

Sudarmani and Kumar [92] propose routing solution for clustered heterogeneous sensor network (HSN) with two-level energy heterogeneous stationary nodes and a mobile sink. They consider fixed cluster heads with load balanced clusters, adaptive transmission power controlled normal nodes and a mobile sink. Mobile sink uses particle swarm optimization (PSO) to optimize its path during data collection from cluster heads. The approach shows improvement in energy consumption and network lifetime.

Vilela and Araujo [93] present Routing Algorithm for Heterogeneous Mobile Networks (RAHMoN) with fixed nodes and energy-rich mobile nodes. They consider two different mobility models, viz. the random direction mobility model, representing UAV (sink), for edge-to-edge entire area coverage; and the random waypoint mobility model for mobile sensor nodes traversing the network. The nodes with higher mobility, greater energy and nearer to sink are considered for cluster head role. Based on simulation results, the algorithm shows efficiency in terms of overhead messages and packet delivery; however, it assumes that the nodes are aware of their and the sink’s locations.

Yao et al. [94] propose Energy-efficient Delay-aware Lifetime-balancing data collection (EDAL) algorithm, which is inspired by open-vehicle routing problems with time deadlines (OVRP-TD) technique of operational research. The open-vehicle routing research optimizes transportation cost and delivery time while distributing the goods to the customer. The heterogeneous nodes (with different radio bandwidth and transmission powers) in EDAL consume different packet transmission energy, and the packets are of different types with heterogeneous delay bounds. The nodes with less residual energy, poor communication links or more transmission cost are not preferred for data forwarding opportunities. A centralized heuristic approach to reduce computational overhead and a distributed heuristic approach for large-scale networks (improved scalability) are also proposed. The work also considers compressive sensing, a data compression technique based on the fact that most of the nodes may not have valid reporting data all the time. It improves the energy efficiency and lifetime-balancing characteristics. Based on simulation and hardware testbed evaluation, EDAL shows a substantial improvement in network lifetime without compromising the packet delay constraints.

With multiple application-specific WSNs deployed over the same area, cooperation among such WSNs has become important for their constructive exploitation. Kinoshita et al. [95] propose a fair cooperative routing algorithm to achieve a balanced lifetime improvement in heterogeneous overlapped multiple WSNs. They consider multiple heterogeneous WSNs functioning in the same area with the presence of few shared nodes, who can communicate with the available WSNs on multiple channels to relay the data packets. They propose two cooperative route selection methods, called pool-based and life-based. In pool-based approach, the shared nodes maintain the energy pool to keep account of energy consumption in cooperative communication. These energy pools are considered for optimal route selection. Another approach, called life-based route selection, considers traffic loads for better balancing in a cooperative environment. The methods show improvements, in comparison with energy-based route selection techniques, in three different scenarios, viz. heterogeneous battery capacity, heterogeneous data transmission and heterogeneous operation start time.

Amjad et al. [96] propose QoS-aware and Heterogeneously Clustered Routing (QHCR) protocol for four-level energy heterogeneous WSN. The sensor nodes under four different energy levels consider their own level-specific cluster heads based on a cost value. The cost value considers the average node distance from the neighbors, the level-specific initial energy and the level-specific number of nodes. It considers multipath intra-cluster communication, where the path metric of a path to the destination is computed based on the initial energy, the expected transmission count of the path, the path loss, etc. Based on the path metric, separate paths are selected for different traffic requirements, e.g., real-time or non-real-time traffic. The approach shows improvement in network lifetime, throughput, stability and end-to-end delay. However, the GPS-based location finding at node level, the level-specific cluster heads for whole WSN area and the centralized decision-making approach might not be the energy-efficient options for a large field deployment.

Jan et al. [97] propose Priority-based Application Specific Congestion Control Clustering (PASCCC) protocol with consideration of heterogeneity, mobility and congestion mitigation. The clustering mechanism is based on LEACH. Similar to TEEN [46], the sensor nodes maintain the hard and soft thresholds to minimize the data transmission through duty cycle optimization. The nodes can move around the field to ensure complete coverage of the WSN field. To support time-varying requirements of the applications, the queue scheduling at nodes considers prioritization of time critical packets. For example, in a temperature and humidity monitoring application, the temperature packets are given higher priority over humidity packets. The protocol improves the network lifetime and data delivery over LEACH and related algorithms.

Malazi et al. [98] consider sensor diversity of heterogeneous sensor nodes in clustering and propose Diversity-based Energy-aware Clustering protocol (DEC). During cluster formation, they prefer energy-rich nodes in the cluster head selection, while maximizing the diversity of sensor types under each cluster. The algorithm performs well in terms of sensing capabilities by improving the percentage of complete clusters, i.e., the clusters with maximum sensor type’s diversity.

Sharma et al. [99] propose SEP-T, a clustering-based routing approach for two-level energy and traffic (packet size) heterogeneous scenario. It is a traffic-aware variant of SEP and it considers nodes’ traffic requirements along with the initial energies during cluster head selection. SEP-T shows improved stability period over SEP algorithm under the traffic heterogeneous scenarios.

Sharma and Bhondekar [100] propose a Traffic and Energy Aware Routing (TEAR) for multi-level multiheterogeneous WSNs. An energy model is presented for multi/random-level energy and traffic heterogeneous WSN and the optimum number of cluster heads are identified. TEAR considers nodes’ traffic requirements along with their energy levels while making CH selection. TEAR shows improved stability period over LEACH, SEP and DEEC under the scenario.

Table 3 highlights the key points and summarizes the routing algorithms for WSNs with computational heterogeneity and other heterogeneous scenarios.

Table 3 A qualitative overview of the routing algorithms for WSNs with computation and other heterogeneities

3.5 An introduction to the routing algorithms for energy harvesting WSNs

Energy harvesting systems [based on solar energy, wind energy, thermal energy, wireless (RF) charging, piezoelectricity, etc.] along with energy management techniques (involving node-level energy management, medium access control protocols, routing algorithms, cross-layer optimization, etc.) can help in attaining sustainable wireless sensor networks (WSNs) [101]. Usage of energy harvesting systems in WSNs can introduce energy heterogeneity due to presence of selective nodes with energy scavenging capabilities and/or disparities/randomness in harvested energies due to environmental factors. Basagni et al. [102] and Anisi et al. [103] discuss energy harvesting and routing aspects in WSNs. The routing techniques for energy harvesting WSNs generally prefer the nodes with higher energy harvesting capabilities for energy-intensive operations, e.g., cluster head role. This is similar to preferring the energy-rich nodes for energy-intensive operations in an energy heterogeneous scenario. The energy harvesting nodes have additional capability to replenish their batteries during the operations; however, the replenished energy is random and difficult to model as it depends on the environmental factors. Shaikh and Zeadally [104] present a comprehensive review on energy harvesting WSNs, which covers energy harvesting modeling along with the taxonomy of energy harvesting sources and hardware aspects for such scenarios. In the following section, an introductory insight on the topic is presented with few routing techniques for the energy harvesting WSNs, which exploit the heterogeneous harvested energies in routing decisions.

Voigt et al. [105] propose solar-aware variants of LEACH, where one variant (based on centralized LEACH) considers nodes solar status (solar powered or battery powered) along with remaining energy and position while making CH decisions at base station level. To cater small sun durations (solar powered duration of the node), it also considers cluster head handover during the steady state. Another variant (based on distributed LEACH) modifies the CH selection threshold function to give higher weightage to the solar powered node over the normal nodes to improve the network lifetime.

Xiao et al. [106] propose Energy Potential LEACH (EP-LEACH), an energy harvesting capable LEACH based on energy potential (EP) function to measure the node’s energy harvesting capability. They argue that the variation in energy harvesting of the WSN nodes makes homogeneity assumption invalid. The precise formula for EP function is difficult to determine as the energy harvesting capability of the nodes depends on both hardware characteristics (e.g., solar panel characteristics, battery capacity and transmission power) and node’s ambient conditions (e.g., temperature, illumination and humidity). In the paper, a basic EP function is introduced with consideration of residual and harvested power over the harvesting interval. The cluster head selection probability prefers high EP nodes and considers node’s network familiarity based on a distance threshold. EP-LEACH shows improvement over LEACH and TEEN in terms of reduced number of node’s death during 24-h period and improved throughput variation.

Dong et al. [107] propose Distance-and-Energy-Aware Routing with Energy Reservation (DEARER), where the nodes with high energy arrival rate or close to the sink are preferred for CH role. The member nodes reserve a portion of their harvested energy for their future CH role. It performs better than direct transmission and approaches the genie-aided routing.

Xu et al. [108] propose a SEP-based algorithm (EH-SEP) for energy harvesting scenario. The algorithm considers node’s residual energy, initial energy and harvested energy in cluster head selection threshold function. It also considers multi-hopped cluster head to base station communication for improved energy efficiency. The simulation results show improved stability period over LEACH and SEP.

Jakobsen et al. [109] propose a Distributed Energy Harvesting Aware Routing algorithm (DEHAR) for multi-hop WSN. The routing algorithm is based on Directed Diffusion [110]-like approach and it considers the current energy status of the network for routing decisions. It finds the shortest paths/distances to the sink node and considers energy availability to apply distance penalties on the paths. Based on simulation results, the algorithm is adaptable to the harvested and stored energy changes.

Eu et al. [111] present Energy Harvesting Opportunistic Routing (EHOR) protocol, a multi-hopped routing approach for purely energy harvester-powered WSNs. The energy-harvested nodes participate in WSN operations only when they have accumulated/harvested a usable level of energy. The nodes are grouped into regions, and the transmission priorities are assigned based on the node’s residual energy and its distance from the sender. EHOR shows improvement in goodput (rate of unique data packets received by the sink), efficiency, data delivery ratio and fairness; however, it does not consider a 2D topology.

Li et al. [112] propose a Joint Routing and Charging (J-RoC) scheme, which considers network energy-aware joint approach for routing and energy replenishing of sensor nodes. The base station collects nodes information (data packet, energy levels, channel conditions, energy consumption rate, etc.) periodically and analyzes the collected information to create nodes charging schedule. The base station provides this information to the sensor nodes for effective routing decisions, and a wireless power charger-based mobile robot is utilized to execute the nodes charging schedule. It considers Collection Tree Protocol (CTP)-based routing with beacon costs considering charging-aware path and energy minimum path. Based on simulation results and testbed (TelosB based) evaluation, J-RoC extends the network lifetime significantly. However, the approach may not be effective in the practical scenarios, where the nodes are not accessible to the mobile robot for charging.

Bozorgi et al. [113] propose a Novel Energy Efficient Clustering (NEEC) protocol considering a hybrid of static and dynamic clustering along with layering-based multi-hop communication. Initially, the base station associates the nodes with different layers based on their distance to the base station which is utilized for inter-cluster multi-hop communication. It also compute nodes’ neighborhood attributes. Then clusters are formed in a distributed manner, where the chance of a node to become cluster head depends on the node’s energy level, the harvested energy, neighborhood attributes and closeness to base station. The results show improved energy efficiency and throughput in comparison with earlier protocol (e.g., ECDC).

Bahbahani and Alsusa [114] propose Energy-Harvesting and Cooperative LEACH (ECO-LEACH), a cross-layer design with combining clustering, duty cycling and cooperative transmission to achieve higher energy efficiency and energy neutral operation. It considers a duty cycle-based cluster head selection (based on energy harvesting capabilities) instead of probabilistic approach of LEACH protocol. Further, the TDMA approach for intra-cluster communication is enhanced, where the member nodes can skip transmission during their assigned timeslots to maintain energy neutral state and the nodes can select TDMA frame in another duty cycle where they are available to work as a relay. The duty cycles’ selection is based on the rate of energy harvesting, packet arrival rate and cluster heads optimal percentage. The ECO-LEACH shows improvement in lifetime and throughput over LEACH and its harvesting energy-aware variant.

A key challenge for routing algorithms in energy harvesting WSNs is to maximize the autonomously sustainable workload in the network. Lattanzi et al. [115] present a methodology for assessing the energy efficiency of routing techniques for energy harvesting wireless sensor networks. It considers that the routing optimization in such scenario should focus on maximizing autonomously sustainable workload, represented by maximum energetically sustainable workload (MESW), instead of network lifetime. The work shows that improved workload sustainability in routing can be achieved by considering environmental power distribution. This opens a new challenge for routing algorithms to become adaptive to the time-varying environmental conditions. Consideration of real-world scenarios, with heterogeneous nodes along with energy harvesting systems, further complicates the routing algorithm design challenges. Table 4 highlights the key points and summarizes the routing algorithms for energy harvesting WSNs.

Table 4 A qualitative overview of the routing algorithms for energy harvesting WSNs

4 Routing in heterogeneous WSNs: interdependencies and future research directions

The evolving IoT landscape needs a synergy among the highly heterogeneous sensing and actuation platforms. To support IoT vision in low-power and lossy networks (LNN), IETF standardized a routing protocol for LNN (RPL) [116, 117]. The presence of technological heterogeneity in different proprietary and non-proprietary WSN solutions is a big challenge for achieving a pervasive integration of sensor networks with Internet [118]. Heterogeneity in WSN can be generalized as existence of disparities in nodes’ hardware configuration and/or functional capabilities. Qiu et al. [119] discussed the architecture and the issues of future heterogeneous ad hoc networks (including WSNs). They envisioned self-organizing algorithms, efficient data fusion, designing of efficient smart hardware and emergency response strategies (e.g., queuing mechanism, fast routing) among the mainstream future research. As the WSNs are resource constraint networks, the routing algorithms in WSNs concentrate on optimal resources utilization. The routing algorithms for various heterogeneous WSN scenarios have been discussed in the previous sections. The routing decisions in realistic multi-heterogeneity scenarios requires an understanding of interdependencies of different heterogeneities, e.g., improved computational and/or link-based performances affect nodes energy consumptions, and the nodes’ energy consumption can again affect the nodes’ connectivity and computation-related decisions.

The routing algorithms for energy heterogeneous WSNs try to balance the network energy consumption pattern to achieve an overall gain in network lifetime and stability period. Many energy-efficient routing algorithms have been proposed for two, three or multiple/random levels energy heterogeneous scenarios. The routing algorithms with consideration of multi-level energy heterogeneous scenario (e.g., nodes with random initial energies) can handle real-world WSN deployments more effectively. In practical scenarios, it is difficult to achieve that all the nodes will have the same initial energies and the same energy consumption pattern during network operations. So, the routing decisions must consider energy heterogeneous scenario and the designing of such energy-efficient methods remain one of the challenging research directions in the field.

The link heterogeneity can help in improving network reliability and network transmission delay. The long-range link can replace the multi-hopped communication, which is slower and more prone to node failure (as more nodes are involved in the multi-hopped communication). The major challenge for routing algorithms in link heterogeneous scenarios is to tackle asymmetric links and to exploit long-range links. Further, the long-range wireless (RF) communication consumes more energy, as the energy consumed in RF transmission for a distance d is proportional to dⁿ, where n ≥ 2, e.g., n = 2 for free space or n = 4 for multipath fading scenarios. So, it is logical to use energy-rich nodes for such long-range communications. Further, to ensure energy efficiency, the optimal transmission range can be targeted using transmission power control approach.

The computational heterogeneity considers fruitful exploitation of the disparities in nodes’ computing resources. In such scenario, a routing algorithm should not only aim for platform-independent functioning, but it should also exploit the disparities in hardware platforms by shifting the processing intensive tasks (data fusion, complex data processing, etc.) to suitable computationally powerful node. However, the task migration decision should be made only when the migration benefits surpass the migration overheads. The in-network processing can reduce the effective number of bits to be communicated across the network and hence it can reduce the network energy consumption. It can decrease the processing latency in immediate nodes and improve the delivery rate. Similar to the fog computing, the in-network and edge-level information processing can help in making low-latency localized control decisions, which can be helpful for triggering the in-network actuators. As the higher computation/processing increases the energy consumption, it is a good idea to support these nodes with better energy sources/batteries. The disparities in sensor modules (e.g., different nodes having different sensors, few nodes having multiple sensors) may introduce disparities in node-level data/traffic generation rate. Traffic heterogeneity consideration in WSN routing algorithms is another interesting research direction for applications having heterogeneous traffic requirements.

Consideration of multiple heterogeneities in a single WSN is another interesting area. Majority of the algorithms have been optimized and analyzed for some particular heterogeneous scenario. In link heterogeneity, the nodes with long-range communication links consume more energy. In computational heterogeneity, the nodes processing more information (number of bits) can consume more energy; however, the computing/processing energy (for information in bits) is quite less in comparison with the energy consumed in RF transmission. Consideration of mobile sink or few mobile relay nodes can also improve routing performance; generally, these nodes are also energy-rich nodes. Energy heterogeneity can be used along with other heterogeneities, where the energy-rich nodes are preferred for resource-intensive operations, e.g., long communication range relay node, information processing node. A few routing algorithms consider the presence of multiple heterogeneities in the WSN, e.g., EDFCM [18] considers energy and computational heterogeneity; CTEF [79] considers energy and link heterogeneity; Wang et al. [90] consider few energy-rich mobile relay nodes along with large number of energy-limited stationary nodes. An ideal routing algorithm should work optimally in any random heterogeneous scenario, which is a great challenge for the researchers.

WSNs are application-specific in nature, and the performance of a WSN not only depends on the node’s characteristics, but also on the environment and the nodes’ deployment. Heterogeneous resources can be introduced in WSN to fulfill the requirements of the application and to improve the application-specific WSN characteristics (e.g., network lifetime, reliability and delay). Consideration of few nodes with energy harvesting systems can improve the WSN performance drastically. However, finding the best-suited heterogeneous solution (heterogeneity type, nodes quantity, heterogeneity levels, node placement, etc.) for a given application requirement is an interesting challenge in the area. Further in an IoT scenario, the information insight received from the cloud/web can also benefit the routing and MAC algorithms in WSNs, e.g., the weather forecast information from Internet can help in prediction of solar/wind harvesting energy, which can help in improving power-management, routing and/or MAC decisions in energy harvesting WSNs. Machine-learning-based intelligent techniques are proposed for many WSN functionalities (including routing) [120] for improving adaptability to the environmental variations. Their application in self-organizing intelligent routing algorithms for dynamic and heterogeneous WSN environments is also an interesting research direction.

A sensor network with application heterogeneity has a greater role to play in Internet of Things arena, where heterogeneous applications specific nodes can use the same sensor network for communicating their information to the cloud through sink node (gateway). The routing algorithms with an application-specific topology selection or a multi-tree-based routing approach to manage application-specific heterogeneous traffic requirements are some of the possible solutions. Designing routing algorithms for such application heterogeneous WSNs is an interesting and challenging research direction. Another interesting area is cooperation in different independent overlapped WSNs to improve the performance of the installation. Further, interoperability of different routing algorithms, which is common in computer networks, could be another interesting research area for future WSNs.

Comparative evaluation of protocols requires effective methodologies for performance analysis. Gerwen et al. [121] propose a benchmarking mechanism for effective performance evaluation of WSN solutions. An effective benchmarking method for performance evaluation of WSN routing algorithms in the given scenario could help in finding and developing effective routing solutions with improved trust. The commercial success of a routing algorithm requires a thorough testing in real-life WSN deployment scenarios for various parameters, e.g., network lifetime, throughput, scalability and fault tolerance. The performance of the most of the routing algorithms has been evaluated on simulation platforms, and their experimental evaluation is required for finding their applicability in the real-life deployment scenarios.

5 Conclusion

The consideration of WSN heterogeneities in WSN routing algorithms has become unavoidable in practical scenarios. This paper provides a survey of the most impactful and the most recent works that focus on the performance improvement in heterogeneous WSNs through efficient routing algorithms. Based on the sensor nodes’ configuration and functional capabilities, the WSN heterogeneities could be of many types, e.g., energy heterogeneity, link heterogeneity, computational heterogeneity, traffic heterogeneity and application heterogeneity. The paper provides a broad coverage of the work, and it discusses a variety of routing algorithms for different heterogeneous scenarios along with the key challenges and the future research directions in the area. The interdependencies of different heterogeneities for routing decisions have been discussed and the routing algorithms for WSNs with multiple heterogeneities have also been considered. The paper also discusses the routing scenarios in WSN with multiple heterogeneous application-specific requirements and the scenarios related to the cooperation among multiple application-specific heterogeneous WSNs. The paper establishes that the routing algorithms in heterogeneous WSN scenarios can be exploited constructively to improve the WSN performance, e.g., to extend the network lifetime, to improve reliable data delivery and to reduce data transmission latency. Although the majority of the work discussed in the paper is based on the research findings and their commercial exploitability is not well addressed, the concepts discussed in the paper are very significant for developing improved routing algorithms for application-specific heterogeneous WSN scenarios.