## 3 A Sub-Clustering Algorithm Based on Spatial Data Correlation
### Constructing Prediction Models  
Perhaps the readings of sensor nodes show high spatial and/or temporal correlation in the monitoring environment. We can predict a sensor node's reading based on the readings of the sensor nodes around it (spatial correlation) or based on itself historical readings (temporal correlation) [16]. Therefore, at the beginning of this procedure, each sensor node in a physical cluster calculates its prediction model according to its historical readings. The prediction models specify the readings at a sensor node as a function of its readings in the past. We suppose that a sensor node has enough memory to store the historical readings. Accordingly, sensor nodes generate their predictions by linear regression [28].  
A sensor node \(s\) measures it's data reading \(R_{s}(t)\) at time \(t\). The prediction model of node \(s\) is denoted as \(\hat{R}_{s}(t)\). Over time, it collects a set of data readings \(\left(R_{s}(t_{1}),R_{s}(t_{2}),...,R_{s}(t_{k})\right)\). With consideration of the characteristics of the application, we may pre-specify a set of basis functions, \(F=\left\{f_{1}(t),f_{2}(t),...,f_{n}(t)\right\}\). In regression, we would like to fit the basis functions \(F\) to those \(k\) data readings, that is, to find basis functions coefficients, \(W=\left(w_{1},w_{2},...,w_{n}\right)^{\top}\). Such that:  
\[\hat{R}_{s}(t)=w_{1}f_{1}(t)+w_{2}f_{2}(t)+\cdots+w_{n}f_{n}(t)=\sum_{i=1}^{n }w_{i}f_{i}(t)\approx R_{s}(t) \tag{1}\]  
where, \(t=t_{1},t_{1}+t^{*},t_{1}+2t^{*},...,t_{k}\), \(t^{*}\) is the frequency of reports requested based on the application and \(t_{k}=t_{1}+(k-1)t^{*}\). To formulize the approximation, we use root mean squared error (RMSE) as the error metric. Hence, the parameters \(W^{*}\) are calculated in order to minimize the RMSE:\[W^{*}=\arg\min_{w}\sqrt{\frac{1}{k}\sum_{i=1}^{k}\left(R_{s}(t)-\hat{R}_{s}(t) \right)^{2}}=\arg\min_{w}\sqrt{\frac{1}{k}\sum_{i=1}^{k}(R_{s}(t)-\sum_{i=1}^{n }w_{i}f_{i}(t))^{2}} \tag{2}\]  
As presented in [28], the basis function coefficients \(W\) can be obtained.  
Subsequently, we use the generated model \(\hat{R}_{s}(t)\) as the predictor for the next \(\Delta\) readings where \(t=t_{k+1},t_{k+2},...,t_{k+\Delta}\). That is to say, during the period (from \(t_{1}+kt^{*}\) to \(t_{1}+(k+\Delta-1)t^{*}\)), the forecasting value \(\hat{R}_{s}(t)\) is conditionally regarded as the concrete reading \(R_{s}(t)\) of sensor node at the \(t^{*}\) interval. If the difference between \(\hat{R}_{s}(t)\) and \(R_{s}(t)\) is within a certain pre-specified error threshold \(\varepsilon\), the sensor node doesn't need to transmit its concrete reading to the cluster head (\(pch\)). The predicted value \(\hat{R}_{s}(t)\) is treated as the concrete reading of sensor node \(s\). It means that the sensor node can reduce transmissions by using prediction model. On the contrary, if the difference is more than \(\varepsilon\), the sensor node needs to send out its concrete reading to \(pch\). Such a predicted value is termed as \"violation\" and the sensor node needs to transmit its concrete reading to \(pch\). After \(\Delta\) readings, the coefficients \(W\) are calculated once again using the last \(k\) readings, as illustrated in Figure 2. And the new obtained \(W\) is sent to \(pch\) and combined with \(F\) to forecast the next \(\Delta\) readings.