摘要：基於LDD的預取策略如DDP考慮了數據距離，但是沒有考慮數據的訪問概率和更新頻率和數據大小，針對以上問題提出基於價值的數據預取(CDP)策略，一些重要的數據預取因素如訪問概率、更新頻率、數據項大小、數據距離和有效範圍等都包含在價值函數裏，根據價值函數值的大小來選擇被預取的數據。透過實驗對比，CDP比DDP策略更有效的提高快取的命中率。
Abstract: LDD-based prefetching strategies like DDP take the data distance into account, but do not take into account the access probability of data, updating data and size of frequency. For these issues, this paper proposes a value-based data prefetching(CDP) strategy, and some important data prefetching factors, such as access probability, update frequency, data item size, data distance and range of data are included in the value function. We can choose the prefetching data based on the size of function value. By comparing the experiment, CDP is more effective than DDP strategy to improve the cache hit rate.
關鍵詞：位置相關資訊服務；位置相關數據；數據預取；快取命中率
Key words: location-dependent information services；location dependent data；data prefetching；cache hit ratio
0 引言
移動計算環境下，網絡的弱連接、低帶寬使得用戶而無法及時獲取所需的資訊，特別是查詢位置相關數據（Location Dependent Data，LDD）時，容易因用戶位置的改變而導致查詢結果過時失效或者不正確。而數據預取技術能夠顯著提高數據訪問速度和充分利用廣播帶寬[1]。
1 基於價值的數據預取策略
1.1 位置相關數據的模型 位置相關數據（LDD），是指其值取決於具體地理位置的數據，LDD具有特定的適用範圍。
數據的有效範圍區域（Valid Scope Area），是指數據實例有效範圍的幾何區域。每個LDD實例有一個特定的有效範圍，只有在此有效範圍之內，該實例纔是正確的。
數據距離（Data Distance），是指MC當前位置和數據實例有效範圍之間的距離。
1.2 CDP預取方法 本文提出CDP策略，預取時根據價值函數的值進行選擇，預取價值函數如下：Cost=Puseful×（benefit-penalty）（1）
式（1）中Puseful爲MC訪問LDD的概率，benefit爲MC預取LDD的獲益價值，penalty爲預取LDD的懲罰代價。
1.2.1 數據預取的獎懲代價 數據預取到本地快取後，並非所有的數據都是MC需要的，經過運算處理後能成爲有效查詢的數據纔是用戶需要的，只有這部分數據才能給MC的查詢訪問帶來獲益。本文用fbenefit（di）表示預取數據di的獲益價值函數，即MC未預取數據時的訪問時間與預取數據時的訪問時間減少的比例。
1.2.2 訪問LDD的概率 對於MC訪問某一種LDD可能性的概率，主要以MC經過該數據有效範圍的概率和未來訪問該數據的概率爲依據，因此把MC將來可能經過有效範圍內數據列爲預取的候選集C。主要考慮以下兩點因素：