1 Introduction

Internet of things is the third revolution of information technology after computer and Internet, which is highly valued by governments, enterprises and academic circles in the world [1]. Wireless sensor networks as the Internet of things “peripheral nerves”, sensory information, wireless communication, distributed information processing technology, the physical world, calculation of the interconnection of the world and human society in the world [1, 2]. Wireless sensor network is a new information processing technology, which is widely used in the security system, target detection and recognition, environmental monitoring, military applications, and more and more widely used [2]. In order to prolong the lifetime of the network and improve the efficiency of the network, the commonly used methods need lots of redundant sensor nodes deployment, redundant configuration to the sensing node, turn the work. As a result, the wireless sensor network coverage and connectivity problems, the CCP (coverage and connectivity problem) in WSNs [3, 4].

In recent years, a large number of researchers have been optimized and solved the problems of CCP-WSNs. Misra et al. [5] addressed the problem of network coverage and connectivity and propose an efficient solution to maintain coverage, while preserving the connectivity of the network, up to 95% coverage of the area, while consuming very less energy of 9.44 J per unit time in the network. Xu et al. [6] proposed a novel topology control algorithm called Adaptive Random Clustering (ARC), and formed a cluster network with required coverage and connectivity without location information. The performance of its coverage intensity and connectivity is analyzed based on the characteristics of cluster topology, and their proper parameters are determined. In [7], the author proposed a new approach to solving the EEC problem using a novel Ant Colony Optimization (ACO) algorithm, the effectiveness of the proposed algorithm over other algorithms, in terms of the whole network lifetime. He et al. [8] proposed a new kind of network, partitioned synchronous network, to jointly address the coverage and connectivity problem. And analyzed the coverage and connectivity performances of partitioned a synchronous network and compare them with those of existing asynchronous network. Razafindralambo et al. [9] presented a mechanism which allows to preserve network connectivity during the deployment of mobile wireless sensors, and showed the connectivity preservation property of our algorithm through analysis and present some simulation results on different deployment schemes such as full coverage, point of interest coverage or barrier coverage. The above algorithm is able to improve network coverage and connectivity, but did not consider the network energy consumption, network lifetime problem. Therefore, in this paper we propose an algorithm based on improved artificial bee colony algorithm for solving the CCP-WSNs coverage and connectivity method, reduce data redundancy and network traffic and improve the efficiency of the network and prolong network lifetime.

The main contributions of our work in this paper can be summarized as follows:

  1. 1.

    Characterize the issues of network coverage and connectivity for the WSNs, and formulate the problem of CCP-WSNs.

  2. 2.

    Present a new network coverage and connectivity algorithm based on improved artificial bee algorithm.

  3. 3.

    Provide extensive simulation results to demonstrate the use and efficiency of the proposed network coverage and connectivity algorithm.

  4. 4.

    Evaluate the performance of the proposed algorithms by comparing them with the network coverage and connectivity algorithms of the random distribution and genetic algorithm.

The rest of the paper is organized as follows: Sect. 2 presents our assumptions and formulates the problem of CCP-WSNs. Section 3 describes the basic principles of the improved PSO algorithm. Section 4 presents the applied mathematical models and describes the proposed method. Section 5 describes the network performance evaluation index. Section 6 provides the parameters and simulation results that validate the performance of our algorithm. Section 7 concludes the paper.

2 Problem Formulation

Research on the CCP-WSNs is mainly to solve these problems: (1) As far as possible to reduce the number of nodes in the work, it is best to be in a state of sleep, decrease energy consumption. (2) Ensure that there is at least one cluster member node in each cluster head. (3) Ensure connectivity and coverage of the network, to ensure that the sensor nodes in the network to Sink nodes to communicate smoothly [10].

The optimal problem of CCP-WSNs is solved to make the entire wireless sensor network to minimize the cost of energy consumption, the optimal coverage to monitor the area, reduce energy consumption, improve work efficiency, and extend the lifetime of network.

