Keywords

1 Introduction

WSNs are extensively used in a wide variety of both indoor as well as outdoor applications. WSNs consist of many tiny sensor nodes in which each individual sensor node senses the useful information from its proximity and sends it to the base station. This individual sensing operation of sensor nodes was very inefficient as a large amount of node energy get dissipated in sensing and transmitting the information individually. WSN clustering was introduced as a solution to this problem [1]. In WSN clustering a group of sensor nodes forms a cluster with each cluster assigned a CH. In WSN clustering an individual sensor node senses the information and transmits the sensed information to its respective CH. The CH aggregates the information from all the sensor nodes and finally transmits the sensed information to the sink. A bottleneck with WSN clusters is that they are battery operated and have limited network lifetime. Since a WSN is connected therefore entire network structure may get disconnected on the death of a CH.

Since a CH have an additional load of receiving and transmitting the sensed data assigned to it, it is equipped with some extra energy to ensure its long-run operation. The extra energy equipped CH is termed as a gateway. Gateways are a crucial component in the structural hierarchy of a WSN but unfortunately, gateways are also battery operated. The entire cluster will die as soon as a gateway is dead. Since gateways have limited battery lifetime, its battery should be consumed in the most efficient manner. Achieving an energy efficient WSN and extending the lifetime of a gateway is an NP-hard problem.

In the past, energy conservation in WSN is considered to be an optimization problem and solved using nature-inspired techniques like genetic algorithm [2, 3], particle swarm optimization [4] etc. Work done by most researchers in the past focus on optimizing the transmission distance between a gateway and a sink to minimize the energy dissipation but no work in the past have considered the transmission distance between a sensor node and a gateway which is a very important factor in energy dissipation of a WSN. To the best of our knowledge this is the first work that focuses on 3 crucial factors in minimizing the energy dissipation (i) Minimize the transmission distance between a gateway and a sink \( (\theta ) \); (ii) minimize the transmission distance between a sensor node and a gateway \( (\varPhi ) \); (iii) minimize the total energy dissipated by a gateway. The proposed algorithm minimizes the above 3 novel parameters using a new nature inspired algorithm BBO [5].

BBO has given good results in many applications like face reorganization [6], remote sensing [7], and travelling tournament problem [8] which encourage the use of BBO to optimize the WSN performance with novel parameters. The BBO-C improves the lifetime of a gateway. BBO-C is compared with PSO clustering [4], GA clustering [3], GLBCA [8], LDC [19]. Related work is presented in Sect. 2. The problem formulation and system model are explained in Sects. 3 and 4 respectively. The proposed BBO-C and the experimental results are presented in Sects. 5 and 6 respectively.

2 Related Work

A lot of work has been done in the past to improve the network lifetime of a WSN. Authors in [8] proposed a clustering algorithm in which a breadth-first tree is used to find the gateway which is least loaded and then sensor node is assigned to that gateway. One big problem with this algorithm is it took a large amount of memory space to store and process BFS. Also execution time while calculating BFS is large. It has a time complexity of the order O (mn 2). In [3], load balancing algorithm of WSN is presented which minimizes the standard deviation of load assigned to the CHs to obtain a load balanced WSN. Authors in [9] presented a fuzzy based clustering algorithm is which 3 fuzzy variables are chosen as node energy, concentration and centrality. This approach suffer a major drawback as it only chose one CH during the clustering process whereas transmission of data, data aggregation and forwarding requires multiple CHs in a WSN scenario. Another fuzzy based WSN routing approach was used in [10]. Authors minimize the energy dissipated in the network but did not consider cluster head to cluster head distance which is a very important parameter in a WSN routing an clustering. Ignoring CH to CH distance may lead to imbalanced CH distribution among the entire network.

