Welcome to Research Journal of Computer Science and Engineering

Abstract

The trend toward the adoption of IoT is increasing in recent years because of its diverse applications in various domains. In the next-generation technology with the Internet of Things (IoT), billions of smart objects will communicate with others and acquire information by themselves. We are looking at the development of an Internet of Things (IoT), where actual devices are in touch with computing devices sensors and actuators are in touch with the Internet, allowing them to host their created data on the IoT-based network. A mature IoT environment involves heavy data transmission causing bottleneck problems because factors like heterogeneity of devices, the Energy level of devices, and scalability affect the IoT-based network. The clustering algorithm put an important role in minimizing the consumption of energy and enhancing the lifetime of the network. This paper put a review of various clustering algorithm and suggest the best clustering algorithm for IoT-based Networks.

Keywords: Internet of Things; Clustering; Wireless Sensor Networks

Introduction

IoT connection has a meaningful impact on the state of life of people and also leads to economic benefits. Thus, IoT is attracting valuable identification from universities, industries, and governments in assisting the creation of newborn technologies and applications, such as modern homes and enterprises, healthcare, environmental monitoring, and smart cities. For such kinds of numerous IoT purposes, the sensed data must be sent to the Base Station (BS) for further operations. This should be accomplished through efficient routing protocols that are important components to hike data transmission, energy efficiency, and scalability in IoT-based networks. In this way development of a suitable routing mechanism is a crucial research domain. For solving such kind of problem clustering can be considered as a suitable mechanism.

Role of Clustering in IoT

• At the cost of cluster head (CH) in clustering, Energy consumption can be minimized.
• Clustering can be minimized topology maintenance overhead.
• Clustering enhanced the scalability of the network for IoT applications.
• Clustering enhances bandwidth utilization.
• Clustering enhances the stability of sensor nodes.

Clustering Technique

There are two techniques for clustering:

• Centralized Clustering: Centralized clustering involves the selection of CH in each cluster by central BS. The BS selects the cluster on the basis of some parameters such as hop count, node type, remaining energy, and minimum distance from BS, etc. The CH is static for a complete network lifetime. Thus, for every there is pre-defined CHs that perform data aggregation and forwarding tasks.
• Distributed Clustering: In this mechanism selection of clusters does not depend on the BS.ie there is no fixed CH. The nodes that match higher to specified parameters become cluster heads. After a certain interval of time when another member node becomes more eligible to form a cluster head, it forms the CH on its own.

Classification of clustering Algorithm

On the basis of cluster head selection and cluster range computation, the algorithm can be classified into the following category.

• Probabilistic
• Deterministic
• Fuzzy logic-based algorithm

Probabilistic Algorithms: Generally, probabilistic type clustering algorithms are simple and have less time and message complexity. This type of clustering algorithm selects the CHs randomly and have nearly optimal overhead, but can be combined with some standard parameter like node density, remaining energy, etc.., to create the cluster. The probabilistic Algorithm can be classified into two categories.

• Equal size probabilistic clustering algorithms.
• Unequal size probabilistic clustering algorithm.

a) Equal size probabilistic algorithms: Equal size clusters are generated with the help of an equal size probabilistic algorithm. These are some important probabilistic algorithms.

1. LEACH: Leach means low energy adaptive clustering algorithm. It is the wellknown clustering approach for WSNs. In this approach, some nodes are elected as cluster heads and other nodes join this cluster as cluster nodes if it is under the range of CHs. Responsibility CHs range is the communication of data between the nods and the transfer of data from sensor node to sink. In this mechanism, each node Si generates a random number between 0 and 1 compared with the defined threshold for that cluster. If the generated number is less than the defined threshold then node Si considers as CHs; otherwise, it acts as a non-cluster head for that round.

2. Centralized LEACH(C-LEACH): To overcome the drawback of the LEACH algorithm a new algorithm C-LEAH is derived. In the case of C-LEACH algorithms are executed at the BS. In the case of the LEACH algorithm, some low-energy nodes may be selected as CHs, which further depletes their energy. In the C-LEACH mechanism, each sensor sends its information like position and energy to the BS, which uses this information to form the cluster head. This cluster is formed by considering the objective to minimize the energy consumption of non-CHs during the data communication between the cluster nodes.

