# Novel Energy-Efficient Data Gathering Scheme Exploiting Spatial-Temporal Correlation for Wireless Sensor Networks

Authors: Ying Zhou; Lihua Yang; Longxiang Yang; Meng Ni
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

A novel energy-efficient data gathering scheme that exploits spatial-temporal correlation is proposed for clustered wireless sensor networks in this paper. In the proposed method, dual prediction is used in the intracluster transmission to reduce the temporal redundancy, and hybrid compressed sensing is employed in the intercluster transmission to reduce the spatial redundancy. Moreover, an error threshold selection scheme is presented for the prediction model by optimizing the relationship between the energy consumption and the recovery accuracy, which makes the proposed method well suitable for different application environments. In addition, the transmission energy consumption is derived to verify the efficiency of the proposed method. Simulation results show that the proposed method has higher energy efficiency compared with the existing schemes, and the sink can recover measurements with reasonable accuracy by using the proposed method.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs), typically consisting of a vast number of densely deployed and collaborative battery-powered sensors, have been widely used in various application fields, such as the environment, industry, and the military [1]. However, the energy constraints are one of the main performance-limiting challenges for the WSNs. In the WSNs, most energy is consumed in three stages: sensing, data processing, and data delivery, and the energy consumed by the data delivery dominates the energy budget. Therefore, the data gathering approach with high energy efficiency is the key to prolong network lifetime.There are two main types of data gathering methods for WSNs: the mobile sink based data gathering methods [2] and the stationary sink based data gathering methods [3]. In the mobile sink scenario, the long delay is an inevitable problem [4], so both the movement speed and the traveling path for the sink are the difficulties in designing. However, the stationary sink can avoid the above problems. In the stationary sink scenario, since the observed data should be transmitted to the sink by multihop forwarding transmission, the high transmission energy consumption by the sensors is a problem that must be considered, which depends on the routing model and the data reduction technique. Therefore, the high energy efficient data collection with efficient routing is the key in the stationary sink scenario.Because of the overlap among the observation regions of the different sensors and the gradual variation of the data observed at a sensor over time, the measurements from a WSN are either spatially or temporally correlated [5], which leads to the existing of much redundant information among the observed data. Therefore, data gathering approaches that exploited the inherent correlation have been widely studied to improve the energy efficiency of the WSNs [6]. In [7–11], data reduction methods that utilized temporal correlation or spatial correlation are presented to reduce the transmission energy consumption. Moreover, many data compression algorithms are employed in these data gathering methods to obtain data reduction, where the network coding (NC) and compressed sensing (CS) techniques are applied in the data gathering methods in [7, 8], which utilize the spatial correlation to reduce the data transmissions. In [9–11], the principal component analysis (PCA) methods or different prediction models are applied to reduce the temporal redundancy. However, the redundant information is still excessive after using the above methods [7–11], which will cause low energy efficiency.To further improve the energy efficiency, data gathering schemes exploring both temporal and spatial correlations [12–15] are presented. In [12], a collective prediction scheme exploiting spatial-temporal correlation (CoPeST) is given for the energy efficient WSNs. In the CoPeST method, the temporal redundancy and spatial redundancy of data are, respectively, reduced by the prediction approach and similarity based subcluster method. However, the energy cost by the frequent updating of cluster and subcluster topology is large in this case. A framework with dedicated combination of data prediction and compression is discussed for clustered WSNs in [13] (which is called as DPPCA method for convenience). In the framework, the Least Mean Square (LMS) dual prediction algorithm is used to reduce the temporal redundancy, and a centralized PCA technique is utilized to eliminate the spatial redundancy of the sensed data. However, these schemes in [12, 13] are not practical in different monitoring environments due to the employed fixed error threshold in the prediction algorithms. By the spatial and temporal compressions, the multiresolution compression and query (MRCQ) framework is given in [14], which organizes sensor nodes hierarchically and establishes multiresolution summaries of sensing data inside the network. In [15], a neighbor-aided Kronecker compressed sensing scheme is provided for the WSNs. However, the delay of the methods in [13–15] cannot be ignored, because the operation of reducing the temporal redundancy can only be executed after collecting enough data from continuous time intervals. Therefore, these schemes in [13–15] are not suited for the WSNs with the requirement of high real-time transmission.To solve the above problems and further improve the energy efficiency, we propose an energy efficient data gathering scheme exploiting spatial-temporal correlation for the WSNs. With distinctions to the above approaches, dual prediction and hybrid compressed sensing techniques are jointed to eliminate the redundancy to improve the energy efficiency in the proposed method. Specifically, dual prediction is utilized during the intracluster transmission, and a new error threshold selection method is designed for the prediction stage, which is obtained by optimizing the relationship between the energy consumption and the recovery accuracy. Moreover, hybrid compressed sensing is employed during intercluster transmission, and the cluster heads (CHs) aggregate all the obtained values only when the number of values is no less than the required number of projections for CS reconstruction. Therefore, the proposed method has high energy efficiency and the reasonable quality.The rest of this paper is organized as follows. The background and system model are discussed in Section2. In Section 3, we introduce our proposed protocol in detail. Section 4 discusses the simulation results and conclusions are given in Section 5.


