# Towards Network Lifetime Maximization: Sink Mobility Aware Multihop Scalable Hybrid Energy Efficient Protocols for Terrestrial WSNs

Authors: Mariam Akbar; Nadeem Javaid; Zahoor Ali Khan; Umar Qasim; Turki Ali Alghamdi; Saad Noor Mohammad; Syed Hassan Ahmed; Majid Iqbal Khan; Safdar Hussain Bouk
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

We propose two routing protocols for Terrestrial Wireless Sensor Networks (TWSNs): Hybrid Energy Efficient Reactive (HEER) and Multihop Hybrid Energy Efficient Reactive (MHEER) routing protocol. The main purpose of designing these protocols is to improve the network lifetime and particularly the stability period of the underlying network. In MHEER, the node with the maximum energy in a region becomes cluster head (CH) of that region for that particular round (or cycle) of time and the number of the CHs in each round remains the same. Our techniques outperform the well-known existing routing protocols: LEACH, TEEN, and DEEC in terms of stability period and network lifetime. We also calculate the confidence interval of all our results which helps us to visualize the possible deviation of our graphs from the mean value. We also implement sink mobility on HEER and MHEER. We refer to them as HEER-SM and MHEER-SM. Simulation results show that HEER-SM and MHEER-SM yield better network lifetime and stability region as compared to the counterpart techniques. We have also carried out simulations with 500 and 1000 nodes in the same field dimensions besides 100 nodes. Simulations prove that the proposed schemes show the same behavior with 500 and 1000 nodes; that is, HEER and MHEER are scalable as well.


---

## Body

## 1. Introduction

A Wireless Sensor Network (WSN) consists of a number of tiny wireless sensors dispersed throughout the network area. These sensors are very small in size and their basic function is to monitor any particular environment. A WSN can be used for security purposes, medical applications, environmental monitoring, and so forth. These sensor nodes monitor their environment and send the desired data to the base station (BS) via some routing protocol. As long as a sensor does not run out of power, it keeps sending its data to the BS. But a sensor cannot be recharged from time to time. Whenever its energy is completely consumed, it is no longer able to sense and send its data. So it is very important to implement an efficient routing protocol to improve the network lifetime and particularly its stability period. The network lifetime is the time period when a network starts working until the last node dies. On the other hand stability period is defined as time period from the start of a network till the death of very first node in the network. Very less energy is consumed in sensing data or aggregating it as compared to the energy consumed in transmission or reception of data. So a routing protocol plays a vital role in improving lifetime of a WSN.Many protocols use clustering as their routing scheme [1–7] as this technique is very effective for data transmission in WSNs. In this technique, the member nodes of a cluster select a CH among themselves for a particular round. All the cluster members send data to their respective CH. The CH receives that data, aggregates it, and then sends it to the BS. Aggregation gets rid of redundant data and only useful data is sent to base station which saves energy. Clustering can be done in two types of networks, that is, homogeneous and heterogeneous. In homogeneous WSNs, all nodes have the same energy level, whereas networks with different node energy levels are termed as heterogeneous networks. Multihoping between CHs is also a technique used for the extension of lifetime of large scale networks [8].Protocols can be classified as proactive and reactive. When the nodes periodically send their data to the BS, these are referred to as proactive. These protocols send information of relevant parameters after a fixed period of time. These types of networks are usually used for applications requiring periodic data monitoring. When the nodes react immediately to sudden and drastic changes in the value of the interested parameter then the protocols are said to be reactive. In reactive protocols, node does not have to wait for a fixed period of time to sense and transmit the data. Its sensors switch on their transmitters whenever there is a drastic change in the value of interested parameter. These protocols are suited for time critical applications.Our proposed protocol is a reactive one for homogeneous networks which uses initial energy and residual energy of a node for selecting a CH. After the selection of a CH, it will broadcast two threshold values. The transmission occurs if and only if the Current Value reaches the threshold value. This technique reduces the number of transmissions and prolongs the network lifetime and stability period.Clustering may be static or dynamic. In static clustering, the clusters do not change their size, whereas in dynamic clustering, depending upon the network characteristics, the clusters change their size during their lifetime period.Our scheme is based on static clustering. Whole area is divided into 10 regions. Each of these 10 regions acts as a cluster. Nodes are randomly deployed in each region and only a single node can become a CH in each region for a particular round. BS is located at the centre of the whole network area. Nodes send their data to the CH of their region via direct communication. The data from the CH to the BS is communicated through direct communication or multihoping depending upon its location. The CHs close to the BS send their data to the BS by using direct communication, whereas nodes which are farther from the BS send their data using Multihop Transmission between them and the CHs which are closer to the BS. The results suggest that it further enhances the network lifetime and stability period.Since communication distance has a significant impact on the energy consumption cost of nodes, we also implement sink mobility in our protocols to reduce the communication distance. In other words, networks with mobile sink remain alive for a longer period of time as compared to networks without sink mobility. In sink mobility, the sink moves in different locations of the network to collect the data. In our protocols, sink does not collect the data during its motion. It only collects data when it is at its sink locations in the network. It stops at its sink locations and collects the data from the nodes. These sink locations are also referred to as sojourn locations. The results depict that HEER-SM and MHEER-SM yield better network lifetime and stability region as compared to HEER and MHEER, respectively. It is worth mentioning here that this work is extended form of the work in [9].


## 2. Related Work

Many researchers have reviewed and analyzed the performance of different protocols in WSNs [10, 11]. LEACH [1] is the first hierarchical clustering algorithm for WSNs. It is based on the dynamic clustering technique. After certain time period, nodes are organized into clusters and each CH is selected on the basis of probability. Due to cluster formation, the distance between CH and member nodes is reduced. Nodes transmit their data at minimum communication distance to minimize the energy consumption cost. This increases the network lifetime as well as throughput of the network. LEACH outperforms classical clustering algorithm by using adaptive clustering and rotating CHs. This saves energy as transmission will only be performed on that specific CH rather than all the nodes.Threshold Sensitive Energy Efficient Network (TEEN) [2] was proposed by Manjeshwar and Agrawal in 2000. It is a reactive protocol for time critical applications. Its CH selection and cluster formation of nodes are the same as those of LEACH. In this scheme, CH broadcasts two threshold values, that is, Hard Threshold (HT) and Soft Threshold (ST). HT is the absolute value of an attribute to trigger a sensor node. HT allows nodes to transmit the event, if the event occurs in the range of interest. Therefore, this not only reduces the number of transmissions but also increases network lifetime. TEEN is designed for time critical application; nodes only transmit data when it is needed according to HT. In the remaining time they switch off the transmitter and get active when HT arrives. The disadvantage of this scheme is that the network could not get operational until HT arrives. If network does not observe HT, user will not receive ant data from the network and even no information whether any node is alive.Smaragdakis et al. [3] proposed a two-level heterogeneous aware protocol, consisting of normal and advanced (high energy) nodes. It is based on the weighted election probabilities of each node according to their respective energy to become a CH. Intuitively, advanced nodes have more probability to become a CH than normal nodes, which seems logical according to their energy consumption. Stable Election Protocol (SEP) does not require any global knowledge of the network. The drawback of SEP is that it does not consider the changing residual energy of the node; hence, the probability of advanced nodes to become CH remains high irrespective of the residual energy left in the node. Moreover, SEP performs below par if the network is more than two levels.In 2006, Qing et al. [4] proposed Distributed Energy Efficient Clustering (DEEC) protocol for WSNs. This scheme minimizes the energy consumption of the nodes by considering average energy of the network and uses it as a reference energy. Due to this approach global knowledge of energy is not required. DEEC is a clustering protocol for two and multilevel heterogeneous networks. In DEEC the probability for a node to become CH is based on residual energy of the node and average energy of network. The epoch for nodes to become CH is set according to the residual energy of a node and average energy of the network. The node with higher initial and residual energy has more chances to become a CH than the low residual energy node. DEEC performs well in multilevel heterogeneous WSN as compared to LEACH and SEP.Efficient Scheduling for the Mobile Sink in Wireless Sensor Networks with Delay Constraint (ESWC) is proposed by Gu et al. in [12]. This protocol implements sink mobility to improve the network lifetime. It also bounds the delay caused by the movement of the sink. A general and practical unified formulation is also provided in this scheme that analyzes jointly the sink mobility, routing, and delay of the network. The authors also propose polynomial-time optimal algorithm. They compare the advantages of mobile sink in the network with that without mobile sink. This protocol also discusses different sink trajectories and their effects on the lifetime, delay, and throughput.Also in [13], the authors implement the sink mobility technique to improve the network lifetime and the stability region. As the mobile sink is driven by petrol or electricity. This protocol also bounds the travel distance of mobile sink to avoid data loss during the transition of mobile sink between sink locations. When mobile sink stops at a certain sink stop, routing tree is constructed and it causes overhead. To avoid it sink stops at a stop for a definite amount of time on each stop. The authors in this paper defined that the sojourn trip of a mobile sink is the sum of sojourn times in the trip. The authors first formulated the problem as a Mixed Integer Linear Programming (MILP), with objective of maximizing the sum of sojourn times in the whole trip. Due to its NP-hardness, they then devised a novel heuristic for it. Then they conducted extensive experiments by simulations to evaluate the performance of the proposed algorithm in terms of network lifetime.The authors in [14] also improved the network lifetime by jointly considering sink mobility as well as routing by considering sink to the finite locations. They also proved the NP-hardness of their proposed model implementing multiple mobile sinks. They proved the NP-hardness of the problem and also investigated the induced subproblems. They developed an efficient primal-dual algorithm to solve the subproblem involving a single sink; then they generalized this algorithm to approximate the original problem involving multiple sinks. Finally, they applied the algorithm to a set of typical topological graphs; the results demonstrate the benefit of involving sink mobility, and they also suggested the desirable moving traces of a sink.In WSNs, sink mobility balances the nodes energy consumption. Nodes have to reconstruct the routes for data transmission when mobile sink moves towards next stop. During transition time, data dissemination is a challenging task. In [15], authors proposed a Virtual Grid Based Dynamic Routes Adjustment (VGDRA) scheme. It reduces the route reconstruction cost of nodes. For this purpose they optimize the sink location and also define communication rules. Few nodes reconstruct their routes to readjust the path with the sink. Through this scheme they extend the network lifetime.In [16], authors proposed a Lifetime Optimization Algorithm with Mobile Sink Nodes for WSNs based on location information (LOA MSN). For obtaining the location information of nodes authors used satellite and RSSI positioning algorithms. They established the movement paths with the help of lifetime optimization and path selection models. Sink obtains the location information of the nodes. Then, through graph theory model, they obtain the movement paths. The mobile sink gathers data from the nodes in the grid center. Through experiments, they show that sink finds optimal path and minimizes nodes’ energy consumption cost, which leads to prolonged network lifetime. LOA MSN uses multiple mobile sinks and minimizes the energy consumption cost; however, it increases data gathering latency.In the paper [17], authors presented an energy efficient routing scheme that maximizes the network throughput. For data forwarding they use multilayer clustering design that finds forwarder node. The role of CH rotated among the nodes is based on the threshold values; this reduces the number of packets dropped. They use Cluster Designing Algorithm (CDA) architecture for the selection of forwarder node and inter- and intracluster routing, CH rotation, and the data delivery; all these processes are energy-aware. The experiments show that careful selection of forwarder node leads towards energy efficient routing in intracluster and interclusters. It also increases throughput and network lifetime. It is also concluded that CH rotation in each round consumes energy; rather CH works until it consumes a certain amount of energy. After that other suitable nodes take the charge of CH.Authors in [18] propose a scheme to improve throughput of the network by considering base station placement problem for Wireless Sensor Networks with Successive Interference Cancelation (SIC). Through mathematical model they address this issue. This model is useful to identify a necessary condition for SIC by considering distances from sensor nodes to the base station. To achieve this they divide the network field into feasible regions and select a point in each small region for the stop of base station. The small region with the greater throughput is considered as a solution.


