## 1 Introduction  
The _K_-nearest neighbor (_K_NN) query is an important type of the spatio-temporal queries. Given a set of objects \(S_{o}\), a query object \(q\), and a value of \(K\), the _K_NN query finds the _K_-nearest neighbors of \(q\) among \(S_{o}\). Previous studies [1; 2; 3; 4; 5; 6] focus on processing the _K_NN queries on moving objects whose locations are obtained through the GPS technique. In this paper, we take the moving objects monitored by the sensor network [7; 8; 9] into consideration in processing the _K_NN queries. Two real-world examplesof _K_NN query are presented as follows. The first example is that a fleet of warships on the sea fighting an enemy squadron. To immediately support a warship in case it is under attack, a _K_NN query may be used to find the friendly warships close to the warship requiring to be supported. The second example is that a traveler planning a trip from city A to city B. In this scenario, the traveler can issue a _K_NN query to find the nearest hotels during the trip. For each moving object tackled in this paper, its location cannot be obtained through the GPS technique. Instead, the moving object is monitored by taking advantage of another positioning technique, the sensor-based tracking system. As the location of each object is determined by the sensor network, the uncertainty of the object's location is much higher than that of object monitored by the GPS technique. This would incur a higher cost of processing the _K_NN queries. In the following, we will discuss the difficulties that need to be addressed in processing the _K_NN queries. The first difficulty is how to quantify the uncertainty of moving objects. As the moving objects are monitored in the sensor network, the uncertainty of objects is dominated by the number of sensors. Due to the limited number of sensors, different deployment strategies for the sensor network will result in different uncertainty of object locations. As such, developing an appropriate sensor deployment is important to effectively reduce the uncertainty of object locations. The second difficulty is how to develop an efficient index for managing the objects moving in the sensor network. The existing index structures are well-designed for the moving objects that have precise location information. In this paper, we consider the moving objects with uncertainty when the _K_NN query is processed. Therefore, a new index structure is needed to manage such moving objects. The third difficulty is how to design an efficient _K_NN query processing algorithm to find the _K_-nearest neighbors of the query object. Due to the movement of objects, the query result would change with time (that is, the query result is dependent on the current location of the query object). This makes the execution of the _K_NN query more complicated. We will discuss the characteristic of the _K_NN query so as to develop the query processing algorithm with better performance. The last difficulty is how to reasonably give each moving object a probability of being the _K_-nearest neighbor (_i.e._, the probability of object being the query result). As the objects move with uncertain location, there exist some objects that are possible to be the _K_-nearest neighbor (that is, these objects are possible answers for the _K_NN query). When the number of possible answers increases, the situation becomes very hard to choose the most appropriate objects. Therefore, a probability model must be built to reasonably provide probabilistic answers to the _K_NN query. The main contributions of this paper are summarized as follows. * An efficient sensor deployment strategy is used to construct the sensor network. * An effective mechanism is designed to quantify the uncertainty of objects moving in such a sensor network. * A grid index with update operations is developed to manage moving objects in the sensor network. * A query processing algorithm is developed to efficiently answer the _K_NN query.