A Multi-hop Routing Algorithm for WSNs based on Compressive Sensing and Multiple Objective Genetic Algorithm

1. Introduction

ENERGY -efficiency is a decisive issue in the wireless sensor networks (WSNs) because the network consists of miniature, cheap, and battery-operated nodes, which are deployed in a harsh environment, where it is difficult to access and recharge them. These nodes are capable of sensing different physical quantities, manipulating data concisely, and communicating with each other nodes over unreliable wireless links. The sensed data is collected and further processed by a Base Station (BS), with wired-power source and higher processing capabilities [1].

Most of the node energies are consumed by communication, so, the researchers developed many techniques to improve the energy efficiency of WSNs. The proposed methods cover different aspects of communication process such as routing, mobile relays, and sinks, optimal deployment, sleep-wake scheduling, opportunistic transmission, data reduction, etc.[2], [3]. Many data reduction schemes are used to improve energy-efficiency, reliability, and memory usage of WSNs; they are categorized to network-based and compression based methods. Networkbased methods include routing algorithms and network coding algorithms, where compression-based algorithms include transform-based, conventional compression, distributed source coding, predictive coding, and compressive sensing [4], [5]. In the traditional Shannon/Nyquist sampling theorem in order to recover the signal correctly, the sampling rate should be higher than twice of the highest frequency of the original signal, which generates a vast amount of data. Thus, data must be compressed to reduce the cost of storage and transmission. In 2006; Donoho, Romberg, Candès, and Tao introduced Compressive Sensing [6- 9], by CS signals can be recovered from fewer samples or measurement under two conditions, the sparsity of the signal (the signal has very few significant coefficients, and the majority are zeros), and the Incoherency among the samples [10]. Recently, diverse researches use CS to reduce the amount of data transmitted to the (BS), which improves the energy-efficiency of WSN. CS needs more computational power to reconstruct the signals, but the BSs with their high processing-capabilities and energy can recover sensed signals.

If N is the length of the sparse vector represents the sensed data, and Mis the number of samples (measurements), the BS can recover the sparse signal [TeX:] $$x \in R^{N}$$ , despite having only k significant coefficients from the observed vector [TeX:] $$y \in R^{M}, M<<N,$$ by solving the linear set [TeX:] $$\mathbf{y}=\Phi x,$$ where [TeX:] $$\Phi \in R^{M * N}$$ is the so-called sensing matrix. Hence, The node performs CS, transmits vector y and the BS receives it. The energy utilized in the transmission of y is a function of its length denoted byM. AsM increases more energy is spent, thus we need to reduce the number M to improve the energy efficiency. Unfortunately, the reconstruction error increases as M decreases (for details see the next section) which require us to strike the right balance between energy-efficiency and reconstructionerror.

In this paper, we propose a CS-based chain routing algorithm, WSN is divided intoM paths, and the energy-efficiency and the reconstruction-error are functions of the number of paths, which represent the number the of the measurements. The energy efficiency and the number of paths also depend on the transmission ranges of the nodes (R). While the reconstruction-error also depends on the quality of the sensing matrix and the number of paths. To find the optimal number of measurements [TeX:] $$\left(M_{\text {opt }}\right),,$$ the optimal transmission range of the nodes [TeX:] $$\left(R_{\text {opt }}\right),$$ and the optimal sensing matrix [TeX:] $$\left(\Phi_{\text {opt }}\right)$$ in terms of mutual coherence, that maxi- mize the energy-efficiency and minimizes the reconstruction error, we use multiple objective genetic algorithms (MOGA).

The contributions of this work are detailed as follows: First, we proposed a multiple objective genetic algorithm to strike the right balance between the energy efficiency and reconstruction error of the compressive sensing method. Second, we introduce a genetic algorithm to improve the characteristics of the sensing matrix by reducing its mutual coherence. Third, we presented a greedy algorithm to split the WSN into multiple paths in a way conserves the balance of the payload, it consists of two subalgorithms, the first defines the leaf nodes of paths, the second build the paths starting from the leaf nodes

The remainder of the paper is organized as follows:

In Section 2, we provide an overview of related work in the literature.

In Section 3, we depict the compressive sensing and Multiobjectives genetic algorithm (MOGA) concisely.

