# A Missing Sensor Data Estimation Algorithm Based on Temporal and Spatial Correlation

Authors: Zhipeng Gao; Weijing Cheng; Xuesong Qiu; Luoming Meng
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

In wireless sensor network, data loss is inevitable due to its inherent characteristics. This phenomenon is even serious in some situation which brings a big challenge to the applications of sensor data. However, the traditional data estimation methods can not be directly used in wireless sensor network and existing estimation algorithms fail to provide a satisfactory accuracy or have high complexity. To address this problem,Temporal and Spatial Correlation Algorithm (TSCA) is proposed to estimate missing data as accurately as possible in this paper. Firstly, it saves all the data sensed at the same time as a time series, and the most relevant series are selected as the analysis sample, which improves efficiency and accuracy of the algorithm significantly. Secondly, it estimates missing values from temporal and spatial dimensions. Different weights are assigned to these two dimensions. Thirdly, there are two strategies to deal with severe data loss, which improves the applicability of the algorithm. Simulation results on different sensor datasets verify that the proposed approach outperforms existing solutions in terms of estimation accuracy.


---

## Body

## 1. Introduction

In recent years, with the development of sensing technology, wireless communication, and computing technology, wireless sensor network (WSN) [1] has been a focus of research and attracts strong attention from military, industry, and academia. In many applications of WSN, data loss [2, 3] is common due to limited resources of sensor nodes [4], interference of noise, and influence of environment. Even in some special situation, this phenomenon is very serious [5] which brings a big challenge for a variety of sensor data processing. If these missing values cannot be filled in accurately, the existing analysis tools cannot be applied. If the missing data are directly deleted, a large amount of raw data will be lost which will reduce the accuracy and reliability of analysis results and cause a great waste of energy. Data estimation algorithms can effectively solve this problem, and they provide strong support for query [6], aggregation, transmission, and warning [7]. So missing data estimation is particularly important for various applications of WSN.However, the traditional data estimation methods [8] cannot be directly used in WSN. Sensor data estimation methods should consider the characteristics of the application system and sensor data. While many studies on sensor data estimation have been conducted and some achievements have been made, there are still some issues unresolved such as underutilization of sensor data’s properties, high computational complexity, and low estimation accuracy.We present aTemporal and Spatial Correlation Algorithm (TSCA) to estimate missing data in this paper. There are four main innovations of this algorithm. Firstly, it saves all the data sensed at the same time as a time series, and the most relevant series are selected as the analysis sample, which improves efficiency and accuracy of the algorithm significantly. Secondly, it selects the most data-relevant sensor nodes and gets spatial estimation based on comprehensive instantaneous rate of change. In the time dimension, it differentiates the order of past frames to estimate the missing rate which highlights the timeliness of sensor data. Thirdly, different weights are assigned to temporal and spatial dimensions to get the final result. Finally, there are two strategies to deal with severe data loss, which improves the applicability of the algorithm.The rest of this paper is organized as follows. Section2 presents the classic estimation algorithms of missing sensor data. Section 3 presents the framework of the algorithm proposed in this paper. Section 4 describes specific design of our algorithm and extends to severe loss scenes. Section 5 evaluates the proposed approach through simulation experiment. Section 6 concludes this paper.


## 2. Related Work

