## 3 Basic System Operation
### SBD Routing
The rest of the head nodes: \(SH_{j+1}\), \(SH_{j+2}\), \(\ldots\), \(SH_{k-1}\) pull data from all of their member nodes. Figure 8: Range query example. Suppose, Figure 8, \(hq\) is the hash value of the query (\(q\), \(r\)). Hence, the range of the hash is [\(h_{q}-r\), \(h_{q}+r\)], where \(h_{q}-r\) belongs to \((i-1)th\) sector and \(h_{q}+r\) belongs to \(i+1\)th sector. Thus the target head nodes are \((i-1)\)th, \(i\)th, \((i+1)\)th sectors. Furthermore, within \((i-1)th\) sector, data is fetched from the member nodes of \(\{r_{i}^{th}\}_{i=t}^{r}\) segments, where \(\mathrm{P}_{M_{i-1}(i)}\leq h_{q-r}\leq\mathrm{P}_{M_{i-1}(i+1)}\). On the other hand, within \((i+1)th\) sector data is fetched from the sensor nodes of \(\{r_{i}^{th}\}_{i=1}^{t}\) segments, where \(\mathrm{P}_{M_{i+1}(i)}\leq h_{q+r}\leq\mathrm{P}_{M_{i+1}(i+1)}\). Finally, within \(i\)th segment, data is fetched from the whole sector. #### 3.6.2 K-Nearest Neighbor Query

Like _range_ query, a query node first calculates hash \(h_{q}\) using Equation (28) for _K-nearest Neighbor Query_ denoted by _KNN_ (\(q\), \(k\)). Here, \(q\) is defined by an \(l\)-dimensional tuple (\(q_{1}\), \(q_{2}\), \(q_{3}\), \(\ldots\), \(q_{l}\)) where \(q_{g},\forall_{g}\in\left[\! [l,l]\!\right]\), denotes the query value of \(g\)th attribute and \(k\) is the number of nearest neighbor nodes containing similar data to \(q\). Thus the _KNN_ (\(q\), \(k\)) is first forwarded to the target sector head node, denoted by _SHi_, where \(P_{i}\leq h_{q}\leq P_{i+1}\). The _KNN_ retrieval protocol is iterative. The SH scans through its segmentation table and includes the closest segment one after another until the following condition is true:

\[\sum_{j=1}^{z}\Phi_{j}\geq k,\ \ where\ \ \ z\leq r \tag{29}\]

In Equation (29), \(\Phi_{j}\) denotes the total number of member nodes in the \(j\)th segment of the target \(i\)th sector. The _SHi_ then broadcast a query request to all the member nodes of the \(\{j^{th}\}_{j=1}^{z}\) segments. The member nodes of the corresponding segments respond to the query request. The _SHi_ accumulates the received responses and sends them to the source query node. Figure 9 shows an example of _K-Nearest Neighbor Query with the value of \(K=9\). Figure 9: The _KNN_(\(q\), 9)—nearest neighbor nodes containing similar data to \(q\) inside Sth sector are \(m_{1}\), \(m_{3}\), \(m_{14}\), \(m_{17}\), \(m_{8}\), \(m_{10}\), \(m_{4}\), \(m_{9}\), \(m_{5}\). Range Query Example. ## 4 DCSMSS Analysis

### SBD Analysis

This section analyzes the SBD performance in terms of routing message complexity (total number of message transfers in the network). The notations used in this section are summarized in Table 5. For simplicity it is assumed that the data transmission is error-free. Assume that the local sensor sampling and reporting rate to _SH_ is \(a\), the remote update rate is \(l\) and the query rate is \(l\). Let _Cu_, _Cu_ and _Cqr_ be the cost of local update, cost of remote update and cost of getting an answer to a query, respectively. Hence, based on this assumption the overall message routing complexity can be defined as shown in Equations (30) and (31). \[C=\alpha\cdot C_{{}_{\mathrm{x}}}+\lambda\cdot C_{{}_{\mathrm{m}}}+\eta\cdot C _{{}_{\mathrm{r}}} \tag{30.a}\]

\[C=\alpha\cdot C_{{}_{\mathrm{x}}}+\lambda\cdot C_{{}_{\mathrm{m}}}+\eta\cdot 2 \cdot C_{{}_{\mathrm{m}}} \tag{30.b}\]

Figure 6:0

Here, _Crx_ is the transmission cost by a wireless sensor node that covers a transmission range of r inside a sector. For a single remote update issued by _S0_ (represented by track (_t0_) and sector (_s0_)) to _SH_ in _S1_ (_t1_, _s1_), _S2_ (_t2_, _s2_),..., _Sn_ (_tn_, _sn_), SBD sends out \(n\) updates to \(n\) different _SHs_. Let _Cn,to,so,n_ and _Cn,SH_ be the cost of remote update from _S0_ to _S1_, _S2_,..., _Sn_ and transmission cost between two _SH_s, respectively. Hence, the cost of this remote update routing can be given by Equation (26).