## 3 \(l\)-\(k\)-Nearest-Neighbors Query Processing
### Algorithm for Query Dissemination
To determine the direction, each sensor node should know its own sector number and track number, and the four borderlines of the track-sector. Algorithm 2 includes the calculation of all of this information about the current sensor node. Each sensor node can calculate the discriminants determining the borderlines of its own track-sector by using its own coordinates and those of the H-node. The current sensor node calculates its distance from the H-node. The track index that the sensor node belongs to is calculated by dividing the distance by the track radius \(l\) (line 2). The algorithm calculates the radius \(R\) of the current track by multiplying the track index by the track radius \(l\), which is the upper arc of the current track (line 3). The lower arc of the current track is \(R\)- \(l\) because the radii of the tracks increase by \(l\). Therefore, we can derive the discriminants that calculate the upper and lower arcs of the track having radius \(R\) centered at \(h\) (lines 4-5). The algorithm checks whether the current track is a margin track or a query track (line 6). If the current track is a margin track, the query message is passed to the next track (lines 11-12). Otherwise, the algorithm checks whether a Q-node is selected (line 7). If a Q-node is selected, the query message is passed to the next track-sector (lines 7-8). Otherwise, the query message is passed to the _next_wnode_ along the lower arc in the current track-sector (lines 9-10). The chord is calculated as \(\frac{\sqrt{3}}{2}\,r\) for the central angle \(\theta_{\mathbf{v}}\). This is the optimal chord to select the next sensor node without interference among the sensor nodes. After obtaining \(\theta_{\mathbf{v}}\) for dividing the search space into sectors, the algorithm calculates the sector number \(s_{idx}\) of the current sensor node by using the coordinates of the current sensor node and the home node (lines 13-14). The algorithm derives the discriminants that calculate the right- and left-side lines of the current track-sector by using \(s_{idx}\) and \(\theta_{\mathbf{v}}\) (lines 15-16). We can obtain the corner points from the four discriminants of the borderlines of the current track sector (line 17). If the current track-sector is a query one and no Q-node is selected, the algorithm selects the sensor node nearest to the corner intersecting the lower arc and the margin sector (lines 18-21). After selecting the Q-node, the algorithm determines the next direction and the _next_wnode_ (lines 22-23). Because the algorithm adopts itinerary traversal [13] to select the next track in a sector, the query message is passed to the next sensor node in the east direction in odd-number tracks. Conversely, the query message is passed in the west direction in even-number tracks. The algorithm finally returns the _next_wnode_ as the coordinates of the corner of the next track-sector (line 24). Algorithm 3 determines the next forward direction of the query message from the current sensor node. According to the itinerary traversal algorithm, the forward direction is determined to be east if the current track index is an odd number, and west if even (lines 1-8). If the current track-sector is the last sector or the margin track, the forward direction is determined to be north because the algorithm does not need to select the Q-node (line 9).