1 Introduction

Recent evolution in sensing and communication technologies have facilitated the development of smart sensing devices for development of smart environment such as smart cities, smart grid, smart home, smart border surveillance, smart target tracking and detection system [1]. These smart sensing devices, also called sensor nodes, are generally small size and operated with help of 2AA battery power. For remote monitoring and/or target tracking application, these sensor nodes are deployed over the area of interest. Since these sensor nodes are generally self-aware and self-configurable, thus form a distributed network after deployment and bootstrapping process. This kind of distributed network is called wireless sensor network (WSN) [1].

There are generally two types of schemes for deployment of sensor nodes over a target area of interest, such as ad-hoc scheme or pre-planned scheme [2]. Ad hoc node deployment scheme is generally helpful in an unfriendly environment such as dense forest and deep sea where human accessibility is very hard [2, 3]. However, this scheme involves a large number of sensor nodes to guarantee full coverage and connectivity of the target region. For this kind of scheme, management of network connectivity and detection of failures are very difficult. The pre-planned node deployment scheme is generally used for the target area which is easily accessible. The main advantages of this scheme include better network topology management and consume less energy. In addition, pre-planned scheme is cost effective [4]. Although, for both kind of node deployment schemes, maintaining desired coverage and connectivity requirements are a very challenging issues [4]. These issues are challenging due to fact that each sensor node has limited communication range, limited power source, prone to malfunctions by some external events and communication link among nodes may be disturb due to wireless link failure. Due to these reasons, coverage of the target points and connectivity between nodes are very essential research challenge [4, 5].

In WSN, coverage problem can be categorized based on the region/specific region/object to be covered [6, 7]. In literature, it is categorized into three groups such as area coverage, barrier coverage, and target coverage problem [6,7,8,9,10,11]. In this research work, we focus on target coverage problem in which each target should be covered by at least one sensor node. In order to provide coverage with high degree of reliability, k-coverage problem is considered where each target region should be covered by at least k sensor nodes [8]. Here k is a pre-defined integer constant and its value depends on the application. In addition, connectivity among the sensor nodes that are covering the target points is also considered in this paper. A sensor node said to be m-connected if there are at least m other sensor nodes in its communication range. In this paper, we consider both “coverage and connectivity” requirements for monitoring a set of target points by an optimal number of sensor nodes [10].

1.1 Problem statement and our contributions

In the literature, it is pointed out that “k-coverage and m-connected” suitable positions node placement problem is a NP-complete problem [3, 7, 10, 11]. In this problem, a set of target points {t1, t2, t3,… tK}and a set of pre-defined suitable positions {p1, p2, p3,…pM}are given. We have to choose an optimal number of suitable positions to locate nodes so that it satisfy both “k-coverage and m-connectivity” requirements.

In order to solve above said problem, we have proposed a BBO [12,13,14] scheme to identify a set of optimal number of suitable positions to locate sensor nodes so that all target region are k-covered and it also satisfies m-connectivity requirement. Our key contributions are listed as follows:

  1. (a)

    A BBO-based node placement algorithm is presented that satisfies “k-coverage” for a given set of target points and “m-connectivity” for the covering sensor nodes.

  2. (b)

    An efficient encoding scheme for the habitat representation is discussed.

  3. (c)

    A novel objective functions along with the BBO’s migration and mutation operators are formulated.

  4. (d)

    Performance evaluation of the proposed algorithm and its comparative study with the state-of-art schemes is also presented under different network scenarios.

1.2 Organization of the paper

The remaining parts of this paper are structured as follows: Sect. 2 presents a brief discussion on the related works on the nature-inspired meta-heuristic algorithms for node deployment with required degree of coverage and connectivity. In Sect. 3, a brief overview of BBO based optimization and system model and different assumptions are presented. Section 4 provides formulation of node placement problem, objective function and a detail explanation of the proposed BBO-based scheme. Section 5 presents performance evaluation and its analysis. Finally, Sect. 6 discusses conclusion and suggest some future works.