The estimation algorithms of missing data have been extensively researched in statistics, for example, Mean Substitution, Imputation by Regression, Expectation Maximization, Maximum Likelihood, Multiple Imputations, Bayesian Estimation, and Hot/Cold Deck Imputation [9]. However, none of these algorithms can be used in WSN, because they require the data miss at random and their efficiency is low.To solve sensor data missing problem, Tiny DB [10] which is a mainstream sensor database system uses the mean of data sensed by other nodes directly as the estimated value. However, when the relationship among the sensor nodes is weak, the estimation result is not precise. MASTER-M algorithm [11] computes the similarity between sensor nodes and sorts them. It selects nodes which have high missing rate as seeds and clusters the whole network into several groups. MARSTER-tree is used to estimate missing data in each cluster. However, the relationship between the sensor nodes is not transitive; for example, S1 and S2, S2 and S3 are similar but S1 and S3 may not be similar. So in an n nodes network, Cn2 calculations and comparisons need to be conducted in each process of clustering. If the similar relationships between the sensor nodes change rapidly, reclustering is needed constantly which will cause high computational complexity. Adaptive Multiple Regression (AMR) algorithm is proposed in [12]. Sample data and the most relevant sensor nodes are determined heuristically. Missing values are evaluated using linear regression models according to the data of the relevant nodes. The key steps in this algorithm are realized heuristically which will increase the computational complexity. In addition, the location-related nodes are not always data-related; for example, in a place with several heat sources [13], the nodes which are near heat sources but far apart from each other may be more relevant. So location-based association mining is not accurate. Assessment using linear regression models also increases errors. Grey System Estimate Algorithm (GSEA) [14] estimates missing values based on gray model. Minimized Similarity Distortion (MSD) [15] uses linear regression to evaluate the loss. The accuracy of both GSEA and MSD is poor.The above algorithms only consider the temporal or spatial correlation and few algorithms take both of them into account. Environmental Space Time Improved Compressive Sensing (ESTI-CS) algorithm [16] is based on compressed sensing. This algorithm uses L1 norm optimization method for solving the reconstructed signal and it requires iteration which causes high complexity. Reference [17] proposes Trend Regression Expanding Cluster Interpolation (TRECI) algorithm which considers the change of sensor data over the time. Sensor nodes are divided into several groups dynamically and time interpolation assessments are conducted within each group. It only analyzes similarity rather than predicting the loss in the spatial dimension. Data Estimation using Statistical Model (DESM) [18] algorithm estimates the missing data based on the propagation characteristics of physical quantities in the time dimension; for example, according to the fact that light intensity is inversely proportional to the square of the distance, the light intensity can be estimated in certain region. In the spatial dimension, it estimates missing data based on the correlation between the estimated node and its surrounding nodes. The disadvantage of this algorithm is that it is only appropriate for attributes which have explicit physical models. Besides, the estimation in the spatial dimension is rough. Reference [19] proposes Mining Autonomously Spatial-Temporal Environmental Rules (MASTER) algorithm. It mines association of sensor data in temporal and spatial dimensions. A big drawback of this algorithm is that when the relationship among sensor data is weak, the prediction is very inaccurate.


## 3. Framework of Proposed Algorithm

Sensor data collected by a nodeSi can be seen as a time series Si=[(Vi1,T1), Vi2,T2,…,(Vin,Tn)]. Vik is the sensing data at Tk. For any time Tk (k=1,2,…,n), if the data Vik is lost, seeking the estimated value Vik′ and minimizing Vik′-Vik are the missing data estimation problem.From the comparison of difference between two consecutive intervals and difference between neighbors [16], we can see that most of measured data in real world always change stably; that is, there is little mutation on environmental value between adjacent time slots. In addition, environments are often smooth in a small area; that is, over a period of time, environmental values are similar among some nodes. Thus, we can use spatiotemporal correlations to estimate the missing data.Considering that the existing missing data estimation algorithms have not made full use of features of sensor data and they have high computational complexity as well as low accuracy, this paper proposes a missing data estimation algorithm based on temporal and spatial correlations as shown in Figure1. The evaluation result of this algorithm is Estimate which can be computed by the following formula:(1)Estimate=∑i=1s_nwi∗V_Spatial+1-∑i=1s_nwi∗V_Temple,where V_Spatial and V_Temple are the analysis results of spatial and temporal correlations. wi is the weight of each relevant sensor node. s_n is the number of sensor nodes used to estimate the missing data.Figure 1
Framework of the algorithm in this paper.This algorithm consists of three parts:(i)
Firstly, the algorithm needs to determine the sample data used in the process of analysis. Because sensor data is time-sensitive, using a different number of sensor data for analysis will get different results. Relationship between the sensor nodes in different periods is not the same, so selecting appropriate data used for analysis is important. Sensor nodes sense data periodically. The algorithm in this paper saves data sensed by all the nodes at the same time as a series. Continuous period produces continuous time series. For example, sensed data atti,ti+1,ti+2,… can be saved as the continuous time series (VS1ti,VS2ti,VS3ti,…,VSmti), (VS1ti+1,VS2ti+1,VS3ti+1,…,VSmti+1), and VS1ti+2,VS2ti+2,VS3ti+2,…,VSmti+2,…. The most relevant time series are selected based on the correlation function as the sample. It cannot only ensure that there are no redundant sample data which will reduce the computational complexity but also ensure that the sample data has the strongest correlation with missing data which will improve the accuracy of the analysis.(ii)
Secondly, correlation analyses are conducted in the spatial dimension. The distance between sensor nodes is defined according to the requirement of estimation. The most relevant sensor nodes are selected based on the distance function through analyzing the aforementioned sample data. Those relevant nodes are used to get spatial estimation. The weight of each relevant nodewi is determined according to the average correlation coefficient with the estimated node.(iii)
Thirdly, in the time dimension, estimation is based on the sample data sensed by the estimated node. In order to give full play to the timeliness of data, past frames are distinguished chronologically during the process of analysis, so the contribution of newer data is greater. The weight of temporal estimation is1-∑i=1S_nwi. Temporal and spatial results are integrated to obtain the final estimation value.


## 4. Detailed Design of TSCA

### 4.1. Select Sample Data