3. HEED Algorithm [10]: Heed means hybrid energy-efficient distributed clustering algorithm. In this mechanism CHs are selected on the base of the remaining energy of nodes and the non-CH node can join the cluster by considering inter-cluster communication cost.

4. Stable Election Protocol (SEP) [11]: In the SEP mechanism the node which has higher energy are called an advanced node. These advanced nodes are deployed in the defined area and act like CHs. Using the SEP it has been observed that the duration of the first and last node die increased nearly two times.

b) Unequal size probabilistic clustering algorithm: In this paradigm, the clustering algorithm forms the cluster of unequal size. The energy holes problem can be solved with the help of this mechanism. Cluster size can be energy-dependent or location-dependent.

1. Energy Driven Unequal Clustering (EDUC) [12]: It is one kind of distributed clustering algorithm that efficiently reduces the energy consumption problem and avoids the hurdles of hotspot formation for unequal size clusters. This algorithm is split in two phases: cluster formation and data collection phases. In the phase of cluster formation, CHs are selected randomly and these CHs served as cluster heads till the end of the network. During the data collection phase data, CHs transfer the data directly to the base station but such single-hop communication is not feasible for large size networks.

2. Unequal HEED [13]: It is the upgrade version of HEED that solves the problem of hotspot formation. In the case of HEED, each CH has the same cluster radius ignoring its distance from the BS, which points out the hotspot problem. UHEED defines unequal size cluster based on the distance of CH from the base station, the size of the cluster is bigger compared to those clusters formed near to BS. In this way, inter-cluster traffic communication is significantly reduced for the CHs nearest to BS.

3. Energy-Efficient Unequal clustering (EEUC) [14]: It is one kind of Hybrid algorithm, which is generally applied for periodic data collection for WSNs. In this case, cluster heads are selected randomly but deepened on the distance CHs from BS. This algorithm was able to support multi-hop routing for forwarding the data packet from CHs to BS. In this CHs are selected considering two parameters: residual energy and distance of forwarding CH to BS.

Deterministic Algorithms: In the case of deterministic algorithms CHs selection and cluster formation depend on some metric like residual energy, node degree, node centrality, distance from BS, etc. A node can get this information by exchanging the information with its neighbors. Because these clusters are formed in a manageable way due this reason it is called a deterministic algorithm. The deterministic Algorithm can be classified into two categories.

• Equal size deterministic clustering algorithms.
• Unequal size deterministic clustering algorithm

a) Equal Size deterministic clustering algorithm: These are some algorithms that generate clusters of equal size.

1. Energy-aware Routing Algorithm [ERA] [15]: In this routing algorithm CH has multiple next-hop nodes to forward its data then data is forwarded in proportion to their remaining energy. But ERA forms an equal size cluster due to this reason it forms a hot spot problem.

b) These are some algorithms that generate clusters of unequal size.

1. EADUC [16]: It is the balanced distributed multi-hop routing protocol that has minimum time and message complexity. In this paradigm, the CHs are selected by considering the ratio of the average energy of the node to the remaining energy of the node to avoid the problem of the hotspot. In this mechanism, unequal size clusters are formed by considering the residual energy and the distance from BS. On the way of routing, if the distance of the cluster head is less than the defined threshold then CH transmits it data directly to BS; otherwise, data is transmitted to BS by using some other nodes.

2. Arranging Cluster size and data Transmission WSNs (ACT) [17]: It is one type of unequal cluster-based routing protocol which able to balance the problem of energy dissipation in CHs.

Fuzzy-Based Algorithms: In a recent study, it has been observed that clustering for WSN depends on various parameters like residual energy, node degree, node centrality, distance from BS, etc. In this way, we can say that concept of fuzzy is very useful for clustering in WSN. Fuzzy-based clustering approaches can be classified into two categories: equal size and unequal size clustering approaches.

• Equal size Fuzzy based clustering algorithms

• Unequal size fuzzy-based clustering algorithms

a) Equal size Fuzzy-based clustering algorithms: These are some fuzzy-based clustering algorithms that generate a cluster of equal size.

1. Cluster Head Election Mechanism using Fuzzy logic: In this method, some tentative CHs are selected from an active node with the help of a probabilistic mechanism. CHs are selected with considering parameters like the energy of tentative nodes and their distance from the neighbor as fuzzy input. But such type probabilistic CHs selection mechanism leads to some low-energy nodes as CH, which will produce inefficient WSN.

