Open Access Library Journal
Vol.02 No.12(2015), Article ID:68998,8 pages
10.4236/oalib.1102251

Reduction of Single Clusters in LEACH Protocol for Wireless Sensor Networks

Yaye Mbekhe Sarr1, Cheikh Sarr1*, Bamba Gueye2

1Faculty of Science and Technology, University of Thies, Thies, Senegal

2Faculty of Science and Technology, University of Dakar (UCAD), Dakar, Senegal

Copyright © 2015 by authors and OALib.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 29 November 2015; accepted 13 December 2015; published 18 December 2015

ABSTRACT

Clustering in wireless sensor networks (WSN) is an efficient way to structure and organize the network. The cluster-head (CH) forms dominant set in the network which is responsible for the creation of clusters, maintenance of the topology and data aggregation. LEACH (Low Energy Adaptive Clustering Hierarchy) is one of the most prominent hierarchical routing protocols used in Wireless Sensors Networks (WSN). Many protocols have been proposed in the literature to improve LEACH protocol. The cluster formation in LEACH is probabilistic, therefore there is heterogeneous size of cluster in the network and sometimes singleton, i.e. cluster with only one node could appear. These singletons directly send information to the base station (BS). Consequently they consume more energy due to the distance to the base station. This paper proposes a hierarchical routing protocol based on LEACH called LEACH-based SNCR that reduces singletons and balances the energy consumption between sensors. Simulations results show that LEACH-based SNCR increases the network lifetime compared to LEACH.

Keywords:

Wireless Sensor Network (WSN), Cluster-Head, Cluster, Election, Energy Saving, Performance

Subject Areas: Network Modeling and Simulation

1. Introduction

Wireless sensors nodes (WSN) consist of hundreds to thousands nodes with sensing, computation, and wireless communications capabilities [1] . Sensors nodes are randomly distributed over an area to collect information on physical or environmental conditions. The collected information is sent to a remote base station (BS) also called sink which processes the data. WSN are considered as one of the most important technologies of the 21th century. Sensor networks are used in application like surveillance (forest fire, meteorological, control of air quality) or connected objects, etc.

The sensors, also called nodes in the rest of the document, are characterized by small size, limited energy and computing capacity. The depletion of the battery causes the “death” of the sensor. A major challenge in WSN is to be able to keep more longer energy of the nodes to extend the lifetime of the network. Thus, in recent years some studies have focused on routing protocols to send the information captured by the sensor nodes to the BS by consuming less energy and then prolonging lifetime of WSN.

The concept of dividing the geographical region to be covered into small zones has been presented as clustering in the literature. The clustering technique means partitioning network nodes into groups called clusters, giving the network a hierarchical organization. The grouping of sensor nodes into clusters has been widely pursued by the research community in order to achieve the network scalability objective. In recent years, researches have focused on energy-aware routing in WSN to efficiently send sensed information to the BS. Various energy efficient routing protocols have been already proposed such as LEACH [2] , PEGASIS [3] and TEEN [4] . LEACH is one of the most popular routing and hierarchical protocols in WSN. This article proposes LEACH- based SCNR, a new protocol which reduces singletons formation in order to provide better performance in terms of power consumption and lifetime in WSN. LEACH-based SNCR solves this problem by integrating the single CH in another cluster and reduces the overall energy consumption over the network.

The rest of the paper is organized as follows: Section 2 presents a state of the art of routing protocols in WSN. Section 3 shows the impact of single nodes on energy consumption. Section 4 describes our LEACH-based SNCR protocol and presents the results of simulations. Finally, Section 5 concludes this work and presents perspectives.

2. Related Work

The goal of any routing protocol is to efficiently route information from a source to a destination [5] . The main constraint in routing in WSN is to route captured information with minimum amount of energy. Several routing protocols have been proposed in the literature.

2.1. Cluster Based Hierarchical Routing Protocols for WSNs

The approach used by the cluster based hierarchical routing is to group sensor nodes into a cluster. A node is elected as cluster-head and its role is to collect captured information by its members and forward them to the base station (Figure 1). LEACH and TEEN are examples of cluster based hierarchical routing protocols.

The advantage of this type of protocol is that they route information more quickly thus reducing latency compared to a multi-hop approach [6] .

The election of the CH could rely on a single metric which can be random as for LEACH of deterministic, or based on combination of several metric.

2.2. LEACH Protocol and Derivatives

LEACH randomly selects nodes in the network and assigns them the role of cluster-head. Subsequently other

Figure 1. Hierarchical routing protocols.

