A Stochastic and Optimized Energy Efficient Clustering Protocol for Wireless Sensor Networks

Abstract

Wireless sensor network consisting of a large number of small sensors of low-power transceiver is effective for gathering data in a variety of environments. Since the network is built with low-cost sensor nodes of limited battery power, it is a challenging task to design an efficient routing scheme maximizing the network lifetime. In this paper, we propose a new clustering protocol reducing the energy taken for routing, and thus extending the network lifetime. The proposed scheme is based on a newly developed model of optimal number of clusters in the network with which the energy consumption can be minimized. It also includes a method of cluster-head rotation inside each cluster, which avoids the clustering operation during normal operation and evenly distributes the load among the nodes. The performance of the proposed scheme is compared with the clustering-based routing protocols, Low-Energy Adaptive Clustering Hierarchy (LEACH), LEACH-Centralized (LEACH-C), and Adaptive and Energy Efficient Clustering (AEEC) algorithm. Simulation results show that it significantly reduces energy consumption and improves network lifetime. It is thus expected to be effective for large-scale semantic sensor web.

1. Introduction

Recently, low-cost and low-power wireless sensor nodes have been applied to various fields [1]. Wireless sensor network (WSN) consists of tiny sensor nodes forming an ad hoc distributed sensing and data propagation network while collecting the information on the physical environment [2, 3]. It is widely used in both the military and civilian applications such as target tracking, surveillance, and security management [4–7]. Typically, a sensor node is a tiny device containing four basic components [2, 8–13]: sensing subsystem for data acquisition from the physical surrounding environment, processing subsystem for local data processing and storage, wireless communication subsystem for data transmission, and power supply subsystem built with a battery of limited energy budget. In addition to them, additional subsystems might also be added according to the target application. With its capabilities for monitoring and control, WSN has been deployed in numerous areas. Such network can provide a fine global picture of the target through the collaboration of many sensors each providing a local view.

Since sensor nodes have limited power supply and cannot be easily recharged or replaced when the battery power is depleted, the operation of WSN needs to be energy efficient. If some sensor nodes have no more energy, the WSN may not allow reliable operation due to partition of the network. Limited energy in each node affects the lifetime of the entire network, and as a result energy efficiency has been a critical design issue for the protocols and algorithms of WSN. Various network architectures and protocols for sensor network have been developed for which energy efficiency is primary goal [9, 14–18].

Many schemes have been proposed to efficiently prolong the lifetime of WSN. Among them, the clustering approach has been recognized as one of effective candidates [19–21]. Here the sensor nodes are grouped into clusters, and the noncluster heads send the data to their cluster head. The cluster head aggregates the received data and transmits them to the base station (BS). The most common approach employed in the representative clustering schemes such as LEACH and AEEC is probabilistic clustering based on randomized cluster-head rotation for evenly distributing the energy consumption among nodes in each cluster [22, 23]. In these schemes cluster formation and cluster-head selection are done in the setup phase. With such random fashion of clustering, every round of the operation has a different number of clusters. Here how to select the cluster head among the nodes can greatly affect the network lifetime. Among various factors causing energy consumption during clustering, wireless data transmission is the most critical one. Because it increases in proportion to the distance between the communicating nodes, the distance of cluster head to the BS is a significant factor. For example, in one-hop cluster communication, the cluster heads farther from the BS will die earlier than the nearer cluster heads. Therefore, deciding the optimal number of clusters is an important problem in the clustering scheme for maximizing the network lifetime. Also, in the existing clustering, clusters are reconstructed every round for load distribution among the cluster head and member nodes in the cluster. During reclustering, however, large energy is consumed. Therefore, reducing the frequency of reclustering is another critical issue with respect to the lifetime of WSN.

In this paper, we propose an energy efficient clustering protocol which can reduce energy consumption and prolong the lifetime of WSN. In the proposed scheme, the clusters are formed based on a newly developed stochastic model of the number of cluster heads allowing minimum energy consumption of the network. The proposed scheme also includes a method of cluster-head rotation in each cluster, with which energy consumption caused by unnecessary reclustering is avoided and the loads are evenly distributed among the nodes. Here rotation of cluster head is decided according to the location information of the sensor nodes, and reclustering occurs only when the topology of network is changed. Simulation results show that the proposed scheme effectively lets energy consumption of the network be balanced and achieves a remarkable improvement of network lifetime compared to the existing cluster-based schemes such as LEACH, LEACH-C, and AEEC.

The remainder of the paper is organized as follows. The following section reviews the related work reported in the literature. Section 3 presents the system model including the energy model, and Section 4 introduces the proposed scheme. In Section 5, energy efficiency of the proposed scheme is analyzed. Simulation results of the proposed scheme and the existing schemes are compared and discussed in Section 6. Finally, Section 7 concludes the paper and outlines future research direction.

2. Related Work

Various routing protocols for WSN have been proposed in the literature [19, 20]. Among them, the clustering approach allows good scalability for relatively large size networks and balances the loads among the nodes and thus increases network lifetime [21, 24, 25].

Low-Energy Adaptive Clustering Hierarchy (LEACH) [22] is one of representative clustering schemes. In LEACH sensors are organized into clusters and one node in each cluster acting as cluster head takes the responsibility of collection, aggregation, and transmission of data to the BS. The operation is divided into rounds, where a round begins with setup phase followed by steady state phase. During the setup phase each node decides by itself whether it becomes the cluster head or not. After that, the cluster head broadcasts an advertisement message to the rest of the nodes. Depending on the received signal strengths, each node decides the cluster head to which it will belong for that round. Each cluster head then creates and broadcasts a TDMA schedule for all the member nodes in its cluster. During the steady state phase, the member nodes start sensing and transmitting data to the cluster heads according to the TDMA schedule, and the fused information by the cluster head is sent to the BS. At the end of a round, a new set of nodes becomes cluster heads for the subsequent round. As the cluster head heavily drains the energy, LEACH facilitates randomized rotation of cluster head to evenly distribute the load among the nodes.