2. Energy-aware distributed Clustering Protocol using Fuzzy logic (ECPF)[18]: In this fuzzy-based paradigm at the beginning of clustering, a set of tentative CHs are selected based on the residual energy of the node. Then, final CHs are selected considering the parameter like residual energy of node and node centrality of CHs.

b) Unequal size fuzzy-based clustering algorithms: Unequal size cluster has been defined to handle the hotspot problems, yet the size of the cluster is defined only considering the parameter like distance of CHs from BS. In recent years, some distributed clustering algorithm has been defined by considering some facts. These are some existing unequal clustering algorithms based on fuzzy logic.

1. EAUCF [19]: It means energy aware fuzzy approach unequal clustering algorithm and it is one kind of distributed clustering algorithm. In this algorithm residual energy of the node and distance of CHs from BS consider as fuzzy inputs.

2. DFCR algorithm [20]: It means distributed fuzzy logic based on unequal clustering and routing algorithm. It is the extended approach of EAUCF. In this approach, two parameters like node degree and node centrality are considered as fuzzy input for cluster range calculation. The cluster head selection is also performed considering residual energy and distance from BS as the selection parameter.

3. DECUC algorithm [21]: It means distributed fuzzy logic-based energy-aware and coverage preserving unequal clustering algorithm for WSN. In this approach, coverage significance considers as fuzzy input which ensures total coverage of the network. This type of algorithm is useful for that type of application where coverage is the primary concern.Clustering Algorithm for IoT Based Networks.

Apart from above discussed clustering algorithm number of clustering algorithms are available which suitable for IoT-based networks which are as follows.

Linked Cluster Algorithm (LCA): One of the early clustering algorithms was the Linked Cluster Algorithm. It was first designed for wired sensors, but it was later adapted for use in wireless sensor networks. This approach minimizes communication conflicts between nodes by utilizing TDMA frames for inter-node communication, with each frame including a communication slot for each node in the network. A node becomes the CH in the Linked Cluster Algorithm if it has the greatest identity among all nodes within one hop of it or among all nodes within one hop of one of its neighbors. Each node in LCA is given a unique ID number, and there are two ways to become a cluster head. The first is whether the node has the highest ID number across all neighbor nodes as well as the node itself. It becomes a cluster head in a second way if none of its neighbors are cluster heads.

LEACH and LEAC-C: Leach refers to a lowenergy adaptive clustering hierarchy that divides the network into clusters using a distributed method. Each node calculates his or her chances of becoming a CH and broadcasts the results. A node chooses its cluster so that reaching the CH involves the least amount of communication energy. By leveraging random rotation among CHs, the algorithm allows for energy balancing among nodes. CH nodes serve as routers, relaying data to the base station while also performing data fusion and aggregation on the data collected by the cluster.

Leach conserves energy by requiring each node to select a cluster based on the least amount of communication energy. Furthermore, there is no overhead in selecting a cluster head because each node makes its own decision. Because CH selection in LEACH is probabilistic, a situation could arise where a node with little energy is chosen as CH, putting the entire cluster in jeopardy. Furthermore, even when nodes can communicate directly with CH, LEACH may result in one-hop intra- and inter-cluster topology.

Hybrid Energy Efficient Cluster Algorithm (HEEC): Younis and Fahmy's Hybrid EnergyEfficient Distributed Clustering (HEED) [22] is a multi-hop WSN clustering technique that solves the LEACH algorithm's drawbacks of unevenly distributed CH. In terms of CH selection, the HEED algorithm differs from LEACH. In the CH election, a node's residual energy is introduced as a parameter. When compared to member nodes in HEED, elected CHs to have a relatively high average residual energy. Instead of sending aggregated data to the BS in a single-hop form as in LEACH, CHs communicate the data to the BS in a multi-hop fashion in HEED. In contrast to the LEACH protocol's single-hop approach, this encourages higher energy conservation and scalability. Even yet, the HEED algorithm has some flaws, as follows:

1) Cluster head rivalry may prevent some nodes from joining any clusters [23].

2) To generate clusters with a lot of packet broadcast, HEED requires numerous iterations.

