Performance Analysis of Wireless Sensor Network by Variation in Cluster Head Selection through mLEACH-CS Algorithm

Abstract

The energy depletion at the nodes due to large volume of data transmission and data reception for large scale Wireless Sensor Networks (WSN) is one of the important areas of concern. Unbalanced energy consumption due to data traffic overhead at the nodes near the base station (BS) results in early node death and reduction in network lifetime. To balance the load at the wireless nodes during clustering, a novel hybrid clustering and routing protocol has been proposed based on mLEACH (modified Low-Energy Adaptive Clustering Hierarchy) and Cuckoo Search (CS) algorithm. Initially, mLEACH protocol is utilized to solve a novel equation designed to select the cluster heads by rotation at every round of data transmission based on the maximum permissible cluster heads in the network. In the second phase, CS algorithm is implemented for uniform distribution of the cluster heads in the network for efficient multi-hop data routing in the network based on several weighted factors. The performance of the proposed algorithm is compared with other algorithms in literature in terms of energy consumption and network lifetime for different positions of the base station and varied number of cluster heads in the model application area. The proposed mLEACH-CS algorithm shows a significant improvement by 60% considering 300 nodes in the WSN architecture while it decreased to 40% for denser network architecture. Optimal choice of the number and position of the cluster heads in certain network architecture has proved beneficial for designing an energy efficient wireless network with improved network lifetime.

Introduction

I. INTRODUCTION

The wireless network frequently finds its application in some remote and hostile environments where replacement of the battery sources becomes impossible and the sensor node energy becomes a constraint. Therefore, limited energy usage by the sensor nodes during data transmission and data reception needs to be looked into for development of large scale WSNs. One of the most effective techniques which have been employed in recent wireless applications has been clustering of sensor nodes which help to conserve the energy of the sensor nodes [1]. The entire set of wireless nodes deployed in the application area is divided into several groups known as clusters. Out of the all the nodes in a cluster, one of the nodes is chosen as a cluster head (CH) which collects the data from all the nearby cluster members (CM), aggregate the data and transmit it to be processed in the remote base station. The transmission can take place directly from the cluster head to the base station or through other intermediate cluster heads if the base station is located at some distance. The final data for the monitored event is displayed after processing at the base station where a model prototype of the entire process is recreated. This document is a template.  For questions on paper guidelines, please contact us via e-mail. In the view of this, it was found that one of the most popular and energy efficient method for clustering of sensor nodes was proposed by Heinzelman et al. known as Low Energy Adaptive Clustering Hierarchy (LEACH) protocol [2]. In this approach, several nodes were grouped into a single cluster and the cluster head for each round of data transmission was chosen by rotation. This attempt helped to conserve the energy of the nodes and the load was shared between all the cluster members. Each CH was assigned the responsibility for collection of data from each of its cluster member (CM) and transmitted the data to the sink node either directly or through multi-hop communication via other CHs. But selection of optimal number of sensor nodes as CHs and their positioning in the network is a very challenging process. The optimal node placement is important since it helps to address important issues such as minimal energy consumption, coverage of the entire application area and least number of signal overlaps.

Younis et.al on the other hand proposed HEED (Hybrid Energy Efficient Distributed clustering) protocol which periodically selected cluster heads based on residual energy of the nodes [3].

This algorithm considered multiple power level of the sensor nodes and accordingly divided the CHs and the CMs into some hierarchical levels for data transmission. However, this approach could design only two-level hierarchy for the entire network and multi-level hierarchies were not supported. An Energy-Efficient and Power Aware (EEPA) routing algorithm was proposed by researchers in a later work which presented a new energy-efficient dynamic clustering technique. In this approach, each node estimated the probability of itself becoming a cluster head by calculating the strength of the received signal power from the active neighbour nodes [4]. The limitation to these approaches was that no assumptions were made related to the node capabilities, power support or presence of other infrastructures in the periphery of the network leading to interference. The selection of ‘m’ cluster heads from ‘n’ sensor nodes was found out to be a non-deterministic polynomial-time hard (NP-hard) problem where the position and number of cluster heads changed for every successive rounds of data transmission [5]. In order to reduce the complexity of this type of non-polynomial problems, various nature inspired meta-heuristic algorithms was utilised for providing efficient solutions regarding placement of cluster heads.