## 2. Background and System Model

### 2.1. Hybrid Compressed Sensing

Compressed sensing [16], as an advanced sampling theory, provides a new data compression solution, and it indicates that only a small fraction of data projections is needed to reconstruct all of the raw data, which contains many zero entries. Assume a data vectorx has aK-sparse representation under a N×N transform basis, i.e., Ψ:(1)x=Ψθwhere x=[x1,x2,…,xN]T. θ=[θ1,θ2,…,θN]T, and it hasK(K≪N) nonzero entries. Under this premise, the projection transformation is appliedx; that is,(2)z=Φx=ϕ1,ϕ2,…,ϕNxwhere Φ is a M×N (M≪N) measurement matrix, and it satisfies the restricted isometry principle (RIP) [17]. ϕi is the corresponding coefficient vector of xi, and ϕi=ϕ1i,ϕ2i,…,ϕMiT. Then theM-dimension vectorz can be used to recover the raw datax by solving a l1-norm minimization.According to the theory, only a few measurements are enough to reconstruct all original data for sink by CS in WSNs. Figure1(a) shows the process of data gathering with pure CS, where each node i codes its data xi with its corresponding coefficient vector ϕi in measurement matrix Φ and then sends outM-dimension vector ∑k=1axkϕk which is aggregated by its encoded vector xkϕk and the (a-1) achieved data vectors. In this case, every node needs to send out M data. However, the number of original data that needs to be transmitted may be smaller than M in the front nodes of links, and it is not the best choice to directly applying the CS coding on every node.Figure 1
Example ofM=3 for difference between pure CS and hybrid CS. (a) Data gathering with pure CS. (b) Data gathering with hybrid CS.
(a) (b)To avoid this problem, a modified hybrid compressed sensing method is discussed in [18]. In the hybrid CS method, each node i is initially set to transmit its raw data directly at first. Then, once an intermediate node j receives more than (M-1) raw readings or any encoded readings, the intermediate node switches to the CS aggregation mode. In this case, the unnecessary transmissions are avoided in the data gathering by the hybrid CS. Figure 1(b) shows the process of data gathering with hybrid CS, where each node sends out original readings directly if the number of readings is smaller than M. Otherwise, the node codes the data with corresponding coefficient vectors and sends outM-dimension coded vector later. Obviously, the hybrid CS has a higher energy efficiency.


### 2.2. System Model

As seen in Figure2, a cluster-based wireless sensor network with N sensor nodes is considered in this paper. The whole network is divided into p clusters. Both cluster members (CMs) and cluster heads (CHs) continuously generate a set of data that need to be collected by the sink. Let x(t)=x1t,x2t,…,xNtT denote the observed data from the network at the time instant t and the data vector can also be written as (3)xt=x1Tt,x2Tt,…,xpTtTwhere xk(t) is the raw data vector of thek-th cluster. The member nodes in a cluster selectively send their data to the CH with prediction model, and the data vector obtained in all CHs is(4)yt=y1t,y2t,…,yNtT=y1Tt,y2Tt,…,ypTtTwhere yk(t) is the obtained data vector by thek-th CH. Then the CHs forward all the data to the sink with hybrid compressed sensing via multihop communication. Assume that each CH knows the CS projection vectors of all nodes within the cluster. TheM-dimension measurement vector obtained in the sink is z(t)=Φy(t) where Φ is a constant M×N measurement matrix which meets the RIP condition. The sink reconstructs the data vector from z(t) with the CS recovery algorithm, such as basis pursuit (BP) and orthogonal matching pursuit (OMP).Figure 2
A cluster-based wireless sensor network.


## 2.1. Hybrid Compressed Sensing