## 3. Counterpart Protocols in Brief

This section provides the readers with brief discussion of the schemes selected for comparison with our proposed protocols.


### 3.1. LEACH

The energy available to the sensor nodes is limited; therefore energy minimizing protocols are required to overcome this dilemma. Previously few protocols have been discussed by authors such as direct communication, multihop communication, and static clustering technique. These methods have few drawbacks that need to be addressed. Along with this, another main issue faced by the sensor nodes is the bounded bandwidth available for wireless communications. Hence a protocol is needed in which bandwidth requirement is controlled.LEACH deals with the problems mentioned above. It reduces the energy consumption of nodes in the transmission and reception of data. It enhances the overall network lifetime and makes the nodes die randomly in the network. As a result it avoids the network partitions and does not leave the areas unattended, which was the drawback of Direct Transmission (DT) and Multihop Transmission (MT) protocols.Sensors generate lots of redundant data and their transmission and reception overburden the network. In LEACH this problem is avoided with the help of data aggression or fusion technique. Through this way multiple numbers of unreliable data packets are composed into a single reliable data packet and as a result communication process is controlled in the overall network.In LEACH the sensors form a cluster together and elect a CH after definite time intervals, randomly depending upon the residual energies of nodes. LEACH allows every node to become the CH with equal probability. After the completion of this startup process the non-CH nodes will decide which cluster they will join. This is decided on the basis of the Received Signal Strength of the advertisement message broadcasted by the CHs. Hence, the overall network breaks up into number of uneven clusters. All the non-CH nodes will transmit their data destined to that CH. Afterwards CH aggregates that data and forwards it towards the sink node. This way the overall transmission distance of the nodes reduces while compromising the energies of very few nodes that need to communicate over the large distances. CDMA codes are used in LEACH to avoid the interference of signals among the intercluster and intracluster nodes.Simulations show very good results as compared to the DT and MT transmission techniques. Energy dissipation is highly reduced in the protocol resulting in larger network lifetime. In LEACH the death of first node occurs 8 times later than the compared protocols. In Direct Transmission technique the nodes farther to the sink die earlier due to larger transmission distance while in MT the nodes nearer to the sink die earlier due to relaying maximum number of data packets, hence creating the partitions in the network. Simulations and experimentations show that the nodes in the LEACH die randomly in the network, which avoids energy holes in the networks.Considering all of this, LEACH is a protocol that performs better than the other three techniques while balancing the energy consumption of the network.


### 3.2. DEEC

In WSN, data transmission mechanism of sensor nodes contributes to network lifetime. However, direct and multihop data transmission techniques failed to achieve maximum network lifetime. Though, clustering mechanism proved to be effective for data gathering in WSNs. However, selection criteria and the number of CHs should be optimum for prolongation of network lifetime. Most of the clustering protocols proposed for WSNs like LEACH, PEGASIS, and HEED consider homogeneous sensor networks. However, the residual energy of nodes varies with time and the network will become heterogeneous.The CH selection mechanism in protocols like LEACH failed to achieve prolonged network lifetime under heterogeneous network scenario. The node with minimum residual energy can be selected as CH as all the nodes have same probability to become CH during network lifetime. SEP considers two-level heterogeneity; however it is required to find the optimal probability for CH selection considering the initial and residual energy of sensor nodes under multilevel heterogeneous networks.To solve the above issue, DEEC algorithm for heterogeneous network has been proposed in this work. DEEC considers multilevel heterogeneous networks by assigning the initial energy to sensor nodes betweenE0 and E0(1+αmax⁡), where E0 is the minimum, while αmax⁡ is the maximum energy value. Also, DEEC assigns rotating epoch pi (probability of a node to be CH for certain number of rounds) to sensor nodes according to their initial and residual energy level. Let optimal probability popt=1/ni, where ni is the number of rounds. To find the optimal and average probability (pi) for CH selection, average energy of network is calculated as(1)Er=1NEtotal1-rR,where R is the total rounds during network lifetime. E(r) is used as a reference energy value, which is compared against the residual energy of each node. So, every node will consume the same amount of energy during each round. pi should be different than popt (optimal probability) for heterogeneous nodes. Using E(r) to be the reference energy,(2)pi=poptEirEr.So, the optimal number of CHs per round per epoch isNpopt. Each node si determines itself to be a CH using probability threshold as(3)Tsi=pi1-pirmod⁡1/pi,if si∈G. G is the set of eligible nodes to become CH at round r. An eligible node selects a random number between 0 and 1 and compares it against threshold; if the generated number is less than the threshold, the node becomes CH for current round. To find the number of rounds (ni) for the node to remain CH(4)ni=noptErEir.So, the high residual energy nodes will be selected as CH more often than the low energy nodes. For multilevel heterogeneous nodespi is calculated as(5)pi=poptN1+αEirN+1Er;and the rotating epoch is(6)Ii=NpoptN1+αi.DEEC uses first order radio model for calculating transmission and reception energy of sensor nodes. According to this model the total energy consumption in a round is calculated as(7)Eround=L2NEelec+NEDA+kmpd4toBS+d2toCH,where L is the number of bits in a packet, k is the number of clusters, EDA is the energy required for data aggregation at CH, and dtoBS and dtoCH are average distance of node from BS and CH, respectively.In DEEC, BS broadcasts total energy of network along with the estimated value for the total number of rounds during network lifetime to all nodes. This information is needed by every node to calculatepi during each round. Also using pi node calculates its threshold value and decides whether it can act as a CH during current round.Performance of DEEC is evaluated and compared against LEACH, LEACH-E, and SEP protocols using MATLAB simulator with 100-node network. Simulation results showed that DEEC performs well under multilevel heterogeneous networks with improved network lifetime and stability period as opposed to LEACH, LEACH-E, and SEP.


## 3.1. LEACH

The energy available to the sensor nodes is limited; therefore energy minimizing protocols are required to overcome this dilemma. Previously few protocols have been discussed by authors such as direct communication, multihop communication, and static clustering technique. These methods have few drawbacks that need to be addressed. Along with this, another main issue faced by the sensor nodes is the bounded bandwidth available for wireless communications. Hence a protocol is needed in which bandwidth requirement is controlled.LEACH deals with the problems mentioned above. It reduces the energy consumption of nodes in the transmission and reception of data. It enhances the overall network lifetime and makes the nodes die randomly in the network. As a result it avoids the network partitions and does not leave the areas unattended, which was the drawback of Direct Transmission (DT) and Multihop Transmission (MT) protocols.Sensors generate lots of redundant data and their transmission and reception overburden the network. In LEACH this problem is avoided with the help of data aggression or fusion technique. Through this way multiple numbers of unreliable data packets are composed into a single reliable data packet and as a result communication process is controlled in the overall network.In LEACH the sensors form a cluster together and elect a CH after definite time intervals, randomly depending upon the residual energies of nodes. LEACH allows every node to become the CH with equal probability. After the completion of this startup process the non-CH nodes will decide which cluster they will join. This is decided on the basis of the Received Signal Strength of the advertisement message broadcasted by the CHs. Hence, the overall network breaks up into number of uneven clusters. All the non-CH nodes will transmit their data destined to that CH. Afterwards CH aggregates that data and forwards it towards the sink node. This way the overall transmission distance of the nodes reduces while compromising the energies of very few nodes that need to communicate over the large distances. CDMA codes are used in LEACH to avoid the interference of signals among the intercluster and intracluster nodes.Simulations show very good results as compared to the DT and MT transmission techniques. Energy dissipation is highly reduced in the protocol resulting in larger network lifetime. In LEACH the death of first node occurs 8 times later than the compared protocols. In Direct Transmission technique the nodes farther to the sink die earlier due to larger transmission distance while in MT the nodes nearer to the sink die earlier due to relaying maximum number of data packets, hence creating the partitions in the network. Simulations and experimentations show that the nodes in the LEACH die randomly in the network, which avoids energy holes in the networks.Considering all of this, LEACH is a protocol that performs better than the other three techniques while balancing the energy consumption of the network.


## 3.2. DEEC

In WSN, data transmission mechanism of sensor nodes contributes to network lifetime. However, direct and multihop data transmission techniques failed to achieve maximum network lifetime. Though, clustering mechanism proved to be effective for data gathering in WSNs. However, selection criteria and the number of CHs should be optimum for prolongation of network lifetime. Most of the clustering protocols proposed for WSNs like LEACH, PEGASIS, and HEED consider homogeneous sensor networks. However, the residual energy of nodes varies with time and the network will become heterogeneous.The CH selection mechanism in protocols like LEACH failed to achieve prolonged network lifetime under heterogeneous network scenario. The node with minimum residual energy can be selected as CH as all the nodes have same probability to become CH during network lifetime. SEP considers two-level heterogeneity; however it is required to find the optimal probability for CH selection considering the initial and residual energy of sensor nodes under multilevel heterogeneous networks.To solve the above issue, DEEC algorithm for heterogeneous network has been proposed in this work. DEEC considers multilevel heterogeneous networks by assigning the initial energy to sensor nodes betweenE0 and E0(1+αmax⁡), where E0 is the minimum, while αmax⁡ is the maximum energy value. Also, DEEC assigns rotating epoch pi (probability of a node to be CH for certain number of rounds) to sensor nodes according to their initial and residual energy level. Let optimal probability popt=1/ni, where ni is the number of rounds. To find the optimal and average probability (pi) for CH selection, average energy of network is calculated as(1)Er=1NEtotal1-rR,where R is the total rounds during network lifetime. E(r) is used as a reference energy value, which is compared against the residual energy of each node. So, every node will consume the same amount of energy during each round. pi should be different than popt (optimal probability) for heterogeneous nodes. Using E(r) to be the reference energy,(2)pi=poptEirEr.So, the optimal number of CHs per round per epoch isNpopt. Each node si determines itself to be a CH using probability threshold as(3)Tsi=pi1-pirmod⁡1/pi,if si∈G. G is the set of eligible nodes to become CH at round r. An eligible node selects a random number between 0 and 1 and compares it against threshold; if the generated number is less than the threshold, the node becomes CH for current round. To find the number of rounds (ni) for the node to remain CH(4)ni=noptErEir.So, the high residual energy nodes will be selected as CH more often than the low energy nodes. For multilevel heterogeneous nodespi is calculated as(5)pi=poptN1+αEirN+1Er;and the rotating epoch is(6)Ii=NpoptN1+αi.DEEC uses first order radio model for calculating transmission and reception energy of sensor nodes. According to this model the total energy consumption in a round is calculated as(7)Eround=L2NEelec+NEDA+kmpd4toBS+d2toCH,where L is the number of bits in a packet, k is the number of clusters, EDA is the energy required for data aggregation at CH, and dtoBS and dtoCH are average distance of node from BS and CH, respectively.In DEEC, BS broadcasts total energy of network along with the estimated value for the total number of rounds during network lifetime to all nodes. This information is needed by every node to calculatepi during each round. Also using pi node calculates its threshold value and decides whether it can act as a CH during current round.Performance of DEEC is evaluated and compared against LEACH, LEACH-E, and SEP protocols using MATLAB simulator with 100-node network. Simulation results showed that DEEC performs well under multilevel heterogeneous networks with improved network lifetime and stability period as opposed to LEACH, LEACH-E, and SEP.


## 4. Proposed Protocols: HEER and MHEER

