## 2 Related Work  
Wireless sensor networks (WSNs) are composed of many devices that sense, store, and transmit data. WSNs have limitations in processing queries because the sensors have limited power supplies, are vulnerable to failure, and have the dynamic property that their availability can vary over time. _k_NN queries retrieve the \(k\) sensor nodes nearest to a point of interest indicated by users, called a query point in WSNs. The _k_NN query can be used to search in border detection and ecological monitoring. _k_NN queries in WSNs have been actively studied to optimize performance given the above limitations of WSNs. _k_NN query processing approaches can be categorized as either fixed index or dynamic index. Fixed-index approaches use a stationary structure based on an R-tree or a spanning tree [10]. These approaches have the critical problem of maintaining the index when the sensor nodes are mobile. Dynamic-index approaches propagate the _k_NN query gradually along itineraries to collect data from sensors in a specific region [11, 12, 13]. The approaches using a fixed-index structure [10] have several problems. The major problem is that index nodes become system bottlenecks because all the query messages are aggregated by index nodes  
Figure 1: Comparisons of results between the _k_NN and the _l-k_NN queries. designated cluster heads. Moreover, large numbers of unnecessary hops from the query point are required because all the query messages are routed along the index hierarchy. This overhead causes significant performance degradation in a large WSN. To overcome these issues, approaches that do not use the fixed index structure have been proposed [11, 12, 13]. KPT [11] assumes a location-aware sensor network and estimates a conservative boundary that includes at least \(k\) sensor nodes to avoid messages' flooding the entire network. However, mobile sensors cause problems in this approach because KPT assumes that the nodes are stationary. The reconstruction cost of the tree is considerably large when the sensor nodes are moving. Moreover, the conservative boundary expands dramatically with increasing \(k\). Some sensor nodes may even turn aside from the boundary during tree construction. The itinerary-based \(k\)NN (IKNN) approach [12, 13] has been proposed to solve these issues. This approach uses both sequential and parallel itinerary processing approaches instead of the tree structure. Two formats have been proposed for the itinerary in IKNN: spiral and parallel. With the spiral itinerary format, the query dissemination starts at the node closest to the query point and follows an itinerary in the form of a spiral. When the number reaches \(k\), the query dissemination is stopped, and the result is sent back to the originator. With the parallel itinerary format, the query dissemination also starts at the node closest to the query point, but it then follows two parallel itineraries. The query stores the number of nodes that answered the query. Neighbor nodes in the different itineraries sum their counts to calculate the total number of nodes that answered the query. The density-aware itinerary-based \(k\)NN (DIKNN) approach [13] divides the region of interest into cone-shaped areas centered at the query point. In each area, an itinerary is created along which a \(k\)NN query is propagated. Itinerary information exchanges occur when itineraries encounter a sector border. When a KNN query reaches a \(k\)NN boundary, the last query node in each sector sends the partial results directly to the source node. Through good estimation of the \(k\)NN boundary, DIKNN improves its query latency over IKNN. However, the accuracy of the \(k\)NN boundary estimation is critical. Although the \(k\)NN approach dynamically adjusts its estimated \(k\)NN boundary, redundancy still exists in the \(k\)NN query result of DIKNN because the partial \(k\)NN query results from all sectors are sent back to the source node without any validation.