Compressed sensing [16], as an advanced sampling theory, provides a new data compression solution, and it indicates that only a small fraction of data projections is needed to reconstruct all of the raw data, which contains many zero entries. Assume a data vectorx has aK-sparse representation under a N×N transform basis, i.e., Ψ:(1)x=Ψθwhere x=[x1,x2,…,xN]T. θ=[θ1,θ2,…,θN]T, and it hasK(K≪N) nonzero entries. Under this premise, the projection transformation is appliedx; that is,(2)z=Φx=ϕ1,ϕ2,…,ϕNxwhere Φ is a M×N (M≪N) measurement matrix, and it satisfies the restricted isometry principle (RIP) [17]. ϕi is the corresponding coefficient vector of xi, and ϕi=ϕ1i,ϕ2i,…,ϕMiT. Then theM-dimension vectorz can be used to recover the raw datax by solving a l1-norm minimization.According to the theory, only a few measurements are enough to reconstruct all original data for sink by CS in WSNs. Figure1(a) shows the process of data gathering with pure CS, where each node i codes its data xi with its corresponding coefficient vector ϕi in measurement matrix Φ and then sends outM-dimension vector ∑k=1axkϕk which is aggregated by its encoded vector xkϕk and the (a-1) achieved data vectors. In this case, every node needs to send out M data. However, the number of original data that needs to be transmitted may be smaller than M in the front nodes of links, and it is not the best choice to directly applying the CS coding on every node.Figure 1
Example ofM=3 for difference between pure CS and hybrid CS. (a) Data gathering with pure CS. (b) Data gathering with hybrid CS.
(a) (b)To avoid this problem, a modified hybrid compressed sensing method is discussed in [18]. In the hybrid CS method, each node i is initially set to transmit its raw data directly at first. Then, once an intermediate node j receives more than (M-1) raw readings or any encoded readings, the intermediate node switches to the CS aggregation mode. In this case, the unnecessary transmissions are avoided in the data gathering by the hybrid CS. Figure 1(b) shows the process of data gathering with hybrid CS, where each node sends out original readings directly if the number of readings is smaller than M. Otherwise, the node codes the data with corresponding coefficient vectors and sends outM-dimension coded vector later. Obviously, the hybrid CS has a higher energy efficiency.


## 2.2. System Model

As seen in Figure2, a cluster-based wireless sensor network with N sensor nodes is considered in this paper. The whole network is divided into p clusters. Both cluster members (CMs) and cluster heads (CHs) continuously generate a set of data that need to be collected by the sink. Let x(t)=x1t,x2t,…,xNtT denote the observed data from the network at the time instant t and the data vector can also be written as (3)xt=x1Tt,x2Tt,…,xpTtTwhere xk(t) is the raw data vector of thek-th cluster. The member nodes in a cluster selectively send their data to the CH with prediction model, and the data vector obtained in all CHs is(4)yt=y1t,y2t,…,yNtT=y1Tt,y2Tt,…,ypTtTwhere yk(t) is the obtained data vector by thek-th CH. Then the CHs forward all the data to the sink with hybrid compressed sensing via multihop communication. Assume that each CH knows the CS projection vectors of all nodes within the cluster. TheM-dimension measurement vector obtained in the sink is z(t)=Φy(t) where Φ is a constant M×N measurement matrix which meets the RIP condition. The sink reconstructs the data vector from z(t) with the CS recovery algorithm, such as basis pursuit (BP) and orthogonal matching pursuit (OMP).Figure 2
A cluster-based wireless sensor network.


## 3. Proposed Method

### 3.1. Overall Description of the Proposed Method

In the proposed method, dual prediction [17] and hybrid compressed sensing are jointed to reduce the energy consumption of data gathering in the clustered WSNs. Moreover, an error threshold selection principle is designed to make the proposed method well suitable for a myriad of environments.Figure3 shows the diagram of the proposed method for the cluster-based WSN. In the scheme, dual prediction technique is firstly applied in the intracluster transmission to eliminate the temporal redundancy of measurements. With the prediction method, the cluster members selectively transmit their measurements to the CHs, and the CHs use the forecasted values instead of the actual ones which are not received. Next, the hybrid CS is used in intercluster transmission to reduce the spatial redundancy. With the hybrid CS, the CHs aggregate the obtained data or not and then send the coded/uncoded vectors to the sink via multihop communication. Finally, the sink reconstructs the original data with a CS recovery algorithm. The details of the proposed scheme are given in the following.Figure 3
The diagram of the proposed method for the cluster-based WSN.Stage 1 (intracluster transmission).
At every sampling timet, each node i obtains an observed value xi(t) from the surrounding environment, and then it forecasts xi^(t) using the preconstructed prediction model. There are two cases that should be considered for the node i as follows:
Case 1. If the error between the forecasted and observed values is over the threshold εi, which is prespecified based on the error threshold selection principle (it will be discussed in the Section 3.2), i.e.,(5)xi^t-xit>εithe node i transfers the actual value xi(t) to its CH.
Case 2. If the forecasted value is acceptable, i.e.,(6)xi^t-xit≤εithe cluster head calculates xi^(t) with the same prediction model to approximate the actual data. In this case, unnecessary transmissions are avoided.Stage 2 (intercluster transmission).
Letyj(t)=yj1(t),yj2(t),…,yjNj(t)T denote the data vector of the cluster head j obtained from the cluster, where Nj is the number of nodes in the clusterj, and yjk(t) is an actual value obtained directly or a prediction value calculated by the CH for thek-th node in cluster j. Assume J=j1,j2,…,jh is the set of cluster heads which transfer their data to the cluster head j. There are two cases that need to be considered for the cluster head j as follows:
Case 1. If ∑k=1hNjk+Nj<M, the cluster head j sends out the data vector yj∗(t) without aggregation, where(7)yj∗t=yj1Tt,yj2Tt,…,yjhTt,yjTtTand the number of elements in yj∗(t) is(8)qj=∑k=1hNjk+NjCase 2. If ∑k=1hNjk+Nj≥M,(9)yj∗t=∑k=1hΦjkyjkt+Φjyjtand(10)qj=MStage 3.
The sink obtains the data vector(11)zt=Φyt=∑k=1pΦkyktand reconstructs the original data with the CS recovery algorithm, such as basis pursuit (BP) and orthogonal matching pursuit (OMP).


