DIKNN: An Itinerary-based KNN Query Processing Algorithm for Mobile Sensor Networks
DIKNN: An Itinerary-based KNN Query Processing Algorithm for Mobile Sensor Networks
复制标题
DOI：
10.1109/icde.2007.367891
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
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查询处理（DIKNN）。DIKNN将搜索区域划分为以查询点为中心的多个锥形区域。然后，它在每个锥形区域中并行执行查询传播和响应收集行程。DIKNN方案的设计还考虑了具有挑战性的问题，如根据传感器节点的空间不规则性或移动性动态调整搜索半径（在跳数方面）。仿真结果表明，DIKNN产生更好的性能和可扩展性比以前的工作，无论是作为k的增加和传感器节点的移动性增加。它的性能优于第二名，节省了高达50%的能源消耗和高达40%的查询响应时间，同时呈现相同水平的查询结果准确性。
Current approaches to k nearest neighbor (KNN) search in mobile sensor networks require 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 also takes into account challenging issues such as the the dynamic adjustment of the search radius (in terms of number of hops) according to spatial irregularity or mobility of sensor nodes. The simulation results show that DIKNN yields substantially better performance and scalability over previous work, both as k increases and as the sensor node mobility increases. It outperforms the second runner with up to 50% saving in energy consumption and up to 40% reduction in query response time, while rendering the same level of query result accuracy.