PSO-based approach for energy-efficient and energy-balanced routing and clustering in wireless sensor networks

Abstract

Many schemes have been proposed for energy-efficient routing in wireless sensor networks (WSNs). However, most of these algorithms focus only on energy efficiency in which each node finds a shortest path to the base station (BS), but remain silent about energy balancing which is equally important to prolong the network lifetime. In this paper, we propose particle swarm optimization-based routing and clustering algorithms for WSNs. The routing algorithm builds a trade-off between energy efficiency and energy balancing, whereas the clustering algorithm takes care of the energy consumption of gateways as well as sensor nodes. We develop an efficient particle-encoding scheme and derive a multi-objective fitness function for each of the proposed routing and clustering algorithms. The algorithms are also capable of tolerating the failure of cluster heads. We perform extensive simulations on the proposed schemes and the results are compared with the existing algorithms to demonstrate their superiority in terms of various performance metrics.

1 Introduction

1.1 Background

Energy conservation of the sensor nodes is the main challenge in deploying wireless sensor networks (WSNs) as the sensor nodes operate on limited and usually irreplaceable battery power (Akyildiz et al. 2002). Many schemes (Lattanzi et al. 2007; Anastasi et al. 2009; Li et al. 2013) have been developed for energy saving of the sensor nodes. However, clustering is the most efficient scheme in this regard (Abbasi and Younis 2007; Kuila and Jana 2014c). In a cluster-based WSN, sensor nodes are divided into distinct groups called clusters. Each sensor node belongs to a single cluster and sends its data to a leader node called cluster head (CH). Some researchers (Azharuddin and Jana 2015a; Azharuddin et al. 2015; Kuila and Jana 2014a, c) have proposed the use of some special nodes called gateways or relay nodes that act as CHs. These gateways are provisioned with extra energy. However, the gateways are also power constraint since they are also battery operated. Therefore, energy conservation of the gateways is also very crucial for the long operation of the WSNs. Many energy-efficient clustering algorithms (Kuila et al. 2013; Low et al. 2008; Bari et al. 2008; Gupta and Younis 2003) have been proposed in this regard. However, none of the algorithms have considered routing load of CHs during cluster formation. Since a substantial amount of energy of CHs is consumed during forwarding of data packets of other CHs to the base station (BS), therefore it is also necessary to minimize the energy consumption of CHs to make the clustering technique more energy efficient.

Many energy-efficient routing algorithms (Bara and Khalil 2012; Kuila and Jana 2014b; Gupta et al. 2013) have been proposed in which attempt is made to find a routing path to the BS, so that the total energy consumption by the gateways is minimized. However, these routing algorithms suffer from energy imbalancing in the network as they follow a static optimal path. As a result, some gateways on the path deplete their energy quickly and can die soon. Therefore, the energy balancing of the gateways in the routing is a vital factor for long operation of the WSN. By energy balancing, we mean that the routing algorithm can select a path so that the gateways consume their energy evenly. However, to incorporate such energy balancing of the gateways the chosen path may be longer to connect the BS. Hence, a trade-off between energy efficiency and energy balancing is indeed a vital issue in designing an efficient routing algorithm. Moreover, the sensor nodes are very prone to failure as they are deployed in harsh environment. Particularly, the failure of CHs disrupts the communication with their member sensor nodes as well as the other CHs. Therefore, clustering and routing algorithms need to be fault tolerant.

In this paper, we address the following problems.

• 1. Fault-tolerant routing with a trade-off between energy efficiency and energy balancing of the gateways.

• 2. Energy-efficient clustering with fault tolerance of the gateways.

Note that the computational complexity of formation of clusters and finding the optimal routes for a large-scale WSNs is very high by a brute force approach (Kuila and Jana 2014b). Therefore, a meta-heuristic approach such as PSO (Kennedy et al. 1995) is highly desirable to achieve a fast and efficient solution of the above clustering and routing problems. Note that, there are some other meta-heuristic approaches to solve the optimization problems such as genetic algorithm (GA), ant colony optimization (ACO), differential evolution (DE). However, the PSO has the following advantages over these algorithms (Kulkarni and Venayagamoorthy 2011). (1) It is very easy to implement on hardware as well as software; (2) it produces high quality of solutions due to its availability to escape from local optima; (3) it converges very quickly than the other meta-heuristic approach. In this paper, our goal is to design energy-efficient and energy-balanced clustering and routing algorithms for WSNs. The algorithm considers the energy consumption of the gateways as well as sensor nodes to prolong the network life time and fault tolerance aspect of the CHs.

1.2 Our contribution

In this paper, we propose a PSO-based routing and clustering algorithm. The routing algorithm builds a trade-off between energy efficiency and energy balancing. The clustering algorithm takes care the energy consumption of gateways by considering their routing load and energy consumption of the sensor nodes. We present efficient particle-encoding schemes for both the algorithms. We show derivation of the fitness function for the proposed algorithms by considering several parameters including average energy needed to transmit a data packet, standard deviation of remaining energy of the path and average remaining energy of the path for all the gateways. We also present an NLP formulation for the routing and clustering problems. We show that the proposed algorithms offer distributed runtime recovery of the sensors as well as gateways due to failure of some CHs.

We perform extensive experiments on the proposed algorithms through simulation run and compare the results with a PSO-based approach namely (Kuila and Jana 2014b), GLBCA, a clustering algorithm by Low et al. (2008), GALBCA, a GA-based clustering proposed by Kuila et al. (2013) and LDC, leach distance clustering by Bari et al. (2008).

Recently, Kuila and Jana (2014b) have also proposed a PSO-based clustering and routing algorithm. The authors in this work, have selected an energy-efficient path by making a trade-off between transmission distance and number of data forwards needed in the routing phase. However, the selected path is energy efficient, but it is not energy balanced because the path remains static throughout the network lifetime. Thus, some CHs faced the problem of heavy routing load and may deplete their energy soon due to transmission of large amount of routing data through them. Thereafter, the authors have formed the clusters by considering routing over head of the CHs for the selected path and assigned least number of sensor nodes to the heavily loaded CHs for balancing the energy consumption of the CHs in the clustering phase. Although, this may slightly reduce the uneven energy consumption problem of the heavily loaded CHs but this should be taken care in the routing phase also which they have not considered. Therefore, the following differences and advantages over the algorithms in Kuila and Jana (2014b) can be noted as follows.

• 1. The proposed algorithm considers energy efficiency as well as energy balancing of the gateways in the routing phase, whereas the algorithm in Kuila and Jana (2014b) considers only the energy efficiency of the gateways and no energy balancing is addressed in the routing phase.

• 2. The proposed algorithms use normalized parameters in their fitness function to give equal weight to the parameters. However, the parameters used in the fitness function in Kuila and Jana (2014b) are not normalized. Therefore, there is always dominance of one parameter over the others in their algorithm and affect the results.

