Keywords

1 Introduction

The wireless sensor network is composed of a large number of sensor nodes that are densely deployed in a remote area and the base station or the access point. The sensor nodes produce some measurable responses to the changes in physical or chemical conditions. The main task of the sensor nodes is to sense those conditions or a particular event and send the sensed data or the response to the base station or sink. It is quite difficult to recharge the battery of the nodes in this type of network as the nodes are deployed in a remote place. On the other hand, to fulfill the application requirements, the network lifetime should be long enough. Thus, energy-efficient routing is the main research area in wireless sensor network. The routing method followed by flat protocols like directed diffusion [1], rumor routing [2], minimum cost forwarding [3] etc. or the multipath-based routing protocols like GEAR [4], MERCC [5] wastes a huge amount of energy in data routing to the base station. Researches has shown that hierarchical protocols like LEACH [6], LEACH-C [7], PEGASIS [8] etc. are more energy efficient in this regard. Thus, the proposed protocol, can be abbreviated as HRP, takes a hierarchical approach in meeting the demand of energy-efficient routing and prolonging the network lifetime. In HRP, the cluster formation in done by the base station. This is followed by cluster head selection, sensing of data, and routing of data. The role of cluster head is rotated among the nodes of a cluster to distribute the load evenly among all the nodes in the cluster. Only the cluster heads of a particular round can take part in routing the data to the base station.

2 Related Work

Energy efficiency and increasing network longevity is the main research area in wireless sensor network for the last few years. Many algorithms are designed to form clusters and select the cluster head which has the responsibility to send the aggregated data to the base station to reduce the energy drainage. Some of them are discussed below.

