Optimal sensors placement scheme for targets coverage with minimized interference using BBO

Abstract

A Wireless Sensor Network (WSN) consists of a group of energy-constrained tiny devices called sensors which have sensing, processing, and communicating capabilities. These sensors are deployed in a region of interest for monitoring targets or detecting events, and forwarding the processed data to the sink nodes or gateways. In any wireless network scenario, the targets are to be covered by at least one sensor in the network in order to detect certain events. Maximizing coverage along with improving energy efficiency of the network is a fundamental issue in WSN. Therefore, a Biogeography Based Optimization (BBO) meta-heuristic technique is employed to place sensors in the region of interest. The proposed scheme solves a multi-objective problem using classical weighted sum approach. A fitness function is derived from combination of conflicting objectives, minimum interference, maximum target coverage, and selection of minimum number of sensor nodes along with connectivity of the network as a constraint. The scheme selects minimum number of sensors to deploy in the field of interest which maximizes the target coverage by minimizing the interference of sensors. The proposed scheme is tested on random and grid deployment scenarios. Finally, the scheme is compared with Genetic Algorithm and Random Scheme. The average interference energy loss on BBO-based scheme is found to be 16% less than that of the GA-based scheme, and 60% less than that of a Random-based scheme.

1 Introduction

Recent advancement in the hardware and wireless technology enabled the development of low cost and an energy-constrained tiny devices known as a sensors, that communicate with each other at short distances through a wireless link. The collaborative settings of these tiny devices form a Wireless Sensor Network (WSN) [1]. In the recent past, WSNs have gained tremendous interest among researchers and industrial communities. WSNs finds a wide variety of applications, including precision agriculture, wild life monitoring, forest-fire prevention and detection, military and domestic surveillance systems etc. WSNs have significant applications in urban areas such as traffic, sewage, and air quality monitoring systems. The primary goal of WSNs is to observe and detect events in the given targets and barriers. One of the fundamental concerns of WSNs is to monitor or track events by covering required targets. There are different types of coverages discussed in the literature like target coverage, area coverage, and barrier coverage [2].

Deployment of sensors in a region of interest is categorized into random deployment and deterministic deployment. Placement of sensors in an inaccessible or hostile area allows random deployment. Placement of sensors in predetermined locations allows deterministic deployment or grid deployment [2,3,4].

In random deployment, locations for sensors are unevenly distributed, and hence some regions are highly dense, some regions are sparse. In the dense regions, there is a possibility for more sensor nodes are interfering during the sensing and transmitting of the data. One of the main causes for the quick power drain in WSNs is due to the interference of signals in the wireless media. This results in message drop and requires message retransmission, which in turn affects the energy efficiency of WSNs. Moreover, the deployed network must be able to monitor all the target points by preserving connectivity of the network. Therefore, It is important to minimize the interference of nodes during their deployment to maximize the coverage while maintaining network connectivity.

Due to the advancement of computational intelligence, scientists have adopted nature inspired techniques to solve real world combinatorial science and engineering problems such as applications in industry 4.0 [5]. These techniques have been adopted to solve some optimization problems such as k-coverage and m-connectivity [6], optimal target coverage problem [7], clustering [8], and node localization problems in WSNs [9,10,11]. The proposed scheme employs Biogeography Based Optimization (BBO) meta-heuristic technique, which is motivated by the study of the geographical distribution of living beings [12]. These geographic regions are well suited for living beings called as habitats or islands. The quality of habitat is determined using Habitat Suitability Index (HSI). The Suitability Index Variables (SIVs) characterizes each habitat. The high HSI habitat has a high emigration rate, where as low HSI habitat has a high immigration rate. Therefore, low HSI habitats are more dynamic in their species distribution than high HSI habitats [12]. The BBO is considered to be a powerful search technique because it includes both exploration and exploitation strategies [13]. It shows same characteristic of Genetic Algorithm (GA) and Differential Evolution (DE) in information sharing among neighbor solutions. The BBO is adopted in solving combinatorial problems in WSNs such as k-coverage and m-connectivity [14], clustering and routing [8, 15], sensor node placement with interference minimization [16].