Authors in [11] proposed a energy efficient dynamic clustering approach which minimizes the energy consumption in the network by considering only one parameter node’s centrality. Authors in [11] did not consider crucial parameters like transmission distance, load of CH, uniform sensor deployment which are important contributing factors in WSN performance. Authors in [12] presented a Distance-Based Residual Energy-Efficient Stable Election Protocol (DRESEP) to achieve a energy efficient WSN. It was an improvement on LEACH algorithm. The basic issue with LEACH was that it chooses CHs on a random basis and a node with low residual energy could become a cluster head resulting in early death of the CH. Early CH death may lead to the disconnection of entire network. DRESEP addressed this problem and chose CH based on the nodes having the maximum residual energy. This approach proved to be successful as it considerably improved the network life but DRESEP does not say anything about the stability and load balancing of a WSN due to which the first CH in DRESEP dies very quickly. Authors in [13] proposed SEECP which was an improvement of DRESEP. In SEECP CHs were chosen in such a way that load is balanced along the nodes and SEECP was successful in obtaining a LOAD balanced and energy efficient WSN. Another routing algorithm is proposed in [8] where authors have presented an algorithm to minimize the communication distance between a CH to another CH using GA. Authors in [14] present a novel algorithm to minimize the distance between a CH and the sink using GA. In both [14, 15] only the transmission distance between CH and sink is emphasized upon. There is no mention of the communication distance between a sensor node to the CH. Authors in [16] used roulette wheel selection for energy efficient routing process. The roulette wheel selection is used to select a set of candidate solution and the fitness function is optimized using GA. In [4] a particle swarm optimization based clustering is proposed to enhance the lifetime of a wireless cluster. They consider network lifetime and CH to sink distance as their fitness function parameters and obtain an energy efficient network using PSO. Unfortunately works in [4] also did not consider sensor node to CH distance and the energy dissipated by the CH. The proposed algorithm uses BBO to minimize all 3 crucial WSN parameters namely sensor node to gateway distance, gateway to sink distance and gateway energy dissipation to achieve a stable and energy efficient network with prolonged lifetime.

3 Problem Formulation

Gateways in a WSN are battery operated and can work as long as the gateway battery is alive. In order to improve the network lifetime of a WSN, battery lifetime of the gateways need to be maximized. Past research works have proved that the battery life of a gateway varies inversely with the increase in sensor nodes in a WSN. A possible solution to this issue is to increase the gateway count in the network so that the increased number of gateways may be able to share the network load.

However, this approach also has a limitation since an increase in gateway count in a network will increase the total network energy dissipation as well (Eqs. 1 and 2). Some of the terminologies used in problem formulation are given in Tables 1 and 2.

Table 1. Terminologies used in the paper 
Full size table
Table 2. Terminologies used in the paper
Full size table
$$ L_{WSN} \, \alpha \,Life_{gat} $$
(1)
$$ Life_{gat} \frac{1}{\alpha } Ener_{gat} $$
(2)

We have

$$ \beta = \sqrt {(N_{x} - gat_{x} )^{2} + \left( {N_{y} - gat_{y} } \right)^{2} } 1 < i,j < N $$
(3)
(4)

Let \( D_{i,j} \) be a decision variable that assign S to G in a WSN

