Energy Hole Minimization with Field Division for Energy Efficient Routing in WSNs

Abstract

We analyze performance of famous cluster based routing protocols and identify the factors affecting energy consumption in wireless sensor networks (WSNs). From theoretical and experimental analysis, it is observed that communication distance and cluster node density are the major sources in the formation of energy and coverage holes. To overcome these deficiencies, we propose a new hybrid approach of static clustering and dynamic selection of cluster heads. We also conduct a comprehensive energy consumption analysis of our technique with selected existing ones. Simulation results show that the proposed technique is relatively better in terms of energy holes minimization and network lifetime prolongation.

1. Introduction

Due to limited battery power of sensor nodes, their energy consumption during network operation is of high concern. Definition of network lifetime varies from application to application. In some cases, network lifetime is considered till death of the first node, while in others it is considered till the death of all nodes [1]. Whatever the definition of network lifetime is, the main purpose is to prolong network lifetime till the required objectives are met. Sensors' battery is the only source of power to keep the network alive. Therefore, network energy must be conserved to fulfil network lifetime requirement of the application. In order to accomplish the energy conservation goal, it is important to find how energy is consumed during network operations. The following are the factors that may affect energy consumption in clustered routing protocols:

• (i)

Distance between cluster head (CH) and base station (BS) is the major factor of energy consumption. If the CH is at far distance from BS, then it has to apply amplification energy to transmit gathered data to BS, consuming a lot of energy.

(ii)

Large size of the cluster is another factor of high energy consumption. Cluster with high number of nodes becomes the reason to quickly drain CH's energy.

(iii)

Optimum number of CHs selection is very important towards balanced energy consumption, because a large number of CHs formed are equivalent to direct communication of nodes to BS and a small number of CHs formed lead to large sized cluster(s). Both cases cause surplus energy consumption.

(iv)

Multihop communication of CHs also leads to high energy consumption as transmissions and receptions are relatively high in number.

Any of the above factors may lead to the creation of energy holes. Energy hole is actually a phenomenon of overloading a node or CH for communication, which causes early death of the node or CH. Creation of energy hole not only reduces the network lifetime but also affects network throughput. Apart from routing layer energy consumption, MAC layer contentions also contribute to energy consumption. However, in this research work, we limit our scope to routing layer energy consumption issues only.

This work is extended form of our previous work in [2]. In this work, our main contributions are as follows. First we identify how unbalanced energy consumption in the traditional clustering protocols becomes the reason for creation of energy holes; to overcome this problem we propose a new technique in which we divide the network field into fixed logical regions. Static clustering and dynamic CH selection technique is used in this approach. A comprehensive mathematical formulation is provided in this work. The simulation results show improved stability period and reduced chance of energy hole creation.

The rest of the paper is organised as follows: Section 2 describes and criticises the work done in literature close to our work; Section 3 elaborates the problem statement in detail; Section 4 describes our proposed scheme; in Section 5, we present energy consumption model of our proposed work; performance evaluation of our proposed scheme with existing scheme is provided in Section 6; and finally conclusion is presented in Section 7.

2. Related Work

LEACH [3] is an initial clustering protocol, introduced by Heinzelman et al. In this protocol, CHs are selected on the basis of random number; therefore, there are chances that the number of CHs formed may or may not be optimum. This causes unbalanced load distribution among the nodes; as a result energy holes are created in the network.

Application-Specific Low Power Routing (ASLPR) protocol [4] is introduced by Shokouhifar and Jalali. Authors provided an application-specific approach for maximizing application required parameter of the protocol such as stability period, network lifetime, and 50% nodes death time. They used genetic algorithm for maximization or minimization of the required parameter. However, performance enhancement of certain parameter is achieved at the cost of other parameters.

Amjad et al., in [5], introduced a new clustering technique, Distributed Regional Energy Efficient Multihop Routing Protocol based on Maximum Energy (DREEM-ME), in WSNs. Authors succeeded in balancing energy consumption of nodes to some extent by dividing the circular field into subfields. Nodes within the subfield suffer long distance communication when these are located at one corner of the subfield and CH is located at the other corner. In such situations, nodes cannot associate with neighbouring subfield's CH, which is at shorter distance.

LEACH-Centralized (LEACH-C) is an extension of LEACH, which is proposed by Heinzelman [6]. In LEACH-C, BS gathers information about each node's location and energy level. Selection of CH is also probabilistic like LEACH. The plus point of this algorithm is that BS makes sure that the node with less energy does not become CH. However, in large scale networks, nodes which are far away from BS are unable to send their energy status to BS.

Israr and Awan [7] introduced Multiclustering protocol. In this protocol, CHs are selected randomly. Inter cluster communication is done through multihoping which reduces energy consumption due to reduced communication distance. Finally, data reaches BS through a number of CHs. Multihop communication could be a source of energy hole creation, if load is not balanced. The beauty of multihop-LEACH is its guaranteed network connectivity.

