. .
Clustering Algorithms





  • To design, develop, and implement an energy efficient wireless sensor network algorithms for grouping the nodes

  • To understand wireless sensor network algorithms for grouping the nodes




Wireless sensor networks (WSNs) may consist of several thousands of homogeneous or heterogeneous sensors that can collect reliable and accurate information in distant and hazardous environments. Wireless Sensor Networks are generally assumed to be energy restrained because sensor nodes operate with small capacity DC source or may be placed such that replacement of its energy source is not possible Most commonly battery is used to supply electricity to the deployed nodes, so it’s important to route the motes to efficiently utilize its power. A basic wireless sensor network requires very little infrastructure. In one such network, nodes can be deployed in an ad hoc fashion. However, the sensor network deployed to obtain data from the environment may require a large number of sensor nodes, depending on the area to be covered. Due to large numbers of nodes the management of network becomes difficult, and complex structure is required.


                              General Overview of Wireless Sensor Networks

                                                        Figure 1:  General Overview of Wireless Sensor Networks


Now you all are aware about the different methods of topology to group the deployed nodes in a network and how data aggregation can takes place between the deployed nodes from the experiments entitled “Wireless Sensor Networks” and “Wireless Sensor Network Data Acquisition, Transmission and Aggregation”.


These sensor nodes are energy constrained and the sensor nodes can perform data aggregation in order to use energy efficiently. The energy required to send data depends on the distance between the nodes and the number of bits which are being transmitted. The energy required for receiving also depends on the number of bits being received. The energy requirement of transmitter and receiver can be defined as in below equations.




Eelec is the energy being dissipated to run the transmitter

Eamp is the energy dissipation of the transmission amplifier

K is the length of the message in bits

d is the distance between transmitter and receiver



