An Energy-Heterogeneous Clustering Scheme to Avoid Energy Holes in Wireless Sensor Networks

Abstract

Clustering techniques can reduce energy consumption of nodes and increase the scalability of the network. However, in uniformly deployed clustering wireless sensor networks, the uneven distribution of communication loads often causes the energy-hole problem, which means that the energy of the nodes in the hole region will be used up sooner than the nodes in other regions. In order to solve the problem, this paper theoretically analyzes the energy consumption of nodes in different network areas, gives the expression of the optimal energy distribution of heterogeneous nodes, and designs an energy-efficient clustering routing protocol. The goal of our work is to propose an energy-heterogeneous clustering scheme (EHCS) that allows the initial energy of the sensor nodes to be varied with the distance to sink. The nearer nodes from sink have more energy. Simulation results show that the method can balance the energy consumption among sensor nodes, achieve an obvious improvement on the network lifetime, and effectively avoid the energy-hole problem.

1. Introduction

Wireless sensor networks are composed of a large number of sensor nodes with limited energy resources. In many applications, the sensor nodes are usually inaccessible to the user after being deployed, and thus, replacement of the energy resource is not feasible. Hence, energy efficiency becomes a key design issue in order to improve the life span of the entire network. In multihop wireless sensor networks characterized by many-to-one traffic pattern, the cluster heads close to sink have to forward data for cluster heads away from sink and thus will tend to die earlier, resulting in network being partitioned and network lifetime being shortened. This is called the energy-hole problem. Simulations results [1] have showed that the energy expended by a sensor node drops significantly as they move away from the sink, and the power expended by a node in the 6th corona is less than 10% of the energy expended by a node in the first corona.

In order to prolong the network lifetime, this paper proposes an energy-heterogeneous clustering scheme where sensor nodes with larger data forwarding loads are given more initial energy. EHCS is only suitable for periodic data gathering applications where in a certain time, the energy consumption of nodes in different network areas is determined and can be calculated theoretically.

The remainder of this paper is organized as follows. Section 2 introduces the literature review. Section 3 defines the network model. Section 4 analyzes the optimal initial energy of nodes. Section 5 describes the clustering algorithm. Section 6 evaluates the performance of the protocol via simulation experiments. Finally, Section 7 reaches the conclusions.

2. Related Work

In order to improve the utilization of network energy, many efficient algorithms have been presented. The first type of algorithms is to adjust transmission ranges of sensor nodes. Tran-Quang et al. [2] have formulated the transmission range adjustment optimization problem as a 0-1 multiple choice knapsack problem and presented a dynamic programming method which allows sensor nodes to dynamically set their individual transmission levels according to their residual energy. Song et al. [3] have proposed an improved corona model with levels for analyzing sensors with adjustable transmission ranges in a WSN with a circular multihop deployment. They have proved that searching optimal transmission ranges of sensors among all coronas is a multiobjective optimization problem (MOP) and have designed a centralized algorithm and a distributed algorithm for assigning the transmission ranges of sensors in each corona for different node distributions. Liu et al. [4] have presented the particle swarm optimization algorithm (PSO) to solve the routing problem of avoiding the energy hole. The algorithm redefines the particle of the PSO, the operation of particle, and the “flying” rules. Liu and Guo [5] have proposed an analytical model to characterize the energy-hole problem and have described an iterative process to determine the optimum value of the model parameters. Zeng et al. [6] have analyzed the characteristics of data distribution in WSN and have obtained some results including the distribution of energy consumptions, the lifetime of each node in different localities, and the data transferring delay. They also proposed energy-hole avoidance for WSN based on adjust transmission power.

The second type of algorithms is to use nonuniform node distribution. Wu et al. [7] have investigated the theoretical aspects of the nonuniform node distribution strategy to avoid the energy hole around the sink and have proved that in a circular sensor network with a uniform node distribution and constant data reporting, the unbalanced energy depletion among the nodes in the whole network is unavoidable. If the ratio between the node densities of the adjacent $(i+1)$ th corona and the ith corona is equal to $(2i-1)/q(2i+1)$ , a suboptimal energy efficiency among the inner parts of the network can be obtained, where q is the geometric proportion. Li et al. [8] have proposed a load-similar node distribution strategy to balance energy consumption and solve the energy-hole problem, based on the analysis of traffic load distribution in the continuous space of the network. Sensor nodes are deployed according to the load distribution. More nodes will be deployed in the range where the average load is higher. Halder et al. [9] have derived the principle of nonuniform node distribution that ensures energy balancing. They also developed a nonuniform, location-wise predetermined node deployment strategy based on this principle leading to an increase in network lifetime.

