于曉寒，盧秉亮，梅義搏

（1.遼寧易橋財(cái)稅科技有限公司，沈陽110000；2.沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽110136）

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

于曉寒1，盧秉亮2，梅義搏2

（1.遼寧易橋財(cái)稅科技有限公司，沈陽110000；2.沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽110136）

位置相關(guān)信息服務(wù)中訪問數(shù)據(jù)涉及到復(fù)雜的空間計(jì)算，導(dǎo)致訪問數(shù)據(jù)的延遲時(shí)間較長，而數(shù)據(jù)預(yù)取能夠顯著提高數(shù)據(jù)的訪問速度，縮短訪問數(shù)據(jù)的時(shí)間?；贚DD的預(yù)取策略如DDP考慮了數(shù)據(jù)距離，但是沒有考慮數(shù)據(jù)的訪問概率和更新頻率及數(shù)據(jù)大小。針對以上問題提出基于價(jià)值的數(shù)據(jù)預(yù)?。–DP）策略，一些重要的數(shù)據(jù)預(yù)取因素如訪問概率、更新頻率、數(shù)據(jù)項(xiàng)大小、數(shù)據(jù)距離和有效范圍等都包含在價(jià)值函數(shù)里，根據(jù)價(jià)值函數(shù)值的大小來選擇被預(yù)取的數(shù)據(jù)。通過實(shí)驗(yàn)對比，CDP比DDP策略能更有效的提高緩存命中率。

位置相關(guān)信息服務(wù)；位置相關(guān)數(shù)據(jù)；數(shù)據(jù)預(yù)??；緩存命中率

1 引 言

隨著人們移動性的增加和移動終端設(shè)備的普及，在位置相關(guān)信息服務(wù)中，位置已經(jīng)成為非常重要的信息，用戶希望隨時(shí)隨地可以訪問與他們地理位置相關(guān)的信息數(shù)據(jù)，這就涉及到位置相關(guān)查詢（LocationDependent Query，LDQ）。然而移動計(jì)算環(huán)境下，網(wǎng)絡(luò)的弱連接、低帶寬使得用戶無法及時(shí)獲取所需的信息，特別是查詢位置相關(guān)數(shù)據(jù)（Location Dependent Data，LDD）時(shí)，容易因用戶位置的改變而導(dǎo)致查詢結(jié)果過時(shí)失效或者不正確。而數(shù)據(jù)預(yù)取技術(shù)能夠顯著提高數(shù)據(jù)訪問速度和充分利用廣播帶寬［1］，已經(jīng)得到廣泛采用。在移動客戶機(jī)（Mobile Client，MC）的緩存里保存部分?jǐn)?shù)據(jù)副本，可以大大減少訪問數(shù)據(jù)的延遲時(shí)間，這樣對于LDQ也會因響應(yīng)時(shí)間的縮短而提高查詢的準(zhǔn)確性和有效性，從而更好的滿足用戶需求。

針對以上問題和LDD的空間位置特性設(shè)計(jì)數(shù)據(jù)預(yù)取策略，主要考慮以下兩種因素：用戶未來使用到LDD的概率；LDD能夠給用戶提供多少有效查詢信息。為此提出一種基于價(jià)值的數(shù)據(jù)預(yù)?。–ost-Based Data Prefetch，CDP）策略，根據(jù)價(jià)值函數(shù)來選擇預(yù)取數(shù)據(jù)，在用戶實(shí)際使用LDD之前把數(shù)據(jù)預(yù)取到本地緩存。

2 基于價(jià)值的數(shù)據(jù)預(yù)取策略

2.1 位置相關(guān)數(shù)據(jù)的模型

位置相關(guān)數(shù)據(jù)（LDD），是指其值取決于具體地理位置的數(shù)據(jù)。如：本地天氣預(yù)報(bào)、事件，旅游景點(diǎn)等具有位置相關(guān)屬性的數(shù)據(jù)都屬于LDD，其在不同的地理區(qū)域值是不同的。由于LDD的值與地理位置之間密切相關(guān)，這類數(shù)據(jù)只在其對應(yīng)的地理區(qū)域才是正確的、有效的，也就是說LDD具有特定的適用范圍。