Since this research work focused on the improvement of networks energy efficiency and reactive protocols are more energy efficient than the proactive ones, thereby we have proposed reactive protocols. In this section, we explain our proposed protocols HEER [9] and MHEER. A number of routing protocols have been proposed in the field of WSNs. Most of them involve clustering. However, not much attention has been devoted towards time critical applications. DEEC, being a proactive heterogeneous network protocol, is not well suited for time critical applications. TEEN is a reactive protocol and it guarantees that the unstable region would be short in a homogenous network. This is due to the well-distributed uniform energy consumption in TEEN. On the other hand, TEEN yields a large unstable region in a heterogeneous network because the CH selection process becomes unstable and the nodes stay in idle state for most of the time. HEER chooses CHs on the basis of residual energies of the nodes. Because of its reactive nature, it reduces the number of transmissions and results in better network lifetime and stability region than TEEN and DEEC. On the other hand, MHEER yields better results in terms of lifetime and stability period as compared to HEER. The number of CHs in HEER is not fixed in every round, whereas MHEER uses static clustering. It also takes into account the maximum energy nodes at the start of each round for the CH selection. We explain both proposed protocols in detail in the following sections.


### 4.1. HEER

As we have already explained, proactive protocols sense their environment and transmit data periodically. They consume energy continuously due to periodic transmissions. Main focus in proactive protocols is on increasing lifetime and throughput and on decreasing energy consumption. In reactive protocols, a node senses the environment periodically but transmits data only when its value reaches the threshold value of the attribute. This technique reduces the number of transmissions. Reactive protocols are application dependent. Keeping in view the fact that data transmission consumes more energy than data sensing, throughput can be minimized or maximized as per application of the network. The throughput in reactive networks is inversely proportional to the network lifetime or its stability period. So, if the number of transmissions is less, it will result in extended stability period as well as network lifetime. However, if the current Sensed Value reaches the threshold value (absolute value) repeatedly then maximum number of transmissions will occur and nodes will die quickly.In this section, we propose HEER, which improves the stable region for clustering hierarchy process for a reactive network in homogeneous and heterogeneous environment. Similar to DEEC, this protocol also takes into account the initial and residual energy of nodes for CH selection. When cluster formation is finished, the CH transmits two threshold values, that is, Hard Threshold (HT) and Soft Threshold (ST). The nodes sense their environment repeatedly and if a parameter from the attributes’ set reaches its HT value, the node switches on its transmitter and transmits data. The Current Value (CV), on which first transmission occurs, is stored in an internal variable in the node called Sensed Value (SV). Now the nodes will again transmit the data to their respective CHs if(8)CV-SV≥ST.If the CV differs from SV by an amount equal to or greater than ST, only then the nodes will transmit their data. It results in reduced number of transmissions. Figure1 shows different states of a cluster. The outermost circle in all the states is referred to as a cluster. Nodes sense their environment continuously until the parameter (CV) reaches its HT value. As CV reaches HT value, the nodes start sending their data to the CH as shown in state (2). The CH receives, aggregates, and then transmits this data to the BS. The CV on which first transmission occurs is stored in SV. The node then again starts sensing its environment as shown in state (3) until the CV differs from SV by an amount equal to or greater than ST. When this condition is again satisfied, the node again switches on its transmitter and sends data to the CH. This data is then transmitted to the BS by the CH as shown in state (4).Figure 1
Idea figure for HEER from data sensing to data transmission for a cluster.


### 4.2. MHEER

An efficient routing protocol is the one [9] which consumes minimum energy and also provides good coverage area. Minimum consumption of energy leads towards better network lifetime and particularly the stability period, whereas good coverage area is useful in getting the required information from the whole network area. The unattended areas are referred to as coverage holes. These coverage holes result in inefficient coverage area and those areas can not be monitored. So, the primary objective of a routing protocol is to achieve minimum energy utilization and full coverage area. Many researches have addressed such matters as in [16–18]. Different approaches can be used to solve this problem, one of which is the division of the network field area into subareas. In the proposed technique, we divide the network area into subareas as explained in the following subsection.We consider a WSN of area 100 m × 100 m. The whole area is divided into ten regions of equal area. Each one of these 10 regions acts like a cluster. The total number of nodes is 100. Each of the 10 regions contains 10 nodes randomly deployed in it. This division helps to improve the coverage area of the network and all areas are efficiently monitored. The network topology can be observed in Figure2.Figure 2
MHEER network topology.The network area is divided into 10 equal regions (i.e., R1–R10) as shown in Figure2. MHEER uses static clustering. Static clustering refers to the type of clustering in which clusters are predetermined and they do not change their number and size during any round. Only one CH is chosen from each region during every round. These CHs are responsible for the transmission of data to the BS. All nodes sense their data and send it to the CH of their region. The CH receives that data, aggregates it, and then transmits it to the BS. The energy consumed during data transmission depends significantly on the distance between the CH and the BS. The greater the distance is, the greater the energy required to transmit that data to the BS is. All CHs have their own distances from the BS which depend upon their region and their location in that region. A CH which is farther from the BS consumes more energy than the CH which is near the BS. MHEER uses multihoping technique to cope with this issue. According to this technique, the CHs which are farther from the BS do not send their data directly to the BS. Instead, they first send it to the CH which is nearer to them as compared to the BS. Those CHs then forward that data to the BS. According to Figure 2, CHs in regions R1, R2, R9, and R10 do not send their data directly to the BS. They calculate their distance from the CHs of the adjacent regions and then send their data to the nearer one. In this way, a CH in region R1 first calculates its distance from the CHs of regions R3 and R4 and then transmits its data to the BS via the CH which is near to it. Similarly, R2 calculates its distance from R3 and R4, whereas R9 and R10 calculate their distances from R7 and R8. This multihoping helps to improve the energy consumption efficiency and improves network lifetime and particularly the stability region.As in any real case scenario, the number of packets received at the BS is never equal to the number of packets sent to the BS. This is because some packets are lost due to certain factors. Those factors may include interference, attenuation, and noise. That is why we implement the Uniform Random Distribution Model [19] for the calculation of packets drop. This makes MHEER more practical.MHEER selects a node as the CH of its region if it has the maximum energy before the start of that round. Initially, all nodes have the same amount of energy and any node can become the CH for first round. A node is chosen randomly to become the CH of that region for the first round. All other nodes send their data to CH which receives that data, aggregates it, and sends it to the BS. When the first round is completed, the amount of energy in each node is not the same anymore. This is because the utilization of energy depends upon the distance between the node or CH which is transmitting and the CH or sink which is receiving. Distance is directly proportional to the energy consumption cost of a transmitting node. As distance for transmission and reception is different for different nodes, their energy consumption will also be different. For every next round, the CHs are selected on the basis of maximum energies. The node with the maximum energy in a region becomes the CH of that region for that particular round.


## 4.1. HEER

As we have already explained, proactive protocols sense their environment and transmit data periodically. They consume energy continuously due to periodic transmissions. Main focus in proactive protocols is on increasing lifetime and throughput and on decreasing energy consumption. In reactive protocols, a node senses the environment periodically but transmits data only when its value reaches the threshold value of the attribute. This technique reduces the number of transmissions. Reactive protocols are application dependent. Keeping in view the fact that data transmission consumes more energy than data sensing, throughput can be minimized or maximized as per application of the network. The throughput in reactive networks is inversely proportional to the network lifetime or its stability period. So, if the number of transmissions is less, it will result in extended stability period as well as network lifetime. However, if the current Sensed Value reaches the threshold value (absolute value) repeatedly then maximum number of transmissions will occur and nodes will die quickly.In this section, we propose HEER, which improves the stable region for clustering hierarchy process for a reactive network in homogeneous and heterogeneous environment. Similar to DEEC, this protocol also takes into account the initial and residual energy of nodes for CH selection. When cluster formation is finished, the CH transmits two threshold values, that is, Hard Threshold (HT) and Soft Threshold (ST). The nodes sense their environment repeatedly and if a parameter from the attributes’ set reaches its HT value, the node switches on its transmitter and transmits data. The Current Value (CV), on which first transmission occurs, is stored in an internal variable in the node called Sensed Value (SV). Now the nodes will again transmit the data to their respective CHs if(8)CV-SV≥ST.If the CV differs from SV by an amount equal to or greater than ST, only then the nodes will transmit their data. It results in reduced number of transmissions. Figure1 shows different states of a cluster. The outermost circle in all the states is referred to as a cluster. Nodes sense their environment continuously until the parameter (CV) reaches its HT value. As CV reaches HT value, the nodes start sending their data to the CH as shown in state (2). The CH receives, aggregates, and then transmits this data to the BS. The CV on which first transmission occurs is stored in SV. The node then again starts sensing its environment as shown in state (3) until the CV differs from SV by an amount equal to or greater than ST. When this condition is again satisfied, the node again switches on its transmitter and sends data to the CH. This data is then transmitted to the BS by the CH as shown in state (4).Figure 1
Idea figure for HEER from data sensing to data transmission for a cluster.


## 4.2. MHEER

An efficient routing protocol is the one [9] which consumes minimum energy and also provides good coverage area. Minimum consumption of energy leads towards better network lifetime and particularly the stability period, whereas good coverage area is useful in getting the required information from the whole network area. The unattended areas are referred to as coverage holes. These coverage holes result in inefficient coverage area and those areas can not be monitored. So, the primary objective of a routing protocol is to achieve minimum energy utilization and full coverage area. Many researches have addressed such matters as in [16–18]. Different approaches can be used to solve this problem, one of which is the division of the network field area into subareas. In the proposed technique, we divide the network area into subareas as explained in the following subsection.We consider a WSN of area 100 m × 100 m. The whole area is divided into ten regions of equal area. Each one of these 10 regions acts like a cluster. The total number of nodes is 100. Each of the 10 regions contains 10 nodes randomly deployed in it. This division helps to improve the coverage area of the network and all areas are efficiently monitored. The network topology can be observed in Figure2.Figure 2
MHEER network topology.The network area is divided into 10 equal regions (i.e., R1–R10) as shown in Figure2. MHEER uses static clustering. Static clustering refers to the type of clustering in which clusters are predetermined and they do not change their number and size during any round. Only one CH is chosen from each region during every round. These CHs are responsible for the transmission of data to the BS. All nodes sense their data and send it to the CH of their region. The CH receives that data, aggregates it, and then transmits it to the BS. The energy consumed during data transmission depends significantly on the distance between the CH and the BS. The greater the distance is, the greater the energy required to transmit that data to the BS is. All CHs have their own distances from the BS which depend upon their region and their location in that region. A CH which is farther from the BS consumes more energy than the CH which is near the BS. MHEER uses multihoping technique to cope with this issue. According to this technique, the CHs which are farther from the BS do not send their data directly to the BS. Instead, they first send it to the CH which is nearer to them as compared to the BS. Those CHs then forward that data to the BS. According to Figure 2, CHs in regions R1, R2, R9, and R10 do not send their data directly to the BS. They calculate their distance from the CHs of the adjacent regions and then send their data to the nearer one. In this way, a CH in region R1 first calculates its distance from the CHs of regions R3 and R4 and then transmits its data to the BS via the CH which is near to it. Similarly, R2 calculates its distance from R3 and R4, whereas R9 and R10 calculate their distances from R7 and R8. This multihoping helps to improve the energy consumption efficiency and improves network lifetime and particularly the stability region.As in any real case scenario, the number of packets received at the BS is never equal to the number of packets sent to the BS. This is because some packets are lost due to certain factors. Those factors may include interference, attenuation, and noise. That is why we implement the Uniform Random Distribution Model [19] for the calculation of packets drop. This makes MHEER more practical.MHEER selects a node as the CH of its region if it has the maximum energy before the start of that round. Initially, all nodes have the same amount of energy and any node can become the CH for first round. A node is chosen randomly to become the CH of that region for the first round. All other nodes send their data to CH which receives that data, aggregates it, and sends it to the BS. When the first round is completed, the amount of energy in each node is not the same anymore. This is because the utilization of energy depends upon the distance between the node or CH which is transmitting and the CH or sink which is receiving. Distance is directly proportional to the energy consumption cost of a transmitting node. As distance for transmission and reception is different for different nodes, their energy consumption will also be different. For every next round, the CHs are selected on the basis of maximum energies. The node with the maximum energy in a region becomes the CH of that region for that particular round.


