## 3 \(l\)-\(k\)-Nearest-Neighbors Query Processing
### Algorithm for Query Dissemination
```
1 IsSelectTrackSector (\(t_{idx},s_{idx}\)) \(\bullet\)Input: a track index \(t_{idx}\), a sector index \(s_{idx}\) \(\bullet\)Output: a Boolean value representing whether this TS is in a query sector or in a margin sector
```
```
1:\(N_{t}\leftarrow\)calculate the total number of tracks
2:\(N_{s}\leftarrow\)calculate the total number of sectors in the current track
3:if (\(N_{s}\) is an odd number)
4:if (\(s_{idx}\) is an odd number & \(s_{idx}\
eq N_{s}\))
5:return\(true\); //current track-sector is in a query sector
6:else
7:if (\(s_{idx}\) is an odd number)
8:return\(true\); //current track-sector is in a query sector
9:returnfalse; //current track-sector is in a margin sector
```

**Algorithm 4** Determining the Sector Type

## 4 Performance Evaluation

In this section, we evaluate the performance of the proposed method in terms of energy efficiency, query latency, and query accuracy. We use the ns-2 simulator [21] for our experiments. We observe the impact of the constraint parameters, such as \(l\) and \(k\), on the performance. ### Experimental Settings

For the performance evaluation, we compare the proposed method with a post processing based method using the \(k\)NN query. The post processing method collects all sensor nodes within the \(l\)-\(k\)NNB using the DIKNN method [13] and selects \(k\) number of \(l\)-distant sensor nodes from the collected sensor nodes. We call the post processing method _DIKNN_ in our experiments. The proposed method and DIKNN are implemented based on the ns-2 simulator. For the routing protocol in sensor networks, we use the geo-routing protocol GPSR [19] in the ns-2. The sensor nodes are randomly distributed in the wireless sensor networks. The movement pattern of the sensor nodes is represented by the random waypoint model (RWP). Each sensor moves to the arbitrary destination at a random speed ranging from 0 to 20. We fix the network size at 300 \(\times\) 300 m\({}^{2}\). We vary the number of sensor nodes from 300 to 1000, and the node degree (_i.e._, neighbor count of each sensor node) ranges from 5 to 20. The distance between the source node and the home node for each query is set to 250 m. The query response size of each sensor nodes is 10 bytes. The performances are obtained by averaging the result over 10 simulation runs. Table 1 summarizes the datasets used for the experiments. Query latency is measured as the elapsed time between when the query is issued by the query point and when query responses are returned. Energy consumption is measured as the total amount of consumed energy during the query processing in the wireless sensor networks. Query accuracy is measured as the set similarity of distance between the ground truth and the proposed method. We use the Hausdorff distance algorithm [22] for the set similarity. Given two result sets of \(l\) - \(k\) NN, \(A\) = \(\{a_{1},a_{2},...,a_{m}\}\) and \(B\) = \(\{b_{1},b_{2},...,b_{n}\}\), the Hausdorff distance calculates set similarity as in Equation (5), where \(a_{i}\) is the distance from sensor node \(s_{i}\) to the home node:

\[H(A,B)=\frac{1}{m}\sum_{a\in A}\min_{b\in B}||a-b|| \tag{5}\]

### Experimental Results

Figure 6 shows the results for the \(l\)-\(k\)NN query accuracy compared with the ground truth. The left figure shows the accuracy with various \(l\) values, such as 10 m, 20 m, 30 m, 40 m and 50 m in the D-300 dataset when \(k\) is set to 30. The \(l\)-\(k\)NN achieves the highest query accuracy when \(l\) is set to 30 m. This is because our method is a greedy algorithm. A small \(l\) generates a large number of query result sets because many sensor nodes satisfy the condition of being \(l\) distances apart. Therefore, the selected result set has a high probability of being different from the ground truth. In the case of a large \(l\), only a small number of result sets are possible. However, the accuracy decreases because the large \(l\) increases the width of each track-sector.