2 Related work

This section presents a brief review of the related works on connected target coverage problem. Since problem of “k-coverage and m-connectivity” aware node placement problem is a NP-complete problem. Thus, an approximate solution for this type of problem is required. In literature, several approximate solutions are proposed for target coverage problem. Generally, connected target coverage problem is solved by using either heuristic algorithm or nature-inspired meta-heuristic algorithm. This section presents a brief discussion on the meta-heuristic based solutions proposed for connected target coverage problem.

Younis et al. have reviewed several schemes proposed for coverage problem in [11]. In [15], an efficient bi-population-based evolutionary algorithm is proposed for full area coverage problem. In this work, proposed algorithm uses different fitness functions for the evaluation of partial-coverage and full-coverage based sensor deployment solutions. In [16], Lanza et al. have discussed relay node placement problem using multi-objective meta-heuristics techniques using three different sub-objectives such as energy, sensitive area coverage and reliability. This approach did not consider full coverage with desired connectivity issue. Liu et al. [4] have discussed an energy efficient algorithm for maintaining coverage and connectivity. This algorithm employs redundant nodes for maintaining the full “coverage and connectivity” in the network. Authors have also proposed a scheme for determining the maximal disjoint sets of the nodes for desired “coverage and connectivity” in the network and proof that this problem is NP-complete problem.

In [17], authors have focused on k-connected deployment and distribution of power resources with objective to enhance coverage and network lifetime. This scheme uses a decomposition based multi-objective evolutionary scheme to discover the minimum number of sensor nodes for coverage to ensure desired connectivity. A multi-objective based evolutionary scheme is proposed in [18] for enhancing the network lifetime and the network coverage. Authors have established a trade-off between these two issues, but did not consider network connectivity issues in this work. A genetic algorithm (GA)-based scheme for sensor nodes deployment with the sufficient coverage has been presented in [19]. This scheme used Mante-Carlo-based mathematical modeling and simulation for solving this problem. However this did not consider connectivity issues in their proposed scheme.

In [20], an optimal relay node placement scheme at pre-specified locations with the desired level of connectivity is proposed. This scheme used a mixed integer linear programming optimization for formulating and optimizing the problem under different constraints. In [21], authors have proposed a heuristic algorithm for “M-connected target coverage problem”. The proposed algorithm considered three different types of coverage such as k-coverage, Q-coverage and simple coverage. This scheme creates an optimized cover set for solving the coverage issue and adds the remaining sensor nodes one-by-one to ensure connectivity in the network. The main limitation of this approach is its high complexity. In [22], authors have discussed an integer linear programming (ILP)-based optimization scheme for evaluating the minimum number of suitable positions for the localization of the relay nodes in such a way that it satisfy k-coverage of the target region.

In [23], a GA-based relay node placement scheme is proposed. In this scheme, “minimum number of relay nodes” are evaluated to localize them at given suitable positions. These schemes focus on “k-connectivity” issue between sensor nodes and the relay node. However, they did not consider “k-connectivity” issues among the relay nodes. In [24], Rebai et al. have discussed a GA-based scheme for finding the optimal number of positions to locate an optimal number of nodes which satisfy full coverage of target area and also ensure satisfactory connectivity among the sensor nodes. The main limitation of this scheme is that sometimes crossover operation may produce invalid offspring. This problem is rectified in [25] by Gupta et al. and they have proposed an improved GA-based solution for node placement for coverage of the given set of target points. This scheme presents “k-coverage” for targets and also “m-connectivity” among sensor nodes. This scheme is also sometimes generates an invalid chromosomes after crossover and mutation operations. In addition, each sensor sends its sensed data directly to the base station which causes limited scalability and faster energy dissipation of sensor nodes, thus poor network lifetime. In [26], authors have proposed a Gravitational Search Algorithm (GSA)-based scheme for node placement with requirement of l-coverage and n-connectivity in the network. The main limitation of GSA-based scheme is that it sometime misses out the global solution after updation of the agent’s velocity and position. Like [25], in [26], each sensor node sends its observed sensor reading directly to the base station which causes faster energy dissipation and limits the scalability of the network.