數(shù)據(jù)的有效范圍區(qū)域（Valid Scope Area），是指數(shù)據(jù)實(shí)例有效范圍的幾何區(qū)域。每個(gè)LDD實(shí)例有一個(gè)特定的有效范圍，只有在此有效范圍之內(nèi)，該實(shí)例才是正確的?？梢栽跊]有先驗(yàn)的用戶移動模式前提下，對同一項(xiàng)不同數(shù)據(jù)實(shí)例最精確的估計(jì)出被訪問的可能性，也就是說，數(shù)據(jù)的有效范圍區(qū)域越大，用戶訪問該數(shù)據(jù)的可能性也就越高。因?yàn)?，通常相對于較小的區(qū)域，用戶有更大可能性位于某個(gè)較大的區(qū)域。本文用近似圓法來描述數(shù)據(jù)的有效范圍，即用內(nèi)切圓的中心和半徑近似表示數(shù)據(jù)項(xiàng)di的有效范圍：vs（di）＝（Ldi，Rangei），其中Ldi為數(shù)據(jù)有效范圍的中心位置，Rangei為半徑，即Rangei是有效范圍邊界到中心位置的距離。

數(shù)據(jù)距離（Data Distance），是指MC當(dāng)前位置和數(shù)據(jù)實(shí)例有效范圍之間的距離。當(dāng)一個(gè)數(shù)據(jù)實(shí)例的有效范圍距用戶當(dāng)前位置還很遠(yuǎn)時(shí)，數(shù)據(jù)將有很小的機(jī)會被訪問，因?yàn)橛脩暨€要經(jīng)過一段時(shí)間才能進(jìn)入該數(shù)據(jù)的有效范圍區(qū)域，而在進(jìn)入有效范圍區(qū)域之前，數(shù)據(jù)實(shí)例對MC來說是無效的。用LMC＝（lx，ly）表示MC的當(dāng)前位置，則di到MC的數(shù)據(jù)距離可用｜LMC-Ldi｜表示。

2.2 預(yù)取數(shù)據(jù)的系統(tǒng)模型

預(yù)取策略使用一個(gè)基于請求的廣播模型按需廣播數(shù)據(jù)。數(shù)據(jù)庫服務(wù)器上的數(shù)據(jù)庫由 N個(gè)數(shù)據(jù)D1，D2，…，DN組成，服務(wù)器負(fù)責(zé)維護(hù)數(shù)據(jù)庫和響應(yīng)MC的數(shù)據(jù)請求。當(dāng)MC需要訪問的數(shù)據(jù)在緩存中找不到時(shí)，就通過上行鏈路向服務(wù)器發(fā)送請求，服務(wù)器接受到該請求后通過廣播信道推送所請求的數(shù)據(jù)，MC監(jiān)聽廣播信道，找到自己需要的數(shù)據(jù)后通過下行鏈路預(yù)取到本地緩存中。假設(shè)數(shù)據(jù)只在服務(wù)器端更新，用μ表示單位時(shí)間內(nèi)數(shù)據(jù)更新的頻率，用λ表示單位時(shí)間內(nèi)MC對服務(wù)器中LDD的訪問頻率。本文假設(shè)MC對服務(wù)器中數(shù)據(jù)項(xiàng)di的訪問模型類似服從Zipf分布，MC訪問數(shù)據(jù)項(xiàng)di的概率為λi；而服務(wù)器中每個(gè)數(shù)據(jù)的更新是隨機(jī)的，假設(shè)數(shù)據(jù)更新模型服從均勻分布，di在單位時(shí)間內(nèi)的更新頻率為μi。

