（计算机软件与理论专业论文）移动数据库中数据预取系统研究与实现.pdf

目录 摘要i a b s t r a c t i i i 第1 章绪论l 1 1 研究背景和意义1 1 2 国内外研究动态2 1 3 研究内容3 1 4 论文的组织结构3 第2 章移动计算与数据预取技术5 2 1 移动计算环境与移动数据库5 2 2 数据预取技术9 2 3 关联规则挖掘技术1 3 2 4 本章小结15 第3 章数据预取系统模型1 7 3 1 数据预取模型分析1 7 3 2v a l u eb a s e dc m i p 数据预取系统的模型1 9 3 3 预取数据的价值评估2 1 3 4v a l u eb a s e dc m i p 数据预取系统的基本功能特征2 2 3 5 本章小结2 3 第4 章关联规则挖掘与数据预取算法2 7 4 1 移动计算环境中的关联规则挖掘算法。2 7 4 2 数据预取算法3 4 4 3 本章小结3 7 第5 章算法性能分析与系统实现3 9 5 1 实验环境与参数设置3 9 5 2 关联规则挖掘算法比较与性能分析4 l 5 3 预取系统的实现与性能分析4 2 5 4 本章小结4 4 第6 章总结与展望4 5 6 1 本文总结4 5 6 2 未来工作展望4 5 参考文献4 7 致谢：51 攻读学位期间所发表的学术论文5 3 1 。 _1l 摘要 移动数据库中数据预取系统 研究与实现 计算机软件与理论专业硕士研究生李靖 指导教师余建桥教授 摘要 移动数据库中数据广播技术及移动通信带宽的有限性引起较大的数据访问延迟，移动客 户机与固定网络频繁( 主动或被动) 断接使得用户事务得不到所需要的数据，移动设备的电 能限制及通过无线网络访问远端服务器将消耗大量的电能等等这些限制性特点，使得传统的 缓存和数据预取技术在移动计算环境中得到广泛的使用。 数据预取技术是对缓存技术的补充。它有效利用了用户访问的时间局部性和空间局部性， 通过结合用户当前和历史的请求，主动预测用户将来可能访问到的数据内容，并将其预取剑 客户机本地缓存中。数据预取技术的关键是如何准确及高效的预测移动客户机朱来将要使用 到的数据并将其预取到缓存中。 数据预取按其在网络中实施预取的位置划分为服务器端预取、代理服务器端顶取和客户 端预取，本文围绕移动数据库中客户端数据预取技术进行了以下主要研究： 一、根据移动计算环境的结构及其特点，得出研究移动数据库中数据预取技术的理论和 现实意义。在分析传统的数据预取系统模型之上提出在移动数据库的客户端利用用户历史访 问记录通过关联规则挖掘技术得到用户访问数据的相关性并结合网络中数据资源的更新频 率，通过价值评估函数进行预取数据选择的预取系统v a l u eb a s e dc m i p 数据预取系统。 v a l u eb a s e dc m i p 数据预取系统依赖两个预取集合：预取数据集合和失效预取集合。预取数 据集合中的数据只要出现广播通道中就将其预取到客户端缓存中。失效预取集合的构造发生 在用户事务请求的数据失效时，不仅向服务器请求该失效数据，而且同时请求与失效数据项 相关的数据。 二、结合移动计算环境中用户数据特点，在传统的关联规则挖掘算法之上，提出一种支 持移动计算的关联规则挖掘算法。频繁项集挖掘算法- n e wa p r i o r i 算法通过减少候选项集 的产生及事务数据库的扫描时间，提高传统关联规则挖掘算法的效率，减少移动客户机的电 能消耗。增量频繁项集更新算法一n e wf u p 算法针对移动客户端的位置变化而导致的兴趣 漂移，对增量事务数据库进行关联规则挖掘， 从而更能准确的预测用户将访问数据。考虑到 移动客户端系统资源的消耗，提出根据客户端电能使用率动态选择支持度和置信度进行关联 规则的挖掘。 三、进行算法的比较分析及数据预取系统的实现。经过算法理论与实验比较分析，本文 i 西南大硕t 学位论文 提出的n e w 关联规则挖掘算法能够减少算法时间复杂度和空间复杂度。同时，apdori n e wf u p 增量频繁项集更新算法能够从增鼍事务数据集中获得更多的频繁项集用于预取数据 的选择，提高缓存的命中率。通过数据预取系统的模拟实现与c m i p 数据预取系统的比较分析， 本文提出的v a l u eb a s e dc m i p 数据预取系统具有可实现性，并且提高了缓存的命中率，降低 了缓存的失效率、减少了数据访问的时间及电能的消耗，提高了服务质量。 i i 关键词：移动计算，数据预取，更新率，关联规则 争 i a b s t r a c t a b s t r a c t d a t ab r o a d c a s t i n gt e c h n o l o g ya n dt h el i m i t a t i o no fm o b i l ec o m m u n i c a t i o nb a n d w i d t hi nm o b i l e d a t a b a s ec a u s e dl a r g ed a t aa c c e s sl a t e n c y ；m o b i l ec l i e n ta n df i x e dn e t w o r kf r e q u e n t l y ( i n i t i a t i v eo r p a s s i v i t y ) d i s c o n n e c ta l l o w st h eu s e rt r a n s a c t i o nn o tt og e tt h er e q u i r e dd a t ai t e m s ；p o w e rc o n s t r a i n t s o fm o b i l ed e v i c e sa n da c c e s sr e m o t es e r v e rt h r o u g ht h ew i r e l e s sn e t w o r kw i l lc o n s u m eal o to f e n e r g ya n ds ot h e s er e s t r i c t i v ef e a t u r e s ，t h et r a d i t i o n a ld a t ac a c h i n ga n dp r e f e t c h i n gi nm o b i l e c o m p u t i n ge n v i r o n m e n t si sw i d e l y u s e d d a t ap r e f e t c h i n gt e c h n o l o g yi st h es u p p l e m e n tt oc a c h et e c h n o l o g y , e f f e c t i v eu s eo ft h eu s e r a c c e s st ot h et e m p o r a ll o c a l i t ya n ds p a t i a ll o c a l i t y , t h r o u g hac o m b i n a t i o no fc u r r e n ta n dh i s t o r i c a l u s e rr e q u e s t s ，i tt a k et h ei n i t i a t i v et of o r e c a s tt h ed a t ac o n t e n tw h a tt h eu s e rw i l lp o s s i b l ea c c e s st oi n f u t u r e ，t h e np r e f e t c h i n gt ot h ec l i e n tl o c a lc a c h e t h ek e yo fd a t ap r e f e t c h i n gt e c h n i q u ei sh o wt o a c c u r a t e l ya n de f f i c i e n t l yp r e d i c tt h ed a t aw i l lb eu s e do ft h em o b i l ec l i e n ti nf u t u r ea n dp r e f e t c hi tt o t h ec a c h e a c c o r d i n gt ot h ei m p l e m e n t a t i o nl o c a t i o ni nt h en e t w o r ko ft h ep r e f e t c hd i v i d e di n t os e r v e r , p r o x ys e r v e ra n dt h ec l i e n t - s i d ep r e f e t c h i n g t h i sp a p e rf o c u s e so nt h ed a t ap r e f e t c h i n gt e c h n o l o g y o f t h ec l i e n ti nt h em o b i l ed a t a b a s ef o rt h ef o l l o w i n gm a j o rs t u d i e s ： f i r s t , a c c o r d i n gt ot h es t r u c t u r e sa n dc h a r a c t e r i s t i c so ft h em o b i l ec o m p u t i n ge n v i r o n m e n t , o b t a i n e dt h a td or e s e a r c ho nt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c eo fd a t ap r e f e t c h i n gi nm o b i l e d a t a b a s et e c h n o l o g y b ya n a l y z i n gt h et r a d i t i o n a lm o d e lo fd a t ap r e f e t c h i n gp r o p o s e dt h a ti nc l i e n t o ft h em o b i l ed a t a b a s et h r o u g hu s et h eu s e r sh i s t o r yr e c o r d st om i n i n ga s s o c i a t i o nr u l ea n do b t a i n t h ec o r r e l a t i o nu s e ra c c e s st od a t a , a n dc o m b i n e dw i t hn e t w o r kd a t ar e s o u r c e so ft h eu p d a t e f r e q u e n c y , t h ev a l u eo fe v a l u a t i o nf u n c t i o nb ys e l e c tt h ep r e f e t c hd a t a v a l u e b a s e dc m i pd a t a p r e f e t c h i n gs y s t e m v a l u e b a s e dc m i pd a t ap r e f e t c h i n gs y s t e mr e l i e so nt w op r e f e t c hs e t s ：t h e a l w a y sp r e f e t c hc o l l e c t i o na n dt h ef a i l u r ep r e f e t c hc o l l e c t i o n a l w a y sp r e f e t c hd a t ai nt h ec o l l e c t i o n w i l lb ea sl o n ga si ta p p e a r si nt h eb r o a d c a s tc h a n n e lp r e f e t c ht ot h ec l i e n tc a c h e f a i l u r ep r e f e t c h o c c u r r e di nt h ec o n s t r u c t i o no fac o l l e c t i o no fu s e rd a t ai nf a i l u r eo ft h er e q u e s t e dt r a n s a c t i o n , n o t o n l yt h ef a i l u r e sd a t at ot h es e r v e rr e q u e s t , b u tw i l la l s or e q u e s tt h ed a t ai t e ma s s o c i a t e dw i t ht h e f a i l u r ed a t a w h i l ef o rm u l t i - c l i e n td a t as e n tt h ec a s ep u tf o r w a r df o re a c hc l i e n tr e q u e s tf o ru n i f i e d d a t ac o l l e c t i o na n dt h e ns e n t t ot h es e r v e r - s i d eu n i f o r m s e c o n d , c o m b i n e dw i t ht h ec h a r a c t e r i s t i c so fu s e rd a t ai nm o b i l ec o m p u t i n ge n v i r o n m e n t , t h r o u g hd or e s e a r c ho n t h et r a d i t i o n a la s s o c i a t i o nr u l em i n i n g a l g o r i t h m ，p u tf o r w a r d st h ea s s o c i a t i o n r u l em i n i n ga l g o r i t h m st h a ts u p p o r tt h em o b i l ec o m p u t i n g f r e q u e n ti t e m s e tm i n i n ga l g o r i t h m n e w _ a p r i o r ia l g o r i t h mb yr e d u c i n gt h eg e n e r a t i o no fc a n d i d a t ei t e m s e t sa n dt h et i m eo fs c a n n i n g t h et r a n s a c t i o nd a t a b a s e ，i m p r o v i n gt h et r a d i t i o n a la s s o c i a t i o nr u l em i n i n ga l g o r i t h me f f i c i e n c ya n d r e d u c ep o w e rc o n s u m p t i o ni nm o b i l ec l i e n t s i n c r e m e n t a lu p d a t i n ga l g o r i t h mf o rf r e q i a e n ti t e m s e t s n e wf i 胆a l g o r i t h mf o rt h el o c a t i o no ft h em o b i l ec l i e n tc h a n g e si ni n t e r e s td u et od r i f t i n c r e m e n t a l i i i 两南夫学硕斗学伊论文 t r a n s a c t i o nd a t a b a s ef o rm i n i n ga s s o c i a t i o nr u l e s ，w h i c hm o r ea c c u r a t e l yp r e d i c tt h eu s e rw i l la c c e s s t h ed a t a t a k i n gi n t oa c c o u n tt h em o b i l ec l i e n ts y s t e mr e s o u r c ec o n s u m p t i o n ，e n e r g yu s a g eb a s e do n t h ec l i e n tp r o p o s e dd y n a m i cs e l e c t i o ns u p p o r ta n dc o n f i d e n c ef o ra s s o c i a t i o nr u l em i n i n g t h i r d c o m p a r a t i v ea n a l y s i so ft h ea l g o r i t h ma n dd a t ap r e f e t c h i n gs y s t e m a f t e rac o m p a r a t i v e a n a l y s i so ft h e o r e t i c a la n de x p e r i m e n t a lm e t h o d ，t h ep r o p o s e dn e w _ a p r i o r ia s s o c i a t i o nr u l em i n i n g a l g o r i t h mc a nr e d u c et h et i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y a tt h es a m et i m e ，n e w f u p i n c r e m e n t a lf r e q u e n ti t e m s e ti n c r e m e n t a lu p d a t ea l g o r i t h mc a l lt r a n s a c t i o n s d a t as e tf r o mt h em o r e f r e q u e n ti t e ms e t sf o rt h ec h o i c eo fp r e - f e t c hd a t at oi m p r o v et h ec a c h eh i tr a t e t h r o u g ha n a l y z i n g a n dc o m p a r i n gt h es i m u l a t i o nv a l u e b a s e dc m i pd a t ap r e f e t c h i n gs y s t e mw i t hc m i pd a t a p r e f e t c h i n gs y s t e m ，y o uc a ns t h ep r o p o s e dv a l u e b a s e dc m i pd a t ap r e f e t c h i n gs y s t e m i s r e a l i z a b l e ，a n dr e d u c et h ef a i l u r er a t eo ft h ec a c h e ，r e d u c i n gt h ed a t aa c c e s st i m ea n dp o w e r c o n s u m p t i o n ，i m p r o v et h eq u a l i t yo fs e r v i c e k e y w o r d s ：m o b i l ec o m p u t i n g ，d a t ap r e f e t c h i n g ，a s s o c i a t i o nr u l e s ， u p d a t er a t e i v 第l 章绪论 第1 章绪论 1 1 研究背景和意义 随着计算机技术、通讯技术和网络互联技术的迅速发展，逐渐成熟的移动通信技术与移 动计算机的结合使人们随时随地访问所需数据变成现实。移动计算系统能够使用户携带着移 动计算机自由移动，并且在移动的同时通过移动通讯网保持与固定结点或其他移动结点连接， 这种新的给用户带来方便的移动计算环境成为了人们的新需求。 然而，与传统的分布式环境相比，移动计算环境又有其自身的特点【1 】：a 、移动性及位置 相关性：移动客户机可以在无线通讯单元内及单元间自由移动，而且在移动的同时仍然可能保 持与其他节点的通讯连接：此外，应用程序及数据查询可能是与用户位置相关的。b 、网络的 频繁断接性：由于网络条件及通讯代价的限制，移动客户机与固定网络或其他移动节点之间经 常处于主动或被动的断接状态。c 、网络条件的多样性：在整个移动计算环境中，不同时间不 同地点联网条件相差十分悬殊。d 、系统规模庞大：在移动计算环境f ，用户规模比常规的固 定网络环境庞大得多。e 、系统的安全性及可靠性较差：由于移动计算平台可以远程访问系统 资源，从而带来新的不安全因素。f 、资源的有限性：移动设备的电源通常只能维持几个小时： 此外，移动设备还受到来自通讯带宽、存储容量、处理能力、用户界面等方面的限制。g 、网 络通讯的非对称性：上行链路的通讯代价与下行链路有很大的差异。 正是由于移动计算环境的这些限制性特点，传统的缓存和数据预取技术在移动计算环境 中的使用得到广泛的认可【2 1 【3 】【4 1 。缓存技术通过利用客户访问的时间局部性原理f 5 l 【6 】，在客户端 本地c a c h e 中存放一份用户当前访问内容的副本，当用户下次访问该内容时，则直接从本地 c a c h e 中读取该内容，从而降低了客户事务请求响应的时间。然而，随着网络资源的更新频率 频繁，数据内容不断增加，缓存带来的性能将不再显著。冈此，为了更好的利用网络的资源 并进一步降低用户事务请求响应时间，引入了数据预取技术。数据预取技术不仅利用了客户 访问的时间局部性5 1 1 6 1 ，同时充分利用了客户访问的空间局部性【7 1 ，通过分析用户当前的访问 请求及历史访问信息，预测用户接f 来可能将访问到的内容并将其提前预取到缓存中。则当 用户下一次请求访问该内容时，则直接从客户端本地c a c h e 中读取该副本，从而提高了资源 的利用率及服务质量。数据预取技术是在缓存技术的基础之上的进一步发展和应用i 羽。数据预 取技术的关键是如何准确的预测把移动客户机未来将要使用到的数据并将其预取到缓存中， 从而减少了移动客户机事务访问时间，并且能够使移动客户机在网络断接的情况下也能够进 行事务处理。用户访问数据的时间局部性指用户刚访问过的数据很有可能在不久会再次被访 问到。空间局部性指少部分内容的访问记录占了总访问记录的相当大比例，主要表现在同一 个内容被同一个客户多次访问，一个内容被多个客户访问。数据预取技术是一种主动的缓存 技术，通过在处理客户当前的事务请求时，在服务器、代理服务器或客户端根据客户的历史 访问记录及当前请求预测用户接f 来将访问到的数据并将其预取到缓存中。可以看到，通过 西南大学硕十学伊论艾 数据颁取技术得到的缓存数据内容不仅有客户已经访问过的内容，同时也包括了客户未曾访 问的内容。 由此可见，在移动计算环境中利用数据预取技术根据移动客户机以前的访问记录，预测 用户将要使用到的数据，并在网络连接阶段把这些数据预驭到客户机缓存中，将显著提高数 据访问速度，减少数据访问时间，同时降低电能的消耗。特别地，在移动客户机网络断接的 情况下，也能进行事务处理。因此，研究数据预取技术在移动数据库中具有重要意义。 1 2 国内外研究动态 数据预取技术一经提出就引起了人们极人的关注。特别地，缓存与预取技术的结合使用 比只用缓存技术更有效的减少事务访问延迟，提高服务器的服务质量。目前国内外比较流行 数据预取模型主要有以下几种： 1 、基于访问概率的预取模型【9 1 【1 0 】【l l 】：主要考虑用户对数据的访问具有一定的规律，具有 历史性和相对集中的爱好，访问概率人的数据就预取剑客户端，因此提出了基于兴趣和访问 行为对未来将要访问的资源进行预测。 2 、基于数据挖掘的预取模型【1 2 】【1 3 】：从大量的数据中挖掘隐含的、先前未知的、对决策有 潜在价值的知识和规则的一种技术。可以根据用户访问的历史数据和当前访问的数据，利用 数据挖掘技术来预测用户将来可能的行为，从而为用户预取相关的数据。 3 、基了二w e b 语义的预取模型【1 4 】【1 5 】：根据用户会话特征，按语义对用户会话进行分类，服 务器确定用户会话所属的类别，并把用户可能使用的文档并发送到客户端。 4 、基于网络性能的预取模趔1 6 1 f 1 7 1 ：基丁：r t t ( r o u n dt r i pt i m e ) 等网络性能指标的w e b 智能加速技术，在对w e b 代理服务器上的业务进行分析和对网络r 1 v r 进行测量分析的基础 上，提出了智能预取技术。 5 、基于流行度的预取模型【1 8 】【1 9 1 ：按照过去访问的历史记录或利用z i p f 第l 定律和第2 定律对w e b 对象访问流行度建模，推算出哪些内容是热点，即最受欢迎或是访问量最多的数 据，然后预取给用户。 6 、基f 神经网络的预取模型【2 0 1 ：基于p p m 树的预测模犁。通过结合页面内容以及用户的 兴趣来调整模碰的输出，提出基于神经网络的w e b 预测模趔。通过抽取网页超链描述文字信息 中的关键词作为神经网络的输入，神经网络输出结果作为数据预取的依据，用户浏览路径页 面作为训练样本反馈给神经网络进行学习。 可以看到上述这些数据预取模型在传统的分布式计算环境中针对w e b 网页预取的应用研 究较多。在分布式计算环境中，基于有线网络进行w e b 页面的传送，传送的是完整的页面。 而在移动计算环境中，基于无线网络进行数据的传送，传送的只是w e b 页面上主要的内容。 并且在分布式计算环境中不用考虑网络带宽和客户端电能等系统资源。因此，传统的数据预 取系统的性能主要取决于预取数据的准确性。然而在移动计算环境中，由于网络的不对称性 2 t 1 3 研究内容 综合考虑移动计算环境特点和影响数据预取的各方面因素，将提出能够适应移动计算环 境的数据预取系统模型，使其能够根据每个用户的历史访问记录及网络中数据资源的更新变 化，准确的预测用户未来将使用到的数据并预取到客户端缓存中。因此，本文的主要研究内 容包括以下几点： 1 、研究设计移动数据库中数据预取系统。通过在移动数据库的客户端利用用户历史访问 记录利用关联规则挖掘技术得到用户访问数据的相关性并结合网络中数据资源的更新频率， 通过价值评估函数进行预取数据选择的预取系统l u eb a s e dc m i p 数据预取系统。使得 系统在给用户提供服务的同时，能够准确预测用户下一时刻将可能访问到的数据并预取到客 户端缓存中，从而减少用户等待服务响应的时间。 2 、设计适应移动计算环境的关联规则挖掘算法。结合移动计算环境中用户数据特点，在 传统的关联规则挖掘算法之上设计适应移动计算的关联规则挖掘算法。通过减少候选项集的 产生及事务数据库的扫描时间，提高传统关联规则挖掘算法的效率，减少移动客户机的电能 消耗。针对移动客户端的位置变化而导致的兴趣漂移，对增量事务数据库进行关联规则挖掘， 从而获得更多的关联规则用于预取数据的选择。考虑到移动客户端系统资源的消耗，提出根 据客户端电能使用率动态选择支持度和置信度进行关联规则的挖掘。 3 、对预取数据的价值评估。考虑到网络中的数据资源的更新频率及数据大小，数据的访 问延迟等等，根据这些参数构造一个预取数据价值评估函数，对数据挖掘得到的数据进行价 值评估，使得选择预取到缓存中的数据更有效。 1 4 论文的组织结构 基于研究内容，全文共分为六章。具体安排如下： 第一章概述了本文的研究背景和意义，分析了与本课题相关的国内外研究现状，结合现 状提出了本文主要研究内容以及论文结构等。 第二章介绍了与本文研究内容相关的研究技术和研究现状，包括移动计算与移动数据库 的概念，数据预取技术的优点、研究现状及不足，关联规则的挖掘技术。 第二章在传统的基于数据挖掘的预取系统基础上，提出了一种能够根据网络数据更新变 化，通过价值评估合理选择预取数据的预取系统。并描述了该预取系统的主要特征、系统结 构及基本功能。针对网络j “播中数据的更新变化及大小，提出了对预取数据利用价值评估函 数进行判断。 第四章介绍了根据预取系统得到的数据预取算法。通过对传统的关联规则挖掘算法的分 析，结合移动计算环境的特点，提出一种支持移动计算环境的关联规则挖掘算法。并介绍了 3 两南夫学硕卜学位论文 算法理论及代码描述。 第五章针对论文中提出的预取算法进行性能分析比较，同时实现数据预取系统，并将其 与c i i p 数据预取系统进行性能对比。 最后，第人章对全文进行t 作总结。总结了论文的主要下作，对以后的研究进行了展望。 4 助理p d a 、笔记本电脑、智能手机等) 的用户也越来越多，在任何时间、任何地点访问任何 数据将成为这个全新信息时代人们的需求。这些都将导致传统的基于有线网络和同定主机的 的分布式计算与分布式数据库不能满足人们的需求。移动计算是随着移动通信、互联网、数 据库、分布式计算等技术的发展而兴起的一种新技术。移动计算技术将使移动计算机或其它 移动智能终端设备在无线通信环境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 ) f 1 1 。 1 、移动计算环境的典型结构 由于移动计算环境的一些自身特点，传统的分布式计算环境中基丁二客户服务器模式已经 不能支持或不能有效支持移动计算环境。移动计算系统主要由位于前台的移动客户端( m o b i l e c l i e n t , 简称m c ) 和位于后台的固定网络中的服务器( s e r v e r ) 组成，它们之间通过移动支持常 点( m o b i l es u p p o r ts t a t i o n , 简称m s s ) 相连。图2 1 展示了一个支持移动计算的典型系统结构1 2 1 1 。 在图2 1 中的移动计算环境中，高速同定网络部分构成连接固定节点的主干网络，在l 爿定 网络中拥有很多移动支持节点( m s s ) 和若干固定主机( f i x e dh o s t ，简称f h ) 。固定网络中 的各固定主机部分维持一个服务器，各服务器维持一个本地数据，服务器之间高速、可靠的 连接，构成传统意义上的分布式计算系统。移动支持节点( m s s ) 是具有无线通信能力的服 务器，同时具备数据存储更新和数据分发的功能，在同定有线网络上保持与其他服务器高速 而可靠的连接，一个m s s 负责建立一个无线网络单元。无线网络单元中的移动客户端( m c ) 是一些移动设备，在与网络维持连接的同时可以跨单元自由移动。移动客户端( m c ) 可以从 任何一个无线网络单元经由m s s 连接剑固定网络中，其处理能力与存储能力与服务器相比非 常有限。这种与固定网络的连接可以通过与m s s 建立链路，也可以通过接收由m s s 发送的广 播信息。一个无线网络单元是由一个m s s 和m c 构成的逻辑上或者物理上的区域。 5 。 两南夫学硕士学忙沦艾 无线蜂窝【c c l l ) 单元 m s s ：m o b i l es u p p o r ts t a t i o n ( 支= 持移动计算的 固定结点) f h ：f i x e dh o s t ( 固定主机) 图2 1 移动计算环境的典型结构 2 、移动计算环境的典型特点 从图2 1 我们可以看出，移动计算环境是传统意义上的分布式计算环境的扩展。用户可以 携带移动终端设备在无线网络单元中自由移动，并在移动过程中通过移动通信网络与同定节 点和其他移动节点交换信息。冈此，与传统的分布式计算环境相比，移动计算环境具有以下 的特点【1 1 【2 2 1 1 4 6 】 ( 1 ) 设备的移动性与位置的相关性。在移动计算环境中，用户携带一台移动设备不仅可以 在不同的地方连接网络，而且可以在移动的同时也保持与固定的网络连接。同时，应用程序 及数据的查询可能是位置相关的。如在行进途中的用户需要了解目的地的交通情况，随着位 置的变化在不同的时间其查询的结果是不同的。这种移动计算平台的移动性将可能导致系统 访问布局的变化和资源的移动性。这就要求移动数据库系统能支持这种移动性，解决过区切 换的问题，并且实现位置相关的处理。 ( 2 ) 网络( 主动或被动) 的频繁断接性。移动计算设备在移动的过程中由于受使用方式、 电源能鼍、网络条件等冈素的限制，移动计算设备与同定网络之间不是长时间的连接，而会 经常发生主动或被动的断接现象。在传统的分布式环境中如果客户机与服务器之间发生断开 现象则被看作是故障，重连后将作为事务故障处理。而在移动计算环境中，m c 可能为了常省 电能或者由r 网络故障的原因，m c 和服务器之间可能频繁地发生断接。这种现象将允许它出 现，并且作为一种正常的状态。这就要求移动数据库系统中的事务在断接状态f 仍然能够继 续运行，或者自动地进入睡眠状态，而不会由于网络断连而撤消操作。 ( 3 ) 网络连接的多样性。移动设备在不同的地方可以使用不同的无线连接方式( 如卫星通 信系统、数字蜂窝系统、红外线技术、蓝牙无线通信网络等) 接入围定网络。这些不同的接 入方式其带宽、可靠性、网络通信协议等的不同将导致在不同的时间可用的网络带宽与服务 质量是的多样性。因此，移动数据库中的查询优化等机制必须针对不同的网络条件选择不同 6 第2 章移动计算与数据预取技术 的策略。 ( 4 ) 系统的安全性及可靠性较低。无线网络与固定网络相比，由于其更容易受到干扰而产 生传输出错或者网络故障现象导致可靠性较低。如受到电磁的干扰或者天气影响会导致传输 数据的丢失；高山、树林等会对网络信号产生影响；用户携带移动设备移动的速度及于基站 的距离也对网络信号产生影响，有时甚至处于盲区( 即无网络信号) 。此外，由于移动设备 便于携带和工作环境的方便，也会带来潜在的不安全因素，如损坏、失窃等。这就要求移动 数据库系统比普通数据库系统提供更强大的安全机制。 ( 5 ) 移动设备资源的有限性。移动设备体积较小且由于其便携性，移动设备主要依靠蓄电 池供电。而现在的电池容量非常有限，一般在正常的连续使用情况下只能维持几个小时。据 研究表明，电池容萤在未来五年内只能提高约3 0 ，远远低于同期c p u 速度和存储容量的发展 速度。尽管已有不少节能技术应用丁二移动设备，但电池容量问题仍将长期存在。此外，移动 设备还收网络通信带宽、存储容量、处理能力的限制。因此，在移动数据库系统中必须充分 考虑这些问题，在进行查询优化处理、存储管理时应提高资源的利用率。 ( 6 ) 网络通信的非对称性。由于物理通信媒介的限制，一般的无线网络通信都是作对称性 的。这主要因为同定节点拥有强大的发送设备，而移动设备的发送能力非常有限。于是这种 非对称性表现在下行通信信道带宽远远大于上行通信信道带宽；同时，网络中传送的数据鼍 具有非对称性，从服务器传送到m c ( 下行数据流) 的数据量远大于从m c 传送到服务器( 上行 数据流) 的数据量。所以，在移动数据库中必须充分考虑到这种差异，采用合适的方式进行数 据的传输。 ( 7 ) 系统的规模庞大。在许多的移动数据库应用环境中，都要求系统同时支持大量的移动 用户的并发访问。如果采用普通的处理方式将导致移动数据库系统的效率非常低，这就要求 移动数据库系统具有比传统的分布式数据库系统高得多的可伸缩性。 2 1 2 移动数据库 从数据库技术的发展历程来看，计算环境和数据库技术保持着一种同步发展的态势，它 们之间相互影响、相互促进。随着移动计算环境逐渐成为数据库技术的研究和应用环境，一 种更加灵活、更加复杂的数据库技术就应运而生这就是移动数据库技术。移动数据库系统是 指能够支持移动计算环境的动态分布式数据库，其数据在物理上分散而逻辑上集中。它涉及 到数据库技术，分布式计算技术，移动通信技术等多个学科。移动数据库系统的目标就是能 够有效地支持移动环境中的各种数据应用，满足用户的访问需求。 l 、移动数据库中的关键技术 ( 1 ) 数据复制与缓存技术吲 2 6 l ：在移动计算环境中，网络的连接是一种弱连接，移动客 户端经常处于断接状态。数据复制与缓存技术指在网络中的多个 i 了点上维护数据的备份，可 以在服务器之间进行数据复制，也可以在客户机上进行数据的缓存。在移动计算环境中，通 过使用数据复制与缓存技术提高移动数据库系统的可用性、可靠性以及访问性能，从而使移 7 阿南人学硕卜学位论文 动客户端征断接状态卜也能进f j 事务处理。但是传统的分布式数据库系统中的复制技术上要 考虑在服务器之间的复制，这种策略是一种静态策略。当m c 环境经常发生变化时，这种复制 技术就不能够适用。目前移动数据库系统中的复制普遍是采用乐观复制法，系统允许m c 在断。 接的情况下在本地缓存中的副本执行读写操作，待重新连接时进行数据同步处理，从而维持 系统数据的一致性。其中，本文的研究课题就是当移动客户端处于连接状态时，如何准确的 预测未来将要使用的数据，并复制到m e 的缓存中。通过预取技术的使用提高缓存的命中率， 降低缓存的失效率，同时减少电源的消耗，支持移动客户端的断接操作。 ( 2 ) 数据广播技术1 2 4 】1 2 6 1 ：在移动计算环境f ，移动客户机经常处于断接状态，且与服务 器通信的网络带宽有限，同时由于网络的非对称性。为了支持大规模的移动用户对数据的并 发访问，由数据库服务器把大多数用户频繁访问的热点数据组织起来，以周期性的广播形式 广播给移动客户端。这就是移动数据库系统中的数据广播技术。通过使用数据广播技术，实 现了以较小的代价解决了大量用户同时访问数据信息的问题，同时充分利用了网络带宽。 ( 3 ) 移动查询优化技术口5 】【2 6 l ：在移动数据库中，查询优化处理是基于移动计算环境的， 由于用户的移动、频繁的断接以及用户所处网络环境的多样性，移动查询优化不能采用传统 的分布式数据库系统中的查询优化算法，必须综合考虑资源、连接状态、m c 所处的环境等等 因素，采用动态策略，利用多种方法，消除断接、带宽多样性等冈素，能够根据网络条件采 取恰当的优化策略。 ( 4 ) 移动事务处理技术【2 3 】 2 6 1 ：m e 发出的事务叫移动事务，该事务通常属于长事务，它不 像分布式事务是在多台固定主机上并发执行，依赖于节点的移动性，不能完全由系统来协调， 还受结点移动行为的控制。传统的事务模型不再适用，需要研究适应于移动计算环境的新的 事务模型。主要涉及到m c 在不同单元提交的移动事务的调度和执行策略，以及事务并发控制 问题等。 ( 5 ) 移动数据库的安全技术【2 6 1 1 2 7 1 2 s 】：通常来说，无线网络的安全性远低于【司定网络。所 以，数据通过无线网络进行传输比通过同定线路传输更易受剑盗用和欺骗；其次，移动设备 的便携性，也使得移动设备更容易失窃；另外移动计算环境使用户可以连入任意网