A Predetermined Deployment Technique for Lifetime Optimization in Clustered WSNs

Abstract

In wireless sensor networks, preserving energy requires utmost attention due to their high resource constraint feature. Clustering is commonly considered as one of the most efficient energy conservation technique. Firstly, considering Rician channel model for inter-cluster communication and a shortest path routing protocol, we analyze the optimization of network lifetime by balancing the energy consumption among different cluster heads (CHs). It is found that cluster radius of each level has significant role in maximization of network lifetime. To meet the requirement of optimization of network lifetime, we devise a routing aware clustering strategy. We also identify Archimedes’ spiral, based on which a deployment function is proposed for distributing member node (MN) and CH. Simulation results demonstrate that the proposed technique significantly outperforms two competing schemes in terms of energy balance, network lifetime and throughput.

1 Introduction

Due to the impetuous advancement of technologies in recent years, wireless sensor networks (WSNs) have become a reliable and mature technology, widely used in several applications ranging from industry to military and home [1]. Almost for all the available platforms of WSNs, sensor nodes are designed to run on batteries, which have very limited energy. Due to the limited on-board energy supply of sensor nodes, the design objective of these systems is normally to conserve as much energy as possible to achieve prolonged network lifetime.

Node deployment is a fundamental issue in WSNs that affects many facets of network operation, including energy management, routing, security. Based on the means of deployment, there are broadly two types of deployment: (i) random deployment, and (ii) predetermined deployment [2]. Random deployment is typically used for inhospitable environments e.g., battlefields surveillance, environmental monitoring [2]. On the contrary, many applications of WSNs serve in controlled setups where predetermined deployment of node is feasible and desirable [2]. Examples of these applications include habitat monitoring, safety assessment of factory floor. The controlled nature of the application allows pre-planning and careful selection for node placement.

To improve scalability and energy efficiency, sensors in WSNs are often organized into clusters [3] that reduce channel contention and packet collisions, resulting in better network throughput under high load [3]. The role of CHs in the clustering paradigm increases the burden on the CHs, forcing them to drain out their energy much faster. Even if the CH is equipped with a more durable battery than the MNs, the large difference in energy consumption between the two can lead to its shorter lifetime. Once the CH dies, no communication can take place between the MNs in that cluster and the rest of the network. The clusters with comparable area coverage and node density have roughly the same volume of intra-cluster data traffic. Nevertheless, the traffic from far away CHs needs to be relayed via CHs closer to the sink. Thus, CHs closer to the sink drain their energy reservoir faster than the other CHs, resulting in energy hole problem [1, 2] that may effect the whole network leading to premature decrease in network lifetime. To avoid this, care should be taken during deployment such that energy dissipation in all nodes takes place uniformly ensuring load balancing throughout the network.

Many works [4] - [8] reported so far deal with the issue of balancing the energy consumption in WSNs, by dividing the network into clusters. Nevertheless, except [4], none of the existing works consider optimization of cluster radius of each level while devising clustering structure. Further, to the best of our knowledge, no attempt has been made yet to identify a mathematical model and design a deployment scheme based on which MNs and CHs are deployed at some predetermined locations. The main contributions of this paper are as follows: Initially, different from [4] - [8], we analyze the energy balancing approach for optimization of network lifetime by jointly considering Rician fading channel and a shortest path routing protocol. Based on the analysis, principle of optimal clustering structure is derived and that in turn computes the optimal cluster radius of each level using a linear program. Similar to [8], we propose a deployment strategy based on Archimedes’ spiral using which both CH and MN are deployed at some predetermined locations. Finally, performance of the optimal clustering strategy is evaluated through quantitative analysis under both ideal and realistic scenarios.

The rest of this paper is organized as follows: In Sect. 2, literature review is provided. The system model considered for the present work is described in Sect. 3. Section 4 theoretically analyzes the network lifetime optimization problem and obtains the clustering strategy. The proposed clustering structure including a deployment strategy based on Archimedes’ spiral is described in Sect. 5. In Sect. 6, simulation results under ideal and more realistic scenarios are provided. Finally, concluding remarks are given in Sect. 7.

2 Literature Review

The state-of-the-art works that deal with the issue of balancing the load throughout the network, by dividing the network into clusters are elaborated in this section.