The relationship between the sensor nodes in WSN will change over time, so analyzing different sample data will generate different relationship, and we get different assessment values. In addition, the size of sample data will have a great impact on the assessment results. Due to the interference of environmental noise, too little sample data cannot reflect the spatiotemporal correlation of sensor data fully, while excessive sample data reflect the average value over an extended period of time rather than the instantaneous correlation which will reduce the accuracy of the assessment. Therefore, the values and the size of sample data should be determined as accurately as possible.Considering the fact that the spatiotemporal correlation of sensor data approximately remains constant in a short period of time, when we assess the missing data attn, data close to tn should be selected accurately as the sample.In WSN, sensor nodes are deployed in the given area. All the sensor nodes can be listed as(S1,S2,S3,…,Sm). These sensor nodes report sensing data at a certain time interval. At time ti, all the reported data constitute a time series S(ti)=(S1ti,S2ti,S3ti,…,Smti). Data sensed at many contiguous moments form a random process S(t), as shown in Figure 2. Assuming that certain sensor data loses at tn, we analyze its average correlation with the former time series to determine the optimal sample data:(2)R=1n-t_k∑j=n-1t_kRssStn,Stjobjective:min⁡ksubject  to:R=max⁡R.Figure 2
Select sample data.As validated by practical data, the correlation of time series is basically stable in a short period of time and then follows a decreasing trend. So we can get the most relevant sample datat_k~(n-1) based on formula (2). t_k is determined heuristically which is initially set to n-1. Correlation between tn and tn-1 is calculated firstly; then, t_k moves forward and the average correlation values are calculated until the average correlation function is maximized. In Figure 2, we can see that t_k=i, so the data between ti~tn-1 are the sample data. Rss which is the value of correlation between two time series can be computed as in the following formula:(3)RssSti,Sti-1=ZtiZti-1T,where Zti is the standardized result of vector S(ti):(4)Zti=normalizeSti=S1tiS1ti2+S2ti2+⋯+Snti2,S2tiS1ti2+S2ti2+⋯+Snti2,…,SntiS1ti2+S2ti2+⋯+Snti2.The pseudocode of selecting process is described as in Algorithm1.Algorithm 1:Procedure SelectSampleData.
Input:
S
m
×
t: matrix of sensor data
Output:
S
m
×
(
t
-
i
+
1
): a collection of sample data
Main Steps:
(1)Zt←normalizeSt
(2)R←0
(3)for i=t-1 to 1 do
(4) Zi←normalizeSj
(5) RssSt,Si←ZtZiT
(6) R_last←R
(7) R←(R+Rss(St,Si))/(t-i)
(8) if R<R_last
(9)    return i;
(10) end for


### 4.2. Spatial Correlation

Definition 1.
If the sample datasets (data sensed betweenti~tn-1) reported by sensor nodes i, j are Si and Sj, data dissimilarity of these two nodes is d_diff(Sitn,Sjtn)=Si-Sj, the collections of lost data are Si_miss and Sj_miss, the frequency of data loss at the same time is d_miss(Sitn,Sjtn)=Si_miss∩Sj_miss, and the size of sample data is sample_size=Si=Sj.Definition 2.
The distance between sensor nodesSi and Sj is d(Sit,Sjt) at t:(5)dSit,Sjt=d_diffSit,Sjt2+d_missSit,Sjt2sample_size,dSit,Sit=1.
IfSj loses data with the estimated node Si at the same time t, then d(Sit,Sjt)=1. For example, in Figure 3, sensor node 3 will be estimated at tn. If there are missing data of a node i (i=1,2,4,…,n) at tn, then d(Sitn,S3tn)=1.Figure 3
Spatial correlation.As shown in Figure3, in order to estimate missing data of sensor node S3, distance between S3 and all the other nodes S1,S2,S4,…,Sm will be computed to get an array d(S3tn)=[dS1tn,S3tn,dS2tn,S3tn,…,d(Smtn,S3tn)]. Select the nodes whose distance from S3 is smaller than the threshold value (the default is 0.2 in this paper) according to d(S3tn). These selected sensor nodes which have strong spatial correlation with node S3 compose the collection S_Correlate.Each node inS_Correlate estimates the missing data based on its instantaneous rate of change at tn. Different weights are distributed to them according to the spatial correlation. The spatial correlation estimation is computed by the following:(6)V_Spatial=∑Siwi∗Vsjtn-1∗dVSitndtnSi∈S_Correlate,where Si is the sensor node in S_Correlate. VSj(tn-1) is the value of node Sj at the first moment before tn. dVSitn/dtn is the instantaneous change rate of the relevant node Si at tn which can be approximated as the change rate between tn and tn-1; that is, dVSitn/dtn=VSitn-VSitn-1/tn-tn-1 .w
i is the weight corresponding to Si, which is determined by the average correlation coefficient between the sensor nodes. The way to calculate wi is shown in the following: (7)wi=ψSi,SjSCorrelate=cov⁡Si,Sjσsi∗σsj∗SCorrelate=ESi-ESi∗Sj-ESjσsi∗σsj∗S_Correlate.The pseudocode of analysis in spatial correlation is described as in Algorithm2.Algorithm 2:Procedure AnalysisInSpace.
Input:
S
m
×
(
t
-
i
+
1
): sample data
S
miss: estimated sensor node
V: threshold of distance
Output:
V
_
Spatial: estimation value in spatial dimension
Main Steps:
(1)V_Spatial←0
(2)for k=t to t-i+1 do
(3)   d_S3t-k+1←dSk,Smiss
(4)   if d_S3t-k+1<=V
(5)    Sk∈S_Correlate
(6)   end if
(7)end for
(8)for each Sk∈S_Correlate
(9) wk⟵ψSk,SmissSCorrelate
(10)rk⟵dVSktdt
(11)V_Spatial←V_Spatial+wk∗rk∗Vsmiss(tn-1)
(12) end for