Low energy adaptive clustering hierarchy (LEACH) [6] is a homogeneous clustering algorithm. It treats all the nodes without discrimination and forms clusters with only single-hop nodes based on the received signal strength and cluster heads are selected randomly. The role of cluster head is rotated among the nodes of the cluster to increase the network lifetime. Aggregated data is directly sent to the base station by each cluster head. In energy-efficient clustering algorithm for data aggregation in WSN (EECA) [9] two phases of clustering are mentioned. Formation of cluster is the first phase. It includes the broadcasting of messages to the neighbor nodes, advertising the radius of each node, residual energy and coordinates. The cluster head selection is based on competition bids calculated by each node. The selected cluster head broadcasts message of itself being the head. The next phase is data aggregation and tree construction. This phase includes calculation of weight on the basis of distance from the base station and then broadcasting of that weight thereby bringing energy efficiency, prolonged lifetime and reduced overhead. Clustering algorithm based on cell combination (CACC) [10] proposed a clustering algorithm in which the monitoring region is divided into hexagonal cells. The division is done on the basis of geographical location of the nodes. Nodes in each cluster are given a particular cluster identity. Each cluster is divided into at least seven hexagonal cells with the cluster head selected from the central cell of each cluster such that the cluster head can easily communicate with nodes of any cell of the cluster. Clustering and multi-hop routing with power control in wireless sensor network [11] provides clustering together with power control. In set-up phase, the node with the maximum residual energy and maximum intracluster broadcast power, is chosen as the cluster head. In steady state phase, packets of request are sent by the base station confirming that those packets never appear twice for a node. On receiving the request, the sensor nodes send sensed data to the cluster head in a single hop. The nodes in turn follow a reverse way to send the aggregated data to the base station. The intracluster communication process of the algorithms is same as LEACH whereas intercluster communication takes place only between two cluster heads. The base station follows a power-efficient path to send requests to the cluster head. However, following the reverse path by the cluster heads leads to the consideration of the same nodes, which reduces their energy considerably. Maximum expected covering location problem (MXCLP) [12] points the necessity of uniform distribution of cluster heads throughout the network. This saves communication cost as well as prolongs the network lifetime. This algorithm uses a math programming approach which is based on the variation of a maximal expected covering location model. In this algorithm, the service failure of links are taken into account and the cluster heads are considered to be reliable. The mobile sensors form overlapping clusters with each node being assigned a particular cluster head. HEED [13] is the modified version of LEACH [6]. It is a distributed clustering scheme in which cluster head is selected on the basis of high residual energy. In this protocol, the probability of two nodes within each other’s transmission range to become cluster head is small. The energy consumption for all the nodes in the network is not considered as same. In HEED, each node is mapped to exactly one cluster and can directly communicate with its cluster head. Proper energy dissipation is obtained in HEED. However, ignoring the network structure brings about uneven energy consumption throughout the network. Mobility-resistant efficient clustering approach (MRECA) [14] functions in a similar manner as that of HEED, with minimal complexities. Nodes are unaware of their locations in this algorithm. The local information and the respective score value in the network are broadcasted by the cluster heads. The score is used to calculate the delay for cluster head announcement. This algorithm is based on the mobility-resistant technique involving deterministic time without iterations. Better energy efficiency is ensured by this approach. The main feature is increased speed of clustering and robustness of the network. MRECA determines when the routing decision is made by the nodes. However, it does not focus on how it is performed. The intercluster communication is not considered in this algorithm which adds to the drawback of this algorithm. In energy-efficient heterogeneous clustered scheme for wireless sensor network [15] it is assumed that a percentage of sensor nodes are equipped with more energy and are immobile with known geographical locations. The introduction of computational heterogeneity, which includes the presence of more powerful microprocessor, more energy and complex data processing ability together with longer term storage, added a lot of advantages to this model. The link heterogeneity is introduced with the inclusion of high bandwidth and long-distance network transceiver which prolonged the lifetime of the network together with reliable data transmission. The energy heterogeneity brought about the energy efficiency to the network, however increasing the implementation cost. In PEGASIS [8] nodes are arranged into chains and the communication takes place only with their closest neighbor. This kind of communication minimizes the power requirement for transmission of data. However, failure of any intermediate node can cut off the link between other nodes. Maximizing network lifetime through varying transmission radii with energy-efficient cluster routing algorithm in wireless sensor networks [16] proposes an improved LEACH [6] protocol for data gathering and aggregation. In the set-up phase of the algorithm, the sensor nodes identify the cluster to which they belong on the basis of the strength of the radio signal they receive from the cluster heads of that round. The cluster heads are selected on the basis of probability and required percentage of cluster heads of the network. A homogeneous network is assumed here and each noncluster head node send the data to the cluster head which in turn forward the data to the EECL node or the energy-efficient cluster head node of the network. The EECL node is the cluster head nearest to the base station. The node being closer to the base station dissipates less energy in transmitting the data to the base station thereby increasing the network lifetime. However, the residual energy of the EECL node is reduced considerably due to receiving of data from all the cluster head nodes and performing data aggregation. QOS supporting and optimal energy allocation for a cluster-based wireless sensor network [16] states that together with energy efficiency, the quality of service, which includes source to link delay, data pass rate, data loss rate etc. must also be taken under consideration. The algorithm states that each cluster is controlled by a cluster head having a finite capacity called single fixed rate. The relaying of traffic from cluster to cluster till the sink to minimize the data congestion and increase network lifetime, makes the cluster heads to depend on total relaying data rate from its own cluster as well as other clusters. Optimal energy allocation in heterogeneous wireless sensor network [17] mentions about sensors having different sensing range, different battery capacities. In this algorithm, nodes near the base station are equipped with more energy, and deployed in an arbitrary topology in an area such that they are connected. The paper provides calculation of probability distribution and expectation of the number of data transmitted in the lifetime of a sensor together with the probability distribution and expectation of the lifetime of the network. It also provides an algorithm design for optimal initial energy allocation to the sensors for prolonging the network lifetime coupled with the derivation of expected number of working sensors at each time. The algorithm takes into account the energy consumption during both sensing and transmitting data. The authors of [18] states that sensors within a cluster report their sensed data to their cluster head. That cluster head sends the aggregated data to higher level cluster head and so on until the data reaches the sink. The closer nodes from a cluster head is selected as next-level nodes by the sending cluster head. This selection procedure continues till the base station is reached. TEEN offers energy-efficient routing with better accuracy and dynamic response time. It combines hierarchical routing with data centric mechanism.

3 Proposed Work

3.1 Basic Method

In the proposed protocol HRP, it is assumed that the network is a static network, that is after deployment the nodes are motionless and contents of same initial energy. The base station or the sink node is assumed to be of high configuration. It is also assumed that all sensor nodes are capable of data aggregation, computing their own residual energy and finding their geographic location.

All the sensor nodes obtain their geographic location and send that to the base station. The base station groups the sensor nodes into different clusters based on their geographic location. Every cluster should have a cluster head to gather data from the other nodes of that region (cluster), aggregate that and send the aggregated data to the sink node. A huge amount of energy is needed for this type of transmission which may cause early death of the cluster head. Thus for every round, change of cluster head is required. The algorithm helps to select the new cluster head and route the aggregated data to the base station.

