移动自组网环境下协作缓存一致性维护机制研究

《移动自组网环境下协作缓存一致性维护机制研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学技术大学博士学位论文移动自组网环境下协作缓存一致性维护机制研究姓名：黄宇申请学位级别：博士专业：计算机软件与理论指导教师：冯玉琳20070401中国科学技术大学学位论文相关声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。本人授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可

2、以将学位论文编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后也遵守此规定。作者签名：盟多pD七年咿月叶天日摘要摘要随着Intemet的迅速发展，原本孤立的个人计算机被联系起来．人们通过Interne!t传递和交换信息，信息资源的发布与访问变得十分方便．如今Internet已经深入人们的生活，这使得向用户提供普适的Intemet接入成为一个有待解决的重要问题．无线通信技术以及移动嵌入式设备制造技术的发展使得移动自组网能够为普适的Internet接入提供有效的支持，而数据的高效分发与共享

3、是基于移动自组网的普适Internet接入中的核心问题．协作缓存技术被广泛地用来实现高效的数据分发与共享．为了保证协作缓存系统中有效的数据访问，缓存的一致性必须被合理地维护．虽然在传统的有线网络环境下，已有许多缓存一致性维护方面的工作．但是已有工作还没有充分地研究移动自组网环境下的协作缓存一致性问题．移动自组网中计算资源(网络带宽，移动结点电池能量等)以及结点自主移动的限制，使得协作缓存一致性维护成为一个更具有挑战性的问题．本论文研究移动自组网环境下的协作缓存一致性维护问题．本文首先提出了一个缓存一致性模型ProbabilisticD

4、eltaConsistency(PDC)．在PDC模型中，用户可以从两个正交的维度(源数据和缓存拷贝之间的差异和有效缓存访问的比率)来设定自己的缓存一致性需求，从而在表述自己的缓存一致性需求时获得很高的灵活性．通过灵活地表述自己的缓存一致性需求，用户可以在动态的移动自组网环境下商效地在缓存一致性和一致性维护开销之间作出权衡．PDC模型还具有很高的一般性(Generality)．通过灵活的参数设置，PDC模型将所有广泛使用韵缓存一致性模型包含为PDC模型的特例．其次，本文提出了一个三维的缓存一致性维护算法设计框架．在该设计框架中．我们研

5、究了缓存一致性维护算法设计中三个正交的关键子问题．第一，我们研究缓存一致性维护控制问题．缓存一致性维护的基本方式包括Push策略和Pull策略．数据源结点和缓存结点何时Push和Pull将影响用户的一致性需求能否被满足，以及相应的缓存一致性维护的开销是否合理．如何在满足用户的一致性需求的前提下，选择最合适的时机触发Push或Pull，尽量减少一致性维护的代价是缓存一致性维护控制算法设计中要解决的主要问题．而在移动自组网环境下。针对这一问题的研究工作还很不充分．本文针对移动自组网环境的特点，提出了基于预测的缓存一致性维护控制算法Pred

6、ictiveCacheConsistency和基于超时值的缓存一致性维护控制算法FlexibleCombinationofPushandPull，高效地在移动自组网环境下决定缓存一致性维护的时机．第二，在缓存一致佳维护的触发时机决定以后，如何在网络中高效地分发数据更新成为一个关键性的问题．这一问题因为移动自组网中结点间的通信依靠中国科学技术大学博士学位论文移动自组网环境下协作缓存一致性维护机制研究多跳的无线连接，以及移动自组网中计算资源(网络带宽，电池能量等)和结点自主移动的限制，变得更具有挑战性．针对移动自组网环境下的数据更新分发问

7、题，本论文提出了层次化的数据更新协作分发算法HierarchicalDataUpdatePropagation(HDUP)．HDUP算法在数据源结点和缓存结点间构建具有树形拓扑结构的Overlay网络，并通过缓存结点在Overlay网络中的协作高效地分发源数据更新．第三，根据数据源结点如何维护各个缓存拷贝的状态，缓存一致性维护算法可以分为两大类：无状态(Stateless)和有状态(Stateful)．无状态的缓存一致性维护算法主要依靠广播机制分发源数据更新。因而会带来较大的通信开销．有状态的缓存一致性维护算法因其选择性的数据更新分发

8、机制而具有通信代价小的特点．本论文提出面向移动自组网的有状态的缓存一致性维护算法GreedyWalk．basedSelectivePush(GWSP)．在GWSP算法中．数据源结点通过维护各个缓存拷贝的状态，选择性地向最