TY - GEN
T1 - Energy efficient processing of K nearest neighbor queries in location-aware sensor networks
AU - Winter, Julian
AU - Xu, Yingqi
AU - Lee, Wang Chien
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33749521727&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749521727&partnerID=8YFLogxK
U2 - 10.1109/MOBIQUITOUS.2005.28
DO - 10.1109/MOBIQUITOUS.2005.28
M3 - Conference contribution
AN - SCOPUS:33749521727
SN - 0769523757
SN - 9780769523750
T3 - MobiQuitous 2005: Second Annual International Conference on Mobile and Ubiquitous Systems -Networking and Services
SP - 281
EP - 292
BT - MobiQuitous 2005
T2 - MobiQuitous 2005: Second Annual International Conference on Mobile and Ubiquitous Systems -Networking and Services
Y2 - 17 July 2005 through 21 July 2005
ER -