1 Introduction

1.1 Background

In recent years, wireless sensor networks (WSNs) have drawn enormous attention because that it can be used in various environments, such as battlefield surveillance, traffic control, animal tracking, home application, security management, medical and health care [1]. In WSNs, due to the limitation of energy and cost, there are many optimization problems such as the maximum lifetime of network, the minimum data routing, the minimum energy consumption, the maximum connectivity and coverage [2, 3].

During above issues, one objective may conflict with others objectives such as between coverage and number of sensor. That is belonging to multi-objective optimization problem (MOP) [4]. In general, maintaining efficient coverage and prolonging the lifetime of WSNs is the most important issues. Many methods have been proposed to maximize the coverage, to minimize the consumption of energy, and to maximize lifetime of network simultaneously [5]. In paper [6], the authors built the balance between coverage efficiency and the capacity of the network that to get Pareto optimal solutions. In order to improve the coverage reliability of Wireless Sensor Networks, Attea et al. [7] addressed the problem of improving coverage reliability of WSNs and maximizing the number of disjoint set covers (DSC) simultaneously. They transformed the definition of single-objective DSC problem into a MOP by adopting an additional conflicting objective. In literature [8], the authors aimed to cover a sensing area by deploying a minimum number of wireless sensors while maintaining the connectivity. They developed an integer linear programming model to solve the problem optimally. To study the maximum coverage deployment problem in WSNs and analyze the properties of the problem, Yoon et al. [9] has proposed an efficient genetic algorithm based on a novel normalization method. Unfortunately, there is only few reported research work concerning the coverage and number of sensor in the field of multi-objective optimization [2, 3].

From above mentioned studies, it can be found that using multi-objective evolutionary algorithms to research these problems is very meaningful and valuable. Meanwhile, many multi-objective evolutionary algorithms (MOEAs) have successfully been employed to tackle MOP over the past decade. During the research results, the NSGA-II [10], the SPEA-II [11] and MOEA/D [12, 13] are the most famous algorithms. Recently, the famous multi-objective and many-objective algorithms, such as IM/MOEA [14], NSGAIII [15], KnEA [16], IMOPEO-PLM [17] and MOEO [18] are presented. These algorithms can handle multi-objective or many-objective problems [19]. The literature [20] claimed that the non-parametric statistical test is concerned for comparing the performance of above different optimization algorithms. Since the Differential Evolution (DE) algorithm is proposed in [21]. Many scholars have devoted to extend their research on multi-objective Differential Evolution. According the improved individual density calculation and Pareto dominance, the multi-objective differential evolution algorithm (MODE) was proposed and achieved good result [22]. The most famous algorithm for solving multi-objective problem based on DE is differential evolution multi-objective optimization (DEMO) [23]. Its best feature is to select next generation individual on the basis of comparing with parent (target) and trial vector. If the trial vector dominates the corresponding parent vector, it replaces the parent vector; otherwise, the parent vector is retained in the current population. If the relationship of parent vector and trial vector is non-dominated, DEMO will put the trial vector into the extra archive. The test results show that the DEMO has significantly improved than NSGAII on convergence and diversity. In this year, a novel differential evolution with event-triggered impulsive control [24] and an improved NSGAIII with elimination operator [25] were presented.

Based on aforementioned analysis for multi-objective algorithms and problems of WSNs, we think there are two points need to be concerned. The first one, we consider using minimum number of sensor nodes so that it will fulfill maximum coverage of WSNs. Obviously, this is belongs to a bi-objective optimization problem. Secondly, its need introduce a suitable two-objective evolution algorithm for solving this problem. To the best of our knowledge, most of above evolution algorithms are based on the Parteo non-dominated sorted to select individuals into the next generation. These algorithms firstly sort the double size of population (SP) individuals based on the Parteo theory. After that, according the result of ranking, they select one SP individuals into next generation. However, this process has some redundant operations: (1) since the goal of sorting is just select one SP individuals into next generation, however, the above algorithms need sort double SP individuals; (2) In above algorithms, after the non-dominated sorted is finished, the operation of selecting individuals into next generation can be executed subsequently. We introduced a method to solve above computation redundancy in this work. In our method, the sorting operation only handles the highest rank individuals in current population. Meanwhile, the individuals can be chosen into the next generation during the proposed sorting operation. When the population of next generation is selected enough, the algorithm is terminated. The proposed method reduces the time complexity since the number of individuals for sorting operation is smaller. In addition, a calculation method of uniform crowding distance is given, which can retain the outline of optimal solution set since the individual is chosen uniformly.

Moreover, a fast two-objective differential evolution algorithm (FTODE) is proposed, which incorporates the introduced sorting method and uniform crowding distance into the classic DE. The simulation experiment used the standard multi-objective optimization problems ZDTl~ZDT4, ZDT6, F1–F5 for testing the performance of FTODE. Furthermore, the experimental results on optimization problems by using non-parametric statistical tests including Kruskal–Wallis test and Friedman test [26] are provided. Simulation results show that the FTODE has greatly improved in terms of time complexity and performance.

