A Case Study of the Cluster-Based Algorithms for Wireless Sensor Networks Based on Residual Energy of the Sensor Nodes

A Case Study of the Cluster-Based Algorithms for Wireless Sensor Networks Based on Residual Energy of the Sensor Nodes

Supriya Das, P. Shanthi Bala Department of Computer Science, Pondicherry University, Puducherry

Abstract

One of the important issues in WSN is the limited battery life of the sensor nodes. The efficient use of the battery power plays an important role in increasing the lifespan of the sensor nodes. From among the various routing algorithms for WSN, cluster-based routing algorithms are known to reduce energy consumption. LEACH is one of the basic clustering algorithms that were proposed to exploit the highly co-related nature of the data of the sensor networks, minimizing the overall energy consumption and data flow in the network. This paper lists out some of the drawbacks of the LEACH algorithm and studies some of the algorithms that are modifications of LEACH based on the energy.

1. Introduction:

   Routing in wireless sensor networks are different from the ones developed for conventional wireless networks because of many reasons. Sensor networks are different from the fixed networks in the sense that are infrastructure less unreliable wireless networks of huge number of sensor nodes with limited resources. The routing algorithms for the WSN need to be designed such that they provide efficient usage of the scarce resources. There are three basic categories of routing in WSN: flat, location-based, cluster-based. Among the these the clustering algorithms demonstrate significant advantages like minimizing overall power consumption, reducing total redundant data flow in the network, providing efficient usage of the bandwidth and power, increasing scalability of the network, over the other algorithms.

   This paper reviews LEACH and studies some of the clustering algorithms which are based on LEACH. These algorithms surveyed here take residual energy, distance between the nodes and optimality of the cluster formation as the parameters

   to judge and increase the efficiency of the algorithms. Section 2 of this paper presents the case study of the few algorithms taken into account because of the aforesaid parameters.