由于LDD的位置相關(guān)性，即數(shù)據(jù)只有在其適用范圍內(nèi)才有效，那么只有MC位于其適用范圍內(nèi)時(shí)，該種LDD的值對于MC才是正確有意義的。所以在數(shù)據(jù)預(yù)取時(shí)首先要考慮 MC所在數(shù)據(jù)區(qū)域的LDD，其次還應(yīng)考慮MC可能移動路徑通過其適用范圍內(nèi)的LDD，將這些LDD列為數(shù)據(jù)預(yù)取的候選集C。得到LDD預(yù)取的候選集后，根據(jù)預(yù)取價(jià)值函數(shù)獲得它的一個(gè)預(yù)取子集S，對任意數(shù)據(jù)di∈S出現(xiàn)在廣播信道時(shí)，預(yù)取到本地緩存。

2.3 CDP預(yù)取方法

為了找出預(yù)取子集S，需要衡量C中每一種LDD被預(yù)取后對MC的影響。在MC緩存有限的情況下，若預(yù)取的LDD確實(shí)被訪問到了，即便是由于預(yù)取LDD耗費(fèi)了一定的緩存空間，但是仍可以給MC帶來獲益，即預(yù)取的數(shù)據(jù)能給MC帶來縮短查詢時(shí)間的收益。為此本文提出CDP策略，預(yù)取時(shí)根據(jù)價(jià)值函數(shù)的值進(jìn)行選擇，預(yù)取價(jià)值函數(shù)如下：

式（1）中Puseful為MC訪問LDD的概率，benefit為MC預(yù)取LDD的獲益價(jià)值，penalty為預(yù)取LDD的懲罰代價(jià)。

2.3.1 數(shù)據(jù)預(yù)取的獎(jiǎng)懲代價(jià)

數(shù)據(jù)預(yù)取到本地緩存后，并非所有的數(shù)據(jù)都是MC需要的，經(jīng)過運(yùn)算處理后能成為有效查詢的數(shù)據(jù)才是用戶需要的，只有這部分?jǐn)?shù)據(jù)才能給MC的查詢訪問帶來獲益。用RiQ表示有效查詢信息比值，即查詢時(shí)數(shù)據(jù)經(jīng)過運(yùn)算處理后產(chǎn)生數(shù)據(jù)量與原來數(shù)據(jù)量的比值。若預(yù)取的數(shù)據(jù)確實(shí)被MC訪問到了，即便是由于預(yù)取耗費(fèi)了一定代價(jià)，但是仍然可以給MC帶來“縮短訪問時(shí)間”的收益。本文用fbenefit（di）表示預(yù)取數(shù)據(jù)di的獲益價(jià)值函數(shù)，即MC未預(yù)取數(shù)據(jù)時(shí)的訪問時(shí)間與預(yù)取數(shù)據(jù)時(shí)的訪問時(shí)間減少的比例。如公式（2）所示：

式（2）中size（i）為di的大小，Tno_prefetch（i）為沒有預(yù)取時(shí)MC請求di的訪問延遲時(shí)間，Tprefetch（i）為di在本地緩存被訪問所需的時(shí)間，Bandwidth是帶寬大小，size（i）／Bandwidth為di在無限網(wǎng)絡(luò)傳輸所需的時(shí)間。

在MC有限資源的條件下，預(yù)取數(shù)據(jù)需要花費(fèi)一定的代價(jià)，即預(yù)取di占用size（i）大小的緩存空間，并且預(yù)取該數(shù)據(jù)還消耗了一定的電能。用MC預(yù)取所消耗的電池電量占整個(gè)剩余電池電量的比例來反映其懲罰代價(jià)，用fpenalty（di）表示預(yù)取數(shù)據(jù)di的懲罰代價(jià)函數(shù)，如公式（3）所示。

式（3）中α為傳輸每比特?cái)?shù)據(jù)MC所消耗的電量，e為MC當(dāng)前的剩余電量。

2.3.2 訪問LDD的概率

對于MC訪問某一種LDD可能性的概率，主要以MC經(jīng)過該數(shù)據(jù)有效范圍的概率和未來訪問該數(shù)據(jù)的概率為依據(jù)，因此把MC將來可能經(jīng)過有效范圍內(nèi)數(shù)據(jù)列為預(yù)取的候選集C。在評價(jià)MC訪問C中某一di的概率時(shí)主要考慮以下兩點(diǎn)因素：