Shu et al. [4] provided energy balanced alternatives that try to maximize network lifetime directly by accounting for the interaction between clustering and routing. To obtain balanced power consumption, two mechanisms are proposed, viz. routing-aware optimal cluster planning and the clustering-aware optimal random relay. Unlike [4], Lai et al. presented a cluster based routing protocol, ACT (arranging cluster sizes and transmission ranges for wireless sensor networks) [5]. The protocol aims in reducing the size of the clusters with closer proximity to the sink as they take the burden of relaying more data than the clusters farther away from the sink. This is achieved by keeping cluster radii near the sink smaller while the clusters located farther away from the sink have larger radii. In another work to conserve energy, Darabkh et al. [6] proposed three clustering algorithms namely adaptive head, static head, and selective static head for mobile target tracking in WSN. Among these algorithms, the static and selective static heads algorithms follow static clustering while the other one follows dynamic clustering. Recently, in order to maximize the lifetime of deployed nodes, Li et al. [7] investigated the problem of constructing optimal clustering architectures in homogeneous WSNs. Most recently, in [8], authors proposed an optimal clustering technique to maximize the lifetime of WSNs. Initially, the authors analyzed the energy balancing approach. Based on the analysis, they derived the principle for optimal clustering structure which, in turn, decides the number of clusters in each layer and the number of MNs associated with each cluster.

Similar to [4, 5, 8] we derived clustering structure by computing the optimal cluster radius. Unlike [4, 5, 8], we analyzed the energy balancing approach for optimization of network lifetime by jointly considering Rician fading channel and a shortest path routing protocol. Further, similar to [8], we propose a deployment strategy based on Archimedes’ spiral using which both CH and MN are deployed at some predetermined locations.

3 System Models

3.1 Network Model

We virtually cover the network area χ of radius R by a disk sector of angle φ (Fig. 1). The disk sector is divided into i number of ring sectors or slices, where i = 1,…,N. In this network model, the sink is considered to be located at the vertex, as shown in Fig. 1 and responsible for collecting data from sensors. Sensors are uniformly deployed across χ with density ρ. Although, we assume a slice based network area, we argue this slice shape is general enough to approximate many other shapes e.g., triangle, square, rectangle etc.

Fig. 1.

Network area division into slices.

In this work, we assume deployment of static heterogeneous node where nodes are organized into clusters. The nodes are heterogeneous in terms of both functionality and battery capability. By functional heterogeneity, we mean a cluster consisting of two types of nodes: MNs and CHs. Similar to [6], we assume a WSN where nodes are divided proactively into many clusters at the time of node deployment. Each MN senses the environment, generates data, and periodically transmits the data to its CH. On the contrary, the CH fuses and forwards the data received from both its MNs and neighbouring CHs which are farther away from the sink. In this way data from a MN reaches the sink through intermediate CHs. We consider that MNs have limited battery capability, whereas CHs are equipped with more durable battery. Without loss of generality, we assume that each CH is located at the centre of its cluster [4]. Because of the symmetric nature of area χ and uniform deployment, the formation of clusters in a slice is also symmetric i.e., any two clusters with the same distance from the sink to their centres cover the same area. We divide the area χ into N number of slices; therefore, N types of clusters exist in the network. Here, the clusters located closest to the sink are placed in 1st slice (1st type) and farthest from the sink are placed in Nth slice (Nth type). Finally, we assume that in ith slice, there are j $\left( {j > 1} \right)$ number of clusters.

3.2 Network Operation

We assume that each MN generates data at a rate n bits/sec. Further, we assume that a CH transmits data to the sink via the shortest path. Precisely, a CH in the ith slice forwards the data packet (formed by fusing the data received from its MNs and CH of (i+1)th slice) to the closest CH in the (i-1)th slice. Next, the CH in the (i-1)th slice employs the same procedure to choose the next forwardee CH for sending its data packet. This process repeats till the data packet arrives at the sink. From the network operation, it is clear that the CH bears more data pressure than the MN and hence, the CH depletes its energy at a much faster rate than the MN. As a strategic point of view, the role of a CH is more critical in maintaining network connectivity than the MNs. Therefore, in this work, we focus our attention on energy depletion at the CHs.

3.3 Energy Model