In LEACH-C [26], cluster formation is decided by BS. In the setup phase, it receives the messages containing the location data and remaining energy of each sensor node. It then selects the nodes having larger energy than the average energy of all the nodes as candidate of cluster head. Among them, the nodes of shorter distance to the neighboring nodes than other candidates are selected as cluster heads using the simulated annealing algorithm [27]. After that, the BS broadcasts a message containing the IDs of the cluster heads for that round.

Energy-Driven Adaptive Clustering Hierarchy (EDACH) [28] increases the lifetime and reliability of sensor network even in the presence of faults at the cluster heads. This is achieved by selecting a proxy node which assumes the role of the current cluster head during one round of operation. The selection is based on the consensus of healthy cluster heads detecting and handling the faults in faulty cluster head. It allows improvement in the stability of the network and reduces the overhead of reclustering. Power-Efficient Gathering in Sensor Information Systems (PEGASIS) [29] is a chain-based protocol trying to extend the network lifetime by letting the nodes communicate with only their closest neighbors, and the nodes take turns to communicate with the BS. Once all the nodes have assumed the role of communication with the BS, a new round begins. This allows energy consumption to spread uniformly over all nodes, while the communication between only adjacent nodes allows small energy consumption. To locate the closest neighbor node for each node, each node uses signal strength to measure the distance to the neighboring nodes and then adjusts the signal strength so that only one node can be heard. Here the chain construction is performed in a greedy fashion.

Adaptive and Energy Efficient Clustering algorithm (AEEC) [23] is another version of LEACH. It makes the nodes of more residual energy have a higher chance to be selected as cluster head. AEEC involves three main phases: the initial phase, the clustering phase, and the data transmission phase. The initial phase is performed only once at the beginning of the network operation. Similar to LEACH, its operation is divided into rounds, where each round consists of the clustering phase and data transmission phase.

3. The System and Energy Model

We first discuss the system and energy model used in the proposed scheme.

3.1. The System Model

The WSN consists of a number of sensor nodes distributed randomly in the target region, where the sensor nodes are homogeneous and energy-constrained. The sensor nodes form clusters periodically and transmit data with enough power to reach the BS. The following are the assumptions employed with the WSN.

• (i)

All nodes are randomly distributed in a two-dimensional plane according to a homogeneous spatial Poisson process with λ intensity.

(ii)

All nodes are homogeneous and have the same capability, and each node is assigned a unique identifier.

(iii)

All nodes are started with the same initial energy.

(iv)

All sensors transmit data with the same power level and hence have the same radio range, r.

(v)

All nodes can use power control to vary the amount of transmission power depending on the distance to the receiver. Each node is able to reach the BS directly.

(vi)

The BS has no energy constraint and is located at the center of target area.

(vii)

Data are fused at the cluster heads to reduce the number of messages.

(viii)

Links are symmetric. A node can compute approximate distance to another node based on the received signal strength.

3.2. The Energy Model of a Sensor

The commonly adopted radio model [22, 26] is used, which is the first order radio model. To estimate the energy consumption of a node, both the free space ( $d^2$ power loss) model and multipath fading ( $d^4$ power loss) channel model are used, which are based on the distance between the transmitter and receiver. For relatively short distances, the propagation loss is assumed to be inversely proportional to $d^2$ , whereas, for longer distances, it is $d^4$ . The transmission power must be controlled to compensate this loss and thus ensure acceptable signal power at the receiver. To transmit an l-bit packet for a distance d, the radio expends the following energy:

$$\begin{array}{ll}{E}_{Tx}\left(l,d\right)& =E_{Tx\text{-elec}}\left(l\right)+E_{Tx\text{-amp}}\left(l,d\right)\\ & =\{\begin{array}{ll}l{E}_{\text{elec}}+l{\epsilon }_{fs}{d}^{\mathrm{2}},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}d<d_o\hfill \\ l{E}_{\text{elec}}+l{\epsilon }_{mp}{d}^{\mathrm{4}},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}d\ge d_o.\hfill \end{array}\end{array}$$

(1)

When a node receives l-bit data, the energy it consumes is

$$\begin{array}{cc}& E_{Rx}\left(l\right)=E_{Rx\text{-elec}}\left(l\right)=l{E}_{\text{elec}}.\end{array}$$

(2)

Here $E_{\text{elec}}$ is the energy cost for transmitting or receiving one-bit data and ${\epsilon }_{fs}$ is the amplifier coefficient. $d^2$ energy loss model is used for the channel attenuation. For simplicity of calculation, the transmission range of each node is assumed to be the same on one condition that the transmission range should cover all the neighbors in the network. For the experiments presented in this paper, the values given in [26] are adopted: $E_{\text{elec}}=50\hspace{0.17em}\text{nJ}/\text{bit}$ , ${\epsilon }_{fs}=\mathrm{10}\hspace{0.17em}\text{pJ}/\text{bit}/{\text{m}}^2$ , and ${\epsilon }_{mp}=0.0013\hspace{0.17em}\text{pJ}/\text{bit}/{\text{m}}^4$ . A sensor node consumes 5 nJ/bit/signal for data aggregation [22, 26]. Also, all data packets are assumed to contain the same number of bits.

4. The Proposed Scheme

In this section, the proposed scheme is presented which employs a self-organizing, adaptive clustering approach. It is based on the newly developed model of optimal cluster-head probability and the scheme of cluster-head rotation in each cluster. It distributes the energy load evenly among the sensor nodes in the network and as a result improves the network lifetime.

