Review
A systematic review on clustering and routing techniques based upon LEACH protocol for wireless sensor networks

https://doi.org/10.1016/j.jnca.2012.12.001Get rights and content

Abstract

In recent years, Wireless Sensor Networks (WSNs) have emerged as a new powerful technology used in many applications such as military operations, surveillance system, Intelligent Transport Systems (ITS) etc. These networks consist of many Sensor Nodes (SNs), which are not only used for monitoring but also capturing the required data from the environment. Most of the research proposals on WSNs have been developed keeping in view of minimization of energy during the process of extracting the essential data from the environment where SNs are deployed. The primary reason for this is the fact that the SNs are operated on battery which discharges quickly after each operation. It has been found in literature that clustering is the most common technique used for energy aware routing in WSNs. The most popular protocol for clustering in WSNs is Low Energy Adaptive Clustering Hierarchy (LEACH) which is based on adaptive clustering technique. This paper provides the taxonomy of various clustering and routing techniques in WSNs based upon metrics such as power management, energy management, network lifetime, optimal cluster head selection, multihop data transmission etc. A comprehensive discussion is provided in the text highlighting the relative advantages and disadvantages of many of the prominent proposals in this category which helps the designers to select a particular proposal based upon its merits over the others.

Introduction

Wireless Sensor Networks (WSNs) are being used in wide range of potential applications such as environment monitoring, military operations, target tracking and surveillance system, vehicle motion control, earthquake detection, patient monitoring systems, pollution control system etc. These networks consist of SNs which are capable of monitoring and processing the data from a particular geographical location and send the same to remote location which is called as Base Station (BS).

WSNs typically consist of small, inexpensive, resource constrained devices that communicate among each other using a multihop wireless communication. Each node of WSN is called as a SN which contains one sensor, embedded processors, limited memory, low-power radio, and is normally operated with battery. Each SN is responsible for sensing a desired event locally and for relaying a remote event sensed by other SNs so that the event is reported to the destination through BS. As SNs have limited energy so applications and protocols for WSNs should be carefully designed for optimized consumption of energy for prolonging the network lifetime. Figure 1 shows the generalized view of WSNs, which consists of a BS, Cluster Heads (CHs) and SNs deployed in a geographical region (Cook and Das, 2004).

Clustering has been widely used in WSNs for designing various energy efficient protocols in WSNs. One of the most common protocols used in this category is Low Energy Adaptive Clustering Hierarchy (LEACH) (Heinzelman et al., 2000). LEACH is a self-organizing, adaptive clustering protocol which uses equalized energy load distribution among the SNs in the WSN. The operation of LEACH is divided into rounds and each round is divided into two phases namely as: setup and steady-state phase. Steady-state phase is always long compared to the set-up phase to minimize the overhead. In LEACH protocol, the SNs organize themselves into local clusters, with one node acting as the leader and known as cluster head (CH) and rest of the nodes act as ordinary nodes. To prolong the lifetime of the network, LEACH includes randomized rotation of the high-energy CH and performs local data fusion to transmit the amount of data being sent from the CHs to the BS. If BS is far away from the network then the energy of CHs will be affected as only CHs are directly communicating with the BS. Set of clusters will be different for different time interval and the decision to become a CH depends on the amount of energy left at the SN. Figure 2 describes the various units in LEACH protocol consisting of transmitter and receiver.

It also shows various parameters of transmitter and receiver as defined by (Heinzelman et al., 2000) which are defined below. Transmitting radio equations are defined as follows (Heinzelman et al., 2000):ETx(k,d)=ETxelec(k)+ETxamp(k,d)ETx(k,d)=Eelec×k+εamp×k×d2

Receiving radio equations areERx(k)=ERxelec(k)ERx(k)=Eelec×kEelec is the radio energy dissipation for transmission and reception and εamp is the amplification factor used for the transmission of k bit message to a distance d.

