Energy Efficient Low Energy Adaptive Clustering Hierarchy (LEACH) Protocol: A Survey

Energy Efficient Low Energy Adaptive Clustering Hierarchy (LEACH) Protocol: A Survey

Nishita Payar

Department of Wireless and Mobile Computing GTU PG-School, BISAG

Gandhinagar, India

Prof. Chandresh R. Parekh

Department of Electronics and Communication Government Engineering College-Sector 28 Gandhinagar, India

Abstract A wireless sensor network consists of hundreds and/or thousands of homogenous and/or heterogeneous nodes that are able to interact with environment and sense data. As these networks are energy constrained, energy efficiency in routing is crucial research issue nowadays. Many flat and hierarchical protocols have been proposed to improve the network lifetime. Low Energy Adaptive Clustering Hierarchy (LEACH) protocol is a well known energy efficient hierarchical routing protocol in WSN. In LEACH, nodes are divided into clusters and cluster heads for clusters are selected. Nodes send their data to respective cluster head and the cluster head is responsible to send the collected and aggregated data directly to the sink. This paper evaluates the performance of the LEACH protocol and gives an improvement to it for energy efficiency. The proposed protocol considers many parameters like residual energy and distance from base station etc. for cluster head selection and energy efficient routing.

KeywordsWireless sensor network, LEACH, Cluster head

1. INTRODUCTION

   Wireless Sensor Networks (WSNs) are similar as mobile ad-hoc networks (MANET) with some more features and constraint like limited energy capacity, non-rechargeable battery life and low memory capacity. Thus wireless sensor network originated as a battlefield surveillance application. Earlier routing protocols did not require point to point communication. Nowadays, the field has been growing with new potential in industrial, health and other monitoring applications and so is the need for more efficient routing algorithms. Due to limited memory and more power consumption, programmers need to consider these two challenges while designing wireless sensor networks. Wireless sensor networks are application specific and nodes has responsibility to sense collect aggregate data and send it further towards the destination. So the routing protocols of WSNs should be such to fulfill these responsibilities. The main characteristics of good routing protocol are awareness of energy, scalability in energy constrained and bandwidth constrained environment, adaptability in limited memory environment. Due to energy constraint in WSN, clustering routing protocols are more important. They are scalable and more energy efficient and easy to manage than direct communication and flat routing protocols.

2. LOW ENERGY ADAPTIVE CLUSTERING

   HIERARCHY (LEACH)

   Low Energy Adaptive Clustering Hierarchy (LEACH) is a clustering-based protocol that utilizes randomized rotation of the cluster-heads to evenly distribute the energy load among the sensor nodes in the network [2]. The protocol is presented by Heinzelman et al. [1]. In this protocol a dense network of homogeneous, energy constrained nodes. These nodes are responsible to send their data to a sink node. In this protocol, TDMA based MAC protocol is integrated clustering approach. In LEACH nodes are divided into clusters. Each cluster consists of a cluster-head which is responsible for creating and maintaining a TDMA schedule, and all other nodes are treated as member nodes. TDMA schedules are assigned to all member nodes. This schedule can be used to exchange data between member and the cluster-head. Member nodes within cluster send data to their CH and cluster-head sends this aggregated data to the sink.

   Figure 1: Organization of LEACH rounds [1]

   LEACH protocol is organized into rounds. Each round is sub-divided into two phases, set-up phase and steady- state phase. A set-up phase is followed by steady state phase. The setup phase starts with the self-election of nodes to cluster-heads. In the following advertisement phase, the cluster-heads inform their neighborhood with an advertisement packet. The cluster-heads contend for the medium using a CSMA protocol with no further provision against the hidden-terminal problem. The non-cluster-head nodes pick the advertisement packet with the strongest received signal strength. In the following cluster-setup

   phase, the members inform their cluster-head (join), again using a CSMA protocol. After the cluster setup- phase, the cluster-head knows the number of members and their identifiers. It constructs a TDMA schedule, picks a CDMA code randomly, and broadcasts this information in

   It is given by:

   T(n) = 1

   1( (1/))

   if n G [4]

   the broadcast schedule sub-phase. After this, the TDMA steady-state phase begins. Because of collisions of advertisement or join packets, the protocol cannot guarantee that each non-cluster-head node belongs to a cluster. However, it can guarantee that nodes belong to at most one cluster.

   The cluster-head is switched on during the whole round and the member nodes have to be switched on during the setup phase and occasionally in the steady-state phase, according to their position in the clusters TDMA schedule.

   With the protocol described so far, LEACH would not be able to cover large geographical areas of some square miles or more, because a cluster-head two miles away from the sink likely does not have enough energy to reach the sink at all, not to mention achieving a low BER. If it can be arranged that a cluster-head can use other cluster-heads for forwarding, this limitation can be mitigated.

   LEACH protocol is energy efficient than the previous protocols but still, the protocol suffers from some deficiencies mentioned below:

   • It assumes that every node can communicate with each other and are able to reach sink, which is not possible for large network.

   • The LEACH protocol elects CH randomly without considering the residual energy of nodes. So it may possible that some nodes may drain out their energy very quickly.

   • Each CH directly communicates with BS no matter how far it is located.

     where G is the set of nodes that are involved in the CH election. T is a threshold function for n (n is the current number of round). Then CH broadcasts advertisement message and further procedure is followed. LEACH is more energy efficient than previous flat routing protocols. In order to make LEACH more energy efficient many solutions have been proposed, the summary of that literatures is given below.

     Enhanced Cluster head Selection Algorithm Using LEACH

     Rudranath Mitra and Anurupa Biswas [3] proposed the solution for the problem of uneven CH distribution where WSNs are deployed randomly in density. They gave the example that if the CH lies at a distant position from the majority of nodes. So to communicate between CH & sensor nodes, since the distance between them is high, energy consumption for the communication is also high. That means, the higher the distance between CH & sensor nodes the greater the energy consumption. For this, the authors have proposed following scheme to choose CH [3].

     Select the CH in the dense node zone. As if nodes are near to the CH, energy consumption is less. They concentrated that the CH should be at optimum distance from the surrounded clusters CH, that is means the distance between them should be balanced or on average. So, energy consumption will be in control.

     Rudranath Mitra and Anurupa Biswas Proposed Mathematical formula [3]:

   • The size of cluster is different, so it may possibe that CH

     1 _

     _

     in highly dense area may consume more transmission energy.

     As energy is a scarce resource in WSN, the main aspect while designing routing protocol is always how to

     1 ( (1/))

     Where:

     _

     _ _

     minimize the energy consumption and thereby improving network lifetime.