Kiani et al. introduced Efficient Intelligent Energy Routing Protocol in wireless sensor networks [8]. In this protocol, cluster shapes are square and a learning machine is introduced for selection of CH. Q-learning [9] technique and a cost function are used for selection of CH. Q-learning is a type of reinforcement learning approach which is based on genetic algorithm. Cost function is based on residual energy of a node and distance of node from BS. Node with maximum Q-value and minimum cost function value is selected as CH. LEACH-Selective Cluster (LEACH-SC) [10] is another cluster based routing protocol introduced by Wang et al. In this protocol, CH selection is probabilistic. A center point between node and sink is calculated. Node nearest to center point is selected as CH. Due to probabilistic selection of CH, the number of CHs in the entire network fluctuates around the optimum number of CHs.

In [11], authors proposed energy consumption model and tried to find energy hole in cluster based routing protocols. Authors identified different areas within the network in which more energy is consumed.

Localization techniques presented in [12, 13] divide the network area into subareas such that the chances of coverage hole creation are minimized.

Cluster based Multipath Routing Protocol (CMRP) is introduced by Sharma and Jena in [14]. This technique operates in four phases: neighbor discovery and topology construction, CH selection and cluster formation, data dissemination, and reclustering and rerouting. In neighbour discovery phase, all nodes send their neighbour information to BS. BS then forms an adjacency matrix on the basis of which it selects CHs. In data dissemination phase, CH and nodes send data in their respective time slots; otherwise these remain in sleep mode to conserve energy. BS monitors nodes' residual energy; as any node's residual energy falls to a certain threshold reclustering and rerouting phases are triggered.

Huang et al., in [15], studied lifetime of cluster in multihop communication. They find out the effects of transmission distance and size on lifetime of cluster.

3. Problem Statement

In this section, we elaborate the drawbacks of clustering protocols, LEACH and ASLPR. These drawbacks motivated us to propose a new protocol.

Probabilistic selection of CHs and transmission distance are two major factors that increase energy consumption of a node. Probabilistic selection of CH does not ensure optimum number of CHs during network operation. When the number of CHs is not optimum, some CHs become overloaded, which consume relatively high network energy [16]. Furthermore, if the overloaded CH is far away from BS then it has to expend more energy to send data to BS. In the following discussion, we elaborate how these two factors affect energy consumption of a node.

(1) Probabilistic CH Selection Does Not Guarantee Nonoccurrence of the Energy Hole Problem during Network Operation. In this method, protocol sets a threshold value for each node to elect itself as CH and then compares this value with a random number. If the random number is less than or equal to the threshold value, then the node becomes CH; otherwise it does not become CH. Due to probabilistic nature of CHs' selection, the total number of CHs fluctuates around the optimum value.

Let N sensor nodes be deployed in a network filed with node density ρ. The number of nodes n in a cluster of radius R can be calculated via the following:

$$\begin{array}{cc}& n=\rho \pi R^{\mathrm{2}}.\end{array}$$

(1)

In the above equation, if ρ is constant then it is clear that n is directly proportional to R of the cluster. If there are fewer number of clusters in the network, it means that R is increased and a large number of nodes are associated with each CH and vice versa. Therefore, we can deduce an inverse relation between R and number of CHs ( $N_{\text{chs}}$ ) in (2) as follows. Consider

$$\begin{array}{cc}& R\propto \frac{\mathrm{1}}{N_{\text{chs}}}.\end{array}$$

(2)

Assume that $n_{\text{opt}}$ is the optimum number of CHs in the network and, by taking (2) into consideration, two cases are possible.

Case 1 (if $N_{\text{chs}}>n_{\text{opt}}$ ).

In this case, R of the cluster decreases and $N_{\text{chs}}$ increases, which results in increased number of long distance transmissions that ultimately leads to high energy consumption.

Case 2 (if $N_{\text{chs}}<n_{\text{opt}}$ ).

In this case, R of the cluster increases and $N_{\text{chs}}$ decreases. It means that data load on CH is increased which increases CH's energy consumption rate.

(2) Distant CHs Consume More Energy. Figure 1 shows energy consumption of CHs at different distances from BS. In this experimental setup, we place BS at zero point of network field. As expected, result shows that CHs near BS deplete less energy as compared to the far away ones. However, the reason of higher energy consumption of CHs which are at shorter distance from BS is large cluster size. These CHs have to forward large amount of data.

Figure 1

Energy consumption of CHs.

(3) Random Deployment of Nodes Does Not Guarantee Avoidance of the Coverage Hole Problem. Random deployment of nodes may cause overlapping problem; that is, two nodes located in the same area sense same location, whereas some area may not be sensed [17]. This may create coverage hole problem.

In ASLPR and LEACH, CH selection process is probabilistic and CHs directly communicate with BS. Therefore, in these protocols, chances of creation of energy and coverage hole are maximum. In the next section, we propose an idea in which we overcome these deficiencies.

