Toward the Optimal Itinerary-Based KNN Query Processing in Mobile Sensor Networks
Toward the Optimal Itinerary-Based KNN Query Processing in Mobile Sensor Networks
复制标题
DOI：
10.1109/tkde.2008.80
复制
发表时间：
2008-12
影响因子：
8.9
通讯作者：
Shan-Hung Wu;Kun-Ta Chuang;Chung-Min Chen;Ming-Syan Chen
中科院分区：
文献类型：
--
作者：
Shan-Hung Wu;Kun-Ta Chuang;Chung-Min Chen;Ming-Syan Chen
K 最近邻（KNN）查询在许多研究中引起了极大的兴趣，并且已成为移动传感器网络中最重要的空间查询之一。 KNN 查询的应用可能包括车辆导航、野生动物社交发现以及战场上的班/排搜索。当前移动传感器网络中的 KNN 搜索方法需要某种索引支持。该索引可以是集中式空间索引，也可以是分布在传感器节点上的网络内数据结构。创建和维护这些索引结构以反映由于传感器节点移动性而导致的网络动态，可能会导致查询响应时间长和电池效率低，从而限制其实际使用。在本文中，我们提出了一种基于免维护行程的方法，称为密度感知行程 KNN 查询处理（DIKNN）。 DIKNN 将搜索区域划分为以查询点为中心的多个锥形区域。然后，它在每个锥形区域中并行执行查询传播和响应收集行程。 DIKNN方案的设计考虑了几个具有挑战性的问题，例如并行度和网络干扰对查询响应时间的权衡，以及根据传感器节点的空间不规则性或移动性动态调整搜索半径（以跳数计）。为了优化 DIKNN 的性能，导出了详细的分析模型，可自动确定各种网络条件下最合适的并行度。该模型经过广泛的模拟验证。仿真结果表明，随着 kappa 的增加和传感器节点移动性的增加，DIKNN 比以前的工作产生了更好的性能和可扩展性。它的性能优于第二名，能耗节省高达 50%，查询响应时间减少高达 40%，同时呈现相同水平的查询结果准确性。
The K-nearest neighbors (KNN) query has been of significant interest in many studies and has become one of the most important spatial queries in mobile sensor networks. Applications of KNN queries may include vehicle navigation, wildlife social discovery, and squad/platoon searching on the battlefields. Current approaches to KNN search in mobile sensor networks require a certain kind of indexing support. This index could be either a centralized spatial index or an in-network data structure that is distributed over the sensor nodes. Creation and maintenance of these index structures, to reflect the network dynamics due to sensor node mobility, may result in long query response time and low battery efficiency, thus limiting their practical use. In this paper, we propose a maintenance-free itinerary-based approach called density-aware itinerary KNN query processing (DIKNN). The DIKNN divides the search area into multiple cone-shape areas centered at the query point. It then performs a query dissemination and response collection itinerary in each of the cone-shape areas in parallel. The design of the DIKNN scheme takes into account several challenging issues such as the trade-off between degree of parallelism and network interference on query response time, and the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. To optimize the performance of DIKNN, a detailed analytical model is derived that automatically determines the most suitable degree of parallelism under various network conditions. This model is validated by extensive simulations. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as kappa increases and as the sensor node mobility increases. It outperforms the second runner with up to a 50 percent saving in energy consumption and up to a 40 percent reduction in query response time, while rendering the same level of query result accuracy.