2. Case Study:

   Cluster-based protocols progresses in rounds and each round consists of four stages: cluster head selection, cluster formation, data aggregation and data transmission. The first step, cluster head selection is an important step because the CHs handles numerous tasks like maintaining coordination among the cluster members, collecting data within the cluster, data fusion processing and transmission of the aggregated data to the sink. Even, the divisions of the sensor nodes into clusters are dependent on the location and number of the CHs. Therefore, CH selection plays an important role in enhancing the performance of the wireless sensor networks. And, this importance in turn, has inspired many researchers to focus on optimizing the cluster head selection process. Different algorithms take different parameters into consideration while designing the routing algorithms to provide better efficiency in context to the applications for which they are designed for.

   Below are a few algorithms that take into account the residual energy of the individual nodes while the cluster head selection process, in order to reduce some of the disadvantages of the classic clustering algorithm, LEACH. We have studied the few algorithms based on LEACH and how they have tried to extend LEACH so as to provide better efficiency. But let us study LEACH to see what has actually provoked the modified algorithms.

   LEACH [1,2]: This protocol is an application- specific, energy efficient, randomized clustering protocol. LEACH was actually defined for reducing the amount of redundant data from flowing in the network, thereby saving energy. LEACH was defined assuming the following characteristics: random selection of cluster heads from amongst the randomly self-configured clusters, localized control and co- ordination amongst the clusters, reduction of the communication overload by compressing the data

   locally, low energy media access control, application- specific protocol. The LEACH algorithm progresses in rounds and each round is divided into two stages; the first stage being the setting up of the clusters and the cluster heads, so is known as the set up phase and the second stage which handles the actual data transmission from the cluster members to the cluster heads and then to the base station/base stations and is called the steady-state phase. In the set-up phase, the nodes are chosen to be the cluster heads on the basis of the random number generated by them which lies between 0 and 1 and then compared against the

   threshold value Tthr

   p

   insufficient energy as cluster heads, which in turn will limit the lifetime of sensor nodes and eventually entire network.

   EECS: An Energy Efficient Clustering Scheme in Wireless Sensor Networks (Mao Ye, Chengfa Li, Guihai Chen1 and Jie Wu) [4]: This paper proposes an energy efficient clustering scheme (EECS) for periodical data collecting applications in WSNs. During the cluster head election phase, a constant number of candidate nodes are elected and they compete becoming the cluster heads according to their residual energy. The competition is performed locally and without iteration, thereby reducing message overhead and also helps in the uniform

   T {1 p{r mod(1/ p)}

   nG

   distribution of cluster heads. Further, a novel

   thr

   0 else

   approach has been introduced to distribute the energy consumption among the sen- sors in the cluster

   However there are also problems with the traditional

   LEACH algorithm, such as:

   • The clusters are randomly selected which may give rise to uneven distribution of energy throughout the network.

   • While selecting the cluster head, neither its residual energy nor its distance from the other nodes or base station is considered.

   • It assumes homogenous nodes and uniform energy consumption of the CHs.

   • LEACH uses single-hop transmission to communicate with the base station, so LEACH cant be used for a large scale network.

   • Leach assumes that the sensor nodes always have some data to send.

     LEACH-C [1,2]: This protocol is quite similar to LEACH in the process of cluster formation at the beginning of each round. But, instead of the nodes randomly self-selecting a CH, a centralized algorithm is run by the sink in LEACH C. The sink first collects the information about the location of all the nodes and then broadcasts its decision about which nodes are to become the CH back to the nodes. This enhances the overall performance of LEACHC over LEACH because it leaves the decision of cluster formation to the sink. However, this makes LEACH- C depended on the sink location. And once the energy cost of communicating with the sink becomes higher than the energy cost for cluster formation, performance of LEACH-C deteriorates. In most WSN applications sinks may be located far away from the network. So, the dependency on the sink location is a major disadvantage of LEACH-C. Also LEACH-C considers the remaining energy of all nodes to choose the cluster heads but not that of the respective node. So, they may select the nodes with

     formation phase. EECS is fully distributed and more energy efficient. The simulation results in this paper show that it prolongs the network lifetime as much as 135% of LEACH.

     An Energy Efficient Clustering Algorithm Based on Residual Energy and Concentration Degree in Wireless Sensor Netwrks (Yuzhong Chen, and Yiping Chen) [5]: This paper analyses the deficiencies of LEACH and an improved cluster- based energy efficient routing algorithm called ECHC is proposed. Here, during the cluster head selection process an election weight taking account of the residual energy and concentration of nodes for cluster-head election is introduced in the proposed algorithm. The algorithm also defines a new criterion for non-cluster nodes to choose its cluster head. In LEACH, the non-cluster nodes depend only on the signal strength of cluster heads to decide on which cluster to join. This rule is based on the assumption that sensor nodes are uniformly distributed in the monitoring region.. In real case scenarios, if the rule is applied in cluster formation without other considerations, clusters will always vary greatly in the number. The cluster head of a relatively big cluster have to spend more energy for collecting data from source nodes than the cluster head in a smaller cluster, bringing unbalanced energy consumption of cluster heads which in consequence will impact the lifetime of the wireless sensor networks. To achieve better load balancing among cluster heads, ECHC introduces a novel criteria for cluster formation. A non-cluster node considers both the residual energy of the cluster head and the size of the cluster when it decides to join a cluster.

     A Energy-Efficient Clustering Routing Algorithm Based on Distance and Residual Energy for

     Wireless Sensor Networks (Zhu Yong, Qing Pei) [6]: This paper, proposes a cluster routing algorithm DECSA considering both the distance and residual energy of nodes, to improve the process of cluster head election and the process of data transmission of network. This makes the nodes with more residual energy have greater probability to become cluster heads. In the stable working stage, it reduces the adverse effect on the energy consumption of the cluster head, resulting from the non-uniform distribution of nodes in network and avoids the direct communication between the base station and the cluster head, which may have less energy and may be far away from base station. The results of simulation indicate that the improved algorithm effectively balances the energy consumption, prolongs 31% of the lifetime,

     EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks (Dilip Kumar, Trilok C. Aseri, R.B. Patel ) [7]: This paper demonstrates the impact of heterogeneous nodes in hierarchical clusters formed in terms of their energy in wireless sensor networks. This paper introduces an energy efficient heterogeneous clustered algorithm for wireless sensor networks based on weighted election probabilities of each node to become a cluster head according to the residual energy in each node. According to this paper, the election process of cluster heads should consider the heterogeneity of the nodes, because in real time applications not all the nodes in the field may have the same initial energy. Simulations results in this paper show that EEHC has extended the lifetime of the network by 10% as compared with LEACH.

     Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection (M. J. Handy, M. Haase, D. Timmermann) [9]: This paper focuses on reducing the overall power consumption of the wireless sensor networks. Here LEACHs stochastic cluster head selection process is extended by a deterministic component. The approach used here to increase the lifetime of the network following LEACH is the inclusion of the remaining energy of each node. This is achieved by reducing the threshold value of the competing node relative to the node's remaining energy. However this process fails to perform after a few rounds. After a certain number of rounds the network gets stuck, though there are nodes available with enough energy to transmit data to the base station. The reason is a cluster-head threshold which is too low, because the remaining nodes have a very low energy level.

     Study on a Cluster-Chain Routing Protocol in Wireless Sensor Networks(Xiaoxiang Bian, Xingcheng Liu, Haengrae Cho) [10]: In this paper, the authors propose the CCRP (Cluster Chain Routing Protocol) protocol designed on the basis of LEACH. This protocol is a more balanced cluster- head selection algorithm that is proposed after synthetically considering two additional parameters, the residual energy and the number of the neighboring nodes. Furthermore, the proposed CCRP improves the data transmission mechanism from the cluster-heads to the base station via constructing a chain among the cluster-heads. This protocols aims at prolonging the overall networks lifetime by evenly distributing the energy consumption among the sensor nodes in the network.

     The Combination of the Optimal Number of Cluster-Heads and Energy Adaptive Cluster-Head Selection Algorithm in Wireless Sensor Networks (Yang Tao, Yaling Zheng) [11]: This paper presents an algorithm that combines the optimal number of cluster-head with energy adaptive cluster head selection algorithm. Here the initial clustering phase is divided into two phases; CH selection and cluster organization. First, each nodes status is build into table at the base station according to the initial status messages (like initial energy) sent to it by the nodes and then the optimal number of CHs is selected according to the table data. In the following rounds, all the nodes in the network first record their current residual energy and calculate the value of the energy dissipated in the previous round. Then, according to the modified threshold value, each node that has elected itself a cluster-head, broadcasts an advertisement message to the rest of nodes. According to this paper only one node will be a cluster-head successfully in a cluster of each round. This ensures that the number of cluster-heads is optimal in the whole network.

     Weighted Spanning Tree clustering routing algorithm based on LEACH (Huazhong Zhang, Peipei Chen, Shulan Gong) [12]: This paper presents the weighted spanning tree algorithm based on LEACH (WST LEACH). Here, the selection of cluster heads are not completely random, but also considering the remaining energy, the distribution density of nodes and the distance from cluster heads to the base station. It establishes a Weighted Spanning Tree through all the cluster heads, by calculating the weight value using the aforementioned factors. Then the data is sent to the base station along this tree after being integrated. It optimizes the data transmission path and reduces the energy consumption. Simulation results show that

     WST LEACH reduces the energy consumption, has higher efficiency and can extend the network lifetime as well.

     An Energy Efficient Routing Scheme for Wireless Sensor Networks (Ki Young Jang, Kyung Tae Kim, Hee Yong Youn) [13]: This paper proposes a protocol to improve both the LEACH and LEACH-C algorithm. The proposed scheme works in three stages- first, electing a new cluster head based on the residual energy of each node only when the energy falls under a certain value. Second, deciding which CH to join according to the cost value determined by the signal power of the CH and the distance the CH and the respective node. Third, data transmission data transmission from the sensor nodes to the cluster head occurs only when the preset condition on the context is satisfied. Simulation in the paper shows that the proposed scheme outperforms LEACH and LEACH-C by 37% and 30%, respectively, in terms of the lifetime of the sensor network.

3. Conclusion:

   In this paper we have reviewed the classic algorithm LEACH and studied some of the algorithms based on it, i.e. which are improvement of LEACH. Here, among all the clustering algorithms those algorithms are studied which consider residual energy as the main parameter in the cluster head selection process. Since CH selection is an important step in the clustering algorithms, optimizing this process leads to an overall enhanced sensor network

4. Rferences:

   • W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks, IEEE Transaction on Wireless Communications, 2002, vol. 1, no. 4, pp. 660670.

   • W.Heinzelman,A.Chandrakasan,H.Balakrish nan. Energy-Efficient communication protocol for wireless microsensor network ,Proc.of the Hawaii International Conference on System Sciences,IEEE Computer Society,Washington.DC USA,Jan 2000,pp.3005-3014.

   • Performance Comparison of LEACH and LEACH-C Protocols by NS2

   • M. Ye, C. Li, G. Chen, and J. Wu, EECS: An Energy Efficient Clustering Scheme in Wireless Sensor Networks, National Laboratory of Novel Softaware Technology,Nanjing University,China.

   • An Energy Efficient Clustering Algorithm Based on Residual Energy and Concentration Degree in Wireless Sensor Networks (Yuzhong Chen, and Yiping Chen), Proceedings of the Second Symposium International Computer Science and Computational Technology(ISCSCT 09), Huangshan, P. R. China, 26-28,Dec. 2009, pp. 306-309

   • Zhu Yong, Qing Pei, A Energy-Efficient Clustering Routing Algorithm Based on Distance and Residual Energy for Wireless Sensor Networks, 2012 International Workshop on Information and Electronics Engineering (IWIEE)

   • EEHC: Energy efficient heterogeneous clustered scheme for wireless sensor networks (Dilip Kumar a,*, Trilok C. Aseri b,1, R.B. Patel c,2), Computer Communications 32 (2009) 662667

   • D. H. Nam, An efficient ad-hoc routing using a hybrid clustering method in a wireless sensor network, in Wireless and Mobile Computing, Networking and Communications, 2007. WiMOB 2007. Third IEEE International Conference on, 2007, pp. 6060.

   • M. J. Handy, M. Haase, D. Timmermann, "Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection," Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks, Stockholm, Sweden, pp. 368-372, Sept. 2002.

   • Bian, X.X.; Liu, X.C.; Cho, H. Study on a Cluster-Chain Routing Protocol in Wireless Sensor Networks. In Proceedings of the 3rd International Conference on Communications and Networking

   • Tao, Y.; Zheng, Y.L. The Combination of the Optimal Number of Cluster-Heads and Energy Adaptive Cluster-Head Selection Algorithm in Wireless Sensor Networks. In Proceedings of International Conference on Wireless Communications, Networking and Mobile Computing

   • Zhang, H.Z.; Chen, P.P.; Gong, S.L. Weighted Spanning Tree Clustering Routing Algorithm Based on Leach. In Proceedings of the 2nd International Conference on Future Computer and Communication (ICFCC 2010), Wuhan, China, 2124 May 2010; pp. V2-223V222-227.

   • Jang, K.Y.; Kim, K.T.; Youn, H.Y. An Energy Efficient Routing Scheme for Wireless Sensor Networks. In Proceedings

     of the International Conference on Computational Science and its Applications (ICCSA 2007), Kuala Lumpur, Malaysia, 2629 August 2007; pp. 399404.

   • Soroush Naeimi,Hamidreza Ghafghazi, Chee-Onn Chow, Hiroshi Ishii. A survey on the taxonomy fo Cluster-based Routing Protocols for homogeneous wireless sensor networks. ISSN 1424-8220.