The operation of the proposed scheme is divided into two phases: setup phase and data collection/transmission phase. The setup phase is for cluster-head selection and cluster formation using homogeneous spatial Poisson process, where the number of clusters is decided such that energy consumption of the network becomes minimal. In the next phase data collection and transmission occur, along with the change of cluster head. During this phase, the sensor nodes collect data and transmit them to the cluster heads according to the schedule, which send them to the BS. After that, the cluster heads are changed if the network topology has not been changed. Otherwise, a new setup phase is started for reclustering.

4.1. Decision on the Probability of Cluster Head

Energy consumption depends on the distance between the transmitter and receiver, that is, the distance between the sensors. Assume that a sensor becomes a cluster head with probability p. Here the cluster heads and the noncluster heads are distributed as independent homogeneous spatial Poisson processes of intensity ${\lambda }_1=p\lambda$ and ${\lambda }_0=(1-p)\lambda$ , respectively. Each noncluster head joins the cluster of the closest cluster head to form a Voronoi tessellation [30]. The plane is divided into zones called the Voronoi cells, where each cell corresponds to a Poisson process with intensity ${\lambda }_{\mathrm{1}}$ , called nucleus of Voronoi cells. Let $N_v$ be the random variable denoting the number of noncluster heads in each Voronoi cell, and let N be the total number of sensors in a bounded region. If $L_v$ is the total length of all segments connecting the noncluster heads to the cluster head in a Voronoi cell, then

$$\begin{array}{cc}& E\left[N_v\mid N=n\right]=\frac{{\lambda }_{\mathrm{0}}}{{\lambda }_{\mathrm{1}}},\hspace{1em}\hspace{1em}E\left[L_v\mid N=n\right]=\frac{{\lambda }_{\mathrm{0}}}{\mathrm{2}{\lambda }_{\mathrm{1}}^{\mathrm{3}/\mathrm{2}}}.\end{array}$$

(3)

Note that these expectations depend only on intensities ${\lambda }_0$ and ${\lambda }_1$ in a Voronoi cell. Using the expectations of the lengths above, an optimal value p minimizing the total energy spent in the network is found.

For WSNs of a large number of energy constrained sensors, it is important to firstly group the sensors into clusters to minimize the energy taken for the communication between the nodes. Note that energy consumption is directly proportional to the distance between the cluster heads and noncluster heads in a cluster and the distance between the cluster head and BS. We thus focus on the distances for minimizing the energy spent in the network. Note that the earlier model of (3) depends only on the intensity of the sensor distribution. In this paper, however, the expected distance between the sensor and cluster head is modeled by including p and the number of sensors, N, and the size of the region for obtaining more accurate estimation on the number of clusters. The number is decided by the probability, p, which minimizes the energy used to exchange data. We next present the proposed model.

In WSN the expected distance between the cluster head and the BS and that between the sensor node and the cluster head depend on the number of sensor nodes, number of clusters, size of the region, and location of BS. The expected distance between a node and its cluster head in a cluster decreases while that between a cluster head and the BS increases as the number of clusters increases in a bounded region. An opposite phenomenon is observed when the number of clusters decreases. Therefore, an optimal value of p in terms of energy efficiency needs to be decided by properly taking account of the tradeoff between sensor node to cluster head and cluster head to BS communication overhead.

Let S denote a bounded region of a plane and let $X(S)$ do the number of sensor nodes contained in S. Then $X(S)$ is a homogeneous spatial Poisson process if it distributes the Poisson postulates, yielding a probability distribution:

$$\begin{array}{cc}& P\left\{X\left(S\right)=n\right\}=\frac{\left[\lambda A{\left(S\right)}^n{e}^{-\lambda A\left(S\right)}\right]}{n!},\hspace{1em}n=\mathrm{0,1},\mathrm{2},\dots .\end{array}$$

(4)

Here λ is a positive constant called the intensity parameter of the process and $A(S)$ represents the area of region S.

If region S is a square of side length, M, then the number of sensors in it follows a Poisson distribution with a mean of $\lambda A(S)$ , where $A(S)$ is $M^2$ . Assume that there exist N sensors in the region for a particular realization of the process. If the probability of becoming a cluster head is p, then $Np$ sensor nodes will become cluster heads on average. Let $D_B(x,y)$ be a random variable denoting the distance between a sensor located at $(x,y)$ and the BS. Without loss of generality, we assume that the BS is located at the center of the square region (i.e., the origin coordinate). Then, the expected distance from the BS to the sensors is given by

$$\begin{array}{l}E\left[D_B\left(x,y\right)\mid X\left(S\right)=N\right]\\ \hspace{1em}={{\displaystyle \int }}_{-M/\mathrm{2}}^{M/\mathrm{2}}{{\displaystyle \int }}_{-M/\mathrm{2}}^{M/\mathrm{2}}\sqrt{x^{\mathrm{2}}+y^{\mathrm{2}}}\frac{\mathrm{1}}{M^{\mathrm{2}}}dx\hspace{0.17em}dy=\mathrm{0.3825}M.\end{array}$$

(5)

Since there exist $Np$ cluster heads on average and the location of a cluster head is independent of those of other cluster heads, the total length of the segments from all the cluster heads to the BS is 0.3825 $NpM$ .

Since a sensor node becomes a cluster head with a probability p, we expect that the cluster head and other sensor nodes are distributed in a cluster as an independent homogeneous spatial Poisson process. Each sensor node joins the cluster of the closest cluster head to form a cluster. Let $X(C)$ be the random variable denoting the number of sensor nodes in a cluster except the cluster head, where C is the area of a cluster. Let $D_C$ be the distance between a sensor node and the cluster head in a cluster. Then, according to the results of [31], the expected number of noncluster heads in a cluster and the expected distance from a sensor node to the cluster head (assumed to be at the center of mass of the cluster) in a cluster are given by