The third type of algorithms is to use mobile sinks or mobile relays to prolong the lifetime of wireless sensor networks. Marta and Cardei [10] have proposed solution to use mobile sinks that change their location when the nearby sensors' energy becomes low. In this way, the sensors located near sinks change over time. In deciding a new location, a sink searches for zones with richer sensor energy. Luo and Hubaux [11] have proved that the best mobility strategy consists in following the periphery of the network (assume that the sensors are deployed within a circle). Gao et al. [12] have proposed a data collection scheme called maximum amount shortest path (MASP) to optimize the mapping between members and subsinks. MASP has been formulated as an integer linear programming problem which is solved by a genetic algorithm. A communication protocol has been designed to implement MASP, which is also applicable in sensor networks with low density and multiple sinks. Cheng et al. [13] have proposed the architecture of multiple mobile sinks sparse wireless sensor network and an opportunistic transmission scheduling algorithm.

The above literature discuss solutions on the problem of the hot spots in flat networks. In the hierarchical network, clustering techniques can increase the scalability of wireless sensor networks and enable the efficient utilization of the limited energy resources. Many efficient energy-aware clustering routing protocols are proposed, for example, LEACH [14], LEACH_C [15], HEED [16], EADEEG [17], and PEGASIS [18].

LEACH (low-energy adaptive clustering hierarchy) utilizes randomized rotation of local cluster-heads to evenly distribute the energy load among the sensors in the network. LEACH uses localized coordination to enable scalability and robustness for dynamic networks and incorporates data fusion into the routing protocol to reduce the amount of information that must be transmitted to sink.

While LEACH has advantage to using distributed cluster formation algorithm, each node makes autonomous decisions. Then, this protocol offers no guarantee about the placement and number of cluster-head nodes. LEACH-C (LEACH-Centralized) is a protocol that uses a centralized clustering algorithm to form the clusters. During the set-up phase, each node sends information about its current location and energy level to sink. Sink runs an optimization algorithm to determine the clusters for that round. Sink may produce better clusters than those formed using the distributed algorithm by dispersing the cluster-head nodes throughout the network.

HEED (hybrid energy-efficient distributed clustering) is a novel distributed clustering approach, which does not make any assumptions about the presence of infrastructure or about node capabilities, other than the availability of multiple power levels in sensor nodes. It periodically selects cluster heads according to a hybrid of the node residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. HEED terminates in $O(1)$ iterations, incurs low message overhead, and achieves fairly uniform cluster head distribution across the network.

EADEEG (an energy-aware data gathering protocol for wireless sensor networks) adopts a new clustering parameter for cluster head election, which can better handle the heterogeneous energy capacities. Furthermore, it also adopts a simple but efficient approach, namely, intracluster coverage to cope with the fractional area coverage problem. EADEEG achieves a good performance in terms of lifetime by minimizing energy consumption for communications and balancing the energy load among all nodes.

In order to reduce the number of nodes communicating directly with sink, PEGASIS (power-efficient gathering in sensor information systems) organizes all sensor nodes into a near-optimal chain according to nodes' location by greedy algorithm. Each node transmits data to the closest possible neighbor. The data is passed along the chain from one node to another node and is fused. Finally, one designated cluster head transmits the combined data to sink. All network nodes take turns as the cluster head to balance the energy consumption of nodes. It is better than LEACH by about 100–300% in terms of network lifetime for different network topologies, but it has the greater delay and needs overall location information to construct the chain.

The above clustering protocols use randomized rotation of cluster heads to balance energy dissipation among sensor nodes. They can achieve local energy balance, but cannot avoid the energy-hole problem. From a global view, the nodes close to sink still deplete the more energy than other nodes. In order to solve the problem, UCS [19], EECS [20], and EEUC [21] use different methods.

UCS (unequal clustering size) assumes that the network is heterogeneous and cluster head nodes have more energy and predetermined locations. It organizes the network into heterogeneous clusters, where some more powerful nodes take on the cluster head role to control network operation, it is important to ensure that energy dissipation of these cluster head nodes is balanced.

