Keywords

1 Introduction

Wireless sensor network (WSN) consists of resource constraint tiny sensor nodes (SNs) [1, 2]. In most of the scenarios, SNs are deployed in the hostile and unreachable area for human beings in order to minutely observe various phenomenon and activities of the environment [2]. It has diverse applications in various fields ranging from small to a large area or sparse to dense deployment or dynamic and static deployment [3].

For longer network lifetime, there is a need to save the battery power of SNs irrespective of deployment strategy [4]. There are many routing protocols based on clustering which claim for energy efficiency to maximize network lifetime [5]. In clustering, WSN is logically divided into groups known as clusters. Each cluster consists of one cluster head (CH) and one or more member nodes (MNs). Election of CHs may be decided by MNs in collaboration (communication) or by doing computations [6]. The computation may save energy in comparison to communications [6].

A CH may save energy either by data aggregation to avoid redundant data transmission and reduce congestion [7] or by reducing delay latency in the packet transmission or by load balancing [8]. Hence, clustering in WSN is still the topic of research in WSN [9].

This paper presents a hierarchical clustering multi-hop communication approach which tries to (i) cover the target area by means of connectivity of clusters by inter-cluster and intra-cluster communications in the WSN (ii) prolong the network lifetime.

The organization of this paper is as follows: Section 2 presents the related work. Section 3 presents the proposed problem and solution. Section 4 analyses the simulation results. Section 5 concludes the paper.

2 Related Work

This section presents related work on cluster-based routing protocols in WSN.

LEACH [10] declares CH based on the threshold value. CH election may have high message overhead which may consume extra energy. In LEACH, CHs may consume more energy compared to the other nodes of the cluster as CHs do single-hop communication with the base station (BS).

TL-LEACH [11] is similar to LEACH with the two-level hierarchy of CHs. The nodes send their data toward BS through secondary CHs and then primary CHs. The two-hop communication in TL-LEACH effectively reduces the total energy usage. A secondary CH has to be in transmission range to a primary CH and a primary CH has to be in communication range to the BS. Then, it assures for successful delivery of data to the BS.

LEACH-C [12] is a centralized clustering algorithm where each node sends information about its location and residual energy to sink. For this, it needs GPS or other tracking methods.

HEED [13] forms clusters and CHs based on two parameters, namely residual energy and cluster density. HEED may take several iterations to form clusters which increase the number of packets exchanged. EG LEACH [8] is the same as LEACH which uses improved threshold condition to consider residual energy into account. It ensures proper selection of CHs in every round.

TEEN [14] is a hierarchical clustering reactive protocol which is based on LEACH protocol for CH selection and cluster formation. APTEEN [15] is the advancement of TEEN protocol; BS forms the cluster which exists for an interval called cluster period. BS has the power to transmit directly to all the nodes in the network.

EECS [16] uses hop communication between CH and BS which may result in longer delay ratio. In UCBR [17], BS through informer nodes knows the location and initial energy of all SNs based on which it decides the radius and CH sequence table for every cluster. A node determines its CH on the basis of received signal strength of advertisement message from CHs. CHs uses location-based multi-hop communication to forward data to BS.

In PEGASIS [18], all nodes form a single-chain structure where a single node takes a turn to transmit data to the BS. Data from nodes is to be transmitted to the nearest neighbor node saving larger transmission energy cost. Load on the cluster member which is closer to CH increases due to the chain. CCS [19] is a modification of PEGASIS protocol where the whole network is divided into co-centric circular tracks called clusters. The members of a cluster form a single-chain structure choosing one of them as the head node. BS forms level-wise hierarchy. Data redundancy exists in CCS because data from a node which is far away from its CH has to travel a large distance in order to reach its CH.

TSC [20] is a hierarchical clustering based on the concept of tracks and sectors. It breaks long chain formed in a single track of CCS into sectors, where each sector now represents clusters that are a level may have more than one clusters. In [21], the chain of PEGASIS protocol is logically divided into a layered transmission node tree.

Authors [22] summarize different routing protocols based on clustering of WSNs during the year 2000 to 2016. Authors [7] present existing hierarchical-based routing protocols during the year 2000 to 2004. It concludes that the hierarchical routing helps in declining the number of redundant messages transmitted to the BS.

Clustering hierarchy protocol based on PSO algorithm [23] is a centralized approach in which BS uses location, residual energy, relay nodes to form clusters and CHs. To reduce the transmission energy cost of CHs, relay nodes are used. CHs send their data to relay nodes which forwards data to BS.

EECP-EI [24] is a multi-level protocol. Selection of CHs and formation of clusters are based on the energy of sensor nodes. The minimum transmission range is set for all nodes in order to form a hierarchy. The CHs are supposed to lie at a minimum distance of ten meters from destination CH.

Authors [25] present a review on recent clustering solution based on machine learning techniques. Concepts like fuzzy logic, swarm intelligence, etc., are used to form clusters. In some of these protocols like ABC-SD, PSO-ECHS, PSO-C, etc., BS use location information of nodes in order to form clusters.