A detailed study on the various classical and swarm intelligence-based clustering approaches proved that a significant improvement in energy savings of the sensor nodes can be obtained [6]. This has prompted the use of several nature inspired meta-heuristic algorithm in the last decade or two in the domain of clustering and routing for wireless sensor networks. Several novel soft computation algorithms have been designed recently such as fish electrolocation optimization which can be later utilised in the domain of optimization of routing path in wireless networks [7]. Centralized LEACH (LEACH-C) was one of the earliest applications of meta-heuristic algorithm-based clustering approach [8]. In this approach, all the sensor nodes initially sent the information about its location and energy to the sink node where simulated annealing based meta-heuristic algorithm is applied to determine the optimal clusters. The node having greater energy than average energy of all the other sensor nodes was elected as the cluster head. But, in this approach there was a greater probability that the elected CH may be far away from the BS as this approach had considered only the energy level of the sensor nodes while selecting CH. More the distance between the CH and the BS resulted in consumption of more energy during data communication between CH and BS. However, LEACH-C performed better than LEACH algorithm in terms of energy consumption and packet delivery ratio [8]. In a later work, Abbas et.al proposed a fuzzy logic and chaotic based genetic algorithm (FLCGA) for cluster head selection process [9]. However, this approach did not consider balanced energy consumption during formation of clusters. A differential evolution-based clustering protocol for wireless networks was proposed in a later work where the objective function was designed based on energy consumption and network lifetime [10]. However, this approach did not focus on uniform distribution of CHs over the entire network, thereby causing unbalanced energy consumption in WSN. In a later work, a clustering approach based on Particle Swarm Optimization (PSO) called enhanced optimized energy efficient routing protocol (E-OEERP) was designed which focused on the left out nodes as one of the members of the cluster [11]. The selection of the CHs through this approach was done considering the distances between the CHS and the base station. This protocol suffered the problem of non-uniform CH distribution resulting in unbalanced energy consumption since all the nodes chosen as CHs were placed near the base station. The routing of data between the CH and the BS was designed through gravitational search algorithm. An unequal clustering protocol based on fuzzy algorithm was proposed in a recent work which considered residual energy of the nodes and the distance between the sensor nodes and the base station as the two input parameters [12]. In a recent work, Rao et.al proposed a clustering protocol based on novel chemical reaction optimization (nCRO) algorithm [13]. Distance between CH and sink, residual energy, and intra-cluster distance were the various parameters that primarily designed the fitness function for application of nCRO. However, non-uniform distribution of the CHs resulted in the energy hole problem. To conserve the energy during transmission of data, a cluste- based energy-efficient data forwarding scheme was designed initially which ensured that even if multiple nodes in a cluster received a data packet, only one node amongst them was elected to send back an acknowledgment signal [14]. This node was elected based on binary exponential back-off algorithm. Another work based on Cascaded Cuckoo Search Algorithm was employed to find the best intermediate positions of the routers to enhance the reliability of the network [15]. Signal attenuation, energy consumption and packet error ratio were the parameters given utmost importance to establish the efficiency of the algorithm. However, recent attempts have focused on simultaneous utilization of clustering and routing algorithm to eliminate the problems related to non-uniform energy consumption and limited network lifetime.

In this work, a modified version of the conventional LEACH protocol, named as modified Low Energy Adaptive Clustering Hierarchy (mLEACH) protocol has been used in unison with a meta-heuristic algorithm known as Cuckoo Search (CS) Algorithm. This hybrid integration of the two algorithms aims at joint optimization of clustering and routing mechanism in the network. Maximum number of nodes eligible to become cluster heads are pre fixed for various number of sensor node deployment scenario in a wireless sensor network.

The position of the cluster heads are selected at every round of data transmission so that a reliable path is established at every round of data transmission. The uniform distribution of the cluster heads ensure that no sensor node is being left out from monitoring and neither there is overlap of signals in any particular cluster head. The overall estimation of the network energy proves reduced energy consumption in the network thereby increasing the lifetime of the network. The results obtained through the proposed approach prove that the attempt to use the node, with maximum residual energy and superior connectivity with all other nodes, as the cluster head helps to eradicate the energy-hole problem related to uneven distribution of cluster heads. The energy consumption is generally high amongst the cluster heads near the base station which needs to handle data from all the nodes and needs to store in the base station. The distribution of the role of cluster head amongst the nodes is therefore important to manage the energy consumption of the network. Considerable amount of improvement in respect to energy consumption and lifetime of the network can be observed compared to the previous works. Performance of the network for diverse number of cluster head deployment and varied sink positions has also been studied which gives an idea about the best network design. Therefore, the main novel contributions of this work have been summarized as follows:

1. Cuckoo Search and modified LEACH algorithm has been co-utilized in this application to jointly optimize the cluster head position and the routing path.
2. mLEACH algorithm aims to select the cluster heads based on residual energy of the nodes and at every round the cluster heads are chosen by rotation. The maximum permissible cluster heads in each round of data transmission has been fixed. Thereby, a novel equation has been proposed for selection of cluster heads through mLEACH algorithm.
3. A novel linear fitness function has been designed based on sink to source distance, the residual energy of the nodes and the highest degree of coverage with minimum signal overlap for optimal positioning of cluster heads to be solved by Cuckoo Search Algorithm.
4. It has been taken care that a proficient multi-hop routing path is created through a number of cluster heads which is well within the pre-specified limit.
5. The performance of the proposed algorithm has been studied for different number of cluster heads and varied base station positions. A comparison of the obtained results has also been done with some classical clustering techniques and some latest proposed protocols found in literature which yields better results.

The rest of the paper has been organized as follows: A brief description of the energy modeling and the problem formulated for this model has been discussed in Section II. Section III discusses the working for the joint optimization through this proposed mLEACH-CS protocol. All the results for the different scenarios and different base station positions and the comparative results with other works in literature have been presented in Section IV. Section V concludes the entire work and gives the scopes for further enhancement of this work in the future.

II. SYSTEM MODEL

A model two-dimensional area of pre-specified size of 200×200 m2 is selected where a set of nodes to be randomly deployed has been pre specified. For simulation purpose and to find out the best position of the control station for maximum data capture, the sink node or the base station (BS) has been fixed at three different co-ordinates for three different case studies. The three different case studies undertaken here consider the BS to be placed at the centre of the network, at the corner of the network and outside the network respectively.

The sink node or the base station (BS) stores all the data collected from the different cluster heads in the control station and evaluates the performance of the process whose parameters are being measured. The sink node is considered to be an energy rich node and it can easily remain connected to all the nodes which are in the range of the sink node. Therefore, fixing the position of the sink node is also equally important when considering only one sink node in the entire network. The cluster heads are assigned to perform the duties of data collection, data aggregation and data transmission and the energy of these cluster heads need to be managed. Minimum threshold energy is the energy required for the nodes to perform the operation of data transmission and whenever the initial energy of the nodes comes below the threshold energy, the nodes stop to operate. The nodes having high residual energy are selected as cluster heads by rotation at every round of data transmission. In this approach, an integrated approach has been undertaken to select the best nodes as cluster heads and their position in the network has been optimally decided so that the data is efficiently transmitted from the sensor nodes to the base station by the help of the cluster heads. The choice of the cluster heads is dependent on the average distance of transmission between the sensor node and base station, the residual energy of the nodes, the optimal number of cluster heads that can be placed, number of nodes in each cluster and maximum network coverage.

 In the process, it becomes necessary to study the energy modelling of the nodes which is dependent on the transmission energy, reception energy and energy required for data aggregation.

V. ACKNOWLEDGMENT

The financial support rendered by IEM-UEM GRANT IN AID is acknowledged by the author of this work. The author would like to express his gratitude to the Department of Electrical Engineering UEM, Kolkata and Department of Power Engineering, Jadavpur University for their constant support. The authors hereby declare they have no conflict of interest.

Conclusion

This work presented an energy efficient Cluster Head selection and positioning algorithm based on Cuckoo Search Algorithm and LEACH algorithm. To design an energy efficient cluster head election process, the fitness function considers the residual energy of the nodes, maximum number of nodes in a certain cluster, intra-cluster distance, cluster-sink distance and maximum network coverage. The simulation results along with the comparison with other existing algorithms namely PSO-ECHS, LDC, PSO-C, LEACH-C and LEACH algorithm shows the superiority in the performance of the algorithm compared to the other algorithms. This algorithm has been tested extensively for different scenarios considering different positions of the sink node and different number of cluster heads in the network. The proposed algorithm performs better than the existing algorithms in terms of total energy consumption and the network lifetime. It was seen that the energy consumption of the network was minimal when the base station was placed at the centre of the application area compared to the base station at the corner or out of field. The percentage improvement in network lifetime compared to the most recent PSO-ECHS algorithm was seen to be more for WSN-1 architecture compared to WSN-2 and WSN-3 architecture where the network architecture represented dense deployment of the nodes. The number of cluster heads was varied in the WSN-1 architecture in two scenarios and it was seen that choice of optimal number of cluster heads and their efficient positioning helps to reduce the energy consumption in the network considerably. Thus, this approach of cluster head selection has proved to be an efficient one. This algorithm has considered efficient positioning of the cluster heads to determine the multi-hop routing path but no routing algorithm has been implemented to validate the routing in real life scenario. Future works can focus on hardware implementation of the nodes by the proposed approach and test the data routing through any existing routing algorithm. Various issues such as energy balancing of the nodes and the fault tolerance of WSNs due to transmission delay and channel availability can be given focus while designing a WSN. Other meta-heuristic algorithms can also be implemented to this problem to study the improvement in performance, if any. The proposed algorithm can be put to use to heterogeneous networks consisting of static and dynamic nodes. The authors of this work are trying to implement the idea in real life scenario with help of industries.