We consider the first order radio model [7, 8] as the energy model, where energy consumption of a node is dominated by its wireless transmissions and receptions; so the other energy consumption factors such as for sensing is ignored. In addition to transmission and reception, a CH also consumes energy for data fusion. According to this radio model, energy consumed by a node for transmission and reception is as follows: Energy consumption for transmitting a n bits packet over a transmission range $R_{c}$ is $e_{tr} \left( {n,\;R_{c} } \right) = \left( {e_{elec} \; + e_{amp} \,R_{c}^{2} } \right)n = e_{t} \,n$, where $e_{t} = e_{elec} + e_{amp} \;R_{c}^{2}$ and $e_{t}$ is the energy required to transmit one bit of data. Whereas, the energy consumption for receiving a n bits packet is $e_{re} \left( n \right) = e_{elec} \;n = e_{r} \;n$, where $e_{r} = e_{elec}$ and $e_{r}$ is the energy required for receiving one bit of data. Finally, energy consumption for fusing n bits packet is $e_{da} \left( n \right) = e_{a} \;n$, where $e_{a}$ is the energy required for fusing one bit of data.

3.4 Channel Model

Motivated by [9], we use a Rician fading channel model to describe the channel between two CHs and also between the CH and the sink. In this channel model, the probability density function of the received signal amplitude is given by:

$$ f_{R} \left( \xi \right) = \frac{\xi }{{\sigma^{2} }}\text{e}^{{ - \left( {{{\xi^{2} + s^{2} } \mathord{\left/ {\vphantom {{\xi^{2} + s^{2} } {2\sigma^{2} }}} \right. \kern-0pt} {2\sigma^{2} }}} \right)}} I_{0} \left( {\frac{{\xi \,\sqrt {2R_{f} } }}{\sigma }} \right) $$

where $\xi$ is a normalized random variable that represents the fluctuation in the fading process, $\sigma^{2}$ is the variance of the multipath components, s is the amplitude of the Line-of-Sight component, $I_{0} \left( \cdot \right)$ is the zero-order Bessel function of the first kind and $R_{f}$ is the Rician factor, given by: $R_{f} = {{s^{2} } \mathord{\left/ {\vphantom {{s^{2} } {2\sigma^{2} }}} \right. \kern-0pt} {2\sigma^{2} }}$. In this channel model, for a transmitter-receiver separation distance l, channel gain is given as:

$$ h\left( l \right) = \frac{{G_{t} G_{r} \omega^{2} }}{{\left( {4\pi l_{0} } \right)^{2} }}\left( {\frac{l}{{l_{0} }}} \right)^{ - \eta } \xi = L\left( {l_{0} } \right)\left( {\frac{l}{{l_{0} }}} \right)^{ - \eta } \xi $$

(1)

where $L\left( {l_{0} } \right) = \tfrac{{G_{t} G_{r} \omega^{2} }}{{\left( {4\pi l_{0} } \right)^{2} }}$ is the path loss of the close-in distance $l_{0}$, $G_{t}$ and $G_{r}$ are the corresponding gains of the transmitting and receiving antennas, $\omega$ is the wavelength of the carrier signal, $\eta$ is the path loss exponent $\left( {2 \le n \le 6} \right)$. Since $\xi$ is random, correct reception of a signal can be guaranteed only when it is represented on a probabilistic basis. Accordingly, in our work, reliable reception of a signal is represented as $\Pr \left\{ {e_{rx} \ge \tau } \right\} \ge \delta_{r}$, where $e_{rx}$ is the energy of the received signal, $\tau$ is a predefined energy threshold and $\delta_{r}$ is the required link reliability.

4 Analysis of Network Lifetime Optimization

We consider the definition of network lifetime as follows:

Definition (Network Lifetime):

The network lifetime is defined as the time until the first CH dies [4]. A CH is considered as dead when the residual energy is less than a predetermined threshold. The threshold value for a CH is considered as when it is neither able to transmit nor able to receive any data.