In order to improve the network lifetime and scalability issues of the scheme mention in [25, 26], a BBO-based meta-heuristic algorithm is proposed in this paper which is already proved its performance over GA-based meta-heuristic algorithm in various application domains [14]. The proposed BBO-based algorithm confirms its performance over GA-based and GSA-based schemes in terms of finding the optimal number of suitable positions and network lifetime under different combination of (k, m) for ensuring target coverage and network connectivity.

3 Background

In this section, first a brief overview of the biogeography-based optimization scheme and its working process is presented. Next, several assumptions and system model is discussed.

3.1 Overview of the biogeography-based optimization (BBO)

Biogeography-based optimization (BBO) is a population-based global optimization technique which was engineered by Simon in 2008 [12]. It is modeled by using the concept of natural immigration and emigration of species. Some species are moving from One Island to another in search of more friendly habitats. In BBO, a habitat is characterized as any area/island which is geographically detached from other islands. Islands that are well to the biological species are having a high Habitat Suitability Index (HSI). A Suitability Index Variable (SIV) is used to characterized livelihood conditions and the area of habitat. In BBO, a habitat with a highest HSI tends to accommodate a large number of species. Each individual is represented as a habitat with a HSI value which is analogous to the fitness of an evolutionary algorithm. A best solution is similar to an island with highest HSI and a worst solution is similar to an island with lowest HSI value [12,13,14].

BBO works in two phases: Migration and Mutation. These phases are briefly described as follows:

  1. (a)

    Migration Phase This phase is employed to share information between the candidate solutions. Suppose there is an optimization problem. Solution search space for this problem is represented as a population of candidate solutions. Each candidate solution vector is an n-dimension vector characterized as a habitat. Like GA and PSO-based optimization techniques, in BBO, high HSI solution shares information with the low HSI solution in order to improve the solution. In BBO, immigration and emigration rates are used for sharing the information. In this phase, first a habitat (Hi) is selected using immigration rate and another habitat (Hj) is selected using emigration rates. After this, some SIVs are migrated from habitat Hj to the habitat Hi.

  2. (b)

    Mutation Phase In an island, population of the species (i.e. HSI) of a natural habitat is significantly deviated due to Cataclysmic events. In order to model the effects of these Cataclysmic events, BBO uses mutation operator. Each habitat, say i, is associated with a probability (Pi) to calculate its mutation rates. If value of Pi is high, there is less possibility of mutation and corresponding candidate solution is close to the optimized solution. It value of Pi is low, there is high possibility of mutation and the corresponding candidate solution is far away from the optimized solution.

3.2 Assumptions and system model

In this research work, a WSN system is modeled where a set of targets are identified and located in an area of interest. In the area of interest, a set of locations is pre-defined where an optimal number of sensor nodes for sensing and monitoring of the given set of target points are to be located. We assume that all target points and suitable positions are stationary and sensor nodes that are covering the target points are also stationary. A sensor node is covering a target point only if it is in its sensing range. A sensor can cover more than one target points. Data collection operations are periodic and divided into rounds similar to scheme proposed in [27,28,29,30]. In each round of data collection, a node senses the targets and reports the target tracking information to the base station.

4 Proposed method

4.1 LP-formulation for node placement problem

Let a set of targets (X = {x1, x2… xT}) and a set of pre-defined possible suitable positions (Y = {y1, y2… yM}) is given. In the problem of the “k-coverage and m-connected” node placement, we have to select an optimal number of suitable positions to locate nodes so that it satisfies “k-coverage and m-connected” for a given value of k and m [21, 25, 26]. Let Trange and Srange represents transmission and sensing range of the sensor nodes, respectively. SCover(ti) is used for determine the set of sensor nodes that are coving a target \(t_{i}\). TCover(si) is used to determine the set of target points that are covered by sensor node si. Connectivity (si) is used to determine set of sensor nodes that are within the direct communication range of nodesi. Mathematical expression for Connectivity (si), SCover(ti), and TCover(si) are illustrated in Eqs. (1), (2) and (3), respectively.