### 3.2. Error Threshold Selection Principle

As illustrated in Section3.1, a node i will send its observed value to the CH if xi^(t)-xi(t)>εi where εi is a user given error threshold. It means that the value εi determines the number of transmissions in every time instant, and it influences the accuracy of data recovery in the sink. Therefore, it is important to select an appropriate error threshold εi for the data gathering scheme with prediction.According to the Central Limit Theorem, we assume unbiased predictions and errors normally distributed. In this paper, we select a simple autoregressive (AR) model to predict in the proposed method, which is only an example for understanding easily. Moreover, the proposed error selection principle is universal for different prediction methods when prediction error distribution models of these methods can be estimated.Al-order AR predictor can be denoted as(12)xi^t=∑k=1lξkxit-kwhere ξ1,ξ2,…,ξl are the parameters of the prediction model, which can be constructed by the Yule-Walker equations or the least square method. Assume the observed value can be written as(13)xit=∑k=1lξkxit-k+eitwhere ei(t) is the prediction error with zero mean and variance σi2, i.e., ei(t)~N(0,σi2). To a fixed error threshold εi, the probability of a node to send its observed data out is(14)α=2-2Φεiσiwhere Φ(·) is the CDF of Gaussian white noise. Clearly, to make sure that the scheme with dual prediction is more energy efficient, the additional computation power must be much less than the reduced energy of transmission; that is,(15)2-αEp<1-αEswhere Ep and Es are the energy costs of a single prediction and sending a value to the CH, respectively. In general, Es is larger than Ep, and suppose Es=kEp. Thus, the error threshold needs to satisfy(16)Φεiσi>k2k-2In practice, the valueσi is unknown. Authors in [10] use σxi1-∑j=1pϕjρxi(j) instead of the unknown value σi, where σxi and ρxi(j) are the standard deviation and correlation coefficient of a stationary time series xi, respectively.Combining (14) and (16), it is obvious that a bigger εi leads to lower energy consumption but decreases the recovery accuracy. Therefore, the choice of εi must be weighed between the energy consumption and the recovery accuracy.The energy consumption for one node sendingT data to its CH in the proposed method is (17)ET=2-αTEp+αTEs=2ΦεiσiTEp+2-2ΦεiσiTEsThe mean square error (MSE) of the process is(18)MSE=1T∑j=1Tηj×ei2jwhere ei(j)≤εi and (19)ηj=0,sendoutxij1,notsendoutxijThus, one can obtain the following:(20)MSE≤1-αεi2Formulate the optimization as(21)min2ΦεiσiEp+2-2ΦεiσiEss.t.Φεiσi>k2k-22Φεiσi-1εi2≤λεi2where λ is a user given parameter which indicates the acceptable maximum recovery accuracy. In practice, the value of λ is between 0 and 1, and it reflects the ratio of expected prediction error to the maximum error. A larger λ means less energy cost (i.e., high energy efficiency) and lower recovery accuracy. The users can determine an appropriate λ depending on the tradeoff between energy efficiency and recovery accuracy for different applications; that is because different applications have different requirements for energy efficiency and recovery accuracy. For example, some applications require high energy efficiency and low recovery accuracy, while others require low energy efficiency and high recovery accuracy. Therefore, the value of λ needs to be determined according to the specific application requirements, and we only give the performance of proposed method under a given value in the simulation.To solve the above optimization problem in Equation (21), Φεi/σi is treated as a variable. In this case, the above optimization is translated into a simple linear programming problem, which can be solved by the existing algorithms [19]. Once Φεi/σi is calculated, εi can be obtained according to the corresponding σi and Gaussian distribution table.Specifically, to ensure the energy efficiency of the system, a small transmit probability is required. In the meanwhile, the accuracy of intracluster transmission should be guarantee to a certain extent. In this case, a prediction model with higher estimated accuracy (but higher computation complexity in general) should be considered.


### 3.3. Procedures of the Proposed Method