## 5. Sink Mobility in HEER and MHEER: HEER-SM and MHEER-SM

In this section, we propose the application of sink mobility on HEER and MHEER and refer to them as HEER-SM and MHEER-SM, respectively. Sink mobility has been proved very effective in extending the network lifetime and particularly the stability region. We put greater emphasis on stability region because this is the region in which the data received at the BS is most reliable as every node is alive during this region. So, in terms of data integrity, stability region is very important. Multiple mobile sinks would significantly prolong the network lifetime and maximize the throughput. However, the installation cost would also significantly increase. Thus, to prolong the network lifetime and maximize throughput while keeping the installation cost within a fairer limit, we have used only one mobile sink.Sink mobility refers to the movement of sink in the network to collect the data from the static nodes. These nodes can be either normal nodes or CHs, depending upon its application. Sink mobility is of two types, controlled and uncontrolled mobility. For the latter, the mobile sink can move randomly in the network region, whereas for the former it can only move along the predefined trajectory. Controlled mobility can be implemented by two ways. In the first way, the sink can move in the network on its predefined locations and these predefined locations can not be changed throughout the network lifetime. While according to the second way the sink moves on its predefined locations these locations are changed after every round. In this way, the sink moves in the controlled fashion, but its trajectory is changed after every round. In our technique, we implement the former method in which the sink locations are predefined and they are not changed throughout the network lifetime. These sink locations are also referred to as sojourn locations. The sink stops at these locations to collect the data from the nodes/CHs.


### 5.1. Network Topology

The number of sinks is restricted to one. All nodes in the network are static; that is, they do not move. The sink moves between different regions in the network area under consideration. It stops at certain sojourn locations and collects the data from the nodes. In order to minimize the communication distance between nodes of a given subregion and mobile sink, the sojourn locations are chosen as the centre points of each subregion. Figure3 shows the network topology of our proposed sink mobility. The × marks show the sojourn locations in the network. The sink is mounted on an unmanned remote controlled vehicle and moves from one sojourn location to the next and collects data from the nodes at these sojourn locations. The nodes collect data and send it to their respective CHs. The mobile sink stops at its sink stops and collects data from nodes or CHs.Figure 3
Sink mobility.The whole travel distance covered by the sink in the whole network lifetime should be bounded because a mobile sink is usually driven by fuel or electricity. When a mobile sink moves from one sink location to another, probability of data loss is high, so the distance between two sink locations should be restricted. The transmission of data from nodes/CHs to sink only occurs when the sink is not moving; that is, sink is located at any sink location. Therefore, the sum of stop times in the mobile sink tour should be maximized. There should be maximum number of stop locations of mobile sink, as could be seen from Figure4.Figure 4
Flowchart of MHEER protocol.


### 5.2. Clustering Mechanism

In our model, a single sink moves around the network to collect the data from the nodes/CHs from its sink locations. These sink locations are predefined and do not change throughout the network lifetime.In MHEER, the sink moves to each region and stops at its specific sojourn location to collect that data. As there are 10 regions, and the sink has to collect the data from all regions, there are 10 sink stops predefined. These stops are located in the middle of each region. The CHs collect data from the nodes, aggregate it, and send it to the sink whenever the sink comes to their region to collect the data. In case of HEER, the area is not divided into subregions. But the sink locations for HEER are also the same as that for MHEER. The difference is that in MHEER each region is predefined and each region has its own CH to transmit the data to the sink. So, when the sink arrives, the CH sends its data to it, whereas, in HEER, the regions are not predefined and clusters change their shape and size. The number of CHs is not the same. So, each CH calculates its distance from its neighbouring sink locations and associates itself with the closest one. The normal nodes, in addition to calculating their distance from the CH, also calculate their distance from the sink location. These nodes then send their data to the one which is closer to them than the others. In this way, energy is quite efficiently consumed.


## 5.1. Network Topology

The number of sinks is restricted to one. All nodes in the network are static; that is, they do not move. The sink moves between different regions in the network area under consideration. It stops at certain sojourn locations and collects the data from the nodes. In order to minimize the communication distance between nodes of a given subregion and mobile sink, the sojourn locations are chosen as the centre points of each subregion. Figure3 shows the network topology of our proposed sink mobility. The × marks show the sojourn locations in the network. The sink is mounted on an unmanned remote controlled vehicle and moves from one sojourn location to the next and collects data from the nodes at these sojourn locations. The nodes collect data and send it to their respective CHs. The mobile sink stops at its sink stops and collects data from nodes or CHs.Figure 3
Sink mobility.The whole travel distance covered by the sink in the whole network lifetime should be bounded because a mobile sink is usually driven by fuel or electricity. When a mobile sink moves from one sink location to another, probability of data loss is high, so the distance between two sink locations should be restricted. The transmission of data from nodes/CHs to sink only occurs when the sink is not moving; that is, sink is located at any sink location. Therefore, the sum of stop times in the mobile sink tour should be maximized. There should be maximum number of stop locations of mobile sink, as could be seen from Figure4.Figure 4
Flowchart of MHEER protocol.


## 5.2. Clustering Mechanism

In our model, a single sink moves around the network to collect the data from the nodes/CHs from its sink locations. These sink locations are predefined and do not change throughout the network lifetime.In MHEER, the sink moves to each region and stops at its specific sojourn location to collect that data. As there are 10 regions, and the sink has to collect the data from all regions, there are 10 sink stops predefined. These stops are located in the middle of each region. The CHs collect data from the nodes, aggregate it, and send it to the sink whenever the sink comes to their region to collect the data. In case of HEER, the area is not divided into subregions. But the sink locations for HEER are also the same as that for MHEER. The difference is that in MHEER each region is predefined and each region has its own CH to transmit the data to the sink. So, when the sink arrives, the CH sends its data to it, whereas, in HEER, the regions are not predefined and clusters change their shape and size. The number of CHs is not the same. So, each CH calculates its distance from its neighbouring sink locations and associates itself with the closest one. The normal nodes, in addition to calculating their distance from the CH, also calculate their distance from the sink location. These nodes then send their data to the one which is closer to them than the others. In this way, energy is quite efficiently consumed.


## 6. Experiments and Discussions

In this section, we discuss the simulation results of our proposed protocols. Table1 summarizes the simulation parameters used to validate the proposed protocols.Table 1
Simulation parameters.
Parameter
Value
Number of nodes
100, 500, 1000
Number of static sinks
1
Number of mobile sinks
1
Static sink location
(50, 50)
Mobile sink location
Specified trajectory (reference Figure3)
Initial energy
0.5 J
Area
100 m × 100 m


### 6.1. Performance Metrics: Definitions

The following performance metrics are considered:(1)
Network lifetime: It is the time period from the start of the network till the death of the last node in the field. It is measured in the unit of time (seconds). It is one of the most important parameters every network is supposed to have.(2)
Throughput: It is the total number of packets successfully received at the BS. It excludes the packet sent by the sensor nodes in the field but dropped on their way to BS because of any reason. Its unit is packets/sec.(3)
Packet drop: It is defined as the number of packets sent towards the BS; however, they are not received at BS.(4)
Total energy consumption: It is defined as the total energy consumed by all the alive nodes. It is measured in Joules.(5)
End-to-end delay: It is the total time taken by all packets to reach from source node to BS. It is also measured in seconds.


### 6.2. Performance Metrics: Discussions

In this section, we discuss the performance parameters by which we measure, evaluate, and then compare our proposed protocols with the existing counterpart protocols. For the sake of fair comparison, we have assumed the Soft and Hard Threshold ranges as in the selected protocol for comparison, that is, TEEN. Similar reason is valid for initial energy of nodes.


#### 6.2.1. Network Lifetime

To understand the network lifetime, we first define the alive nodes. The nodes with sufficient energy to sense, process, and then transmit the data to the neighbors, and/or BS or any other node in its transmission range, are generally referred to as alive nodes. Generally, the lifetime of any network is depending upon the number of alive nodes (which in fact is depending upon the initial energy and consumption of energy). As per our assumption, even if a single alive node in the network is working, the network is assumed alive. High energy consumption could result in short lifetime and vice versa. The efficient routing protocols generally result in the efficient consumption of energy which ultimately improves the network lifetime.In Figure5, we compare the network lifetime of TEEN, DEEC, HEER, MHEER, HEER-SM, and MHEER-SM. We can see that MHEER-SM has the best lifetime as compared to the other protocols, whereas TEEN has the least network lifetime. This is because MHEER-SM has the same network topology as that of MHEER with the exception that MHEER-SM has mobile sink. This mobile sink moves to every region and collects data from the CH of each region. In this way, the distance between the CHs and sink reduces, which results in efficient consumption of energy. We can observe that HEER outperforms TEEN and DEEC. This is because HEER selects the CHs on the basis of their residual energies. The data is transmitted only when the threshold limit is achieved. It further reduces the number of transmissions and improves the network lifetime. MHEER on the other hand outperforms HEER. This is because MHEER is based on multihoping and the distant CHs transmit their data via multihoping. In this way, the energy is efficiently consumed. MHEER has static clusters and each cluster has one CH and fixed a number of nodes. This helps in improving coverage area and coverage holes are reduced. HEER-SM and MHEER-SM perform better than HEER and MHEER because mobility helps to reduce the distance between the CHs and the sink. In this way, the network lifetime and stability region are further improved. Lifetime and nodes dying at frequent intervals are given in Table 2.Table 2
Dead nodes at different instants of time (for 100 nodes).
Protocol name
First node dead at
Last node dead at
Dead nodes
0.01 sec
0.02 sec
0.03 sec
0.04 sec
HEER
0.024 sec
0.044 sec
0
0
15
81
HEER-SM
0.037 sec
0.044 sec
0
0
0
19
MHEER
0.0344 sec
0.044 sec
0
0
0
56
MHEER-SM
0.037 sec
0.044 sec
0
0
0
9
TEEN
0.0138 sec
0.027 sec
0
60
100
100
DEEC
0.013 sec
0.031 sec
0
17
94
100Figure 5
Lifetime of network for different numbers of nodes.
(a)
Lifetime of network for 100 nodes
(b)
Lifetime of network for 500 nodes
(c)
Lifetime of network for 1000 nodes


#### 6.2.2. Lifetime Maximization Model

