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

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

摘要：基于LDD的預(yù)取策略如DDP考慮了數(shù)據(jù)距離，但是沒有考慮數(shù)據(jù)的訪問(wèn)概率和更新頻率和數(shù)據(jù)大小，針對(duì)以上問(wèn)題提出基于價(jià)值的數(shù)據(jù)預(yù)取(CDP)策略，一些重要的數(shù)據(jù)預(yù)取因素如訪問(wèn)概率、更新頻率、數(shù)據(jù)項(xiàng)大小、數(shù)據(jù)距離和有效范圍等都包含在價(jià)值函數(shù)里，根據(jù)價(jià)值函數(shù)值的大小來(lái)選擇被預(yù)取的數(shù)據(jù)。通過(guò)實(shí)驗(yàn)對(duì)比，CDP比DDP策略更有效的提高緩存的命中率。Abstract:LDD-basedprefetchingstrategieslikeDDPtakethedatadistanceintoaccount，butdonottakeintoaccounttheaccessprobabilityofdata，updatingdataandsizeoffrequency.Fortheseissues，thispaperproposesavalue-baseddataprefetching(CDP)strategy，andsomeimportantdataprefetchingfactors，suchasaccessprobability，updatefrequency，dataitemsize，datadistanceandrangeofdataareincludedinthevaluefunction.Wecanchoosetheprefetchingdatabasedonthesizeoffunctionvalue.Bycomparingtheexperiment，CDPismoreeffectivethanDDPstrategytoimprovethecachehitrate.關(guān)鍵詞：位置相關(guān)信息服務(wù)；位置相關(guān)數(shù)據(jù)；數(shù)據(jù)預(yù)取；緩存命中率Keywords:location-dependentinformationservices；locationdependentdata；dataprefetching；cachehitratio0引言移動(dòng)計(jì)算環(huán)境下，網(wǎng)絡(luò)的弱連接、低帶寬使得用戶而無(wú)法及時(shí)獲取所需的信息，特別是查詢位置相關(guān)數(shù)據(jù)（LocationDependentData，LDD）時(shí)，容易因用戶位置的改變而導(dǎo)致查詢結(jié)果過(guò)時(shí)失效或者不正確。而數(shù)據(jù)預(yù)取技術(shù)能夠顯著提高數(shù)據(jù)訪問(wèn)速度和充分利用廣播帶寬[1]。1基于價(jià)值的數(shù)據(jù)預(yù)取策略1.1位置相關(guān)數(shù)據(jù)的模型位置相關(guān)數(shù)據(jù)（LDD），是指其值取決于具體地理位置的數(shù)據(jù)，LDD具有特定的適用范圍。數(shù)據(jù)的有效范圍區(qū)域（ValidScopeArea），是指數(shù)據(jù)實(shí)例有效范圍的幾何區(qū)域。每個(gè)LDD實(shí)例有一個(gè)特定的有效范圍，只有在此有效范圍之內(nèi)，該實(shí)例才是正確的。數(shù)據(jù)距離（DataDistance），是指MC當(dāng)前位置和數(shù)據(jù)實(shí)例有效范圍之間的距離。1.2CDP預(yù)取方法本文提出CDP策略，預(yù)取時(shí)根據(jù)價(jià)值函數(shù)的值進(jìn)行選擇，預(yù)取價(jià)值函數(shù)如下：Cost=Puseful×（benefit-penalty）（1）式（1）中Puseful為MC訪問(wèn)LDD的概率，benefit為MC預(yù)取LDD的獲益價(jià)值，penalty為預(yù)取LDD的懲罰代價(jià)。1.2.1數(shù)據(jù)預(yù)取的獎(jiǎng)懲代價(jià)數(shù)據(jù)預(yù)取到本地緩存后，并非所有的數(shù)據(jù)都是MC需要的，經(jīng)過(guò)運(yùn)算處理后能成為有效查詢的數(shù)據(jù)才是用戶需要的，只有這部分?jǐn)?shù)據(jù)才能給MC的查詢?cè)L問(wèn)帶來(lái)獲益。本文用fbenefit（di）表示預(yù)取數(shù)據(jù)di的獲益價(jià)值函數(shù)，即MC未預(yù)取數(shù)據(jù)時(shí)的訪問(wèn)時(shí)間與預(yù)取數(shù)據(jù)時(shí)的訪問(wèn)時(shí)間減少的比例。1.2.2訪問(wèn)LDD的概率對(duì)于MC訪問(wèn)某一種LDD可能性的概率，主要以MC經(jīng)過(guò)該數(shù)據(jù)有效范圍的概率和未來(lái)訪問(wèn)該數(shù)據(jù)的概率為依據(jù)，因此把MC將來(lái)可能經(jīng)過(guò)有效范圍內(nèi)數(shù)據(jù)列為預(yù)取的候選集C。主要考慮以下兩點(diǎn)因素：①?gòu)臅r(shí)間的角度來(lái)考慮。越久未被更新的數(shù)據(jù)，說(shuō)明其因服務(wù)器端的數(shù)據(jù)更新而導(dǎo)致預(yù)取數(shù)據(jù)失效的可能性越小；而越久未被訪問(wèn)的數(shù)據(jù)說(shuō)明其比較陳舊，再次被訪問(wèn)的可能性就越小。②從空間的角度來(lái)考慮。研究表明，在位置相關(guān)信息服務(wù)的數(shù)據(jù)訪問(wèn)中，MC沿著某條移動(dòng)路徑通過(guò)的概率越高，數(shù)據(jù)距MC當(dāng)前的位置越近，且數(shù)據(jù)有效范圍區(qū)域的面積越大，或者越靠近MC當(dāng)前移動(dòng)路徑或移動(dòng)方向上的LDD越容易被訪問(wèn)。1.3備選預(yù)取數(shù)據(jù)的擇取數(shù)據(jù)預(yù)取的目標(biāo)是希望在MC有限資源的前提下，使得所預(yù)取的數(shù)據(jù)盡可能都是MC需要的，并且盡可能多的提供有效查詢信息。在數(shù)據(jù)擇取過(guò)程中應(yīng)考慮以下兩種