4. Proposed Scheme

Localization problem has been commonly addressed. In this problem, network area is logically divided into subareas [12, 13] that helps in controlling the coverage hole problem. Therefore, we also use divide and rule technique to resolve this problem. In this section, we describe formation of regions and their mathematical formulations, CHs' selection procedure, protocol operation, and communication schematic of our proposed scheme.

4.1. Formation of Regions

In traditional cluster formation techniques, CHs are selected on the basis of probability. Nodes then associate with each CH on the basis of received signal strength, thus forming a cluster. In our protocol, BS divides the entire network area into small logical regions. Each region represents a static cluster, which reduces the communication distance between node and CH, and CH and BS. The following two steps describe the formation of regions in detail.

In step one, network area is divided into n equal distant concentric squares. Value of n is taken as $\mathrm{3}$ . Therefore, network is divided into three equal distant concentric squares. We name these square as internal square ( $I_s$ ), middle square ( $M_s$ ), and outer square ( $O_s$ ). BS is located at the centre of the network field; therefore its coordinates are taken as reference point subject to concentric squares formation. Coordinates of centre point are represented as $C_p(x_{\mathrm{1}},y_{\mathrm{1}})$ . The following equations are used to divide network field into concentric squares.

Coordinates of the top right corner of $I_s$ are

$$\begin{array}{cc}& T_r^{I_s}\left(x_{\mathrm{2}},y_{\mathrm{2}}\right)=\left(x_{\mathrm{1}}+d,y_{\mathrm{1}}+d\right).\end{array}$$

(3)

Coordinates of the bottom right corner of $I_s$ are

$$\begin{array}{cc}& B_r^{I_s}\left(x_{\mathrm{3}},y_{\mathrm{3}}\right)=\left(x_{\mathrm{1}}+d,y_{\mathrm{1}}-d\right).\end{array}$$

(4)

Coordinates of top left corner of $I_s$ are

$$\begin{array}{cc}& T_l^{I_s}\left(x_{\mathrm{4}},y_{\mathrm{4}}\right)=\left(x_{\mathrm{1}}-d,y_{\mathrm{1}}+d\right).\end{array}$$

(5)

Coordinates of bottom left corner of $I_s$ are

$$\begin{array}{cc}& B_l^{I_s}\left(x_{\mathrm{5}},y_{\mathrm{5}}\right)=\left(x_{\mathrm{1}}-d,y_{\mathrm{1}}-d\right),\end{array}$$

(6)

where d is the distance from the center of network field to the boundary of $I_s$ as shown in Figure 2.

Figure 2

Formation of regions.

If we have n number of concentric squares, then the coordinates of nth square $(S_n)$ can be found out from the following way:

$$\begin{array}{cc}& d=\frac{x\mathrm{1}}{n}.\end{array}$$

(7)

d is multiple of $\mathrm{2}$ and $\mathrm{3}$ for $M_s$ and $O_s$ , respectively:

$$\begin{array}{cc}& d_{\mathrm{2}}=\mathrm{2}d,\\ d_{\mathrm{3}}=\mathrm{3}d.\end{array}$$

(8)

From (8) we can establish a relation to find d for nth square as

$$\begin{array}{cc}& d_n=nd,\\ S_n^{T_r}\left(x_n,y_n\right)=\left(x_{\mathrm{1}}+d_n,y_n+d_n\right),\\ S_n^{B_r}\left(x_n,y_n\right)=\left(x_{\mathrm{1}}+d_n,y_{\mathrm{1}}-d_n\right),\\ S_n^{T_l}\left(x,y\right)=\left(x_{\mathrm{1}}-d_n,y_{\mathrm{1}}+d_n\right),\\ S_n^{B_l}\left(x,y\right)=\left(x_{\mathrm{1}}-d_n,y_{\mathrm{1}}-d_n\right).\end{array}$$

(9)

In step two, network area between two concentric squares is divided into two types of quadrilaterals; square regions formed at the corners are named as corner regions (CRs) and rectangular regions which are formed in the middle are named as noncorner regions (NCR) as shown in Figure 2. Theoretically, these areas can be obtained by taking top right and bottom right corners of $I_s$ as reference points. Adding d in x-coordinate of top right and bottom right corners of $I_s$ , that is, $(x_{\mathrm{2}}+d,y_{\mathrm{2}})$ and $(x_{\mathrm{3}}+d,y_{\mathrm{3}})$ , we get points A and B on $M_s$ as shown in Figure 2. Connecting A and B with top right and bottom right corners, respectively, we get rectangle NCR1. Following the same procedure we get rectangles NCR2, NCR3, and NCR4. Four other square regions are CR1, CR2, CR3, and CR4. Area between $M_s$ and $O_s$ is also divided in the same way to get NCR5, NCR6, NCR7, and NCR8. Remaining four square regions are CR5, CR6, CR7, and CR8.

4.2. CH Selection