Our proposed protocol models a WSN as a graphG={ζ∪ζ0, υ∪υ0}, where ζ and ζ0 are the set of sensors and sink locations, respectively. N=|ζ| is the number of sensors and N0=|ζ0| is the number of sink sites. υ=ζ∪ζ is the set of wireless links between sensors nodes and υ0=ζ∪ζ0 is the set of wireless links between sensor nodes and sink locations. lic∈υ if the CH c is within the communication range ρi of node i, where ∀i,c∈ζ. Similarly, lik∈υ0 if the sink location k is within the communication range of node i, and lck∈υ0 if the CH c is within the communication range of sink location k, where ∀k∈ζ0. αi is the data generation rate of a node i and its value is the same for all nodes. The sink speed is taken as infinity.The sink has unlimited energy and there is no energy issue for sink. The residual time of the sink at each location is defined asτk. Nodes send their data only during this time. Nodes do not send their data whenever the sink is in motion. λic is the amount of data from node i to CH c. λik is the amount of data from node i to the sink location k. And λck is the amount of data from CH c to the sink location k. σ=1, if the sink is at the sink site of a region. eicT is the energy required to transmit one unit data from node i to CH c. The energy dissipated for the transmission of one unit data from node i to sink location k is defined as eikT. The amount of energy consumed for the reception of one unit data is given as eciR.Since the objective function and its given constraints are mixed integer nonlinear, we have chosen mixed integer nonlinear programming model:(9)MaximizeX=∑r∑kτkr9aSubject to:∑reckT∑lck∈υ0λckr+ejcR∑ljc∈υλjcr≤Ec,ωir=1,∀j,c∈υ,∀k∈υ0,9b∑reikT∑lik∈υ0λikr+eicT∑lic∈υλicr≤Ei,ωir=0,∀i,c∈υ,∀k∈υ0,9c∑iσic=0,iffdic≤dik,∀i,c∈υ,∀k∈υ0,9dτk>0,λij≥0,∀k,i,j,9e∀i,j,c∈υ,∀k∈υ0.This model is a mixed integer nonlinear programming model. We explain each equation below.Objective Function. The objective function of this sink mobility model is to maximize the sojourn time of sink. The reason behind it is that the sink collects the data from the nodes or CHs only when it is at its sink location. It does not collect the data when it is in motion. So, as long as the sink stays at its sink location, it collects the data. In this way, improving the sojourn time will result in improving the network lifetime which is our main goal.Energy Constraint. According to these constraints, if a node is a CH, it receives the data from the nodes and sends that data to the sink. The energy consumed during this process should be less than that of the initial energy of the CH. Similarly, if a node is not a CH, then it will either send its data to the CH or to the sink depending upon their distance from that node. This consumption of energy should also be less than the initial energy of the node.Flow Constraint. This constraint shows that a node only sends its data to the CH if and only if the distance of the CH from the node is lesser than the distance between the sink and the node. If this distance is greater, then the node transmits its data directly to the sink instead of sending its data to the sink via the CH.Pause Time Constraint. This constraint says that every pause time of the sink must be greater than zero because sink does not collect data when it is in motion. It collects the data of the nodes or the CHs only when it is at its sink site. So, the sojourn time should be greater than zero to collect that data.


#### 6.2.3. Throughput

In this subsection, we discuss the number of packets sent to the BS. Figure6 shows the total number of packets sent to BS, in TEEN, DEEC, HEER, MHEER, HEER-SM, and MHEER-SM. We know that the CH selection in HEER and HEER-SM is based on the probability assigned to each node. This results in uneven number of CHs in each time round. As the number of CHs in each time round is not the same, the number of packets sent to the BS per time round is also not fixed. The number of packets sent to the BS varies in every time round. As the probability of CHs per time round in HEER and HEER-SM is 0.1, the number of CHs in every time round should be 10. So the number of packets sent to the BS should also be 10. But the number of CHs does not remain fixed. As a result, the number of packets sent to BS is also not the same.Figure 6
Packets sent to BS.
(a)
Throughput of network for 100 nodes
(b)
Throughput of network for 500 nodes
(c)
Throughput of network for 1000 nodesIn case of MHEER and MHEER-SM, the selection of CHs is based on the maximum residual energy of a node in its region. As there are 10 regions and every region has 1 CH in each time round, the number of CHs in each time round is also 10. Each CH is responsible for sending its data to the BS. So, packets sent to the BS in every time round are also 10.


#### 6.2.4. Data Gathering Maximization Model

We also define a new model for the data gathering. In this model, we maximize the data gathering at the sink which results in maximized throughput. Maximum throughput leads to the conclusion that maximum data is gathered at the sink. This total data gatheringλk at the sink site k can be defined as the sum of the data transmitted by the nodes and the CHs to the sink site. τmin⁡ is the minimum sojourn time for which sink stays at site k. ℵ is the total number of regions. It can be given by the following equation:(10)λk=∑r∑lik∈υ0λikr+∑lck∈υ0λckr,∀i,c∈υ,∀k∈υ0.This is also a mixed integer nonlinear programming model:(11)Maximizeλk,11asubject to:τkr≥τmin⁡,∀k∈υ0,∀r,11bζ0=xlim×Sℵ,whereSmax⁡≥S≥1,11cζ0=ylim×Sℵ,whereSmax⁡≥S≥1.Objective Function. We maximize the data gathering at the sink which results in maximized throughput. Maximum throughput leads to the conclusion that maximum data is gathered at the sink. This total data gathering λk at the sink site k can be defined as the sum of the data transmitted by the nodes and the CHs to the sink site.Sojourn Time Constraint. According to this constraint, increasing the sojourn time increases the amount of data gathering. This is because the greater the time the sink stays at its sink location, the greater the time nodes and CHs get to send their data to the sink. So, a sink should stay for more time at its sink location than its least possible sojourn limit. This results in maximum data gathering.Sink Locations Constraint. This constraint discusses the number of sink sites. The greater the number of sink sites, the greater the amount of data gathered. So if a sink stops at more locations, it gathers more data than the sink which stays at few locations. According to this constraint, the number of sink locations should be according to the network area and the number of regions in it. So, the number of sink sites can be determined by using the maximum limits of network’s length x, width y, and the number of regions.


#### 6.2.5. Packet Drop

Packet drop can be defined as number of total packets sent minus the total number of packets received. Interflow and intraflow interferences, congestion, path loss, attenuation, noise, and so forth could be the reasons for the packet drops. In our proposed techniques, we have used the uniform random distribution to calculate the number of dropped packets. We assume that it makes our protocol relatively robust as compared to the counterpart schemes. We use 0.3 as the packet drop probability value, which means, during every time round, a packet has a probability of 30% to be dropped.Figures6 and 7 show the total number of packets transmitted in the network and number of packets successively received only at the BS, respectively. From the figures it can be observed that total number of packets received at the BS is remarkably less than the total number of packets sent in the whole network.Figure 7
Packet drop for whole network lifetime for 100, 500, and 1000 nodes.
(a)
Total number of packets dropped for 100 nodes
(b)
Total number of packets dropped for 500 nodes
(c)
Total number of packets dropped for 1000 nodes


#### 6.2.6. Energy Consumption

In this section, total energy consumption analysis is presented. Total energy includes the energy required for transmission, reception, and aggregation. Energy consumption of the network is inversely proportional to the network lifetime. From Figures5 and 8 it is obvious that shorter network lifetime results in greater energy consumption. Figure 8 compares the energy consumption of HEER, HEER-SM, MHEER, MHEER-SM, TEEN, and DEEC. In the beginning, TEEN and DEEC have maximum energy consumption as compared to remaining protocol plots. DEEC being proactive protocol consumes more energy because of periodic transmissions and addition of advanced nodes which adds to total energy consumption count.Figure 8
Energy consumption of the network for different numbers of nodes.
(a)
Energy consumption for 100 nodes
(b)
Energy consumption for 500 nodes
(c)
Energy consumption for 1000 nodesTEEN being reactive protocol consumes more energy among all reactive protocols because of random selection of CH and dies out faster. HEER is also a reactive protocol; however, it takes into account residual and initial energy of nodes in CH selection process. Therefore, it has better energy consumption because of load balancing as compared to TEEN and DEEC. Although stable region of HEER is more than TEEN and DEEC (Figure5), fluctuations in plots of HEER are due to its reactive nature. Protocol may have few or many transmissions in any particular time round. The CH selection is dynamic in HEER; therefore, it has more energy consumption than MHEER and MHEER-SM. In dynamic CH selection process sometimes CH is far from BS and more transmission energy is consumed. MHEER consumes less energy and shows better network lifetime because of static clustering and nondistant transmissions from CH to BS. In case CH is far from BS, it transmits data to nearest CH instead of sending it to BS.The introduction of mobile sink in HEER-SM yields less energy consumption because sink may be more closer than CH or BS to receive data. Hence, nodes or CHs do not do distant transmissions. However, sink mobility in MHEER has very little impact on energy consumption and network lifetime because the static clustering architecture of MHEER is enough to achieve such lifetime with the current mobility pattern of sink.


#### 6.2.7. Delay

Figure9 shows the end-to-end delay of the network. This delay includes the time required by all the alive nodes to transmit data to CH and from CH to BS.Figure 9
End-to-end delay of the network for 100, 500, and 1000 nodes.
(a)
End-to-end delay of the network for 100 nodes
(b)
End-to-end delay of the network for 500 nodes
(c)
End-to-end delay of the network for 1000 nodesFrom Figure9, it can be seen that sink mobility improves delay performance. MHEER-SM has 39.8% less delay as compared to MHEER and results are even better in HEER-SM with 65% less delay in comparison to HEER. The improvement in delay performance is because of availability of sink in close vicinity after frequent intervals. Nodes, instead of transmitting data to CH and then CH taking another few seconds to transmit data to BS, transmit directly to mobile sink. MHEER chooses maximum energy node as a CH which then transmits data to BS. CH can be at any location in the particular region and may not be nearest to all the cluster members in that region. However, in MHEER-SM the sojourn locations of MS are almost in the centre of every region that makes it feasible for all the cluster members and also CHs to transmit data with minimum delay and energy when mobile sink is there.Delay difference in HEER and DEEC is small in the beginning because both are following the same CH selection criteria; however, it increases later on because of difference in lifetime of both protocols. HEER has many alive nodes when DEEC dies out completely (ref. Figure5).Another observation from Figure9 is that static clustering protocols like MHEER and MHEER-SM have less delay as compared to dynamic clustering protocols like TEEN, DEEC, HEER, and HEER-SM. The location of CHs in case of dynamic clustering is not fixed. CH and cluster members may be too close or too far from BS and CH, respectively. In addition, number of CHs is not fixed. Therefore, there may be less than optimal number of CHs in any particular time round that leads to unbalanced regions. Nodes and CH as a result do too many distant transmissions and thus add more delay.


### 6.3. Performance Trade-Offs Made by HEER/MHEER and HEER-SM/MHEER-SM

