# WSNs Compressed Sensing Signal Reconstruction Based on Improved Kernel Fuzzy Clustering and Discrete Differential Evolution Algorithm

Authors: Zhou-zhou Liu; Shi-ning Li
Journal: Journal of Sensors
 (2019)

---

## Abstract

To reconstruct compressed sensing (CS) signal fast and accurately, this paper proposes an improved discrete differential evolution (IDDE) algorithm based on fuzzy clustering for CS reconstruction. Aiming to overcome the shortcomings of traditional CS reconstruction algorithm, such as heavy dependence on sparsity and low precision of reconstruction, a discrete differential evolution (DDE) algorithm based on improved kernel fuzzy clustering is designed. In this algorithm, fuzzy clustering algorithm is used to analyze the evolutionary population, which improves the pertinence and scientificity of population learning evolution while realizing effective clustering. The differential evolutionary particle coding method and evolutionary mechanism are redefined. And the improved fuzzy clustering discrete differential evolution algorithm is applied to CS reconstruction algorithm, in which signal with unknown sparsity is considered as particle coding. Then the wireless sensor networks (WSNs) sparse signal is accurately reconstructed through the iterative evolution of population. Finally, simulations are carried out in the WSNs data acquisition environment. Results show that compared with traditional reconstruction algorithms such as StOMP, the reconstruction accuracy of the algorithm proposed in this paper is improved by 36.4-51.9%, and the reconstruction time is reduced by 15.1-31.3%.


---

## Body

## 1. Introduction

The rapid development of wireless sensor networks (WSNs) has binging human society into the era of big data. However, huge amount of data collected from sensor network is also accompanied by the sharp increase of the signal bandwidth [1]. If we still adopt the traditional Nyquist sampling theorem for data acquisition in this case, it will bring unprecedented challenges to the hardware system [2]. The advent of compressive sensing (CS) [3] solved this problem and created a whole new approach for the signal information processing [4, 5]. Through a series of nonlinear optimization algorithm, CS is able to accurately reconstruct compressible signal from a small amount of data and greatly reduced the requirement for the sampling rate [6]. Thus, the theory of compressed sensing is gradually and widely applied to image processing, wireless sensor networks, radio communication, etc.Sparse representation, observation matrix, and reconstruction algorithm are the core contents in compressed sensing, and the reconstruction algorithm is the most critical part [7]. It is commonly divided into three kinds: convex optimization algorithm, greedy algorithm, and their combination. The key problem in CS reconstruction is how to use a small amount of observed signal to reconstruct the original signal rapidly and accurately. Furthermore, several problems, such as high computational complexity, large amount of data, and preset sparsity, still need to be solved. Reference [7] proposed a SL0 reconstruction algorithm for compressive sensing based on BFGS quasi Newton method, which effectively improved the iterative efficiency of greedy matching pursuit algorithm by taking advantage of the rapid convergence of quasi Newton method. Wang et al. [2] introduced Dice coefficient matching metric into SWOMP reconstruction algorithm to overcome the inherent defect that the inner product matching criterion of SWOMP is sensitive to residual signals. Simulation results show that their algorithm has higher signal reconstruction success rate. In [8], researchers discussed the signal reconstruction algorithm for compressed sensing without prior information of signal sparsity. But the signal reconstruction accuracy of this algorithm needs to be improved.Currently, most compressed sensing algorithms reconstruct the original signal by minimizing itsl0 or l1 norm [9]. This is NP-hard problem. Therefore, we propose a WSNs compressed sensing signal reconstruction algorithm based on fuzzy clustering and discrete differential evolution. In this algorithm, we consider signal with unknown sparsity as differential evolution particle coding and reconstruct the signal through population iterative evolution. To improve the efficiency and accuracy of signal reconstruction, fuzzy clustering is utilized while the differential evolution mechanism is redefined. Finally, simulation experiments are carried out to verify its validity.


## 2. Differential Evolution Algorithm Based on Fuzzy Clustering

### 2.1. Differential Evolution

Differential evolution (DE) [10] is a kind of intelligent optimization algorithm with random search. It preserves the individuals with better fitness through mutation and competition to achieve the desired end. Due to its excellent global convergence and good robustness, fewer number of control parameters, and easy to be implemented, DE has been widely used in solving complex optimization problems [11].An iteration of the classical DE algorithm mainly consists of three basic steps: mutation, crossover, and selection. For N-dimensional optimization, there exists a differential evolution population composed ofP particles Xitxi1t,⋯,xiNt (i∈1,P) for the current generation t. The process of performing mutation on Xitxi1t,⋯,xiNt can be expressed as(1)Vit=Xat+F×Xbt-Xctwhere F∈0.4,1 denotes the scalar number, Vit denotes the mutant particle. The indices a,b,c∈1,P are mutually exclusive integers randomly chosen from the range [1,P], which are also different from i. In essence, mutation randomly selects three different particles from the current population, multiplies the difference of any two of these three particles with the scalar number F, and adds the scaled difference to the third one to obtain the mutant particle to fuse more individual information.To enhance the potential diversity of the population, crossover operation is then performed. It is a process of selecting components fromVitvi1t,⋯,viNt and Xit according to certain probability to obtain the trial particle, described as(2)Uitui1t,⋯,uiNt⇐uijt=vijtrandbj≤CRorj=rnbrixijtrandbj>CRorj≠rnbriwhere CR∈0,1 is called the crossover rate, randbj∈0,1 is a random number lying between 0 and 1, and rnbri is an integer randomly selected from range 1,N, which ensures that Uit gets at least one component from Vit.Then, the next generation particleXit+1 is selected in the form of roulette to keep the population size constant over subsequent generations. Taking the minimum optimization as an example, the selection operation is described as(3)Xit+1=Uit,iffUit≤fXitXit,elsewhere fXit is the fitness value of particle Xit.We can see that, in each iteration, the population always keeps the better individual with higher fitness, so as to reach the global optimal solution.


