Nature-Inspired Algorithms for k-Coverage and m-Connectivity Problems in Wireless Sensor Networks

Abstract

Efficient deployment of the sensor nodes takes an important role in proper coverage and connectivity of the wireless sensor networks (WSNs). The key issues that need to be taken care during deployment are the number of deployed sensors, coverage of the target/region, and connectivity among the sensor nodes. As the sensor nodes are prone to various kinds of failure, it is essential for k-coverage of the targets and m-connectivity among the sensor nodes. Here, k-coverage of the targets indicates that all the targets are covered by at least k number of sensor nodes so that failure of k − 1 sensor nodes can also ensure coverage of the targets. Similarly, m-connectivity of the sensor nodes indicates all the sensor nodes are connected with other m − 1 sensor nodes. Note that the k-coverage and m-connectivity problem for WSNs is nondeterministic polynomial (NP)-hard in nature. In this chapter, nature-inspired algorithms are studied and designed to solve the problem. Particle swarm optimization (PSO), differential evolution (DE), genetic algorithms (GA), and gravitational search algorithm (GSA) are studied and designed for the problem. The chromosome, vector, particle, and agent are efficiently represented. An efficient derivation of fitness functions is provided with the conflicting objectives. An extensive simulation is also conducted.

1 Introduction

Wireless sensor networks (WSNs) draw a great attention of the researchers for their various potential applications. A sensor node performs multiple functions as sensing, communication, and data processing. Sensor nodes can collaborate among them to monitor or sense the area of interest (AoI), collect the sensory data, process the data, and transmit to the base station (BS) directly or through multi-hop [1,2,3,4]. As the sensor nodes are equipped with limited energy source, it is very essential and challenging to conserve the limited energy [5,6,7,8,9]. Moreover, sensor nodes can sense and communicate within the limited sensing and communication range. A region/target is said to be covered if it falls within the sensing range. Similarly, two sensor nodes can communicate with each other if they are within the communication range of each other. Therefore, it is also very essential to provide an efficient coverage and connectivity [10,11,12,13,14,15,16] to monitor the region/target and to transmit the sensed data to the base station.

Deployment of sensor nodes has vital role for ensuring an efficient coverage and connectivity in the network. There are mainly two types of deployment scheme in WSN: preplanned [14] and ad hoc [14] deployment. In preplanned scheme, sensor nodes are deployed in planned manner in an accessible area and thereby the network has better management with saving in cost and energy. In ad hoc scheme, sensor nodes are deployed randomly in the harsh environment where human interference is not possible. Ad hoc deployment does not guarantee the coverage and connectivity. Thus, this scheme requires large number of sensor nodes for proposed function of the network.

Sensor nodes are prone to failure due to hardware failure, energy depletion, natural calamities, etc. As a result, network becomes functionless. Therefore, for better performance of the network k-coverage and m-connectivity are desirable. However, cost for the k-coverage and m-connectivity should also be optimized by deploying the minimum number of sensor nodes. Therefore, deployment of minimum number of sensor nodes for desire coverage and connectivity is an NP-hard [14, 16,17,18] problem. In limited time, it is not feasible or computationally very expensive to find the optimal solutions for the NP-hard problem.

In this chapter, we studied the target coverage with connectivity problem as in [14]. As an example, a network scenario with 7 target points (t₁, t₂, t₃, …, t₇) and 14 potential positions (ρ₁, ρ₂, ρ₃, …, ρ₁₄) is shown in Fig. 1. Here, among the 14 potential positions, 9 positions are selected to place the sensor nodes. We can also observe that all the target points are covered by at least three sensor nodes and each sensor node is connected with at least other two neighbor sensor nodes. Therefore, we can say that scenario of the network as shown in Fig. 1 in chapter “Ambient Intelligence for Patient-Centric Healthcare Delivery: Technologies, Framework and Applications” is three coverage of the target and two connectivity of the sensor nodes, i.e., 3-coverage and 2-connectivity.

Fig. 1

A simple network scenario with 3-coverage and 2-connectivity [14]

