Unequal Clustering Methods in Wireless Sensor Networks

Abstract

Due to its many applications, WSN has become a crucial technology for ubiquitous living and is still being actively researched. An important design consideration for WSN is energy awareness. The most common energy-efficient strategy, clustering offers numerous advantages, such as improved energy efficiency, extended lifetime, enhanced scalability, and reduced latency. However, it can also introduce the issue of creating hot spots. Uneven clustering is suggested as a remedy. When there is unequal clustering, the base station (BS) distance directly affects how big the cluster is. We were motivated to conduct this analysis because there were no current, in-depth survey articles that used unequal clustering methodologies. This research provides a comprehensive examination of various unequal clustering methods, along with their objectives, characteristics, and more. Furthermore, classifications of unequal clustering approaches are established and compared based on various cluster features, Cluster Head (CH) properties, and the clustering method employed.

Introduction

I. INTRODUCTION

The rapid advancement in integrated circuits (IC) and information technology (IT) has given rise to the production of affordable sensor nodes characterized by compact form factors. Wireless Sensor Networks (WSN) play a pivotal role in the Internet of Things (IoT), facilitating the exchange of data among billions of devices to enhance user management of the environment. WSNs are networks comprised of multiple sensor nodes positioned in an unstructured manner, designed for the purpose of observing and engaging with the physical world. Every sensor node consists of four essential components: sensors, power supplies, microcontrollers, and transceivers. The sensors within the sensing unit monitor various physical properties, including pressure, humidity, vibration, temperature, infrared radiation, vehicle movement, and more in the actual world.Following the processing of the sensed data by the processing unit, the communication unit transmits this information to the base station (BS) either directly in a single hop or through intermediary nodes. WSN finds widespread applications in real-time monitoring and tracking, including areas such as military surveillance, industrial automation, disaster management, inventory control, and more. WSN is commonly employed in locations where human intervention is difficult or impractical. In the design of WSNs, issues with energy usage, bandwidth, and memory are key concerns. Due to the hostile environment in which the sensors are used, repairing or recharging the batteries is very challenging or impossible. A WSN has a higher transmission cost than processing and sensing costs. To extend the network's lifespan, data from sensor nodes must be  transmitted to the base station (BS) using an energy-efficient data transmission method.

 Clustering represents a crucial energy-efficient strategy. In this approach, sensor nodes are organized into clusters, collectively known as units. From the cluster's ordinary nodes, known as cluster members, a Cluster Head (CH) is selected. In a clustered Wireless Sensor Network (WSN), two types of traffic exist: inter-cluster traffic, involving data transfer between clusters   and intra-cluster traffic, involving data transmission within a cluster. Cluster members gather data from real-world parameters and transmit it to the Cluster Head (CH). After gathering the data to eliminate duplicates, the CH either directly or indirectly delivers the combined data to the CH. The cluster members are unable to transmit data directly to the Base Station (BS); they must instead send it to the CH, who then sends it to the BS.

The benefits of clustering include improved bandwidth utilisation, lower overhead, greater connection, a more stable network architecture, faster network response times, reduced routing table size and effective load balancing. Cluster Heads (CHs) located closer to the Base Station (BS) typically consume more energy and deplete their energy reserves more rapidly compared to CHs situated farther away from the BS.  Cluster Heads (CHs) that are in close proximity to the Base Station (BS) experience heavy traffic due to data aggregation, intra-cluster traffic originating from their own cluster members, and inter-cluster traffic from other CHs responsible for relaying data to the BS.

This situation can disrupt network connectivity, causing clusters near the Base Station (BS) to encounter coverage issues, which is commonly referred to as the "hot spot problem."

Cluster Heads (CHs) located closest to the Base Station (BS) tend to experience a high volume of traffic due to data aggregation, intra-cluster traffic from their own cluster members, and inter-cluster traffic from other CHs responsible for relaying data to the BS. With increasing distance between the Base Station (BS) and Cluster Heads (CHs), uneven clustering leads to larger cluster sizes for nodes farther away from the BS and smaller cluster sizes for nodes closer to the BS. The cluster size is directly related to the distance between Cluster Heads (CHs) and the Base Station (BS). Cluster size also grows with increasing distance from BS. A smaller cluster located in proximity to the Base Station (BS) is characterized by having fewer cluster members and lower levels of intra-cluster activity. Smaller clusters tend to prioritize inter-cluster traffic and allocate less energy towards intra-cluster traffic as a consequence. Larger clusters located farther from the Base Station (BS) are more likely to have a greater number of cluster members and utilize more energy for intra-cluster transmission. This eliminates the requirement for greater energy usage in inter-cluster routing and consequently reduces the energy needed for inter-cluster traffic. Unequal clustering ensures that Cluster Heads (CHs) located closer to the Base Station (BS) and those farther away from the BS expend approximately the same amount of energy. Hence, unequal clustering effectively distributes the network load and resolves the hot spot problem.

