1 Introduction

In these days, wireless sensor networks have been widely used in urban and nature environments such as river, forest, bridges, and offices (Lundquist et al. 2003). The wireless sensor networks are sensing, actuating, and wireless communication infrastructures that allow us to receive events from target environments (Martincic and Schwiebert 2005).

Typically, the wireless sensor network consists of hundreds or even thousands of sensor nodes deployed in a remote region to sense events. The sensor nodes communicate with each other to transmit their sensed data to sink node (or base-station). Then, the sink node transfers the data to the human director to know events from the remote region. In the sensor networks, wireless transmission is the most energy consuming operation. In addition, each sensor node have very limited batteries, and it is very hard to recharge them (Karl and Willig 2005). Therefore, energy-efficient transmission protocol is required to maximize network lifetime of the entire sensor networks.

Many kinds of efforts have been done on developing energy-efficient transmission protocols for wireless sensor networks. Those can be categorized into routing, and clustering protocols. Particularly, the clustering protocols can significantly reduce energy consumption by aggregating multiple sensed data to be transmitted to the sink node (or destination node). However, every existing clustering protocol selects cluster head nodes (or cluster heads) periodically, and they only consider ‘How can we select cluster heads more energy-efficiently?’ or ‘What is the best selection of cluster heads?’ without concentrating on energy-efficient period of the cluster heads replacement. For this reason, the existing clustering protocols unnecessarily select and replace cluster heads, and it may dissipate the limited batteries on the sensor nodes. Such energy overhead can significantly reduce the lifetime of the entire sensor networks.

In this paper, we present T-LEACH, which is a threshold-based cluster head replacement scheme for clustering protocols of wireless sensor networks. T-LEACH minimizes the number of cluster head selection by using threshold of residual energy. Lifetime of the entire networks can be extended compared with the existing clustering protocols by reducing the amount of head selection and replacement cost. In our simulation, evaluation results show that T-LEACH outperformed LEACH in terms of energy consumption and network lifetime.

The rest of this paper is organized as follows. In Section 2, we present existing works relating to the routing and clustering protocols for wireless sensor networks. In Section 3, we present the design of T-LEACH in detail with several examples. Section 4 shows evaluated performance of the T-LEACH using TinyOS simulator called TOSSIM (Levis 2002). Finally, several concluding remarks are given in Section 5.

2 Related works

In this section, we briefly present the existing works relating to our scheme. Many kinds of data aggregation protocols have been proposed for wireless sensor networks. These can be categorized into two classes; hierarchical clustering protocols, and chain-based aggregation protocols.

LEACH presented in (Heinzelman et al. 2000) is well-known clustering protocol for wireless sensor networks. LEACH includes distributed cluster formation, local processing to reduce global communication, and randomized rotation of cluster-heads. Together, these features allow LEACH to achieve the desired properties. However, there is no guarantee that nodes selected as cluster head are evenly dispersed throughout the network because procedure to select cluster head is based on the random cluster formation method having local probability. To solve this problem, an improved version of LEACH was proposed, named LEACH-C(Heinzelman 2000). In LEACH-C, cluster formation is made by a centralized algorithm at the base station.

In 2005, Li et al. proposed EEUC, which is an energy-efficient unequal clustering protocol. It partitions nodes into clusters of unequal size, clusters closer to the base station have smaller sizes than those farther away from the base station. Thus cluster heads closer to the base station can preserve energy for the inter-cluster data forwarding.

In 2002, Lindsey and Raghavendra proposed PEGASIS. It makes a communication chain using a TSP(Traveling Sales Person) heuristic. Each node only communicates with two close neighbors along the communication chain. Only a single designated node gathers data from other nodes and transmits the aggregated data to the sink node.

Chan and Perrig proposed an ACE algorithm (Chan and Perrig 2004). It forms clusters based on connectivity information of each node. A node which has the highest connectivity becomes cluster head. If multiple nodes have the highest degree of connectivity, a node which has low unique identifier will be selected as a cluster head. The cluster formation based on a connectivity of nodes is not an appropriate way because every node must maintain connectivity each other, but wireless sensor networks consist of too many nodes.