• 3. The routing algorithm (Kuila and Jana 2014b) finds a static route from all the CHs to the BS for the entire network operation. On the other hand, the path selected by our proposed algorithm is not fixed rather changes after every setup phase as we consider energy balancing of the gateways.

• 4. We consider the fault tolerance issues in both routing and clustering in contrast to Kuila and Jana (2014b) which does not consider any fault tolerance in each of the routing and clustering algorithms.

By simulation results we show that our proposed algorithm outperform the algorithms proposed in Kuila and Jana (2014b) in many aspects.

The rest of the paper is organized as follows. The related work is presented in Sect. 2. The system model and basic phases are described in Sect. 3 which includes energy model and network model. The basic terminologies are described in Sect. 4. The proposed PSO-based routing and PSO-based clustering algorithms are discussed in Sects. 5 and 6, respectively. The simulation results are presented in Sect. 7 and we conclude in Sect. 8.

2 Related works

A rich literature is available on clustering and routing algorithms for WSNs. However, we present and categorize them related to our work. For each category, first clustering is discussed followed by routing algorithms.

2.1 Heuristic-based clustering and routing

There is ample number of clustering algorithms developed for WSNs (Abbasi and Younis 2007; Chaurasiya et al. 2012; Gupta and Younis 2003; Kuila and Jana 2012, 2014a; Low et al. 2008; Mehra et al. 2015). In Low et al. (2008), the authors have proposed a load balancing clustering algorithm by using a breadth-first search (BFS) tree of the sensor nodes. For n sensor nodes and m CHs, its time complexity is $O (mn^{2})$ which is very high for a large scale WSN. Moreover, it takes significant amount of memory space. Kuila and Jana (2014a) have improved the algorithm Low et al. (2008) by proposing a new load-balanced clustering algorithm having time complexity of $O (n \text { log } n)$. The authors in Gupta and Younis (2003) have proposed a clustering algorithm called LBC, which takes $O(mn \text { log } n)$ time in the worst case. In all the above algorithms, the main focus was to balance the sensor load of the CHs while forming clusters. However, they have not considered the energy balancing of the CHs and the sensor nodes. They have also not considered the fault tolerance of CHs. An energy-efficient load-balanced clustering algorithm (EELBCA) have proposed in Kuila and Jana (2012) with $O(n \text { log } m)$ time. However, the algorithm does not consider residual energy of the sensor nodes and fault-tolerant issue. In Chaurasiya et al. (2012), the authors have proposed an energy-balanced clustering algorithm for enhancing lifetime of WSN. The algorithm divide the target area into a number of clusters and the cluster heads are chosen based on the relative position of the nodes and their residual energy. A self organized load balancing clustering protocol has been proposed in Mehra et al. (2015) which effectively increases the network lifetime. However, both the algorithms Chaurasiya et al. (2012), Mehra et al. (2015) have not considered the fault-tolerant issue. In Azharuddin et al. (2013), we have proposed a fault tolerance clustering algorithm. However, the algorithm does not deal with the residual energy of sensor nodes, and load as well as energy balancing of CHs.

Many routing algorithms have been proposed in WSNs, the survey of which can be found in Akkaya and Younis (2005). Low-energy adaptive cluster hierarchy (LEACH) Heinzelman et al. (2002) is a well-known algorithm that dynamically rotates the work load of the CHs among the sensor nodes for the purpose of load balancing. However, its main demerit is that a node with very low energy may be selected as a CH and thus it can quickly die. Moreover, the CHs transmit their data directly to the BS via single hop communication which is not desirable for balancing the energy consumption of CH and this leads to quick death of a CH. Many algorithms improve the performance of LEACH which can be found in Gupta and Pandey (2014), Tyagi and Kumar (2013), but they have also not considered the fault-tolerant issue. There are some algorithms (Xue-feng and La-yuan 2011; Yessad et al. 2012; Yang et al. 2012) which consider the energy balancing issue of WSN. In Yessad et al. (2012), the authors have proposed a multipath routing protocol for balancing the energy consumption of the nodes for homogeneous WSN. The path is chosen based on some probability considering residual energy, communication energy cost and the number of paths. However, the algorithm is not suitable for large scale network. The authors in Yang et al. (2012), proposed an uneven clustering topology control strategy on the basis of minimum hop of the nodes to solve the energy hole problem. The performance of LEACH and PEGASIS are analyzed theoretically as well as simulation in Xue-feng and La-yuan (2011).

A few routing algorithms (Djukic and Valaee 2006; Intanagonwiwat et al. 2000) have been reported which consider fault-tolerant issues. Direct diffusion (DD) (Intanagonwiwat et al. 2000) routing protocol is most popular among them. DD is a multipath routing protocol based on query driven data delivery. In DD, multiple node disjoint paths are created between source nodes and the BS. However, DD cannot be used for the applications which require continuous data delivery as it is based on query driven. Moreover, this protocol is not energy efficient as it broadcasts a low rate interest message periodically and it is not suitable for large-scale networks. Another fault-tolerant routing algorithm is erasure coding (Djukic and Valaee 2006) in which source node decodes each data packet of size bM bits into M fragments each of size b and generates another K coding fragments to have in total a set of $M + K$ fragments and sends it over n multiple paths. The drawback of this protocol is that performance becomes worst when packet loss condition is very high and therefore, it may not be applicable for large-scale network. Recently the authors in Magán-Carrión et al. (2015) have proposed algorithms for anomaly detection and data loss/modification identification and recovery in WSNs using multivariate analysis. The authors have tested their missing data recovery algorithm under several routing algorithms and demonstrated that the underlying routing algorithm has a clear influence in the recovery performance. Recently we have also proposed some fault tolerance algorithms which can be found in Azharuddin et al. (2015), Azharuddin and Jana (2015a), Azharuddin and Jana (2015b). A brief review on various fault-tolerant algorithms for WSNs can be found in Chouikhi et al. (2015).

2.2 Soft computin-based clustering and routing

