Modern Clustering Techniques in Wireless Sensor Networks

1.1. Wireless sensor networks

In the recent years, wireless sensor networks (WSNs) have attained significant roles in various applications and have attracted the attention of researchers due to their complex, multifaceted requirements which often divulge inherent tradeoffs. A wireless sensor network is made up of sensor nodes connected through an ad hoc and self-configuring connectivity.

A wireless sensor network consists of a set of spatially distributed autonomous sensor nodes to monitor environmental parameters such as temperature, pressure, etc., and to cooperatively pass their data through the network to a primary location called sink. The sink of a WSN collects data from the sensor nodes and reports the same to users through the Internet or through any private virtual network (PVN). By nature, WSNs inherit features and requirements of an ad hoc network. WSN belongs to the class of low range wireless personal area network (LPWPAN).

A sensor node consists of a radio transceiver (which performs the role of both transmitter and receiver), a microcontroller, and an electronic circuit for interfacing with the associated sensors and an energy source (usually a battery or an embedded form of energy harvesting). The cost and size of sensor nodes show a significant degree of variation depending upon the nature of the applications. In many applications, sensor nodes demand self-organization due to the randomness present in uncontrolled, non-deterministic topologies.

Depending upon the nature of applications, various categories of sensor nodes are provided for monitoring parameters such as temperature, moisture, sound, motion of objects, etc. In essence, sensor networks compensate for human efforts in inaccessible terrains and present more comfortable, smart snapshots of the environment. In the recent future, sensor networks would conquer an integral part of human life and make existing personal computers, mobile communication devices and other computing devices less popular.

A sensor network may be composed of homogenous or heterogeneous sensor nodes. They may monitor either space or objects or interactions of these two. Today, sensor networks are employed in diversified fields such as battle field surveillance, medical diagnostics, precision agriculture, weather monitoring and home appliances control. Every sensor application demands its own set of requirements and characteristics. Some sensor applications employ reactors in the place of ordinary sensors to react to the events in an appropriate manner.

Design of WSNs exhibits challenges due to the limited resources in terms of storage, processing and communication of messages. In most of the sensor applications, these resources become non-renewable also. Theoretical estimation could not be accurate enough in many scenarios to predict and prevent failure of sensor networks. The design complexity of WSNs increases with emerging applications and their requirements. Conventional algorithms designed for ad hoc networks are not good enough to cater to the needs of these sensor applications and this mandates new policies and protocols to be evolved.

Wireless sensor networks can be classified into pre-deterministic and unattended networks based on the type of applications. Former category of networks gains the advantages of quality of service (QoS), fault tolerance, robustness and scalability. In many pragmatic scenarios, human supervision for sensor networks is limited or prohibited since the nodes are dispersed in critical environments such as deeper part of jungles and underwater environments. These networks are called as unattended networks.

Also, an inherent trade-off is observed amidst the parameters used to determine the performance of a WSN. The applications seldom reconcile with identical set of parameters. Juxtaposing the requirements, they resist generalized solutions owing to their nature of self-contradiction and application-specific precincts. As the autonomy of nodes increase, scalability of the solutions is challenged. Research efforts made to improve throughput often result in increased overhead. There is a combined need for fast convergence time and minimum energy consumption of sensor nodes. When the solutions are inclined toward one or a set of parameters, they habitually compromise the rest of the performance factors. This intricacy leads to many interesting queries and solutions in describing the efficiency of a WSN. Slicing over the temporal and spatial domains, the process becomes more complex, multifaceted and highly specialized.

The lifetime of a sensor network is stanchly dependent on the energy consumption, especially when there is no provision for human access to the involved sensor nodes. Hence, many methods have been proposed to minimize energy consumption in wireless sensor networks. The design of wireless sensor networks exhibits many challenges from this perspective.

The performance of a wireless sensor network is not only multifaceted but also inherently imbalanced under one or limited angles of perception. A holistic and fair approach requires an unambiguous and complete understanding of sensor applications.

1.2. Clustering in wireless sensor networks

Sensor nodes in an environment collect data and transmit it to a sink either directly or collaboratively through other nodes. Many sensor applications cluster the sensor nodes to achieve scalability, robustness and reduced network traffic.