EECS (energy-efficient clustering scheme) elects cluster heads with more residual energy through local radio communication while achieving well cluster head distribution; furthermore, it introduces a novel method to balance the load among the cluster heads. EECS is fully distributed and more energy efficient. Simulation results show that EECS outperforms LEACH significantly with prolonging the network lifetime over 35%.

EEUC introduces an unequal clustering mechanism to balance the energy consumption among cluster heads. Cluster heads closer to sink have smaller sizes than those heads father away from sink, thus cluster heads closer to sink can preserve some energy for the purpose of intercluster data forwarding.

3. Network Model

A sensor network consisting of N sensor nodes randomly deployed within a circle field to continuously monitor the surrounding environment. The ith sensor node is denoted by $n_i$ , and the corresponding sensor node set is denoted by $S=\{n_1,n_2,\dots ,n_N\}$ . We assume that the sensor network has the following properties.

• (i)

All sensor nodes and sink are stationary after deployment. There is a base station (i.e., sink) which is located in the center of the sensing field and has unlimited energy.

(ii)

Sensor nodes are heterogeneous, and nodes in different rings have different initial energy. All nodes are location-unaware, that is, not equipped with GPS-capable antennae. The energy of nodes cannot be renewed.

(iii)

All nodes are assigned a unique identifier and have the function of data aggregation. The intracluster sensed information is highly correlated; thus, the cluster head can aggregate N data packets from its members into a single length-fixed packet. But intercluster data is not correlated and cannot be fused.

(iv)

Nodes can figure out the distance to the sender according to RSSI (received signal strength indication) and can use power control to tune the amount of transmission power by the transmission distance to receiver. Such as the Berkeley Mote, it has 100 transmission power levels.

The network structure model is illustrated in Figure 1.

Figure 1

Network structure model.

The whole network region is divided into multilayer rings, and each ring has the same width w. Assuming that the number of rings is k, $C_i$ denotes the ith ring from the inside to the outside. In clusters, the communication radius of nodes is $r_c=w$ . In order to guarantee connectivity among the different cluster heads, the maximal communication radius of cluster heads is set to $r_h=2r_c$ . Therefore, the cluster heads in rings $C_1$ and $C_2$ can directly send data to sink, but the cluster heads in ring $C_i\hspace{0.17em}\hspace{0.17em}(i\in 3,\dots ,k)$ can only transfer data to the cluster heads in ring $C_{i-1}\hspace{0.17em}\hspace{0.17em}(i\in 3,\dots ,k)$ . The relay load steps up from the outside to the inside, and the energy of nodes also increases.

4. Energy Analysis

4.1. Energy Consumption Model

This paper uses energy consumption model in [15]. The energy dissipation of transmission depends on the distance between the transmitter and receiver. When the distance is relatively far, the multiple-path fading channel model ( $d^4$ power loss) is used. Otherwise, the free space model ( $d^2$ power loss) is used. The energy consumption for transmission of an l-bit packet over distance d is