1.2 Our contribution and organization of the paper

In this paper, we proposed a fast two-objective differential evolution algorithm (FTODE) to solve the two-objective optimization problem of WSNs. The two objectives are the minimum number of sensor used and the maximum coverage rate. Our main contributions are summarized as follows:

  1. (a)

    We present a fast two-objective differential evolution algorithm (FTODE), which contains a fast non-dominated solution sorted method and a uniform crowding distance calculation method.

  2. (b)

    We establish a two-objective coverage problem of WSNs, namely use of minimum number of sensor nodes for maximum coverage rate.

  3. (c)

    We perform extensive simulation experiment on the presented algorithm, compare and analyze results with existing and related algorithms.

The rest of this paper is organized as follows. In Sect. 2, related work is discussed emphasizing coverage problem in WSNs, Differential Evolution and multi-objective optimization. Section 3 presents the fast two-objective differential evolution algorithm. Section 4 provides the simulation experimental, the parameter settings for the investigation, and the performance of the proposed algorithm. In Sect. 5, we use the proposed FTODE to solve the two-objective coverage problem of WSNs. Finally, the conclusions and further work are discussed in Sect. 6.

2 Related works

2.1 The two-objective coverage problem in WSNs

In WSNs, one of the most critical issues is maximizing the lifetime of network while maintaining coverage and connectivity [2, 3, 28]. Therefore, the coverage problem influences the lifetime, the connectivity and the cost of network. In this work, the two-objective coverage problem is that using the minimum sensor nodes to coverage the maximum targets.

For the point-coverage problem of WSNs, suppose that there are a set of targets \(T=\{ t_{\mathrm {1}} {,t}_{\mathrm {2}}{,t}_{\mathrm {3}}{,\ldots ,t}_{\mathrm {m}}\}\) in an \(L \times W\) area, and then we randomly deploy a set of sensors \(S=\{ s_{\mathrm {1}} {,s}_{\mathrm {2}} {,s}_{\mathrm {3}},\ldots ,s_{\mathrm {n}}\}\) in this area to monitor the targets. All of the sensors have sleep and active mode. In the active mode, sensors can sense information of target and assume sensors have same sensing region, but in sleep mode it can’t sense due to save energy. A target is said to be covered by a sensor if it lies within the sensing region of the sensor. In order to prolong the lifetime of WSNs, we need to find the maximum number of disjoint sensor covers. This problem can be solved via transformation to the DSC problem, which is defined as finding the maximum number C of disjoint complete cover sets [8, 28]. The corresponding cover set \(C_{i}\) is satisfied following conditions:

Every cover \(C_{i}\) is a subset of \(S, i\in [1, C_{max}]\), where the \(C_{max}\) is the upper bound of disjoint set covers number C. The maximum number of full cover subsets \((C_{max})\) can be used as the upper limit of the number of disjoint set covers. \(C_{i} \in S\) and each \(C_{i}\) can complete coverage to all of the targets. Beyond that, for every of \(t_{i}\) belongs to at least one member of \(C_{i}\), and for any two different covers \(C_{i}\) and \(C_{j,} C_{i}\cap C_{j} =\phi \). We use the Fig. 1 as example, there are five sensors S1, S2, S3, S4, S5, and four targets t1, t2, t3, t4, every sensor have same circular sensing region.

Fig. 1
figure 1

A randomly deploy figure of WSNs by five sensors and four targets

Full size image

From the above mentioned, we can maximize the lifetime of WSNs by maximizing the number of completely cover subsets. Meanwhile, for saving the number of sensor nodes, how using less sensor nodes to find more completely cover subsets is our main aiming. Namely, in this work the two optimization objectives are: maximum the number of completely cover subsets and minimum the number of used sensor nodes.

2.2 Differential evolution

DE is firstly proposed by Price and Store [21], with the advantage of its fast speed, less parameter, easy to implement and so on, which has become one of the most famous evolution algorithms. Because of DE is belonging to evolutionary algorithm, it have also included crossover, selection, update, and other basic structures. For saving the space of paper, the details of the DE algorithm are not provided in here and shown in the literature [21, 27].

2.3 The mathematical description of multi-objective optimization

The features of multi-objective and single-objective optimization problem are different. In the single-objective optimization, the optimal solution is usually unique. However, in a multi-objective optimization, the optimal solution is a set because of the various objective functions are conflict each other. Considering the minimum of multi-objective problem, there are n decisions variables, m target variables can be expressed as Eq. (1) [10, 11, 14].

