Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

A wireless sensor network (WSN) is a network of distributed autonomous devices that can sense or monitor physical or environmental conditions cooperatively. In WSNs, there exists a large number of small, inexpensive, spatially distributed sensor nodes that are deployed in an ad hoc manner in vast geographical areas for remote operations and these nodes can acquire, process, and transmit data over wireless medium. WSNs also are used in numerous applications such as security detection, traffic tracking, environmental monitoring, because of characteristics of the low cost and ease of operation [1]. In addition, battery supply, storage resources and commutation bandwidth tremendously restrict the communication and computational capabilities of sensor nodes [2]. Therefore, there has been significant research concentrate that revolves around reaping and minimizing energy. But above all, it may be impossible to replace or change the batteries of the sensor nodes because of cost and operating environment considerations [3]. Therefore, the optimal power allocation can be considered as one of the crucial issues for designing a WSN.

Differential evolution (DE), which was firstly proposed by Storn and Price [4], is one of the most powerful EAs for global numerical optimization. The advantages of DE are its simple structure, ease of use, speed, and robustness, which leads it on many applications, such as data mining, neural network training, pattern recognition, digital filter design, engineering design, etc. [5]. More applications of DE can be found in the literature [6].

The OPA in WSN can be seen as a constrained numerical optimization problem [3]. In addition, the optimal power allocation in WSNs have attained considerable attention. Recently, there are several algorithms are proposed for OPA, such as particle swarm optimization (PSO) [3, 7, 8], hybrid DE with biogeography-based optimization [9]. Both the two algorithms achieved good performance for independent and identically distributed (i.i.d.) and correlated data fusion in WSNs. In addition, due to the advantages of DE in the numerical optimization, recently, DE has been successfully used for the constrained optimization problems (COPs) by means of employing the constraint-handling techniques [10]. Meanwhile there is no single parameter setting and strategy that is able to consistently obtain the best results for the OPA with different number of sensor nodes [11]. Therefore, it is worth exploring more effective algorithm for OPA.

Differential mutation is the crucial operator in DE which is operated based on the distribution of solutions in the current population. New offsprings are created by combining the parent individual and the mutant individual. Only if the offspring has better fitness value, it can replace its parent. However, it is a difficult and crucial task to choose which mutation strategy for the performance of the DE [12, 13]. Based on the above consideration, in this paper, we proposed a multi-operator differential evolution based on Probability Matching and constrained credit assignment for solving the OPA. The proposed method is referred to as PM-MDE, in short.

2 Preliminaries

In this section, we first briefly describe the optimal power allocation in WSNs, followed by the description of the classical DE algorithm. Then, the constraint-handling technique used in this work is introduced. Finally, adaptive strategy selection is presented.

2.1 Optimal Power Allocation in WSNs

Generally, the power allocation problem can be considered as a constrained numerical optimization problem and it also can be formulated as follows [3]:

$$\begin{aligned} \mathop {\min }\limits _{{G_k} \ge 0} \sum \limits _{k = 1}^L {G_k^2} \end{aligned}$$
(1)

subject to

$$\begin{aligned} \begin{array}{l} P(E) = Q(\frac{1}{2}\sqrt{{m^2}{e^T}A\sum {_L^{ - 1}Ae} } ) \le \varepsilon , \\ {G_k} \ge 0,\\ K = 1,\ldots ,L. \end{array} \end{aligned}$$
(2)

where \( \varepsilon \) is the required fusion error probability threshold, L indicates the number of sensor nodes, m represents the deterministic signal and \( {G_K} \) is the amplifier gain at node k. e is the L-length vector with all ones. The covariance matrix is \( \sum {_L} = {A^T}\sum {_v} A + \sum {_w} \), where \(A=diag({H_1}{G_1},\ldots ,{H_L}{G_L})\), \( \sum {_v} \) is the observation and \(\sum {_w} \) is receiver noise covariances. Specially, when the local observations and the receiver noise are both i.i.d., the probability of fusion error can be simplified to:

$$\begin{aligned} P(E) = Q\left( {\frac{m}{2}\sqrt{\sum \limits _{k = 1}^L {\frac{{H_K^2G_K^2}}{{\delta _v^2H_K^2G_K^2 + \delta _\omega ^2}}} } } \right) \le \varepsilon . \end{aligned}$$
(3)