In PEDAP (Özgür Tan and Körpeoglu 2003), Tan and Korpeoglu have proposed the most optimized minimum spanning tree based on a wireless routing technique. PEDAP compared performances of LEACH and PEGASIS. It shows that the network lifetime of PEDAP is little better than PEGASIS.

Yang et al. proposed SHORT (Yang et al. 2003) for a higher energy-efficiency, longer network lifetime, and larger amount of process than PEDAP-PA. This technique uses centralized control technique and needs a powerful base station. The result of performance measurement shows that SHORT has a better performance in the performance of "Energy × Delay" than existing data collection protocol based on a chain.

HEED (Younis and Fahmy 2004) considers limitations of communication distance of wireless network and intra-cluster communication value and expands LEACH. In each node, the probability to be a temporary cluster head is based on residual energy possessed by each node and every temporary cluster head competes to be the last cluster head. The last cluster head is decided by intra-cluster head communication value.

TEEN (Manjeshwar and Agrawal 2001) is similar to LEACH except that sensor nodes do not have data being transferred periodically. In TEEN, each sensor node decides to transmit their sensed sdata or not using a threshold value. Cluster heads broadcast the value, and if a sensed data is bigger than the threshold value, each node transmits data. LEACH has a feature which is appropriate for proactive sensor network, but TEEN is appropriate for reactive sensor network. APTEEN (Manjeshwar and Agrawal 2002) provides hybrid network which minimizes the uppermost limit of proactive sensor network and reactive sensor network and combines merits of both sensor networks. In APTEEN, sensor nodes can periodically transfer data and well respond to sudden change of an attribute value of measured data.

3 T-LEACH: Threshold-based LEACH protocol

In this section, we present overview of the clustering protocols for wireless sensor networks. Then, we present the main design of T-LEACH in detail with several examples.

3.1 Overview of clustering protocols

In wireless sensor networks, clustering is an essential way to minimize energy consumption incurred by wireless transmission between sensor nodes. Typically, existing clustering protocols have two kinds of phases in each communication round (T round); one head selection phase (T sp), and multiple data communication phases (T dp). Each data communication phase is composed of intra communication phase (T intra) and inter communication phase (T inter). Figure 1 briefly presents the two phases.

Fig. 1
figure 1

Round and phases of a clustering protocol

Full size image

In Fig. 1, the first phase is a selection phase to vote and select head nodes (Karl and Willig 2005; Hou et al. 2005). The second phases are data communication phases to transmit sensed data to the sink node. The stages continue repeatedly. In the selection phase, an energy-aware cluster formation algorithm is required to balance energy consumption for all sensor nodes. Recently, many kinds of algorithms have been developed using probability, residual energy, and connectivity of the networks. After the selection phase, each node except cluster heads becomes a participant of a cluster. Then, each node transmits its sensed data to the head node in intra communication phase. The head nodes aggregate data received from participants, and transmit it to the sink node in inter communication phase.

In general, sum of T dp in a round is longer than T sp in the existing clustering protocols. If the sum of T dp is too long, cluster heads consume too much power on aggregation and transmission. On the other hand, if it is too short, frequent head selection may spoil the energy-efficiency of the entire wireless sensor networks.

Figure 2 shows an example of clusters in wireless sensor networks. In LEACH protocol, each cluster set is determined by the distance from the cluster heads. Each node participates in a cluster which has the nearest head node in the entire networks.

Fig. 2
figure 2

An example of clusters in wireless sensor networks

Full size image

Table 1 shows several existing cluster head selection protocols. As shown in this table, many efforts have been done on the cluster head selection protocol to balance and reduce energy consumption. In a clustering protocol, energy-aware cluster head selection is necessary, but also, replacement of the head nodes is the most important one. In this paper, we focus on the cluster head replacement to improve both energy-efficiency and balance of energy consumption.

Table 1 Existing cluster head selection protocols
Full size table

3.2 Impact of clustering protocol on energy consumption

The degree of energy consumption on each sensor node changes according to the distance between cluster head and sink node, and transmission method by multi-hop or by single-hop. In case of single-hop(e.g. LEACH), because cluster head transmits data to sink node directly, it’s very different that energy consuming degrees of clusters which the closest cluster near to the sink node, and the farthest cluster away from the sink node. Generally, the farthest cluster away from sink node consumes more energy than other clusters. In case of multi-hop, because of transmit data from all clusters by relay, the closest cluster near to sink node consuming large energy.

