位置相關信息服務中一種基于價值的數據預取方法

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