A sample scenario of clustering is shown in Figure 1. Here, clusters are provided with cluster heads and these cluster heads transmit the aggregated data to the base station or the sink.

The primary advantage of clustering is the scalability of performance across the expanding sensor networks. In addition to this, clustering approach provides numerous secondary advantages. It ensures reliability and avoids one-point failure due to its localized solutions. A clustering solution can suggest a sleep/wakeup schedule for a WSN to effectively reduce power consumption. In many sensor applications, all the sensor nodes are not required to be in wakeup state and consume energy. Based on the temporal and spatial dependencies, some sensor nodes can be put in sleep mode in which no energy is consumed. An effective schedule can be devised and communicated to these sensor nodes through the sink or administrator. Also, clustering ensures scalability of the application performance due to its semi-distributed nature.

As indicated in the work done by Abbasi and Younis [1], clustering possesses certain challenges amidst its advantages. There are selected sensor nodes identified as “cluster heads,” which monitor and regulate the data flow across clusters for which considerable energy is consumed. Hence, the process of reclustering and reelection of cluster heads is required which results in the reduced lifetime of sensor networks.

One of the conventional clustering protocols named low energy adaptive clustering hierarchy (LEACH) [2] addresses the overloading of clusters and it rotates the role of cluster heads among the sensor nodes present in a cluster. The significant drawback of this approach is that no weightage is given for the residual energy of the sensor nodes. The limitations of LEACH motivated researchers to revisit and improve the LEACH protocol to adopt QoS requirements of WSNs. In general, LEACH and its variants suffer from scalability and load balancing despite their simplicity.

An energy aware clustering protocol using fuzzy logic (ECPF) [3] which is a hierarchical clustering protocol employs a fuzzy based system with the input variables namely, the node degree and the node centrality to form on-demand clusters. This work inspired many researchers to re-estimate the role of cluster heads from the intra-cluster perspective in a hierarchical sensor environment.

A clustering approach namely, energy aware clustering scheme with transmission power control for sensor networks (EACLE) [4] presents a distributed approach for path selection to reach the sink. This scheme sets different levels of transmission power for intra-cluster and inter-cluster communication to improve energy savings.

An energy harvesting protocol namely, energy harvesting and information transmission protocol (EHITP) [5] estimates the energy to be harvested based on the outage probability.

The aforementioned contemporary clustering approaches for wireless sensor networks indicate the need for the new clustering solutions from multiple perspectives.

The advent of new technologies and emerging trends in application development challenge the research findings of performance in WSNs, especially from the energy perspective. A family of solutions is needed to work with various types of unattended sensor networks where many parameters are unpredictable due to the random deployment of sensor nodes. Observing closely, focus is required more on the communication overheads of sensor nodes. Also, any proposed clustering approach should be tested for its scalability in a WSN environment.

1.3. Organization of the chapter

The remaining part of this chapter presents the four proposed clustering approaches for wireless sensor networks. These approaches have improved the lifetime of sensor networks by taking advantages of techniques such as cognitive cluster head selection, support for energy harvesting, hierarchical clustering and effective sleep scheduling of sensor nodes. These have been presented in the following sections, titled, energy aware fuzzy clustering algorithm (EAFCA) [6], efficient energy harvesting assisted clustering (EEHC) algorithm [7], energy-efficient recursive clustering (EERC) algorithm [8] and adaptive distributed clustering algorithm (ADCA) [9], respectively.

2.1. Effective cluster head election in EAFCA

Energy aware fuzzy clustering algorithm (EAFCA) is a proposal based on cognitive technique for non-probabilistic clustering process. In this, the sensor nodes are assumed to be deployed in an unmanned wireless sensor application and clustered from the energy perspective.

The following assumptions have been made on the experimental environment.

• The sensor deployment is done in a random manner.

• It is an unmanned sensor environment.

• All the sensor nodes are kept static.

• The distance between two sensor nodes is measured through the received signal strength.

2.2. Cluster formation

