Energy efficient processing of K nearest neighbor queries in location-aware sensor networks

The k nearest neighbor (KNN) query, an essential query for information processing in sensor networks, has not received sufficient attention in the research community of sensor networks. In this paper, we examine in-network processing of KNN queries by proposing two alternative algorithms, namely the...

Full description

Saved in:
Bibliographic Details
Main Authors: Winter, J., Xu, Y., Lee, W.-C.
Format: Conference Proceeding
Language:English
Subjects:
Data mining
Energy efficiency
Energy storage
Intelligent networks
Nearest neighbor searches
Routing
Sensor phenomena and characterization
Sensor systems
Spatial databases
Wireless sensor networks
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The k nearest neighbor (KNN) query, an essential query for information processing in sensor networks, has not received sufficient attention in the research community of sensor networks. In this paper, we examine in-network processing of KNN queries by proposing two alternative algorithms, namely the GeoRouting Tree (GRT) and the KNN Boundary Tree (KBT). The former is based on a distributed spatial index structure and prunes off the irrelevant nodes during query propagation. The latter is based upon ad-hoc geographic routing and first obtains a region within which at least k nearest sensor nodes are enclosed and then decides the k nearest nodes to the query point. We provide an extensive performance evaluation to study the impact of various system factors and protocol parameters. Our results show that GRT yields a good tradeoff between energy consumption and query accuracy in static scenarios. On the other hand, KBT achieves better energy efficiency while being more tolerant to network dynamics.
DOI:10.1109/MOBIQUITOUS.2005.28