A Survey on LEACH-based Hierarchical Routing Protocols in Wireless Sensor Network

A Survey on LEACH-based Hierarchical Routing Protocols in Wireless Sensor Network

Jyoti Singh, Bhanu Pratap Singh

Department of CSE,

VITS Satna, Madhya paradesh, INDIA

Subhadra Bose Shaw

Department of CSE

MNNIT Allahabad, Uttar Pradesh, INDIA

Abstract Due to the wide range of applications the use of wireless sensor networks (WSNs) in past few years have increased a lot and it has become a hot research area now a days. One of the important issues in wireless sensor network is the inherent limited battery power in network sensor nodes. Since most of the energy is consumed by the radio transmission and reception, energy efficient routing protocol is required to enhance the lifetime of WSN. Based on the network structure, there are two broad categories of routing protocols in WSNs: flat routing and hierarchical routing. Many researchers are working on these different routing protocols of wireless sensor networks. In this paper the focus is mainly on the survey of the energy-efficient hierarchical cluster-based routing protocols based on Low-Energy Adaptive Clustering Hierarchy (LEACH) which is the first and most popular energy-efficient hierarchical clustering algorithm for WSNs. In this paper we have outlined the advantages of clustering for WSNs, and systematically analyze different LEACH based WSN clustering routing protocols.

Keywords Cluster-based routing, Data transmission, Energy-efficient, Hierarchical routing, LEACH, Wireless sensor network.

1. INTRODUCTION

   Wireless sensor networks are self-organized wireless network systems consisting of many low-cost and resource- constraint sensor nodes. It can be comprised of hundreds or thousands of sensors, depending on the requirement of quality of service (QoS) and the capability to tolerate a fault. Battery power is a crucial parameter in sensor networks as they are often deployed in adversarial and unattended environments for critical applications such as battlefield reconnaissance and medical monitoring. The nodes in the network send their data to the base station (BS) from where the end user can access the sensed data. As most of the battery power is utilized in data transmission between sensor nodes and base station the routing algorithms must be designed to increase lifespan of nodes in the network in order to improve the overall network performance.

   Routing in WSNs is a challenging issue [3,4] due to the following reasons:

   • Resources are limited in terms of power supply, processing capability and transmission bandwidth.

   • It is difficult to design a global addressing scheme due to unpredictable and frequent topology changes.

   • Collected data by sensor nodes usually results in data redundancy.

   • Most applications of WSNs require the only communication scheme from multiple sources to one particular sink, rather than multicast or peer to peer.

   • In real time applications data transmissions should be accomplished within a particular period of time. Thus, bounded latency for data transmissions must be considered. Nevertheless, energy conservation is more important than quality of service (QoS) in most applications as energy is directly related to network lifetime.

     Depending on network structure, routing protocols in WSNs can be broadly divided into two categories: flat routing and hierarchical routing. In a flat routing protocols all nodes perform the same functions in the network. Usually hop by hop data transmission takes place. Flooding and Gossiping

     [5] are two typical examples of flat routing protocol. Flat routing is relatively effective in small-scale networks [1]. However, it is not suitable in large-scale networks because of limited resources.

     On the other hand, in a hierarchical or clustering routing protocols nodes are grouped into clusters. Generally, each cluster consists of a leader node called cluster head (CH) and member nodes. Normally nodes having higher energy act as CH and perform the task of data aggregation and transmit information to the base station, while the remaining nodes

     i.e. the nodes with lower energy perform the task of information sensing . In the last few years, many clustering routing protocols have been developed for WSNs. In this paper we have discussed the most prominent clustering routing algorithm LEACH and other LEACH based protocols that have been developed for WSNs.

     The remainder of this paper is organized as follows: Section 2 outlines the advantages and objectives of clustering for WSNs. Section 3 provides an overview of clustering routing algorithms based on LEACH. Finally, Section 4 summarizes and concludes the paper.

