Scalable Computing and Communications: Theory and Practice

24

–––––––––––––––––––––––

KNN Queries in Mobile Sensor Networks

Wei-Guang Teng and Kun-Ta Chuang

24.1   INTRODUCTION

Mobile sensor networks have received a significant amount of research attention in recent years because they can support a wide range of applications, for example, intelligent transportation systems (ITS) [1], wildlife conservation systems [2], and battlefield surveillance systems [3]. In most applications for sensor networks, it is expected that data on sensor nodes can be periodically queried by an external source. Important statistical information about the underlying physical processes can thus be collected for further use.

Recently, query processing techniques, including range queries, k-nearest neighbor (KNN) queries, and snapshot queries, have been widely utilized in different applications. Among the various query types for aggregating sensor information, theKNN query, which aims at finding the KNNs around a query point, q, has been recognized as one of the key spatial queries in mobile sensor networks [4–7]. Applications of KNN queries include vehicle navigation, wildlife social discovery, and squad/platoon searching on the battlefields. KNN queries can also be applied to emergency situations such as tracing the insurgents of a traffic accident, discovering the impact of a forest fire, and seeking our nearby survivors around a battlefield stronghold.

The problem of developing an efficient algorithm for a KNN search in a spatial or multidimensional database ...