The average intra-cluster and inter-cluster traffic load carried by the CHs in the ith $\left( {i = 1, \ldots ,N - 1} \right)$ slice is given by $\pi \left( {r_{i}^{2} - r_{i - 1}^{2} } \right)\rho \,n\,{\varphi \mathord{\left/ {\vphantom {\varphi {2\pi }}} \right. \kern-0pt} {2\pi }}$ and $\pi \left( {R^{2} - r_{i}^{2} } \right)\rho \,n\,{\varphi \mathord{\left/ {\vphantom {\varphi {2\pi }}} \right. \kern-0pt} {2\pi }}$, respectively. On the contrary, the average intra-cluster traffic carried by the CHs in the Nth slice is given by $\pi \left( {R^{2} - r_{N - 1}^{2} } \right)\rho \,n\,{\varphi \mathord{\left/ {\vphantom {\varphi {2\pi }}} \right. \kern-0pt} {2\pi }}$. Let $C_{i}$ be the number of CHs in the ith slice. Therefore, $C_{i}$ is approximately given by $\tfrac{{2\,r_{i} }}{{r_{i} - r_{i - 1} }}\tfrac{\varphi }{2\pi }$. Let $E_{ij}$ be the expected energy consumed by jth CH in the ith slice for transmitting all of its traffic to the nearest CH in the (i−1)th slice and $l_{i}$ be the physical distance between these two CHs. Therefore, the expected energy consumed by jth CH in the ith $\left( {i = 1, \ldots ,N - 1} \right)$ slice is given by:

$$ E_{ij} = \pi \left( {R^{2} - r_{i - 1}^{2} } \right)\rho \,n\frac{\varphi }{2\pi }\frac{{\left( {r_{i} - r_{i - 1} } \right)}}{{2r_{i} }}\frac{2\pi }{\varphi }\left( {e_{r} + e_{t} + e_{a} } \right) $$

$$ E_{ij} = \frac{{\left( {R^{2} - r_{i - 1}^{2} } \right)\left( {r_{i} - r_{i - 1} } \right)}}{{2r_{i} }}\rho \,n\left( {e_{r} + e_{t} + e_{a} } \right) $$

(2)

where $e_{t} = e_{elec} + e_{amp} l_{i}^{2}$. The expected energy consumed by jth CH in the Nth slice can be calculated applying (2) and using the standard convention that a sum of terms is zero if its lower index is greater than its upper bound.

Let $e_{ti}$ be the over-the-air RF energy consumed when transmitting one bit from jth CH in the ith slice to jth CH in the (i-1)th slice. So, the above (2) can be rewritten as:

$$ E_{ij} = \frac{{\left( {R^{2} - r_{i - 1}^{2} } \right)\left( {r_{i} - r_{i - 1} } \right)}}{{2r_{i} }}\rho \,n\left( {e_{r} + e_{t} + e_{a} + e_{ti} } \right) . $$

(3)

According to the network model, the distance between two CHs in the ith slice and the (i-1)th slice is given by:

$$ l_{i} = \left\{ {\begin{array}{*{20}c} {\tfrac{{r_{i} }}{2}\quad \quad \quad \;\;\,for\;i = 1,2\quad \quad } \\ {\tfrac{{r_{i} - r_{i - 2} }}{2}\quad \quad for\;i = 3,4, \ldots ,N} \\ \end{array} } \right. $$

Now, for given $l_{i}$ and channel model (1), the over-the-air RF energy consumed for receiving one bit, $e_{ri}$, is given as:

$$ e_{ri} = e_{ti} \;L\left( {l_{0} } \right)\left( {\frac{{l_{i} }}{{l_{0} }}} \right)^{ - \eta } \xi . $$

For a Rician fading channel, the link reliability requirement can be expressed as:

$$ \begin{aligned} \delta_{r} & = \Pr \left\{ {e_{ri} \ge \tau } \right\} \\ \,\, = & \Pr \left\{ {\xi \ge \frac{\tau }{{e_{ti} \,L\left( {l_{0} } \right)}}\left( {\frac{{l_{i} }}{{l_{0} }}} \right)^{\eta } } \right\} \\ \,\,\, = & e^{{\frac{ - \tau }{{e_{ti} \,L\left( {l_{0} } \right)}}\left( {\frac{{l_{i} }}{{l_{0} }}} \right)^{\eta } }} \\ \end{aligned} $$

From the above expression, we can express $e_{ti}$ as:

$$ e_{ti} = \frac{ - \tau }{{L\left( {l_{0} } \right)\,\log \delta_{r} }}\left( {\frac{{l_{i} }}{{l_{0} }}} \right)^{\eta } $$

Under shortest path routing, the maximum number of links of an end-to-end path is N (i.e., maximum number of slices). Therefore, to generate the constraint on path reliability, $\delta_{p}$, the minimum link reliability must be:

$$ \delta_{r} = \delta_{p}^{{\tfrac{1}{N}}} $$

Therefore,

$$ e_{ti} = \frac{ - N\tau }{{L\left( {l_{0} } \right)\,\log \delta_{p} }}\left( {\frac{{l_{i} }}{{l_{0} }}} \right)^{\eta } = \beta \,l_{i}^{\eta } $$

where $\beta = \tfrac{ - N\tau }{{L\left( {l_{0} } \right)\,l_{0}^{\eta } \,\log \delta_{p} }}$ and it is a constant. Consequently, the energy consumed by jth CH in the ith slice, given in (3), can be rewritten as:

$$ E_{ij} = \frac{{\left( {R^{2} - r_{i - 1}^{2} } \right)\left( {r_{i} - r_{i - 1} } \right)}}{{2r_{i} }}\rho \,n\left( {e_{r} + e_{t} + e_{a} + \beta \,l_{i}^{\eta } } \right)\, $$

(4)

From (4), the expected energy consumption of a CH in a slice can be approximately represented as a function of cluster radius. Our objective is to determine the optimal radius of a cluster in slices that minimizes the expected energy consumption among all CHs. This optimization problem can be formulated as follows:

$$ \left\{ \begin{aligned} \mathop {\hbox{min} }\limits_{{r_{1} ,r_{2} , \ldots ,r_{N} }} \quad \left\{ {E_{1j} ,\;E_{2j} ,\; \cdots ,E_{Nj} } \right\} \hfill \\ such\;that\quad r_{1} < r_{2} < \cdots < r_{N} = R \hfill \\ \end{aligned} \right. $$

(5)

subject to

$$ \left[ {\pi \left( {\left( {r_{i}^{2} - r_{i - 1}^{2} } \right) + \sum\nolimits_{h = i}^{N} {\left( {r_{h + 1}^{2} - r_{h}^{2} } \right)} } \right)\rho \,n\,\frac{\varphi }{2\pi }} \right] - \pi \sum\nolimits_{h = i - 1}^{N} {\left( {r_{h + 1}^{2} - r_{h}^{2} } \right)} \rho \,n\,\frac{\varphi }{2\pi } = 0\;\forall \,1 \le i \le N $$

(6)

$$ n\,\sum\nolimits_{i = 1}^{N} {\pi \left( {r_{i}^{2} - r_{i - 1}^{2} } \right)\rho \,\frac{\varphi }{2\pi }} = n\,\pi R^{2} \rho \,\frac{\varphi }{2\pi }\quad \forall \,1 \le i \le N $$

(7)

The constraint (6) guarantees inter-cluster flow preservation i.e. all data packets generated at or forwarded to a slice are pushed out of it. The constraint (7) specifies that the sum of all data packets generated at a given time duration in the network is constant. If we examine both the function to be optimized and the constraints given above, we see that its objective function is monomial and the constraints are signomials. Hence, its optimal solution can be found using generalized geometric programming (GGP) as introduced in [10]. Once the radius profile of clusters is obtained by solving the above optimization problem, we can ensure that all CHs deployed in the sensor field deplete their energy at minimum rate and hence, optimal network lifetime is achieved.

It has been observed in the recent past state-of-the-work [11] that, except mitigating energy hole problem, predetermined node deployment shows significant improvement in end-to-end delay, throughput, etc. Motivated by [8, 12], we proposed a predetermined deployment strategy based on Archimedes’ spiral. We have examined different standard geometric models e.g., Gaussian distribution and found Archimedes’ spiral to be one that can be modeled as slice based network architecture because the successive circular turns of Archimedes’ spiral have a constant separation distance. This feature primarily motivates us to consider Archimedes’ spiral as a node distribution function. The detailed features of the said spiral is given in the next section where we have shown how Archimedes’ spiral based node deployment can be mapped or used for ring sector based network architecture.

5 The Clustering Technique

The proposed energy balanced clustering strategy consists of evaluation of optimal cluster radius, MNs/CHs deployment, cluster setup and routing path formation phases. The evaluation of optimal cluster radius and routing path formation are already discussed in Sect. 4 and Sect. 3.2, respectively. In this section, we describe MNs/CHs deployment and cluster setup phases.

5.1 Deployment Phase

In this section, a deployment function based on Archimedes’ spiral is proposed.

5.1.1 Archimedes’ Spiral

A spiral is defined as a curve, which emanates from a central point, getting progressively farther away as it revolves around the point. An Archimedes’ spiral is a continuous spiral [8, 12] with polar equation $R_{d} = \theta \;B$ where $R_{d}$ is the radial distance, $\theta$ is the polar angle and $B$ is a real number whose value is constant. The distance between two successive circular turns can be calculated using the value of $B$. One of the features of the Archimedes’ spiral is that its successive circular turns have a constant separation distance equal to 2πB (Fig. 2)

Fig. 2.

Node distribution function based on Archimedes’ spiral.

5.1.2 Deployment with Discrete Archimedes’ Spiral

As the Archimedes’ spiral is a continuous curve, to use it as a deployment function, it should be transformed into discrete form so that MNs/CHs may be deployed at those discrete locations. We propose the discrete spiral, as in (8) and (9), to be used as the node deployment function.

$$ f\left( {\theta_{k} } \right) = \theta_{k} \,B $$

(8)

where $\theta_{k} \in \left[ {2\left( {k - 1} \right)\pi ,\;2\,k\,\pi } \right]$ for $k = 1, \ldots ,K.$

Now, within the designated range of locations in each circular turn, discrete points need to be identified for deployment. We propose to decompose $\theta_{k}$ for each k into m discrete locations and at each discrete location nodes are deployed. The decomposition of $\theta_{k}$ is given as follows:

$$ \theta_{k} \left( m \right) = \left[ {2\left( {k - 1} \right)\pi + m\,\varphi_{k} } \right] $$

(9)

for $k = 1, \ldots ,K$ and for each k, $m = 1, \ldots ,\tfrac{2\pi }{{\varphi_{k} }}.$ In (9), $\varphi_{k}$ represents the angular gap between two adjacent nodes in kth circular turn as shown in Fig. 2. While deploying the nodes at m discrete locations in each circular turn, we assume that deployment starts at location m = $\tfrac{2\pi }{{\varphi_{k} }}$ and ends at m = 1.

Our objective is to model Archimedes’ spiral as a node deployment function in such a way that it approximately represents the ring sector based network area (Fig. 1). In order to achieve our goal, we propose to decompose the ith slice into multiple regions of size $w_{i} \times w_{i}$, where $w_{i} = r_{i} - r_{i - 1}$. Each of the regions would hold an Archimedes’ spiral. We consider this spiral as a cluster, where point of origin of this spiral is CH. MNs are deployed uniformly at discrete locations in each circular turn.

• The radius $\left( {r^{\prime}_{k} } \right)$ of circular turn (Fig. 2) of proposed Archimedes’ spiral is considered approximately as:

  $$ \tfrac{1}{2}\left[ {2\pi \;k\;B + 2\pi \left( {k + 1} \right)B} \right] = \pi \left( {2k + 1} \right)B $$
  $$ r^{\prime}_{k} = \pi (\,2k + 1)B. $$

  Therefore, the separation distance between two successive circular turns of Archimedes’ spiral is $r^{\prime}_{k} - r^{\prime}_{k - 1} = 2\pi \,B$.

• The relationship between the width of two successive circular turns in the proposed Archimedes’ spiral and $R_{s}$ is $\pi B \le R_{s}$ (Fig. 2).

• For the proposed node deployment function, the number of MNs and CHs deployed in clusters of ith type is ${{\left( {r_{i}^{2} - r_{i - 1}^{2} } \right)\varphi \,\rho } \mathord{\left/ {\vphantom {{\left( {r_{i}^{2} - r_{i - 1}^{2} } \right)\varphi \,\rho } 2}} \right. \kern-0pt} 2}\,$ and ${{r_{i} \,\varphi } \mathord{\left/ {\vphantom {{r_{i} \,\varphi } {\left( {r_{i} - r_{i - 1} } \right)}}} \right. \kern-0pt} {\left( {r_{i} - r_{i - 1} } \right)}}$, respectively. Further, the number of MNs in any cluster is deployed uniformly at discrete locations using a point as the centre where CH is located by controlling the values of $\theta_{k}$ and $\varphi_{k}$, respectively.

Once the optimal cluster radius of each slice is obtained by solving (5)-(7), it is required to know K and $\varphi_{k}$ to implement the deployment scheme. The following lemmas derived K and $\varphi_{k}$ for a given region while maintaining coverage and connectivity.

Lemma 1: For a given region $w_{i} \times w_{i}$, the required number of circular turns (K) should stand in relation with $w_{i}$ as $K \le \left\lceil {{{w_{i} } \mathord{\left/ {\vphantom {{w_{i} } {2\sqrt 2 \,\pi B}}} \right. \kern-0pt} {2\sqrt 2 \,\pi B}}} \right\rceil$, where $B \le {{R_{s} } \mathord{\left/ {\vphantom {{R_{s} } \pi }} \right. \kern-0pt} \pi }$.

Lemma 2: In a given K circular region, for Archimedes’ spiral based node deployment function, the angular gap $\varphi_{k}$ between two adjacent MNs in kth circular turn stands in relation with $R_{s}$ as follows:

$$ \varphi_{k} = 2\;\cos^{ - 1} \left( {\frac{{\left( {f\left( {\theta_{k} } \right)} \right)^{2} + \left( {r^{\prime}_{k} } \right)^{2} - R_{s}^{2} }}{{2\;f\left( {\theta_{k} } \right)\;r^{\prime}_{k} }}} \right). $$

Due to page limitation, the proofs of Lemma 1 and 2 could not be incorporated.

5.2 Cluster Setup Phase

Since the number of clusters in a slice, number of MNs under any cluster and deployment locations are known a priori, no separate algorithm is designed for the CH selection. Once the CH and MNs are deployed in a circular region based on the proposed deployment function, a cluster is formed. In each such region, nodes (i.e., both MN and CH) are deployed using (8) and (9). The CHs are deployed at the origin of each circular region. We claim that the proposed deployment is feasible. As reported in [13], air-dropped deployment in a controllable manner is feasible even in an inaccessible terrain. We propose to compute the optimal cluster radius of each slice and number of nodes in each circular region of the network off-line prior to the actual deployment. At last, the pre-computed nodes are to be dropped (e.g. from helicopter) using a point (i.e., CH) as the centre following the proposed deployment function. Real life applications e.g., precision agriculture [11] implement node deployment using such methods.

6 Performance Evaluation

Performance of the proposed Lifetime Oriented Clustering Structure using Archimedes’ spiral based node deployment (LOCS), reported in Sect. 5 is measured through simulation. Simulation results of LOCS scheme are compared with two existing clustering approaches namely Energy Balanced Clustering Approach (EBCA) [4] and ATC [5]. During simulation of EBCA, CH is deployed at the centre of each cluster and MNs are deployed random uniformly around the CH. On the contrary, during simulation of ATC, CH is deployed at the middle of the square and MNs are deployed at predetermined locations around the CH forming a grid topology.

6.1 Simulation Environment

The evaluation is performed using Matlab 7.0.1 simulator. We model all the three schemes, under both ideal and realistic scenarios. Here, by ideal scenario we mean the scenario considered during theoretical analysis in Sect. 4. On the contrary, in realistic scenario, in addition to ideal scenario we consider a medium access control (MAC) protocol which includes idle/sleep schedule of the nodes. Moreover, in realistic scenario, energy consumption is considered for idle, sleeping and sensing in addition to transmission, reception and fusion. The MAC protocol is implemented by IEEE 802.11 carrier sense multiple access with collision avoidance (CSMA/CA) [14]. This MAC protocol defines two medium access mechanisms viz. distributed coordination function (DCF) and point coordination function. Considering the decentralized nature of WSN, DCF is the considered mechanism while simulating all the schemes. Further, we considered a network area consisting of 6 slices. To bring all the schemes in the same platform, during simulation, we have deployed same number of MNs and clusters in a slice. Extensive simulation is performed with a confidence level of 95 % and average of 200 independent runs is taken while plotting the simulation graphs.

6.2 Simulation Metrics

To evaluate the performance of all the three schemes, energy balance, network lifetime and throughput are considered as performance metrics. In our experiment, energy balance is measured by the parameter energy consumption rate per CH in a slice as given in (4). We define throughput as the amount of data (in terms of bits) received at the sink per unit time and it is measured over a period of 1 s. We conducted three sets of experiments where first set measures energy balancing in the network, second set verifies the enhancement of network lifetime and third set measures the throughput. During simulation, we consider initial energy of a CH and a MN as 50 J and 5 J, respectively. Further, similar to [4], radio and channel models parameters are considered as $e_{t} = 60\,{\text{nJ}}$, $e_{r} = e_{a} = 50\,{\text{nJ}}$, $l_{0} = 10\,\text{m}$, $G_{t} = G_{r} = 1$, $\eta = 4$, τ = 10⁻¹⁷ J, $\delta_{r} = 0.99$, $\omega = 0.125\,\text{m}$ and $R_{f} = 20$ [9]. Finally, similar to [2], we assume $R_{s} = 10\,\text{m}$ and $n = 400\,{\text{bits}}$. Unless, specified otherwise, we use the same parameters with same values of the DCF mechanism as described in [14] during implementation of MAC protocol e.g., queuing delay, saturation point. In plots, scheme names with ‘(R)’ signify performance under realistic scenario and without it under ideal scenario.

6.3 Energy Balance

Figure 3 shows ECR per CH for network consisting of 6 slices. We observe from the plot that the nature of the graph for the LOCS is fairly straight. Further, it is observed that in LOCS, for both ideal and realistic scenarios, the plot is almost constant for all slices. For example, in ideal scenario, ECR per CH is 35.70 μJ/sec whereas in realistic scenario, it is 62.48 μJ/sec. On the contrary, in both EBCA and ATC, it is observed that ECR per CH varies abruptly in different slices. Also, in both the competing schemes, it is observed that CHs in the 1st slice have maximum ECR per CH and CHs in the 6th (farthest) slice have the lowest ECR per CH. This justifies that LOCS is relatively more energy balanced compared to the competing schemes viz. EBCA and ATC. Now, for all the schemes if we compare the results of both scenarios, it is observed that ECR per CH (realistic) in all the cases is higher compared to ECR per CH (ideal). The additional energy usage for realistic scenario is due to the implementation of MAC protocol.

Fig. 3.

Energy consumption rate per CH under ideal and realistic scenarios.

6.4 Network Lifetime

The graphs illustrated in Fig. 4 represent the network lifetime. For ideal scenario, it is observed that the network lifetime of LOCS is 11.57 % and 23.67 % more than that of EBCA and ATC, respectively. On the contrary, for realistic scenario, it is 10.82 % and 19.74 % more than that of EBCA and ATC, respectively. Moreover, in LOCS the flat nature of the plot ensures that in all the slices, network lifetime terminates in more or less the same time as compared to EBCA and ATC. This ensures that energy in LOCS is balanced to a greater extent than both the competent schemes. Now, if we compare the simulation results of network lifetime both for ideal and realistic scenarios, network lifetime is reduced in realistic scenario, as there is additional energy consumption due to the implementation of MAC protocol.

Fig. 4.

Network lifetime under ideal and realistic scenarios.

6.5 Throughput

Figure 5 shows data throughput of LOCS, EBCA and ATC as measured at the sink under the multi-hop benchmark. It is observed from Fig. 5 that for each of the competing schemes’ throughput rises, then becomes steady and finally falls. Nevertheless, in case of LOCS, once the curve becomes steady, it remains more or less steady compared to all the competing schemes. It is due to the fact that in LOCS, nodes are deployed in a more controllable manner compared to the methods used in both EBCA and ATC. The controlled deployment handles the traffic intensity more judiciously than other means of deployment resulting in reducing the possibility of packet collision and congestion. We observed that the performance of average throughput improves over EBCA and ATC by 10.46 %, and 39.32 %, respectively using LOCS.

Fig. 5.

Throughput comparison over simulation running time.

7 Conclusion and Future Work

In this work, we analyzed the problem of network lifetime optimization by balancing energy consumption at different CHs in a clustered WSN. Analysis revealed the cluster radius of each level have significant role in optimization of network lifetime by avoiding energy hole [2]. Considering the results of this analysis, we developed a joint deployment and routing aware optimal clustering strategy. Our proposed optimal clustering strategy considered the deployment of both CH and MN at some predetermined locations. To deploy both CH and MN at some predetermined locations, we identified Archimedes’ spiral, based on which a deployment function is proposed for distributing MN and CH. Simulation results clearly demonstrate our strategy’s dominance over the existing two competing clustering strategies [4, 5] in terms of all the three performance metrics viz. energy balance, network lifetime and throughput. In future, the proposed clustering strategy may be made more realistic by considering 3-D environment.