2. ADVANTAGES OF CLUSTERING

   In this section we have discussed the advantages of clustering routing protocols in WSN.

   • More Scalability: In clustering routing scheme, sensor nodes are grouped into clusters. The CHs are responsible for aggregation of data, information dissemination and network management. The normal nodes are responsible for events sensing and collecting information from their surroundings. This type of network is more scalable to respond to events in the environment [3].

   • Data Aggregation: To eliminate redundant transmission data is aggregated by the CH and fused data is sent to the BS [2]. Usually CHs form a hierarchical structure to transmit aggregated data through other CHs which results in significant energy savings [47].

   • Less Energy Consumption: Data aggregation helps to reduce data transmission and saves energy. Moreover, intra-cluster and inter-cluster communications reduce the number of sensor

     steady-state phase for data aggregation, compression, and transmission to the sink. Cluster heads (CHs) use CSMA MAC protocol to advertise their status. Thus, all non-cluster head sensors must keep their receivers ON during the setup phase in order to receive the advertisements sent by the CHs. These CHs are selected with some probability by themselves and broadcast their status to the other sensors in the network.

     The decision for a sensor to become a CH is made independently without any negotiation with the other sensors. Specifically, a sensor decides to become a CH based on the desired percentage P of CHs, the current round r, and the set of sensors that have not become CH in the past 1/P rounds. Nodes which are not selected as the CH in the last 1/P round generates a random number between 0 to 1. If the number is less than T(n), the node becomes a CH for the current round, where T(n) is a threshold given by the following formula:

     p

     nodes directly communicating with the BS thus allowing less

     energy consumption.

     T(n) =

     1: if n G

   • More Robustness: In response to network changes like addition of new nodes, node mobility and unpredicted failures, etc. a clustering routing scheme only needs to manage individual clusters not the entire network. In order to increase the lifetime of WSN, CHs are rotated among all the sensor nodes to avoid single point of failure.

   • Load Balancing: Here it means construction of equal-sized clusters to prolong the network lifetime as it prevents the premature energy exhaustion of CHs. Moreover, multi-path routing also helps to achieve load balancing.

   • Fault-Tolerance: Re-clustering is done to recover from a cluster head failure. Backup CH can be assigned to get recovery from a CH failure.

   • Maximizing Network Lifetime: Since clustering helps in more energy-efficient routing it increases the overall lifetime of WSN.

