Sink mobility aware energy-efficient network integrated super heterogeneous protocol for WSNs

In order to achieve energy efficiency at the network layer in WSNs, many routing protocols have been proposed (Table 1). These protocols decide the routing path for delivering the data to the end station [16]. Generally, routing protocols can be divided into three categories: (i) flat routing protocols, (ii) cluster-based routing protocols, and (iii) location-based routing protocols. Nodes perform similar tasks, there exists no structure for routing, nodes are connected, and they forward data through connected nodes, in the first category of routing protocols. Whereas in the second category, network is divided into clusters and nodes select CH and send data through CH. As the name indicates, the third category exploits nodes’ location for routing. Among these categories, cluster-based routing protocols are the most energy-efficient ones. Therefore, category number two is our focal point in this research work.

Heinzelman et al. [9] introduced a clustering algorithm for homogeneous WSNs; LEACH, which is based on probability nodes, select themselves as CHs. They divide the protocol operation into two phases: setup phase and steady state phase. In the setup phase, two tasks are performed: selection of CHs and association of cluster members with CHs. Every node generates a random number (between 0 and 1) and compares this random number with a pre-defined threshold value. If the generated random number is greater than the pre-defined threshold value and the node has not been selected as CH for the last \(\frac {1}{p}\) rounds (p is the probability of CH selection), then it is selected as the CH for the current round. The CH node(s) sends an association message to the non-CH nodes to inform them that it is the CH now. On reception, the non-CH nodes respond to the nearest CH node by sending a confirmation message. Soon after the setup phase, the steady state phase begins with data transmission from nodes to CHs and then from CHs to the BS. All these transmissions and receptions are performed within the allocated Time Division Multiple Access (TDMA) slots while keeping in mind that these allocations are centrally controlled by the BS.

In EACLE [17], the route selection is executed independently after the CH selection. This two-phase control approach increases the overheads and reduces the battery power, which shortens the lifetime of the WSNs. To cope with this problem, the authors proposed a clustering-based routing protocol Power Aware Routing and Clustering (PARC) Scheme for WSNs which reduces these overheads.

HEED [10] is a distributed clustering algorithm which stochastically selects the CHs. This hybrid approach selects CHs on the basis of probability and minimizes the energy cost by association mechanism. This algorithm exploits the availability of multiple transmission power levels of nodes and correlates the selection probability of each node to its residual energy.

In [18], authors proposed a novel method for mobile sink operations in which the probe priority of the mobile sink is determined from data priority to increase the QoS. They use the mobile sink to reduce the routing hot spot.

In the SEP protocol proposed in [11], every protocol in which every sensor node in a heterogeneous two-level hierarchical network independently selects itself as a CH based on its initial energy.

Qing et al. [12] proposed the DEEC protocol in which the CH selection is based on the probability of the ratio of residual energy of nodes and the average energy of the network. In this algorithm, a node with a higher energy has more chances to be selected as CH.

The DDEEC, proposed in [13], selects CHs on the basis of residual energy of nodes. Thus, this process makes the advanced nodes more probable to be selected as CHs during the initial rounds as compared to the normal nodes. As the initial energy of nodes is reduced and as time passed by, advanced nodes will have the same CH selection probability like the normal ones.

Saini and Sharma [14] proposed the EDEEC protocol which extends the concept of heterogeneity to three energy levels by adding the concept of super nodes.

Authors in [19] introduced the Hierarchical Ring Location Service (HRLS) protocol, a practical distributed location service which provides sink location information in a scalable and distributed manner. In contrast to existing hierarchical-based location services, each sink in HRLS distributively constructs its own hierarchy of grid rings.

In [20], authors proposed a new independent structure-based routing protocol which implements a sink mobility and provides scalability by exploiting k-level independent grid structure for data dissemination from source to destination. However, independent of the number of movement of both sinks and events, the propped protocol does not construct any additional routing structure.

Zhao et al. [21] proposed a framework to maximize the lifetime of WSNs by using a mobile sink. They formulated linear programming models for static as well as mobile sinks. Within a predefined delay tolerance level, each node does not need to send the data immediately as it becomes available. Instead, a node can store data temporarily and transmit it when the mobile sink arrives at the most favorable location for achieving extended network lifetime.