### 4.3. Temporal Correlation

As shown in Figure4, we estimate the missing data based on historical sample data of the estimated node. Evaluated result is obtained by a comprehensive measure on the variation of sample data. Change rate of data is defined as rtn:(8)rtn=∇Vtntn-tn-1=Vtn-Vtn-1tn-tn-1,where Vtn is the sensing data of the estimated node at tn.Figure 4
Temporal correlation.Change rates of all sample data are computed, and different weightswtn are given to them; then, we can get the weighted rate of change rw:(9)rw=∑rt∗wt.Based on the weighted rate of change and value of the estimated node attn-1, we can get the temporal estimation V_Temple:(10)V_Temple=Vtn-1+rw∗tn-tn-1.The way to calculate the weighted rate of change is listed in Table1, where rt is the rate of change. wt based on the sequence is assigned to each rt. The pseudocode of analysis in temporal correlation is described in Algorithm 3.Table 1
Weighted rate of change.
Time
t
n
-
1
t
n
-
2
t
n
-
3
t
n
-
4
⋯
t
i
Data
V
t
n
-
1
V
t
n
-
2
V
t
n
-
3
V
t
n
-
4
⋯
Vt
i
r
t
∇
V
t
n
-
1
t
n
-
1
-
t
n
-
2
∇
V
t
n
-
2
t
n
-
2
-
t
n
-
3
∇
V
t
n
-
3
t
n
-
3
-
t
n
-
4
⋯
∇
V
t
i
+
1
t
i
+
1
-
t
i
w
t
n
-
i
-
1
∑
k
=
1
n
-
i
-
1
k
n
-
i
-
2
∑
k
=
1
n
-
i
-
1
k
n
-
i
-
3
∑
k
=
1
n
-
i
-
1
k
⋯
1
∑
k
=
1
n
-
i
-
1
kAlgorithm 3:Procedure AnalysisInTime.
Input:
S
miss
×
(
t
-
i
+
1
): sample data of estimated sensor node
Output:
V_Temple: estimation value in temporal dimension
Main Steps:
(1)for j=t-1 to i do
(2) rtj⟵∇Vtjtj-tj-1
(3) wtj⟵j+1-i∑k=1n-ik
(4)end for
(5)rw←∑rtj∗wtj
(6)V_Temple←Vtn-1+rw∗tn-tn-1


### 4.4. Discussion

Unlike traditional missing data [20], sensor data have five typical patterns of missing [16] which areElement Random Loss,Block Random Loss,Element Frequent Loss in Row,Successive Elements Loss in Row, andCombinational Loss, as shown in Figure 5. The algorithm in this paper usesCombinational Loss mode, that is, any combination of the first four modes. In order to improve the applicability of our algorithm, we take a certain strategy to make the algorithm suitable for some serious loss situations. This algorithm estimates missing values from the spatiotemporal aspects, so severe loss mainly shows up as rows or columns missing continuously.Figure 5
Data loss patterns in WSN (the black cells represent missing data).
(a)
Element Random Loss
(b)
Block Random Loss
(c)
Element Frequent Loss in Row
(d)
Successive Elements Loss in RowAs for severe data loss in time series, if data missing rate of a time series exceeds a certain threshold (the default is 40% in this paper), this time series will be ignored and we move forward to select sample data. As shown in Figure6(a), the loss of time series at tn-2 is serious, so this moment will be ignored in the selection process of the sample data.Figure 6
Severe data loss patterns in this paper (the black cells represent missing data).
(a)
Severe data loss in time series
(b)
Severe data loss in sample dataIf data missing rate of the estimated sensor node does not exceed the threshold (the default is 50% in this paper), missing data will be ignored and the algorithm described before will be used to estimate the missing data directly. If the missing rate of sample data exceeds the threshold, the algorithm will obtain the final result through iteration. As shown in Figure6(b), node 6 has a serious lack of sample data. Compute the values of node 6 at tn-6, tn-5, tn-3, and tn-2 in turn until the missing rate is less than the threshold. Every iteration is conducted based on the results of last estimation. So if the result of previous estimation is not accurate enough, the estimation error in the next time will increase. However, the algorithm in this paper avoids the iteration in spatial correlation analysis by calculating the distance. Iteration occurs only in temporal correlation analysis. From the simulation results in the fifth section, it can be seen that the iterative error of our algorithm is small.