Nowadays, nature-inspired algorithms (NIAs) are drawing a great attention of the researchers as these algorithms are found to be very efficient to find the optimal solutions for the real-life complex problems. NIAs are classified into evolutionary algorithms (EAs) and swarm intelligence algorithms (SIAs). These algorithms are extensively used to solve many optimization problems of WSNs [19,20,21,22,23,24,25,26,27,28,29].

1.1 Author’s Contribution

In this chapter, we have studied the k-covered and m-connectivity problem as in [14]. Various nature-inspired approaches like genetic algorithm (GA), particle swarm optimization (PSO), differential evolution (DE), and gravitational search algorithm (GSA) are also studied and employed for the above mentioned problem. Our contributions are summarized as follows:

• A linear programming (LP) is formulated for the aforesaid problem.

• Efficient representation of chromosome, particle, vector, and agent for GA, PSO, DE, and GSA, respectively. Moreover, they are generated such a way that validity of them cannot be disturbed after the operations of EAs (e.g., crossover, mutation, velocity and potion updation, etc.).

• Derivation of efficient fitness function is given. Here, three conflicting objectives are considered.

• An extensive simulation is conducted and comparisons are shown for the algorithms.

1.2 Organization of the Chapter

Rest of the chapter is organized as follows. Section 2 provides a brief overview of nature-inspired algorithms. Network model, problem formulation, terminologies, and derivation of fitness function are defined in Sect. 3. GA-, PSO-, DE-, and GSA-based approaches are discussed in Sects. 4–7, respectively. Experimental results are shown in Sect. 8 and the chapter is concluded in Sect. 9.

2 Nature-Inspired Algorithms

Nature-inspired algorithms (NIAs) are inspired by the processes, perceived from nature to solve the various optimization problems. These algorithms have drawn enormous attention of the researchers to solve various optimization problems in the field of engineering, biomedical, finance, etc. NIAs find the optimal solution for real-life problem which is classified as NP-hard. It is a population-based algorithm which is classified into evolutionary algorithms (EAs) and swarm-intelligence-based algorithms (SIAs). EAs are motivated by the theory of Charles Darwin called survival of the fittest. The individual in the population survives and reproduces offspring only if they can fit themselves in the given environment. Whereas SIAs are inspired by the collective behavior of swarms like bird flocking, fish schooling, ant colony, bee colony, etc. An overview of some popular nature-inspired approaches is as follows.

2.1 Genetic Algorithm

Genetic algorithm (GA) [30,31,32,33,34] is a population-based meta-heuristic optimization algorithm. A population of size N_p is created by randomly generating the chromosomes. Each chromosome represents the complete solution to the problem. Chromosomes in the population are updated by applying the genetic operations (selection, crossover, and mutation) to explore the search space to find the near-optimal solution. In the selection phase, a set of chromosomes are selected from the population. Selection operation is followed by the crossover operation. In crossover operation, two-parent chromosomes exchange their information to produce two child offspring chromosomes. Finally, a gene value is randomly selected and mutated. Mutation is also applied with some modification according to the application characteristic. This process repeats iteratively till the desired or satisfactory chromosome is obtained or maximum number of iterations.

2.2 Particle Swarm Optimization

Particle swarm optimization (PSO) [1, 35, 36] is a stochastic optimization method that is motivated by the social behavior of bird flocking or fish schooling. It can be observed that birds, fishes, etc. always travel in a group without colliding with each other. To avoid the collision, each member uses the group information and adjusts its position and velocity to follow the group. This approach reduces the efforts of each individual to find the food, shelter, etc. Initially, a swarm (say size N_p) of particles is created randomly where an individual particle represents a complete solution to a multidimensional optimization problem. All particles in the population have equal dimension (say D) and also initiated with random velocities in search space. In the dth dimension of the hyperspace, a particle P_i, 1 ≤ i ≤ N_p with position β_i,d, 1 ≤ d ≤ D can be represented as follows:

$$ P_{i} = \left[ {\beta_{i,1} ,\beta_{i,2} ,\beta_{i,3, \ldots ,} \beta_{i,d} } \right] $$

(1)

The quality of the particles is evaluated by the derived fitness function. In order to search the near-optimal solution, the velocities and positions of the particles are updated in each iteration. The velocity of the particles is updated by two best particles, i.e., personal best (Pbest_i) and global best (Gbest). Pbest_i be the best particle that has been observed so far for P_i. Gbest be the best particle among the swarm. The velocity and position of the particles are updated as follows:

$$ \begin{aligned} v_{i,d} (t) & = w \times v_{i,d} \left( {t - 1} \right) + c_{1} \times r_{1} \times \left( {Pbest_{i,d} - \beta_{i,d} \left( {t - 1} \right)} \right) + c_{2} \times r_{2} \\ & \quad \times \left( {Gbest_{i,d} - \beta_{i,d} \left( {t - 1} \right)} \right) \\ \end{aligned} $$

(2)

$$ \beta_{i,d} (t) = \beta_{i,d} \left( {t - 1} \right) + v_{i,d} (t) $$

(3)

where w represents the inertial weight, c₁ and c₂ are positive constant values called acceleration coefficient, and r₁ and r₂ are two independently generated random number in the range [0, 1]. The update process will continue till the acceptable solution is achieved or the maximum number of iterations are reached.

2.3 Differential Evolution

Differential evolution (DE) [37,38,39] is one of the most powerful stochastic real parameter based evolutionary algorithms. DE is widely used to solve many optimization problems. Initially, a population (size say N_p) is created by randomly generating the set of vectors of dimension, say D. Each individual vector represents the complete solution to the problem. The quality of the vectors is evaluated by the derived fitness function. After the initialization of the population, the quality of the vectors is enhanced by the mutation, crossover, and selection operation. In each iteration, the vectors are updated. The final solution is obtained by evaluating the solutions till the maximum iteration is reached.

DE with different variants can be represented in general form as DE/β/γ/δ. DE denotes the differential evolution, β specifies the vector to be muted (which can be selected as randomly or best vector from population), γ specifies the number of vectors that are considered for mutation operation of β, and δ denotes crossover scheme (binomial or exponential). In the mutation operation, each candidate vector called target vector and other three vectors are randomly chosen. Thereafter, a new vector called donor vector is generated using mutation. Mutation operation is followed by crossover operation. In crossover operation, target vector and donor vector exchange their information to generate a child vector called trail vector. Finally, fitness function is used in selection operation to select the best vector among the trial vector and target vector for the next generation. Algorithm iterates continuously to generate the new vectors till the termination criteria are obtained or acceptable vector for the problem is achieved.

2.4 Gravitational Search Algorithm

Gravitational search algorithm (GSA) [40] is a population-based stochastic optimization technique. This algorithm is inspired from the law of gravitation and law of motion. In GSA, each solution is represented by agent that represents the complete solution for a multidimensional optimization problem. The agents are initialized with position, velocity, acceleration, and mass. According to the law of gravitation, objects in the universe attract each other by a gravitational force. During this movement, object having lower mass moves toward the object with higher mass. The objects with lower mass have higher acceleration whereas objects with higher mass have slower acceleration. The agents with lighter mass will get attracted toward the agent with heaviest mass. Performance of the agent is dignified by its mass. An agent with heavier mass is considered as the optimal solution to the problem. An ith agent from the population of size N_p is denoted as follows:

$$ \lambda_{i} = \left\{ {\lambda_{i}^{1} ,\lambda_{i}^{2} ,\lambda_{i}^{3} , \ldots ,\lambda_{i}^{d} } \right\},\;\forall i,\;1 \le i \le N_{p} $$

(4)

where λ ^d_i represents the position value of ith agent in the dth dimension. At iteration t, the gravitational force acting on agent λ_i from agent λ_j in the dth dimension is defined as follows:

$$ F_{ij}^{d} = G(t) \times \frac{{M_{pi} (t) \times M_{aj} (t)}}{{R_{ij} (t) + \varepsilon }} \times \left\{ {\lambda_{i}^{d} (t) - \lambda_{j}^{d} (t)} \right\} $$

(5)

where G(t) is the gravitational constant at iteration t, ε is the small constant, passive gravitational mass of agent λ_i and active gravitational mass of agent λ_j are represented by M_pi(t) and M_aj(t), respectively, and R_ij(t) denotes the Euclidean distance between two agents λ_i and λ_j at iteration t. The value of gravitational constant G(t) with initial value G₀ is calculated as follows:

$$ G(t) = G_{0} \times \left( { - \beta t} \right)/e^{tmax} $$

(6)

where tmax denotes the maximum number of iteration and value of control parameter is represented by β. The total force applied by all agents on the agent λ_i in the dth is calculated by the following formula:

$$ F_{i}^{d} = \sum\limits_{j = 1,j \ne i}^{Np} {rand_{j} \times F_{ij}^{d} ,where\,rand_{j} \in \left[ {0,1} \right]} $$

(7)

The relation among mass (M), acceleration (a), and force is given by the law of motion. Therefore, the acceleration of λ_i in dth dimension is given as follows:

$$ a_{i}^{d} = F_{i}^{d} (t)/M_{ii} (t) $$

(8)

where M_ii denotes the inertial mass of an agent λ_i. The velocity and position of λ_i are updated by using the following equations:

$$ v_{i}^{d} \left( {t + 1} \right) = rand_{i} \times v_{i}^{d} (t) + a_{i}^{d} (t) $$

(9)

$$ \lambda_{i}^{d} \left( {t + 1} \right) = \lambda_{i}^{d} (t) + v_{i}^{d} \left( {t + 1} \right) $$

(10)

where rand_i ∊ [0, 1]. The gravitational and inertial masses of an agent are assumed to be equal in GSA, i.e., M_ai = M_pi = M_ii = M_i.

In a population, N_p agents are evaluated by the fitness function. In iteration t, among all agents, best(t) and worst(t) are the best and worst agents for the maximization problem denoted as

$$ best(t) = max_{{j \in \left[ {1, \ldots Np} \right]}} fit_{j} (t) $$

(11)

$$ worst(t) = min_{{j \in \left[ {1, \ldots Np} \right]}} fit_{j} (t) $$

(12)

The mass of every agent is calculated by the fitness value obtained from Eqs. (11) and (12). The mass M_i of an agent λ_i is determined as follows:

$$ m_{i} = \frac{{fit_{i} (t) - worst(t)}}{best(t) - worst(t)} $$

(13)

$$ M_{i} = \frac{{m_{i} (t)}}{{\sum\nolimits_{j = 1}^{Np} {m_{i} (t)} }} $$

(14)

The exploitation must fade in and exploration must fade out to avoid from trapping in local optimum as the laps of iterations continue. Therefore, only K agents with best fitness value, i.e., Kbest will apply force to others. Kbest value linearly decreases to one as it is a function of time. Thus, Eq. (7) could be revised as follows:

$$ F_{i}^{d} = \sum\limits_{j \in Kbest,j \ne i} {rand_{j} \times F_{ij}^{d} ,where\,rand_{j} \in \left[ {0,1} \right]} $$

(15)

However, the subsequent changes in the position and velocity occur with the process of repeatedly updating the acceleration of the agent. This process of updating continues till the optimal solution is obtained or maximum iteration is reached.

3 Network Model and Problem Formulation

3.1 Network Model

Based on our problem, we have assumed a 2D WSN with few target points, a base station, and few predefined potential positions. Target points need to be monitored by placing the sensor nodes on the given potential positions. Assumed WSN is supposed to have the following properties [41,42,43,44,45,46]:

• All the target points and deployed sensor nodes are stationary.

• Target is said to be covered if it falls within the sensing range of sensor nodes.

• Two nodes are connected if they are within communication range of each other.

• A sensor node can sense more than one target point.

• All the sensor nodes have same sensing and communication range.

3.2 Terminologies

Before formulation of problem, first, we define some terminologies used in this chapter.

• P = {ρ₁, ρ₁, ρ₁, …, ρ_N} denotes the N number of predefined potential positions.

• S = {s₁, s₂, s₃, …, s_Z} denotes the set of Z number of deployed sensor nodes on selected potential positions.

• T = {t₁, t₂, t₃, …, t_M} denotes the M number of target points.

• R_sen and R_com denote the sensing and communication range of the sensor nodes, respectively.

• D(s_i, t_j) represents the Euclidean distance between s_i and t_j.

• SC_cov(t_i) denotes the set of sensor nodes that cover t_i, i.e.,

  $$ SC_{cov} \left( {t_{i} } \right) = \left\{ {s_{j} |D\left( {s_{i} ,t_{j} } \right) \le R_{sen} ,\;\forall j,\;1 \le j \le Z} \right\} $$

  (16)