After the sensor nodes are deployed, the distance between any two sensor nodes have to be computed. For this, our proposed approach employs a mechanism in which a beacon signal is transmitted from the sink to the rest of the sensor nodes. Based on the received signal strength, a sensor node can calculate its distance from the sink. Then a group of tentative cluster heads (TCHs) are elected from the sensor network for a specific fraction of the entire network as follows. A threshold “T” is calculated and forwarded to all the sensor nodes. Every sensor node generates a random number and compares the same against the received threshold value. Suppose the generated value is more than the threshold, then the sensor node declares itself as a cluster head. Otherwise, it becomes an ordinary sensor node.

The proposed method results in 2-hop cluster formation and a permanent cluster head (CH) is elected based on fuzzy logic which emphasizes the following three factors:

(1) Remaining residual energy:

This parameter is expected to be higher for an eligible CH in a competition phase as it is heavily engaged to intra-cluster and inter-cluster data traffic.

(2) Node degree at its 2-hop coverage:

This parameter signifies the total number of neighbors which are located in the 2-hop distance from the tentative CH and is calculated as in Eq. (1). It is desirable for a tentative cluster head to have a higher value for this parameter to become a permanent cluster head.

where S₂-hop-nbr(i) gives the total number of neighbors for the tentative cluster head in its 2-hop coverage. A typical 2-hop clustering environment in wireless sensor networks is represented in Figure 2 [6].

(3) Centrality of the CH:

For an effective CH, this parameter should yield low values to reduce energy consumption during the data aggregation and flooding processes. Centrality of a node is calculated using Eq. (2).

where, the parameter “d(i,j)” represents the distance between nodes “i” and “j” in which node j is a member of the set 2-hop-nbr. The variable “A” represents area of the network.

Using tentative cluster heads (TCHs) that are identified and by employing fuzzy logic, primary cluster heads (PCHs) are elected considering the aforementioned three parameters. The fuzzy output variable “chance” is computed for every tentative cluster head as shown in Table 1 to compute its probability to become to a permanent cluster head.

Using Mamdani method, the fuzzy if-then rules are processed. Every tentative cluster head obtains its chance values and broadcasts the same to all its 2-hop neighbors. It happens in subsequent stages of hop coverage.

Thus a sensor node can either become a cluster head or remains as an ordinary node. An ordinary node has to identify the suitable cluster to join. Suppose it has received advertisements from two or more cluster heads to join, then it will choose the nearby cluster head and joins its group. This is done from the energy perspective. On certain occasions, it may receive advertisements from two cluster heads which are located at equal distances. In such case, the sensor node will choose the cluster head from whom the advertisement has been received earlier and joins. Thus overlapping of clustering is avoided.

Following the process of cluster formation, the data is generated from the sensor nodes. The cluster heads collect the data from the cluster nodes and aggregate the data. Here, a cluster is formed on 2-hop coverage and hence the aggregation can be done on a larger scale compared to the conventional 1-hop clustering approaches.

The cluster heads have to report the aggregated data to the sink. Unlike LEACH and many conventional algorithms, the proposed algorithm inherits the presence of multi-hop relay between the cluster head and the sink. This multi-hop relay favors the selection of any one path based on certain probability among multiple choices and the selected path is not necessarily to be an optimal path as followed in many approaches. The repetitive employment of a few popular paths which have been identified as efficient paths causes energy depletion of nodes on these paths and pushes them die soon. Our idea of selecting less used or unused paths can effectively contribute to the distribution of energy consumption and prolong the lifetime of sensor nodes.

2.3. Performance evaluation of EAFCA

The performance of the algorithm is evaluated under three different scenarios. In scenario 1, the sink is positioned at the center and 100 sensor nodes are deployed. In scenario 2, the sink is positioned at the center while the number of sensor nodes deployed was doubled as 200 to test the scalability of the network. In scenario 3, the sink is located outside the predefined WSN boundaries and the network size is maintained as in scenario 2. The performance of EAFCA algorithm is compared against the benchmarking protocols namely, low energy adaptive clustering hierarchy (LEACH), energy aware clustering protocol using fuzzy logic (ECPF) and energy aware clustering scheme with transmission power control for sensor networks (EACLE).