### 2.2. Improved Kernel FCM

Fuzzy C-means clustering algorithm (FCM) is one of the most widely used clustering algorithms. It uses membership to describe the degree to which a data belongs to a certain subclass for data classification [12]. For a S-dimension dataset X∈RS, clustering is to divide n samples xk∈X, k=1,2,⋯,n, into C subclasses while making the value of the clustering objective function minimum; that is, (4)minJU,V=∑i=1C∑k=1nμikmxk-vi2where μik is the membership of sample xk to the ith subclass, U=μikC×n is the membership matrix, V=vi (i=1,2,⋯,C) is the set of clustering center, and m is the fuzzy weighted index. Let ∂J/∂μik=0,∂J/∂vi=0; we have(5)∂J∂μik=0⇒μik=xk-vi-2/m-1∑j=1Cxk-vj-2/m-1,∂J∂vi=0⇒vi=∑k=1nμikmxk∑k=1nμikms.t.∑i=1Cμik=1,μik∈0,1,∑k=1nμik∈0,1It can be seen that FCM is a kind of local search algorithm and is sensitive to initial values [13]. Since FCM uses Euclidean distance to evaluate the similarity, it is only suitable for processing data with appropriate compactness and good dispersion. Therefore, kernel fuzzy C-means clustering algorithm (KFCM) is used to replace the Euclidean distance with kernel-induced distance, expressed as(6)minJU,V=∑i=1C∑k=1nμikmΦxk-Φvi2Φxk-Φvi2 in (6) can be further derived into the following form:(7)Φxk-Φvi2=Φxk-ΦviTΦxk-Φvi=ΦTxkΦxk-ΦTxkΦvi-ΦxkΦTvi+ΦTviΦvi=Kxk,xk-2Kxk,vi+Kvi,viwhere Kx,v=ΦTxΦv is the inner product of kernel function. In this paper, we select Gaussian function as Kx,v, which means Kx,v=exp-xk-vi2/σ2, Kxk,xk=1, Kvk,vk=1, and ΦTxkΦvi=ΦxkΦTvi. Thus, the clustering objective function, membership μik, and clustering center vi can be calculated according to the following equations:(8)minJU,V=2∑i=1C∑k=1nμikm1-Kxk,vi+Kvi,vi(9)μik=1-Kxk,vi-1/m-1∑j=1C1-Kxk,vj-1/m-1,vi=∑k=1nμikmKxk,vixk∑k=1nμikmKxk,viAlthough KFCM adopts kernel-induced distance to broaden its application range, it still has many problems waiting to be solved. Firstly, the clustering number C should be set in advance, but the preset value will affect the final clustering result directly. Secondly, KFCM usually generates the initial clustering center through random initialization, which reduces the clustering effectiveness. Finally, the value of fuzzy weighted indexm, to a great extent, affects the clustering result.


### 2.3. Implementation of Improved Kernel FCM

