導(dǎo)語：信息服務(wù)的數(shù)據(jù)預(yù)取方法綜述一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：基于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）時，容易因用戶位置的改變而導(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當(dāng)前位置和數(shù)據(jù)實例有效范圍之間的距離。

1.2CDP預(yù)取方法本文提出CDP策略，預(yù)取時根據(jù)價值函數(shù)的值進(jìn)行選擇，預(yù)取價值函數(shù)如下：Cost=Puseful×（benefit-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)過運(yùn)算處理后能成為有效查詢的數(shù)據(jù)才是用戶需要的，只有這部分?jǐn)?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將來可能經(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當(dāng)前的位置越近，且數(shù)據(jù)有效范圍區(qū)域的面積越大，或者越靠近MC當(dāng)前移動路徑或移動方向上的LDD越容易被訪問。

1.3備選預(yù)取數(shù)據(jù)的擇取數(shù)據(jù)預(yù)取的目標(biāo)是希望在MC有限資源的前提下，使得所預(yù)取的數(shù)據(jù)盡可能都是MC需要的，并且盡可能多的提供有效查詢信息。

在數(shù)據(jù)擇取過程中應(yīng)考慮以下兩種情況：

①當(dāng)S=0（緩存已滿）時，不論C中是否有剩余的未被預(yù)取的LDD，都將停止預(yù)取。

②當(dāng)0＜S（緩存還有剩余空間）且size（i）>S，則根據(jù)MC當(dāng)前位置和緩存的剩余空間來計算應(yīng)預(yù)取數(shù)據(jù)總量的大小。

2模擬實驗及性能分析

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

3結(jié)論

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

參考文獻(xiàn)：

[1]李國徽，楊兵，陳輝，等.移動環(huán)境下支持實時事務(wù)處理的數(shù)據(jù)預(yù)取[J].計算機(jī)學(xué)報，2008，31（10）：1841-1847.

[2]YinL，CaoG.Adaptivepower-awareprefetchinwirelesanetworks[J]．IEEETransactionsWire1essCommunications，2004.3（5）：1648-1658.

[3]JiangZ，KleinrockL.Webprefetchinginamobileenvironment[J].IEEEPersonalCommunications，1998，5（5）：25-34.

[4]PersoneVDN，GrassiV，MorlupiA.ModelingandevaluationofprefetCAD快速繪制電路圖的方法與技巧探索chingpoliciesforcontext-awareinformationservices

[C].Proceedingsofthe4thAnnualInternationalConferenceonMobileComputingandNetworking，1998：55-65.

[5]ZhengB，XuJ，LeeDL.Cacheinvalidationandreplacementstrategiesforlocation-dependentdatainmobileenvironments[J].IEEETransactionsonComputers，2002，51（10）：1141-1153.