The metrics employed for computing the lifetime of sensor networks are, first node dies (FND) and half of the nodes alive (HNA) metrics. These two metrics are widely adopted based on the viewpoint whether the energy depletion of the very first node in the network or half of the nodes indicate the death of the network. From the simulation results, it has been observed that the proposed algorithm shows 88% energy improvement compared to LEACH, 46% of improvement with respect to EACLE and 30% of improvement with respect to ECPF.

It is to be observed that LEACH shows the poorest performance among the selected clustering approaches since it does not re-elect cluster heads from the energy perspective and it continues to be a probabilistic model. EACLE shows some improvement in energy consumption as studied from the simulation results. The gain in energy efficiency is achieved in EACLE since it employs multiple paths for inter-cluster traffic and postpones the death of sensor nodes. ECPF claims more energy improvement since it adopts a fuzzy based cluster head election. The results observed across both FND and HNA metric confirms this claim.

The proposed EAFCA reduces energy efficiency by considering necessary and sufficient parameters for a cluster head election and assumes a feasible configuration in which 2-hop coverage is given for every cluster head and multi-hop relay is done for inter-cluster communication. The results demonstrate that EAFCA keeps WSN functioning for longer time than the other approaches.

This work stands as a representative for cognitive and effective cluster head election process. Such strategies expose the sensor networks and its applications to the emerging era of explorations and can be eventually commercialized.

3.1. Energy harvesting in wireless sensor networks

Lifetime of wireless sensor applications depends upon the lifetime of the sensor nodes which are constrained by their energy resources. This can be managed by the use of energy harvesting, utilizing ambient sources to prolong the life of the batteries in wireless sensor nodes. The efficiency of this approach depends upon how much energy is harvested. This can majorly influence the lifetime of sensor nodes and in turn that of the sensor network. In our efficient energy harvesting assisted clustering (EEHC) for wireless sensor networks, the effective energy harvesting for wireless sensor networks is experimented and studied through an efficient energy budgeting. The measurement of energy consumption, energy budgeting and energy harvesting are presented as follows.

3.2. Energy consumption

A sensor node consumes energy during sensing the data and forwarding it to the cluster head. A cluster head consumes the energy during the reception, data aggregation and forwarding the aggregated data. The energy consumption of a cluster member to sense and transmit 1-bit of information to the cluster head is estimated in Eq. (3):

Assuming a sensing rate of “x,” the total data sensed and transmitted by “n” cluster members in a time period “t” is estimated as given in Eq. (4).

Since the maximum number of cluster members are located at 1-hop distance to the cluster head, it is assumed that the data sensed at time “t” is transmitted to the cluster head within the same interval. Suppose a cluster head collects L-bit length of data at time “t,” (i.e., L= x.t.n) then the total energy conservation for data reception, aggregation and forwarding in that CH across time period “t” is estimated as given in Eq. (5).

where α stands for aggregation ratio.

The total energy consumed in time “t” for a cluster is given in Eq. (6).

For a time slot “t,” the entire cluster, i.e., all the cluster nodes including the cluster head should harvest the energy equal to that of the estimated energy. Suppose there are “n” cluster members and a cluster head, then the energy that is required to be harvested by a sensor node in a cluster is given by the Eq. (7).

3.3. Energy harvestings

For every time interval “T” between time “t₁” and “t₁+T,” the harvested energy is calculated as given in Eq. (8).

In Eq. (8), the three components represent the energy of the node at starting time “t₁,” energy harvested at time interval “T” and energy leakage during this interval. The factor “τ” represents charging efficiency. All the sensor nodes are provided with the storage buffers to store the harvested energy.

3.4. Energy budget

The energy consumed must be compensated by the energy harvested within the boundary of a cluster in any given time slot, i.e., the energy budget should harvest more energy than that of the energy consumed in every cluster periodically. An efficient energy budget should ensure that the energy consumption should not be increased than the energy harvested across any time slice.

3.5. Performance evaluation of EEHC

