## 3 A Sub-Clustering Algorithm Based on Spatial Data Correlation
### Sub-Clustering to be Virtual Clusters  
In order for more energy savings to keep fewer sensor nodes radio on, or say to avoid idle listening, we further partition (sub-clustering) the physical cluster based on the spatial data correlation of sensor nodes. The sensor nodes with high spatial data correlation are formed into a virtual cluster and only the representative nodes keep their radio on. Here, our sub-clustering algorithm is composed of two procedures: virtual cluster head selection procedure (VCHS procedure) and virtual cluster construction procedure (VCC procedure). Even though large number of sensor nodes may turn their radio off, the network reachability in our algorithm is still preserved since the underlying hierarchical routing protocol is responsible for it. At the specified sample time stamp \(t_{k}\), \(pch\) has received the sets of concrete data readings \((R_{s}(t_{1}),R_{s}(t_{2}),...,R_{s}(t_{k}))\) of sensor node \(s\in S\) where \(S\) is the set of cluster members of \(pch\). The communication hop counts between sensor nodes \(s\in S\) are one or more which is depending on the underlying hierarchical routing protocol. Since we intend to separate the set \(S\) into several virtual clusters depending on the spatial data correlation, the calculation of correlation tries to identify in what degree a node \(x\in S\) is correlated with its neighbors \(y=\{y|\ y\in N(x)\}\) where \(N(x)\) is denoted as the set of node \(x\)'s neighbors belonging to \(S\). The data readings of \(x\) and \(y\) are denoted as \((R_{x}(t_{1}),R_{x}(t_{2}),...,R_{x}(t_{k}))\) and \((R_{y}(t_{1}),R_{y}(t_{2}),...,R_{y}(t_{k}))\), respectively. We define \(d_{xy}\) as the difference (distance) between the data readings of node \(x\) and \(y\) by the Euclidean distance:  
Figure 2: Using \(k\) concrete data readings to forecast the next \(\Delta\) data readings. \[d_{xy}=\sqrt{\left|R_{x}(t_{1})-R_{y}(t_{1})\right|^{2}+\left|R_{x}(t_{2})-R_{y}( t_{2})\right|^{2}+\cdots+\left|R_{x}(t_{k})-R_{y}(t_{k})\right|^{2}} \tag{3}\]  
Then, the expected value of \(d_{xy}\) is  
\[E\big{(}d_{xy}\big{)}=\overline{d_{x}}=\frac{1}{\left|N(x)\right|}\sum_{y\in N (x)}d_{xy} \tag{4}\]  
where \(\left|N(x)\right|\) is the number of nodes in \(N(x)\). Also, the deviation of \(d_{xy}\) is \(D\big{(}d_{xy}\big{)}\):  
\[D\big{(}d_{xy}\big{)} =E\left\{\left[d_{xy}-E\big{(}d_{xy}\big{)}\right]^{2}\right\}= \frac{1}{\left|N(x)\right|}\sum_{y\in N(x)}\big{(}d_{xy}-\overline{d_{x}} \big{)}^{2}=E\big{(}d_{xy}^{2}\big{)}-\left[E\big{(}d_{xy}\big{)}\right]^{2} \tag{5}\] \[=\frac{1}{\left|N(x)\right|}\sum_{y\in N(x)}d_{xy}^{2}-\overline {d_{x}}^{2}\]  
In order to find out a measurement of spatial correlated weight for each node \(x\in S\), we further define the weight \(scw_{x}\) of node \(x\) as  
\[scw_{x}=\frac{\left[\sum_{y\in N(x)}\big{|}d_{xy}-\overline{d_{x}}\big{|} \right]^{2}}{\left|N(x)\right|^{2}D\big{(}d_{xy}\big{)}}=\frac{\left[\sum_{y \in N(x)}\big{|}d_{xy}-\overline{d_{x}}\big{|}\right]^{2}}{\left|N(x)\right| \sum_{y\in N(x)}(d_{xy}-\overline{d_{x}})^{2}} \tag{6}\]  
According to Cauchy-Schwarz inequality, we have  
\[\left[\sum_{y\in N(x)}\big{|}d_{xy}-\overline{d_{x}}\big{|}\right]^{2}\leq \left|N(x)\right|\sum_{y\in N(x)}(d_{xy}-\overline{d_{x}})^{2} \tag{7}\]  
As the result, \(0\leq scw_{x}\leq 1\). The definition of \(scw_{x}\) takes into consideration the average spatial distance deviation between node \(x\) and \(N(x)\). Thus, the larger value of \(scw_{x}\) is, the smaller difference variation between node \(x\) and \(N(x)\). That is, node \(x\) has higher spatial correlation with \(N(x)\) as its \(scw_{x}\) is larger. Based on the measurements, there are two possible situations when a node should be assigned as a determined/candidate one of virtual cluster head (\(vch\)):  
1. A node has very low \(scw\). (\(lb-vch\), a determined \(vch\) satisfying the predefined lower bound \(scw^{lb}\))
2. A node has very high \(scw\).