Algorithm1 illustrates the proposed threshold selection-based data collection algorithm. As discussed in Section 3.1, the procedure of the proposed method is as the following 4 paragraphs:Algorithm 1:Threshold selection-based data collection algorithm.
1:  Each cluster member obtains its error thresholdεi using (21) Stage1: Intra-cluster Transmission 2:for each cluster member i 3:   forecastsxi^(t) for the current sampling time t using the preconstructed prediction model; 4:    calculates the error betweenxi^(t) and the observed value xi(t); 5:ifx^i(t)-xi(t)>εi 6:    the nodei transfers the actual value to its cluster heads 7:else 8:    the corresponding cluster head calculatesxi^(t) with the same prediction model; 9:end 10:end Stage2. Inter-cluster Transmission 11:  After stage 1, each cluster headj obtains the values of its members yj∗(t)=[yj1T(t),yj2T(t),…,yjhT(t),yjT(t)]T. 12:for each cluster head j in the multi-hop link 13:   calculates the number of values which have been obtained by the nodej from all front cluster headsJ=j1,j2,…,jh in the link and its own members; 14:if∑k=1hNjk+Nj≥M 15:yj∗(t)=∑k=1hΦjkyjk(t)+Φjyj(t) 16:else 17:yj∗(t)=[yj1T(t),yj2T(t),…,yjhT(t),yjT(t)]T 18:end 19:   sends outyj∗(t); 20:end Stage3. Reconstruction 21:  The sink obtains the data vector z(t)=Φy(t)=∑k=1pΦkyk(t) and reconstructs the original data with the CS recovery algorithm.Firstly, each cluster member calculates its error threshold according to the error threshold selection principle which is discussed in Section3.2.Then, intracluster transmission begins. The cluster member predicts the current value and compares the predicted value with the actual observed one. If the error between them is larger than the error threshold, the cluster member sends the observed reading to its corresponding cluster head. Else, the cluster head predicts the current value with the same prediction model.Next, once the cluster heads collect all data of their members, the intercluster transmission begins. If the number of data that needs to be transmitted for one cluster head is less thanM, the cluster head sent these data out directly. Else, the cluster head aggregates these data to M dimension with compressed sensing which is discussed in Section 2.1 and sends the coded data out after.Finally, the sink reconstructs the original data according to the obtained data vector and some CS recovery algorithms.Ignore the computation complexity of the reconstruction process. Assume the complexity of the applied prediction model isOpred, and the computation complexity of stage 1 is N-p2-αOpred+2. The computation complexity of stage 2 is about OMN which depends on the complexity of the matrix multiplication Φy(t). Thus, the total computation complexity of Algorithm 1 is about N-p2-αOpred+2+OMN.


### 3.4. Transmission Energy Cost Analysis

In this paper, the reduction of the communication cost means the energy saving while guaranteeing the user-defined data accuracy. As shown in Figure3, the scheme concludes two communication stages: intracluster transmission with prediction and intercluster transmission with compressed sensing.Assume that there areN nodes in network (p of them are cluster heads), and each node has T data for gathering. In intracluster transmission, each node costs Ep energy to forecast the current value, and then the node sends its observed data to its cluster with probability α; otherwise, the cluster head needs to predict the data with probability (1-α). The expected energy cost of each cluster member for this process is αEs+(1-α)Ep. Therefore, the energy cost of intracluster transmission is(22)E1=T2-αN-pEp+αN-pEsIn intercluster transmission, the energy cost of each cluster headk for each time is qkEt, where qk is the number of data that CH k needs to send out (which is defined in Section 3.1), and Et is the energy cost for a cluster head sending out data. Therefore, the transmission energy cost of intercluster transmission is(23)E2=T∑k=1pqkEtwhere p is the number of clusters in network.Combining (22) and (23), the total transmission energy cost is(24)Etotal=T2-αN-pEp+αN-pEs+∑k=1pqkEt


## 3.1. Overall Description of the Proposed Method

In the proposed method, dual prediction [17] and hybrid compressed sensing are jointed to reduce the energy consumption of data gathering in the clustered WSNs. Moreover, an error threshold selection principle is designed to make the proposed method well suitable for a myriad of environments.Figure3 shows the diagram of the proposed method for the cluster-based WSN. In the scheme, dual prediction technique is firstly applied in the intracluster transmission to eliminate the temporal redundancy of measurements. With the prediction method, the cluster members selectively transmit their measurements to the CHs, and the CHs use the forecasted values instead of the actual ones which are not received. Next, the hybrid CS is used in intercluster transmission to reduce the spatial redundancy. With the hybrid CS, the CHs aggregate the obtained data or not and then send the coded/uncoded vectors to the sink via multihop communication. Finally, the sink reconstructs the original data with a CS recovery algorithm. The details of the proposed scheme are given in the following.Figure 3
The diagram of the proposed method for the cluster-based WSN.Stage 1 (intracluster transmission).
At every sampling timet, each node i obtains an observed value xi(t) from the surrounding environment, and then it forecasts xi^(t) using the preconstructed prediction model. There are two cases that should be considered for the node i as follows:
Case 1. If the error between the forecasted and observed values is over the threshold εi, which is prespecified based on the error threshold selection principle (it will be discussed in the Section 3.2), i.e.,(5)xi^t-xit>εithe node i transfers the actual value xi(t) to its CH.
Case 2. If the forecasted value is acceptable, i.e.,(6)xi^t-xit≤εithe cluster head calculates xi^(t) with the same prediction model to approximate the actual data. In this case, unnecessary transmissions are avoided.Stage 2 (intercluster transmission).
Letyj(t)=yj1(t),yj2(t),…,yjNj(t)T denote the data vector of the cluster head j obtained from the cluster, where Nj is the number of nodes in the clusterj, and yjk(t) is an actual value obtained directly or a prediction value calculated by the CH for thek-th node in cluster j. Assume J=j1,j2,…,jh is the set of cluster heads which transfer their data to the cluster head j. There are two cases that need to be considered for the cluster head j as follows:
Case 1. If ∑k=1hNjk+Nj<M, the cluster head j sends out the data vector yj∗(t) without aggregation, where(7)yj∗t=yj1Tt,yj2Tt,…,yjhTt,yjTtTand the number of elements in yj∗(t) is(8)qj=∑k=1hNjk+NjCase 2. If ∑k=1hNjk+Nj≥M,(9)yj∗t=∑k=1hΦjkyjkt+Φjyjtand(10)qj=MStage 3.
The sink obtains the data vector(11)zt=Φyt=∑k=1pΦkyktand reconstructs the original data with the CS recovery algorithm, such as basis pursuit (BP) and orthogonal matching pursuit (OMP).


