## 3 \(l\)-\(k\)-Nearest-Neighbors Query Processing
### Algorithm for Query Dissemination
\begin{table}
\begin{tabular}{c c c} \hline Name & Network Size & Number of Nodes \\ \hline D-300 & 300 \(\times\) 300 m\({}^{2}\) & 300 \\ D-500 & 300 \(\times\) 300 m\({}^{2}\) & 500 \\ D-1000 & 300 \(\times\) 300 m\({}^{2}\) & 1000 \\ \hline \end{tabular}
\end{table} 
Table 1: Summary of datasets. The right figure shows the results for the query accuracy with various datasets, such as D-300, D-500, and D-1000 when \(l\) and \(k\) are set to 30 m and 30, respectively. As the number of total sensor nodes increases, the query accuracy decreases. This result is related to the densities of the datasets. A dataset with high density includes a large number of result sets satisfying \(l\)-\(k\)NN. Therefore, the selected result set has a high probability of being different from the ground truth. Figure 7 shows the results for the query accuracy and latency with various network sizes when the number of nodes, \(l\) and \(k\) are 300, 30 m and 30, respectively. As a network size increases, the query accuracy decreases, but the query latency increases. This performance degradation is because the larger network has sparser regions, where a sparse region has a few number of sensor nodes. Therefore, the \(l\)-\(k\)NN algorithm selects sensor nodes whose distance is larger than the ground truth. Similarly, the query latency shows a similar trend to the query accuracy because the average number of transmissions increases in the large network. Figure 8 shows the results of query accuracy and latency with various values of mobility for each sensor in D-300. This experiment for the impact of moving speeds is evaluated by varying maximum moving speeds from 20 m/s to 35 m/s when \(l\) and \(k\) are set to 30 m and 30, respectively. The left figure shows the query accuracy. As the moving speed increases, the query accuracy decreases. When the

Figure 6: Comparisons of the \(l\)-\(k\)NN accuracy. (**a**) \(l\)-\(k\)NN accuracy with various values of \(l\); (**b**) \(l\)-\(k\)NN accuracy with various datasets. Figure 7: Comparisons of query performance with various network sizes. (**a**) Query accuracy with various network sizes; (**b**) Query latency with various network sizes. moving speed is faster, the selected sensor has a larger distance compared with the ground truth. This is because the selected Q-nodes moves to arbitrary points fast during next Q-nodes are selected. The right figure shows the query latency. The query latency increases rapidly when the moving speed is faster than 30 m/s. This is because the average number of transmissions increases when the moving speed is fast. Figure 9 shows the results of query latency between DIKNN and _l_-kNN for D-300. When the constraint parameters l and k are sufficiently large, the _l_-_k_NN obtains better performance than the DIKNN. When l is smaller than or equal to r (_l_ = 10 m), _l_-_k_NN is slower than DIKNN. This is because DIKNN broadcasts only one time to all sensor nodes within the sensor radio range, but _l_-_k_NN broadcasts _r_/_l_ times. When \(l\) is larger than \(r\) (_l_ = 20 m and \(l\) = 30 m), _l_-_k_NN is faster than DIKNN because DIKNN each time broadcasts, but _l_-_k_NN disseminates the query message to a small number of sensor nodes with GPSR in the _l_-_k_NN. For large enough \(k\), _l_-_k_NN is faster than DIKNN when \(l\) is larger than \(r\). This explanation is similar to that for the results of \(l\). A large k leads DIKNN to perform many broadcasts. Figure 10 shows the results for the energy consumption of _l_-_k_NN with various values of \(l\) and \(k\) for D-300. When \(l\) is equal to \(r\), DIKNN consumes less energy than _l_-_k_NN. However, when \(l\) is larger than \(r\), DIKNN consumes more energy than DIKNN. For large enough \(k\), DIKNN consumes more energy than

Figure 8: Comparisons of query performance with various values of mobility. (**a**) Query accuracy with with various values of mobility; (**b**) Query latency with various values of mobility. Figure 9: Comparisons of the query latency with various values of \(l\) and \(k\).