For optimized energy WSN, many clustering and uneven clustering approaches have been presented over the past ten years. Even while unequal clustering procedures have been the subject of numerous extensive surveys, few people have actually conducted one. The deployment regions of the nodes (square or circular), mobility, position awareness, and data aggregation are contrasted between the protocols. Probabilistic based uneven clustering algorithms are analysed. Another analysis of unequal clustering algorithms based on probability is offered. It assesses different protocols based on criteria such as the number of nodes, energy efficiency, cluster balance, location awareness, and heterogeneity level. We were motivated to carry out this work because there was a current, thorough survey of unequal clustering protocols missing. In the process of scrutinizing unequal clustering, this study conducts a comparison of different cluster attributes, the quality of Cluster Heads (CH), and clustering methods. It also delves into the objectives, characteristics, categorization, merits, and drawbacks of each methodology. The subsequent sections of the essay are organized as follows: Section 2 offers an introduction to unequal clustering, outlining its objectives and defining characteristics. Section 3 focuses on the classification of unequal clustering approaches, providing detailed descriptions of each method. Section 4 undertakes the task of comparing and tabulating various classification techniques. Section 5 concludes the paper, summarizing the key findings and insights presented throughout the essay.

II. INTRODUCTION ON UNEVEN CLUSTERING

The objectives and properties of uneven clustering are fully discussed in the section overview.

A. Unequal of clustering goals

With a few extra functions, unequal clustering has the same goals as equal clustering. In a WSN, the nodes are grouped according to various goals that are dependent on the needs of the applications. Uneven clustering most frequently aims to reduce energy consumption and get rid of hot spot issues. The following details a few of the extra goals.

1. Scalability

In accordance with the demands of the application, a significant quantity of sensor nodes, typically ranging from hundreds to thousands, is deployed in real-world scenarios. When building routing solutions, it is important to consider how well the system will function with this extensive quantity of sensor nodes. When a node within a cluster intends to transmit data to a node in another cluster, it becomes crucial for the nodes within the originating cluster to possess knowledge about the attributes of the corresponding receiving Cluster Head (CH). In order for a node within the cluster to transmit data to a node in a different cluster, it is essential for the cluster nodes to have information about the attributes of the respective receiving Cluster Head (CH). Consequently, the routing table becomes more compact and exhibits improved scalability.

2. Fault-Tolerant

In a number of applications, sensors are placed in extreme environments (helicopter drops, for example), increasing the danger of physical damage and node dysfunction. When using crucial applications where losing a small amount of sensor data might have disastrous results, fault-tolerant nodes are crucial. A secure and fault-tolerant WSN can be created effectively using clustering. The self-organized Wireless Sensor Network (WSN) effectively handles the issue by re-clustering the network.         Re-clustering disturbs current operations in addition to adding to the resource strain. Re-clustering, allocating backup CHs, deputising CHs, rotating CHs, and other similar strategies produce fault-tolerance with the benefit  of  sufficient load balance.

3. Data Fusion and Aggregation

There is a higher likelihood of data redundancy since a large number of sensors in the physical world sense the same data. Data aggregation serves as an effective technique for reducing the volume of transmissions and minimising redundant data transmission. This kind of signal processing combines all packets that have been received into one output packet. This method reduces extraneous noise while boosting the common data. In a Wireless Sensor Network (WSN), the Cluster Head (CH) consolidates all the data it collects from its cluster members and subsequently transmits this aggregated data to the Base Station (BS) through either a single hop or multiple hops. Consequently, this approach significantly reduces the overall network load and the number of transmissions.

4. Load balance

For the network to last longer, load balancing is essential. A significant problem is load balancing, where CHs are chosen among accessible network nodes. The CHs must have an even load distribution to avoid a hot spot issue.Each CH uses nearly the same amount of energy thanks to uneven clustering, which assures a dispersed load. Due of this, building a network with increased energy efficiency is easy.

5. Stabilized Network Topology

Cluster Head is chosen from each cluster of nodes, and Cluster Head is in charge of any changes to the cluster's topology. The Cluster Head (CH) maintains information about its cluster members, including their node IDs, locations, and energy levels.

 Hierarchical architecture makes it easier to manage network topology than flat architecture. Changes to the network topology caused by a node moving to a different cluster or dying are promptly recognised and reported by CH to BS for ensuring the proper maintenance of the network topology.

