移动环境下语义缓存一致性策略和替换算法的研究

论文摘要

在移动计算环境下,由于通信带宽窄,网络断接频繁,客户端能源有限等缺点,给移动环境下的数据访问提出了挑战。因此,在客户端进行数据缓存变得非常必要。语义缓存是基于客户查询语义相关建立的一种客户缓存,内容由以往查询的结果及相应的语义描述组成。客户端利用本地缓存的语义信息进行推理,从而确定客户查询是否可在本地被完全解答或部分解答。现存的研究在语义缓存的模型,一致性维护,替换策略以及查询处理等方面均存在缺陷,语义缓存在移动环境下所采用的体系结构也在很大程度上限制了语义缓存的应用。为了克服这些缺陷,本文首先提出了一种新的DSM架构,给出了DSM架构的详细定义和工作模式,同时详细阐述了DSM的功能设计和基本实现。并在此基础上定义了基于DSM架构下的语义缓存一致性维护策略,根据移动环境的网络多样性实行不同的维护机制,在强连接下以尽量减少查询响应时间为目标,在弱连接下以减少网络开销为主要性能优化目标,并且对断接后的客户端进行特别的缓存维护。同时,给出了维护语义缓存一致性的详细算法,详细的理论证明和实验结果都保证了该一致性维护策略的正确性和有效性。替换策略是保证语义缓存命中率的关键技术,不同的应用背景对应了不同的替换策略。本文针对位置相关下的数据访问提出了基于预定义栅格的最小代价替换策略PGMC(a Predefined Grid of the Minimum Costsemantic cache replacement strategy),给出了预定义栅格的概念和语义缓存结构,并给出了详细算法。本策略基于典型的位置相关语义缓存模型,针对当前语义缓存替换策略的不足,加入了对数据项时间因素的考虑,同时结合对移动端运动方向的预测,加入了对用户常规路径的探测,并对位于常规路径上的数据的代价进行修改,这样有助于提高缓存命中率,缩短查询响应时间,节省网络开销。从模拟实验结果来看,PGMC算法在缓存命中率和查询响应时间方面相对于以往的算法都有显著的提高和改进,具有更大的优越性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 移动计算
• 1.1.2 移动计算环境模型及特点
• 1.1.3 移动计算环境下的语义缓存的应用背景
• 1.2 语义缓存存在和发展的必然性
• 1.3 研究问题、目标及主要内容
• 1.3.1 研究的问题和目标
• 1.3.2 论文的主要内容
• 1.4 论文的结构安排
• 第二章 移动计算下的语义缓存的基本概念及关键技术
• 2.1 移动计算下的语义缓存的模型及特点
• 2.1.1 缓存的内容和组织
• 2.1.2 语义缓存模型
• 2.2 移动计算下的语义缓存的关键技术的介绍
• 2.2.1 查询处理技术
• 2.2.2 缓存替换策略
• 2.2.3 一致性维护策略
• 2.3 位置相关数据的定义和查询处理
• 2.3.1 位置相关数据定义
• 2.3.2 位置相关查询的处理
• 2.4 小结
• 第三章 基于DSM架构的语义缓存一致性策略
• 3.1 基本思想
• 3.2 DSM体系结构
• 3.2.1 DSM的体系结构
• 3.2.2 DSM的系统工作模式
• 3.3 DSM功能设计
• 3.3.1 DSM主要接口函数一览表
• 3.3.2 MC，SS，DS之间的功能交互
• 3.4 客户机接入退出网络的详细流程
• 3.4.1 MC接入初始化
• 3.4.2 MC位置更新
• 3.4.3 MC主动断连
• 3.5 缓存一致性策略
• 3.5.1 策略描述
• 3.5.2 各状态的详细流程
• 3.5.3 缓存一致性算法
• 3.6 正确性证明
• 3.7 性能分析
• 3.7.1 模拟模型
• 3.7.2 系统参数
• 3.7.3 结果分析
• 3.8 小结
• 第四章 基于预定义栅格的位置相关缓存替换策略
• 4.1 替换策略的设计思想
• 4.2 预定义栅格的最小代价语义缓存替换策略PGMC
• 4.2.1 预定义栅格的概念
• 4.2.2 语义缓存结构
• 4.2.3 PGMC替换策略
• 4.3 替换算法
• 4.4 性能分析
• 4.4.1 实验场景和参数设置
• 4.4.2 结果分析
• 4.5 小结
• 第五章 结论和展望
• 5.1 总结
• 5.2 下一步工作
• 参考文献
• 致谢
• 攻读学位期间发表论文情况