In our protocol, CH selection process is centralized. In the setup phase, BS decides which node will be the CH in each cycle. BS knows the location of all node; therefore, on the basis of central reference point of each region, BS decides CH in each cycle. BS prepares this schedule in each cycle and broadcasts it to all nodes. Each node on reception of CH schedule associates itself with BS's nominated CH. BS disqualifies those nodes to become CH whose residual energy status is below threshold. Nodes inform BS about their residual energy status by embedding current energy status in the data packet while sending data to CH or BS. DR protocol considers multihop inter cluster communication. As we assume $n=3$ , inter cluster communication is performed at two levels, primary and secondary. Selection of primary level CH follows the following sequence: (i) nodes in $I_s$ are near BS and directly send data to BS; (ii) one CH is selected in each NCR; (iii) mid-point of each NCR is considered as a reference point for the selection of CH; and (iv) node near central reference point is selected as CH first; in next simulation cycle, next nearest node from the reference point is selected as CH and so on.

Secondary level CH are selected as follows: (i) CHs in $O_s$ region forward data to CHs of adjacent $M_s$ region's CHs; (ii) they aggregate data of their own nodes and data from primary level CH; and (iii) then secondary level CHs transmit aggregated data to BS.

In this scheme, nodes associate with CH in two different methods. In first method, nodes of the same region are associated with their own region's CH only. Therefore, this method of association is known as confined association of nodes with respective region's CHs. Second method of association is known as nonconfined association of nodes. In this method, a node can be associated with neighbouring region's CH on the basis of minimum distance. For example, if a node of NCR1 is nearer to NCR2's CH, then it is associated with NCR2's CH instead of NCR1's CH. Both these methods have their own advantages and disadvantages; therefore, in performance evaluation section, we performed experiment with these methods separately.

4.3. Protocol Operation

In setup phase, BS divides the network field into small regions. In each region, one CH is selected per cycle. CHs of $O_s$ regions select front neighboring CHs of $M_s$ regions as their next hop CHs. Nodes of CR send data to BS or associate themselves with one of the neighbouring region CHs, based on minimum distance. If distances are equal, then CH with greater residual energy is selected. $I_s$ nodes directly send data to BS. In our technique CH selection process is centralized; therefore nodes do not perform CH selection process distributively, which saves time and energy, unlike LEACH in which nodes execute CH selection process in each round. Thus our technique is fast and efficient in terms of energy and network lifetime compared to other techniques as shown in Figures 7 and 9.

In steady state phase, each node sends data to CH in its allocated time slot. Primary level CHs send aggregated data to their respective secondary level CHs that forward the aggregated data to BS.

4.4. DR Schematic

Our proposed scheme is summarized with the help of schematic diagram shown in Figure 3. The diagram shows three types of communications: type 1, type 2, and type 3. Nodes that belong to $I_s$ directly communicate with BS, and this type of communication is known as type 1 communication. Similarly, nodes that lie within the premises of $M_s$ send data to CH, which communicates with BS; such type of communication is called type 2 communication. Finally, nodes of $O_s$ send data to their respective regions CHs and then CHs of NCR5, NCR6, NCR7, and NCR8 communicate with their adjacent front neighbour CHs as the next hops; such type of communication is called type 3 communication.

Figure 3

Schematic of DR.

In our technique, CH selection is centralized. Each CH receives a message from BS containing CH ID, next hop and previous hop CH IDs. BS uses FDMA scheme to communicate with CHs. In this scheme, dedicated frequency is allocated to each CH. Inter cluster communication is performed through TDMA based scheduling. Each node sends data to its respective CH within its allocated time slot. TDMA schedule also contains a time slot for previous hop CH. The flowchart in Figure 4 shows TDMA slot allocation process of nodes and CHs.

Figure 4

TDMA slot allocation.

Direct Sequence Spread Spectrum (DSSS) technique is used to avoid node to CH and CH to CH collision. During TDMA scheduling, CHs inform member nodes to send data according to allocated DSSS code. This type of coding is known as transmitter based coding [17].

5. Energy Consumption Model

In this section, we develop a mathematical model to calculate energy consumption in different regions of the network field. In literature, different radio models have been introduced as selection of simulation radio model varies from application to application. For example, [18] presents simulation radio model for park and university areas. However, we adopt basic radio model from [19] due to its typical usage. The energy consumption equations (10) and (11) are adopted from [19] which show per bit energy cost of transmission ( $T_{\text{Eenergy}}$ ) and reception ( $R_{\text{Energy}}$ ) of data over the distance D. Consider

$$\begin{array}{cc}& T_{\text{Eenergy}}=\left\{\begin{array}{cc}{E}_{\text{elec}}+{\epsilon }_{f_s}{D}^{\mathrm{2}}\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}D<D_{\mathrm{0}}\hfill \\ E_{\text{elec}}+{\epsilon }_{\text{amp}}{D}^{\mathrm{4}},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}D\ge D_{\mathrm{0}},\hfill \end{array}\right.\end{array}$$

