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

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

6、果過時(shí)失效或者不正確。而數(shù)據(jù)預(yù)取技術(shù)能夠顯著提高數(shù)據(jù)訪問速度和充分利用廣播帶寬[1]。 </p><p>　　1 基于價(jià)值的數(shù)據(jù)預(yù)取策略 </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ù)實(shí)例

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

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

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

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

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

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

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

14、t;/p><p><b>　　參考文獻(xiàn)： </b></p><p>　　[1]李國徽，楊兵，陳輝，等.移動(dòng)環(huán)境下支持實(shí)時(shí)事務(wù)處理的數(shù)據(jù)預(yù)取[J].計(jì)算機(jī)學(xué)報(bào)，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. <