In our scheme of MHEER, improvement in end-to-end delay is achieved at the cost of frequent transmissions due to packet loss, whereas in MHEER-SM the end-to-end delay is achieved at the cost of greater energy consumption, as shown in Table3. The end-to-end delay of the network in MHEER and MHEER-SM is improved compared to HEER and HEER-SM. The improvement in delay performance is because of availability of sink in close vicinity after frequent intervals. Instead of transmitting data to cluster head and then cluster head forwarding data to base station after some time delay, nodes transmit data directly to mobile sink. In MHEER-SM, the sojourn locations of mobile station are almost in the center of every region that makes it feasible for all the cluster members and also cluster heads to transmit data with minimum delay when mobile sink is there. Delay difference in HEER and DEEC is small in the beginning because both are following the same cluster head selection criteria; however, it increases later on because of difference in lifetime of both protocols.Table 3
Performance trade-offs made by the protocols.
Protocol
Achieved parameter
Figure
Compromised parameter
Figure
HEER
End-to-end delay improves
Figure9
Throughput
Figure6
MHEER
End-to-end delay improves
Figure9
Frequent transmissions due to packet loss
Figure7
HEER-SM
End-to-end delay improves
Figure9
Energy consumption
Figure8
MHEER-SM
End-to-end delay improves
Figure9
Energy consumption
Figure8
HEER
Stability period extends
Figure5
End-to-end delay
Figure9
MHEER
Stability period extends
Figure5
Redundant transmissions due to packet loss
Figure7
HEER-SM
Stability period extends
Figure5
Greater energy consumption
Figure8
MHEER-SM
Stability period extends
Figure5
Throughput
Figure6
HEER
Lifetime extends
Figure5
End-to-end delay and energy consumption
Figures8 and 9
MHEER
Lifetime extends
Figure5
Throughput
Figure6
HEER-SM
Lifetime extends
Figure5
End-to-end delay
Figure9
MHEER-SM
Lifetime extends
Figure5
Throughput
Figure6In MHEER and MHEER-SM, the stability period is improved because of the same network topology in both schemes with the exception that MHEER-SM has mobile sink. This mobile sink moves to every region and collects data from the CH of each region. In this way, the distance between the CHs and sink reduces, which results in efficient energy consumption. The stability period of MHEER is improved but at the cost of redundant transmissions due to packet loss at the sink. The stability period of MHEER-SM is improved but at the cost of the network throughput. MHEER has static clusters and each cluster has one CH and fixed a number of nodes. This helps in improving coverage area and coverage holes are reduced.HEER-SM and MHEER-SM perform better than HEER and MHEER because mobility helps to reduce the distance between the CHs and the sink. In this way, the network lifetime and stability region are further improved. Fluctuations in plots of HEER are due to its reactive nature. Protocol may have few or many transmissions in any particular time round. Cluster head selection is dynamic in HEER; therefore it has more energy consumption than MHEER and MHEER-SM. In dynamic selection process, CH may be far from BS and more transmission energy is consumed. MHEER consumes less energy and shows better network lifetime because of static clustering and nondistant transmissions from CH to BS. In case CH is far from BS, it transmits data to nearest CH instead of sending it to BS.In MHEER and MHEER-SM, network lifetime is improved at the cost of net throughput of the network. The drop in network lifetime in MHEER and MHEER-SM is much less than that of other schemes. In HEER and HEER-SM, network lifetime is improved at the cost of end-to-end delay of the network and energy consumption. HEER improves the stable region for clustering hierarchy process for a reactive network in homogeneous and heterogeneous environment. The nodes sense their environment repeatedly and if a parameter from the attributes set reaches its HT value, the node switches on its transmitter and transmits data. In case of HEER, the area is not divided into subregions. But the sink locations for HEER are also the same as that for MHEER. The difference is that in MHEER each region is predefined and each region has its own CH to transmit the data to the sink, whereas, in HEER, the regions are not predefined and clusters change their shape and size.


## 6.1. Performance Metrics: Definitions

The following performance metrics are considered:(1)
Network lifetime: It is the time period from the start of the network till the death of the last node in the field. It is measured in the unit of time (seconds). It is one of the most important parameters every network is supposed to have.(2)
Throughput: It is the total number of packets successfully received at the BS. It excludes the packet sent by the sensor nodes in the field but dropped on their way to BS because of any reason. Its unit is packets/sec.(3)
Packet drop: It is defined as the number of packets sent towards the BS; however, they are not received at BS.(4)
Total energy consumption: It is defined as the total energy consumed by all the alive nodes. It is measured in Joules.(5)
End-to-end delay: It is the total time taken by all packets to reach from source node to BS. It is also measured in seconds.


## 6.2. Performance Metrics: Discussions

In this section, we discuss the performance parameters by which we measure, evaluate, and then compare our proposed protocols with the existing counterpart protocols. For the sake of fair comparison, we have assumed the Soft and Hard Threshold ranges as in the selected protocol for comparison, that is, TEEN. Similar reason is valid for initial energy of nodes.


### 6.2.1. Network Lifetime

To understand the network lifetime, we first define the alive nodes. The nodes with sufficient energy to sense, process, and then transmit the data to the neighbors, and/or BS or any other node in its transmission range, are generally referred to as alive nodes. Generally, the lifetime of any network is depending upon the number of alive nodes (which in fact is depending upon the initial energy and consumption of energy). As per our assumption, even if a single alive node in the network is working, the network is assumed alive. High energy consumption could result in short lifetime and vice versa. The efficient routing protocols generally result in the efficient consumption of energy which ultimately improves the network lifetime.In Figure5, we compare the network lifetime of TEEN, DEEC, HEER, MHEER, HEER-SM, and MHEER-SM. We can see that MHEER-SM has the best lifetime as compared to the other protocols, whereas TEEN has the least network lifetime. This is because MHEER-SM has the same network topology as that of MHEER with the exception that MHEER-SM has mobile sink. This mobile sink moves to every region and collects data from the CH of each region. In this way, the distance between the CHs and sink reduces, which results in efficient consumption of energy. We can observe that HEER outperforms TEEN and DEEC. This is because HEER selects the CHs on the basis of their residual energies. The data is transmitted only when the threshold limit is achieved. It further reduces the number of transmissions and improves the network lifetime. MHEER on the other hand outperforms HEER. This is because MHEER is based on multihoping and the distant CHs transmit their data via multihoping. In this way, the energy is efficiently consumed. MHEER has static clusters and each cluster has one CH and fixed a number of nodes. This helps in improving coverage area and coverage holes are reduced. HEER-SM and MHEER-SM perform better than HEER and MHEER because mobility helps to reduce the distance between the CHs and the sink. In this way, the network lifetime and stability region are further improved. Lifetime and nodes dying at frequent intervals are given in Table 2.Table 2
Dead nodes at different instants of time (for 100 nodes).
Protocol name
First node dead at
Last node dead at
Dead nodes
0.01 sec
0.02 sec
0.03 sec
0.04 sec
HEER
0.024 sec
0.044 sec
0
0
15
81
HEER-SM
0.037 sec
0.044 sec
0
0
0
19
MHEER
0.0344 sec
0.044 sec
0
0
0
56
MHEER-SM
0.037 sec
0.044 sec
0
0
0
9
TEEN
0.0138 sec
0.027 sec
0
60
100
100
DEEC
0.013 sec
0.031 sec
0
17
94
100Figure 5
Lifetime of network for different numbers of nodes.
(a)
Lifetime of network for 100 nodes
(b)
Lifetime of network for 500 nodes
(c)
Lifetime of network for 1000 nodes


### 6.2.2. Lifetime Maximization Model

Our proposed protocol models a WSN as a graphG={ζ∪ζ0, υ∪υ0}, where ζ and ζ0 are the set of sensors and sink locations, respectively. N=|ζ| is the number of sensors and N0=|ζ0| is the number of sink sites. υ=ζ∪ζ is the set of wireless links between sensors nodes and υ0=ζ∪ζ0 is the set of wireless links between sensor nodes and sink locations. lic∈υ if the CH c is within the communication range ρi of node i, where ∀i,c∈ζ. Similarly, lik∈υ0 if the sink location k is within the communication range of node i, and lck∈υ0 if the CH c is within the communication range of sink location k, where ∀k∈ζ0. αi is the data generation rate of a node i and its value is the same for all nodes. The sink speed is taken as infinity.The sink has unlimited energy and there is no energy issue for sink. The residual time of the sink at each location is defined asτk. Nodes send their data only during this time. Nodes do not send their data whenever the sink is in motion. λic is the amount of data from node i to CH c. λik is the amount of data from node i to the sink location k. And λck is the amount of data from CH c to the sink location k. σ=1, if the sink is at the sink site of a region. eicT is the energy required to transmit one unit data from node i to CH c. The energy dissipated for the transmission of one unit data from node i to sink location k is defined as eikT. The amount of energy consumed for the reception of one unit data is given as eciR.Since the objective function and its given constraints are mixed integer nonlinear, we have chosen mixed integer nonlinear programming model:(9)MaximizeX=∑r∑kτkr9aSubject to:∑reckT∑lck∈υ0λckr+ejcR∑ljc∈υλjcr≤Ec,ωir=1,∀j,c∈υ,∀k∈υ0,9b∑reikT∑lik∈υ0λikr+eicT∑lic∈υλicr≤Ei,ωir=0,∀i,c∈υ,∀k∈υ0,9c∑iσic=0,iffdic≤dik,∀i,c∈υ,∀k∈υ0,9dτk>0,λij≥0,∀k,i,j,9e∀i,j,c∈υ,∀k∈υ0.This model is a mixed integer nonlinear programming model. We explain each equation below.Objective Function. The objective function of this sink mobility model is to maximize the sojourn time of sink. The reason behind it is that the sink collects the data from the nodes or CHs only when it is at its sink location. It does not collect the data when it is in motion. So, as long as the sink stays at its sink location, it collects the data. In this way, improving the sojourn time will result in improving the network lifetime which is our main goal.Energy Constraint. According to these constraints, if a node is a CH, it receives the data from the nodes and sends that data to the sink. The energy consumed during this process should be less than that of the initial energy of the CH. Similarly, if a node is not a CH, then it will either send its data to the CH or to the sink depending upon their distance from that node. This consumption of energy should also be less than the initial energy of the node.Flow Constraint. This constraint shows that a node only sends its data to the CH if and only if the distance of the CH from the node is lesser than the distance between the sink and the node. If this distance is greater, then the node transmits its data directly to the sink instead of sending its data to the sink via the CH.Pause Time Constraint. This constraint says that every pause time of the sink must be greater than zero because sink does not collect data when it is in motion. It collects the data of the nodes or the CHs only when it is at its sink site. So, the sojourn time should be greater than zero to collect that data.


### 6.2.3. Throughput

In this subsection, we discuss the number of packets sent to the BS. Figure6 shows the total number of packets sent to BS, in TEEN, DEEC, HEER, MHEER, HEER-SM, and MHEER-SM. We know that the CH selection in HEER and HEER-SM is based on the probability assigned to each node. This results in uneven number of CHs in each time round. As the number of CHs in each time round is not the same, the number of packets sent to the BS per time round is also not fixed. The number of packets sent to the BS varies in every time round. As the probability of CHs per time round in HEER and HEER-SM is 0.1, the number of CHs in every time round should be 10. So the number of packets sent to the BS should also be 10. But the number of CHs does not remain fixed. As a result, the number of packets sent to BS is also not the same.Figure 6
Packets sent to BS.
(a)
Throughput of network for 100 nodes
(b)
Throughput of network for 500 nodes
(c)
Throughput of network for 1000 nodesIn case of MHEER and MHEER-SM, the selection of CHs is based on the maximum residual energy of a node in its region. As there are 10 regions and every region has 1 CH in each time round, the number of CHs in each time round is also 10. Each CH is responsible for sending its data to the BS. So, packets sent to the BS in every time round are also 10.


### 6.2.4. Data Gathering Maximization Model

We also define a new model for the data gathering. In this model, we maximize the data gathering at the sink which results in maximized throughput. Maximum throughput leads to the conclusion that maximum data is gathered at the sink. This total data gatheringλk at the sink site k can be defined as the sum of the data transmitted by the nodes and the CHs to the sink site. τmin⁡ is the minimum sojourn time for which sink stays at site k. ℵ is the total number of regions. It can be given by the following equation:(10)λk=∑r∑lik∈υ0λikr+∑lck∈υ0λckr,∀i,c∈υ,∀k∈υ0.This is also a mixed integer nonlinear programming model:(11)Maximizeλk,11asubject to:τkr≥τmin⁡,∀k∈υ0,∀r,11bζ0=xlim×Sℵ,whereSmax⁡≥S≥1,11cζ0=ylim×Sℵ,whereSmax⁡≥S≥1.Objective Function. We maximize the data gathering at the sink which results in maximized throughput. Maximum throughput leads to the conclusion that maximum data is gathered at the sink. This total data gathering λk at the sink site k can be defined as the sum of the data transmitted by the nodes and the CHs to the sink site.Sojourn Time Constraint. According to this constraint, increasing the sojourn time increases the amount of data gathering. This is because the greater the time the sink stays at its sink location, the greater the time nodes and CHs get to send their data to the sink. So, a sink should stay for more time at its sink location than its least possible sojourn limit. This results in maximum data gathering.Sink Locations Constraint. This constraint discusses the number of sink sites. The greater the number of sink sites, the greater the amount of data gathered. So if a sink stops at more locations, it gathers more data than the sink which stays at few locations. According to this constraint, the number of sink locations should be according to the network area and the number of regions in it. So, the number of sink sites can be determined by using the maximum limits of network’s length x, width y, and the number of regions.