In this part, we introduce validity index based on compactness and dispersion to realize the automatic classification of clustering number and initialization of the cluster center with “maximum benefit” to increase the clustering performance.Validity index an appropriate validity index will well reflect the clustering quality. The number of clusters that makes the validity index reaches the optimum is called the optimum number of clusters. Therefore, we use compactness Var and dispersion Sep to define validity index VSU,V as(10)VSU,V=Var△U,VSep△U,C(11)Var△U,V=VarU,VVarmax,Varmax=max︸CVarU,VSep△U,V=SepU,CSepmax,Sepmax=max︸CSepU,Cwhere C=2,3,⋯,Cmax and Cmax is the maximum number of clusters. The compactness Var and dispersion Sep are computed in the following way:(12)VarU,V=∑i-1C∑j=1nμikd2xj,viniC+1C-1dxj,vi=1-exp-βxj-vi2,β=1n∑j=1nxj-1n∑j=1nxj2-1(13)SepU,C=1-maxi≠jmaxi≠jminμik,μjkwhere ni is the sample number of the ith subclass. From the calculation formulas above, it can be seen that a smaller Var means better homogeneity within a class, and a larger Sep indicates greater separation between classes. In summary, the smaller the value of validity index is, the better the clustering quality.Initialization of the cluster center with “maximum benefit” to reduce the influence of the random initialization cluster center has on the clustering results, the initialization of the cluster center with “maximum benefit” is designed. In sample set X=x1,x2,⋯,xn, randomly select one sample xk, k=1,2,⋯,n, as the first classification clustering center, written as v1=xk. Then, select another sample xj (j≠k) with probability Pxj→v2 from the remaining samples as the second classification clustering center, expressed as v2=xj. Here, the calculation formula for Pxj→v2 is (14)Pxj→v2=xj-v12∑i=1nxi-v12,i=1,2,⋯,n∧i≠kThe third classification clustering center, v3=xw (w≠j≠k), is selected from the remaining samples with the probability Pxw→v3:(15)Pxw→v3=xw-v12+xw-v22∑i=1nxi-v12+∑i=1nxi-v22,i=1,2,⋯,n∧i≠k≠jand so on, until the C clustering centers are all selected. Such procedure ensures enough differences between classes and effectively reduces the probability of the algorithm falling into local optimal.The improved kernel FCM (IKFCM) can realize the automatic classification of clustering number. Its pseudocode is shown in Pseudocode1.Pseudocode 1
(1) Set the original number of clusters C=2 and initialize parameters: maximum number of clusters C m a x, fuzzy weighted index m, maximum number of iterations Tmax, and the stopping criterion Θ. (2) Initialize the clustering center V according to the “maximum benefit” clustering center initialization method. Calculate the initial membership matrix according to (9). For C=2:Cmax (3) While (vkt-vkt-1≤Θt≤Tmax) do (4) {Calculate membership matrix Ut and clustering center Vt according to (9). (5) t+1→t. (6) Calculate validity index VSCU,V according to (10)-(13). End for (7) Output results: the C corresponding to the minimum V S C U , V is the optimal number of clusters, and the corresponding clustering center and membership is the optimal Vand U respectively.


### 2.4. Implementation of Differential Evolution Based on IKFCM

Like other intelligent optimization algorithms, the population diversity of DE decreases with the increase of iteration times, and the random selection of individuals for mutation may accelerate the population trapped in local optimal [14]. Thus, in order to further improve the global optimization ability and convergence accuracy of DE, we use fuzzy clustering to analyze the population, making it more scientific for selecting particles for mutation in each iteration.As one of the most widely used clustering algorithms, FCM classifies data through analyzing how closely a data is relative to different classes, making data samples with more similarity be classified into the same class. In this paper, we utilize IKFCM for cluster analysis before DE, and its classification result is considered as the basis of selecting particles for mutation. After a certain number of iterations, the population is divided into C subclasses by IKFCM, and there are more similarities within classes and greater differences between classes. When it comes to mutation, particlesXat, Xbt, and Xct will be selected from different classes, thus effectively expanding the diversity of mutant particle and ensuring that particles with larger differences will be participated in the population’s evolution and eventually improves the convergence performance of DE. The specific process of the DE based on fuzzy clustering, named IDDE, is presented in Figure 1.Figure 1
Flow chart of IDDE.


## 2.1. Differential Evolution

Differential evolution (DE) [10] is a kind of intelligent optimization algorithm with random search. It preserves the individuals with better fitness through mutation and competition to achieve the desired end. Due to its excellent global convergence and good robustness, fewer number of control parameters, and easy to be implemented, DE has been widely used in solving complex optimization problems [11].An iteration of the classical DE algorithm mainly consists of three basic steps: mutation, crossover, and selection. For N-dimensional optimization, there exists a differential evolution population composed ofP particles Xitxi1t,⋯,xiNt (i∈1,P) for the current generation t. The process of performing mutation on Xitxi1t,⋯,xiNt can be expressed as(1)Vit=Xat+F×Xbt-Xctwhere F∈0.4,1 denotes the scalar number, Vit denotes the mutant particle. The indices a,b,c∈1,P are mutually exclusive integers randomly chosen from the range [1,P], which are also different from i. In essence, mutation randomly selects three different particles from the current population, multiplies the difference of any two of these three particles with the scalar number F, and adds the scaled difference to the third one to obtain the mutant particle to fuse more individual information.To enhance the potential diversity of the population, crossover operation is then performed. It is a process of selecting components fromVitvi1t,⋯,viNt and Xit according to certain probability to obtain the trial particle, described as(2)Uitui1t,⋯,uiNt⇐uijt=vijtrandbj≤CRorj=rnbrixijtrandbj>CRorj≠rnbriwhere CR∈0,1 is called the crossover rate, randbj∈0,1 is a random number lying between 0 and 1, and rnbri is an integer randomly selected from range 1,N, which ensures that Uit gets at least one component from Vit.Then, the next generation particleXit+1 is selected in the form of roulette to keep the population size constant over subsequent generations. Taking the minimum optimization as an example, the selection operation is described as(3)Xit+1=Uit,iffUit≤fXitXit,elsewhere fXit is the fitness value of particle Xit.We can see that, in each iteration, the population always keeps the better individual with higher fitness, so as to reach the global optimal solution.


## 2.2. Improved Kernel FCM

Fuzzy C-means clustering algorithm (FCM) is one of the most widely used clustering algorithms. It uses membership to describe the degree to which a data belongs to a certain subclass for data classification [12]. For a S-dimension dataset X∈RS, clustering is to divide n samples xk∈X, k=1,2,⋯,n, into C subclasses while making the value of the clustering objective function minimum; that is, (4)minJU,V=∑i=1C∑k=1nμikmxk-vi2where μik is the membership of sample xk to the ith subclass, U=μikC×n is the membership matrix, V=vi (i=1,2,⋯,C) is the set of clustering center, and m is the fuzzy weighted index. Let ∂J/∂μik=0,∂J/∂vi=0; we have(5)∂J∂μik=0⇒μik=xk-vi-2/m-1∑j=1Cxk-vj-2/m-1,∂J∂vi=0⇒vi=∑k=1nμikmxk∑k=1nμikms.t.∑i=1Cμik=1,μik∈0,1,∑k=1nμik∈0,1It can be seen that FCM is a kind of local search algorithm and is sensitive to initial values [13]. Since FCM uses Euclidean distance to evaluate the similarity, it is only suitable for processing data with appropriate compactness and good dispersion. Therefore, kernel fuzzy C-means clustering algorithm (KFCM) is used to replace the Euclidean distance with kernel-induced distance, expressed as(6)minJU,V=∑i=1C∑k=1nμikmΦxk-Φvi2Φxk-Φvi2 in (6) can be further derived into the following form:(7)Φxk-Φvi2=Φxk-ΦviTΦxk-Φvi=ΦTxkΦxk-ΦTxkΦvi-ΦxkΦTvi+ΦTviΦvi=Kxk,xk-2Kxk,vi+Kvi,viwhere Kx,v=ΦTxΦv is the inner product of kernel function. In this paper, we select Gaussian function as Kx,v, which means Kx,v=exp-xk-vi2/σ2, Kxk,xk=1, Kvk,vk=1, and ΦTxkΦvi=ΦxkΦTvi. Thus, the clustering objective function, membership μik, and clustering center vi can be calculated according to the following equations:(8)minJU,V=2∑i=1C∑k=1nμikm1-Kxk,vi+Kvi,vi(9)μik=1-Kxk,vi-1/m-1∑j=1C1-Kxk,vj-1/m-1,vi=∑k=1nμikmKxk,vixk∑k=1nμikmKxk,viAlthough KFCM adopts kernel-induced distance to broaden its application range, it still has many problems waiting to be solved. Firstly, the clustering number C should be set in advance, but the preset value will affect the final clustering result directly. Secondly, KFCM usually generates the initial clustering center through random initialization, which reduces the clustering effectiveness. Finally, the value of fuzzy weighted indexm, to a great extent, affects the clustering result.


## 2.3. Implementation of Improved Kernel FCM

In this part, we introduce validity index based on compactness and dispersion to realize the automatic classification of clustering number and initialization of the cluster center with “maximum benefit” to increase the clustering performance.Validity index an appropriate validity index will well reflect the clustering quality. The number of clusters that makes the validity index reaches the optimum is called the optimum number of clusters. Therefore, we use compactness Var and dispersion Sep to define validity index VSU,V as(10)VSU,V=Var△U,VSep△U,C(11)Var△U,V=VarU,VVarmax,Varmax=max︸CVarU,VSep△U,V=SepU,CSepmax,Sepmax=max︸CSepU,Cwhere C=2,3,⋯,Cmax and Cmax is the maximum number of clusters. The compactness Var and dispersion Sep are computed in the following way:(12)VarU,V=∑i-1C∑j=1nμikd2xj,viniC+1C-1dxj,vi=1-exp-βxj-vi2,β=1n∑j=1nxj-1n∑j=1nxj2-1(13)SepU,C=1-maxi≠jmaxi≠jminμik,μjkwhere ni is the sample number of the ith subclass. From the calculation formulas above, it can be seen that a smaller Var means better homogeneity within a class, and a larger Sep indicates greater separation between classes. In summary, the smaller the value of validity index is, the better the clustering quality.Initialization of the cluster center with “maximum benefit” to reduce the influence of the random initialization cluster center has on the clustering results, the initialization of the cluster center with “maximum benefit” is designed. In sample set X=x1,x2,⋯,xn, randomly select one sample xk, k=1,2,⋯,n, as the first classification clustering center, written as v1=xk. Then, select another sample xj (j≠k) with probability Pxj→v2 from the remaining samples as the second classification clustering center, expressed as v2=xj. Here, the calculation formula for Pxj→v2 is (14)Pxj→v2=xj-v12∑i=1nxi-v12,i=1,2,⋯,n∧i≠kThe third classification clustering center, v3=xw (w≠j≠k), is selected from the remaining samples with the probability Pxw→v3:(15)Pxw→v3=xw-v12+xw-v22∑i=1nxi-v12+∑i=1nxi-v22,i=1,2,⋯,n∧i≠k≠jand so on, until the C clustering centers are all selected. Such procedure ensures enough differences between classes and effectively reduces the probability of the algorithm falling into local optimal.The improved kernel FCM (IKFCM) can realize the automatic classification of clustering number. Its pseudocode is shown in Pseudocode1.Pseudocode 1
(1) Set the original number of clusters C=2 and initialize parameters: maximum number of clusters C m a x, fuzzy weighted index m, maximum number of iterations Tmax, and the stopping criterion Θ. (2) Initialize the clustering center V according to the “maximum benefit” clustering center initialization method. Calculate the initial membership matrix according to (9). For C=2:Cmax (3) While (vkt-vkt-1≤Θt≤Tmax) do (4) {Calculate membership matrix Ut and clustering center Vt according to (9). (5) t+1→t. (6) Calculate validity index VSCU,V according to (10)-(13). End for (7) Output results: the C corresponding to the minimum V S C U , V is the optimal number of clusters, and the corresponding clustering center and membership is the optimal Vand U respectively.


## 2.4. Implementation of Differential Evolution Based on IKFCM

Like other intelligent optimization algorithms, the population diversity of DE decreases with the increase of iteration times, and the random selection of individuals for mutation may accelerate the population trapped in local optimal [14]. Thus, in order to further improve the global optimization ability and convergence accuracy of DE, we use fuzzy clustering to analyze the population, making it more scientific for selecting particles for mutation in each iteration.As one of the most widely used clustering algorithms, FCM classifies data through analyzing how closely a data is relative to different classes, making data samples with more similarity be classified into the same class. In this paper, we utilize IKFCM for cluster analysis before DE, and its classification result is considered as the basis of selecting particles for mutation. After a certain number of iterations, the population is divided into C subclasses by IKFCM, and there are more similarities within classes and greater differences between classes. When it comes to mutation, particlesXat, Xbt, and Xct will be selected from different classes, thus effectively expanding the diversity of mutant particle and ensuring that particles with larger differences will be participated in the population’s evolution and eventually improves the convergence performance of DE. The specific process of the DE based on fuzzy clustering, named IDDE, is presented in Figure 1.Figure 1
Flow chart of IDDE.


## 3. Compressed Sensing Signal Reconstruction Based on IDDE

### 3.1. Compressed Sensing Sparse Signal Reconstruction

In compressed sensing,ΨN×N is called sparse matrix if it can be used to linearly describe signal XN×1 sparsely. We can express it as(16)XN×1=ΨN×NsN×1where sN×1s1,⋯,sN denotes the linear description of XN×1 under ΨN×N and its sparsity satisfies K<<N. There exists a measurement matrix ΦM×N that allows XN×1 be described with a small amount of data as(17)yM×1=ΦM×NXN×1where yM×1 is the measurement vector and satisfies M<<N. From (6) and (7), we have(18)yM×1=AM×N=ΦM×NΨN×NAM×NsN×1=AsOnce AM×N satisfies RIP condition [12], the original signal can be reconstructed by solving the l0 norm; that is,(19)minsl0s.t.y=As=ΦΨsSince the process of solving (9) is a NP-hard, considering the signal with unknown sparsity as the differential evolution particle coding, we propose a compressive sensing signal reconstruction algorithm based on IDDE, which accurately reconstructed the unknown sparsity signal through population evolution.


### 3.2. Implementation of Compressed Sensing Signal Reconstruction Based on IDDE

DE is mainly used for continuous optimization, but for discrete optimization, it will generate large numbers of solutions that do not conform to the requirements, severely reducing its convergence efficiency. In this case, taking the CS reconstruction algorithm into account, the differential evolutionary particle coding method and evolutionary mechanism in IDDE are redefined.Definition 1 (particle coding).
In CS reconstruction algorithm optimization, define particle coding as(20)Xixi1,⋯,xiN←xij=1,ifsj≠00,elseIt is obvious that Xixi1,⋯,xiN is correspondence with the nonzero elements in the sparse signal sN×1s1,⋯,sN.Definition 2.
Randomly selectF′ (1≤F′≤N) code bits in particle Xj, and replace the corresponding code bits in particle Xi (i≠j) with it. The exchange process is denoted as F′Xi←Xj:(21)F′Xi←Xj=xi1←xj1,⋯,xjk←xjk︸F′Then, the mutation step in IDDE can be refreshed as(22)Vi,1t=F1′Xi←Xa,Vi,2t=F2′Xi←Xb,Vi,3t=F3′Xi←Xcwhere Xa, Xb, and Xc are three particles randomly selected from three different clusters, which are also different from the cluster that contain Xi.
As can be seen from (22), by performing crossover on the three mutant particles, respectively, we will obtain three trial particles Ui,1t, Ui,2t, and Ui,3t. Then, a particle with better fitness will be selected between the three trial particles and Xi as(23)Xit+1=Ui,jt,Ui,jt=minfUi,1t,Ui,2t,Ui,3tXit,elseDefinition 3 (objective function).
In CS reconstruction algorithm optimization, define the objective function as(24)minfXi=y-ΦΨXi2
As the objective function of CS reconstruction algorithm optimization is defined, IDDE would locate the nonzero elements of the sparse signal code after certain times of evolution and obtain the amplitude of the nonzero elements through least square method. Finally, the signal is precisely reconstructed. The performance of the CS reconstruction algorithm is superior due to its utilization of fuzzy clustering and improved discrete differential evolution algorithm. The pseudocode of the CS reconstruction algorithm based on IDDE is shown in Pseudocode2.Pseudocode 2
(1) Initialize parameters: maximum number of iterations T m a x, cluster number C and the stopping criterion. (2) Initialize the population of IDDE, and set t=0. (3) While (the requirement of IDDE is not satisfied) do  (4) While (the stopping criterion of IKFCM is not satisfied) do// cluster analysis the population  (5) Calculate H=hikC×P and O=oi according to (3).  (6) For i=1:P// update the particle (7) Randomly select 3 particles from different clusters which do not contain Xit. Perform mutation according to (22) to obtain Vi,1t, Vi,2t and Vi,3t. (8) Generate Ui,1t, Ui,2t and Ui,3t through crossover in the following way: U i t u i 1 t , ⋯ , u i N t ⇐ u i j t = v i j t r a n d b j ≤ C R   o r   j = r n b r i x i j t r a n d b j > C R   o r   j ≠ r n b r i (9) Evaluate the trial particle Uit If Ui,jt=minf()(Ui,1t,Ui,2t,Ui,3t), then Xit+1=Ui,jt Else Xit+1=Xit End if (10) End for (11) t+1→t  (12) Output results.


### 3.3. Application of IDDE in WSNs

In this part, we study the sparse event detection [13] in the context of wireless sensor networks (WSNs). Q wireless sensor nodes are placed within the monitoring scope of WSNs to monitor N event sources. K network events randomly occurred from the N event sources at some time. We use vector sN×1=s1,s2,⋯,sNT to denote the energy signal of the event sources (si=0 means that the ith event source did not happen any event). Obviously, if K≪N, sN×1 is a sparse signal with sparsity of K. Assuming Q=N, signals received by N nodes xN×1=x1,x2,⋯,xNT can be written as(25)x1x2⋮xN=h1,1d1,1-αh1,2d1,2-α⋯h1,Nd1,N-αh2,1d2,1-αh2,2d2,2-α⋯h2,Nd2,N-α⋮⋮⋱⋮hN,1dM,1-αhN,2dM,2-α⋯hN,NdM,N-αs1s2⋮sN=ΨN×Nswhere di,j is the distance the signal transmitted, hi,j is the energy attenuation model. According to CS theory, sparse event can be detected by the data received by M nodes.(26)yM×1=y1y2⋮yM=10⋯0⋯001⋯0⋯0⋮⋮⋱⋮00⋯100x1x2⋮xN=ΦM×NxN×1By (25) and (26), we have yM×1=ΦM×NxN×1=ΦM×NΨN×NsN×1=AM×NsN×1. It can be shown that when M≥OcK+1ln⁡N/K, A can meet the requirement of RIP. But the CS reconstruction algorithm based on IDDE requires that an accurate measurement matrix should be guaranteed. Thus we transform matrix AM×N in the following way:(27)A=UΣVTwhere ΣM×N is semipositive definite diagonal matrix, U, and V is orthogonal matrix. Therefore, (27) can be rewritten as(28)y=ΦM×NxN×1=As=UΣVTs=Uσ10⋯00σ2⋯0⋮⋮⋱⋮00⋯σM︷M×M0⋯00⋯0⋮00⋯0︷N-M×MVTsEquation (28) can be further transformed into(29)Σ1-1UTy=Σ1-1UTUΣ1︷M×M0︷N-M×MV1︷M×MV2︷N-M×Ms=V1Ts⇒y′=Σ1-1UTy=V1TsEquation (29) represents a new measurement system. As seen from the derivation process, the measurement matrix V1T is row orthogonal matrix; thus RIP condition is satisfied.In this case, sparse event detection in WSNs is transformed into the problem of usingM wireless sensor nodes to detect K event sources. The detailed steps include training parameters with the experimental data in the deployment test stage of WSNs to obtain the optimal parameter configuration; processing received signal by the use of reconstruction algorithm based on IDDE to obtain the sparse signal vector sN×1 in the detection stage to monitor sparse events effectively and timely.


## 3.1. Compressed Sensing Sparse Signal Reconstruction

In compressed sensing,ΨN×N is called sparse matrix if it can be used to linearly describe signal XN×1 sparsely. We can express it as(16)XN×1=ΨN×NsN×1where sN×1s1,⋯,sN denotes the linear description of XN×1 under ΨN×N and its sparsity satisfies K<<N. There exists a measurement matrix ΦM×N that allows XN×1 be described with a small amount of data as(17)yM×1=ΦM×NXN×1where yM×1 is the measurement vector and satisfies M<<N. From (6) and (7), we have(18)yM×1=AM×N=ΦM×NΨN×NAM×NsN×1=AsOnce AM×N satisfies RIP condition [12], the original signal can be reconstructed by solving the l0 norm; that is,(19)minsl0s.t.y=As=ΦΨsSince the process of solving (9) is a NP-hard, considering the signal with unknown sparsity as the differential evolution particle coding, we propose a compressive sensing signal reconstruction algorithm based on IDDE, which accurately reconstructed the unknown sparsity signal through population evolution.


## 3.2. Implementation of Compressed Sensing Signal Reconstruction Based on IDDE

DE is mainly used for continuous optimization, but for discrete optimization, it will generate large numbers of solutions that do not conform to the requirements, severely reducing its convergence efficiency. In this case, taking the CS reconstruction algorithm into account, the differential evolutionary particle coding method and evolutionary mechanism in IDDE are redefined.Definition 1 (particle coding).
In CS reconstruction algorithm optimization, define particle coding as(20)Xixi1,⋯,xiN←xij=1,ifsj≠00,elseIt is obvious that Xixi1,⋯,xiN is correspondence with the nonzero elements in the sparse signal sN×1s1,⋯,sN.Definition 2.
Randomly selectF′ (1≤F′≤N) code bits in particle Xj, and replace the corresponding code bits in particle Xi (i≠j) with it. The exchange process is denoted as F′Xi←Xj:(21)F′Xi←Xj=xi1←xj1,⋯,xjk←xjk︸F′Then, the mutation step in IDDE can be refreshed as(22)Vi,1t=F1′Xi←Xa,Vi,2t=F2′Xi←Xb,Vi,3t=F3′Xi←Xcwhere Xa, Xb, and Xc are three particles randomly selected from three different clusters, which are also different from the cluster that contain Xi.
As can be seen from (22), by performing crossover on the three mutant particles, respectively, we will obtain three trial particles Ui,1t, Ui,2t, and Ui,3t. Then, a particle with better fitness will be selected between the three trial particles and Xi as(23)Xit+1=Ui,jt,Ui,jt=minfUi,1t,Ui,2t,Ui,3tXit,elseDefinition 3 (objective function).
In CS reconstruction algorithm optimization, define the objective function as(24)minfXi=y-ΦΨXi2
As the objective function of CS reconstruction algorithm optimization is defined, IDDE would locate the nonzero elements of the sparse signal code after certain times of evolution and obtain the amplitude of the nonzero elements through least square method. Finally, the signal is precisely reconstructed. The performance of the CS reconstruction algorithm is superior due to its utilization of fuzzy clustering and improved discrete differential evolution algorithm. The pseudocode of the CS reconstruction algorithm based on IDDE is shown in Pseudocode2.Pseudocode 2
(1) Initialize parameters: maximum number of iterations T m a x, cluster number C and the stopping criterion. (2) Initialize the population of IDDE, and set t=0. (3) While (the requirement of IDDE is not satisfied) do  (4) While (the stopping criterion of IKFCM is not satisfied) do// cluster analysis the population  (5) Calculate H=hikC×P and O=oi according to (3).  (6) For i=1:P// update the particle (7) Randomly select 3 particles from different clusters which do not contain Xit. Perform mutation according to (22) to obtain Vi,1t, Vi,2t and Vi,3t. (8) Generate Ui,1t, Ui,2t and Ui,3t through crossover in the following way: U i t u i 1 t , ⋯ , u i N t ⇐ u i j t = v i j t r a n d b j ≤ C R   o r   j = r n b r i x i j t r a n d b j > C R   o r   j ≠ r n b r i (9) Evaluate the trial particle Uit If Ui,jt=minf()(Ui,1t,Ui,2t,Ui,3t), then Xit+1=Ui,jt Else Xit+1=Xit End if (10) End for (11) t+1→t  (12) Output results.


## 3.3. Application of IDDE in WSNs

In this part, we study the sparse event detection [13] in the context of wireless sensor networks (WSNs). Q wireless sensor nodes are placed within the monitoring scope of WSNs to monitor N event sources. K network events randomly occurred from the N event sources at some time. We use vector sN×1=s1,s2,⋯,sNT to denote the energy signal of the event sources (si=0 means that the ith event source did not happen any event). Obviously, if K≪N, sN×1 is a sparse signal with sparsity of K. Assuming Q=N, signals received by N nodes xN×1=x1,x2,⋯,xNT can be written as(25)x1x2⋮xN=h1,1d1,1-αh1,2d1,2-α⋯h1,Nd1,N-αh2,1d2,1-αh2,2d2,2-α⋯h2,Nd2,N-α⋮⋮⋱⋮hN,1dM,1-αhN,2dM,2-α⋯hN,NdM,N-αs1s2⋮sN=ΨN×Nswhere di,j is the distance the signal transmitted, hi,j is the energy attenuation model. According to CS theory, sparse event can be detected by the data received by M nodes.(26)yM×1=y1y2⋮yM=10⋯0⋯001⋯0⋯0⋮⋮⋱⋮00⋯100x1x2⋮xN=ΦM×NxN×1By (25) and (26), we have yM×1=ΦM×NxN×1=ΦM×NΨN×NsN×1=AM×NsN×1. It can be shown that when M≥OcK+1ln⁡N/K, A can meet the requirement of RIP. But the CS reconstruction algorithm based on IDDE requires that an accurate measurement matrix should be guaranteed. Thus we transform matrix AM×N in the following way:(27)A=UΣVTwhere ΣM×N is semipositive definite diagonal matrix, U, and V is orthogonal matrix. Therefore, (27) can be rewritten as(28)y=ΦM×NxN×1=As=UΣVTs=Uσ10⋯00σ2⋯0⋮⋮⋱⋮00⋯σM︷M×M0⋯00⋯0⋮00⋯0︷N-M×MVTsEquation (28) can be further transformed into(29)Σ1-1UTy=Σ1-1UTUΣ1︷M×M0︷N-M×MV1︷M×MV2︷N-M×Ms=V1Ts⇒y′=Σ1-1UTy=V1TsEquation (29) represents a new measurement system. As seen from the derivation process, the measurement matrix V1T is row orthogonal matrix; thus RIP condition is satisfied.In this case, sparse event detection in WSNs is transformed into the problem of usingM wireless sensor nodes to detect K event sources. The detailed steps include training parameters with the experimental data in the deployment test stage of WSNs to obtain the optimal parameter configuration; processing received signal by the use of reconstruction algorithm based on IDDE to obtain the sparse signal vector sN×1 in the detection stage to monitor sparse events effectively and timely.


## 4. Simulation

Simulations are performed in MATLAB to demonstrate the effectiveness of our algorithm. We deployQ=500 sensor nodes to monitor the temperature of N=120 places. The event source sequence corresponded to event energy signal sN×1=s1,s2,⋯,sNT. Reconstruction success rate RS, reconstruction time T, and reconstruction relative error RE are selected to evaluate the reconstruction performance. The reconstruction relative error RE is calculated as follows:(30)RE=∑i=1Nsi-si^∑i=1Nsi2×100%where sN×1s1,⋯,sN denotes the original signal and sN×1^s1^,⋯,sN^ stands for the reconstructed signal. The reconstruction success rate RS refers to the probability that RE is less than the threshold δ.


### 4.1. Reconstruction Performance

Selecting typical discrete signal as the original signal and the reconstruction performance of the reconstruction algorithm based on IDDE under the assumption thatK is unknown is analyzed. The performance of our algorithm is also compared to the blind sparsity reconstruction algorithm in [8], SWOMP in [2], and the classical StOMP. Run each algorithm independently for 50 times, calculate the average reconstruction success rate RS¯, the average reconstruction time T¯, and the average reconstruction relative error RE¯ for performance analysis, and set different δ for different signal. The reconstruction result of the CS reconstruction algorithm based on IDDE is shown in Figure 2. The evaluation index results of the 4 reconstruction algorithms are compared in Table 1.Table 1
Evaluation index comparisons of the four reconstruction algorithms.
Signal Index Algorithm This paper Literature[8] Literature[2] StOMP  Signal1 R S ¯ 100% 97.3% 50.2% 17.3% T ¯/s 0.17 0.38 0.28 0.37 R E ¯ 0.007 0.012 1.845 3.330  Signal2 R S ¯ 100% 98.2% 49.2% 15.3% T ¯/s 0.25 0.44 0.36 0.82 R E ¯ 0.014 0.018 1.038 2.143  Signal3 R S ¯ 100% 97.6% 55.7% 10.8% T ¯/s 0.56 0.92 0.66 1.27 R E ¯ 0.013 0.017 1.836 3.045Figure 2
Reconstruction result of the IDDE reconstruction algorithm.It can be seen from Figure2 that the CS reconstruction algorithm based on IDDE can obtain enough recovered data points from the compressed sensing data and reconstruct to the original signal, indicating that the algorithm we proposed in this paper is capable of reconstructing signal with unknown sparsity. In Table 1, the reconstruction success rates of the algorithm we propose reached 100% for different original signals, the algorithm in [8] reached above 97%, and the algorithm in [2] was only about 50% and StOMP could hardly reconstruct the original signal. In terms of reconstruction time, our algorithm is significantly faster than the other 3 algorithms, with T¯ reduced by 15.1-31.3%. As for reconstruction error, compared with the algorithm in [2], which has relatively better reconstruction success rate, the RE of our algorithm decreased by about 36.4-51.9%. In summary, compared with previous reconstruction algorithms such as StOMP, the CS reconstruction algorithm based on IDDE proposed in this paper performs better, much more suitable for reconstructing signal with unknown sparsity. All these advantages on one hand could be accredited to the utilization of IDDE. Through IDDE, the signal sparsity is transformed into particle coding, which makes the differential evolution algorithm be able to find the global optimum solution while obtaining the location of nonzero elements. On the other hand, fuzzy clustering is used to analyze the population, making the learning target of the population evolution more rational and scientific, which ultimately improves the reconstruction performance of our algorithm.


### 4.2. Effects of Parameters on the Reconstruction Algorithm Performance

SparsityK and observation time M are critical to the reconstruction accuracy. Simulations were carried out to examine the reconstruction success rate of the CS reconstruction algorithm based on IDDE under different K and M, respectively, the blind sparsity reconstruction algorithm in [8], SWOMP in [2], and StOMP are also simulated as a comparison. Each algorithm runs 50 times. Comparison results are shown in Figures 3 and 4.Figure 3
SparsityK versus reconstruction success rate (M=100).Figure 4
Observation timeM versus reconstruction success rate (K=20).Figure3 shows that, when the signal length and M are fixed, all the four reconstruction success rate curves decrease with the increase of K. Compared with the other 3 algorithms, our algorithm maintains a reconstruction success rate of over 94% when K is within the range of (25, 35), while that of the other 3 algorithms decrease significantly.As shown in Figure4, when the signal length and K are unchanged, all the 4 curves rise with the increase of M, and the RS¯ of the algorithm we proposed is much better than the other 3 algorithms with the same M. Especially when M=80, the RS¯ of our algorithm can reach 100%.However, large number of sensor nodes means large network energy consumption, which is unfavorable to prolong the survival time of WSNs. Thus, in the following part, we analyze the robustness and antinoise performance of our algorithm.


### 4.3. Antinoise Performance

Add white noise into the discrete signal to be detected and select the reconstruction algorithm in [8] and StOMP as a comparison. We investigate their antinoise performances under SNR ranging from 20dB to 45dB.From Figure5, we can see that if the noise is not very serious, the reconstruction success rates of the three algorithms change a little as the noise level changes. When the noise is at a high level, the reconstruction success rates change significantly with the noise level. The RS¯ of the algorithm we propose will still remain around 93% if the SNR decrease to 15dB while the other two algorithms decrease obviously, indicating that our algorithm is good at resisting noise.Figure 5
SNR versus reconstruction success rate (K=30, M=100, N=120).


## 4.1. Reconstruction Performance

Selecting typical discrete signal as the original signal and the reconstruction performance of the reconstruction algorithm based on IDDE under the assumption thatK is unknown is analyzed. The performance of our algorithm is also compared to the blind sparsity reconstruction algorithm in [8], SWOMP in [2], and the classical StOMP. Run each algorithm independently for 50 times, calculate the average reconstruction success rate RS¯, the average reconstruction time T¯, and the average reconstruction relative error RE¯ for performance analysis, and set different δ for different signal. The reconstruction result of the CS reconstruction algorithm based on IDDE is shown in Figure 2. The evaluation index results of the 4 reconstruction algorithms are compared in Table 1.Table 1
Evaluation index comparisons of the four reconstruction algorithms.
Signal Index Algorithm This paper Literature[8] Literature[2] StOMP  Signal1 R S ¯ 100% 97.3% 50.2% 17.3% T ¯/s 0.17 0.38 0.28 0.37 R E ¯ 0.007 0.012 1.845 3.330  Signal2 R S ¯ 100% 98.2% 49.2% 15.3% T ¯/s 0.25 0.44 0.36 0.82 R E ¯ 0.014 0.018 1.038 2.143  Signal3 R S ¯ 100% 97.6% 55.7% 10.8% T ¯/s 0.56 0.92 0.66 1.27 R E ¯ 0.013 0.017 1.836 3.045Figure 2
Reconstruction result of the IDDE reconstruction algorithm.It can be seen from Figure2 that the CS reconstruction algorithm based on IDDE can obtain enough recovered data points from the compressed sensing data and reconstruct to the original signal, indicating that the algorithm we proposed in this paper is capable of reconstructing signal with unknown sparsity. In Table 1, the reconstruction success rates of the algorithm we propose reached 100% for different original signals, the algorithm in [8] reached above 97%, and the algorithm in [2] was only about 50% and StOMP could hardly reconstruct the original signal. In terms of reconstruction time, our algorithm is significantly faster than the other 3 algorithms, with T¯ reduced by 15.1-31.3%. As for reconstruction error, compared with the algorithm in [2], which has relatively better reconstruction success rate, the RE of our algorithm decreased by about 36.4-51.9%. In summary, compared with previous reconstruction algorithms such as StOMP, the CS reconstruction algorithm based on IDDE proposed in this paper performs better, much more suitable for reconstructing signal with unknown sparsity. All these advantages on one hand could be accredited to the utilization of IDDE. Through IDDE, the signal sparsity is transformed into particle coding, which makes the differential evolution algorithm be able to find the global optimum solution while obtaining the location of nonzero elements. On the other hand, fuzzy clustering is used to analyze the population, making the learning target of the population evolution more rational and scientific, which ultimately improves the reconstruction performance of our algorithm.


## 4.2. Effects of Parameters on the Reconstruction Algorithm Performance

SparsityK and observation time M are critical to the reconstruction accuracy. Simulations were carried out to examine the reconstruction success rate of the CS reconstruction algorithm based on IDDE under different K and M, respectively, the blind sparsity reconstruction algorithm in [8], SWOMP in [2], and StOMP are also simulated as a comparison. Each algorithm runs 50 times. Comparison results are shown in Figures 3 and 4.Figure 3
SparsityK versus reconstruction success rate (M=100).Figure 4
Observation timeM versus reconstruction success rate (K=20).Figure3 shows that, when the signal length and M are fixed, all the four reconstruction success rate curves decrease with the increase of K. Compared with the other 3 algorithms, our algorithm maintains a reconstruction success rate of over 94% when K is within the range of (25, 35), while that of the other 3 algorithms decrease significantly.As shown in Figure4, when the signal length and K are unchanged, all the 4 curves rise with the increase of M, and the RS¯ of the algorithm we proposed is much better than the other 3 algorithms with the same M. Especially when M=80, the RS¯ of our algorithm can reach 100%.However, large number of sensor nodes means large network energy consumption, which is unfavorable to prolong the survival time of WSNs. Thus, in the following part, we analyze the robustness and antinoise performance of our algorithm.


## 4.3. Antinoise Performance

Add white noise into the discrete signal to be detected and select the reconstruction algorithm in [8] and StOMP as a comparison. We investigate their antinoise performances under SNR ranging from 20dB to 45dB.From Figure5, we can see that if the noise is not very serious, the reconstruction success rates of the three algorithms change a little as the noise level changes. When the noise is at a high level, the reconstruction success rates change significantly with the noise level. The RS¯ of the algorithm we propose will still remain around 93% if the SNR decrease to 15dB while the other two algorithms decrease obviously, indicating that our algorithm is good at resisting noise.Figure 5
SNR versus reconstruction success rate (K=30, M=100, N=120).


## 5. Conclusions

In this paper, we propose a compressed sensing signal reconstruction algorithm based on IDDE. The algorithm employs intelligent optimization and fuzzy clustering together, transforming signal reconstruction into the global optimization of differential algorithm, to reconstruct signal with unknown sparsity through fuzzy cluster analysis, particle coding, and differential evolution. Its application in WSNs sparse event detection is also discussed. Simulation results testify that the algorithm we propose performs excellent in signal reconstruction and is robust to noise and interference.



---

*Source: 7039510-2019-06-16.xml*