以資訊關聯度為導向之近鄰預取查詢策略

An Information Relevency-oriented Nearest Neighbor Prefetching Query Policy

林彥亨(Yen-Heng Lin)

指導教授 ： 段裘慶

國立臺北科技大學/電資學院/電腦與通訊研究所/碩士(2009年)

https://doi.org/10.6841/NTUT.2009.00497

摘要

近年來，隨著無線通信技術日益進步，整體行動用戶數也急遽成長，因而位置相依資訊服務遂成為行動計算諸多熱門探討議題之一。
然而，行動主機於可攜性設計原則下，記憶體容量往往有所限制，且因地形與訊號之不確定性因素皆可能使行動用戶難以即時取得所需之資料，故於行動通訊系統中，常以資料預取機制解決上述之問題，意使行動用戶端於適用之有效範圍內，預先取得其未來極有可能提出請求之資料，以期達成存取服務不中斷之目標。
於行動計算環境下，由於行動主機與遠端資料庫伺服器間所進行之遠距通訊行為易產生高額之網路流量，同時也增加資料庫伺服器工作負載，是故若能在預取架構中加入代理伺服器，藉以優化查詢機制之功效，將可顯著提昇系統服務之品質。
本篇論文以資訊關聯度為導向運用於預取機制，將行動環境中所存之位置相依資料、資料間之關聯資訊及其他預取影響因子納入考慮，並傳至代理器作預取資訊價值函數運算，以取得具高參考價值意義之位置相依資訊。然而，代理器將以此資訊作為預取決策之主要參考，同時透過發送「位置相依資料」與「關聯價值」服務來達成縮短查詢回應時間及降低遠端資料庫伺服器工作負載之目的。最後，由模擬實驗結果顯示，本文所提出之預取策略在多數情況下皆具較高之快取命中率及較少之回應時間；以快取命中率而言，當LDD種類數量為6時，本策略將優於其他策略平均約15%；而延遲時間將低於其他策略平均約0.24秒，且更能有效提昇行動通訊系統之效能。

關鍵字

資料預取 ； 位置相依資訊服務 ； 代理伺服器 ； 資訊價值 ； 行動計算

並列摘要

Due to the limitations on the connection qualities and available bandwidth in the mobile networks, mobile units (MUs) have been difficult to effectively access location based services. Hence, in most mobile communication systems, a data prefetching policy is usually proposed to improve the access service qualities. We proposed a two tier Location Dependent Information Services (LDISs) framework. In the framework, a proxy server first utilizes the Prefetching Information Valuable Function (PIV) to calculate the prefetching values for valid location dependent data (LDD). The proxy server then makes its caching decision on all LDDs with PIVs. Finally, the proxy server provides MUs with the LDDs having higher relevancy values. Therefore, reduce the response time for MUs and workload for the remote database server.
The simulation results showed that our proposed LDIS framework and caching strategy could yield a higher accuracy of caching and rate of LDD utilization, and promote the efficiency of data services for mobile communication systems.

並列關鍵字

Location dependent information Services ； Data prefetching ； Proxy server ； Information valuable ； Mobilie Computing

參考文獻

[1] I. F. Akyildiz, J. S. M. Ho, and Y. B. Lin, “Movement-based location update and selective paging for PCS networks,” IEEE/ACM Trans. Networking, vol. 4, no. 4, pp. 629–638, Aug. 1996.

[2] D. L. Lee, J. Xu, and B. Zheng, “Data Management in Location-Dependent Information Services,” IEEE Pervasive Computing, vol. 1, Issue 3, pp. 65-72, 2002.

[3] M. H. Dunham and V. Kumar, “Location Dependent Data and its Management in Mobile Databases,” in Proc. of the IEEE DEXA, Vienna, Austria, pp. 414-419, Aug. 1998.

[4] U. Kubach and K. Rothermel, “Exploiting Location Information for Infostation-Based Hoarding,” in Proc. of the ACM MobiCom 2001, Rome, Italy, pp. 15-27, Jul. 2001.

[6] A. R. Hurson, G.. Xu, and J. Sustersic, “Window Query Processing with Proxy Cache,“ in Proc. of the 7th International Conference on Mobile Data management, Nara, Japan, pp. 39-39, May 9-13, 2006.