3. RELATED WORK

   The LEACH is the most representative routing protocols among hierarchical protocols, whose purpose is to balance the energy consumption of all nodes and thereby to increase the lifetime of network. LEACH randomizes the selection of cluster-heads so energy load is balanced among the network and the lifetime is increased. LEACH uses the following strategy to elect CH.

   A sensor node chooses a random number, r, between 0 and 1. Let a threshold value be T(n). If this random number is less than a threshold value, T(n), the node becomes a cluster-head for the current round. The threshold value is calculated based on an equation that incorporates the desired percentage to become a cluster-head (p), the current round, and the set of nodes that have not been selected as a cluster-head in the last (1/P) rounds, denoted by G.

   En_current is the current amount of energy En_max is the initial amount of energy

   Davg is the average distance from all other nodes in the cluster

   Einter_node is the distance between any two nodes in the cluster

   Dch_avg is the average distance from the node to the neighboring CHs

   Dcentre_avg is the average distance of the neighboring CHs from the centre of the cluster

   The advantages of the proposed scheme are as follows:

   • Optimizes the distance between head nodes and other nodes, and thereby reduces energy consumption and chances of loss of signal strength.

   • Optimizes the distance between the inter CH nodes, thus optimizing the communication between head nodes and central server.

   • The new approach selects the optimized node as head node which has the minimal cost in terms of energy while communicating with other nodes, thus increasing the lifetime of the network.

   Enhanced Leach Protocol to Increase Network Life Time:

   Sonu Vashist and Jitender Khurana [5] discussed the characteristics of WSNs in their paper, data flow in clustering network of WSNs and different clustering routing protocols. They focused on network lifetime with LEACH. They concluded that while routing theres an extra overhead due to network routing redundant messages and running redundant sensors.

   As a solution Sonu Vashist and Jitender Khurana proposed that in the 2nd round, each node would send residual energy along with the sending time stamp T- S(sending time stamp of last data packet) and the remaining lifetime of battery. When the BS receives the packet, it will calculate T-R (receiving time stamp of last data packet at BS) – T-S (the difference between receiving timestamp and current time stamp). Then if difference > = remaining lifetime of node the node will become=CH otherwise if remaining lifetime = max among all nodes of the cluster choose the node as CH. It is then concluded that the proposed protocol improves network lifetime.

   Enhancing the Performance of LEACH Protocol:

   Yun Li, Nan Yu, Weiyi Zhang, Weiliang Zhao, Xiaohu You and Mahmoud Daneshmand [6] investigated on how many frames should be optimum in the time slot to improve the performance of LEACH. They concluded with investigation and simulation that that m=5 is good for tradeoff between lifetime and throughput.

   A Location Based Clustering Algorithm:

   Lin SHEN and Xiangquan SHIA [7] have analyzed the LEACH protocol. They assumed the precondition in this paper, that is, CHs are very closely located and the distance between them becomes negligible. Then they identified one loop-hole that when multiple CHs are randomly selected within a small area, a big extra energy loss occurs. The amount of lost energy is approximately proportional to the number of CHs in the area. In order to solve that, they gave the idea of CH selection on temporal distribution. The formula to elect CH in the paper was as follows [7]:

   They concluded that the lifespan of the new progressive clustering protocol is longer than that of the original LEACH protocol. The data transferred with the new protocol is 1/3 more than that with the old protocol, and the lifespan of the network with the new protocol is almost doubled compared with that of the old protocol.

   Figure 2: Comparison of the lifetime of two protocols [7]

   A REFORMED CLUSTER-HEAD OF LEACH:

   J.R.BHADESHIYA and V. S.VORA [8] concentrated on the issue of number of CH within the network is discussed. The authors have given that the number of cluster-head nodes is the prerequisite to implement clustering, LEACH protocol has not given the numerical computation method to determine the number of cluster-head nodes explicitly. The cluster-head selection is depending on the selection of random number from 0 to 1. If the threshold value for the node is more than the random number then the node can become a cluster-head for the current round. J.R.BHADESHIYA and V. S.VORA gave the idea to improve the conventional protocol by limiting the number of CHs per round or in other words dividing the area into the finite number of grids. They analyzed that the case with 4% cluster-head, 5% cluster-head. In case of 4% & 5% CH per round 4% nodes & 5% nodes will announced for cluster-head for current round in cluster rest of nodes in the cluster will join them for the current round. In each round CH will be fixed (4% or 5% of) and all other nodes in the cluster are cluster nodes. They obtained the solution that fixed number of cluster will improve the life span of the cluster because in every round only 4% nodes & 5% nodes will be selected as cluster-head so rest of nodes transfer to data to only those 4% cluster-head. After analyses and simulation it has been concluded in the paper that an improved protocol based on LEACH, Modified LEACH with 4% & 5% Cluster-head protocol is presented in this paper Modified LEACH (4% CH) protocol indicates the optimal number of CHs in a network and considers residual energy in the stage of cluster-heads selection. Simulation results of the paper show that the modified LEACH (4% CH) can extend lifetime and reduce the energy consuming, it has better performance than LEACH protocol.

   Energy Efficient Routing Protocol:

   H.Srikanth.Kamath [9] discussed the functionality of LEACH protocol. He pointed that random CH selection is less energy efficient and then he introduced the new scheme of CH selection, in which residual energy of the node is considered. H.Srikanth.Kamath gave the new equation of T (n) for CH selection is as follows [9]:

   Where Eresidual is the residual energy of node, Eo is the initial energy of node, is the number of consecutive rounds during which a node has not been cluster-head by far. When elected as cluster-head, the value of for that node is reset to 0. This threshold ensures nodes of higher residual energy have a greater chance of becoming a cluster-head, which balances the energy consumption of the network. H.Srikanth.Kamath also suggested the concept of relay node, and introduced new protocol named LEACH-R has been introduced in the paper. This due to the energy saved in transmission by the improvement of cluster-head selection and the R (relay) node.

   Assisted-Leach (A-Leach) Energy Efficient Routing Protocol for Wireless Sensor Networks:

   Sunkara Vinodh Kumar and Ajit Pal [11] presented a new idea of helper nodes in the above paper in which, the member nodes send their sensed data to the CH. CH aggregates these data and sends it further to helper node which routes this data to the next hop helper node towards BS. The design for this protocol operation is shown in Figure 3

   Figure 3: Design for protocol operation of A-LEACH [11]

   By proposingthis protocol, the authors have found that by using next hop helper nodes the overhead of route formulation to BS is reduced. Furthermore, the network lifetime is improved by distributing the minimized energy dissipation throughout the nodes

   Objective and analyses

   While literature review, it has been analyzed that a conventional LEACH protocol suffers from the problem of random CH selection and uneven CH distribution. From this analysis and as energy is a very crucial resource in WSNs the future work will be concentrated on how to make conventional LEACH protocol more energy efficient and balance energy consumption within the network. The concentrated parameter of this proposed work is the residual energy of the nodes and the distance between CHs. The proposed work will focus on conventional LEACH protocol. The conventional LEACH protocol will be analyzed and area of improvement will be focused to make it energy efficient. For analyses, improvement and simulation Castalia simulator will be used.

   Proposed scheme

   To overcome the above mentioned deficiencies, a new scheme for LEACH protocol is proposed in which following assumptions have been made:

   1. All nodes are homogeneous.

   2. All nodes are having same initial energy level when the network is deployed.

   3. All nodes in the network are static.

   4. The sink node is wired and far away from the network, so there isnt any issue regarding the energy level of sink

   The main objective of the proposed scheme is as follows:

   1. To select the CH based on residual energy to avoid the CH failure.

   2. To maintain the distance between the CH so that the protocol can be optimized for energy consumption.

   3. To improve the network lifetime

   Now, by taking the above assumptions into account, the following scheme have been proposed.

   Each rounds of the improved algorithm of LEACH are of

   Tr time and has the following phases.

   Set up Phase

   In the first round of the set up phase, the CH selection will be same as the conventional LEACH protocol. It means a sensor node chooses a random number, r, between 0 and 1. If this random number is less than a threshold value, T(n), the node becomes a cluster-head for the current round. The threshold value is calculated based on an equation that incorporates the desired percentage to become a cluster- head, the current round, and the set of nodes that have not been selected as a cluster-head in the last (1/P) rounds, denoted by G.

   It is given by:

4. PROBLEM STATEMENT AND PROPOSED SOLUTION

   T(n) = 1

   1( (1/))

   if n G [4]

   Many literatures have been published in order to improve energy efficiency using different techniques but still according to LEACHs deficiencies level of energy remains unbalanced. This is because the CH sends data directly to the sink. So if the CH is far away from the sink, it will consume more transmission power to send data directly to sink.

   where G is the set of nodes that are involved in the CH election.

   From the second round of set up phase of the proposed LEACH protocol, the residual energy and the distance between the nodes will be considered and CH will be

   selected such that they have more energy as compared to other nodes and they are evenly distributed.

   Steady State Phase

   The steady state phase of the proposed LEACH protocol will be same as of the conventional LEACH protocol.

5. SIMULATION AND FUTURE WORK

   After reviewing the earlier literatures on LEACH protocol, the above strategy is proposed for improvement in conventional LEACH protocol. Castalia simulator and Omnet++ will be used to implement the algorithm and studying various aspects of the simulator to have a grip on that. The future work will be concentrated on implementing this algorithm in Castalia simulator and simulating the results.

6. CONCLUSION

Routing in WSN is very different than the wired network. Its challenges has got a lot of attention and opened wide doors for research. In the matter of WSNs, energy is main issue while considering the routing. In the research so far it has given that LEACH is energy efficient than the previous routing protocols. And still it could be more energy efficient. The focus of the future work will be to make LEACH energy efficient by considering residual energy and distance between the CHs and thereby to improve network lifetime of the wireless sensor network.