In Section 4, we analyse the objectives and the variables of the MOGA.

In section 5, proposed CCS_MOGA algorithm is described.

In Section 6, we give the numerical results of a detailed performance of the algorithm under different scenarios.

In section 7, we state some conclusions and give some commentary on the future.

II. RELATED WORKS

In WSN, the nodes are typically battery operated. Therefore, energy is considered to be a limited resource, and energy efficiency is a crucial factor in designing and operating of WSN. In Multi-hop routing, the source node uses other nodes as relay nodes in conveying the data packets to a distention node outside its transmission range. Thus, multi-hop routing extends the communication coverage of the nodes and also improves the energy efficiency of the nodes requiring only relatively short distance transmissions [11].

Many researchers used the multi-hop techniques to develop routing protocols for WSN aiming to strike a good balance among different QoS requirements, such as energy efficiency, delay, and reliability. The authors of [12] proposed a multi-hop routing protocol that improves energy efficiency by reducing the excessive overhead, but it is not suitable for large scale WSNs. The researchers in [13] presented balanced and energy efficient multi-hop (BEEMH) based on the Dijkstra algorithm. They suggested the residual energy and location as criteria for the selection cluster heads. It improves the performance in terms of the energy efficiency but it has poor performance in terms of reliability. In [14], the authors used Taylor series and cat salp swarm algorithm (Taylor C-SSA) to develop a multi-hop routing protocol that improves the performance in terms of energy efficiency and security. We proposed in [15] maximum of minimum residual energy protocol (MMREP), where the packet is sent to the BS over the path of which the minimum remaining energy is maximum subject to a predefined reliability constraint. Also, we presented optimal residual energy based protocol (OREBP), where the entropy is used to guarantee that the distribution of the residual energy will remain as close to uniform as possible, but the complexity of algorithm increases as the size of the WSN increases.

Besides multi-hop routing, various data reduction schemes are used to enhance the performance metrics of WSNs. E.g. network coding (NC) is an example of a network-based data reduction technique, researches such as [16]–[20] use network coding to maximize the life and the reliability of WSNs. They use combined packets as redundant data to improve the E2E error rate.

Compressive sensing is an example of compression-based data reduction techniques. Recently, several algorithms were developed to host CS into WSNs, some of them aim to reduce the payload and the energy dissipated in data collection by shrinking the amount of transmitted data. Some researchers present algorithms to improve the reconstructions error, others aim to reduce the complexity of the algorithms or to improve the security of WSNs [21]. In the literature, there are two schemes of CS, plain-CS (all the nodes perform CS) and hybrid-CS (specific nodes perform CS).

The authors of [22] suppose hybrid-CS for chain based WSNs, some nodes forward native packets (Forwarders), others perform CS (Aggregators). Nodes have less than K descendants are forwarders, the nodes have aggregator descendants, or more than K-1 descendants are considered as an aggregator where K is the length of the compressed vector (number of measurements). The method discussed in [23] is also a hybrid-CS algorithm, which is based on mobile agents. There are M agents, where M is the number of measurements, in the paper the authors developed a greedy algorithm to determine the path of the mobile agent. The mobile agent collects the reading of interest nodes; they are the nodes corresponding to the non-zero elements of the row of the measurement matrix agreeing with the ID of the mobile agents. The measurement matrix is a sparse random binary matrix. When all the agents return to the BS, it uses compressive sensing reconstruction algorithms to get the readings of nodes. Unfortunately, the sensing matrix is random, and it may happen that some nodes remain unvisited.

Random walk (RW) routing is used in [24],M random walks are initiated, where M is the number of measurements, in each round, the readings of k random nodes are collected. The authors use the mixing time of the graph to determine k, the number of nodes to be visited by RW, the [TeX:] $$k^{t h}$$ node collects the spare measurement of round [TeX:] $$M_{i},$$ then it applies [TeX:] $$\Phi_{i}$$ of the sensing matrix to produce [TeX:] $$\mathbf{y}_{i}, i=1,2, \cdots, M.$$ The measurement vector y is sent directly to the BS, which collects the M measurement vectors needed for recovery process.