(10)

where $D_{\mathrm{0}}$ is the reference distance. Consider

$$\begin{array}{cc}& \begin{array}{c}{R}_{\text{Energy}}=\left(E_{\text{elec}}\right).\end{array}\end{array}$$

(11)

5.1. Energy Consumption in $I_s$

In this subsection, we first calculate node density and then energy consumption in $I_s$ . From Figure 2, each side of $I_s$ is $\mathrm{2}d$ in length and width; therefore, area of $I_s$ is

$$\begin{array}{cc}& A_{I_s}=\mathrm{4}{d}^{\mathrm{2}}.\end{array}$$

(12)

The number of nodes in $I_s$ is given by

$$\begin{array}{cc}& N_{I_s}=\mathrm{4}\rho d^{\mathrm{2}},\end{array}$$

(13)

where ρ is the node density per unit area.

Nodes of $I_s$ directly transmit data to BS; therefore, their energy consumption “ $E_{I_s}^{T_x}$ ” is given by the following equation:

$$\begin{array}{cc}& E_{I_s}^{T_x}=\mathrm{4}\rho d^{\mathrm{2}}{T}_{\text{Energy}}.\end{array}$$

(14)

5.2. Energy Consumption in CRs

From Figure 2, d is the reference distance for the formation of NCR. Therefore, area of CR is given by

$$\begin{array}{cc}& A_{\text{CR}}=d^{\mathrm{2}}.\end{array}$$

(15)

The number of nodes in CR is given by

$$\begin{array}{cc}& N_{\text{CR}}=\rho d^{\mathrm{2}}.\end{array}$$

(16)

Depending on minimum distance, nodes of CR may transmit data to BS or to neighbouring NCR's CH. Their energy consumption “ $E_{\text{CR}}^{T_x}$ ” for sending data to BS is given by the following equation:

$$\begin{array}{cc}& E_{\text{CR}}^{T_x}=\left(\mathrm{1}-P\right)\rho d^{\mathrm{2}}{T}_{\text{Energy}},\end{array}$$

(17)

where P is the probability of sending data to CH and $(\mathrm{1}-P)$ is the probability of sending data to BS.

5.3. Energy Consumption in $M_s$

In $M_s$ , there are two types of nodes, normal and CHs. We separately calculate their energy consumption.

There are four NCRs and four CRs. The area of each NCR in $M_s$ is $\mathrm{2}{d}^{\mathrm{2}}$ . Each CR node may associate with one of the NCR CHs or directly send data to BS. Energy consumption of non-CH nodes in $M_s$ per NCR ( $E_{M_s/\text{NCR}}^{T_x}$ ) is given by the following equation:

$$\begin{array}{cc}& E_{M_s/\text{NCR}}^{T_x}=\left(\mathrm{2}\rho d^{\mathrm{2}}-\mathrm{1}\right)T_{\text{Energy}}.\end{array}$$

(18)

There are total four regions, one CH in each region. Each CH consumes energy in transmission ( $E_{M_s\_\text{CH}}^{T_x}$ ), aggregation, (ϕ) and reception ( $E_{M_s\_\text{CH}}^{Rx}$ ) processes; therefore, the energy consumption of each CH is calculated individually as follows.

Transmission Energy. Consider

$$\begin{array}{cc}& E_{M_s\_\text{CH}}^{T_x}=\left(\mathrm{2}\rho d^{\mathrm{2}}+P\rho d^{\mathrm{2}}\right)T_{\text{Energy}}+\varphi .\end{array}$$

(19)

Transmission energy of all CHs, $E_{M_s\_\text{all}\_\text{CH}}^{T_x}$ , in regions of $M_s$ is given by the following equation:

$$\begin{array}{cc}& E_{M_s\_\text{all}\_\text{CH}}^{T_x}=\left(\mathrm{8}\rho d^{\mathrm{2}}+\mathrm{4}P\rho d^{\mathrm{2}}\right)T_{\text{Energy}}+\mathrm{4}\varphi .\end{array}$$

(20)

Receive Energy. Equation (21) calculates receive energy of CH as follows:

$$\begin{array}{cc}& E_{M_s\_\text{CH}}^{Rx}=\left(\left(\mathrm{2}\rho d^{\mathrm{2}}-\mathrm{1}\right)+P\rho d^{\mathrm{2}}\right)R_{\text{Energy}}.\end{array}$$

(21)

Receive energy of all CHs, $E_{M_s\_\text{all}\_\text{CH}}^{Rx}$ , in regions of $M_s$ is given by the following equation:

$$\begin{array}{cc}& E_{M_s\_\text{all}\_\text{CH}}^{Rx}=\left(\left(\mathrm{8}\rho d^{\mathrm{2}}-\mathrm{4}\right)+\mathrm{4}P\rho d^{\mathrm{2}}\right)R_{\text{Energy}}.\end{array}$$

