## 3 A Sub-Clustering Algorithm Based on Spatial Data Correlation
### Sub-Clustering to be Virtual Clusters
(\(ub-vch\), a candidate \(vch\) satisfying the predefined upper bound \(scw^{ub}\))  
Obviously, nodes being in either of two situations should be conditionally chosen as the representative node for a virtual cluster, depicted in Figure 3a. For the first situation, a node becomes \(lb-vch\) due to its low \(scw\). This means that the data readings of the node are evidently different from its neighbors. Taking into consideration the application accuracy and integrity, a low \(scw\) node should be still awake in monitoring the environment. For the second situation, the upper bound of the weight is used to make sure that the nodes having higher correlation with their neighbors are chosen to be \(ub-vch\)s. However, it is possible that neighboring \(ub-vch\)s are highly correlated. They should be grouped into a virtual cluster, as depicted in Figure 3b. Noted that the \(scw_{x}^{max}\) is calculated at \(pch\) side and possible \(vch\)s are selected in a centralized manner. As to virtual cluster construction (VCC) procedure, the virtual clusters are constructed in a distributed manner oppositely. If a node can join several clusters, it has to choose the nearest \(vch\) to join. The results can refer to Figure 3c. The details of VCC procedure are described as follows. After the virtual cluster construction, the representative nodes have to bear the monitoring responsibility. Meanwhile, the energy consumption for readings transmission is effectively reduced because of the representative mechanism. That is to say, the rest of nodes simultaneously turn their radio and sensing unit off and the energy are further conserved due to the contribution of the representative nodes. Virtual cluster heads selection (VCHS) procedure:  
Input: \((R_{s}(t_{1}),R_{s}(t_{2}),...,R_{s}(t_{k}))\) of sensor node \(s\in S\), lower bound and upper bound of spatial correlated weight \(scw_{x}\) for any node \(x\in S\)  
Output: the set \(V\)', \(V\)' of virtual cluster heads \((vch)\) of \(S\)  
Step1: \(V\)', \(V\)' = \(\emptyset\)  
Step2: calculation of spatial correlated weight \(scw_{x}\) for any node \(x\in S\)  
Step3: on \(lb-vch\) (\(V\)' = \(\emptyset\))  
if \((scw_{x}\leq scw^{lb})\)\(V\)' = \(V\)' + \(x\);  
Step4: on \(ub-vch\) (\(V\)' = \(\emptyset\))  
for each node \(x\), \(scw_{x}^{max}=\max\{scw_{y}\}\)\(y\in N(x)\)  
if \((scw_{x}\geq scw^{ub}\) and \(scw_{x}>scw_{x}^{max})\)\(V\)' = \(V\)'' + \(x\);  
Virtual cluster construction (VCC) procedure:  
Step1: each node \(x\) (\(x\in V\)') broadcasts an _indicator_ message to \(N(x)\)  
Step2: each node \(x\) (\(x\) (\(x\) (\(S-V\)' - \(V\)')) receives no _indicator_ message after a predefined time period, \(x\) broadcasts an indicator message to \(N(x)\)  
Step3: node \(y\) (\(y\) (\(y\) (\(S-V\)' - \(V\)')) joins the virtual cluster of \(x\) (\(VC_{x}\)):  
3-1: if \(y\) receives only one _indicator_ message from \(x\)  
3-2: if \(y\) receives more than two _indicator_ messages from \(N(y)\), then it joins \(VC_{x}\) if \(d_{xy}=\min\{d_{xy}\}\)  
Figure 3: The role transition of nodes during virtual cluster construction (VCC) process. **(a)** sensor nodes within a physical cluster; **(b)** some _ub-vchs_ are absorbed by the _ub-vch_ with max (scw); **(c)** vchs are determined after VCC procedure. Step4: if node \(y\) decides to join \(VC_{x}\), it sends a _join_ message to node \(x\)  
Step5: if node \(x\) receives a _join_ message, it sends back an _acknowledge_ message to \(y\). Hence \(x\) is the virtual cluster head (\(vch\)) of \(VC_{x}\) and \(y\) is a member of \(VC_{x}\).