The algorithm proposed in [25] is a plain-CS for chain based WSNs; all the nodes are connected like a chain. Each node creates its sensing vector based on a global seed broadcasted by the sink. The nodes forward the summed compressed vector from one to another until the head of the chain, which sends the received vector directly to the sink. Energy-efficient compressive sensing-based clustering routing protocol (EECSR) is a plain- CS algorithm [26]; it is a cluster-based scheme. The authors suppose a sector-shaped network, divided into k layers; all of them have the same width. They calculate the optimal number of the clusters for each layer, the optimal size of the clusters, and the optimal location of the cluster heads (CHs) in terms of energy efficiency. All the calculations depend on the geometrical specification of the network and the number of measurements. Members of the clusters transmit compressed to the CHs. HCs collect the compressed data and forward it to BS.

The above mentioned algorithms are based on random measurement matrices; nevertheless, the authors of [27] propose cluster size load balancing for CS algorithm (CSLB-CS); it is a cluster-based algorithm. Besides using a cluster load balancing technique to reduce the total number of transmissions, they use Chicken Swarm Optimization Algorithm to improve the accuracy and robustness of the reconstruction process.

Some works combine more than one data reduction technique; for example, [28] proposes a compression scheme that combines CS, NC, and spatial-temporal compression. It supposes a clustered topology; the authors formulate an optimization model to minimize the reconstruction error; they presume that the reconstruction error is a function of the total flow rate and link transmission rate. The overall flow rate is measured as the number of received measurements; a predefined reliability probability is considered as an optimization parameter.

Some researches concentrate on improving the energy efficiency [20]–[23], others concentrate on improving reconstruction error [27], [28], [34]. In this work, we balance among payload, energy-efficiency, and accuracy of the reconstruction process by minimizing reconstruction error.

III. THE SYSTEM MODEL

A. A Brief Summary of Compressive Sensing

The fundamental idea of CS is that certain signals can be recovered correctly from fewer samples or measurement than classical methods; the possibility of this idea depends on two principles:

1. Sparsity: The signal has only very few significant coefficients, and the majority of the coefficients are zeros.

2. Incoherency: The coherency between two signals decreases as the linearity between them decreases

If is a dense vector represents the original signal, then it can be expanded into an orthonormal basis [TeX:] $$\Psi$$ (such as wavelet basis, Fourier basis, DCT, etc.) to acquire a sparse vector x as follows:

x as a sparse vector with length N and with k significant element is sampled into vector y which has the sampled values of x as follows:

where [TeX:] $$\Phi$$ is the sensing matrix (Measurement matrix) and M is the number of measurements (samples) and [TeX:] $$N>>M.$$

Since [TeX:] $$N>>M,$$ There are infinitely many possible solutions, each solution represents a possible signal reconstruction, if the RIP holds, [TeX:] $$l_{0}$$- -norm and [TeX:] $$l_{1}$$- norm can be used to reconstruct the signal if [TeX:] $$\hat{x}$$ is the reconstructed vector:

Reconstruction by [TeX:] $$l_{0}-$$ norm is accurate, but it is slow because it is an NP-complete algorithm, where [TeX:] $$l_{1^{-}}$$ -norm is correct, efficient, and linear programming problem [29].

B. Multi-Objectives Genetic Algorithm

To optimize the parameters, we will use multiple objective genetic agorithms (MOGAs). MOGA is a nature-inspired metaheuristic algorithm which is widely used in WSNs to achieve the optimum of multiple contradictory objectives [30,31]. These objectives are adjusted simultaneously subject to a set of restrictions. In case multi-objective optimization there is not a specific definition of the optimal solution, so, instead of a single solution yielded by traditional genetic algorithm (GA), MOGA finds a set of multiple non-dominated solutions, all of them are accepted, the best solution is subjective based on the needs of the designer [32].

MOGA uses a vector of fitness functions [TeX:] $$\mathbf{F}(x)=\left[f_{1}(x), f_{2}(x), \cdots, f_{n}(x)\right]^{T}$$ to find a vector of decision variables which satisfy a set of inequality and equality constraints, these constraints define the viable domain contains all the acceptable solutions.

