Abstract
Research on wireless sensor network (WSN) has increased tremendously throughout the years. In WSN, sensor nodes are deployed to operate autonomously in remote environments. Depending on the network orientation, WSN can be of two types: flat network and hierarchical or cluster-based network. Various advantages of cluster-based WSN are energy efficiency, better network communication, efficient topology management, minimized delay, and so forth. Consequently, clustering has become a key research area in WSN. Different approaches for WSN, using cluster concepts, have been proposed. The objective of this paper is to review and analyze the latest prominent cluster-based WSN algorithms using various measurement parameters. In this paper, unique performance metrics are designed which efficiently evaluate prominent clustering schemes. Moreover, we also develop taxonomy for the classification of the clustering schemes. Based on performance metrics, quantitative and qualitative analyses are performed to compare the advantages and disadvantages of the algorithms. Finally, we also put forward open research issues in the development of low cost, scalable, robust clustering schemes.
1. Introduction
Wireless sensor networks (WSNs) are highly resource constrained with limited power, bandwidth, processing capabilities, storage, and computational capabilities. Therefore, sensor nodes are mostly inoperable and irreplaceable when failure occurs due to energy depletion. Increasing network sustainability and lifetime are the key issues for the contemporary studies in sensor domain. Normally, energy depletion is highly dominated by radio transmission. The energy depletion of radio communication is directly related to any transmission in the network. Clustering technique reduces the number of radio transmissions and increases sensor network lifetime [1, 2]. Thus, clustering technique can, efficiently, increase lifetime of various sensor applications, such as robot control, environmental control, offices, smart homes, manufacturing environments, body area networks, and underwater sensor networks [3–8].
In traditional flat WSN, node's status and functionality are identical, and node acts as a data generator and router. Flat network is not efficient in energy conserving as compared to cluster-based WSN wherein network size is larger. Transmission happens in traditional flat network in the form of flooding [9]. In flooding, message is sent from the source node to destination where the entire network is used for a single operation. However, such technique causes data redundancy. To overcome the problem of data redundancy in flat network, directed diffusion technique has been suggested in [10, 11]. Direct Diffusion continuously monitors redundant data. However, this technique is not efficient where data input stream is large like environment monitoring. Another technique has been proposed to avoid redundancy in flat network is rumor. However, this technique also gives poor results when the number of events gets larger [12]. Flat sensor network scheme is mainly proactive which yields unsatisfactory performance for highly dense network [13–15]. Large sensor network generates more data that highly affects flat network performance. Communication overhead of flat network routing protocols is
To achieve the small sensor network features in a large sensor network, various solutions have been proposed to break a sensor network into smaller groups. Clustering is the one that demonstrates scalable results. The basic idea behind clustering is to group down the network into small networks. Clustering provides logical organization of small units and hence is easy to manage. The structured networks have many advantages as compared to flat network, such as data aggregation, reducing communication overhead, ease of managing, minimizing overall power consumption, energy efficiency, and prolonging sensor network life time. Moreover, clustering results in efficient dynamic routing from sensor to sensor or to specific nodes (sink nodes) [5, 16, 17].
Few challenges of WSN are as follows:
Overall network performance is affected by the limited power in sensor nodes. New deploy nodes execute cluster formation scheme while new redeployed nodes execute cluster maintenance. Such schemes are very critical for large network. In multihop networks, every node acts as a data originator and data router. Therefore, node(s) malfunction(s) causes topological manipulation which requires network reorganization and packet rerouting. Sensor nodes have low transmission bandwidth and low processing capabilities. Data transmission difficulties are unpredictable in WSN; thus, a proper fault tolerance or reliability schemes are essential. Data collection is performed by cluster head(s). This may result in redundant data which misuses sensor power. Hidden terminal problems may cause collision which results in energy wastage. Network performance degrades when the maximum extent of nodes in a network is undefined.
This paper addresses a few prominent issues in cluster performance metrics, which are absent in the recent review articles, such as domino effects, computational round, communication complexity, cluster maintenance, ID-based heuristic, degree-based heuristic, collaborative cover heuristic, and weight based heuristic clustering. Moreover, this work is the comprehensive review of every aspect regarding the cluster-based algorithms and schemes for WSN. Because of the significance of clustering in WSN and the accessibility of thorough works in this field, a holistic overview is vital at this stage. The objective of this paper is to critically review and analyze the prominent state of the art of cluster-based WSN algorithms. First, various cluster-based schemes are distributed into goal specific categories. Then, the advantages and disadvantages of the cluster-based schemes are highlighted. Moreover, comparative study of various approaches through qualitative and quantitative analysis is presented, which assists in developing the efficient cluster-based protocols. Finally, open research issues are discussed which can be the future line of directions.
The rest of the paper is presented as follows. Section 2 provides the existing review of articles on cluster-based WSN. Overview of cluster-based WSN is discussed in Section 3. Section 4 provides an overview of clustering schemes, where various cluster performance metrics are presented. Prominent cluster-based WSN protocols are discussed and analyzed (qualitatively and quantitatively) in Section 5. Section 6 discusses the open research areas in cluster-based WSN. Conclusions of this paper are drawn in Section 7.
2. Earlier Review of Articles in Cluster-Based WSNs
Cluster-based WSNs are a highly dynamic research area. The published articles in this domain are extremely diverse in terms of their approaches and implementations. However, there exist a few published survey papers, such as [18, 19], which provide a diverse comparison approach. Article [18] has become obsolete and does not show the latest dominant study in the area, while article [19] is the most recent review work among the survey articles that have been considered in this paper. A brief survey on cluster-based algorithms is presented in [19], where different taxonomy for measuring cluster-based architectures is presented with their advantages and disadvantages. However, article [19] explores the limited performance metrics. It overlooks some imperative performance metrics in exploring clustered protocols, such as communication cost. Moreover, quantitative analysis is not presented in [19].
Article [20] presents an extensive review on clustering protocols for WSN. This article mentions taxonomy of cluster structures and then shortens several cluster procedures on convergence time based protocols. It compares these clustering methods based on cluster overlapping, location awareness, cluster stability, and convergence rate.
A review paper presented in [21] discusses clustering protocols in WSN, which are categorized based on cluster formation and cluster-head (CH) selection. The authors discuss various significant design issues, and present various performance problems linked with the clustering algorithms. Another study, conducted in [22] on CH election policies, presents various types of taxonomy, such as deterministic, adaptive and joint metric schemes. The CH election cost is compared with cluster development and CHs distribution. Moreover, necessity of scalable, energy efficient and stable clustering schemes is placed forward for WSN.
Here, in [23], the authors state the overall cluster formation techniques in WSN. They review a simple organization of the only three considerations during cluster formation, namely, centralized or distributed CH formation, single-hop or multihop intra- and interclusters communication. They also highlight some issues in WSN and introduce few routing methods.
Review paper in [24] discusses three noticeable benefits of clustering approaches, such as high scalability, less outflows, and easy preservation. The authors present an organization of WSN cluster structures and eight cluster characteristics. They have studied some energy efficient cluster-based WSN protocols, namely, HCC, LEACH, PEGASIS, HEED, TEEN, APTEEN, ACE, EECS, EEUC, PEACH, FLOC, LID, DCA, 3HBA, and CDS. In [24], each algorithm is measured based on clustering head election characteristic and clustering characteristics. A survey on cluster-based WSN protocols discusses the important issues of five famous cluster-based WSN algorithms, namely, TL-LEACH, EECS, EEUC, HEED, and LEACH in [25]. The authors compare all these cluster-based protocols based on various metrics, such as uniformity of CH distribution, residual energy, distance of hop, cluster size, and delay and cluster formation techniques. Another study is conducted in [26] which compares various cluster-based algorithms. They present some basic ideas associated with the clustering procedure. They examine LEACH-based protocols with active and reactive protocols in WSN and compare the major performance metrics of these algorithms.
Design issues and comparative study of cluster-based WSN algorithms to improve the network lifetime are studied in [27]. Authors in [20] highlight various challenging elements that affect the design of clustering protocols. Moreover, several effective classical cluster-based schemes in WSNs with comparative study are conversed in the article.
It is observed that some measurements are missing in the abovementioned recent survey articles, namely, domino effects, computation round, communication complexity, cluster maintenance, and cluster-head election which are based on ID-based heuristic, degree-based heuristic, collaborative cover heuristic, or weight based heuristic. Without considering these measurement parameters, exploring and comparing WSN clustering schemes may not provide efficient outcomes. These performance metrics also have significant impact on sensor's energy depletion. Thus, this paper compares various cluster-based algorithms, and in each category quantitative and qualitative analyses are done to determine the efficiency of the cluster-based algorithms. In order to attain holistic knowledge of this domain and development of the algorithms, issues presented in this paper are vital in the development of cluster-based WSNs algorithm.
3. Overview of Cluster-Based WSN
3.1. What Is Cluster-Based Network?
The performance of the flat network may degrade once the size of the network increases. This is because of the fact that increasing the network size and control overhead in wireless sensor network also leads to the relevant increases. Clustering is one of the widely investigated solutions to scale down the large flat sensor network and to make the network operations more efficient. In clustering, the network is organized into logical groups which depend on network characteristics and applications' requirements. Cluster-based WSN has various advantages as compared to flat WSN, such as energy efficiency and prolonging network lifetime [17]. Cluster-based WSNs are defined as a hierarchal organization of sensor network. Numerous researches emphasize the operative and proficient clustering structures for WSN. Typically, in a cluster-based architecture, network is divided into virtual groups as shown in Figure 1.
Cluster-based network.
Figure 1 describes cluster-based network where the network is logically divided into clusters represented by dotted lines. There may exist three types of nodes in the network, namely, cluster head (CH), gateway (GW), and member node (MN). In a cluster, cluster-head is the local coordinator that aggregates and forwards data to base station. Meanwhile, member nodes (MNs) are the leaf nodes that send data to cluster-head. Nodes, which lay between two clusters, are known as gateway nodes, where the gateways connect two or more cluster heads. The advantage of the gateway node is to form a predefined multihop intercluster communication route, known as backbone of the network. Each CH retains neighboring GWs' information in its routing table where the routing table helps the CHs to make routing decision promptly. Backbone makes the data communication more efficient. The various features of cluster-based WSN are summarized as follows.
3.1.1. Features of Cluster-Based WSN
Data Fusion. During data fusion, CHs gather data from different nodes and send them to the base station (BS). Data fusion also eliminates redundant data on CH level, which eliminates extra burden on sensor nodes during communication. Hence, data fusion enhances the overall network lifetime [28] and reserves the entire network energy [29].
Data Load Management. Cluster provides efficient data load management and uniform network lifetime. CHs, closer to the BS, experience extra data loads in order to relay data from upper layers. To overcome this problem, CHs, which are closer to the BS, keep lesser member nodes to diminish load. Thus, the entire nodes have equal energy depletion, and network lifetime becomes uniform [30].
Efficient Energy Saving. In flat networks, data is transmitted through flooding, whereas in cluster-based network data is aggregated on CH level and sends it to the BS via multihop routing. Multihop routing in cluster-based network helps in decreasing the number of transmission paths, which saves energy exponentially [31].
Relay Node. Network is partitioned or disconnected when nodes fail to communicate. The relay node is used to reestablish the path and join the partitions. Relay node can be static or mobile. However, initial task of a static node is to find out the disjoint portion and then to deploy relay node there. However, mobile relay node is a special type of node which places itself in disjoint portion [32].
Robustness. Once the cluster-based WSN is formed, the second important step is cluster maintenance. Cluster maintenance is useful to maintain the network integrity. It handles different scenarios, such as changing network size, movements in nodes, and unexpected operational flaw. Clustering algorithms merely require managing these variations within each cluster. Therefore, cluster maintenance makes the network highly robust and more convenient in topological manipulations.
Collision Avoidance. In sensor network, when single channel is considered it is shared among sensor nodes. Thus, the performance of the network decreases when many nodes send data concurrently which causes collision. This can be efficiently solved in cluster-based WSN, where CH assigns unique time slot to every member node via scheduling [33].
Latency Reduction. Latency refers to the total time that a message requires to travel from source to destination node. Cluster-based WSN enhances the delivery performance of the packet by maintaining routing table at the CH level to make efficient routing decision. Moreover, cluster-based networks grounded on connected dominating set (CDS) form a predefined communication pathway called backbone tree, which enables quick and efficient multihop routing [30].
Secure Data Communication. As data aggregation is performed by CH, malicious nodes may attack to alter or hack data. In cluster-based WSN, strong authentication schemes are developed to avoid malicious nodes joining the network. These schemes improve data integrity and confidentiality [28].
Fault Tolerance. Sensor nodes may be affected by hardware failure, delay, interference, energy exhaustion, and so forth. Due to such constraints, where the nodes are not replaceable in harsh atmosphere, cluster-based protocols are suitable. Therefore, WSNs must have the ability to reconfigure themselves without human intervention, particularly in harsh environments and inaccessible locations. In order to secure aggregated data, fault tolerance technique needs to be considered during protocol design stage. Cluster maintenance and CH backup are more feasible techniques to secure the entire network reconstruction when CH is malfunctioning [34, 35].
Data Communication Assurance. CH sends the aggregated data to the base station through single-hop or multihop routing. In mobile network, the probability of data loss takes keen interest in recent researches because of its high chance of occurrence. To handle such problems in mobile node, the node sends a joint request to its CH before the actual data communication takes place. If the sender receives the acknowledgement message, then it initiates data transmission; otherwise the sender node considers that it is no more a part of the network and that it needs to rejoin the network. When the node is rejoined, the network then initiates data sending to parent node. Thus, connectivity assurance between member nodes and their CH is a crucial task for successful data delivery [36].
Deadlock Prevention. In multihop communication, data is transmitted to the base station using intermediate nodes. In this criterion, different nodes relay the data to the base station. Thus, the node closer to the sink node is overburdened with more information as compared to far nodes. Therefore, nodes, closer to the BS, deplete energy quicker, and deadlock occurs near the BS. This may cause the partition of the entire network into groups. Consequently, the far nodes may not be able to approach BS because of the limited range. Meanwhile, other nodes still have energy. To handle such problems, load balanced clusters were investigated, where a cluster, nearer to base station, retains smaller number of MNs than a cluster far from the base station. Therefore, nearer CH maintains enough energy for intercluster communication. Consequently, deadlock prevention can be efficiently handled by using unequal size cluster [37, 38].
Network Lifetime. Increasing of network lifetime is an important consideration as nodes retain limited power, bandwidth, and processing capabilities. Typically, it is a highly crucial task to optimize a few problems in WSNs, such as intracluster communication cost, redundant data gathering, and uniform cluster loads. Such factors are taken into consideration during CH election, which extends the lifetime of the network. Moreover, higher energy route is prioritized for data transmission, where such criterion adopts uniformed energy depletion in the network and enhances network lifetime [39, 40].
Efficient Quality of Services. The functionalities and network applications of WSN prompt the prerequisite of quality of service (QoS). Typically, effective QoS parameters are end-to-end delay, reliability, throughput, jitter, and bandwidth. It is difficult to satisfy all the necessities of QoS parameters in cluster-based protocols. Trade-off is required to consider one or more QoS parameters based on application requirements. The state-of-the-art cluster-based protocols emphasize the energy efficiency, rather than QoS. QoS issues are considered for real time application domain, such as healthcare application, battlefield applications, and event observing [41, 42].
4. Performance Metrics of Cluster-Based WSN
In this section, a set of performance metrics are enumerated which can be used to categorize and differentiate cluster-based WSN algorithms. One of the benefits of clustering is to make network scalable in situation when sensor nodes' number is huge. Nevertheless, there are downsides of using a cluster-based network, such as higher cost overhead during network construction as compared to flat sensor network. Cost of clustering is an important parameter to authenticate the effectiveness of the scheme. Moreover, it also refers to the improvement of network structure in terms of network scalability. Cost of the clustering schemes in this paper is evaluated qualitatively and quantitatively. The effectiveness of each algorithm as well as their shortcomings are determined. In this part, various performance metrics of cluster-based WSNs are discussed. Based on these parameters, the cost of clustering is evaluated more efficiently. Figure 2 describes various performance metrics of cluster-based WSN and each performance metric is discussed afterwards.
Performance metrics of cluster-based WSN.
Cluster Formation. Cluster formation is the setup phase of building cluster-based architecture from flat sensor network. Cluster formation is divided into two categories, namely, network model and cluster-head election.
Network Model. Network model represents the characteristics of a network. Two basic components of network model are described below.
Node Type. A node can be of two types, either mobile node or stationary node. In the former way, CHs, MNs, or GWs or all three can be mobile. Therefore, mobile node (CH or MN) changes its position dynamically in terms of other nodes. A challenging problem in such scenario is to retain cluster for long time and to overcome problems associated with packet loss. On the other hand, in stationary nodes, CHs, MNs, and GWs are the static nodes that do not change their positions in terms of other nodes [20]. Network Type. In WSN, cluster formation is either distributed or centralized. In centralized technique, a base station or CH needs universal information about the sensor network. In the distributed technique, a node becomes either CH or member node without the entire network information. Cluster-Head Election. CH election can be of different types: ID-based heuristic [43], degree-based heuristic [44], coverage based heuristic [45], and greater weight based heuristic. In ID-based heuristic, node ID is taken into consideration for CH election, like a smallest ID node becomes CH. In degree-based heuristic, quantity of neighbors is considered for CH election, while collaborative cover based heuristic considers average hop distance between two communicating nodes. It is indicated in [46] that the degree-based heuristic is better than ID-based heuristic in recognizing smaller size CDSs. However, collaborative cover heuristic [45] is better than degree-based heuristic in recognizing smaller size CDSs. Moreover, in weight based clustering, various parameters are considered to elect CH, such as remaining energy, communication cost, and distance. In weight based criterion, a node is elected as a CH based on energy cost.
Cluster Complexity. Cluster complexity defines the transmission complexity of the network. There are two types of cluster complexity, namely, computational complexity and communication complexity.
Computational Round/Time Complexity. Computational round specifies the total number of rounds in which cluster formation is accomplished. Computational round is a significant metric in cluster formation for static and mobile sensor network. It indicates an unbound time complexity in mobile sensor nodes. Hence, the more round results more data communication which decreases the efficiency of clustering algorithms [47]. Communication Complexity/Message Complexity. Message complexity is categorized into three types that are data aggregation, broadcasting, and multicasting. Converge-casting is an example of data aggregation that is performed at CH level and initiated from bottom to top manner towards the base station (BS). In broadcasting, messages are disseminated from top (base station) and go down in the entire network [48], while in multicasting, messages are disseminated from one node to set of nodes. Moreover, communication complexity is also dependent on the number of edges. Control Message. During network formation and maintenance, nodes exchange control information, which is unlike data message. Control message is directly proportional to energy depletion of a node. Moreover, the control information results in more energy depletion and vice versa. All the studied algorithms in this paper are evaluated via three scales: low, medium, and high [49, 50].
Cluster Communication. Cluster communication is a data sending mechanism from MNs to CH and from CH to base station. There are two types of data communication mechanism and those are intracluster and intercluster.
Intracluster Communication. In cluster-based WSN, intracluster communication is diversified into two approaches, such as single-hop intracluster communication manner and multiple-hop intracluster communication manner. In the case of single-hop intracluster, all MNs in the cluster send data to the corresponding CH straightly, while in multihop intracluster data moves through intermediate MNs in order to convey the message to the corresponding CH. Single-hop intracluster performs efficiently comparatively multihop intracluster communication in terms of energy conservation [51, 52]. Intercluster Communication. In cluster-based WSN, intercluster communication is also diversified into two classes which are single-hop intercluster communication manner and multiple-hop intercluster communication manner. In the case of intercluster single-hop, all CHs communicate with the BS directly. In contrast, data is relayed through intermediate nodes towards base station in intercluster multiple-hop. To increase scalability of sensor network, multihop intercluster communication performs efficiently as compared to single-hop intercluster routing [53].
Cluster Management. Cluster management deals with the topological manipulation in the cluster-based WSN. It is categorized into two types: cluster maintenance and domino effects.
Cluster Maintenance. Cluster-based network formation deals with the clusters formation, where cluster maintenance handles the topological changes when clusters are formed. Cluster topology manipulates new neighboring node discovery or the existing node leaving the cluster-based network. Thus, cluster maintenance deals with updating the cluster structure according to the change network topology. If clustering scheme is not scalable enough to facilitate cluster maintenance, then it results in domino effects. Thus, the whole network needs to be rebuilt from scratch [54, 55]. Domino Effects. There are some situations where cluster-based network is rebuilt from scratch due to damage or movement of sensor node. Such situation occurs when cluster has no maintenance mechanism. In other words, domino effect results in reclustering the entire network when the existing nodes want to leave or new nodes want to join the network while maintenance mechanism is absent in the network [56].
5. Taxonomy of Cluster-Based WSN Schemes
In this section, cluster-based algorithms are divided into seven groups as described in Table 1. Different clustering algorithms are studied under one of the seven scenarios. In each group, algorithms are compared qualitatively and quantitatively to identify different algorithms' characteristics. Qualitative and quantitative analysis is performed which is based on the performance metrics as discussed in the previous section. It is worth mentioning that generally a cluster algorithm retains more than one single objective which is also discussed in this section.
Brief overview of seven cluster schemes.
Connected Dominated Set Based Cluster. Considering wireless sensor network as graph G, a vertex (node) subset S of G is a dominating set (DS) if each vertex in G either belongs to S or is adjacent to at least one vertex in S. Connected dominating set (CDS) forms the backbone tree of the network. Each CH in the backbone has either direct connection with other CH or indirect connection with other CH through other nodes. Backbone tree is a predefined communication path to send data to base station. The advantage of the backbone is to speed up the routing decision from source node to destination node [57, 58].
Mobility Aware Cluster. Mobility aware cluster comprises mobile sensor nodes. Mobile sensor nodes move with respect to place and thus cause reclustering. To reduce reclustering issue, identical speed of nodes is grouped to form clusters. Thus, it results in prolonging cluster lifetime which also saves the energy during reclustering [35, 59].
Energy Efficient Cluster. Sensor nodes mostly have limited and irreplaceable supply of energy. The nodes lifetime can be saved using energy efficient clustering techniques [60].
Load Balancing. Load balancing puts limitation on nodes' density to specific area during cluster formation phase. Thus, such consideration forms sensor network in a way that the data load is distributed equally among all sensor nodes. Consequently, lifetime of the network is uniform [61, 62].
Dynamic Cluster. Cluster maintenance is a very important step to maintain all clusters of the network whenever any topological changes occur. Cluster maintenance makes the network dynamic when a new node joins or the existing node leaves the cluster. The dynamic feature of the network, efficiently, handles the topological manipulation of the network without affecting the whole network [2, 63].
Homogenous and Heterogeneous Cluster. In homogeneous network, all nodes/data are of the same type. Therefore, CHs are selected in a random way while in heterogeneous networks node(s)/data are of different types. Moreover, in body area networks, different types of nodes are used in order to gather different types of data which is also heterogeneous network.
Another type of heterogeneous network consists of nodes which are of different resources in terms of energy and processing power. Mostly, CHs are preassigned and have extra capabilities in the network [64, 65].
Based on the mentioned classifications, in each category, the pros and cons of each algorithm are compared qualitatively and quantitatively. The summary of each group is described in Table 1. Figure 3 shows different algorithms which are discussed in the next section.
Network Type. In WSN, cluster formation is either distributed or centralized. In centralized technique, a base station or CH needs universal information about the sensor network. In the distributed technique, a node becomes either CH or member node without the entire network information.
Cluster-Head Election. CH election can be of different types: ID-based heuristic [43], degree-based heuristic [44], coverage based heuristic [45], and greater weight based heuristic. In ID-based heuristic, node ID is taken into consideration for CH election, like a smallest ID node becomes CH. In degree-based heuristic, quantity of neighbors is considered for CH election, while collaborative cover based heuristic considers average hop distance between two communicating nodes. It is indicated in [46] that the degree-based heuristic is better than ID-based heuristic in recognizing smaller size CDSs. However, collaborative cover heuristic [45] is better than degree-based heuristic in recognizing smaller size CDSs. Moreover, in weight based clustering, various parameters are considered to elect CH, such as remaining energy, communication cost, and distance. In weight based criterion, a node is elected as a CH based on energy cost.
Illustrating different algorithms highlighted in specific group.
5.1. CDS-Based Cluster
DS-Based Cluster considers two types of nodes which are CH and MN. CH gathers data from MNs and forwards it to other nodes via routing table. Each CH acquires routing table and retains information of all its neighboring nodes. CHs are a dominating set which is a subset of the set consisting of all the nodes in the network [6]. Considering wireless sensor network in graph G, a vertex (node) subset S of G is a DS if each vertex in G either belongs to S or is adjacent to at least one vertex in S.
When the dominating nodes are directly connected or indirectly connected through intermediate nodes, then they form connected dominating set. The CDS forms virtual backbone in the network which provides efficient energy utilization of sensor nodes and efficient data communication in the network. Let an undirected graph represent
5.1.1. DACDS
New Distributed Algorithm connected dominating set is proposed in [44] to build DS. Initially, in [44] it uses the distributed leader election algorithm [66] to build a rooted spanning tree. Later on, every node finds its level as follows. Firstly, a root node announces its lowest level 0. Other nodes, upon receiving the level message from their parent node, increase the level by 1. Secondly, a labeling strategy is used to distribute the nodes in the tree to be either gray or black according to their level (the organize pair of id and level). The labeling mechanism starts from the root node and finishes at the leaf node. The marking process is complete when it reaches the leaf nodes. An MIS can be constructed in the following way.
Figure 4 shows the node which is in the lowest rank level 0. It becomes the root node and marks itself as a black node.
Illustrating DACDS protocol.
Black nodes become dominator nodes (i.e., CH) and send dominator message to their neighbors. The nodes which receive a dominator message for the first time mark themselves as gray nodes and declare themselves as dominatee nodes (i.e., MNs). Then, the dominatee node broadcasts a message to its neighboring nodes about its dominatee status. When a node receives the dominatee messages from all of its neighbors with lower ranks, it marks itself black and declares itself as a dominator by broadcasting a dominator message. In the last phase, black nodes form connected dominating set (CDS). Minimum connected dominating set (MCDS) of DACDS is
5.1.2. MCDS-CCH
Minimum connected dominating set (MCDS) using a collaborative cover heuristic (CCH) for WSN is proposed in [45]. The CCH is based on size optimization of MIS and CDS. Proposed algorithm in [45] optimizes independent nodes (i.e., CHs) based on the inspiration of coverage instead of ID- or degree-based heuristic. After electing independent nodes, the neighboring nodes are connected. The duplicated vertices are recursively removed via Steiner tree. The algorithm is self-organized when node physically moves. It has been concluded that the size of MCDS of CCH algorithm is intuitively efficient as compared to [67].
Figure 5 defines MCDS via celebrative cover heuristic. The nodes A, B, C, and D are an independent set of nodes and are connected with each other through a connector. The connection is formed, based on independent nodes coverage. The nodes which are within the coverage of the independent node become the member nodes of their independent node.
Describing MCDS using celebrative cover heuristic.
5.1.3. DBCDS
New node deployment based on connected dominating set (DBCDS) is proposed in [68] which forms connected dominating set (CDS), when nodes are deployed. The DBCDS provides better solution to nodes deployment problem in wireless sensor networks (WSNs). New nodes are randomly deployed in 3D monitoring space, where the disconnected nodes move towards the sink node until connection is achieved. The sink node broadcast the ready message in order to collect the information of all nodes to form the network. A node keeps moving towards the sink node until it receives the ready message to confirm that it is in the range of sink node. Once the ready message is received, the node replies to the sink by sending its location information. After gathering information of all nodes, the sink executes a centralized algorithm to determine the CDS among the nodes and adjust the right location of dominated nodes in the network. Consequently, the dominated nodes are moved and adjust their location accordingly, which is also in the communication range of dominating nodes. Thus, the high coverage network is also achieved. Advantages of the proposed algorithm are improved network coverage rate and efficient data routing, and a single node is used to collect information of the specific location in the network.
5.1.4. GBCHS
Grid based cluster-head selection (GBCHS) is presented in [69] to elect the CH among new deployed nodes while clusters are formed based on data transmission. The proposed algorithm works in centralized manner and needs global information of the network about location. Each node sends its location information to the sink node. After gathering information of the location, sink node finds the center point of each grid and sends this information to new deployed nodes. Once nodes receive the message from the sink node, they determine their distance from center point. A node whose distance is very close to the center point declares itself as a CH. This process is carried out in each grid. Advantages of such algorithms include less overhead to elect CH and energy efficiency as nodes distance is average.
5.1.5. Qualitative Analysis of CDS-Based Cluster
Table 2 describes all the three algorithms' features. A CDS improves data routing in WSNs in terms of smaller end-to-end delay, less energy usage, and so forth. An efficient CDS is to be smaller, more robust, and of low stretch (backbone routing should not be longer than the shortest path). A minimum connected dominating set (MCDS) has many advantages in terms of data traffic, less communication overheads, less energy consumption, efficient use of bandwidth, and increasing network lifetime. MCDS is an NP-hard problem in unit disk graph [70, 71]. DACDS is a degree-based heuristic to form CDSs, and MCDS-CCH is a collaborative coverage heuristic to form CDSs. In terms of minimum connected dominating set (MCDS), collaborative coverage heuristics MCDS-CCH is better than degree-based heuristics DACDS, whereas degree-based heuristics DACDS is better than ID-based heuristics CDS-ER [45]. Computation round of MCDS-CCH is higher than DACDS, whereas DACDS computational round is higher than CDS-ER. In terms of communication complexity, CDS-ER is higher than DACDS, whereas DACDS is higher than MCDS-CCH.
Quantitative analysis of connected dominating set based cluster.
Some of the disadvantages of DBCDS algorithm are as follows. Firstly, the algorithm is operated in a centralized manner which requires global optimization location information of the nodes to form CDS. Thus, the network may suffer from large number of messages when the number of nodes in the network is exceeding. Secondly, the network requires an efficient collision avoidance scheme in order to successfully send the messages. Thirdly, communication overheads highly affect network performance in terms of node energy and delay. Fourthly, nodes leaving happening in the network may cause rebuilding the network from scratch. However, in GBCHS the network lacks backbone formation which ultimately limits the network coverage.
5.2. Mobility Aware Cluster
Mobility aware clustering defines the mobility variations of sensor nodes. It describes topology manipulation and route annulment at the time when the sensor node moves. In mobility aware clustering, the key consideration for cluster formation is to group the nodes, based on identical motion. Thus, the links in inter- and intraclustering can get more intensely connected, which decreases the reclustering and packet loss issues.
5.2.1. LEACH-ME
Leach Mobile Enhancement Protocol (LEACH-ME) is a cluster-based protocol which is suitable for mobile nodes in WSNs [72]. The design objective is to choose a node with low mobility as a CH for longer cluster life. In order to quantify the low mobility factor, two parameters are considered, namely, remoteness and time. Remoteness is measured by data communication link changes rate. Thus, uniform speed clusters are developed where CH has the least speed in the group. The advantage of such cluster development is to maintain least maintenance in the network. Consequently, CHs are retained for longer time. Remoteness is measured, based on the mentioned equation.
Let
And 
5.2.2. MBC
Mobility based cluster (MBC) protocol is suggested in [73] which is suitable when nodes are mobile. MBC considers two efficient parameters for CH election which are remaining energy and the expected connection time. For longer network lifetime, CH election considers a node having more energy as compared to other nodes. Furthermore, to overcome the issues of data loss, the expected connection time between CH and MNs is considered. MBC algorithm considers two important phases for the network, namely, setup phase and steady state phase. In the network setup phase, nodes decide their status as either CH or MN based on the below formula:
The algorithm considers two phases, namely, steady state phase and setup phase, in order to reduce the number of lost messages. In steady state phase, member node (MN) checks its link status before sending data to CH. When an acknowledgement message is sent to MN from CH, it describes that MN is still a child of CH. Consequently, MN initiates data sending to its parent node (CH). Moreover, to maintain reliability of path between MN and CH, both nodes maintain cluster time information. When the time hits on the CH level, then a message is broadcast to cluster members.
As described in Figure 6, node number 7 withdraws its old cluster (cluster 1) and rejoins a new cluster (cluster 4). On the other hand, node number 10 withdraws its old cluster (cluster 4) and rejoins a new cluster (cluster 1). Therefore, cluster 1 and cluster 5 of new TDMA scheduling are adjusted on CHs level. In Figure 7, when node 7 leaves the network, then its time slot is also removed. Hence, the time slot of node 7 is unoccupied as node leaves the network. When cluster-head receives the joining message from node 10, then the unoccupied time slot is reserved for node 10. The time slotting is altered when a node joining and node leaving happens.
Illustrating MBC algorithm.
Illustrating TDMA of cluster 1.
In MBC, every MN is assigned a timeslot for data transmission. MN sends its data within its timeslot boundaries and broadcasts a new joint message to a new cluster at the time it drops the connection with the respective CH.
5.2.3. VGDRA
Virtual Grid Based Dynamic Routes Adjustment (VGDRA) scheme presented in [74] aims to maintain nearly optimal routes to the latest location of a mobile sink at the expense of least communication overheads. It partitions the sensor field into square number of equal sized cells where each cell is administered by a locally elected cell-header. To cope with dynamic network topology caused by sink's mobility, it defines a set of communication rules that govern the routes readjustment process. Following those communication rules, only a subset of the elected cell-headers takes part in routes readjustment process, thereby offering nearly optimal data delivery routes while incurring least communication overhead. To cope with speed variation of mobile sink and guaranteed data delivery, this work is, further, enhanced in [75] where appropriate forwarder nodes are selected along mobile sink's trajectory. The role of cell-header is progressively delegated to other nodes that help to achieve balanced energy consumption and improve network's lifetime. Advantages of these algorithms are minimum communication overheads and improved data delivery performance.
5.2.4. Qualitative Analysis of Mobility Aware Cluster
Table 3 describes all three algorithms features. The intracluster communication of all the three algorithms is considered as single-hop while intercluster communication is multihop. During cluster formation phase, nodes send a node joining request message. The nodes are considered as mobile nodes; hence, network topology changes rapidly. All the three algorithms also invoke reclustering of the network; since there are no cluster maintenance considerations.
Quantitative analysis of mobility aware cluster.
To address the mobility issues, LEACH-ME considers low mobility node to be CH. The LEACH-ME requires
In MBC, reclustering is lesser than CBR and Leach-M because of its core features. In case of vast mobile node environment, the MBC protocol decreases the packet loss by 25% comparatively to CBR [77] and 50% comparatively to LEACH-M [76]. However, it considers centralized cluster formation, and, therefore, nodes suffer from extra communication overheads.
5.3. Energy Efficient Cluster
One of the key challenges in WSNs is increasing lifetime of the network, because sensor nodes are mostly constrained by limited energy and irreplaceable power supply. Thus, energy of the sensor nodes needs to be used wisely. Energy efficient clustering is one of the techniques that can extend sensor network lifetime. Cluster-based WSNs consist of CH and MNs, where CH handles extra work as compared to the MNs, such as data aggregation (from MNs) and data routing (from lower level). Thus, CHs have excess of chances to “die” soon. Enhancing the network lifetime is a critical issue in wireless sensor network.
5.3.1. HEED
Hybrid Energy Efficient Distributed Clustering (HEED) is energy efficient clustering [78]. HEED considers two important parameters for CH election, and these are node's residual energy as a primary parameter and node's degree or intracluster communication cost as a secondary parameter. Comparing HEED with LEACH, HEED performs better in terms of enhancing network life time. LEACH elects CH randomly which makes few nodes die fast. In HEED, each MN is associated with a cluster. In HEED, the total clustering cost is minimized as the CHs are distributed properly across the network. Each node finds its own probability to become CH, based on the below mentioned equation:
HEED considers multihop inter- and intracluster communication. The algorithm considerations are as follows: firstly, a Distribute clustering scheme where CH election considers two significant parameters as mentioned earlier; secondly, the clustering process terminating within a specific cycle limit; thirdly, reducing control overhead; fourthly, the intercluster communication is multihop between CHs as described in Figure 8.
Describes HEED protocol.
5.3.2. DWEHC
Distributed Weight Based Energy Efficient Hierarchical Clustering (DWEHC) is introduced in [79] which is more efficient and goal-oriented as compared to HEED. DWEHC is a distributed multihop intraclustering topology as described in Figure 9. Every sensor node calculates its weight by the below equation and either declares itself as a CH or locates itself as a MN:
Illustrates DWEHC protocol.
DWEHC takes two parameters into consideration for CH election: preserved energy and the neighbor proximity. In neighboring node, the node that retains the highest weight becomes the CH. All first level members have direct communication with CH and the other nodes with lower energy access indirectly to the CH through other MNs. Each node finds the relay node to approach CH at lesser cost. Based on node's distance to its neighboring node, it decides to remain in the first level or move to the second level. This process is repeated until all nodes settle on energy efficient intraclustering. Every CH allocates a range in which all MNs must exist within that range. Thus, it limits the maximum number of levels up to a certain range.
5.3.3. PACDS
On calculating power-aware connected dominating sets are proposed in [80] to discuss efficient routing in cluster-based WSN. In the proposed scheme, connected dominating set is formed, based on the sensor node degree and the level of energy of every host. The aim is to offer CH election scheme so that overall energy depletion is well-adjusted in the network, and a relatively small connected dominating set is produced at the same time. DS nodes retain some remarkable batteries as compared to non-DS nodes because nodes of DS execute some extra tasks, like data gathering, routing information, and data routing. Thus, it is compulsory to reduce energy utilization of DS. One technique is to reduce DS density, and, thus, unnecessary mobile sensor nodes are removed from DS. This technique secures their energy depletion for operating as cluster-heads. In [43], certain extra procedures are recommended to remove needless dominating nodes.
In [80], some procedures, based on energy level, are also suggested to define whether a node can be in DS or not. The mobile sensor node is excluded from the dominating set when the node and its members are adjacent to other DS. The suggested scheme in [80] is more energy efficient as compared to other DS-based clustering procedures as it attempts to remove mobile nodes for DS that has lesser residual energy. A flat architecture is depicted in Figure 10(a). Figure 10(b) is a cluster-based architecture. Figure 10(b) shows the CHs, namely, A, B, C, and D, which retain less energy, and its MNs are also within the range of higher energy. Thus, the CHs along with their associated child nodes become as a member node of higher energy cluster-head, and its child nodes are also moved to other cluster-heads. Figure 10(c) describes the graph after excluding the less energy CHs.
Describes PACDS algorithms.
5.3.4. Qualitative Analysis of Energy Efficient Cluster
Table 4 describes all three algorithms' features. The three algorithms are weight based cluster-head election. Intracluster is single-hop, and intercluster is multihop, and which are considerations. HEED and DWEHC are considered stationary nodes while PACDS are considered mobile nodes. If a few nodes are faulty in HEED or DWEHS, this may cause severe problem. Such situation makes the network into a disjoint portion where one portion may become out of range from another portion. Therefore, stationary nodes may suffer more as compared to mobile node. Since no algorithm has cluster maintenance, therefore, network is restructured from scratch whenever a node dies in any of the algorithms. In HEED, tentative CHs leave some unconnected nodes, when permanent CH gets elected. In HEED algorithm, all nodes get neighbor information that requires
Quantitative analysis of energy efficient cluster.
5.4. Load Balancing Cluster
The basic idea of load balancing cluster is to achieve uniform lifetime of the network. Load balancing cluster algorithms handle optimum quantity of nodes in cluster. If the numbers of nodes is too large in a cluster, CH is overloaded as it performs multiple tasks. On the other hand, cluster formation with small number of nodes causes the high number of clusters. Therefore, the network increases the hierarchical length and larger end-to-end delay. Load balancing limits the number of nodes in a cluster. Whenever cluster size exceeds its predefined limit, load balancing procedure accommodates extra node in other clusters or forms a new cluster.
5.4.1. AMC
An adaptive multihop cluster-based scheme is proposed in [81] which is a load balancing clustering. Initial construction of cluster formation is not described in AMC. However, for cluster maintenance, every node broadcasts its information, including its ID, status, and CID (CH/member/gateway) to other nodes in the cluster. A CH can get information of each neighboring cluster node. Each cluster can handle up to certain limit of MNs via upper and lower bounds (U and L).
In AMC, cluster merging occurs when one MN
Figure 11 describes AMC protocol. There are three clusters in the network: cluster A, cluster B, and cluster C. Each cluster must maintain a specific number of member nodes to maintain proper load balancing. If the member nodes of the cluster are less than lower bound, then the cluster merges with the neighboring cluster. In Figure 11, cluster C considers that a mobile node j moves to cluster B. After moving to cluster B, the cluster size becomes lesser than lower bound. Hence, to merge cluster C with either cluster A or cluster B, CH of cluster C gets information about the neighboring cluster size. As the size of cluster A is lesser than the size of cluster B, therefore, cluster C merges with cluster A. In situation when the member nodes increase from upper bound, cluster splits into two clusters.
Describing AMC algorithm.
5.4.2. LBGC
Load Balancing Group Clustering (LBGC) is proposed in [82]. LBGC mainly focuses on multihop routing mechanism to reduce energy consumption. But this may cause problem of “hot-spots” in sensor networks. For example, the energy of the CH, which is near to the BS, depletes faster due to higher number of transaction as compared to those nodes which are far from the BS. To overcome this problem, they use unequal-grouping method to attain load balance among the entire CHs. The distance among the group head (GH) and BS serves as grouping condition to make the groups which are near to the BS and smaller than the far ones possible.
LBGC protocol, periodically, elects CHs, and it implements dynamic route calculation according to the state of energy allocating of sensor network. LBGC reelects the CH by considering its transmission costs and extra energy and rearranges cluster. Load of the nodes is distributed, based on their remaining energy among all the nodes. It proves better load balance and increases life for the sensor network. If each dominator in CDS is not equal, then the heavy dominator nodes decrease their energy very rapidly.
5.4.3. LBCD-GA
Load Balance Connected Dominating Set Genetic Algorithm (LBCDS-GA) is proposed in [83], which assures that each dominator (i.e., CH) is balanced in terms of work load in MCDS and allocates dominatee (i.e., MN) node to every dominator (i.e. CH). To overcome “hot-spots” problem, the author proposes Genetic Algorithm (GA). GA is mainly population based search algorithm. It considers the number of dominators in dominating set. GAs are heuristic search based algorithms on evolutionary thoughts of natural assortment and genetics [84]. Figure 12 illustrates the load LBCD-GA algorithm. Figure 12(a) illustrates a flat network. In Figure 12(b), there are two dominator nodes: dominator 4 and dominator 5. If each node sends the same amount of data at fixed rate, then dominator 4 exhausts energy quicker than dominator 7. Therefore, in Figure 12(c), the number of dominators is increased. Thus, in terms of load balancing, Figure 12(c) gives results better than Figure 12(b). However, still dominatee balance is not uniform. Thus, in Figure 12(d), dominatee, that is, node 4, connects with dominator, that is, node 6. Subsequently, in terms of enhancing network life time, Figure 12(d) provides results better than Figures 12(b) and 12(c).
Illustrating LBCD-GA algorithm.
5.4.4. Qualitative Analysis of Load Balancing Cluster
Table 5 summarizes three load balancing cluster-based schemes as discussed before. AMC adopts multihop communication in both intra- and intercluster communication. AMC has no domino effect of reclustering and retains good cluster stability whereas both the LBGC and LBCD-GA have no maintenance mechanism and result in domino effects. Making a MCDS for a WSN is an NP-hard problem even in the unit disk graph [83] model. Many research works have been devoted to achieving a better performance ratio. For CDS, algorithms are categorized into two stages: one-stage and two-stage algorithms. The objective of one-stage algorithms [85] is to build a CDS directly, while two-stage algorithms build a CDS in two phases. First phase builds minimum DS, while second phase uses Steiner Tree method to build a CDS [86]. In [85], the author proposes two centralized greedy algorithms. The first algorithm is a one-stage strategy with an approximation ratio of
Quantitative analysis of load balancing cluster.
5.5. Dynamic Cluster
The sensor network has sufficient scalability to permit new nodes to join, or the existing nodes to leave the network without interrupting network data flow. However, it has been explored that flat sensor network is not scalable as cluster-based WSN [13, 14, 87]. In cluster-based network, cluster formation and cluster maintenance methods are used to maintain the structure of the network. Cluster formation deals with building of cluster structure. Cluster maintenance deals with updating the cluster network when a new node wants to join and the existing node leaves the network. Dynamic clustering ensures network robustness wherein new node joining and fault tolerance techniques are addressed in the network environment. The objective of the new nodes deployment in the network can be divided into two types, such as relay node and new nodes. Relay node joins the disjoint paths of the network and new nodes increase the coverage area of the network. The cluster becomes unstable whenever cluster maintenance is absent in the algorithm [2]. Thus, it results in loss of routing information at the time when changes occur in the network. Therefore, overall network performance degrades. To overcome this problem, it is suggested to build efficient cluster maintenance scheme. Consequently, it avoids loss of routing information and improves overall performance of routing protocol [88].
5.5.1. CNet(G)
Construction and Maintenance of Novel Cluster-based Wireless Sensor Network (CNet(G)) is proposed in [89, 90] as described in Figure 13. There are three types of nodes in CNet(G), namely, MN, CH, and GW. MNs are single-hop intraconnected with CH. CHs are connected through gateway (GW). Thus, CHs and GWs form a predefined routing path which is called backbone. Network maintenance is performed through two operations, namely, node-move-in and node-move-out. Node-move-in describes a single node joining while node-move-out describes a single node leaving the CNet(G). When a new node needs to join the network, then it is deployed to the network field. The node is joined and gets its status, based on in-range node status. The node that is within the range of the new node is described by the neighbor node.
Describing CNet(G) topology.
The new node searches the neighbor nodes based on priority in order to join as described in Figure 14. Firstly, new node searches a CH in neighbor, if CH does not exist then new searches a GW node. When the CH and GW do not exist in neighbor, then new searches a MN. Otherwise, when neighboring node of new node is gateway node, then new node joins the network as CH. If the neighboring node is member node, then neighbor node changes its own status from member node to gateway node and new joins as CH.
Describing new node joining in CNet(G).
As described earlier, node-move-out is a single node leaving algorithm and sends “leaving message” to child nodes in order to leave the network. When the child nodes receive the message, then they withdraw the network and rejoin from the scratch as described in Figure 15. In Figure 15, the decedent nodes of the leaving node withdraw the network and rejoin via calling node-move-in algorithm.
Describing the leaving node procedure.
The merits of structured network provide key features such as minimizing communication overheads, choosing data aggregation points, increasing the probability of aggregating redundant data, and minimizing the overall power consumption [91].
5.5.2. CBNet(G)
Novel Cluster-Based Architecture and a Routing Protocol for Dynamic Ad Hoc Radio Networks CBNet(G) are proposed in [92] which is mainly designed to support a timely and energy efficient, loop-free, on demand routing protocol. CBNet(G) considers multihop intra- and intercluster communication as described in Figure 16. Two maintenance algorithms are also developed for CBNet(G), namely, node-move-in and node-move-out. Node-move-in is a single new node joining algorithm while node-move-out is a single existing node leaving algorithm. Both algorithms are described below.
Describing network topology of CBNet(G).
When a new node is deployed in the network, then the node calls node-move-in to join the network. New node determines its status according to the in-range node of the network. When there is a CH(s) in the range of the new node, then the node joins as an ordinary node. Whereas when the new node finds any cluster forwarding node in its neighbor, then the new node becomes as an ordinary node and chooses one of the cluster forwarding nodes as its parent node, which is having the least distance to its CH. When there is a forwarding node within the range of the new node, the new node becomes ordinary node and also elects a forwarding node which is having the least distance to its CH as its parent. Else, if the new node has an ordinary node in its range, which is also closer to CH
5.5.3. NNDBC
Node nonuniform deployment based on clustering (NNDBC) algorithm for UWSNs is introduced in [93] which addresses nodes joining and nodes leaving procedures. The coverage targets of NNDBC algorithm are the isolated events whose distribution is usually nonuniform in the mentioned space. NNDBC aims to optimize network connectivity rate and improve network lifetime for nonuniform deployed networks. The clustering formation is based upon communication range which is used to determine the network connectivity. The nodes in the cluster consist of in-cluster nodes and cluster-head node. The in-cluster nodes are connected to their own cluster-head node, whereas the cluster-head nodes are connected to the closest node (say gateway node) of the other cluster.
After the network formation, steady state phase is executed. In this phase, when a node i energy is lesser than the threshold energy then the node is substituted by another node. Thus, node cluster head
5.5.4. Qualitative Analysis Cluster Maintenance
Table 6 summarizes the features and objectives of three maintenance schemes. CNet(G) is a single-hop intracluster while CBNet(G) is multihop intracluster communication. In Table 6, q represents neighboring nodes of the new joining node; p represents the number of CH in CNet(G); k is the maximum radius of cluster; r is the number of intracluster nodes, and l is the size of intercluster. CNet(G) is a single node joining and single node leaving algorithm. When a single node is deployed to join the network, it gets the neighbor nodes' information. The computational round of CNet(G) is
Quantitative analysis of cluster maintenance.
CBNet(G) consists of five types of nodes: CH nodes, forwarding nodes, cluster forwarding nodes, gateway nodes, and ordinary nodes. Similarly, CBNet(G) addresses single node joining and single node leaving the network. The new node waits to listen from all the nodes before joining and then chooses a suitable node to establish the join connection. The time complexity and message complexity of CBNet(G) are higher than CNet(G) as described in Table 6.
The disadvantages of the NNDBC algorithm are as follows: high communication overheads occur in the network as the algorithm requires running on centralized manner [19]. Secondly, the algorithm has lack of minimizing number of messages to form the network. Thirdly, the descendant nodes of leaving node need to rejoin the network from scratch which degrades network performance.
5.6. Homogeneous and Heterogeneous Cluster
In homogeneous network, all nodes/data are of the same type; thus, CHs are selected in random way, while in heterogeneous networks node(s)/data are of different types. In case of WBANs, different types of nodes are required to monitor different health parameters of the human beings. Thus, WBANs is a type of heterogeneous network [4].
5.6.1. TL-LEACH
TL-LEACH is introduced in [94] which maintains two-level hierarchy of CH: primary CH (CHi) and secondary CH (CHij) as presented in Figure 17. MNs send the data to secondary CH; secondary CH sends the aggregated data to primary CH, and finally primary CH sends the aggregated data to the base station. In TL-LEACH, energy is equally assigned to all the nodes. The algorithm consists of four basic phases: in the first phase, nodes send request to form the network and it is called “advertisement phase.” Second phase is cluster setup phase; third phase is schedule creation, and the last phase is data transmission. During the second phase, each node is primary CH or secondary CH or ordinary node. If a node becomes primary CH, then it informs the neighboring nodes about its status. Thereafter, the secondary CH decides which primary CH it belongs to, and it informs its primary CH by sending a message. In the same way, each MN decides which secondary CH the node belongs to, and it informs its secondary CH by sending a message.
Describing TL-LEACH topology.
To avoid collision, Carrier Sense Multiple Access (CSMA) is used. In the third phase, each primary CH forms a TDMA schedule and assigns it to secondary CH in its group. In the same way, every secondary CH creates scheduling and assigns it to their MNs. In the last phase, data transmission happens with respect to TDMA scheduling. Figure 17 describes the network in three levels. In the first level, CHs are in direct communication with the base station. In the second level, secondary CHs send the aggregated date to primary CHs. In the third level, MNs gather the data from the environments and send them to secondary CHs.
5.6.2. UCS
Unequal Cluster Size (UCS) is suggested in [95] to balance energy of the network and to increase lifetime of the network. UCS is heterogeneous cluster model for WSN. It is considered that the base station is laying in the middle of the network. All CHs are preordered positions and arranged in circle around the base station. In UCS, it is considered as a sensing field in circle. Each circle is, further, divided into layers. As shown in Figure 18, it is considered that the shape and size of the entire cluster within layer are identical.
Describing UCS network.
However, the shape and size of clusters in two layers are different. The CH, which is near the base station, consumes more energy due to high burden of relaying packets coming from upper CH. Therefore, the CH nodes, which are near to BS, keep lesser number of MNs as compared to CHs far away from the base station which makes uniform lifetime of the time.
The energy usage of a CH depends on inter- and intracluster communication. However, the energy usage on intercluster data communication is a property of expecting load from other CHs. A CH near the base station suffers from more energy depletion due to relaying other CH data. It is concluded that cluster size optimization based on distance with the BS maximizes the life time of the network. For example, in Figure 18, there are two layers of CH: inner CH and outer CH. The shape and size of the entire cluster within layer are identical. However, the two layers of cluster are different which make uniform lifetime of the network.
5.6.3. Critical Data Routing in WBSNs (CDR)
The algorithm in [96] describes dominating set based new nodes joining. The data communication is divided into three tiers: Intra, Inter, and Extra [4]. In the first tier, that is, intra, a new joining node forwards the sensed data to the local coordinator which acts as a cluster head [4]. The three main issues with intra are as follows: firstly, heterogeneous nature of the sense data which requires different quality of service parameters. Secondly, temperature rise of the implanted sensor nodes which may be harmful for human tissue. Thirdly, high and dynamic path loss due to the postural movements [96–98].
In [97], the authors have classified the sensed data by new node into reliability sensitive data and normal data, while in [98] the data is being classified into critical data and normal data. However, in [96] the data is categorized into three classes, that is, reliability sensitive data, delay sensitive data, and normal data. The aforementioned three schemes are modular based where different modules are used to perform the various tasks. The routing decisions are based on the nature of data, temperature rise, and path loss. All these schemes performs better as compared to other state-of-the-art schemes due to multiobjective selection criteria. However, in node joining, messages are transmitted among new node and existing node. These messages use node's energy in data transmission. The algorithm has lack of a mechanism to minimize the messages.
5.6.4. Qualitative Analysis of Homogenous and Heterogeneous Cluster
In a homogeneous network, CH is highly-loaded by member nodes and other CH(s) in sending information towards the remote base station. If a CH has n child node(s) then it might have
TL-LEACH is a homogeneous cluster-based scheme which forms primary and secondary CH. It rotates the roles of both primary and secondary CH to maintain efficient load distribution.
On the other hand, UCS is a heterogeneous cluster-based scheme. CHs are designated super nodes where the overall network lifetime is determined by the life time of CH nodes [95]. CHs have enough energy to meet
In UCS, CH nodes are super nodes which are deployed in preassigned location that reduces universality. Moreover, two-hop intercluster transmission decreases the network communication range. Furthermore, CH node serves as the fusion point as well as the command center of its cluster. As a result, when a CH node fails, all the sensor nodes in that cluster have to be reassigned to other neighboring clusters (Table 7).
Quantitative analysis of homogeneous and heterogeneous network.
6. Open Research Areas in Cluster-Based WSNs
Recent proposed cluster-based schemes have a lot of critical concerns for the concrete deployment of wireless sensor network. Nevertheless, it is observed that some issues are still pertaining in the latest research. The issues, open for research in cluster-based WSNs, are as follows.
Cluster Formation
An efficient minimum connected dominating set (MCDS) exhibits less routing complexity due to its shortest path. Collaborative cover heuristic CCH provides efficient results in terms of MCDS. More work needs to be done to improve CCH to reduce routing complexity. Nodes mobility may also introduce cluster reclustering and reconfigurability. Auxiliary cluster head might be elected from the cluster members, which can act as a cluster head. This technique may make the cluster more stable. During cluster formation, control messages transmit between nodes which consume the node's energy. Control messages might be decreased when the complexity of the cluster formation depends upon the neighbor nodes instead of entire network.
Cluster Maintenance
Network maintenance is an inseparable part for sensor network architecture. At the network reconfiguration phases, nodes need to discover the neighboring nodes, where the neighbor discovery process requires synchronization among the nodes. Therefore, an efficient synchronization scheme is a challenging issue to discover the neighbor nodes. The state-of-the-art of cluster-based WSNs focuse on single node deployment, where multinodes deployment is still missing in dynamic clustering. If the channel is to be considered as single, then data and beacon collisions may happen that interrupt multi node joining. Randomize algorithms might be one of the solutions to overcome collision and to successfully join multi nodes. The state of the art of cluster-based WSNs addresses only single node leaving the network. However, multiple nodes may leave the network. Leaving nodes might be parent nodes, and leaf nodes depend on the minimum energy level of sensor meets. If leaving nodes are parent node, then centralizing algorithm, using DFS algorithm, might be one of the solutions to handle multiple nodes leaving. If leaving nodes are the leaf nodes, then multiple node leaving might be possible without informing centralize node. New nodes need to discover all their neighbor nodes to join the network. However, gathering the entire neighbors' information requires high number of computation rounds. The number of computation rounds might be reduced when new nodes gather information about a specific node in their neighborhood to join the network. Therefore, algorithms need to be developed to optimize computation rounds during neighbor nodes discovery. The key challenges in mobile aware nodes are to select the accurate CH to retain network for long time. Dynamic strategies need to be developed to exchange reliable information among the neighboring CH election.
Others
With the increasing sensor nodes, the probability of the redundant information also increases. Up to some extent, redundant information is worthy for data reliability. However, redundant data wastes sensor energy. Thus, a trade-off is required between redundancy minimization and data reliability. More research is recommended to address QoS issues in cluster-based WSNs. This is mainly considered in all real time applications domain. Emergency monitoring in medical care is a real time application where data is required without any delay due to path loss or any other factors.
7. Conclusions
For the best use of cluster-based WSN, a robust cluster-based WSN algorithm is an absolute requirement. In this paper, a complete study on the latest cluster-based WSN with their qualities and impediments is presented. Acknowledging the restrictions of non-cluster-based architecture, cluster-based architecture is a better answer for WSN. Cluster divides the large distributed networks into groups to reduce overhead. Thus, it makes it possible to retain the features of small network in dense network.
Intra- and intercluster routing, control message, domino effects, computation round, communication complexity, node type, basic control, cluster maintenance, cluster-head election, ID-based heuristic, Degree-based heuristic and collaborative cover heuristic, and weight based heuristic are the primary performance metrics that have been recognized to assess the cluster-based WSN.
Communication cost is directly proportional to sensor energy. Therefore, more communication cost results in more energy depletion. An efficient maintenance mechanism overcomes the problem of reclustering. Single-hop intercluster communication gives good results as compared to multihop intercluster communication in terms of energy depletion, while multihop intercluster communication provides good results as compared to single-hop intercluster communication in terms of network scalability. Control overhead is also an important parameter that highly affects energy, where high control overheads result in more energy depletion.
We, thoroughly, discussed various goal specific algorithms to identify the impact of clustering and dynamic challenges. This paper helps to examine the vital challenges during algorithm development, like cluster stability and data loss issues, cluster-head election where energy consumption is the consideration, uniform load balancing, efficient network maintenance, and role of heterogeneous network to increase network lifetime. Each goal specific cluster scheme has its own scenario and objective. In the general consideration, for any goal specific scenario, it is important to consider control overhead and network maintenance. With this survey, readers can design efficient goal specific algorithms, bearing in mind other important considerations too. We have, similarly, highlighted the open issues for future research in cluster-based WSN.
Footnotes
Competing Interests
The authors declare no conflict of interests.
Acknowledgments
This work is partially supported by grants GUP Tier 1, 2014-2015, with Vote no. 05H61, GUP Tier 1 with Vote no. 11H39, 2015–2017, and Malaysia-Japan and International Institute of Technology and (MJIIT) of Universiti Teknologi Malaysia (UTM) Research Grant with Vote no. 4J044, Ministry of Higher Education (MoHE), 2012–2017.