Energy Efficient Clustering Algorithms for Wireless Sensor Networks

Download Full-Text PDF Cite this Publication

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.

  1. 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.

  2. 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).

  3. 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.

  4. 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.

      1. The Impact of Directional Data Traffic on Lifetime of WSNs

        Table II shows the lifetime in rounds of the nodes in the linear network when eamp = 50 pJ/b/m2. The nodes can send data to the sink either by a single-hop route or by a multi-hop route. In case the node uses a multi-hop route, it can increase its transmission power to reach the next available node if its neighbor were to die.

        TABLE II Node Lifetime in Rounds when eamp = 50 pJ/p/m2.

        It can be seen that in a single-hop network, the first node dies at 270 rounds whereas in a multi-hop network the first node dies at 908 rounds. If we assume that the network dies when 50% of the area of the network is out of coverage, as the performance of the network under these conditions will be greatly reduced, then the network dies at 734 rounds for single- hop scenario and 1073 rounds for multi-hop scenario. Therefore choosing to use multi-hop route when available will extend the life of the network.

        If the nodes lifetimes are equalized then no node will die prematurely. Sensor nodes have limited maximum transmission ranges; therefore it is unreasonable to expect all nodes to be able to reach the data sink in a single hop in many networks. Residual energy in the nodes that can no longer reach the sink because the distance between themselves and (the next node to) the sink is greater than its maximum transmission range is wasted.

        If each node in Fig. 2 represents a cluster then the lifetime of different clusters can be equalized by allocating energy to the cluster in accordance with its burden. This can be realized by assigning different numbers of nodes to each cluster in a clustered WSN. In a homogeneous

        WSN with identical nodes and uniform node distribution, equalization of the cluster lifetime will result in clusters of different sizes.

      2. Improvement Achieved by Equalizing Node Lifetime Using P to express the total power consumption of a node and Einitial to express the initial energy of that node, to equalize node lifetime, (2) must be observed, in which const is a constant.

        Einitial /P=const

        The system in Fig. 2 has a total energy of 2.5 J as each node has 0.5J energy. Each node needs to relay a different data amount from others. This data amount is relevant to the node burden. If this 2.5J can be freely re-allocated to each node according to its burden, the node lifetime in the system as shown in Fig. 2 can be equalized.

        Table III shows the equalized lifetime of each node and the energy allocated to each node in the multi-hop system. The lifetime of the network when all nodes have the same initial energy is 1073 rounds when 50% dies. Yet this lifetime becomes 1551 rounds after the node lifetime is equalized. It can be seen that the lifetime of the network is extended substantially. In a clustered WSN, such energy allocation can be realized by allocating different number of nodes to different clusters according to their burdens.

        TABLE III Equalized Node Lifetime in Rounds and re- allocated Energy (J)

        when eamp = 50

        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

        Besides the network lifetime extension, the performance of delivering data to the sink is also improved. When some nodes die prematurely, the area monitored by these nodes will be out of coverage and thus the data that the nodes deliver to the sink are only from the partial network and cannot convey the full information of the network. Equalizing the node lifetime makes more data from the entire network be sent to the sink.

      3. Related Work

        Ye et al. improved LEACH by assigning lesser number of nodes to the cluster heads which are far from the sink, in order to compensate the higher burden (caused by the increased requirement of the power to reach the cluster head). However, sending data to the sink from one single hop is not feasible or efficient in terms of energy, especially when the sensor networks are large in size.

        As discussed earlier, a protocol was developed by Muruganathan et al., which creates clusters that are almost same in size, and use multi hop routing between the cluster head to the sink. The cluster head which hops in the last is selected randomly from all the cluster heads, in order to decrease the burden on the cluster heads which are located near to the sink. But this algorithm doesnt scale the large networks, because the cluster heads that are located at a distance from the sink, will not be having sufficient transmission power required for reaching the sink in one hop.

        TYPE TO ENTER A CAPTION.

        The directional data traffic going towards the sink is accommodated in (16) with the help of a chessboard configuration (fig 1) for wireless sensor networks that are heterogeneous. The network is divided into different clusters. Every grid has a cluster head (super node), which has more energy than the member nodes. In every grid, the member nodes that are located in close proximity to the cluster head will have more burden than the ones that are located farther, as they have to relay more data from the member nodes.

        The chessboard configuration will separate the network lifetime in 2 periods. In the first period, the cluster heads in the grids that have darker shades will be active. When they run out of energy, the first period comes to an end. Then the cluster heads in the grids with lighter shades become active and then the second period begins. The nodes that were close to the cluster head with more burden in the first period are far from the cluster head in the second period, and therefore the high burden gets distributed. For wireless sensor networks that are heterogeneous and in which nodes are more powerful than others, this algorithm is more suitable.

  5. 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

      1. N. Vlajic and D. Xia, Wireless Sensor Networks: To Cluster or Not to Cluster? Proc. Of WoWMoM06, 2006.

      2. D. Wei, Clustering Algorithms for Sensor Networks and Mobile Ad Hoc Networks to Improve Energy Efficiency, PhD thesis, University of Cape Town, Sep. 2007.

      3. J. Yu and P. Chong, A Survey of Clustering Schemes for Mobile Ad Hoc Networks,IEEE Communication Surveys, 7(1): 32-48, March 2005.

      4. 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.

      5. 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.

      6. H. Chen and S. Megerian, Cluster Sizing and Head Selection for Efficient DataAggregation and Routing in Sensor Networks, Proc. of IEEE WCNC 2006.

      7. 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.

      8. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless Sensor Networks: A Survey, Computer Networks, vol. 38, pp. 393-422, 2002.

      9. 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,

      10. 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.

      11. 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.

      12. M.Ye,C.Li,G.ChenandJ.Wu,EECS:AnEnergyEfficientClustering Scheme in Wireless

      13. Sensor Networks, Proc. of IPCCC 2005, pp. 535- 540, April 2005.

      14. 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.

      15. 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.

      16. 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.

      17. W. Wang and A. Jantsch, An Algorithm for Electing Cluster Heads Based on Maximum

      18. Residual Energy, Proc. of ACM IWCMC06, pp. 1465-1470, July 2006.

      19. 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.

      20. S. Ghiasi, A. Srivastava, X. Yang and M. Sarrafzadeh, Optimal Energy Aware

        Clustering in Sensor Networks, Sensors, pp. 258-269, Jul. 2002.

      21. 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.

      22. 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.

      23. G. Gupta and M. Younis, Load-Balanced Clustering of Wireless Sensor Networks, Proc. of IEEE ICC, pp. 1848-1852, 2003.

      24. W. B. Heinzelman, Application-Specific Protocol Architectures for WirelessNetworks, PhD Thesis, Massachusetts Institute of Technology, June 2000.

      25. Y. Zhou, M. Hart, S. Vadgama and A. Rouz, A Hierarchical Clustering Method inWireless Ad Hoc Sensor Networks, Proc. of IEEE ICC 2007.

      26. P. Wang, C. Li and J. Zheng, Distributed Minimum-Cost Clustering Protocol forUnderWater Sensor Networks (UWSNs), Proc. of IEEE ICC 2007.

      27. 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.

      28. V. Kawadia and P. R. Kumar, Power Control and Clustering in Ad Hoc Networks,

      29. Proc. of IEEE INFOCOM, pp. 459-469, 2003.

      30. 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)

      31. Abbasi, A.A., Younis, M.: A survey on clustering algorithms for wireless sensor networks. Comput. Commun. 30(1415), 28262841 (2007)

      32. 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)

      33. 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)

      34. 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)

      35. Gupta, G.P.: Improved cuckoo search-based clustering protocol for wireless sensor networks. Procedia Comput. Sci. 125, 234 240 (2018)

      36. 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)

      37. Rajpurohit, J., Sharma, T.K., Abraham, A., Vaishali, : Glossary of metaheuristic algorithms. Int. J. Comput. Inf. Syst. Ind. Manage. Appl. 9, 181205 (2017)

      38. Kaur, S., Mahajan, R.: Hybrid meta-heuristic optimization based energy efficient protocol for wireless sensor networks. Egypt. Inf. J. (2018)

      39. 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)

Leave a Reply

Your email address will not be published. Required fields are marked *