For cluster formation, each SN decides whether or not to become a CH for the current round. This decision is based on the percentage of CHs for the network and the number of times the SN has been a CH so far. In this process, every SN has to select a random number between 0 and 1. If the number is less than a threshold T(n), the SN becomes a CH for the current round. The threshold is set as follows (Heinzelman et al., 2000):T(n)={pp(rmod1p),nG0,otherwisewhere P is the desired percentage of CHs (e.g., P=0.05), r is the current round, and G is the set of SNs that have not been CHs in the last 1/P rounds. During round 0, every SN has a probability P of becoming a CH. The SNs that are CHs in round 0 cannot be CHs for the next 1/P rounds. Thus the probability that the remaining SNs are CHs must be increased, since there are less SNs that are eligible to become CHs. Using this threshold, each SN will be a CH at some point within 1/P rounds. Table 1 shows the various parameters used in LEACH protocol (Heinzelman., 2000).

Each round of the LEACH protocol is defined by the set-up and steady phases. In set-up phase, CH for the current round broadcasts an advertisement message to the rest of the SNs. The SNs must keep their receivers on and based on the received signal strength of the advertisement, every non-CH node decides to which cluster it belongs for this round. If ties occur then a random CH is selected. In steady phase, the energy of all Cluster Members (CMs) can be reduced using sleep mode activation and now data transmission can begin. Once the CH has all the data from the CMs, the CH aggregates and fused the data to the BS. After a certain time, which is determined a priori, the next round begins with each SN determining if it should be a CH for this round. Figure 3 shows the steps used in the protocol.

Apart from many potential applications of WSNs, there are many constraints such as deployment strategy, optimal energy consumption, computation and storage, scalability, security, fault tolerance, reliability, Quality of Service (QoS), adaptability and bandwidth utilization. Many proposals in the literature are reported based upon the above defined parameters. Keeping in view of the above issues, this paper provides a detailed description of various existing LEACH based routing and clustering protocols which are used to solve many of the above defined issued in WSNs.

Rest of the paper is organized as follows. Section 2 provides the taxonomy of different clustering based routing protocols depending upon various parameters. Section 3 provides the comparison of all LEACH based clustering protocols with respect to various parameters. Section 4 provides the open issues in this area and finally Section 5 concludes the article.

Section snippets

Taxonomy of clustering based protocols

There are several parameters based upon which LEACH protocol has been modified and accordingly various variants of LEACH protocol exist in the literature. Figure 4 describes various parameters based upon which various categories of LEACH based protocols have been developed. The purpose of this paper is to provide the detailed description of all those modified LEACH based protocols according to the categorization shown in Fig. 4.

Comparison and discussion of existing protocols

Table 2 below provides a comparison of all the above protocols with respect to various parameters. As WSNs are applications specific, so we have selected various parameters depending upon applications where these can be applied. The detailed analysis of all the variants of LEACH based routing and clustering protocols with respect to various parameters are listed below in Table 2. Various parameters selected for discussion are data transmission, network type, routing type, latency, deployment

Open issues

In this paper, we have presented various routing clustering protocols based upon LEACH protocol by selecting different parameters. Based upon these parameters, a detailed comparison is provided for various existing protocols. Although we have selected different parameters which are specific to the applications where WSNs can be applied but still there are many open issues which can be further investigated keeping in view of this newly emerging area. One of the open issues is the use of

Conclusions

In WSNs, selection of CH node is very important aspect and the major research going in the direction is focused on how to minimize energy consumption during the process of extracting the essential data as the SNs are powered by batteries which have limited energy. Clustering has been used widely for efficient routing for the data communication from SNs to BS. It has been observed in the literature that Clustering reduces the energy consumption which prolong the life time of WSN. Low Energy

Acknowledgments

Authors would like to thank all anonymous reviewers for their valuable suggestion and comments which improves the overall quality of the paper.

References (77)

  • Kuei-Ping Shih et al.

    On target coverage in wireless heterogeneous sensor networks with multiple sensing units

    Journal of Network and Computer Applications

    (2009)
  • Konstantinos Samdanis et al.

    Autonomic hierarchical reconfiguration for wireless access networks

    Journal of Network and Computer Applications

    (2009)
  • Neelofer Tamboli et al.

    Coverage-aware connectivity restoration in mobile sensor networks

    Journal of Network and Computer Applications

    (2010)
  • Mohamed K. Watfa et al.

    BARC: a battery aware reliable clustering algorithm for sensor networks

    Journal of Network and Computer Applications

    (2009)
  • Sangho Yi et al.

    PEACH: power-efficient and adaptive clustering hierarchy protocol for wireless sensor networks

    Computer Communications

    (2007)
  • Junqi Zhang et al.

    Wireless sensor network key management survey and taxonomy

    Journal of Network and Computer Applications

    (2010)
  • Hasan Al-Refai et al.

    Efficient routing LEACH (ER-LEACH) enhanced on LEACH protocol in wireless sensor networks. Part I

    International Journal of Academic Research

    (2011)
  • A. Allirani et al.

    An energy efficient cluster formation protocol with low latency in wireless sensor networks

    World Academy of Science, Engineering and Technology

    (2009)
  • Abdulsalam Hanady M., Kamel Layla K., W-LEACH: weighted low energy adaptive clustering hierarchy aggregation algorithm...
  • Alizadeh Sayyad, Ghaffari Ali. An energy-efficient hierarchical clustering protocole in wireless sensor networks. IEEE;...
  • Hosseinalipour, Ali, KeyKhosravi, Davood, Mirzaei Somarin, Abbas. New hierarchical routing protocol for WSNs. In:...
  • Bian Xiaoxiang, Liu Xingcheng, Cho Haengrae. Study on a cluster-chain routing protocol in wireless sensor networks....
  • Bakr Bilal Abu, Lilien Leszek, Extending wireless sensor network lifetime in the LEACH-SM protocol by spare selection....
  • S. Bhatti1 et al.

    Clustering and fault tolerance for target tracking using wireless sensor networks

    IET Wireless Sensor Systems

    (2011)
  • D.J. Cook et al.

    Smart environments: technologies, protocols, and applications

    (2004)
  • Benjamin J. Culpepper et al.

    Design and analysis of hybrid indirect transmissions (HIT) for data gathering in wireless micro sensor networks

    Mobile Computing and Communications Review

    (2004)
  • Cui Xiaoyan, Liu Zhao. BCEE: a balanced-clustering, energy-efficient hierarchical routing protocol in wireless sensor...
  • Zhuo Cheng et al.

    Protocols for local data delivery in wireless microsensor networks.

    (2002)
  • Ding Xuxing, Xie Fangfang, Wu Qing. Energy-balanced clustering with master/slave method for wireless sensor networks....
  • Duan Cuiqin, Sun Jingjing, Zhou Duan, Zhang Jianxian. An energy efficient regional partitioned clustering routing...
  • Derogarian Fardin, Ferreira João Canas, Grade Tavares Vítor M. A routing protocol for wsn based on the implementation...
  • S. Deng et al.

    Mobility-based clustering protocol for wireless sensor networks with mobile nodes

    IET Wireless Sensor Systems

    (2011)
  • Farooq Muhamnmad Omer, Dogar Abdul Basit, Shah Ghalib Asadullah. MR-LEACH: multi-hop routing with low energy adaptive...
  • Guo Yinghui, Liu Yun, Zhang Zhenjiang, Ding Fei. Study on the energy efficiency based on improved leach in wireless...
  • Jian Guan et al.

    Energy balanced routing algorithm based on mobile sink for wireless sensor networks

    Journal of Computational Information Systems

    (2012)
  • Hou Rui, Ren Weizheng, Zhang Yaodong. A wireless sensor network clustering algorithm based on energy and distance. In:...
  • Wendi B. Heinzelman et al.

    An application-specific protocol architecture for wireless microsensor networks

    IEEE Transactions on Wireless Communications

    (2002)
  • M.J. Handy et al.

    Low energy adaptive clustering hierarchy with deterministic cluster-head selection

    IEEE

    (2002)
  • Cited by (408)

    • C4O: chain-based cooperative clustering using coati optimization algorithm in WSN

      2024, International Journal of Reconfigurable and Embedded Systems
    View all citing articles on Scopus
    View full text