## 3.2. Error Threshold Selection Principle

As illustrated in Section3.1, a node i will send its observed value to the CH if xi^(t)-xi(t)>εi where εi is a user given error threshold. It means that the value εi determines the number of transmissions in every time instant, and it influences the accuracy of data recovery in the sink. Therefore, it is important to select an appropriate error threshold εi for the data gathering scheme with prediction.According to the Central Limit Theorem, we assume unbiased predictions and errors normally distributed. In this paper, we select a simple autoregressive (AR) model to predict in the proposed method, which is only an example for understanding easily. Moreover, the proposed error selection principle is universal for different prediction methods when prediction error distribution models of these methods can be estimated.Al-order AR predictor can be denoted as(12)xi^t=∑k=1lξkxit-kwhere ξ1,ξ2,…,ξl are the parameters of the prediction model, which can be constructed by the Yule-Walker equations or the least square method. Assume the observed value can be written as(13)xit=∑k=1lξkxit-k+eitwhere ei(t) is the prediction error with zero mean and variance σi2, i.e., ei(t)~N(0,σi2). To a fixed error threshold εi, the probability of a node to send its observed data out is(14)α=2-2Φεiσiwhere Φ(·) is the CDF of Gaussian white noise. Clearly, to make sure that the scheme with dual prediction is more energy efficient, the additional computation power must be much less than the reduced energy of transmission; that is,(15)2-αEp<1-αEswhere Ep and Es are the energy costs of a single prediction and sending a value to the CH, respectively. In general, Es is larger than Ep, and suppose Es=kEp. Thus, the error threshold needs to satisfy(16)Φεiσi>k2k-2In practice, the valueσi is unknown. Authors in [10] use σxi1-∑j=1pϕjρxi(j) instead of the unknown value σi, where σxi and ρxi(j) are the standard deviation and correlation coefficient of a stationary time series xi, respectively.Combining (14) and (16), it is obvious that a bigger εi leads to lower energy consumption but decreases the recovery accuracy. Therefore, the choice of εi must be weighed between the energy consumption and the recovery accuracy.The energy consumption for one node sendingT data to its CH in the proposed method is (17)ET=2-αTEp+αTEs=2ΦεiσiTEp+2-2ΦεiσiTEsThe mean square error (MSE) of the process is(18)MSE=1T∑j=1Tηj×ei2jwhere ei(j)≤εi and (19)ηj=0,sendoutxij1,notsendoutxijThus, one can obtain the following:(20)MSE≤1-αεi2Formulate the optimization as(21)min2ΦεiσiEp+2-2ΦεiσiEss.t.Φεiσi>k2k-22Φεiσi-1εi2≤λεi2where λ is a user given parameter which indicates the acceptable maximum recovery accuracy. In practice, the value of λ is between 0 and 1, and it reflects the ratio of expected prediction error to the maximum error. A larger λ means less energy cost (i.e., high energy efficiency) and lower recovery accuracy. The users can determine an appropriate λ depending on the tradeoff between energy efficiency and recovery accuracy for different applications; that is because different applications have different requirements for energy efficiency and recovery accuracy. For example, some applications require high energy efficiency and low recovery accuracy, while others require low energy efficiency and high recovery accuracy. Therefore, the value of λ needs to be determined according to the specific application requirements, and we only give the performance of proposed method under a given value in the simulation.To solve the above optimization problem in Equation (21), Φεi/σi is treated as a variable. In this case, the above optimization is translated into a simple linear programming problem, which can be solved by the existing algorithms [19]. Once Φεi/σi is calculated, εi can be obtained according to the corresponding σi and Gaussian distribution table.Specifically, to ensure the energy efficiency of the system, a small transmit probability is required. In the meanwhile, the accuracy of intracluster transmission should be guarantee to a certain extent. In this case, a prediction model with higher estimated accuracy (but higher computation complexity in general) should be considered.