6. Prolonged lifespan

The fundamental goal of unequal clustering is to optimize the network's overall lifespan. Given the energy constraints of the sensors, enhancing network lifetime is crucial for real-time applications. Choosing nodes with a higher number of neighboring nodes as Cluster Heads (CHs) can effectively reduce intra-cluster communication. To maximise longevity, clustering and routing processes can potentially be integrated. By evenly distributing the CHs among the cluster members, unequal clustering increases the lifetime of WSNs. The longevity of the network can also be effectively increased by using sleep modes and cluster maintenance approaches.

B. Characteristics of Clustering

Different clustering algorithms are categorised using a variety of clustering features. The three unbalanced clustering features are thoroughly covered in this section.

1. Features of clusters
2. Characteristics of CH
3. Process properties for clustering

Features of clusters

Cluster properties, which encapsulate the cluster's characteristics, encompass aspects such as number of cluster, size of the cluster, inter-cluster communication  and intra-cluster communication.

Number of clusters

The production of a predefined or variable number of clusters depends on the requirements of the application. In certain cases, the proportion of cluster nodes can constitute 5% of all the nodes deployed in the network. When the CHs are chosen at random, the number of clusters varies in several applications.

Size of the cluster

Clusters of equal and unequal size can be separated based on the cluster size. A cluster's size is constant when it is dispersed uniformly across the network. The cluster size in uneven clustering is established depending on proximity to Base Station. The cluster size is smaller when the nodes are closer to the Base Station (BS) and progressively increases as the distance from the BS becomes greater.

Inter – cluster communication

Inter-cluster communication can occur through direct transmission or multi-hop communication. In large-scale Wireless Sensor Networks (WSNs), multi-hop techniques are frequently favored for energy-efficient data transmissions from Cluster Heads (CHs) to the Base Station (BS), with the data relayed through intermediary CHs. Single hop transmission is used in some small-scale WSN applications to connect the CH and BS.

Intra – cluster communication

An integral part of intra-cluster communication involves data transmission between a cluster member and its respective Cluster Head (CH). The nature of communication, whether direct or multi-hop, depends on the specific clustering algorithms employed. Data transmission inside a cluster in large scale WSN requires multi-hop communication.

Characteristics of CH

Data from cluster members are gathered by CH, who then aggregates the data before sending it directly or over many hops to BS.

Role of CH

The CH gathers information from those in its cluster, aggregates it based on performance, and then transmits it to the BS.

Process properties for clustering

Below is a list of the characteristics of the clustering process.

Clustering methods

Clustering can be done in two ways: centralised and dispersed. While distributed systems are frequently used in large scale WSN,A central authority, such as a BS or a super node, controls every part of the operation formation of cluster, selection of CH etc.) in centralised techniques.

Objective of Node grouping 

In this study, many nodes grouping aims have already been covered. for instance, load balancing and fault tolerance.

Nature

Clustering can be accomplished through reactive, proactive or hybrid approaches.The node continuously transmits the information it senses to the Cluster Head (CH). In the proactive clustering approach, the Cluster Head (CH) consistently sends data to the Base Station (BS). In the reactive clustering approach, the Cluster Head (CH) transmits data when the sensed value surpasses a predefined threshold. In hybrid circumstances, the Cluster Head (CH) sends data to the Base Station (BS) at longer predetermined intervals and also when the sensed value exceeds a predefined threshold.

Selection of CH

In Wireless Sensor Networks (WSN), the selection of Cluster Heads (CHs) can be accomplished using one of three methods: predefined types, attribute-based methods, or probabilistic approaches. In probabilistic methods, CHs are chosen at random without any prior thought. In the attribute-based method of selecting Cluster Heads (CHs), various metrics are considered, such as residual energy, node degree, node centrality, anticipated residual energy, distance to the Base Station (BS), and more. In the predefined approach, Cluster Heads (CHs) are selected in advance before the sensors are deployed in the sensing field.

III. CATEGORIZATION OF UNEQUAL CLUSTERING ALGORITHMS

Hundreds to thousands of sensor nodes make up the majority of WSNs. Uneven clustering is a practical way to set up plenty of nodes, distribute the load uniformly, and get rid of hot spots. The extensive literature review of reported uneven clustering techniques is included in this section. Fig. 3 shows how these three types of algorithms are organised hierarchically.