nodes join the cluster-heads and form the clusters. In order to reduce the amount of information transmitted to the base station, the cluster-heads collect and aggregate data captured by other nodes in the cluster in one package and send it to the base station.

LEACH is divided into rounds and each round consists of two phases: the configuration phase, “setup phase” and the transmission phase “steady phase”. During the set-up phase, the cluster-head are elected and clusters are formed. Each node chooses a random number between 0 and 1. If the value is less than a threshold T(n), the node becomes the cluster-head. The threshold is defined as:

where p is the percentage of desired clusters, r is the current round, G represents the set of nodes that have not yet been elected as cluster-head (CH) about the 1/p last rounds.

The CHs inform their neighborhood that they become CH. Then the non-CH nodes join the closest CHs to form a cluster.

During the steady phase the nodes send data to the CH of the cluster they belong. The cluster-head aggregates the received data and sends the aggregated packet to the base station. At the beginning of the steady phase, a scheduling TDMA (Time Division Multiple Access) is used to assign to each node a slot time for transmitting its data. In order to save energy, non-CH nodes are active only during their transmission time, the rest of the time they put on standby their radio. The cluster-head is constantly active to receive data from his cluster members. At the end of around, another round starts with a new “set up phase”. Nodes that were cluster-head during the preceding round cannot be reelected again.

Subsequently, several LEACH improvements have been proposed including LEACH-C [7] , LEACH-V [8] LEACH-R [9] , LEACH-M [10] , etc. However, heterogeneous clusters size problem remains. Indeed, as the cluster formation algorithm is probabilistic, it generates clusters of different sizes. There may be in the same network “big” and “small” clusters. In some cases, there may be single clusters composed of only one node which is the CH. Single CH directly send their data to the base station. This situation can quickly drain the battery of nodes and reduce the network lifetime.

3. Impact of Single Nodes on Energy Consumption of LEACH Protocol

For modeling impact of single nodes on energy consumption in LEACH protocol, we use the same model of energy consumption for wireless transmissions as described in [2] . Let us consider a node transmitting a k bit message over a distance, the consumer model is:

(1)

For the node receiving the k bit messages, the energy consumption is:

(2)

where Eelec is the energy consumed by the transmitter and receiver circuit. In Equation (1), if the distance between the transmitting and the receiving node is below a threshold d0 using the free space model, we use multipath model and therefore and represents the transmission amplifiers.

During the “setup phase”, nodes are randomly grouped into clusters. In some cases, single cluster appears. Single clusters send their information directly to the base station during the entire round. As BS is distant from the node, the energy consumption is higher. To get an idea of the average energy consumed by single cluster, we simulate a sensor network and use LEACH as routing protocol. We collect the energy consumption of all nodes and made a comparison between the energy consumption of CH, single CH and simple nodes that are cluster members. The energy consumption model used is the same as in the LEACH protocol.

Figure 2 shows the average energy consumption of nodes compared to single CH and simple nodes. Simulation results show that the single CH node on average consumes 10 times more than the simple node because they

Figure 2. Comparison of the average energy consumption of cluster-heads, single CH and simple nodes.

directly send their data to the base station. They are also active anytime while simple nodes send over smaller distances (to their cluster-head) and are active just during their transmission time. After, they return on standby the rest of the time. The CHs consume 44% more energy than single CH due to the collection and aggregation of cluster member’s information.

Let’s define NRG1 and NRG2 the overall energy consumption of the network in case 1) and case 2) of Figure 3:

Let’s define diff, the difference between NRG1 and NRG2 by

(3)

By developing and reducing Equation (3) and supposing that the amount of the energy consumed by CH in both cases is basically the same we obtains the following expression:

where Eelec is the energy dissipated per unit of information transmitted or received, is the energy dissipated by the cluster-head to aggregate the collected data and is the energy dissipated per unit of information and length, is the distance from the CH to the BS.

If is higher than a threshold diff becomes positive then NRG1 is greater than NRG2. Hence, LEACH protocol uses less power when removing single clusters.

The results of the previous section show that single clusters unnecessarily consume energy by sending directly information to the BS. LEACH-based SNCR solves this problem by integrating the single CH in another cluster and reduces the energy consumption. When the single CH joins a cluster, it becomes a simple node.

So we established the LEACH-based SNCR protocol that uses SNCR mechanism (Single Cluster Node Reduction) [11] . The idea is to detect at the beginning of each round all single clusters and integrate them into other clusters ensuring a balanced distribution of energy.

(a) (b)

