Improved LEACH Routing Communication Protocol for a Wireless Sensor Network

Abstract

A WSN (wireless sensor network) consists of thousands of sensor nodes with limited energy, memory, and computation capability. The applications of WSN in some extreme environment make sensor nodes difficult to replace once they use up the resource. Hence, many researchers in this field focus on how to design a property routing protocol to prolong the life span of the network. The classical hierarchical protocols such as LEACH and LEACH-C have better performance in saving the energy consumption. However, the choosing formula neglecting the change of Nodes' energy will make the nodes acting as cluster heads too many times die early owing to the consumption of too much energy. Also, the high frequency of reclustering wastes certain amount of energy. In order to make the energy distribute more evenly among different nodes, we improve the tradition equation used for selecting cluster heads with considering the dynamic change of nodes' energy. Meanwhile, we propose to establish a vice cluster head for each cluster during the communication process, which aims to diminish the energy consumption spent on the reclustering and prolong the time of being in a steady-state phase. Simulations show that our improved protocol performs better than the LEACH and the LEACH-C.

1. Introduction

WSN (wireless sensor network) [1] consists of more than hundreds of small sensor nodes which have limited power, memory, and computational capabilities. The application of the WSN involves many fields, such as the military battlefield, forest fire detection, and other extreme environments [2]. In these situations, it is difficult to replace the dead nodes caused by energy's depletion with new ones to supply energy for the system. Therefore, making sensor nodes working as long as possible is the main method to maximize the lifecycle of the system. Because the energy's consumption of sensor node mainly originates from the long distance transmission of data along the routing path, an efficient routing path formed by the routing protocol will have a great impact on the energy's consumption [3]. So how to design an energy-efficient routing protocol becomes the main goal for the wireless sensor network.

The conventional wire routing protocol cannot adapt to the wireless sensor network due to the inherent property of WSN. Hence, many protocols have been proposed to satisfy the need of WSN. The cluster idea present in [4, 5] has a significant reflection to the research of WSN routing protocols. It organizes the sensor nodes into different clusters, with a cluster head in each cluster executing the data collecting and transmitting tasks for other member nodes. The main idea introduced in the hierarchical routing protocols is to divide the whole network into two or more levels with each level performing different tasks. LEACH (low energy adaptive clustering hierarchy) [5] is a classical version in the hierarchical routing protocol family which divides the communication process into rounds with each round including a set-up phase and a steady-state phase. In the set-up phase, some sensor nodes are selected as cluster heads (CHs) according to certain rules and other nodes join in the clusters as member nodes. In the steady-state phase, the CHs collect and aggregate the data coming from their own cluster members and then transmit them to a base station (BS). Based on the LEACH, LEACH-C differs from LEACH in that it uses a central algorithm to finish the choice of CHs in each round, but it needs all the sensor nodes to transmit their information to remote BS [6]. No matter LEACH or LEACH-C, the existence of cluster head (CH) in a cluster avoids the long transmission distance to BS in a communication process for each sensor node. Meanwhile, the aggregation of the data on the cluster heads reduces almost simultaneously a lot of redundancy data message coming from different member nodes [7]. However, due to the inherent characteristic of LEACH and LEACH-C, the unnecessary energy consumption caused by the unreasonable choosing formula and the high frequency of reclustering among sensor nodes will cause the uneven energy distribution and waste a certain amount of energy in the whole network. Based on the ideology of traditional LEACH, we modify the choosing formula for considering the dynamic change of sensor nodes' energy and change the process of choosing CHs to reduce the frequency of re-cluttering.

The remainder of the paper is organized as follows. In Section 2, we present LEACH and LEACH-C in detail. Section 3 develops our proposed protocol and provides its theoretical analysis. We evaluate the performances of three protocols via ns2 in Section 4. In Section 5, conclusion is derived based on the analysis and simulation.

2. LEACH and LEACH-C Protocols

LEACH is the most popular hierarchical cluster based routing protocol for a wireless sensor network [5]. In LEACH, the nodes in the deployed area are organized into local clusters and the communication process is divided into rounds with each round including set-up and steady-state phases. During the communication process, each cluster has a cluster head (CH) which is responsible for creating and manipulating a TDMA (time division multiple access) schedule table used by its member nodes to get when to transmit data packets. Once some emergency affairs happen in the monitor area, the sensor nodes are triggered to send data to their own cluster head instead of the remote BS by themselves. The cluster head mainly collects the data coming from different member nodes and does some aggregation to diminish the redundancy firstly and then transmits them to BS. In the whole process, the cluster head just works as a relay node to help member nodes shorten the transmission distance so as to save energy. As for the set-up and steady-state phases in a round, they can be described as follows.

