Keywords

1 Introduction

Wireless sensor networks (WSNs) is an infrastructure-less network that consists of at least one base station (BS) and a plenteous amount of sovereign sensors having capabilities like data processing and communication, disseminated to cover a large geographical region. These BS receives the data from these disseminated sensor nodes. Because of wireless nature, WSNs are easily deployable. The evolution of WSNs was initially stimulated by armed forces for supervision in conflict zones, tracking militancy, tracking opponents movement [1], but now the application is extended to medical and health, industrial infrastructure, calamity management, habitat monitoring etc. [2], thereby connecting the three distinct world, i.e., the physical realm, the computing world, and the human society. A typical wireless sensor network’s sensor nodes are composed of a radio transceiver having an antenna, a microcontroller, a sensor interfacing electronic circuit and a power supply, usually a battery. The capability of a single sensor node is limited which makes them inadequate in congregating valuable information from a particular domain [3]. To accomplish the data congregation process, hundreds or even thousands of sensors are deployed to work collectively. WSNs do not have need of a central organization and are self-configurable. Since WSNs mostly have a dense deployment of sensor nodes, this provides the ability to withstand harsh environmental conditions without network failure [4].

WSNs catch their application in very diverse areas. Having a look at the projects involving WSNs around the globe, we can broadly identify different types of WSNs [5], like structure sensor network (SSN), transport and logistics sensor network (TSN), body sensor network (BSN), environmental sensor network (ESN) and participatory sensor network (PSN).

The sensor nodes in wireless sensor networks perform the task of collecting raw data from deployed region along with data storage, some local data processing and routing [6]. The processed information is then passed to the intended base station. In doing so, the sensor nodes consume energy. Mostly, sensors are powered by small batteries which cannot be replaced or even recharged because of the deployment of sensors in unattended environments. So, energy constraints must be taken into account in WSNs design goal. A large number of sensors and the energy constraints provoke for some energy-aware routing algorithms and data gathering protocol which can offer an extended lifetime of sensors and scalability [7]. To achieve high energy efficiency, extended lifetime and scalability objective, the research community has widely adopted the idea of grouping sensor nodes into clusters in large-scale WSN environments.

The hierarchical network structure has a two-level hierarchy. Each cluster in the network elects a particular sensor node as the cluster head (CH) for coordinating the data gathering and aggregation process in the cluster. The CHs nodes form the upper level and all other nodes in the cluster constitute the subsequent level. The CH node accumulates data from sensor nodes within its neighborhood and passes them after processing and aggregation to the base station through other intermediate CH nodes or directly. The energy drain rate for CH nodes is higher than the ordinary sensor nodes because CH nodes transmit data over a long range (CH to base station) while other nodes communicate only with CH nodes within their cluster. Figure 1 shows typical hierarchical network architecture for a wireless sensor network. The figure shows a number of sensor nodes organized in different clusters and having a particular node as their respective cluster head (CH) which gather data from other plane nodes within the cluster and transmit it to the sink or base station after necessary processing. In order to optimize the energy consumption, one can switch the CH responsibility among other sensor nodes in the cluster by periodically re-electing new CHs in the cluster [7]. Clustering provides certain advantages such as reduction in communication overhead, eradication of data redundancy and increased efficiency of data transmission with drawbacks like overheads in cluster formation and election of CHs [6].

Fig. 1
figure 1

Hierarchical network architecture of a WSN

Full size image

In this chapter, we have provided a broad survey of some existing hierarchical routing protocols proposed recently. Based on certain metrics, we also plan to compare the performances of these protocols.

The rest of the paper is organized as follows: Sect. 2 covers a brief description of research that has been carried out in this area. The overview and classification of WSN hierarchical routing protocols along with the design challenges that must be taken care are discussed in Sect. 3. Section 4 presents the comparison of performances based on certain attributes. The last section concludes the paper.

2 Related Work

Several research studies have been done in the context of classifying and comparing the routing protocols for wireless sensor networks. These comparisons give an idea about their behavior and effectiveness. Deosarkar et al. [8] presented a detailed discussion of different clustering schemes emphasizing mainly on the taxonomy of adaptive, deterministic and combine metric scheme based cluster head selection strategies. They compared the CH selection cost with that of cluster formation, creation of clusters, and distribution of CHs.

A survey on clustering algorithms by Jiang et al. [9] was presented by giving the taxonomy of clustering schemes for WSN based on certain clustering attributes and discussing some prominent advantages like less overhead, easy maintenance and more scalability for WSNs. Clustering algorithms like LEACH, HEED, PEGASIS, and EEUC were analyzed and compared.

Abbasi and Younis [10] surveyed the present clustering algorithms and give a taxonomy of clustering algorithms. They presented a summary of WSN clustering algorithms based on convergence time, highlighting their features and complexity. Based on certain metrics like cluster overlapping, stability, rate of convergence and mobility support, they compared these clustering approaches.

