Energy Efficient Clustering Algorithms for Wireless Sensor Networks

Dr. Mukta Agarwal; Dr. Pravin H. Bhathawala; Harish Morwani

doi:10.17577/IJERTCONV9IS05080

ICRADL - 2021 (Volume 09 - Issue 05)

Energy Efficient Clustering Algorithms for Wireless Sensor Networks

DOI : 10.17577/IJERTCONV9IS05080

Download Full-Text PDF Cite this Publication

Open Access
Article Download / Views: 118
Authors : Dr. Mukta Agarwal, Dr. Pravin H. Bhathawala, Harish Morwani
Paper ID : IJERTCONV9IS05080
Volume & Issue : ICRADL – 2021 (Volume 09 – Issue 05)
Published (First Online): 01-04-2021
ISSN (Online) : 2278-0181
Publisher Name : IJERT
License: This work is licensed under a Creative Commons Attribution 4.0 International License

PDF Version

View

Text Only Version

Energy Efficient Clustering Algorithms for Wireless Sensor Networks

Dr. Mukta Agarwal, Dr. Pravin H. Bhathawala, Prof. Harish Morwani

Abstract-Energy efficiency is a major concern in Wireless Sensor Networks (WSNs). Many clustering algorithms have been proposed for such a purpose. This paper investigates the existing clustering algorithms. The algorithms have been classified and some representatives are described in each category. After analyzing the strengths and the weaknesses of each category, an important characteristic of WSNs is pointed out for further improvement of energy efficiency for WSNs.

INTRODUCTION

Since the energy supply for sensor nodes is very limited, it is important to improve the efficiency of the energy for wireless sensor networks (WSN). The most efficient organization- clustering is being applied widely in the recent past. In cluttering algorithms, the nodes that are geographically closer are arranged into groups, and every group is called a cluster. In every cluster the nodes are given roles, like cluster head (CH), member nee or gateway nodes.

The clustered is the coordinator for its cluster, and performs tasks like,
- Arrangements for intra cluster transmissions
- Aggregation of data
- Cluster maintenance
- Data forwarding
The gateway nodes are present in more than one cluster, and forward data between different clusters. They are not essential for clustered wireless sensor networks. For a clustered WSN, the clustered and gateway is its backbone. The member nodes dont have clustered nodes and they dont have any links inter clusters.

This paper studies the energy efficient clustering algorithms for WSNs that can be accessed.
ENERGY MODEL

That energy model that has been used in this paper is like the one used by many energy efficient cluttering algorithms.

It shows the energy consumption E in sending a units of data between nodes: E=ET+ER=aÃ—(e +e Ã—dn)+aÃ—e tamp r (1) where ET and ER are the energy consumptions of transmitting and receiving data respectively. The energy dissipated in operating the transmitter radio, transmitter amplifier and receiver radio are expressed as e, e and e tamp r respectively.

Furthermore, d is the distance between nodes and n is the parameter of power attenuation with (2 n 4).
ALGORITHM LASSIFICATION

The efficient of energy is a major challenge of wireless sensor network. The clustering scheme attempts to decrease the consumption of power in order to increase the lifespan of network. Below are the classifications of the existing cluttering algorithms into 6 categories:

Aggregating data: To reduce the amount of data that needs to be sent to the sink

Rotating the role of CH: To distribute the higher burden of a CH among the nodes

Equalizing cluster size: To balance the burden among the clusters

Locating CH in the central area of the cluster: To reduce the total power consumption of intra-cluster communication Assigning the lowest needed power to the nodes: To minimize the power consumption of each hop

Optimizing route using different power level clusters: To select the route with the lowest energy to relay the data
1. Aggregating Data
  
  Transmitting the data for processing after systematic collection of the data is the primary operating in a wireless sensor network (WSN). The challenge in this kind of data collection is to save the sensor energy in order to maximize the sensor life, and therefore the network lifetime. Data aggregation has now become a basic tenet in wireless sensor network. The main idea is to aggregate data from various sensors to reduce the repeated transmissions. Two methods have been proposed to aggregate data in the clustered WSN: Requiring a CH for aggregating data after collecting data from all the member nodes, and before communication in another cluster occurs.Aggregating data over each passing hop.
  
  Local data aggregating is applied by the low energy adaptive clustering hierarchy (LEACH) in order to decrease global communication. Before sending the data to the sink, CH aggregates the collected data at the end of every data transmission period, in this algorithm.
  
  An algorithm was proposed by Chen and Megerian, in which closet sizes are based on the correlation of sensor data. When there is high correlation, larger clusters are formed, and it leads to multi hop routes to the cluster head. In order to reduce the amount of data which is transmitted, data is aggregated at each hop on it was to the cluster head.