The mathematical model of CCP-WSNs is defined and described, constraint conditions and analyses as follows: given the coverage area T, measured regional node set D, sensor set S, the mathematical model of CCP-WSNs is function combination optimization, and it is the NP-hard problem. Parameters and variables meet the following conditions: S are Sensor nodes set, \(S = \left\{ {1,2, \ldots ,n} \right\}\). D is the Target node set to be detected, \(D = \left\{ {1,2, \ldots ,m} \right\}\). r is the node communication radius. k is the accuracy of network coverage, network coverage. fi is the energy cost of the normal communication of the ith sensor node. aij is when the jth sensor node coverage to the ith to be measured area sensing node, then aij = 1, otherwise aij = 0,\(j \in S,i \in D\). ni is the ith node that has not been covered by the perceived network when the ni = 1, otherwise ni = 0. TS is a sensing node connected link set. Td is the edge set between the sensing node and the overlay node. Tm is a set of nodes and Sink. \(z_{{^{ij} }} \le x_{i} ,\forall j \in S,\forall l(S - j),\;\;\forall ij \in (T^{s} \cup T^{m} )\); \((i,j) \in T^{s} \cup T^{d},\,j \in S\). Os(T) is a set of edge (i, j), \((i,j) \in T^{s} \cup T^{m} ,i \in S\). ME is the residual energy of the node, TE is the node transmits the data of the consumed energy; RE is the energy consumed by the node receiving the data; NC is the coverage energy consumption when the monitored point is not covered. xi is a decision variable, when the jth sensor nodes in the perception of information to send data, xi = 1, otherwise xi = 0, j ∈ S. When the graph theoretic edge (i, j) in the sensor node between the transmission path 1 and m, zij = 1, otherwise zij = 0, (i, j) ∈ TS. In addition, if the node is activated, then its decision variable value yi = 1, otherwise yi = 0. The variable hj indicates that the jth node to be measured is not covered. The variable ei indicates that the current node of energy is consumed.

The WSNs coverage and connectivity objective function and constraint conditions are expressed as follows:

$$Minimize \, \sum\limits_{j} {f_{j} x_{j} } + \sum\limits_{i} {n_{i} }$$
(1)
$$Subject{\text{ to }}\sum\limits_{j} {a_{ij} x_{j} } \ge k, \, \forall i \in D$$
(2)
$$Minimize \, \sum\limits_{i \in S} {e_{i} } + \sum\limits_{j \in D} {NC_{j} \times h_{j} }$$
(3)
$$\sum\limits_{{i,j \in I_{j}^{d} (A^{d} )}} {x_{ij} } + h_{j} \ge n,\forall j \in D$$
(4)
$$\sum\limits_{{i,j \in I_{j}^{s} (A^{s} )}} {z_{lij} } - \sum\limits_{{j,k \in O_{j}^{s} (A^{s} \cup A^{m} )}} {z_{ljk} } = 0,\forall j \in (S \cup m - l),\forall l \in S$$
(5)
$$\sum\limits_{{j,k \in O_{j}^{s} (A^{s} \cup A^{m} )}} {z_{ljk} } = - yl,\,j = l,\forall l \in S$$
(6)
$$z_{lij} \le yi,\forall i \in S,\forall l \in (S - j),\forall ij \in (T^{s} \cup T^{m} )$$
(7)
$$z_{lij} \le yj,\forall j \in S,\forall l \in (S - j),\forall ij \in (T^{s} \cup T^{m} )$$
(8)
$$ME_{i} \times yi + \sum\limits_{l \in (S - i)} {\sum\limits_{{ki \in I_{i}^{s} (A^{s} \cup A^{m} )}} {RE_{i} } \times } z_{lki} + \sum\limits_{l \in S} {\sum\limits_{{ij \in I_{i}^{s} (A^{s} \cup A^{m} )}} {TE_{ij} } \times } z_{lki} \times z_{lij} \le e_{i} ,\forall i \in S$$
(9)
$$x_{ij} \le y_{i} ,\forall i \in S,\forall ij \in T^{d} ,\quad 0 \le x_{ij} \le 1,\forall ij \in T^{d}$$
(10)
$$h_{j} \ge o,\forall j \in D,\quad e_{i} \ge 0,\forall i \in S,\quad y,z \in \left\{ {0,1} \right\},\quad x,h,e \in R$$
(11)

