A Survey on LEACH and its Variant in Wireless Sensor Network 1st Bhavya R Patel, 2nd Jignesh patel 1st PG Student, 2nd Asst.Prof. 1st Computer Engineering, 2nd Computer Engineering S.R.Patel Engineering College, Unjha, Mehsana,India 1bhavyapatel9@gmail.com, 2 jigneshpatel.er@gmail.com __________________________________________________________________________________________________________
Abstract-Sensor webs consisting of nodes with limited battery power and wireless communications are deployed to collect useful information from the field. Gathering sensed information in an energy efficient manner is critical to operate the sensor network for a long period of time. A data collection problem is defined where, in a round of communication, each sensor node has a packet to be sent to the distant base station. If each node transmits its sensed data directly to the base station then it will deplete its power quickly. Since wireless communications consume significant amounts of battery power, sensor nodes should spend as little energy as possible receiving and transmitting data. It is necessary for communication protocols to maximize nodes' lifetimes, reduce bandwidth consumption by using local collaboration among the nodes, and tolerate node failures. Most of the work in energy efficient data gathering application is motivated by LEACH by allowing rotation of cluster head for load distribution. In this paper, we have presented several existing methods for energy efficient cluster head selection in wireless sensor network.
I. INTRODUCTION
Modern wireless sensor networks are made up of a large number of inexpensive devices that are networked via low power wireless communications. It is the networking capability that fundamentally differentiates a sensor network from a mere collection of sensors, by enabling cooperation, coordination, and collaboration among sensor assets. Harvesting advances in the past decade in microelectronics, sensing, analog and digital signal processing, wireless communications, and networking, wireless sensor network technology is expected to have a significant impact on our lives in the twenty-first century. Proposed applications of sensor networks include environmental monitoring, natural disaster prediction and relief, homeland security, healthcare, manufacturing, transportation, and home appliances and entertainment. Sensor networks are expected to be a crucial part in future military missions, for example, as embodied in the concepts of network centric warfare and network-enabled capability. Wireless sensor networks differ fundamentally from general data networks such as the internet, and as such they require the adoption of a different design paradigm. Often sensor networks are application specific; they are designed and deployed for special purposes. Thus the network design must take into account the specific intended applications. More fundamentally, in the context of wireless sensor networks, the broadcast nature of the medium must be taken into account. For battery-operated sensors, energy conservation is one of the most important design parameters, since replacing batteries may be difficult or impossible in many applications. Thus sensor network designs must be optimized to extend the network lifetime. The energy and bandwidth constraints and the potential large-scale deployment pose challenges to efficient resource allocation and sensor management. The constraint most often associated with sensor network design is that sensor nodes operate with limited energy budgets.
Typically, they are powered through batteries, which must be either replaced or recharged (e.g., using solar power) when depleted. For some nodes, neither option is appropriate, that is, they will simply be discarded once their energy source is depleted. Whether the battery can be recharged or not significantly affects the strategy applied to energy consumption. For non-rechargeable batteries, a sensor node should be able to operate until either its mission time has passed or the battery can be replaced. The length of the mission time depends on the type of application, for example, scientists monitoring glacial movements may need sensors that can operate for several years while a sensor in a battlefield scenario may only be needed for a few hours or days. As a consequence, the first and often most important design challenge for a WSN is energy efficiency. The rest of the paper is organized as follows: Section II describes unique constraints and challenges in wireless sensor networks. Section III describes LEACH and its variations. Finally conclusion is presented in last section.
II. UNIQUE CONSTRAINTS AND CHALLENGES The challenges we face in designing sensor network systems and applications include the following: • Limited hardware: Each node has limited processing, storage, and communication capabilities, and limited energy supply and bandwidth. • Limited support for networking: The network is peer-to-peer, with a mesh topology and dynamic, mobile, and unreliable connectivity. There are no universal routing protocols or central registry services. Each node acts both as a router and as an application host. • Limited support for software development: The tasks are typically real-time and massively distributed, involve dynamic collaboration among nodes, and must handle multiple competing events. Global properties can be specified only via local instructions. Because of the coupling between applications and system layers, the software architecture must be co-designed with the information processing architecture.
III. EXISTING METHODS FOR CLUSTER HEAD SELECTION
LEACH Protocol[1][2]
Low Energy Adaptive Clustering Hierarchy (LEACH) protocol has attracted intensive attention because of its energy efficient, simplicity and load balancing properties. LEACH is a cluster based protocol. The numbers of cluster heads and cluster members generated by LEACH are important parameters for achieving better performance. LEACH organizes nodes into clusters with one node from each cluster serving as a cluster-head (CH). It randomly selects some predetermined number of nodes as cluster heads. CHs then advertise themselves and other nodes join one of those cluster heads whose signal they found strongest (i.e. the CH which is nearest to them). In this way a cluster is formed. The CH then makes a Time Divison Multiple Access (TDMA) schedule for the nodes under its cluster. The communication between different clusters is done through CHs in a Code Divison Multiple Access (CDMA) manner. The CHs collect the data from their clusters and aggregate it before sending it to the other CHs or base station (BS). After a predetermined time lapse, the cluster formation step is repeated so that different nodes are given a chance to become CHs and energy consumption is thus uniformly distributed. LEACH protocol Operation can be divided into two phases: Setup phase and Steady phase.In the setup phase, the clusters are formed and a cluster-head (CH) is chosen for each cluster. While in the steady phase, data is sensed and sent to the central base station. The steady phase is longer than the setup phase. This is done in order to minimize the overhead cost. Drawbacks in LEACH:  It is not applicable to networks that are deployed in large region as it uses single hop routing where each node can transmit directly to the cluster head and the sink  The cluster heads used in the LEACH will consume a large amount of energy if they are located farther away from the sink.  It does not guarantee good cluster head distribution and it involves the assumption of uniform energy consumption for the cluster heads. So sometimes possible one cluster has many member node and in other very few member node.  It uses dynamic clustering which results in extra overhead .  The time duration of the setup phase is nondeterministic and the collisions will cause the time duration too long and hence the sensing services are interrupted. Due to that LEACH may be unstable during the setup phase that depends on the density of sensors.  LEACH does not support mobility nodes.
LEACH-C: (Centralized)[2] However, using a central control algorithm to form the clusters may produce better clusters by dispersing the cluster-head nodes throughout the network. This is the basis for LEACH-C (LEACH-Centralized), a protocol that uses a centralized clustering algorithm and the same steady-state protocol as LEACH (e.g., nodes send their data to the cluster-head, and the cluster-head aggregates the data and sends the aggregate signal to the base station).During the set-up phase of LEACH-C, each node sends information about its current location and energy level to the base station. While LEACH-C produces superior clusters to LEACH, there is a cost to using a centralized cluster formation algorithm compared to a distributed algorithm. This protocol requires a GPS or other location-tracking device on the nodes, and the start-up phase is more energy-intensive than the distributed approach since information from each node must be transmitted to the base station at the beginning of each round. LEACH-F (Fixed Cluster, Rotating Cluster-Head)
Adapting the clusters depending on which nodes are cluster-heads for a particular round is advantageous because it ensures that nodes communicate with the cluster-head node that requires the lowest amount of transmit power. In addition to reducing energy dissipation, this ensures minimum inter-cluster interference, as the power of an interfering message will be less than (or, at most, equal to) the power of the message the cluster-head is receiving. If, on the other hand, the clusters were fixed and only the clusterhead nodes were rotated, a node may have to use a large amount of power to communicate with its cluster-head when there is another cluster's cluster-head close by [3]. The advantage of fixed clusters is that once the clusters are formed, there is no set-up overhead at the beginning of each round. Depending on the cost for forming adaptive clusters, an approach where the clusters are formed once and fixed and the cluster-head position rotates among the nodes in the cluster may be more energy-efficient than LEACH. This is the basis for LEACH-F (LEACH with Fixed clusters). In LEACH-F, clusters are created using the centralized cluster formation algorithm developed for LEACH-C. The base station determines optimal clusters and broadcasts the cluster information to the nodes. This broadcast message includes the cluster ID for each node, from which the nodes can determine the TDMA schedule and the order to rotate the cluster-head position. Drawbacks:  New node can not be added.  Does not support mobilty  Do not adjust behavior on node dying.
Multi hop LEACH[4] The distance between the cluster head and the base station is increased enormously when the network diameter is increased beyond a certain level in which the scenario is not suitable for Leach routing protocol The energy efficiency of the protocol can be increased by using multi-hop communication within the cluster. It is a complete distributed clustering based routing protocol. Drawbacks:  Significant overhead to maintain network topology and medium access control.
LEACH-B [5] LEACH-B (Balanced) which proposes an enhanced version of LEACH by finding the number of CHs which are near optimal. In LEACH-B, there is a second stage for selecting CHs through considering the residual energy of candidate nodes to become CHs, which modifies the number of CH sat the set up phase considering the node’s residual energy. This protocol can save energy consumption by ensuring that the clusters are balanced. The optimal number of CHs is between 3 and 5 from total 100 nodes (3% - 5%). Drawbacks:  Extra overhead of electing cluster head
LEACH-V (VICE CH) The Vice-LEACH protocol in which the cluster contains a CH (which is responsible only for sending data that is received from the cluster members to the BS), a viceCH (the node that will become a CH in case the old CH dies), and cluster nodes (for gathering data from environment and send it to the CH). In the original leach, the CH is always on to receive data from cluster members, aggregate these data, and then send it to the BS that might be located far away from it[10]. The CH will die earlier than the other nodes in the cluster because of its operation of receiving, Sending and overhearing. When the CH dies, the cluster will become isolated because the data gathered by cluster nodes will never reach the base station. In V-LEACH protocol, besides having a CH in the cluster, there is a vice-CH that takes the role of the CH when the original CH dies. By doing that, data collected by the cluster nodes will always reach the BS. Therefore, no need to elect a new CH each time the CH dies. This will extend the overall network lifetime. Drawback:  Extra processing for selecting vice-CH. PEGASIS: Power-Efficient Gathering in Sensor Information System [7] The main idea in PEGASIS is for each node to receive from and transmit to close neighbors and take sums being the leader for transmission to the BS. This approach distributes the energy load evenly among the sensor nodes in the network. The author initially places the nodes randomly in the play field, and therefore, the i-th node is at a random location. The node will be organized to form a chain, which can either be accomplished by the sensor nodes themselves using a greedy algorithm starting from some node. Alternatively, the BS can compute this chain and broadcast it to all the sensor nodes. PEGASIS improves on LEACH by saving energy in several stages. First, in the local gathering, the distances that most of the nodes transmit are much less compared to transmitting to a cluster-head in LEACH. Second, the amount of data for the leader to receive is at most two messages instead of 20 (20 nodes per cluster in LEACH for a 100-node network). Finally, only one node transmits to the BS in each round of communication.
Energy Efficient Chain Based Routing [8] In the proposed protocol, the network is divided to a set of strips. It is assumed that “h” is height of each strip and there are “k” strips in the sensor network, computed by “k=L/h”, where “L” is length of wireless sensor network. In each strip, a chain is formed among the sensor nodes and a chain head is selected. In order to balance energy consumption among all sensor nodes in the network, the chain head’s role should be rotated among the sensor nodes to prevent their exhaustion.
CONCLUSION Sensor nodes are resource limited devices. Energy is very crucial for sensor networks. LEACH is completely distributed, requiring no control information from the base station. We have presented several existing energy efficient cluster head selection methods. Still it is an active research area. REFERENCES
[1] W. Heinzelman, A. Chandrakasan and H. Balakrishnan,”Energy-Efficient Communication Protocol for Wireless Micro sensor Networks,” Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS ’00), January 2000. [2] Wendi B. Heinzelman, Anantha P. Chandrakasan, Hari Balakrishnan; “An Application-Specific Protocol Architecture for Wireless Microsensor Networks”; IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 1, NO. 4, OCTOBER 2002 [3] Wendi B. Heinzelman “Application-Specific Protocol Architectures For WSN “Submitted To The Department Of Electrical Engineering And Computer Science In Partial Fulfilment Of The Requirements For The Degree Of Doctor Of Philosophy At The MASSACHUSETTS INSTITUTE OF TECHNOLOGY June 2000 [4] K.Ramesh, Dr.K.Somasundaram “A COMPARATIVE STUDY OF CLUSTERHEAD SELECTION ALGORITHMS IN WIRELESS SENSOR NETWORKS ” International Journal Of Computer Science & Engineering Survey (IJCSES) Vol.2, No.4, November 2011 [5] Mu Tong, Minghao Tang “LEACH-B:An Improved LEACH Protocol for Wireless Sensor Network” In IEEE International conference on Wireless Communications, 2010 [6] J.Gnanambigai, Dr.N.Rengarajan, K.Anbukkarasi “ Leach AND Its Descendant Protocols: A Survey” International Journal Of Communication AND Computer TECHNOLOGIES September 2012
[