一种面向移动设备基于预测的缓存优化方法

摘要

一种面向移动设备基于预测的缓存优化方法，移动设备中的缓存是一种有限的存储资源，其大小是相对固定的。当移动设备需要对当前的缓存进行替代更新时，首先，根据移动设备当前的运动状态预测将来可能的位置，即利用移动设备周期性记录的速度和方向计算出未来一段时间间隔内的预测平均速度，再结合记录的位置信息计算出预测的未来位置。然后，基于概率函数表示的感知用户移动性的缓存价值模型，计算网格单元数据项可能被访问的概率，按照网格单元数据项可能被访问的概率从高到低排序。最后，选择概率最低的K个网格单元数据项优先替换，直到有足够的缓存空间存放新的网格单元数据项。优化了移动设备的缓存使用方法，提高了该缓存的利用率，最终达到了减少移动设备和远程服务器之间通信代价的目的。

主权项

1.一种面向移动设备基于预测的缓存优化方法，其特征是：当移动设备需要对当前的缓存进行替代更新时，首先，根据移动设备当前的运动状态预测将来可能的位置，即利用移动设备周期性记录的速度和方向计算出未来一段时间间隔内的预测平均速度，再结合记录的位置信息计算出预测的未来位置。然后，基于概率函数表示的感知用户移动性的缓存价值模型，计算网格单元数据项可能被访问的概率，按照网格单元数据项可能被访问的概率从高到低排序，最后，选择概率最低的K个网格单元数据项优先替换，直到有足够的缓存空间存放新的网格单元数据项；包括如下步骤：步骤1，已知服务器端的空间数据以网格文件索引方式被划分成H行W列个统一的网格，取H=W=100，其中，空间数据是指包含空间数据对象的集合，每个空间数据对象的位置用符点型的坐标点来表示，且每个空间数据对象都包含位置在内的大小为100比特的属性值，划分后的网格单元记为C₁,C₂,C₃,…,C_g,…,C₁₀₀₀₀，每个网格单元作为数据存储的最小单位，记为网格单元数据项，它包含本网格单元内所有的空间数据对象的属性值，每个网格单元数据项用网格单元中心点的坐标(x_g,y_g)来表示，记为C_g(x_g,y_g)，服务器保存所有空间数据对象和形如<left,right,top,bottom,H,W,flags>的网格文件索引字符串，其中left、right、top、bottom分别取为0、1000、1000、0，它表示整个空间数据的范围，H、W表示网格单元被划分成H行W列，flags由0、1序列组成，表示网格单元中是否包含空间数据对象，是用1表示，否用0表示。每个移动设备进入到服务器的覆盖范围内都会接收到来自服务器端的网格文件索引字符串。根据移动设备端的网格文件索引字符串和当前位置可以判断它当前属于哪个网格单元，假设每个移动设备都装备GPS全球定位系统，且拥有300KB的缓存空间用来存储网格单元数据项和网格文件索引字符串，当移动设备发起空间查询请求时，首先检查本地存储能否完全应答查询请求，如果不能，通过路由表向邻居节点请求，对于那些既不在本地存储也不在于路由表中的数据，将请求发送给服务器，某一时刻，当移动设备接收到来自于服务器或邻居节点的查询结果，即为新的网格单元数据项，记为C_m，而此时移动设备的缓存空间不足，需要执行替换更新时，通过查询GPS获得移动设备当前时刻t_c的位置坐标，记为M_i(x,y)；步骤2，假设移动设备通过GPS能够每隔一个固定周期T获取其速度信息，则移动设备M_i在[t_c,t_c+Δt]时间间隔内的预测平均速度表示如下：$\overrightarrow{v}=\rho ·\overrightarrow{v}\left(n\right)+\rho (1-\rho )\overrightarrow{v}(n-1)+···{\rho (1-\rho )}^{19}\overrightarrow{v}(n-19)+···{+\rho (1-\rho )}^n\overrightarrow{v}\left(0\right)---\left(1\right)$其中，ρ是更新权重的参数，且0<ρ≤1，表示初始速度信息，表示nT时刻更新速度信息，t_c表示当前时刻，Δt表示预测时间间隔，且nT≤t_c≤(n+1)T，为了方便计算，取当前时刻前20个固定周期时刻记录的速度信息来计算预测平均速度，即取式(1)的前20项，ρ取0.8，Δt取50s，求得预测平均速度其中大小方向夹角且0°≤α≤180°；步骤3，移动设备M_i在[t_c,t_c+Δt]时间间隔内从M_i(x,y)运动到新的位置M′_i(x′,y′)，通过下式求得：M′_i(x′,y′)=(x+v·cosα·Δt,y+v·sinα·Δt)    （2）步骤4，确定移动设备M_i缓存中每一个网格单元数据项C_j对应的网格单元中心点C_j(x_j,y_j)与移动设备当前位置M_i(x,y)的连线M_iC_j的方向夹角β：其中0°≤β≤180°     (3)步骤5，计算概率函数prob(M_i,C_j,Δt)：$\mathrm{prob}(M_i,C_j,\mathrm{\Delta t})=\frac{{\left[(1+\cos (\beta -\alpha )\right]}^{\mu }}{{\left[\right|x_j-\frac{x+x^{\prime }}{2}|+|y_j-\frac{y+y^{\prime }}{2}\left|\right]}^{\sigma }}---\left(4\right)$它表示移动设备M_i在[t_c,t_c+Δt]时间间隔内访问网格单元数据项C_j的概率，其中，分子项表示网格中心点和当前位置连线的方向与设备运动方向两者的夹角差的衡量参数；分母项表示网格单元中心点C_j(x_j,y_j)与M_iM′_i的中心点O的曼哈顿距离，μ和σ为调节参数，取μ=1，σ=0.2；步骤6，对移动设备M_i缓存中每一个网格单元数据项C_j，按照其被访问的概率大小进行排序，选择概率最低的K个进行优先替换更新，直到移动设备M_i有足够的存储空间来存储新的网格单元数据项C_m为止,此时结束替换更新操作，其中K满足第一项表示新的网格单元数据项的大小，第二项表示K个概率最低的网格单元数据项的大小之和。