位置相關信息服務中一種基于價值的數據預取方法

1、<p>　　位置相關信息服務中一種基于價值的數據預取方法</p><p>　　摘要：基于LDD的預取策略如DDP考慮了數據距離，但是沒有考慮數據的訪問概率和更新頻率和數據大小，針對以上問題提出基于價值的數據預取(CDP)策略，一些重要的數據預取因素如訪問概率、更新頻率、數據項大小、數據距離和有效范圍等都包含在價值函數里，根據價值函數值的大小來選擇被預取的數據。通過實驗對比，CDP比DDP策略更有效的提高

2、緩存的命中率。 </p><p>　　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. Fo

3、r 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

4、 are included in the value function. We can choose the prefetching data based on the size o</p><p>　　關鍵詞：位置相關信息服務；位置相關數據；數據預??；緩存命中率 </p><p>　　Key words: location-dependent information services；l

5、ocation dependent data；data prefetching；cache hit ratio </p><p><b>　　0 引言 </b></p><p>　　移動計算環(huán)境下，網絡的弱連接、低帶寬使得用戶而無法及時獲取所需的信息，特別是查詢位置相關數據（Location Dependent Data，LDD）時，容易因用戶位置的改變而導致查詢結

6、果過時失效或者不正確。而數據預取技術能夠顯著提高數據訪問速度和充分利用廣播帶寬[1]。 </p><p>　　1 基于價值的數據預取策略 </p><p>　　1.1 位置相關數據的模型 位置相關數據（LDD），是指其值取決于具體地理位置的數據，LDD具有特定的適用范圍。 </p><p>　　數據的有效范圍區(qū)域（Valid Scope Area），是指數據實例

7、有效范圍的幾何區(qū)域。每個LDD實例有一個特定的有效范圍，只有在此有效范圍之內，該實例才是正確的。 </p><p>　　數據距離（Data Distance），是指MC當前位置和數據實例有效范圍之間的距離。 </p><p>　　1.2 CDP預取方法 本文提出CDP策略，預取時根據價值函數的值進行選擇，預取價值函數如下：Cost=Puseful×（benefit-penal

8、ty）（1） </p><p>　　式（1）中Puseful為MC訪問LDD的概率，benefit為MC預取LDD的獲益價值，penalty為預取LDD的懲罰代價。 </p><p>　　1.2.1 數據預取的獎懲代價 數據預取到本地緩存后，并非所有的數據都是MC需要的，經過運算處理后能成為有效查詢的數據才是用戶需要的，只有這部分數據才能給MC的查詢訪問帶來獲益。本文用fbenefit（

9、di）表示預取數據di的獲益價值函數，即MC未預取數據時的訪問時間與預取數據時的訪問時間減少的比例。 </p><p>　　1.2.2 訪問LDD的概率 對于MC訪問某一種LDD可能性的概率，主要以MC經過該數據有效范圍的概率和未來訪問該數據的概率為依據，因此把MC將來可能經過有效范圍內數據列為預取的候選集C。主要考慮以下兩點因素：①從時間的角度來考慮。越久未被更新的數據，說明其因服務器端的數據更新而導致預取數

10、據失效的可能性越??；而越久未被訪問的數據說明其比較陳舊，再次被訪問的可能性就越小。②從空間的角度來考慮。研究表明，在位置相關信息服務的數據訪問中，MC沿著某條移動路徑通過的概率越高，數據距MC當前的位置越近，且數據有效范圍區(qū)域的面積越大，或者越靠近MC當前移動路徑或移動方向上的LDD越容易被訪問。 </p><p>　　1.3 備選預取數據的擇取 數據預取的目標是希望在MC有限資源的前提下，使得所預取的數據盡可

11、能都是MC需要的，并且盡可能多的提供有效查詢信息。 </p><p>　　在數據擇取過程中應考慮以下兩種情況： </p><p>　?、佼擲=0（緩存已滿）時，不論C中是否有剩余的未被預取的LDD，都將停止預取。 </p><p>　　②當0＜S（緩存還有剩余空間）且size（i）&gt;S，則根據MC當前位置和緩存的剩余空間來計算應預取數據總量的大小。 &

12、lt;/p><p>　　2 模擬實驗及性能分析 </p><p>　　實驗以預取數據在緩存中的命中率為指標進行測試對比。測試的工作負載為一組隨機產生的查詢序列，由100個查詢組成，每次查詢生成的條件字段、條件值和數據表都是按照一定的規(guī)則隨機產生的。將MC的緩存的大小分別設置為實驗數據總量的10%、15%、20%、25%、30%時分別進行五組實驗，實驗結果如圖1所示。 </p>

13、<p><b>　　3 結論 </b></p><p>　　在移動環(huán)境中，數據預取是有效提高訪問速度和減少數據訪問時間的一個可行辦法。本文主要考慮MC訪問LDD可能性概率以及每一種數據能提供多少有效查詢信息，設計出一個預取價值選擇函數，在候選集中找到預取數據，只要這些數據出現在廣播信道，就預取到本地緩存。通過實驗比較，CDP策略比DDP、DHP策略更有效的提高了緩存命中率。 &l

14、t;/p><p><b>　　參考文獻： </b></p><p>　　[1]李國徽，楊兵，陳輝，等.移動環(huán)境下支持實時事務處理的數據預取[J].計算機學報，2008，31（10）：1841-1847. </p><p>　　[2]Yin L，Cao G.Adaptive power-aware prefetch in wirelesa netwo

15、rks[J]．IEEE Transactions Wire1ess Communications，2004.3（5）：1648-1658. </p><p>　　[3]Jiang Z，Kleinrock L.Web prefetching in a mobile environment[J].IEEE Personal Communications，1998，5（5）：25-34. </p><

16、;p>　　[4]Persone V D N，Grassi V，Morlupi A.Modeling and evaluation of prefetching policies for context-aware information services[C].Proceedings of the 4th Annual International Conference on Mobile Computing and Network

17、ing，1998：55-65. </p><p>　　[5]Zheng B，Xu J，Lee D L.Cache invalidation and replacement strategies for location-dependent data in mobile environments[J].IEEE Transactions on Computers，2002，51（10）：1141-1153. <