摘要：基于LDD的预取策略如DDP考虑了数据距离，但是没有考虑数据的访问概率和更新频率和数据大小，针对以上问题提出基于价值的数据预取(CDP)策略，一些重要的数据预取因素如访问概率、更新频率、数据项大小、数据距离和有效范围等都包含在价值函数里，根据价值函数值的大小来选择被预取的数据。通过实验对比，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.
关键词：位置相关信息服务；位置相关数据；数据预取；缓存命中率
Key words: location-dependent information services；location dependent data；data prefetching；cache hit ratio
0 引言
移动计算环境下，网络的弱连接、低带宽使得用户而无法及时获取所需的信息，特别是查询位置相关数据（Location Dependent Data，LDD）时，容易因用户位置的改变而导致查询结果过时失效或者不正确。而数据预取技术能够显著提高数据访问速度和充分利用广播带宽[1]。
1 基于价值的数据预取策略
1.1 位置相关数据的模型 位置相关数据（LDD），是指其值取决于具体地理位置的数据，LDD具有特定的适用范围。
数据的有效范围区域（Valid Scope Area），是指数据实例有效范围的几何区域。每个LDD实例有一个特定的有效范围，只有在此有效范围之内，该实例才是正确的。
数据距离（Data Distance），是指MC当前位置和数据实例有效范围之间的距离。
1.2 CDP预取方法 本文提出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需要的，并且尽可能多的提供有效查询信息。
在数据择取过程中应考虑以下两种情况：
①当S=0（缓存已满）时，不论C中是否有剩余的未被预取的LDD，都将停止预取。
②当0＜S（缓存还有剩余空间）且size（i）>S，则根据MC当前位置和缓存的剩余空间来计算应预取数据总量的大小。
2 模拟实验及性能分析
实验以预取数据在缓存中的命中率为指标进行测试对比。测试的工作负载为一组随机产生的查询序列，由100个查询组成，每次查询生成的条件字段、条件值和数据表都是按照一定的规则随机产生的。将MC的缓存的大小分别设置为实验数据总量的10%、15%、20%、25%、30%时分别进行五组实验，实验结果如图1所示。
3 结论
在移动环境中，数据预取是有效提高访问速度和减少数据访问时间的一个可行办法。本文主要考虑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.