Review on LEACH for Wireless Sensor Network

pp 27- 31

Pramod Sharma

Professor, Department of ECE, JIEM, Jaipur.

erpramodsharma@gmail.com

applications such as industrial process monitoring and control, environment and habitat monitoring, machine health monitoring, home automation, health care applications, nuclear reactor control, fire detection, object tracking and traffic control. Energy utilization and network life time are key issues in design of routing proto- cols for Wireless sensor network. LEACH is the first clustering routing protocol which is proven to be better compared to other such algorithms. TL-LEACH is one of the descendants of LEACH that saves better the energy consumption by building a two-level hierarchy. It uses random rotation of local cluster base stations to better distribute the energy load among the sensors in the network especially when the density of network is higher.

Key Words:  WSN, LEACH, TL-LEACH.

  1. INTRODUCTION

LEACH (Low-Energy Adaptive Clustering Hierarchy) is the first clustering routing protocol which is proven to be better compared to other clustering algorithms.  It is a distributed clustering algorithm, first proposed in 2000 by W. R. Heinzelman et al. [1]. The authors have suggested a hierarchical adaptive approach in which CHs are selected with a random probability independent of others to organize the nodes into clusters. TL-LEACH is one of the descendants of LEACH proposed by V. Loscri et al. in the year 2005[2], which introduces a two level hierarchy for cluster formation. It uses random rotation of local cluster base stations to better distribute the energy load among the sensors in the network, especially when the density of network is higher. As the clusters are adaptive in LEACH and TL-LEACH, poor clustering set-up during a round will affect overall performance.  However, using a central control scheme for cluster set-up may produce better clusters by distributing the cluster head nodes throughout the network.   In 2007 Taewook Kang et al. [3] proposed a centralized clustering algorithm, LEACH-C that realizes the above idea and provides better results through uniform distribution of CHs avoiding their redundant creation of in a small area. The main objectives of LEACH, was to find a way to low consumption of energy in the cluster and to improve the life time of WSN. EACH adopts a hierarchical and adaptive approach to organize the network into a set of clusters, managed by selected CHs. The CH carries out multiple tasks, such as periodic collection of data from the members of the cluster, aggregation of data to remove redundancy among correlated values, transmission of the aggregated data directly to the base station through a single hop method, creation and advertisement of a TDMA schedule. In the schedule created by the CH, each node of the cluster is assigned a time slot that can be used by non-CH nodes for transmission.   The CHs broadcast the schedule to their corresponding  cluster members. For reducing the likelihood of collisions among sensor nodes, LEACH nodes use a code division multiple accesses (CDMA) based scheme for communication. The network model used by LEACH is depicted in Figure1.

Figure 1: A Network Model of LEACH

Figure 2: Two Phases of LEACH

  1. OPERATIONS OF LEACH

The basic operation of LEACH consists of many rounds, each round being divided into two phases.  The phases of LEACH are illustrated in Figure 2. The first phase called the setup phase consists of three steps,

 (i)  Cluster head advertisement,

   (ii)  Cluster set-up and

(iii)  Transmission schedule creation.

The second phase, the steady-state phase, focuses on,

  • Data transmission to cluster heads,
  • Signal processing (data aggregation/ fusion) and
  • Delivery to the base station.

To minimize the protocol overhead, the duration of the setup phase is assumed to be relatively shorter than the steady-state phase. At the beginning of the setup phase, cluster-head selection takes place. The role of CH rotates among sensor nodes, thereby distributing energy consumption evenly across the network nodes. To  determine  if it  is its  turn to become a CH, a node n, generates  a random  number  x (between  0 and  1), and  compares  it with  the CH selection threshold T(n).