The energy required to send data from one node to another is proportional to distance and the total number of sent messages. Thus, energy consumed for a node i after sending some messages can be written as

$$ E_{ci} = \sum\limits_{j = 1}^{n} {{{k}} * } {\text{ dist}}_{ij} * N_{m} + E_{a} $$
(1)

where, dist ij is distance between nodes i and j, N m is total number of sent messages from node i to j, k is a constant value, E a is the energy required for data aggregation.

The residual energy for node i will be

$$ E_{\text{Res}} = E_{i} - E_{ci} $$
(2)

where E i is the initial energy.

If the residual energy E Res of node i is greater than the threshold value, then it becomes a candidate node of cluster head selection process. Threshold value can be defined as energy required in accepting data from all nodes, aggregate that, and send that to neighbor nodes.

Every candidate node will calculate the selection probability Prob i value for itself. The probability value is given as

$$ {\text{prob}}_{i} = {{E_{\text{Res}} } \mathord{\left/ {\vphantom {{E_{\text{Res}} } D}} \right. \kern-0pt} D}_{i} $$
(3)

where

$$ D_{i} = \sum\limits_{j = 1}^{n} {{\text{dist}}{{_{ij} } \mathord{\left/ {\vphantom {{_{ij} } n}} \right. \kern-0pt} n}} $$
(4)

where n is the number of neighbor nodes of node i.

Now all the nodes broadcast their probability value Prob i to the neighbors. Every node checks their own value, compares that with the others, and finds the maximum. The node containing the maximum Prob i value will send the success message to all its neighbors.

After selection of the cluster head, the aggregated data should reach to the base station in an energy-efficient way. The algorithm takes care of this by selecting a leader node among the cluster heads. To choose a leader, every cluster head will calculate a weight value by

$$ W_{i} = {\text{k}} * \left( {\frac{{E_{\text{Res}} }}{{D_{b} }}} \right) $$
(5)

where, E Res is the residual energy of cluster head i and D b is the distance of that cluster head from the base station.

Each cluster head will broadcast its weight value to other cluster heads. The cluster heads compare the received weight values and the cluster head having the maximum weight value is considered as leader node. The leader aggregates all data coming from different cluster heads before sending it to the base station.

3.2 Algorithm

4 Simulation Result

A network with 100 nodes is created to analyze the performance of HRP. The list of parameters is given in Table 1.

Table 1 Parameter list
Full size table

The initial power of every node is considered 500 J. The size of each packet of data is taken as 1 kB. EECA [9] is chosen for comparison of performance. In EECA, one node can be a member of more than one cluster as shown in Fig. 1, which causes data redundancy and leads to more energy drainage. In HRP, base station has formed the cluster so that no node can be there in common areas, thus reducing data redundancy and energy wastage.

Fig. 1
figure 1

Nodes in common field of two different cluster

Full size image

In EECA, distance from the source node is not measured at the time of weight calculation. The energy depletion depends on distance and to get the optimized weight value both the distance, from the base station and from the source node should be measured. Consider Fig. 2 for example.

Fig. 2
figure 2

Sending aggregated data to base station through different path

Full size image

Here the values along with edges are representing the distance and by two paths aggregated data can be sent to the base station. Now we calculate the weight value according to Eq. (5) considering the fixed value K = 5 and E Res = 20 for both the path.

The weight value for the path with dotted line is 3.703 and that with the solid line is 5.00. Though the distance from the base station for the first one is smaller, it has the lower weight value due to the greater distance from the source node. Thus HRP makes uniform load distribution among the cluster heads and increases network lifetime by considering both the distance from the source node and from the base station.

In Fig. 3, it is observed that after completion of six rounds more nodes are dead for EECA than HRP.

Fig. 3
figure 3

Number of dead nodes versus number of round

Full size image

Again after each round, the average residual energy of the network is calculated and plotted for EECA [9] and HRP as follows.

Figure 4, shows that after sixth round the algorithm EECA lost more energy than HRP. Thus, HRP is more energy aware than EECA.

Fig. 4
figure 4

Average residual energy versus number of round

Full size image

5 Conclusion

The main concern of researchers in the domain of WSN is to provide energy-efficient routing due to the restrictions on battery power of the sensors. In this paper, an attempt has been made to provide efficient power utilization during routing of information in WSN. The proposed algorithm divides the network into several clusters, selects a cluster head, aggregates the data of that cluster, and sends that to the base station through other cluster heads. The proposed HRP logic has been compared against EECA, and the simulation result shows that network longevity is increased in case of HRP.