（1）從時(shí)間角度來考慮。越久未被更新的數(shù)據(jù)，說明其因服務(wù)器端的數(shù)據(jù)更新而導(dǎo)致預(yù)取數(shù)據(jù)失效的可能性越??；而越久未被訪問的數(shù)據(jù)說明其比較陳舊，再次被訪問的可能性就越小。因此，為了反映數(shù)據(jù)最近經(jīng)常被訪問且不易更新的訪問概率，本文用式（4）來表示在時(shí)間上訪問數(shù)據(jù)的概率。

其中tcurrent是系統(tǒng)當(dāng)前時(shí)間，tu，i是di最后一次被更新的時(shí)間，tq，i是di最后一次被訪問的時(shí)間。式（4）中若tcurrent-tq，i＝0，則令（tcurrent-tu，i）／（tcurrenttq，i）＝1，即剛被訪問過的數(shù)據(jù)很可能被再次訪問；若μi＝0，則令μi／λi＝1，即很久未被更新的數(shù)據(jù)在未來較短時(shí)間內(nèi)也不會被再次更新。

（2）從空間角度來考慮。研究表明［5］，在位置相關(guān)信息服務(wù)的數(shù)據(jù)訪問中，MC沿著某條移動路徑通過的概率越高，數(shù)據(jù)距MC當(dāng)前的位置越近，且數(shù)據(jù)有效范圍區(qū)域的面積越大，或者越靠近MC當(dāng)前移動路徑或移動方向上的LDD越容易被訪問。

用Puseful（di）表示訪問di的概率。假設(shè)總共有k條可能移動路徑（Possible Moving Paths，PMP），其中沿PMPj（1≤j≤k）移動的概率為PPMPj（（∑PPMPj）≤1）。若是MC沿著PMPj移動，從出發(fā)到離開di有效范圍區(qū)域的距離為｜LMC-Ldi｜＋Rangei，而其中在di有效范圍區(qū)域的距離為2Rangei，那么訪問di的概率：

2.4 備選預(yù)取數(shù)據(jù)的擇取

數(shù)據(jù)預(yù)取的目標(biāo)是希望在MC有限資源的前提下，使得所預(yù)取的數(shù)據(jù)盡可能都是MC需要的，并且盡可能多的提供有效查詢信息。若數(shù)據(jù)的屬性一定時(shí)，對于每一數(shù)據(jù)項(xiàng)di，其預(yù)取價(jià)值函數(shù)為。

假設(shè)MC緩存的剩余空閑空間為Sfree，為了提高系統(tǒng)的整體性能，考慮到預(yù)取數(shù)據(jù)對MC有限資源的影響，希望對于候選集C中被擇取的n種LDD，其預(yù)取獲得的總價(jià)值盡可能的接近最大值。那么對于預(yù)取候選集合C中的數(shù)據(jù)di，即尋找一個(gè)預(yù)取價(jià)值最大的預(yù)取子集S，用下列目標(biāo)函數(shù)描述：

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

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

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

3 模擬實(shí)驗(yàn)及性能分析

3.1 試驗(yàn)環(huán)境及參數(shù)設(shè)置

