Abstract: To propose a Reliable, Energy Efficient, Fault Tolerant (REEFT) clustering algorithm for aggregating sensor measurements in Wireless Sensor Network (WSN). It is a hierarchical algorithm in which energy efficiency is achieved by constructing static clusters with reliable cluster head based on distance. Lifetime of WSN is improved through solving the important issues in WSN, which are distribution of clusters, optimal number of clusters and number of nodes in a cluster and optimal time duration of clustering cycle. Also the algorithm include fault tolerance feature to tolerate the Cluster Head (CH) failure and improve the packet delivery ratio. The algorithm was tested using simulations and its performance improvements were analyzed.
INTRODUCTION
Wireless Sensor Network (WSN) is a network consisting of a large number of nodes equipped with the devices for sensing, processing and wireless transmission. These devices organize themselves into Ad hoc networks having a centralized entity for the entire network called base station or sink. The sensor elements in the nodes senses different types of occurrences (e.g., temperature, magnetism, sound, light) from the surrounding environments and send the data to the Base Station (BS) through which it is connected to outside world. However, acquiring data from the deployment area of sensors is challenging due to multiple issues associated with a WSN. The major issue is the limited energy of sensor nodes which has huge impacts on the life-cycle of the entire network. Processing and transmission of data in WSN, consumes energy but more energy is spent for data transmission compared to processing. Though a wide variety of techniques have been proposed for efficiently managing the energy consumption, clustering is one of the key techniques to reduce the power consumption and prolong the lifetime of the WSN.
Clustering of sensor nodes reduces the amount of communications in the network by reducing the number of nodes taking part in transmission so the size of the routing table and also reducing the number of redundant data and control packets (Chang and Ju, 2012). Thus the fast, reliable and efficient clustering algorithm must support the scalability and dynamic topology. The algorithm must able to discover the clusters with minimum domain knowledge and deal with noise and outliers (Yu and Chong, 2005). Efficient clustering mechanism can simplify the design and overcome the challenges and issues of WSN. The goal of the clustering process is forming optimum number of tight, complete and reliable clusters. The clustering algorithm must converge fast so that the other functions like routing the information in WSN should not be delayed. The energy efficient clustering algorithm should exchange minimum control messages to elect cluster head and form distributed clusters of more or less equal size (Mitrokotsa and Douligeris, 2009).
To coordinate the sensing, processing and communication process of nodes within each cluster a node is elected as a leader called as Cluster Head (CH). The data sensed by the nodes will be aggregated by the CH and sent to the BS. Energy consumption can be balanced by rotating the leadership among the nodes and re-election of CH depends on energy level, mobility and connectivity etc. The clustering mechanism must efficiently solve the problems of heterogeneity, deciding the frequency of CH rotation and maintenance of clusters depends on the node and network constraints. Clustering in WSNs faces several deployment challenges such as ensuring connectivity, bandwidth and data rate, occurrence of faults and node duty cycle. Sensor nodes and links in WSN are fault prone due to the energy, hardware constraints, security issue and wireless link challenges (Liu et al., 2009). Therefore it is necessary to incorporate fault tolerance in WSN to improve the reliability (Paradis and Han, 2007). Incorporating fault tolerance is simpler in cluster based architecture than flat WSN.
RELATED WORKS
The hierarchical cluster-based topology is suitable for sensor network to meet out the scalability issue and energy efficiency by reducing the data redundancy and there by prolong network lifetime. The objectives of a clustering algorithm is providing a good distribution of clusters to achieve load balancing with minimum amount of communication between nodes in order to reduce the energy consumption and latency. The clusters can also improve the system capacity and reduce the delay. It is appreciated that if the algorithm is distributed and so synchronization is not required to form the clusters (Younis et al., 2006). In general clustering can be classified in two types based on its approach, in the first approach initially cluster head is selected randomly followed by grouping of neighbour nodes. In the second approach, the area of the network is divided into regular or irregular polygons followed by selecting a most probable node as a CH. The selected CH performs aggregation process on the received data from the nodes within the clusters and then sends it to the BS. On performing aggregation function by cluster-head for longer time, a significant amount of CH energy wasted and it will die sooner than any other nodes. This situation leads to re-clustering which again cause energy consumption (Ji et al., 2012) which would be avoided. Clustering algorithms in various contexts proposed in the existing literatures, forms the clusters either in distributed or centralized manner to achieve the above objectives with the goal of maximizing the lifetime of sensor network. Designing WSN with optimal cluster size and optimal assignment of nodes to cluster heads by Baccour et al. (2012) assuming number and position of CH are priori known and it is not always possible in dynamic nature of sensor network.
Depending on the application, spatial distribution and structure of clusters, the clustering algorithms can be classified as follows:
| • | Exclusive Clustering in which the nodes are grouped into disjoint cluster, i.e., non-overlapping the clusters. Area in which the sensors placed is partitioned into smaller area of rectangle, square or (Buttyan and Schaffer, 2010) or polygons (Voronoi cells) and nodes within the cells establish link to form clusters. Example is K-means clustering |
| • | Overlapping Clustering, in which each node may belong to two or more clusters with different degrees of membership. It uses fuzzy sets and each node will be associated to an appropriate membership value (Hesong and Jie, 2005) |
| • | Hierarchical Agglomerative Clustering (HAC) is based on the union between the two or more nearest clusters. A distributed HAC (DHAC) method is proposed in Taruna et al. (2011) for distributed environments by clustering the nodes with in single hop. Probabilistic Clustering use a completely probabilistic approach to maximize the connectivity and density functions. This types of algorithm converges quickly and produce balanced clusters (Saeidmanesh et al., 2009) and its disadvantages are analysed by Kim et al. (2008) |
LEACH is the earliest protocol in which the CH is randomly selected and it may not be spatially distributed and costs a higher communication overhead. The periodic rotation or re-election of CH needs extra energy to rebuild clusters. Improvement of various aspects of LEACH carried by many researchers in which instead of randomly selecting the CH, the node who have more energy or depends on position and connectivity have the stronger possibility for becoming CH (Kuhn et al., 2006). Wireless Sensor Network is prone to failure due to unreliable nodes and wireless medium, unattended deployment in the inhospitable environment. Failures in higher level of hierarchy e.g., cluster-head cause more damage to the system because the whole cluster becomes inaccessible. Hence efficient clustering mechanism is required to tolerate the faults and recover sensors from a failed cluster is proposed in Ozdemir and Xiao (2011). The malfunction or compromised node may send corrupted data to CH which will negatively affect the correctness of the data aggregation results and thereby wasting the resources of the network. So the CH must able to detect the faulty data (Chiasserini et al., 2006) and exclude it from the aggregation process or correct faulty data and carry over the aggregation. The existing works able to detect certain types of faults using statistical models, rank based or artificial intelligent techniques and improves the detection accuracy and false alarm rate.
CLUSTERING USING DISTANCE MEASURES
The hierarchical clustering process, groups the sensor nodes deployed in a network based on some similarity aspects and cluster head for each cluster is elected either centrally or distributed. Each cluster there by efficiently coordinated, periodically send their observations or respond the query routed to the cluster. Formally the clusters belongs to hierarchical architecture represented as a set of clusters:
C = {C1, C2, ..., CN}
of S, such that:
and:
The two main types of measures used to estimate the relation between the nodes are distance measures and similarity measures. In wireless sensor networks, the distance measure is used to cluster the nodes due to the reason as follows. The energy consumption in a non cluster node consists of the average energy required for data processing and transmitting data to CH. Similarly energy consumption for cluster head nodes consists of energy for data transmission to BS in addition, the energy consumed for data collection and aggregation of data from non cluster head nodes. In the energy dissipation model proposed by Heinzelman et al. (2000) to exchange an L-bit message between the two sensor nodes, the energy consumption can be calculated as:
| (1) |
| (2) |
where, d is the distance between the two sensor nodes, Etx (L, d) is the transmitter energy consumption and Erx (L) is the receiver energy consumption. Eelec is the electronics energy consumption per bit in the transmitter and receiver sensor nodes and εamp is the amplifier energy consumption in transmitter sensor nodes, which can be calculated by:
| (3) |
where, d0 is a threshold value, εfs and εmp are communication energy parameters. From the Eq. 1-3, it is obvious that the data transmission between sensor nodes takes most of the energy consumption in the wireless sensor networks. Taking into account the energy consumption by sensor nodes, the data transmission distance must be reduced and the packets delay should be avoided. Hence, in the proposed model, nodes are clustered based on distance between the nodes and reduction in energy consumption is realized by clustering the nearby nodes.
Let the Euclidean distance between two nodes ni (x1, y1) and nj (x2, y2) is the inter-node distance denoted as:
| (4) |
and 0 = ≤d (ni, nj) = ≤RTx
where, Rtx is the transmission range of the nodes.
To start forming clusters in the proposed algorithm, nodes are grouped if the inter-node Euclidean distance given by Eq. 4 is less than the optimal distance ρ, which is the first level. The second level is to combine a node with a cluster if the maximum of distance between the node and each node in the cluster must be less than the distance ρ. In the third level two clusters can be combined if the distance between each node in a cluster to each node in the other cluster must be less than the optimal distance ρ.
PROPOSED CLUSTERING ALGORITHM
As soon as all the nodes of the network deployed, they must organize themselves into clusters before transmitting the sensed information to BS. In the distance based clustered architecture the nodes transmit data over smaller distance and so the energy spent will be much lesser than the energy required to transmit directly to BS. In order to organize the nodes in to clusters, some of the parameters of the network are assumed as:
| • | WSN consists of densely deployed nodes and these nodes are randomly deployed |
| • | The nodes and BS are stationary and the locations of the nodes are known to the BS |
| • | Initially battery power of all nodes will be maximum and equal. Energy spent for transmission is much larger and it is negligible for sensing |
| • | In proposed model the grouping is carried in BS and cluster-heads are elected in distributive manner |
The proposed REEFT algorithm operates in three phases, which are grouping phase, cluster head selection phase and data aggregation phase.
In the grouping phase the network is organized into clusters, executed in 3 steps, which are:
| Step 1: | BS initializes all nodes in the network |
| Step 2: | BS executes the hierarchical grouping algorithm and sends the grouping information to all nodes |
| Step 3: | Nodes self organize and establish communication links among their group members |
Grouping of nodes-phase I: This section discusses the proposed approach for grouping of the randomly deployed nodes in to clusters, based on the inter-node distance. The nodes with inter-node distance lesser than the optimal distance ρ are grouped into one cluster using this algorithm. Depends on the node density of WSN, ρ can be varied to keep the no of nodes per cluster (m) and so the number of clusters (k) is optimum. In a random deployment it may be possible that large number of nodes placed within small distance. In this case the size of the cluster depends on the number of nodes in the clusters, may not same and some of the clusters may have larger number of nodes in size) than other clusters. This situation leads to formation clusters of variable size and overload the cluster head of high density clusters. The traffic generated by these clusters will make the network unbalanced and it becomes a hindrance for the routing. The energy consumed in intra-cluster processing varies proportionally to the number of nodes within the cluster. In a densely deployed WSN, ρ can be decreased to limit the m which in turn increases k. In sparsely deployed WSN, ρ can increased to have m optimal, which in turn decreases the k. In the proposed algorithm the maximum number of nodes in a cluster is restricted to m and its value is depends on the data rate and available bandwidth. Thus the distance between the nodes and cluster size are the two parameters used as termination criteria for the algorithm and it forms the distributed and traffic balanced clusters.
Let N be the number of nodes in the field and K be the number of nodes in a cluster, then the Euclidean distance between all pairs nodes can be computed by BS and grouping in REEFT algorithm is performed as follows:
| Step 1: | Begin with each node in the WSN is considered as distinct clusters having level L(0) = 0 and sequence number s = 0 and indexed by {C1, C2, ... CN}. For the ith cluster, let Ki denote the number of nodes in the cluster and initially Ki = 1 for i = 1, 2, ..., N and Ci = {n1, n2, ... nK} where, n represents nodes |
| Step 2: | Find the most nearby pair of clusters with the least distance measure which is less than ρ in the current clustering, say pair (Cq), (Cr), according to d(Cq, Cr) = min [d(Ci, Cj)<ρ, where the minimum is over all pairs of clusters in the current clustering |
| Step 3: | Increment the sequence number: s = s +1. Merge clusters (Cq) and (Cr) into a single cluster to form the next clustering s. Set the level of this clustering to L(s) = d(Cq, Cr). Update the number of nodes count of the new cluster Ks+1 is incremented to Kq +Kr |
| Step 4: | Update the proximity matrix D, by deleting the rows and columns corresponding to clusters (Cq) and (Cr) and adding a row and column corresponding to the newly formed cluster. The proximity between the new cluster, denoted (Cq, Cr) and old cluster (Cp) is defined in this way: d(Cp, (Cq, Cr) = min d(Cp, Cq), d(Cp, Cr) and if d(Cp, (Cq, Cr)<ρ and Ks+1<m, then go to step 2 |
| Step 5: | If all objects are in any one of the cluster stop, else go to step 2 and repeat the steps 2, 3 and 4, else stop |
Cluster head election-phase II: Cluster head election algorithm for resource constrained and fault prone WSN should demand low communication overhead, low complexity in terms of time and messages. On the termination of the algorithm ensures exactly one cluster head at a time and non cluster node must know its CH. By rotating the cluster-head randomly, energy consumption is expected to be uniformly distributed. The re-election of new CH selection mechanism must be executed after the crash failure of existing CH in order to extend the lifetime of the cluster. The algorithms which elect the CH randomly must search the fittest nodes among the entire network would increase the cluster setup time and energy as a function of number of nodes in the network, whereas in the proposed algorithm a node within the cluster is elected as CH which tremendously decreases the time and energy and improve the scalability. The important features added to the REEFT algorithm in order to improve its performance are minimizing the time and energy costs and essential parameters to evaluate the fitness of nodes are explained in the following paragraphs.
One of the features is that the REEFT algorithm needs comparatively a lesser number of messages between the nodes to elect the CH since grouping is controlled by the base station and the CH is elected among the nodes within the group through localized co-ordination. The second feature is the reliable cluster head selection in which the nodes belongs to one of the group use initial energy of the nodes and network topology features of number of neighbour nodes (Di) and link quality (Qi) to select the CH. Similarly the residual energy, neighbour nodes and link quality are the metrics used for rotating the CH. Each node can find their neighbour nodes using Hello message containing temporary Node-id (ni), Cluster-id (Ci) and sequence number with a time to live value of one. Link quality indicator is used to analyze the reliability of the radio channel and the most significant factors leads to link unreliability typically in WSN are noise and interferences. Link quality estimation in WSNs is a prime factor used for performing several mechanisms and network protocols. For an instance, routing protocols rely on link quality estimation to improve the throughput. Link quality estimation also plays a crucial role for topology control mechanisms to maintain the stability of high quality links for aggregation (Yang and Sikdar, 2007). Passive link monitoring and measuring technique is the most suitable for WSN due to its limited resources. In the proposed algorithm, a link between two nodes can be analyzed based on the hello and ACK packets reception ratio.
| Table 1: | Notations used in cluster head selection |
For example if a node is receiving a packet first time itself without error and retransmission then the link quality can be maximum. The nodes at the centre of a cluster obviously have larger LQI and number of neighbours and thus it has more probability to become CH many times and died earlier than the nodes at the edges. A parameter to count the number of times it acted as CH is used to distribute the leadership equally to all fitted nodes. The fitness variables and their notations used to are listed in Table 1.
When the measurement of the topological parameters Di and Qi,j completed by the nodes, the reliability parameter LQI and fitness parameter W can be computed using the Eq. 5 and 6, respectively:
| (5) |
| (6) |
where, the initial value of Fi is 1 and each time a node become CH it incremented by 1. Emax is the energy with which the node started and Eini is the energy at the beginning of each CH cycle. The temporary node-id of each node is updated as defined in the Eq. 7:
| (7) |
where, Disti is the distance between node Ni and CH. The node with the highest node-id (Ni) is elected as the CH and it broadcast the message to all other nodes in the cluster. Deciding the time duration of CH cycle of a node to act as cluster head, is always a difficult problem since a long duration CH cycle consumes large energy and short duration CH cycle increase the overhead due to frequent CH election. The optimal duration of CH cycle is decided based on the residual energy of the CH. The Eq. 8 defines the energy spent by a CH node during a round of data aggregation Ech which includes the energy spent to receive data packets sent by the non cluster nodes, energy cost for computing aggregation (Eagg) and energy required to transmit the aggregated data to BS.
| (8) |
where, Lci is the length of data packets sent by non cluster nodes. ETX (L, dBS) and energy spent by non cluster nodes (Enc) can be computed using Eq. 1. The cluster head cycle is energy bounded and it is dynamically rotated when the energy of the CH is decreased to residual energy Eres. The lifetime of a cluster head is decided according to its initial energy and residual energy and Eres can be set as 50% of the initial energy. In REEFT, Eres is used to withdraw its leadership in order to continue its sensing operation and extend the lifetime of the node and so as the cluster. The number of rounds R over that a node can act as a cluster head is depends on initial energy and can be found from the relation expressed in the Eq. 9 and 10:
| (9) |
which gives as:
| (10) |
Data aggregation-phase III: When a node is elected as a CH and it broadcast the message to all nodes within the cluster. Then the non CH nodes send their sensed information to the CH in the data aggregation phase. To avoid the collision at CH, it establishes a TDMA traffic pattern and distributes time slots between cluster members. At the end of each round, CH aggregates the data and sends it to the BS. In the proposed frame work fault tolerance is achieved in straight forward manner and it is the third feature of the REEFT algorithm. In each cluster the fitness parameter calculation update the node-id and a candidate list consist of nodes having larger node-id excluding current CH node-id is maintained. When a CH fails, simply a new node having highest node-id is elected as CH and recovers the cluster from the failure by sending it own data to BS for the current round. It broadcast the message and the cluster members send their data to the new CH. The Fig. 1 explains the three different phases of the REEFT algorithm. The deployed nodes are grouped based on the distance is shown in Fig. 1a, cluster head selection based on fitness parameter in Fig. 1b and few candidate nodes in a cluster in Fig. 1c.
SIMULATION RESULTS AND DISCUSSION
The effectiveness of the proposed algorithm is briefly demonstrated in section. The simulation results are implemented using the simulator ns2. Table 2 shows the network parameters and communication energy parameters used in the simulation. The network consists of randomly deployed 100 stable nodes and fixed base station.
The clusters are formed by grouping based on distance and electing cluster head based on fitness factor. Two energy efficient metrics of time versus number of nodes alive and average remaining energy and reliability metric of data delivery ratio are used for analyzing and evaluating the proposed algorithm. The results are compared with performance of LEACH algorithm and the proposed algorithm shows a definite amount of performance improvement which is shown in Fig. 2a-c.
The performance improvement can be achieved by solving some of the issues in LEACH protocol, which does not ensure the optimal number and distribution of cluster heads since the CH election is random.
| Fig. 1(a-c): | (a) Cluster architecture, (b) Cluster head election and (c) Candidate nodes in the clusters |
| Fig. 2(a-c): | Performance of REEFT algorithm (a) No. of nodes alive as a function of time (b) Average remaining energy as a function of time and (c) Packet delivery ratio as a function of time |
| Table 2: | Description of network simulation parameters |
So it is possible that more number of nodes can be elected as CHs from one part of the network. But in REEFT nodes are grouped based on the optimal distance and optimal number of nodes per cluster which ensures distributed and balanced clusters and so more number of nodes are alive in each round than LEACH as given in Fig. 2a. REEFT is a static clustering technique which minimizes the number of cluster head selection by using a threshold on number of rounds based on residual energy. It is already proved in T-LEACH (Hong et al., 2009) that by reducing the amount of cluster head selection and replacement cost, the lifetime of the entire networks can be extended. Before the CH energy reaches to minimum CH is shifted to next candidate node and so the average energy dissipation in each round is less compared with LEACH as shown in Fig. 2b. Thus all the nodes in a cluster started with same energy dissipate uniformly and die almost at the same time in REEFT. The data delivery ratio is improved using REEFT due to the provision of fault tolerance through fault recovery from CH fault. During the aggregation phase, fault is injected to the CH and fault tolerant capability of the algorithm is tested using the simulation. When a CH fails, a node on the top of the candidate list automatically announces itself as CH and sent its current data packet to BS. Also it recovers the cluster by aggregating the data from its cluster members. Data delivery ratio is given the ratio of data delivered to data attempted over fixed time period. In this algorithm each cluster sends data packet to BS for every round even if some of the cluster heads become faulty. The results of the simulation are given in Fig. 2c. shows the improvement in data delivered to BS with respect to time.
CONCLUSION
An energy efficient hierarchical clustering algorithm REEFT is proposed in this paper. The algorithm first partitioned the node into groups and locally selects CH based on fitness parameters to produce distributed and reliable clusters. The overhead incurred in CH election and CH rotation is less compared to LEACH, so the algorithm demands that less energy complexity which is required for a resource constrained WSN. The clusters are flexible in terms cluster size and can be chosen depends on node density and so the WSN application. The algorithm tolerates CH failure and extent the lifetime of the WSN. The algorithm was simulated and the results show the improvements in performance of WSN. REEFT produces clusters of single hop homogeneous clusters. The future works may be to improve energy efficiency still by constructing multi hop clusters with heterogeneous sensor nodes may be investigated. Also investigate a dynamic clustering model to include new nodes to the cluster.