Yadav and Rana [11] presented a survey on cluster based routing strategies in WSNs suggesting a taxonomy of the clustering protocols. They have discussed in detail the merits and limitations of various cluster based protocols like GAF, SLGC, HGMR, TSC, PEGASIS, HCTE, BCDCP, MWBLA, and LEACH-VF and also compared these protocols for their performances based on certain performance attributes like load balancing, algorithm complexity, delivery delay, etc., thereby concluding that cluster based routing strategies are much more efficient than other schemes in performance enhancement of WSNs.

A general classification of various cluster-based protocols for WSNs based on CH selection and cluster formation parameters is given by Kumarawadu et al. [12]. They have discussed some design challenges and performance issues of probabilistic cluster based, neighborhood information based, biologically inspired clustering and identity-based clustering algorithms.

Maimour et al. [13] discussed clustering routing protocols from the perspective of achieving energy efficiency and presented a review from data routing perspective, proposing a simple categorization of routing protocols for clustering in WSNs. Pre-established and on-demand clustering routing protocols are discussed along with nine other clustering protocols.

Wei et al. [14] presented a review of state-of-the-art routing methods for wireless sensor networks outlining the clustering architecture. Based on attributes like the hop count between CH and nodes, parameters for CH selection and the existence of centralized control during cluster formation, they have given a simple classification of clustering routing protocols. Some design challenges were also discussed.

A comparative analysis to improve the network lifetime for certain WSN clustering routing algorithms is presented by Haneef and Zhongliang [15] along with the design challenges that comes into the way and affect the design of WSN’s routing protocols. The authors presented a taxonomy of routing protocols and a comparative analysis of many efficient clustering based routing protocols is given.

Lotf et al. [16] surveyed some clustering protocols and discuss their operations along with their advantages and limitations. The authors compared clustering algorithms like EECS, TEEN, APTEEN, and LEACH on the basis of network lifetime and energy consumptions.

A brief introduction of design goals of clustering and overview of operations of proposed clustering algorithms are given by Dechene et al. [17]. The authors have examined the performances of heuristic, weighted, hierarchical, and grid-based clustering algorithms from two aspects: power, energy and network lifetime; and quality and reliability of links.

A simple survey by Xu and Gao [18] of clustering routing protocols is presented. The authors have described only six clustering algorithms. Comparison of these routing algorithms has been done based on certain performance factors like data aggregation, robustness, network lifespan, energy conservation, scalability, and security.

A detailed survey of chain-based routing protocols has been presented by Marhoon et al. [19] highlighting the characteristics of the chain based routing and discussing the advantages and disadvantages of these protocols over other classes of protocols by explaining the functioning of many of the chain-based routing protocols. They have discussed the protocols like PEGASIS, CRBCC, REC+, BCBRP, RPB, and PCCR.

3 Overview of Hierarchical Routing Protocols

In WSN, the responsibility of routing implementation for the data coming to the network is done by the network layer. In single-hop networks, the source node can directly communicate with the sink but this is not the case in multi-hop networks. In multi-hop networks, the data packets transmitted by source node are relayed by the intermediate hops in the network so that the data packets can reach the sink. In all these scenarios, routing tables has to be maintained for smooth operation and are governed by some routing protocols. Network structure, communication initiator, routing path establishment, protocol operation and selection of next hop are some criteria to classify the routing strategies in WSNs. Further, the routing protocols based on wireless network architecture can be categorized into three subcategories namely flat, hierarchical and location based routing protocols. The role of sensor nodes is same in flat routing in comparison to that in hierarchical routing. As routing decisions are inherently localized, the location-based routing allows the network size to be scalable without a significant increase in signaling overhead. Our main focus in this work is on network structure based hierarchical routing protocols.

The selection of nodes makes hierarchical routing energy-efficient in a way that sensing information is assigned to the nodes with low energy while data processing and transmission task are assigned to nodes with high energy. Thus, increased lifetime, scalability and energy minimization can be achieved. The hierarchical routing can also be called as cluster based routing. Block, grid, and chain cluster based routing protocols are the typical classification of hierarchical routing protocols [20, 21]. Figure 2 shows a taxonomy of network structure based routing protocols.

Fig. 2
figure 2

Taxonomy of network structure based routing protocols

Full size image

3.1 Challenges for Hierarchical/Clustering Protocols

In WSNs, clustering seems to play an important role. Clustering in WSN improves bandwidth utilization, thereby reducing the useful energy consumption and it also reduces the wasteful energy consumption as a result of reduced overhead [22]. However, besides several advantages, clustering scheme must take into account certain key limitations which are of particular importance in WSNs [23].

Network Lifetime: The energy limitations on sensor nodes greatly affect the network lifespan for sensor nodes in a wireless network. Effective clustering aids in reducing energy usage in intra-cluster and inter-cluster communication, thereby increasing network lifetime.