The node becomes a CH if it’s generated value, x, is less than T (n). The CH selection threshold, T (n) is aimed to ensure with high possibility that a predetermined fraction of nodes, P, should be elected as CHs at each round.  Further, the threshold ensures that the nodes, those have been CHs in last 1/P rounds, will not again be selected in the current round.  At the completion of the CH selection process, every node that is selected as a CH, advertises its new role to the rest of the network. Upon receiving the advertisements, each remaining node selects a cluster to join based on the received signal strength. Then the nodes inform their corresponding CHs of their desire to become a member of the cluster. Once the cluster is formed, each CH creates and distributes a TDMA schedule that specifies the time slots allocated to each member of the cluster for transmission. CHs also select CDMA code so as to reduce inter-cluster interference, which is then distributed to all members of its cluster [4].

The completion of the setup phase signals the start of the steady-state phase.  In this phase, nodes collect the required data and use their allocated slots to transmit those to the CH. Data collection is performed periodically. Then, the CH nodes receive all the data; aggregate them before sending to the base-station. The network goes back into the setup phase after a certain time, which is determined a priori.

Advantages and Drawbacks of LEACH:

Major advantages of LEACH include,

  • It incorporates data fusion into routing protocol.
  • It is 4-8 times effective over direct communication in prolonging the network lifetime.

Some drawbacks of LEACH are

  • It may lead to large number of clusters.
  • CHs are un-uniformly distributed in the network.
  • There is less number of data signals received at BS.
  • TL-LEACH

The main objectives of TL-LEACH was to find a way to minimize the consumption of energy than LEACH and hence to improve the life time of WSN.TL-LEACH uses the concept of data-fusion rigorously through a two-level hierarchy in order to avoid the overloading of data. Large energy gain can be resulted from data fusion, as less data is needed to be transmitted to the base station. TL-LEACH uses the following techniques to realise energy and latency efficiency: Randomized, adaptive and self-configuring cluster formation, Localized control for data transfer.

 TL-LEACH introduces a two-level hierarchy: a top level represented by cluster- head called primary cluster-head or master  cluster head (MCH), a second level represented by secondary cluster-head or CH and simple nodes.The two-level  hierarchy of TL-LEACH is shown in the Figure 3. In TL-LEACH, a partial local computation starts in each secondary CH and completes at primary CHs at the top level, from where data is transmitted to the base station directly.

Figure 3: A Network Model of TL-LEACH

  As LEACH, the basic operation of TL-LEACH consists of many rounds, each round being divided into two phases. In the setup phase initially each node decides if it wants to be, in current round, primary cluster-head (MCH), secondary cluster-head (CH) or simple node.  A node that has elected itself as MCH has to advertise other nodes.  The mechanism used in this phase is the CSMA. Subsequently CHs send the advertisement to the simple nodes.  In the cluster set-up step each CH decides which primary cluster it belongs to and each simple node decides its secondary cluster based on the received signal strength of advertisement, and both confirm their joining.  A MCH knows which nodes are in its group and creates a TDMA schedule, assigning each node a slot to transmit. It also chooses a CDMA code and informs all the nodes at the second level in its group to transmit using this code.  Each CH transmits the information to nodes in its cluster, both the code to be used use to transmit and the schedule. In the steady-state phase, each node transmits according  to the TDMA  schedule decided by its corresponding  primary CH. Non-CH nodes transmit data to their respective secondary  cluster heads. CHs retransmit the aggregate data to their respective primary cluster heads.  MCHs forward the fused data to the Base Station.

Advantages and Drawbacks of TL-LEACH:

Major advantages of TL-LEACH, include

  • The use of two-levels of clusters for data transmissions is advantageous as compared to LEACH because of the small transmit distances for more nodes. In this way only a few nodes are required to transmit through a long distances to the base station.
  • It incorporates improved data aggregation and fusion than LEACH.
  • Number of primary clusters in TL-LEACH is less, so it can be applied for larger networks.

Major drawbacks of TL-LEACH include,

  • It may lead to non-uniform distribution of CHs in the network.
  • of cluster heads formed in each round are not uniform, which may otherwise have increased the network lifetime to some extent.
  1. LEACH-C