## 4.1. Select Sample Data

The relationship between the sensor nodes in WSN will change over time, so analyzing different sample data will generate different relationship, and we get different assessment values. In addition, the size of sample data will have a great impact on the assessment results. Due to the interference of environmental noise, too little sample data cannot reflect the spatiotemporal correlation of sensor data fully, while excessive sample data reflect the average value over an extended period of time rather than the instantaneous correlation which will reduce the accuracy of the assessment. Therefore, the values and the size of sample data should be determined as accurately as possible.Considering the fact that the spatiotemporal correlation of sensor data approximately remains constant in a short period of time, when we assess the missing data attn, data close to tn should be selected accurately as the sample.In WSN, sensor nodes are deployed in the given area. All the sensor nodes can be listed as(S1,S2,S3,…,Sm). These sensor nodes report sensing data at a certain time interval. At time ti, all the reported data constitute a time series S(ti)=(S1ti,S2ti,S3ti,…,Smti). Data sensed at many contiguous moments form a random process S(t), as shown in Figure 2. Assuming that certain sensor data loses at tn, we analyze its average correlation with the former time series to determine the optimal sample data:(2)R=1n-t_k∑j=n-1t_kRssStn,Stjobjective:min⁡ksubject  to:R=max⁡R.Figure 2
Select sample data.As validated by practical data, the correlation of time series is basically stable in a short period of time and then follows a decreasing trend. So we can get the most relevant sample datat_k~(n-1) based on formula (2). t_k is determined heuristically which is initially set to n-1. Correlation between tn and tn-1 is calculated firstly; then, t_k moves forward and the average correlation values are calculated until the average correlation function is maximized. In Figure 2, we can see that t_k=i, so the data between ti~tn-1 are the sample data. Rss which is the value of correlation between two time series can be computed as in the following formula:(3)RssSti,Sti-1=ZtiZti-1T,where Zti is the standardized result of vector S(ti):(4)Zti=normalizeSti=S1tiS1ti2+S2ti2+⋯+Snti2,S2tiS1ti2+S2ti2+⋯+Snti2,…,SntiS1ti2+S2ti2+⋯+Snti2.The pseudocode of selecting process is described as in Algorithm1.Algorithm 1:Procedure SelectSampleData.
Input:
S
m
×
t: matrix of sensor data
Output:
S
m
×
(
t
-
i
+
1
): a collection of sample data
Main Steps:
(1)Zt←normalizeSt
(2)R←0
(3)for i=t-1 to 1 do
(4) Zi←normalizeSj
(5) RssSt,Si←ZtZiT
(6) R_last←R
(7) R←(R+Rss(St,Si))/(t-i)
(8) if R<R_last
(9)    return i;
(10) end for


## 4.2. Spatial Correlation