MOGA is based on Pareto-Optimality; it uses the fitness functions vector to find Pareto-optimal solutions. As shown in Fig. 1, Pareto-optimal solutions are the vector [TeX:] $$\mathbf{X}=\left[x_{1}, x_{2}, \cdots, x_{n}\right]^{T}$$ that contains all the feasible solutions that minimize at least one objective without causing a simultaneous increase in any of the other objectives. Pareto-optimal set or Pareto-front [TeX:] $$\hat{\mathbf{X}}=\left[\hat{x}_{1}, \hat{x}_{2}, \cdots, \hat{x}_{n}\right]^{T}$$ is the vector of solutions that are not dominated by any other solution in solution space, [TeX:] $$\hat{\mathbf{X}}$$ is not dominated by X if and only if [32]:

and

C. Network Model

We model the network as a graph G(V,E,d), where V is the vertices that represent the nodes, e is the set of edges that connect the vertices, and [TeX:] $$d_{i j},(i, j=1, \cdots, N)$$ is the Euclidian distance between node i and j. There is a connection between node i and node j if [TeX:] $$d_{i j}$$ is less than the transmission range of the nodes; [TeX:] $$e=\left\{(i, j) \mid \forall i, j \in V, d_{i j} \leq R\right\}.$$ The nodes use each other as relays to forward the packets to the BS in multi-hop transmission manner. We assume the N nodes are randomly deployed onto a square sensing field with an edge of D, agreeing to a 2D normal distribution; the BS is allocated in the center of the sensing field.