The inequality in (3) can be expressed as follows:

$$\begin{aligned} \beta \le \sqrt{\sum \limits _{k = 1}^L {\frac{{H_K^2G_K^2}}{{\delta _v^2H_K^2G_K^2 + \delta _\omega ^2}}} } \end{aligned}$$
(4)

where \( \beta = \frac{2}{m}{Q^{-1}}(\varepsilon )\) and \(Q( \cdot )\) is the complementary Gaussian cumulative distribution function. \( {\delta _v}\) means the variances of the observation noise and \({\delta _w}\) represents the receiver noise. \( {H_k} \) indicates the channel fading coefficient. It is needed to point that \({H_k}\) follows an exponential distribution (i.e., Rayleigh fading) with unit mean [9].

Besides the above situation, when the sensor observations are spatially correlated, the observation noise covariance matrix \( \sum {_v}\) can be formulated as follows [14]:

$$\begin{aligned} \sum {_v} =\delta _v^2 \left( \begin{array}{lllll} 1&{}{\rho ^d} &{} \cdots &{} {\rho ^{d(L-2)}} &{} {\rho ^{d(L-1)}} \\ {\rho ^d} &{}1&{}\cdots &{} {\rho ^{d(L-3)}} &{} {\rho ^{d(L-2)}} \\ \vdots &{} \vdots &{}\ddots &{}\vdots &{}\vdots \\ {\rho ^{d(L-1)}} &{} {\rho ^{d(L-2)}}&{} \cdots &{} {\rho ^d} &{} 1 \end{array} \right) \end{aligned}$$
(5)

The inequality in (3) can be expressed as follows:

$$\begin{aligned} \beta \le \sqrt{{e^T}A\sum {_n^{-1}Ae}} \end{aligned}$$
(6)

where \(d_j=d(j-1),j=1,\ldots L\), which means the sensor nodes are equally spaced along a straight line. Because \( \sum {_v}\) is not diagonal, it is difficult to evaluate \(\sum {_n^{-1}} \) in closed form. Therefore, it is necessary to introduce a specific sensor network model which derives an upper bound for P(E) and is proposed by Wimalajeewa and Jayaweera [3]. Finally, DE algorithm becomes suitable to use for OPA under arbitrary correlated observation.

2.2 Differential Evolution

DE is a simple yet efficient evolutionary algorithm (EA) for global numerical optimization [4]. For the population initialization, a uniform distribution is usually used in the literature within the search space. After initialization, DE generates offsprings based on combining the parent individual and several other individuals of the same population which means that offsprings are generated according to mutation operation and crossover operation. An offspring is evaluated by a fitness function and then replaces the parent individual only if it has an equal or better fitness value. DE repeats this procedure that generates offsprings and replaces parent individual until a predefined termination criterion is satisfied. Generally, the terminal conditions can be fixed either the maximum number of fitness function evaluations (\({Max\_NFFEs}\)) or define a desired solution value to be reached (VTR).

3 Multi-operator Based Differential Evolution (PM-MDE)

In this section, we will introduce our proposed PM-MDE algorithm in detail. It is previously mentioned that there are many mutation strategies in DE and it is hard to choose the most suitable strategy for different problem in the different stage of evolution. Therefore, it is significant to autonomously select appropriate mutation strategy for OPA. To achieve this performance, in this work, we propose the multi-operator differential evolution for OPA based on Probability Matching (PM) technique and credit assignment method [15]. The PM technique and the credit assignment method are integrated into DE to implement the adaptive strategy selection and the relative fitness improvement calculation. Moreover, the parameter adaptation method of CR and F proposed in [16] is adopted in this work.

3.1 Strategy Selection and Probability Matching

Following [17], in this subsection the adaptive strategy selection will be introduced. Firstly, it can be supposed that we have \(K(K > 1)\) strategies in the pool \(A = \left\{ {{a_1},\ldots ,{a_k}} \right\} \) and a probability vector can be described like \(P(t) = \left\{ {{p_1}(t),\ldots ,{p_K}(t)} \right\} (\forall t:{p_{\min }} \le {p_i}(t) \le 1;\sum {_{i = 1}^K{p_i}(t)} = 1)\). The \({r_a}(t)\) presents reward which be achieved by a strategy a after its application at time t. The PM method is used to adaptively update the probability \({P_a}(t)\) of each strategy a based on its reward. \({q_a}(t)\) is the known quality (or empirical estimate) of a strategy a, that is updated as follows [18]:

$$\begin{aligned} {q_a}(t + 1) = {q_a}(t) + \alpha \cdot [{r_a}(t) - {q_a}(t)], \end{aligned}$$
(7)

where \(\alpha \in (0,1]\) is the adaptation rate. The PM method updates the probability \({P_a}(t)\) as follows [15, 18]:

$$\begin{aligned} {p_a}(t + 1) = {p_{\min }} + (1 - K \cdot {P_{\min }})\frac{{{q_a}(t + 1)}}{{\sum {_{i = 1}^K{q_i}(t + 1)} }}. \end{aligned}$$
(8)

where \({p_{\min }} \in (0,1]\) represents the minimum probability value of each strategy, the objective of this is to ensure no operator gets lost. It is indicated by Eq. (8) that when only one strategy achieves a reward during a long period of time and all other strategies receive no reward, then its selection probability \({P_a}(t)\) converges to \({p_{\max }} = {p_{\min }} + (1 - K \cdot {p_{\min }})\). It also can be seen that \(\sum {_{a = 1}^K} {p_a}(t) = 1\) and \(0< {P_{\min }} < \frac{1}{K}\).

3.2 Constrained Credit Assignment

As mentioned above, the OPA problem is a constrained optimization problem. Therefore, to assign the credit for each search operator, we need to design the constrained credit assignment technique. In this work, the constraint-handling technique named improved adaptive trade-off model [19] is employed, which was proposed by Wang and Cai and is the improved version of ATM [20]. In IATM, the population can be divided into three situations such as infeasible situation, semi-feasible situation and feasible situation.

In the infeasible situation, the solutions are measured based on their constraint violation. In the semi-feasible situation, the population includes both feasible and infeasible solutions and it can be divided into the feasible group (\({Z_1}\)) and the infeasible group (\({Z_2}\)) based on the feasibility of each solution. The infeasible individuals in the semi-feasible situation should be handled and evaluated based on their constraint violation. Then, the objective function can be seen as \(f(\mathbf {x})\) and \(\mathbf {x}\) is the vector of the solution. The objective function value \(f({\mathbf {x}_i})\) of the solution \({\mathbf {x}_i}\) is converted into

$$\begin{aligned} f'(\mathbf {x}_i) = \left\{ \begin{array}{ll} f(\mathbf {x}_i) ,&{}{i \in {Z_1}}\\ \max { \{ \varphi \cdot f({\mathbf {x}_{best}}) + (1 - \varphi ) \cdot f(\mathbf {x}_{worst}),f(\mathbf {x}_i) \}},&{}{i \in {Z_2}} \end{array} \right. \end{aligned}$$
(9)

where \(\varphi \) represents the feasibility ratio of the last population, and \(\mathbf {x}_{best}\) and \(\mathbf {x}_{worst}\) are the best and worst individual in the feasible group \({Z_1}\), respectively. After achieving the changed objective function value of each individual, then it should be normalized as

$$\begin{aligned} {f_\mathrm {nor}}({\mathbf {x}_i}) = \frac{{f'(\mathbf {x}_i) - \mathop {\text {min}}\limits _{j \in {Z_1} \cup {Z_2}} f'(\mathbf {x}_j)}}{{\mathop {\text {max} }\limits _{j \in {Z_1} \cup {Z_2}} f'(\mathbf {x}_j) - \mathop {\text {min}}\limits _{j \in {Z_1} \cup {Z_2}} f'(\mathbf {x}_j)}}. \end{aligned}$$
(10)

In addition, the normalized constraint violation can be evaluated as