3) Due to the relaying network traffic near the BS, the CH nodes closest to the BS consume significantly more energy. As a result, the CH nodes that are closer to the BS may fast deplete the battery.

Energy Efficiency Load-Balancing clustering (EELBC): EELBC is a clustering algorithm that uses a min-heap approach. The number of sensor nodes given to the cluster heads (CHs) is used to create a min-heap. We show that for n sensor nodes and m CHs, the algorithm executes in O (n log m) time.

Energy-efficient unequal clustering (EEUC): [24] is a competitive distributed uneven clustering technique in which cluster-heads are chosen based on their neighbor's high residual energy and distance from the base station (BS). Because the node could not interact directly with the BS due to the limited transmission range, EEUC divides the nodes into clusters of uneven size, with clusters closer to the base station having smaller sizes than those farther away from the BS. The competitive range is assigned to each node. This competitive range reduces the distance between the base station and the user. As a result, clusters closer to the base station are smaller in size, allowing the CH to conserve more energy for inter-cluster transmission while using less energy for intracluster communication because each node generates a random number between 0 and 1 in each cluster construction round to select whether or not to participate in the cluster-head election, the EEUC method is also a probabilistic clustering algorithm. If a sensor node chooses to participate in the cluster head election, it is designated as a tentative cluster head. In order to become a genuine cluster head, tentative cluster heads in local regions participate. The residual energy of each tentative cluster head is used in this competition. The remaining sensor nodes join the closest cluster when the cluster-head election is completed.

Energy Efficient multi-level clustering algorithm for large-scale WSN (EEMC): A cluster setup phase is followed by a data transmission phase in the EEMC [36]. Nodes transfer their residual energy to the sink, and level-1 CHs are elected based on higher residual energy and shorter distance to the sink, whereas neighbors of CH1 are elected based on distance and residual energy. At various levels, distinct Chs are formed, and data is transmitted in a multi-hop method.

Distributed Weight-Based Energy-Efficient Hierarchical clustering protocol (DWEHC): Each node in this algorithm [35] first locates its neighbors (in its enclosure region) before calculating its weight, which is dependent on its residual energy and distance from its neighbors. A cluster head is the greatest weight node in a neighborhood. The cluster head hierarchy will then be joined by neighboring nodes. The clustering procedure takes O (1) iterations to complete and is unaffected by network topology or size. The performance characteristics of DWEHC clusters are excellent.

Energy Efficient Clustering Schemes (EECS): The EECS [26] main goal is to extend the network's lifetime and increase the number of packets sent to mobile sinks in the network. The node's leftover energy, distance, and the in this approach, data overhead is taken into account while choosing a cluster head. The mobile sink's waiting time is approximated. The role of the sensor node is represented as a finite state machine based on the mobility model. The state transition is achieved using the Markov model.

Algorithm for cluster establishment (ACE): Sensor nodes are frequently joined into clusters to reduce channel contention, support scalability, and extend the lifetime of sensor networks. The Technique for Cluster Establishment (ACE) [27] is a sensor network clustering algorithm that uses three rounds of feedback to create a highly efficient cover of homogenous clusters across the network.

Grid clustering routing protocol for WSN (GROUP): A grid-clustering routing technique for large-scale wireless sensor networks that provides scalable and efficient packet routing In GROUP [28], the sink creates a cluster grid structure proactively, dynamically, and randomly. Only a small percentage of all sensor nodes will vote for cluster chiefs. GROUP can divide the energy burden throughout the network's sensors and provide in-network processing to limit the quantity of data that must be sent to the sink.

Energy-Aware clustering scheme with transmission power control (EACLE): EACLE [29] for wireless sensor networks is made up of three parts: "EACLE clustering" is a distributed clustering method based on transmission power control, "EACLE routing" builds a tree rooted at a sink node and sets the paths from sensor nodes while considering energy efficiency, and "EACLE transmission timing control" changes the transmission timing with different levels of transmission power to avoid packet collisions and facilitates paddling.