Authors in [22] focused on the upper bound of the total distance traveled by the mobile sink. Authors believe that the inter-transition distance between any two successive positions of a mobile sink must be restricted to avoid data loss. Also, considering the overhead on a routing tree construction at each sojourn location of the mobile sink, it is required that the mobile sink sojourns for at least a certain duration at each of its sojourn locations.

In [23], Luo and Hubaux jointly considered sink mobility and routing to maximize data collection during the network lifetime. However, authors in [21‐23] do not exploit clustering, whereas we do so in order to prolong the network lifetime. Mobility of actors has been exploited in [24‐26] to improve or recover connected coverage lost due to failure of an actor.

A distributed localization technique has been presented in [27] for WSNs. In this technique, position estimation is performed by each node in an iterative manner by solving spatially constrained local programs. On the bases of range and estimated position(s), the defined constraints enable the nodes to update their positions on regular intervals. In order to reduce energy consumption of the network, a stopping criteria for wireless transmissions has been introduced.

A Virtual Grid-Based Dynamic Routes Adjustment (VGDRA) scheme is presented in [28]. It minimizes the remonstration cost of routes and maintain optimal routes near the mobile sink stop. They design set of rules for communication through which few nodes adjust their routes for data delivery. Through this strategy, they minimize the energy consumption of remaining nodes. As a result, this scheme improves network lifetime as compared to the existing schemes.

Our proposed scheme is a hybrid that utilizes the benefits of both clustering and sink mobility. To maximize the network efficiency, we consider a four-level heterogeneous network, where the network field is divided into clusters. Cluster formation method and CH selection criteria are defined in the next sections. The CH that has minimum energy, mobile sink stops on its location and directly gathers data from nodes. In this way CH minimizes the energy consumption and stays alive for a longer time.

A WSN can have nodes with different initial energies. Such kind of network is heterogeneous where initial energies of nodes are different. In our proposed scheme, we consider four different energy levels of nodes. On the bases of their energy, we call them normal, advanced, super, and ultra-super. Where normal nodes’ energy is E ₀, advanced nodes are of fraction m of normal nodes in the network, and their energy is a times more than that of the normal ones, i.e., E ₀(1+a). Super nodes have greater energy as compared to the advanced nodes and they are of fraction m ₀ of normal nodes with energy b times greater as compared to normal nodes, E ₀(1+b). Similarly, ultra-super nodes are of fraction m ₁ of normal nodes with u times more energy than normal nodes, E ₀(1+u). Total number of ultra-super nodes presented in the network are calculated as follows:

where N is the total number of nodes in the network. Super nodes in the network are calculated as

Advanced nodes in the network are computed by

Whereas normal nodes are calculated as follows:

Initial energy of the ultra-super nodes is calculated as follows:

Initial energy of the super nodes is calculated as follows:

The total initial energy of all advanced nodes is computed by

Initial energy of the normal nodes is calculated as follows:

Initial energy of the heterogeneous network is computed by adding the energies of normal, advanced, super, and ultra-super nodes. The total initial energy is given in Eqs. (9) and (10) as follows:

As compared to the homogeneous network with initial energy E ₀, our proposed heterogeneous WSN contains N m ₁(1+u)+N m ₀(1+b)+N m(1+a)+N(1−m ₁−m ₀−m) times more energy. Both networks have equal number of nodes. Figure 1 presents the network model of BEENISH

When the network starts operation, nodes consume different amounts of energy for transmission depending upon the distance. Moreover, as compared to the nodes in the cluster, CH has more load of transmission, as it receives the data from member nodes and sends it to BS. In this way, CHs consume more energy. After some time, the residual energy of nodes present in the network may vary. We conclude that after a certain time (rounds), a homogeneous system becomes heterogeneous because of difference in residual energy of nodes.

This section presents the brief overview of our proposed scheme BEENISH, then we describe iBEENISH. Selection criterion of CHs in BEENISH considers the residual energy of nodes and the average energy level of the network. Moreover, BEENISH considers a heterogeneous network with four different energy level nodes (i.e., normal, advanced, super, and ultra-super).