• TC_cov(s_i) denotes the set of target points which are covered by s_i, i.e.,

  $$ TC_{cov} \left( {s_{i} } \right) = \left\{ {t_{j} |D\left( {s_{i} ,t_{j} } \right) \le R_{sen} ,\;\forall j,\;1 \le j \le M} \right\} $$

  (17)

• C_con(s_i) denotes the set of sensor nodes that are within the communication range of s_i toward BS, i.e.,

  $$ \begin{aligned} C_{con} \left( {s_{i} } \right) & = \{ s_{j} |D\left( {s_{i} ,s_{j} } \right) \le R_{com} ,\& D\left( {s_{i} ,s_{j} } \right) \\ & \quad \ge D\left( {s_{j} ,BS} \right),\forall j,1 \le j \le Z\} \\ \end{aligned} $$

  (18)

• COV_cost(t_i) denotes the coverage cost of t_i.

• CON_cost(s_i) denotes the connection cost of s_i.

• k and m are the desired coverage and connectivity (k and m are some predefined value).

• BS denotes base station.

3.3 Problem Definition

Given a WSN with N predefined potential positions and M target points, we have to place the sensor nodes on selected potential positions, considering the following objectives:

• Selection of minimum number of potential positions for placement of sensor nodes.

• Placed sensor nodes must ensure the k-coverage of the targets.

• Placed sensor nodes must be m-connected among themselves.

Before formulation of linear programming (LP) of the given problem, we define the following Boolean variables:

$$ \lambda_{i} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {If\,a\,sensor\,node\,is\,placed\,at\,\rho_{i} } \hfill \\ {0,} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(19)

$$ \beta_{ij} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {If\,s_{j} \,provides\,coverage\,to\,t_{i} } \hfill \\ {0,} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(20)

$$ \partial_{ij} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {If\,s_{i} \,is\,within\,R_{com} \,of\,s_{j} } \hfill \\ {0,} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(21)

$$ \delta_{i} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {If\,\rho_{i} \,is\,within\,R_{com} \,of\,BS} \hfill \\ {0,} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(22)

Now, the LP of the given problem is defined as follows:

$$ Minimize\sum\limits_{i = 1}^{N} {\lambda_{i} } $$

(23)

Subject to:

$$ \sum\limits_{j = 1}^{Z} {\beta_{ij} \times \lambda_{j} \ge k,\,where\,i = 1\,to\,M} $$

(24)

$$ \left( {\sum\limits_{j = 1}^{Z} {\partial_{ij} \times \lambda_{j} + \delta_{i} } } \right) \ge m,\,where\,i = 1\,to\,Z $$

(25)

$$ \left( {\lambda_{j} ,\beta_{ij} ,\partial_{ij} ,\delta_{i} } \right) \in \left\{ {0,1} \right\} $$

(26)

Constraint 24 ensures the k-coverage of each target point and m-connectivity among the deployed sensor nodes is ensured by the constraint 25. Restriction on the decision variables is given by constraint 26.

3.4 Derivation of Fitness Function

In this chapter, we have studied four nature-inspired algorithms. The algorithms are initialized with population which consists of member of solutions (i.e., chromosomes/vectors/particles/agents). The solutions are evaluated on the basis of fitness function. The following objectives are considered as in [14].

Objective 1 (Deployment of minimum number of sensor nodes): Let us assume that out of given N potential positions, Z numbers of potential positions are selected by particular solution to place the sensor nodes. The first objective is as follows:

$$ Objective\,1{:}\,Minimize\,O_{1} = Z/N $$

(27)

Objective 2 (Maximization of k-coverage): The second objective is to maximize the k-coverage of all the target (M) points in the network which can be stated as follows:

$$ Objective\,2{:}\,Maximize\,O_{2} = \frac{{\sum\nolimits_{i = 1}^{M} {COV_{cost} \left( {t_{i} } \right)} }}{{\left( {M \times k} \right)}} $$

(28)

where coverage cost (COV_cost(t_i)) of t_i, is defined as follows:

$$ COV_{cost} \left( {t_{i} } \right) = \left\{ {\begin{array}{*{20}l} {k,} \hfill & {If\left| {SC_{cov} \left( {t_{i} } \right)} \right| \ge k} \hfill \\ {SC_{cov} \left( {t_{i} } \right),} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(29)

Objective 3 (Maximization of m-connectivity): Deployed sensor nodes on the selected potential positions must be m-connected and toward BS. The third objective can be stated as follows:

$$ Objective\,3{:}\,Maximize\,O_{3} = \frac{{\sum\nolimits_{i = 1}^{Z} {CON_{cost} \left( {s_{i} } \right)} }}{{\left( {Z \times m} \right)}} $$

(30)

where connection cost (CON_cost(s_i)) of s_i is given as

$$ CON_{cost} \left( {t_{i} } \right) = \left\{ {\begin{array}{*{20}l} {m,} \hfill & {If\left| {C_{con} \left( {s_{i} } \right)} \right| \ge m} \hfill \\ {C_{con} \left( {s_{i} } \right),} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(31)

The above objectives are conflicting in nature. Weight sum approach (WSA) [47] is found to be very efficient to form a single fitness function taking multiple multi-objective functions. Thus, WSA scheme is used as follows:

$$ F = w_{1} \times \left( {1 - O_{1} } \right) + w_{2} \times O_{2} + w_{3} \times O_{3} $$

(32)

$$ \begin{aligned} {\text{i}} . {\text{e}} .,\,F = & w_{1} \times \left( {1 - \left( {Z/N} \right)} \right) + w_{2} \times \frac{{\sum\nolimits_{i = 1}^{M} {COV_{cost} \left( {t_{i} } \right)} }}{{\left( {M \times k} \right)}} \\ & + \,w_{3} \times \frac{{\sum\nolimits_{i = 1}^{Z} {CON_{cost} \left( {s_{i} } \right)} }}{{\left( {Z \times m} \right)}} \\ \end{aligned} $$

(33)

where w₂ + w₂ + w₃ = 1 and 0 ≤ w_i ≤ 1, ∀i, i = 1 to 3. The final objective is to maximize the fitness value, i.e.,

$$ Objective = Maximize\,F $$

(34)

Based on this fitness value as defined in Eq. 33, the solutions are evaluated. Solution with higher fitness value is considered as the better solution.

4 GA-Based Approach

4.1 Chromosome Encoding

The chromosomes are encoded as in [14]. Here, the chromosome as a string of zeros and ones is taken. The number of potential positions in the network is taken as the length of the chromosomes. If the value of ith gene is 1 then it implies that the ρ_i is selected for the placement of sensor nodes. Otherwise, no sensor nodes are placed at ρ_i.

Illustration: Let us consider a WSN with nine potential positions. Therefore, length of the chromosome is nine as in Fig. 2. It can be observed that gene value at position 5 is 1 which represents that the sensor node is placed at position ρ₅. Similarly, sensor nodes are also placed at ρ₁, ρ₃, ρ₇, and ρ₉. Whereas no sensor nodes are placed at ρ₂, ρ₄, ρ₆, and ρ₈ as the gene value at positions 2, 4, 6, and 8 is 0.

Fig. 2

Chromosome representation

4.2 Initialization of Population

The initial population is randomly generated set of the chromosomes.

4.3 Fitness Function

Chromosomes are evaluated on the basis of the fitness function as defined in Sect. 2.4, Eq. 31.

4.4 Selection, Crossover, and Mutation Operation

In selection phase, two valid chromosomes called parents are selected from the population which can undergo crossover operation to produce new offspring. There are many selection methods like Roulette-wheel selection, rank selection, tournament selection, etc. Here, Roulette-wheel selection method is used.

Crossover operation is performed on two selected chromosomes. This operation is regulated by the crossover probability. Evolution of the search speed is reformed by varying this crossover probability. There are different types of crossover like one-point crossover, two-point crossover, uniform crossover, etc. Crossover points are chosen randomly in the chromosome beyond that the parent chromosomes exchange their information to produce new child chromosomes. Here, two-point crossover operation is used.

The crossover operation is followed by the mutation operation. In mutation operation, a randomly selected gene value within a chromosome is altered to produce a new species with arbitrary locus in the fitness landscape. Like crossover, performance of mutation operation is also regulated by the mutation probability. Mutation probability is usually lower than crossover probability. Mutation produces a chromosome which cannot converge in the local optimum.

5 PSO-Based Approach

5.1 Particle Representation

It is very essential to represent the particles in such a way that an individual particle must represent the complete solution to the problem. The dimensions of the particle are taken same as the number of potential positions (i.e., N) in the network. A swarm is a set of randomly generated N_P number of particles. The ith particle of the population may be represented by a vector P_i as follows:

$$ P_{i} = \left[ {\beta_{i,1} ,\beta_{i,2} ,\beta_{i,3} , \ldots ,\beta_{i,N} } \right] $$

where each component is given as β_i,d, 0 ≤ i ≤ Np, 1 ≤ d ≤ N. Here, β_i,j represents the jth component of the ith particle. Each component of the particles is initialized by randomly generated uniformly distributed number rand(0, 1), 0 < rand(0, 1) ≤ 1. Here, if the component value (say jth component) of the particle is greater than the defined threshold value (Th) then the corresponding potential position (jth) is being placed with a sensor node. Otherwise, sensor node is not placed at the potential position.

Illustration: Let us consider a WSN with nine potential positions. Therefore, dimension of the particle is same as the number of potential positions, i.e., nine. Figure 3 shows the particle representation of the corresponding WSN. Now, random numbers are generated for each component of the particle. We can also define a threshold value Th (say 0.54) which is compared with each component value. If the generated ith component value is greater than the Th value then the corresponding ith position is selected to place the sensor node. From Fig. 3, it can be observed that the component value at positions 1, 2, 3, 5, 7, and 9 has value greater than the defined Th. Therefore, the potential positions ρ₁, ρ_2, ρ_3, ρ₅, ρ₇, and ρ₉ are chosen for placement of sensor nodes. However, no sensor nodes are placed at potential positions ρ₄, ρ₆, and ρ₈ as the component value at that 4, 6, and 8 is less than Th, i.e., 0.54.

Fig. 3

Particle representation

5.2 Fitness Function

Here, same fitness function is used as discussed in Sect. 3.4, Eq. 31.

5.3 Velocity and Position Update

In each iteration, the velocity and position of the particles are updated using Eqs. 2 and 3, respectively. Similarly, Pbest and Gbest are also updated accordingly.

6 DE-Based Approach

6.1 Vector Representation

The vectors are encoded same as the particles in PSO.

6.2 Fitness Function

The fitness function is used same as in GA and PSO.

6.3 Mutation

For the crossover and mutation operation, the DE/best/1/bin scheme is used. In differential mutation operation (say at tth generation for ith vector), a donor vector (ѵ ^donor _{i, t} ) is created for each member vector (target vector) (ѵ ^tar _{i, t} ) in the population. The best vector (ѵ ^best_i,t ) and other two distinct vectors (ѵ_x,t and ѵ_y,t) are randomly chosen from the population such that i ≠ x ≠ y ≠ best. After that, difference of distinct vectors is multiplied with scaling factor F and added to best vector to generate a donor vector. The mutation operation can be defined as follows:

$$ v_{i,t}^{donor} = v_{i,t}^{best} + F\left( {v_{x,t} - v_{y,t} } \right) $$

(35)

6.4 Crossover

Crossover operation is performed to generate a new vector called trail vector ѵ ^trial_i,t . Here, binomial crossover operation is performed in between donor vector and target vector. We choose a predefined crossover rate (say CR) and operation for crossover can be defined as follows:

$$ v_{i,t}^{trial} = \left\{ {\begin{array}{*{20}l} {v_{i,t}^{donor} ,} \hfill & {if\left( {rand\left[ {0,1} \right] \le CR} \right)} \hfill \\ {v_{i,t}^{tar} ,} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(36)

Each component of the trail vector is generated as follows. For each component, we choose a random value between 0 and 1. Say for ith component of a trail vector a chosen random value is less than or equal to CR than ith component of trail vector is same as the ith component of the donor vector. Otherwise, ith component of trail vector is same as the ith component of target vector.

6.5 Selection

Survival among the trail vector and target vector which acts as a target vector ѵ ^tar _{i, t+1} in the next generation (t + 1) is decided by the selection operation. Derived fitness function as defined in Eq. 31 is used to evaluate both the vectors. If the fitness of the trail vector is found to be better than target vector then it will replace the target vector for the next generation. Otherwise, target vector will be part of next generation. The selection operation is defined as follows:

$$ v_{i,t + 1}^{tar} = \left\{ {\begin{array}{*{20}l} {v_{i,t}^{trial} ,} \hfill & {if\left( {f\left( {v_{i,t}^{trial} } \right) \ge f\left( {v_{i,t}^{tar} } \right)} \right)} \hfill \\ {v_{i,t}^{tar} ,} \hfill & {Otherwise} \hfill \\ \end{array} } \right. $$

(37)

where f(ѵ ^trial _{i, t} ) and f(ѵ ^tar _{i, t} ) represent the fitness of the trail vector and target vector for the generation t.

7 GSA-Based Approach

7.1 Agent Representation

Agents are represented in the same way as the particle.

7.2 Update Velocity, Mass, Position, and Force

The velocity, mass, position, and force of the agents are updated by Eqs. 9, 14, 10, and 15, respectively.

7.3 Fitness Function

Fitness function is used same as in GA, PSO, and DE.

8 Experimental Results

We have performed extensive simulation of the algorithms using MATLAB and C programming. We have considered the scenario for random deployment where potential positions are randomly taken in the network area of 300 × 300 m². BS is located at the position (300, 150) as shown in Fig. 4. The target points are denoted by the black triangle, potential positions are denoted by red circle, and selected potential points are denoted by blue circle. The used simulation parameters for PSO, DE, GA, and GSA are given in Table 1. It should be noted that it is very hard to precisely and accurately finalize the weight values. Therefore, we have tested for various combinations of the weight values and found a better result for w₁ = 0.3, w₂ = 0.3, and w₃ = 0.4. Therefore, we have taken the same.

Fig. 4

Selection of potential positions by a GA, b PSO, c DE, and d GSA

Table 1 Simulation parameters

We first execute the algorithms for $k = 1$ and $m = 1$ with randomly placed 50 target points and 150 potential positions. We have taken the sensing and communication range as 40 meters and 70 meters, respectively. The selected potential positions for the algorithms are shown in Fig. 4a–d. It can be seen that the PSO, DE, GA, and GSA select 36, 41, 27, and 33 potential positions, respectively. The objective 1 of the derived fitness function forces to select minimum number of sensor nodes. Other two fitness functions ensure coverage and connectivity.

We have also executed the simulation by varying the value of k from 1 to 3 and m from 1 to 3. The number of selected potential positions by the algorithms with varying the number of target points is shown in Fig. 5a–c. From Fig. 5a–c, it can also be observed that as the number of target points increases corresponding potential positions also increases for different values of k and m.

Fig. 5

Selection of potential positions by varying the number of target points for a $k= 1$, m − 1, b $k = 2$, m − 2, and c $k = 3$, m − 3

9 Conclusion

In this chapter, we have presented four nature-inspired algorithms, namely, GA-, PSO-, DE-, and GSA-based approach for the deployment of sensor nodes. The objectives for the deployment of sensor nodes are as selection of minimum number of potential positions for the placement of sensor nodes such that all the target points are k-covered along with m-connectivity among the placed sensor nodes. Linear programming is also formulated. Efficient representations of chromosome, particle, vector, and agents are illustrated for GA, PSO, DE, and GSA, respectively. To evaluate the solutions, derivation of an efficient fitness function is given by considering all the objectives. An extensive simulation is conducted for all the algorithms by varying the number of k and m, and target points. As all the algorithms are executed with the same derived fitness function, it is very hard to conclude and compare the performance among them. While, for a particular scenario, GA is proving better performance, for some other scenario, GSA may provide better.

In large industries, the scheme can be used to monitor some critical points like gas leakage, fire zone, etc. As the problem is multi-objective in nature, some suitable multi-objective evolutionary algorithm (MOEA) may be employed for the same. Mobility of the sensor nodes is not considered. The works may be extended by considering the mobility of the sensor nodes. Moreover, energy consumption of the sensor nodes is also not considered.