Current article focus on obtaining optimal number of sensors to place in the region of interest for maximizing target coverage and minimizing interference of the sensors while maintaining connectivity of the network.

The contributions of the paper are listed below:

• A novel BBO-based algorithm for optimal sensors deployment with minimum interference and maximum coverage of the target points by preserving connectivity of the network.

• A novel fitness function with an elegant vector encoding scheme.

• The scheme is tested on random and grid deployment scenarios.

• The proposed algorithm is compared with Genetic Algorithm and Random Scheme.

The remaining parts of the paper is organized as follows. Section 2 discusses related work on interference, target coverage, and meta-heuristic schemes in WSN’s. The classical BBO is briefed in Sect. 3. Network model and preliminaries are summarized in Sect. 4. The detail discussion of proposed algorithm is presented in Sect. 5. Simulation analysis and comparison with other methods is shown in Sect. 6. Finally, Sect. 7 concludes the paper.

2 Related work

Diverse variants of topology control based interference minimization solutions for WSNs are discussed in the literature. The author in [17] proved that minimizing receiver interference of the network is NP-hard. An optimal algorithm for minimizing the maximum sender interference proposed in [18]. The authors in [19] proposed an algorithm for minimizing maximum interference as well as total interference of the network. Minimizing maximum and average node interference for WSN is proposed in  [20]. The authors in [21] presented an algorithm which produces the best sender interference spanning tree, which produces minimum interference value for the WSN. To minimize the total interference of the WSNs, authors in [22] assign different power levels to each sensor node to form a connected graph.

There are many coverage problems addressed in the literature. The authors in [23] discussed a heuristic which produces a disjoint sensor cover. The disjoint set covers the entire area and only one of the disjoint is active at a given time. The algorithm achieves a significant improvement in energy saving by preserving coverage area. The authors in [24] adopted an approximation algorithm, where the lifetime of the network is extended without considering a disjoint set; thus a sensor node can present in more than one sensor cover, and also proved that the target coverage problem belongs to NP-Complete class.

There are many works on target coverage problem using different meta-heuristic methods. The authors in [25] proposed a genetic algorithm (GA) technique for wireless sensor node placement with required coverage. However, connectivity constraint is not considered in their work. The authors in [26] solved the coverage problem by designing cover optimization in the first phase and M-connected optimization in the second phase.

In [27] authors proposed Gravitational Search Algorithm (GSA) scheme for wireless sensor node deployment in the network. This scheme provides l-coverage and n-connectivity in the WSN. Authors in [28] adopted territorial predator scent marking algorithm for efficient sensor placement. The proposed scheme achieves maximum coverage and full connectivity with minimum energy consumption. In [29] authors solved both coverage and connectivity problem using improved GA approach, where for a given a set of points, it finds the minimum number of potential positions to place sensor nodes to achieve k-coverage of targets and m-connectivity with other sensors.

Harmony Search (HS) based scheme for wireless sensor node placement is proposed in [30]. The proposed scheme finds an optimal number of sensors and also finds optimal locations to place sensors to maximize the coverage area of the field with minimum network cost. In the paper [31], the authors adopted Imperialist Competitive Algorithm (ICA) to solve the coverage problem, In the proposed technique, efficient formation of cover sets are achieved by activating minimum number of sensor nodes to cover targets in the network. In [7] authors proposed Differential Evolution (DE) based target coverage scheme which assign the targets to sensors optimally to prolong lifetime of the network. The authors in [32] proposed a sensor deployment for target coverage solution using Particle Swarm Optimization (PSO). In this technique mobile sensors are used for coverage patching.

All aforementioned meta-heuristic techniques are used to solve target coverage problem alone or target coverage with connectivity problem in WSN. However, none of them solve combination of interference and target coverage problem by maintaining connectivity of the WSN and hence a novel BBO-based meta-heuristic scheme is adopted to solve the said combined problem.

3 Classical biogeography-based optimization