2. Rotating the Role of the CH
  
  The cluster heads of WSN lose energy more quickly than member nodes because they have more burdens. Rotation of cluster head role helps in distribution of increased burden, and therefore premature death of cluster head is prevented.
  
  Network lifetime is divided in rounds by LEACH. A round consists of a set up phase and a steady phase. In the set up phase, it is determined locally by each node if itll become a CH or not. It depends on the nodes remaining energy. The ones that have high energy remaining get an advantage. Then clusters are formed by the nodes that are not cluster heads. They join a cluster head based on the strength of the signal of the advertisements they received from the cluster heads. It
  
  has been observed that in comparison to the schemes where the cluster heads remains fixed, LEACH leads to reduced consumption of the energy and leads to improved network lifetime.
  
  Cluster Head Election Protocol (CHEP) was proposed by Liu and Lin. It bases the selection of the cluster head based on the energy remaining in the member nodes. According to them, once a cluster has been formed with a cluster head, all the member nodes are going to send their remaining energy to the cluster head only by one. The one with the highest energy value remaining becomes the successor. That node becomes the cluster head for that cluster cycle.
  
  A centralized algorithm for clustering was proposed by Muruganathan for organizing clusters better. It is assumed that the base station (sink) has computational power and resources, and so the task of division of the network into clusters and selection of the cluster heads is performed by it. The algorithm comprises of setup and communication phases. In the set up phase, every node sends its remaining node value to the case station, and then the base station determines the nodes which have the higher energy remaining. Out of all the nodes, only a certain number of them will become the cluster heads. Therefore the burden of being the cluster head is thus distributed though the repetition of this process.
3. Equalizing Cluster Size
  
  Rotation of the cluster head role leads to a balanced consumption of power amongst the nodes. It can even be more balanced if the burden on the clusters is similar. therefore, many algorithms of clustering, assign almost equal number of nodes to all the clusters. Muruganathan et al. proposed the Base Station Controlled Dynamic Clustering Protocol (BCDCP), uses the base station for dividing networks intro clusters of equal size. After the cluster head is selected, use station splits the networks in two clusters, after selecting 2 nodes which have the highest separating distance for being the cluster head of each cluster. Then nodes are allocated to each cluster, on the basis of the distance, before they are divided into equal number of nodal clusters. Every Custer is divided and it is continued till the time required number of cluster heads are allocated.
  
  Two lgorithms- rapid and persistent were proposed by Krishnan and Starobinski, for the efficient clustering of message, with local cluster size bounds. Every cluster initiator has a budget for the members of clusters in both the algorithms. The budget is split between the neighboring nodes in the rapid algorithm system. The neighboring nodes of the closer heads, mimic the cluster head, and pass on their remaining budget to their own neighbors. If the nodes are not able to allocate their full budget, it can lead to smaller cluster sizes. In the persistent algorithm, it is taken into account that neighboring nodes may not be able to allocate the entire budget to the neighbor. So the nodes forward the remaining budget to the cluster head, so that it can be distributed for better balance of the cluster size.
4. Locating the CH in the Central Area of the Cluster
  
  The location of the closet head in the cluster also affects the total power consumption of the cluster. Section of a node as the cluster head in the centre of the cluster, leads to reduced total power consumption in the intra-cluster communication. Energy for the relaying data is saved, as in the multi hop cluster, member node sends the data to the cluster head through a multi hop route, and number of hops is minimized. In a single hop cluster also the power consumption is saved, as all the member nodes send the data to the cluster head, and the sum of the squares of the distance reduces.
  
  A scheme for clustering and routing for aggregating data was proposed by Chen and Megerian. It was proposed that the cluster head should be selected which is central in the cluster and dispersed within the network. The maximum numbers of minimum hops (max-min hops) that are needed for communicating with all the others nodes in the cluster are determined by each node. The nodes which have the least max-min hops are eligible for becoming the cluster heads.
  
  Ghiasi et al. considered optimization of the cluster formation, by calculating the distance between the cluster heads with all the nodes, which it can support for the formation of the clusters. Clusters are selected on the basis of the minimum total square of the distances between the cluster head and the member nodes. Energy consumed during the process when the member nodes send data to the CH will be reduced significantly according to (1) when n=2.