## 3.3. Procedures of the Proposed Method

Algorithm1 illustrates the proposed threshold selection-based data collection algorithm. As discussed in Section 3.1, the procedure of the proposed method is as the following 4 paragraphs:Algorithm 1:Threshold selection-based data collection algorithm.
1:  Each cluster member obtains its error thresholdεi using (21) Stage1: Intra-cluster Transmission 2:for each cluster member i 3:   forecastsxi^(t) for the current sampling time t using the preconstructed prediction model; 4:    calculates the error betweenxi^(t) and the observed value xi(t); 5:ifx^i(t)-xi(t)>εi 6:    the nodei transfers the actual value to its cluster heads 7:else 8:    the corresponding cluster head calculatesxi^(t) with the same prediction model; 9:end 10:end Stage2. Inter-cluster Transmission 11:  After stage 1, each cluster headj obtains the values of its members yj∗(t)=[yj1T(t),yj2T(t),…,yjhT(t),yjT(t)]T. 12:for each cluster head j in the multi-hop link 13:   calculates the number of values which have been obtained by the nodej from all front cluster headsJ=j1,j2,…,jh in the link and its own members; 14:if∑k=1hNjk+Nj≥M 15:yj∗(t)=∑k=1hΦjkyjk(t)+Φjyj(t) 16:else 17:yj∗(t)=[yj1T(t),yj2T(t),…,yjhT(t),yjT(t)]T 18:end 19:   sends outyj∗(t); 20:end Stage3. Reconstruction 21:  The sink obtains the data vector z(t)=Φy(t)=∑k=1pΦkyk(t) and reconstructs the original data with the CS recovery algorithm.Firstly, each cluster member calculates its error threshold according to the error threshold selection principle which is discussed in Section3.2.Then, intracluster transmission begins. The cluster member predicts the current value and compares the predicted value with the actual observed one. If the error between them is larger than the error threshold, the cluster member sends the observed reading to its corresponding cluster head. Else, the cluster head predicts the current value with the same prediction model.Next, once the cluster heads collect all data of their members, the intercluster transmission begins. If the number of data that needs to be transmitted for one cluster head is less thanM, the cluster head sent these data out directly. Else, the cluster head aggregates these data to M dimension with compressed sensing which is discussed in Section 2.1 and sends the coded data out after.Finally, the sink reconstructs the original data according to the obtained data vector and some CS recovery algorithms.Ignore the computation complexity of the reconstruction process. Assume the complexity of the applied prediction model isOpred, and the computation complexity of stage 1 is N-p2-αOpred+2. The computation complexity of stage 2 is about OMN which depends on the complexity of the matrix multiplication Φy(t). Thus, the total computation complexity of Algorithm 1 is about N-p2-αOpred+2+OMN.


## 3.4. Transmission Energy Cost Analysis

In this paper, the reduction of the communication cost means the energy saving while guaranteeing the user-defined data accuracy. As shown in Figure3, the scheme concludes two communication stages: intracluster transmission with prediction and intercluster transmission with compressed sensing.Assume that there areN nodes in network (p of them are cluster heads), and each node has T data for gathering. In intracluster transmission, each node costs Ep energy to forecast the current value, and then the node sends its observed data to its cluster with probability α; otherwise, the cluster head needs to predict the data with probability (1-α). The expected energy cost of each cluster member for this process is αEs+(1-α)Ep. Therefore, the energy cost of intracluster transmission is(22)E1=T2-αN-pEp+αN-pEsIn intercluster transmission, the energy cost of each cluster headk for each time is qkEt, where qk is the number of data that CH k needs to send out (which is defined in Section 3.1), and Et is the energy cost for a cluster head sending out data. Therefore, the transmission energy cost of intercluster transmission is(23)E2=T∑k=1pqkEtwhere p is the number of clusters in network.Combining (22) and (23), the total transmission energy cost is(24)Etotal=T2-αN-pEp+αN-pEs+∑k=1pqkEt


## 4. Results and Discussion

