（计算机应用技术专业论文）移动计算环境中基于移动代理的数据管理技术研究.pdf

摘要移动计算的网络环境具有鲜明的特点：移动性、频繁断接性、带宽多样性、可伸缩性、弱可靠性、网络通信的非对称性、电源能力的局限性。这些特点使得移动计算环境的数据管理技术需要考虑许多在传统分布式系统中不用考虑的问题：如对断接操作的支持、对跨区事务的支持、对位置相关数据的管理、以及对提高有限资源的利用率和对系统效率的考虑等等。本文在对移动计算环境中数据管理领域的最新研究成果进行了系统、全面地分析和总结的基础上，就缓存技术、数据复制技术和移动代理技术展开了深入、细致地研究，阐明了作者的观点。取得了若干创新和成果。本文的主要创新点包括：1 提出了一种新的针对移动计算环境的数据管理体系结构：基于移动代理的数据管理体系结构( d m a b m a ) 。d m a b m a 采用了m s s a g e n t 和m a 架构，通过代理的合理插入，把移动计算环境分成了两大部分：传统的分布式网络部分和无线网络部分，这样针对不同的网络环境可以选择更合适的方法和技术解决相应的问题，增强了系统的整体性能。2 提出了一种新的缓存失效策略：基于移动代理的缓存失效方案( c i s b m a ) 。c i s b m a 能较好的处理移动计算环境中由于频繁断连带来的诸多问题，能充分利用固定网络的高带宽和高可靠性来弥补无线网络的有限带宽和弱可靠性，该策略是为当前广泛采用的移动计算网络结构而设计的，具有较强的实际应用价值。3 提出了一种新的复制机制：温和一致性代理复制机制( m c a r m ) 。m c a r m 采用了主节点的复制管理器与辅助节点的m s s a g e n t 协调工作的架构，吸取严格一致性协议和弱一致性协议的优势，又避开其局限性和复杂性，更好的适应移动计算环境的要求，并能与缓存失效策略c i s b m a 协同工作，较好满足了移动应用的需求。4 提出了一种应用于d m a b m a 的移动a g e n t 机制，该机制用j a v a 语言实现它提供了灵活的计算模式，是支持系统异构性、移动主机断接性、减少无线网络上的通信流量的有力保障手段。d m a b m a 是一种针对移动计算环境，具有高可用性的体系结构，它将移动计算网络上大量分散的节点组织成一个逻辑网络，与数据复制、数据缓存和移动代理等技术相结合，形成一个具有高伸缩性、高性能的数据管理体系。关键词：移动计算环境，数据管理体系结构，移动代理，缓存失效，数据复制a b s t r a c tm o b i l ec o m p u t i n ge n v i r o n m e n th a sr e m a r k a b l ec h a r a c t e r i s t i c si n c l u d i n gm o b i l i t y , f r e q u e n td i s c o n n e c t i o n ，v a r i e t yo fb a n d w i d t h ，s c a l a b i l i t y , w e a kr e l i a b i l i t y ,d i s s y m m e t r yo fc o m m u n i c a t i o n ，b a t t e r yp o w e rr e s t r i c t i o n s ，e t c ，w h i c hb r i n g sn e wc h a l l e n g e st od a t am a n a g e m e n t h o ws h o u l dt h ed i s c o n n e c t i o no fm o b i l eh o s tb eh a n d l e d ? h o ws h o u l dt h eh a n d o f f t r a n s a c t i o n sb ep r o c e s s e d ? h o ws h o u l dt h el o c a t i o nd e p e n d e n td a t ab em a n a g e d ? h o wc o u l dt h eu t i l i z a t i o no fr e s o u r c e sa n dt h ep e r f o r m a n c eb ei m p r o v e d ?b a s e do nt h es y s t e m a t i ca n a l y s i sa n dc o m p r e h e n s i v es u m m a r i z a t i o no ft h er e l e v a n tw o r ko 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 ge n v i r o n m e n t ，t h i sd i s s e r t a t i o nr e s e a r c h e st h r e ep r i m a r yf i e l d si nd e p t h ，i l l u s t r a t i n gt h ea u t h o r sc r e a t i v ev i e w p o i n t ss o a st om a k ei m p o r t a n tb r e a k t h r o u g h s t h ei n n o v a t i o n si nt h i sd i s s e r t a t i o na r em a i n l ya sf o l l o w s ：1 an e wa r c h i t e c t u r eo fd a t am a n a g e m e n ta r c h i t e c t u r eb a s e o nm o b i l ea g e n t ( d m a b m a ) i nm o b i l ec o m p u t i n ge n v i r o n m e n ti sp r e s e n t e d ，i ta d o p t st h ef r a m e w o r ko fm s s a g e n ta n dm o b i l e - a g e n t ，w h i c ht h r o u g hi n s e r t i o no fa g e n t ，d i v i d e st h em o b i l ec o m p u t i n ge n v i r o n m e n ti n t ot w op a r t ：t r a d i t i o n a ld i s t r i b u t e dn e t w o r ka n dw i r e l e s sn e t w o r k s ot h a tw ec o u l ds e l e c tt h eo p t i m a lm e t h o dt os o l v ed i f f e r e n tp r o b l e mf o rd i f f e r e n tn e t w o r k st oi m p r o v et h ep e r f o r m a n c eo ft h ew h o l es y s t e m 2 an e ws t r a t e g yo fc a c h ei n v a l i d a t i o ns c h e m ab a s e o nm o b i l ea g e n t ( c l s b m a )i sp r e s e n t e d i tc a r lb eu s e dt os o l v em a n yt h ep r o b l e m sr e s u l t i n gf r o mt h ed i s c o n n e c t i o no fm o b i l eh o s ti nm o b i l ec o m p u t i n ge n v i r o n m e n t , a n dc a nm a k eu pf o rt h ed e f e c t so ft h el i m i t e db a n d w i d t ha n dw e a kr e l i a b i l i t yo ft h ew i r e l e s sn e t w o r kt h r o u g ht h eh i g hb a n d w i d t ha n dh i 卧r e l i a b i l i t yo ft h ef i x e dn e t w o r k t h i ss t r a t e g yi si n t e n d e dt ob ea p p l i e dt ot h ec o m m o nm o b i l en e t w o r k i n ga n dh a sp r e f e r a b l ep r a c t i c a b i l i t y i i i3 an e wm e c h a n i s mo fm o d e r a t ec o n s i s t e n c ya g e n tr e p l i c a t i o nm e c h a n i s m( m c a r m ) i sp r e s e n t e d ，i ta d o p t sah a r m o n i o u sf r a m e w o r ko fr e p l i c a t i o nm a n a g e ri nm a s t e rn o d ea n dm s s - a g e n ti ns e c o n d a r yn o d e ，w h i c hh a sa d v a n t a g eo ft h et i g h tc o n s i s t e n c yp r o t o c o la n dl o o s ec o n s i s t e n c yp r o t o c o lr e s p e c t i v e l yw h i l ea v o i d i n gt h e i ri n s u f f i c i e n c ya n dc o m p l e x i t ya tt h es a m et i m es o a st oa d a p tw e l lt ot 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 s m c a r mc a nw o r kw i t hc i s b m ai nh a r m o n yt om e e tm o b i l ea p p l i c a t i o n sd e m a n d 4 am o b i l ea g e n tm e c h a n i s ma p p l i e dt od m a b m ai sp r e s e n t e d ，i m p l e m e n t i n gb yj a v aa n do f f e r i n gt h ef l e x i b l ec o m p u t i n gm o d e w h i c hc a l ls u p p o r tt h eh e t e r o g e n e o u ss y s t e ma n dm o b i l eh o s t sd i s c o n n e c t i o ns oa st oc a nr e d u c et h et r a f f i c so f v v i r e l e s sn e t w o r k d m a b m ai sah i g ha v a i l a b l ea r c h i t e c t u r ei nm o b i l ec o m p u t i n ge n v i r o n m e n t ，w h i c ho r g a n i z e sal o g i cn e t w o r ki n c l u d i n gal o to f d i s t r i b u t e dn o d e s u n i t e d 谢md a t ar e p l i c a t i o n ，d a t ac a c h i n ga n dm o b i l ea g e n tt e c h n o l o g i e s ，d m a b m af o r m sas c a l a b l ea n dh i g hp e r f o r m a n c ed a t am a n a g e m e n ta r c h i t e c t u r e k e y w o r d s ：m o b i l ec o m p u t i n ge n v i r o n m e n t ，d a t am a n a g e m e n ta r c h i t e c t u r e ，m o b i l ea g e n t ，c a c h ei n v a l i d a t i o n ，d a t ar e p l i c a t i o n缩略词表缩略词英文注释m s sm o b i l es u p p o r ts t a t i o nm hm o b i l eh o s tm am o b i l ea g e n td m a b m ad a t am a n a g e m e n ta r c h i t e c t u r eb a s e - o nm o b i l ea g e n tc i s b m ac a c h ei n v a l i d a t i o ns c h e m ab a s e o nm o b i l ea g e n tm c a r mm o d e r a t ec o n s i s t e n c ya g e n tr e p l i c a t i o nm e c h a n i s mm a em o b i l ea g e n te n v i r o n m e n tm i pm o b i l e i pc i pc e l l u l a ri pr mr e p l i c a t i o nm a n a g e rr m ir e m o t em e t h o di n v o c a t i o nj v mj a v av i r t u a lm a c h j n e中文注释移动支持站移动主机移动代理基于移动代理的数据管理体系结构基于移动代理的缓存失效方案温和一致性代理复制机制移动代理环境移动i p蜂窝p复制管理器远程方法调用j a v a 虚拟机电子科技大学博士论文1 1 论文的研究背景第一章引言计算技术和无线通讯技术的发展与结合产生了一种全新的计算模式移动计算模式。随着信息社会的发展，人们对使用信息的场合、时间、方式和方法提出了越来越多全新的概念，而这些需求的出现正是移动计算技术发展的源动力。在过去的1 0 年里，这种全新的计算模式得到了飞速的发展，并在越来越多的领域中发挥了不可替代的作用。可以预测，移动计算模式必将成为未来信息时代的重要成员，并对人们使用信息的方式产生深远的影响。移动计算模式代表着网络发展的一种必然趋势。国际著名的i t 市场研究机构m e t ag r o u p 和g a r t n e rg r o u p 等的研究报告表明，在未来的1 0 年之内，8 0 以上的商业用户将采用远程或移动的解决方案；全球将有数亿职员的日常办公环境是非传统的工作环境。这是一个巨大的市场，而在其中占据核心地位的移动数据管理技术也将具有广阔的市场前景和发展空间。1 1 1 移动计算环境的网络结构移动计算环境是分布式计算环境的扩展，它的网络可根据其结构分为有中心网络( i n 盘a s t r u c t u r e d n e u v o r k ) 和无中心网络( i n f r a s t r u c t u r e l e s s n e t w o r k ) 。在有中心网络中，移动用户通过固定的基站进行通信，如商用移动通信系统；而a dh o c 是一种无中心网络。l l 。l ，1 典型的网络结构在现有数字网络的基础上，典型的网络结构如图l 一1 所示 1 1 。在移动计算环境中，高速固定网络部分构成主干，固定网络中拥有若干移动支持站( m o b i l es u p p o r ts t a t i o n ，简称m s s ) ；m s s 是支持移动计算的固定站点，具有无线通信接口，负责管理特定的无线网络单元；移动主机( m o b i l eh o s t ，简称m h ) 可以从任何个无线网络单元经由m s s 连接到固定网络中：而f h 是f i x e dh o s t 的简称，指没有无线通信接口的固定主机。相对于可靠性不高的无线网络单元，我们将固定网络部分称为可信部分。第一章引言无线广播单元图1 - 1 移动计算环境的典型结构无线局域网1 1 1 2a dh o c 网络结构a dh o e 网络是一种无中心的网络，它指的是一种工作在无固定结构环境下的自组织的无线移动网络 2 1 【3 】，即m a n e t ，它几乎不需要手工配置和维护，就能使网络内的节点工作在一起。一个m a n e t 完全可以有能力不用在路由层配置而自发地形成网络的结构，而且，路由层可以根据节点的移动，处理频繁的网络拓扑结构的重配置。m a n e t 网络是移动的，即网络中的所有节点都可以完全自由的在空间中移动，在任何时刻，一个连接模式的建立只依赖于各个节点的位置和它们收发器的覆盖范围。只要节点可以提供不同的网络接口，m a n e t就可以成为一个多种网络并存的异种网络。a dh o c 网络是一种有特殊用途的对等式网络，使用无线通信技术，网络中的节点互相作为其邻居( 在其直接通信范围内的节点) 的路由器，通过节点转发实现节点间的通信。它又被称为多跳网络( m u l t ih o pn e t w o r k ) 、无固定网络设施的网络( i n f r a s t r u c t u r e l e s s n e t w o r k ) 或自组织网络( s e l f o r g a n i z e d n e t w o r k ) 。如图1 - 2 所示，在a dh o c 网络中，既不需要一个固定的网络结构，也没有专用的固定的基站或路由器作为网络的管理中心。网络中的每个节点都相当于一个移动的路由器，这些节点作为同等实体相互连接，实现信息包的转发，它们都参与路由的发现和维护过程，从而构成了一个a d h o c 网络。电子科技大学博士论文图1 2 a d h o e 网络与有中心网络相比，a d h o c 网络不需要提供固定的骨干设施，因此，a d h o c网络主要应用在军事上，以及一些紧急情况，如受灾地区的通信、边远地区和勘探等场合的通信。在a dh o c 网络中，每一个移动节点都有自己的无线收发器，使之可以在一定范围内与其它节点通信，一个节点也可同时配备几个收发装置，使得它可以连接在固定网络上，成为与固定网络联系的一个接口。除非采用了间接通信机制，否则一个节点是无法与在其通信范围之外的其它节点通信的。节点间的通信可以通过节点链完成，链上的相邻节点是直接通信的，沿着这条链路，数据就可以以“多跳”的方式传输，因此所有节点都必须有能够路由和转发数据的能力。a dh o c 网络有平面结构和分级结构两种。平面结构是完全的分布式结构，不仅网络规模受限，有些控制功能也很难实现。而分级结构通过分簇和引入相对的控制中心，使网络有较好的可扩充性，并且可以使用基于有中心的控制技术，随着a dh o c 应用的增加，网络逐渐呈现出分级化的趋势。1 1 2 现有的无线网络技术移动计算网络基本上可以分为两种解决方案；广域解决方案和局域解决方案。广域方案主要是依靠无线蜂窝数据通信网络和卫星通信网络作为移动计算第一章引言的物理网；而无线局域网是在地域范围上受限制，但能提供更高速率的移动解决方案。1 1 2 1 模拟蜂窝系统模拟蜂窝系统是早期的移动通话系统，它的覆盖区域被划分为多个区间( c e l l ，类似于蜂窝) ，通过模拟调频信号来传输语音，可以复用附近( 不是邻接)区间的传送频率。c d p d ( c e l l u l a rd i g i t a lp a c k e td a t a ) 就是一种利用模拟蜂窝通信系统的语音通道传输数据的技术，它所支持的最大数据传输率为1 9 2 k b s 。1 1 2 2 数字蜂窝系统数字蜂窝系统被称为第二代蜂窝系统，它采用了数字编码技术，与传统的模拟蜂窝系统相比，最大的优点是它的抗干扰能力强和频带的利用率高。它具有很高的强壮性和智能性，可以灵活地与有线数字网络集成，降低了r f 发射功率，可以对私有通信加密，降低了系统的复杂度，支持更大的用户容量。1 1 2 3 卫星网络移动卫星服务允许全球覆盖，可以支持6 4 k b p s 4 5 m b p s 的速率。在这些系统中，卫星起着移动通信基站的作用，支持用户在地球的任何角落进行通信。卫星通信网络的一个典型特点是非对称性，即卫星的下行信道带宽要远大于上行信道。但卫星接入方式受气候影响较大，在下雨情况下卫星的传输极容易发生衰减。此外，卫星的传输并不安全，侵入卫星链路比侵入陆地线路更容易，所以需要客户自己在发出信号之前对数据加密并建立应用层防火墙。1 1 2 4 红外技术上述无线网络技术都是通过无线电频段进行通信的，而红外技术则是利用红外线来传输数据，它的优点是带宽较高( 可达1 6 m b p s ) ，不需要分配无线电频谱，不易受电子干扰。但是其缺点也很突出，如传输距离有限( 不到2 英里) 、受视距限制( 必须在视线上直接对准) 、易受环境的干扰( 中间不能有任何阻挡) ，同时只限于在两个设备之间进行，不能同时链接更多的设备。1 1 2 5 无线局域网无线局域网被称为室内无线网络，相对于室外无线网络( 如蜂窝通信系统) ，它的数据传输率要高两个数量级，达到2 l o m b p s 。无线局域网一般采用电子科技大学博士论文c s m a i c d 和c s m a c a 协议，其缺点是作用范围较小，一般只能局限于一幢建筑物内使用。目前无线局域网领域的两个代表为：i e e e 的8 0 2 1 1 和欧洲电信标准协会( e t s i ) 开发的h i p e r l a n 。1 1 2 6 人域网随着各种短距离无线通信技术的发展，学术界提出了人域网( p a n ：p e r s o n a la r e an e t w o r k ) ，其核心思想是：用无线电或红外线代替传统的有线电缆，实现个人信息终端的智能化互联，组建个人化的信息网络。从计算机网络的角度看，p a n 是一个局域网；从电信网络角度看，p a n 是一个接入网，因此有人把p a n称为电信网络的“最后一米”的解决方案。大家所熟悉的蓝牙( b l u e t o o c h ) 技术就是属于p a n 的一种技术。1 1 3 移动计算环境的特点移动计算网络的技术特点主要表现在三个方面：无线通信、用户移动性和便携式。无线通信信道的速率低、误码率高，如何提高速率，保证数据通信的可靠性是一个重要的问题；用户的移动性带来了用户动态跟踪和寻址、移动切换时通信性能的稳定性等需要深入研究解决的问题：移动终端的便携性对移动计算网络的普及至关重要。以上这三个特点使移动计算网络的设计与实现同固定计算机网络有很大的不同，需要在硬件、协议和应用程序等方面进行更多的创新。与基于固定网络的传统分布式环境相比，移动计算环境具有以下特点：移动性：移动计算机在环境中流动，这就导致系统访问布局的变化和资源的移动性。用户在移动过程中的数据和信息需求经常是位置相关( l o c a t i o n d e p e n d e n t ) 和时间相关( t i m e d e p e n d e n t ) 的，如用户需要了解沿其前进方向半径为1k m 的地区的天气和交通情况在不同地点、时间的查询结果是不同的，这种需求是传统d b m s 不能提供的。断接性：一般移动主机与网络不是长时间连接，而是频繁、有预见的入网和断接。传统的数据库管理系统为用户提供服务时，都是基于长时间联网的。比如：当用户提交服务请求后进行断接操作，下次又联入网络要求服务结果，传统的数据库管理系统是无法提供此类服务的。第一章引言带宽多样性：移动主机的移动性使得不同时间可用的网络带宽与服务质量变化多端，甚至相差悬殊。移动主机既可以联入高带宽的固定网络中，也可以工作在低带宽的无线广域网中，因此，移动数据的查询优化等机制必须针对不同的网络条件选择最合适的策略。网络通信的非对称性：由于物理通信媒介的限制，一般的无线网络通信都是非对称的。固定服务器节点可以拥有强大的发送设备，而移动计算机的发送能力非常有限，于是下行链路的通信带宽和代价与上行链路相差很大。另外，许多客户服务器应用中的信息流动范型也会引起通信的非对称性。移动主机的电源能力：移动计算机主要依靠蓄电池供电，而现在的电池容量非常有限，一般在正常情况下只能维持2 到5 小时。据估计，电池容量在未来五年内只能提高3 0 ，这远远低于同期c p u 速度和存储容量的发展速度。因此，尽管有不少节能技术应用于移动计算机，但电池容量问题仍将长期存在。可靠性：无线网络与固定网络相比，可靠性较低，更容易受到靠干扰而出现网络故障。规模：许多移动数据应用环境都需要同时支持大量的移动用户并发访问，这就要求移动计算环境下的数据库系统比传统的数据库系统有高得多得可伸缩性。移动数据库系统是传统分布式数据库系统的扩展，d u n _ h a m 等【4 1 按照自治性、分布性以及异构性对分布式系统做了分类，如图1 3 所示。移动异构数据库系统一分布异构数据库系统异构性分布性十移动同构i 笪蔓同塑移动多数据库系统数据库系统数据库系统分布多数据库系统分布异构多数据库系统移动异构多数据库系统图1 - 3 移动数据库系统分类图自治性电子科技大学博士论文移动计算网络必然包含固定网络部分，而这个固定网络部分构成一般的分布系统，因此，移动计算系统可以看成分布式系统的动态类型，其网络中节点之间的链路能够动态地变化，如移动计算机与m s s 之间的连接。根据移动计算系统的这个特点，d u n h a n 将移动数据库系统定位为移动异构多数据库系统。一般认为，移动计算是分布计算的推广，分布计算是移动计算的特殊形式。尽管两者之间许多方面是相通的，但它们之间仍存在着不少差别。一个主要差别是：分布计算的目标位置是透明的，而移动计算的目标位置是不透明的；另一个主要差别是代价，性能观不同，这使得分布式数据库中，许多问题的最佳解决方案在移动计算环境中反而是不可接收的。表1 1 中，列举了移动数据库管理中的关键技术与传统分布式数据库之间的一些主要差别吼表1 - 1 移动数据管理和分布数据管理的差别数据管理技术移动数据管理与分布数据管理的差别应用程序可能是位置相关的：需要适应可变的系统环境。事务处理能够描述移动性的新模型：事务的过区切换。频繁的网络分割；移动计算机的断接不认为是系统故障；故障恢复移动性可能要求更多的日志记录；在过区切换时从短暂断接中恢复的技术。不同程度的一致性约束( 弱一致性约束) ；数据复制频繁的断接使移动计算机的缓存刷新必须采用新技术。位置相关；不同的代价因素；查询结果可能返回到不同的位置：查询处理需要可适应技术；特殊查询方式；数据广播。名字解析移动性和断接性要求采用新型的全局命名策略。1 2 移动计算环境中的数据管理技术第一章引言移动计算环境中的数据管理问题是一个新兴的研究领域，目前尚不成熟，但在这一领域中，许多研究人员已经开展了大量的研究工作，提出了许多的理论、技术和方法，本节将对与本论文密切相关的三个研究方向中的已有研究成果进行系统分析和总结。1 2 1 缓存技术缓存( c a c h e ) 技术在传统的分布式系统中得到广泛应用，但移动计算环境具有低带宽、易断连、低电源容量的特性，使得移动客户缓存的管理要充分考虑频繁断连带来的诸多问题，因此，缓存管理协议应能优化利用有限带宽、容忍断连、有效使用电能，并对无线网络提供不同q o s 的适应性。本小节将介绍两种典型的移动计算环境中的缓存管理策略：缓存失效报告技术和语义缓存技术。1 2 1 1 缓存失效报告技术i m i e l i n s k i 和b a r b a r a 等人，提出了一种新的缓存技术，称为缓存失效报告技术6 】【7 1 ：即服务器定期或异步地广播缓存失效报告，该报告中包含了最近被更新的对象，根据报告内容，客户可使缓存中被更新对象失效，以保证缓存的有效性。在该算法的基础上，针对不同的情况，又提出了许多改进算法，例如，j i n g和a h m e d 等人提出的一种基于位序列( b i t s e q u e n c e s ) 自适应缓存失效策略【8 】；c a i 和t a n 等人提出了一种能有效节约移动主机电能的缓存失效策略【9 】【1 0 1 ；以及我们提出的在移动计算环境中基于移动代理的缓存失效方案【1 ”。缓存失效策略是本文的研究重点之一，我们将在第三章中进行详细的分析和讨论。1 2 1 2 语义缓存语义缓存是一种基于客户查询语句之间语义相关性而建立的缓存，语义缓存的内容由以往查询的结果以及查询描述构成，缓存命中通过将查询语句同缓存中的各个缓存项描述匹配判断。客户通过语义缓存可以实现动态的数据复制并动态的定义他所感兴趣的数据空间。在现实世界中，大量应用所发出的查询具有很强的语义相关性，例如：一个企业的部门经理，他通常对他所负责的部电子科技大学博士论文门情况更加感兴趣，因此对企业数据库的查询多是与该部门相关的数据，这些查询之间的语义相关性就高。相比其他以对象或元组为粒度，基于空间局部性和时间局部性的缓存，以查询结果为缓存粒度、基于查询语义局部性和时间局部性的语义缓存更适用于关联查询访问，而且当数据存放的聚集度不好时，也能保证缓存效率。文献 1 2 将语义缓存同以页和元组为粒度的缓存进行性能比较，通过实验验证了语义缓存较另两种缓存对关联查询处理具有更少的通信开销和更快的响应时间；文献 1 3 】 1 4 】研究了匹配紧密相关的布尔表达式相交以及包含的判断问题：文献 1 5 侧重讨论了缓存完整性和缓存致性方面的设计和性能的考虑：文献 1 6 】对如何由视图得出查询结果做了理论分析，对查询从语义缓存导出有定的指导意义；文献 1 7 】提出了一个从缓存获得查询结果的语义缓存逻辑框架，研究工作是基于d a t a l o g 进行的。文献 1 2 【1 8 】讨论了基于语义的缓存替代策略。基于语义内容的数据缓冲管理方法是一种很有效的方法，主要有以下特点： 客户端具有缓存数据的语义描述。在查询处理时，客户端使用语义信息决定本地数据是否可以满足查询条件。通过修改查询条件，向服务器发出本地缓存不能满足的部分数据的查询请求，从丽减小通信开销。 缓存替换策略信息存储在一个可动态调整的语义区中。其优点是不用维护每一个元组的替换信息，而是通过语义信息维护一组元组的替换信息，极大地减少了物理存储开销。 可以使用复杂函数来决定缓存替换的条件。由于本文的重点不在语义缓存上，所以我们简单的介绍一下基于语义缓存的查询导出，其基本思想是：首先确定与当前查询作用在相交关系上的缓存项，再从这些相关的缓存项中判断有无查询的精确匹配或包含可导出匹配，如果有，查询结果可从该缓存项描述的缓存块中通过投影、选择查询操作获取；若没有，但缓存项与查询是可查询裁剪相交的，也可对查询进行裁剪，将裁剪后的查询送到服务方处理，连同缓存中获得的部分查询结果一起构成查询结果。利用已有的查询结果对查询处理进行优化，最早在文献 1 9 1 6 】中有讨论。其中文献 1 9 】的思路是从一组查询请求中找出公共表达式来进行查询优化，也就是通过使用前面查询产生的中间结果优化后续查询的处理。文献【1 6 考虑如何通第一章引言过导出关系计算查询，在理论上做了较好的研究，但没有考虑相交情况，也缺乏进一步的算法研究。文献 1 2 1 5 】提出基于语义相关的缓存模型，列举缓存满足查询可能出现的情况，但并未对如何从缓存中找出查询结果做深入讨论。文献【1 7 】 2 0 】基于d a t a l o g 和逻辑数据库对如何用语义缓存满足查询进行研究。如何依据缓存描述的信息从缓存中找出可能包含的查询结果或部分结果是基于语义相关缓存研究的重要问题。1 2 2 数据复制技术复制( r e p l i c a t i o n ) 的主要目的是提高分布式数据库系统的可用性、可靠性以及访问性能。传统的复制技术主要考虑在服务器之间的复制，并且假设服务器之间是经常保持连接的；此外，传统的复制策略都是静态的，即由系统管理员统一安排好复制布局后就固定不变了，如果系统中用户访问范型发生较大变化而要求改变当前布局时，必须要管理员重新配置分布系统。因此，传统的复制技术在移动计算环境中不能有效工作。复制是指在多个节点上完成数据的备份，包括服务器的中心数据库的复制以及在移动主机中保存数据库的复制，其目的是保持数据库系统各节点中数据状态的一致性。迄今为止人们已经提出了多种移动复制算法：如两级复制算法【2 ”、b a y o u x 系统 2 2 1 、主动复制机制矧、自适应数据复制算法】，而且也有文献把数据广播技术纳入复制机制，称为空中复制，本小节将讨论目前具有代表性的研究成果有j g r a y 的两级复制机制和空中复制( 数据广播) 技术。1 2 2 1 两级复制技术两级数据复制技术把数据库视为数据对象的集合，每个数据对象有一个主版本和多个副版本，主版本存储在被称为主节点的基节点上，副版本同时存放在基节点和移动节点，移动节点上的数据对象复本有两个版本：移动主版本来自数据对象主版本所在的主节点；暂态版本是移动节点上被暂时更新的对象值，只有在对主版本更新后才能永久化。两级复制机制假设移动数据库系统由两类节点构成：一类是基节点，它们连接在固定网络中，每个基节点都维护数据库的一个复制( 即第一级复制) ，并且是大部分数据对象的主节点；另一类是移动节点，它们有时通过无线网络与电子科技大学博士论文基节点连接，有时处于断接状态，它们也存有数据库的复制( 即第二级复制) ，可以在断接时提交暂态事务( t e n t a t i v et r a n s a c t i o n ) ，一个移动节点也可以是部分数据对象的主节点。移动节点每个复制数据对象都维护两个版本： 主版本：从对象主节点得到的最新值。 暂态版本：由本地暂态事务更新的对象值。类似的，事务也分为两类： 基事务：基事务只在对象的主节点上执行，并更新对象的主拷贝。它们运行时可以涉及多个基节点，但最多只能访问一个联机的移动节点。 暂态事务：暂态事务对本地暂态数据操作，产生新的暂态版本。以后它将产生一个基事务，以更新主拷贝值，使暂态版本永久化。暂态事务必须遵循一条范围准则：它们只能访问主节点( 基节点或发出该事务的移动节点) 的数据对象。这样就保证了当以后暂态事务转换为基事务时，所有该事务所涉及到的数据对象的主拷贝都是可以访问的。由暂态事务生成的基事务可能会执行失败，也可能产生不同的结果。因此基事务必须遵循一个可接受性准则：若它产生了与暂态事务不同的结果，如果该结果能够通过准则测试，那么就是可以接受的。可接受性准则实际放宽了对一致性的要求，因而减少了基事务失败的几率，但是仍然保证了事务执行的正确性，例如：银行帐号的剩余金额不能为负：订票座位必须靠近左走廊；实际价格不能超过暂态事务的结果如果由一个暂态事务生成的基事务失败了，系统将通知发出该事务的节点及其用户，告之该事务失败了及其失败原因，用户可根据这些信息选择重发事务还是放弃。当移动节点处于断接状态时，两级复制机制允许用户继续使用移动节点上的数据库复制。假设一个移动节点是在前一天之前断接的，因此它所拥有的基数据对象( 主节点是基节点的数据对象称为基数据对象) 的主版本都是一天前的。该节点在断接状态下继续工作，生成若干暂态事务，这些暂态事务将更新结果记录在移动节点的暂态版本中。如果该移动节点需要访问这些数据对象，第一章引言它所看见的实际上都是暂态版本，即暂态事务生成的暂态结果对移动节点是可见的。当移动节点结束断接状态，重新于基节点相连时，移动节点将：1 丢弃基数据对象的暂态版本，因为稍后将从主节点得到更新值。2 将主节点的所有数据对象的更新值传送给相连的基节点，由该基节点继续传播给其它基节点。3 ，将所有暂态事务及其输入参数传送给基节点，由该基节点按照暂态事务在移动节点上的提交顺序依次执行对应的基事务。4 从基节点接收所有主节点不是自己的数据对象的更新值。5 。接收每个暂态事务生成的基事务是否成功提交的信息。与该移动节点相连的基节点是两级复制机制中的另一级，当发现一个移动节点联机时，基节点将：1 将所有延迟未发的复制数据对象更新事务发送给移动节点。2 接收主节点是该移动节点的数据对象的更新事务序列。3 接收移动节点的暂态事务序列、它们的输入参数以及可按收准则。依次以基事务的形式重做每个暂态事务，并将成功提交的事务结果返回给移动节点。如果基事务未能通过可接受性准则，则该事务夭折，基节点将有关失败信息返回给移动节点。如果可按收性准则要求基事务的结果与暂态事务必须相同，所有后续读取该暂态事务结果的暂态事务都必须级联夭折，因此，弱一些的可接受准则能够大大提高暂态事务的通过率。4 基节点提交了一个基事务后，就将该复制更新事务传播给所有其它复制节点。5 当所有暂态事务都通过基事务重新处理之后，移动计算机的数据库复制状态与基节点达成致。综上所述，两级数据复制机制具有如下特点： 移动节点可以在断接情况下对数据库做临时修改；电子科技大学博士论文在基节点上的并发事务是可串行化的； 只有在基节点上的事务提交后，相关事务的结果才成为永久；在所有相连节点上的复制收敛于基节点系统的状态。1 2 2 2 空中复制( 数据广播) 技术因为无线网络通信的非对称性，在一个移动单元内，从服务器到移动主机的下行通信带宽一般要远大于从移动主机到服务器的上行通信带宽，而且移动主机从服务器接收数据的开销也远小于发送开销；在很多场合，即使是处于断接状态的移动主机也可以选择接收从服务器发送的下行广播信息。于是服务器可以把大多数移动主机用户频繁访问的数据( 即热点数据) 组织起来，经由m s s以周期性的广播形式提供给移动主机访问，这就是移动计算环境下的数据广播技术，这种在广播信道上做数据复制( 单向) 的方式称为“空中复制”。与传统的c l i e n t s e r v e r 联机数据请求方式相比，数据广播技术存在很多优点。首先，因为服务器广播数据的开销与接收广播的移动主机个数是无关的，这就可以以很小的代价支持大规模的移动用户同时访问被广播的热点数据，极大地提高系统的可伸缩性；其次，由于移动主机可以从广播中复制取得常用的热点数据，使其向服务器发送访问请求的频率大幅减少，节约了有限的带宽，同时减少了服务器处理每个联机移动主机的开销，进而使服务器可以同时接收更多联机m h 的访问；而且，即使在断按时，i v i l - i 也可访问到最新数据。数据广播的研究可以从不同的角度分类：按被广播数据库的覆盖范围分类：全集、子集。按广播内容的实时性分类：静态的、动态的。 按是否广播索引分类：带索引广播、无索引广播。 按广播数据流的组织形式分类：平坦调度、偏斜调度、多盘调度。按客户的查询方式分类：主动的、被动的。数据广播技术在公共信息的发布、军事应用等领域有着很好的应用前景。其中最主要的研究课题是，研究服务器如何根据m h 的访问概率分布生成最适第一章引言合m h 访问的广播程序，即数据广播的调度问题。要评价一个数据广播调度策略优劣，主要考虑两个指标 2 5 】【2 6 】： 访问时间( a c c e s st i m e ) ：从移动客户提出数据访问请求开始，到从数据广播中得到结果为止所需时间，访问时间决定了移动用户查询的响应时间。 调协时间( t u n i n gt i m e ) ：在完成一个访问请求期间，移动主机保持接听广播的总时间。调协时间决定了移动主机的电源消耗，因为如果不接听广播，移动主机可转入休眠状态。大部分移动主机依靠有限的电池供电，因此减少调协时间也是数据广播的一个重要研究课题。数据广播服务器必须根据所有m h 的需要来组织广播程序，即数据广播的调度。一种最简单的调度方法就是将所有待广播的数据项简单地并在一起，在每个广播周期里各个数据项的出现频度是相同的，这种调度称作平坦调度( f l a ts c h e d u l e ) ；反之，各个数据项出现的频度不是完全相同的，称作非平坦调度。如果在一个广播调度中，每个数据项的实例都是等距的，则将该调度称作平均调度；否则称为非平均调度【卸。在优化访问时间研究领域晟著名的成果是一种称为多盘广播( m u l t i d i s kb r o a d c a s t ) 的调度方法 2 7 】删，它是由美国b r o w n 大学的a c h a r y a 等人提出的，适合对各个数据访问概率具有较大偏斜度的环境。其基本思想是：将数据库的所有数据项按照访问概率分为k 组，即b l ，b 2 ，b k 。b l 中的数据项访问概率最高，而b k 最低。在一个广播调度中，同个组内的数据项以相同的频度广播，而不同组的广播频度是不同的。设b i 的广播频度为f i ，则f l f 2 f k ，于是，数据广播可以比喻为k 个具有不同传输率的磁盘( d i s k ) ，通过将访问概率高的数据项放在相对快速的磁盘中，就可以降低所有请求的平均访问时间，因此称之为“多盘广播”。在a e h a r y a 的方法中，需要人工确定盘数、数据项到各盘的分配以及各盘的相对频度，在实际应用中不具有可操作性，3 c 献v 2 9 1 在此基础上提出了启发式解决方案，由计算机自动确定数据项到各盘的分配以及各盘的相对频度，但仍需人工确定盘数。1 2 3 移动代理技术l4电子科技大学博士论文1 2 3 1 移动代理的定义根据文献 3 0 3 1 】 3 2 等的描述，移动代理( m o b i l e a g e n t ) 是一个代替人或其它程序执行某种任务的程序，它在复杂的网络系统中能自主地从一台主机移动到另一台主机，该程序能够选择何时、向何地移动。在移动时，该程序可以根据要求挂起其运行，然后转移到网络的其它地方重新开始或继续