（计算机应用技术专业论文）移动环境中数据广播相关技术的研究.pdf

摘要 无线通信网络、移动设备以及i n t e r n e t 的出现和普及促进了移动计算的发展。 出于移动计算不同于传统的分布式计算环境，有其鲜明的特点：移动性、断接性、 弱连接性、资源的局限性、网络通信的多样性和非对称性等，这些限制了传统的 数据库技术在移动环境下的应用，同时也产生了新的研究领域。数据广播技术由 于其良好的扩展性被广泛应用于移动计算环境。本文着重讨论和研究了数据广播 及其相关技术。 广播数据的优化调度是数据广播的核心技术。本文详细研究了推方式下的优 化调度。结合广播磁盘的概念。分析了基于多盘调度的算法，相对于传统的调度 算法，该方法具有较好的实用性。为了满足用户的个性化设计，广播系统一般设 置请求响应通道。请求响应通道有较快的响应时间，因此要充分利用；但是又不 能过载。文章研究了请求响应通道和广播通道的适应性平衡算法，它能适用系统 负载的动态变化。 为了降低查询时延和对无线带宽的访问，在移动主机端一般采用c a c h e 缓存 经常访问的数据。目前的研究一般采用失效报告的方式维护c a c h e 的一致性，该 方法在某些情况下会由于报告长度过长而造成较大的时延。本文研究了基于数据 绝对值的c a c h e 一致性策略，该方法大大降低了失效报告的长度。为了提高c a c h e 命中率，文章进一步研究了基于d 值的适应性预取策略，它可以动态适应移动主 机的电源使用情况。 为了节约移动主机的电源，需要尽量减少对无线带宽的访问。因此，在数据 广播中一般采用为广播数据建立索引的方式。针对数据库中数据访问的倾斜性， 文章提出建立基于数据访问概率的索引技术，并给出了o r d 算法，它可以根据 给定的索引树创建最优的广播序列。 关键字移动计算、数据广播、数据调度、c a c h e 一致性、数据预取、索引广播 a b s t r a c t t h ee m e r g e n c ea n dp o p u l a r i z a t i o no fw i r e l e s sc o m m u n i c a t i o n s ，m o b i l ed e v i c e a n di n t e r n e ta c c e l e r a t et h e d e v e l o p m e n t o fm o b i l e c o m p u t i n g d i f f e r e n t f r o m t r a d i t i o n a ld i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ，t h em o b i l ec o m p u t i n ge n v i r o n m e n th a s s o m ed i s t i n c tf e a t u r e s ：m o b i l i t y , d i s c o n n e c t i o n ，w e a kc o n n e c t i v i t y , r e s o u r c es c a r c i t y , d i v e r s i t ya n da s y m m e t r yo fn e t w o r kc o m m u n i c a t i o ne t e t h e s ef e a t u r e sr e s t r i c tt h e u s eo fe x i s t i n gc l a s s i c a ld a t a b a s et e c h n o l o g i e si nm o b i l ee n v i r o n m e n t s ，a n dp r o d u c e n e wr e s e a r c hf i e l d s d u et ot h eg o o de x p a n s i b i l i t y , d a t ab r o a d c a s ti su s e di nm o b i l e c o m p u t i n gw i d e l y i nt h i sp a p e r , s e v e r a lk e yt e c h n o l o g i e sa b o u td a t ab r o a d c a s ta r e i n v e s t i g a t e d d a t as c h e d u l i n gi st h em o s ti m p o r t a n ti s s u ei nd a t ab r o a d c a s t i nt h i sp a p e r , t h e p u s h b a s e d d a t a s c h e d u l i n gp o l i c i e s i s i n v e s t i g a t e d i nd e t m la n dam u l t i d i s k s c h e d u l i n ga l g o r i t h m i s a n a l y z e d t h i sa l g o r i t h mi se a s yt oa p p l yc o n t r a s t i n gt o t r a d i t i o n a ls c h e d u l i n gp o l i c i e s o n - d e m a n dc h a n n e li sa l w a y su s e di nm a n yb r o a d c a s t s y s t e m sf o ri n d i v i d u a t i o no f u s e r s ，w h i c hu s u a lh a s af a s t e rr e s p o n s et i m e ，s oi ts h o u l d b eu s e di nf u l l o nt h eo t h e rh a n di tc o u l dn o tb eo v e r l o a d e d i nt h i sp a p e r , a na d a p t i v e b a l a n c ea l g o r i t h mb e t w e e no n d e m a n dc h a n n e la n db r o a d c a s tc h a n n e li si n v e s t i g a t e d ， w h i c hc a l la d a p tt ot h ec h a n g eo f s y s t e m sl o a d i no r d e rt or e d u c eq u e r yl a t e n c y , m o b i l ed e v i c es h o u l dc a c h e ”h o t ”d a t a t o m a i n t a i nt h ec o n s i s t e n c yo fm o b i l ec a c h e ，s y s t e ma l w a y sb r o a d c a s ti n v a l i d a t er e p o r t i ft h ei n v a l i d a t er e p o r ti s l o n gt h e nt h ed e l a yw i l lb eg r e a t i no r d e rt or e d u c et h e l e n g t ho fi n v a l i d a t er e p o r t ，ac o n s i s t e n c yp o l i c y b a s e do nd a t aa b s o l u t ev a l i d i t y i n t e r v a li sp r o p o s e d ap r e f e t c hp o l i c yb a s e do nd - v a l u ei sf u t u r ei n v e s t i g a t e dt o i m p r o v e t h eh i tr a t i oo f c a c h e t h i sp o l i c yc a na d a p tt ot h ee n e r g yo f m o b i l ed e v i c e i no r d e rt os a v ee n e r g y , t h em o b i l es h o u l dr e d u c ea c c e s st ow i r e l e s sc h a n n e l s s o i n d e xb r o a d c a s t i n gi sa l w a y sa d o p t e d d u et ot h ed a t aa c c e s ss k e w , i n d e xt e c h n o l o g y b a s e do nd a t aa c c e s sp r o b a b i l i t yi sp r o p o s e d a tl a s to r da l g o r i t h mi sp r o p o s e dt o c r e a t eo p t i m a lb r o a d c a s ts e q u e n c ea c c o r d i n g t og i v e ni n d e xt r e 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 ab r o a d c a s t ，d a t as c h e d u l i n g ，c a c h ec o n s i s t e n c y d a t ap r e f e t c h ，i n d e xb r o a d c a s t i n g 撼章绪论 第一章绪论昂一早三；曩节匕 1 1 移动数据库应用背撩 - 冤线逐臻网络、移动设螽戮及i n t e m e t 戆出瑷秘磬及，给久类戆穗惑获繇方 式带来了一场革命，在任褥辩候、任何地点都麓羧入两络获取所需储怠将成为 2 1 世纪的普遍需求。随着移动计算时代的到来，移动数据库在许多成用领域体 现了其独有的优越性，因而受到了业界和学界的煎视。文献 w a n g o u 给出了几 个移动数搬库的典型应用： 公共傣憨茨毒 在移渤环境下，大量的移劝用户将通过笔记本电脑、掌上电脑、p d a 、车 载平臼等移动设备的无线通讯接口获取各种备样的公共信息，如股票行情、 天气状况和交通信息等。 实时数攥采集 驻豫除避务受为鲷，嚣蓊许多保险监务员都健溺笔记本毫藏或警上龟藏管 理有关客户和保单数据，在外出联系业务的谂中，业务员需要随时从总部 调出最新的数据资料。并随时查询某个客户的信息；完成交易麟，他又需 要将最新输入的保单信息及时反馈给总部。这种模式摆脱了时悯、地点和 场合的跟涮，克照了传统数据处理方式造成鹣延迟耪混乱，撬巍丁数据管 瑾熬效率。 位鼹棚关查询 位鼹相关查询是移动数搦应用中最具特色也最吸引人之处。设想一个旅游 者抵达一个陌生的城市，他可以通过随身携带的移动设备查询许多信息， 努最邋靛餐牙在哪里，怎转去最近豹医窿等甾。与簧统静数据黪粪谗不司 黥怒，上述查询静结暴怒与谴嚣鞠关酶，阏徉一令阅蘧在不闲豹| 逄理位置 得到的回答可能是不同的。 此外，移动数据库技术酉已合g p s 技术，可用于智能交通管理、大宗货物运 输管理和消防现场作业等。移动数据库技术还猩零售业、制造业、众融业、医 疗里墨三等锈域聂瑷了广翅豹嶷愆蔻景。移动数爨薄广泛懿瘦曩鬟袋掺翻了对移 麓数据库技术的理论研究。 硕士学位论文：穆动环境中数据广播相燕技术的研究 1 2 移动计算环境 1 2 1 移动计算环境简介 移动计算环境包括移动主机( m h ，m o b i l eh o s t ) 署【i 有线计算机网络，它的典 鍪续梅翔潮1 1 疑示 z a s 9 8 。m 鞋是一秘可移动熬诗箕设备，它氢季毳缓携式诗 算枫、移动手机、个人数字代理( p d a ，p e r s o n a ld i g i t a la s s i s t a n t ) 、手持计算机 ( h a n d h o l dp c ) 、随身计算机( p o c k e tp c ) 矛n 掌上电j a i ( p a l mp c ) 等。m h 通过无线 网络与移动支持计算机( m s b ，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 h ，m h 可戳京蜂窝闻移动，移动辩需鼗从一令m s s 虱受令m s s 静控涮交羧( h a n d o f t ) 过程。由于m h 有时会关闭电源，一个m h 可能会离开一个蜂窝而随后在某个 很远的蜂窝内重新启动，因此，蜂窝间的移动不一定是在相邻蜂窝间进行的。 m h 和m s s 之间无线连接的速度较慢( 从几十k 剿几m 不等) 且不稳定 f o r 9 4 ， 掰以无线涟接熬低赘宽和不稳定是移动诗算中数攥传输联要考虑的黧感。 图1 i 移动计算环境 移动计算可以认为是一种扩展的分存式计算，它可以进一步区分为两种结 ( 1 ) 磐户孝建瑁嚣务器( c 稻，c l l 张s e 辩e 母绩耩，数瓣管瑾凌髓集中褒藤定瀚络豹 服务器，t ，m s s 负责管理m h ，m h 通过m s s 与其它m h 联系； 瓣一章绪论 ( 2 ) 分奄式缝稳，溪煮兹谤棼援逶遂毒线或无线嚣溺终遗牙连接，数撵管理 功l 在它们之褥是分布式的，不存在一个中心的按制瑕务器，任何m h 之闽可 以通过光线网络进行联系，如几台便携式计算机利用红外线传输临时组成个 网络。 1 2 。2 移动计算舔境特点 与基于固定网络的传统分布式计算环境相比，移动计算环境具有以下特点： 移幼性。在移动计算环境中，移动主机不必有固定的位置和网络地址。 邋年巾计算平台的移动性可能导致系统访间布局的变化和资源的移动性； 频繁瓣凝接毪。无线遗按是一秘弱连接，靼低豢宽、长延遮、不稳定帮 经常性的断开( 由予通信故障或为了节约避接费用和电源) ，熙这种不 稳定性是不可预测的； 滗线连接的多样性。移动主机在不同的地点将使用不同的网络连接，如 在庭内霹基通过红努线琏套线鼹终连接，掰在室终，要使臻爱线湮窝， 菠楚有时使嗣至璧蕊撩，不同的连接袭魂为耀络漭谈、豢赛、靠毪等 的巨大变化； 网络通信的非对称蚀。由于物理通信媒介的限制，一般的无线瞬络通信 都魁非对称的，表现在固定服务器节点可以拥有强大的发送设备，丽移 动至筑豹发送裁力饕攀鸯隈，子是下 亍链貉( 1 受务器舅移动烹撬) 豹逶 信骺宽与代价和上行镰路是相差很大瓣。诧外，许多客户，服务器应餍 中的信息流动范型也会弓i 起通信的非对称性； 资源的有限性。移动设备的电源通常只能维持几个小时；此外，移动设 蘩述受到通讯带宽、存储容量、处理能力的限制。移动数据撵系统必须 充分考虑这鳖隈裁，京查澳霞往、事务鲶毽、存德管理等瀵繇萤提裹资 源的利用效率： 系统规模庞大。许多移动数据库应用环境，如公共交通信息系统，都要 求系统同时支持大爨的移动用户并发访问，这就要求移动数据摩系统必 须其有毙传统客户，瓣务器及分毒式数攒黪系统离缮多的可 枣缭蛙； 系统的安全性及可纛性较差。由于移动计算平台可以远程访问系统资 源，从而带来新的不安全因素。此外，穆动主机遗失、失窃簿现象也容 硕士学位论文：移动环境中数据广播相关技术的研究 易发生，因此移动数据库系统应该提供比普通数据库系统更强的安全机 制。 以上是移动计算环境所固有的特性，虽然移动计算的硬件基础近几年来发 展迅速，但在目前乃至不久的将来，移动主机的资源与台式计算机相比，它的 存贮量、计算能力、网络带宽还是比较有限的。 1 。3 移动计算和数据库的结合 移动计算包含硬件、软件和数据的移动，通常有两方面的含义 w e i 0 0 】，一 是指代码的移动，称为m o b i l ec o m p u t a t i o n ，如a g e n t 等；二是指计算设备的移 动，称为m o b i l ec o m p u t i n g 。这里是指第二种含义，即移动计算是指用户使用便 携式计算机、p d as h 掌上电脑等移动设备在不固定的场地接入有线或无线网络， 从计算环境中获取数据和信息进行相应的计算处理和决策的过程 f e n 9 0 1 。 图1 2 移动系统的分层结构 移动计算的出现，对计算机技术的发展有着深远的意义，移动计算是当今 许多计算机领域的研究热点，如计算机网络、分布式系统、操作系统、分布式 数据库、软件工程、应用开发等，图1 2 显示了移动系统的分层概念结构。由 于移动计算使得计算机不必有固定的位置和网络地址，摆脱了有线网络的束缚， 使得人们在任何时间、任何地点以任何方式存取信息成为现实。 随着移动设备和无线通信网络的技术发展以及硬件价格的逐步低廉，移动 计算的应用将会越来越普及，同时也提出了对移动环境下数据库应用的需求。 公司职员可以在旅途中使用便携式计算机通过无线网络或i n t e m e t 连接到公司 的数据库，处理日常事务；保险推销员可以使用p d a 向客户提供保险咨询、接 受用户订单以及处理理赔事件；邮递服务使用移动计算机辅助邮件的跟踪；紧 急响应服务使用移动计算机在灾难、医疗急救及类似情况下访问现场信息，并 第一章绪论 且输入与当时情况有关的数据。移动数据库新的应用领域还在不断地出现。 移动计算与数据库技术的结合成了一个新的研究领域，山于移动计算环境 具有其鲜明的特点 a 1 0 9 3 ，f e n 9 0 1 ，i m i 9 4 a ：移动性、断接性、低带宽和带宽的 多样性、弱连接性、可伸缩性、网络通信的非对称性、计算资源和电源的局限 性等，这些环境特点限制了许多传统数据库技术在移动环境下的运用，决定了 移动环境下数据库技术的不同解决方案 s i l 9 7 ，b a r 9 9 1 。移动数据库由于c p u 、 存贮器等计算资源的局限，又兼有嵌入式数据库的特点。 1 4 移动数据库关键技术 为了实现移动数据库必须解决移动计算环境中断接性、移动性、通讯的不 对称性等因素对数据库系统的影响。下面将分别介绍移动数据库的关键技术及 研究状况： 移动事务处理 移动事务有着与分布式事务完全不同的特点，一个移动事务不能简单地 区分为本地事务和远程事务，它是经过一组的节点。一个分布式事务是在 多个计算机和数据集上并发执行的，它的执行完全由系统来协调( 包括并发 控制、复制数据管理和原子提交等) 。而移动事务的执行有可能是串行地经 过多个m s s 和多个数据集，它依赖于节点的移动( 在一个m s s 上的一个移 动子事务可以看作是一个分布式事务) 。移动事务的执行不完全由系统来协 调，它受节点移动行为的控制，传统的a c i d 事务不再适用，需要一个新 的事务模型。 移动事务模型的关键是对移动性的处理，当移动主机跨越蜂窝进行控制 交接时，事务的执行要作特殊的处理。 数据广播 使用数据广播有三个原因，首先是无线带宽的不对称性，上行带宽远远 小于下行带宽；其次，移动主机避免了发送数据请求的能源开销：另外， 广播数据可以立刻被大量的移动主机接收到，而没有额外的开销。数据广 播使得传输带宽得到了更有效的利用，它广泛应用于服务器向移动客户机 发送信息。本文主要研究数据广播及其相关技术，因此在这里不再赘述。 数据复制缓存技术 硕士学位论文：移动环境中数据广播相关技术的研究 在分布式数据库和数据仓库中，普遍采用数据复制的方法，提高数据的 可用性和系统的性能。传统的同步复制方法由于高通信开销和操作延迟， 会引起事务的大量阻塞和死锁。 针对同步复制方法的缺点，许多研究提出了乐观复制方法f g r a y 9 6 ， a n d 9 8 ，p i t 9 9 a ，k e m m e 9 9 ，p a c 9 9 ，h o l 0 0 c 1 。乐观复制方法降低了网络通信量， 并且事务回滚所引起的代价也小，只需放弃本地的更新即可，与其它节点 无关。但是乐观复制方法的缺点是，当一个事务预提交( p r e c o m m i t ) 时，它 并不知道是否能够成功提交，要等到更新信息传播到其它节点之后才能知 道是否存在数据冲突，若有数据冲突则事务需要回滚，以维持数据的一致 性，所以在乐观复制方法中存在着延迟与一致性的矛盾。一些研究表明， 在加以适当的限制条件下，乐观复制方法在性能上优于同步复制方法 a n d 9 8 ，p i t 9 9 a ，数据库厂商都普遍采用乐观复制方法。 移动查询优化 移动数据库中，查询优化是基于环境的，优化的目标不仅包括响应时间 和吞吐量，还要综合考虑连接时间、能源参数、存贮器和移动主机的位置 等环境因素。由于移动环境参数处于不断的变化之中，并且这种变化是很 难预测的，所以移动数据库的查询优化比传统数据库更为复杂。并且由于 移动环境的资源局限，无法像大型数据库那样具有详细的统计数据和实现 复杂的优化算法。因此，适应性的优化技术是实现移动环境下查询处理的 关键。 移动计算环境中，适应性查询处理包含两方面的内容，一是查询优化要 针对环境因素的变化动态地调整策略，包括用消耗比较充足的资源来交换 相对缺乏的资源，如利用缓存来减少对带宽的要求，以及耗费电源进行计 算来减少网络传输的数据量等；二是当移动主机面临急剧的资源不足时， 如网络带宽的下降是几个数量级的时候，这时是无法通过消耗其它资源来 抵偿的，要采取降低对数据要求的方法，有选择地完成部分查询操作。这 种降低数据要求的适应性方法在o d y s s e y 系统 n o b l e 9 7 q b 采用，它通过降 低所传输多媒体数据的质量，来适应无线网络带宽的频繁变化。 安全 无线网络与固定网络相比，可靠性较低，这是由于无论从任何地点都可 以侦听无线电波，而且无线网络更容易受到干扰而出现网络故障；移动主 机由于其便携性和工作环境，带来潜在的不安全因素，如碰撞、磁场干扰、 第一章绪论 遗失、失窃等。这些都是移动数据库的安全技术问题。 目前，安全技术的主要措施是：对移动主机进行认证，防止非注册移动 主机的欺骗性接入；对无线路径加密，以防止第三方盗用：对移动用户提 供身份保护，防止用户位置泄密或被跟踪 l i 0 0 】。 人机界面 移动主机的未来发展趋势是更小、更易于携带和使用。它很可能将采用 笔输入或语音输入等方式取代难以再缩小的键盘。屏幕尺寸也会迸一步减 小。因而移动数据库的人机界面必须进行改造。如，现有的数据库查询语 言s q l 在笔输入计算机上不易使用，更理想的方法是设计一种可视化的查 询输入环境，诸如查询类型、模式选择、属性选择以及查询参数的输入等 都可以简单地用笔输入来完成。其次，屏幕尺寸地缩小也将影响查询结果 的输出形式，那种将结果数据按原样全部输出的方式显然不适合移动主机， 更好的方法可能是采用能够反映用户基本查询意图的模糊输出方式 l i 0 2 。 1 5 本文主要研究内容 本文的研究内容及章节安排如下 第二章介绍了数据广播的基本概念及其相关技术，包括数据广播的主要性 能参数；数据广播的主要研究方向，并概述了各个方向的研究情况。 第三章讨论了数据优化调度算法，分析了推方式下的优化调度策略；之后 考虑了广播通道和请求响应通道的平衡问题。 第四章研究了c a c h e 一致性问题和数据预取，针对c a c h e 一致性问题，研究 了基于数据绝对值的c a c h e 一致性策略，该方法大大降低了失效报告的长度： 为了提高c a c h e 命中率，文章进一步研究了基于d 值的适应性预取策略，它可 以动态适应移动主机的电源使用情况。 第五章研究了索引广播的问题，提出了创建基于访问概率索引树的算法 ( c f ，v f ) ，针对构造的索引树使用o r d 算法可以获得最优广播序列，从而给 出了完整的索引广播策略，具有一定的实用价值。 第六章总结了本文的工作，并对今后进一步的工作进行了展望。 硕一i ：学位论文t 移动环境中数据广捅相关技术的研究 第二章数据广播概论 数据广播是将热点数据通过共享无线信道发送给大量用户的一种传播方 式。在移动环境下，由于无线通信的低带宽和网络通信的非对称性，数据广播 是一种有效的数据访问方式。本章主要介绍数据广播及其相关技术的一些基本 概念。 2 1 引论 数据广播广泛应用于非对称的通信环境中，通信的不对称来源于以下两个 因素 s w a 9 5 ： 1 1 通信网络的物理特性，如无线网络、有线电视网络等，在这些通信中， 下行带宽远远大于上行带宽； 2 1 工作负荷的不对称，在c s 结构中，服务器要响应大量客户机的服务请 求，往往承担比客户机大得多的工作负荷。 。p a g ea b r o a d c a s ts c h e d u l e 一 i 、且且，) 。 一_ 一- ， 图2 1 无线通讯中的数据广播系统 上图给出了无线通讯中的数据广播系统 c h i 9 7 】。服务器将共享数据组织 起来，通过无线信道连续性地进行广播。用户通过侦听信道获取自己需要的数 据。与传统的c s 联机数据请求方式相比，数据广播具有以下优点： 很好的伸缩性。数据广播最大的优点是它的开销跟移动主机的数量无 关。因此它可以以很小的代价支持大量的移动主机同时访问数据； 第二章数据广播概论 节约有限带宽。移动主机从数据广播中获取数据，可以避免减少与服务 器间的上行网络通信； 适合不稳定的网络连接。在移动环境下，由于无线带宽的不稳定性，移 动主机会经常i r j e 务器断开连接。通过数据广播，即使在断开时，也允 许移动主机访问最新数据。 2 2 数据广播性能参数 在数据广播中，有两个主要的性能参数 访问时间( a c c e s st i m e ，也称为存取时间) ：指从用户提出查询请求，到 结果返回所需的时间。访问时间一般作为系统响应时间的衡量标准。 和调谐时间( t u n i n gt i m e ) ：指客户机为了获得查询结果，用于侦听信道 的时间。移动主机侦听信道需要消耗电源，因而一般将该参数作为数据 访问消耗电源的衡量标准。 根据上面的性能参数，我们将数据广播领域的主要研究内容分为以下三个 方向：1 ) 广播数据的优化调度，以降低平均访问时间；2 ) 为广播数据建立索 引结构，以降低调谐时间；3 ) 通过广播通道和请求响应( o n - d e m a n d ) 通道结 合的方式降低平均访问时间。除此之外，移动主机的c a c h e 和预取策略是对上 述三方面的补充 c h i 0 2 。 2 3 广播数据的优化调度 广播数据的优化调度可以细化为两个方面：1 ) 选择广播数据；2 ) 按一定的 顺序组织广播数据。其实，这两方面在实际的研究中不可能完全分开。 2 3 1 推方式下的数据调度方式 在推方式下，服务器将需要广播的数据组织起来，通过无线信道进行周期 性的广播。服务器根据调度策略确定广播数据的广播顺序和频率。在推方式下， 主要包括以下四种兆型的数据调度方式： 均匀广播( f l a tb r o a d c a s o 最简单的数据调度策略就是均匀广播。在该方 法中所有的数据都以相同的频率进行广播，所有数据的访问时问都是广播 硕二e 学位论文：移动环境中数据广捅相关技术的研究 周期的1 2 。由于在多数情况下，用户的数据存取是非均匀的，因此均匀广 播的总体性能不高。 基于概率的广播方式为了适应数据访问的非均衡性，提出了基于概率的 广播方式。我们为每个数据设定一个基于访问概率的函数f ；，根据函数值确 定数据的广播顺序和频率。在文献 j o h s s y p ，设置如下： ：廷 乞h , l q j 其中，q i 是数据的访问概率，n 是数据项的总数。在该方法中，某些数据项 的访问时延可能会非常大。 广播磁盘( b r o a d c a s t d i s k s ) 将数据库中的数据分配到不同的“逻辑磁盘” 中，每个盘以不同的频率和速度广播。该方法类似于传统的存贮体系结构， 因此称为广播磁盘。关于该方法在后面会详细介绍，这里不再赘述。 最优调度策略文献 h a m 9 9 ，c h i 9 7 ，v a i 9 9 ，j o h s 8 研究了最优的广播调度， 在文献 h a m 9 9 1 中给出了最小化平均访问时间的平方根规贝t ( s q u a r e - r o o t r u l e ) 。该规则包括两个条件：1 ) 每个数据项的广播实例都是等间距的；2 ) 每 个实例之问的间隔正比于数据项访问概率的平方根，反比于数据项大小的 平方根。如果广播调度满足这两个条件，则平均访问时间可以取得理论最 优值。但是这两个条件在实际应用中很难满足，因此出现了很多近似的方 法。 2 3 2 拉方式下的数据调度方式 在拉( p u l l ) 方式下，用户向服务器提交请求，服务器根据用户的请求查询所 需的数据项，并将其返回给用户。与推方式不同的是，服务器可以获得用户对 数据的访问模式，因此比较容易设计调度策略。 第二章数据广播概论 图2 2 拉方式下的调度模型 图2 2 给出了采用拉方式进行广播调度的模型 j o h 8 8 。根据用户的请求，服 务器选择某个数据项进行广播。服务器的决策过程可以用状态转换来描述。假 设某个时刻服务器处于状态 ( n i ，1 2 ，n n ) ，】，其中n l 表示等待数据项d i 的请求数目( 0 n i k ) ，j 表示服务器i f l 前正在处理的数据项。如果j = 0 ，表示 服务器处于空闲状态。在新的数据请求到达或者处理完某个请求后，服务器的 状态发生转换。假设服务器在上面的状态下，接受到一个新的数据请求r i ，则 转换到如下状态【( n l ，n i + l ，n n ) ，j l 。服务器处理完数据项d i 的请求后 转换到状态【( n l ，n 。= o ，n n ) ，j 】。服务器状态转换的关键是确定下一 个需要处理的数据项请求。有两种调度策略： 1 ) 经常访问的数据优先( m r f ，m o s tr e q u e s tf i r s t ) ：选择等待请求数最大 的数据项，即在上述状态中n 。最大的数据； 2 ) 等待最久的数据优先( l w f ，l o n g e s t w a i tf i r s t ) ：计算数据项的所有等 待时延，选择时延最大的数据。 在用户数目不大时，系统的平均访问时间跟调度策略关系不大。在数据项 访问概率相同的情况下，m r f 算法的效率高于l w f 。如果用户的数据请求符 合z i p f 分布，则l w f 算法的平均访问时问小于m r f ，即在该情况下l w f 算 法效率较高【j o h 8 8 】。需要注意的是，构造l w f 算法的代价较高。 2 4 请求响应通道 数据广播可以满足大量用户的需求，因此也造成了较大的时延。为了满足 硕士学位论文：移动环境中数据广播相关技术的研究 用户的个性化要求，一些通信系统增加了请求响应通道( o n d e m a n dc h a n n e l ) ， 它采用点对点的通信方式( 见图2 3 ) ，与广播通道是相互独立的。对于一个服务 器而言，它的请求响应通道个数是固定的，由于请求响应通道能够提供比广播 通道更快速的响应时间，因此要充分利用；另一方面，请求响应通道又不可以 过载，否则系统的响应时间将无限增大，对请求响应通道的调度要维持它的请 求率在一个给定的水平上 c h i 0 0 1 。在3 - 3 节中，我们将详细讨论请求响应通道 和广播通道的平衡问题。 m s s 广播通道 2 5 索引广播技术 请求响应通道 图2 3 请求响应通道 数据广播中，数据项的识别有两种方法，自识别和索引广播。采用自识别 方法时，用户需要一直侦听广播直到接收到所需的数据，这将会耗费大量的电 源。由于移动主机的电源非常有限，所以数据广播一般都采用索引广播，移动 主机可以只在规定的时间接收数据，其它时间处于休眠状态( d o z em o d e ) ，减少 了调谐时间。 f - n n 弓i 的构造问题类似于文件系统中的索引结构，然而在文件系统领域 并未对索引结构作细致深入的研究，这是因为： ( 1 ) 在文件系统中，访问索引的代价远小于c p u 和i o 等其它操作 第二章数据广播概论 ( 2 ) 文件系统中频繁的更新操作使得维护复杂的索引结构非常困难。 在移动环境下，由于侦听目录占去了移动事务的大部分时间，所以构造复 杂的索引是有意义的。 如果在每次数据广播中只发送一次索引，则当用户错过接收索引时问时， 只能等待下一次广播，这将会增加延迟时间。可以采取在一次数据广播中重复 发送m 次索引的方法，降低因为用户错过接收索引而带来的延迟，这称为( 1 ，1 1 1 ) 索引技术，文献 i m i 9 4 b ，i m i 9 7 对如何选取最优的m 值进行了分析。在( 1 ，m ) 索 引技术中，每次复制的索引没有必要完全相同，只需保证每次复制的索引包含 接下来要广播的内容即可。 2 6c a c h e 管理和数据预取 服务器的数据广播对某个特定的移动主机来说往往具有局限性，这主要是 由以下因素所致：移动主机提供给服务器的访问概率可能不准确；移动主机的 访问概率可能随时间变化；服务器通常会优先考虑一些重要移动主机的访问概 率分布；服务器归纳的访问概率分布反映的是移动主机的总体访问概率分布。 因此，移动主机需要将一部分数据缓存到本地c a c h e 中。根据数据广播的特 点，移动主机需要缓存那些本地访问概率较高却在广播中出现频率较低的数据， 而对本地访问概率高且在广播中出现频率也较高以及本地访问概率较低的数据 对象不予考虑，这与传统的缓存技术有很大的不同。由于这些特点，移动主机 必须采用基于代价的缓存管理策略，即考虑缓存不命中时，从数据广播中获得 一个对象的代价。 有研究表明，对传统的缓存技术，p 算法是最优的，即当缓存满时将最低访 问概率的对象替换掉。对于数据广播环境下的移动客户缓存技术，p i x 算法是 最优的，即当缓存满时将p x 值最小的对象替换掉，其中p 和x 分别是对象的 访问概率和广播频率。由于对象的访问概率无法准确预知且比较所有缓存对象 代价太高，因此在实际应用中必须对p i x 进行近似。s a c h a r y a 等人提出了l i x 算法，它能较好的应用于实际情况中。 在传统的c l i e n t s e r v e r 或三层结构中，有两种方法维护c a c h e 的一致性：1 ) 服务器发送缓存失效信息给移动主机；2 ) 移动主机通过查询服务器来验证 c a c h e 的有效性。但是，在移动环境中，由于移动主机的移动性和频繁的断开， 这些方法都不再适用。针对该情况，d b a r b a r a 和t i m i e l i n s k i 等人提出了失效 硕二l 学位论文：移动环境中数据广播相关技术的研究 报告的策略。它是目前c a c h e 一致性管理采取的主要方法。 2 7 小结 本章主要介绍了数据广播的基本概念及其相关技术，包括数据广播的主要 性能参数；数据广播的主要研究方向。针对几个主要的研究方向，各小节给出 了一个概述，后面的章节将对各个方向的研究情况进行深入讨论。 第三章数据的优化调度和通道平衡策略 第三章数据的优化调度和通道平衡策略 广播数据的优化调度是数据广播技术的重要研究方向，本章主要讨论推方 式下的数据调度策略，研究如何通过广播数据的优化调度以降低数据的平均访 问时间。之后，文章考虑了请求响应通道和广播通道的平衡问题。 3 1 推和拉的广播方式 数据广播技术根据用户的不同交互方式分为推( p u s h ) 方式和拉( p u n ) 方式。在 拉方式中，用户的请求通过上行带宽发送给服务器，然后服务器在数据广播中 发送请求的数据，该数据同时可以被其它用户所接收。 推方式适合于通信的不对称性，它的最大优点是良好的可扩展性，数据传 播的开销并不随着用户数的增加而增加。推方式的一个缺点是，当用户请求的 数据不在缓存上时，他只能等待数据的下一次广播，有可能会造成很大的延迟。 采用拉方式容易使服务器成为瓶颈，需要对用户的请求加以限制。一种方 法是系统设置一个拉通道带宽的使用上限，即拉通道带宽占总带宽的最高比例。 另外一种方法是设置一个阈值，只有当用户请求的数据项在广播中到达的延迟 时间大于该阈值时，才允许发送拉请求。 文献【a c h 9 7 】研究了在广播磁盘中采用推和拉相结合的方法，把数据广播分 为两个通道，分别用于推和拉的数据广播，总的带宽在两者之问共享，用户根 据广播数据的延迟来决定是等待广播的数据还是向服务器发送请求。 本章接下来分推和拉两种方式讨论如何优化数据的广播调度策略。 3 2 推方式下的广播调度 本小节主要研究在推方式下如何通过广播数据的优化调度以降低平均访问 时间。 3 2 1 理论最优值 首先，我们通过理论分析，给出平均访问时间的理论最优值。 i i i 士学位g , 3 c , 移动环境中数据广播相关技术的研究 假设广播数据库由n 个数据项组成，即d l , d 2 ，d n ，且所有数据项的长度 相同。对任意一个数据访问请求，它访问d i 的概率为q i 。设广播一个数据项的 时间为单位时间1 ，数据广播以周期方式进行，且一个广播周期由l 个时间单 位组成，即广播周期为l 。 一个数据项在广播周期中的一次出现称为它的一个实例。在一个广播周期 中，可以包含一个数据项的多个实例，数据项d i 的实例个数称为d i 的频率，记 为k i 。 一个数据项两个实例之间的间隔是指从开始广播第j 个实例到开始广播第 j + 1 个实例所花费的时间。t ，表示数据项d 。的第r 个实例与下一个实例间的间 隔。注意k i t = i t ，= l ，该等式可以从下图中得出【j o h 8 8 】。 一1 2 一1k 1 1 il l i 5j i f 图3 1 广播周期 数据项的平均访问时间是指用户在请求数据项d i 时的平均等待时间，记为 s i 。假设该请求均匀分布落在广播周期中的任意时刻，则 数据广播的平均访问时间为 耻善等+ 孚， n1n l s = q ，s 。= 寺g j ( f ) 2 i = 1山l = l卢i 等式( 1 ) 可以用来计算任何广播周期的平均访问时间。这里，我们引入一个 定理( i i l ! 明参见【a m m 8 7 】) 。 定理3 1 广播调度取得最小平均访问时间的必要条件是每个数据项的实例 都是等间距的。 由此得到t r = l k i ，将该式代入( 1 ) 中得到 第三章数据的优化涮度和通道甲衡策略 s 生争旦 2 智女， 当访问概率q i 确定时，平均访问时间完全取决于k 的分布。当k 。取以下值 时，式( 2 ) 取得最小值。 此时，s 要( 兰厄) ：。 二j = l 鲁：，旦 i j - 1 n 七j q ” 从上面的证明中，我们可以得出下面的定理。 定理3 2 给定每个数据项d i 的访问概率q i ，当每个数据项的实例都是等间 距的，且d i 的频率k i 正比于万时，平均访问时间s 取最优值( 最小值) l i 9 9 。 3 2 2 广播数据的优化调度算法 根据上面的理论推导，我们可以给出如下的优化调度算法： 假设广播周期为l 个时间单位。数据项按照访问概率的降序排列，即q l q 2 q n ，各个时间槽的编号为0 ，1 ，l 一1 。 1 1 为各个数据项选择整数频率k l ，使得n i - l k i = l ，并且对所有的i ，j 使 得k i k j 的值尽量接近q i q j ； 2 1 对所有的数据项选择各个实例之间的间隔值t ，( 整数) ，使得 ，1 t r - l ，并且使得t ，的值尽量接近l k i ； 3 ) 为数据项1 到n - 1 分配时间槽。分配时参照2 ) 中计算得到的间隔。在 这个过程中，由于该方法的近似性，很可能会出现冲突，即在为数据项 j 分配时间槽时，有可能该时间槽已被数据项i ( f k 。通过将谤闷概率高的数据颈敞在相对 快速的磁盘中，就可以降低所有请求的平均访问时间。 数据顼的访坚 淼b 盘孵均燃螽| 莠盘的大；! 盎- 如- 产广播黻 可糕节鬻r 冒嗣袭广一1 个蠡ll 频率lll 豳3 3 多盘调度流程图 多盘调度算法构造一个广播调度的过程如下( 如图3 3 所示) ： 1 ) 将菠鸯数据矮羧谤融藏率递减次痔赘 臻，势莰次分裁隽k 个纛，定义 癜b 的容量c i 为数獭项的个数，平均访黼概率p i 为b 内所霄数据项访 问概率的平均值，即p 。= _ 1 吼； o ，e 且 2 确定各鑫豹撞对广臻貘拳羲，曩为正整数，曼f i f 2 f k ，净1 , 2 。哭； 3 ) 产生广播调度： i 。将每个盘分割为若干块；首先，求得所有盘的广播频率的最小 公倍数l c m ：然后，将每个盘b i 分割为n u mc h u n k s ( i ) 一l c m f i 令摇强大小豹决，记为c ，j = l + + h u mc h u n k s ( i ) e 鲤象不 麓整分，刚强不满的块审填充空阏数据； i i 按如下程序交错广播各盘中的块，生成广播调度： f o r ( i = o ；i 0 时，k 个具有最高请求率的数据项被安排在广播通道，其余的通过请求响应通道进行 传输。 k = m i n ji i x - 沁) 其中，。e 。e 。是 1 ，1