5. Assigning the Lowest Needed Power to the Nodes
  
  In this algorithm, the power consumption of every link is reduced, by assignment of the lowest power to the member node or the cluster head, for communication within the cluster. Also lowest power needed is given to the gateway nodes, for the communication inter clusters.
  
  According to the algorithm in (28) assumes that every node has the capacity to adjust the power of transmission so that each link that can be assigned to every node. Firstly, clusters are created by grouping the nodes that are closer in network, so that the transmission range reduces.
  
  Simulated annealing algorithm is used for it. While maintaining the connection within the cluster, it assigns every node in the cluster the lowest transmission power. The pair of nodes having minimum distance between 2 clusters, they are chosen as the gateway nodes. These nodes then release the communication between the cluster heads.
  
  The final step is assigning the lowest possible power of consumption to the gateway nodes, in order to maintain the backbone of the network.
6. Optimizing Route Using Different Power Level Clusters Almost all clustering algorithms, assume a wireless sensor network with uniform node distribution. However, the sensor nodes are not always evenly distributed in the network, and so different areas may be having different node densities. The nodes in an area may be crossing each other by using a low transmission power through multi hops. But, they may not be able to reach the nodes that are in other areas with the help pf low transmission power. So, the nodes may be organized in clusters with varying power levels. This leads to energy saving.
  
  For non homogeneous spaced networks, Kawadia and Kumar proposed CLUSTERPOW. The nodes are grouped on the basis of energy levels, and there are no cluster heads in this protocol. The nodes belong to multiple clusters of various transmission energy levels. The source selects a path to the destination with the help of the hops which need lower transmission power level. This happens for the transmission of messages from the source to the destination. Therefore, energy consumption is decreased.
ANALYSIS OF ALGORITHMS

The algorithms which have been described in the earlier sections improve the efficiency of the energy of wireless sensor networks:

Algorithms using aggregation of data lead to decreased amount of data to be sent, and therefore reduce the energy of the routing data to the cluster heads or to the sinks.

Since cluster heads have more burden than member nodes, rotations of the cluster heads leads to sharing of burden and therefore extends the useful lifetime.

Clusters that have more number of nodes have higher burden, as their cluster heads have to receive, aggregate and transmit data from all the nodes. Also when the distance between the nodes and the cluster heads is more, more hops are required for the data to reach the cluster head and therefore more transmission power is used. So, equalizing the cluster sizes is a better option.

Section of nodes which are in the centre of the cluster as the cluster head leads to decreased power consumption of the communication within the cluster. But, many algorithms achieve this with re-clustering of nodes with ripple effect. This clustering again and again many lead to energy consumption.

By assigning the lowest transmission power to the nodes, power consumption can be decreased, where they are aware of the local information, and where they aRe Abe to adjust their power.

Organizing the nodes into clusters with different power levels in WSNs with uneven node distribution improves energy efficiency by optimizing the different power level hops and also increases network capacity.
CONCLUSION

In this paper, recently proposed clustering algorithms for wireless sensor networks have been studied. They were classified into aggregating data, equalization of cluster sizes, rotating of the role of the cluster heads, locating the cluster head in the centre of the clusters, assigning lowest required power to nodes and optimizing routes with the help if different power level clusters. The main features of the categories were summarized and some of the algorithms were also discussed. Then the strengths and weaknesses of each one of them were analyzed. The analysis shows that the energy efficient clustered wireless sensor network can be improved even more by equalization of the Cluster lifetime by considering that the directional data traffic bidders the clusters in a different manner. Another conclusion is that the performance of sending data to the sing can also be further optimized by equalizing the cluster lifetime. This will stop the premature node or cluster death, and the data which is delivered to the sink will be carrying information for the entire network.

REFERENCES