2.1. Set-Up Phase

After finishing the deployment of sensor nodes, each node in the monitor field decides independently of other nodes whether it can become a cluster head in the current round. During the phase, each node generates a random number between 0 and 1 and then compares the threshold value with [8]

$$\begin{array}{cc}& T\left(n\right)=\{\begin{array}{cc}\frac{p}{\mathrm{1}-p*\left[r\mathrm{mod}(\mathrm{1}/p)\right]},\hfill & n\in G,\hfill \\ \mathrm{0},\hfill & n\notin G,\hfill \end{array}\end{array}$$

(1)

where p is the percentage of cluster heads over all nodes in the network, r is the number of rounds of selection, and G is the set of nodes that have not been selected as cluster heads in round $1/p$ . The node whose number is larger than the threshold will select itself as a cluster head and then broadcasts the message to its surround sensor nodes. In this phase, a node may receive more than one broadcast message from different cluster heads, but the node can judge its distance to a cluster from the strength of received broadcast signal; the stronger the signal, the closer to a cluster. So the node whose number is smaller than threshold will only send request message containing its ID to the cluster which has the strongest signal strength for saving energy spent on the transmitting distance. Once the cluster head receives request message coming from one node, it records the node's ID and proclaims it as its member node. After the message exchanges between cluster heads and normal nodes, each CH gets its own member nodes' information about IDs and each normal node gets which cluster it belongs to. Based on the message it records, the CH creates a TDMA schedule table and broadcasts it to the cluster members. Therefore, all the member nodes get their idle slots for data transmission, and then the steady-state phase starts.

2.2. Steady-State Phase

The establishment of a cluster head in each cluster during the set-up phase provides a guarantee for the data transmission in a steady-state phase. In normal circumstances, member nodes can turn off their radio until they sense the necessary environment data. If there are some data in need to transmit, they will send the data to CH during the idle slots recorded in the TDMA schedule table. As for the CHs, they have to keep up communication status at all times so as to receive the data from different member nodes. After receiving all the data sent by their members, CHs will aggregate them firstly and then send them to BS. Because some sensor nodes may sense similar environment data, the aggregation on the cluster head can diminish unnecessary bandwidth cost and communication traffic, which has a positive reflection to the energy's consumption. Also, the data transmission distance becomes shorter comparing with transmitting to BS separately for each member node, which can save some energy for the member nodes. However, the heavy tasks executing on CH can lead to too much energy consumption. In order to avoid making the CHs die early and cause the cascade effect in the network, a new round begins and new clusters will be rebuilt in the whole network.

2.3. LEACH-C Protocol

Based on the LEACH, LEACH-C also organizes the sensor nodes into clusters with each cluster a cluster head and divides a round into set-up and steady-state phases. It differs from LEACH only in that it uses a high-energy base station to finish the choice of cluster heads. In the set-up phase of each round, every sensor node sends its information about energy to remote BS. Then the BS selects the cluster heads based on the energy information and broadcasts the IDs of cluster heads to other member nodes. This method can make the nodes with more energy and more chance to become the cluster head in the current round. But in this phase, every sensor node needs to send its ID and energy information to remote BS to compete for the role of cluster heads, which causes energy consumption on the long distance transition. Equation (2) has a good description of transition distance influence on the consumption of energy [3]:

$$\begin{array}{cc}& E_{\mathrm{trans}}(k,d)=\{\begin{array}{cc}k{E}_{\text{elec}}+k{\epsilon }_{fs}{d}^{\mathrm{2}}\hfill & \left(d<d_{\mathrm{0}}\right),\hfill \\ k{E}_{\text{elec}}+k{\epsilon }_{mp}{d}^{\mathrm{4}}\hfill & \left(d\ge d_{\mathrm{0}}\right).\hfill \end{array}\end{array}$$

(2)

The transmission energy of transmitting a k-bit message over a distance d will cost $E_{\mathrm{trans}}$ ; ${\epsilon }_{fs}$ and ${\epsilon }_{mp}$ are the power consumption of transferring 1 bit of data in different condition. We can obtain that there will be a certain amount of energy needed to be spent on the transition of energy information for each sensor node in every round, which cannot be neglected in communication; especially the BS locates far away from the monitor field and the network has a lot of sensor nodes.

Although LEACH and LEACH-C protocols act in a good manner, they also suffer from many drawbacks like the following.

• (i)

CHs' selection is random, which does not take into account the residual energy of every node or need the support of BS.

(ii)

The high frequency of reclustering wastes a certain amount of energy.

(iii)

It cannot cover a large area.

(iv)

CHs are not uniformly distributed, where CHs can be located at the edge of the cluster.

3. The Improvement to the Cluster-Based Leach Protocol

Motivated by the original LEACH, LEACH-C and other improvement protocols [9, 10], we propose a modification to the cluster head selection process to reduce energy consumption. For a microsensor network, we first make the following assumptions.

• (i)

The base station (BS) is located far from the sensors and is immobile.

(ii)

All nodes in the network are homogenous and have limited energy with an indentify ID.

(iii)

All nodes are able to reach BS and can communicate with each other.

(iv)

Cluster heads perform data compression and aggregation.

In the improvement, we also make use of the clustering ideology in hierarchical and divide a round into a set-up phase and steady-state phase. The set-up phase will use improved formula to select appropriate cluster heads (CHs) which are responsible for collecting data from their member nodes and transmitting them to BS. As the introduction in Section 3, CHs will consume more energy than member nodes because of the heavy tasks. In order to avoid making the CHs die early, LEACH and LEACH-C take the measure of beginning a new round and rebuilding the clusters. However, in this paper, we will make use of the member nodes' information dynamically achieved by cluster heads in the steady phase to choose the vice cluster heads (VCHs) which take over the role of cluster heads in the later period of steady phase. Comparing with the traditional LEACH and LEACH-C, the VCHs proposed will diminish the frequency of reclustering in the same interval and prolong the time of being in steady-state phase, which will prolong the lifecycle of the whole network.

3.1. Choosing Cluster Heads (CHs) in the Set-Up Phase

Based on the fact that LEACH does not take into account the residual energy of the nodes during the selection of cluster heads in the set-up phase, we develop the current energy and the times being selected CH or VCH which will be shown later in the paper. We first consider that the threshold $T(n)$ is modified to the following equation:

$$\begin{array}{cc}& T\left(n\right)=\hspace{0.17em}\hspace{0.17em}\{\begin{array}{c}\frac{p}{\mathrm{1}-p*\left[r\mathrm{mod}(\mathrm{1}/p)\right]}\hfill \\ \times \begin{array}{c}[\frac{E_{n\_\text{current}}}{E_{n\_\text{init}}}+\left(\mathrm{1}-\frac{E_{n\_\text{current}}}{E_{n\_\text{init}}}\right)\end{array}\hfill \\ \times \frac{p}{\text{CH}\_\text{times}+\text{VCH}\_\text{times}+\mathrm{1}}],\hspace{1em}n\in G,\hfill \\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{1em}n\notin G,\hfill \end{array}\end{array}$$

(3)

where p is the percentage of cluster heads over all the nodes in the network, R is the number of rounds selection in current time. G is the set of nodes that have not been selected as cluster heads in round $1/p$ . $E_{n\_\text{current}}$ is the residual energy of the node and $E_{n\_\text{init}}$ is the initial energy of every node. CH_times (VCH_times) is the times of being selected CH (VCH_times) once. Deducing from (3), we can obtain that the larger the $E_{n\_\text{current}}$ , the larger the $T(n)$ . So we can infer that the node which has more energy will have a bigger probability to become the cluster head in the current round. At the same time, if a node acts as CH or VCH for too much time, the energy it consumes will be larger than other sensor nodes. However, the improved equation can make the probability of a node acting as too much time CH or VCHs to become CH again lower. We can observe that the improved formula adds some helpful determinacy factors in the selection of cluster heads, which is beneficial to the stabilization of clusters. The authors in [11] proposed that if there are too much cluster heads in the deployed area, it will cause some unnecessary consumption of energy. In order to limit the cluster heads' number to a reasonable range, we develop the simulated annealing algorithm to create appropriate numbers of cluster heads which is about 4%-5% of the total sensor nodes introduced in [12]. After finishing the selection of cluster heads in the set-up phase by using the improved equation and simulated annealing algorithm, the steady-state phase of a round begins.

3.2. Vice Cluster Heads' (VCHs') Establishment during the Steady-State Phase

In the steady-state phase of LEACH and LEACH-C protocols, the cluster heads will deplete more energy than member nodes because they have to take the responsibility of aggregating and relaying data to remote BS for their member nodes. In order to avoid making the cluster heads die early after undergoing certain of communication time, a new round begins to reorganize the nodes into clusters and reselect the cluster heads. So, all the nodes have to reappraise themselves and rebuild the cluster heads in order to campaign for new cluster heads. As a result, it consumes some energy spent on recompeting the cluster heads and shortens the total time of being in steady-state phase. In this paper, we propose a new scheme to prolong the time of being in steady phase and diminish the frequency of recluster. The new scheme works as follows.

During the data communication in steady-state phase, because all member nodes send the data sensed from environment to their own cluster head, the cluster head can have the opportunity to learn the status information of its members. Based on this fact, the cluster head can record the information of different member nodes dynamically, the format of the information just like $〈id,E〉$ , which means the member node id has residual energy E. Through this way, the CH will have global energy information to its member nodes. In order to prolong the time of being in steady-state phase and delay a new round's coming, CH will appoint a member node which has the maximum energy in cluster to take over the role of it if consuming too much energy in the later steady-state phase of current round. We can call the member node which is appointed by the CH vice cluster (VCH). In order to make the rest of member nodes get the id of VCH, the CH will broadcast this message containing the VCHsid to other member nodes. After that, the CH itself will become a normal member node because of the too much energy consumption and the establishment of VCH in a cluster. Since then, all the member nodes will send their data to VCH, which compresses data firstly and then relays them to BS. We can observe that the establishment of VCH in cluster can prolong the communication time of being in steady-state phase and delay the coming of a new round. But after a certain time, the VCH will also consume more energy than the member nodes due to the heavy tasks undertaken as previous CH. To avoid making the VCH die early, a new round of selecting CHs in the set-up phase will start among all the nodes. So we can call the whole communication in our improved protocol as the cycle of “CH-VCH-CH.” It can be described using the Figure 1.

Figure 1

Improved hierarchical protocol working process.

In the proposed protocol, we take the measure of selecting a VCH for each cluster in the later period of the steady-state phase in a round by using the energy information achieved by CH, which can diminish the frequency of reclustering and prolong the time of being in steady-state phase. In the whole communication phase of a round, CH and VCH have the same role to undertake collecting data from member nodes and relaying them to BS. The difference is that the CH takes the responsibility in the earlier stage of the steady-state phase in a round, while VCH replaces the CH and works in the later stage of the steady phase. Also, the CHs selection originates the competition among all the nodes in the set-up phase. However, VCH is established directly by CH in the later stage of the steady-state phase in a round. We can obtain that the method of establishing VCH is simple and rapid comparing with the generation and cooperation of random numbers in the set-up phase. They all have a good benefit to the saving of energy in the whole network.

4. Simulation Result

In this section, we examine the improved protocol through NS2 [13]. A network of 100 nodes is deployed in an area of $\mathrm{100}\hspace{0.17em}\text{m}\mathrm{\hspace{0.17em}\hspace{0.17em}}\times \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{100}\hspace{0.17em}\text{m}$ with BS at (50, 175). The main parameters of the simulation experiments are described in Table 1.

Table 1

Summary of the parameters used in the simulation experiments.

Parameter	Value
Number of nodes	100
Network size	100 m × 100 m
BS location	(50, 175)
Radio speed	2 Mbps
Data size	25 bytes
Initial node power	2 J
Numbers of CH	5
Simulation time	600 secs

In order to compare the advantage of the improved protocol with the original LEACH and LEACH-C, we use three performance metrics for comparison: numbers of nodes alive over simulation time, the consumption of the whole network's energy over simulation rounds, and the message amounts created by the three different protocols. The simulation results are illustrated in Figures 2–4.

Figure 2

Number of nodes alive over simulation time.

Figure 3

Energy consumption over simulation rounds.

Figure 4

Message created over number of nodes.

Observed from Figure 2, we can obtain that the numbers of nodes alive in improved protocol surpasses the nodes alive in LEACH and LEACH-C protocols at the same time. The network using LEACH routing protocol stops its life at about 450 seconds and LEACH-C can maintain the lifecycle to about 500 seconds, while the improved protocol can prolong its lifetime to 570 seconds.

Because of the introducing of VCH, some energy spent on the reclustering and recomputing among different nodes gets certain of economy. Observed from Figure 3, we can obtain that our improved routing protocol consumes less energy than LEACH and LEACH-C over the simulation rounds.

Due to our modification to the steady-state phase, the times for choosing the cluster heads and broadcasting the notifications to each member node in the whole network become less as well as the message created by the nodes, which means the remaining energy of the network using our improved protocol exceeds that of the original LEACH and LEACH-C used. The result is validated through ns2 simulation in Figure 4.

5. Conclusion

In this paper, an overview of the original LEACH and LEACH-C protocols is presented and a new version of hierarchical protocol is proposed. The proposed protocol obtains energy efficiency by the modification to choosing of cluster heads formula and the steady-state phase.

The modification to the choosing of cluster heads formula makes the sensor nodes which have more energy and play less role in making the CH or VCH have more opportunity to act as CHs in the coming round. So the total energy of the whole network has more even distribution among different nodes. The introduction of VCH makes the frequency of reclustering more lowly and prolongs the time of being in steady-state phase; thus the energy used for calculating the formula on every nodes reduces. Through the modification and simulation, we can conclude that our proposed protocol performs better than LEACH and LEACH-C protocols.