Many soft computing-based approaches have been developed for clustering and routing in WSNs. Kuila et al. (2013) have proposed a GA-based load-balanced clustering algorithm for WSNs and it works for both equal and unequal load of sensor nodes. The algorithm has faster convergence and better load balancing than the traditional GA (Goldberg 1989). However, the major demerit of this algorithm is that CHs communicate directly with the BS which is impractical for large area networks. Moreover, the algorithm does not consider the residual energy of sensor nodes and gateways during cluster formation. Chakraborty et al. (2012) have presented a differential evolution-based routing algorithm for more than thousand relay nodes such that the energy consumption of the maximum energy-consuming relay node is minimized. However, the authors do not take care of the cluster formation. Some improper clustering may lead to serious energy inefficiency of the relay nodes. Singh and Lobiyal (2012) have used the PSO for CH selection among the normal sensor nodes and do not take care of the cluster formation. PSO and ant colony optimization (ACO) are used in WSNs for other optimization problems also and they can be found in Kulkarni and Venayagamoorthy (2011), Saleem et al. (2011), Zungeru et al. (2012). The authors in Bari et al. (2009) have proposed a GA-based routing algorithm where the fitness function is defined by the network lifetime only. Gupta et al. (2013) have also proposed GA-based routing algorithm called GAR, which minimizes the overall communication distance from the gateways to the BS. However, both these algorithms (Bari et al. 2009; Gupta et al. 2013) consider the only routing of aggregated data from the gateways to the BS without considering data communication from the sensor nodes to the gateways within each cluster. Moreover, all the algorithms (Chakraborty et al. 2012; Kuila et al. 2013) do not consider the fault-tolerant issue. Furthermore, it is worth nothing that, most of algorithms (Bari et al. 2009; Gupta et al. 2013; Gupta and Younis 2003; Kuila and Jana 2014b) focus on energy efficiency only and none of the above algorithms consider the energy efficiency and energy balancing simultaneously. Moreover, none of the above algorithms consider the fault-tolerant issue in routing as well as in clustering phase. To the best of our knowledge, there are no routing and clustering algorithms for large-scale WSNs which consider energy efficiency and energy balancing with the fault-tolerant issue using particle swarm optimization approach.

3 System models and basic phases

3.1 Network model

We consider a WSN model which is partial heterogeneous in nature with two types of nodes, i.e., normal sensor nodes and higher energy provisioned gateways. Normal sensor nodes are responsible for sensing local data and send it to their respective gateways, whereas gateways receive the data from their member sensor nodes, aggregate the received data and forward them to their next-hop gateways toward the BS. All the gateways act as CHs in the network. Nodes can be deployed manually or randomly into the target area. However, all the sensor nodes and gateways become stationary after deployment. A sensor node can join to a gateway if it is within the communication range of the sensor node. Gateways are capable of long-haul communication compared to sensor nodes. All the communications are over wireless links which are established between two nodes only if they are within communication range of each other. We also assume that wireless links are symmetric, so that a node can compute the approximate distance to another node based on received signal strength as proposed in Banerjee et al. (2014), Baronti et al. (2007), Xu et al. (2010). Current implementation supports TDMA ( Association IS 2001) to provide MAC layer communication. Gateways use CSMA/CA MAC protocol to communicate with base station ( Association IS 2001; Baronti et al. 2007). Moreover, we use the same radio model for energy consumption as described in Heinzelman et al. (2002).

3.2 Basic phases

At the beginning, each sensor node and gateway undergoes bootstrapping process in which the BS assigns unique IDs to all of them. After that the sensor nodes and the gateways broadcast their IDs using CSMA/CA MAC layer protocol. Therefore, each gateway can collect the IDs of the all sensor nodes and the gateways which are within maximum communication range of sensor nodes and gateways respectively. Finally, each gateway sends this local network information to the BS.

This is followed by network setup which consists of a setup phase followed by the steady-state phase, and it is shown in Fig. 1. The setup is again divided into route setup and clustering. After receiving the local network information, the BS first builds a hop tree where each gateway is assigned a hop value which is used to set up the route. After that, the BS first executes the routing algorithm to setup the next hop CH for each CH and then the cluster is formed by using the final route setup. When the routing and clustering phase is over, all the CHs are informed about their next hop CH toward the BS and their hop value. Moreover, all the sensor nodes are also informed about the ID of the CH to which the sensor nodes have assigned. The steady-state phase is composed of some pre-specified rounds, say 50 or 75 rounds (Heinzelman et al. 2002). In each round, the gateways receive the sensed data from the cluster members and aggregate them to transfer it to the BS. Setup and steady-state phases are repeated (see Fig. 1) until all the gateways become inactive or die. The CHs provide a TDMA schedule to their member sensor nodes for intracluster communication and use slotted CSMA/CA MAC ( Association IS 2001) protocol to communicate with its next hop CH. Now, we present our proposed (1) routing and (2) clustering algorithms as follows.

Fig. 1

Network setup

4 Basic terminologies

The following terminologies are used to develop the proposed algorithm.

• 1. A set of sensor nodes denoted by $S=\{s_{1},s_{2},s_{3}, \dots ,s_{n}\}$.

• 2. The set of gateways is denoted by $\xi =\{g_{1},g_{2},g_{3}, \dots ,g_{m}\}$ and $g_{m+1}$ indicates the base station (BS), $n > m$ .

• 3. $d_{max}$ and $R_{s}$ denote the maximum communication range of the gateways and sensor nodes, respectively

• 4. $E_{r}(g_{i})$ denotes the remaining residual energy of $g_{i}$.

• 5. $dis(g_{i}, g_{j})$ denotes the distance between $g_{i}$ and $g_{j}$.

• 6. $ComCH(s_{i})$ is the set of gateways which are within maximum communication range of $s_{i}$, i.e., $R_{s}$ of sensor node $s_{i}$. In other words,

  $$\begin{aligned} ComCH(s_{i})=\{g_{j}|dis(s_{i}, g_{j})\le R_{s} \wedge \forall g_{j}\in \xi \} \end{aligned}$$

  (1)

  Therefore, $s_{i}$ can be assigned to any one of the gateway from $ComCH(s_{i})$, where $ComCH(s_{i})\subseteq \xi$.

• 7. $Com(g_{i}):$ The set of gateways, which are within communication range of $g_{i}$. The BS may also be a member of $Com(g_{i})$. In other words,

  $$\begin{aligned} Com(g_{i})=\{g_{j}| \forall g_{j}\in \{\xi +g_{m+1}\} \wedge dis(g_{i}, g_{j})\le d_{max}\} \nonumber \\ \end{aligned}$$

  (2)