Biogeography-Based Optimization (BBO) is a widely accepted meta-heuristic algorithm to solve many real world combinatorial problems. It is employed in solving many science and engineering optimization problems. The algorithm has five stages which consist of initialization of habitats or vectors (here onwards habitats and vectors are used interchangeably) fitness calculation, migration, mutation, and selection. The entire process of BBO is shown in Fig. 1.

Fig. 1

Flowchart of classical biogeography-based optimization

Fig. 2

Species model of a single habitat in BBO

The Fig. 2 represents species abundance in a single habitat, where $\lambda$ and $\mu$ are immigration and emigration rates of species, respectively. The variables I and E are maximum immigration and emigration rates, respectively. The variable $S_0$ denotes equilibrium number of species at which immigration and emigration rates are equal. The maximum number of species that can live in a habitat are indicated by $S_{max}$.

The species count at habitat i is given by,

$$\begin{aligned} S_i= S_{max}\times \frac{HSI_{i}}{\sum _{i=1}^{H_{max}}HSI_{i}} \end{aligned}$$

(1)

where $H_{max}$ is the number of habitats. The immigration rate of habitat i is given by,

$$\begin{aligned} \lambda _{i}= I\times \left( 1-\frac{S_i}{S_{max}}\right) \end{aligned}$$

(2)

The emigration rate of habitat i is given by,

$$\begin{aligned} \mu _{i}= E\times \frac{S_i}{S_{max}} \end{aligned}$$

(3)

The essential phases of the BBO algorithm are migration and mutation stages as described below.

3.1 Migration phase

In this stage, information is shared among habitats. High fitness or Habitat Suitability Index (HSI) habitat shares information with low HSI habitat to obtain a better habitat. The habitats are exchanging their information using Suitability Index Variables (SIVs). These SIVs are moved between habitats using their immigration and emigration rates. Suppose first habitat $H_i$ is chosen based on its immigration rate, and second habitat $H_j$ is chosen using emigration rate, then some SIVs are moved from $H_j$ to $H_i$.

3.2 Mutation phase

Habitats are prone to undergo sudden changes due to natural catastrophes. The BBO adopts SIV mutation to model these changes. Each habitat i is associated with a probability $P_i$ to obtain mutation rate $M_i$. The value of the $P_i$ is computed using $\lambda _{i}$ and $\mu _{i}$. The high $P_i$ vector has less chance for mutation and a low $P_i$ vector has a high chance for mutation [12]. The mutation rate is computed using the following formula,

$$\begin{aligned} M_i=M_{max}\times \left( \frac{1-P_i}{P_{max}}\right) \end{aligned}$$

(4)

where $M_{max}$ is user-specified maximum mutation rate, $P_i$ is mutation probability of $i^{th}$ habitat, $P_{max}$ is the maximum mutation probability among habitats, and $M_i$ is the mutation rate of $i^{th}$ habitat.

4 Network model and preliminaries

Fig. 3

An instance of a network model

The network is formed using homogeneous nodes having equal energy, same sensing, and communicating capabilities. Initially, different potential positions for deploying sensors are identified randomly to monitor set of target points. The sensors that are deployed in identified locations forward data to the base station directly or via other nodes. The adopted network architecture for the proposed work is shown in Fig. 3.

4.1 Preliminaries

Suppose P is the set of n potential positions $P = \{p_1, p_2 \ldots , p_n \}$ which are identified positions on a region of interest. Let T denotes the set of k targets $T = \{t_1, t_2, \ldots , t_k\}$ are to be monitored. Let $S =\{s_1, s_2 \ldots , s_m \}$ denotes the set of sensors placed in selected m potential positions.

Let $C_{R}$ and $S_{R}$ represents the communication and sensing range of the wireless sensor nodes respectively. Euclidean formula is adopted to calculate distance measure between two points. If $p=(x_1,y_1)$ and $q=(x_2,y_2)$ two points on two dimensional plane then the distance is computed as follows:

$$\begin{aligned} \text {distance}(p,q)= \sqrt{(x_2-x_1)^2+ (y_2-y_1)^2} \end{aligned}$$

(5)

