Over the past decade, there has been significant rise in the interests for the potential utilization of wireless sensor networks(WSNs) in an extensive variety of applications and it has turned into a widely researched area. Based on the structure of WSN systems routing can be done as flat or hierarchical. Due to variety of advantages, clustering has became an important research area for routing in WSNs. In this paper, we critically analyse currently proposed clustering protocols for Wireless Sensor Networks. We will concisely discuss about the operations of these protocols with their advantages and disadvantages, and additionally contrast these diverse approaches according to several significant metrics.

Keywords – Clustering algorithms, Wireless Sensor Networks.


A wireless sensor network is set of sensors which are deployed in a sensor field to monitor the characteristics the environment, collect data regarding them and processor that data related to the phenomenon. The sensors are small pro- cessing units with restricted assets: constrained battery power, low memory, little computation power, low information rates, low data transfer and so on. These sensors can be deployed in places which are not accessible by humans and so wired sensors are of no use in such cases. Even though they have little memory, small power, less data rates but when they are deployed in large numbers they can provide us with huge computational abilities. The utilization of the WSN will give productive and costs compelling answers for many issues. However, we have to take into account the constraints related to the sensors. Routing is a very important aspect for WSNs. WSN are very much different from the ad hoc networks.

Routing in WSN is more challenging as compared to ad hoc networks. Firstly, because of the constraints in power, memory, and data rates. Secondly, you cannot design a global addressing scheme like Internet Protocol (IP). The issue with having a global addressing scheme is it will increase the computational and memory overhead every time the address of the nodes is updated. Thirdly, data redundancy has to be as less as possible because of memory constraints. Retransmission of data is also an issue as it curtails the energy of the nodes. Fourthly, sensors nodes have bounded latency which calls for the need for better clustering between the nodes. This means that we should have an algorithm for faster transmission of data. Routing protocols in WSN are divided into two categories: flat routing and hierarchical routing. In a flat routing, all nodes have the same tasks and have the same functionalities. Data transmission is performed by hopping between the nodes usually in the form of flooding. This kind of routing is effective for small networks like the one in which all the nodes are sensing and transmitting the data to the base station. In a large WSN network this is not the case and therefore hierarchical topology is used. In such a topology different nodes perform different tasks and therefore they are grouped into a cluster.

In a clustered WSN we can identify three main elements: Base station (BS), Cluster Head (CH), Sensor nodes (SN). The Sensor nodes are the ones which carry out the task of sensing the environment and collect the data. They mainly detect any events in the surrounding and if needed do little data processing and finally transmit the data to the Cluster Head. But the data sensing and processing takes a lot of power and therefore there are power constraints and efficient algorithms that can optimize the power consumption have to be designed. The Base station performs the most important task of processing the data it has received and then providing it to the end user. It is generally fixed at a point and is far away from the sensor network. The Cluster Head acts as the link between SN and BS. The tasks of the CH includes that of aggregating the data from the sensor nodes before sending it to the BS. So CH acts as the sink for the SN and BS acts as sink for the BS. Even if any communication has to be done by the BS it is through the CHs of the clusters.

There are many ways to classify the clusters of which the two popular classification are (a) heterogeneous and ho- mogenous clusters and (b) static and dynamic clusters. In heterogeneous sensor networks there are set of sensors which have higher processing capabilities and complex hardware. This sensor nodes generally act as the cluster heads. They do the important task of processing the data received from other nodes. The other type of sensors are those which sense the desired attributes of the environment. In homogeneous networks all the nodes are identical in terms of processing capabilities and hardware. Static clusters are formed during the deployment of the network itself. The attributes of each cluster like the size of the cluster, the CH and, the number of participating nodes is static. This kind of clustering is helpful when the sensor filed is predetermined, and the targets of the sensors are not in motion and it is easy to replace the sensors in the network. Dynamic networks make better use of the sensors. They are generally used when the sensors are homogeneous but can be used for heterogeneous networks too. There is no pre allocation of the CH as it is was the case in static network. The formation of a cluster can be triggered by a special message and the attributes of the clusters are variable. So size of the clusters can be modified and it gives the network runtime capabilities for cluster size variation, task distribution etc. However a CH election method, cluster formation method and cluster maintenance methods have to be designed.

Benefits and Objectives of clustering