$$Connectivity\left( {s_{i} } \right) = \left\{ {s_{j} } \right.|{\text{dist}}(s_{i} ,s_{j} ) \le T_{range} , \forall j, 1 \le j \le M$$
(1)
$$SCover\left( {t_{i} } \right) = \left\{ {s_{j} } \right.|{\text{dist}}(t_{i} ,s_{j} ) \le S_{range} , \forall j, 1 \le j \le M$$
(2)
$$TCover\left( {s_{i} } \right) = \left\{ {t_{j} } \right.|{\text{dist}}(t_{j} ,s_{i} ) \le S_{range} , \forall j, 1 \le j \le T$$
(3)

In order to formulate “k-coverage and m-connected” node placement problem, three variables aij, bij and ci, are defined for deciding the coverage of target by sensor nodes, connectivity among the sensor nodes and selection of suitable positions, respectively. These variables are defined as follows:

$$a_{ij} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {if\,target\,t_{i} \,is\,covered\,by\,sensor\,node\,s_{j} } \hfill \\ {0,} \hfill & {otherwise } \hfill \\ \end{array} } \right.$$
(4)
$$b_{ij} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & { if\,a\,sensor\,node\,s_{i} \,is\,directly\,conned\,to\,sensor\,node\,s_{j} } \hfill \\ {0,} \hfill & {otherwise } \hfill \\ \end{array} } \right.$$
(5)
$$c_{i} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & { if\,a\,potential\,position\,p_{i} \,is\,selected\,for\,node\,placement\,1 \le i \le Y} \hfill \\ {0,} \hfill & {otherwise } \hfill \\ \end{array} } \right.$$
(6)

LP-formulation for “k-coverage and m-connected node placement problem” can be expressed as follows:

$${\text{Minimize}}\;P = \mathop \sum \limits_{i = 1}^{Y} c_{i}$$
(7)

Subject to

$$\mathop \sum \limits_{i = 1}^{M} a_{i,j} \ge k,\forall i, 1 \le i \le N$$
(8)
$$\mathop \sum \limits_{i = 1}^{M + 1} b_{i,j} \ge m,\forall i, 1 \le i \le M$$
(9)

4.2 Derivation of objective function