The performance of our EEHC has been compared with a modern clustering protocol named energy harvesting and information transmission protocol (EHITP) and the classical clustering protocol LEACH under three scenarios. In scenario 1, 100 sensor nodes are deployed in a region of 200 × 200 m². In scenarios 2 and 3, the population of sensor nodes and area are doubled successively. The experimental results indicate that EEHC exhibits a mean improvement of 91 and 67% when compared to LEACH and EHITP, respectively.

Thus the harvesting can be made efficient through appropriate budgeting in wireless sensor networks and this budgeting further is influenced by the nature of the sensor applications and critical dynamic constraints.

4.1. Event based clustering in wireless sensor networks

Generally, wireless sensor networks are employed for two purposes: continuous data monitoring and event monitoring. An example for the former category is a weather monitoring sensor network that measures temperature, moisture, etc. A typical event-based sensor network is habitat monitoring such as surveillance of wild animals and smart home applications. Except a few applications in the second category, most of the senor nodes are put on sleep mode in order to save power and the effective sleep/wakeup scheduling algorithms are required to determine the set of sensor nodes that can be scheduled to sleep with respect to time.

The energy-efficient recursive clustering (EERC) algorithm is an event-driven clustering algorithm, i.e., on the occurrence of an event, the clusters are formed to reduce energy dissemination, in a recursive fashion. The recursive clustering approach employs two stages of clustering process. The first stage of clustering is followed by further partitioning of clusters. Then CHs are elected from energy perspective.

4.2. Recursive clustering approach

The recursive clustering approach employs two stages of clustering process. After the deployment of sensor nodes, the distance between the nodes is computed using Euclidean distance. Based on the distance, “k” number of clusters are formed which results in the first stage of clusters. Since the clustering process is modeled as recursive process further the “k” number of clusters is divided in “j” number of clusters based on the distance and interval between the nodes which leads to the second stage of clusters. A typical process of this two-stage clustering is pictorially represented as shown in Figure 3. After recursive clustering process, CH is elected based on energy levels and employing round robin scheduling algorithm. Based on the computations, the node with minimum turnaround time and high energy is elected as the CH among the nodes in the cluster.

Each node senses the data for every two rounds. After the completion of two rounds, turnaround time is calculated. The node having the minimum turnaround time is elected as the cluster head among the nodes in the cluster. The sensed data from each node is sent to the cluster head. In the cluster head, data is aggregated and sent to the base station by the multi-hop routing. The aggregated data in a cluster head leads to less transmission data, decrease in overheads and decrease in energy consumption.

4.3. Performance evaluation of EERC

The performance of our EERC has been evaluated against the conventional LEACH clustering approach under three scenarios through simulation. In scenario 1, the number of sensor node deployed is 100 and in order to test the scalability the scenario 2 and scenario 3 were considered. In scenario 2, 250 sensor nodes and in scenario 3, 500 sensor nodes have been considered.

From the results obtained for scenario 1, our EERC approach shows performance improvement when compared to the classic LEACH protocol. For 100 nodes, there is 23.85% increase in lifetime, 0.287% decrease in energy consumption, 2.522% decrease in delay, 1.497% increase in transmission time, 1.8% increase in goodput and 0.56% decrease in overhead. In scenario 2, EERC shows performance improvement of 12.58% increase in lifetime, 0.402% decrease in energy consumption, 9.815% decrease in delay, 9.289% increase in transmission time, 0.524% increase in goodput and 0.554% decrease in overhead. In scenario 3, EERC exhibits performance improvement of 11.03% increase in lifetime, 0.619% decrease in energy consumption, 5.735% decrease in delay, 9.289% increase in transmission time, 0.524% increase in goodput and 0.554% decrease in overhead throughput.

Thus the recursive clustering technique gives considerable improvement across various performance factors, sustaining the equilibrium of the entire network.

5.1. Similarity measure in sensor data

Similarity Measure is the metric that is employed in this approach for clustering the sensor nodes from a temporal and spatial perspective. The sensor nodes of the same neighborhood produce similar data. Similarly, the data generated from the same sensor node may exhibit similarity to considerable extend except exceptional scenarios of an application. Also, the data that is generated from the same sensor node on successive timeslots in the period of observation may reveal similarity. The redundancy of the data generation and aggregation is effectively controlled through this technique which considerably contributes to the energy consumption in sensor networks.

