（计算机科学与技术专业论文）移动计算环境下缓存策略的研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名_ 芝士五芝日期：型! ! ：! 篁：! z 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务o ( 保密的论文在解密后应遵守此规定) 研究生t ：叶猃导师c 捌：枷：沙儿s j 1 7 中文摘要 计算机技术和无线通信技术的发展与结合推动了一种全新的计算环境一移 动计算环境的出现和发展。越来越多的服务能通过无线方式获取，从而推动了 用户使用移动设备来广泛获取这些服务的需求逐渐增长。然而，移动计算环境 存在着一些局限性，如无线网络的低带宽、移动节点有限的能量资源、上下行 通信链路的非对称性和服务器端与移动节点间频繁的断接。为了更方便用户获 取信息，针对移动计算环境的特殊性，人们对移动计算环境下的数据管理展开 了研究。 将经常访问到的数据项进行缓存是一项有效的措施，能提高网络性能，因 为该措施能减少网络拥塞、查询延迟和电量消耗。当应用缓存技术时，维护缓 存的一致性成为一个主要问题，因为在服务器端发生更新的数据项应该相应在 移动节点的缓存中得到更新。由于移动计算环境固有的移动性和频繁断接性的 特点，移动节点难免主动或被动地与服务器断接，从而导致维持移动节点上的 缓存数据和服务器端数据之间的一致性更加复杂。 本文首先介绍了移动计算的概念、特点以及缓存一致性的研究现状，讨论 了移动计算的典型环境、移动节点缓存的工作状态，着重讨论了缓存的一致性 问题、缓存失效策略的分类依据以及现有的缓存失效策略的逐步演化过程。其 次，本文在h a i d a rs a f a 等人提出的选择自适应排序( s e l e c t i v ea d a p t i v es o r t e d , s a s ) 缓存失效策略的基础上进行了改进，克服该策略所带来的缓存内容与服务 器端内容不一致等缺点，着重于对于长时间断接时缓存的一致性维护。当移动 节点的断接时间过长时，改进策略并不是直接清除整个缓存，而是根据服务器 端数据的特点并依靠服务器端的帮助来提高移动节点的缓存数据的重用性，以 最大限度地利用缓存内容，并将时间戳与计数器( 即记录移动节点向服务器端发 送验证数据组有效性请求的数目) 相结合，动态地调整广播窗口以适应移动节点 不同的断接时间。最后，通过n s 2 进行仿真实验，将改进策略的性能与现有的 缓存失效策略中的一种策略进行比较。实验表明，改进策略在查询延迟、带宽 利用和能量消耗等方面能获得较好的性能，尤其是在长时间断接时。 关键字：移动计算，失效报告，缓存失效，数据广播 a b s t r a c t w i t ht h ed e v e l o p m e n ta n dc o m b i n a t i o no fc o m p u t e rt e c h n i q u e 一a n dw i r e l e s s c o m m u n i c a t i o nt e c h n i q u e ，an e wc o m p u t i n ge n v i r o n m e n tc a l l e dm o b i l ec o m p u t i n gi s a p p e a r i n ga n dd e v e l o p i n g 1 1 1 ed i v e r s i t yo fs e r v i c e sd e l i v e r e do v e rw i r e l e s sc h a n n e l s h a si n c r e a s e dp e o p l e sd e s i r ei nu b i q u i t o u s l ya c c e s s i n gt h e s es e r v i c e sf r o m 也e i r m o b i l ed e v i c e s h o w e v e r , au b i q u i t o u sm o b i l ec o m p u t i n ge n v i r o n m e n tf a c e ss e v e r a l l i m i t a t i o n ss u c h 弱l o wb a n d w i d t ho fw i r e l e s sn e t w o r k , l i m i t e de n e r g yr e s o u r c e so f m o b i l en o d e , t h ea s y m m e t r yo fu p - d o w nc o m m u n i c a t i o nl i n ka n df r e q u e n t d i s c o n n e c t i o nb e t w e e nt h es e r v e ra n dm o b i l ed e v i c e s f o rf a c i l i t a t i n gu s e r st oa c o 鹪s i n f o r m a t i o n , c o n s i d e r i n gt h es p e c i f i c i t i e so f m o b i l ec o m p u t i n ge n v i r o n m e n t , r e s e a r c h o nd a t am a n a g e m e n ti nm o b i l ec o m p u t i n gi sc a r r i e do u t c a c h i n gf r e q u e n t l ya c c e s s e dd a t ai sa ne f f e c t i v et e c h n i q u et oi m p r o v et h e n e t w o r kp e r f o r m a n c eb e c a u s ei tr e d u c e st h en e t w o r kc o n g e s t i o n ，t h eq u e r yd e l a y , a n d t h ep o w e rc o n s u m p t i o n w h e nc a c h i n gi su s e d , m a i n t a i n i n gc a c h ec o n s i s t e n c y b e c o m e sam a j o rc h a l l e n g es i n c ed a t ai t e m st h a ta r eu p d a t e do nt h es e r v e rs h o u l db e a l s ou p d a t e di nt h ec a c h eo ft h em o b i l ed e v i c e s d i s c o n n e c t i o nb e t w e e nm o b i l ec l i e n t a n ds e r v e rc a l lh a r d l yb ea v o i d e dd u et ot h ei n h e r e n tf e a t u r e so fm o b i l ec o m p u t i n g e n v i r o n m e n t , w h i c hl e a d st om o r oc o m p l e x i t yo fm a i n t a i n i n gc a c h ec o n s i s t e n c y b e t w e e nc a c h eo fm o b i l en o d ea n ds e r v e r f i r s t l y , t h i s t h e s i si n t r o d u c e st h e c o n c e p ta n dc h a r a c t e r i s t i c s o fm o b i l e c o m p u t i n g , a sw e l la sr e s e a r c h e so nc a c h ec o n s i s t e n c y , d i s c u s s e st y p i c a lm o b i l e c o m p u t i n ge n v i r o n m e n t , w o r k i n gs t a t u so fm o b i l en o d ec a c h e , f o c u s e so nc a c h e c o n s i s t e n c y , c l a s s i f i c a t i o no fc a c h ei n v a l i d a t i o ns t r a t e g i e sa n de v o l u t i o no fe x i s t e d c a c h ei n v a l i d a t i o ns t r a t e g i e s s e c o n d l y ，ac a c h ei n v a l i d a t i o ns c h e m ec a l l e ds e l e c t i v e a d a p t i v ep r o p o s e db yh a i d a rs a f ai si m p r o v e d n ee n h a n c e ds h e m eo v e r c o m e st h e s h o r t c o m i n go fs a s t h a ti tc a u s e sc o n t e n t si nc a c h en o tc o n s i s t e n t 谢lt h o s ei nt h e s e r v e r , a n df o c u s e so nm a i n t a i n i n gc a c h ec o n s i s t e n c ya f t e ral o n gt i m ed i s c o n n e c t i o n w h e nm o b i l en o d ed i s c o n n e c t sf r o ms e r v e rf o rav e r yl o n gt i o m ，i td o e s n tc l e a ra l l t h ec a c h e , b u ti m p r o v e st h er e u s a b i l i t yo fc a c h e dd a t ai nm o b i l en o d e , a c c o r d i n gt o c h a r a c t e r i s t i co fs e r v e r sd a t aa n dd e p e n d i n go ns e r v e r sh e l p ，i no r d e rt o 墩c a c h e 笛 m u c ha s p o s s i b l e t h ee n h a n c e ds t r a t e g yc o m b i n e st i m e s t a m pa n dc o u n t e rt o d y n a m i c l l ya d j u s tb r o a d c a s t i n gw i n d o ws i z e f i n a l l y , t h ep e r f o r m a n c eo ft h e e n h a n c e ds t r a t e g yi se v a l u a t e da n dc o m p a r e dw i t ho n es t r a t e g yo fe x i s t e ds t a r t e g i e s b yn s 一2 r e s u l t ss h o w e dt h a tas i g n i f i c a n tc o s tr e d u c t i o nc a nb eo b t a i n e dw i n lt h e p r o p o s e ds t r a t e g yw h e nm e a s u r i n gp e r f o r m a n c em e t r i c ss u c ha sd e l a y , b a n d w i d 电 a n de n e r g y , e s p e c i a l l yu n d e rt h ec o n d i t i o no f l o n gd i s c o n n e c t i o n k e y w o r d s ：m o b i l ec o m p u t i n g , i n v a l i d a t i o nr e p o r t ，c a c h ei n v a l i d a t i o n , d a t ab r o a d c a s t 1 1 1 目录 中文摘要i a b s t r a c t i i 第l 章绪论l 1 1 研究背景l 1 2 研究现状2 1 3 研究内容。3 1 4 论文的组织结构。4 第2 章移动计算中的缓存失效策略5 2 1 无线移动计算环境介绍5 2 2 缓存介绍6 2 3 移动节点缓存的工作状态8 2 a 缓存一致性问题9 2 5 缓存失效策略的分类1 0 2 5 1 失效报告的内容。1 2 2 5 2 失效机制1 4 2 6 缓存失效策略的演化15 2 6 1 广播时间戳( b r o a d c a s t i n gt s ) 策略一1 7 2 6 2 改进的失效报告( u i r ) 策略1 8 2 6 3 组失效报告( g i r ) 策略。2 0 2 6 4 选择缓存失效( s c i ) 策略。2 l 2 6 5 选择自适应排序( s a s ) 策略2 4 2 7 本章小结2 6 第3 章一种改进的移动计算缓存失效策略( e s a s ) 2 7 3 1 问题引入2 7 3 2 设计和数据结构2 8 3 3 详细设计。2 9 3 3 1 服务器端算法2 9 3 3 2 移动节点端算法3 0 3 3 3 长时间断接后移动节点的缓存处理过程( p f o 喀如c j i 3 4 3 4 讨论3 5 3 5 本章小结3 6 第4 章性能分析3 7 4 1 仿真平台n s 2 简介3 7 4 2 仿真环境、模型和参数3 8 4 3 不同参数对性能的影响4 l 4 3 1 报告更新历史( r q x r tu p d a t eh i s t o r y ) ，础。4 1 4 3 2 移动节点断接时间( m o b i l en o d ed i s c o n n e c t i o nt i m e ) ，厶胁4 2 4 3 3 数据项更新率( o b j e c t su p d a t er a t e ) 。4 5 4 3 4 查询到达率( q u e r ya n i v a lr a t e ) 。4 6 4 3 5 数据项组大d , ( o b j e c tg r o u ps i z e ) 。4 8 4 3 6 移动节点的断接率( d i s c o n n e c t i o np r o b a b i l i t y ) 4 9 4 4 本章小结4 l 第5 章总结与展望5 2 致谢5 4 参考文献5 5 攻读硕士学位期间发表学术论文5 8 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 手持移动设备以及移动计算技术的日趋发展，使移动设备接入i n t e m e t 成为 现实。根据中国互联网络信息中心c n n i c 发布的第2 7 次中国互联网络发展 状况统计报告【l 】，截止2 0 1 0 年1 2 月底4 5 7 亿的中国网民中手机网民规模为 3 0 3 亿2 0 1 0 年，网民上网设备多样化程度加深，手机和笔记本电脑作为上网 设备的比例迅速攀升，互联网移动化的趋势日趋明显。3 g 网络促进了移动计算 领域技术的发展。为满足用户在任何时间，任何地点获得信息的普遍需求，使 移动计算系统面临挑战。 移动计算概念的版本比较多，下面给出一些典型概念【2 】。 概念之一，a c m ( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y ，美国计算机协会) 给 出的概念是：所谓移动计算，就是用户在任何时间、任何位置均能不间断地获 取网络服务，包括数据服务和计算服务。 概念之二，商场现代化给出的概念是：所谓移动计算，指的是在任何地 点和运动状态下，便携式设备的用户都能通过相应的网络设施从数据源处获得 信息与服务。 概念之三，遥感世界给出的概念是：利用移动终端，通过无线通信网络 与远程服务器交换数据的分布式计算，称为移动计算。 概念之四，微计算机信息给出的概念是：随着计算机网络的日益发展， 在终端网络和软件平台等方面取得了显著的进步。这些显著进步不仅满足了人 们对信息获取实时性和便利性的需求，而且还推动了移动计算技术的迅猛发展。 利用移动终端通过无线和固定网络与远程服务器交换数据的分布计算环境，称 为移动计算。 概念之五，( m o b i l ec o m p u t i n g ) ) 一书中给出的概念是：移动计算就是利用 计算机与通信技术，在用户离开固定设施时也能在不间断地工作的情况下创建 业务解决方案的规程。 尽管不同的组织或不同的书给出的移动计算的概念是不同的，但这些概念 均包含在移动过程中不中断用户的业务，即用户在任何时间、任何地点均能从 武汉理工大学硕士学位论文 网络中获取所期望的服务。 在分布式系统中，强大的计算机通过固定的网络基础设施相互连接。与分 布式系统相比，移动计算环境有一些基本的区别，移动计算系统必须满足三个 特殊的方面【3 4 】【5 】： 第一，手持设备具有有限的显示、c p u 资源、存储、电池寿命和安全能力。 手持设备通常比不上桌面计算机和服务器的计算与存储能力。另外，设备的物 理尺寸决定了屏幕空间和输入性能。此外，电池寿命仍是一个重要问题。移动 应用需要通过限制所有形式资源的使用来延长电池寿命。此外，移动设备的安 全性和鲁棒性不及桌面计算机，移动设备更容易丢失，损坏或被盗，从而需要 新的信息保密和保护的方法。 第二，网络连接是间歇的、低带宽的和高延迟的。尽管无线网络，如市区 的w i f i 网络，正以迅猛的速度进行部署，移动设备能够无处不在的连接仍然只 是一个目标。无线网状网络的建立能够实现更远距离的通信。然而这种连接只 是处于暂时的最好状态，因为当设备所有者移动到新位置时，这种连接会被打 断。此外，通信延迟会变得更高，因为网络发现时间长并且需要多跳。因此， 移动系统必须适应设备之间的间歇的、普遍低带宽的和高延迟的无线连接，提 供更高带宽，鲁棒性更强的通信。 第三，环境状况和用户上下文环境不断变化。一个用户的上下文环境包括 位置、时间、进度、同事、期限和兴趣，这些都会影响信息需求，从而影响用 户期望从移动应用所获取的服务。因此应用程序必须调整其行为，以适应每个 用户不断变化的上下文环境以及现有的计算资源的变化，包括网络带宽和剩余 电量的变化。一个应用程序的适应性对其整体可用性有着重大影响。 由于移动计算的特殊需求，构造一个移动应用系统，必须在终端、网络、 数据库平台及应用开发上做一些特定考虑。 1 2 研究现状 移动计算的研究涉及到很多领域【6 l 【7 】，包括数据复制技术；数据广播调度算 法；客户机缓存管理算法；a g e n t 智能化、标准化及a g e n t 与传统中间件的连接 与协调；与位置相关的移动计算的优化方法；基于w e b 的移动计算系统的应用 开发等。移动计算系统的现有技术，包括用于离线数据访问的数据复制和缓存， 远程访问位于其他机器上的数据，服务器或代理p c 上的无负载计算，根据用户 2 武汉理工大学硕+ 学位论文 上下文环境和信息需求的变化来调整系统的策略和机制等。本文所关注的研究 问题是移动计算环境中的缓存技术，尤其是缓存数据的一致性研究。 有关移动计算环境中缓存数据的一致性研究，目前主要的研究成果有【8 】： j g r a y 提出了两级复制的框架，其中心思想是假设移动系统中含有移动终 端、基站节点( 即服务器) ，该节点位于固定网络中维持数据的一个副本( 一级复 制) ，服务器之间总是保持连接的，而移动终端则有时与服务器保持连接，但相 当多的时间处于断接状态，移动终端上也有数据的一个副本( 二级复制) 。 k i s t l e r 提出了一种乐观缓存方案，在卡内基梅隆大学中的c o d a 移动文件系 统中使用。c o d a 是一个通过复制与缓存技术来实现的文件系统，对移动环境下 缓存技术研究比较彻底，其目标是最大化“老”数据的可用性。在结构上，c o d a 可视为一组u n i x 客户和u n i x 文件服务器，每个客户都有本地磁盘用于缓存。 c o d a 在移动终端上建立一个用户级缓存管理进程，通过终端、服务器的连接或 断接状态进行管理。 k e l l e r 等人提出一种缓存机制用来支持移动客户机在断接时的操作，即基于 谓词的缓存机制。 p i s s i o n u n 等人提出一种基于历史的预测缓存机制。 b a r b a r ad 等人提出了缓存失效广播技术，即服务器以周期性广播的形式向 移动节点发送失效报告，该方案在解决缓存失效技术以维护移动节点缓存的一 致性方面最具代表性【9 】。 以上的研究为本文研究移动计算环境下的数据一致性提供了良好的基础， 在这些研究成果的基础上，本文认真分析了现有的基于失效报告的失效策略， 并对h a i d a rs a f a 等人提出的失效策略进行改进。 1 3 研究内容 移动计算环境的特点有：网络条件多样性、网络通信上下行链路的非对称 性、频繁断接性、移动节点电源能力的有限性、可靠性低等。与传统的数据管 理相比，移动计算环境下的数据管理有很大的不同。在移动环境下的解决缓存 数据的不一致性问题，缓存失效广播技术的应用越来越广泛。该技术针对移动 计算环境的特点，通过将缓存技术和数据广播技术有效结合起来，以解决移动 环境下缓存管理的问题【i o 】。 本文在分析了移动计算环境中在缓存数据的一致性维护方面取得的成果之 3 武汉理工大学硕士学位论文 后，对h a i d a rs a f a 等人提出的选择自适应排序【1 1 ( s e l e c t i v ea d a p t i v es o r t e d s a s ) 缓存失效策略进行了改进。论文围绕移动计算环境下的缓存策略做了以下有意 义的工作： ( 1 ) 讨论了移动计算的典型环境以及与移动计算环境中缓存一致性相关的 问题。 ( 2 ) 详细介绍了目前存在的基于数据广播的失效报告来实现的缓存策略的 逐步演化过程，分析了现有策略的优点和不足。 ( 3 ) 在h a i d a rs a r a 等人提出的缓存失效策略的基础上进行了改进，着重于对 于长时间断接时缓存的一致性维护，以获得较好的整体性能。 ( 4 ) 针对改进后的方案，运用n s 2 网络模拟器进行仿真，将本文提出的改 进方案与现有的失效策略在不同参数下进行比较，并对实验结果进行分析。 1 4 论文的组织结构 本文共分为五章： 第l 章：绪论。介绍本课题的研究背景及意义，分析移动计算环境领域相 关的问题，尤其是缓存策略在国内外的研究现状和面临的问题，提出了本文的 主要研究内容。 第2 章：移动计算中的缓存失效策略。首先介绍传统意义上的缓存，然后 基于移动计算环境的特点提出用于移动计算环境的缓存策略面临的问题，最后 详细介绍目前存在的基于数据广播的失效报告来实现的缓存策略的逐步演化过 程，分析了每种缓存策略的优点和不足。 第3 章：一种改进的移动计算缓存失效策略。如何动态改变广播窗口的大 小以及在移动节点长时间断接时如何利用数据项的本身特点来尽可能挽救缓存 中的数据项而不是清除整个缓存，为解决这些问题，本章对h a i d a rs a r a 等人提 出的选择自适应排序( s a s ) 缓存失效策略进行改进，解决该策略所带来的问题， 以获得更好的性能。 第4 章：性能分析。在不同方面对改进后的缓存失效策略的性能与现有的 缓存失效策略中的一种策略进行比较，可以发现改进后的缓存失效策略能够获 得更好的性能。 第5 章：总结与展望。在总结了本文的主要工作的基础上，对未来的研究 工作进行了展望。 。 4 武汉理工大学硕士学位论文 第2 章移动计算中的缓存失效策略 2 1 无线移动计算环境介绍 一个典型的移动计算环境如图2 1 所示【1 2 】【1 3 1 。图2 1 体现以下几点： ( 1 ) 高速固定网络部分形成连接固定节点的骨干，多个固定主机服务器( f i x e d h o s t ，简称f h ) 和移动服务支持节点( m o b i l es e r v e rs t a t i o n ，简称m s s ) 构成固定网 络，每个m s s 负责建立一个无线网络单元，无线网络单元内的移动节点( m o b i l e n o d e , 简称m n ) 通过无线网络与m s s 连接； ( 2 ) 移动节点( m n ) 能自由移动； ( 3 ) 每个f h 维护一个本地数据库，包含通常的数据库服务器和文件服务器， 可以处理客户的联机请求以及保持所有请求的历史记录，且数据库服务器保存 所有数据项。 m n m n 无线单元 m n m n 无线单元 图2 1 无线移动计算环境 目前的移动通信技术主要有【1 4 】1 1 5 】：移动卫星通信系统、蜂窝通信系统、红 外技术和无线局域网，“蓝牙”标准也可以归类为无线局域网。其中，蜂窝通信技 术已经发展到第三代，目前第二代蜂窝通信系统仍处于广泛使用之中，而第三 代蜂窝移动通信网络，即3 g 技术，将成为无线通信的重点。全球第三代移动通 信系统标准中，有三个被国际电联正式批准：( 1 ) 美国高通公司的 c d m a 2 0 0 0 ( c o d ed i v i s i o nm u l t i p l ea c c e s s2 0 0 0 ) ；( 2 ) 欧洲诺基亚、爱立信等公司 5 武汉理工大学硕士学位论文 推行的w c d m a ( w i d e b a n dc o d ed i v i s i o nm u l t i p l e a c c e s s ) ；( 3 ) 中国大唐公司和西 门子等公司倡导的t d s c d m a ( t i m od i v i s i o ns y n c h r o n o u sc o d ed i v i s i o n m u l t i p l ea c c e s s ) 。无线单元所能覆盖的范围和数据传输率因采用的无线通信技术 而不同。如移动卫星通信系统的一个无线单元的直径可大于4 0 0 英里；蜂窝系 统发射器的信号覆盖范围直径为几英里，最大数据传输率为几十k b p s ：红外线 的传输范围不到2 英里，数据传输率可高达近2 0 m b p s ；而无线局域网能覆盖的 无线单元半径只有几十米，数据传输率一般在2 m b p s 至1 0 m b p s 。 2 2 缓存介绍 计算机系统性能的提高与c p u 和内存之间的存取速度有关。若c p u 以较高 速度工作，但内存以相对较低的速度存取，则导致c p u 等待，降低系统的处理 速度，并浪费c p u 的处理能力。在不会大量增加p c 系统成本的前提下，缓存 是提升性能的一个非常有效的技术。为了减少c p u 与内存之间的速度差异，将 一块与内存相比速度较快、容量较小的s r a m ( s t a t i cr a n d o ma c c e s sm e m o r y ) 插 入到慢速内存与快速c p u 之间，起到缓冲作用，从而一方面c p u 能以较快速度 读取内存中的数据；另一方面不会使系统成本过高上升，这就是缓存技术。因 此缓存技术可以缩短c p u 的等待时间，使c p u 尽可能地处于忙碌状态【i 刀。 缓存技术在计算机的数据存储方面已经应用广泛。缓存是重复收集数据的 场所，若这些数据在其它地方分布，则获取这些数据的代价将很高，访问时间 相对较长，同时比从缓存中读取的成本要高。缓存是一个临时存储区域，应用 程序可快速地从缓存获取经常访问的数据。一旦数据被存储在缓存中，就可 能在将来被访问到，而不必重新从数据源获取或重新计算原始数据。缓存是基 于计算机程序访问的局部性原理而工作。局部性原理是一个由经验得出的结论： “一个程序9 0 的时间运行在1 0 的代码上”。计算机程序从时间和空间都表现 出“局部性”：( 1 ) 时间的局部性，最近被访问的内存内容( 指令或数据) 很快还 会被访问；( 2 ) 空间的局部性，靠近当前正在被访问内存的内存内容很快也会被 访问。程序访问的局部性原理为缓存的应用提供了理论依据。高速缓存不仅仅 用于c p u 和硬盘驱动器，同时也经常用于w e b 浏览器和w e b 服务器。 己经广泛应用的缓存技术有【1 刀f 1 8 19 】【2 0 】： ( 1 ) c p u 缓存。c p u 利用缓存减少访问内存的平均时间。c p u 缓存是更小的、 速度更快的内存，其中保存主存经常访问到的数据拷贝。现在，大多数台式计 6 武汉理工大学硕士学位论文 算机或服务器的c p u 至少有3 个独立的缓存：指令缓存加快读取执行的指令， 数据缓存加快数据的存取，快速重编址缓冲器加快用于读取指令和存取数据时 的虚拟地址到物理地址的转换。 ( 2 ) 磁盘缓存。硬盘的速度与随机存储器相比相当慢，但能提供大量的存储 空间，磁盘缓存就是用来改善读写磁盘所花费的时间。现在，磁盘缓存通常作 为硬盘的一部分。磁盘缓存也可以是随机存储器的特定分区。c p u 缓存的一般 管理完全是由硬件完成，而其他缓存的管理则多是由软件完成。c p u 缓存和磁 盘缓存正是体现出分层存储管理的思想。 ( 3 ) w e b 缓存。w e b 缓存保存网页文件的拷贝，当特定的条件满足时，对相 同文件的随后的请求能从w e b 缓存得到响应，而不是每次都从服务器端下载。 w e b 缓存有利于加快w e b 应用的响应并节省网络带宽。在w e b 浏览器和w e b 代理服务器中w e b 缓存得到广泛应用。w e b 浏览器中内置w e b 缓存，其中缓存 访问过的服务器端数据。w e b 缓存是缓存技术中研究最为广泛的，并深刻影响 着后来的无线网络中的缓存技术。一些i n t e m e t 服务提供商或组织使用的高速缓 存代理服务器是一个可以被网络间的所有用户共享使用的w e b 缓存。另外，还 有一种w e b 缓存技术应用于p 2 p 网络，这种w e b 缓存要求使用在对等应用程序 中，以加速点对点传输。 决定缓存性能的主要参数包括：大小、访问延迟、命中率、替换策略和一 致性策略【1 7 】。 缓存大小是指缓存的最大存储容量。缓存的大小是固定不变的、有限的， 所以其中应该缓存访问频率高的数据。如果缓存的本身大小不能容纳需要缓存 的内容，就需要将缓存中过时的内容用新的内容替换掉。 访问延迟是指从用户发出一个请求开始，到用户接收到该请求的响应为止 所经历的时间。当缓存不命中时，需要从实际的服务器中读取数据，然后再返 回给用户，从而增大了访问延迟。当缓存命中时，与不采用缓存的系统相比， 访问延迟会较小。应采用两者的折中应用于实际中，。 命中率是指程序运行时缓存命中次数占所有对内存访问次数的比例。缓存 效率的高低就是取决于命中率。通常情况下，会通过设计算法来最大限度地提 高缓存命中率。 命中率和缓存大小两个指标之间存在着矛盾。缓存太小，造成频繁的替换， 会降低命中率，而增大缓存会降低缓存命中率、缓存效率降低以及增加检索缓 存的时间，缓存过大或过小都会增大系统访问延迟。因此，缓存大小一般是固 7 武汉理工大学硕士学位论文 定的。对于用户来说，缓存中每个数据项的有用性并不完全一样，在某些时刻 某些数据项被用户请求的概率大，某些数据项则相对较小。被用户请求的改良 版越大，就越有用。因此缓存替换策略就是，当缓存的本身大小不能容纳需要 缓存的内容时，应该从缓存中移走对系统来说有用性最小的缓存数据项，并把 较高有用性的数据项放入缓存中。 服务器端数据的更新会导致缓存中的数据过期而变得无效。若此时系统还 是利用缓存中的数据来响应用户请求，用户得到的响应将是错误的。为了维护 服务器端数据与缓存数据的一致性必须提出一个可行的方法，这就是一致性策 略需要解决的问题。 2 3 移动节点缓存的工作状态 移动节点的缓存是服务器端数据库的一个子集。为了适应移动用户与网络 频繁断接的需求，移动节点的缓存具有3 种工作状态：联机状态、断接状态和 集成状态【2 1 1 。根据移动节点与服务器不同的网络连接状态，移动节点缓存将在 这三种状态之间发生转换。移动节点缓存的工作状态转换图如图2 2 所示。 图2 - 2 移动节点缓存的工作状态转换图 ( 1 ) 联机状态：当移动节点缓存处于工作状态中联机状态下时，缓存可以收 集数据，数据收集工作依靠数据复制，而数据复制发生在服务器端数据库的同 步服务器上，并且移动节点缓存做好准备以随时转为断接状态。 ( 2 ) 断接状态：当移动节点与服务器端断接时，为了满足移动用户对数据进 行访问的需求，此时需要使用缓存中的数据，移动节点缓存也就进入了断接状 态，直到移动节点重新连接上服务器。 ( 3 ) 集成状态：当移动节点重新连接上服务器端时，移动节点缓存的工作状 态转为集成状态，通过使用特定的同步算法，移动节点缓存中的内容利用同步 8 武汉理工大学硕士学位论文 服务器进行与服务器端数据库的同步，然后工作状态重新转为联机状态。 2 4 缓存一致性问题 在移动和无线环境下的普适计算是一项极具挑战性的任务，有以下一些原 因：( 1 ) 无线方式以窄带宽而著称，移动用户与固定用户相比使用更少的带宽并 遇到更多的错误；( 2 ) 移动用户有很大的移动性，经常间歇性地从一个无线单元 移进或移出，导致频繁的网络断接；( 3 ) 移动设备与固定工作站相比，具有有限 的电源能力【2 l j 。 对移动节点经常访问的数据项进行缓存是一种重要的技术，该技术能提高 网络的性能以及能更好地访问数据或服务，能减少从服务器端检索数据的时间， 从而产生更少的网络负载，并允许用户在与服务器断接的情况下仍能访问移动 节点缓存中的数据。 移动节点的缓存机制具有缓存粒度、缓存一致性策略和缓存替换算法这三 个标志性的特征【捌。通常情况下，相对稳定的网络环境、高速的网络带宽以及 位于服务器端数据项访问的高度局部性是传统的缓存技术的基本要求。而本文 前面章节提到的移动计算环境的特殊性都与这些要求相违背，所以本文在考虑 到移动计算环境的特殊性的前提下，对缓存机制中维护缓存一致性的策略展开 研究。 缓存一致性问题是指当源数据发生更新、同时用户向已缓存该源数据的副 本发出查询请求时，如何判断缓存的数据项的有效性以及如何维持源数据与缓 存数据之间的一致性。移动计算环境的特殊性给维护移动节点缓存数据和服务 器端数据之间的一致性增加了复杂性。移动计算环境下，弱一致性问题存在于 移动节点和服务器端的数据上。从缓存数据和服务器端数据的一致性复杂度和 一致性程度两方面考虑，并与应用的实际情况相结合，数据的一致性可以分为 强一致性和弱一致性瞄】。本文研究的缓存一致性问题主要是为了达到维护移动 节点缓存和固定服务器端数据之间一致性的目的。强一致性要求查询请求获得 的值是服务器端数据的最新值以及能够立即提交更新请求；弱一致性则可以利 用移动节点的缓存信息执行查询或更新请求。因此，若移动节点缓存在移动节 点和服务器之间处于联机状态时，应该能达到维护数据的强一致性；相反在断 接状态下，缓存最好能达到维护数据的弱一致性。 位于移动节点上的缓存数据的一致性问题包括两个方面的主要内容 2 3 】：( 1 ) 9 武汉理工大学硕士学位论文 服务器端要向各个移动节点及时通知服务器端数据的更新，而且更新移动节点 缓存中的相应内容。缓存数据的被动更新是指由服务器端数据的更新而产生的 缓存数据的更新；( 2 ) 移动节点更新的数据要及时通知到服务器端，并及时向服 务器端提交更新，缓存数据的主动更新是指由移动节点缓存数据的更新提交到 数据库服务器端的最终更新。一般情况下，为了解决缓存的一致性问题利用移 动节点缓存数据的被动更新，这种方法效率更高。在这种方法中，维护缓存数 据一致性的实现主要依靠服务器端周期性地向移动节点广播更新信息。 总之，维护缓存的一致性意味着，当服务器端的数据项发生更新时，这些 更新应该也能复制到移动节点的缓存中。然而，因为移动节点的频繁断接性以 及高频率移动性，使得移动节点无法获取最新的数据项更新，从而导致缓存失 效。为了保证缓存一致性，移动节点将不得不清除整个缓存并从头开始建立缓 存，或者使缓存的相应数据项失效。缓存失效策略保证移动节点从失效状态变 成有效状态来恢复缓存。同时，一个好的失效策略应该能考虑到移动环境中稀 有的网络带宽以及移动节点有限的资源【i 。 2 5 缓存失效策略的分类 移动节点的缓存要不是一个有效缓存，即缓存里的数据项都是有效的；要 不是一个失效缓存，即缓存中至少有一个数据项失效。当一个缓存变成失效的 时，可以使用两种方法来恢复其有效性：( 1 ) 由移动节点发起的方法；( 2 ) 由服务 器发起的方法。 在由移动节点发起的方法中，移动节点向服务器发送上行请求来验证缓存 中的哪些数据项是有效的，用这种方式来启动缓存失效进程。因为大量的上行 请求发送到服务器，这种方式产生大量网络负载。而且，如果多个移动节点缓 存同一个数据项，就会发送若干上行请求来使缓存失效，导致网络带宽的利用 率低。 在服务器发起的缓存失效方法中，存在两种策略分类：( 1 ) 基于有状态服务 器的策略；( 2 ) 基于无状态服务器的策略。 在基于有状态服务器的策略中，服务器知道移动节点的缓存状态，这些移 动节点在其覆盖域之内。当服务器更新一个数据项，服务器向缓存该数据项的 移动节点直接发送一个缓存失效消息，该消息包含已更新数据项的更新后的值。 在这种情况下，移动节点在查询到达时能很快地响应查询。然而，如果一个移 l o 武汉理工大学硕士学位论文 动节点断接了，移动节点就会丢失一些失效消息，其缓存就会变成一个失效缓 存。对于这个问题的解决方案是当移动节点重新连接上时，服务器能重新发送 该节点所错过的失效消息。然而这种方案同时给移动节点和服务器都增加了额 外的网络负载，用来跟踪移动节点的状态、缓存的内容和缓存的状态。 在基于无状态服务器策略中，服务器广播一个失效报告( i n v a l i d a t i o nr e p o r t , 瓜) ，该失效报告包含已更新数据项的列表。在这种上下文环境中，存在两种方 法广播失效报告： ( 1 ) 在同步的方法中，服务器周期性地广播失效报告，并为移动节点节省电 源资源，因为在下一个广播周期到来之前移动节点可以处于休眠