行動環境上之高效能與省電之KNN查詢處理系統之研究

Abstract

在眾多無線網路服務媒體所提供的服務查詢中，以Nearest Neighbor (NN)查詢與 k-Nearest Neighbor (k-NN)查詢最為常見。舉例來說：人們在下了火車離開火車站後， 通常想找離火車站最近(NN)的飯店休息，因此他會要求服務媒體提供離火車站最近飯 店的位址資訊；在市區中的汽車駕駛想要從他現在的位址連接到高速公路上，因此他 會要求服務媒體提供離他目前位址最靠近的k 個(k-NN)交流道位址資訊。研究文獻結 果指出，在行動資訊系統與行動設備間架設支援k-NN 查詢的proxy 能在少量增加建置 成本的情形下，有效地增快查詢的反應時間與降低行動資訊系統的總工作量。因此在 本計畫中，我們想要針對NN 與k-NN 查詢服務提出一個方案，提昇行動資訊系統的延 展性與效能，並節省使用端行動設備的能源消耗。我們將研發適用於行動計算環境下 之支援k-NN 查詢的系統架構，其主要議題如下：在第一年中，我們首先將研發提供整 合NN 查詢服務的系統架構，用以提升行動資訊系統的延展性與系統效能；接著我們 將研發快速的estimated valid region 成長方法；最後我們將研發合適之快取管理演算 法。在第二年中，我們將著重於k-NN 查詢。我們首先將修改之前設計之系統架構以支 援k-NN 查詢。我們也將著手研發省電之行動設備端(mobile client)與服務提供端(service provider)的溝通機制，由於行動設備大部分消耗電源在於與伺服器通訊，如果能有效的 減少行動設備與伺服器的通訊量，將有效的減少行動設備的能源消耗。因此我們將研 發適合行動資訊系統與行動設備的溝通機制，並將其與proxy 整合，減少proxy 與行動 設備間資料的傳輸量，並藉以減少行動設備的能源消耗。最後，我們將著手開發實驗 平台並實作所開發之演算法，以便進行效能評估。