More Scalability: Clustering can localize the route set up in the clusters and help to reduce the size of routing table stored in each sensor node. Scalability in this context implies improved data aggregation, load balancing between the sensor nodes, and efficient utilization of the resources.Data Aggregation: Data aggregation is any process in which information is gathered form the nodes and expressed in a summary form. This helps to reduce the data redundancies. The most popular data aggre- gation/fusion method is clustering data aggregation.Less load: Due to data aggregation there is less load on the BS in terms of processing and receiving the data. If data is aggregated hierarchically then a lot of redundant data is removed and the load on the nodes above in the hierarchy is reduced.Less Energy: Due to clustering and data aggregation in clusters a lot of transmission and reception energy is saved and this helps to increase the lifetime of the network.More Robustness: The cluster head in the clusters can be rotated based on the clustering algorithms and this significantly increases the power efficiency of the network and thus makes it robust.Latency Reduction: When a WSN is divided into clus- ters, only CHs perform the task of data transmissions out of the cluster. The mode of data transmissions only out of the cluster helps avoiding collisions between the nodes. Accordingly latency is reduced.Load Balancing: Load balancing is an essential con- sideration aiming at prolonging the network lifetime in WSNs. Due to the clustering load balancing is effectively done.Maximizing of the Network Lifetime: Network lifetime is an inevitable consideration in WSNs, because sensor nodes are constrained in power supply, processing capability and transmission bandwidth, especially for applications of harsh environments.Fault-Tolerance: Due to the applicability of WSNs in a good many dynamic scenarios, sensor nodes may suffer from energy depletion, transmission errors, hardware malfunction, malicious attacks and so on. This constraints lead to fault which are reduced if better clustering algorithms are used.

Implementation Aspects

In the implementation of Wireless Sensor Networks, clus- tering algorithms are important to overcome some of the con- straints. There are various aspects that need to be considered before the selection of a clustering algorithm for a particular implementation.
Clustering Cost: Clustering is implemented to de- crease the energy consumption in Wireless Sensor Networks. However, clustering itself requires trans- mission of cluster formation data and processing tasks for the creation and maintenance of clusters. This must be considered while implementing a clustering algorithm.Selection of cluster heads and clusters: The type of application determines the characteristics of clusters such as area of the cluster, number of nodes in a cluster, level of cluster. The cluster heads may be chosen on the basis of type of cluster, energy level, randomly or based on any other criteria.Load balancing: Clustering is used to avoid excessive and unnecessary energy usage in Wireless Sensor Networks. A cluster head is chosen to transmit the cluster data to the base station. To avoid putting a strain on the resources of a single node in the cluster acting as the cluster head, clustering algorithms should be designed to balance the load among all nodes in a cluster. This may be done by implementation of a cluster head rotation scheme.Real-time operation: Time determinism of the data being tracked by the Wireless Sensor Network is an extremely important factor in choosing the clustering design. For applications with high real-time require- ment, clustering algorithm with the least amount of delay must be selected.Synchronization: In order to overcome the limitation of low energy capacity, Wireless Sensor Networks make use of slotted transmission algorithms. These re- quire time synchronization among the network nodes. Synchronization and scheduling are important factors during the formation of clusters in order to increase network lifetime and performance.Data Aggregation: In Wireless Sensor Networks with dense deployment, there are multiple nodes collecting similar information. Sending redundant information uses excess energy. Processing requires less energy than communication. Hence, processing is done within the network to reduce energy consumption. Cluster heads may act as in-network base stations processing the data before it is sent further.Repair Mechanisms: There may be link breakages and node deaths in Wireless Sensor Networks. Based on the criticality of the application, a clustering approach should be chosen which would allow these distur- bances to be accommodated.Quality of Service (QoS): QoS requirements such as packet delivery ratio, delay, throughput are applica- tion dependent and clustering algorithms need to be designed while keeping these parameters in mind.

Characteristics of different Clustering Routing Protocols in WSNs

Comparison of Different Clustering Protocols in WSN


Research into the implementation of Wireless Sensors Net- works has increased manifold in the past few years. Wireless Sensor Networks have a wide range of applications from civilian assistance like in farming to environmental monitoring even of inaccessible areas to military assistance. Different application place different constraints on the network and hence, require different algorithms. In this paper, we have presented the benefits and objectives of clustering in a Wireless Sensor Network, the various aspects to be considered while designing a clustering algorithm. We have given an overview of some of the existing clustering protocols and their advantages and disadvantages. Finally, we have given a comparison of the different protocols based on some important parameters.