$$\begin{array}{cc}& E_s\left(l,d\right)=\{\begin{array}{cc}l·E_{\text{elec}}+l·{\epsilon }_{\text{fs}}·d^2,\hfill & d<d_0,\hfill \\ l·E_{\text{elec}}+l·{\epsilon }_{\text{mp}}·d^4,\hfill & d\ge d_0.\hfill \end{array}\end{array}$$

(1)

The radio dissipation $E_{\text{elec}}$ is to run the transmitter or receiver circuitry, which depends on many factors, such as the digital coding and modulation. The amplifier energies ${\epsilon }_{\text{fs}}$ and ${\epsilon }_{\text{mp}}$ are, respectively, the energy required by power amplification to achieve an acceptable bit-error rate in the two models. The distance $d_0=\sqrt{{\epsilon }_{\text{fs}}/{\epsilon }_{\text{mp}}}$ is a threshold value.

To receive this message, the radio dissipates energy is

$$\begin{array}{cc}& E_r\left(l\right)=l·E_{\text{elec}}.\end{array}$$

(2)

The energy expended for data merging is

$$\begin{array}{cc}& E_m\left(m,l\right)=m·l·E_{\text{DA}},\end{array}$$

(3)

where m is the number of messages, and $E_{\text{DA}}$ is the energy dissipation per bit for fusion.

4.2. Theory Analysis

Theorem 1.

Assume that the area of the ring $C_i$ is $S_i$ , and the intracluster communication radius is $r_c$ , then in the ring $C_i$ , the expected value of the number of cluster heads is

$$\begin{array}{cc}& H_i=\lceil \frac{4·S_i}{3\sqrt{3}·r_c^2}\rceil .\end{array}$$

(4)

Proof.

The wireless sensor network is a network of high-density, and clusters need to cover all the nodes in the entire network. Then, the overlap between clusters exists, and only one cluster head node exists in any cluster. When the overlap among clusters is most, the number of the cluster heads is maximal. The figure of maximal cluster heads is showed in Figure 2.

In Figure 2, the cluster head A is a regular hexagon with the edge length $r_c/\sqrt{3}$ , and the area is $\sqrt{3}·r_c^2/2$ . So, in the ring $C_i$ , the maximal number of the cluster heads is

$$\begin{array}{cc}& H_{\max }=\lceil \frac{2·S_i}{\sqrt{3}·r_c^2}\rceil .\end{array}$$

(5)

On the contrary, when the overlap among clusters is least, the number of the cluster heads is minimal. The figure of minimal cluster heads is showed in Figure 3.

In Figure 3, the cluster head A is a regular hexagon. So in the ring $C_i$ , the minimal number of the cluster heads is

$$\begin{array}{cc}& H_{\min }=\lceil \frac{2·S_i}{3\sqrt{3}·r_c^2}\rceil .\end{array}$$

(6)

Therefore, in the ring $C_i$ , the expected value of the number of cluster heads is

$$\begin{array}{cc}& H_i=\lceil \frac{4·S_i}{3\sqrt{3}·r_c^2}\rceil .\end{array}$$

(7)

Figure 2

Maximal cluster heads.

Figure 3

Minimal cluster heads.

Theorem 2.

Assume that the area of the ring $C_i$ is $S_i$ , the intracluster communication radius is $r_c$ , and the region covered by the cluster is approximately thought as a circle with radius r, then the expected value of the squared distance from the cluster members to the cluster head is

$$\begin{array}{cc}& d_{ch}^2=\frac{9·r_c^2}{8\sqrt{3}·\pi }.\end{array}$$

(8)

Proof.

The expected value of the squared distance from the members to the cluster head (assumed to be at the center of mass of the cluster) is given by

$$\begin{array}{l}{d}_{\text{ch}}^2=\iint (x^2+y^2)\rho (x,y)dx\hspace{0.17em}dy\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=\iint r^2\rho (r,\theta )r\hspace{0.17em}dr\hspace{0.17em}d\theta ,\hfill \end{array}$$

(9)

where ρ is the density of nodes,

$$\begin{array}{cc}& \rho =\frac{4}{3\sqrt{3}·r_c^2}.\end{array}$$

(10)

The cluster radius r can be computed by the following formula:

$$\begin{array}{cc}& \pi ·r^2=\frac{S_i}{H_i}=\frac{3\sqrt{3}·r_c^2}{4},\\ r=\frac{\sqrt{3}·\sqrt[4]{3}·r_c}{2\sqrt{\pi }},\\ d_{\text{ch}}^2=\rho {{\displaystyle \int }}_{\theta =0}^{2\pi }{{\displaystyle \int }}_{r=0}^{\sqrt{3}·\sqrt[4]{3}·r_c/2\sqrt{\pi }}{r}^{3}dr\hspace{0.17em}d\theta .\end{array}$$

(11)

Therefore, the expected value of the squared distance from the cluster members to the cluster head is

$$\begin{array}{cc}& d_{\text{ch}}^2=\frac{3\sqrt{3}·r_c^2}{8\pi }.\end{array}$$

(12)

Theorem 3.

Assume that the area of the ring $C_i$ is $S_i$ and the intracluster communication radius is $r_c$ , then the expected value of the distance between two neighboring cluster heads is

$$\begin{array}{cc}& d_{hh}=\frac{\sqrt{3\sqrt{3}}·r_c}{\sqrt{\pi }}.\end{array}$$

(13)

Proof.

The expected value of the distance between two neighboring cluster heads is given by

$$\begin{array}{cc}& \pi {\left(\frac{d_{\text{hh}}}{2}\right)}^2=\frac{S_i}{H_i}.\end{array}$$

(14)

Therefore,

$$\begin{array}{cc}& d_{\text{hh}}=2\sqrt{\frac{S_i}{H_i·\pi }}=\frac{\sqrt{3\sqrt{3}}·r_c}{\sqrt{\pi }}.\end{array}$$

(15)

Theorem 4.

Assume that the area of ring $C_i$ is $S_i$ , the number of nodes in ring $C_i$ is $N_i$ , the density of nodes is ρ, the distance from the cluster member to the cluster head is $d_{ch}\hspace{0.17em}\hspace{0.17em}(d_{ch}\le d_0)$ , the distance between two neighboring cluster heads is $d_{hh}$ , and the maximal radius of ring $C_i$ is $R_i$ , then the initial energy of each node is as follows.

In ring $C_i$ , $(i\in [2,\dots ,k-1])$ , there will be two conditions for consideration:

• (1)

when $d_{ch}\le d_0$ and $d_{hh}\le d_0$ ,

$$\begin{array}{l}{e}_i=\frac{l{E}_{elec}(2{{\displaystyle \sum }}_{j=i+1}^k{H}_j+2N_i-H_i)}{N_i}\\ +\frac{l{\epsilon }_{fs}{d}_{hh}^2\left({{\displaystyle \sum }}_{j=i+1}^k{H}_j+H_i\right)}{N_i}\\ +\frac{l{\epsilon }_{fs}{d}_{ch}^2\left(N_i-H_i\right)+l{E}_{DA}{N}_i}{N_i};\end{array}$$

(16)

(2)

when $d_{ch}\le d_0$ and $d_{hh}>d_0$ ,

$$\begin{array}{l}{e}_i=\frac{l{E}_{elec}\left(2{{\displaystyle \sum }}_{j=i+1}^k{H}_j+2N_i-H_i\right)}{N_i}\\ +\frac{l{\epsilon }_{mp}{d}_{hh}^4\left({{\displaystyle \sum }}_{j=i+1}^k{H}_j+H_i\right)}{N_i}\\ +\frac{l{\epsilon }_{fs}{d}_{ch}^2\left(N_i-H_i\right)+l{E}_{DA}{N}_i}{N_i},\end{array}$$

(17)

 

where $N_i=S_i\rho =\pi (R_i^2-R_{i-1}^2)\rho$ , $2\le i\le k$ .

Proof.

In ring $C_i\hspace{0.17em}\hspace{0.17em}(i\in [2,\dots ,k-1])$ , the energy of cluster heads is dissipated in the following four aspects: (1) receiving the data from cluster members; (2) fusing the data from cluster members; (3) sending the data in cluster; (4) forwarding the data from other cluster heads.

• (1)

For receiving data from cluster members, the energy dissipation of a cluster head in ring $C_i$ is

$$\begin{array}{cc}& E_r=l{E}_{\text{elec}}\left(\frac{N_i}{H_i}-1\right).\end{array}$$

(18)

(2)

For merging data from cluster members, the energy dissipation of a cluster head in ring $C_i$ is

$$\begin{array}{cc}& E_m=l{E}_{\text{DA}}\frac{N_i}{H_i}.\end{array}$$

(19)

(3)

For sending one frame data, the energy dissipation of a cluster head in ring $C_i$ is

$$\begin{array}{cc}& E_s=l{E}_{\text{elec}}+l{\epsilon }_{\text{fs}}{d}_{\text{hh}}^2.\end{array}$$

(20)

(4)

For collecting one frame data, the total energy dissipation of a cluster head in ring $C_i$ is

$$\begin{array}{l}{E}_{\text{ch}}=E_r+E_m+E_s\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=l{E}_{\text{elec}}\left(\frac{N_i}{H_i}-1\right)+l{E}_{DA}\frac{N_i}{H_i}+l{E}_{\text{elec}}+l{\epsilon }_{fs}{d}_{hh}^2.\hfill \end{array}$$

(21)

(5)

The energy dissipation of a cluster member in ring $C_i$ is

$$\begin{array}{cc}& E_{\text{mem}}=l{E}_{\text{elec}}+l{\epsilon }_{\text{fs}}{d}_{\text{ch}}^2.\end{array}$$

(22)

(6)

For collecting one frame data, in ring $C_i$ , the total energy dissipation in a cluster is

$$\begin{array}{cc}& E_{\text{cluster}}=E_{\text{ch}}+E_{\text{mem}}\left(\frac{N_i}{H_i}-1\right).\end{array}$$

(23)

(7)

In ring $C_i$ , the amount of data that nodes needs to forward is

$$\begin{array}{cc}& S={{\displaystyle \sum }}_{j=i+1}^k{H}_j.\end{array}$$

(24)

(8)

For forwarding data from the outer cluster heads, the energy dissipation of nodes in ring $C_i$ is

$$\begin{array}{cc}& E_f=2l{E}_{\text{elec}}\left({{\displaystyle \sum }}_{j=i+1}^k{H}_j\right)+l{\epsilon }_{\text{fs}}{d}_{\text{hh}}^2\left({{\displaystyle \sum }}_{j=i+1}^k{H}_j\right).\end{array}$$

(25)

(9)

In ring $C_i$ , the total energy dissipation of all nodes is

$$\begin{array}{l}{E}_i=H_i{E}_{\text{cluster}}+E_f\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}=2l{E}_{\text{elec}}{N}_i+l{E}_{\text{DA}}{N}_i+l{\epsilon }_{\text{fs}}{d}_{\text{hh}}^2{H}_i\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+l{\epsilon }_{\text{fs}}{N}_i{d}_{\text{ch}}^2-l{E}_{\text{elec}}{H}_i-l{\epsilon }_{\text{fs}}{H}_i{d}_{\text{ch}}^2\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+2l{E}_{\text{elec}}\left(\sum _{j=i+1}^k{H}_j\right)+l{\epsilon }_{\text{fs}}{d}_{\text{hh}}^2\left(\sum _{j=i+1}^k{H}_j\right).\hfill \end{array}$$