3. HIERARCHICAL ROUTING PROTOCOLS IN WSNS

   LEACH: It is the most popular energy-efficient hierarchical routing algorithm proposed by W.R.Heinzelman [7] for WSNs to reduce power consumption. In LEACH, direct communication is used by each CH to forward the data to the base station (BS). LEACH divides the network into several clusters. Since energy dissipation of the sensor depends on the distance LEACH attempts to transmit data over short distances and reduce total number of transmission and reception operations [6]. The key features of LEACH are: (i) randomized rotation of the CH and corresponding clusters, (ii) local aggregation of data to reduce global communication, (iii) localized coordination and control for cluster set-up and operation.

   In LEACH CH rotation takes place rather than selecting one in static manner, to give an opportunity to each sensor to become a CH and avoid quick dieing of CH by total battery depletion. The operation of LEACH is divided into rounds, each of which has mainly two phases namely (i) a setup phase to organize the network into clusters, CH advertisement, and transmission schedule creation and (ii) a

   1prmod

   p

   T(n) = 0 :

   otherwise (1)

   where G is the set of nodes that have been CHs in the last 1/P rounds. Once the network is divided into clusters, a CH computes a TDMA schedule for its sensors specifying when a sensor in the cluster is allowed to send its data. Thus, a sensor will turns its radio ON only when it is authorized to transmit according to the schedule created by its cluster head, therefore significant energy is being saved by switching off the receivers during idle period. Furthermore, LEACH enables data fusion in each cluster by aggregating the data which not only minimizes redundancy but also reduces the total amount of data sent to the sink. The sensors within a cluster transmit their sensed data over short distances, whereas CHs communicate directly with the sink.

   Fig. 1: LEACH

   Drawback of LEACH The algorithm possesses clustering approach and if implemented properly it can lead to energy- efficient routing in WSNs. But still it has some shortcomings as described below:

   • It uses single-hop routing where each node can transmit directly to the cluster-head and the sink. So it is applicable only for small network and not suitable to networks deployed in large regions.

   • Dynamic clustering brings extra overhead, e.g. rotation of cluster head, advertisements, reclustering etc., which may diminish the gain in energy consumption.

   • LEACH provides time slots for each node in the TDMA schedule generated by CHs in the network. Sensor nodes are supposed to send their data in its own time slot but this method wastes bandwidth because some nodes might not have data to transmit.

   • Though LEACH helps the sensors within their cluster dissipate their energy slowly, a larger amount of energy is consumed by the CHs when they are located farther away from the sink.

   • LEACH clustering terminates in a finite number of iterations, but does not guarantee good CH distribution. There is no mechanism to ensure that the elected CHs will be uniformly distributed over the network. So all cluster heads may be concentrated only in one part of the network. That's why uniform energy consumption for CHs is not practical.

   Since LEACH has many drawbacks, many researchers have been working to make this protocol performs better. Some of these research works are briefly discussed in the following points.

   LEACH-Centralized (LEACH-C): It is a centralized clustering algorithm based on LEACH [6]. During the set-up phase each node sends information about current location and energy level to the base station (BS). BS will determine clusters, CH node and member nodes of each cluster. The BS utilizes the global information about the network to produce better clusters which require less energy for data transmission. In LEACH-C the number of CHs in each round equals a predetermined optimal value unlike LEACH where the number of CHs may vary among different rounds due to lack of global coordination among nodes. Optimal formation of clusters are possible but to achieve this communication with the BS in each round by all the sensor nodes is required. It is less reliable due to single point of failure and can cause hotspot problem.

   LEACH with Fixed Cluster (LEACH-F): In LEACH-F [8] clusters that are formed once are fixed. Then, the cluster head position rotates among the nodes within the cluster. The advantage is that there is no set-up overhead at the beginning of each round due to reclustering. To build clusters LEACH-F uses the same centralized concept of LEACH-C algorithm. The method lacks scalability since fixed clusters do not allow new nodes to be added and the lifespan of such network is very less because it never adjusts the clusters as nodes dye.

   Solar-aware Centralized LEACH: Energy harvesting is essential in some applications of WSN, especially when sensor nodes are placed in non-accessible areas like battlefield [9]. For such kind of applications the authors in [9] proposed sLEACH , in which solar power is used to improve lifetime of WSN. In solar-aware centralized LEACH cluster heads are selected via BS using LEACH-C. BS normally selects solar powered nodes through maximizing residual energy. In sLEACH nodes transmit their solar status to BS along with energy level. Nodes with higher energy are selected as CH.

   Performance of sensor network is increased when number of solar-aware nodes is increased. Life time of sensor network depends on the duration of sun. This is the energy harvesting time. If sunDuration is small, CH handover is performed in sLEACH [9]. If the node serving as CH is running on battery and another node in a cluster sends data with flag, then its solar power is increased. Thus the latter node becomes the CH in place of the first serving CH. The new CH is selected during steady state phase enhancing the lifetime of the network.

   Multi-hop LEACH: If networks diameter is increased beyond a certain limit, then LEACH routing protocol cannot handle the situation because distance between CH and BS is increased enormously. In this case, single-hop energy dissipation of CH is not affordable. To solve this problem, Multi-hop LEACH is proposed in [10].

   Fig. 2: Inter-cluster and Intra-cluster communication in Multi-hop LEACH [6]

   It is a distributed clustering based routing protocol. Setup phase is like LEACH. In steady state phase CH collects data from all member nodes and transmit the aggregated data directly or indirectly through other CHs to the BS. There are two types of possible communication in Multi-hop LEACH. In inter-cluster communication the CHs of different clusters communicate among each other. In intra-cluster communication the member nodes of each cluster send their sensed data to their corresponding CH. The algorithm selects the best path with minimum hop count between the CH and BS.

   H-LEACH : The method is proposed by considering the concept of minimizing the communication distance between nodes to conserve energy [15]. It employs the same clustering approach as LEACH during initial phases and later it extends LEACH by further clustering the cluster heads and nominates one of the cluster head, which then acts as the Master Cluster Head (MCH), to forward data to the base station. In H- LEACH finally only one MCH is involved to transmit all compressed data to base station, so central point of failure situation may occur when the MCH will be dead.

   EEE LEACH: Energy Efficient Extended LEACH is an [14] approach of multilevel clustering technique to increase energy efficiency by decreasing the radio communication distance.

   The approach involves two layers of clusters formation. In the first layer CHs are formed similar to LEACH where the member nodes transmit their own data to their corresponding CH and the CHs aggregate the received data. Againin the second layer Master Cluster Heads (MCH) are created. The CHs search the nearest MCHs by calculating the distance between them and transmit their aggregate data to the respective MCHs. All MCHs received data from their nearest CHs and aggregate all the received data and forward the compressed information to the base station (BS). The number of CHs and MCHs are initially decided by using a predetermined fractional value p (election probability value) for CHs and pm for MCHs. In EEE LEACH, the numbers of MCHs are less than the number of CHs to reduce the overall communication distance between the nodes and BS. EEE LEACH protocol provides better network life-time and is more energy-efficient than LEACH.

   Mobile LEACH (M-LEACH): LEACH does not support mobility. It is only applicable on static network. To support the concept of mobility Mobile LEACH (M-LEACH) has been proposed. It allows mobility of member nodes and CH during setup and steady state phases. It also considers remaining energy of the CH selection [11]. Some assumptions of this algorithm are: initially, all nodes are homogeneous in terms of antenna gain and all nodes receive their location information through Global Positioning System (GPS) and BS is considered fixed in M-LEACH.

   Distributed setup phase of LEACH is modified by M-LEACH in order to select suitable CH. In M-LEACH, CHs are elected on the basis of attenuation model. Optimum CHs are selected to reduce the power of attenuation. Other criteria of CH selection is based on mobility of nodes. A node with minimum mobility and lowest attenuation power is selected as CH in M- LEACH. Then selected CHs broadcast their status to all nodes in transmission range. Member nodes compute their willingness from multiple CHs and select the CH with maximum residual energy. In steady state phase, if member nodes move away from CH or CH moves away from its member nodes then another CH becomes suitable for member nodes. It results into inefficient clustering formation. To deal with this problem, M-LEACH provides hand-over mechanism for nodes to switch on to new CH. When nodes decide to make handoff, they send DIS-JOIN message to current CH and also send JOIN-REQ to new CH. After occurring hand- off, CHs re-schedule their transmission pattern.

   I-LEACH : The proposed I-LEACH routing protocol [12] outperforms LEACH by overcoming some of its shortcomings. In I-LEACH, first of all the probability based selection criteria for a CH was replaced with concept of remaining energy. The other limitation has been solved out by the uniform distribution of the CHs. Cluster formation is done on the basis of x-axis coordinates of the nodes. It helped out in the uniform distribution of the CHs. So non-CH nodes will not require transmitting their data over long distance. I-LEACH showed substantial improvement over LEACH.

   U-LEACH: It combines the good features of both I-LEACH and PEGASIS (Power-Efficient Gathering in Sensor Information Systems) protocols and introduces the concept of heterogeneity in the WSN [12]. Formation of clusters is based on the x-coordinate values of the sensor nodes like I-LEACH. Cluster heads are selected based on the residual energy of the sensor nodes after completion of the clustering process. In each cluster, a node with higher remaining energy than other nodes will be selected as CH. Later on, an MCH is selected from these CHs periodically. After the clustering procedure chain formation takes place in each cluster. Chain starts from the farthest node in a cluster and eventually ends with the CH. At each CH data aggregation takes place to reduce the gathered data from all the sensor nodes of the cluster into compact and meaningful information. The sensors have two different levels of energy, half of the nodes get higher values than the rest of the sensor nodes. The distribution of the energy is done symmetrically i.e. even numbered nodes gets one value of the energy while odd numbered nodes get the other value of energy.

   V-Leach : The New version of LEACH protocol in which each cluster contains: CH (responsible only for sending data that is received from the cluster members to the BS), vice-CH (the node that will become a CH of the cluster in case of CH dies), cluster nodes (gathering data from environment and send it to the CH) [13]. In LEACH when the CH dies, the cluster will become useless because the data gathered by cluster nodes will never reach the base station. But in this method the vice-CH takes the role of the CH when the CH dies. So cluster nodes data will always reach the BS and there is no need to elect a new CH whenever CH dies. This will increase the overall network life time. But in case the Vice Cluster Head Dies, the routing protocol does not provide any solution for that and the network start reducing energy very fast and finally it dies completely.

   Improved V-Leach : It is an improvement over the V-Leach which has tried to remove the shortcoming of V-LEACH by increasing the network lifetime [13]. In this method, initially the Vice Cluster Head is elected along with the cluster heads based on the energy and the distance parameters. When the cluster head dies, it is replaced by Vice Cluster Head and at the same time new Vice Cluster Head will be selected. It means the cluster head will stay over the life of network. The decision of the Cluster head and Vice Cluster head is taken on the basis of Energy, Distance and Remaining Energy of the sensor nodes. This algorithm provides better network lifetime than V-LEACH.

   .