### 6.2.5. Packet Drop

Packet drop can be defined as number of total packets sent minus the total number of packets received. Interflow and intraflow interferences, congestion, path loss, attenuation, noise, and so forth could be the reasons for the packet drops. In our proposed techniques, we have used the uniform random distribution to calculate the number of dropped packets. We assume that it makes our protocol relatively robust as compared to the counterpart schemes. We use 0.3 as the packet drop probability value, which means, during every time round, a packet has a probability of 30% to be dropped.Figures6 and 7 show the total number of packets transmitted in the network and number of packets successively received only at the BS, respectively. From the figures it can be observed that total number of packets received at the BS is remarkably less than the total number of packets sent in the whole network.Figure 7
Packet drop for whole network lifetime for 100, 500, and 1000 nodes.
(a)
Total number of packets dropped for 100 nodes
(b)
Total number of packets dropped for 500 nodes
(c)
Total number of packets dropped for 1000 nodes


### 6.2.6. Energy Consumption

In this section, total energy consumption analysis is presented. Total energy includes the energy required for transmission, reception, and aggregation. Energy consumption of the network is inversely proportional to the network lifetime. From Figures5 and 8 it is obvious that shorter network lifetime results in greater energy consumption. Figure 8 compares the energy consumption of HEER, HEER-SM, MHEER, MHEER-SM, TEEN, and DEEC. In the beginning, TEEN and DEEC have maximum energy consumption as compared to remaining protocol plots. DEEC being proactive protocol consumes more energy because of periodic transmissions and addition of advanced nodes which adds to total energy consumption count.Figure 8
Energy consumption of the network for different numbers of nodes.
(a)
Energy consumption for 100 nodes
(b)
Energy consumption for 500 nodes
(c)
Energy consumption for 1000 nodesTEEN being reactive protocol consumes more energy among all reactive protocols because of random selection of CH and dies out faster. HEER is also a reactive protocol; however, it takes into account residual and initial energy of nodes in CH selection process. Therefore, it has better energy consumption because of load balancing as compared to TEEN and DEEC. Although stable region of HEER is more than TEEN and DEEC (Figure5), fluctuations in plots of HEER are due to its reactive nature. Protocol may have few or many transmissions in any particular time round. The CH selection is dynamic in HEER; therefore, it has more energy consumption than MHEER and MHEER-SM. In dynamic CH selection process sometimes CH is far from BS and more transmission energy is consumed. MHEER consumes less energy and shows better network lifetime because of static clustering and nondistant transmissions from CH to BS. In case CH is far from BS, it transmits data to nearest CH instead of sending it to BS.The introduction of mobile sink in HEER-SM yields less energy consumption because sink may be more closer than CH or BS to receive data. Hence, nodes or CHs do not do distant transmissions. However, sink mobility in MHEER has very little impact on energy consumption and network lifetime because the static clustering architecture of MHEER is enough to achieve such lifetime with the current mobility pattern of sink.


### 6.2.7. Delay

Figure9 shows the end-to-end delay of the network. This delay includes the time required by all the alive nodes to transmit data to CH and from CH to BS.Figure 9
End-to-end delay of the network for 100, 500, and 1000 nodes.
(a)
End-to-end delay of the network for 100 nodes
(b)
End-to-end delay of the network for 500 nodes
(c)
End-to-end delay of the network for 1000 nodesFrom Figure9, it can be seen that sink mobility improves delay performance. MHEER-SM has 39.8% less delay as compared to MHEER and results are even better in HEER-SM with 65% less delay in comparison to HEER. The improvement in delay performance is because of availability of sink in close vicinity after frequent intervals. Nodes, instead of transmitting data to CH and then CH taking another few seconds to transmit data to BS, transmit directly to mobile sink. MHEER chooses maximum energy node as a CH which then transmits data to BS. CH can be at any location in the particular region and may not be nearest to all the cluster members in that region. However, in MHEER-SM the sojourn locations of MS are almost in the centre of every region that makes it feasible for all the cluster members and also CHs to transmit data with minimum delay and energy when mobile sink is there.Delay difference in HEER and DEEC is small in the beginning because both are following the same CH selection criteria; however, it increases later on because of difference in lifetime of both protocols. HEER has many alive nodes when DEEC dies out completely (ref. Figure5).Another observation from Figure9 is that static clustering protocols like MHEER and MHEER-SM have less delay as compared to dynamic clustering protocols like TEEN, DEEC, HEER, and HEER-SM. The location of CHs in case of dynamic clustering is not fixed. CH and cluster members may be too close or too far from BS and CH, respectively. In addition, number of CHs is not fixed. Therefore, there may be less than optimal number of CHs in any particular time round that leads to unbalanced regions. Nodes and CH as a result do too many distant transmissions and thus add more delay.


## 6.2.1. Network Lifetime

To understand the network lifetime, we first define the alive nodes. The nodes with sufficient energy to sense, process, and then transmit the data to the neighbors, and/or BS or any other node in its transmission range, are generally referred to as alive nodes. Generally, the lifetime of any network is depending upon the number of alive nodes (which in fact is depending upon the initial energy and consumption of energy). As per our assumption, even if a single alive node in the network is working, the network is assumed alive. High energy consumption could result in short lifetime and vice versa. The efficient routing protocols generally result in the efficient consumption of energy which ultimately improves the network lifetime.In Figure5, we compare the network lifetime of TEEN, DEEC, HEER, MHEER, HEER-SM, and MHEER-SM. We can see that MHEER-SM has the best lifetime as compared to the other protocols, whereas TEEN has the least network lifetime. This is because MHEER-SM has the same network topology as that of MHEER with the exception that MHEER-SM has mobile sink. This mobile sink moves to every region and collects data from the CH of each region. In this way, the distance between the CHs and sink reduces, which results in efficient consumption of energy. We can observe that HEER outperforms TEEN and DEEC. This is because HEER selects the CHs on the basis of their residual energies. The data is transmitted only when the threshold limit is achieved. It further reduces the number of transmissions and improves the network lifetime. MHEER on the other hand outperforms HEER. This is because MHEER is based on multihoping and the distant CHs transmit their data via multihoping. In this way, the energy is efficiently consumed. MHEER has static clusters and each cluster has one CH and fixed a number of nodes. This helps in improving coverage area and coverage holes are reduced. HEER-SM and MHEER-SM perform better than HEER and MHEER because mobility helps to reduce the distance between the CHs and the sink. In this way, the network lifetime and stability region are further improved. Lifetime and nodes dying at frequent intervals are given in Table 2.Table 2
Dead nodes at different instants of time (for 100 nodes).
Protocol name
First node dead at
Last node dead at
Dead nodes
0.01 sec
0.02 sec
0.03 sec
0.04 sec
HEER
0.024 sec
0.044 sec
0
0
15
81
HEER-SM
0.037 sec
0.044 sec
0
0
0
19
MHEER
0.0344 sec
0.044 sec
0
0
0
56
MHEER-SM
0.037 sec
0.044 sec
0
0
0
9
TEEN
0.0138 sec
0.027 sec
0
60
100
100
DEEC
0.013 sec
0.031 sec
0
17
94
100Figure 5
Lifetime of network for different numbers of nodes.
(a)
Lifetime of network for 100 nodes
(b)
Lifetime of network for 500 nodes
(c)
Lifetime of network for 1000 nodes


## 6.2.2. Lifetime Maximization Model

Our proposed protocol models a WSN as a graphG={ζ∪ζ0, υ∪υ0}, where ζ and ζ0 are the set of sensors and sink locations, respectively. N=|ζ| is the number of sensors and N0=|ζ0| is the number of sink sites. υ=ζ∪ζ is the set of wireless links between sensors nodes and υ0=ζ∪ζ0 is the set of wireless links between sensor nodes and sink locations. lic∈υ if the CH c is within the communication range ρi of node i, where ∀i,c∈ζ. Similarly, lik∈υ0 if the sink location k is within the communication range of node i, and lck∈υ0 if the CH c is within the communication range of sink location k, where ∀k∈ζ0. αi is the data generation rate of a node i and its value is the same for all nodes. The sink speed is taken as infinity.The sink has unlimited energy and there is no energy issue for sink. The residual time of the sink at each location is defined asτk. Nodes send their data only during this time. Nodes do not send their data whenever the sink is in motion. λic is the amount of data from node i to CH c. λik is the amount of data from node i to the sink location k. And λck is the amount of data from CH c to the sink location k. σ=1, if the sink is at the sink site of a region. eicT is the energy required to transmit one unit data from node i to CH c. The energy dissipated for the transmission of one unit data from node i to sink location k is defined as eikT. The amount of energy consumed for the reception of one unit data is given as eciR.Since the objective function and its given constraints are mixed integer nonlinear, we have chosen mixed integer nonlinear programming model:(9)MaximizeX=∑r∑kτkr9aSubject to:∑reckT∑lck∈υ0λckr+ejcR∑ljc∈υλjcr≤Ec,ωir=1,∀j,c∈υ,∀k∈υ0,9b∑reikT∑lik∈υ0λikr+eicT∑lic∈υλicr≤Ei,ωir=0,∀i,c∈υ,∀k∈υ0,9c∑iσic=0,iffdic≤dik,∀i,c∈υ,∀k∈υ0,9dτk>0,λij≥0,∀k,i,j,9e∀i,j,c∈υ,∀k∈υ0.This model is a mixed integer nonlinear programming model. We explain each equation below.Objective Function. The objective function of this sink mobility model is to maximize the sojourn time of sink. The reason behind it is that the sink collects the data from the nodes or CHs only when it is at its sink location. It does not collect the data when it is in motion. So, as long as the sink stays at its sink location, it collects the data. In this way, improving the sojourn time will result in improving the network lifetime which is our main goal.Energy Constraint. According to these constraints, if a node is a CH, it receives the data from the nodes and sends that data to the sink. The energy consumed during this process should be less than that of the initial energy of the CH. Similarly, if a node is not a CH, then it will either send its data to the CH or to the sink depending upon their distance from that node. This consumption of energy should also be less than the initial energy of the node.Flow Constraint. This constraint shows that a node only sends its data to the CH if and only if the distance of the CH from the node is lesser than the distance between the sink and the node. If this distance is greater, then the node transmits its data directly to the sink instead of sending its data to the sink via the CH.Pause Time Constraint. This constraint says that every pause time of the sink must be greater than zero because sink does not collect data when it is in motion. It collects the data of the nodes or the CHs only when it is at its sink site. So, the sojourn time should be greater than zero to collect that data.


## 6.2.3. Throughput

In this subsection, we discuss the number of packets sent to the BS. Figure6 shows the total number of packets sent to BS, in TEEN, DEEC, HEER, MHEER, HEER-SM, and MHEER-SM. We know that the CH selection in HEER and HEER-SM is based on the probability assigned to each node. This results in uneven number of CHs in each time round. As the number of CHs in each time round is not the same, the number of packets sent to the BS per time round is also not fixed. The number of packets sent to the BS varies in every time round. As the probability of CHs per time round in HEER and HEER-SM is 0.1, the number of CHs in every time round should be 10. So the number of packets sent to the BS should also be 10. But the number of CHs does not remain fixed. As a result, the number of packets sent to BS is also not the same.Figure 6
Packets sent to BS.
(a)
Throughput of network for 100 nodes
(b)
Throughput of network for 500 nodes
(c)
Throughput of network for 1000 nodesIn case of MHEER and MHEER-SM, the selection of CHs is based on the maximum residual energy of a node in its region. As there are 10 regions and every region has 1 CH in each time round, the number of CHs in each time round is also 10. Each CH is responsible for sending its data to the BS. So, packets sent to the BS in every time round are also 10.