The above protocols do not guarantee connectivity among CHs as there may be a possibility of selection of CHs which may not be in the direct communication range of any other CH in the network. This may happen when the cluster formation is not centralized. In such a case, the formation of the hierarchy is not possible. This paper proposes a solution to establish intra-cluster and inter-cluster communications in the hierarchy.

3 Proposed Problem and Solution

3.1 Proposed Problem

Single-hop communication between CHs and BS is suitable in small-target areas. In large-target areas, BS may use location data of SNs to build hierarchy among CHs. It may not be possible to form hierarchy among CHs when clusters are formed independently or clusters are formed based on local information. Some routing protocols form a multi-hop communication hierarchy from BS, but they fail to describe how the hierarchy will be formed when a CH is not in direct communication range of any other CH in the network. This situation may result in the non-transmission of data toward BS. This paper proposes an algorithm to solve these issues unless a hole is present in the network during deployment itself.

3.2 Network Model

Figure 1 presents the network model of the proposed algorithm. The network model is based on multi-hop hierarchical clustering approach. Communication between the CHs to the BS can be in single or multiple hops. Member nodes communicate to their CH directly or by way of proxy CH.

Fig. 1
figure 1

Proposed network model

Full size image

3.3 Assumptions

  1. (i)

    SNs are static.

  2. (ii)

    Every SN has a unique ID.

  3. (iii)

    Single BS is inside the network.

3.4 Proposed Algorithm

  1. 1.

    Cluster-formation phase (modified version [6])

  2. 2.

    Hierarchy-formation phase

    1. (a)

      Case 1: Hierarchy formation between CHs if they are in communication range of each other.

    2. (b)

      Case 2: Hierarchy formation between CH (already joined in the hierarchy) and a MN of another cluster whose CH is not in communication range to any already joined CH in the hierarchy.

    3. (c)

      Case 3: Hierarchy formation between a MN (whose CH has already joined hierarchy) and CH which has not joined hierarchy.

    4. (d)

      Case 4: Hierarchy formation between a MN (whose CH has already joined hierarchy) and a MN whose CH has not joined hierarchy.

  3. 3.

    If a cluster is not able to join the hierarchy by above four cases of hierarchy formation, then it is a hole in the network.

  4. 4.

    The algorithm terminates, after all, CHs have either joined hierarchy or is declared as a hole.

3.5 Explanation of the Proposed Algorithm

Cluster-Formation Phase The proposed algorithm chooses CH based on computation [6]. Figure 2 describes the cluster-formation phase of the proposed algorithm. Every node randomly takes a value 0 or 1 for variable p. If p = 0, then the node generates a random value x.

Fig. 2
figure 2

Cluster-formation phase a initialization b synthesis phase

Full size image

Now holdback value will be xth random value. holdback value restricts SN to either declare or not to declare itself as CH. If p = 1, then that particular node will generate holdback value only once. This may decrease the probability of generating the same holdback value for neighboring nodes.

Initially, every node has a cluster identity (CID) which is initialized as NULL. If holdback = 0, then node declares itself as CH and broadcasts the clustering message CLUSTER (CID, noh) where noh = 1 is the hop count. Upon receiving this message, nodes check their CID value. If CID = NULL, then CID = cid to join the respective cluster. The holdback value decreases after every time ‘t’ until the node joins a cluster or declares itself as CH. After the cluster-formation phase, the entire network gets divided into a group of clusters.

Hierarchy-Formation Phase. In this phase, BS starts the formation of hierarchy among CHs. This assures for intercommunication between two clusters. This phase may use the following cases: (i) Case 1: CH to CH (ii) Case 2: CH to Member (M) (iii) Case 3: Member to CH (iv) Case 4: Member to Member. Figure 3 describes the hierarchy-formation phase of the algorithm.

Fig. 3
figure 3

Hierarchy-formation phase

Full size image

Case 1

CH1 to CH2 (CH–CH).In CH1 to CH2, the cluster heads of two different clusters can directly communicate with each other. They join the partial hierarchy tree as shown in Fig. 4. After joining the hierarchy, the respective CHs inform their members that it has joined the hierarchy. And then, CHs broadcast messages to search for another CHs who has not yet joined the hierarchy.

Fig. 4
figure 4

Case 1: CH–CH communication possibility in hierarchy formation

Full size image

Case 2

CH2 to M1 (CH–M). CHs after joining the hierarchy check for Case 2 possibility. There may be a case where some CHs are not in communication range to any of the CHs that has already joined the partial hierarchy tree. But some members of such clusters are reachable by a CH that has joined the partial hierarchy tree. Figure 5 shows Case 2 where the proposed protocol implements reconstitution of that cluster by electing the reachable member (M1) as new CH of that cluster. MNs join their new CH and old CH becomes a member of new CH. Here, there may be a possibility of intra-cluster communication through M11 to old CH (named as Proxy CH) to new CH.

Fig. 5
figure 5