4. CONCLUSION AND FUTURE WORK

   A Wireless sensor networks consists of thousands of tiny, low cost, low power and multifunctional sensor nodes where each node has very low battery life. Different energy efficient routing algorithms have been designed for this. As this is a very broad area we have only surveyed and summarized in this paper LEACH and various hierarchical clustering routing protocol based on LEACH. LEACH uses distributed cluster formation & randomized rotation of the cluster head to reduce

   the network energy consumption and thereby enhance the network lifetime. The various LEACH-based routing algorithms discussed above have different assumptions. They have their own advantages and pitfalls. Each of them has its own application domain where it can perform better than the other. So which method should be used that depends on the situation itself. Further research can be done to find the best possible optimal routing algorithm which will be promising in terms of energy efficiency as well as provide the required Quality of Service (QoS) posed by real-time applications. Significant research work is going on in these different energy-efficient clustering routing protocols in order to maximize the life time of the wireless sensor network. Moreover, the process of data aggregation and fusion in clusters is also an interesting problem to explore.

5. REFERENCES

1. Xuxun Liu, A Survey on Clustering Routing Protocols in Wireless Sensor Networks , Sensors 2012, pp. 1113-11153.

2. Yue, J.Zhang, W.Xiao, W. Tang, D. Tang, J. Energy efficient and balanced cluster-based data aggregation algorithm for wireless sensor networks, Procedia Eng. 2012, 20092015.