$$\begin{aligned} {C_\mathrm {nor}}({\mathbf {x}_i}) = \left\{ \begin{array}{ll} 0 ,&{} {i \in {Z_1}}\\ \frac{{C({\mathbf {x}_i}) - \mathop {\text {min}}\limits _{j \in {Z_2}} C({\mathbf {x}_j})}}{{\mathop {\text {max}}\limits _{j \in {Z_2}} C({\mathbf {x}_j}) - \mathop {\text {min}}\limits _{j \in {Z_2}} C({\mathbf {x}_j})}} , &{} {i \in {Z_2}} \end{array}\right. \end{aligned}$$
(11)

where \(C(\mathbf {x})\) represents the distance of the solution \(\mathbf {x}\) from the boundaries of the feasible set, which also reflects the degree of its constraint violation.

Then, the final fitness function is obtained as follows:

$$\begin{aligned} {f_\mathrm {final}}({\mathbf {x}_i}) = {f_\mathrm {nor}}({\mathbf {x}_i}) + {C_\mathrm {nor}}({\mathbf {x}_i}). \end{aligned}$$
(12)

In the feasible situation, it is to say that all solutions are feasible in the population, the performance of the situation can be evaluated by the objective function value.

Based on the above fitness transformation technique, similar to the method in [21], the relative fitness improvement \(\eta _i\) can be calculated by

$$\begin{aligned} {\eta _i} = \left\{ \begin{array}{ll} \frac{\delta _1 }{{{f(\mathbf {u}_i)}}} \cdot ({f(\mathbf {x}_i)} - {f(\mathbf {u}_i)}),&{} \text {feasible situation}\\ \frac{\delta _2 }{{{C(\mathbf {u}_i)}}} \cdot ({C(\mathbf {x}_i)} - {C(\mathbf {u}_i)}),&{} \text {infeasible situation}\\ \frac{\delta _3 }{{{f_\mathrm {final}(\mathbf {u}_i)}}} \cdot ({f_\mathrm {final}(\mathbf {x}_i)} - {f_\mathrm {final}(\mathbf {u}_i)}), &{} \text {semi-feasible situation} \end{array} \right. \end{aligned}$$
(13)

where \(i = 1,\ldots ,\mu \). \(\delta \) is the objective fitness of the best-so-far solution in the population. \(\mathbf {x}_i\) and \(\mathbf {v}_i\) are the parent and its offspring, respectively.

figure a

In [17], four different credit assignment methods are presented, and the averaged normalization reward is able to provide highly-competitive results through benchmark functions. Based on this consideration, the averaged normalization reward is selected for the credit assignment in this work and is listed as follows:

$$\begin{aligned} {r_a}(t) = \frac{{{r'_a}(t)}}{{\mathop {\text {max}}\limits _{a = 1,\ldots ,K} {r'_a}(t)}} \end{aligned}$$
(14)

where \({r'_a}(t)\) is calculated as

$$\begin{aligned} {r'_a}(t) = \frac{{\sum {_{i = 1}^{\left| {{S_a}} \right| }\left| {{S_a}} \right| } }}{{\left| {{S_a}} \right| }} \end{aligned}$$
(15)

and \(S_a\) is the set of all relative fitness improvement \({\eta _i}\) of a strategy \(a~(a=1,\cdots ,K)\) at generation t.

3.3 Strategy Pool

DE has realized using different mutation strategies to achieve different performance for solving different problems. Instead of employing the computationally enormous trial-and-error search for the most suitable mutation strategy, we maintain a strategy candidate pool including four mutation strategies. In this work, we choose several effective mutation strategies commonly referred to in DE literatures and choose some of them to construct the strategy candidate pool which are listed as follows:

  1. (1)

    “DE/rand/1”:

    $$\begin{aligned} \mathbf {v}_i = \mathbf {x}_{r1} + F \cdot \big (\mathbf {x}_{r2}-\mathbf {x}_{r3}\big ) \end{aligned}$$
    (16)
  2. (2)

    “DE/current-to-best/1”:

    $$\begin{aligned} \mathbf {v}_i = \mathbf {x}_{i} + F \cdot \big (\mathbf {x}_{best}-\mathbf {x}_{i}\big ) + F \cdot \big (\mathbf {x}_{r_2}-\mathbf {x}_{r_3}\big ) \end{aligned}$$
    (17)
  3. (3)

    “DE/rand-to-best/1”:

    $$\begin{aligned} \mathbf {v}_i = \mathbf {x}_{r1} + F \cdot \big (\mathbf {x}_{best}-\mathbf {x}_{r1}\big ) + F \cdot \big (\mathbf {x}_{r_2}-\mathbf {x}_{r_3}\big ) \end{aligned}$$
    (18)
  4. (4)

    “DE/current-to-rand/1 ”:

    $$\begin{aligned} \mathbf {v}_i = \mathbf {x}_{i} + F \cdot \big (\mathbf {x}_{r1}-\mathbf {x}_{i}\big ) + F \cdot \big (\mathbf {x}_{r_2}-\mathbf {x}_{r_3}\big ) \end{aligned}$$
    (19)

    where \({\mathbf {x}_{best}}\) is the best individual in the current generation, \({r_1},{r_2},{r_3},{r_4},{r_5} \in \{ 1,\ldots ,NP\} \) and \({r_1} \ne {r_2} \ne {r_3} \ne {r_4} \ne {r_5} \ne i\).

It is noteworthy that there are many other strategies could also be incorporated in the pool; the above strategies are just used as an example for the evaluation of the proposed method. It must also be pointed out that the size of the strategy pool and the selection of the strategies used in the pool is not sure and there are no theoretical studies as of today on the choice of the optimal number of available strategies and on the selection of strategies to form the strategy pool [12]. Therefore, by combining the above-mentioned two aspects with the DE algorithm, the PM-MDE method is developed. The pseudo-code of PM-MDE is illustrated in Algorithm 1. During evolution, at each generation t, there is only one strategy \(SI_i\) been selected based on the choice probability of the strategy for each target parent i. Then the offspring is generated by employing the selected strategy. The relative fitness improvement \({\eta _i}\) based on constraint handling technique is calculated and stored in the set \(S_{SI_i}\) after evaluating the offspring. Finally, parameters value of PM-MDE algorithm such as the reward, quality and probability of each strategy are updated. In addition, to remedy the parameter fine-tuning, in this work, the parameter adaptation technique proposed in [16] is used in PM-MDE.

4 Experimental Results and Analysis

In this section, we perform comprehensive experiments to evaluate the performance of PM-MDE and compare the results of our methods with a algorithm named CBBO-DE, which is a hybridization of BBO algorithm and DE algorithm for OPA.

4.1 Experimental Settings

Without loss of generality, for all experiments, we use the following parameters unless a change is mentioned:

  • Population size: \(NP = 100\);

  • \(\mu _{CR}=0.5\) and \(\mu _F=0.5\) [4];

  • Number of strategies: \(K=4\); minimal probability: \(p_{min}=0.05\); adaptation rate: \(\alpha =0.3\);

  • Maximum Number of Fitness Function Evaluations (Max_NFFEs): 30, 000.

Moreover, all experiments were run 30 times. Simulations have been carried out for various values of parameters: fusion error threshold \(\varepsilon \), correlation degree \(\rho \), and number of sensors (L), and the performances of the different algorithms are shown for different combinations: \(\rho =\{0,0.01,0.1,0.5\}\). \(\rho =0\) represents the uncorrelated case. The fusion error threshold \(\varepsilon \) takes its values in \(\{0.1,0.05,0.01,0.001\}\). The observation signal-to-noise ratio (SNR) \(r_0\) was set at 10 dB.

Table 1. Numerical results of DE with fixed strategy and PM-MDE to optimal power allocation in WSNs when the observation are i.i.d. with \(\rho = 0,\varepsilon = 0.1\) and different number of sensors.
Full size table
Table 2. Numerical results of PM-MDE with CBBO-DE to optimal power allocation in WSNs when the observation are i.i.d. with \(\rho = 0,\varepsilon = \{0.1,0.05,0.01,0.001\}\) and different number of sensors.
Full size table

4.2 Numerical Results

In this section, in order to compare the performance of the adaptive strategy selection for OPA, the DE with fixed strategy and recently proposed algorithm for OPA are considered. For fair comparison, the adaptive parameters control keeps the same in all simulation. The statistical features (mean, and standard deviation values) of the best feasible solutions obtained after 30 independent runs for each case study are used to evaluate the performance of the competing algorithms. Numerical results of competing algorithms for OPA problems in WSNs are shown in Tables 1, 2, 3, 4 and 5 when the observations are i.i.d and correlated. In addition, the best result among competing algorithms in Tables 1, 2, 3, 4 and 5 are shown in boldface.

Firstly, we choose four strategies which are frequently used in DE literature as the competing algorithm in Table 1. From results in the Table 1 we can see that PM-MDE algorithm we proposed is significantly better than DE with fixed strategies on most of the value of L (sensors) when the observations are i.i.d with \(\rho =0\) and \(\varepsilon =0.1\). Second, in \(L=50\), DE algorithm with DE/best/1 obtains best results and better results were found by PM-MDE among all competing algorithms. Important observations about the convergence rate and stability of different algorithms can be made from the results presented in Table 1 and these results suggest that the overall convergence rate of PM-MDE is the best or second best for OPA in the competing algorithms.

Table 3. Numerical results of PM-MDE with CBBO-DE to optimal power allocation in WSNs when the observation are correlated with \(\rho = \{0.01,0.1,0.5\}\), \(L=10\), \(\varepsilon = \{0.1,0.05,0.01,0.001\}\).
Full size table

Table 2 shows a comparison of the performances of PM-MDE algorithm and CBBO-DE algorithm, for the different values of \(\varepsilon \) and L, in the uncorrelated case (\(\rho =0\)). Firstly, various simulations of PM-MDE with \(\varepsilon \) chosen from \(\{0.1,0.05,0.01,0.001\}\) shown that PM-MDE algorithm emerged the best candidate result for \(L=10\) and \(L=50\) sensors in terms of the best mean results. For the \(L=20\) sensors case, the CBBO-DE produces the best mean results. Secondly, simulation results also indicate that PM-MDE does function efficiently within the large number of sensors.

Table 4. Numerical results of PM-MDE with CBBO-DE to optimal power allocation in WSNs when the observation are correlated with \(\rho = \{0.01,0.1,0.5\}\), \(L=20\), \(\varepsilon = \{0.1,0.05,0.01,0.001\}\).
Full size table

Tables 3, 4 and 5 show the results of the comparison with CBBO-DE when the observations are correlated in the case of \(L=10,20,50\) sensors for different values of the fusion error probability \(\varepsilon \) and the degree of correlation \(\rho \), respectively. In the experiments reported above, the results are shown for \(\rho =\{0,0.01,0.1,0.5\}\) and \(\varepsilon =\{0.1,0.05,0.01,0.001\}\). It can be seen that in each case, PM-MDE respectively outperforms other competing algorithm in 10, 8, and 12. From Table 5, specifically, we can see that PM-MDE has emerged as the best performer since it obtained the best mean results in the all cases. It is similar to the observation from above experiments, where PM-MDE algorithm does show obvious performance improvement for OPA, especially in the large number of sensors PM-MDE algorithm obtains better performance.

Overall, according to the results shown in Tables 1, 2, 3, 4 and 5 and the above analysis, we can conclude that when the observations are i.i.d and correlated (Tables 3, 4 and 5), the performance improvement for PM-MDE, compared to the other competing algorithm, was better for \(L=10 ,20,\,\text {and}\,50\) sensors. Meanwhile, PM-MDE obtains better results for the larger sensors.

Table 5. Numerical results of PM-MDE with CBBO-DE to optimal power allocation in WSNs when the observation are correlated with \(\rho = \{0.01,0.1,0.5\}\), \(L=50\) senors, \(\varepsilon = \{0.1,0.05,0.01,0.001\}\) and different number of sensors.
Full size table

5 Conclusions

Optimal power allocation (OPA) is considered to be one of the key issues in designing a wireless sensor network (WSN). In this paper, multi-operator differential evolution is proposed for the optimal power allocation in WSNs. Combining with the constraint-handling technique, DE can be used to deal with OPA. However, the DE performance mainly depends on mutation and crossover operators. This new algorithm adaptively chooses the suitable strategy for a specific problem, meanwhile the probability matching technique and credit assignment method are integrated into DE algorithm. In addition, PM-MDE is compared with DE algorithm using fixed strategy and CBBO-DE algorithm proposed in [11] for OPA. The numerical results indicate that PM-MDE has outperformed the other competing algorithms for several types of simulation case studies, including both independent local observation cases and correlated observation cases. It has also been observed that, PM-MDE algorithm function efficiently within the large number of sensors.