ACKNOWLEDGMENT

I am very grateful to my family members, friends and faculties who have always helped and supported me throughout this journey of my study and research.

REFERENCES

1. holger Karl, Andreas Willing, PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS, Wiley Student Edition

2. Qiangfeng Jiang, D. Manivannan, Routing Protocols for Sensor Networks

3. Rudranath Mitra, Anurupa Biswas, Enhanced Clusterhead Selection Algorithm Using LEACH Protocol for Wireless Sensor Networks, International Journal Of Computational Engineering Research, May-June 2012

4. Jamal N. Al-Karaki Ahmed E. Kamal , Routing Techniques in Wireless Sensor Networks: A Survey

5. Sonu Vashist, Jitender Khurana, Enhanced Leach Protocol to Increase Network Life Time, International Journal of Emerging Technology and Advanced Engineering, June 2013

6. Yun Li, Nan Yu, Weiyi Zhang, Weiliang Zhao, Xiaohu You, Mahmoud Daneshmand, Enhancing the Performance of LEACH Protocol in Wireless Sensor Networks, IEEE INFOCOM 2011 Workshop on M2MCN, 2011,

7. Lin SHEN, Xiangquan SHIA, Location Based Clustering Algorithm for Wireless Sensor Networks, international journal of intelligent control and systems, spetermber-2008

8. Mr. J.R.bhadeshiya, Prof. V. S.vora, a reformed cluster-head of leach protocol and performance analysis with conventional routing protocol for wsn, journal of information, knowledge and research in electronics and communication engineering, october-2013

9. H.Srikanth.Kamath, Energy Efficient Routing Protocol for Wireless Sensor Networks, International Journal of Advanced Computer Research, June-2013

10. S. G. Shiva Prasad Yadav, Dr. A. Chitra, Wireless Sensor Networks – Architectures, Protocols, Simulators and Applications: a Survey, International Journal of Electronics and Computer Science Engineering

11. Sunkara Vinodh Kumar, Ajit Pal, Assisted-Leach (A-Leach) Energy Efficient Routing Protocol for Wireless Sensor Networks, International Journal of Computer and Communication Engineering, July-2013