Power-efficient and adaptive clustering hierarchy (PEACH): The PEACH [30-37] protocol is a wireless sensor network clustering hierarchy protocol that is both power-efficient and adaptive. PEACH builds clusters without additional overhead and provides adaptive multi-level clustering by utilizing the overhearing properties of wireless communication. PEACH can also be utilized in both location-aware and location-insensitive wireless sensor networks. When compared to conventional clustering methods, PEACH considerably reduces node energy usage and increases network longevity. PEACH's performance is less influenced by sensor node dispersion than other clustering techniques.

Passive clustering (PC): The PC protocol is designed for mobile nodes in a passive clustering wireless sensor network. This approach does not rely on a packet control protocol and does not necessitate the reconstruction of the cluster topology after each CH exit or when its energy level falls below a certain level. The goal of this approach is to reduce overhead and conserve energy. Furthermore, it enables balanced energy consumption by network nodes and allows for the cluster architecture to be maintained for longer than passive clustering.

Conclusion

We analyzed numerous clustering algorithms often employed in the context of WSNs in this research. AI algorithms were classed based on energy efficiency, mobility, data aggregation, and network type. We also looked into the routing requirements of several IoT domains, such as smart healthcare, smart transportation, and environmental monitoring. It was discovered that applications like environmental monitoring, agriculture, and surveillance behave similarly to normal WSN applications, whereas applications like Smart Healthcare, Smart Home, and others encounter obstacles such as varied node types and mobility requirements. We recommended applicable clustering methods suitable for a certain domain based on the requirements of various IoT applications. Clustering algorithms appear to be a promising solution to the IoT's topology maintenance, energy requirements, and data aggregation problems. However, issues such as fault tolerance, service quality, and secure communication must be addressed.

References