• 8. $Next\_Hop\_G((g_{i}):$ It is the set of gateways which can be selected as a next hop gateway of $g_{i}$. The next hop gateway must be toward the BS. Therefore,

  $$\begin{aligned}&Next\_Hop\_G((g_{i}) = \{g_{j}|\forall g_{j}\in Com(g_{i})\nonumber \\&\quad \wedge \,dis(g_{j}, g_{m+1})\le dis(g_{i}, g_{m+1})\} \end{aligned}$$

  (3)

• 9. $Next\_Hop(g_{i})$ is the gateway $g_{j}, g_{j} \in Next\_Hop\_G(g_{i})$ which is selected as next-hop gateway by $g_{i}$ toward BS in data routing phase. Here, the next hop gateway may be the BS if the BS is within communication range of $g_{i}$.

Depending upon the energy consumption of gateways due to transmission of data and available energy of the gateways in the path selected by the proposed algorithm (discuss later), we define some terminologies.

Definition 1

(ENTD and Avg_ENTD) Energy needed to transmit data by a CH $g_{i}$ denoted by ${ENTD}(g_{i})$ is the amount of energy needed to transmit a single data packet to its next-hop CH. Mathematically,

$$\begin{aligned} ENTD(g_{i})=E_{T}(g_{i}, Next\_Hop(g_{i})) \end{aligned}$$

(4)

where $E_{T} ()$ represents the energy consumption due to transmission of data.

Normalization of ENTD: The ENTD is normalized to adjust its value in the range [0, 1]. The purpose of normalization is to adjust the value measured on different scales into a common scale, so that there will be an equal impact when multiple objectives are superposed (The details are discussed in Sects. 5.2 and 6.2). Suppose, $E_{max}$ and $E_{min}$ be the maximum and minimum energy consumption due to transmission of single data packet in the network. Therefore, ENTD of $g_{i}$ can be written in normalized form as follows.

$$\begin{aligned} Norm.\_ENTD(g_{i})=\dfrac{{ENTD}(g_{i})-E_{min}}{E_{max}-E_{min}} \end{aligned}$$

(5)

Therefore, total ENTD for all the gateways in normalized form can be written as follows.

$$\begin{aligned} {Total}\_{ENTD}=\sum _{i=1}^{m}{{Norm}.\_{ENTD}(g_{i})}, \quad \forall g_{i}\in \xi \end{aligned}$$

(6)

The average energy needed to transmit data $(Avg\_ENTD)$ in normalized form is given by

$$\begin{aligned} {Avg}\_{ENTD}= & {} \dfrac{{Total}\_{ENTD}}{m}\nonumber \\= & {} \dfrac{1}{m}\sum _{i=1}^{m}{{Norm}.\_{ENTD}(g_{i})}, \quad \forall g_{i}\in \xi \end{aligned}$$

(7)

Definition 2

(REP and Avg_REP) Remaining energy of the path (REP) is the total amount of remaining energy of all the CHs in the routing path which is selected using the PSO algorithm. Note that, next-hop CH of a CH can be the BS. In this case, we consider the remaining energy of the BS is equal to the initial energy of the gateways. Therefore, it can be expressed as follows:

$$\begin{aligned} {REP}= & {} \sum _{i=1}^{m}{E_{r}(Next\_Hop(g_{i}))},\forall g_{i}\in \xi \nonumber \\&\wedge \,Next\_Hop(g_{i})\in \{\xi +g_{m+1}\} \end{aligned}$$

(8)

Normalization of REP: Let $E_{init}$ be the initial energy of all the CHs. Therefore, remaining energy of every gateway (including BS) in normalized form can be expressed as follows.

$$\begin{aligned}&{Norm}.\_E_{r}(Next\_Hop(g_{i}))\nonumber \\ {}&\quad =\dfrac{E_{r}(Next\_Hop(g_{i}))}{E_{init}},\quad \forall g_{i}\in \xi \end{aligned}$$

(9)

Therefore, REP in normalized form can be written as

$$\begin{aligned} {Norm}.\_{REP}= & {} \sum _{i=1}^{m}{{Norm}.\_E_{r}(Next\_Hop(g_{i}))}, \,\, \forall g_{i}\in \xi \nonumber \\&\wedge \,Next\_Hop(g_{i})\in \{\xi +g_{m+1}\} \nonumber \\ \end{aligned}$$

(10)

The average remaining energy of each CH in the path (Avg_REP) in normalized form is given by

$$\begin{aligned} {Avg}\_{REP}= & {} \dfrac{{Norm.}\_{REP}}{m} \nonumber \\= & {} \dfrac{1}{m}\sum _{i=1}^{m}{{Norm}.\_E_{r}(Next\_Hop(g_{i}))} \end{aligned}$$

(11)

The standard deviation (SD) of remaining energy of the path can be expressed as follows:

$$\begin{aligned} SD = \sqrt{\dfrac{1}{m}\sum _{i=1}^{m}{({Norm}.\_E_{r}(Next\_Hop(g_{i}))-{Avg}\_{REP})^{2}}} \nonumber \\ \end{aligned}$$

(12)

5 Proposed PSO-based routing

Before presenting the proposed algorithm, we give an outline of the particle swarm optimization (PSO) (Kennedy et al. 1995) technique. PSO consists of a swarm of particles of a predefined size (say $N_{P}$). Each particle $P_{i}$, $1 \le i \le N_{P}$ provides a complete solution to a multidimensional optimization problem. The dimension D of all the particles is equal. The particle $P_{i}$ has position $X_{id}$, $1 \le d \le D$ and velocity $V_{id}$ in the d th dimension of the multidimensional space. Let the i th particle $P_{i}$ of the population be represented by

$$\begin{aligned} P_{i}=[X_{i,1}, X_{i,2}, X_{i,3},\ldots , X_{i,D}] \end{aligned}$$

(13)

A fitness function is used to evaluate each particle to judge its quality for the solution to the problem. In order to achieve the global best position, the particle $P_{i}$ follows its own best, i.e., personal best called $Pbest_{i}$ and the global best called Gbest to update its own velocity and position. In each iteration, its velocity $V_{id}$ and position $X_{id}$ in the dimension D is updated using the following equations, respectively.

$$\begin{aligned} V_{i,d}(t)= & {} w\times V_{i,d}(t-1)+ c_{1}\times r_{1}\times (Xpbest_{i,d} \nonumber \\&-\,X_{i,d}(t-1))+ c_{2} \nonumber \\&\times \, r_{2}\times (Xgbest_{d}-X_{i,d}(t-1)) \end{aligned}$$

(14)

$$\begin{aligned} X_{i,d}(t)= & {} X_{i,d}(t-1)+V_{i,d}(t-1) \end{aligned}$$

(15)

where, w is the inertial weight, $c_1$ and $c_2$ are two non negative constants called acceleration factor and $r_{1}$ and $r_{2}$ are two different uniformly distributed random numbers in the range [0,1]. The update process is iteratively repeated until either an acceptable Gbest is achieved or a fixed number of iterations, say $t_{max}$ is reached.

Now, we present our PSO-based routing algorithm. We use the particle representation for routing same as described in Kuila and Jana (2014b). The determination of fitness function is followed as follows.

5.1 Fitness function derivation

We drive a suitable fitness function to evaluate the quality of individual particle toward the routing solution in the initial population. To do this, we use the terminologies ${Avg}\_{ENTD}$, ${Avg}\_{REP}$ and SD which are defined in the previous section. Note that, there are two objectives in our proposed routing algorithm. The first one is the energy efficiency, and it can be achieved by efficiently forwarding the data from all the gateways to the BS by spending small amount of energy. This is only possible if the selected routing path is shortest to the BS, or in the other hand ${Avg}\_{ENTD}$ is minimum. The second one is the energy balancing in which the energy consumption of the gateways in the path should be uniform. This can be achieved by forwarding the data packets to the BS through energy dense path. Therefore, the path having higher ${Avg}\_{REP}$ is a better choice for balanced energy consumption of the gateways. However, there may be possibility of having few gateways with very low residual energy in a path with higher ${Avg}\_{REP}$. To mitigate this problem, we use another parameter, i.e., standard deviation of remaining energy of the gateways (SD) in the path. Note that the SD for a path, with higher ${Avg}\_{REP}$ and also with few low-energy gateways, is higher due to variation in the remaining energy of the gateways in the path. Therefore, the path with higher ${Avg}\_{REP}$ and lower SD would be the better path in terms of energy balancing.

$$\begin{aligned}&\text {Objective 1: Minimize} {Avg}\_{ENTD}\nonumber \\&\quad = \dfrac{1}{m}\sum _{i=1}^{m}{{Norm}.\_{ENTD}(g_{i})}, \quad \forall g_{i}\in \xi \end{aligned}$$

(16)

$$\begin{aligned}&\text {Objective 2: } \text {Minimize}\dfrac{SD}{{Avg}\_{REP}} \nonumber \\&\quad = \dfrac{\sqrt{\dfrac{1}{m}\sum _{i=1}^{m}{({Norm}.\_E_{r}(Next\_Hop(g_{i}))- {Avg}\_{REP})^{2}}}}{\dfrac{1}{m}\sum _{i=1}^{m}{{Norm}.\_E_{r}(Next\_Hop(g_{i}))}}\nonumber \\ \end{aligned}$$

(17)

Note that, for energy efficiency a shortest path to the BS is chosen whereas, for energy balancing a path with higher remaining energy is chosen which may not be a shortest path to the BS. Therefore the two objectives are conflicting with each other and there should be a trade-off between these two conflicting objectives. Now we use a weight sum approach (WSA) (Konak et al. 2006) for the construction of the multi-objective fitness function. It is a classical approach for solving the multi-objective optimization problem. In this approach, a weight value W is multiplied with each objective. Finally, all the multiplied values are added to convert the multiple objectives into a single scalar objective function as follows.

$$\begin{aligned} {Fitness}= W\times {Avg}\_{ENTD}+(1-W)\times \dfrac{SD}{{Avg}\_{REP}}\nonumber \\ \end{aligned}$$

(18)

where $0 \le W \le 1$ and our objective is to minimize the fitness value. Thus the single objective can be expressed as follows.

$$\begin{aligned} \text {Objective} = \text {Minimize} {Fitness} \end{aligned}$$

(19)

Note that, lower the fitness value, the better is the particle position. The pseudocode of the PSO-based algorithm is given in Algorithm 1.

Lemma 1

All the parameters in the fitness function have equal dominance on the fitness function.

Proof

In Eq. (18), we have calculated the fitness value for routing solution. The SD and ${Avg}\_{REP}$ in Eq. (17) have been calculated using the normalized data set, therefore the calculated value of the Eq. (17) will also be normalized, i.e., in the range [0, 1]. Similarly, we have also calculated ${Avg}\_{ENTD}$ in Eq. (16) using the normalized data set and hence ${Avg}\_{ENTD}$ is also in normalized form. Therefore, when we convert these two objective functions (Eqs. 16, 17) into a single objective using a weight sum approach, the final result will also be in normalized form and each parameter will have equal dominance in the fitness function. Hence all the objectives have equal effect on the fitness function. $\square$

5.2 NLP formulation of routing problem

In this section, we present the NLP formulation of the routing problem where our objective is energy efficiency as well as energy balancing of gateways. Let $X_{i,j}$ be a Boolean variable defined as by

$$\begin{aligned} X_{i,j}=\left\{ \begin{array} {ll} 1, &{} \quad \text {If } Next\_Hop(g_{i})=g_{j}, \quad \forall g_{i}\in \xi , \quad \forall g_{j}\in \{\xi +g_{m+1}\}\\ 0, &{} \quad \text {Otherwise} \end{array} \right. \end{aligned}$$

(20)

Therefore, the NLP formulation for the routing problem can be written as follows.

$$\begin{aligned} \text {Minimize}\,{Fitness}= & {} W\times {Avg}\_{ENTD} \nonumber \\&+\,(1-W)\times \dfrac{SD}{{Avg}\_{REP}} \end{aligned}$$

(21)

Subject to:

$$\begin{aligned}&\sum _{j=1}^{m+1}{X_{i,j}=1}, 1\le i\le m,\nonumber \\&\quad \forall g_{i}\in \xi , \quad \forall g_{j}\in \{\xi +g_{m+1}\} \text { and } i\ne j \end{aligned}$$

(22)

$$\begin{aligned}&\sum _{j=1}^{m+1}{dis(g_{i},g_{j})\times X_{i,j}\le d_{max}}, 1\le i\le m, \quad \forall g_{i}\in \xi ,\nonumber \\&\quad \forall g_{j}\in \{\xi +g_{m+1}\} \text { and } i\ne j \end{aligned}$$

(23)

Note that, constraint (22) ensures that for each gateway $g_{i}$ selects only one next-hop gateway in the network, while the constraint (23) ensures that the selected next-hop gateway of each gateway is within the maximum communication range ($d_{max}$) of the gateways.

5.3 Fault tolerance

There is a perilous impact of failure of gateways during network operation. A gateway may become faulty at any time during the steady state phase as described in Sect. 3.2. The fault can be detected by a gateway when it does not receive any the data acknowledgment receipt from its next hop gateway (Banerjee et al. 2014). After the detection of failure of the next hop gateway, a gateway $g_{i}$ broadcasts a HELP message. On receiving the HELP message, all the neighbor gateways belong to ${Com}(g_{i})$ send a REPLY message to $g_{i}$ to provide their residual energy and the hop value. Suppose the hop value of $g_{i}$ is k which is provided by the BS as described in the Sect. 3.2, therefore $g_{i}$ selects that neighbor whose hop value is $k-1$. Note that there may be more than one gateway in $Com(g_{i})$ with hop value $k-1$. In that case, the gateway with highest residual energy will be selected as a $Next\_Hop(g_{i})$. If there is no gateway with hop value $k-1$ in $Com(g_{i})$, then the $g_{i}$ seeks a gateway having same hop value, i.e., k in $Com(g_{i})$; otherwise, $g_{i}$ declares itself as inactive in the current steady-state phase (see Fig. 1) and pass this message to its preceding neighbor gateway $g_{h}$ for which $Next\_Hop(g_{h}) = g_{i}$. Therefore, the gateway $g_{h}$ can also recover itself from sending data packets to $g_{i}$ which has not any $Next\_Hop$ gateway and can select another gateway for sending data packets to the BS. After the end of steady-state phase, the BS again executes the routing algorithm and fixes the route for the next steady-state phase. Note that, the PSO-based routing algorithm is centralized algorithm, but fault tolerance phase is distributed as individual gateway is taking decision by its own.

Lemma 2

The routing graph of the network created by the PSO-based routing algorithm is loop free in the selection process of the next-hop gateway.

Proof

As we have discussed in Sect. 3.2 that the BS constructs a hop tree before the route setup and each gateway $g_{i}$ selects a gateway from its $Next\_Hop\_G(g_{i})$. Since the hop value of each gateway in $Next\_Hop\_G(g_{i})$ has the hop value one less than the hop value of the gateway $g_{i}$. Therefore, each gateway $g_{i}$, $g_{i}\in \xi$ selects its $Next\_Hop(g_{i})$ toward the BS and there is no provision of creating routing loop in the route setup phase. Similarly, whenever the $Next\_Hop(g_{i})$ of a gateway $g_{i}$ is failed, then the $g_{i}$ finds another gateway from the $Com(g_{i})$ and finds a path toward the BS by selecting a gateway whose hop value is one less than the hop value of the $g_{i}$. Therefore, we can say that there is no way creating routing loop again. Moreover, if the $g_{i}$ does not find any gateway from its $Com(g_{i})$ with hop value one less than the hop value of $g_{i}$, then it finds a gateway with same hop value. As no gateway in the setup phase selects its next hop gateway with same hop value, therefore there is always a path toward the BS when $g_{i}$ selects its $Next\_Hop(g_{i})$ with same hop value for the fault tolerance and there will be no routing loop. Therefore, we can say that our proposed PSO-based routing algorithm is loop free. $\square$

6 PSO-based clustering

Now we present the clustering algorithm. The BS executes the clustering algorithm and it uses the route setup information as discussed in Sect. 5. The particle representation for the clustering solution is same as the paper (Kuila and Jana 2014b). This is worth noting that the fitness function is derived by normalizing lifetime and average intra cluster distance in contrast to Kuila and Jana (2014b) which derives the fitness function without considering such normalization.

6.1 Fitness function derivation

We construct the fitness function for clustering problem in such a way that it should minimize the energy consumption of the gateways and the sensor nodes. This can be done as follows.

6.1.1 Minimization of energy consumption of the gateways

Since, the gateways are not only responsible for receiving the data packets from its neighbors and transmitting it to the BS at the routing phase, but also for receiving sensed data packets from their member sensor nodes and aggregation of the data at the clustering phase. The energy consumption of the gateways can further be minimized in the clustering phase by assigning least number of sensor nodes to the gateways having higher routing load. Therefore, the rate of energy consumption of the gateways is minimized by minimizing the load of sensor nodes in the clustering phase and hence, the lifetime of the gateways are maximized. Now, we calculate the number of packets received (say $P_{rev}$) by a gateway $g_{i}$ from its neighbor gateways per round. It can be done recursively as follows.

$$\begin{aligned} P_{rcv}(g_{i})=\left\{ \begin{array} {ll} \sum {P_{rcv}(g_{j})}, &{} \quad \text {If } Next\_Hop(g_{j})=g_{i}, \forall g_{j}\in \xi \\ \\ 0, &{} \quad \text {Otherwise} \end{array} \right. \end{aligned}$$

(24)

Let, $E_{R} , E_{DA}$ and $E_{T}$ be the energy consumption of the gateways due to data receiving, data aggregation and data transmission of single packets to its next hop gateway respectively. Therefore, energy consumption of a gateway $g_{i}$ in a round can be calculated as follows.

• 1. Energy consumption of $g_{i}$ due to receiving all data packets from its neighbors (say $g_{k}$) in data and it is equal to

  $$\begin{aligned} P_{rcv}(g_{i})\times E_{R} \end{aligned}$$

  (25)

• 2. Energy consumption of $g_{i}$ due to receiving data packets from its cluster members and their aggregation and this is equal to

  $$\begin{aligned} Clstrmembr(g_{i})\times (E_{R}+E_{DA}) \end{aligned}$$

  (26)

• 3. Energy consumption of $g_{i}$ due to transmission of data packets to the next-hop gateway (say $g_{j}$) which is equal to

  $$\begin{aligned} (P_{rcv}(g_{i})+1)\times E_{T} \end{aligned}$$

  (27)

  Note that, a gateway converts the data packets received from all of its member sensor nodes into a single data packet following a data aggregation method. Therefore, the gateway forwards its own aggregated data packet as well as the data packets received from its neighbor gateways to the BS.

Therefore the total energy consumed by $g_{i}$ per round can be calculated by combining Eqs. (25), (26) and (27) as follows.

$$\begin{aligned} E_{consmp}(g_{i})= & {} P_{rcv}(g_{i})\times E_{R} + Clstrmembr(g_{i}) \nonumber \\&\times \,(E_{R}+E_{DA}) + (P_{rcv}(g_{i})+1)\times E_{T}\quad \end{aligned}$$

(28)

Then, the lifetime of $g_{i}$ with remaining residual energy $E_{r}(g_{i})$ can be calculated as follows.

$$\begin{aligned} {Lifetime}\_G(g_{i})=\dfrac{E_{r}(g_{i})}{E_{consmp}(g_{i})} \end{aligned}$$

(29)

Now we again normalize the Lifetime of each gateway into the range [0, 1] to minimize its dominance when multiple objectives are superposed.

Normalization of Lifetime (${\varvec{g}}_{{{\varvec{i}}}}$): Suppose $L_{min}$ and $L_{max}$ denotes the gateway with minimum and maximum lifetime, respectively, in the network which are calculated as follows.

$$\begin{aligned} {L_{min}}= & {} {\textit{min } \{{Lifetime}\_G(g_{i}), \forall g_{i}\in \xi \}}\\ {L_{max}}= & {} {\textit{max } \{{Lifetime}\_G(g_{i}), \forall g_{i}\in \xi \}} \end{aligned}$$

Therefore, lifetime of each gateway in normal form can be written as follows:

$$\begin{aligned}&{Norm}.\_{Lifetime}(g_{i})\nonumber \\ {}&\quad =\dfrac{{Lifetime}\_G(g_{i})-L_{min}}{L_{max}-L_{min}},\quad \forall g_{i}\in \xi \end{aligned}$$

(30)

Now our objective is to minimize the rate of energy consumption of the gateways so that the lifetime of the gateway will be maximized. In other word, maximize the lifetime of the gateway having minimum lifetime in the network. It can be expressed as follows.

$$\begin{aligned}&\text {Maximize}\,{Lifetime}\nonumber \\ {}&\quad =\textit{min}\{{Norm}.\_{Lifetime}(g_{i})|\quad \forall g_{i}\in \xi \} \end{aligned}$$

(31)

Therefore, fitness value is higher if the Lifetime is higher, i.e.,

$$\begin{aligned} {fitness}\propto {Lifetime} \end{aligned}$$

(32)

6.1.2 Minimization of energy consumption of sensor nodes

As the main source of energy consumption of the sensor nodes is due to the transmission of the sense data to their respective CHs. Therefore, the energy consumption of the sensor nodes can be minimized by minimizing the distance between the sensor nodes and their corresponding CHs or Intracluster_distance. This can be possible if we assign a sensor node to its nearest CH. If we denote the minimum and the maximum Intracluster_distance by $D_{min}$ and $D_{max}$, respectively, then the average Intracluster_distance can be calculated as follows.

$$\begin{aligned}&Avg\_Intracluster\_distance \nonumber \\&\qquad =\dfrac{1}{n}\sum _{i=1}^{n}\left( { \dfrac{dis(s_{i},CH_{i})-D_{min}}{D_{max}-D_{min}}}\right) \end{aligned}$$

(33)

where $CH_{i}$ is the cluster head of the sensor node $s_{i}$. Here, our objective is to minimize the $Avg\_Intracluster\_distance$, in other words

$$\begin{aligned}&\text {Minimize}Avg\_Intracluster\_distance\nonumber \\&\qquad =\dfrac{1}{n}\sum _{i=1}^{n}\left( { \dfrac{dis(s_{i},CH_{i})-D_{min}}{D_{max}-D_{min}}}\right) \end{aligned}$$

(34)

Therefore, shorter the $Avg\_Intracluster\_distance$, the higher is the fitness value and hence, the fitness function is inversely proportional to the $Avg\_Intracluster\_distance$. Hence,

$$\begin{aligned} fitness \propto \dfrac{1}{Avg\_Intracluster\_distance} \end{aligned}$$

(35)

By combining the Eqs. (32) and (35), we can write

$$\begin{aligned} fitness \propto \dfrac{Lifetime}{Avg\_Intracluster\_distance} \end{aligned}$$

(36)

$$\begin{aligned} \text {i.e., }fitness =K\times \dfrac{Lifetime}{Avg\_Intracluster\_distance} \end{aligned}$$

(37)

where k is proportionality constant, and without loss of generality, we assume that $k=1$ as the fitness value is used only for comparison purpose. Therefore,

$$\begin{aligned} fitness = \dfrac{Lifetime}{Avg\_Intracluster\_distance} \end{aligned}$$

(38)

and our objective is to maximize the fitness value. In other words,

$$\begin{aligned} \text {Objective: Maximize }fitness \end{aligned}$$

(39)

Therefore, the higher the fitness value is, the better is the particle position.

6.2 NLP formulation of clustering problem

We present a NLP formulation for the clustering solution, where our objective is to minimize the energy consumption of gateways as well as the sensor nodes. The energy consumption of the gateways can be minimized by minimizing the rate of energy consumption of the gateways by assigning least number of sensor nodes to them. On the other hand, the energy consumption of the sensor nodes can be minimized if the distance between the sensor nodes and their corresponding gateways is minimized. Let $Y_{i,j}$ be a Boolean variable such that

$$\begin{aligned} Y_{i,j}=\left\{ \begin{array} {ll} 1, &{} \quad \text {If } s_{i} \text { is assigned to } g_{j}, \forall s_{i}\in S \wedge g_{j}\in \xi \\ \\ 0, &{} \quad \text {Otherwise} \end{array} \right. \end{aligned}$$

(40)

Then the LP of the clustering problem can be written as follows.

$$\begin{aligned} \text {Minimize } fitness = \dfrac{Lifetime}{Avg\_Intracluster\_distance} \end{aligned}$$

(41)

Subject to:

$$\begin{aligned}&\sum _{j=1}^{m}{Y_{i,j}=1}, 1\le i\le n, \quad \forall s_{i}\in S, g_{j}\in \xi \end{aligned}$$

(42)

$$\begin{aligned}&\sum _{j=1}^{m}{dis(s_{i},g_{j})\times Y_{i,j}\le R_{s}}, 1\le i\le n, \quad \forall s_{i}\in S, g_{j}\in \xi \end{aligned}$$

(43)

The constraint (42) guarantees that each sensor node $s_{i}, \forall s_{i} \in S$ is assigned to one and only one gateway, whereas the constraint (43) ensures that a sensor node is assigned to a gateway which is within the communication range of sensor node ($R_{s}$).

Remark 6.1

The above fitness function can also be expressed similar to that of routing as follows:

$$\begin{aligned} {Fitness}= & {} W\times {Lifetime} \nonumber \\&+\,(1-W)\times \dfrac{1}{Avg\_Intracluster\_distance}\nonumber \\ \end{aligned}$$

(44)

we performed simulation by using both the fitness functions following Eqs. (38) and (44). However, we have observed that clustering algorithm by using the fitness function given by Eq. (38) provides better simulation result.

6.3 Fault tolerance

There is also an effect of failure of a gateway to its member sensor nodes in a cluster. A gateway may fail at any time of the steady-state phase, and it can be detected by its member sensor nodes if they do not receive any data acknowledgment receipt (Banerjee et al. 2014). Whenever a member sensor node $s_{i}$ detects the failure of its CH, then it broadcasts a HELP message within $R_{s}$ communication range. Then all the gateways $g_{i}, g_{i} \in ComCH(s_{i})$ reply to this HELP message. If there is only one gateway in the $ComCH(s_{i})$ then $s_{i}$ simply joins that gateway for that steady-state phase. If there is more than one gateways in the $ComCH(s_{i})$ then $s_{i}$ joins the nearest gateway for that steady-state phase. Note that, the distance between the sensor node and the gateway can be measured based on received signal strength of the reply message (Xu et al. 2010). If a sensor node does not find any gateway within its communication range the sensor node is considered to be dead.

7 Simulation results

7.1 Simulation setup

For the simulation run of the proposed algorithms, we used MATLAB R2012b and C programming language on an Intel i7 processor, 3.40 GHz CPU and 2 GB RAM running on the platform Microsoft Windows 7. The simulations were carried out by assuming various WSN scenarios in which the number of sensor nodes varies from 300 to 700 and the number of gateways from 60 to 90. The initial energy of the sensor nodes and the gateways along with other parametric values were assumed similar as Heinzelman et al. (2002) as shown in Table 1.

Table 1 Simulation parameters

To evaluate the performance of the proposed algorithm, we carried out the experiment on two different scenarios of WSNs (namely WSN#1 and WSN#2), each having $500\times 500$ square meter area. In WSN#1, the position of the BS was taken at the center of the region with coordinate (250, 250), whereas in WSN#2 the position of the BS was taken at the boundary of the region with coordinate (500, 250). The parameter values for the PSO were taken same as in Bratton and Kennedy (2007) which is shown in Table 2 and the number of particles in the initial population were kept 60. Note that the weight value ( W ) is application dependent and selection of this value is difficult (Konak et al. 2006). However, we used $W = 0.4$ as it provides the best result among selected values. As our proposed PSO-based algorithms consist of clustering as well as multi-hop routing algorithm, therefore we executed the GA-based multi-hop routing algorithm (Bari et al. 2009) along with all the existing algorithms, except (Kuila and Jana 2014b), used here for the sake of fair comparison.

Table 2 PSO parameters

7.2 Performance with respect to network lifetime

First, we compare the result of the proposed algorithm in terms of the network lifetime with respect to first gateway die. The comparisons were made by executing the similar existing algorithms namely, GALBCA [a GA-based clustering algorithm presented by Kuila et al. (2013)], GLBCA [a clustering algorithm by Low et al. (2008)], LDC (leach distance clustering by Bari et al. (2008)) and a PSO-based approach by Kuila and Jana (2014b). The results were depicted in Figs. 2 and  3 respectively for two different scenarios of WSN, i.e., WSN#1 and WSN#2.

Fig. 2

Comparison in terms of network lifetime for a 60 gateways and b 90 gateways in WSN#1

Fig. 3

Comparison in terms of network lifetime for a 60 gateways and b 90 gateways in WSN#2

It is observed from the Figs. 2 and  3 that the proposed PSO-based algorithm has better network lifetime than the Kuila et al., GLBCA, GALBCA and LDC. The reason behind this is that, we have considered the energy efficiency and energy balancing of the gateways in the routing phase [using Eq. (18)]. Moreover, it also takes care of those CHs which depletes energy rapidly due to routing overhead and assigned less number of sensor nodes in the clustering phase (using Eq. (32)). Therefore, the proposed algorithm reduces the chance of quick death of a CH in the network and hence increase the network lifetime. However the existing algorithms do not consider the balance energy consumption of the CHs due to data forwarding and hence CHs near to the BS die quickly due to the extra workload of data routing.

On the other hand, the number of data packets received by the BS in proposed algorithm is much greater than the existing algorithms since the network lifetime is higher than the existing algorithms. This is shown in Fig. 4 for 600 sensor nodes and 60–90 gateways in both the scenarios.

Fig. 4

Comparison in terms of total data packets received by the base station in a WSN#1 and b WSN#2

7.3 Performance with respect to energy consumption

We ran the algorithm to measure their total energy consumption. The comparison results per round for 600 sensor nodes and 90 gateways is shown in Fig. 5 for WSN#1 and WSN#2. It can be observed that the proposed algorithm consumes a little bit less amount of energy per round. However, a substantial amount of energy is consumed not only for receiving the higher number of data packets by the BS (see Fig. 4) but also for the activeness of large number of sensor nodes and gateways due to long network lifetime. Therefore, we can claim that the total energy consumption of the proposed algorithm is actually much lower than the existing algorithm.

Fig. 5

Comparison in terms of total energy consumption in a WSN#1 and b WSN#2

This can also be verified by showing the energy consumption per packet per round as given in Fig. 6 for 600 sensor nodes and 90 gateways. Note that, it is much lower than the existing algorithms. This is due to efficient fitness function for routing as well as clustering of the proposed algorithm.

Fig. 6

Comparison in terms of energy consumption per packet in a WSN#1 and b WSN#2

7.4 Performance with respect to energy balancing

Next we show the energy balancing by running the proposed algorithm as well as existing algorithm. For this, we consider two metrics, i.e., the standard deviation of remaining energy of the gateways and the difference between first gateway die (FGD) and last gateway die (LGD). The results are shown in Figs. 7 and 8. Figure 7 shows that the proposed algorithm has much lower SD per round than the others. As we know that lower the SD better is the energy balancing. Therefore, we can say that the proposed algorithm has the better energy balancing of the gateways. Again the reason for this is due to efficient fitness function for the routing and the clustering phases (using Eqs. 18, 38). The route is selected by the routing algorithm by considering energy efficiency as well as energy balancing. On the other hand, cluster formation is done by assigning the least number of sensor nodes to the gateway which deteriorates its own energy faster.

Fig. 7

Comparison in terms of SD of remaining energy of the gateways a WSN#1 (70–600) and b WSN#2

Fig. 8

Difference between FGD (First gateway die) and LGD (Last gateway die) for a WSN#1 and b WSN#2

Figure 8 shows the comparisons of the results in terms of the difference between the first gateway die (FGD) and the last gateway die (LGD) in rounds for WSN#1 and WSN#2. Here, we ran the algorithms for 300–600 sensor nodes and 90 gateways for both the scenarios to compare the balancing of the lifetime of the gateways in the network. Therefore, if the difference is lower, then the balancing of the lifetime of the gateways is better. It can be observed from the Fig. 8 that the proposed algorithm outperforms better existing algorithms as we considered the energy balancing of the gateways along with energy efficiency.

7.5 Performance with respect to number of inactive nodes

Now, we represent the comparison results in terms of number of inactive sensor nodes per round. An inactive sensor node is one which has residual energy but has no alive CH to communicate with. Figure 9 shows the number of inactive sensor nodes per round for 600 sensor nodes and 60 gateways for proposed algorithm which is much lesser than the existing algorithms. The reason behind this is that, we minimize the energy consumption of the gateways at clustering phase and hence maximize the lifetime of the gateways (using Eq. 32) which helps the sensor nodes to be active longer period of time. Moreover, we also consider the fault tolerance of the sensor nodes, so that a sensor node joins another CH in its communication range, if any CH exists, due to the failure of its CH. Note that, Kuila et al. does not consider the fault tolerance issue due to CH failure, although it minimizes the energy consumption of the gateways at clustering phase. On the other hand the GLBCA and GALBCA only balances the load of the CHs and hence, a sensor node may be assigned to a CH farther from it for balancing the load of CHs. Therefore, the CH die quickly for long-haul communication and member sensor nodes become inactive. Moreover, although a sensor node is assigned to its nearest CH to reduce the energy consumption of the sensor nodes in LDC, but it does not consider the load balancing of the CHs and the data forwarding overhead. As a result, member sensor nodes become inactive due to the quick failure its CH as they have not considered the fault-tolerant issue.

Fig. 9

Comparison in terms of inactive sensor nodes in a WSN#1 and b WSN#2

8 Conclusion

In this paper, we have presented energy-efficient and energy-balanced routing and clustering algorithms which are based on particle swarm optimization (PSO). The routing algorithm builds a trade-off between energy efficiency and energy balancing, whereas the clustering takes care energy consumption of the gateways and the sensor nodes. We have presented NLP formulation for both the routing and the clustering algorithms. Each algorithm is also shown to be fault tolerant in distributed way. We have performed various experiments using two different scenarios of the WSN and it has been shown that the proposed schemes outperform the existing algorithms, namely Kuila et al., GLBCA, GALBCA, and LDC in terms of various performance metrics such as network lifetime, total energy consumption, number of data packets received by the BS, standard deviation of remaining energy of gateways and the number of inactive sensor nodes. However, we have considered only permanent failure of the CHs for fault tolerance. In future, our attempt will be made to design energy aware routing and clustering by emphasizing on partial and transient failure of the gateways and also in mobile scenario. The proposed scheme is a centralized algorithm which is to be run by the BS. Therefore, we will also try to develop and implement a distributed algorithm by avoiding computation load on the BS and by making the network self-configurable and self-healing.