To evaluate the performance of the proposed method, the cluster-based WSNs with fixed area are considered. For simplicity, the LEACH [20] is used for the clustering approach in the simulation, and the probability for each node to become a cluster head is set to 0.1. In the simulation, the number of nodes N of the synthetic network takes value from 500 to 1500, and each node in the network hasT=1000 values that need to be gathered. The parameter λ of the proposed method ranges from 0.01 to 0.95. A simple AR predictor is used in the simulation, and ten history data values can be cached by each node for constructing the parameters of the prediction model. The energy cost model of MICAZ [21] is used for energy estimation of our work. In MICAZ model, the transmission cost of one bit is 600 nJ and the computation energy per clock cycle is 3.5 nJ. Assume that data is with 16 bits. In comparison with the proposed method, the available schemes, i.e., DPPCA [13] and CHCS [18], are also simulated, specifically, the fixed threshold of the DPPCA method which with prediction program is set to 0.1 according to the reference. All simulations are run in the MATLAB software.Figure4 shows the percentage of failed predictions and MSE curves versus the different error threshold at one node for the first stage of the proposed method. In Figure 4, MSE is the mean square error of the prediction stage of the proposed method. Clearly, if the prediction fails in a time instant, the node will need to send the raw data to its CH. As the error threshold increases, the percentage of failed predictions decreases and the MSE performance is degraded. When the error threshold is larger than 0.2, the percentage of failed predictions tends to decrease slightly, while the MSE performance is still degraded rapidly, because the prediction error obeys an approximate Gaussian distribution in general.Figure 4
Percentage of transmission nodes and MSE performance under the different error thresholds.Figure5 gives the error threshold curve versus the different for the proposed method λ. In Figure 5, λ is a user given parameter, and a larger λ means a larger MSE performance for the first stage of the proposed method. In the simulation,k=30 is considered for determining the error threshold. From Figure 5, the error threshold increases rapidly when λ is larger than 0.8. According to the MSE performance in Figure 4, the MSE performance will be too poor in this case. Therefore, a reasonable λ should be chosen in practical application.Figure 5
Error threshold against differentλ for the proposed method (N=1000).Figure6 gives the number of transmissions curves versus the number of clusters in network for the proposed method. From Figure 6, one can see that the total number of transmissions increases as the number of clusters increases in network, because more clusters in network mean more intercluster transmissions, and while prediction model is applied in intracluster transmission, the number of intercluster transmissions is larger. In addition, as the number of clusters increases, the total numbers of transmissions with different λ tend to be the same. It is because the number of intracluster transmissions will be reduced (note that its limit value will tend to zero) as the number of clusters increases, and the value of λ only affects the intracluster transmission, so the gaps between the numbers of intracluster transmissions with different λ become smaller as the number of clusters increases.Figure 6
Total number of transmissions against the number of clusters in network for the proposed method (N=1000).Figure7 shows the total number of transmissions curves versus the number of nodes in the network for different methods. In Figure 7, “normal method” is one without any compression operation during the transmission. From Figure 7, one can see that the transmission energy consumption of the proposed method is smaller than those of the available methods. Compared with the normal method, the proposed method reduces the transmission energy consumption by 50%. Moreover, the proposed method can reduce the transmission energy cost about 40% and 20% when compared with the CHCS and DPPCA methods, respectively; that is because the proposed method uses dual prediction with adaptive error threshold and hybrid compressed sensing. In addition, as the number of nodes increases, the proposed method will have better energy efficiency, which also shows that the proposed method is suitable for the large-scale networks.Figure 7
Total number of transmissions against the number of nodes in network for different methods.Figure8 gives the MSE performance against the number of nodes for different methods. In Figure 8, the CHCS in [18] and the DPPCA in [13] are compared with the proposed method. From Figure 8, one can see that the MSE performance improves as the number of nodes increases. It is because the distribution area for all nodes of the network is assumed to be fixed, and the node density increases with the increase of total number of nodes. In this case, the overlap degree of observed area for nodes is higher, which means that the spatial correlation of observed data increases. Therefore, the MSE performance improves when the compressed sensing with fixed compression ratio is applied in intertransmission stage. Moreover, one can see that the MSE performance of the CHCS method is the best due to its only having the intercluster compression, but it costs the most energy in transmission stage which can be seen from Figure 7. The MSE performance of the DPPCA method is a little better while λ = 0.8, but the advantage gradually diminished as the network size increases, and the DPPCA method always costs much more energy than the proposed method which can be seen from Figure 7. When λ is smaller than 0.4, the MSE performance of the proposed is better, and meanwhile the proposed method still has a higher energy efficiency. Therefore, taking into consideration the energy cost and the MSE performance, the proposed method with adaptive threshold has a distinct advantage in practical applications.Figure 8
MSE performance of different methods against the number of nodes in network.


## 5. Conclusions

In this paper, a novel energy-efficient data gathering scheme exploiting both spatial and temporal correlations is proposed for clustered WSNs. The method uses dual prediction to reduce the temporal redundancy during the intracluster transmission, and the hybrid CS technique is utilized to reduce the spatial redundancy during the intercluster transmission. In this way, the transmission energy cost is decreased greatly. To enhance the availability of the proposed method for different environments, an error threshold selection principle based on the tradeoff between the MSE and the energy cost is designed. Compared with the CHCS and DPPCA methods, the proposed scheme can greatly reduce the transmission energy cost. In addition, the proposed method offers adequate data recovery accuracy, and it can perform well in large-scale and dense WSNs.



---

*Source: 4182563-2019-05-19.xml*