Definition 1.
If the sample datasets (data sensed betweenti~tn-1) reported by sensor nodes i, j are Si and Sj, data dissimilarity of these two nodes is d_diff(Sitn,Sjtn)=Si-Sj, the collections of lost data are Si_miss and Sj_miss, the frequency of data loss at the same time is d_miss(Sitn,Sjtn)=Si_miss∩Sj_miss, and the size of sample data is sample_size=Si=Sj.Definition 2.
The distance between sensor nodesSi and Sj is d(Sit,Sjt) at t:(5)dSit,Sjt=d_diffSit,Sjt2+d_missSit,Sjt2sample_size,dSit,Sit=1.
IfSj loses data with the estimated node Si at the same time t, then d(Sit,Sjt)=1. For example, in Figure 3, sensor node 3 will be estimated at tn. If there are missing data of a node i (i=1,2,4,…,n) at tn, then d(Sitn,S3tn)=1.Figure 3
Spatial correlation.As shown in Figure3, in order to estimate missing data of sensor node S3, distance between S3 and all the other nodes S1,S2,S4,…,Sm will be computed to get an array d(S3tn)=[dS1tn,S3tn,dS2tn,S3tn,…,d(Smtn,S3tn)]. Select the nodes whose distance from S3 is smaller than the threshold value (the default is 0.2 in this paper) according to d(S3tn). These selected sensor nodes which have strong spatial correlation with node S3 compose the collection S_Correlate.Each node inS_Correlate estimates the missing data based on its instantaneous rate of change at tn. Different weights are distributed to them according to the spatial correlation. The spatial correlation estimation is computed by the following:(6)V_Spatial=∑Siwi∗Vsjtn-1∗dVSitndtnSi∈S_Correlate,where Si is the sensor node in S_Correlate. VSj(tn-1) is the value of node Sj at the first moment before tn. dVSitn/dtn is the instantaneous change rate of the relevant node Si at tn which can be approximated as the change rate between tn and tn-1; that is, dVSitn/dtn=VSitn-VSitn-1/tn-tn-1 .w
i is the weight corresponding to Si, which is determined by the average correlation coefficient between the sensor nodes. The way to calculate wi is shown in the following: (7)wi=ψSi,SjSCorrelate=cov⁡Si,Sjσsi∗σsj∗SCorrelate=ESi-ESi∗Sj-ESjσsi∗σsj∗S_Correlate.The pseudocode of analysis in spatial correlation is described as in Algorithm2.Algorithm 2:Procedure AnalysisInSpace.
Input:
S
m
×
(
t
-
i
+
1
): sample data
S
miss: estimated sensor node
V: threshold of distance
Output:
V
_
Spatial: estimation value in spatial dimension
Main Steps:
(1)V_Spatial←0
(2)for k=t to t-i+1 do
(3)   d_S3t-k+1←dSk,Smiss
(4)   if d_S3t-k+1<=V
(5)    Sk∈S_Correlate
(6)   end if
(7)end for
(8)for each Sk∈S_Correlate
(9) wk⟵ψSk,SmissSCorrelate
(10)rk⟵dVSktdt
(11)V_Spatial←V_Spatial+wk∗rk∗Vsmiss(tn-1)
(12) end for


## 4.3. Temporal Correlation

As shown in Figure4, we estimate the missing data based on historical sample data of the estimated node. Evaluated result is obtained by a comprehensive measure on the variation of sample data. Change rate of data is defined as rtn:(8)rtn=∇Vtntn-tn-1=Vtn-Vtn-1tn-tn-1,where Vtn is the sensing data of the estimated node at tn.Figure 4
Temporal correlation.Change rates of all sample data are computed, and different weightswtn are given to them; then, we can get the weighted rate of change rw:(9)rw=∑rt∗wt.Based on the weighted rate of change and value of the estimated node attn-1, we can get the temporal estimation V_Temple:(10)V_Temple=Vtn-1+rw∗tn-tn-1.The way to calculate the weighted rate of change is listed in Table1, where rt is the rate of change. wt based on the sequence is assigned to each rt. The pseudocode of analysis in temporal correlation is described in Algorithm 3.Table 1
Weighted rate of change.
Time
t
n
-
1
t
n
-
2
t
n
-
3
t
n
-
4
⋯
t
i
Data
V
t
n
-
1
V
t
n
-
2
V
t
n
-
3
V
t
n
-
4
⋯
Vt
i
r
t
∇
V
t
n
-
1
t
n
-
1
-
t
n
-
2
∇
V
t
n
-
2
t
n
-
2
-
t
n
-
3
∇
V
t
n
-
3
t
n
-
3
-
t
n
-
4
⋯
∇
V
t
i
+
1
t
i
+
1
-
t
i
w
t
n
-
i
-
1
∑
k
=
1
n
-
i
-
1
k
n
-
i
-
2
∑
k
=
1
n
-
i
-
1
k
n
-
i
-
3
∑
k
=
1
n
-
i
-
1
k
⋯
1
∑
k
=
1
n
-
i
-
1
kAlgorithm 3:Procedure AnalysisInTime.
Input:
S
miss
×
(
t
-
i
+
1
): sample data of estimated sensor node
Output:
V_Temple: estimation value in temporal dimension
Main Steps:
(1)for j=t-1 to i do
(2) rtj⟵∇Vtjtj-tj-1
(3) wtj⟵j+1-i∑k=1n-ik
(4)end for
(5)rw←∑rtj∗wtj
(6)V_Temple←Vtn-1+rw∗tn-tn-1


## 4.4. Discussion

