## 1 Introduction  
Advancements in wireless technology and sensors have enabled rapid development of mobile sensor networks in which moving sensor nodes are wirelessly connected. Recently, mobile sensor networks have received a lot of attention because they have a variety of applications, such as intelligent transportation systems [1], wildlife conservation systems [2], and battlefield surveillance systems [3]. The \(k\)-nearest neighbors (\(k\)NN) query is an important spatial query in spatial or multidimensional databases [4; 5; 6]. In mobile sensor networks, the \(k\)NN query is to find the \(k\) sensor nodes closest to the query point \(q\). The \(k\)NN query can be used in vehicle navigation, wildlife social activity discovery, forest fire impact investigations, and squad/platoon searches on the battlefield [7]. Traditional \(k\)NN query processing techniques assume the context that location data are collected in a centralized database [8; 9]. Collecting a massive amount of sensed data to a centralized database incurs unnecessary and redundant message transmissions. These traditional techniques are infeasible for mobile sensor networks due to the high communication cost and energy consumption. Recently, in-network techniques have been proposed to overcome these problems. Representative \(k\)NN query processing techniques are PT [10], KPT [11], DIKNN [12; 13] and GDRKNN [14]. Studies of these methods have shown improved performance by using index and _ad hoc_ geographic routing techniques. Especially, they have focused on reducing the number of transmissions because the greatest energy consumption by sensor nodes is due to communication. This paper focuses on a novel spatial query problem, the \(k\)NN query with a distance constraint, named \(l\)-distant \(k\)-nearest neighbors (\(l\)-\(k\)NN). The \(l\)-\(k\)NN query finds the \(k\) sensor nodes nearest to the query point \(q\) and at least separated from each other by a distance \(l\). One of main objectives of the \(k\)NN query is to facilitate collection of sensor data samples around the query location in the applications [15]. However, since the existing \(k\)NN query does not consider the distribution of the objects in the query result, it has the severe drawback that the objects sampled can be skewed only in a small area rather than the whole area of interest. If we need well distributed or wide coverage of the \(k\)NN result in the applications of the \(k\)NN query, the \(l\)-\(k\)NN query is more suitable because it finds well scattered objects over the area of interest. An example of \(l\)-\(k\)NN query is survival discovery on the battlefield [7]. Suppose we want to seek for the nearby survivals around a battlefield stronghold. While the \(k\)NN query finds simply \(k\) nearest survivals, our proposed \(l\)-\(k\)NN query can reveal the distribution of survivals around the battlefield stronghold. Figure 1 shows comparisons of results between the \(k\)NN and the \(l\)-\(k\)NN queries when \(k\) is set to 4. Given the query point \(q\), the result for the \(k\)NN query is \(S_{1}\), \(S_{2}\), \(S_{3}\) and \(S_{4}\), which are skewed in a small area and cover only the left side of the query point. When \(k\) increases from 4 to 5, the right side is still not covered because \(S_{5}\) is selected additionally. The result for the \(l\)-\(k\)NN query is \(S_{4}\), \(S_{6}\), \(S_{7}\) and \(S_{8}\), which covers the wider area in a well distributed way. Considering the limited computing power and batteries of sensor nodes, processing a \(l\)-\(k\)NN query is problematically expensive in terms of energy consumption in mobile sensor networks. For \(n\) sensor nodes, \({}_{n}C_{k}\) is the number of cases possible for selecting \(k\) sensor nodes. Moreover, we need to verify the \(l\)-distant constraint between each pair of sensor nodes \({}_{k}C_{2}\) times for each case. To compute the \(l\)-\(k\)NN query for all the cases, a great number of message transmissions would be required, which would incur huge battery consumption.