References

[1] W. Rehan, S. Fischer, M. Rehan, M.H. Rehmani, “A comprehensive survey on multichannel routing in wireless sensor networks”, Journal of Network and Computer Applications, Elsevier, vol. 95, 2017, pp. 1-25. [2] W. B. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, “Energy Efficient Communication Protocol for wireless microsensor network”, 33rd International Conference of System Sciences, IEEE, 4-7 Jan, 2000, Hawaii, US. [3] O. Younis, S. Fahmy, “HEED: Hybrid energy efficient distributed clustering approach for Ad Hoc sensor networks”, IEEE Transactions on Mobile Computing, vol. 3(4), 2004, pp. 366–379. [4] M. Yu, K. K. Leung, A. Malvankar, “A dynamic clustering and energy efficient routing technique for sensor networks”, IEEE Transactions on Wireless Communications, vol. 6(8), 2007, pp. 3069-3079. [5] P.Agarwal, C. Procopiuc, “Exact and approximation algorithms for clustering”, Algorithmica, Springer, vol. 33, 2002, pp. 201-226. [6] A. M. Zungeru, L. M. Ang, K. P. Seng, “Classical and swarm intelligence based routing protocols for wireless sensor networks: a survey and comparison”, Journal of Network and Computer Applications, vol. 35, 2012, pp. 1508–1536. [7] V. Halder, N. Chakraborty, “A novel evolutionary technique based on electrolocation principle of elephant nose fish and shark: fish electrolocation optimization”, Soft Computing, Springer, vol. 21(14), 2016, pp. 3827-3848. [8] W. B. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, “An application specific protocol architecture for wireless microsensor networks”, IEEE Transactions on Wireless Communication, vol. 1(4), 2002, pp. 660-670. [9] K. Abbas, S.M.Abedini, Z.Faraneh, S.A.R. Al-Haddad, “Cluster head selection using fuzzy logic and chaotic based genetic algorithm in wireless sensor network”, Journal of Basic and Applied Scientific Research, vol. 3 (4), 2013, pp. 694–703. [10] P. Kulia, P.K. Jana, “A novel differential evolution based clustering algorithm for wireless sensor networks”, Applied Soft Computing, Elsevier, vol. 25, 2014, pp. 414-425. [11] J. R. Parvin, C. Vasanthanayaki, “Particle Swarm-optimization based clustering by preventing residual nodes in wireless sensor networks”, IEEE Sensors Journal, vol. 15(8), 2015, pp. 4264-4274. [12] R. Logambigai, A. Kannan, “Fuzzy logic based unequal clustering for wireless sensor networks”, Wireless Networks, Springer, vol. 22(3), 2016, pp. 945-957. [13] P.C. Rao, H. Banka, “Energy efficient clustering algorithms for wireless sensor networks: Novel chemical reaction optimization approach”, Wireless Networks, vol. 23 (2), 2015, pp. 433–452. [14] J. Jung, T. Park, C. Kim,“A forwarding scheme for reliable and energy-efficient data delivery in cluster-based sensor networks”, IEEE Communication Letters, vol. 9(2), 2005, pp. 112–114. [15] Arnab Ghosh, Niladri Chakraborty, “Cascaded Cuckoo Search Optimization of Router Placement in Signal Attenuation Minimization for Wireless Sensor Network in Indoor Environment”, Engineering Optimization, Taylor & Francis, vol.51(12), 2019, pp. 2127- 2146, doi: 10.1080/0305215X.2019.1569645 [16] G. P. Gupta, S. Jha, “Integrated Clustering and Routing Protocol for wireless sensor networks using Cuckoo Search and Harmony Search based meta-heuristic techniques”, Engineering Applications of Artificial Intelligence, Elsevier, vol. 68, 2018, pp. 101-109. [17] Anurag Kumar, D. Manjunath, Joy Kuri, Chapter 10, Wireless Networking, Elsevier Publications, pp.337-372. [18] P.C. Srinivasa Rao, P.K. Jana, H. Banka, “A particle swarm optimization based energy efficient cluster head selection algorithm for wireless sensor networks”, Wireless Networks, Springer, vol. 23(7), 2017, pp. 2005-2020. [19] MATLAB-www.mathworks.com/matlab 2013. [20] A. Bari, A. Jaekel, S. Bandhyopadhyay, “Clustering strategies for improving the lifetime of two-tiered sensor networks”, Computer Communications, Elsevier, vol. 31(14), 2008, pp. 3451–3459.

Copyright

Copyright © 2022 Arnab Ghosh. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.