Unlike traditional missing data [20], sensor data have five typical patterns of missing [16] which areElement Random Loss,Block Random Loss,Element Frequent Loss in Row,Successive Elements Loss in Row, andCombinational Loss, as shown in Figure 5. The algorithm in this paper usesCombinational Loss mode, that is, any combination of the first four modes. In order to improve the applicability of our algorithm, we take a certain strategy to make the algorithm suitable for some serious loss situations. This algorithm estimates missing values from the spatiotemporal aspects, so severe loss mainly shows up as rows or columns missing continuously.Figure 5
Data loss patterns in WSN (the black cells represent missing data).
(a)
Element Random Loss
(b)
Block Random Loss
(c)
Element Frequent Loss in Row
(d)
Successive Elements Loss in RowAs for severe data loss in time series, if data missing rate of a time series exceeds a certain threshold (the default is 40% in this paper), this time series will be ignored and we move forward to select sample data. As shown in Figure6(a), the loss of time series at tn-2 is serious, so this moment will be ignored in the selection process of the sample data.Figure 6
Severe data loss patterns in this paper (the black cells represent missing data).
(a)
Severe data loss in time series
(b)
Severe data loss in sample dataIf data missing rate of the estimated sensor node does not exceed the threshold (the default is 50% in this paper), missing data will be ignored and the algorithm described before will be used to estimate the missing data directly. If the missing rate of sample data exceeds the threshold, the algorithm will obtain the final result through iteration. As shown in Figure6(b), node 6 has a serious lack of sample data. Compute the values of node 6 at tn-6, tn-5, tn-3, and tn-2 in turn until the missing rate is less than the threshold. Every iteration is conducted based on the results of last estimation. So if the result of previous estimation is not accurate enough, the estimation error in the next time will increase. However, the algorithm in this paper avoids the iteration in spatial correlation analysis by calculating the distance. Iteration occurs only in temporal correlation analysis. From the simulation results in the fifth section, it can be seen that the iterative error of our algorithm is small.


## 5. Performance Evaluation

The algorithm proposed in this paper is evaluated over real-world data, namely, Intel-lab dataset [21]. This dataset is a trace of readings from 54 sensor nodes deployed in the Intel Research Berkeley Lab. These sensor nodes collected light, humidity, temperature, and other information once every 30 s from February 28 to April 5, 2004.Since the original dataset contains missing values, in order to evaluate the performance of the algorithm, we select the relatively complete part of the test data through deleting sensor nodes which contain serious data loss. For example, when the sampling interval is set to five minutes, there is a serious lack of sensor data in nodes 5 and 15 (with 90% of data lost). So data of these two sensor nodes will not be selected as sample. In this paper, we use the accuracy of the estimation as the evaluation criteria. Specifically, we use Root Mean Square Error (RMSE):(11)RMSE=averageVsjti-V′sjti2,where Vsjti is the known value which is assumed as missing data.V′sjti is the estimated value of Vsjti.To verify the effectiveness of the algorithm proposed in this paper, we compare it against other algorithms—AMR [12], TRECI [17], DESM [18], and MASTER [19].


### 5.1. Convergence

Loss rate of raw data is about 5%. We verify the validity of the first step in this algorithm on the original temperature dataset where the sampling interval is set to 5 min. By calculating the average correlation, it can be known that the size of the sample data is 13. We choose a different number of data, and accuracy comparison of results is shown in Figure7. It shows that a small or too large amount of data will cause an increase in the error rate. So we choose the smallest advisable size to ensure the accuracy while reducing the complexity of the algorithm. In Figure 8, we compare different algorithms against the size of required sample converging to the optimal solution. It can be seen that TSCA converges fast and has the best performance.Figure 7
RMSE versus the size of sample data.Figure 8
Convergence.


### 5.2. Estimation on Temperature

Error rate is compared among different algorithms on the original dataset where different sampling intervals are set, as shown in Figure9. The spatiotemporal correlation of temperature is strong, so MASTER can obtain accurate relationships based on mining correlation rules. But a few of sensor nodes which are not associated with others will increase the estimation error, so its error is slightly larger than TSCA. As the sampling interval increases, temporal correlation of the sensor data weakens. TRECI and DESM use temporal correlation, so estimation error increases. However, the increase of DESM is slight because it also considers spatial correlation. The spatial correlation of the indoor sensor node in a short period of time remains substantially constant, so the sampling interval has little effect on AMR which only considers the spatial correlation. Particularly, TSCA takes the temporal and spatial correlation into account and assigns different weights according to the time series of data which makes newer data playing a more important role in the evaluation, so the size of the sampling interval has less effect on the results.Figure 9
RMSE versus sampling interval on temperature.According to [16], 23% of data are lost among 84,600 time slots (one month) of Intel Indoor dataset. Therefore, we conduct the error comparison among different algorithms where data missing rate is set as 5%–35% and the sampling interval is set as 5 min. Figure 10 shows that error of all the algorithms increases with the missing rate. This is because spatiotemporal correlation of sensor data will become weaker as missing rate increases. However, TSCA takes corresponding strategies based on the patterns of data loss as described in Section 4 which reduces errors greatly.Figure 10
RMSE versus data loss on temperature.


### 5.3. Estimation on Humidity