(22)

Total communication energy consumed in all regions of $M_s$ is given by the following equation:

$$\begin{array}{cc}& E_{M_s}^{\text{Tot}}=E_{M_s\_\text{node}}^{T_x}+E_{M_s\_\text{all}\_\text{CH}}^{T_x}+E_{M_s\_\text{all}\_\text{CH}}^{Rx}.\end{array}$$

(23)

5.4. Energy Consumption in $O_s$

In DR protocol, area of NCR of $O_s$ increases from $I_s$ to $O_s$ . Length of one side of $M_s$ 's NCR is equal to $\mathrm{2}d$ . Similarly, length of one side of $O_s$ 's NCR is equal to $\mathrm{4}d$ . On the other hand, width of all the regions remains the same, that is, d. Considering values of length and width, area of each NCR of $O_s$ can be calculated as $\mathrm{4}{d}^{\mathrm{2}}$ . Taking area into account, total energy consumption of $O_s$ is calculated by the following equation:

$$\begin{array}{cc}& E_{O_s}^{\text{Tot}}=E_{O_s\_\text{node}}^{T_x}+E_{O_s\_\text{all}\_\text{CH}}^{T_x}+E_{O_s\_\text{all}\_\text{CH}}^{Rx}.\end{array}$$

(24)

5.5. Experimental Analysis of Theoretical Model

Our main focus is to reduce the communication distance between node and CH or/and between CH and BS. In this section, we conduct experiments to verify our theoretical model. Energy consumption of nodes mainly depends on transmission distance and packet size that is why nodes in different regions of the network die at different instants. In addition to these two reasons, energy consumption of CHs depends on the number of associated nodes.

(1) Effect of Distance on Energy Consumption of CH. In the first experiment, we randomly deploy 11 nodes in each region of the network field. Nodes are initialized with homogeneous energy of 0.5 joules. After execution of cluster setup phase, distance information is gathered as shown in Table 1. The result of this experiment is shown in Figure 5.

Table 1

Distance between CH to CH and BS.

	Distance from BS (m)	Inter CH distance (m)
$M_s$ CH	26.05	20.02
$O_s$ CH	42.91

Figure 5

Impact of distance on energy consumption of CH.

Finding 1. Figure 5 shows the difference of energy consumption between $O_s$ CH and $M_s$ CH. Energy consumption of $O_s$ CH is plotted for two different scenarios: first when it directly sends data to BS and second when data is sent to $M_s$ CH. Direct communication with BS exponentially increases energy consumption because of long distance. However, energy consumption of $M_s$ CH is minimum due to shorter distance. The same result can also be analyzed in (19). If we simplify (19) keeping ρ and ϕ constant as shown in (25), we can analyze that energy consumption is directly proportional to the distance. Hence it is proved that experimental results are supporting theoretical analysis. Consider

$$\begin{array}{cc}& E_{M_s\_\text{CH}}^{T_x}\propto \rho d^{\mathrm{2}}.\end{array}$$

(25)

(2) Effect of Node Density on Energy Consumption of CH. In the second experiment, we conduct tests for different node densities. A number of nodes associated with a CH are taken as 10, 25, 50, and 75. The rest of the experimental settings is the same as that of experiment 1. In this experiment, our objective is to analyze the effect of node density on energy consumption. Results of this experiment are shown in Figure 6.

Figure 6

Impact of density on energy consumption of CH.

Figure 7

Average energy consumption.

Finding 2. In experimental results of Figure 6, increase in energy consumption of $O_s$ CH for node densities of 10 and 25 is linear when it sends data to $M_s$ CH. The reason behind linear increase is shorter distance and less node density. The effect of node density on $M_s$ CH is also linear. However, for node density of 50, energy consumption increases quadratically. Above node density of 50, energy consumption of $M_s$ and $O_s$ CHs is also quadratic. However, if distance increases then node density and long distance create a combined effect on energy consumption. As shown in Figure 6, energy consumption of $O_s$ CH increases exponentially when it sends data to BS; that is, energy consumption steps up from .002 j to .01 j. Now if we analyze (19) and simplify it as (25) by keeping ϕ as constant then we can see that energy consumption is directly proportional to the product of node density and distance. Hence, experimental and theoretical results are supporting each other. In order to achieve prolonged network lifetime, theoretical and experimental results lead us to the conclusion: balanced node density among CHs and reduced communication distance are necessary. Therefore, we have proposed a technique to reduce communication distance through intra-CH communication and inter cluster communication and to reduce load on each CH via regions formation.

6. Performance Evaluation