Case 2: CH–M communication possibility in hierarchy formation

Full size image

Case 3

M2 to CH1 (M–CH). A CH may not be able to join the partial hierarchy tree by Case 1 and Case 2. Figure 6 shows Case 3 communication possibility. The unjointed CH searches for a MN whose CH has joined the partial hierarchy tree. It chooses any one such member (say, M2). M2 becomes CH and joins the partial hierarchy tree through CH2. CH1 joins the partial hierarchy tree through M2.

Fig. 6
figure 6

Case 3: M–CH communication possibility in hierarchy formation

Full size image

Case 4

M1 to M2 (M–M). If the above three cases (Case 1, Case 2, and Case 3) are not possible between two clusters, then Case 4 communication may be possible. Figure 7 describes Case 4. The unjointed CHs (say, CH1) chooses anyone of its MN (M1) that is in communication range to a MN (M2) belonging to already joined CH in the partial hierarchy tree. M2 becomes CH. M1 becomes new CH, CH1 becomes MN of M1, and MNs join their new CH. Intra-cluster communication may be possible. Both members M1 and M2 join the hierarchy tree through CH2.

Fig. 7
figure 7

Case 4: M–M communication possibility in hierarchy formation

Full size image

In the end, the proposed algorithm synthesizes the hierarchy of clusters. If not, there is a chance of hole in the network. The proposed algorithm detects the hole in the network; if any, but, does not provide solution to remove the holes.

4 Implementation and Result Analysis

The proposed algorithm (EEHCR), TL-LEACH [11], and MR-LEACH [26] are simulated in OMNeT++ network simulator and results have been captured. The nodes are deployed randomly in the target area. Table 1 lists parameters used for setting up the simulation environment:

Table 1 Assumed parameters of the simulation
Full size table

Figure 8 shows that on increasing the number of SNs, there is a greater number of Case 1: CH–CH and probability of other three cases (Case 2: CH–M, Case 3: M–CH and Case 4: M–M) of the proposed algorithm decreases. This will reduce the number of communications for synthesizing hierarchy, resulting in saving of battery power.

Fig. 8
figure 8

Count of all four cases of communication possibility in hierarchy-formation phase

Full size image

Figure 9 shows the total number of CHs formed in three different protocols, TL-LEACH, MR-LEACH, and the proposed algorithm. It also shows how many CHs have not joined in the hierarchy tree formed by the above protocols. Here, communication range of sensor nodes is considered the same for all the three protocols. The result shows that the proposed algorithm performs better than TL-LEACH and MR-LEACH protocol. The proposed algorithm can connect 99.9% of formed CHs of the network in the hierarchy tree.

Fig. 9
figure 9

Comparison of network connectivity among protocols

Full size image

Figure 10a shows that in the TL-LEACH, all nodes are dead by 220 s whereas in the proposed algorithm, nodes are alive up to 475 s. Figure 10b shows that in the MR-LEACH, all nodes are dead by 90 s whereas in the proposed algorithm, nodes are dead by 118 s. The proposed algorithm performs better than the TL-LEACH and MR-LEACH.

Fig. 10
figure 10

Alive nodes with time. a TL-LEACH and the proposed algorithm b MR-LEACH and the proposed algorithm

Full size image

Figure 11 illustrates the performance of the proposed algorithm with respect to number of messages received at BS in comparison to TL-LEACH and MR-LEACH. Figure 11a shows that 330 more number of messages are able to reach the BS in the proposed algorithm compared to TL-LEACH while compared to MR-LEACH in Fig. 11b, six more number of messages are received at the BS in the proposed algorithm. The proposed algorithm performs better than TL-LEACH and MR-LEACH.

Fig. 11
figure 11

A number of nodes alive to messages received at BS a TL-LEACH and the proposed algorithm b MR-LEACH and the proposed algorithm

Full size image

Figure 12 shows the network lifetime of the proposed algorithm, TL-LEACH, and MR-LEACH. This paper considers a network is alive until first CH is dead for simulation purpose because when a CH node dies, messages to this node could not be forwarded toward BS. A particular area of the network could not be communicated now. But in case of a non-CH node dies in the current round, neighboring SNs to this node could still sense the area. The proposed algorithm performs better than TL-LEACH and MR-LEACH.

Fig. 12
figure 12

Network lifetime in high-density nodes a TL-LEACH and the proposed algorithm b MR-LEACH and the proposed algorithm

Full size image

5 Conclusion

This paper proposed the EEHCR protocol for WSN. It is implemented in OMNeT++ simulator and is compared with two cluster-based hierarchical routing protocols, TL-LEACH and MR-LEACH. The proposed algorithm achieves better connectivity between clusters and shows an increase in network lifetime. A higher number of messages are successfully able to reach the BS in the proposed algorithm compared to TL-LEACH and MR-LEACH. The proposed algorithm performs best when all the CHs join the hierarchy tree by Case 1: CH–CH because, then, new CH is not needed. Simulation results show that the proposed protocol outperforms other comparative clustering protocols.