N. Vlajic and D. Xia, Wireless Sensor Networks: To Cluster or Not to Cluster? Proc. Of WoWMoM06, 2006.
D. Wei, Clustering Algorithms for Sensor Networks and Mobile Ad Hoc Networks to Improve Energy Efficiency, PhD thesis, University of Cape Town, Sep. 2007.
J. Yu and P. Chong, A Survey of Clustering Schemes for Mobile Ad Hoc Networks,IEEE Communication Surveys, 7(1): 32-48, March 2005.
D. Wei and H. A. Chan, 'Clustering Ad Hoc Networks: Schemes and Classifications,Proc. of IEEE SECON'06 under the track of IEEE IWWAN 2006, pp. 920-926, June 2006.
W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, Energy- efficient Communication Protocol for Wireless Microsensor Networks, Proc. of the 33rd IEEE Hawaii International Conference on System Science, Jan. 2000.
H. Chen and S. Megerian, Cluster Sizing and Head Selection for Efficient DataAggregation and Routing in Sensor Networks, Proc. of IEEE WCNC 2006.
J.-S. Liu and C.-H. R. Lin, Energy-Efficiency Clustering Protocol in Wireless SensorNetworks, Ad Hoc Networks, vol. 3, pp. 371-388, May 2005. D. Wei, H. A. Chan and K. V. N. Kameri, Circular-Layer Algorithm fr Ad Hoc Sensor Networks to Balance Power Consumption Proc. of IEEE SECON'06 under the track of IEEE IWWAN 2006, pp. 945-950, June 2006.
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless Sensor Networks: A Survey, Computer Networks, vol. 38, pp. 393-422, 2002.
K. Dasgupta, K. Kalpakis and P. Namjoshi, An Efficient Clustering- Based Heuristicfor Data Gathering and Aggregation in Sensor Networks, Proc. of IEEE WCNC, pp. 1948-

1953, 2003,
B. Krishnamachari, D. Estrin and S. Wicker, The Impact of Data Aggregation inWireless Sensor Networks, Proc. of Intl. Workshop on Distributed Event-Based Systems,

2002.
S. D. Muruganathan, D. C. F. Ma, R. I. Bhasin and A. O. Fapojuwo, A Centralized Energy-Efficient Routing Protocol for Wireless Sensor Networks, IEEE Radio Communications, pp S8-S13, March 2005.
M.Ye,C.Li,G.ChenandJ.Wu,EECS:AnEnergyEfficientClustering Scheme in Wireless
Sensor Networks, Proc. of IPCCC 2005, pp. 535- 540, April 2005.
Y. He, Y. Zhang, Y. Ji and X. Shen, A New Energy Efficient Approach by Separating Data Collection and Data Report in Wireless Sensor Networks, Proc. of ACM IWCMC06, pp. 1165-1170, July 2006.
O. Younis and S. Fahmy, HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks, IEEE Transactions on Mobile Computing, 3(4): 366-379, 2004.
X. Du and Y. Xiao, Increasing Network Lifetime by Balancing Node Energy Consumption in Heterogeneous Sensor Networks, Wiley Journal of Wireless Communications and Mobile Computing (WCMC), 2006, DOI: 0.1002/wcm.452, in press. [17] G. Pei and C. Chien, Low Power TDMA in Large Wireless Sensor Networks, Proc. of IEEE MILCOM, pp. 347- 351, October 2001.
W. Wang and A. Jantsch, An Algorithm for Electing Cluster Heads Based on Maximum
Residual Energy, Proc. of ACM IWCMC06, pp. 1465-1470, July 2006.
Z. El-Bazzal, M. Kadoch, A. L. Agba, F. Gagnon and M. Bennani, An Efficient Management Algorithm for Clustering in Mobile Ad Hoc Network, Proc. of PM2HW2N06, pp. 25-31, Oct. 2006.
S. Ghiasi, A. Srivastava, X. Yang and M. Sarrafzadeh, Optimal Energy Aware