We evaluate our proposed DR scheme by comparing it with ASLPR, DREEM-ME, and LEACH in terms of stability period, network lifetime, throughput, average energy consumption, propagation delay, and scalability. In this section, association of nodes with CH as confined and nonconfined is experimented separately. The results of confined method of association are named as CDR and those of nonconfined association are named as NCDR. We assume a network area of $100\hspace{0.17em}\text{m}\times 100\hspace{0.17em}\text{m}$ , with $\mathrm{100}$ nodes initialized with homogeneous amount of energy. Nodes are uniformly distributed and randomly deployed within the regions. BS is placed at the centre of network field. First-order simulation radio model [19] is used to calculate energy consumption in transmission and reception process. According to this model, $\mathrm{50}$  nJ/bit energy is consumed in transmit and receive electronics, $\mathrm{5}$  nJ/bit/signal in data aggregation process, $\mathrm{10}$  pJ/bit/4m² in amplification of radio signal when transmission distance is less than prescribed range (reference distance), and $\mathrm{0.013}$  pJ/bit/m⁴ in amplification of radio signal when transmission distance is greater than reference distance. Average results are obtained after 5 times of execution of all protocols with $\mathrm{95}\%$ confidence interval.

6.1. Average Energy Consumption

Energy consumption of all compared protocols and our technique is shown in Figure 7. From this experimental comparison it can be seen that average energy consumption of CDR's nodes is minimum. Reduction in communication distance and load sharing of CHs through multihop communication are the major causes of low energy consumption. Energy consumption of NCDR is slightly higher than CDR. The reason is that in NCDR nodes are free to associate with any of the neighbouring region's CHs; therefore, load on neighbouring region's CH may increase which increases energy consumption.

6.2. Stability Period and Network Lifetime

Stability period is the time when death of the first node occurs. This time is also known as first node death time (FDT). As we can see from Figure 8 and Table 2, FDT of LEACH occurs at 2196th second, whereas FDT of ASLPR and DREEM-ME occurs at 2793th second and 3336th second, respectively. However, FDT of CDR is at 4139th second which shows that CDR is more stable. Figure 9 shows that difference between FDT and all nodes death time (ADT) of CDR is large, whereas this difference is small in other compared techniques. Therefore, we can say that CDR's ADT is $\mathrm{46.94}\%$ , $\mathrm{32.51}\%$ , and $\mathrm{19.4}\%$ more than LEACH, ASLPR, and DREEM-ME, respectively. Balanced energy consumption reduces the chance of creation of energy hole. Load balancing in CDR is achieved through association of fixed number of nodes with each CH in each cycle. On the other hand, energy consumption of nodes in LEACH and DREEM-ME is not balanced due to which nodes' start dying continuously after FDT. Unbalanced load distribution and nonoptimized number of CHs cause sharp slope of LEACH graph line in Figure 9. Steady slope line of CDR protocol is because of balanced energy consumption of nodes and CHs. FDT of CDR and DREEM-ME is almost the same because the number of CHs and node density are kept the same in DR and DREEM-ME. However, CDR leads in network lifetime. Network lifetime of DREEM-ME decreases rapidly and $\mathrm{85}\%$ of the nodes die after just 402 seconds of FDT, which also shows creation of energy hole. FDT of NCDR also occurs quickly. The main reason is unbalanced load distribution of nodes with CH. It may be possible that more nodes are closer with any one CH due to which transmission load on this CH may increase and its energy depletes quickly which ultimately reduces FDT.

Table 2

FDT and ADT comparison.

Protocol	FDT	ADT	Improvement of DR in FDT (%)	Improvement of DR in ADT (%)
DR	4139	9565	—	—
DREEM-ME	3336	8921	19.4	6.73
ASLPR	2793	4028	32.51	57.88
LEACH	2196	3098	46.94	67.61

Figure 8

Comparison: dead nodes.

Figure 9

Comparison: alive nodes.

6.3. Throughput

Throughput is measured in terms of successfully received packets at BS. However, the total number of packets sent is not necessarily equal to the number of received packets at BS. For simulations, we use random uniform model [20] for packet drop count. According to this model, a packet is dropped if link status is bad. In this simulation setup, we suppose that the probability of bad link is $\mathrm{30}\%$ .

Figures 10 and 12 show that, in CDR and NCDR, a more number of packets are received as compared to LEACH, ASLPR, and DREEM-ME. There are three reasons behind higher throughput of CDR and NCDR: (1) enhanced network lifetime, (2) enhanced stability period, and (3) improved connectivity. However, due to longer network lifetime, number of packets transmitted are higher; therefore packets' drop rate is also higher as depicted in Figure 11. Improvement of CDR over DREEM-ME, ASLPR, and LEACH in terms of packets sent, packets received, and packets dropped is shown in Table 3.

Table 3

Comparison: packets sent, packets received, and packets dropped.

	DR	DREEM-ME	ASLPR	LEACH
Packets sent	126335	100520	12176	9785
Improvement of DR (%)		20.43	90.36	92.25
Packets received	88449	70538	8548	6901
Improvement of DR (%)		20.25	90.33	92.19
Packets dropped	37886	29982	3628	2884
Improvement of DR (%)		−20.86	−90.42	−92.38

Figure 10

