SCHS: Smart Cluster Head Selection Scheme for Clustering Algorithms in Wireless Sensor Networks ()
1. Introduction
Recently many researchers have shown great interest in wireless sensor networks [1] due to their wide range of application in the field of military surveillance [2], fire detection [3], habitat monitoring [4], industry [5], health monitoring [6] and many more. Wireless sensor networks [1,7] are composed of large number of randomly deployed sensor nodes. Sensor nodes are deployed within concerned area or very next to it. Wireless sensor net-works have at least one base station that works as a gateway between the sensor network and outside world. Sensor nodes sense the phenomenon and send the data to base station via single or multi-hop communication. Users access the data stored at base station.
Sensor nodes have limited battery power, memory and processing capabilities. So lifetime of a wireless sensor network is limited by on-board energy of sensor nodes. Due to harsh deployed area, replacement or recharge of battery is not feasible. Lack of infrastructure and large number of sensor nodes causes huge flow of message transfer through the network. As most of the energy is consumed during communication [7], currently different clustering algorithms [8,9] are proposed for wireless sensor networks to use energy of nodes efficiently.
Clustering algorithms are used in wireless sensor networks to reduce energy consumption. Operation of clustering algorithm is executed in rounds and each round is composed of two phases: setup phase and steady phase. Nodes are organized in independent sets or clusters. At least one cluster head is selected for each cluster. The sensed data is not directly sent to the base station but via respective cluster heads. Cluster head collects data of sensor nodes that belongs to that cluster. Clustering algorithms apply data aggregation techniques [8,16] which reduce the collected data at cluster head in the form of significant information. Cluster heads then send the aggregated data to base station.
Cluster head selection plays significant role for energy efficiency of clustering algorithms. Intra-cluster communication distance depends upon position of selected cluster head in a cluster and intra-cluster energy consumption depends upon intra-cluster communication distance. Clusters with high intra-cluster communication distance will consume more energy than other clusters. In this paper, a simple and efficient smart cluster head selection (SCHS) scheme is proposed that reduces the intra-cluster communication distance. The simulation results show that SCHS has significant improvement over LEACH [10] in terms of lifetime of network and data units gathered at base station.
The rest of paper is organized as follows. Section 2 describes the clustering schemes proposed in literature. Section 3 details network model and Section 4 discusses the significance of intra-cluster communication and the proposed solution to reduce it. Simulation results are shown in Section 5. Section 6 concludes the paper and scope of future work.
2. Related Review
LEACH (Low Energy Adaptive Cluster Hierarchy) [10] is fully distributed algorithm. In set-up phase cluster heads selection, cluster formation and TDMA scheduling are performed. In steady phase, nodes send data to cluster head and cluster head aggregate the data. Aggregated data is send to base station. After a fix round time, reclustering is performed. Role of cluster head is rotated to all the sensor nodes to make the network load balance. LEACH scheme does not guarantee about equal number of cluster heads in each round.
EBUC (Energy-Balanced Unequal Clustering) [11] is a centralized protocol that organize network in unequal clusters and CHs relay data of other CHs via multi-hop routing. PSO is applied at BS to select high energy nodes for CH role and for formation of clusters with unequal nodes. Clusters closer to BS are formed of small size to consume less intra-cluster energy and hence are ready for inter-cluster communication energy consumption. But protocol works only when BS is located outside the interested working area.
ADRP (Adaptive Decentralized Re-clustering Protocol) [12] selects a cluster head and set of next heads for upcoming few rounds based on residual energy of each nodes and average energy of cluster. In the initial phase, nodes send status of their energy and location to base station. Base station partitions the network in clusters and selects a cluster head for each cluster along with a set of next heads. In the cycle phase, cluster head aggregates the data and sends to the base station. In the re-cluster stage, nodes transit to cluster head from set of next heads without any assistance from base station. If the set of next heads is empty, initial phase is executed again.
EAP (Energy-Aware Routing Protocol) [17] provides new parameters for cluster head selection to handle heterogeneous energy of nodes. A node maintains a table of residual energy of neighbouring nodes within cluster range of node to calculate average residual energy of all these nodes. A node having residual energy higher than average residual energy has high probability of cluster head selection.
DEEC (Distributed Energy-Efficient Clustering) [13] has a two-level heterogeneous network. Sensor nodes are categorized in two types: advance nodes and normal nodes. Advanced nodes have higher energy than normal nodes. Initial and residual energy level of nodes is used for cluster head selection. So the high energy nodes are more probabilistic to select as cluster head than low energy nodes. High energy nodes are doing more work while low energy level nodes are doing work of sensing. EEHC (Energy Efficient Heterogeneous Clustering) [14] extended the node heterogeneity to three types: super nodes, advance nodes and normal nodes.
None of the schemes have a view on cluster head selection such that to minimize intra-cluster communication. Work of this paper proposed a simple and efficient cluster head selection scheme that reduce intra-cluster communication and extend lifetime of network.
3. Network Model
In our proposed protocol following network assumptions are considered:
• All sensor nodes are homogenous.
• All nodes are stationary once deployed in the field.
• Nodes are location aware i.e. nodes are equipped with any GPS device or use some method to find location.
• There is single base station located outside the field.
• All nodes have data to send.
• The nodes are considered to die only when their energy is exhausted.
3.1. Energy Model
In Wireless sensor networks, nodes are deployed randomly, i.e. positions of nodes are not pre-engineered. Most of the energy is dissipated during communication in sensor networks as it depends on the distance between the two nodes. Energy dissipation model is shown in Figure 1.
Both sending and receiving process of data communication consumes energy. According to energy model proposed in [7], for sending m-bit data over a distance d, the total energy consumed by a node is given by:
(1)
and hence
(2)
while the energy consumption for receiving that message is given by:
(3)
Figure 1. Radio energy dissipation model.
4. Problem Statement and Proposed Solution
4.1. Problem Statement
4.1.1. Intra-Cluster Distance
Intra-cluster distance and total cluster distance are synonyms. Total cluster distance is the measure of intracluster communication. Total cluster distance is defined as the sum of the distance of all nodes in the cluster to cluster head as in Equation (4).
(4)
where N is the number of nodes in a cluster and Distance (i,CH) is distance of a node to cluster head. Energy efficiency of a cluster depends on the intra-cluster communication. The steady phase of clustering approach is longer than the set-up phase. In steady phase there is intra-cluster communication between nodes to cluster head and long distance inter-cluster communication between cluster heads and base station. Intra-cluster communication phase involves all sensor nodes and hence communication is much higher than inter-cluster communication. So intra-cluster communication consumes most of the energy from the network. Hence clusters with less total cluster distance are considered as more energy efficient.
4.1.2. Effect of Cluster Head Selection on Intra-Cluster Distance
Figure 2 shows a network with 50 nodes deployed randomly and uniformly over a 50 × 50 m2 area. The network is considered having a single cluster. The total cluster distance is calculated for each node considering it as cluster head.
Table 1 shows that clusters having cluster head nodes positioned near the center of cluster have less total cluster distance, while cluster head nodes positioned far from the center of cluster have large total cluster distance. So cluster head selection is an important issue and it affects energy efficiency of clustering approach drastically incase of improper selection. Hence the cluster head selection should be optimized to minimize intra-cluster communication.