Figure 3. Comparison of the energy consumption of two sensor network: one with singleton and the other one without singleton. (a) Network of two clusters with one singleton; (b) Network with one cluster and no singleton.

4. LEACH-BASED-SNCR

The SNCR described in [11] reduces single clusters in wireless sensor networks. The algorithm works as follows: the CH initialize a timer called WT (Wait Time) which is inversely proportional to its degree of connectivity. At the end of the WT timer, the CH informs its neighbors by sending them a message “CH_INFORM_MSG”. Then simple nodes receiving the message select the sender as CH while the CH stores it in a “SRC_INFORM_MSG” list. Finally a single CH recognizes itself that his message “CH_INFORM_MSG” is not transmitted. It then inspects his “SRC_INFORM_MSG” list. If the list is not empty, it selects the first node of the list as CH. After performing these steps, single CH joins other clusters.

In order to minimize the energy consumption of each micro-sensor and to generally increase the lifespan of the network, we propose the LEACH-based SCNR algorithm whose originality is based on integrating singleton in existing cluster. The LEACH-based SNCR algorithm also provides an energy balance through the network nodes. Once all data are gathered, the cluster-head aggregates them and sends them to a base station.

We make the following assumptions:

• Nodes are uniformly distributed over the capture zone.

• Nodes and the base station are fixed.

• All nodes can communicate directly with the base station.

• Sensors send at fixed rates and still have data to transmit to the BS.

• Communication is symmetric.

We use the technique described by SNCR to reduce single clusters in LEACH. We work with the centralized version of LEACH called LEACH-C where the BS is in charge of creating clusters and inform the sensor status. This choice is justified by the fact that BS has greater computing power and avoids the emission control packets.

In LEACH-C, each node sends its information position and energy level, to BS. The latter is in charge of forming clusters by following the same steps as in the version distributed LEACH. Once determined clusters, the BS sends to each node status and the cluster to which it belongs.

The main idea is to transform the single CH into simple node by integrating them into an existing cluster. In the LEACH-based SNCR protocol, the BS checks the number of sensors per cluster and if it detects a single cluster it assigns it to the nearest cluster. Then it sends the information to the sensors. Singletons and clusters are eliminated. Centralized LEACH allows better control topologies and formation of clusters in sensor networks.

5. Experiments and Results

In this section, we present the experimental results obtained with LEACH and LEACH-based-SNCR. We compare LEACH-based SCNRO to LEACH because of its energy efficiency concern.

5.1. Conditions Simulations

To evaluate the performances of LEACH-based SNCR, we perform some simulations under the Omnet++ simulator. In order to use a realistic model for transmitting and receiving costs we consider the Texas Instruments CC2420 ZigBee1 wireless module as sensor network. These sensor nodes consume 0.77 mW when idle, 35.46 mW for receiving (Rx), and 31.32 mW for transmitting (Tx). When a cluster-head receives data from a child, it stores them until it needs to send its own data and then sends the aggregated data to its base station

The network is composed by 100 nodes spread over an area of 100 × 100 m. Each node has an initial energy of 0.5 J. We run the simulation 1000 times to have reliable results. The parameters used in the simulations are summarized in Table 1.

5.2. Comparison-Based LEACH and LEACH-SNCR

The simulation conditions are the same as described above in Table 1. In this section we make a detailed comparison between LEACH and LEACH-based SNCR. The average of simulations is used to generate these results. We define the network lifetime as the time until 50% of all initial nodes die.

Figure 4 represents the total number of nodes “dead” in the network with LEACH and LEACH-based protocols-SNCR. This figure shows that for the two protocols, nodes energy deplete at the same rate until round 90. Towards the 100th round, we note that the number of dead nodes in LEACH is greater than LEACH-based SNCR. The simulation stops on average round 109 and 117. LEACH-based-SNCR provides life extension of 15% higher than LEACH due to integration of singleton in existing cluster.

Figure 5 gives the overall consumption of the network in each round. Their consumption is almost similar but we realize that LEACH-based-SNCR has a lifespan higher than LEACH.

To further emphasize the difference in energy consumption Figure 6 shows the difference in energy consumption between LEACH and LEACH-based SNCR-based at each the round. We note that this energy saving is most notable between rounds 64 and 100. This is due to the fact that at this stage the number of alive nodes decreases and the probability of having single cluster increases. By integrating the single CH in existing clusters and turning them into simple nodes, the overall energy consumption of the network decreases.

Figure 4. Number of dead nodes according to rounds.

Table 1. Simulations parameter.

Figure 5. Energy consumption according to round.