Rotating epoch is defined with n _i that represents number of rounds for a node s _i in which it can become a CH, where i=1,2,....N. Energy consumption of CH (node) is greater than member nodes in a cluster. If p _opt represents the optimal probability for the selection of CHs in a homogeneous network, then p _opt N is the number of CHs per round are ensured on average. n _i is defined as \(n_{i}=\frac {1}{p_{\text {opt}}},\) in which each node s _i atleast once becomes CH. We are considering different energy levels among nodes, so when network operation starts, it follows LEACH criteria and epoch n _i is kept constant for all nodes. Due to which there is non-uniform energy distribution. Low energy node can be selected as CH and drains its energy. As a result, less energy nodes die before the nodes with greater energy. To overcome this deficiency, BEENISH rotates the epoch on the basis of nodes’ residual energy levels, E _i (r). As a result, energy consumption is balanced because initially nodes with high energy have high residual energy and they are frequently selected as CHs as compared to normal ones. More specifically, ultra-super nodes have high frequency to become CH as compared to rest of the three levels. After that, super nodes are more frequently selected as CH as compared to the remaining two levels. Similarly, normal nodes have less frequency of becoming CH as compared to the advanced nodes. In this way, the load distribution on each node is almost uniform.

Let for epoch n _i , \(p_{i}=\frac {1}{n_{i}}\) defines the probability of a node to become a CH. Our proposed scheme chooses the average probability p _i to be p _opt which ensures that there are p _opt number of CHs in each round. Hence, all nodes die at approximately the same time. If the energy levels of nodes are different, then p _i >p _opt for high energy nodes.

\(\bar {E}(r)\) represents the average energy of the network during the r ^{t h} round [12]. It is calculated as follows:

Where, R shows the total number of rounds from start of the network till all the nodes die which is given as:

where E _round is the network’s energy consumption per round and is calculated as

where the number of clusters in every round are denoted by k, CH pays cost in the form of data aggregation energy E _DA, distance between CH and BS is represented by d _toBS, whereas, distance between node in a cluster and CH is d _toCH. If N nodes are randomly deployed in an M ² region, then

The value of k _opt (that is optimal number of clusters in the network) is given below. It is calculated by taking the derivative of E _round with respect to k and setting it equal to zero.

The value of threshold probability is calculated in the same manner as authors did in [9, 12]. Based on this value, a node s _i decides whether to become a CH or not. The threshold probability is given below:

where G is the set of nodes which are eligible to be selected as CHs. Set G represents the nodes that do not become CH. These nodes choose a random number between 0 and 1. Then they compare chosen number to the threshold T(s _i ), if number is less than threshold value then node s _i becomes CH for that particular round.

As we describe earlier that after certain rounds, the homogeneous network becomes heterogeneous with multiple levels of energy. In BEENISH, initially we introduce four level heterogeneous network and four types of nodes with different initial energies (normal, advanced, super and ultra-super nodes). CH selection probability of normal, advanced, super and ultra-super is given below:

The above expression shows that a node with high residual energy has high probability of becoming CH. This strategy is energy efficient and distributes the load among the nodes in a balanced manner. As a result, stability period of the network increases. As it is possible that at some stages during the network lifetime three types of greater energy nodes (ultra-super, super, and advanced) have the same energy as that of normal nodes, in this case, ultra-super nodes have high frequency to be selected as CH and they are penalized more than super and advanced nodes. Similarly, in comparison to advanced nodes, super nodes are more penalized. To avoid this conventional approach for selecting CH, in the proposed scheme, probability of nodes to become CH varies with the varying residual energy. Implementing the above mentioned strategy of frequently penalizing the nodes with higher residual energies balances energy consumption resulting in smooth behavior of the proposed schemes.

In this regard, our proposed iBEENISH protocol makes some changes in the probabilities defined in the BEENISH protocol. The difference is based on the absolute residual energy T _absolute, which varies the probability according to variation in the residual energy. If ultra-super, super, and advanced nodes drain their energies and their residual energy become equal to the same energy level as that of normal nodes, then the probability of becoming a CH varies and all four kind of nodes will have the same probability. The selection probabilities of nodes to become CHs in iBEENISH are given in Eq. (18):

Absolute residual energy level is denoted by T _absolute and its value is given in Eq. (19):

where the value of z lies in the range of [0,1]. If z=0 and T _absolute=0, then the scheme working behind is BEENISH. We run the simulation many times varying the value of z. The value of z=0.71 is showing best results. The main objective is to obtain longer stability period. It is observed that it is not necessary that all nodes with a higher energy level become CH. There is always an optimal number of CHs in the network. Sometimes, it is also probable that normal nodes become CH. In Fig. 2, we obtain best results for first dead node using the parameters given in Table 2.

