Clustering Analysis in Wireless Sensor Networks: The Ambit of Performance Metrics and Schemes Taxonomy

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 $O (n^{2})$ , where n represents the total number of nodes in the network [3]. This result implies that such algorithm increases routing overheads. Therefore, flat network performs efficiently in a situation where network size is small.

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: (i)

Overall network performance is affected by the limited power in sensor nodes.

(ii)

New deploy nodes execute cluster formation scheme while new redeployed nodes execute cluster maintenance. Such schemes are very critical for large network.

(iii)

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.

(iv)

Sensor nodes have low transmission bandwidth and low processing capabilities.

(v)

Data transmission difficulties are unpredictable in WSN; thus, a proper fault tolerance or reliability schemes are essential.

(vi)

Data collection is performed by cluster head(s). This may result in redundant data which misuses sensor power.

(vii)

Hidden terminal problems may cause collision which results in energy wastage.

(viii)

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.

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.

Figure 2

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. (i)

Network Model. Network model represents the characteristics of a network. Two basic components of network model are described below.

(a)

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

(b)

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.

(ii)

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. (i)

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

(ii)

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.

(iii)

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. (i)

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

(ii)

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. (i)

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

(ii)

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.

Table 1

Brief overview of seven cluster schemes.

Number	Cluster schemes	Objective
5.1	CDS-based cluster	All dominating nodes are joined together and form a subgraph to enhance communication routing and energy efficiency.
5.2	Mobility aware cluster	Mobile nodes of cluster are constructed and maintained with relative speed to tighten nodes within same cluster.
5.3	Energy efficient cluster	Sensor nodes are irreplaceable and of limited energy. Suitable cluster leads to extending life of network.
5.4	Load balancing cluster	Spreading the workload of the network equally. In such scenario, CHs apply restriction on child nodes in order to accept a certain limit of child nodes.
5.5	Dynamic cluster	When a new node is joining and existing node is leaving in existing network, dynamic cluster handles such situation.
5.6	Homogenous and heterogeneous cluster	In homogenous network, node/data is of same type, while in heterogeneous network node/data is of different type.

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.