$$ D_{i,j} = \left\{ {\begin{array}{*{20}c} 1 & {if\,sensor\, node\, N_{i} \,is\, assigned \,to\, gateway \,gat_{j} \,\,1 < i < N,\,1 < j < N,} \\ 0 & {otherwise} \\ \end{array} } \right. $$
(5)

We can formulate the objective function as nonlinear programming.

$$ {\text{Maximize}}\,{\text{X}}\, = \frac{{Life_{WSN} }}{\varPhi } + \frac{{Life_{WSN} }}{\theta } $$
(6)

Subject to constraint

$$ \mathop \sum \limits_{\begin{aligned} j = 1 \hfill \\ \end{aligned} }^{N} (\mathop \sum \limits_{i = 1}^{N} D_{i,j} > 1) = G,\quad 1 < i,j < N $$
(7)
$$ \mathop \sum \limits_{\begin{aligned} j = 1 \hfill \\ \end{aligned} }^{N} D_{i,j} = 1,\quad 1 < i,j < N $$
(8)

In BBO-C, the objective function (Eqs. 6–8) is maximized using BBO. BBO-C make sure that entire deployment region is covered with adequate sensor nodes and also maximizes the network lifetime.

4 System Model and the Terminologies Used

For the sake of fair comparison, we use the similar system model as used in [4]. We use multipath fading (mp) and free space (fs) channels for data transmission. The condition for the data transmission is given in Eqs. 9 and 10 respectively. Here \( {\text{E}}_{\text{tr}} \) is the energy consumed in transmission of an m-bit message and \( {\text{E}}_{\text{el }} \) is the energy dissipated in electronics in the model. \( {\text{K}}_{\text{diss}} \) is the dissipation constant. \( {\text{E}}_{\text{amp }} \) is the amplifier for transmission.

$$ E_{tr} = E_{el} * K_{diss} + E_{amp } * K_{diss} * d^{2 } \;\;for\;\;d < d_{0} $$
(9)
$$ E_{tr} = E_{el} * K_{diss} + E_{amp } * K_{diss} * d^{4 } \;\;for\;\;d > d_{0} $$
(10)

\( E_{rec} \) is the energy consumed in receiving a m bit packet which is given by Eq. 11

$$ E_{rec} = E_{el} * K_{diss} $$
(11)

5 Proposed Algorithm

5.1 Overview of BBO

BBO is an evolutionary algorithm that takes inspiration from bio diversity of species and converges to the optimum solution [17]. In BBO an individual is represented by a habitat. A population may contain many habitats like chromosomes in genetic algorithms. For each habitat in the population, habitat suitability index (HSI) value is calculated. A habitat having high HSI value is considered to have higher fitness and more suitable for a population to grow and vice versa for habitat having low HSI value [16, 18]. Based on this HSI value rank of each individual is calculated. Migration operation is based on immigration rate \( (\lambda_{i} ) \) and emigration rate \( (\mu_{i} ) \) as shown in Eqs. 12 and 13 respectively.

$$ \lambda_{i} = I *\left( {1 - \frac{{k_{i} }}{n}} \right) $$
(12)
$$ \upmu_{i} = E *\left( {\frac{{k_{i} }}{n}} \right) $$
(13)

Here \( I \) and \( E \) are the maximum immigration rate and emigration rate of an individual. \( k_{i} \) is the rank of a habitat. n is the size of the population. A habitat having high HSI value will emigrate its suitability index variables (SIVs) to habitat having low HSI value and habitat having low HSI value will immigrate SIVs from habitat having high HSI value [19, 20]. Probabilistic mutation is performed based on Eq. 14.

$$ m_{i} = m_{max} * $$
(14)

Here \( m_{i} \) is the mutation probability, \( m_{max} \) is the maximum \( m_{i} \), \( p_{i} \) Is the prior probability of existence of a solution. The algorithm stops after achieving the optimum solution.

5.2 Implementation of BBO

To initialize the algorithm, all the sensor nodes and gateways are randomly distributed in the deployment area. The performance of a WSN is measured in terms of its network lifetime and CH energy dissipation. In the proposed algorithm we use BBO based energy efficient clustering to minimize the energy dissipation in the network and extend the operational lifetime of a WSN. Communication distances through which a sensor node or a CH sends data to the sink have a direct impact on the energy dissipated and network lifetime of a WSN. Lesser the communication distance less will be the energy dissipated by the CHs to transmit information to the sink. Therefore in the proposed clustering is done in such a way that clusters with optimum transmission distance are formed which minimize the communication distance and energy dissipated by CH in a WSN.

5.3 Calculation of HSI

For each habitat, we calculate HSI which defines the goodness of a solution. As explained earlier minimization of transmission distance and CH dissipated energy are two crucial WSN performance parameters. HSI is defined in such a way that each sensor node is assigned to its optimum CH and only those nodes are chosen as CH which dissipate minimum energy, ensuring the long run operation of the CHs. Precisely, HSI depends minimizing the sum of all \( \theta \),sum of all \( \varPhi \) and minimizing total energy dissipated by the gateways. HSI is calculated in Eq. 15.

(15)

5.4 Migration

By minimizing the fitness function given in Eq. 15 we achieve a network which is stable and has an improved network lifetime due to minimizing energy dissipation.

After calculation of the HSI each habitat is ranked in descending order of their HSI value. Based on the rank of each habitat vector their Immigration \( (\lambda ) \) and emigration rates (µ) are calculated using Eqs. 12 and 13. The entire migration operation is performed using MPX crossover.

5.4.1 MPX Crossover

MPX crossover (Table 3) is used in migration step. In MPX crossover we generate a random vector of 0’s and 1’s. If an entry in the random vector is 1, choose an SIV/CH from immigrating habitat else choose a CH from emigrating habitat.

Table 3. MPX crossover to obtain a modified vector.
Full size table

5.5 Mutation

Mutation operator is performed to randomly modify the solution coming from migration step. The solution is modified from a random gene position in a habitat. Mutation step is an important part of the algorithm framework as it maintains diversity in the population. The solution is mutated as per Eq. 14 [22].

The BBO clustering algorithm is run until the optimum solution is obtained or the maximum numbers of iterations are elapsed. The Pseudo code for the proposed algorithm is given below.

figure a

6 Results

Results are compared with PSO based clustering [4], GLBCA [8], GA [3] and LDC [19]. The simulation parameters used are shown in Table 4. For the evaluation of results, we consider two scenarios in which the base station is placed at coordinates (500, 250) and (250, 250) respectively.

Table 4. Simulation parameters.
Full size table

Scenario 1 – Sink at (500, 250)

The proposed algorithm is compared with the existing works in terms of network lifetime of sensor nodes as presented in Figs. 1 and 2 respectively. As visible from Figs. 1 and 2 respectively, network lifetime of sensor nodes is considerably increased in BBO-C. This is because BBO-C performs clustering in such a way that every sensor node is able to find its optimum location with respect to the gateway which results in a reduction of total network energy dissipation by minimizing \( \theta \) and \( \varPhi \). BBO-C performs better than the existing works for packets sent to the sink as shown in Fig. 3.

Fig. 1.
figure 1

Network lifetime comparison for 60 gateways

Full size image
Fig. 2.
figure 2

Network lifetime comparison for 90 gateways.

Full size image
Fig. 3.
figure 3

Comparison of packets sent to sink.

Full size image

Scenario 2 – Sink at (250, 250)

The proposed algorithm is compared with the existing works in terms of network lifetime and packets sent for new sink location. The comparison of the proposed algorithm with the existing works is shown in Figs. 4, 5 and 6 respectively.

Fig. 4.
figure 4

Network lifetime comparison for 60 gateways.

Full size image
Fig. 5.
figure 5

Network lifetime comparison for 90 gateways

Full size image
Fig. 6.
figure 6

Comparison of packets sent to sink.

Full size image

7 Conclusion

In this paper a new nature inspired algorithm BBO is presented to achieve energy efficient clustering in WSN. A dynamic and effective fitness function is used to achieve enhanced network performance. Minimization of the communication distance and maximizing the residual energy improves the network lifetime. Maximizing the network lifetime by minimizing the energy dissipation and the communication distance is solved as an optimization problem using BBO. The cluster thus formed dissipates less energy and improves the network lifetime of a WSN. BBO based clustering outperform many past algorithms like PSO, GLBCA, GA and LDC by 38.2%, 53.6%, 58.8% and 62.2% respectively.