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

于曉寒，盧秉亮，梅義搏

（1.遼寧易橋財稅科技有限公司，沈陽110000；2.沈陽航空航天大學計算機學院，沈陽110136）

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

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

（1.遼寧易橋財稅科技有限公司，沈陽110000；2.沈陽航空航天大學計算機學院，沈陽110136）

位置相關信息服務中訪問數據涉及到復雜的空間計算，導致訪問數據的延遲時間較長，而數據預取能夠顯著提高數據的訪問速度，縮短訪問數據的時間。基于LDD的預取策略如DDP考慮了數據距離，但是沒有考慮數據的訪問概率和更新頻率及數據大小。針對以上問題提出基于價值的數據預取（CDP）策略，一些重要的數據預取因素如訪問概率、更新頻率、數據項大小、數據距離和有效范圍等都包含在價值函數里，根據價值函數值的大小來選擇被預取的數據。通過實驗對比，CDP比DDP策略能更有效的提高緩存命中率。

位置相關信息服務；位置相關數據；數據預取；緩存命中率

1 引 言

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

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

2 基于價值的數據預取策略

2.1 位置相關數據的模型

位置相關數據（LDD），是指其值取決于具體地理位置的數據。如：本地天氣預報、事件，旅游景點等具有位置相關屬性的數據都屬于LDD，其在不同的地理區域值是不同的。由于LDD的值與地理位置之間密切相關，這類數據只在其對應的地理區域才是正確的、有效的，也就是說LDD具有特定的適用范圍。

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

數據距離（Data Distance），是指MC當前位置和數據實例有效范圍之間的距離。當一個數據實例的有效范圍距用戶當前位置還很遠時，數據將有很小的機會被訪問，因為用戶還要經過一段時間才能進入該數據的有效范圍區域，而在進入有效范圍區域之前，數據實例對MC來說是無效的。用LMC＝（lx，ly）表示MC的當前位置，則di到MC的數據距離可用｜LMC-Ldi｜表示。

2.2 預取數據的系統模型

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

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

2.3 CDP預取方法

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

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

2.3.1 數據預取的獎懲代價

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

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

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

式（3）中α為傳輸每比特數據MC所消耗的電量，e為MC當前的剩余電量。

2.3.2 訪問LDD的概率

對于MC訪問某一種LDD可能性的概率，主要以MC經過該數據有效范圍的概率和未來訪問該數據的概率為依據，因此把MC將來可能經過有效范圍內數據列為預取的候選集C。在評價MC訪問C中某一di的概率時主要考慮以下兩點因素：

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

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

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

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

2.4 備選預取數據的擇取

數據預取的目標是希望在MC有限資源的前提下，使得所預取的數據盡可能都是MC需要的，并且盡可能多的提供有效查詢信息。若數據的屬性一定時，對于每一數據項di，其預取價值函數為。

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

在數據擇取過程中應考慮以下兩種情況：

（1）當Sfree＝0（緩存已滿）時，不論C中是否有剩余的未被預取的LDD，都將停止預取。

（2）當0＜Sfree（緩存還有剩余空間）且（i）＞Sfree時，則根據MC當前位置和緩存的剩余空間來計算應預取數據總量的大小。

3 模擬實驗及性能分析

3.1 試驗環境及參數設置

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

表1 實驗參數及缺省值

3.2 實驗結果分析

為了更好的評估預取策略的效果，實驗以預取數據在緩存中的命中率為指標進行測試對比。測試的工作負載為一組隨機產生的查詢序列，由100個查詢組成，每次查詢生成的條件字段、條件值和數據表都是按照一定的規則隨機產生的。將MC的緩存大小分別設置為實驗數據總量的10%、15%、20%、25%、30%時分別進行五組實驗，實驗結果如圖1所示。

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

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

4 結束語

在移動環境中，數據預取是有效提高訪問速度和減少數據訪問時間的一個可行辦法。本文主要考慮MC訪問LDD的可能性概率以及每一種數據能提供多少有效查詢信息，設計出一個預取價值選擇函數，在候選集中找到預取數據，只要這些數據出現在廣播信道，就預取到本地緩存。通過實驗比較，CDP策略比DDP、DHP策略更有效的提高了緩存命中率。

［1］李國徽，楊兵，陳輝，等.移動環境下支持實時事務處理的數據預取［J］.計算機學報，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-），男，遼寧沈陽人，碩士研究生，主研方向：管理信息系統與數據庫。

2013-06-09