Through value c, the number of CHs are optimized and it is a positive integer. For both smaller and larger values of c, our scheme works in a “direct communication” manner. The reason behind this is that the majority of nodes send their data directly to the BS. In direct communication, nodes send their data directly to BS. The nodes that are far from the BS consume more energy in long-distance transmissions. In order to avoid long-distance communication, we find the optimum value of c which provides the best results in terms of the death of the first node. For this purpose, we run simulations many times by varying value of c between range [ 0,1] and find that at c=0.02 network shows better results in terms of the death of the first node; Fig. 2 shows how c affects the round in which the first node dies.

The energy efficiency is the main objective in any WSN so that the network lifetime and stability period can be maximized. Nowadays, sink mobility is an effective way to maximize the network lifetime and stability period of the network. So, we introduce sink mobility in BEENISH and iBEENISH protocols and then examine their effects. We put a greater emphasis on the network stability period because a greater stability period gives better and reliable data.

Sink mobility is divided into two classes: un-controlled and controlled mobility. In the first technique, the sink is able to move freely/randomly in the network, whereas, in the second technique, the sink can follow only pre-defined path throughout the network lifetime. Furthermore, controlled mobility is of two types. The first one is non-adaptive and non-flexible, which chooses fixed sojourn locations of the sink for the whole network lifetime, whereas the second technique is adaptive, robust, and flexible because it chooses sojourn locations for mobile sink in every round in order to maximize the network lifetime. We implement this adaptive technique.

When the sink is static, the probability of getting coverage holes in the network increases. After some time, when network is operational, the energy of few nodes in the network possibly becomes low which can lead toward a coverage hole problem. Coverage holes are avoided in WSN because those regions where nodes die are left unattended and then it becomes difficult to monitor. Sink mobility effectively minimizes the generation of coverage holes and balances the energy consumption among the sensors. This is why we implement sink mobility in BEENISH and iBEENISH and improve the stability period of both of them. Sink mobility versions of BEENISH and iBEENISH are MBEENISH and iMBEENISH, respectively.

In this section, we assess the performance of BEENISH, iBEENISH, MBEENISH, and iMBEENISH protocols using MATLAB. The assessment is done by considering the stability period, network lifetime and packets sent to the BS, and packets received at the BS as performance parameters. The stability period is defined as the time interval from the start of the network till the death of the first node, whereas the instability period is the period from the death of the first node till the death of the last node. Network lifetime is the time period until the last node dies. Data packets sent to the BS is the measure of the number of packets that are sent by nodes to the BS throughout the network lifetime.

We consider a WSN where 100 nodes are randomly deployed in the 10 m×100 m network field. We are not considering energy loss due to signal collisions and interference between signals of different nodes that are due to dynamic random channel conditions. Table 2 represents the radio parameters we used in the proposed scheme simulations. We compare the proposed schemes (variants of BEENISH) with DEEC, DDEEC, and EDEEC.

For simulations, we consider the network that contains 40 normal nodes having E ₀ initial energy, whereas 30 advanced nodes (m=0.6 fraction of normal nodes) with 2 times more energy (a=2.0) than normal nodes. The 21 super nodes (m ₀=0.5 fraction of normal nodes) containing b=2.5 times more energy than normal nodes. Finally, 9 ultra-super nodes (m ₁=0.3 fraction of normal nodes) containing u=3 times more energy than normal nodes. All nodes remain alive until their energy is consumed. Figure 7 shows alive nodes against the number of rounds. First node of DEEC, DDEEC, EDEEC, BEENISH, iBEENISH, MBEENISH, and iMBEENISH dies at 1287, 1523, 1595, 1754, 2046, 2237, and 2421 rounds, respectively, and all nodes die at 6520, 5144, 8046, 8109, 8521, 8630, and 9102 rounds, respectively. Figure 7 shows that alive nodes in BEENISH and iBEENISH gradually die which means that these two protocols are more efficient protocols than DEEC, EDEEC, and DDEEC. Nodes die in the following sequence: normal, advanced, super, and ultra-super. When a, b, u, m, m ₀, and m ₁ are changed, the resulting network lifetime, stability period, and behavior of the network also change. BEENISH and iBEENISH are performing much better than the other protocols because the threshold we set for the probability of nodes extend the network lifetime and stability period as shown in Fig. 7. From this figure, the stable period of MBEENISH is 92 % of the stable period of iMBEENISH. Similarly, the stable period of iBEENISH is 85 % of that of iMBEENISH. In the same way, BEENISH is 74 % of iMBEENISH in terms of stability period. DEEC, DDEEC, and EDEEC are 54, 63, and 66 % of iMBEENISH protocol in terms of stability period. Figure 7 b, c shows that with the variation in the dimensions of network from 100 m×100 m to 250 m×250 m and 500 m×500 m, with varying number of nodes from 100 to 250 and 500, respectively; the network becomes sparse and nodes consume more energy during network establishment and transmissions.