Consequently, in cluster tree topology, energy consumption degrees are different as the roles of sensor nodes, thus, role of cluster head needed large power must be distributed for energy-efficient networks. Figures 3 and 4 show intra-cluster and inter-cluster range.

Fig. 3
figure 3

Maximum distance between member nodes

Full size image
Fig. 4
figure 4

Maximum distance between cluster heads

Full size image

The FND means first node die and LND means last node die (Handy et al. 2002) time can be used to represent the barometers of energy-efficient network, because the infection of withdrawn arbitrary node spreads out to whole network. Consequently, the interval between FND and LND time must be minimized to be the greatest energy-efficient network.

Figure 5, result of the simulation, shows process of LEACH from the viewpoint of dissemination of dying nodes. It is known to us that the number of dying nodes with time increased linearly. This figure will used to compare the result of proposed algorithm and previous algorithm.

Fig. 5
figure 5

Progress of network lifetime of LEACH (Using TinyViz Simulator)

Full size image

If position of sink node is fixed, cluster construction related with distance of sink node. Otherwise, it needed to research more considerable that clusters constructed energy-efficiently.

3.3 T-LEACH: Threshold-based cluster head replacement

T-LEACH stands for threshold-based LEACH because it replaces cluster heads based on the threshold value of residual energy on the sensor nodes. In this subsection, we present the design of T-LEACH in detail.

In traditional protocols relating to cluster optimization, the authors proposed that the number of cluster heads be reduced to decrease energy consumption or that energy efficiency-based optimal cluster sizes be constructed to extend the survival time of the network. LEACH algorithm has a structure where cluster heads are selected according to probabilistic values and the collection and transmission of messages occur during each round. Consequently, the number of cluster heads and rounding periods come to be closely related to energy consumption. In these algorithms, nodes play the roles of cluster heads periodically, and these are not considering energy cost of that time. When arbitrary sensor nodes become cluster heads through the performance of rounds, nodes selected as cluster heads must broadcast to member nodes of the clusters to which they belong that they have become cluster heads. Consequently, as the frequency of rounding and of cluster head replacement increases, energy consumption increases due to message transmission for broadcasting.

All the nodes start with initial power. It’s impossible that sensor nodes recharge energy and replace battery in ubiquitous sensor networks. Thus, it’s very important that sensor nodes expense energy efficiently. To calculate the whole energy consumption of the networks, we have to consider two parts. One is quantity of energy as roles of sensor nodes. Another is a volume of energy when role of sensor nodes is exchange. There is a significant disparity of energy consumption between cluster heads and member nodes.

All member nodes are transmitting perceived data to cluster head on allocated time slot periodically. And then cluster head transmit data aggregated in the cluster. Generally used RF chip by sensors, Chipcon CC2420 RF transceiver, consumes 17.4 mA on transmission and 19.7 mA on reception of radio at 250 kbps data rate (Bergli 2003).

Due to figure of network lifetime, it must be included that energy degree when cluster head replacing because of that.

P Tx represents amounts of energy consumed for 1 byte data transmission, P Rx the amounts of energy consumed for receiving 1 byte data. Whole network consists of n nodes, and if it is comprised of C% clusters, and it happens R count of cluster head replacement. pk Tx, pk Rx are size of packet when transmission and reception happen. In this time, Eq. 1 (additional energy consumption during cluster head replacement) represents of whole energy degree that network has consuming.