Probabilistic clustering

One of the key objectives of the probabilistic clustering method is to maximise network longevity. This approach uses a random selection mechanism to choose the CH. This clustering strategy has been found to be simple, close to ideal in overhead, quicker to converge, and energy efficient. The time complexity and message complexity of a clustering technique should be minimal. There are two different categories of probabilistic approaches: hybrid methods and random methods. Simple random techniques that choose CHs and randomly shaping the network can approach an optimal overhead level. By combining random methods with particular characteristics, such as residual energy or distance from the BS, hybrid approaches are employed to properly balance the clusters. due to the competitive or repetitive nature of hybrid strategies, their message and temporal complexity are increased. The section that follows is where we discuss about random approaches.

Deterministic algorithm 

Unlike probabilistic approaches, deterministic methods employ accepted measures to select CHs. At the local level, conventional metrics such as node centrality, projected residual energy, distance to the base station, remaining energy, and node degree are extensively utilized. Usually, neighboring nodes engage in exchanging information to keep it updated. The elected CH clusters are easier to manage, which explains why this strategy is known as a deterministic approach. These are further categorized into four groups: compound unequal clustering method, fuzzy method, heuristic method, and weight method. In the weight-based approach, the weight of each node is calculated considering multiple factors, such as remaining energy, node degree, proximity to the base station, among others. The cluster head is chosen as the node with the lowest weight among all the nodes. Fuzzy method is employed to designate cluster heads in situations where there is a higher degree of uncertainty. Cluster heads are selected using fuzzy input parameters. Since evolutionary algorithms can identify the optimal solutions for NP hard issues, the clustering problem in WSN is categorised as an NP hard problem. Heuristic-based clustering algorithms have provided the best solution for selecting CHs and cluster size in recent years. The use of heuristics is centralised, and BS or another central figure is in charge of managing network activity. Some solutions use agent nodes to work in a distributed manner under peculiar situations. Compound algorithms use a variety of metrics in clustering procedures, including connected graphs, Sierpinski triangles, etc.

Preset clustering algorithm

The CHs or clusters in the Preset clustering method are predetermined before being deployed in the real world. Network and static conditions are not considered, which is one of this approach's major shortcomings. Network topology varies often in WSN due to wireless link and node failures. These techniques may not be well-suited for real-time applications.

IV. DISCUSSION

Uneven clustering procedures can be divided into three groups: preset type algorithm, deterministic algorithm, and probabilistic algorithm. The use of probability-based algorithms is increased by their simplicity, energy efficiency, and quick convergence. There are two categories: random and hybrid. While random techniques are easy to use and achieve close to optimum overhead, they are inefficient energy savers. In hybrid approaches, random methods are combined with attributes such as residual energy or distance to the base station. Hybrid strategies tend to increase both message and temporal complexity due to their repetitive or competitive nature. Deterministic methods use some measures for CH selection and are not probability-based. Compared to probabilistic approaches, it is more trustworthy and controllable. Due to its complexity and delayed convergence, it is unsuitable for large scale WSN. It can be categorized into four groups: weight-method, fuzzy method, heuristic method, and compound techniques, as well as methods relying on multiple factors. The complexity of the message is increased by iterative weight-based methods. Algorithm execution and message exchange require more energy in fuzzy techniques. Heuristic methodologies require network-wide data and BS control. Heuristic techniques are often not feasible due to the centralised and time-consuming approach. The network's Quality of Service (QoS) requirements must consequently be balanced against the provisioning process's simplicity.In complex WSNs like environmental monitoring, the probabilistic approaches are easy to use, quickly converge, and perform well. Applications that require more dependability and durability can use deterministic algorithms. Heuristic technique is preferable for achieving optimal results in application-specific environments. Although the current methods are thoroughly evaluated, some aspects of clustering have not yet been looked into.

The majority of clustering techniques are static and incapable of adapting to changes in the network. So perhaps future research will concentrate on dynamic clustering. Second, the network's mobility is not taken into account. Three components can be mobile in a clustered WSN: the cluster members, CH, and BS. The frequent topology changes brought on by WSN with mobility result in higher overhead. Data-centric routing solutions are required since WSN are often data-centric. The majority of algorithms are created for proactive networks, and reactive networks have access to fewer strategies. Future research can focus further on clustering techniques for reactive networks.

Conclusion