In the objective function of the above equation constraints in Eq. (1) is communicated with the function we want to optimize the network coverage. The Eq. (2) is to ensure that the regional monitoring network coverage accuracy is k, and also the constraint Eqs. (3)–(11), computing network connectivity are associated with constraint problem, Eqs. (3)–(11) is to ensure the performance of network connectivity. We are looking for the mathematical model of the optimal solution,we can be obtained the monitor of the sensing area near a to sink as the center node optimal set, with as little as possible sensor nodes cover all to be monitoring points, reduce energy consumption, improve network efficiency and prolong the network lifetime.

3 Basic Principle of Artificial Bee Colony Algorithm

In 2005, researchers Karaboga according to bee colony foraging behavior, establish in bee colony life habit model, proposed a novel meta heuristic intelligent bionic algorithm—artificial bee colony algorithm (ABC) [11]. The Artificial bee colony algorithm in solving combined optimization problem to obtain good optimal solution and it will optimize the solution for bees honey nectar source location and nectar collection number of optimization problems.

The ABC algorithm can be split into four main steps [12].

(1) Initialization: Assume that population size is SN, where N is the first generated food source of initial population Xi = {Xi1, Xi2,…, XiD}(i = 1, 2, …, N), and D is the vector dimension of the optimization problem. The random initial population is then

$$X_{i} = X_{\hbox{min} } + rand(0,1) \cdot (X_{\hbox{max} } - X_{\hbox{min} } )$$
(12)

(2) Population updating: The initial positions of food sources are randomly generated and each employed bee assigned to a food source, then every employed bee determines a new neighboring food source of its currently associated food source via Eq. (9), then computes the nectar amount of the new food source for each iteration. If the nectar amount of the new food source is higher than the previous one, the employed bee moves to the new food source—if not, it continues with the old one.

$$V_{ij} = X_{ij} + rand( - 1,1) \cdot (X_{ij} - X_{kj} )$$
(13)

where k ∈ {1, 2, 3, …, SN}, j ∈ {1,2,3,…,D}, rand(− 1,1) is the numerical value between randomly produced (− 1,1), which controls the producing range of Xij neighborhood. The neighborhood scope gradually decreases as the search approaches the optimum solution [13].

(3) Bee source selection: In this stage, the employed bees move according to the income rate (calculated according to fitness value) of their sources. Food sources with high income rates are more likely to be selected, according to the following equation:

$$P_{i} = \frac{{fit\left( {X_{i} } \right)}}{{\sum\nolimits_{n = 1}^{\text{SN}} {fit\left( {X_{n} } \right)} }}$$
(14)

where fit(Xn) is the fitness value of the solution n(n) proportional to the nectar amount of the food source n∈{1,2,3,…, SN}. Fitness is calculated as follows:

$$fit\left( {X_{n} } \right) = \left\{ {\begin{array}{*{20}l} {\frac{1}{{f\left( {X_{n} } \right)}},} \hfill & {\quad f\left( {X_{n} } \right) \ge 0} \hfill \\ {1 + abs\left( {f\left( {X_{n} } \right)} \right),} \hfill & {\quad f\left( {X_{n} } \right) < 0} \hfill \\ \end{array} } \right.$$
(15)

where f(Xn) is the objective function value of bee source Xn, The followed bees search in the neighborhood of the sources of foraging bees, which improves the local exploitative ability of the algorithm.

(4) Population elimination: Suppose a certain solution gains no obvious improvement after continuous limit cycling updates, it is then assumed to be caught into local optimum and is abandoned, then the corresponding onlooker bees turn into scouting bees and randomly produce a new solution to replace the eliminated solution by Eq. (16):

$$X_{ij} = X_{{\hbox{min} {\text{ j}}}} + rand\left( {0,1} \right)\left( {X_{{\hbox{max} {\text{ j}}}} - X_{{\hbox{min} {\text{ j}}}} } \right)$$
(16)

The new solution obtained by calculation replaces the old and the optimum solution is output accordingly. j ∈ {1,2,3,…,D}, rand(0,1) is the numerical value between randomly produced (− 1,1), and Xmax and Xmin are the maximum and minimum values [14].

The ABC algorithm is a new type of intelligent population optimization which shows the following advantages: (1) the bee population algorithm is convergent to the whole, and at relatively quick convergence speed; (2) the application range of the algorithm is quite wide; (3) it requires relatively few parameters to be set compared to other optimum algorithms; and (4) it based upon population, so it is easily realized and processed.

The specific flow chart of artificial bee colony algorithm is shown in Fig. 1.

Fig. 1
figure 1

The flow chart of artificial bee colony algorithm

Full size image

Due to the roulette wheel method choice of bee with artificial bee colony algorithm, which makes it easy to fall into the trap of local optimal solution and reduce the diversity of the population, cause premature convergence and premature stagnation phenomenon, and ultimately affect the convergence speed of the algorithm. Therefore, the improved of artificial bee colony algorithm (IABC) are proposed, in free search algorithm and pheromone to the selected area, improve the searching scope of the artificial bee colony algorithm the avoid falling into local optimum “trap”. The artificial bee colony searching area pheromone must adapt to the sensitivity of the bee, the search direction of the algorithm is oriented, and the objective optimization function has a very fast convergence in the prescribed search area. The sensitivity of the pheromone with the choice of honey instead of gambling roulettes, and improves the algorithm convergence speed.

4 The Application of IABC in CCP-WSNs

In the artificial bee colony algorithm, wireless sensor network coverage and connectivity degree of the optimization process are really equivalent to search for yield of the highest nectar source process. The corresponding relationship between the CCP problem of WSNs and the artificial bee colony is shown in Table 1. The leader bee has excellent flower nectar and the characteristics of elite. The follow bees can increase the number of good nectar source corresponding to the bee populations, and improve the convergence speed. The scout bee can randomly search near new sources of nectar, equivalent to expand the function solution diversity and help the algorithm to escape from solving the function to the local optimum problem.

Table 1 The corresponding relation between the behavior of bees and network coverage connectivity optimization function problem
Full size table

The objective function of WSNs coverage and connectivity optimization based on improved artificial bee colony algorithm is as follows:

$$Minimize \, \sum\limits_{i \in S} {AE_{i} } \times y_{i} + \sum\limits_{j \in D} {NC_{j} \times h_{j} }$$
(17)
$$subject{\text{ to: }}\sum\limits_{ij} {x_{ij} } + h_{j} \ge 1,\forall j \in D,\forall ij \in T^{d}$$
(18)

The following is given in this paper the improved artificial bee colony algorithm in CCP-WSNs implementation steps:

  1. 1.

    Swarm initialization. The leader bees, employed bees and other bee population initialization, set the number of iterations, which the leader bees and the employed bees each accounted for 50%, one of the investigation.

  2. 2.

    Choose the better individuals for nectar and mark

  3. 3.

    The lead bees randomly selected nectar and its nectar for cross comparison, contrast to produce a new position, preferred marker new nectar.

  4. 4.

    The followed bee in accordance with the free search method improved search ways to choose appropriate nectar, and cross comparison, resulting in a new location of the nectar source is creating.

  5. 5.

    Comparison and selection step 3, 4 in the outstanding individuals as the generation of labeled best nectar.

  6. 6.

    Judging whether to reach the maximum number of iterations and the set of optimal solutions, if achieved, recording the best nectar source location and go to step 7, otherwise go to step 2.

  7. 7.

    Output of searching the optimum location source. That is the optimal solution of CCP-WSNs.

5 Network Performance Evaluation Index

Effective evaluation of coverage of wireless sensor networks is helpful to save the network energy consumption, prolong the network lifetime and improve the network efficiency [15]. Therefore WSNs coverage and connectivity performance evaluation criteria for analysis, WSNs coverage strategy and network availability is essential. In this paper, we study from the following three aspects.

  1. (1)

    The coverage capability

The degree of coverage of the monitoring area is measure coverage of WSNs seeding strategy is effective is an important index, the degree of coverage (CD) is defined as follows: In a sensing area with si as the center, a radius of ri, if the region a point within the range of si perception, so this point is called the coverage of si. The coverage of network calculation formula is as follows: \(CD = {{\left( { \cup Z_{{s_{i} }} } \right)} \mathord{\left/ {\vphantom {{\left( { \cup Z_{{s_{i} }} } \right)} A}} \right. \kern-0pt} A},\;\;i = 1,2, \ldots ,n\).

  1. (2)

    Connectivity of the network

Network connectivity is an important index to measure the network nodes sensing perception, sensing and communication to the quality of service, cannot guarantee network connectivity network, even if the network coverage and high, is useless [16]. Degree of connection (TD) is defined as follows: Define Rci as sensing node communication radius, if the distance between the two nodes Si and Sj is less than the minimum communication radius between them, that is \(d(s_{i} ,s_{j} ) \le \hbox{min} \left\{ {R_{{c_{i} }} ,R_{{c_{j} }} } \right\}\). So called from the two points there is a communication edge between Eij, when \(d(s_{i} ,s_{j} ) \le \hbox{min} \left\{ {R_{{c_{i} }} ,R_{{c_{j} }} } \right\}\), The Eij value of the node si is 1, when \(d(s_{i} ,s_{j} ) > \hbox{min} \left\{ {R_{{c_{i} }} ,R_{{c_{j} }} } \right\}\), Eij= 0. Therefore, the computation formula for the connectivity of Si the sensing node is \(TD(s_{i} ) = \sum\nolimits_{j = 1}^{n} {E_{ij} , \, } j = 1,2, \ldots ,n,j \ne i\).

  1. (3)

    Energy efficiency

Wireless sensor network node by cost constraints, cannot replace the battery power supply and environment interference, energy consumption is very large, resulting in greatly shorten the lifetime of the network [17]. How to save node energy consumption, it has become an important indicator to measure the performance of WSNs. In this paper, we mainly study the relationship between the network lifetime and the number of sensing nodes.

6 Algorithm Simulation and Result Analysis

In order to assess the performance of the proposed algorithm in WSNs coverage and connectivity, the simulation experiment was carried out by using MATLAB 2014b software. The simulation scene is 200 m × 200 m area, randomly deployed 40–60 sensor nodes, all of the target points to be monitored grid type distribution, sink node in the middle of the scene [18]. The sensing radius of the sensor node is 20 m, and the transmission rate between nodes is 0.5 Mbps. The initial energy of the common node is 1 J, the Sink is set to 10 J, the maximum value of the data packet is 256B, and the simulation duration is 500 s. Artificial bee colony algorithm parameter settings: The number of calculation cycle is set to 100, the leader bees and follow the total number of bee are 50, and each accounted for half of the total, the control parameters defining the number of 10, the colony initial weights rmin = 0.4, rmax = 1.2, the initial of r value is set to 1, the threshold ε = 10−6.

We mainly on the random distribution [19], genetic algorithm (GA) [20] and the improved artificial bee colony algorithm is proposed in this paper of three algorithms are compared, which from the relationship between the degree of coverage and the number of sensing nodes, connectivity and node sensing quantitative relation and connectivity coverage efficiency, network lifetime and node sensing quantitative relations, reached the same coverage and connectivity degrees takes five aspects of wireless sensor network coverage, research on wireless sensor network coverage and connectivity problems, each simulation experiment was 50 times average.

  1. (1)

    The relationship between the degree of coverage and the number of nodes

Generally speaking, the more sensor nodes, the stronger of the network communication capability, but due to the cost and efficiency and other objective factors we should be considered in the data transmission process. Therefore, it is necessary to design the reasonable perception of node number and meet the requirement of network coverage. The relationship between the degree of coverage and the number of sensing nodes is shown in Fig. 2. As can be seen from Fig. 2, the number of sensor nodes is positively correlated with the effective degree of coverage. With the increase of the number of sensor nodes, coverage of the three algorithms are increased, but covered degree increase is not the same, randomly distributed nodes coverage increased minimum amplitude, covering is the lowest, the genetic algorithm of second degree of coverage, the improved artificial bee colony algorithm of coverage is the best, in a sense the same number of nodes, according to the algorithm of node deployment, network coverage is the highest.

Fig. 2
figure 2

The relationship between the degree of coverage and the number of nodes

Full size image
  1. (2)

    The relationship between the average connectivity and the number of sensor nodes

The average connectivity of the network and the number of sensing nodes are compared with three algorithms, as showed in Fig. 3. As can be seen from Fig. 3, with the increase of the number of sensor nodes, the network connectivity of the three algorithms is increasing. Randomly distributed network connectivity rate increase in the amplitude of the smallest, in a sense the same number of nodes connectivity rate lowest genetic algorithm of the connectivity rate times, is proposed in this paper improved artificial bee colony algorithm connectivity best, network connectivity in less than 50–60%, with less number of nodes required, when the connection ratio is more than 80%, the required number of nodes rose sharply.

Fig. 3
figure 3

Comparison of the number of nodes required for the same connectivity

Full size image
  1. (3)

    Comparison of three algorithms coverage connectivity

In order to better reflect the superiority of the algorithm presented in this paper, the coverage of the three algorithms connectivity rate of contrast, the contrast not in the sense the same number of nodes, but with the increase of network simulation iterations, three algorithms of network coverage connectivity efficiency were compared. The coverage connectivity of three algorithm is compared as shown in Fig. 4. From Fig. 4 it can be seen that in the iterative number 250 times, three algorithms of connected coverage rate are in a straight line rise, but randomly distributed WSNs connected coverage rate minimum connected coverage rate at about 86.3%, genetic algorithm times, about 89.2%, covering algorithm is proposed in this paper connectivity rate highest about 93.6%. After the 250 generation, the coverage connectivity of the three algorithms is balanced, and the coverage of the network is saturated. In short, random distribution of WSNs coverage connectivity is the smallest, followed by genetic algorithm, the algorithm proposed in this paper covers the highest connectivity.

Fig. 4
figure 4

Comparison of three algorithms coverage connectivity

Full size image
  1. (4)

    The relationship between network lifetime and the number of sensor nodes

With the same time change of the number of nodes, the network lifetime of the three algorithms is normalized, the comparison diagram is shown in Fig. 5. From Fig. 5 that after normalization of the network lifetime impressions know the number of nodes increase gradually declined, mainly because of the number of nodes increases, the greater the network energy consumption and, the network lifetime is shorter. From the comparison of the three algorithms, it can be seen that the random distribution network lifetime is the shortest, and the genetic algorithm is the second. The improved artificial bee colony algorithm proposed in this paper has the longest lifetime.

Fig. 5
figure 5

Comparison of normalized network lifetime

Full size image
  1. (5)

    The time required to achieve the same coverage and connectivity

In order to better reflect the superior performance of the algorithm proposed in this paper, the three algorithms to achieve the same coverage and connectivity time required for the comparison, compared to the results shown in Fig. 6. Figure 6 includes network coverage reached 0.9 for the comparison of time and network connectivity rate of 90% for time comparison, 50 times the experimental and calculated to achieve the same coverage and connectivity required time average value. From figure can be seen, the genetic algorithm of the network takes a long time, reaching about 9.2 s, randomly distributed second, about 8.1 s, improved artificial bee colony algorithm time is about 6.9 s, three kinds of algorithms required time difference, but in this paper, the algorithm of the shortest time consuming, are the most efficient.

Fig. 6
figure 6

The time required to achieve the same coverage and connectivity

Full size image

7 Conclusions

In this paper, we mainly study three kinds of WSNs Coverage and connectivity of algorithm performance analysis and comparison, through the simulation and experimental verification, randomly distribution, genetic algorithm, and the proposed algorithm in this paper are compared, the proposed algorithm has higher coverage and connected degree, reducing the redundancy and traffic, improve network reliability and prolong the network lifetime.

For future work, we plan to validate the proposed schemes on different scenarios with the mobile sinks of mobile wireless sensor networks. We also plan to study the reliability with network lifetime maximization as the optimization objective as future work.