A Uniform Clustering Mechanism for Wireless Sensor Networks

Abstract

In wireless sensor networks with dynamic clustering, the cluster heads are usually not selected on the basis of their locations. This causes irregular distribution of cluster heads and highly variable number of nodes in the clusters. Also, some of the clusters are spread over large areas within the network, causing limited spatial correlation between associated sensor nodes. These irregularities in cluster placements and dimensions negatively impact the efficiency of a wireless sensor network. For example, for a cooperative data aggregation, it necessitates variable or large sized packets while the aggregations, based on spatial correlation of sensor nodes, cannot be exploited easily. In this paper, we have developed a Distributed Uniform Clustering Algorithm (DUCA) for cluster based WSN. In DUCA, cluster formation mechanism is based on a virtual-grid system and sensing ranges of nodes that provide even distribution of clusters, homogenized cluster sizes, and reduced energy consumption. Simulation results show that DUCA improves the distribution of cluster heads by more than 2 times and reduces the energy consumption within a range of 15% to 50% as compared to the existing protocols.

1. Introduction

The basic job of a wireless sensor network (WSN) is to sense and collect the physical or quantifiable data from its surroundings and forward it to some central location. The central location may possibly be an isolated system or it could be a part of a globally stretched infrastructure, for example, the Internet of Things (IoT). The IoT, as envisioned, consists of data sensing and collecting objects, attached to communication devices, providing data that can be analysed and used to initiate automated actions. It has been estimated that by 2015 there will be around 25 billion devices wirelessly connected around the globe [1]. This has created a new perception of incorporating WSN as data collecting component of IoT. However, this requires much larger and wide-ranging sensor networks than currently being imagined [2]. Cooperative energy efficient data collection from such network puts new challenges on the system.

In a large scale WSN, usually, the nodes collaborate with each other to collect and forward data in a hierarchal manner. For this purpose, cluster based protocols are commonly employed. In majority of the cluster based protocols, the clusters are formed dynamically and repeatedly to collect the data from multiple sensor nodes. Usually the dynamic cluster based protocols have highly variable-sized clusters which are not formed uniformly, for example, in LEACH [3], HEED [4], EAP [5], and TDEEC [6]. By “cluster size” we mean the number of nodes in a cluster. Due to the irregular placement of sensor nodes and variable sizes of clusters, we need to have variable or large sized packets for data collection and aggregation. On the contrary, it has been shown in the previous research works that due to the limitations and resource constraints of a WSN, its optimal packet size should be small and should have fixed length [7, 8]. These packet sizes can be constrained by homogenizing cluster sizes in a WSN.

In this work our main objective is to develop a uniform cluster formation mechanism for WSNs without consuming extra energy of the network. For this purpose, we have proposed a new solution which can develop homogeneous clusters in terms of number of nodes with reduced variations in the cluster sizes. In our proposed mechanism the even distribution of cluster heads and clusters is achieved by implementing an energy efficient usage of virtual grids in the network. Unlike previously proposed grid-cluster based protocols, in our mechanism a grid is not taken as a cluster rather clusters are formed on the basis of distances of nodes to their nearest cluster heads. The sizes of clusters are further reduced by exploiting the redundant and overlapped sensing ranges, which occur due to the random placements of sensor nodes in the network.

The remaining paper is organized as follows. Section 2 further explains the problems that arise due to the highly variable sized clusters in WSNs. Section 3 gives a brief overview of the methods given in current literature to solve the problem. Section 4 explains the proposed algorithm design and compares it with the existing protocols. Section 5 discusses a heuristic approach that can be used to reduce the cluster sizes by exploiting the sensing ranges of the nodes. In Section 6, a mathematical relationship is presented that finds the optimum number of grids in the network for a given number of sensor nodes. Section 7 evaluates our proposal against centrally controlled based and grid-cluster based protocols using simulations. Finally, Section 8 concludes the paper.

2. Variable Sized Clusters in a Dynamic Cluster Based WSN

In many of the dynamic cluster based protocols like [3–6, 9–11], the location of the CHs is not considered in the CH-selection criteria. As a result, the selected CHs are not uniformly distributed in the region. For example, it can be seen in Figure 1(a) that all of the CHs are formed in the lower right corner of the network area (Figure 1(a) is a snap shot of one of the rounds taken from a simulation of LEACH protocol [3]). This type of nonuniform selection of CHs has created the following side effects on the system.

• (1)

The sizes of clusters, in terms of number of nodes per cluster, are highly variable as shown in Figure 1(b). This results in the requirement of large or variable sized packets for the aggregation of data. On the other hand, due to resource constraints, the optimal packet sizes in WSNs are considered to be small and of fixed length [7, 8, 12].

(2)

There are some clusters in the network which are spread on large regions. This implies that there must be several nodes which have to contact distantly located CHs to forward their data, for example, clusters 1 and 2 in Figure 1(b). Also, the data at the CHs of these clusters must be collected from far off areas of the region. This influences the system in two ways.

• (a)

The distant nodes in large sized clusters need to spend higher energy to transmit the data to their CHs. According to the free space energy consumption relation (see (1)), energy consumed in the transmission of k bit $(E_{TX})$ is dependent majorly on two factors: size of the data packet $(k)$ and the distance between the source and destination $(d)$ . $E_{\text{elec}}$ and $E_{\text{amp}}$ are the energies consumed in electronic circuitry and the amplification power of the node, respectively. These energies are kept constant for a given node type:

$$\begin{array}{cc}& E_{TX}\left(k,d\right)=E_{\text{elec}}\times k+E_{\text{amp}}\times k\times d^{\mathrm{2}}.\end{array}$$

(1)

(b)

Usually in WSNs the sensor nodes placed in close vicinity have spatial correlation. Therefore, CHs after collecting data from these nodes aggregate the data into a single packet. These aggregations are usually based on simple rules of taking average, sum, difference, or maximum of the correlated data. These methods of aggregations are also called “summary based” aggregation. In large sized clusters with sensor nodes placed at far off distances, there is less chance of having good degree of spatial correlation among the data. Therefore, logical and balanced aggregation of data cannot be used easily.