Despite being a popular energy-efficient strategy, clustering has a hot spot issue and significantly reduces network lifetime. Uneven clustering maximises network longevity, removes hotspot issues, and distributes the load uniformly. These protocols are described along with their goals, traits, categories, benefits, and drawbacks. Probabilistic methods are well-suited for large-scale Wireless Sensor Networks (WSNs) like those used in environmental monitoring because of their simplicity and ability to achieve faster convergence. Deterministic clustering algorithms are suitable for applications that demand higher dependability and robustness. Heuristic clustering technique is preferable for achieving the best solution in an application-specific setting. All the assessed methods are compared by considering various cluster characteristics, Cluster Head (CH) attributes, and the clustering procedure.

References

[1] Abo-zahhad, M., Ahmed, S.M., Sabor, N., 2014. A new energy-efficient adaptive clustering protocol based on genetic algorithm for improving the lifetime and the stable period of wireless sensor networks. Int. J. Energy Inf. Commun. 5, 47– 72. http://dx.doi.org/10.14257/ijeic.2014.5.3.05. [2] Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E., 2002. Wireless sensor networks: a survey. Comput. Networks 38, 393–422. http://dx.doi.org/10.1016/ S1389-1286(01)00302-4. [3] Anastasi, G., Conti, M., Di Francesco, M., Passarella, A., 2009. Energy conservation in wireless sensor networks: a survey. Ad Hoc Netw. 7, 537–568. http://dx.doi.org/ 10.1016/j.adhoc.2008.06.003. [4] Bagci, H., Yazici, A., Member, S., 2010. An energy and proximity-based unequal clustering algorithm for wireless sensor networks. In: 39th Annu. IEEE Conf. Local Comput. Networks. 18–23. [5] Bagci, H., Yazici, A., 2010. An energy aware fuzzy unequal clustering algorithm for wireless sensor networks. IEEE Int. Conf. Fuzzy Syst., 1–8 (FUZZ) [6] Baranidharan, B., Santhi, B., 2016. DUCF: distributed load balancing unequal clustering in wireless sensor networks using fuzzy approach. Appl. Soft Comput. J. 40, 495–506. http://dx.doi.org/10.1016/j.asoc.2015.11.044. [7] Chen, G., Li, C., Ye, M., Wu, J., 2009. An unequal cluster-based routing protocol in wireless sensor networks. Wirel. Networks 15, 193–207. http://dx.doi.org/ 10.1007/s11276-007-0035-8. [8] Dorigo, M., Gambardella, L.M., 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1, 53– 66. http://dx.doi.org/10.1109/4235.585892. [9] Estrin, D., Heidemann, J., Kumar, S., Rey, M., 1999. Next Century Challenges: Scalale Coordination in Sesnor Networks. Admiralty Way. Inf. Sci. (Ny). [10] Ever, E., Luchmun, R., Mostarda, L., Navarra, A., Shah, P., 2012. UHEED – an unequal clustering algorithm for wireless sensor networks. Sensornets. [11] Fan, X., Du, F., 2015. Shuffled frog leaping algorithm based unequal clustering strategy for wireless sensor networks. Appl. Math. Inf. Sci. 1426, 1415–1426. [12] Gajjar, S., Sarkar, M., Dasgupta, K., 2014. ScienceDirect FAMACRO : fuzzy and ant colony optimization BASED MAC/routing cross-layer protocol for wireless sensor networks. Appl. Soft Comput. J., 235–247 [13] Gajjar, S., Talati, A., 2015. FUCP: fuzzy based unequal clustering protocol for wireless sensor networks. In: 39th Natl. Syst. Conf. 1–6. [14] Kaur, Gurmeet, Varsha, 2016. Review on hierarchical unequal clustering based protocols in Wireless Sensor Network. Int. J. Rec. Innov. Comput. Commun. 4, 96–99. [15] Gupta, V., Pandey, R., 2016. An improved energy aware distributed unequal clustering protocol for heterogeneous wireless sensor networks. Eng. Sci. Technol. Int. J. 19, 1050–1058. http://dx.doi.org/10.1016/j.jestch. 2015.12.015. [16] Heinzelman, W.B., Chandrakasan, A.P., Balakrishnan, H., 2002. An application- specific protocol architecture for wireless microsensor networks. IEEE Trans. Wirel. Commun. 1, 660–670. http://dx.doi.org/10.1109/TWC.2002.804190. [17] Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H., 2000. Energy-efficient communication protocol for wireless microsensor networks. In: Proc. 33rd Annu. Hawaii Int. Conf. Syst. Sci. 0, 3005–3014. doi:http://dx.doi.org/10.1109/ HICSS.2000.926982.

Copyright

Copyright © 2023 Brindha. T, Mrs. M. Raju. 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.