Figure 3

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 $G = (V, E)$ , where V is a set of nodes and E is a set of links between nodes. $V^{'}$ is a subset of Vand $V^{'}$ forms CDS of graph G, if each vertex u is a member of V, such that $(u, v)$ is a member of E and subgraph is induced by $V^{'}$ . An efficient CDS should be more robust and of smaller size.

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.

Figure 4

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 $8 o p t + 1$ , where opt represents size of black nodes.

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.

Figure 5

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.

Table 2

Quantitative analysis of connected dominating set based cluster.

	5.1.1	5.1.2	5.1.3	5.1.4
Cluster detail	DACDS	MCDS-CCH	DBCDS	GBCHS
CH election	Degree based	Collaborative Cover based	Degree based	Degree based
Intracluster routing	Single-hop	Single-hop	Single-hop	Single-hop
Intercluster routing	Multihop	Multihop	Multihop	Single-hop
Control message	High	High	High	Medium
Domino effect	Yes	Yes	Yes	Yes
Computation round	$O (n)$	$O (n)$	$O (P_{t} * n)$ and $O (P_{t} * (n - 1))$	$O (n \log n)$
Communication complexity	$O (n \log n)$	$O (n)$	$O (\log n)$	$O (q)$
Stationary or mobile	Static	Static	Mobile	Mobile
Maintenance	No	No	No	No
Basic control	Distributed	Distributed	Centralized	Centralized

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 $n_{i} (t), i = 0,1, 2,3, \dots, N - 1$ , where N describes nodes density, be the location vector of sensor node i at time t.

And $d_{i j} (t) = | n_{j} (t) - n_{i} (t) |$ is the distance between sensor node i and node j at time t. So, the remoteness from sensor node i to sensor node j at time t is $R_{i j} (t) = F (d_{i j} (t))$ , where F describes remoteness function. Distance from node i to node j is described by remoteness. Thus, nodes remoteness regarding time is measured as

\begin{matrix} M (t) = \frac{1}{N - 1} \sum_{j = 0}^{N - 1} |d_{i j} (t)|, \end{matrix}

(1)

where

d_{i j}

describes the total distance from ith node to jth node and N describes the total number of nodes in the network. The data transmission starts at active time slot

t_{1}

and receives at time slot

t_{2}

. The distance

d_{i j} (t) = R a d i o v e l o c i t y * | t_{2} - t_{1} |

. When a message is received, it is easy to determine the mobility factor of N nodes.

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:

\begin{matrix} T {(n)}_{n e w} = \frac{p}{1 - p \times [r \mod (1 / p)]} (\frac{E_{n_c u r r e n t}}{E_{m a x}} \frac{v_{m a x} - v_{n_c u r r e n t}}{v_{m a x}}), \forall n \in G, \end{matrix}

(2)

where p is the expected percentage of CHs (e.g.,

p = 0.05

), r describes current trip,

E_{n_c u r r e n t}

describes current energy,

v_{n_c u r r e n t}

describes current speed,

E_{m a x}

describes initial energy, and

v_{m a x}

describes maximum speed of the node. When CH is selected, it informs the neighboring nodes via sending a message. After receiving the message, the neighbor nodes send join appeal to the CH. When the join appeal is received, CH makes reservation of a timeslot for the newly MN.

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.

Figure 6

Illustrating MBC algorithm.

Figure 7

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.

Table 3

Quantitative analysis of mobility aware cluster.

	5.2.1	5.2.2	5.2.3
Cluster detail	Leach ME	MBC	VGDRA
CH election	Weight based	Weight based	Weight based
Intracluster routing	Single-hop	Single-hop	Single-hop
Intercluster routing	Multihop	Multihop	Multihop
Control message	Medium	Medium	High
Domino effect	Yes	Yes	Yes
Computation round	$O (n^{2})$	$O (n \log n)$	$O (n)$
Communication complexity	$O (\|q\|)$	$O (\log n)$	$O (\log n)$
Stationary or mobile	Mobile	Mobile	Mobile
Maintenance	No	No	No
Basic control	Distributed	Centralized	Distributed

To address the mobility issues, LEACH-ME considers low mobility node to be CH. The LEACH-ME requires $O (n^{2})$ rounds for cluster formation and reconfiguration and thus provides stable clustering as compared to LEACH-M [76]. Each mobile node sends $O (| q |)$ messages to its neighbor to determine the relative speed, where q represents one-hop direct neighbor. Each mobile node aggregates node mobility information, and a node having less mobility declares itself as a cluster head.

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:

\begin{matrix} {C H}_{p r o b} = C_{p r o b} \frac{E_{r e s i d u a l}}{E_{m a x}} . \end{matrix}

(3)

C_{p r o b}

describes the number of network nodes to become CHs (e.g., 5%),

E_{r e s i d u a l}

describes the present node energy, and

E_{m a x}

describes maximum energy.

{C H}_{p r o b}

is not allowed to be lesser than a certain limit of the threshold. Therefore, every node executes certain iteration until it finds the CH. A node would be a tentative CH, if its probability is less than 1. A node becomes MN when it finds other less cost CH. On the other hand, a node acts as a permanent CH when its probability reaches 1.

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.

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:

\begin{matrix} W_{w e i g h t} (s) = [\sum_{u \in N_{α, c} (s)} \frac{(R - d)}{6 R}] \times \frac{E_{r e s i d u a l} (s)}{E_{i n i t i a l} (s)}, \end{matrix}

(4)

where R is cluster range and d is distance from node s to node u where u is the neighboring node of node s and

E_{r e s i d u a l} (s)

and

E_{i n i t i a l} (s)

are the residual and initial energy in s, which is considered uniform for all the nodes.

Figure 9

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.

Figure 10

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 $O (n * r)$ messages where r denotes the number of rotations. On the other hand, DWEHC requires remaining energy and neighbor proximity information requires $O (n + c)$ rounds where c denotes proximity information. DWEHS suffers from huge number of control message. In the first phase, it gathers information from each node energy and then decides a higher energy node to be in DS. In the second phase, it tries to reduce the size of a DS to avoid unnecessary energy consumption. Thus, it requires $O (n^{2})$ rounds to form the network, which is higher than $O (n)$ and $O (n + c)$ rounds.

Table 4

Quantitative analysis of energy efficient cluster.

	5.3.1	5.3.2	5.3.3
Cluster detail	HEED	DWEHC	PACDS
CH election	Weight based	Weight based	Weight based
Intracluster routing	Single-hop	Single-hop	Single-hop
Intercluster routing	Multihop	Multihop	Multihop
Control message	High	High	High
Domino effect	Yes	Yes	Yes
Computation round	$O (n * r)$	$O (n + c)$	$O (n^{2})$
Communication complexity	—	$O (n)$	$O (n + m)$
Stationary or mobile	Stationary	Stationary	Mobile
Maintenance	No	No	No
Basic control	Distributed	Distributed	Distributed

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 $| C_{i} |$ distance is less than L from cluster $C_{j}$ . Cluster $C_{i}$ searches for its neighboring cluster $C_{j}$ to assure $| C_{i} + C_{j} | \leq U$ and increase the total number. In another situation when $| C_{i} | + | C_{j} | > U$ for the entire neighboring clusters, it minimizes the value via searching $C_{j}$ . After joining two clusters, the CH keeps more member nodes.

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.

Figure 11

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

Figure 12

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 $2 H (Δ) + 2$ , where Δ is the maximum node degree in a network and H is a harmonic function. The second strategy is a two-stage strategy with an approximation ratio of $2 H (Δ) + 2$ proposed in [85].

Table 5

Quantitative analysis of load balancing cluster.

	5.4.1	5.4.2	5.4.3
Cluster detail	AMC	LBGC	LBCD-GA
CH election	Weight based	Weight based	Weight based
Intracluster routing	Single-hop	Single-hop	Single-hop
Intercluster routing	Multihop	Multihop	Multihop
Control message	High	High	High
Domino effect	No	Yes	Yes
Computation round	—	Two rounds	$O (n \log n)$
Communication complexity	—	—	—
Stationary or mobile	Mobile	Stationary	Stationary
Maintenance	Yes	No	No
Basic control	Distributed	Distributed	Distributed

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.

Figure 13

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.

Figure 14

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.

Figure 15

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.

Figure 16

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 $k (k \geq 2)$ , the new node elects a parent node which has the minimum distance to its CH. Thus, the new node becomes an ordinary node, and the selected node changes its status to the forwarding node. Else, if the new node finds gateway nodes in its neighbor, the new one becomes a CH. Else, ordinary node is within the range of the new node whose distance to their CHs is k. The new selects an ordinary node as its parent and becomes a CH. The chosen node changes its status from the ordinary node to gateway node and all other nodes, which are fallen on the root from the gateway node to its CH, also change their status to cluster forwarding node.

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 $c (i)$ of i broadcast help-need message to other clusters. A cluster head that has received the message checks a node whose contribution degree is smaller than node i. The cluster head sends help-gives message when the node exits. Thus, the node i moves to the new cluster head upon receiving the help-gives message. Advantages of the algorithm are improved network connectivity and lower aggregate contribution degree to substitute the dying node.

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 $O (\log q)$ which is lower than CBNet(G). However, in node leaving procedure, the decedent nodes of the leaving node rejoin the network. It happens that the size of the subtree of leaving node is bigger than the other subtree. Therefore, the complexity of joining subtree may be very near to the network formation.

Table 6

Quantitative analysis of cluster maintenance.

	5.5.1	5.5.2	5.5.3
Cluster detail	CNet(G)	CBNet(G)	NNDBC
CH election	Degree based	Degree based	Degree based
Intracluster routing	Single-hop	Multihop	Single-hop
Intercluster routing	Multihop	Multihop	Multihop
Control message	Medium	High	High
Domino effect	No	No	No
Computation round	$O (\log q)$	$O (q + k)$	—
Communication complexity	$O (2 p - 1)$	$O (r + l)$	—
Stationary or mobile	Stationary	Stationary	Mobile
Maintenance	Yes	Yes	Yes
Basic control	Distributed	Distributed	Distributed

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 (CH_i) and secondary CH (CH_ij) 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.

Figure 17

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.

Figure 18

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 $O (n + Δ)$ data overheads where n is the number of its child nodes, and Δ is the additional data load of relaying information. Therefore, the chances of CH(s) dying earlier are more than the other nodes. It is indigent that all the nodes use their battery at the same period and very less energy is left behind.

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 $O (n + Δ)$ data overheads where n is the child nodes, and Δ is the additional data load of relaying information. In UCS, the number of MNs in each CH is not constant. CH changes its number of nodes based on the estimated communication load. Therefore, UCS claims that it maintains more identical energy dissipation between the CHs. Thus, energy dissipation for each CH is similar which increases the total network lifetime.

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

Table 7

Quantitative analysis of homogeneous and heterogeneous network.

	5.6.1	5.6.2	5.6.3
Cluster detail	TL	UCS	CDR
CH election	Degree based	Weight based	Weight based
Intracluster routing	Single-hop	Multihop	Single-hop
Intercluster routing	Multihop	Multihop	Multihop
Control message	High	High	Medium
Domino effect	Yes	No	No
Computation round	—	—	—
Communication complexity	—	—	—
Stationary or mobile	Stationary	Mobile	Stationary
Maintenance	No	Yes	No
Basic control	Distributed	Distributed	Distributed

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 (i)

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.

(ii)

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.

(iii)

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 (i)

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.

(ii)

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.

(iii)

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.

(iv)

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.

(v)

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 (i)

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.

(ii)

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.

References

Razzaque

M. A.

Bleakley

Dobson

Compression in wireless sensor networks: a survey and comparative evaluation

ACM Transactions on Sensor Networks 2013 10 1, article 5

10.1145/2528948

2-s2.0-84890423310

Han

Zhang

Liu

Tian

A general self-organized tree-based energy-balance routing protocol for wireless sensor network

IEEE Transactions on Nuclear Science 2014 61 2 732 740

10.1109/TNS.2014.2309351

2-s2.0-84899479260

Belding-Royer

E. M.

Hierarchical routing in ad hoc mobile networks

Wireless Communications and Mobile Computing 2002 2 5 515 532

10.1002/wcm.74

2-s2.0-0042218631

Bangash

J. I.

Abdullah

A. H.

Anisi

M. H.

Khan

A. W.

A survey of routing protocols in wireless body sensor networks

Sensors 2014 14 1 1322 1357

10.3390/s140101322

2-s2.0-84940275326

Karaboga

Okdem

Ozturk

Cluster based wireless sensor network routing using artificial bee colony algorithm

Wireless Networks 2012 18 7 847 860

10.1007/s11276-012-0438-z

2-s2.0-84869864314

Jiang

Node self-deployment algorithm based on an uneven cluster with radius adjusting for underwater sensor networks

Sensors 2016 16 1 98

10.3390/s16010098

Jiang

Liu

Ruan

Jiang

A new node deployment and location dispatch algorithm for underwater sensor networks

Sensors 2016 16 1 82

10.3390/s16010082

Valero

Sivanathan

Bosché

Abdel-Wahab

Musculoskeletal disorders in construction: a review and a novel system for activity tracking with body area network

Applied Ergonomics 2016 54 120 130

10.1016/j.apergo.2015.11.020

Zymunt

Haas

J. Y. H.

Gossip-based ad hoc routing

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '02)

2002

IEEE

1707 1716

10.1109/INFCOM.2002.1019424

10.

Intanagonwiwat

Govindan

Estrin

Heidemann

Silva

Directed diffusion for wireless sensor networking

IEEE/ACM Transactions on Networking 2003 11 1 2 16

10.1109/TNET.2002.808417

2-s2.0-0037295692

11.

Pang

Guo

Xue

Martin

C. F.

A POMDP based routing model to enhance directed diffusion in wireless sensor networks

Proceedings of the International Conference on Control Engineering and Communication Technology (ICCECT '13)

2013

IEEE Computer Society

180 183

10.1109/ICCECT.2013.49

12.

Braginsky

Estrin

Rumor routing algorthim for sensor networks

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications (WSNA '02)

September 2002

Atlanta, Ga, USA

ACM

22 31

10.1145/570738.570742

2-s2.0-0036986248

13.

Gupta

Kumar

P. R.

The capacity of wireless networks

IEEE Transactions on Information Theory 2000 46 2 388 404

10.1109/18.825799

MR1748976

2-s2.0-33747142749

14.

Hong

Gerla

An ad hoc network with mobile backbones

Proceedings of the International Conference on Communications (ICC '02)

May 2002

3138 3143

2-s2.0-0036286440

15.

Sinha

Lobiyal

D. K.

Performance evaluation of data aggregation for cluster-based wireless sensor network

Human-Centric Computing and Information Sciences 2013 3, article 13 1 17

10.1186/2192-1962-3-13

16.

Perkins

C. E.

Royer

E. M.

Das

S. R.

Marina

M. K.

Performance comparison of two on-demand routing protocols for ad hoc networks

IEEE Personal Communications 2001 8 1 16 28

10.1109/98.904895

2-s2.0-0035249889

17.

Vlajic

Xia

Wireless sensor networks: to cluster or not to cluster?

Proceedings of the International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM '06)

June 2006

Buffalo-Niagara Falls, NY, USA

IEEE Computer Society

258 266

10.1109/wowmom.2006.116

2-s2.0-33845925844

18.

J. Y.

Chong

P. H. J.

A survey of clustering schemes for mobile ad hoc networks

IEEE Communications Surveys & Tutorials 2005 7 1 32 48

10.1109/comst.2005.1423333

2-s2.0-84892572090

19.

Liu

A survey on clustering routing protocols in wireless sensor networks

Sensors 2012 12 8 11113 11153

10.3390/s120811113

2-s2.0-84865362384

20.

Abbasi

A. A.

Younis

A survey on clustering algorithms for wireless sensor networks

Computer Communications 2007 30 14-15 2826 2841

10.1016/j.comcom.2007.05.024

2-s2.0-34548850872

21.

Kumarawadu

Dechene

D. J.

Luccini

Sauer

Algorithms for node clustering in wireless sensor networks: a survey

Proceedings of the 4th International Conference on Information and Automation for Sustainability (ICIAFS '08)

December 2008

295 300

10.1109/iciafs.2008.4783999

2-s2.0-64049084294

22.

Deosarkar

B. P.

Yadav

N. S.

Yadav

R. P.

Clusterhead selection in clustering algorithms for wireless sensor networks: a survey

Proceedings of the International Conference on Computing, Communication and Networking (ICCCN '08)

December 2008

St. Thomas, Virgin Islands, USA

IEEE

1 8

10.1109/icccnet.2008.4787686

2-s2.0-63649099481

23.

Wei

Yang

Gao

Zhang

Cluster-based routing protocols in wireless sensor networks: a survey

Proceedings of the International Conference on Computer Science and Network Technology (ICCSNT '11)

December 2011

Harbin, China

IEEE

1659 1663

10.1109/iccsnt.2011.6182285

2-s2.0-84860617979

24.

Jiang

Yuan

Zhao

Towards clustering algorithms in wireless sensor networks-a survey

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '09)

April 2009

Budapest, Hungary

10.1109/wcnc.2009.4917996

2-s2.0-70349187092

25.

Boyinbode

Takizawa

A survey on clustering algorithms for wireless sensor networks

International Journal of Space-Based and Situated Computing 2011 1 2/3 130 136

10.1504/ijssc.2011.040339

26.

Arboleda C

L. M.

Nasser

Comparison of clustering algorithms and protocols for wireless sensor networks

Proceedings of the Canadian Conference on Electrical and Computer Engineering (CCECE '06)

May 2006

Ottawa, Canada

1787 1792

10.1109/ccece.2006.277358

2-s2.0-39049086878

27.

Haneef

Zhongliang

Design challenges and comparative analysis of cluster based routing protocols used in wireless sensor networks for improving network life time

Advances in Information Sciences and Service Sciences 2012 4 1 450 459

10.4156/AISS.vol4.issue1.56

2-s2.0-84856573209

28.

Ozdemir

Xiao

Secure data aggregation in wireless sensor networks: a comprehensive overview

Computer Networks 2009 53 12 2022 2037

10.1016/j.comnet.2009.02.023

2-s2.0-67549118456

29.

Rajagopalan

Varshney

P. K.

Data aggregation techniques in sensor networks: a survey

IEEE Communications Surveys and Tutorials 2006 8 4 48 63

10.1109/comst.2006.283821

2-s2.0-84874468531

30.

Pan

Greedy construction of load-balanced virtual backbones in wireless sensor networks

Wireless Communications and Mobile Computing 2014 14 7 673 688

10.1002/wcm.2218

2-s2.0-84897990303

31.

Maraiya

Kant

Gupta

Wireless sensor network: a review on data aggregation

International Journal of Scientific & Engineering Research 2011 2 4 1 7

32.

Lee

Younis

Lee

Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance

Ad Hoc Networks 2015 24 1 19

10.1016/j.adhoc.2014.07.012

2-s2.0-84908117957

33.

Lee

S. H.

Lee

Song

Lee

H. S.

Gradual cluster head election for high network connectivity in large-scale sensor networks

Proceedings of the 13th International Conference on Advanced Communication Technology: Smart Service Innovation through Mobile Interactivity (ICACT '11)

February 2011

168 172

2-s2.0-79955688962

34.

Mokhtar

Merabti

A survey of network management architecture in wireless sensor network

Proceedings of the 6th Annual PostGraduate Symposium on The Convergence of Telecommunications, Networking and Broadcasting

2006

35.

Younis

Senturk

I. F.

Akkaya

Lee

Senel

Topology management techniques for tolerating node failures in wireless sensor networks: a survey

Computer Networks 2014 58 1 254 283

10.1016/j.comnet.2013.08.021

2-s2.0-84893734846

36.

Freris

N. M.

Kowshik

Kumar

P. R.

Fundamentals of large sensor networks: connectivity, capacity, clocks, and computation

Proceedings of the IEEE 2010 98 11 1828 1846

10.1109/jproc.2010.2065790

2-s2.0-77958151307

37.

Liu

A.-F.

Zhang

P.-H.

Chen

Z.-G.

Theoretical analysis of the lifetime and energy hole in cluster based wireless sensor networks

Journal of Parallel and Distributed Computing 2011 71 10 1327 1355

10.1016/j.jpdc.2011.05.003

ZBL1225.68045

2-s2.0-80051666129

38.

Chen

An unequal cluster-based routing protocol in wireless sensor networks

Wireless Networks 2009 15 2 193 207

10.1007/s11276-007-0035-8

2-s2.0-59349098891

39.

Aziz

A. A.

Sekercioglu

Y. A.

Fitzpatrick

Ivanovich

A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks

IEEE Communications Surveys & Tutorials 2013 15 1 121 144

10.1109/surv.2012.031612.00124

2-s2.0-84873710092

40.

Liao

Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks

IEEE Sensors Journal 2013 13 5 1498 1506

10.1109/JSEN.2012.2227704

2-s2.0-84875749929

41.

Sahin

Gungor

V. C.

Kocak

Tuna

Quality-of-service differentiation in single-path and multi-path routing for wireless sensor network-based smart grid applications

Ad Hoc Networks 2014 22 43 60

10.1016/j.adhoc.2014.05.005

2-s2.0-84906313559

42.

Tapia

D. I.

Alonso

R. S.

García

Ó.

de la Prieta

Pérez-Lancho

Cloud-IO: cloud computing platform for the fast deployment of services over wireless sensor networks

7th International Conference on Knowledge Management in Organizations: Service and Cloud Computing 2013 172

Berlin, Germany

Springer

493 504 Advances in Intelligent Systems and Computing

10.1007/978-3-642-30867-3_44

43.

On calculating connected dominating set for efficient routing in ad hoc wireless networks

Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications

August 1999

Seattle, Wash, USA

ACM

7 14

10.1145/313239.313261

44.

Wan

P.-J.

Alzoubi

K. M.

Frieder

Distributed construction of connected dominating set in wireless ad hoc networks

Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS '02)

June 2002

1597 1604

2-s2.0-0036346466

45.

Misra

Mandal

Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks

IEEE Transactions on Parallel and Distributed Systems 2010 21 3 292 302

10.1109/tpds.2009.78

2-s2.0-76749100173

46.

Cardei

Cheng

D.-Z.

Connected domination in multihop ad hoc wireless networks

Proceedings of the 6th Joint Conference on Information Sciences (JCIS '02)

March 2002

251 255

2-s2.0-1642394904

47.

Zhang

Simon

Aydin

Harvesting-aware energy management for time-critical wireless sensor networks with joint voltage and modulation scaling

IEEE Transactions on Industrial Informatics 2013 9 1 514 526

10.1109/tii.2011.2174247

2-s2.0-84871821424

48.

X.-Y.

Wang

Complexity of data collection, aggregation, and selection for wireless sensor networks

IEEE Transactions on Computers 2011 60 3 386 399

10.1109/tc.2010.50

MR2767390

2-s2.0-79551553052

49.

Huang

Xiao

Soltani

Mutka

M. W.

The evolution of MAC protocols in wireless sensor networks: a survey

IEEE Communications Surveys & Tutorials 2013 15 1 101 120

10.1109/surv.2012.040412.00105

2-s2.0-84873710037

50.

Villas

L. A.

Boukerche

De Oliveira

H. A. B. F.

De Araujo

R. B.

Loureiro

A. A. F.

A spatial correlation aware algorithm to perform efficient data collection in wireless sensor networks

Ad Hoc Networks 2014 12 1 69 85

10.1016/j.adhoc.2011.08.005

2-s2.0-84888646633

51.

Wang

Yang

Lin

Keeping desired QoS by a Partial coverage algorithm for cluster-based wireless sensor networks

Journal of Networks 2014 9 12 3221 3229

10.4304/jnw.9.12.3221-3229

52.

Quang

P. T. A.

Kim

D.-S.

Throughput-aware routing for industrial sensor networks: application to ISA100.11a

IEEE Transactions on Industrial Informatics 2014 10 1 351 363

10.1109/tii.2013.2255617

2-s2.0-84890929971

53.

Gupta

S. K.

Jain

Sinha

Energy efficient clustering protocol for minimizing cluster size and inter cluster communication in heterogeneous wireless sensor network

International Journal of Advanced Research in Computer and Communication Engineering 2013 2 8

54.

Sharma

Jena

S. K.

Cluster based multipath routing protocol for wireless sensor networks

ACM SIGCOMM Computer Communication Review 2015 45 2 14 20

10.1145/2766330.2766333

55.

Carrano

R. C.

Passos

Magalhaes

L. C. S.

Albuquerque

C. V. N.

Survey and taxonomy of duty cycling mechanisms in wireless sensor networks

IEEE Communications Surveys and Tutorials 2014 16 1 181 194

10.1109/SURV.2013.052213.00116

2-s2.0-84894670694

56.

Chiang

C.-C.

H.-K.

Liu

Gerla

Routing in clustered multihop, mobile wireless networks with fading channel

Proceedings of the IEEE Singapore International Conference on Networks (SICON '97)

1997

57.

Dagdeviren

Erciyes

Tse

Semi-asynchronous and distributed weighted connected dominating set algorithms for wireless sensor networks

Computer Standards and Interfaces 2015 42 143 156

10.1016/j.csi.2015.05.005

2-s2.0-84937577759

58.

Tahouri

Atani

R. E.

Karbasi

A. H.

Deldjoo

Application of connected dominating sets in wildfire detection based on wireless sensor networks

International Journal of Information Technology, Communications and Convergence 2015 3 2 139 160

10.1504/ijitcc.2015.071021

59.

Ahmad

Jabbar

Paul

Rho

Mobility aware energy efficient congestion control in mobile wireless sensor network

International Journal of Distributed Sensor Networks 2014 2014 13

530416

10.1155/2014/530416

2-s2.0-84896460105

60.

Hoang

D. C.

Yadav

Kumar

Panda

S. K.

Real-time implementation of a harmony search algorithm-based clustering protocol for energy-efficient wireless sensor networks

IEEE Transactions on Industrial Informatics 2014 10 1 774 783

10.1109/TII.2013.2273739

2-s2.0-84891065680

61.

Shrivastava

Pokle

S. B.

Energy efficient scheduling strategy for data collection in wireless sensor networks

Proceedings of the International Conference on Electronic Systems, Signal Processing, and Computing Technologies (ICESC '14)

January 2014

170 173

10.1109/icesc.2014.35

2-s2.0-84896768667

62.

Kaur Kapoor

Majumdar

Nandy

Techniques for allocation of sensors in shared wireless sensor networks

Journal of Networks 2015 10 1 15 28

10.4304/jnw.10.01.15-28

63.

Deng

Shen

Mobility-based clustering protocol for wireless sensor networks with mobile nodes

IET Wireless Sensor Systems 2011 1 1 39 47

10.1049/iet-wss.2010.0084

64.

Singhal

Suri

A comparative study of hierarchical routing protocols in wireless sensor networks

Proceedings of the 2nd IEEE International Conference on Computing for Sustainable Global Development (INDIACom '15)

March 2015

New Delhi, India

1018 1023

65.

Kumar

Performance analysis of energy efficient clustering protocols for maximising lifetime of wireless sensor networks

IET Wireless Sensor Systems 2014 4 1 9 16

10.1049/iet-wss.2012.0150

2-s2.0-84896922748

66.

Vasudevan

Kurose

Towsley

Design and analysis of a leader election algorithm for mobile ad hoc networks

Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP '04)

October 2004

Berlin, Germany

IEEE

350 360

10.1109/icnp.2004.1348124

2-s2.0-17744394265

67.

Balaji

Revathi

An efficient heuristic for the minimum connected dominating set problem on ad hoc wireless networks

Proceedings of WASET 2012 68 1045 1051

68.

Jiang

Liu

Node deployment algorithm for underwater sensor networks based on connected dominating set

Sensors 2016 16 3 388

10.3390/s16030388

69.

Haseeb

Bakar

K. A.

Abdullah

A. H.

Ahmed

Grid based cluster head selection mechanism for wireless sensor network

Telkomnika (Telecommunication Computing Electronics and Control) 2015 13 1 269 276

10.12928/TELKOMNIKA.v13i1.1190

2-s2.0-84923167231

70.

Asgarnezhad

Torkestani

J. A.

A survey on backbone formation algorithms for Wireless Sensor Networks: (a new classification)

Proceedings of the Australasian Telecommunication Networks And Applications Conference (ATNAC '11)

November 2011

Melbourne, Australia

1 4

10.1109/atnac.2011.6096632

2-s2.0-84255209115

71.

Liu

Wang

Guo

A survey on connected dominating set construction algorithm for wireless sensor networks

Information Technology Journal 2010 9 6 1081 1092

10.3923/itj.2010.1081.1092

2-s2.0-77954531375

72.

Kumar

G. S.

Vinu Paul

M. V.

Athithan

Jacob

K. P.

Routing protocol enhancement for handling node mobility in wireless sensor networks

Proceedings of the IEEE Region 10 Conference (TENCON '08)

November 2008

Hyderabad, India

10.1109/tencon.2008.4766540

2-s2.0-63049109870

73.

Deng

Shen

Mobility-based clustering protocol for wireless sensor networks with mobile nodes

IEEE Xplore: IET Wireless Sensor Systems 2011 1 1 39 47

74.

Khan

A. W.

Abdullah

A. H.

Razzaque

M. A.

Bangash

J. I.

VGDRA: a virtual grid-based dynamic routes adjustment scheme for mobile sink-based wireless sensor networks

IEEE Sensors Journal 2015 15 1 526 534

10.1109/jsen.2014.2347137

2-s2.0-84910623698

75.

Khan

A. W.

Abdullah

A. H.

Abdur Razzaque

Bangash

J. I.

Altameem

VGDD: a virtual grid based data dissemination scheme for wireless sensor networks with mobile sink

International Journal of Distributed Sensor Networks 2015 2015 17

890348

10.1155/2015/890348

2-s2.0-84924256227

76.

Kim

D.-S.

Chung

Y.-J.

Self-organization routing protocol supporting mobile nodes for wireless sensor network

Proceedings of the 1st International Multi-Symposiums on Computer and Computational Sciences (IMSCCS '06)

June 2006

Hangzhou, China

622 626

10.1109/IMSCCS.2006.265

77.

Luo

Zhang

A new cluster based routing protocol for VANET

Proceedings of the 2nd International Conference on Networks Security, Wireless Communications and Trusted Computing (NSWCTC '10)

April 2010

176 180

10.1109/nswctc.2010.48

2-s2.0-77954388490

78.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

10.1109/tmc.2004.41

2-s2.0-10944266504

79.

Ding

Holliday

Celik

Distributed energy-efficient hierarchical clustering for wireless sensor networks

Proceedings of the IEEE International Conference on Distributed Computing in Sensor Networks

July 2005

Santa Clara University

322 339

2-s2.0-26444521722

80.

Dai

Gao

Stojmenovic

On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks

Journal of Communications and Networks 2002 4 1 59 70

10.1109/JCN.2002.6596934

2-s2.0-0038735958

81.

Ohta

Inoue

Kakuda

An adaptive multihop clustering scheme for highly mobile ad hoc networks

Proceedings of the 6th International Symposium on Autonomous Decentralized Systems (ISADS '03)

April 2003

293 300

10.1109/isads.2003.1193960

2-s2.0-84942237253

82.

Deng

A load balance clustering algorithm for heterogeneous wireless sensor networks

Proceedings of the International Conference on E-Product E-Service and E-Entertainment (ICEEE '10)

November 2010

Henan, China

IEEE

1 4

10.1109/iceee.2010.5661337

2-s2.0-78651481362

83.

Liang

Y.-C.

Chen

K.-C.

G. Y.

Mähönen

Cognitive radio networking and communications: an overview

IEEE Transactions on Vehicular Technology 2011 60 7 3386 3407

10.1109/tvt.2011.2158673

2-s2.0-80052863987

84.

Goldberg

D. E.

Holland

J. H.

Genetic algorithms and machine learning

Machine Learning 1988 3 2 95 99

85.

Guha

Khuller

Approximation algorithms for connected dominating sets

Algorithmica 1998 20 4 374 387

10.1007/pl00009201

MR1600830

86.

Steiner Tree Problems in Computer Communication Networks 2008

World Scientific

10.1142/9789812791450

MR2406173

87.

Hong

Gerla

Scalable routing protocols for mobile ad hoc networks

IEEE Network 2002 16 4 11 21

10.1109/mnet.2002.1020231

2-s2.0-0036638646

88.

Yadav

N. S.

Deosarkar

B. P.

Yadav

A low control overhead cluster maintenance scheme for mobile ad hoc NETworks (MANETs)

International Journal of Recent Trends in Engineering 2010 1 1 100 104

89.

Uchida

Islam

A. K. M. M.

Katayama

Chen

Wada

Construction and maintenance of a novel cluster-based architecture for ad hoc sensor networks

Journal of Ad Hoc and Sensor Wireless Networks 2008 6 1-2 1 31

90.

Islam

A. K. M. M.

Wada

Uchida

Chen

A better dynamic cluster-based structure of wireless sensor network for efficient routing

International Journal of Innovative Computing, Information and Control 2012 8 10 6747 6760

2-s2.0-84866020617

91.

Basagni

Mastrogiovanni

Petrioli

A performance comparison of protocols for clustering and backbone formation in large scale ad hoc networks

Proceedings of the IEEE International Conference on Mobile Ad-Hoc and Sensor Systems

October 2004

70 79

2-s2.0-20344365067

92.

Islam

A. M.

Katayama

Chen

Wada

A novel cluster-based architecture and routing protocols for dynamic ad-hoc radio networks

Journal of Electrical Engineering, The Institution of Engineers, Bangladesh 2006 EE33 1-2

93.

Jiang

Liu

Node non-uniform deployment based on clustering algorithm for underwater sensor networks

Sensors 2015 15 12 29997 30010

10.3390/s151229786

94.

Loscri

Morabito

Marano

A two-levels hierarchy for low-energy adaptive clustering hierarchy (TL-LEACH)

Proceedings of the IEEE 62nd Vehicular Technology Conference (VTC '05)

2005

IEEE

1809 1813

10.1109/VETECF.2005.1558418

95.

Soro

Heinzelman

W. B.

Prolonging the lifetime of wireless sensor networks via unequal clustering

Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS '05)

April 2005

10.1109/ipdps.2005.365

2-s2.0-33746310074

96.

Bangash

J. I.

Khan

A. W.

Abdullah

A. H.

Data-centric routing for intra wireless body sensor networks

Journal of Medical Systems 2015 39 9 1 13

10.1007/s10916-015-0268-5

2-s2.0-84939545482

97.

Bangash

J. I.

Abdullah

A. H.

Abdur Razzaque

Khan

A. W.

Reliability aware routing for intra-wireless body sensor networks

International Journal of Distributed Sensor Networks 2014 2014 10

786537

10.1155/2014/786537

2-s2.0-84908338714

98.

Bangash

J. I.

Abdullah

A. H.

Khan

A. W.

Razzaque

M. A.

Yusof

Critical Data Routing (CDR) for intra wireless body sensor networks

TELKOMNIKA 2015 13 1 181 192

10.12928/telkomnika.v13i1.365

2-s2.0-84923128274