Figure 1

Dynamic cluster based WSN.

3. Related Work

Some solutions have been proposed in the past to overcome the variations in the cluster sizes of WSN. We have divided these mechanisms into two categories:

• (1)

centrally controlled cluster formation protocols;

(2)

grid-cluster based protocols.

3.1. Centrally Controlled Cluster Formation Protocols

In these protocols the clusters are formed dynamically but the process is controlled centrally by the sink. For example, in Base Station Controlled Dynamic Clustering Protocol (BCDCP) [13], at the start of each round, all nodes send their current energy status to the sink. The sink chooses a set of CH candidates based on their energy levels. To get a set of clusters with approximately equal sizes, the sink runs the cluster splitting algorithm iteratively. In each iteration step the algorithm selects the CHs by maximizing the distances between the selected CHs, therefore creating uniformly placed CHs in the network. To form clusters, the nodes are associated to the CHs based on the closest distance. Once the clusters are formed, the extra nodes are handed and taken over between the two neighbour clusters in order to balance the size of the clusters. This whole process is centrally controlled by the sink node.

In LEACH-C [3] at the start of each cluster formation round, each node sends its residual energy level and location information to the sink node. The sink node selects CHs and builds clusters using the simulated annealing algorithm. Once the CHs and associated nodes are determined, the sink broadcasts CH IDs and Time Division Multiple Access (TDMA) schedules for each node. All nodes look for their IDs to be matched as the CH ID, if not matched then the nodes follow the Time Division Multiple Access (TDMA) schedule to broadcast their data. The data transmission phase of LEACH-C is identical to that of LEACH. This way the sink, knowing the global information of nodes, forms more uniform sized clusters.

Similar procedure has been adapted in Cluster-Based Energy-Efficient Data Collecting and Aggregation Protocol (CEDCAP) [14]. After receiving the knowledge of energy levels and locations of all nodes, the sink selects the CHs and their associated nodes. Like LEACH-C, here also sink provides the data transmission TDMA schedules to all nodes. But in CEDCAP, the TDMA calculated by the sink are scheduled according to the node degree control of each cluster. Based on the node degree control a set of nodes in each cluster are kept dormant for some period of time, hence reducing the redundant data transmission in the network.

Drawback. In centrally controlled cluster formation protocols in order to provide the energy and location status of nodes, all nodes should send extra overhead of control packets at the start of each round [3]. Besides, each node needs to remain in idle listening mode for a considerable time, in order to receive its CH IDs and TDMA schedules. Whether it is a single hop or a multihop network, additional communication cost is incurred. This cost further increases with the size of network or if nodes are placed at far off places in the network.

3.2. Grid-Cluster Based Protocols

Unlike centrally controlled cluster formation protocols, in grid-cluster based protocols the CH selection decisions are distributed among the nodes themselves. Therefore, it can work well in a large scale network. The basic idea of grid-cluster protocols is to divide the network area into equal sized virtual grids where each grid is considered as a cluster with one CH in each cluster [15–20]. The role of CH is rotated among different nodes within a cluster. Figure 2 depicts the grid-cluster method where every grid contains one CH. The main characteristics of the grid-cluster based protocols can be given as follows.

• (1)

A grid is considered as a cluster; that is, the clusters are fixed and not dynamic. Although this method decreases the variations in sizes and locations of the clusters, due to the random deployment of nodes, it cannot create all equal sized clusters. Authors in [18] have tried to further even out this irregularity such that after setting one CH in each grid, the sizes of clusters are adjusted by handing and taking over extra nodes to and from the neighbour grids. This is done through a centralized control system and requires an extra overhead of control packets which consumes extra energy and delay in the system.

(2)

Each grid contains one CH in it and the role of CH rotates among the nodes within a grid. For example, in [16, 20], there is a rotation of CHs which is based on a back-off timer. The back-off timer is calculated on the basis of residual energy levels of each node within a grid. In some of the grid-cluster protocols, the algorithm selects one CH per grid based on its energy level, while there is no rotation of CHs made until the energy of existing CH is completely depleted [17, 19].

Figure 2

Grid-cluster based WSN.

Drawback. Grid-cluster protocols have regularized the CH distributions, in the network, to some extent and have substantially reduced the variations in the cluster sizes. But the network energy consumed in these protocols is very high compared to a dynamic cluster based protocol. The reason behind this is that the selection of CHs is done only within a grid and not with respect to the whole network, as is done in LEACH. Therefore, this method does not give a fair selection of CH with respect to all of the nodes of the network. Another reason of high energy consumption is that the clusters are not formed on the basis of the distances to the closest CHs. Irrespective of the distance a node will always have to associate with the CH belonging to its own grid. For example, in Figure 2 in grid number 1 the nodes in the lower right corner of the grid will have to transmit their data to the distant CH in their grid, whereas there were two closer CHs available in grid number 2 and 5.

4. Proposed Solution

In this research work we have proposed a Distributed Uniform Clustering Algorithm (DUCA) to distribute the CHs evenly and to reduce the variations in cluster sizes in a dynamic cluster based WSN. In DUCA to get an even distribution of CHs, the network is divided into virtual grids. Unlike existing grid-cluster based protocols, the grids in DUCA do not represent a cluster. Our suggested CH selection and node association mechanism has substantially reduced the network energy consumptions compared to existing grid-cluster protocols and LEACH-C as a centrally controlled protocol.

4.1. Assumptions

Following are the basic assumptions made in DUCA design.

• (i)

Initially a large number of equally charged sensor nodes are randomly deployed in the field and there is a sink node in the centre of the field.

(ii)

Each sensor node is stationary after deployment and is capable of getting its location information by the use of global positioning system or by using any other method of localization.

(iii)

Initially based on their locations each node is informed about their respective grid ID.

