位置相關(guān)信息服務中一種基于價值的數(shù)據(jù)預取方法

1、<p>　　位置相關(guān)信息服務中一種基于價值的數(shù)據(jù)預取方法</p><p>　　摘要：基于LDD的預取策略如DDP考慮了數(shù)據(jù)距離，但是沒有考慮數(shù)據(jù)的訪問概率和更新頻率和數(shù)據(jù)大小，針對以上問題提出基于價值的數(shù)據(jù)預取(CDP)策略，一些重要的數(shù)據(jù)預取因素如訪問概率、更新頻率、數(shù)據(jù)項大小、數(shù)據(jù)距離和有效范圍等都包含在價值函數(shù)里，根據(jù)價值函數(shù)值的大小來選擇被預取的數(shù)據(jù)。通過實驗對比，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>　　關(guān)鍵詞：位置相關(guān)信息服務；位置相關(guān)數(shù)據(jù)；數(shù)據(jù)預??；緩存命中率 </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)境下，網(wǎng)絡的弱連接、低帶寬使得用戶而無法及時獲取所需的信息，特別是查詢位置相關(guān)數(shù)據(jù)（Location Dependent Data，LDD）時，容易因用戶位置的改變而導致查詢結(jié)

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

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

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

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

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

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

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

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

14、t;/p><p><b>　　參考文獻： </b></p><p>　　[1]李國徽，楊兵，陳輝，等.移動環(huán)境下支持實時事務處理的數(shù)據(jù)預取[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. <