Error of humidity estimation is compared among different algorithms on the original dataset where the sampling intervals are set as 1–30 min, as shown in Figure11. Compared with temperature, spatiotemporal correlations of humidity are weaker, and the spatial correlation is much weaker than the temporal one. AMR is only based on the spatial correlation, so its error is maximal. Like temperature, temporal correlation of the sensor data weakens with the sampling interval increasing. TRECI is mainly based on temporal correlation so its error increases remarkably. When the sampling interval reaches 30 min, error of TRECI exceeds AMR algorithm’s. Results of the other three algorithms are similar, but the error of TSCA is still the smallest.Figure 11
RMSE versus sampling interval on humidity.Figure12 shows error rate in the situation of different data loss probability. When loss rate is more than 20%, spatial and temporal correlations of humidity are severely affected and error rate of DESM, TRECI, and AMR surges. Loss rate has a greater impact on the temporal correlation, so error rate of TRECI increases more significantly. TSCA is mainly based on the latest data and the missing data in the sample have been processed, so its performance remains relatively stable.Figure 12
RMSE versus data loss on humidity.


## 5.1. Convergence

Loss rate of raw data is about 5%. We verify the validity of the first step in this algorithm on the original temperature dataset where the sampling interval is set to 5 min. By calculating the average correlation, it can be known that the size of the sample data is 13. We choose a different number of data, and accuracy comparison of results is shown in Figure7. It shows that a small or too large amount of data will cause an increase in the error rate. So we choose the smallest advisable size to ensure the accuracy while reducing the complexity of the algorithm. In Figure 8, we compare different algorithms against the size of required sample converging to the optimal solution. It can be seen that TSCA converges fast and has the best performance.Figure 7
RMSE versus the size of sample data.Figure 8
Convergence.


## 5.2. Estimation on Temperature

Error rate is compared among different algorithms on the original dataset where different sampling intervals are set, as shown in Figure9. The spatiotemporal correlation of temperature is strong, so MASTER can obtain accurate relationships based on mining correlation rules. But a few of sensor nodes which are not associated with others will increase the estimation error, so its error is slightly larger than TSCA. As the sampling interval increases, temporal correlation of the sensor data weakens. TRECI and DESM use temporal correlation, so estimation error increases. However, the increase of DESM is slight because it also considers spatial correlation. The spatial correlation of the indoor sensor node in a short period of time remains substantially constant, so the sampling interval has little effect on AMR which only considers the spatial correlation. Particularly, TSCA takes the temporal and spatial correlation into account and assigns different weights according to the time series of data which makes newer data playing a more important role in the evaluation, so the size of the sampling interval has less effect on the results.Figure 9
RMSE versus sampling interval on temperature.According to [16], 23% of data are lost among 84,600 time slots (one month) of Intel Indoor dataset. Therefore, we conduct the error comparison among different algorithms where data missing rate is set as 5%–35% and the sampling interval is set as 5 min. Figure 10 shows that error of all the algorithms increases with the missing rate. This is because spatiotemporal correlation of sensor data will become weaker as missing rate increases. However, TSCA takes corresponding strategies based on the patterns of data loss as described in Section 4 which reduces errors greatly.Figure 10
RMSE versus data loss on temperature.


## 5.3. Estimation on Humidity

Error of humidity estimation is compared among different algorithms on the original dataset where the sampling intervals are set as 1–30 min, as shown in Figure11. Compared with temperature, spatiotemporal correlations of humidity are weaker, and the spatial correlation is much weaker than the temporal one. AMR is only based on the spatial correlation, so its error is maximal. Like temperature, temporal correlation of the sensor data weakens with the sampling interval increasing. TRECI is mainly based on temporal correlation so its error increases remarkably. When the sampling interval reaches 30 min, error of TRECI exceeds AMR algorithm’s. Results of the other three algorithms are similar, but the error of TSCA is still the smallest.Figure 11
RMSE versus sampling interval on humidity.Figure12 shows error rate in the situation of different data loss probability. When loss rate is more than 20%, spatial and temporal correlations of humidity are severely affected and error rate of DESM, TRECI, and AMR surges. Loss rate has a greater impact on the temporal correlation, so error rate of TRECI increases more significantly. TSCA is mainly based on the latest data and the missing data in the sample have been processed, so its performance remains relatively stable.Figure 12
RMSE versus data loss on humidity.


## 6. Conclusion

Considering the deficiencies of the existing algorithms for missing data assessment, TSCA is proposed in this paper based on spatiotemporal correlation of sensor data. This algorithm selects the most relevant data as the analysis sample which ensures that there are no redundant sample data and the sample has the strongest correlation with the missing data. Thus, the efficiency and accuracy of this algorithm are significantly improved. What is more, a comprehensive analysis of the time and space is conducted to get estimation for missing data. Experimental results show that, no matter what the cases, TSCA always performs the best compared with other algorithms.In the future, we can exploit the correlations between different attributes to further improve the accuracy of estimation; for example, light has an impact on temperature in many scenarios.



---

*Source: 435391-2015-10-29.xml*