Clustering in Sensor Networks, Sensors, pp. 258-269, Jul. 2002.
S. Bandyopadhyay and E. J. Coyle, An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks, Proc. of IEEE INFOCOM, pp. 1713-1723, 2003. [22]
R. Krishnan and D. Starobinski, Efficient Clustering Algorithms for Self-Organizing Wireless Sensor Networks, Ad Hoc Networks, 4(1): 36- 59, Jan. 2006.
L. Ramachandran, M. Kapoor, A. Sarkar and A. Aggarwal, Clustering Algorithms for Wireless Ad Hoc Networks, Proc. of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 54-63, August 2000.
G. Gupta and M. Younis, Load-Balanced Clustering of Wireless Sensor Networks, Proc. of IEEE ICC, pp. 1848-1852, 2003.
W. B. Heinzelman, Application-Specific Protocol Architectures for WirelessNetworks, PhD Thesis, Massachusetts Institute of Technology, June 2000.
Y. Zhou, M. Hart, S. Vadgama and A. Rouz, A Hierarchical Clustering Method inWireless Ad Hoc Sensor Networks, Proc. of IEEE ICC 2007.
P. Wang, C. Li and J. Zheng, Distributed Minimum-Cost Clustering Protocol forUnderWater Sensor Networks (UWSNs), Proc. of IEEE ICC 2007.
K. S. Manousakis and J. S. Baras, Clustering for Transmission Range Control and Connectivity Assurance for Self Configured Ad Hoc Networks, Proc. of IEEE MILCOM, pp. 1042-1047, 2003.
V. Kawadia and P. R. Kumar, Power Control and Clustering in Ad Hoc Networks,
Proc. of IEEE INFOCOM, pp. 459-469, 2003.
Gachhadar, A., Acharya, O.N.: K-means based energy aware clustering algorithm in wireless sensor network. Int. J. Sci. Eng. Res. 5(5), 156161 (2012)
Abbasi, A.A., Younis, M.: A survey on clustering algorithms for wireless sensor networks. Comput. Commun. 30(1415), 28262841 (2007)
Sisodia, D., Singh, L., Sisodia, S., Saxena, K.: Clustering techniques: a brief survey of different clustering algorithms. Int. J. Latest Trends Eng. Technol. (IJLTET) 1(3), 8287 (2012)
Shokrollahi, A., Mazloom-Nezhad, M.B.: An energy-efficient clustering algorithm using fuzzy C-means and genetic fuzzy system for wireless sensor network. J. Circuits Syst. Comput. 26(01), 1750004 (2017)
Chen, J.: Improving life time of wireless sensor networks by using fuzzy c-means induced clustering. In: World Automation Congress (WAC), pp. 14. IEEE (2012)
Gupta, G.P.: Improved cuckoo search-based clustering protocol for wireless sensor networks. Procedia Comput. Sci. 125, 234 240 (2018)
Agrawal, D., Pandey, S.: FLIHSBC: fuzzy logic and improved harmony search based clustering algorithm for wireless sensor networks to prolong the network lifetime. In: International Conference on Ubiquitous Computing and Ambient Intelligence, pp. 570578, Springer, Cham (2017)
Rajpurohit, J., Sharma, T.K., Abraham, A., Vaishali, : Glossary of metaheuristic algorithms. Int. J. Comput. Inf. Syst. Ind. Manage. Appl. 9, 181205 (2017)
Kaur, S., Mahajan, R.: Hybrid meta-heuristic optimization based energy efficient protocol for wireless sensor networks. Egypt. Inf. J. (2018)
Sharma, R., Vashisht, V., Singh, A.V., Kumar, S.: Analysis of existing clustering algorithms for wireless sensor networks. In: System Performance and Management Analytics, pp. 259277. Springer, Singapore (2018)

Node	Single hop	Multi-hop with variable necessary tx
1	5237	908
2	1591	986
3	734	1073
4	419	1187
5	270	1396

Node	Lifetime	Allocated Energy
1	1564	0.8545
2	1559	0.6772
3	1551	0.5000
4	1533	0.3227
5	1474	0.1456

Node	Single hop	Multi-hop with variable necessary tx
1	5237	908
2	1591	986
3	734	1073
4	419	1187
5	270	1396

Node	Lifetime	Allocated Energy
1	1564	0.8545
2	1559	0.6772
3	1551	0.5000
4	1533	0.3227
5	1474	0.1456

Energy Efficient Clustering Algorithms for Wireless Sensor Networks

Leave a Reply