The  main  objectives of LEACH-C  was to produce  better performance  in terms of energy  consumption,  by  dispersing  the cluster heads  throughout the network and hence to improve the life time of WSN. LEACH  is  distributed  cluster  formation  algorithm,   which  offers no  guarantee about the placement and number  of cluster  head  nodes. LEACH-centralized is a protocol that uses a centralized clustering algorithm for cluster set-up and the same steady-state phase as LEACH [5, 3]. Leach-C tries to avoid redundant creation of cluster heads in a small area.   It attempts to minimize the amount of energy for the ordinary nodes to transmit their data to the cluster head.

As LEACH and TL-LEACH, the basic operation of LEACH-C consists of many rounds, each round being divided into two phases. In the set-up phase of LEACH-C, information about a node’s current location and residual energy level is sent to the BS [5]. The BS ensures better distribution of en- erg load among all the nodes, in addition to determining good clusters.  To do this, BS computes the average energy of nodes, and determines the nodes having energy above this average as candidates for CH. BS selects CHs from the candidate nodes in a random  basis such that a CH does not lie inside a predefined radius  of any other CH [3].

In the CH selection process shown in Figure 4 (a), node a, b, c, and d are elected for candidate nodes for CHs among the sensor nodes.  First, the BS selects node a as CH. As node b is within radius r of a, it is ruled out of the qualification of candidate nodes.  Similarly, node d is also ruled out of the qualification. As a result, node a and c are actually selected as CHs as shown in Figure 4(b).

This approach does not find the optimal clusters but one of the beneficial parts is the computation, which is not NP-hard anymore as in conventional LEACH-C .Once the CHs and associated clusters are found, the BS broadcasts a message that contains the CH ID for each node. If the node ID matches with the CH ID, then it becomes a cluster head;  otherwise the node determines its TDMA slot for data transmission, from the TDMA schedule and goes to sleep until it’s time to transmit data.

The steady-state phase of LEACH-C is identical to that of the LEACH protocol, i.e.  The nodes collect data and send them to their CHs during the TDMA slot allocated, where the data are aggregated or diffused

Figure 4: Basic Concept Used in LEACH-C for CH Selection mitted to the BS.

Major advantages of LEACH-C include,

  • CHs are evenly distributed among the nodes in the network.
  • of cluster heads formed in each round are almost uniform, which results in more number of nodes being alive till the end of the network lifetime.
  • Life time of network will be more compared to LEACH.

LEACH-C has also a drawback of being a single hop protocol that will not be able to provide more data aggregation and fusion.  And hence BS may receive more number of redundant data causing wastage of energy.

REFERENCE

  • R.Heinzelman, A.P.Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless micro sensor networks.  In  Proceedings  of the  33rd  Hawaii  International Conference   on  System   Sciences,   volume  8,  pages  8020–8029, Washington,  DC,  USA,  2000. IEEE Computer Society.
  • Loscri, G. Moabite, and S. Marino. A two-level hierarchy for low-energy adaptive clustering hierarchy (tl-leach). In Vehicular Technology Conference. 2005 IEEE 62nd, volume 3, pages1809–1813, 2005.
  • Taewook Kang,  Jangkyu Yun,   Hoseung  Lee,  Icksoo  Lee,  Hyunsook  Kim,  Byunghwa Lee, Byeongjik  Lee, and  Kijun  A clustering method for energy efficient routing in wireless sensor networks. In Proceedings of the  6th WSEAS  International Conference on Electronics, Hardware, Wireless and  Optical  Communications,  EHAC’07,  pages  133–138, Stevens Point, Wisconsin,  USA, 2007. World Scientific and Engineering Academy and Society (WSEAS).
  • Shrubby, D. Minoli, and T. Znati. Wireless Sensor Networks: Technology Protocols and Applications.  Wiley, 2007.
  • R. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan. An application specific protocol architecture for wireless microsensor networks. Wireless Communications, IEEE Transactions on, 1(4):660–670, 2002.