Figure 2 : Centralized Network


 When we are using direct transmission between the transmitter and receiver as shown in the above figure the energy required for transmitter amplifier circuit will be equal to that shown in equation (1).
           «math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«msub»«mi»E«/mi»«mrow»«mi»t«/mi»«mi»r«/mi»«mi»a«/mi»«mi»n«/mi»«mi»s«/mi»«mi»m«/mi»«mi»i«/mi»«mi»t«/mi»«mi»t«/mi»«mi»i«/mi»«mi»n«/mi»«mi»g«/mi»«/mrow»«/msub»«mo»§nbsp;«/mo»«mo»=«/mo»«mo»§nbsp;«/mo»«mo»(«/mo»«msub»«mi»E«/mi»«mrow»«mi»e«/mi»«mi»l«/mi»«mi»e«/mi»«mi»c«/mi»«/mrow»«/msub»«mo»§#215;«/mo»«mi»k«/mi»«mo»)«/mo»«mo»+«/mo»«mo»(«/mo»«msub»«mi»E«/mi»«mrow»«mi»a«/mi»«mi»m«/mi»«mi»p«/mi»«/mrow»«/msub»«mo»§#215;«/mo»«mi»k«/mi»«mo»§#215;«/mo»«mo»(«/mo»«mfrac»«mi»d«/mi»«mn»2«/mn»«/mfrac»«msup»«mo»)«/mo»«mn»2«/mn»«/msup»«mo»)«/mo»«mo»§nbsp;«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo».«/mo»«mo»(«/mo»«mn»3«/mn»«mo»)«/mo»«/math»

  Then the energy required for transmitting data from source node to destination node in the multi hope case will be half that of the direct transmission.


  Figure 3: Multihop Network


In many situations, the data collected by many nodes will be same. In such cases, redundant data transmission can be eliminated by forming group of nodes called clusters and by electing one node among the nodes in the cluster to be cluster head. All nodes can send data to the cluster head where the aggregation of data can takes place.
There are two types of clustering techniques. The clustering technique applied in homogeneous sensor networks is called homogeneous clustering schemes, and the clustering technique applied in the heterogeneous sensor networks is referred to as heterogeneous clustering schemes. 
In order to solve all these problems Wendi Rabiner et al. in the paper “Energy-Efficient Communication Protocol for Wireless Micro sensor Networks” proposed an algorithm for energy efficient protocol for cluster head election in a hierarchical network. If we have used fixed node as the cluster head, then it has to collect data from all of its child nodes and has to process the data for all the time period. This leads to faster battery drainage in the fixed cluster head. Even if one cluster head dies, it will affect the working of the network. By choosing dynamic cluster head, this problem can be eliminated. LEACH is an example of clustering protocol for wireless sensor network which consider homogeneous sensor networks where all sensor nodes are designed with the same battery energy. HEED, PEGASIS are some of the other examples of the clustering algorithm.

LEACH stands for Low Energy Adaptive Clustering Hierarchy which is the first protocol of hierarchical routing which proposed data fusion, it is of milestone significance in clustering routing protocol.


All the nodes in a network organize themselves into local cluster, with one node acting as the cluster head. All non-cluster head node transmit their data to the cluster head, while the CH node receive data from all the cluster members or leaf nodes, perform signal processing functions on the data aggregation and transmit data to the remote base station. Therefore, being a cluster head node is much more energy intensive than being a non-cluster head node. Thus, when a cluster head node dies, all the nodes that belong to the cluster lose communication. The problem of LEACH protocol is balance the energy consumption, network energy consumption.


LEACH minimize the communication energy that is dissipated by the cluster heads and the cluster members as much as 8 times when compared with direct transmission and minimum transmission energy routing.



                                                                               Figure 4:   LEACH Protocol


LEACH incorporates randomized rotation of the high-energy cluster-head position such that it rotates among the sensors in order to avoid draining the battery of any one sensor in the network. In this way, the energy load associated with being a cluster-head is evenly distributed among the nodes. Since the cluster-head node knows all the cluster members, it can create a TDMA schedule that tells each node exactly when to transmit its data. In addition, using a TDMA schedule for data transfer prevents intra-cluster collisions. The operation of LEACH is divided into rounds. Each round begins with a set-up phase when the clusters are organized, followed by a steady-state phase where several frames of data are transferred from the nodes to the cluster-head and onto the base station.


In the set-up phase, the clusters are arranged and cluster-heads are chosen. In the first round, each node selects a random number between 0 and 1 and compares it to the threshold T(n) given in (4) and if the number is less than a threshold, the node becomes a cluster head. 


                                                              ( 4 ) 


Where p is the desired percentage of cluster heads,

 r is the current round,

G is the set of nodes that have not been cluster heads in the last 1/p rounds


In each round, selected cluster-heads broadcast an advertisement message to all the nodes in the network, informing their new status. After receiving this message, each of the non-cluster-head nodes can determine to which cluster they belong to based on the strength of the received signal. Then, according to the number of nodes in a given cluster, that cluster’s cluster-head generates a TDMA (Time Division Multiple Access) schedule, and broadcasts a transmission time window to its CHs.


TDMA is a scheme where all concerned earth stations use the same carrier frequency and bandwidth with time sharing, non-overlapping intervals.


In the steady state phase. Nodes in each cluster can begin sensing the information and transmitting sensed information to their own cluster-head throughout the distributed transmission time. The cluster-head node conducts the data fusion, aggregating, compressing and then sending the aggregated data to the base station. Since the BS is usually far from the field, communicating to the base station will consume a lot of the cluster-heads energy. When the designated transmission time is over, the steady state phase finishes and the network retreats into the setup stage and begins an alternate round, starting with choice of new cluster heads.


HEED stands for Hybrid Energy-Efficient Distributed Clustering. ​HEED is one of the most effective cluster-based routing protocols in WSN. HEED has four primary objectives [15]: 


(i) Prolonging network lifetime by distributing energy consumption

(ii) Terminating the clustering process within a constant number of iterations

(iii) Minimizing control overhead (to be linear in the number of nodes)

(iv) Producing well-distributed cluster heads


It is a distributed, energy efficient clustering approach which makes use of two parameters to cluster the network; the sensor residual energy as a primary parameter and IntraCommunication like node degree and node proximity as a secondary parameter [14]. The HEED operation for clustering is divided into three phases; the initialization phase in which the sensors put their probabilities to become CHs, the main processing phase in which the sensors go through many steps to elect the CHs and the finalization phase in which each sensor join the least communication-cost CH or announce itself as a CH . The re-clustering in HEED is triggered dynamically at the beginning of each round which is a predefined period of time; the round in HEED can be in the range of seconds, minutes or even hours depending on the application at hand [14].


The HEED clustering operation is invoked at each node in order to decide if the node will elect to become a cluster head or join a cluster. A cluster head is responsible for two important tasks:

(1) intra-cluster coordination, i.e., coordinating among nodes within its cluster

(2) Inter-cluster communication, i.e., communicating with other cluster heads and/or external observers.



Figure 5:   Intra-cluster and Inter-cluster communication in WSN [Ref: 16]


The cluster range or radius is determined by the transmission power level used for intra-cluster announcements and during clustering. We refer to this as the cluster power level. The cluster power level should be set to one of the lower power levels of a node, to increase spatial reuse, and reserve higher power levels for inter-cluster communication. Selecting cluster heads is based on two parameters: a primary parameter and a secondary one. HEED uses the primary parameter to probabilistically select an initial set of cluster heads, and the secondary parameter to “break ties.” A tie in this context means that a node falls within the “cluster range” of more than one cluster head. The mechanism of breaking ties according to cost also ensures that the probability of having two cluster heads within the same cluster range is minimized, i.e., cluster heads are well-distributed in the network.


The primary parameter depends on the node residual energy. Thus, a node with high residual energy has a higher chance of electing to become a cluster head. The secondary parameter is the intra-cluster “communication cost”. This cost is a function of (i) cluster properties, such as cluster size, and (ii) whether or not variable power levels are permissible for transmission within a cluster, i.e., if each node is allowed to use the minimum power level to reach its cluster head or if all intra-cluster communication must use the same power level. If the power level used for intra-cluster communication is fixed for all nodes, then the cost can be proportional to (i) node degree, if the requirement is to distribute load among cluster heads, or (ii) 1/node degree, if the requirement is to create dense clusters. This means that a node joins the cluster head with minimum degree to distribute cluster head load (possibly at the expense of increased interference and reduced spatial reuse), or joins the one with maximum degree to create dense clusters. We use the terms minimum degree cost and maximum degree cost to denote these cost types.


System PEGASIS [17] is another hierarchical routing protocol which considered as an improvement over LEACH. PEGASIS stands for Power - Efficient GAthering in Sensor Information System. In PEGASIS, The primary idea is having each node to receive from and transmit to adjacent neighbors and then each node will take its turn later to be the chain leader. The nodes in PEGASIS are organized to form a chain either by the sensors themselves using a greedy algorithm starting from the randomly chosen node, usually the farthest nodes from the sink, or by having the sink construct the chain and transmits these information to the rest of sensors. In PEGASIS, the data aggregation is performed at every node on the chain except the end nodes in the chain and the network topology is assumed to be known. PEGASIS [17] performs better than LEACH because it reduces the consumed energy in its phases. In its local gathering stage, the summation of distances among transmitting nodes is less than transmitting to a CH in LEACH. Also the amount of data received by the leader of chain is much less from that in LEACH. Finally, in each round, only there is one node envoys the collected data to the sink node [16]. 






Cite this Simulator:

..... .....

Copyright @ 2017 Under the NME ICT initiative of MHRD

 Powered by AmritaVirtual Lab Collaborative Platform [ Ver 00.10. ]