位置相关信息服务中一种基于价值的数据预取方法

       摘要：基于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。主要考虑以下两点因素：