Sink mobility prolongs the network lifetime and stability period to a greater extent as shown in Fig. 7. The sink moves from one location to the other and sojourns for a certain time making virtual sojourn regions. The mobile sink collects data from CHs and nodes which are lying in its current virtual sojourn region, and then moves to a next location and collects data from nodes and CHs of that sojourn region. The stability period of iMBEENISH is approximately 2350 rounds greater than iBEENISH and the stability period of MBEENISH is almost 2000 rounds more as compared to BEENISH. If we do not apply clustering in the network then these protocols will improve effectively. This is because the sink mobility along with clustering is a difficult task to handle. MBEENISH and iMBEENISH are more energy efficient as compared to DEEC, DDEEC, and EDEEC as shown in Fig. 7. This is because the mobile sink goes to five sink locations to collect data from CHs and nodes. This results in efficient consumption of energy. It is clearly seen from the results that MBEENISH and iMBEENISH are more efficient than the other selected protocols in terms of stability period, network lifetime, and packets sent to the BS even in the case of when the network contains more super and advanced nodes as compared to normal nodes.

Figure 8 shows that MBEENISH and iMBEENISH send more number of packets to the BS as compared to the other selected protocols because every node checks the distance between its corresponding CH and the BS, and send packets to the BS if it is at a shorter distance. Packets sent to the BS by nodes and CHs collectively make BEENISH, iBEENISH, MBEENISH, and iMBEENISH better than DEEC, DDEEC, and EDEEC. This is because DEEC, EDEEC, and DDEEC use clustering in such a way that the BS does not receive that much packets from non-CH nodes. But in iMBEENISH and MBEENISH, the sink goes near to the CHs and collects data. It also collects data from nodes which find it closer than their corresponding CHs. According to the sink mobility model (MSM), mobile sink sojourns at five sink locations in the network and gathers the data from those five CHs. Also, the sink collects data from every node which has any sink location in its communication range. Thus, this can lead to an increased number of packets sent to the BS. Throughput of the expanded network fields with extended number of nodes are shown in Fig. 8 b, c. In Fig. 8 b, the throughput of iMBEENISH and MBEENISH is almost the same. Figure 8 c depicts that in initial rounds, iMBEENISH has higher throughput than MBEENISH; however, after that, MBEENISH has higher throughput because with 500 nodes in 500 m×500 m network dimensions it has a longer stability period.

Wireless links have slightly higher probability of bad link status, and there are chances that some of the packets may drop on their way. So, Figs. 8 and 9 show that packets received are not the same as packets sent in every round using (random uniformed model for dropped packets [30]). When nodes start to die, packets received at the BS also start to decrease; when all nodes are dead, throughput curve saturates (not increasing). In DEEC, the selected CHs vary with time. As a result, the number of received packets at the BS also vary. As shown in Fig. 9, the packets received are 30 % less than the packets sent to the BS which is shown in Fig. 8. Packets received for the networks with increased area (and more number of nodes as compared to the previous scenarios) are shown in Fig. 9 b, c. The experimental results show that with an increase both in field dimensions and in number of nodes, throughput of the network increases. Also, the number of packets received by BS increases.

Figure 10 shows the rate at which CHs are selected in DEEC, EDEED, DDEEC, BEENISH, iBEENISH, MBEENISH, and iMBEENISH. From this figure, we observe that among the selected routing protocols, DEEC has the highest rate of CH selection, since the CH selection in DEEC, DDEEC, and EDEEC is totally based on random number and threshold value and this criteria does not guarantee optimum number of CHs. Due to this reason, surplus CHs are selected, which cause an early stage death of nodes in the respective protocols. Our proposed protocols also depend on a random number; however, we compensate this deficiency by adjusting the probability of CHs’ selection. In this way, the chances of CH selection tend toward its optimal value (as per our proposed protocols). Rate of CH selection decreases with new field dimensions and increased number of nodes, as obvious from Fig. 10 b, c due to sparsity.