Limited Energy: Sensor nodes in WSNs are operated by small size battery, so their energy storage has a limit. This limited energy must be used efficiently, and must be taken into consideration as overall energy consumed in the network can greatly be reduced by applying proper clustering scheme.

Limited Capabilities: Numerous abilities of sensor nodes like processing, communication range, storage, and memory get limited by the small amount of stored energy and small physical size of sensor nodes. It is possible to make efficient use of shared resources within an organizational structure by applying good clustering algorithm, simultaneously taking the limitations of sensor nodes into account.

Cost of Clustering: Clustering plays a key role, but at some cost. Certain resources like processing tasks and communication are always required in creating and maintaining the clustering topology. Costs involved in these tasks are overhead as these resources will not be used for sensing or transmitting data.

Cluster Formation and Selection of CHs: The physical dimension of a cluster or the number of sensor nodes within a cluster may play a vital role in the functioning of a cluster for a particular application. Therefore, the designers have to examine cautiously the cluster formation in a network while designing for a particular application. These criteria also have an impact on election and re-election of cluster heads (CHs) within the cluster.

Scalability: In WSN, the coverage range of the nodes is limited. This leads to the deployment of thousands of sensor nodes where a relatively larger area has to be covered. Therefore, the routing protocols in such scenarios must be capable of handling a vast amount of sensor nodes. In a network with a massive number of nodes, it is not possible to preserve the global information of network topology for every node in the network.

Data Aggregation: The larger wireless sensor networks are often densely populated. In such scenario, there is always a possibility that multiple nodes sense similar information. Therefore, there must be some mechanism which can eradicate data duplication. Data aggregation is a technique which differentiates useful data from sensed data. Data aggregation capabilities are being provided by many clustering algorithms. So, while selecting a clustering approach, the requirement for data aggregation must be carefully considered.

Synchronization: Limited energy capacity of sensor nodes has an adverse impact on the performance of wireless sensor networks. Energy usage can be minimized by allowing sensor nodes to repeatedly schedule sleep interludes through particular slotted transmission scheme such a TDMA. To have a proper setup and maintainable transmission schedule, such schemes require certain synchronization mechanisms. Thus, synchronization and scheduling will have a great impact on overall performance of WSNs while considering a clustering scheme.

Secure Communication: In hierarchical routing protocols, communication takes place within the cluster as well as outside world. An energy efficient and secure inter-cluster as well as intra-cluster communication is one of the most important challenges for clustering protocol design.

Repair Mechanisms: Because of the absence of static structure, the wireless sensor networks are frequently prone to node movement, delay, interference and node demise. A link failure can occur as a result of these situations. Therefore, while looking for clustering schemes, link recovery and reliable data communication mechanism must be considered.

Quality of Service: Quality of service (QoS) requirements in WSNs is very important aspect from an overall network standpoint. These services are prompted by the functionalities and applications of the network. Some application-dependent QoS requirements are packet loss tolerance, acceptable delay, and precision. The main focus of most existing clustering routing algorithms is to provide energy efficient network utilization rather than QoS support. The design process must consider the QoS metrics for better network performance.

4 Comparison of Hierarchical Routing Protocols

In this section, we present the comparison between some popular hierarchical routing protocols like LEACH, HEED, EECS, EEHC, LEACH-VF, PEACH, CCM, PANEL, TTDD, GAF, SLGC, HGMR, CCS, PEGASIS, and TSC in WSN based on important metrics like cluster stability, scalability, mobility, energy efficiency, data aggregation, and delivery delay in Table 1.

Table 1 Comparison between different hierarchical routing protocols in WSNs
Full size table

From this comparative study, we observe that:

  • Block cluster based routing protocols provide better cluster stability than others.

  • Very few (e.g., HGMR) provides very high scalability and other provides moderate to low scalability.

  • Most of the protocols provide no mobility (e.g., EECS, EEHC) while few protocols provide limited mobility (e.g., HEED, CCM).

  • Block cluster based protocols provide better energy efficiency than others.

  • Most of the grid based protocols does not support data aggregation.

  • The delivery delay varies from very low (e.g., SLGC) to very high (e.g., TTDD, PEGASIS).

5 Conclusion

Wireless sensor networks have received much attraction in recent years and find their application in an extensively broad spectrum like environmental monitoring, security surveillance, and military applications. In WSNs what is more challenging is the design of routing protocols which can support robustness, effectiveness, and scalability. The hierarchical based routing protocols can well match the challenges and constraints of WSNs.

In this paper, we have provided an in-depth analysis of protocols for hierarchical routing used in WSNs and also established a taxonomy of network structure based routing protocols. In our work, we have focused on certain merits and limitations of some popular network structure based hierarchical routing protocols based on certain attributes and presented the result in a tabular form. The comparison analysis reflects that application of hierarchical routing to wireless sensor networks improves their performances up to a great extent. In future, the information provided in this paper can be used by researchers willing to devise their own hierarchical routing protocol.