## 3 \(l\)-\(k\)-Nearest-Neighbors Query Processing
### \(l\)-\(k\)NN Query Dissemination
One track-sector can contain at most one Q-node, and we can calculate  
Figure 4: Dividing the search space into tracks and sectors. are. Therefore, once the query message reaches a Q-node in a track-sector, the query message escapes this track-sector and heads quickly to the next track-sector containing a Q-node. The query message traverses between only those track-sectors containing Q-nodes. As explained above, the Q-node is selected around the inner corner intersecting the lower arc and the margin sector in a query track. We regard the corners as virtual vertices because we cannot know whether any sensor nodes exist in the corners. The query message is propagated to the virtual vertex along borders of tracks and sectors by itinerary traversal [7]. The Q-node is selected near the virtual vertex. The itinerary traversal selects the next sensor nodes in the range of \(\frac{\sqrt{3}}{2}r\) rather than \(r\) in order to balance query accuracy and energy efficiency [20]. If there is no sensor node near the virtual vertex, we seek the Q-node by routing around the virtual vertex based on the right-hand rule of GPSR. Figure 5a shows an example of query dissemination in a sector, where \(v_{i}\) is a virtual vertex and \(Q_{j}\) is a Q-node. The virtual vertices \(v_{2}\), \(v_{6}\) and \(v_{10}\) are the corners intersecting the lower arc and the margin sector in query tracks. Q-nodes \(Q_{1}\), \(Q_{2}\) and \(Q_{3}\) are the nearest vertices to the virtual vertices, respectively. The query message is propagated from \(Q_{1}\) to \(v_{6}\) and from \(Q_{2}\) to \(v_{10}\) along the borders of the sector and tracks by itinerary traversal. Figure 5b shows an example of the right-hand rule of GPSR. If there is no sensor node near the virtual vertex \(v_{3}\), we try to route around \(v_{3}\) to seek the path from H-node to the next Q-node, \(Q_{2}\). For fast query processing, we adopt parallel computing for query dissemination in each sector. The query dissemination in each sector is an independent subtask. Therefore, this parallelization reduces query latency without accuracy degradation. The number of subtasks has a great effect on the performance. When the number of subtasks is large, network throughput degrades because contentions and collisions occur frequently at the data link and physical layers. Conversely, a small number of subtasks increases latency. Considering this analysis, we determine the number of subtasks as the  
Figure 5: Query dissemination among track-sectors. (**a**) Query dissemination; (**b**) Right-hand rule of GPSR. number \(n_{1}\) of sectors in the first track. Since the query message traverses only the track-sectors containing Q-nodes that are surrounded by margin tracks and sectors, contentions and collisions are minimized in the parallel query dissemination. At the end of dissemination, query responses are aggregated at the H-node. The H-node can take more than k number of Q-nodes because \(l\)-\(k\)NNB is the estimated boundary considering the worst case. To select the nearest \(k\) number of Q-nodes, the Q-nodes are sorted in ascending order according to their distances from the H-node. Finally, the H-node selects the top-\(k\) number of Q-nodes and transmits back to the query source by GPSR.