$$P_{{\text{HR}}} = \left\{ {\left( {pk_{{\text{Tx}}} \cdot P_{{\text{Tx}}} + pk_{{\text{Rx}}} \cdot P_{{\text{Rx}}} \cdot \left( {nC - 1} \right)} \right.} \right\} \cdot R \cdot nC$$
(1)

In the Eq. 1, nC represent the number of nodes per each cluster. If receive cost is three times of transmit cost, Eq. 2 (simplified expression of Eq. 1) is replaced Eq. 1 as follows.

$$P_{{\text{HR}}} = R \cdot nC\left( {3nC - 2} \right) \cdot pk \cdot P_{{\text{Tx}}} $$
(2)

In this Eq. 2, it seems that total amount of consumed energy of cluster head replacement is commensurate to R which is the number of count of cluster head replacement.

Figure 6 shows the traditional cluster head replacement process. Here, cluster heads are replaced during each round period to allow all nodes to play the roles of cluster head evenly. However, this method can actually lead to the overuse of messages for broadcasting that the nodes have been selected as cluster heads.

Fig. 6
figure 6

Existing methods of cluster head replacement

Full size image

On the other hand, Fig. 7 shows concept of proposed algorithm that delayed head replacement when residual energy of cluster head reaches to threshold value.

Fig. 7
figure 7

Proposed methods of cluster head replacement based on threshold

Full size image

In T-LEACH, decision whether to perform rounding is made based on additional residual energy in each sensor node to replace cluster heads. In other words, when current cluster heads maintain residual energy at a level above the pre-established threshold, heads are not replaced even when it is time to replace them and the time of rounding is delayed until the level falls below the threshold, thus making it possible for nodes to continuously play the roles of cluster heads. Also we know that whole energy consumption can be reduced by minimizing the number of R in Eq. 2.

One cluster consists of n nodes, CH denotes cluster head and CM denotes the member node. Firstly, the member nodes transmit data to the cluster head consuming amounts of P Tx × n (byte) and keep sleep mode until next round’s time slot. Secondly, there are two times of energy consumption stages in the cluster heads; One is aggregation stage, in this stage, cluster head consumes amounts of P Rx × n (byte) × (N − 1) to aggregate data. N denotes the number of nodes per each cluster. Another is the transmission stage to the sink node. In the transmission stage, cluster head expenses amounts of P Tx × n (byte) × (N − 1) to transmit data. Obviously, cost of transmission stage can increased caused of growing distance to the sink node.

To acquire threshold value, we also have to know how many times of round to active as member node in a cluster. The threshold must be set to amounts of CountRND × P Tx × n (byte) for accomplishment of member nodes until network extinguishes its own energy. COUNTRND representing times of round, is calculated as follows:

$${\text{Count}}_{{\text{RND}}} = \frac{{P_{{\text{HR}}} }}{{P_{{\text{WEC}}} }} \cdot 100$$
(3)

P HR denotes power consumption of head replacement, P WEC denotes whole energy of each cluster and is represented Eq. 4 (total power of each cluster).

$$P_{{\text{WEC}}} = {\text{NumofNodesPerCluster}} \cdot {\text{InitPowerofEachNode}}$$
(4)

In this equation, P WEC denotes total amount of energy granted each cluster unit.

$$\matrix {P\left( i \right)_{{\text{HR}}} = \left\{ {\left( {N_i - 1} \right) \cdot pk_{{\text{Tx}}} P_{{\text{Tx}}} \cdot pk_{{\text{Rx}}} P_{{\text{Rx}}} } \right\}} \\ { + \left\{ {\left( {N_i - 1} \right) \cdot pk_{{\text{Rx}}} P_{{\text{Rx}}} + \left( {N_i - 1} \right) \cdot pk_{{\text{Tx}}} P_{{\text{Tx}}} } \right\}} \\ { = n\left( {5N_i - 3} \right)P_{{\text{Tx}}} } \ $$
(5)

Equation 5 (energy consumption degrees per round in each cluster unit i) represents of the amounts of energy cost for a round. Here, P HR composed of two cost value; one is the energy cost when the node is role of cluster head, and the other is the energy cost when the node actives member node. With Eqs. 3 (the number of round times) and 5, what the threshold value when the cluster head can be replaced:

$$P_{{\text{Th}}} = {\text{Count}}_{{\text{RND}}} \cdot \left( {pk_{{\text{Tx}}} + pk_{{\text{Rx}}} } \right)P_{{\text{Tx}}} $$
(6)

In Eq. 6 (threshold value for cluster head replacement), P Th represents threshold level of cluster head replacement. As we apply it to LEACH algorithm, we could not only improve lifetime of LEACH but also make network to balance as shorten interval between FND and LND time.

4 Performance evaluation

In this section, we evaluate performance of T-LEACH compared with LEACH protocol in detail including energy-efficiency and network lifetime. We used TOSSIM as a simulator to evaluate performance of the clustering protocols. Using TOSSIM, we compare FND and LND time for each protocol.

The basic environmental variables used in performance evaluation assume that different amounts of energy consumption would be generated according to the roles performed by sensor nodes and make a distinction between the network size and the distance among sensor nodes. The network size was presumed as a square measuring 100 × 100 m, sink nodes were assumed to be in the arbitrary location, and the performance of algorithms was evaluated by the networks’ lifetime. In addition, the amount of energy consumed was measured in consideration of the energy consumption needed for the cluster head replacement performed by each sensor node and the amount of energy consumed in broadcast messages regarding cluster member nodes generated when head replacement has been performed and cluster heads have been replaced. Table 2 shows the environmental variables applied to performance evaluation.

Table 2 Environmental variables
Full size table

As shown in Table 2, the number of sensor nodes is from 100 to 500. Every node was given an identical amount, 5 J, of initial energy. The energy for transmission was assumed 20 nJ/bit + 1 pJ/bit/m3. The energy for reception was assumed 60 nJ/bit. The packet length was assumed 32 bytes. Each of the experiment performed 100 trials individually, and computes the average to compare results.

Figure 8 shows network lifetime in terms of FND and LND when using the original LEACH protocol. In this figure, the number of nodes changes from 100 to 500.

Fig. 8
figure 8

Network lifetime of LEACH

Full size image

In Fig. 8, there is some difference between FND and LND of LEACH protocol. Even if many sensor nodes are alive, it’s impossible to observe certain area where corresponding nodes are died.

Figure 9 represents progress of network lifetime when using T-LEACH protocol. Let us compare this result with Fig. 3. Based on the two results, we can observe that T-LEACH is more energy-efficient than LEACH.

Fig. 9
figure 9

Progress of network lifetime of T-LEACH

Full size image

Figures 10, 11 and 12 show the network lifetime of the modified LEACH protocols. We modified LEACH protocol by adapting the proposed scheme with fixed threshold value (6~10% of the initial energy on each sensor node). Where the number of nodes is 100 and 300, the networks carry on the longest lifetime at 9% threshold value. On the other hand, when the number of nodes is 500, the result shows the greatest value at 7% threshold value.

Fig. 10
figure 10

Network lifetime of modified LEACH when changing threshold (the number of nodes: 100)

Full size image
Fig. 11
figure 11

Network lifetime of modified LEACH when changing threshold (the number of nodes: 300)

Full size image
Fig. 12
figure 12

Network lifetime of modified LEACH when changing threshold (the number of nodes: 300)

Full size image

In case of the modified LEACH, uniform percentage of threshold value is applied to all nodes. However, in the actual environment of wireless sensor networks, it is impossible to use the same threshold value.

Figure 13 shows result of T-LEACH in terms of FND and LND when the number of nodes is 100, 300, and 500. In this result, threshold levels are applied differently for each node because each cluster has the different number of participant nodes. Figure 14 shows the network lifetime of LEACH sand T-LEACH in terms of FND and LND. In this result, we can observe that T-LEACH outperformed LEACH in terms of network lifetime. Especially, T-LEACH shows almost same result in FND and LND. Based on this result, we confirm that T-LEACH is also better than LEACH in terms of balancing the energy consumption of the sensor nodes.

Fig. 13
figure 13

Network lifetime of T-LEACH

Full size image
Fig. 14
figure 14

Network lifetime of LEACH and T-LEACH

Full size image

5 Conclusions

Many kinds of existing clustering protocols have been developed to balance and maximize lifetime of the sensor nodes in wireless sensor networks. However, the existing clustering protocols do not consider the energy-efficient duration of the cluster heads replacement. Frequent cluster head selection and replacement may unnecessarily dissipate limited battery power of the entire sensor networks. In this paper, we present T-LEACH, which is a threshold-based cluster head replacement scheme for wireless sensor networks. It minimizes the number of cluster head selection and replacement by using the threshold value of the residual energy. Reducing the amount of head selection and replacement cost, the lifetime of the entire networks can be extended compared with the existing clustering protocols. Our simulation results show that T-LEACH outperformed LEACH in terms of the balancing energy consumption and the network lifetime.

We are currently extending our work to implement T-LEACH protocol on existing sensor operating systems for wireless sensor networks. We are convinced that if we apply the proposed scheme to the real sensor nodes, we can get more energy-efficient and long-lasting wireless sensor networks.