$$\begin{array}{ll}& E\left[X\left(C\right)\mid X\left(S\right)=N\right]=\frac{\mathrm{1}}{p}-\mathrm{1},\end{array}$$

(6)

$$\begin{array}{l}E\left[D_C\mid X\left(S\right)=N\right]={\iint }_C\sqrt{x^{\mathrm{2}}+y^{\mathrm{2}}}k(x,y)dA\left(C\right)\\ ={{\displaystyle \int }}_{\mathrm{0}}^{\mathrm{2}\pi }{{\displaystyle \int }}_{\mathrm{0}}^{M/\sqrt{Np\pi }}{r}^{\mathrm{2}}\frac{Np}{M^{\mathrm{2}}}dr\hspace{0.17em}d\theta =\frac{\mathrm{2}M}{\mathrm{3}\sqrt{Np\pi }},\end{array}$$

(7)

respectively. Here, region C is a circle of radius M/ $\sqrt{Np\pi }$ . The density of sensor nodes of the cluster, $k(x,y)$ , is uniform, and it is approximately $M^2/Np$ .

Let $E_C$ be the expected total energy used by the sensor nodes in a cluster to transmit one unit of data to their respective cluster head. Since there are $Np$ clusters, the expected value of $E_C$ conditioned on $X(S)=N$ is given by

$$\begin{array}{l}E\left[E_C\mid X\left(S\right)=N\right]=N\left(\mathrm{1}-p\right)·\frac{E\left[E_C\mid X\left(S\right)=N\right]}{r}\\ =N^{\mathrm{1}/\mathrm{2}}·\frac{2M}{\mathrm{3}r\sqrt{\pi }}\frac{\mathrm{1}-p}{\sqrt{p}}.\end{array}$$

(8)

If the total energy spent by the cluster heads to transmit the aggregated information to the BS is denoted by $E_B$ , then

$$\begin{array}{l}E\left[E_B\mid X\left(S\right)=N\right]\\ \hspace{1em}\hspace{1em}=Np·\frac{E\left[D_B\mid X\left(S\right)=N\right]}{r}=\frac{\mathrm{0.3825}NpM}{r}.\end{array}$$

(9)

Let $E_T$ be the total energy consumption with the condition of $X(S)=N$ in the network. Then

$$\begin{array}{l}E\left[E_T\mid X\left(S\right)=N\right]\\ \hspace{1em}=E\left[E_C\mid X\left(S\right)=N\right]+E\left[E_B\mid X\left(S\right)=N\right].\end{array}$$

(10)

Taking the expectation of (10), the total energy consumption of the network is obtained:

$$\begin{array}{l}E\left[E_T\right]=E\left[E\left[E_T\mid X\left(S\right)=N\right]\right]\\ =E\left[X{\left(S\right)}^{\mathrm{1}/\mathrm{2}}\right]·\frac{\mathrm{2}M}{\mathrm{3}r\sqrt{\pi }}\frac{\mathrm{1}-p}{\sqrt{p}}\\ +E\left[X\left(S\right)\right]·\frac{\mathrm{0.3825}pM}{r},\end{array}$$

(11)

where $E[·]$ is expectation of a homogeneous Poisson process.

$E[E_T]$ will have a minimum value for a value of p, which is obtained by the first derivative of (11):

$$\begin{array}{cc}& \mathrm{2}{c}_{\mathrm{2}}{p}^{\mathrm{3}/\mathrm{2}}-c_{\mathrm{1}}(p+\mathrm{1})=\mathrm{0},\end{array}$$

(12)

where $c_1=2M·E[{(X(S))}^{1/2}]/\mathrm{3}\sqrt{\pi }$ and $c_2=0.3825M·E[X(S)]$ .

Equation (12) has three roots, two of which are imaginary. The second derivative of (11) is positive and log concave for the only real root of (12), and hence the real root minimizes the total energy consumption, $E[E_T]$ .

The only real root of (12) is as follows:

$$\begin{array}{l}p=\frac{0.0833c_1^2}{c_2^2}\\ \hspace{1em}+(\phantom{{{+83.1384c_1^2\sqrt{c_1^2{c}_2^6+27c_2^8})}^{\mathrm{1}/\mathrm{3}})}^{-1}}\left(\mathrm{0.1050}\left(c_1^4+24c_1^2{c}_2^2\right)\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\times (\phantom{{+83.1384c_1^2\sqrt{c_1^2{c}_2^6+27c_2^8})}^{\mathrm{1}/\mathrm{3}}}{c}_2^2(\phantom{\sqrt{c_1^2{c}_2^6+27c_2^8}}2c_1^6+72c_1^4{c}_2^2+432c_1^2{c}_2^4\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{{83.1384c_1^2\sqrt{c_1^2{c}_2^6+27c_2^8})}^{\mathrm{1}/\mathrm{3}})}^{-1})\\ \hspace{1em}+\frac{\mathrm{0.0661}}{c_2^2}\\ \hspace{1em}+(\phantom{\sqrt{c_1^2{c}_2^6+27c_2^8}}2c_1^6+72c_1^4{c}_2^2+432c_1^2{c}_2^4\\ \hspace{1em}\hspace{1em}\hspace{1em}+{83.1384c_1^2\sqrt{c_1^2{c}_2^6+27c_2^8})}^{1/3}.\end{array}$$

(13)

The optimal cluster-head probability, p, is obtained for the proposed scheme. Next, the cluster heads are selected using p, and the clusters are formed.

4.2. Cluster Formation

In the proposed scheme, a proportion of sensor nodes stochastically elect themselves as cluster heads. For this, each node determines a random number between 0 and 1. If the number is smaller than a threshold $T_{\text{new}}(n)$ , the node becomes a cluster head for that round. The threshold of node_n, $T_{\text{new}}(n)$ , is set as follows:

$$\begin{array}{cc}& T_{\text{new}}\left(n\right)=\frac{p}{1-p\times \left(R\mathrm{mod}\left(1/p\right)\right)},\hspace{1em}\forall n\in G\\ T_{\text{new}}\left(n\right)=\mathrm{0},\hspace{1em}\forall n\notin G\end{array}$$

(14)

with p as the proposed optimal cluster-head probability found in (13), R as the number of the first round, and G as the set of nodes. This algorithm ensures that every node becomes a cluster head exactly once within 1/p rounds [22]. Here the method for cluster-head selection is similar to LEACH. Note, however, that the proposed scheme employs different p. The node electing itself as a cluster head broadcasts an advertisement (ADV) message using a nonpersistent carrier-sense multiple access (CSMA) MAC protocol [32, 33] to the rest of the nodes. This short message contains the node's ID and a header distinguishing it as an announcement message. The message must be broadcast with enough power to reach all the nodes in the network. The ADV messages ensure the elimination of collisions when CSMA is used, since there is no hidden terminal problem [26, 34]. When a node receives an advertisement message from the cluster heads, it sends the join-request (Join_REQ) message to the cluster head which it chooses as its cluster head based on the received signal power. This message using nonpersistent CSMA MAC protocol is again a short message, including the node's ID, the cluster head's ID, and the node's location information. The proposed scheme adopts the scheme of cluster-head rotation in each cluster. For this, the Join_REQ message is stored in the cluster head. Each cluster head identifies its member nodes through the received Join_REQ messages.

After the clusters are formed, the cluster head decides the order of cluster-head rotation in each cluster and creates the TDMA schedule like LEACH. The TDMA schedule ensures that there are no collisions among data messages and also allows the radio components of noncluster head node to be turned off at all times except during their transmission time to minimize energy consumption.

In the proposed scheme, the schedule includes the order of cluster-head rotation and the transmission schedule of the member nodes in the cluster. After the schedule of cluster-head rotation is received by all the nodes in the cluster, the cluster-head selection and cluster formation phase is complete, and the data collection and transmission phase begins.

4.3. Rotation of Cluster Head

In the existing clustering schemes, clusters are reconstructed every round for load distribution among the cluster head and member nodes in the cluster. Thus, for T rounds, the cluster setup phase takes place as many as T times. During these phases, large energy is consumed. To reduce energy consumption during the cluster setup phase, the proposed scheme does not change the clusters until the network topology is changed due to dead node or link once the clusters are formed. The timeline of LEACH and the proposed scheme are shown in Figure 1. Figure 1(a) shows that the setup process is repeated with LEACH, while Figure 1(b) of the proposed scheme does not. In the proposed scheme, the cluster heads transmit a head-replacement (Head_REP) message in the last frame of each round to inform cluster-head change to the member nodes in the cluster. When a member node receives a Head_REP message from the cluster head, it sends the confirmation (CONF) message to the cluster head for changing the cluster head. After that, the cluster head is changed by the order of cluster-head rotation without reclustering and the next round begins. The cluster head compares the node number of cluster-head rotation schedule with the node number of CONF message received from the member nodes for handling abnormal situation (e.g., dead node). If the two numbers are not the same, the cluster head regards it as an occurrence of dead node. Then it broadcasts a reclustering (Re_beg) message to all the cluster heads in the network. When the cluster heads receive the Re_beg message, the setup phase is started for new cluster-head selection and cluster formation. Here, the messages for cluster-head change and reclustering are very short, and thus transmission of them consumes small amount of energy.

Figure 1

The timeline of LEACH and the proposed scheme.

The setup phase of the proposed scheme is similar to LEACH. Here clusters are formed and cluster heads are elected. After the cluster formation, the order of cluster-head rotation in each cluster is decided by the cluster head based on the location information of Join_REQ message received from the member nodes.

For deciding the order of cluster-head rotation, assume that the coordinate of the cluster head is $(x,y)$ and those of the n member nodes in the cluster are $(x_i,y_i)$ , $i=1,2,\dots$ ,n. Then, the distance between each member node and the cluster head can be expressed as follows:

$$\begin{array}{cc}& \sqrt{{\left(x-x_{\mathrm{1}}\right)}^{\mathrm{2}}+{\left(y-y_{\mathrm{1}}\right)}^{\mathrm{2}}}=d_{\mathrm{1}},\\ \sqrt{{\left(x-x_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(y-y_{\mathrm{2}}\right)}^{\mathrm{2}}}=d_2,\\ ⋮\\ \sqrt{{\left(x-x_n\right)}^{\mathrm{2}}+{\left(y-y_n\right)}^{\mathrm{2}}}=d_n.\end{array}$$

(15)

After that, the cluster head sorts the distances, $D_{\text{set}}=\{d_1,d_2,d_3,\dots ,d_n\}$ , in ascending order. The node nearest to the cluster head will be in the first in the list, and thus it will become the next cluster head. After the cluster heads create the list of cluster-head rotation, they broadcast it to the member nodes in the cluster, which includes {node_id, rotation_number} of all member nodes. Here, node_id is a unique identification of each node, and rotation_number is the order of the node to become the cluster head. This approach is for reducing the overhead of reclustering and supporting high energy efficiency.

4.4. Data Collection and Transmission

After the setup phase is over, the data collection and transmission phase begins. At the beginning of this phase, every node collects data and sends them to the cluster head at most once per frame during its allocated transmission slot indicated in the TDMA schedule. To avoid intercluster interference, each node communicates using different direct-sequence spread spectrum (DS-SS) as in LEACH. When the data are received from all member nodes in the cluster, each cluster head aggregates the data and transmits them to the BS using a fixed spreading code and CSMA.

The data transmission from the member nodes uses minimum amount of energy by referring to the strength of the received cluster-head advertisement signal and the assumption of symmetrical radio channel. The radios of the member nodes are turned off until their allocated transmission time to save the energy. Since all the nodes have data to send to the cluster head while the total bandwidth is fixed, the TDMA schedule is used for efficient use of bandwidth and low latency in addition to energy efficiency. The cluster head must keep its receiver on to receive all the data from the nodes in the cluster. The data fusion in the cluster head might be a simple averaging of the data or complex data processing. After the fusion, the data are sent to the BS. When the data transmissions from all cluster heads to the BS are finished, the data collection and transmission phase of the current round is completed. After that, the next round starts the data collection and transmission phase without reclustering but after the rotation of cluster head.

5. Analysis of Energy Efficiency

In this section, energy efficiency of the proposed scheme is analyzed. First, the energy dissipated during setup phase is evaluated. Then the energy used during data transmission phase is analyzed.

5.1. Energy Cost of Setup Phase

In the setup phase the cluster head handles two transmission processes, one reception process, TDMA scheduling process for allocating the time slot of each member node, and scheduling process for cluster-head rotation. The two transmission processes are for sending ADV message and the TDMA schedule, respectively, and the reception process is for accepting Join_REQ message generated as a response to the ADV message. Meanwhile, the noncluster head node handles one transmission process and two reception processes. The transmission process is for sending Join_REQ message, while the reception processes are for receiving ADV message and TDMA schedule from the cluster head.

To model the energy consumed during the setup phase, (1) representing the energy consumed by a sensor node for transmission and (2) for reception are used. The amount of energy consumed by cluster head ( $E_{\text{setup-ch}}$ ) and noncluster node ( $E_{\text{setup-non-ch}}$ ) is derived from (16) and (17), respectively:

$$\begin{array}{l}{E}_{\text{setup-ch}}=\left(E_{Rx}\left(l\right)\times \left(\frac{N}{k}-\mathrm{1}\right)\right)\\ +E_{\text{schedule}}+E_{\text{CH-rotation}}+\left(E_{Tx}\left(l,d\right)\times 2\right),\end{array}$$

(16)

$$\begin{array}{ll}& E_{\text{setup-non-ch}}=E_{Tx}\left(l,d\right)+\left(E_{Rx}\left(l\right)\times 2\right).\end{array}$$

(17)

Here $E_{\text{schedule}}$ is the amount of energy consumed for TDMA scheduling in the cluster head, while $E_{\text{CH-rotation}}$ is for creating the schedule of cluster-head rotation. k is the number of clusters in network. One of the two transmissions accounted in (16) is long-distance transmission for sending ADV message to noncluster head nodes in the network, and the other one is short-distance transmission for sending the TDMA schedule to the nodes in the cluster. Therefore, (16) can be expressed by (18) based on (1) and (2). Equation (17) represents the short-distance transmission to the cluster head, and it can be expressed as

$$\begin{array}{l}{E}_{\text{setup-ch}}\\ \hspace{1em}=l{E}_{\text{elec}}\left(\frac{N}{k}-1\right)+E_{\text{schedule}}+E_{\text{CH-rotation}}\\ \hspace{1em}\hspace{1em}+\left(I{E}_{\text{elec}}+l{\epsilon }_{mp}{d}^4\right)+\left(I{E}_{\text{elec}}+l{\epsilon }_{fs}{d}^2\right),\end{array}$$

(18)

$$\begin{array}{ll}& E_{\text{setup-non-ch}}=\left(l{E}_{\text{elec}}+l{\epsilon }_{fs}{d}^2\right)+\mathrm{2}l{E}_{\text{elec}}.\end{array}$$

(19)

The first term of (19), $l{E}_{\text{elec}}+l{\epsilon }_{fs}{d}^2$ , can be expressed as (20) by short-distance transmission between the member node and cluster head:

$$\begin{array}{cc}& l{E}_{\text{elec}}+l{\epsilon }_{fs}{d}^2=\left(l{E}_{\text{elec}}+l{\epsilon }_{fs}\frac{M^2}{2\pi k}\right).\end{array}$$

(20)

Therefore, (18) and (19) can be expressed by (21), respectively:

$$\begin{array}{l}{E}_{\text{setup-ch}}=l{E}_{\text{elec}}\left(\frac{N}{k}-\mathrm{1}\right)+E_{\text{schedule}}+E_{\text{CH-rotation}}\\ +\left(I{E}_{\text{elec}}+l{\epsilon }_{mp}{d}^4\right)+I{E}_{\text{elec}}+l{\epsilon }_{fs}\frac{M^2}{2\pi k}.\\ E_{\text{setup-non-ch}}=\left(l{E}_{\text{elec}}+l{\epsilon }_{fs}\frac{M^{\mathrm{2}}}{\mathrm{2}\pi k}\right)+\mathrm{2}l{E}_{\text{elec}}.\end{array}$$

(21)

The amount of energy consumption in a single cluster during the setup phase, represented by (21), is as follows:

$$\begin{array}{l}{E}_{\text{setup-cluster}}=E_{\text{setup-ch}}+\left(\frac{N}{k}-1\right)E_{\text{setup-non-ch}}\\ =E_{\text{schedule}}+E_{\text{CH-rotation}}\\ \hspace{1em}+l(\phantom{\left(E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\right)}{E}_{\text{elec}}\left(\frac{N}{k}-1\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(E_{\text{elec}}+{\epsilon }_{mp}{d}^4\right)+E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\\ \hspace{1em}\hspace{1em}\hspace{1em}+\left(E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\right)+2E_{\text{elec}}).\end{array}$$

(22)

Therefore, as in (23), the total energy consumption of all the sensor nodes during the setup phase in a round can be obtained by multiplying (22), which expresses the amount of energy consumption in a single cluster, by the number of clusters, k:

$$\begin{array}{l}{E}_{\text{setup}}=k\left(E_{\text{setup-ch}}+\left(\frac{N}{k}-1\right)E_{\text{setup-non-ch}}\right)\\ =l(\phantom{\left({\epsilon }_{\text{mp}}{d}^4+\left(E_{\text{elec}}+{\epsilon }_{\text{fs}}\frac{M^2}{2\pi k}\right)\right)}N\left(4E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}+k\left({\epsilon }_{mp}{d}^4+\left(E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\right)\right))\\ \hspace{1em}+E_{\text{schedule}}+E_{\text{CH-rotation}}.\end{array}$$

(23)

5.2. Energy Cost of Data Transmission Phase

The data collection and transmission phase of the proposed scheme is identical to that of LEACH and LEACH-C. In this phase each cluster head dissipates energy for receiving signals from the nodes, aggregating the data, transmitting the aggregated data to the BS, transmitting Head_REP message to inform the member nodes in the cluster of change of the cluster head for next round, and receiving CONF message from the member nodes for the confirmation of cluster-head change. Each member node needs to transmit its data to the cluster head once during a round, receive Head_REP message for cluster-head change, and transmit CONF message to the cluster head. Therefore, the energy dissipated in the cluster head ( $E_{\text{CH}}$ ) and noncluster head ( $E_{\text{non-CH}}$ ) during one round can be expressed as (24) and (25), respectively:

$$\begin{array}{l}{E}_{\text{CH}}=l{E}_{\text{elec}}\left(\frac{N}{k}-1\right)\\ \hspace{1em}+t\left(E_{\text{elec}}+{\epsilon }_{fs}{d}^{\mathrm{2}}\right)+t{E}_{\text{elec}}\left(\frac{N}{k}-1\right)\\ \hspace{1em}+l{E}_{DA}\frac{N}{k}+\left(l{E}_{\text{elec}}+l{\epsilon }_{mp}{d}_{\text{toBS}}^4\right)\end{array}$$

(24)

$$\begin{array}{l}{E}_{\text{non-CH}}\\ \hspace{1em}=l\left(E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\right)+t{E}_{\text{elec}}+t\left(E_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}\right),\end{array}$$

(25)

where l is the number of bits in each message, N is the number of nodes, $d_{\text{toBS}}$ is the distance from the cluster head to the BS, and t is the number of bits of Head_REP message used for the short-distance transmission inside a cluster. Here complete data aggregation in each sensor node is assumed, which consumes $E_{DA}$ (nJ/bit/signal). It is set to be 5 nJ/bit/signal [22, 26]. Using (24) and (25), the energy dissipated in a cluster is

$$\begin{array}{l}{E}_{\text{cluster}}\\ \hspace{1em}=E_{\text{CH}}+\left(\frac{N}{k}-1\right)E_{\text{non-CH}}\approx E_{\text{CH}}+\left(\frac{N}{K}\right)E_{\text{non-CH}},\\ E_{\text{total}}\\ \hspace{1em}=l\left(N{E}_{\text{elec}}+N{E}_{DA}+k{\epsilon }_{mp}{d}_{\text{toBS}}^4+N{E}_{\text{elec}}+{\epsilon }_{fs}\frac{M^2}{2\pi k}N\right)\\ \hspace{1em}\hspace{1em}+t\left(N{E}_{\text{elec}}\right)+t\left(3E_{\text{elec}}+2{\epsilon }_{fs}\frac{M^2}{2\pi k}\right).\end{array}$$

(26)

6. Performance Evaluation

In this section, the performance of the proposed scheme is evaluated via computer simulation. Here OMNeT++ simulator [35] is used and the results are compared with three representative cluster-based routing protocols, LEACH, LEACH-C, and AEEC. The performance is measured by average energy dissipation, network lifetime, total number of messages successfully delivered, and number of live nodes. For the simplicity, ideal MAC layer and error-free communication links are assumed. For the implementation of LEACH-C, the setting in [26] was adopted. For the implementation of LEACH, the probability for a node to be selected as a cluster head is decided using the model presented in [22, 26]. The simulation parameters are summarized in Table 1.

Table 1

The parameters used in the simulation.

Parameter	Value
Size of target area	100 × 100
Location of BS	(50, 50)
Number of nodes	(100~500)
Initial energy	0.5 J
$E_{\text{elec}}$	50 nJ/bit
${\epsilon }_{fs}$	10 pJ/bit/m2
${\epsilon }_{mp}$	0.0013 pJ/bit/m4
$E_{\text{schedule}}$	5 nJ/bit/signal
$E_{\text{CH-rotation}}$	5 nJ/bit/signal
$E_{DA}$	5 nJ/bit/signal
$d_o$	70 m
Token size	64 bit
Data packet size	500 byte

For the proposed scheme, the optimal cluster-head probability is first computed. For various intensities of $\lambda =(0.01,0.03,0.05)$ of sensors in a bounded region, the probability for a sensor to be a cluster head is computed by (12). Table 2 lists the probability obtained using the developed model and the corresponding energy consumption obtained by (11) for different intensities. Here, M is set to 100, and thus there exist 100, 300, and 500 nodes if $\lambda =0.01$ , 0.03, and 0.05, respectively.

Table 2

The P probability and corresponding energy consumption based on the proposed model.

Intensity (λ)	Probability (P)
0.01	0.147
0.03	0.099
0.05	0.083

Note that the validity of the P value estimated by the proposed analytical model can be verified through simulation. Figure 2 shows average energy consumed by the entire network as P varies, when $\lambda =0.01$ , 0.03, and 0.05. Here the data are collected with 100-node network for 1000 seconds. Observe from Figure 2 that average energy consumption per round is minimum with the P value obtained using (12). This validates the accuracy of the developed model. It also reveals that the number of clusters obtained by the developed model of cluster-head probability is very close to that of the simulation with which the energy consumption of the network is minimum.

Figure 2

The average energy consumption per round versus probability of being a cluster head for each node.

The proposed scheme employs the approach of cluster-head rotation in each cluster to minimize the energy consumption caused by unnecessary reclustering. For the validation of the effectiveness of the rotation approach, the amount of energy consumed during the setup phase is compared to that of the existing cluster-based schemes in Figure 3. Notice that LEACH-C and LEACH dissipate several times as much energy as the proposed scheme. The energy dissipated at the beginning of each round is constant with LEACH-C because a similar number of transmissions and receptions occur in each round (large transmission power to reach the BS and the probability of collision is small). With LEACH and AEEC, however, the amount of energy consumed varies between the rounds as it depends on the number of cluster heads and their locations within the network changing in each round. With the proposed scheme, energy consumption during the setup phase in each round does not occur except the first round. This is because the setup phase is avoided due to cluster-head rotation until a dead node appears in the network. Here reclustering occurs 72 times with the proposed scheme during 1553 rounds. Note that reclustering occurs every round with the other schemes.

Figure 3

The energy consumption during setup phase per round.

Figure 4 depicts the total remaining energy in the network. Observe from the figure that the energy consumed by the proposed scheme is significantly smaller than the others, particularly in the early rounds. This is due to effective cluster formation and cluster-head rotation.

Figure 4

The total remaining energy of the network.

Figure 5 shows the number of live sensor nodes as the round proceeds with 0.5 J/node initially. It shows that the time when the first node dies with the proposed scheme is about 32%, 23%, and 7% larger than that of LEACH, LEACH-C, and AEEC, respectively. The time when all the nodes die with the proposed scheme is also significantly larger than them. The proposed scheme substantially improves the network lifetime with respect to both the time when a node starts to die ( $t_1$ ) and the time when all the nodes are dead ( $t_2$ ). The relatively small interval between $t_1$ and $t_2$ implies that the proposed scheme successfully balances the load among the nodes. In LEACH, all cluster heads can be located near the edges of the network or adjacent nodes can become cluster heads. Although LEACH-C and AEEC solve the problem of uncertainty on the number of cluster heads in each round which LEACH has, they still have the problem of unbalanced energy loads. To solve this problem, the proposed scheme decides the number of cluster heads allowing minimum energy consumption of the entire network. The proposed scheme also includes a method of cluster-head rotation in each cluster, with which energy consumption caused by unnecessary reclustering is avoided and the loads are evenly distributed among the nodes. Reconstructing the clusters every round for load balancing among the nodes consumes a large amount of energy. In order to minimize the energy consumption, cluster head is rotated without reclustering with the proposed scheme. Reclustering occurs only when the network topology is changed due to dead nodes. This approach ensures balanced energy consumption among the nodes and as a result increases the network lifetime.

Figure 5

Comparison of the number of live nodes as the round proceeds.

Figure 6 shows the total number of messages received by the BS over the number of rounds. For the experiment, a network is assumed having 100 sensor nodes in an area of 100 m × 100 m, and each node begins with an initial energy of 0.5 J. Observe from Figure 6 that the proposed scheme delivers 58%, 37%, and 16% more messages than LEACH, LEACH-C, and AEEC, respectively. This is achieved by balanced clustering and even distribution of the load among the cluster heads.

Figure 6

The total number of messages received by the BS over the rounds.

Note that only the number of live nodes over time may not correctly indicate the performance of a protocol. For example, assume that a protocol transmits fewer packets than others. Then it will consume smaller energy even though the energy efficiency might be even worse than others. For more comprehensive comparison, thus, the percentage of live nodes is checked as the amount of data packets received by the BS is varied as shown in Figure 7. The figure reveals that the proposed scheme delivers more messages with the same number of live nodes as the others. This is because it needs less energy for transmitting the messages.

Figure 7

The number of live nodes as the amount of data sent to the BS grows.

A node is considered dead when its energy is fully depleted, and dead node is excluded from the subsequent rounds. Figure 8 shows the round number when some portion of the nodes are dead. Notice from the figure that the proposed scheme consistently outperforms the existing schemes. For example, with 70% dead nodes, it is approximately 36%, 24%, and 7% better than LEACH, LEACH-C, and AEEC, respectively.

Figure 8

Comparison of the number of rounds as the percentage of dead nodes increases.

7. Conclusion and Future Work

In this paper, we have proposed an energy efficient clustering protocol which effectively reduces energy consumption and prolongs the network lifetime of WSN. It employs a self-organizing, adaptive clustering approach with a newly developed model of optimal cluster-head probability and cluster-head rotation. In the proposed scheme, the clusters are formed according to the analytical model finding the number of cluster heads allowing minimum energy consumption of the network. The proposed scheme also lets the cluster head be rotated inside each cluster without reclustering, which reduces the energy consumed for clustering and evenly distributes the load among the nodes. Reclustering occurs only when the network topology is changed. The order of cluster-head rotation inside a cluster is based on the location of the sensor nodes, allowing efficient implementation and usage of energy. Simulation results show that the proposed scheme substantially improves the network lifetime and energy efficiency compared to LEACH, LEACH-C, and AEEC by effectively balancing the energy consumption over the sensors nodes and minimizing energy consumption.

In the future, we will expand the proposed cluster-head selection scheme by including other factors such as the shape of the target area. Also, a new scheme for scalable and fault-local clustering will be investigated. As another variation of clustering, chain structure can be embedded in the cluster of nodes. We will explore the possibility of extending the multiple-chain approach for data gathering to enhance the energy efficiency. The proposed scheme will also be tested and expanded considering various environments and applications where the requirements on the energy and communication latency are diverse.