$$\begin{aligned} \left\{ {\begin{array}{l} Min\;y=F(x)=(f_{1} (x),f_{2} (x),\ldots ,f_{m} (x)) \\ \qquad s.t.\;\;\;g_{i} \le 0,i=1,2,3,\ldots ,q \\ \qquad h_{i} =0,j=1,2,3,\ldots ,p \\ \end{array}} \right. \end{aligned}$$
(1)

where \(x=(x_{1} ,\ldots ,x_{n} )\in X\subset R_{n} \) is the decision vector, X is the decision space with n-dimensional. The target vector is \(y=(y_{1} ,\ldots ,y_{n} )\in Y\subset R_{m} , Y \) is the target space, are m-dimensional. F(x) are m mapping functions that make decision space to the target space. The \(g_{i} (x)\le 0(i=1,2,3,\ldots ,q)\) is q inequality constraints, \(h_{i} (x)=0(j=1,2,3,\ldots ,p)\)are equality constraints. The detail concept description about multi-objective is shown in [14]. In the interest of saving space, we are not discuss them in this article

However, it is should be noted that: (1) usually, in a multi-objective problem, one global optimal solution like in single-objective optimization does not exist. There are only Pareto optimal solutions in multi-objective problem. The Pareto optimal solutions are an acceptable “not bad” solution, and usually there are multiple Pareto optimal solutions. (2) All Pareto optimal solutions constitute a solution set of multi-objective optimization problem. In practical problems, according to the preferences of decision makers, they can select a suitable solution from the set as the final optimal solution. Therefore, the primary problem of multi-objective optimization is to find out Pareto optimal solutions as much as possible.

3 The fast two-objective differential evolution algorithm

The classical multi-objective evolution algorithm based on the Pareto non-dominated exist some redundant operations. To reduce redundant operations and enhance the computation speed, we present a fast sorting method based on non-dominated solutions. In addition, we introduce a uniform crowding distance calculation method. Furthermore, we combine the proposed methods to improve the performance of two-objective DE algorithm.

3.1 A fast non-dominated solution sorted method

One of the most famous multi-objective evolution algorithms is NSGAII [10]. In the canonical NSGAII, all individuals (2N,N is population size) are ranked and divided into different levels according to the non-dominated relation firstly. After that, based on the level (level 1 is the highest rank) in descending order, NSGAII selects some individuals into the next generation. It should be noted that the aim of selecting is just to choose excellent N individuals into the next generation. However, the NSGAII needs deal with all of 2N individuals.

From the foregoing, if we can reduce the number of individuals during the sorting operation, the time complexity of the algorithm will be decreased significantly. Hence, on the basis of the potential feature of sorting operation, this section proposes a fast method to sort and select the individual. This method suits to all of the multi-objective optimizations, we just describe it in the two-objective problem for concise. The method is shown on Algorithm 1.

figure a

The main advantage of the proposed method is that it can select individual into next population during the sorting operation. Hence, the time complexity is descending due to the number of individuals for sorting operation is smaller.

In detail, before sorting and selecting the individual, the method firstly choose three special individuals. These special individuals belong to the highest level in current population. More specifically, the three individuals are the shortest distance to horizontal axis (minimum \(f_{1})\), to vertical axis (minimum \(f_{2})\), and to the original point, respectively. Note that these special individuals maybe repeat in some time. These special individuals are stored in a set \(S_{r}\). Then we compare the remaining individualsi of population with each special individual in \(S_{r}\). If the individual i non-dominate with all the special individuals in \(S_{r}\), then the i is belongs to the highest level in current population and is added to the set \(S_{r}\). Repeating above process for the next individuali, the method will find out those individuals that are belong to the current highest level.

Now, all individuals of \(S_{r}\) are obtained which belongs to the highest level in current population. After that the proposed method chooses all individuals of \(S_{r}\) into the next generation. If the number of cumulative individuals in next generation is less than N, the method will compute the next level by repeating above operation for the remainder individuals; otherwise, the crowded distance calculation is performed to select part of the current highest level individuals into next generation. When the number of the next generation    individuals is just equal N, the algorithm terminates and don’t processes the remaining individual to allocate level.

3.2 Theoretical basis for special individual in the fast non-dominated solution sorted method

The most important of our proposed method is how to prove three special individuals belong to the highest level of the current population. The three special individuals are shown in Fig. 2. Here, based on the Pareto dominance and sorting order theory, the analysis of special individual is given on below. For describing the problem conveniently, we use x and y represent the functions \(f_{1}\) and \(f_{2}\), respectively.

Theorem 1

If the x value of individual a (x, y) is the minimum abscissa of all individuals, this individual belongs to the highest level of current population.

Theorem 2

If the y value of individual c (x, y) is the minimum ordinate of all individuals, the individual c belongs to the highest level of current population.

Theorem 3

For all individuals in the current population, if the distance from the individual b (x, y) to the original point is the minimum, the individual b belongs to the highest level of current population.

Analysis for Theorem 1

Three special individuals are shown in Fig. 2. In current population, we assume that the minimum abscissa of all individuals is \(x_{min}\) . The coordinates of that individual is \( a(x_{min}\), \(a_{y})\), so there is not exist an individual \(k(k_{x}, k_{y})\) satisfaction \(k_{x} < x_{min}\).

According to the Pareto theory, there is not exist an individual dominate the \(a(x_{min}, a_{y})\) in the current population. Therefore, the individual \(a(x_{min,}a_{y})\) belongs to the highest level distinctly. Others proof of Theorems 2 and 3 are similar above..

It should be emphasized that these special individuals may repeat each other in sometimes. Hence, the check operation for these individuals whether repeat is needed.

Fig. 2
figure 2

Three special individuals in the proposed method

Full size image

3.3 A uniform crowding distance calculation method

This section presents a uniform crowding distance calculation method, which is shown in Fig. 3 and Algorithm 2. When all the current highest level individuals are chosen into the next generation, the cumulative number of next generation is bigger than N, it need to select part of individuals. The presented crowded distance calculation method can evenly selects part of the current highest level individuals into next generation.

Fig. 3
figure 3

A method of uniform crowding distance calculation

Full size image

The uniformity selection is based on the distribution of the relative position in the current level individuals. This method can ensure that the individuals with a representative range are not discarded easily.

For example, there are 10 solid dots (individuals) belong to the highest level in Fig. 3. We need select 5 solid dots (individuals) into the next generation based crowding distance. We use the uniform crowding calculation method to select that. Firstly, we evenly draw 5 vertical lines between all of these individuals.

Then, find the nearest distance of 5 individuals to five lines, respectively. These 5 individuals are selected into the next generation. The detail process of this method is given in Algorithm 2.

figure b

3.4 The overall framework and time complexity analysis of fast two-objective differential evolutionary algorithm

According to above fast non-dominated sorting method and uniform crowding distance calculation, we combine them with the DE to propose a fast two-objective differential evolution (FTODE). The general framework of the FTODE is shown in Algorithm 3.

figure c

The FTODE reduces the time complexity of algorithm by decreasing the number of individuals for sorting operation. The NSGAII is the most famous in all multi-objective evolutionary algorithms. However, it needs firstly rank and assign the level for all individuals (2N), and then select parts of individuals (N) into the next generation. In the first version of NSGA, the time complexity of non-dominated solutions sorting is \(O(n^{3})\). So far as to    the NSGAII, the time complexity is \(O(n^{2})\). The reason of high time complexity is that it needs to sort and assign level for all individuals (2N) by non-dominated relation.

Table 1 Ten bi-objective functions
Full size table

In FTODE, the best time complexity is O(n). When the number of individuals in the first level is greater than or equal to the population size N, these individuals are selected into the next generation directly. If this number is greater than N, the crowding distance calculation is needed and the remaining levels of individuals are not need to be ranked. Considering the worst case, the FTODEs’ time complexity is \(O(n^{2})\). In this condition, the algorithm needs to sort and assign level for all level individuals by their non-dominated relation.

In the Ref. [25], the authors claimed that the low selection pressure of Pareto dominance cause the MOEAs fail to handle many-objective optimization problems. Recently, Deb presented NSGAIII that also employs the uniformly distributed reference points to promote population diversity [15]. Thus, based on the above analysis, it’s found that the FTODE has high selection pressure of the Pareto-dominace relation and uniformly distributed reference points.

Generally, the individuals are distributed randomly in early stage of evolution. In order to choose N individuals into the next generation, it needs to handle more levels individuals. However, in later stage of evolution, many individuals are evaluated in the higher levels. Hence, just considering few levels, it can obtain N individuals into the next generation. In this case, the FTODE will show its high efficiency.

4 Simulation experiment for the FTODE

To verify the effectiveness of the proposed fast non-dominated sorting and uniform crowded distance calculation, we compare the FTODE with others classical algorithms in this section.

4.1 Experimental conditions and parameter settings

The simulation experiments use the standard minimum two-objective optimization problems ZDTl~ZDT4, ZDT6 [10], and F1–F5 [12] as testing functions. These functions are shown in Table 1.

Table 2 Running time and number of comparisons for the three sorting methods, second (number of comparisons)
Full size table

Without special explanation, The FTODE uses parameters as follows: Population size \(N=100\), scaling factor \(F=0.5\), crossover probability \(C_{r}=0.3\), the maximum evolution generation is 250, the mutation strategy is “DE/Rand/1/bin”. The parameter settings of other classic comparison algorithms are referred by original literatures. All the experiments have been implemented by MATLAB software on a 3.3 GHz PC with processor core i5-4590 and 4G RAM.

It’s important to note that we default use two-objective function for experiment test due to convenience. The proposed method is suitable for more than two objectives, which will be verified on many-objective optimization problem in the future work.

4.2 Running speed comparison

To verify the high efficiency of our proposed fast sorting method, this subsection compares the NSGAIIs’ non-dominated sorting method [10], an efficient approach to non-dominated sorting (ENS) [30] and the proposed method on the arithmetic speed. We compare the efficiency of three methods on two-objective problem with different population scale. The computing time and number of comparison for three methods are shown in Table 2 and Fig. 4. It should be noted that in this test, the individuals are randomly generated and the three algorithms only calculated levels for all individuals of population.

The Table 2 and Fig. 4 show that the proposed method spends less computing time and number of comparison than NSGAIIs’ method, but slightly more than ENSs’ method. Specifically, when the number of individual (NP) is small, the proposed method shows better than the NSGAIIs’ method, similar with ENSs’ method. Moreover, during the large scale populations (NP), the running speed of our algorithm significantly fast than NSGAIIs’ method. However, it is found that our method cannot beat the ENS on speed and number of comparison. The reason is that ENS is an excellent method, which has the best computing speed so far and published in the top journal of evolution computation [30].

Fig. 4
figure 4

Running time comparison on the two sorting methods

Full size image

4.3 Overall performance comparison

This subsection offers the overall performance comparison between the FTODE and classical algorithms, which contains two parts experiments. Firstly, we use the convergence indicator \(\gamma \)and diversity metric \(\Delta \) to evaluate the performance of algorithms on problem ZDT1-4 and ZDT6 [10]. The comparing results are shown in the Tables 3 and 4.

Table 3 Convergence metric \(\gamma \) comparison test on multi-objective minimization problem ZDT1-ZDT4 and ZDT6
Full size table
Table 4 Diversity metric \(\Delta \) comparison test on multi-objective minimization problem ZDT1-ZDT4 and ZDT6
Full size table
Table 5 Ranks, the statistic, and related p value achieved by the Kruskal–Wallis, Friedman test for Tables 3 and 4
Full size table

As can be seen from the Tables 3 and 4, the FTODE is significantly better than NSGAII, SPEAII on convergence and diversity index. In addition, the Tables 3 and 4 imply that our FTODE preforms slightly better than the DEMO and similar with the IMOPEO-PLM. Specifically, FTODE converges better than all the other MOEAs on ZDT1 and ZDT2 problems. For ZDT3 and ZDT6 problem, FTODE preforms only worse than DEMO and IMOPEO-PLM in terms of \(\gamma \), respectively.

Furthermore, motivated by the research results on the use of non-parametric tests for analyzing the algorithms’ behavior [17, 20, 26], we apply non-parametric statistical test, e.g., Kruskal–Wallis and Friedman test, to compare the performance of algorithms based on convergence and diversity. Table 5 shows ranks, the statistics and related p value obtained by the Kruskal–Wallis and Friedman tests. From the Table 5, it is clear that a significant difference exists across the set of different algorithms in the terms of convergence and diversity because all the related p values are less than 0.05. FTODE achieves the best rank both in Kruskal–Wallis and Friedman in terms of convergence, and only slightly worse than IMOPEO-PLM in terms of diversity. That because of the IMOPEO-PLM is an excellent method based on extremal optimization (EO), which has effective mutation operation and mechanism of generating new population [17].

Secondly, to analyze the proposed methods’ performance with fast convergence, we used those novel algorithms, such as IM/MOEA [14], NSGAIII [15] and KnEA [16] for comparing on different evolution generations. Fortunately, the platform of PlatEMO [29] has integrated those algorithms, so we can employ this platform to help us completing the comparison experiment. It should be note that we use the IGD [5, 6] as metric to evaluate performance of algorithms in this part test. The results are shown in the Tables 6, 7 and 8 with the evolution generation are 100, 250, and 500, respectively.

Table 6 IGD-Metric on multi-objective minimization problem ZDT1-ZDT4, ZDT6 and F1–F5 with 100 evolution generation
Full size table

From the Table 6, it can be seen that FTODE shows the best overall performance. Especially, FTODE have the best results on ZDT1, ZDT2, ZDT3, F2, F3 and F5. When the evolution generation is 250, the results in Table 7 reveal our FTODE also has best performance on ZDT1, ZDT3, F2 and F3. However, in Table 8, when the evolution generation is 500, the MOEA/D/DE [12] performs the best result on ZDT3, F1, F2 and F3; the FTODE has the best IGD on ZDT1, ZDT2, ZDT6 and F5. In other word, the FTODE shows similar performance with MOEA/D/DE but better than others four comparison algorithms when evolution generation is 500. Based on above analysis for Tables 6, 7 and 8, we can conclude that our FTODE has best performance when the evolution generation is small, and has competitive performance when the evolution generation is large. Namely, our algorithm can quickly converge to the optimal sets with less evolution generations.

In conclusion, the first experiment of this subsection shows that the proposed FTODE has competitive performance, which clearly won NSGAII, SPEAII and DEMO, similar with IMOPEO-PLM. The second part experiment claims that the FTODE has better convergence speed than those comparison algorithms.

Table 7 IGD-Metric on multi-objective minimization problem ZDT1-ZDT4, ZDT6 and F1–F5 with 250 evolution generation
Full size table
Table 8 IGD-Metric on multi-objective minimization problem ZDT1-ZDT4, ZDT6 and F1–F5 with 500 evolution generation
Full size table

4.4 Comparison with proposed uniform crowding distance calculation method and classic method

In this subsection, to demonstrate the efficiency of proposed uniform crowding distance calculation method, we provided the experiment tests for this method. . In the FTODE framework, we compare with Debs’ crowding distance method and proposed uniform crowding distance calculation method in terms of convergence metric. . The parameters of this test are: the population size \(\textit{NP}=100\), the scaling factor \(F=0.5\), the crossover probability \(C_{r}=0.3\), the maximum evolution generation is FES\(~=250\), the mutation strategy is “DE/Rand/1/bin”.

The test result for convergence is shown in Table 9, in which outside the parentheses are mean value, and in the parentheses are variances.

Table 9 Convergence metric \(\gamma \) comparison test for two methods of crowding distance in FTODE
Full size table

Clearly, the proposed uniform crowding distance calculation performs better than Debs’ crowding distance calculation method on all test problems. Especially on the function ZDT1 and ZDT2, the performance of the proposed method has significantly improved than comparison algorithm. Therefore, it is proved that the proposed uniform crowding distance calculation method is effective.

4.5 Parameter setting of the FTODE

To study the effect of parameters on the performance of FTODE, this subsection uses the different crossover probability \(C_{r}\), and mutation strategy for comparison and analysis. Storn and Price in [21] have indicated that a reasonable value for F is usually between 0.4 and 1, and a good initial choice of F was 0.5. Hence, we adopt the \(F=0.5\) and convergence metric for comparing the performance with different \(C_{r}\) and “DE/BEST/1” mutation strategy. The experiment results are provided in Tables 10 and 11.

Table 10 Comparison for different parameter with “DE/rand/1” mutation in terms of convergence metric \(\gamma \)
Full size table
Table 11 Comparison for different parameter with “DE/best/1” mutation in terms of convergence metric \(\gamma \)
Full size table

From Tables 10 and 11, we find that the best performance of FTODE is when using the “DE/Rand/1” mutation strategy with the \(F=0.5\) and the \(C_{r}=0.3\). Hence, the \(F = 0.5\) and \(C_{r} = 0.3\) as experience values are obtained. Similarly, when using mutation strategy “DE/Current-to-best/1”, the results of all the parameters combination are worse than with “DE/Rand/1/bin” mutation strategy. It should be noted that the FTODE using parameters \(F = 0.5\), \(C_{r} = 0.2\) and “DE/Rand/1” mutation also presents good performance. The reason is maybe that the small value of \(C_{r}\) between 0.2 and 0.3 is suitable for this method. We will deeply research the relationship between performance and these parameters in the future.

In short, through a series of parameters setting experimental for contrasting, we obtain that the suitable parameters of FTODE algorithm are: mutation strategy is “DE/Rand/1”, variation factor \(F = 0.5\) and crossover probability \(C_{r}\) is 0.3.

5 Using the FTODE to solve the two-objective coverage problem of WSNs

In this section, we use the proposed FTODE to solve the two-objective coverage problem of WSNs. In brief, the goal of issue is to use the less number of sensor nodes to cover the more target points in the WSNs.

5.1 The two-objective coverage problem of WSNs

In a WSN, the coverage problem is an important issue. In the area of \(L*W (L\) is length and W is width), there are m target points \(T=\{t_{1},t_{2},t_{3},\ldots ,t_{m}\}\) and n wireless sensor nodes \(S=\{S_{1},S_{2},S_{3},\ldots ,S_{n}\}\).

A sensor generally has two operation modes, active and sleep mode. When in active mode, a sensor can carry out its full operations, such as sensing and communication. To maintain those operations, sensors need to consume a relatively large amount of energy. In contrast, a sensor in a sleep mode uses only a small amount of energy and can be awoken in a scheduled working interval for full operations. Hence, in the point-coverage WSNs, we can maximize the lifetime of WSNs by maximizing the number of completely cover subsets [28]. Meanwhile, for saving the cost, how using less sensor nodes to find more completely cover subsets are our two optimization objectives. Although we briefly introduced a method to solve this problem in previous work [3], we will provide more detail and systematic method for this issue in this paper.

Firstly, we define the first optimization objective is \(f_{1}(x)=m/m_{max}\), m\(\in \)[1,m\(_{max}\)]. The m indicates the number of sensor nodes are used, which is the smaller the better. The \(m_{max}\) is the upper limit of m in theory. The second optimization objective is that we can obtain the number of completely cover subsets. To convert into a minimization problem, we use \(f_{\mathrm {2}}(x) =1-C/C_{max}\) as the second objective function. The C is the number of completely cover subset. The \(C_{max}\) indicates the upper limit of the number of completely cover subset. The others parameters are described detailed in the literature [28]. Hence, from above analysis, we deduce the minimization problem mode of the two-objective coverage problem of WSNs as follow Eq. (2).

$$\begin{aligned} \textit{Min} \left\{ {\begin{array}{l} f_{1} =\frac{m}{m_{\max } } \\ f_{2} =1-\frac{C}{C_{\max } } \\ \end{array}} \right. \quad s.t. 1<m\le m_{max}; 1<C\le C_{max}\nonumber \\ \end{aligned}$$
(2)

5.2 The representation of chromosomes

Intuitively, we use integer representation to encode a grouping combination of sensors. The value of a gene is produced randomly, which range is [0,\( C_{\mathrm {max}}\)]. A genes’ value indicates an index of the subset that the sensor joins, thus the sensors with the same index number will form a disjoint cover set. Note that if the value of a gene is 0, means this sensor is unused or in sleep mode. Hence, a chromosome represents an allocation scheme. The purpose of optimization is to find an allocation scheme that with less sensor nodes but more completely coverage subsets.

For example, suppose a chromosome is \(\textit{CH}= (1, 2, 3, 2, 1, 0, 3, 1, 2)\). It means that there are nine sensors but just eight of them are used, because the 0 indicates this sensor is unused. Hence, the used number of sensors is 8, namely the function \(f_{\mathrm {1}}=8/9\). Considering the second objective, this chromosome has three disjoint subsets. The set 1contains sensor \(S_{1}\), \(S_{6}\) and \(S_{8}\); set 2 contains sensor \(S_{2}\), \(S_{4}\) and \(S_{9}\); the set 3 contains \(S_{3}\) and \(S_{7}\). If each of the above three sets can completely cover all targets, it means that we obtained the number of disjoint set cover is 3. Assume the \(C_{max}\) is 4 in theory, then the objective function \(f_{\mathrm {2}}=1-(3/4)\).

5.3 The method of initialization recombination crossover and mutation

According to the representation of chromosomes, we randomly generate an integer between 0 and \(C_{\mathrm {max}}\) as each gene’s value (subset number) in the initialization. The sensors with same gene value mean that they shall form a subset.

The recombination operation is performed after the initialization, which guarantees at least one critical target’s sensor is divided into different disjoint sets (subsets). However, there are may exist many critical targets in WSNs, and it is very difficult to scatter all of corresponding sensors into different subsets [3, 28]. Thus, our recombination operation considers every chromosome, then randomly chooses a critical target and recombines different gene values to their corresponding sensors.

Take the chromosome CH\(_{2}\) as example, after initialization the chromosome CH\(_{2}\) is (2, 1, 1, 1, 2), then the recombination operation will be performed. According to above analysis, there are three critical targets (\(t_{2}\), \(t_{3}\), \(t_{4})\), which \(t_{2}\in (S_{2}\), \(S_{3})\), \(t_{3}\in (S_{1}\), \(S_{4})\), \(t_{4}\in (S_{3}\), \(S_{4})\). Thus, we randomly choose one critical target from \(t_{2}\), \(t_{3}\), \(t_{4}\), suppose that the target \(t_{4 }\)is chosen and its’ corresponding sensors are be scatted into different subset, such as one case is \(S_{3}=2\), \(S_{4}=1\). Namely the chromosome CH\(_{2}\) is became CH\(_{2} = (2, 1, 2, 1, 2)\). It’s obvious that after recombination operation the CH\(_{2}\) has better fitness than before. The pseudo code of recombination is given in Algorithm 4. It is need to explain that the code is described by Matlab language and the bold words are inner functions or keywords in Matlab.

figure d

Due to the mutation strategy is “DE/Rand/1” and the crossover style is binomial crossover. So, after mutation operation, the values of gene maybe become float type. Therefore, it needs to do round number operation for genes because their value should be integer type. We use the ceiling way for round number operation. If the value of gene without the range \([0, C_{\mathrm {max}}\)], the method will regenerate its value between the [0,\( C_{\mathrm {max}}\)].

5.4 The overview flow of using FTODE to research the two-objective coverage of WSNs

This subsection provides the overview flow of using FTODE to research the two-objective coverage of WSNs. The overview is offered in Algorithm 5.

figure e

5.5 Simulation experiment and analysis

For verification the performance of the FTODE, we use the NSGAII, FTODE and the classical DE to solve the same problem as comparison. It’s worth noting that the test sets of experiment are actual data and we have not the Parteo optimal set in theory. So, we cannot use the convergence indicator to compare their performance. However, when the evolution is finished, we draw those individuals belong to the first level of all algorithms for comparison. The algorithm has more individuals belong to the first level and these individuals more closely to origin, its’ performance will better.

We use six test sets for comparison experiment, the detail of test sets is shown in Table 12.

Table 12 The six test sets for comparison experiment
Full size table

The result of comparison experiments are shown in Figs. 5, 6, 7, 8, 9 and 10. In these figures, we just draw the first levels’ individual of different algorithms for comparison.

Fig. 5
figure 5

The first level individuals in case 1

Full size image
Fig. 6
figure 6

The first level individuals in case 2

Full size image
Fig. 7
figure 7

The first level individuals in case 3

Full size image
Fig. 8
figure 8

The first level individuals in case 4

Full size image
Fig. 9
figure 9

The first level individuals in case 5

Full size image

According to the Pareto-dominate principle, the Figs. 5, 6, 7, 8, 9 and 10 illustrate that the FTODEs’ performance is better than these comparison algorithms on the two-objective coverage problem of WSNs. In detail, the FTODE shows better solutions than both canon DE and the NSGAII on the case 3. On the case 2, 4, 5, 6, the FTODE displays better performance than DE and NSGAII significantly. More specifically, in these cases, most of individuals in the FTODE dominate that in DE and NSGAII. Furthermore, the number of first level individuals in FTODE is more than that in comparison algorithms on case 4, 5, 6. On the case 1, the FTODE provides slight better performance than the DE and NSGAII.

Based on above analysis, the FTODE performs the best among the three algorithms on the six test cases. Therefore, it can be drawn a conclusion that the proposed FTODE is reasonable and efficient to solve the two-objective coverage problem of WSNs.

Fig. 10
figure 10

The first level individuals in case 6

Full size image

5.6 Parameter setting of the FTODE algorithm

Price in [21] has indicated that a reasonable value for F is usually between 0.4 and 1, and a good initial choice of was 0.5. Hence, we use the \(F=0.5\) as default value with the “DE/Rand/1” mutation strategy.

The parameter \(C_{r}\) controls how many parameters in expectation are changed in a population member. To test the \(C_{r}\) influences the performance of FTODE, we use \(C_{r}=0.3\), 0.5, 0.8 for comparing test, respectively.

Because there are have not the optimization set in theory, we draw those individuals in the first level of algorithm for comparison when the evolution finished. The results are shown in Figs. 11, 12, 13, 14, 15 and 16.

Fig. 11
figure 11

The first level individuals in case 1 with various \(C_{r}\)

Full size image
Fig. 12
figure 12

The first level individuals in case 2 with various \(C_{r}\)

Full size image
Fig. 13
figure 13

The first level individuals in case 3 with various \(C_{r}\)

Full size image
Fig. 14
figure 14

The first level individuals in case 4 with various \(C_{r}\)

Full size image
Fig. 15
figure 15

The first level individuals in case 5 with various \(C_{r}\)

Full size image
Fig. 16
figure 16

The first level individuals in case 6 with various \(C_{r}\)

Full size image

Overall, The Figs. 11, 12, 13, 14, 15 and 16 show that the FTODE provides the best performance when the \(C_{r}=0.3\).Specifically, on the test 1, three crossover styles have similar performance, and the \(C_{r}=0.3\) strategy offers slight better than others. On the test 2-6, the FTODE with \(C_{r}=0.3\) provides the best solutions. Especially on the test 4 and 6, it obtains significant good solution on quantity of the first level. It is note that on test 2 and 3, there are exist a solution with \(f_{2}=0\) when \(f_{1}\ne 1\). That means using part number of sensors can find the maximum complete cover sets in theory. In other word, the number of sensors has some redundancy in this test. Without these redundant sensors, the algorithm also obtains the maximum complete cover sets in theory. From above analyses we can conclude that the suitable parameters setting are \(F=0.5\) and \(C_{r}=0.3\).

In addition, to study the various mutation strategies, with \(F=0.5\) and \(C_{r} = 0.3\) we adopt “DE/Rand/1”, “DE/Best/1” and “DE/current-to-best/1” for comparing, respectively.

Similar with others test in this subsection, we draw individuals in the first level of algorithm for comparison when the evolution finished. The results are shown in Figs. 17, 18, 19, 20, 21 and 22.

Fig. 17
figure 17

The first level individuals in case 1 with various mutation strategies

Full size image
Fig. 18
figure 18

The first level individuals in case 2 with various mutation strategies

Full size image
Fig. 19
figure 19

The first level individuals in case 3 with various mutation strategies

Full size image
Fig. 20
figure 20

The first level individuals in case 4 with various mutation strategies

Full size image
Fig. 21
figure 21

The first level individuals in case 5 with various mutation strategies

Full size image
Fig. 22
figure 22

The first level individuals in case 6 with various mutation strategies

Full size image

Figs 17 18, 19, 20, 21 and 22 show that the FTODE with the “DE/rand/1” mutation can obtain the best effect. Specifically, using this mutation strategy, the FTODE provides better performance than others strategies significant on test 2–4 and 6. On the test 1 and 5, all of these mutation strategies offer similar solutions. In a word, the performance of FTODE with the “DE/rand/1” mutation is the best, with the “DE/best/1” and “DE/current-to-best” mutation ranked second and third, respectively.

6 Conclusions

In this paper, to study the two-objective coverage problem of WSNs by means of DE, we proposed an improved DE algorithm with fast non-dominated solutions sorting and uniform crowding distance calculation. According to the principle and potential feature of non-dominated sorting solution, a fast non-dominated solutions sorting method was introduced. This method can reduce the number of individuals in sorting operation and choose individuals into next generation simultaneously. This method reduces the number of individuals for sorting process and the time complexity of algorithm. In addition, the uniform crowding distance calculation will retain the outline of optimal solution set, which can enhance the populations’ diversity.

Then, we incorporated the introduced sorting method and uniform crowding distance into the DE to solve the two-objective coverage problem of WSNs. For this specific problem, the two objectives are formulated as: the minimum number of sensor used and the maximum coverage rate. The decimal integer encoding is used and a recombination operation is introduced into FTODE. Simulation results show that the proposed FTODE provides better performance than the classic comparison algorithms.

Although the FTODE is suitable for multi-objective problem, this paper just applies it in two-objective optimization. The limitation of this method is that it needs to choose too many special individuals when handling the many-objective problem. In the future research work, we will extend the proposed algorithm to study the many-objective problems in WSNs and research the relationship between performance and these parameters.