## 6.2.4. Data Gathering Maximization Model

We also define a new model for the data gathering. In this model, we maximize the data gathering at the sink which results in maximized throughput. Maximum throughput leads to the conclusion that maximum data is gathered at the sink. This total data gatheringλk at the sink site k can be defined as the sum of the data transmitted by the nodes and the CHs to the sink site. τmin⁡ is the minimum sojourn time for which sink stays at site k. ℵ is the total number of regions. It can be given by the following equation:(10)λk=∑r∑lik∈υ0λikr+∑lck∈υ0λckr,∀i,c∈υ,∀k∈υ0.This is also a mixed integer nonlinear programming model:(11)Maximizeλk,11asubject to:τkr≥τmin⁡,∀k∈υ0,∀r,11bζ0=xlim×Sℵ,whereSmax⁡≥S≥1,11cζ0=ylim×Sℵ,whereSmax⁡≥S≥1.Objective Function. We maximize the data gathering at the sink which results in maximized throughput. Maximum throughput leads to the conclusion that maximum data is gathered at the sink. This total data gathering λk at the sink site k can be defined as the sum of the data transmitted by the nodes and the CHs to the sink site.Sojourn Time Constraint. According to this constraint, increasing the sojourn time increases the amount of data gathering. This is because the greater the time the sink stays at its sink location, the greater the time nodes and CHs get to send their data to the sink. So, a sink should stay for more time at its sink location than its least possible sojourn limit. This results in maximum data gathering.Sink Locations Constraint. This constraint discusses the number of sink sites. The greater the number of sink sites, the greater the amount of data gathered. So if a sink stops at more locations, it gathers more data than the sink which stays at few locations. According to this constraint, the number of sink locations should be according to the network area and the number of regions in it. So, the number of sink sites can be determined by using the maximum limits of network’s length x, width y, and the number of regions.


## 6.2.5. Packet Drop

Packet drop can be defined as number of total packets sent minus the total number of packets received. Interflow and intraflow interferences, congestion, path loss, attenuation, noise, and so forth could be the reasons for the packet drops. In our proposed techniques, we have used the uniform random distribution to calculate the number of dropped packets. We assume that it makes our protocol relatively robust as compared to the counterpart schemes. We use 0.3 as the packet drop probability value, which means, during every time round, a packet has a probability of 30% to be dropped.Figures6 and 7 show the total number of packets transmitted in the network and number of packets successively received only at the BS, respectively. From the figures it can be observed that total number of packets received at the BS is remarkably less than the total number of packets sent in the whole network.Figure 7
Packet drop for whole network lifetime for 100, 500, and 1000 nodes.
(a)
Total number of packets dropped for 100 nodes
(b)
Total number of packets dropped for 500 nodes
(c)
Total number of packets dropped for 1000 nodes


## 6.2.6. Energy Consumption

In this section, total energy consumption analysis is presented. Total energy includes the energy required for transmission, reception, and aggregation. Energy consumption of the network is inversely proportional to the network lifetime. From Figures5 and 8 it is obvious that shorter network lifetime results in greater energy consumption. Figure 8 compares the energy consumption of HEER, HEER-SM, MHEER, MHEER-SM, TEEN, and DEEC. In the beginning, TEEN and DEEC have maximum energy consumption as compared to remaining protocol plots. DEEC being proactive protocol consumes more energy because of periodic transmissions and addition of advanced nodes which adds to total energy consumption count.Figure 8
Energy consumption of the network for different numbers of nodes.
(a)
Energy consumption for 100 nodes
(b)
Energy consumption for 500 nodes
(c)
Energy consumption for 1000 nodesTEEN being reactive protocol consumes more energy among all reactive protocols because of random selection of CH and dies out faster. HEER is also a reactive protocol; however, it takes into account residual and initial energy of nodes in CH selection process. Therefore, it has better energy consumption because of load balancing as compared to TEEN and DEEC. Although stable region of HEER is more than TEEN and DEEC (Figure5), fluctuations in plots of HEER are due to its reactive nature. Protocol may have few or many transmissions in any particular time round. The CH selection is dynamic in HEER; therefore, it has more energy consumption than MHEER and MHEER-SM. In dynamic CH selection process sometimes CH is far from BS and more transmission energy is consumed. MHEER consumes less energy and shows better network lifetime because of static clustering and nondistant transmissions from CH to BS. In case CH is far from BS, it transmits data to nearest CH instead of sending it to BS.The introduction of mobile sink in HEER-SM yields less energy consumption because sink may be more closer than CH or BS to receive data. Hence, nodes or CHs do not do distant transmissions. However, sink mobility in MHEER has very little impact on energy consumption and network lifetime because the static clustering architecture of MHEER is enough to achieve such lifetime with the current mobility pattern of sink.


## 6.2.7. Delay

Figure9 shows the end-to-end delay of the network. This delay includes the time required by all the alive nodes to transmit data to CH and from CH to BS.Figure 9
End-to-end delay of the network for 100, 500, and 1000 nodes.
(a)
End-to-end delay of the network for 100 nodes
(b)
End-to-end delay of the network for 500 nodes
(c)
End-to-end delay of the network for 1000 nodesFrom Figure9, it can be seen that sink mobility improves delay performance. MHEER-SM has 39.8% less delay as compared to MHEER and results are even better in HEER-SM with 65% less delay in comparison to HEER. The improvement in delay performance is because of availability of sink in close vicinity after frequent intervals. Nodes, instead of transmitting data to CH and then CH taking another few seconds to transmit data to BS, transmit directly to mobile sink. MHEER chooses maximum energy node as a CH which then transmits data to BS. CH can be at any location in the particular region and may not be nearest to all the cluster members in that region. However, in MHEER-SM the sojourn locations of MS are almost in the centre of every region that makes it feasible for all the cluster members and also CHs to transmit data with minimum delay and energy when mobile sink is there.Delay difference in HEER and DEEC is small in the beginning because both are following the same CH selection criteria; however, it increases later on because of difference in lifetime of both protocols. HEER has many alive nodes when DEEC dies out completely (ref. Figure5).Another observation from Figure9 is that static clustering protocols like MHEER and MHEER-SM have less delay as compared to dynamic clustering protocols like TEEN, DEEC, HEER, and HEER-SM. The location of CHs in case of dynamic clustering is not fixed. CH and cluster members may be too close or too far from BS and CH, respectively. In addition, number of CHs is not fixed. Therefore, there may be less than optimal number of CHs in any particular time round that leads to unbalanced regions. Nodes and CH as a result do too many distant transmissions and thus add more delay.


## 6.3. Performance Trade-Offs Made by HEER/MHEER and HEER-SM/MHEER-SM

In our scheme of MHEER, improvement in end-to-end delay is achieved at the cost of frequent transmissions due to packet loss, whereas in MHEER-SM the end-to-end delay is achieved at the cost of greater energy consumption, as shown in Table3. The end-to-end delay of the network in MHEER and MHEER-SM is improved compared to HEER and HEER-SM. The improvement in delay performance is because of availability of sink in close vicinity after frequent intervals. Instead of transmitting data to cluster head and then cluster head forwarding data to base station after some time delay, nodes transmit data directly to mobile sink. In MHEER-SM, the sojourn locations of mobile station are almost in the center of every region that makes it feasible for all the cluster members and also cluster heads to transmit data with minimum delay when mobile sink is there. Delay difference in HEER and DEEC is small in the beginning because both are following the same cluster head selection criteria; however, it increases later on because of difference in lifetime of both protocols.Table 3
Performance trade-offs made by the protocols.
Protocol
Achieved parameter
Figure
Compromised parameter
Figure
HEER
End-to-end delay improves
Figure9
Throughput
Figure6
MHEER
End-to-end delay improves
Figure9
Frequent transmissions due to packet loss
Figure7
HEER-SM
End-to-end delay improves
Figure9
Energy consumption
Figure8
MHEER-SM
End-to-end delay improves
Figure9
Energy consumption
Figure8
HEER
Stability period extends
Figure5
End-to-end delay
Figure9
MHEER
Stability period extends
Figure5
Redundant transmissions due to packet loss
Figure7
HEER-SM
Stability period extends
Figure5
Greater energy consumption
Figure8
MHEER-SM
Stability period extends
Figure5
Throughput
Figure6
HEER
Lifetime extends
Figure5
End-to-end delay and energy consumption
Figures8 and 9
MHEER
Lifetime extends
Figure5
Throughput
Figure6
HEER-SM
Lifetime extends
Figure5
End-to-end delay
Figure9
MHEER-SM
Lifetime extends
Figure5
Throughput
Figure6In MHEER and MHEER-SM, the stability period is improved because of the same network topology in both schemes with the exception that MHEER-SM has mobile sink. This mobile sink moves to every region and collects data from the CH of each region. In this way, the distance between the CHs and sink reduces, which results in efficient energy consumption. The stability period of MHEER is improved but at the cost of redundant transmissions due to packet loss at the sink. The stability period of MHEER-SM is improved but at the cost of the network throughput. MHEER has static clusters and each cluster has one CH and fixed a number of nodes. This helps in improving coverage area and coverage holes are reduced.HEER-SM and MHEER-SM perform better than HEER and MHEER because mobility helps to reduce the distance between the CHs and the sink. In this way, the network lifetime and stability region are further improved. Fluctuations in plots of HEER are due to its reactive nature. Protocol may have few or many transmissions in any particular time round. Cluster head selection is dynamic in HEER; therefore it has more energy consumption than MHEER and MHEER-SM. In dynamic selection process, CH may be far from BS and more transmission energy is consumed. MHEER consumes less energy and shows better network lifetime because of static clustering and nondistant transmissions from CH to BS. In case CH is far from BS, it transmits data to nearest CH instead of sending it to BS.In MHEER and MHEER-SM, network lifetime is improved at the cost of net throughput of the network. The drop in network lifetime in MHEER and MHEER-SM is much less than that of other schemes. In HEER and HEER-SM, network lifetime is improved at the cost of end-to-end delay of the network and energy consumption. HEER improves the stable region for clustering hierarchy process for a reactive network in homogeneous and heterogeneous environment. The nodes sense their environment repeatedly and if a parameter from the attributes set reaches its HT value, the node switches on its transmitter and transmits data. In case of HEER, the area is not divided into subregions. But the sink locations for HEER are also the same as that for MHEER. The difference is that in MHEER each region is predefined and each region has its own CH to transmit the data to the sink, whereas, in HEER, the regions are not predefined and clusters change their shape and size.


## 7. Conclusion

In this paper, we have proposed two scalable routing protocols, HEER and MHEER. The proposed techniques select the cluster heads based upon the residual energy of the nodes. Fixed number of cluster heads (only in MHEER) are selected in each cycle of protocol operation; we call it “round.” Because of HEER’s reactive nature, it reduces the number of transmissions and results in better network lifetime and stability region than TEEN and DEEC. On the other hand, MHEER yields better results in terms of lifetime and stability period as compared to HEER. The number of CHs in HEER is not fixed in every round, whereas MHEER uses static clustering. It also takes into account the maximum energy nodes at the start of each round for the CH selection. HEER and MHEER are then incorporated with mobile sinks. As mobile sink has no constraints of energy consumption, it enhances the working of both techniques. Ultimately, HEER and MHEER outperform TEEN, DEEC, and HEER protocols in network lifetime, stability period, area coverage, and throughput. Thus, these schemes enhance the desired attributes, minimum energy consumption, maximum stability period, better lifetime, and throughput, as compared with other protocols. Thirdly, both of the proposed techniques are scalable; that is, they even perform well when run for 500 and 1000 nodes in the same scenarios.



---

*Source: 908495-2015-10-25.xml*