信息服務(wù)的數(shù)據(jù)預(yù)取方法綜述.doc

1、信息服務(wù)的數(shù)據(jù)預(yù)取方法綜述摘要：基于lDD的預(yù)取策略如DDp考慮了數(shù)據(jù)距離，但是沒有考慮數(shù)據(jù)的訪問概率和更新頻率和數(shù)據(jù)大小，針對以上問題提出基于價值的數(shù)據(jù)預(yù)取(cDp)策略，一些重要的數(shù)據(jù)預(yù)取因素如訪問概率、更新頻率、數(shù)據(jù)項大小、數(shù)據(jù)距離和有效范圍等都包含在價值函數(shù)里，根據(jù)價值函數(shù)值的大小來選擇被預(yù)取的數(shù)據(jù)。通過實驗對比，cDp比DDp策略更有效的提高緩存的命中率。關(guān)鍵詞：位置相關(guān)信息服務(wù)；位置相關(guān)數(shù)據(jù)；數(shù)據(jù)預(yù)??；緩存命中率0引言移動計算環(huán)境下，網(wǎng)絡(luò)的弱連接、低帶寬使得用戶而無法及時獲取所需的信息，特別是查詢位置相關(guān)數(shù)據(jù)（locationDependentData，lDD）時，容易因用戶位置的

2、改變而導(dǎo)致查詢結(jié)果過時失效或者不正確。而數(shù)據(jù)預(yù)取技術(shù)能夠顯著提高數(shù)據(jù)訪問速度和充分利用廣播帶寬1。1基于價值的數(shù)據(jù)預(yù)取策略1.1位置相關(guān)數(shù)據(jù)的模型位置相關(guān)數(shù)據(jù)（lDD），是指其值取決于具體地理位置的數(shù)據(jù)，lDD具有特定的適用范圍。數(shù)據(jù)的有效范圍區(qū)域（ValidscopeArea），是指數(shù)據(jù)實例有效范圍的幾何區(qū)域。每個lDD實例有一個特定的有效范圍，只有在此有效范圍之內(nèi)，該實例才是正確的。數(shù)據(jù)距離（DataDistance），是指mc當前位置和數(shù)據(jù)實例有效范圍之間的距離。1.2cDp預(yù)取方法本文提出cDp策略，預(yù)取時根據(jù)價值函數(shù)的值進行選擇，預(yù)取價值函數(shù)如下：cost=puseful（benef

3、it-penalty）（1）式（1）中puseful為mc訪問lDD的概率，benefit為mc預(yù)取lDD的獲益價值，penalty為預(yù)取lDD的懲罰代價。1.2.1數(shù)據(jù)預(yù)取的獎懲代價數(shù)據(jù)預(yù)取到本地緩存后，并非所有的數(shù)據(jù)都是mc需要的，經(jīng)過運算處理后能成為有效查詢的數(shù)據(jù)才是用戶需要的，只有這部分數(shù)據(jù)才能給mc的查詢訪問帶來獲益。本文用fbenefit（di）表示預(yù)取數(shù)據(jù)di的獲益價值函數(shù)，即mc未預(yù)取數(shù)據(jù)時的訪問時間與預(yù)取數(shù)據(jù)時的訪問時間減少的比例。1.2.2訪問lDD的概率對于mc訪問某一種lDD可能性的概率，主要以mc經(jīng)過該數(shù)據(jù)有效范圍的概率和未來訪問該數(shù)據(jù)的概率為依據(jù)，因此把mc將來可能

4、經(jīng)過有效范圍內(nèi)數(shù)據(jù)列為預(yù)取的候選集c。主要考慮以下兩點因素：從時間的角度來考慮。越久未被更新的數(shù)據(jù)，說明其因服務(wù)器端的數(shù)據(jù)更新而導(dǎo)致預(yù)取數(shù)據(jù)失效的可能性越??；而越久未被訪問的數(shù)據(jù)說明其比較陳舊，再次被訪問的可能性就越小。從空間的角度來考慮。研究表明，在位置相關(guān)信息服務(wù)的數(shù)據(jù)訪問中，mc沿著某條移動路徑通過的概率越高，數(shù)據(jù)距mc當前的位置越近，且數(shù)據(jù)有效范圍區(qū)域的面積越大，或者越靠近mc當前移動路徑或移動方向上的lDD越容易被訪問。1.3備選預(yù)取數(shù)據(jù)的擇取數(shù)據(jù)預(yù)取的目標是希望在mc有限資源的前提下，使得所預(yù)取的數(shù)據(jù)盡可能都是mc需要的，并且盡可能多的提供有效查詢信息。在數(shù)據(jù)擇取過程中應(yīng)考慮以下兩

5、種情況：當s=0（緩存已滿）時，不論c中是否有剩余的未被預(yù)取的lDD，都將停止預(yù)取。當0s（緩存還有剩余空間）且size（i）>s，則根據(jù)mc當前位置和緩存的剩余空間來計算應(yīng)預(yù)取數(shù)據(jù)總量的大小。2模擬實驗及性能分析實驗以預(yù)取數(shù)據(jù)在緩存中的命中率為指標進行測試對比。測試的工作負載為一組隨機產(chǎn)生的查詢序列，由100個查詢組成，每次查詢生成的條件字段、條件值和數(shù)據(jù)表都是按照一定的規(guī)則隨機產(chǎn)生的。將mc的緩存的大小分別設(shè)置為實驗數(shù)據(jù)總量的10%、15%、20%、25%、30%時分別進行五組實驗，實驗結(jié)果如圖1所示。3結(jié)論在移動環(huán)境中，數(shù)據(jù)預(yù)取是有效提高訪問速度和減少數(shù)據(jù)訪問時間的一個可行辦法。本

6、文主要考慮mc訪問lDD可能性概率以及每一種數(shù)據(jù)能提供多少有效查詢信息，設(shè)計出一個預(yù)取價值選擇函數(shù)，在候選集中找到預(yù)取數(shù)據(jù)，只要這些數(shù)據(jù)出現(xiàn)在廣播信道，就預(yù)取到本地緩存。通過實驗比較，cDp策略比DDp、DHp策略更有效的提高了緩存命中率。參考文獻：1李國徽，楊兵，陳輝，等.移動環(huán)境下支持實時事務(wù)處理的數(shù)據(jù)預(yù)取J.計算機學報，2021，31（10）：1841-1847.2Yinl，caog.Adaptivepower-awareprefetchinwirelesaworksJieeetransactionswire1essmunications，2021.3（5）：1648-1658.3Jia

7、ngZ，Kleinrockl.webprefetchinginamobileenvironmentJ.ieeepersonalmunications，1998，5（5）：25-34.4personeVDn，grassiV，morlupiA.modelingandevaluationofprefetcAD快速繪制電路圖的方法與技巧探索ceedingsofthe4thAnnualinternationalconferenceonmobileputingandworking，1998：55-65.5ZhengB，xuJ，leeDl.cacheinvalidationandreplacementst