Let $\alpha _{ij}$, $\beta _{i}$, $\gamma _{i}$, $\delta _{ij}$, $\psi _{i}^{BS}$ are sensing interference, target coverage, selection of potential positions, connectivity between sensors, and connectivity of base station with alteast one sensor respectively. And formally defined as follows:

$$\begin{aligned} \alpha _{ij}= & {} {\left\{ \begin{array}{ll} 1 &{} distance(s_i,s_j) \le 2 \times S_R\ \\ &{} \forall i,~ \forall j,~ 1 \le i,j \le m\\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(6)

$$\begin{aligned} \beta _i= & {} {\left\{ \begin{array}{ll} 1 &{} \exists s_j \in S , ~ Scov(s_j,t_i)=1 \\ &{} \forall i, ~ 1 \le i \le k ~\text {and}~ \forall j, ~ 1 \le j \le m \\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(7)

Where $Scov(s_j,t_i)$ defined as follows,

$$\begin{aligned} Scov(s_j,t_i)= & {} {\left\{ \begin{array}{ll} 1 &{} distance(s_j,t_i) \le S_R\ \\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(8)

$$\begin{aligned} \gamma _{i}= & {} {\left\{ \begin{array}{ll} 1 &{} ~ \gamma _i ~ \text {is selected for node deployment}\\ &{}~ \forall i,~ 1 \le i \le n\\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(9)

$$\begin{aligned} \delta _{ij}= & {} {\left\{ \begin{array}{ll} 1 &{} \exists s_j \in S , distance(s_i,s_j) \le C_R\ \\ &{} \forall i,~ \forall j,~ 1 \le i,j \le m\\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(10)

$$\begin{aligned} \psi _{i}^{BS}= & {} {\left\{ \begin{array}{ll} 1 &{} \exists s_i \in S , ~ distance(s_i,BS) \le C_R\ \\ &{} \forall i,~ 1 \le i\le m\\ 0 &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

(11)

Definition 4.1.1

Sensing Interference Ratio (SIR) of the network is the ratio of total sensing interference experienced by the network to the sum of currently deployed sensors. The underlying formula for SIR is given in Eq. 14.

Definition 4.1.2

Target Coverage Ratio (TCR) of the network is the ratio of the sum of target points covered by the sensors to the total number of target points in the region of interest. The underlying formula for TCR is given in Eq. 16.

Definition 4.1.3

Sensor to Potential Position Ratio (SPPR) of the network is the ratio of sum of potential positions considered for sensor placement to the total number of potential positions. The underlying formula for SPPR is given in Eq. 17.

5 Proposed algorithm

Fig. 4

An instance of vector encoding

Illustration 1

In this article, a BBO based optimal sensors placement with maximum target coverage and minimum interference algorithm is proposed.

Given $P= \{p_1,p_2,p_3,\ldots , p_n$} and $T= \{t_1,t_2,t_3,\ldots , t_k$}, the objective is to choose optimal number of sensors and their positions such that,

• 1. Minimize the sensing interference for the sensor network.

• 2. Maximize the target point coverage of the sensor network.

• 3. Minimize the selection of potential positions to deploy sensors in the network while preserving the connectivity of the network.

5.1 Representation of habitats

In the proposed technique, initial habitats are generated using boolean values. The number of potential positions in a habitat gives length of a vector. Placement of a sensor in $i^{th}$ position is indicated by a boolean value 1 and non placement of a sensor is indicated by a boolean value 0.

5.2 Initialization of habitats

Each habitat represents selection of potential positions to place sensors. The $g^{th}$ generation of $i^{th}$ habitat having length n is represented as follows:

$$\begin{aligned} H_{i,g} = [SIV_{1,i,g}, SIV_{2,i,g}, SIV_{3,i,g}, \ldots , SIV_{n,i,g}] \end{aligned}$$

(12)

The Habitat Suitability Index(HSI) measures the fitness or goodness of $i^{th}$ habitat as indicated below:

$$\begin{aligned} HSI_{i,g} =f([SIV_{1,i,g}, SIV_{2,i,g}, SIV_{3,i,g}, \ldots , SIV_{n,i,g}]) \end{aligned}$$

(13)

Suppose there are 6 targets $T =\{t_1, t_2, \ldots , t_6\}$ and 8 potential positions $P =\{p_1,p_2, \ldots , p_{8}\}$ are considered as shown in Fig. 4a. The number of potential position is the length of the habitat, which is 8 as according to Fig. 4b.

Figure 4b represents a encoded habitat. The binary value 1 in the positions $p_1, ~ p_2, ~ p_3, ~ p_6, ~p_7$ and $p_8$ indicates that the sensor nodes are deployed on these potential positions. The binary value 0 in the positions $p_4 ~\text {and} ~p_5$ denotes that the sensor nodes are not placed on these potential positions.

5.3 Derivation of fitness function

Objective 1

It is to minimize SIR and is formally defined as follows:

$$\begin{aligned} \text {Minimize} ~ o_1 = \frac{1}{m }\sum _{i=1}^{m}\sum _{j=i+1}^{m} \alpha _{ij} \end{aligned}$$

(14)

where m is the number of position selected to deploy sensor nodes.

OR

$$\begin{aligned} \text {Maximize} ~ {o_1}' = 1-\frac{1}{m}\sum _{i=1}^{m}\sum _{j=i+1}^{m} \alpha _{ij} \end{aligned}$$

(15)

Objective 2

It is to maximize TCR and is formally defined as follows:

$$\begin{aligned} \text {Maximize} ~ o_2 = \frac{1}{k}\sum _{i=1}^{k} \beta _i \end{aligned}$$

(16)

Objective 3

It is to minimize SPPR and is formally defined as follows:

$$\begin{aligned} \text {Minimize} ~ o_3 = \frac{1}{n}\sum _{i=1}^{n} \gamma _{i} \end{aligned}$$

(17)

OR

$$\begin{aligned} \text {Maximize} ~ {o_3}' = 1.0- \frac{1}{n}\sum _{i=1}^{n} \gamma _{i} \end{aligned}$$

(18)

Since all the objectives are conflicting in nature, a final objective function(O) is devised by applying a weighted sum approach  [33, 34] as shown below:

$$\begin{aligned} \text {Maximize } ~ O = w_1 \times {o_1}' + w_2 \times {o_2}+ w_3 \times {o_3}' \end{aligned}$$

(19)

Subject to

$$\begin{aligned} \frac{1}{m}\sum _{i=j=1}^{m} \delta _{ij} \times \gamma _{i} + \psi _{i}^{BS} = 2 \end{aligned}$$

(20)

here $w_i$ is a weight variable, with $0 < w_i \le 1,~ 1 \le i \le 3$, $w_1 + w_2 +w_3 =1$, $\delta _{ij} \in \{0,1\}$, $\gamma _{i} \in \{0,1\}$ and $\psi _{i}^{BS} \in \{0,1\}$

The total interference energy loss ($E_{Loss}^{Total}$) of the network is defined as the total energy drain due to interference in the network and formally defined as follows:

$$\begin{aligned} E_{Loss}^{Total}= I_{Count}^{Total} \times E_{Loss}^{Interference} \end{aligned}$$

(21)

where $I_{Count}^{Total}$ and $E_{Loss}^{Interference}$ are interference number of the network and the energy loss per interference respectively.

Illustration 2

Consider an optimal placement of sensors as shown in Fig. 4b and corresponding SIR determination and TCR determination are shown in Tables 1 and  2 respectively.

Table 1 Optimal sensor nodes placement (SIR determination)

Table 2 Optimal sensor nodes placement (TCR determination)

The variable $Icnt(s_i)$ and $Scov(t_i)$ represents interference count of the sensor $s_i$ and sensor coverage of the target $t_i$ respectively. The value 1 in the cell indicates that whether the sensor covers another sensor or target and the value 0 indiates sensor is not covered by other sensor or target.

The fitness value of the vector is computed using the Eq. 19 is given by,

$O_1=w_1 \times o'_1 + w_2 \times o_2 + w_3 \times o'_3$, where $w_1 =0.3, ~ w_2=0.4, ~ w_3=0.3 ~ \text{and}\, o'_3=1.0 -\frac{m}{n} =1.0-\frac{6}{8}$

$O_1=0.3 \times 1 + 0.4\times 1.0 + 0.3 \times 0.25=0.775$, here $o'_1$, $o_2$ are taken from Tables 1 and  2.

Table 3 Non optimal sensor nodes placement (SIR determination)

Table 4 Non optimal sensor nodes placement (TCR determination)

The non optimal sensor placement of sensors vector is shown in Fig. 4c. The fitness value of vector computed using the Eq. 19 is given by, $O_2=0.3 \times 0.33 + 0.4 \times 0.67 + 0.3 \times 0.25=0.442$,  here $o'_1$ and $o_2$ are taken from Tables 3 and  4 respectively. where $w_1 =0.3, ~ w_2=0.4, ~ w_3=0.3 ~ \text {and} ~ o'_3=1.0 -\frac{m}{n} =1.0-\frac{6}{8}$

Since it is a maximization problem, the habitat having fitness value $O_1=0.775$ is better than that of the habitat having fitness value $O_2=0.442$. The computed interference energy loss for the network with non optimal sensor nodes placement using Eq. 21 is 0.08 Joule and which is ideally zero in the network with optimal sensor nodes placement.

5.4 Migration

In this stage, habitats $H_i$ and $H_j$ are selected stochastically based on immigration rate $\lambda _i$ and emigration rate $\mu _j$ respectively. After choosing habitats a random number is generated between (0, 1). If the random number is less than $\lambda _i$, then migration is performed between habitats. To perform the migration, a random position is selected between (1, n), and SIV are shifted from habitat $H_j$ to habitat $H_i$ from the selected position to the last position of habitat $H_j$.

5.5 Mutation

This process involves the selection of a vector based on mutation probability of respective vector. Once the habitat is selected, check for value at the position, if the value is 1 then it is changed to 0; otherwise to 1.

5.6 Pseudo-code of BBO-based sensor placement algorithm

The proposed scheme is depicted in Algorithm 1. The algorithm consists of two main stages. They are the migration process (lines 18–29) and the mutation process (lines 30–36). Initially, the $best_{fitness}$ and $M_{max}$ are set to value 0 and value 0.2 respectively (line 1). The habitats are initialized with 0’s and 1’s (lines 2–4). The initial iteration is set to 1 (line 5) and the entire procedure for the BBO is presented (lines 6–38). Firstly, fitness computation for each habitat and selection of best habitat that has highest fitness value are performed (lines 7–11). The species count of each habitat is calculated (lines 12–14). Next, immigration rate and emigration rate are computed for each habitat (lines 15–17). In lines 18-29, the migration procedure is presented. Each habitat $H_i$, a associated habitat $H_j$ is selected based on emigration rate to perform SIV’s migration from habitat $H_j$ to habitat $H_i$ (lines 18-19). In this process, a random number is generated (line 20). If the generated random number is less than the emigration rate of habitat $H_j$ (line 21), then a random position $p_1$ is selected in habitat $H_j$ (line 22). Next, all SIV’s from position $p_1$ to position n are moved from habitat $H_j$ to habitat $H_i$ (lines 23-26). In lines 30-36, a habitat mutation procedure is presented. Firstly, immigration rate and emigration rate of the each habitat is used to compute its mutation probability (line 30). A habitat $H_i$ is selected which has maximum mutation probability ($p_{max}$). A random number is generated (line 32). If the generated random number is less than the maximum mutation probability, then a random position $p_2$ is selected in habitat $H_i$ (lines 33-34). Next, if the value of the position $p_2$ is 1, then replace it is with 0; othewise it is with 1 (line 35). Goto line 6 and repeat the process till the maximum iteration is reached and the algorithm terminates. Finally, the habitat with best solution is selected for placing sensors (line 39).

6 Simulation and discussion

This section discusses performance analysis of the proposed scheme and gives comparative analysis with other schemes. The experiments are carried out using MATLAB 2018a on an Intel(R) Core(TM) i5-8250U CPU@1.60 GHz 1.80 GHz and 8 GB RAM running on Microsoft Windows 10, 64-bit operating system, x64-based processor.

A WSN is created with n number of potential positions and k number of target points. A 300 $\times$ 300 network field is created and sink is placed at the center of the field (150, 150). The potential positions and target points are randomly generated on the field. The parameter values for the WSN is mentioned in Table 5.

Table 5 Simulation parameters

The proposed technique is compared with Random scheme and GA based scheme for performance comparisons. In Random scheme, the potential positions to deploy sensors to cover the given target points are identified randomly using uniform distribution. If the identified potential positions form the connected network, then these potential positions are considered for placing sensors. The SIR and TCR are computed for these sensors. The GA algorithm is a optimization technique or heuristic solution-search method proposed by John Holland. The main components of the GA algorithms are the chromosome representation, the fitness function evaluation, cross over, mutation, and selection [35]. We adopted single-point cross over and roulette wheel selection method in this algorithm.

The parameter settings for heuristic techniques are decided as follows. The 200 potential positions and 200 target points are used to find appropriate simulation parameters. A population size of 100 habitats and 100 generations are considered for the experiments and verified experimentally that these generic parameter values are enough for proper convergence of the proposed algorithm. However, the control parameter mutation probability $M_{max}$ for BBO method is adopted from [14] and also verified with different values of $M_{max}$ and confirmed that results are comparatively better for $M_{max}=0.2$. It is observed in the literature that the control parameter like mutation rate for GA is set between 0.01 to 0.05. Therefore, the mutation rate is set to 0.02 and varied the crossover rate from 0.1 to 0.9 and confirmed through repeated experiments that the result is better when crossover rate is 0.2. The final parameter settings for heuristic methods for the simulations are mentioned in Table 6.

Table 6 Parameter settings for BBO and GA

Table 7 Weight values and multi-objective results (potential positions = 200 and targets = 200)

Table 8 BBO multi-objective results (normalized)

Table 9 GA multi-objective results (normalized)

Fig. 5

Pareto solutions for SIR, TCR and SPPR on different weight values

In the Eq. 19, the second component (TCR) is the maximization component and other two components(SIR and SPPR) are the minimization components. Therefore, weight of second component $w_2$ is varied from 0.1 to 0.9 in steps of 0.1 and accordingly equal weights are assigned to $w_1$ and $w_3$ to decide appropriate weight values. The results are computed for 15 instances of experiments for each set of weight values for $w_1$, $w_2$ and $w_3$ and mean result is tabulated in Table 7. The multi-objective results for BBO and GA approaches are presented in normalized form in Tables 8 and  9 respectively using the Eq. 22.

$$\begin{aligned} {x_i}^{normalized}= \frac{x_i}{\sqrt{\sum _{1}^{n}{x_i}^2}} \end{aligned}$$

(22)

here $x_i$ denotes each data value and n represents number of data values present.

The Pareto solution  [33] for SIR, TCR, and SPPR on different weight values is shown in Fig. 5. It is required note that the selection of weight values in a precise and accurate manner is very difficult, even for someone familiar with the problem domain [36]. Therefore, we adopted weight values $w_1=0.3$, $w_2=0.4$ and $w_3=0.3$ in both heuristic methods for simulations.

6.1 Result and analysis

This Section details the result analysis of the experiments that are carried out.

Fig. 6

Performance of proposed scheme

Fig. 7

Scenario 1: candidate positions are on a grid

Fig. 8

Scenario 2: candidate positions are random

Fig. 9

Best performance on grid and random scenario

Fig. 10

Mean performance on grid and random scenario

The experiments are performed using same data on all three algorithms. The 30 instances of experiments are carried out for each set of targets to handle the random nature of these algorithms. Figure 6 shows the performance analysis of BBO-based scheme when the number of target points increase from 50 to 200. The 30 instances of experiments are carried out on each set of target points and the graph is drawn by taking the best and mean of the results. Here, 200 potential positions are identified to deploy sensors. It is observed from the graph that the $\mathrm {BBO\_SIR}$ increases when the number of target points increase. It is because of more number of potential positions are selected to place sensors, which gives scope for more interference of signals. The simulations are performed on grid and random scenarios as shown in Figs. 7 and 8. The Figs. 9 and 10 illustrates the best and mean comparison of SIR and TCR for grid and random scenarios respectively when target points increase from 25 to 100. The 30 instances of the experiments are carried out on each set of target points and graph is drawn by taking best and mean of the results. In these experiments, 100 potential positions are identified to deploy sensors. In both the graph, it is observed that the best and mean $\mathrm {Grid\_SIR}$ is zero, which is to indicates no sensors are interfering with each other due to the fact that potential positions are identified on grid cross points. It is also seen that the $\mathrm {Random\_SIR}$ increases as the number of target points increase. $\mathrm {Grid\_TCR}$ is better than that of the $\mathrm {Random\_TCR}$ because the targets are optimally covered in grid scenario as compared to random scenario.

Fig. 11

SIR performance comparions between BBO, GA, and random schemes

Fig. 12

TCR performance comparions between BBO, GA, and random schemes

Fig. 13

Selected positions comparions between BBO, GA, and random schemes

Fig. 14

Energy loss comparions between BBO, GA, and random schemes

Table 10 Comparison results for SIR (30 instance of experiments are conducted )

Table 11 Comparison results for TCR (30 instance of experiments are conducted)

The comparison results for SIR for different values of targets is tabulated in Table 10 as best, worst, mean, standard deviation, and 95% Confidence Interval (CI). It is observed that in all algorithms SIR is increases with increase in target points. It is due to more number of sensors are required to cover as number of target point increases and hence more scope for interference. Similarly, the comparison results for TCR for different values of targets is tabulated in Table 11 as best, worst, mean, standard deviation, and 95% Confidence Interval (CI). It is noted that the TCR decreases as number of target points increase in all algorithms. It is also observed that the $\mathrm {BBO\_TCR}$ decreases when number of targets increase.

Figures 11 and  12 depicts the performance comparisons of the BBO-based scheme, GA-based scheme, and Random-based scheme for SIR and TCR respectively. Here, number of target points increases from 50 to 200. The 30 instances of experiments are carried out for each set of target points. The best and mean of these results are depicted in the graph. In these experiments, 200 potential positions are identified to deploy sensors. It is observed that the SIR is low in BBO-based scheme as compared to the other scheme and TCR is better than that of the other schemes. Figure 13 illustrates the number of selected positions between BBO-based scheme, GA-based scheme, and Random scheme when number of target points increase from 50 to 200. The 30 instances of experiments are carried out to obtain results. The graph shows the best and mean of these results. In these experiments, 200 potentials positions are identified to deploy sensors. It is observed that the number of selected positions to place sensors are less in BBO-based scheme as compared with other schemes. The BBO-based scheme outperforms the GA-based scheme due to the premature convergence behavior of the GA over BBO. Finally, Fig. 14 depicts performance of the average network energy loss due to interference when number of target points increases from 50 to 200. In these experiments, 200 potential positions are identified to deploy sensors. Figure 14 shows average energy loss in network of BBO-based scheme is better than that of other schemes. It is also noted that the average energy loss in network due to interference in BBO-based scheme is 16% less than that of GA-based scheme and 60% less than that of the Random-based scheme.

7 Conclusion

In this paper, optimal sensors placement BBO-based scheme is proposed with a combined goal of maximized target coverage and minimized interference while maintaining connectivity of the network. An elegant vector encoding for habitat representation and novel fitness function is formulated for the proposed scheme. Working of the proposed scheme is illustrated with suitable example. The performance study of sensing interference ratio and target coverage ratio on grid and random scenarios were conducted. A comparison study of the BBO-based scheme with other scheme was carried out. The least energy loss due to interference in BBO-based scheme confirms its superiority over other schemes. In future, a fuzzy model can be incorporated to find better results.