We deal with two types of rounds (as they are introduced in [33]: Transmission rounds and construction rounds, which is used in dynamic topology WSN, re-construction round appears in case of mobile sink, mobile nodes, or in case of energy holes problem.

In our proposed model, transmission rounds appear deterministically when nodes have to collect data. Construction rounds appear in the initialization stage, and when a predefined percentage of the nodes die, transmission rounds appear deterministically when nodes have to collect data. At the beginning of each construction round, the BS uses the multi-objective genetic algorithm to calculate the optimal number of the measurement [TeX:] $$M_{o p t} ;$$ the optimal transmission range [TeX:] $$R_{o p t},$$ and the optimal sensing matrix [TeX:] $$\Phi_{o p t} \in R^{M * N}.$$ BS constructs [TeX:] $$M_{o p t}$$ paths using the algorithms in the next section, and broadcasts [TeX:] $$\Phi_{\text {opt }}$$ over the network. Each node has a copy of the row number m of [TeX:] $$\Phi_{\text {opt }}\left(\phi_{m}\right).$$

IV. OPTIMIZATION METHODS

We developed a multi-objective genetic algorithm that seeks the optimal Number of measurements, the optimal transmission range, and the optimal measurement matrix. The goal is minimizing the consumed energy as well as the reconstruction error.

A. Energy Efficiency

In WSN, consumed energy is proportional to [TeX:] $$d^{\alpha}$$ where d is the transmission distance, and is the path-loss exponent. Statistically, if R is the transmission range of the nodes, then the mean square of communication distances [TeX:] $$E\left[r^{2}\right]=R^{2} / 2$$ [24]. For M paths with [TeX:] $$n_{c}$$ is the average path length, the consumed energy of nodes in the path is:

If the average distance between the M path leaders and the BS is[TeX:] $$d_{a v}$$; then the total energy consumed by the path leaders to transmit a unit of compressed data is:

so, if the sensing field is a square with an edge of length D and the BS is allocated in the centre, the average distance between the chain leaders and the base [24]:

where f(x,y) is the joint probability function (pdf), which is equal to [TeX:] $$1 / D^{2}.$$

The total energy consumed by the nodes in the path and the path leaders is [TeX:] $$E=E_{c h}+E_{L B S}$$ from (10)–(12), the consumed energy in the network is:

Equation (10) shows that as M increases, the consumed energy increases.

B. Reconstruction Error

CS paradigm has three types of reconstruction errors, original dense data error[TeX:] $$\left(e_{\theta}\right),$$ sparse data error [TeX:] $$\left(e_{x}\right),$$ and observed data error [TeX:] $$\left(e_{y}\right) .$$ They are defined as follows [34]:

stations

where , x, and 4 are the sensed vectors, and [TeX:] $$\hat{\theta}, \hat{x}, \text { and } \hat{y}$$ are the reconstructed vectors. Authors of [34] prove that the three errors are harmonious, and minimizing one minimizes the others.

In this study, we minimize [TeX:] $$\left(e_{y}\right),$$ in the same manner as (2), [TeX:] $$\hat{y}=\Phi \hat{x}, \text { from }(1), \hat{x}=\Psi \hat{\theta}, \text { if } \Omega=\Phi \Psi,$$ then (13) becomes:

(14) Shows that asM increase [TeX:] $$e_{y}$$ decreases, the fact that contradicts the statement of (10).

C. Transmission Range

To guarantee graph connectivity [35], transmission range R should satisfy [TeX:] $$R=\sqrt{A(\log N+\epsilon \log n) / \pi N}$$ where A is the area of sensing field, n is the number of nodes, and [TeX:] $$\epsilon$$ is a constant depends on structural properties of the graph. The transmission range R and required transmission power P are exponentially proportional [35],

where R is the transmission range, k size of data unit in the bet, and C is a constant depends on antenna gain, wavelength, and transmission rate and noise level. Using small transmission ranges improves energy efficiency, but more paths are needed to guarantee connectivity, which means a larger M.

Each sensor node standard supports several levels of transmission levels. For example, MICA2 has 26 transmission power levels from 0.01 mW (corresponds to 28 m transmission range) to 3.1623 mW (corresponds to 118.1.3 m transmission range) [36].

Each node uses two transmission ranges:

[TeX:] $$R_{c}$$ : It is a narrow range; the nodes use this range to communicate with its neighbors of the same path; it is small because it covers just the average distance between two nodes. We have to ensure that the degree of each node [TeX:] $$\geq 2,$$ one for receiving, and the other for transmission.

[TeX:] $$R_{B S}:$$ It is broader than [TeX:] $$R_{c}$$; the path leader nodes use this range to send the compressed data to the BS directly.

D. Sensing Matrix

To reconstruct x correctly from y, [TeX:] $$\Phi$$ should obey these two conditions:

[TeX:] $$(\mu)$$ between [TeX:] $$\Psi \text { and } \Phi$$ should be as minimum as possible where:

The upper bound of [TeX:] $$\mu$$ is one, where the lower bound is a function of M and N :[TeX:] $$\sqrt{\frac{N-M}{M(N-1)}}$$

It satisfies the restricted isometry property (RIP) of order K, which is achieved if the restricted isometry constant [TeX:] $$(R I C) \delta_{k}$$ is not close to one, where:

Both properties are related to each other

As [TeX:] $$\mu$$ decreases,[TeX:] $$\delta_{k}$$ decreases, small [TeX:] $$\delta_{k}$$ means a higher probability that the sensing matrix satisfies the RIP. The probability of successful data construction depends on the number of measurements M.M is determined based on [TeX:] $$\delta_{k} \text { and } \mu$$ [29]:

This equation indicates that:

As the coherence decreases, fewer measurements are needed

As the sparsity increases K decreases, fewer measurements are needed

Smaller [TeX:] $$\delta$$ means a higher number of measurements is needed. Fortunately, it is an N-complete problem; however, fortunately, any random matrix drawn from Gaussian, +1/-1, Bernoulli distributions, has a high probability of possessing these properties.

V. CCS-MOGA

In this section, we elaborate on the simulation results of the path based CS algorithm, optimized by MOGA (CCS-MOGA); it consists of three stages; (i) seeking [TeX:] $$M_{o p t}, R_{o p t}, \text { and } \Phi_{o p t} ;(\mathrm{ii}):$$ Construction the network based on optimal values of the MOGA variables; (iii) the accomplishment of CS. The aim is to improve the clashed objectives energy-efficiency and reconstruction error simultaneously.

A. Seeking [TeX:] $$M_{o p t}, R_{o p t}, \text { and } \Phi_{o p t}$$

The objective functions of MOGA are shown in (10) and (13), subject to the constraints shown in (16), (18) and the specification of MICA2 mentioned in Section 6.3. The output of the multiple-objective genetic algorithm is an optimal measuring matrix with minimum mutual coherency and a Pareto front as shown in the Fig. 1. The figure shows that as the energy increases the reconstruction error decreases and vice versa. Table 1 shows these optimal values of the energy and the reconstruction error, it also shows the corresponding values of M and R

The optimal point of Pareto front is the knee point of the curve in Fig. 2, but the user can use another point up to his/her concerns, in the direction of energy efficiency or accuracy.

In first stage, Besides [TeX:] $$M_{o p t}, R_{o p t},$$ the algorithm optimizes the sensing matrix by minimizing [TeX:] $$\mu ;$$ it starts with a random pattern follows i.i.d. Gaussian distribution, then it is improved until the value of the fitness function for the best point in the current population is less than or equal to fitness limit. We define the fitness limit as the lower boundary of the [TeX:] $$\mu.$$

B. 5.2 Network Construction

Based on calculated M the WSN is divided into M paths, to guarantee maximum coverage and minimum isolated node, M leaf nodes (cl) should satisfy:

Where dis (m, i) is the distance between leaf node m and node i, which means that the leaf nodes are the farthest nodes from the BS and the farthest from each other.

M paths are constructed; as shown in algorithm (2), each of them starts with a leaf node as a header, then in turn, each leaf node select the closest node to be a member of it’s path, the new members be the new header, and so on. But the arrangement of the nodes in the path is not optimal, the shortest path is [TeX:] $$\text { spath }_{i}=\left\{c l_{i}, c l_{i}+1, \ldots, B S\right\}$$ where:

Algorithm 3 is used to optimize the arrangement of the nodes to achieve the shortest paths as shown in Fig. 4.

C. 5.3 Compressive Sensing

At the beginning of a transmission round, each path selects a path leader based on the ratio of residual energy and distance from the sink. Each node receives the data from the preceding node and add it to its data, and pass the summation to the next node in the path, [TeX:] $$x_{i}=\sum_{i=1,2, \cdots, n_{c}} x_{i}, i=\left\{1,2, \cdots, n_{c}\right\},$$ and [TeX:] $$n_{c}$$ is the length of the path.

CL arranges the received data into [TeX:] $$\mathbf{X}_{m} \in R^{1 * N};$$ it includes the readings of each node into its corresponding element of [TeX:] $$\mathbf{X}_{m},\mathbf{X}_{m}$$ is a sparse vector, all its elements are zeros, just the elements corresponding to members of path m, The sparsity level K is determined by the number of measurements, fewer number of measurements mean longer paths and lower level of sparsity. CL calculates [TeX:] $$y_{m}=\phi_{m} \boldsymbol{X} m, m=\left\{1,2, \cdots, M_{o p t}\right\}$$ and transmits it directly to the BS. BS concatenates [TeX:] $$y_{m}, m= \left\{1,2, \cdots, M_{o p t}\right\} \text { to obtain } \mathbf{Y} \in R^{1 * M}$$ which reconstructed to recover [TeX:] $$\mathbf{X}, \boldsymbol{X}=\bigcup_{m=1}^{M} X_{m}.$$

VI. SIMULATION AND NUMERICAL RESULTS

We used MATLAB R2018 to simulate the algorithm. We compared the non-compression, proposed plain compression and some other plain compression algorithms with each other. Also we evaluated the impact of optimization on the system performance with respect to energy efficiency and accuracy of construction.

We assumed different numbers of sensors ( 25-500 nodes ) deployed in a grid of 100x100 m, the nodes are deployed according to a 2D normal distribution. We presume MICA2, where ETx is 3.12 [TeX:] $$\mu \mathrm{J} / \mathrm{bit}$$ and ERx is 2.34 [TeX:] $$\mu \mathrm{J} / \mathrm{bit}$$ [36] , the energy spent by the electronics is neglected and is 2.5 for both short and long transmissions.

In the first experiment, we explored the impact of the optimization of sensing matrix, Fig. 6 shows the mutual coherency [TeX:] $$\mu$$ for both random and optimized matrices for different sizes ofM, it shows that the optimized sensing matrix always has lower [TeX:] $$\mu,$$ which means lower probability of reconstruction error as shown illuminated by (16)–(18).

Fig. 7 emphasizes that the optimization of sensing matrix in terms of mutual coherency affords mostly lower reconstruction error regardless of the number of measurements. In some rare case, random matrix may show low coherence, by the nature of randomness, but we still need a systematic optimization and our systems should not be controlled by coincidences. In the second experiment, we investigated the relations among objectives and variables of optimization system; Fig. 8 shows the reconstruction error, Fig. 9 shows the average consumed energy per a round of data collection, we simulates WSNs with different number of sensors. The figures compare the minimum, the optimal and the maximum values of these two objectives as reported by the Pareto front of the optimization system, the optimal values always found in between minimum and maximum values. We also noted an uneven relation between the number of nodes and the average energy. This occurs because we suppose random distribution of nodes for each case, but in general, there is an increasing tendency of average energy as the number of nodes increases, and the reconstruction error drops as the number of nodes increases. We assume a WSN containing 500 nodes for the third experiment. The nodes are deployed in a grid of 100x100 m agreeing to a 2D normal distribution. Fig. 10 shows the relations between the number of measurements as an optimization variable on one side, and the objectives of the optimization from the other side. The left y-axis shows the energy as an objective, where the right

y-axis shows the reconstruction error as the second objective. The result coincides the theoretical depiction mentioned above; as the number of measurements increases more energy is consumed, but less error probability transpires. The crossing point between the two curves matches the knee point of the Pareto front shown in Fig. 2.

Fig. 11 shows the relations among the objectives and the transmission range as a variable. Lower transmission range improves the energy efficiency, exactly as (4) tells, but it increases the reconstruction error because, with low transmission range,

less paths are needed to guarantee the connectivity of the WSN, which means fewer number of measurements and longer paths that means lower level of sparsity as explained in Section 5.3.

In the last experiments, we explore the energy efficiency of CCS-MOGA as a compressive sensing algorithm. We compare it with two other scenarios:

the first is the Non-CS algorithm, which represents the traditional multiple path PEGASIS algorithm, where each node fuse the received packet into its packets, then it forwards the fused packets to the closest neighbor, when it arrives at CL, it aggregates the packets together in a predefined packet length (we assume it 100), then sends them directly to the BS without any type of compression [37].

the second scenario, we suppose a T-CS algorithm, it is accomplished in many researches such as [24], [25], each CL compresses its data using its own measurements matrix and then sends the samples vector with length of M to the BS.

Fig. 12 shows the energy efficiency characterized by the average of consumed energy per node after 1000 of transmission rounds. We assume WSNs with different numbers of nodes (50- 500) in the same sensing field of previous experiments. The figure shows much lower energy consumption of CCS-MOGA, it is a reasonable result, because each CL sends just one element of vector y as shown in Fig. 5, where in case of non-CS, each CL sends a vector of 100 element. We note that the average of consumed energy per node in case of T-CS changes linearly with the size of the network, because the length of vector sent by CL depends onM, asM increases the length of the vector increases and the spent energy increases too.

Energy efficiency is not only measured by reducing the amount of consumed energy, The distribution of the consumed energy is also vital. A uniform distribution of consumed energy among the nodes means the lack of bottleneck nodes and deficiency of overloaded nodes, which may prolong the life span of WSN [15]. Fig. 13 shows the variance of the consumed energy of the nodes. Low variance means more uniformity of distribution of consumed energy. WSNs use CS-MOGA show a very low variance, so they tend to have longer life span than the other two scenarios.

In general, CCS-MOGA is a heuristical optimization algorithm, in which the performance of MOGA depends on its parameters (the population size, the maximum number of gener-

ation, etc.). To achieve a better performance requires a higher level of parameters, which increases the complexity of the algorithm. Hence, future works are needed to investigate other optimization techniques that improve the performance in terms of optimality and complexity.

VII. CONCLUSIONS

In this paper, we developed an algorithm based on multiple objective genetic algorithm to find the optimal values of the variables of compressive sensing paradigm. We optimized the number of measurements, transmission range and the mutual coherence of sensing matrix. We found that the optimizing these variables will indeed maximize the energy efficiency and minimize the probability of reconstruction error. The proposed algorithm provides a good trade-off between these two objectives. We also proposed a compressive sensing procedure that reduces the length of sensing vector to save on energy. The algorithm provides a dynamic construction of WSN based on the values of optimization variables and objectives. The performance of the proposed algorithms were compared to the performance of multiple paths PEGASIS and traditional CS algorithms and a higher energy efficiency has been achieved.