(iv)

Design of the DUCA is such that it does not require any change in the existing MAC layer of a dynamic cluster based protocol. All the contentions in DUCA are solved by the MAC layer proposed for LEACH protocol.

4.2. Algorithm Design

In DUCA, initially the sink decides the required number of CHs (C) in the network. To distribute the CHs evenly, network area is divided into $G_T$ number of grids such that we get $C\approx G_T$ .

DUCA requires that each sensor node should know which grid it belongs to. In Section 4.2.1, we have explained the method and algorithm used to calculate the grid IDs for each node.

In DUCA, like other existing cluster based protocols, the collection of data is done in rounds, whereas the cluster formation process is divided into three phases. CH selections are done in the first two phases (explained in Sections 4.2.2 and 4.2.3, resp.) and node associations are done in the third phase (explained in Section 4.2.4). To make sure that we get at least one CH in almost every grid, more than required number of CHs are preelected in the first phase of CH election. This is done so that after going through the second phase of CH election we can get the required number of evenly distributed CHs in the field.

4.2.1. Detection of Grid IDs

Suppose the network is spread on a rectangular or square area with the dimensions of X by Y units (for the sake of simplicity, in our simulations we have assumed a square area). The sink calculates and assigns grid IDs to all sensor nodes in the network, based on the following steps.

Steps

•  

$(1)$ Sink divides the network area into equal sized $G_T$ number of virtual grids. Each grid is assigned its ID according to its row number and column number in the field, calculated as follows.

 

Let G = grids in one column = grids in one row. The height and width of each grid are $G_{\text{height}}=Y/\sqrt{G_T}$ and $G_{\text{width}}=X/\sqrt{G_T}$ , respectively.

 

Based on the row number and column number of each grid, their grid IDs are calculated using the following, where i is the grid ID of ith grid:

$$\begin{array}{cc}& G_{i\text{Row}}=\{\begin{array}{cc}G\hfill & \text{for}\hspace{0.17em}\hspace{0.17em}\left(\left(\frac{i}{G}\right)-\lfloor \frac{i}{G}\rfloor \right)=\mathrm{0}\hfill \\ \left\{\left(\left(\frac{i}{G}\right)-\lfloor \frac{i}{G}\rfloor \right)\times G\right\}\hfill & \text{elsewhere}\hfill \end{array}\\ {\text{Grid}}_{i\text{Col}}=\lceil \left(\frac{i}{G}\right)\rceil .\end{array}$$

(2)

 

And midpoint of ith grid can be calculated as follows:

$$\begin{array}{cc}& G_{i\text{Mid}}=\left(G_{\text{height}}\times \left(G_{i\text{Col}}-\frac{\mathrm{1}}{\mathrm{2}}\right)\right)\hspace{1em}\text{by}\hspace{0.17em}\hspace{0.17em}\left(G_{\text{width}}\times \left(G_{i\text{Row}}-\frac{\mathrm{1}}{\mathrm{2}}\right)\right).\end{array}$$

(3)

 

$(2)$ Each node sends its location information (x, y coordinates) to the sink. The sink uses Algorithm 1 to calculate the grid ID for each node.

 

$(3)$ Sink broadcasts the grid IDs of all nodes so that every node, for the rest of its lifetime, knows its location and to which grid it belongs to.

Table 1 shows all the symbols and their meanings used in this paper.

Table 1

Symbols and their definitions.

Symbols	Definitions
n	Number of nodes in the network
C	Number of Cluster heads
$G_T$	Total Number of Grids
${\text{TR}}_s$	Threshold Sensing Range
$R_s$	Sensing range of a sensor node
$R_{\max S}$	Maximum required sensing range
$r_s$	Side Length of the network area
$G_{\text{height}}$	Height of each grid
$G_{\text{width}}$	Width of each grid
$G_{i\text{Row}}$	Row number of ith grid
$G_{i\text{Col}}$	Column number of ith grid
$G_{i\text{Mid}}$	Mid Point of ith grid
G	Grids in one row or column
$G_{\text{CH}}$	Number of grids that have the highest probability of having one CH in each grid
$G_{\text{CHmax}}$	Maximum number of grids beyond which the probability of having one CH in each grid starts decreasing
$\mathrm{d}$	Percentage of distortion in data after its aggregation

Algorithm 1: Algorithm to assign Grid-IDs to each node based on their locations.

for  $j=FirstNode$ to $Lastnode$  do

  Initialize:  $\text{Gri}{\text{d}}_i=\mathrm{1}$

 for  $gx=\mathrm{1}$ to G do

  if  x coordinate of $j\le (G_{\text{width}}\times gx$ ) then

   for  $gy=\mathrm{1}$ to G do

    if y coordinate of $j\le (G_{\text{height}}\times gy$ ) then

     Assign  $\text{Gri}{\text{d}}_{\text{ID}}\hspace{0.17em}\text{of}\hspace{0.17em}j=\text{Gri}{\text{d}}_i$

     break

    end if

    Increment:  $\text{Gri}{\text{d}}_i$ by 1

   end for

   break

  end if

  Increment:  $\text{Gri}{\text{d}}_i=(gx\times G)+\mathrm{1}$

 end for

end for

4.2.2. CH Election Phase 1

In this phase our aim is to get a fair selection of CHs to equalize the consumption of energy among all the nodes in the network. Therefore, the CHs are elected based on the number of times they have been selected in the previous rounds. For this the election method has been adopted from the LEACH protocol. According to LEACH, in every round, each node generates a random number between 0 and 1 and if the number is less than a threshold value $T(n)$ , the node gets elected for that round. The value of $T(n)$ is calculated as follows [3]:

$$\begin{array}{cc}& T\left(n\right)=\{\begin{array}{cc}\frac{p_{\text{CH}}}{\mathrm{1}-p_{\text{CH}}*\left(r\mathrm{mod}\left(\mathrm{1}/p_{\text{CH}}\right)\right)}\hfill & \text{for}\hspace{0.17em}\hspace{0.17em}n\in X\hfill \\ \mathrm{0}\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(4)

$p_{\text{CH}}$ is the required percentage of CH in the network; that is, $p_{\text{CH}}=C/n$ , where n is the total number of nodes in the network and X is the set of nodes that have not been cluster heads in the last $\mathrm{1}/p_{\text{CH}}$ rounds. r is the round number for which the CH is being elected. If taken average over a large number of rounds, LEACH's $T(n)$ formula always gives exact value of $p_{\text{CH}}$ , while in an individual round it highly deviates from the required value of $p_{\text{CH}}$ . Thus, by using LEACH's $T(n)$ formula in DUCA's first phase of CH selection, it was found that there are many rounds, where $C\ll G_T$ . As a result, the relation $C\approx G_T$ could not be achieved in DUCA's second phase of CH selection. In DUCA more number of CHs are needed to be preelected than eventually required; that is, we need to keep $p_{\text{CH}}>C/n$ . But increasing the value of $p_{\text{CH}}$ gives a corresponding increase of network energy consumption. The reason behind this increase of energy consumption is that with a larger value of $p_{\text{CH}}$ the CHs are not elected fairly based on their previous number of selections. Question arises: how much greater should we keep the value of $p_{\text{CH}}$ so that the number of nodes elected in this phase is large enough to get at least one CH in each grid but not large so that it would consume a considerable amount of extra energy. We have estimated the value of $p_{\text{CH}}$ as follows.

Let P be the probability that almost every grid contains at least one CH after first phase of CH election; then, we have to maximize P such that

$$\begin{array}{cc}& \frac{G_T}{n}\le p_{\text{CH}}<n,\hspace{1em}\hspace{1em}{E}_c<E_{cG},\end{array}$$

(5)

where $E_c$ is the network energy consumed in our algorithm for C number of cluster heads and $E_{cG}$ is the network energy consumed in a grid-cluster based algorithm for C number of cluster heads. It was seen through the results based on extensive simulations of the proposed method that if p is increased by $G_T$ times in (4), then optimal number of preelected CHs can be obtained with minimal extra energy consumptions.

4.2.3. CH Election Phase 2

The preelected CHs in phase 1 are not evenly distributed; therefore, the aim of this phase is to get an even distribution of CHs in the network. Following are the steps taken.

Steps

• (1)

All the CHs elected in phase 1 broadcast their residual energy levels and their grid IDs within their grid region.

(2)

If there were more than one CH in a grid, after hearing the broadcast in Step 1, the one with the highest energy level gets itself elected automatically. The remaining CHs, belonging to the same grid, will go back into their normal node mode for this round.

(3)

The elected CHs, finally, advertise their elections. This time, the broadcast range is increased to cover the nodes in the adjacent grids also. This is done because DUCA tries to get $C\approx G_T$ and not $C=G_T$ . It means that there is a small possibility in few rounds that there exists a grid which has no CH in it. In that case the nodes in the grid without a CH can associate themselves with the closest CH in adjacent grid.

This method gives number of CHs elected as almost equals to the number of grids in the region; that is, $C\approx G_T$ , and if the ratio of $n/G_T$ is according to (11) (explained in Section 6) we get the number of CHs exactly equal to the number of grids; that is, $C=G_T$ .

4.2.4. Nodes Association Phase

The remaining nodes, after hearing CH advertisements, determine their closest CH on the basis of received signal strengths of multiple CHs. In this phase we have used a parameter, namely, Threshold Sensing Range ( ${\text{TR}}_s$ ), to further reduce the sizes of clusters. It is assumed that the acceptable value of ${\text{TR}}_s$ which is based on the sensing range of nodes is provided by the sink (in Section 5 we have explained a method to suggest a suitable value for ${\text{TR}}_s$ ). Once all the clusters are set, CHs collect, aggregate, and forward data to the sink. The clusters are formed based on the following steps.

Steps

• (1)

Irrespective of their grid IDs, nodes broadcast their association requests to the CH, which has the shortest distance to them. In these broadcasts, the nodes also send their residual energy levels and their locations to the respective CHs.

(2)

CHs calculate the distances between each of its associated nodes and select the active nodes for this round according to the algorithm shown in Algorithm 2. ASST_LIST is the list of nodes which are associated to this CH and the ACTIVE_LIST is the list of nodes which are active for this round only.

(3)

The CH puts a node to either SLEEP_STATE or ACTIVE_STATE depending on ${\text{TR}}_s$ value between the nodes and the energy level $E_N$ of the node N. The CHs provide slots in the TDMA schedules only for the ACTIVE_STATE nodes and the redundant nodes remain in SLEEP_STATE for this round.

Algorithm 2: Algorithm to select associate nodes based on $\text{T}{\text{R}}_s$ .

Require:  Put all nodes in the ASST_LIST into IDLE_STATE

 Initialize: ACTIVE_LIST $\leftarrow$ ASST_LIST

 From ASST_LIST

 for  $i=FirstNode$ to $SecondLastnode$  do

  for  $j=NextNode$ to $LastNode$  do

   if  The distance between i & $j\le \text{T}{\text{R}}_s$  then

    if  $i\in$ ACTIVE_STATE then  Put $j\in$ SLEEP_STATE

    else if  $E_i\ge E_j$  then

     Put $i\in$ ACTIVE_STATE and $j\in$ SLEEP_STATE

     Decrease j from the ACTIVE_LIST

    else

     Put $j\in$ ACTIVE_STATE and $i\in$ SLEEP_STATE

     Decrease i from the ACTIVE_LIST

    end if

   end if

  end for

 end for

Ensure:  TDMA Schedule $\leftarrow$ ACTIVE_LIST

4.3. Comparisons of Proposed Algorithm with Centrally Controlled and Grid-Cluster Based Protocols

The comparison analysis of DUCA with the centrally controlled and grid-cluster based protocols are given as follows.

• (1)

The startup phase in centrally controlled cluster formation protocol is always more energy intensive than the distributed approach since the information from each node must be transmitted to the sink at the beginning of each round [3]. This cost of communication increases for the nodes that are far away from the sink [3]. This is not the case with our algorithm since it is based on distributed clustering method.

(2)

Unlike centrally controlled protocol the CH selection decision is distributed among the nodes; therefore, the proposed algorithm can be used in a large scale network with reduced overheads.

(3)

Unlike existing grid-cluster based protocols, the grids used in our algorithm is only for the even distribution of CHs and not for the cluster formations. Our suggested CH selection and node association mechanism have substantially reduced the overall energy consumption of the network compared to the existing grid-cluster based protocol. There are following main points that can differentiate our mechanism with any other grid-cluster based protocol proposed so far.

• (a)

With randomly deployed nodes there can be many grids which have small number of nodes. Therefore, using CH selections criteria only within the grids could not give fair CH selections based on overall number of nodes in the network. This can be explained as follows. For example, in Figure 2, grid numbers 8 and 5 have only three nodes in each of them. If these three nodes become CH alternatively, the chances of their expiring as compared to other nodes in the network will be very high. Therefore, a simple rule of selecting one CH per grid as considered in existing grid-cluster based protocols does not give a balanced consumption of the network energy. That is why in DUCA, every grid does not necessarily contain one CH in it. However, we try to maintain the relation as $C\approx G_T$ .

(b)

In DUCA, a grid does not necessarily represent a cluster; rather, a cluster is formed based on the distances of each node to its nearest CH. As a result, a CH may have its associated nodes from more than one grid while maintaining even distribution of clusters and lower energy expenditure in the network.

(c)

In our algorithm based on a parameter, introduced as Threshold Sensing Range ${\text{TR}}_s<R_s$ , the sizes of clusters are further reduced by selecting only those nodes which do not fall within ${\text{TR}}_s$ range of each other.

(d)

Unlike existing grid-cluster based protocol, in DUCA not all of the grids must be containing one CH for the entire time period. There may be few grids which would remain without CHs in some of the rounds.

The overall effect after the implementation of the DUCA is that we are now able to have the following:

• (1)

cluster heads and clusters, as evenly spread in the network;

(2)

a significant improvement in the energy consumption as compared to a regular grid-cluster based protocol;

(3)

the selection of CHs is done locally and there is no need of centralized CH selections by the sink;

(4)

in each grid only those nodes will be elected as CHs which have the highest residual energies;

(5)

the sizes of clusters are in a limited range and the clusters are confined in a close vicinity. This helps in appropriate aggregation of the data specially within a small sized data packet.

5. A Heuristic Approach to Determine the Threshold Sensing Range (TR _s )

In our algorithm using a suitable value of Threshold Sensing Range ( ${\text{TR}}_s$ ) can reduce the sizes of clusters and the redundant data flow in the network. In this section we will discuss a method through which the value of ${\text{TR}}_s$ can be estimated in a network of randomly deployed sensor nodes.

A network is said to be covered if each point of it is covered by the sensing range of at least one node. In a randomly deployed WSN, to guarantee the coverage of the whole area, generally more sensors are deployed than needed. This is done so that the sensing or monitoring tasks can be performed to compensate the lack of exact positioning and to improve the fault tolerance [21]. On the other hand, this creates many regions in the network which are covered by more than one sensing node. These regions cause redundant flow of data packets in the network, thus creating unnecessary energy consumption of the network. In DUCA, the parameter ${\text{TR}}_s<R_s$ has been used by the CHs to further reduce their cluster sizes, by selecting only those nodes which do not fall within the ${\text{TR}}_s$ range of each other (Algorithm 2).

In a large scale randomly deployed network of sensor nodes, there are three ways through which an acceptable value of ${\text{TR}}_s$ can be estimated:

• (1)

application requirement;

(2)

deployment strategy of the nodes;

(3)

the number of nodes deployed in the area.

Based on the application requirements, approximating the value of ${\text{TR}}_s$ is beyond the scope of this paper discussion. However, based on the deployment strategy and the number of nodes in the network, an approximate value of ${\text{TR}}_s$ can be estimated as follows.

5.1. Calculation of TR _s

Let n be the minimal number of nodes, required for an optimal and deterministic (not random) placement of nodes (i.e., each point of the network area is covered with at least one sensor node). Then, the relation between n and the sensing ranges $R_s$ of nodes can be given as follows [22]:

$$\begin{array}{cc}& \frac{n\times \pi R_s^{\mathrm{2}}}{A}=\frac{\mathrm{2}\pi }{\sqrt{\mathrm{27}}},\end{array}$$

(6)

where A is the size of the monitored area and $R_s$ is assumed to be same for all the nodes.

When nodes are deployed randomly, their placements are assumed to be uniformly distributed. It means that each node has equal probability to be placed at any location within the area. It can intuitively be said that to have a minimum value of $R_s$ the nodes should be placed evenly and equidistantly. This can be called the best case, whereas worst case would be when all of the nodes have fallen at one location which is the farthest point to the center of the field. A square region in Figure 3, with its sides as $r_s$ and area size as $A=r_s^2$ , explains the best and worst placements of nodes based on the minimum requirement of $R_s$ . From (6), we can say that with n evenly placed nodes, to have the whole area covered, the sensing range required for each node can be given as

$$\begin{array}{l}{R}_s=\sqrt{\mathrm{0.38}\times \frac{r_s^{\mathrm{2}}}{n}}\\ \text{or}\hspace{0.17em}\hspace{0.17em}{R}_s=\mathrm{0.62}\times \frac{r_s}{\sqrt{n}}.\end{array}$$

(7)

Figure 3

The best and worst case scenarios for randomly deployed nodes in a square region.

From Figure 3, for the worst case is the longest distance between the two points of a square region; that is, a diagonal of a square, given as $R_s=\sqrt{\mathrm{2}}\times r_s$ .

In the process of random deployment of nodes, if p is the probability that the nodes are arranged according to the best case then $(\mathrm{1}-p)$ is the probability that the nodes are deployed as worst case. Therefore, the minimum sensing range $R_s$ that each node should have can be given as

$$\begin{array}{cc}& R_s=\left(\mathrm{0.62}\times \frac{r_s}{\sqrt{n}}\right)\left(p\right)+\sqrt{\mathrm{2}}\times r_s\left(\mathrm{1}-p\right).\end{array}$$

(8)

${\text{TR}}_s$ is the distance between two nodes in a network which are sensing almost the same region of the network, shown in Figure 4, and can be given as

$$\begin{array}{cc}& \text{T}{\text{R}}_s=\mathrm{2}\times \left(l-\left(R_s-R_{\max s}\right)\right),\end{array}$$

(9)

where $R_s$ is the available sensing range, $R_{\max s}$ is the maximum required sensing range, and l is the difference between outer boundaries of $R_s$ and $R_{\max s}$ . From (8) and (9), for $R_s>R_{\max s}$ and considering worst and best case scenarios in a randomly deployed network, the value of ${\text{TR}}_s$ can be estimated as

$$\begin{array}{l}{\text{TR}}_s=\mathrm{2}\times (l-(\left(\mathrm{0.62}\times \frac{r_s}{\sqrt{n}}\right)\left(p\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\sqrt{\mathrm{2}}\times r_s\left(\mathrm{1}-p\right)-R_{\max s}\phantom{\frac{r_s}{\sqrt{n}}})).\end{array}$$

(10)

Figure 4

Threshold Sensing Range ( ${\text{TR}}_s$ ) between two nodes.

Table 1 shows all the symbols and their meanings used in this paper.

6. Relation between Number of Nodes, Grids, and Cluster Heads in the Network

In DUCA, to get the desired number of CHs, the network is divided into the same number of virtual grids. In this section we will explore the relation between $G_T$ , n, and C in a network of randomly deployed nodes.

It was seen during the implementation of our proposed algorithm that for a small value of $G_T$ the relation $C\approx G_T$ can easily be maintained; that is, almost every grid contains one CH in it, whereas this relation cannot be achieved for lower values of n or higher values of $G_T$ . Through an extensive simulation of our proposed algorithm, we have developed a formula to find the minimum value of n that can be suggested prior to the network deployment such that the relationship of $C\approx G_T$ remains there.

In a network with n uniformly deployed nodes, let $G_{\text{CH}}$ be the number of grids that have the highest probability of having one CH in each grid. Let $G_{\text{CHmax}}$ be the maximum number of grids beyond which the probability of having one CH in each grid starts decreasing; that is, $G_{\text{CHmax}}$ is the upper limit of $G_{\text{CH}}$ . Our purpose is to find the value of $G_{\text{CHmax}}$ for any value of n. We executed our simulation, repeatedly, for a wide range of n and different area sizes. Each case was repeatedly calculated for $G_{\text{CH}}=4$ to n. An extreme case of $G_{\text{CH}}=n$ was also taken where it was assumed that there is only one sensor node in each grid. The results obtained shown in Figure 5 are the averages of data collected. By adjusting its trend line equation with the data collected from the simulations, the relation of $G_{\text{CHmax}}$ with n can be defined as follows:

$$\begin{array}{cc}& G_{\text{CHmax}}\cong {\left(\lfloor \left(\mathrm{0.24}\times n+\mathrm{6.5}\right)\rfloor \right)}^{\mathrm{2}}.\end{array}$$

(11)

Figure 5

Upper limit of $G_{\text{CH}}$ for different value of n.

The above equation can be explained as follows. For n number of nodes within a finite size of area, we should not have more than $G_{CHmax}$ grids if we want to have one CH in almost every grid. For example, for $n=\mathrm{200}$ if we want to have almost one CH in every grid we should have $G_T\le \mathrm{49}$ grids. In other words for a network having 49 or less grids, to maintain the relation as $C\approx G_T$ , we should have $n\ge \mathrm{200}$ nodes deployed uniformly in the area.

7. Evaluation of Proposed Solution

To analyze and compare DUCA solution with the existing protocols we developed a model of WSN with randomly deployed nodes, in which DUCA was compared with the following:

• (1)

LEACH protocol: as an example of dynamic cluster based protocol;

(2)

grid-cluster based protocol: as an example of existing distributed uniformly cluster formation protocol;

(3)

LEACH-C protocol: as an example of centrally controlled uniform cluster formation protocol.

Our aim is to show that our proposed mechanism gives a better solution, in terms of cluster sizes and distributions, compared to LEACH protocol while giving a substantial decrease of network energy consumption compared to grid-cluster and LEACH-C protocols.

7.1. Simulation Parameters

Simulation models were set up using MATLAB for LEACH, LEACH-C, grid-cluster based, and DUCA protocols. Multiple numbers of nodes ranging from 50 to 500 were considered in different field area sizes. The protocols were compared based on different parameters like network energy consumptions, cluster sizes, locations of CHs, and frame sizes. Random function seeds used for the deployment of nodes were kept the same for the four protocols, in each scenario. The CH election criteria and the nodes association criteria used in the simulations are discussed in detail in Section 4.2. Equations used for the calculation of grid ID of each node is given in Section 4.2.1. The data were collected after extensive repetitions of each simulated scenario with different random seeds.

The basic parameters used in the simulations are shown in Table 2. However, the values of m (number of frames sent per round) were not considered according to the method used in LEACH protocol. The authors of LEACH have acquired a method to establish the value of m by making it dependent on the initial energy $E_o$ given to each node by the following [3]:

$$\begin{array}{cc}& m=\frac{E_o}{E_{\text{CH}/\text{round}}+\left(\left(n/C\right)-\mathrm{1}\right)E_{\text{nonCH}/\text{round}}},\end{array}$$

(12)

where n is the total number of nodes, C is the expected number of CHs or clusters per round, $E_{\text{CH}/\text{round}}$ is the energy consumed by all CHs per round, and $E_{n\text{onCH}/\text{round}}$ is the energy consumed by all non-CH nodes per round.

Table 2

Parameters and their values used in simulations.

Parameters	Definations	Values taken in Simulations
n	Number of nodes in the field	50 to 500
N	Number of associated nodes in a cluster	Variable
$E_o$	Initial Energy given to every node	$\mathrm{2.5}$  J
$E_{\text{elec}}$	Energy dissipated in electronics for 1 bit Transmission and reception	$\mathrm{50}$  nJ/bit
$E_{\text{amp}}$	Energy consumed in power amplifier in free-space model	$\mathrm{10}$  pJ/bit/m2
$E_{\mathrm{tr}}$	Energy consumed in power amplifier in two-ray propagation model	$\mathrm{0.0013}$  pJ/bit/m4
$K_d$	Data packet size	250 Bytes
$K_c$	Control packet size	25 Bytes
$K_t$	TDMA schedule packet size	$(K_c+N)\times \hspace{0.17em}\text{Bytes}$
α	Throughput of non-persistent CSMA	0.814
$d_{\text{crossover}}$	Distance after which line of sight does not work well	87 m
m	Number of data frames per round in each cluster	10, 50, 100

This is because the authors of LEACH have assumed that on average if there are $n/C$ rounds before each node becomes a CH, then each node should have enough energy to be a CH once and non-CH $((n/C)-\mathrm{1})$ times. By using the values of n, $E_o$ , $E_{\text{elec}}$ , $E_{\text{amp}}$ , and $E_{\mathrm{tr}}$ mentioned in Table 2 they have come up to the conclusion that m should be given as [3]

$$\begin{array}{cc}& m=\frac{E_o}{\mathrm{9}mJ}.\end{array}$$

(13)

Now for the calculation of $E_{\text{CH}/\text{round}}$ and $E_{\text{nonCH}/\text{round}}$ they have considered the factor $n/C$ as a constant value, while it has been shown that the value of C in LEACH is highly variable [3]. Moreover, not only the value of C but also the number of nodes in the clusters are highly variable. For example, in a network of 100 nodes (n) and 5 clusters (C), the sizes of clusters highly deviate from the assumed value of $n/C=20$ nodes per cluster. Therefore, in our simulations we have considered m independent of the initial energy assigned to each node.

According to our inference the number of frames per round should be dependent on the application requirement and amount of data to be transferred in each round and not on the initial energy assigned to each node. Since in our analysis we have considered network energy consumptions and not the energy consumed in each node, therefore varying the sizes of m had no effect on overall comparison of the four protocols. Hence, for our simulations we have selected $m=\mathrm{10}$ .

7.2. Calculation of Distortion Percentages in Received Data

The size of a cluster can affect the data aggregation process on a CH. This can be understood through two important factors, that is, the percentage of distortions $(\mathbf{d})$ in the data, received by the sink, and the payload requirement for the aggregation of data on a CH. Therefore, using these parameters, the effects of large and variable sized clusters in data aggregations have been analysed.

The sizes of clusters affect the requirement of payload size at a CH. If the data collected at CH are aggregated without summarizing or compressing it then it is called packet merging. In packet merging the payload size requirement increases linearly with the increase of cluster size. Consider an example of packet merging, where each data element takes only 2 bytes and each node's ID takes 1 byte. Even with this minimal requirement of bytes, a cluster of 8 nodes requires 24 bytes in a packet, excluding header, while a cluster of 40 nodes would require 120 bytes excluding the header. On the other hand, if compression or summary (average, sum, difference, or maximum) of all readings is taken then the distortion in the individual received data increases with the increased size of clusters.

Many of the previously proposed protocols have used summary based aggregations in their networks. In summary based aggregations it has been assumed that the sensors are highly correlated. High correlation in sensors means that the sensors’ data values are close enough so that their summarized value can give an adequate overview of all of the data. However, this might not be true in real world environments. Therefore, aggregating by taking summary of multiple data values can give distortions in individual reconstructed data at the receiver.

To analyse this we have used different types of sensor data planes to collect the data through the clustered network. These data planes were synthesized by taking actual readings from IRIS motes using MTS420 sensor boards. These sensor boards give different types of sensed data readings, such as temperature, seismic vibrations, light, and humidity. Table 3 shows few of the samples of data collected from MTS420 sensor boards. There are different ranges in which these data types lie. Some of them may give high variations from one node to another or may not give variations at all. Therefore, we have used two types of sensed data planes: one with low variations of data (LV plane) and one with high variations of data (HV plane), shown in Figures 6 and 7, respectively. Also different ranges of data in each plane were considered. First, we did the summary based aggregations using these synthetic sensed data planes in a cluster based WSN. Then, the percentage of distortion $(\mathbf{d})$ in the received data was calculated.

Table 3

MTS420CA Sensor Board Data Readings.

[2013/05/18 18:52:48] MTS420 sensor data
Humidity	Temp	Light	X-axis Accel	Y-axis Accel	Pressure
(%)	( ${}^{°}\text{C}$ )	(lux)	(mg)	(mg)	(mbar)
89	33	66.01	600	380	991.682556
86	33	66.01	720	420	991.589172
72	33	53.13	680	400	991.868713
71	32	62.79	700	400	991.77594
64	32	42.09	740	400	991.755066
54	32	69.23	720	380	991.557861
50	32	62.79	740	380	991.650635
43	32	62.79	740	380	991.743408
40	31	66.01	780	400	991.7323
37	32	56.35	760	380	991.86676
35	32	56.35	760	380	991.865713
34	31	56.35	760	360	991.337594

Figure 6

Low variation data (LV) plane.

Figure 7

High variation data (HV) plane.

In a cluster of N nodes, if the sensed data from node j is $m_j$ then d in received ${\stackrel{-}{m}}_j$ at the sink can be given as

$$\begin{array}{cc}& \mathbf{d}=\text{Distortion}\%=\left|\frac{m_j-{\stackrel{-}{m}}_j}{m_j}\right|\times \mathrm{100}.\end{array}$$

(14)

7.3. Results and Findings

In this work, we have compared the cost of clustering using single-hop communication of nodes between LEACH, LEACH-C, grid-cluster, and DUCA protocols. We have also examined the effect of cluster size on d using multiple kinds of data collected from different types of environment.

Figure 8 gives a generalized overview of d in the received data for different cluster sizes. Distortion in small clusters is 40 to 60% lower than the value of d in larger clusters. This is true for clusters with less than 11% nodes in all data sensing planes (except for LV plane with low ranges). However, in HV plane with low range, the value of d decreases again for very large sized clusters. This is because the size of clusters becomes large enough compared to the cumulative ratio of data range and data variations in the field, giving a lower value of d in the received data.

Figure 8

Distortion percentage $\mathbf{\left(}\mathbf{d}\mathbf{\right)}$ in summary aggregation.

In a network with 9% CH, there is a higher chance of 11% nodes per cluster, as shown in Figure 9, whereas the minimum energy consumed is in the range of 4 to 10% CHs in the network, as can be seen from Figure 10. Although taking higher values of CH% can give smaller clusters, the results have shown that the energy consumption increases in the network.

Figure 9

The probability distributions of cluster size in LEACH, LEACH-C, grid-cluster, and DUCA protocols.

Figure 10

Network energy consumption in 1000 rounds comparisons of LEACH, LEACH-C, grid-cluster based, and DUCA.

Concluding above paragraphs and by examining Figures 8, 9, and 10 together it can be said that around 9% CH selections can give the optimum results in terms of minimum energy consumption and distortion percentages in the data.

The results have shown that there is a significant improvement in the cluster size variations in DUCA as compared to LEACH protocol. On the other hand, the energy consumptions, in DUCA, are very low compared to the existing grid-cluster based and LEACH-C protocols.

Figure 9 shows high variations in the cluster sizes of LEACH protocol, which has been reduced significantly by implementing DUCA based CH selections. For example, in a network of 100 nodes and 4% CHs, the sizes of clusters in the case of LEACH have an average of 24 nodes with a standard deviation of 11.87 and the largest size of cluster is of 77 nodes. In the case of DUCA, these values reduced to 24 nodes, StDev = 6.47, and 50 nodes, respectively. That is, there is almost 2 times decrease in the variations of the cluster sizes. Although the cluster sizes improve significantly in LEACH-C and grid-cluster protocols, from Figure 10 it can be seen that this stability of cluster sizes costs almost 1.5 times more energy consumptions in the network.

The comparison of energy consumption within the network is shown in Figure 10. In grid-cluster based network, large amount of energy is consumed at 5% to 8% CH. According to our analysis, this is due to the fact that the selection of CHs is not done with respect to the whole network; rather, it is based on the energy levels of nodes within their respective grids only. Another reason is that the grids are considered as clusters irrespective of the distance of each node to its nearest CH, whereas in the proposed algorithm the CH selection criteria are based on the node's energy levels with respect to its grid as well as the whole network. Also, the clusters are formed on the basis of nodes’ distances to their nearest CHs. In LEACH-C, since each node needs to transmit its status to the sink in the start-up phase of each round, therefore it is more energy intensive. This cost of energy is always added up to the cost of normal data communications of the nodes.

Significant amount of energy can further be conserved if the sensing ranges of nodes are kept large enough such that the number of active nodes per cluster can be reduced. This can be implemented if a reasonable value of ${\text{TR}}_s$ is selected from (10) and Figures 11 and 12. In the case of higher percentage of CHs, not only the sizes of clusters get reduced but also the variations in the sizes get better. For example, in a network with 9% CHs, the average cluster size is reduced to 10 nodes with ${\text{TR}}_s=\mathrm{5}$ which was more than 11 nodes without ${\text{TR}}_s$ . Its probability distribution gets more stabilized with a standard deviation of 3.8 which was 6.67 for the case of LEACH and 4.9 for DUCA protocol without using ${\text{TR}}_s$ in the cluster formations.

Figure 11

Network energy consumed in 1000 rounds; area = 1000 m² for different ${\text{TR}}_s$ values.

Figure 12

PMF comparison of cluster sizes with ${\text{TR}}_s=5$  m.

Figure 13 gives the minimum network energy consumptions for different number of nodes in LEACH, LEACH-C, grid-cluster, and DUCA protocols. The effect of increase in number of nodes is much more in LEACH-C and grid-cluster protocols as compared to LEACH and DUCA, such that for 4 times increase in number of nodes the energy consumption increased to 8 times in grid-cluster and LEACH-C, while it increases 4 and 5.5 times in LEACH and DUCA, respectively. Therefore, in grid-cluster and LEACH-C based protocols the ratio of number of nodes to network energy increases from 2.7 to 5.6 approximately. In case of LEACH it remains almost the same while increases slightly from 1.9 to 2.7 in the case of DUCA.

Figure 13

Minimum network energy consumption for different number of nodes.

8. Conclusion

In dynamic cluster based WSN, usually the sizes of clusters get highly variable when the CH selections are not based on the location of the nodes. This requires large or variable sized packets for the fusion or aggregation of data. On the other hand, if the CH selections are based only on their location, sizes of clusters become stable but it increases the overall energy consumption of the network. Centrally controlled CH selection mechanisms also give a homogeneous distribution of clusters but these procedures require extra communication energy at the start of each round. In the proposed algorithm (DUCA), cluster size variations have been substantially reduced without spending extra energy in the network. In DUCA, virtual-grid parameters have been used for even distribution of CHs while the clusters are formed on the basis of distances to CHs and not the grids. Since smaller clusters produce fewer distortions in aggregated data, the sizes of clusters are also reduced by exploiting the sensing ranges of nodes.