Objective function is used to determine the quality of a habitat in BBA-based scheme. In our proposed scheme, following parameters are used for derivation of the objective function.

  1. (a)

    Coverage of the target (\(f_{1}\)) In order to provide k-coverage to a target, at least k sensor nodes have to cover a target [25]. So our first objective in terms of coverage of the target is defined as follows:

    $$Maximize\quad f_{1} = \frac{1}{T \times k}.\mathop \sum \limits_{i = 1}^{T} CoverCost\left( {t_{i} } \right)$$
    (10)

    where T is number of number of target points and coverage cost (\(CoverCost\left( {t_{i} } \right)\)) of a target ti is calculated using Eq. 11.

    $$CoverCost\left( {t_{i} } \right) = \left\{ {\begin{array}{*{20}l} {k,} \hfill & {if\,\left| {{\text{SCover}}\left( {t_{i} } \right)} \right| \ge k} \hfill \\ {k - \left| {{\text{SCover}}\left( {t_{i} } \right)} \right|} \hfill & {otherwise} \hfill \\ \end{array} } \right.$$
    (11)
  2. (b)

    Connectivity of the sensor nodes (f2) In order to satisfy m-connectivity of the sensor nodes, each sensor node, which is covering the target, should be connected to the base station [21, 25, 26]. So our second objective in terms of m-connectivity of the sensor node is defined as follows:

    $$Maximize\quad f_{2} = \frac{1}{P \times m} \times \mathop \sum \limits_{i = 1}^{P} ConnectivityCost(s_{i} )$$
    (12)

    where P is number of suitable points selected out of M possible suitable positions to place the nodes and connectivity cost (\(ConnectivityCost\left( {s_{i} } \right)\)) of a sensor node si is calculated using Eq. 13.

    $$ConnectivityCost\left( {s_{i} } \right) = \left\{ {\begin{array}{*{20}l} {m,} \hfill & {if\,\left| {{\text{Connectivity}}\left( {s_{i} } \right)} \right| \ge m} \hfill \\ {m - \left| {{\text{Connectivity}}\left( {s_{i} } \right)} \right|} \hfill & {otherwise} \hfill \\ \end{array} } \right.$$
    (13)

Selection of Suitable positions (\(f_{3}\)) The main purpose of the proposed solution is to select a minimum number of suitable points (P) so that all targets points will satisfy k-coverage and the sensor nodes that are covering the targets are also fulfill m-connectivity for some given value of k and m. So, our third objective in terms of optimal suitable positions is defined as follows:

$$Maximize\quad f_{3} = \left( {1 - \frac{P}{M}} \right)$$
(14)

Based on the individual objectives as described above, we can devised a multi-objective function (F) which is weighted sum of the f1, f2, and f3.

$$Maximize \quad F = w_{1} \times f_{1} + w_{2} \times f_{2} + w_{3} \times f_{3}$$
(15)

Here, \(w_{i}\) is weight, where \(0 < w_{i} \le 1, 1 \le i \le 3\), and \(w_{1} + w_{2} + w_{3} = 1\). The value of weight w1,  w2,  and w3 is used to set the part of each sub-objective function (fi) to determine the quality of the solutions. In order to provide best solution for the node placement, we have tested with different combination of the value of w1,  w2,  and \(w_{3}\). Through experiments, it is observed that \(w_{1} = 0.30, w_{2} = 0.30, and w_{3} = 0.40\), provides best solution. The main objective of BBO algorithm is to find best habitat with better fitness value.

4.3 BBO-based node placement algorithm

In this section, a detail description of BBO-based “k-coverage and m-connected” node placement algorithm is explained. Proposed algorithm selects near-optimal suitable positions to locate the sensor nodes for fulfilling “k-coverage and m-connected” in the network. Proposed scheme has divided into four operations such as illustration of the habitat, habitat initialization, habitat mutation and migration. Each operation is discussed in detail as follows:

figure c
  1. (a)

    Illustration of habitat In BBO-based scheme, a habitat illustrates a candidate solution for a given problem. In the suitable position node placement problem, a habitat represents a set of suitable positions. The size of each habitat is equal to the number of suitable positions available.

  2. (b)

    Initialization of habitat In BBO, initial population is a randomly generated in order to set a number of habitats. Each habitat is a solution vector which is encoded using binary number. Pseudo-code for initializing the population is illustrated in Algorithm 1.

  3. (c)

    Habitat migration In the migration phase of BBO-based scheme, two habitats Hi and Hj are chosen probabilistically based on the immigration rate (Ii) and emigration rate (Ej), respectively. After selection of habitat Hi and Hj, generate a random number r1 between (0,1) if generated value r1 is less than \(I_{i}\) them habitat migration is performed. In habitat migration, one position is randomly generated between 1 and P. From generated position to last position, all population of Hj is shifted in Hi solution. In this way, all habitats are updated until best solution is achieved. Pseudo-code for Habitat Migration is given in Step 11 to Step 19 in Algorithm 1.

    In Fig. 1, the working of habitat migration operator is illustrated. In Fig. 1, step 1, five habitats (H1–H5) is taken and randomly initialized them with binary number 0 and 1 by using expression as illustrated in initialization of population part of Algorithm1. Next, HSI value (i.e. fitness value) for each habitat H1–H5 is evaluated as illustrated in step 2 of Fig. 1. Afterward, species count is calculated for each habitat H1–H5 as illustrated in the step 3 of Fig. 1. Step 4 of the Fig. 1 illustrates calculation of immigration and emigration rate based on species count as evaluated in the step 3 of Fig. 1. Step 5 of the Fig. 1 illustrates the main working of habitat migration process in which two habitats are selected such as H3 and H5. H3 is selected based on high immigration rate and H5 is selected based on high emigration rate.

    Fig. 1
    figure 1

    Illustration of the habitat migration process

    Full size image
  4. (d)

    Mutation Operator In mutation process, mutation probability is used for selecting a habitat. A random number r2 is generated between (0, 1). If value of r2 is less than maximum mutation probability, mutation is performed. Afterward a random position is chosen in habitat and its value is changed, i.e. if selected position has value 0 then it is replaced with 1and if value is 1 it is replaced with 0.

In Fig. 2, an illustration of the working of mutation operator is discussed with an example. Step (1) of the Fig. 2 illustrates emigration rate of Habitat H1–H5 as calculated in the step (4) of the Fig. 1. Next, mutation probability is evaluated for each habitat H1–H5 as illustrated in the step (2) of the Fig. 2. As discussed in Sect. 3.1, possibility of selection of a habitat Hi depends on mutation probability. If mutation probability is high for a habitat Hi, its possibility for mutation is also high. So H3 has highest mutation probability as shown in the step (2) of the Fig. 2. In the step (3) of the Fig. 2, an element in Habitat H3 is selected randomly. If value of the selected element is 0, replace it by 1 and vice versa. So in example as shown in Fig. 2, 6th element has value 1, replace it by 0.

Fig. 2
figure 2

Illustration of habitat mutation process

Full size image

5 Performance evaluation and discussion

This section presents performance evaluation the proposed BBO-based scheme and compare its performance with the state-of-art schemes such as GA-based scheme [25] and GSA-based scheme [26] for “k-coverage and m-connectivity” based node placement problem for monitoring the given set of target points.

5.1 Simulation environment

For the simulation analysis of the proposed scheme and its comparisons with existing schemes, a network scenario for WSN was setup which contains T number of target points, P number of suitable positions and n number of sensor nodes. Here, T, P and n are variable and its value is listed in Table 1. Dimension of network is 300 × 300 and sink is place at the corner location (300,300). In this work, evaluation of the optimal number of suitable positions are done at the sink node in a centralized control manner using MATLAB and the data collection round is performed in a distributed manner using Castalia3.2 simulator [31]. Castalia3.2 is a wireless body area and sensor network simulator which is based on the OMNeT++ simulation platform [31].

Table 1 Parameter list
Full size table

For simulation, two network scenarios, namely WSN_Random and WSN_Grid are considered. In WSN_Randon, a set of suitable positions are randomly located. However, in the WSN_Grid, suitable positions are located at cross-point of the grids. To execute the meta-heuristic based algorithms, we have considered an initial population in which total 60 habitat is generated for BBO-based scheme and 60 chromosomes and agents are generated for GA-based scheme and GSA-based scheme, respectively.

5.2 Result analysis

Figure 3 illustrates the performance analysis of the proposed BBO-based scheme when number of suitable positions increases from 100 to 300. Figure 3 shows the performance of the proposed scheme in terms of number of selected positions for a network scenario where all suitable positions are randomly located. In this experiment, 100 target points are fixed and performance of the proposed scheme under different combination of coverage and connectivity factor (k, m) is tested. It can be examined from Fig. 3 that number of selected positions increases when number of suitable positions (M) increases. This is due to fact that when M increases, it gives more scope to deploy sensor nodes for required degree of coverage of the given target points and connectivity of the sensor nodes, thus optimal number of sensor nodes required to be covered the given target points also increases. It can also viewed from Fig. 3 that as value of k and m increases, number of suitable positions to be selected for locating the sensor nodes, is also increases.

Fig. 3
figure 3

Performance comparison in terms of number of selected suitable position for WSN_Random

Full size image

Figure 4 illustrates the performance analysis of the proposed BBO-based scheme when all suitable positions are located at cross-point of the grids and number of suitable positions increases from 100 to 300. In this experiment, 100 target points are identified and these points need to cover by a minimum number of sensor nodes that satisfied desired coverage and connectivity factor. It can be viewed from Fig. 4 that number of selected suitable positions are less for WSN_Grid network scenario, compare to the WSN_Random network scenario. This due to fact that suitable positions are selected in a pre-planned manner, i.e. near to the cross-point of the grid which requires less sensor nodes to cover the target points.

Fig. 4
figure 4

Performance comparison in terms of number of selected suitable position for WSN_Grid

Full size image

Figure 5 shows the performance comparison of the proposed BBO-based scheme with two existing schemes such as GA-based [25] and GSA-based [26] schemes, when value of the coverage factor k varies from 1 to 3 and value of connectivity factor m varies from 1 to 2. It can be viewed from Fig. 5 that proposed scheme selects minimum number of suitable position for locating the sensor nodes compare to GA and GSA-based schemes. This is due to fact that exploration and exploitation of the BBO-based meta-heuristic perform better than GA-based meta-heuristic scheme.

Fig. 5
figure 5

Performance comparison in terms of number of selected suitable position for WSN_Random

Full size image

Figure 6 illustrates the results analysis of the proposed scheme in terms of number of selected suitable positions for network scenario WSN_Random where nodes are randomly deployed within the network. Results are taken by varying the value of the coverage factor k from 1 to 3. It can be seen from the Fig. 6 that the proposed BBO-based scheme performs better that the existing schemes. This due to fact that convergence rate of BBO is faster than GA and GSA-based metaheuristic scheme.

Fig. 6
figure 6

Performance comparison in terms of number of selected suitable position for WSN_Grid

Full size image

Figure 7 and 8 shows the performance of the proposed scheme in terms of network lifetime when number of nodes are increases from 100 to 300 for the network scenario WSN_Random and WSN_Grid, respectively. Figure 7 illustrates that the network lifetime increases as number of sensor nodes increases. This is due to fact that node density within the network increases due to increase in number of sensor nodes that causes availability of sufficient number of nodes for covering the appropriate target points. Thus increase functional lifetime of the network. At illustrated in Fig. 8, Network lifetime for the network scenario WSN_Grid is higher compare to the network lifetime achieved for network scenario WSN_Random. This is due to fact that potential positional are pre-determined at the cross-point of each grid cell for WSN_Grid network scenario which made distribution of the potential positions uniform and the load distribution among the sensor nodes are also uniform. Because of these facts, performance of the proposed scheme is better for WSN_Grid scenario in terms of the network lifetime.

Fig. 7
figure 7

Performance comparison in terms of network lifetime for WSN_Random

Full size image
Fig. 8
figure 8

Performance comparison in terms of network lifetime for WSN_Grid

Full size image

6 Conclusions

In this paper, k-coverage and m-connected suitable positions node placement problem is studied for WSNs. A BBO-based scheme is proposed for finding the optimal number of selected suitable positions for deployment of sensor nodes that satisfied k-coverage and m-connectivity requirements in the network. The proposed BBO-based scheme provides an efficient encoding scheme for the habitat representation and formulates an objective function along with the BBO’s migration and mutation operators. For better understanding of the working of the proposed scheme, all steps of the BBO have been illustrated with help of a suitable example. The performance of the proposed scheme to find approximate optimal number of suitable positions under different combinations of k and m are discussed in detail. In addition, a comparative study with the GA-based and the GSA-based schemes have also been done and its analysis confirms the superiority of the proposed BBO-based scheme over them. In the future, we plan to modify the proposed algorithm for barrier-coverage problem of heterogeneous mobile WSNs.