## 6 Performance Evaluation
### Efficiency Evaluation  
In this subsection, we measure the performance of the proposed _K_NN algorithm and the PNNQ approach in terms of the CPU time and the number of accessed cells of grid index. Four experiments are conducted to investigate the effects of four important factors on the performance of processing the KNN query. These important factors include the _distribution of objects_, the _number of object_, the _time_\(T_{u}\)_at which object changes its location_, and the _value of K_. The first experiment studies how the distribution of objects affects the performance of KNN and PNNQ by considering three types of object distributions. These object distributions are the _uniform distribution_, the _Gaussian distribution_ (with variance 0.05 and a mean being the coordinate of the center), and the _Zipf distribution_ (with skew coefficient 0.8). Note that hereafter all figures use a logarithmic scale for the _y_-axis. As shown in Figure 8a, the CPU time of both approaches for the uniform distribution is slightly lower than that for the Gaussian and Zipf distributions. This is because for the Gaussian and Zipf distributions, the objects are closer to each other (compared to the uniform distribution) so that more CPU time is required to find the _K_NN result. As for the number of accessed cells, Figure 8b indicates that when the objects follow the Zipf distribution, the KNN approach requires a little more accessed cells (comparing to the uniform and Gaussian distributions). For the PNNQ approach, the number of accessed cells remains constant regardless of the object distribution. The main reason is that PNNQ is performed without the grid index support so that all the grid cells need to be accessed. From the above experimental results, we know that the KNN approach significantly outperforms the PNNQ approach. Figure 9 illustrates the performance of the KNN and PNNQ approaches as a function of the number of objects (ranging from 0.1 K to 200 K), in terms of the CPU overhead and the number of accessed cells. As shown in Figure 9a, the CPU time for both approaches increases with the increase of object number because more distance computations of objects are required for finding the _K_NN result. Nevertheless, the KNN approach significantly outperforms the PNNQ approach in all cases. This is mainly because for the PNNQ approach the distances of all objects have to be computed which incurs high computation cost as the object number increases, whereas for the KNN approach the unnecessary distance computation of these objects can be avoided by applying the designed pruning criteria and the support of grid index. The experimental result in Figure 9b illustrates that the number of accessed for the PNNQ approach remains constant in all cases. This is because no matter what the object quantity is, for the PNNQ approach all cells need to be accessed. An interesting observation from Figure 9b is that \begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameter** & **Default** & **Range** \\ \hline Object distribution & uniform & uniform, Gaussian, zipf \\ Object number (K) & 100 & 0.1, 1, 10, 100, 200 \\ \(T_{u}\) & 15 & 5, 10, 15, 20, 25 \\ \(K\) & 10 & 1, 5, 10, 15, 20 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: System parameters. a larger number of objects results in a lower number of cells that need to be accessed in processing the KNN query. The main reason is that when the sensor network is sparse (e.g., object number is 0.1 K or 1 K), more cells have to be accessed so as to find the \(K^{\text{th}}\) NN, while a dense network (e.g., object number is 200 K) may lead to early termination of finding the \(K^{\text{th}}\) NN so that fewer cells are accessed. In the following, we demonstrate the efficiency of the proposed algorithm by studying the effect of the update interval (_i.e._, the value of \(T_{u}\)) on the query performance.