1. Atzori L, Iera A, Morabito G. 2010. The internet of things: A survey. Computer Network. 54: 2787-2805.
2. Akyildiz I, Su W, Sankarasubramaniam Y. 2002. Wireless sensor networks: A survey. Computer Network. 38: 393-422.
3. Yick J, Mukherjee B, Ghosal D. 2008. Wireless sensor network survey. Computer Network. 52: 2292-2330.
4. Dada A, Thiesse F. 2008. Sensor applications in the supply chain: The example of quality-based issuing of perishables on Internet of Things. 4592: 140-154.
5. Ilic A, Staake T, Fleisch E. 2009. Using sensor information to reduce the carbon footprint of perishable goods. IEEE Pervasive Computer. 8: 22-29.
6. Gao T, Greenspan D, Welsh M. 2006. Vital Signs Monitoring and Patient Tracking over a Wireless Network.” In Proceedings of the 27th Annual International Conference of the Engineering in Medicine and Biology Society. 102-105. Ref.: https://pubmed.ncbi.nlm.nih.gov/17282121/ DOI: https://doi.org/10.1109/iembs.2005.1616352
7. Chatzigiannakis I, Mylonas G, Vitaletti. 2011. An Urban pervasive applications: Challenges, scenarios and case studies. Computer Sci Rev. 5: 103-118.
8. Sanchez L, Galache J, Gutierrez V. 2011. The Meeting Point between Future Internet Research and Experimentation and the Smart Cities. In Proceedings of the 2011 IEEE Future Network & Mobile Summit. 1-8.
9. Cuong Duc Truong. Routing and Sensor Search in the Internet of Things. Ph. D Dissertation Report From the Institute of Computer Engineering of the University.
10. Jiazi Yi, Thomas Clausen, Ulrich Herberg. 2015. Depth-First Forwarding for Unreliable Networks: Extensions and Applications. IEEE Internet of Things Journal. 2.
11. Weisheng Tang, Xiaoyuan Ma, Jun Huang. Toward Improved RPL: A Congestion Avoidance Multipath Routing Protocol with Time Factor for Wireless Sensor Networks. Journal of Sensors.
12. Lutando Ngqakaza, Antoine Bagula. 2014. Least Path Interference Beaconing Protocol (LIBP): A Frugal Routing Protocol for The Internet-of-Things. Wired/Wireless Internet Communications. 28: 148-161.
13. Adnan Aijaz, Hamid Aghvami. 2015. Cognitive Machine-to-Machine Communications for Internet-of-Things: A Protocol Stack Perspective. IEEE Internet of Things Journal. 2: 2.
14. JDR Nepomuceno, NMC Tiglao. 2017. Performance evaluation of 6TiSCH for resilient data transport in wireless sensor networks,” in Proceedings of the 31 International Conference on Information Networking. 552-557.
15. SG. 2012. Recommendation Short range narrowband digital radio communication transceivers phy and mac layer specifications,” Tech Rep. International Telecommunication Union, 2012.
16. J Nieminen, T Savolainen, M Isomaki. 2015. Ipv6 over BLUETOOTH® Low Energy. Tech Rep RFC. 7668.
17. Amol D, Rajesh P, Jayashree P. 2016. Routing Issue in Internet of Things: A Survey.
18. Quynh TN, Nien LM, Khoi NN. 2015. Multipath RPL protocols for greenhouse environment monitoring system based on Internet of Things. Electricalngineering/Electronics, Computer, Telecommunications and Information Technology. 3645: 103-234.
19. Adnan Aijaz, Hamid Aghvami. 2015. Cognitive Machine-to-Machine Communications for Internet-of-Things: A Protocol Stack Perspective. IEEE Internet of Things Journal. 2: 2.
20. Weisheng Tang, Xiaoyuan Ma, Jun Huang. Toward Improved RPL: A Congestion Avoidance Multipath Routing Protocol with Time Factor for Wireless Sensor Networks. Journal of Sensors.
21. Talwar M. 2015. Routing techniques and protocols for internet of things: a survey. Proceeding of the NCRIET-2015. 417-423.
22. Farah Nasri, Neila Moussa, Abdellatif Mtibaa. Internet of Things: Intelligent system for healthcare Based on WSN and Android.
23. Mehaseb AM, Yasser G, Hadia EH. 2013. WSN Application Traffic Characterization for Integration within the Internet of the Things. International Conference on Mobile Ad-hoc and Sensor Networks, IEEE.
24. Hasan OAS. 2015. Intelligent Traffic Information System Based on Integration of Internet of Things and Agent Technology. International Journal of Advanced Computer Science and Applications. 6: 2.
25. Omar Said. Mehedi Masud. 2013. Towards Internet of Things: Survey and Future Vision”, International Journal of Computer Networks (IJCN). 5: 1.
26. Paul Fremantle. 2014. A Reference Architecture for the Internet of Things. White paper.
27. Huasong C, Leung V, Chow C. 2009. Enabling technologies for wireless body area networks: A survey and outlook. IEEE Communications Magazine. 47: 84-93.
28. Swati Dewangan. 2017. Comparative analytics of centralized and distributed clustering algorithm for energy-efficient wireless sensor network. Research Journal of computer and Information Technology Science. 5: 2017.
29. Younis O, Fahmy S. 2004. HEED: A hybrid, energy-efficient, distributedclustering approach for ad hoc sensor networks. IEEE Trans. Mobile Comput. 3: 366-379.
30. Lin CH, Tsai MJ. 2006. A comment on HEED: A hybrid, energyefficient,distributed clustering approach for ad hoc sensor networks. IEEE Trans. Mobile Comput. 5: 1471-1472.
31. Pratyay K, Prasanta KJ. 2012. Improved Load Balanced Clustering Algorithm for Wireless Sensor Networks. Adcons. 7135: 399-404.
32. S Younis, S Fahmy. 2004. Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy-Efficient Approach. Proceedings of IEEE INFOCOM.
33. Pradeepa K, Duraisamy S. 2016. Energyefficient positioning of mobile base stations to improve wireless sensor network lifetime. International Journal of Sensor Networks. 20: 92-103.
34. Hu Q, Li Q, Wang X. 2008. An Optimal Algorithm for Minimizing Cluster Overlap of ACE. Wireless Algorithms, Systems, and Applications. WASA. 5258.
35. Yu Liyang, Wang Neng, Zhang Wei. 2006. GROUP: A Grid-Clustering Routing Protocol for Wireless Sensor Networks. 1-5.
36. Yanagihara K, Taketsugu J, Fukui K. 2007. EACLE: Energy-Aware Clustering Scheme with Transmission Power Control for Sensor Networks. Wireless Pers Commun. 40: 401- 415.
37.Sangho Yi, Junyoung Heo, Yookun Cho. 2007. PEACH: Power-efficient and adaptive clustering hierarchy protocol for wireless sensor networks. Computer Communications. 30: 14-15.

Download Provisional PDF Here