Comparison: packets sent to BS.

Figure 11

Comparison: packets dropped.

Figure 12

Comparison: throughput.

6.4. Propagation Delay

Propagation delay is the time taken by a packet to reach BS (Figure 13). In LEACH and ASLPR, CHs directly send data to BS without involving intermediate hops. Therefore, in these protocols, propagation delay is directly proportional to the distance covered by a packet to reach BS. Meanwhile, in CDR, NCDR, and DREEM-ME, CHs are using intermediate hop to send data to BS. Therefore, the start of the network propagation delay of all four protocols is almost the same. Propagation delays of CDR and DREEM-ME are minimum as compared to LEACH and ASLPR because former protocols also use intermediate hop to send data to BS. However, as the network operation progresses, propagation delay reduces gradually. This is because farthest nodes in CDR die earlier and then the nearest nodes.

Figure 13

Comparison: propagation delay.

6.5. Scalability Analysis

A large number of nodes are involved in WSN; therefore it is essential to measure the performance of network in terms of scalability. Scalability is the measurement of the performance of network when communication load increases or network grows larger. A routing protocol is said to be scalable if it maintains or degrades, in a minor way, its performance with the expanding communication load. To measure the performance of proposed and existing protocols discussed in this research work, FDT, ADT, throughput, and packets drop are selected as the performance parameters. In the experimental setup, we randomly deployed 100, 300, 500, 800, and 1000 nodes in the network field. Figure 14 shows experimental result of FDT. In this experimental result, performance of LEACH remains stable with minor fluctuation in FDT; however, its performance is not improved. Performance of ASLPR, CDR, and NCDR is also inconsistent. In ASLPR, for 100, 300, and 500 nodes, performance of the protocol shows improved trend. The reason behind improved performance is that with the increase in number of nodes overall energy of the network is increased; therefore plot is showing increasing trend. However, for 800 and 1000 nodes, performance is slightly decreased; this is because more than 500 nodes in ASLPR are creating interference effect due to which nodes are wasting energy in overhearing. In CDR, nodes experience more interference effect because ADT is degraded. The reason behind degrading effect is that nodes in the regions are equally deployed; therefore increase in number of nodes is creating equal interference effect which is collectively degrading overall FDT performance of CDR. Performance of DREEM-ME and NCDR also shows continuous degrading trend. There are two reasons; nodes in the clusters of DREEM-ME and NCDR are equally distributed; however, these are free to associate with neighbouring cluster's CH, which increases load on neighbouring CH and the other reason is interference.

Figure 14

First node death time.

Figure 15 depicts performance analysis of protocols under discussion in terms of ADT. Figure 15 shows that behaviour of CDR, NCDR, and DREEM-ME is stable. It shows that, with the passage of time as nodes die, interference effect is reduced and nodes' ADT time becomes the same for varying number of nodes. ADT of ASLPR and LEACH is fluctuating. In ASLPR, it is increased for 300, 500, and 800 nodes; however, it is decreased for 1000 nodes.

Figure 15

All nodes death time.

Figures 16 and 17 represent behavior of these protocols in terms of packet drop and throughput. In both cases, increasing trend of CDR, NCDR, and DREEM-ME is logarithmic. The reason is straightforward; ADT of CDR, NCDR, and DREEM-ME protocols is also higher than LEACH and ASLPR. However, packet drop and throughput analysis of LEACH and ASLPR show that increasing trend is linear. The reason is that their ADT is less than CDR and DREEM-ME.

Figure 16

Packet drop for different number of nodes.

Figure 17

Throughput for different number of nodes.

From the above experimental analysis of scalability, it is clear that all four protocols are scalable because the performance of all protocols is almost stable in terms of ADT, FDT, throughput, and packet drop. However, minor degradation is a trade-off between increased work load and expansion of the network.

7. Conclusion and Future Work

Unbalanced load on nodes leads to the creation/formation of energy holes, which may also lead to coverage hole(s). Energy holes cause traffic blockage in multihop transmissions. In this regard, we have studied existing cluster organization based routing techniques and identified the causes of energy hole(s) creation/formation. Subject to our contribution, we have proposed static clustering and dynamic CH selection mechanism. As per our proposition, division of the network area into rectangular and square-shaped regions guarantees network coverage and cluster load balancing. Simulation results showed that, due to balanced energy consumption, network lifetime of our proposed scheme is prolonged, 6% more than ASLPR, 57% more than DREEM-ME, and 67% more than DREEM-ME. Moreover, our protocol achieves 92%, 90%, and 20% more throughput than LEACH, DREEM-ME, and ASLPR, respectively.

The drawback of our approach is that nodes of one region are bounded to associate with respective region's CH only; however, it is possible that the neighbouring CH may be at less distance than its own CH. Therefore, in future, we are interested in improving these deficiencies keeping in view a balanced network load. Moreover, we are also interested in theoretical evaluation of our proposed scheme with the existing research work.