位置相關(guān)信息服務(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策略更有效的提高緩存的命中率。
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.
關(guān)鍵詞：位置相關(guān)信息服務(wù)；位置相關(guān)數(shù)據(jù)；數(shù)據(jù)預(yù)取；緩存命中率
Key words: location-dependent information services；location dependent data；data prefetching；cache hit ratio
0 引言
移動計算環(huán)境下，網(wǎng)絡(luò)的弱連接、低帶寬使得用戶而無法及時獲取所需的信息，特別是查詢位置相關(guān)數(shù)據(jù)（Location Dependent Data，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ū)域（Valid Scope Area），是指數(shù)據(jù)實例有效范圍的幾何區(qū)域。每個LDD實例有一個特定的有效范圍，只有在此有效范圍之內(nèi)，該實例才是正確的。
數(shù)據(jù)距離（Data Distance），是指MC當(dāng)前位置和數(shù)據(jù)實例有效范圍之間的距離。
1.2 CDP預(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]Yin L，Cao G.Adaptive power-aware prefetch in wirelesa networks[J]．IEEE Transactions Wire1ess Communications，2004.3（5）：1648-1658.
[3]Jiang Z，Kleinrock L.Web prefetching in a mobile environment[J].IEEE Personal Communications，1998，5（5）：25-34.
[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 Networking，1998：55-65.
[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.
【位置相關(guān)信息服務(wù)中一種基于價值的數(shù)據(jù)預(yù)取方法】相關(guān)文章：
一種基于位置信息的UWB Ad Hoc網(wǎng)絡(luò)路由算法03-30
基于顧客價值的服務(wù)戰(zhàn)略特征分析03-22
基于ＤＣＦ和期權(quán)價值的戰(zhàn)略評價方法03-21
基于SDO的異構(gòu)服務(wù)數(shù)據(jù)模型研究03-28
一種檢測轉(zhuǎn)子位置的可靠方法03-07
H.264中一種改進(jìn)的基于結(jié)構(gòu)相似性的運(yùn)動估計方法03-07
價值鏈模型下基于過程的服務(wù)營銷03-23