(26)

(10)

When $d_{\text{ch}}\le d_0$ and $d_{\text{hh}}\le d_0$ , in ring $C_i$ , the initial energy of each node is

$$\begin{array}{l}{e}_i=\frac{E_i}{N_i}\hfill \\ \hspace{0.17em}\hspace{0.17em}=\frac{l{E}_{\text{elec}}\left(2{\sum }_{j=i+1}^k{H}_j+2N_i-H_i\right)}{N_i}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\frac{l{\epsilon }_{\text{fs}}{d}_{\text{hh}}^2\left({\sum }_{j=i+1}^k{H}_j+H_i\right)}{N_i}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\frac{l{\epsilon }_{\text{fs}}{d}_{\text{ch}}^2(N_i-H_i)+l{E}_{\text{DA}}{N}_i}{N_i}\hfill \end{array}$$

(27)

(11)

When $d_{\text{ch}}\le d_0$ and $d_{\text{hh}}>d_0$ , the proving process is similar, so we omit it.

5. Clustering Algorithm

After the network deployment, sink broadcasts a Sink_ADV message to start all nodes to work, and each node computes out the approximate distanceto sink by the received signal strength of the Sink_ADV message.

5.1. Cluster Setup

In EHCS, in order to reduce the energy cost for the cluster head competition, a small number of nodes are chosen as candidate cluster heads to compete for final cluster heads by the predefined probability. Each candidate cluster head broadcasts Hello message in radius $r_c$ and collects the Hello messages from the adjacent candidate cluster heads to establish the neighbor information table which includes the node number ID, the residual energy of the node, and the state of the node (candidate node or common node). The node with the largest residual energy is elected as the final cluster head. After the election of the cluster head ends, each cluster head broadcasts Head_ADV message to announce its own cluster head identity. Common nodes join the nearest cluster by the received signal strength of the Head_ADV message and send a Join_Msg message to the cluster head. Finally, each cluster head broadcasts TDMA messages to its cluster member to assign the time slot of the data collection. During the cluster setup, a common node will passively become a cluster head if it is not within the communication range of all cluster heads and cannot join any cluster.

