（计算机软件与理论专业论文）无线数据广播环境下的索引技术研究.pdf

摘要 随着技术和需求的发展，计算方式在不断地变化，从6 0 年代开始的集中式 计算，到今天广泛采用的分布式计算，n - 十一世纪的移动计算，新的计算方式， 带来了新的研究课题和挑战。 在移动计算环境中为了支持大量m u ( m o b i l e u n i t ，移动终端) 并发访问服 务器上的数据，人们提出了服务器向空中广播数据，m u 从空中获取数据的新的 数据发送模式，即数据广播。在数据广播中所谓调谐时间就是指在完成一个访问 请求期间，m u 保持激活状态的总时间。而当前m u 主要靠电池供电，为了减小m u 的调谐时间而使用索引技术，数据广播中的索引又称为空中索引。空中索引的作 用就是预测删所需要的数据的到达时间，使得m u 在其需要的数据到达时才进入 激活状态来接收数据，减少m u 保持激活状态的时间，以达到节能的目的。 在数据广播环境下位图索引有着一些特有的优势：与数据广播的调度算法无 关；符合数据广播环境的只读特点；查询速度快。而当前很多索引方法都对数据 广播的调度算法提出了要求和限制，因此本文提出了使用位图索引作为数据广播 中的空中索引。 首先提出了最简单的位图分布方式和均匀的位图分布方式。所谓最简单的位 图分布方式是指在数据广播周期的最开始处广播一个完整的位图索引；为了减小 等待索引的信息，可以在一个广播周期中均匀的插入多个完整的位图索引，这样 m u 错过了一个索引时就不必等待整个广播周期，即均匀的位图分布方式。 其次，为了进一步提高性能，针对数据访问概率具有偏斜性的特点，即多数 m u 的数据访问请求集中在相对少数的数据项上，提出了使用b r o a d c a s td i s k s 方 法来分布位图索引的方式，这种方式根据数据项的访问概率来分布其位图索引， 对于访问概率较高的数据项，关于它的位图索引广播的次数也较多，这样能使得 多数m u 不会错过它所需要的位图索引；而对于访问概率较低的数据项，关于 它的位图以较低的次数广播，使得整个广播周期不会变得过大。实验表明，使用 b r o a d c a s td i s k s 方法来分布位图索引的方式与使用b 树索引相比有明显的性能提 高。 关键词：移动计算，数据广播，空中索引，位图索引，b r o a d c a s t d i s k s a b s t r a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g i e sa n dd e m a n d s t h ec o m p u t i n gm o d e sa r ec h a n g i n g g r a d u a l l y c o n c e n t r a t e dc o m p u t i n gi nt h e1 9 6 0 sh a sc h a n g e di n t ot o d a y sw i d e l ya d o p t e d d i s t r i b u t e dc o m p u t i n g a n dm o b i l ec o m p u t i n ge m e r g e di nt h e1 9 9 0 s t h ed e v e l o p m e n to f m o b i l ec o m p u t i n gw i l le n a b l et h eu s e r st oa c c e s sd a t aa n y w h e r ea n da n y t i m e d a t ab r o a d c a s ti su s e dt os a t i s f yt h el a r g en u m b e ro f r e q u e s t sf r o mt h em o b i l eu n i t s ( m u ) s i m u l t a n e o u s l y t h et u n i n gt i m ei st h et i m es p e n tb yam ul i s t e n i n gt ot h ec h a n n e l ，t h i sw i l l d e t e r m i n et h ep o w e rc o n s u m e db ym ut or e t r i e v et h er e q u i r e dd a t a n o w a d a y sm o s tm u sa r e p o w e r e db yb a r e r y ，s oa i ri n d e xi sn e c e s s a r yf o rm u st op r e d i c tt h ea r r i v a lt i m eo ft h e i r d e s i r e dd a t a ，m u sc a ns t a yi np o w e rs a v i n gm o d ea n dt u n ei n t ot h eb r o a d c a s tc h a n n e lo n l y w h e nt h ed a t ao f i n t e r e s tt ot h e ma i r i v e b i t m a pi n d e xh a ss o m es p e c i a la d v a n t a g e si nd a t ab r o a d e a s t ：b i t m a pi n d e xh a sn o t h i n g t od ow i t ht h ea l g o r i t h mo fd a t ab r o a d c a s t ；i t sa d a p t e dt ot h er e a d - o n l yp r o p e r t yo fd a t a b r o a d c a s te n v i r o n m e n t ；a n dt h ep r o c e s so f r e q u e s ti sr a p i d t h i sd i s s e r t a t i o nf i r s t l yu s e sb i t m a pi n d e xa sa i ri n d e xi n as i m p l e s tw a y , t h a ti s ， b r o a d c a s tb i t m a pi n d e xa tt h eb e g i n n i n go ft h eb r o a d c a s tc y c l e i no r d e rt od e c r e a s et h et i m e o f w a i t i n gf o ri n d e x , t h ed u p l i c a t i o n so f t h eb i t m a pi n d e xm i n s e r t e di n t ot h eb r o a d c a s tc y c l e u n i f o r m l y , t oa c h i e v eb e t t e rp e r f o r m a n c ew i t hs k e w e dq u e r i e s ，an e wm e t h o do f u s i n gb i t m a pi n d e x d i s t r i b u t e dw i t hb r o a d c a s td i s k si si n t r o d u c e d t h eb i t m a pi n d e xo fh o td a t aa r eb r o a d c a s t e d w i t hah i g hf r e q u e n c ya n dt h eb i t m a pi n d e xo f c o l dd a t am b r o a d c a s t e dw i t hal o wf r e q u e n c y , s om o s t1 v f i i j sw i l ln o tm i s st h ei n d e xo f t h e i rr e q u i r e dd a t aa n dt h eb r o a d c a s tc y c l ew i l ln o tb e t o ol o n gb e c a u s eo ft h ed u p l i c a t i o no fi n d e x a n dt h et i m eo fp r o b i n gt h ea r r i v i n gt i m eo f n e e d e dd a t ai t e m si sr e d u c e d i t sa l s of l e x i b l et og e te i t h e rag o o dt u n i n gt i m eo rag o o da c c e s s t i m e i t sp r o v e db ye x p e r i m e n tt h a tt h i sm e t h o dh a sa no b v i o u si m p r o v e m e n tc o m p a r e dt ot h e m e t h o du s i n gbt r e e k e yw 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 ，a i ri n d e x ，b i t m a pi n d e x ，b r o a d c a s t d i s k s h 1 1 研究背景 第一章引言 随着i n t e m e t 的快速发展和普及，当今社会已经进入信息时代，信息和数据 处理处于越来越重要的地位。而蜂窝通信、无线l a n 和卫星通信等无线通信技 术的快速发展，使用户在任何地点任何时刻访问信息成为可能。 可以预见，未来的绝大部分移动计算机都将配备以无线网络为主的移动联网 设备，以支持移动用户访问网络中数据的需要。这将是一种更加灵活、复杂的分 布计算环境，人们称之为移动计算( m o b i l ec o m p u t i n g ) 【i m i e l 9 9 4 b 1 。 图1 一l 所示是一个典型的支持移动计算的系统模型 i m i e l 9 9 4 b 。它包括3 类 计算设备： 具有无线通信接口，支持移动计算的固定主机( m s s ) 没有无线通信接口的固定主机( f h ) 移动计算设备( m u ) 所有主机通过固定网络连接在一起，固定网络中每个m s s 负责建立一个无 线网络单元( 如图中所示的无线广播单元或无线局域网单元) ，单元内的m u 与m s s 之间通过无线网络连接。相对于可靠性不高的无线网络单元，我们将固 定网络部分称为可信部分。这些无线网络单元的覆盖范围取决于它们采用的无线 通信技术，例如无线l a n 单元只能覆盖一幢大楼，而采用卫星通信的无线网络 单元只需几个即可覆盖整个地球 d h a w l 9 9 7 。总之，在图l - 1 所示的移动计算环 境中，m u 可以从任何一个无线网络单元经由m s s 联接到固定网络中，从而实 现了自由的移动性。 注 图1 _ 1一个典型的移动计算系统模型 分 1 1 1 移动计算系统的组成 我们从4 个方面介绍无线移动计算系统的组成。 1 无线通信网络 m u 通过无线通信网络和m s s 连接，目前已经投入使用的移动通信与联网 技术主要有以下几种 d h a l 9 9 9 1 ： ( 1 ) 蜂窝通信系统 蜂窝通信网分模拟蜂窝通信系统和数字蜂窝通信系统两种，模拟蜂窝通信系 统是早期的移动通话系统，现在应用的基本上都是数字蜂窝通信系统。数字蜂窝 通信系统被称为第二代蜂窝系统，它采用了数字编码技术。目前比较有代表性的 数字蜂窝系统包括g s m 、c d m a 。2 5 g 和3 g 通信系统正在成为新的通信系统， 第四代移动通信系统也正在制订中。模拟蜂窝系统和数字蜂窝系统都能够通过设 立多个小区( 类似于蜂窝) 覆盖较大的地理范围( 如整个城市) ，因此以它们为 基础建立的无线网络也称作无线广域网( w w a n ) 。 ( 2 ) 无线局域网( w l a n ) 与无线网络相比，它的数据传输率要高两个数量级，新的无线l a n 产品传 输率已达到11 m b s ，使用被称为i s m ( i n d u s t r i a l ，s c i e n t i f i c ，a n dm e d i c a l ) 频带进 行通信( i s m 频带是无须获得许可就可以自由使用的频率) 。无线局域网的缺点 是作用范围较小，一般只能局限于一幢建筑物内使用。 ( 3 ) 8 0 2 1 1 家族谱 i e e e8 0 2 1 1 是第一代无线局域网标准之一。该标准定义了物理层和媒体访 问控n ( m a c ) 协议的规范，允许无线局域网及无线设备制造商在一定范围内建立 互操作网络设备。由于8 0 2 1l 在速率和传输距离上都不能满足人们的需要，因 此，i e e e 小组又相继推出了8 0 2 b 和8 0 2 1l a 两个新标准。8 0 2 1 l g 是为解决 2 蓝牙产品和无线局域n ( 8 0 2 1 l b ) 两种技术之间的干扰问题而出现的。8 0 2 1 1 9 其 实是一种混合标准，它既能适应传统的8 0 2 1 1 b 标准，在2 4 g h z 频率下提供每 秒11 m b i t s 数据传输率，也符合8 0 2 1l a 标准在5 g h z 频率下提供5 6 m b i v s 数据 传输率。 ( 4 ) 蓝牙( b l u e t o o t h ) 蓝牙( i e e e8 0 2 1 5 ) 是一项最新标准，对于8 0 2 1 1 来说，它的出现不是为 了竞争而是相互补充。蓝牙比8 0 2 1 l 更具移动性，比如，8 0 2 1 l 限制在办公室 和校园内，蓝牙能把一个设备连接到l a n 和w a n ，甚至支持全球漫游。此外， 蓝牙成本低、体积小，可用于更多的设备。但是，蓝牙主要是点对点的短距离无 线发送技术，本质上要么是r f 要么是红外线，传输范围约为1 0 米左右，无线 数据传输速率达到7 2 0 b p s 到1 m b p s 。“蓝牙”技术包含一套完整的加密和认证 机制，因此具有很强的安全性。 ( 5 ) 卫星通信网 移动卫星服务允许全球覆盖。在这些系统中，卫星起着移动通信基站的作用， 其最大特点是能够为全球每一个角落的用户提供通信服务，是陆地移动通信系统 的扩展和延伸，在边远地区、海岛、受灾区等通信方面更具有独特的优越性。卫 星通信系统按所用轨道可分为：静止轨道( g e o ) 、中轨道( m e 0 ) 和低轨道 ( l e o ) 三种。其中，低轨道卫星系统将允许用户手机蛊接与卫星通信，因此携 带和使用起来更加方便。 ( 6 ) 红外线技术 红外线局域网采用小于1um 波长的红外线作为传输媒体，有较强的方向性， 受太阳光的干扰大。红外线支持1 2 m b s 数据速率，适于近距离通信。 2 移动计算设备 所有可自由移动的计算设备，大到便携电脑、车载p c ，小到掌上电脑、p d a 、 e b o o k 、移动电话、b p 机，都可称为移动计算设备。 3 嵌入式操作系统( e m b e d d e do p e r a t i n gs y s t e m ，e o s ) 对于移动计算应用而言，在移动设备上运行的操作系统通常被称为嵌入式操 作系统，它就是整个移动计算应用的核心。嵌入式操作系统是一种实时的、支持 移动计算应用的操作系统软件，通常包括与硬件相关的底层驱动软件、系统内核、 设备驱动接口、通信协议、图形界面和标准化浏览器等。 目前嵌入式操作系统主要有p a l m 公司的p a l mo s 、m i c r o s o f t 公司的w i n d o w s c e 以及嵌入式l i n u x 。 4 无线应用服务器( w i r e l e s s a p p l i c a t i o ns e r v e r ，w a s ) 无线应用服务器是一个可以使客户通过无线设备访问e b u s i n e s s 应用、企 业数据和i n t e r n e t 的企业级应用服务器。支持多种有线和无线连接协议，包括 w a p 、p a l m 、c p d p 等无线网络，提供完整的框架体系帮助用户快速开发基于各 种不同无线设备的应用程序，支持各种不同设备的特性( 例如：浏览器支持的内 容格式等) ，并且提供定义和访问个性化内容的能力。目前的产品有b e a w e b l o g i es e r v e r ，o r a c l e 9 i a sw i r e l e s s ，s y b a s ei a n y w h e r es o l u t i o n s 等。 5 移动数据库 从数据管理的角度看，所谓移动计算实际上就是如何向分布在不同位置的移 动用户提供优质的信息服务( 信息的存储、查询、计算等) ，也就是设计出的数 据库系统能够安全、快速、有效地向各种用户终端设备提供数据服务。 目前有s y b a s e 的移动及嵌入计算解决方案s q la n y w h e r es t u d i o ，o r a c l e 移 动数据库旗舰产品o r a c l e9 il i t e ，i b m 的d b 2e v e r y w h e r e 以及微软基于w i n d o w s c e 的嵌入式s q ls e r v e r 产品。 6 应用软件 然而移动计算方面的应用软件有所欠缺，是阻碍移动计算发展的障碍。如何 帮助用户开发出适合他们需求的移动应用。这也是今后各移动计算产品提供商与 其合作伙伴要努力的方向。将来这些移动计算厂商的竞争将主要集中在应用软件 方面，谁的经验丰富，哪个平台上的应用软件多，谁就可能获胜。 1 1 2 移动计算特点 与基于固定网络的传统分布计算环境相比，移动计算环境具有以下一些主要 特点 i m i e l 9 9 4 b ，b u r b l 9 9 9 ，s a t y l 9 9 6 b 】； 计算机和用户的移动性 在移动计算环境中，一台移动计算机不仅可以在不同的地方联通网络，而且 在移动的同时也可以保持网络连接。这种计算平台的移动性可能导致系统访问布 局的变化和资源的移动性。而且，个人的移动性( 即在不同地方使用当地的计算 设备) 也随着个人通信网p c n 与网络计算机n c 的提出而日益突出。 断接性 移动计算中的断接( d i s c o n n e c t ) 和传统分布式计算中的连接失败( f a i l u r e ) 是有本质区别的，移动计算机的主动断接不是一种故障，而是一种工作方式，可 以认为是有计划的连接失败，是可以预见的。移动计算机在移动过程中，由于使 用方式、电源、无线通信费用、网络条件等因素的限制，一般不采用保持持续联 网的工作方式，而是间歇性入网、断接。 大规模并发用户 许多移动应用环境，如公共交通信息系统，都要求系统同时支持大量的移动 4 用户并发访问，这就要求移动计算系统必须具有比传统客户朋艮务器及分布式系 统高得多的可伸缩性。 新的信息传输媒介 无线通信提供了一种新的发送数据到大量用户的有效方法。和固定网络不同 的是，无线广播时不管接收的客户数有多少，m s s 的广播代价并不改变。 无线连接的低带宽 和固定网络相比，无线连接的带宽要小很多，无限w a n 的带宽只有几十 k b p s ，目前最新的无线l a n 产品带宽可达到1 1 m b p s ，但是和爆炸式增长的数 据相比，这些带宽是不够的，对于需要传输多媒体数据的应用场合而言更是如此。 网络通信的非对称性 由于物理通信媒介的限制，一般的无线网络通信都是非对称的，表现在固定 服务器节点可以拥有强大的发送设备，而移动计算机的发送能力非常有限，于是 下行链路( 服务器到移动计算机) 的通信带宽与代价和上行链路( 移动计算机到 服务器) 是相差很大的。此外，许多客户朋受务器应用中的信息流动范型也会引 起通信的非对称性。 可靠性 无线网络与固定网络相比，可靠性较低，更容易受到干扰而出现网络故障； 此外，移动计算机由于其便携性和工作环境，也带来潜在的不安全因素，包括失 窃、遗失、损坏，等等。如果存放有重要机密数据的移动计算机失窃，将可能导 致严重的后果。 1 1 3 研究热点和现状 按照无线网络的组网方式，可以分两类：一为具有中心节点做服务器的c s 方式，如蜂窝通信网络；二为无固定基础设施、自组织的a dh o e 方式。无线数 据广播和有线数据广播是有很大差别的。在c s 结构的无线网络中，服务器向空 中发送信号，接收者个数与发送代价基本无关；有线数据广播通过有线网络向每 个接收者发送数据，传输代价与接收者的个数有关，这一关键差别使得两者的调 度算法截然不同。a dh o e 网络更是在组网方式上和有线网络有根本区别。 从数据管理的角度看，所谓移动计算实际上就是如何向分布在不同位置的移 动用户提供优质的信息服务( 信息的存储、查询、计算等) ，也就是设计出的数 据库系统能够安全、快速、有效地向各种用户终端设备提供数据服务。 有关数据广播的研究主要集中的以下几个方向： 数据广播技术 利用无线网络通信不对称的特点，为支持大规模的移动用户对热点数据的并 发访问，研究将熟点数据组织在共享无线信道上的广播技术，通过对空中数据及 其索引的合理组织，使移动用户可以以最小的代价有选择地接收数据，从而提高 查询效率及移动数据库的可伸缩性。 对于c s 结构的无线网络，数据广播的核心研究课题是：如何组织数据广播 信道中的数据，使之适合于移动计算机访问。主要的研究课题是各种数据广播的 调度算法。传统上，衡量这些数据广播调度算法优劣的指标主要有两个，它们是： 1 访问时间( a t ：a c c e s st i m e ) ，指从i v l u 提出数据访问请求开始，到m u 从数据广播频道中得到结果为止所需的时间。访问时间决定了m u 查询的响 应时间： 2 调谐时间( t t ：t u n i n gt i m e ) ，指在完成一个访问请求期间，m u 保持接听 广播的总时间。在不接听广播的时间里，m u 可以转入休眠模式，此时消耗 的电源相对于激活状态可以忽略不计。 c s 结构无线网络中的数据广播调度可以分为两方面： 一静态数据广播调度，是指m u 具有固定访问模式条件下的数据广播调度， 即每个广播数据项被访问的概率是固定的。m u 只有在下行广播信道中 选择接收自己需要的数据。静态数据广播是一种纯的“推( p u s h ) ”方式的 数据发送方式。 _ o n d e m a n d 数据广播调度，m u 首先提出数据访问请求，服务器考察等 待响应的所有请求，选择下一个( 批) 广播的内容( 数据项) 。m u 先 通过上行信道发送查询请求，然后从下行广播信道中选择接收自己需要 的数据。 早期的研究主要集中在静态数据广播调度，目前的研究越来越多地讨论 o i l d e m a n d 方式的数据广播调度。广播数据的索引、移动客户端的c a c h e 策略是 和调度算法关联较密切的两个研究内容。 空中索引技术 减少访问时间是数据广播调度算法最主要的目标。而减小调谐时间则是使用 空中索引的主要目标。所谓调谐时间就是指在完成一个访问请求期间，移动终端 保持激活状态的总时间。移动终端允许在激活模式( a c t i v e 模式) 和休眠模式 ( d o z e 模式) 间切换，在休眠模式下移动终端耗电量远小于在激活模式下的耗电 量。调谐时间是耗电量的一个主要衡量方式，目前绝大多数移动终端都是使用电 池供电，而且据估计在未来的几十年里电池的性能只会有2 0 的提高，因此减小 调谐时间是数据广播中的一个重要课题。 6 在理论上，如果客户预先对数据广播的调度组织结构完全了解，知道它所需 的数据项将在什么时候广播，则该客户在访问数据广播时的调谐时间总为1 ，即 只需要直接将所要求的数据项从广播信道中接收下来即可。但是，由于客户的移 动性、服务器上数据库的变化导致数据广播结构的变化、可能存在多种不同的数 据广播服务等因素，在实际应用环境中，客户往往无法预先获知有关数据广播结 构的完全信息。在极端情况下，客户必须不断地监听数据广播的内容，直到接收 到所需数据项为止，这时的调谐时间等于访问时间。显然，这种持续不断监听的 方式将极大地浪费客户有限的电源。 在数据广播中为了减小调谐时间而使用索引技术，这里的索引又称为空中索 引。索引的作用就是预测客户所需要的数据的到达时间，减少移动终端保持激活 状态的时间，以达到节能的目的。如果没有索引调谐时间就等于访问时间，因为 在整个数据广播周期内移动终端对广播的每个数据项都要进行判断以确定是否 是它所需要的数据。但是加入了索引无疑又会增加访问时间，这是因为加入索引 就相当于在要广播的数据之外额外加入了其他的数据，整个广播周期变长了。因 此访问时间和调谐时间是相互平衡的，需要在它们之间寻找一个平衡点。 1 2 论文工作 节能是无线数据广播中考虑的一个重要方面，为达到这个目的，很多基于磁 盘系统的索引技术被应用到数据广播中如b 树等。论文的主要内容是在研究数 据广播环境的特点后提出使用位图索引作为数据广播中的空中索引，并讨论了不 同分布模式下的性能。之所以使用位图索引作为数据广播中的空中索引，是在考 虑无线数据广播环境的特点和位图索引的特点而提出的，主要有如下几点： 1 与数据广播的算法无关。多数空中索引方法都对数据广播提出了额外要求， 要求平坦调度( 即一个广播周期中每个数据项只广播一次) ，或者要求对数 据项排序等。而位图索引则对数据广播采用何种算法没有要求，因为位图 索引本身就是将数据项在广播周期中的位置以位向量的形式表现出来，要 求数据项以什么方式排列对位图索引没有意义a 2 符合数据广播环境的特点。数据广播环境下的一个显著特点就是这是个只 读环境，数据通过服务器向客户广播，客户只是接收需要的数据，因此位 图索引的修改代价可以忽略。 3 查询速度快。对于客户的查询，如果得到了位图索引，那么就能够得知所 7 有符合条件的数据项的位置，客户只要依次等待所有数据项的到来即可， 无需再次查询索引。如果在数据项的多个属性上建有位图索引，那么就能 够方便快速的进行范围查询和部分匹配查询，因为查询可以转换为简单的 位向量的布尔操作如a n d ，o r ，x o r ，n o t 等。 论文主要内容为以下两部分： 1 基于无线数据广播环境和位图索引的特点，首先提出了最简单的位图分布方式和 均匀的位图分布方式。所谓最简单的分布方式是指在数据广播周期的最开始处 广播一个完整的位图索引，这种分布模式最简单，但是等待索引的时间可 能会很长，因为一旦m u 错过广播周期开始处的索引，它必须等待整个广 播周期完毕后才能获得索引信息。为了减小等待索引的信息，可以在一个 广播周期中均匀的插入m 个完整的位图索引，这样m u 错过了一个索引时 就不必等待整个广播周期。但是这样也有不利之处，即在一个广播周期中 多次广播索引，会使得整个广播周期变得更长，进而使得访问时间变长， 而且每次都广播整个位图索引并不必要，因为可能有些数据项并不是所有 m u 都需要，即它是“冷门”数据，多次广播关于它的索引没有太多意义。 2 以上两种分布方式的不足的地方都是没有考虑数据访问概率具有偏斜性的 情况，即多数m u 的数据访问请求集中在相对少数的数据项上( 如8 0 2 0 现 象，8 0 的访问集中在2 0 的数据上) 。这也是当前大多数方法都没有考虑 的地方，因此对于某些“冷门”数据的位图索引的多次广播对提高整体性能 并没有太多帮助，反而会增加广播周期的长度，增加系统数据广播的开销。 而对于“热门”数据如果索引广播的此数不够多的话，那么大多数客户都会 错过索引而造成等待索引时间过长，进而影响整个系统的性能。因此可以给 位图索引的每个位向量赋予一个“访问概率”的概念，即该位向量的“访问 概率”为其代表的所有数据项的平均访问概率，这样在一个广播周期中不是 以整个位图索引为单位来广播索引，而是以位向量为单位来广播索引。对于 “访问概率”较高的位向量可以在一个周期中以较高的频率广播，而对于“访 问概率”较低的位向量以较低的频率来广播。这样既能减小多数客户等待索 引的时间，又能不使得一个广播周期变得很庞大，以达到访问时间与调谐时 间之间较好的平衡。论文提出了使用b r o a d c a s td i s k s 方法来分布位图索引的 方式，根据数据项访问概率，使用位图作为数据广播的索引，结合了位图能 高效回答复杂查询的优点和数据广播的只读环境的特点，使移动终端在复杂 查询时能快速得到所需索引信息，减少了移动终端等待数据时保持激活状态 的时间，达到节能的目的。并且在访问时间和调谐时间的平衡选择有很大的 灵活性。 1 3 论文组织方式 论文共分五章，后续章节按如下方式组织： 第一章是引言。 第二章对数据广播技术和现有的空中索引方法做一介绍。介绍了移动计算环 境下的数据广播技术的研究现状以及一些经典算法和现有的主要的空中索引技 术，讨论了空中索引要解决的问题以及现有方法的一些不足之处。 第三章提出了使用位图索引作为空中索引，提出了使用最简单的分布方式和 均匀分布的方式这两种位图索引的分布模式。 第四章在第三章提出的两种模式的基础上提出了根据数据项的访问概率使 用b r o a d c a s td i s k s 方法来分布位图索引，并给出了性能分析和实验分析。 第五章总结了全文的研究成果，并指出可能的进一步研究工作。 第二章数据广播及空中索引简介 随着无线网络，卫星等无线通信能力的提高，有越来越多基于数据发布的应 用，这些应用的显著特征就是向大量的客户发布数据。在采用固定网络的 c l i e n t s e r v e r 结构中，c l i e n t 在需要从s e r v e r 得到数据时，发出一个请求，s e r v e r 响应后把数据发送给c l i e n t 。与固定网络相比较，无线通信具有带宽小、通信质 量差的特点，而且移动计算设备( m o b i l eu n i t ，以下简称m u ，或又称为移动客 户) 往往只有很小的存储能力。为了支持大量m u 并发访问服务器上的数据， 人们提出了服务器向空中广播数据，m u 从空中获取数据的新的数据发送模式， 即数据广播。 数据广播技术在公共信息的发布( 股市、汇市、交通) 、军事应用( 如美 军g b s 系统) 等领域有着很好的应用前景。数据广播作为数据发布的主要技术 方式，在应用中扮演着熏要角色，因为数据广播在无线数据应用中有着特有的优 势：第一，数据广播是一种一对多的方式，数据通过很少数量的数据服务器广播 到很大数量的客户端；第二，很多已有的无线通信技术可以用于数据广播，如支 持移动用户的无线通信系统可以通过加入数据广播模块而实现数据广播的功能。 广播方式有三种：一种称之为“拉”，一种称之为“推”，第三种称之为混合式， 即“拉”与“推”的结合。 数据广播中最主要的课题是研究服务器如何根据m u 的访问概率分布生成 最适合m u 访问的广播程序，即数据广播的调度问题。如图2 1 所示是一种最简 单的调度方法，它将所有待广播的数据项简单地并在一起，在每个广播周期里各 个数据项的出现频率是相同的。我们把这种调度称作平坦调度( f l a ts c h e d u l e ) 。 如果在一个广播调度中，各个数据项出现的频率不是完全相同的，则将这种调度 称作非平坦调度。如果在一个广播调度中，每个数据项的实例都是等距的，则将 该调度称作平均调度；否则称为非平均调度 a c h a l 9 9 5 b ，李1 9 9 8 】。 圈2 - 1最简单的调度方法：平坦调度 1 0 看图2 - 2 所示的例子 a c h a l 9 9 5 b ，有( a ) 、 ( b ) 、( c ) 三个调度，( a ) 是平坦调度，( b ) 和( c ) 是非平坦调度，( c ) 是平均调度，( b ) 是非平均调 度。通过表2 - 1 列出的一组数据的比较，可以观察到，如果对每个数据项的访问 频率是相同的，那么平坦调度( a ) 是最佳的；如果对各个数据项的访问频率差 异较大，那么非平坦调度的性能会更优；平均调度( c ) 总是比非平均调度( b ) 好。 访问概率 平均访问时间( 以一个广播数据项为单位) ab c 调度( a )调度( b ) 调度( c ) 0 3 3 30 3 3 30 3 3 31 5 01 7 5 1 6 7 0 5 00 2 50 2 51 5 01 6 31 5 0 0 7 50 1 2 50 1 2 51 5 0 1 4 41 2 5 0 9 00 0 50 0 51 5 01 3 3l1 0 1 o0 00 01 5 0 1 2 51 0 0 表2 1 图2 - 2 中3 个调度比较 要评价一个广播调度程序的优劣，主要考虑两个指标： ( 1 ) 访问时间( a c c e s st i m e ，以下简称a t ) ：从m u 提出数据访问请求 开始，到m u 从数据广播中得到结果为止所需的时间。访问时问决定了移动用 户查询的响应时间。这方面的研究主要是如何根据数据项的不同的访问概率，在 一个广播周期内安排数据项的出现频率和位置，使的m u 的平均访问时间最小。 ( 2 ) 调谐时间( t u n i n gt i m e ，简称丁丁) ：在完成一个访问请求期间，m u 保持接听广播的总时间。调谐时间决定了m u 接听数据广播时的电源消耗，因 为在不接听广播的时间里，m u 可以转入休眠模式，此时m u 消耗的电源相对于 m u 处于激活状态时消耗的电源可以忽略不计。因为大部分m u 都是依靠能量有 限的电池供电的，因此减小m u 的调谐时间也成为数据广播中的一个重要研究 课题。现在的研究中普遍采用在广播数据中插入索引信息的方法来优化调谐时 间。 誊 2 1 数据广播调度 2 1 1 基于推的数据广播调度 平坦调度 如前面所介绍的，平坦调度是最简单的数据广播调度模式，在这种模式下所 有的数据项以相同的概率出现，以轮换的方式进行广播。在平坦调度下对所有的 数据项的访问时间都是相同的，为一个广播周期的1 2 。平坦调度的模式很简单， 在所有数据项的访问概率相同的情况下性能很好，但是在实际的应用中一般对于 数据库的数据访问是不平均的，呈现出明显的偏斜，如典型的“8 0 2 0 ”现象， 即8 0 的访问请求落在2 0 的数据项上。在这种情况下平坦调度的性能很难保 证。 多盘调度 美国b r o w n 大学的s a c h a r y a 等人对数据广播访问时间的优化进行了大量的 研究，提出了一种多盘广播( m u l t i d i s kb r o a d c a s t ) 机带t j a c h a l 9 9 5 a ，a c h a l 9 9 5 b ， a c h a l 9 9 7 b ，李1 9 9 8 ，来适合对各个数据项的访问概率具有较大偏斜度的环境。 数据广播多盘调度的基本思想是：将数据库的所有数据项按照访问概率分为k 组，即b l ，b 2 ，b k 。b l 中的数据项访问概率最高，而b k 最低。在一个广播调 度中，同一个组内的数据项以相同的频率广播，而不同组的广播频率是不同的， 设b i 的广播频率为f i ，则f l 6 f z 。于是，数据广播可以比喻为k 个具有不同 传输率的磁盘( d i s k ) ，通过将访问概率高的数据项放在相对快速的磁盘中，就可 以降低所有请求的平均访问时间，因此我们称之为“多盘广播”。多盘调度的流 程如图2 3 所示【李i 1 9 9 8 】。 图2 3 多盘调度流程图 多盘调度的算法一般有如下步骤： a c h a l 9 9 5 b 】 将所有数据项按照访问概率从高到低的顺序排列。 将具有相同的访问概率的数据项分配到相同的磁盘， n u m _ d i s k s 。 为每个磁盘i ( 1 - i - n u m _ d i s k s ) 选择相对的广播频率坟i ) ， 磁盘的数目为 相对的广播频率 必须为整数。 计算3 中给出的f f i ) 的最小公倍数l c m ，将每个磁盘分成更小的，大小相等 的块( c h u n k ) ，每个磁盘分成的块的数目为n u m ( i ) = l c m f ( i ) 。c i d 表示第i 个磁盘 上的第i 个块。 在一个广播周期中数据广播的时候交替广播每个磁盘的块中的内容： f o r i = 0 t o l c m 1 f o r j = 1t on u m _ d i s k s 广播块q ，( i m o d h u m ( i ) ) 中的内容 e n d f o r e n d f o r 下面的图演示了就是一个多盘调度的例子，为了论述简单假设数据广播时一 次只广播一个数据项的实例。假设a 1 一a 7 为7 个数据项，其中a l 的访问概率最 高，a 2 、a 3 的访问概率相同，访问概率低于a l 。a 4 a 7 访问概率相同，但是最低。 首先根据2 将a l a 7 分配到不同的“磁盘”d i ( i = l ，2 ，3 ) ： d 1d 2d 3 “磁盘”d 1 ，d 2 ，d 3 的相对广播速率为4 、2 、1 ，根据4 将“磁盘”数据分 配到小的块： c i ，0c 2 ，0c 2 ，ic 3 ，0c 3 ，lc 3 ，2c 3 ，3 根据5 ，一个广播周期将是按如下方式广播数据： 2 1 2 基于拉的数据广播调度 基于“推”的数据广播调度能够满足多数m u 的需要，但是某些m u 的需 求很难保证，而且很多时候服务器并不知道m u 访问数据的规律。为了克服这 些不足之处，很多的研究中提出了“拉”的数据传输方式，又称为点播式数据广 播。一个典型的点播式数据广播系统模型如图1 2 - - 4 所示 a c h a l 9 9 8 】。 叁一 p m 呦峭t s 图2 4 典型的点播式数据广播系统 点播式数据广播和纯“推”( p u s h ) 方式发送数据的数据广播比较，主要的区 别有两点： ( 1 ) 需要有上行信道用来发送数据访问请求。 ( 2 ) 服务器不知道m u 的访问规律。 在一个点播式的系统中，当m u 需要数据的时候通过上行信道向服务器发送 请求，m u 发送的请求放到服务器的m u 请求队列中，服务器重复的从队列中选 择m u 请求，将m u 请求的数据通过下行信道广播出去，m u 监听信道并获取所 需的数据项。因此点播式数据广播调度的核心研究课题就是确定数据项广播的优 先次序，即下一个广播周期中应该广播哪些数据项。 【a k s 0 1 9 9 8 提出了f c f s ( f i r s t - c o m e f i r s t s e r v e d ) 调度算法，按访问请求的时 间顺序广播数据项。由于只考虑访问请求的时间，而不考虑对数据项访问频率的 差别，所以平均性能差。【d y k e l 9 8 6 】中提出了三种调度算法：m r f 、m r f l 和 l w f 。m r f ( m o s t - r e q u e s t f i r s t ) 调度算法优先广播那些具有最多的正在等待的请 求数的数据项。因为每次广播的都是那些正在等待的请求数最多的数据项，所以 在每次广播都有最大的响应比( 响应的请求数总请求数) ，能得到很小的平均访问 时间( a n 。如果有多个数据项具有同样多的正在等待的请求数则任意选择一个进 行广播。如果数据项的访问概率相同，那么m r f 能够获得最好的性能。 m r f l ( m r fl o w ) 调度算法和m r f 调度算法一样，不同之处是m r f l 调度算法 在有多个数据项的正在等待的请求数一样多的时候，它选择访问概率最低的数据 项进行广播。l w f ( l o n g e s t - w a i t - f i r s t ) 调度算法把具有最大等待时i 茸q ( i e 在等待的 所有请求的总的等待时间) 的数据项优先广播。如果数据项的访问概率满足z i p f 分布 z i p n 9 4 9 ，那么l w f 能够获得最好的性能。在数据量较小时m r f l 的性 能和l w f 相近，但是当数据量很大的时候，l w f 并不实用，因为对每个数据项 每次调度前都要重新计算请求该数据项的所有请求的等待时间，而m r f l 的性 能和m r f 相近，因为数据库较大时多个数据项具有同样多的正在等待的请求数 1 4 的概率降低了，m r f l 也就退化为m r f 了。 m r f 算法中对请求频繁的数据项的等待时间较短，但是对于请求不频繁的 数据项的等待时间可能会很长，因为必须等到对该数据项的请求到达一定数目的 时候才会广播该数据，因此m r f 并不是一个能够避免“饥饿”的算法，某些 m u 的请求有可能永远得不到回答。f c f s 是一个能够避免“饥饿”的算法，但 是它对忽视了数据项的访问概率，因此实际性能较差。l w f 较好的考虑了数据 项的访问概率，而且也是能够避免“饥饿”，但是数据量很大的时候并不实用。 基于以上考虑，f a k s 0 1 9 9 9 提出了一种新的调度算法：r x w 。r x w 算法每 次选择r w 最大的进行广播，其中r 为对该数据项的正在等待的请求的数目， w 是这些请求中等待最久的那个请求的等待时间。因此该算法广播的数据或者 它是热点数据，或者在外部对它的请求有某些请求已经等待了很长时间。r x w 算法可以通过维护两个有序队列实现：r 队列和w 队列。r 队列中按r 的值进 行排序，w 队列中按照w 的值进行排列。实验表明