The component of similarity measure amidst the data sensed from sensor nodes opens the door to devise an effective sleep schedule and save energy. This idea is capitalized in the proposed adaptive distributed clustering algorithm (ADCA).

5.2. Phases in adaptive distributed clustering algorithm

It employs two major phases: a cluster formation phase and an adaptive sleep duty cycle phase. In the cluster formation phase, the data generation rate and the similarity between data series are analyzed by the sink. Based on estimation, the nodes are grouped into various clusters. In each cluster, the cluster heads are selected based on the connectivity and residual energy.

In practical scenarios, the clusters may not be in equal size. Based on the similarity measure of the time series, the clustering is done in this approach. By using the similarity measure, the degree of spatial correlation can be calculated. Generally, for two locations with high spatial correlation, their corresponding time series are associated with a high similarity measure. Hence, in a very smooth sub-region, the observed measure has only small changes within the sub-region. In other words, the difference between the observations at any two locations within the sub-region may be very small and hence negligible.

Therefore, without compromising the observation reliability, the working sensor nodes within this sub-region could be sparse. On the other hand, the working sensor nodes should be dense in a fast changing sub-region. The spatial sampling rate has to match the spatial variation of the observed physical incident by setting an appropriate similarity measure threshold value. Hence, the similarity measure threshold value includes a degree of independency. This value can be tuned to balance the trade-off between reliability and energy consumption.

In the sleep duty cycle phase, the data generation rates of cluster members are compared with a minimum threshold level. The nodes which have rates lower than the threshold level are cumulatively allotted a sleep duty cycle for a predefined period. The sleep/wakeup schedule is informed to every sensor node. The scheduling is done on a fair and distributed manner to regulate energy consumption.

Every cluster head collects the data from its members and checks for the similarity in the received data. If it encounters a significant level of change, it reports to the sink along with the data. The sink then performs reclustering or rescheduling of sleep duty cycle, if necessary. Thus, a part of the workload of the sink in periodical checking of the nodes is shared by the cluster heads.

The data values of two sensor nodes n_i and n_j are said to be similar, if

where mt_i and mt_j are the magnitudes of the values of n_i and n_j

where D_ij is the distance between n_i and n_j and D_Th is the distance threshold.

where R_i and R_j are the sending rates of n_i and n_j, respectively.

Sending rates are calculated in Eqs. (12) and (13).

here, NP_i is the number of packets sent by sensor node i in a time period T.

δ_ij is the absolute difference of sending rates of n_i and n_j

δ_min is the minimum threshold value for δ_R.

The two nodes can be represented as points in three dimensions. Node i has a set of coordinates (mt_i, D_i and R_i) and Node j has coordinates (mt_j, D_j and R_j).Therefore the Similarity Distance between the nodes n_i and n_j is given by the Eq. (14).

where, x_i1 = mt_i, x_i2 = D_i, x_i3 = R_i and x_j1 = mt_j, x_j2 = D_j, x_j3 = R_j.

Here, “n” refers to the number of similarity metrics.

5.3. Cluster formation

In our proposed algorithm, the clustering problem is represented as a clique-covering problem. A graph G is created such that each sensor node is a vertex in the graph. An edge (u,v) between nodes u and v is drawn if SM (u,v) > SM_Th.

A cluster is observed as a clique in this problem. A greedy algorithm is used to heuristically find the cliques. Until all vertices are covered, the search starts from the vertex with the largest node degree. The output of this algorithm is a set of cliques that cover all vertices.

5.4. Performance evaluation of ADCA

The performance of the proposed ADCA algorithm has been compared against a contemporary clustering algorithm named energy-efficient distributed clustering (EEDC) algorithm [10]. Number of sensor nodes has been varied from 20 to 100 in a simulation area of 500 × 500 m². The results obtained show the performance improvement gained by ADCA with respect to EEDC in terms of energy consumption (25%), delay (18%) and delivery ratio (20%) from the mean measurements of multiple runs.

Thus the effective sleep duty cycle considerably reduces the energy consumption in wireless sensor networks ensuring that the overhead and delay are not increased under such scenarios.