5.2. Formation of Intercluster Forwarding Tree

The cluster head broadcasts a TREE_ADV message which includes the node number ID, the residual energy of the node, and the distance to sink. After collecting the TREE_ADV messages from the adjacent cluster heads, each cluster head establishes the neighbor cluster head information table which includes the number ID of the adjacent cluster head, the residual energy E of the adjacent cluster head, the distance from the adjacent cluster head to sink, and the distance from it to the adjacent cluster head.

In order to setup the intercluster forwarding tree, each cluster head chooses a suitable neighbor cluster head as its parent node. For the cluster head i, if $S(i)$ denotes the set of its neighbor cluster heads, its parent node $p(i)$ is selected by the following equation:

$$\begin{array}{l}p\left(i\right)=\{\begin{array}{ll}\text{Sink},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}d\left(i,\text{Sink}\right)<r_h,\hfill \\ j,\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(28)

$$\begin{array}{l}j=\arg \hspace{0.17em}\min \{\cos t\left(k\right),k\in S\left(i\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\text{and}\hspace{0.17em}\hspace{0.17em}d\left(k,\text{Sink}\right)<d\left(i,\text{Sink}\right)\},\\ \cos t\left(k\right)=w*\frac{d^2(i,k)+d^2(k,\text{Sink})}{d_{\max }}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+(1-w)*\frac{E_{\max }-E\left(k\right)}{E_{\max }},\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}0\le w\le 1,\\ d_{\max }=\max \left\{d^2\left(i,k\right)+d^2\left(k,\text{Sink}\right)\right\},\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}{E}_{\max }=\max \left\{E\left(k\right)\right\},\end{array}$$