Figure 6. Energy gain of LEACH-based SNCR over LEACH according to rounds.

Initial energy available in the network is 50 J (0.5 J per node). Sensors consume energy during sending and reception. Simulations stopped when the number of dead reached 50% of all initial nodes. The residual energy of the system is the total energy of the remaining 50% of other live nodes. The results show that the residual energy of LEACH-based SNCR is less than 32% compared to LEACH because LEACH-based SNCR distributes more evenly the energy consumption. This situation shows that LEACH-based SNCR operates better in the network by extending lifetime and balancing the energy consumption among sensor nodes.

6. Conclusions and Future Works

LEACH is a probabilistic protocol that randomly forms clusters. Sometimes, LEACH generates single clusters. These single clusters directly send the collected information to the remote BS and consume uselessly energy. In this paper, we have introduced the LEACH-based SNCR which solves the problem of single cluster without generating supplementary control packets overhead. LEACH-based SNCR simply integrates the single CH in another cluster and reduces the overall energy consumption over the network and provides energy balancing among nodes.

Our future plans include extending our proposed routing scheme to the mobility scenarios in Wireless Sensor networks. We will also extend the comparison of LEACH-based SNCR with other similar algorithms like BLAC [12] and use other energy models.

Cite this paper

Yaye Mbekhe Sarr,Cheikh Sarr,Bamba Gueye, (2015) Reduction of Single Clusters in LEACH Protocol for Wireless Sensor Networks. Open Access Library Journal,02,1-8. doi: 10.4236/oalib.1102251

References

  1. 1. Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422.

  2. 2. Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Vol. 2, 10.

  3. 3. Lindsey, S. and Raghavendra, C.S. (2002) PEGASIS: Power-Efficient Gathering in Sensor Information Systems. Aerospace Conference Proceedings, 3, 3-1125-3-1130.
    http://dx.doi.org/10.1109/AERO.2002.1035242

  4. 4. Manjeshwar, A. and Agrawal, D.P. (2001) TEEN: A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks. Proceedings of 15th International Parallel and Distributed Processing Symposium, San Francisco, 23-27 April 2001, 189.

  5. 5. Frey, H., Rührup, S. and Stojmenović, I. (2009) Routing in Wireless Sensor Networks. In: Misra, S.C., Woungang, I. and Misra, S., Eds., Guide to Wireless Sensor Networks, Springer, London, 81-111.
    http://dx.doi.org/10.1007/978-1-84882-218-4_4

  6. 6. Singh, S.K., Singh, M.P. and Singh, D.K. (2010) A Survey of Energy-Efficient Hierarchical Cluster-Based Routing in Wireless Sensor Networks. International Journal of Advanced Networking and Application (IJANA), 2, 570-580.

  7. 7. Heinzelman, W.B., Chandrakasan, A.P. and Balakrishnan, H. (2002) An Application-Specific Protocol Architecture for Wireless Microsensor Networks. IEEE Transactions on Wireless Communications, 1, 660-670.
    http://dx.doi.org/10.1109/TWC.2002.804190

  8. 8. Ahlawat, A. and Malik, V. (2013) An Extended Vice-Cluster Selection Approach to Improve V LEACH Protocol in WSN. 2013 3rd International Conference on Advanced Computing and Communication Technologies (ACCT), Rohtak, 6-7 April 2013, 236-240.

  9. 9. Li, Y.-Z., Zhang, A.-L. and Liang, Y.-Z. (2013) Improvement of LEACH Protocol for Wireless Sensor Networks. 2013 3rd International on Conference Instrumentation, Measurement, Computer, Communication and Control (IMCCC), 21-23 September 2013, 323-326.

  10. 10. Mhatre, V. and Rosenberg, C. (2004) Homogeneous vs Heterogeneous Clustered Sensor Networks: A Comparative Study. 2004 IEEE International Conference on Communications, Vol. 6, 3646-3651.

  11. 11. Diallo, C., Marot, M. and Becker, M. (2010) Single-Node Cluster Reduction in WSN and Energy-Efficiency during Cluster Formation. 9th IFIP Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net), Juan Les Pins, 23-25 June 2010, 1-10.

  12. 12. Ducrocq, T., Mitton, N. and Hauspie, M. (2013). Energybased clustering for wireless sensor network lifetime optimization. 2013 IEEE Wireless Communications and Networking Conference (WCNC), Shanghai, 7-10 April 2013, 968-973.
    http://dx.doi.org/10.1109/WCNC.2013.6554695

NOTES

*Corresponding author.

1http://www.ti.com/lit/ds/symlink/cc2420.pdf