- 相關(guān)推薦
位置相關(guān)信息服務(wù)中一種基于價(jià)值的數據預取方法
摘要：基于LDD的預取策略如DDP考慮了數據距離，但是沒(méi)有考慮數據的訪(fǎng)問(wèn)概率和更新頻率和數據大小，針對以上問(wèn)題提出基于價(jià)值的數據預取(CDP)策略，一些重要的數據預取因素如訪(fǎng)問(wèn)概率、更新頻率、數據項大小、數據距離和有效范圍等都包含在價(jià)值函數里，根據價(jià)值函數值的大小來(lái)選擇被預取的數據。通過(guò)實(shí)驗對比，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)數據；數據預��；緩存命中率
Key words: location-dependent information services；location dependent data；data prefetching；cache hit ratio
0 引言
移動(dòng)計算環(huán)境下，網(wǎng)絡(luò )的弱連接、低帶寬使得用戶(hù)而無(wú)法及時(shí)獲取所需的信息，特別是查詢(xún)位置相關(guān)數據（Location Dependent Data，LDD）時(shí)，容易因用戶(hù)位置的改變而導致查詢(xún)結果過(guò)時(shí)失效或者不正確。而數據預取技術(shù)能夠顯著(zhù)提高數據訪(fǎng)問(wèn)速度和充分利用廣播帶寬[1]。
1 基于價(jià)值的數據預取策略
1.1 位置相關(guān)數據的模型 位置相關(guān)數據（LDD），是指其值取決于具體地理位置的數據，LDD具有特定的適用范圍。
數據的有效范圍區域（Valid Scope Area），是指數據實(shí)例有效范圍的幾何區域。每個(gè)LDD實(shí)例有一個(gè)特定的有效范圍，只有在此有效范圍之內，該實(shí)例才是正確的。
數據距離（Data Distance），是指MC當前位置和數據實(shí)例有效范圍之間的距離。
1.2 CDP預取方法 本文提出CDP策略，預取時(shí)根據價(jià)值函數的值進(jìn)行選擇，預取價(jià)值函數如下：Cost=Puseful×（benefit-penalty）（1）
式（1）中Puseful為MC訪(fǎng)問(wèn)LDD的概率，benefit為MC預取LDD的獲益價(jià)值，penalty為預取LDD的懲罰代價(jià)。
1.2.1 數據預取的獎懲代價(jià) 數據預取到本地緩存后，并非所有的數據都是MC需要的，經(jīng)過(guò)運算處理后能成為有效查詢(xún)的數據才是用戶(hù)需要的，只有這部分數據才能給MC的查詢(xún)訪(fǎng)問(wèn)帶來(lái)獲益。本文用fbenefit（di）表示預取數據di的獲益價(jià)值函數，即MC未預取數據時(shí)的訪(fǎng)問(wèn)時(shí)間與預取數據時(shí)的訪(fǎng)問(wèn)時(shí)間減少的比例。
1.2.2 訪(fǎng)問(wèn)LDD的概率 對于MC訪(fǎng)問(wèn)某一種LDD可能性的概率，主要以MC經(jīng)過(guò)該數據有效范圍的概率和未來(lái)訪(fǎng)問(wèn)該數據的概率為依據，因此把MC將來(lái)可能經(jīng)過(guò)有效范圍內數據列為預取的候選集C。主要考慮以下兩點(diǎn)因素：①從時(shí)間的角度來(lái)考慮。越久未被更新的數據，說(shuō)明其因服務(wù)器端的數據更新而導致預取數據失效的可能性越��；而越久未被訪(fǎng)問(wèn)的數據說(shuō)明其比較陳舊，再次被訪(fǎng)問(wèn)的可能性就越小。②從空間的角度來(lái)考慮。研究表明，在位置相關(guān)信息服務(wù)的數據訪(fǎng)問(wèn)中，MC沿著(zhù)某條移動(dòng)路徑通過(guò)的概率越高，數據距MC當前的位置越近，且數據有效范圍區域的面積越大，或者越靠近MC當前移動(dòng)路徑或移動(dòng)方向上的LDD越容易被訪(fǎng)問(wèn)。
1.3 備選預取數據的擇取 數據預取的目標是希望在MC有限資源的前提下，使得所預取的數據盡可能都是MC需要的，并且盡可能多的提供有效查詢(xún)信息。
在數據擇取過(guò)程中應考慮以下兩種情況：
①當S=0（緩存已滿(mǎn)）時(shí)，不論C中是否有剩余的未被預取的LDD，都將停止預取。
②當0＜S（緩存還有剩余空間）且size（i）>S，則根據MC當前位置和緩存的剩余空間來(lái)計算應預取數據總量的大小。
2 模擬實(shí)驗及性能分析
實(shí)驗以預取數據在緩存中的命中率為指標進(jìn)行測試對比。測試的工作負載為一組隨機產(chǎn)生的查詢(xún)序列，由100個(gè)查詢(xún)組成，每次查詢(xún)生成的條件字段、條件值和數據表都是按照一定的規則隨機產(chǎn)生的。將MC的緩存的大小分別設置為實(shí)驗數據總量的10%、15%、20%、25%、30%時(shí)分別進(jìn)行五組實(shí)驗，實(shí)驗結果如圖1所示。
3 結論
在移動(dòng)環(huán)境中，數據預取是有效提高訪(fǎng)問(wèn)速度和減少數據訪(fǎng)問(wèn)時(shí)間的一個(gè)可行辦法。本文主要考慮MC訪(fǎng)問(wèn)LDD可能性概率以及每一種數據能提供多少有效查詢(xún)信息，設計出一個(gè)預取價(jià)值選擇函數，在候選集中找到預取數據，只要這些數據出現在廣播信道，就預取到本地緩存。通過(guò)實(shí)驗比較，CDP策略比DDP、DHP策略更有效的提高了緩存命中率。
參考文獻：
[1]李國徽，楊兵，陳輝，等.移動(dòng)環(huán)境下支持實(shí)時(shí)事務(wù)處理的數據預取[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ù)中一種基于價(jià)值的數據預取方法】相關(guān)文章：
一種基于路測數據的基站定位方法03-07
基于聚類(lèi)分析的數據挖掘方法03-08
一種基于位置信息的UWB Ad Hoc網(wǎng)絡(luò )路由算法03-30
基于ＤＣＦ和期權價(jià)值的戰略評價(jià)方法03-21
基于SDO的異構服務(wù)數據模型研究03-28
一種檢測轉子位置的可靠方法03-07