(29)

where d denotes the distance, and E is the residual energy of nodes. If sink is in the intercluster communication range, the cluster head directly passes data to sink; otherwise, it chooses the minimum cost node as the parent node from the neighbor cluster heads closer to sink. The cost is computed by the relay distance and the residual energy of nodes to reduce and balance the network energy consumption. After all cluster heads have found a parent node, an intercluster tree rooted at sink is created.

5.3. Data Collection

The cluster members collect the data and send it to the cluster head. Then, the cluster head fuses the intracluster data and transmits the compressed data to its parent node along the forwarding tree. The parent node forwards the received data to sink. After collecting the predetermined number of frames, the network enters into the next round and reclustering.

6. Simulations Results

In order to evaluate the performance of the protocol, EHCS is compared with multihop HEED and LEACH-C via simulations. Simulation parameters are listed in Table 1.

Table 1

Simulation parameters.

Parameter	Value
Radius of network	200 m
Number of nodes N	300
Location of sink	Regional center
$d_0$	87 m
$E_{\text{elec}}$	50 nJ/bit
${\mathrm{\epsilon }}_{\text{fs}}$	10 pJ/bit/m2
${\mathrm{\epsilon }}_{\text{mp}}$	0.0013 pJ/bit/m4
$E_{\text{DA}}$	5 nJ/bit/signal
Packet size l	4000 bits
Frames/round	20
Intracluster communication radius $r_c$	50 m
Intercluster communication radius $r_h$	100 m
Width of the ring w	50 m

Figure 4 shows the node distribution in the three protocols.

Figure 4

Distribution of nodes.

Figure 5 shows the clustering structure in EHCS. “*” denotes the cluster heads, and “∙” denotes the cluster members. Each cluster head chooses a neighbor cluster head closer to sink as its relay node.

Figure 5

Clustering structure in EHCS.

Table 2 shows the death time of nodes in the three protocols and the improvement rate of EHCS over LEACH_C and multihop HEED. If the death time of the first node is used as a comparison standard, EHCS is better than LEACH_C by 287.5% and multihop HEED by 20.8%. So, EHCS can better balance the energy consumption of nodes and prolong the lifetime of the network.

Table 2

Performance comparison among three protocols.

Percent of dead nodes	Death time (rounds)			Improvement rate (%)
	LEACH_C	HEED	EHCS	LEACH_C	HEED
First node	24	77	93	287.5%	20.8%
10%	43	93	100	132.6%	7.5%
20%	53	98	102	92.5%	4.1%
30%	73	102	104	42.5%	2.0%
40%	89	105	106	19.1%	1.0%
50%	98	107	108	10.2%	0.9%

7. Conclusions

Clustering is one of the key technologies of wireless sensor networks and has a significant impact on the network performance, but in clustering networks, many-to-one traffic pattern easily leads to the energy-hole problem because of the unbalanced energy dissipation among sensor nodes. We design an energy-heterogeneous clustering scheme where nodes closer to sink have more initial energy to provide the enough energy for forwarding data from outer cluster heads. Simulation results show that the proposed protocol is better than LEACH_C by 287.5% and multihop HEED by 20.8%, if the death time of the first node is used as a comparison standard.