為了評估本文提出的CDP策略，參照文獻(xiàn)［4］提出的實(shí)驗(yàn)場景進(jìn)行模擬實(shí)驗(yàn)，并和DDP策略進(jìn)行對比。實(shí)驗(yàn)系統(tǒng)中有一個(gè)服務(wù)器和多個(gè)MC，它們之間由無線網(wǎng)絡(luò)連接組成。服務(wù)器負(fù)責(zé)維護(hù)數(shù)據(jù)庫，并且根據(jù)MC請求的預(yù)取數(shù)據(jù)集合，采用按需廣播的方式向MC廣播數(shù)據(jù)內(nèi)容和失效報(bào)告內(nèi)容。，服務(wù)器的數(shù)據(jù)庫中有一個(gè)表，數(shù)據(jù)項(xiàng)的總數(shù)為1000，每個(gè)數(shù)據(jù)的大小在最大／小值之間平均分布。數(shù)據(jù)訪問模式和更新模式應(yīng)用在這些數(shù)據(jù)項(xiàng)上，假設(shè)在整個(gè)訪問過程中，80%的更新發(fā)生在20%的數(shù)據(jù)分區(qū)上，數(shù)據(jù)的訪問模式服從Zifp分布，數(shù)據(jù)的訪問頻率、更新頻率和數(shù)據(jù)項(xiàng)的大小之間都沒有明顯聯(lián)系。在模擬實(shí)驗(yàn)中，MC在一個(gè)4km×4km的地圖上移動并隨時(shí)發(fā)出查詢請求，LDD在地圖上均勻分布，并且MC如果處于連接狀態(tài)，則一直監(jiān)聽廣播內(nèi)容和失效報(bào)告，以預(yù)取數(shù)據(jù)和維護(hù)本地緩存數(shù)據(jù)一致性。表1包含了實(shí)驗(yàn)數(shù)據(jù)的關(guān)鍵參數(shù)和其缺省值。

表1 實(shí)驗(yàn)參數(shù)及缺省值

3.2 實(shí)驗(yàn)結(jié)果分析

為了更好的評估預(yù)取策略的效果，實(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所示。

圖1 緩存大小對緩存命中率的影響

由圖1所示的實(shí)驗(yàn)結(jié)果可以看出，CDP策略在預(yù)取數(shù)據(jù)的緩存命中率方面，相對于DDP策略提高比較明顯。這是因?yàn)镈DP策略僅考慮了數(shù)據(jù)距離，在預(yù)取時(shí)僅考慮距離近的數(shù)據(jù)，但其沒有考慮數(shù)據(jù)的訪問概率、更新頻率和大小；而CDP策略綜合考慮了數(shù)據(jù)的訪問概率、更新頻率、數(shù)據(jù)大小、距離和有效范圍等數(shù)據(jù)預(yù)取的關(guān)鍵因素，把這些價(jià)值較高的數(shù)據(jù)預(yù)取到本地緩存。由實(shí)驗(yàn)結(jié)果還可以看出隨著緩存容量的增加，其緩存命中率也隨之有所增加，但當(dāng)緩存容量增加到一定幅度時(shí)，即當(dāng)緩存大小為數(shù)據(jù)總量的25%以后，單純提高系統(tǒng)緩存容量的大小，對查詢命中率的影響卻不是很明顯。

4 結(jié)束語

在移動環(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策略更有效的提高了緩存命中率。

［1］李國徽，楊兵，陳輝，等.移動環(huán)境下支持實(shí)時(shí)事務(wù)處理的數(shù)據(jù)預(yù)取［J］.計(jì)算機(jī)學(xué)報(bào)，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.

A Method of Data Prefetch in Location Dependent Information Services

YU Xiao-han1，LU Bing-liang2，MEIYi-bo2
（1.Liaoning YiQiao Fiscal and Taxation Technology Co.，Ltd.，Shenyang 110000，China；2.School of Computer，Shenyang Aerospace University，Shenyang 110136，China）

Accessing data related to complex spatial calculations leads to a longer delay time in location dependent information services.The data prefetch can greatly improve data access speed and shorten the delay time.The prefetch strategy，based on LDD，such as DDP，considers the data distance except for the access probabilities，update rates and the size.So，the cost-based data prefetch（CDP）strategy is proposed，which takes such important prefetch factors as access probabilities，update rates，data size，data distance，valid scope，etc.into cost function.The prefetch data is selected according to the value of the cost function.The contrast experiments show that CDP is more effective than DDP strategies to improve the cache hit rate.

Mobile database；Location dependent data；Data prefetching；Cache hit rate

10.3969／j.issn.1002-2279.2014.01.017

TP311.138

：A

：1002-2279（2014）01-0061-04

于曉寒（1978-），男，遼寧沈陽人，碩士研究生，主研方向：管理信息系統(tǒng)與數(shù)據(jù)庫。

2013-06-09