3. Seah, W., Tan, Y. Eds., Sustainable Wireless Sensor Networks, InTech Open Access Publisher: Rijeka, Croatia, 2010.

4. Li, C.; Zhang, H.X.; Hao, B.B.; Li, J.D. A survey on routing protocols for large-scale wireless sensor networks, Sensors 2011, 11, 34983526.

5. Haas, Z.J.; Halpern, J.Y.; Li, L. Gossip-Based Ad Hoc Routing, In Proceedings of the 19th Conference of the IEEE Communications Society (INFOCOM), New York, NY, USA, 2327 June 2002; pp. 17071716.

6. Shio Kumar Singh , M P Singh, D K Singh, A Survey of Energy-Efficient Hierarchical Cluster-Based Routing in Wireless Sensor Networks , Int. J. of Advanced Networking and Applications Volume: 02, Issue: 02, 2010, pp. 570-580.

7. W.R. Heinzelman, A. Chandrakasa, and H. Balakrishnan, Energy- efficient Communication Protocol for Wireless Microsensor Networks, in IEEE Computer Society Proceedings of the Thirty Third Hawaii International Conference on System Sciences (HICSS '00), Washington, DC, USA, Jan. 2000, vol. 8, pp. 8020.

8. W.R. Heinzelman, Application-Specific Protocol Architecture for Wireless Networks PhD Thesis, Massachusetts Institute of Technology, June 2000.

9. Thiemo Voigt, Hartmut Ritter, Jochen Schiller, Adam Dunkels, and Juan Alonso, Solar-aware Clustering in Wireless Sensor Networks, In Proceedings of the Ninth IEEE Symposium on Computers and Communications, June 2004.

10. Rajashree.V.Biradar, Dr.S.R. Sawant, Dr. R. R. Mudholkar , Dr. V.C

    .Patil, Multihop Routing In Self-Organizing Wireless Sensor Networks , IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 1, January 2011.

11. M. Aslam, N. Javaid, A. Rahim, U. Nazir, A. Bibi, Z. A. Khan, Survey of Extended LEACH-Based Clustering Routing Protocols for Wireless Sensor Networks , IEEE 14th International Conference on High Performance Computing and Communications , 2012, pp. 1232-1239.

12. Naveen Kumar, Jasbir Kaur,Improved LEACH Protocol for Wireless Sensor Networks. In Proceedings of International Conference on Wireless Communications Networking and Mobile Computing, Wuhan, China, 2011. 13. Naveen Kumar , Sandeep , Pawan Bhutani , Prity Mishra, U-LEACH: A Novel Routing Protocol for Heterogeneous Wireless Sensor Networks , International Conference on Communication, Information & Computing Technology (ICCICT), Mumbai, India , Oct. 19-20, 2012.

1. Nutan sindhwani, rohit vaid , V LEACH: An Energy Efficient Communication Protocol for WSN , vol. 2, No. 2, February-March 2013

   , pp. 79-84.

2. Meenakshi Sharma, Kalpana Sharma, An Energy Efficient Extended LEACH (EEE LEACH), International Conference on Communication Systems and Network Technologies , IEEE , 2012, pp. 377-382.

3. Wairagu G. Richard, Extending LEACH routing algorithm for Wireless Sensor Network, Data Communications Engineering, Makerere University, 2009.