平行化路徑式KNN查詢演算法運用於無線感測器網路

Abstract

在無線感測器網路中，用來得到給定的限制條件下的感測資料的空間式的查詢，可以運用在許多應用中，例如：環境監測、軍事監視等。一種典型的空間式查詢，KNN查詢，便是給定一空間上的查詢位置，以及欲收集的資料個數K 值，來收集空間中感測到的資料。近期的研究中，一種路徑式的KNN 查詢演算法被發展出來，乃沿著預先計算好的路徑來作資料的收集的演算法，被研究出較其他演算法，可以達到較好的電力效率。但是，路徑式KNN 演算法中，如何設計以及計算出路徑，便是此種演算法的一大挑戰。在此篇論文中，我們提出一種新的路徑式KNN 查詢演算法，叫作PCIKNN，根據使用者不同的目的，例如：最佳化查詢時間、最佳化電力消耗，來計算出查詢路徑。PCIKNN 的效能，在數學上以及實驗上被證明較目前其他路徑式KNN 演算法，擁有較好的效能，在於查詢精確度、查詢時間以及電力消耗等。

Spatial queries for extracting data from wireless sensor networks are important for many applications, such as environmental monitoring and military surveillance. One such query is K Nearest Neighbor (KNN) query that facilitates sampling of monitored sensor data in correspondence with a given query location. Recently, itinerary-based KNN query processing techniques, that propagate queries and collect data along a pre-determined itinerary, have been developed concurrently [27][30]. These research works demonstrate that itinerary-based KNN query processing algorithms are able to achieve better energy efficiency than other existing algorithms. However, how to derive itineraries based on different performance requirements remains a challenging problem. In this paper, we propose a new itinerary-based KNN query processing technique, called PCIKNN, that derives different tineraries aiming at optimizing two performance criteria, response latency and energy consumption. The performance of PCIKNN is analyzed mathematically and evaluated through extensive experiments. Experimental results show that PCIKNN has better performance, such as accuracy, energy consumption and query latency, and has scalability than the state-of-the-art.