论文部分内容阅读
随着Internet的迅速发展,原本孤立的个人计算机被联系起来。人们通过Internet传递和交换信息,信息资源的发布与访问变得十分方便。如今Internet已经深入人们的生活,这使得向用户提供普适的Internet接入成为一个有待解决的重要问题。无线通信技术以及移动嵌入式设备制造技术的发展使得移动自组网能够为普适的Internet接入提供有效的支持,而数据的高效分发与共享是基于移动自组网的普适Internet接入中的核心问题。协作缓存技术被广泛地用来实现高效的数据分发与共享。为了保证协作缓存系统中有效的数据访问,缓存的一致性必须被合理地维护。虽然在传统的有线网络环境下,已有许多缓存一致性维护方面的工作,但是已有工作还没有充分地研究移动自组网环境下的协作缓存一致性问题。移动自组网中计算资源(网络带宽,移动结点电池能量等)以及结点自主移动的限制,使得协作缓存一致性维护成为一个更具有挑战性的问题。本论文研究移动自组网环境下的协作缓存一致性维护问题。本文首先提出了一个缓存一致性模型Probabilistic Delta Consistency(PDC)。在PDC模型中,用户可以从两个正交的维度(源数据和缓存拷贝之间的差异和有效缓存访问的比率)来设定自己的缓存一致性需求,从而在表述自己的缓存一致性需求时获得很高的灵活性。通过灵活地表述自己的缓存一致性需求,用户可以在动态的移动自组网环境下高效地在缓存一致性和一致性维护开销之间作出权衡。PDC模型还具有很高的一般性(Generality)。通过灵活的参数设置,PDC模型将所有广泛使用的缓存一致性模型包含为PDC模型的特例。其次,本文提出了一个三维的缓存一致性维护算法设计框架。在该设计框架中,我们研究了缓存一致性维护算法设计中三个正交的关键子问题。第一,我们研究缓存一致性维护控制问题。缓存一致性维护的基本方式包括Push策略和Pull策略。数据源结点和缓存结点何时Push和Pull将影响用户的一致性需求能否被满足,以及相应的缓存一致性维护的开销是否合理。如何在满足用户的一致性需求的前提下,选择最合适的时机触发Push或Pull,尽量减少一致性维护的代价是缓存一致性维护控制算法设计中要解决的主要问题。而在移动自组网环境下,针对这一问题的研究工作还很不充分。本文针对移动自组网环境的特点,提出了基于预测的缓存一致性维护控制算法Predictive Cache Consistency和基于超时值的缓存一致性维护控制算法Flexible Combination of Push and Pull,高效地在移动自组网环境下决定缓存一致性维护的时机。第二,在缓存一致性维护的触发时机决定以后,如何在网络中高效地分发数据更新成为一个关键性的问题。这一问题因为移动自组网中结点间的通信依靠多跳的无线连接,以及移动自组网中计算资源(网络带宽,电池能量等)和结点自主移动的限制,变得更具有挑战性。针对移动自组网环境下的数据更新分发问题,本论文提出了层次化的数据更新协作分发算法Hierarchical Data Update Propagation(HDUP)。HDUP算法在数据源结点和缓存结点间构建具有树形拓扑结构的Overlay网络,并通过缓存结点在Overlay网络中的协作高效地分发源数据更新。第三,根据数据源结点如何维护各个缓存拷贝的状态,缓存一致性维护算法可以分为两大类:无状态(Stateless)和有状态(Stateful)。无状态的缓存一致性维护算法主要依靠广播机制分发源数据更新,因而会带来较大的通信开销。有状态的缓存一致性维护算法因其选择性的数据更新分发机制而具有通信代价小的特点。本论文提出面向移动自组网的有状态的缓存一致性维护算法Greedy Walk-based Selective Push(GWSP)。在GWSP算法中,数据源结点通过维护各个缓存拷贝的状态,选择性地向最需要数据更新的结点分发更新,有效地降低了缓存一致性维护开销。最后,为了验证本论文提出的缓存一致性维护算法,我们开发了面向移动自组网的协作缓存原型系统P2PSim。P2PSim系统基于C++及标准模板库STL开发。它实现了本论文提出的缓存一致性维护算法和用于性能比较的已有一致性维护算法。本论文详细描述了P2PSim原型系统的设计与实现。