嵌入式移动实时数据库管理系统的数据广播调度策略研究.doc

《嵌入式移动实时数据库管理系统的数据广播调度策略研究.doc》由会员分享，可在线阅读，更多相关《嵌入式移动实时数据库管理系统的数据广播调度策略研究.doc（52页珍藏版）》请在三一办公上搜索。

1、分 类 号 学号 2005612100164学校代码 10487 密级 公开 硕士学位论文嵌入式移动实时数据库管理系统的数据广播调度策略研究学位申请人：石磊学科专业：计算机软件与理论指导教师：卢炎生 教授答辩日期：2007年6月2日A Thesis Submitted in Partial Fulfillment of the Requirementsfor the Degree of Master of EngineeringResearch on Broadcast Scheduling Strategyin Embedded Mobile Real-Time DBMSCandidate

2、:Shi LeiMajor :Computer Software and TheorySupervisor :Prof. Lu YanshengHuazhong University of Science and TechnologyWuhan 430074, P. R. ChinaJune, 2007独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作

3、者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密，在_年解密后适用本授权书。本论文属于不保密。（请在以上方框内打“”）学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日摘 要在嵌入式移动实时数据库系统中，无线网络环境具有带宽小、非对称、通信质量差等特点，为了支持大量移动用户并发访问数据库服务器上

4、的内容，提高网络通信的伸缩性，人们提出数据广播这一重要的数据分发方式。数据广播技术的研究主要包括数据广播模式、数据广播调度、数据广播组织，其中广播调度是数据广播应用中的关键技术。着重研究支持实时应用的数据广播调度策略。首先综述国内外在广播调度方向上的研究进展，对各种调度策略进行定性分析与评价。而后综合移动实时数据库中数据的各种特征，提出一种基于混合广播模式的实时数据广播模型，同时给出数据广播技术研究中的前提与假设。然后简要介绍自适应混合广播调度策略TC-AHB，并在此该策略基础上，提出一种改进的自适应混合调度策略Improved TC-AHB。TC-AHB策略能够根据数据的请求模式以及时间限制

5、等特征来动态计算周期广播的带宽比例及被调度的数据，同时，该策略设计的采样技术能够自适应调节采样的数据对象与采样时间，从而有效地获取数据的请求模式。Improved TC-AHB策略在继承这些技术优点的同时，进一步将TC-AHB策略推广到基于事务的多数据项广播调度中，同时，Improved TC-AHB策略采用“分布式周期广播”思想，以更精细的周期广播粒度来解决过长的周期广播时段与事务及数据的实时要求之间的矛盾。最后基于提出的实时数据广播模型，实现一个调度策略性能评价仿真系统，将Improved TC-AHB与TC-AHB，以及流行的按需调度策略EDF-T进行实验性能比较。实验结果表明：基于混合

6、广播模式的调度策略更适合于实时环境下的数据广播应用；Improved TC-AHB策略具有更低的事务失败率，以及更小的上行信道负荷。关键词：嵌入式移动实时数据库，数据广播，混合广播模式，调度策略，自适应AbstractIn the embedded mobile real-time database system (EMRTDBMS), Wireless network has the features of low bandwidth, asymmetry and poor quality, in order to support a large number of mobile clien

7、ts concurrently accessing the content in database servers, and to improve the scalability of the network communication, data broadcast tech., an important data dissemination method, is provided and applied in EMRTDBMS. Broadcast mode, scheduling strategy, and data organization are the main research

8、directions of data broadcast tech. Scheduling strategy is the key direction particularly.This paper emphasizes on scheduling strategy for data broadcast in real-time environment. Firstly, we introduce the progress of research on scheduling strategy in the past few years, and give the qualitative ana

9、lysis of those provided strategies. Secondly, by analyzing the characters of data in real-time database, we provide a Real-Time Data Broadcast Model based on hybrid broadcast mode. Then, we give a brief description of TC-AHB, a hybrid broadcast scheduling strategy. And based on that strategy, we pro

10、vide an improved scheduling strategy, named Improved TC-AHB.By taking the information of data requested mode and data deadline into calculation, TC-AHB can dynamically calculate the bandwidth ratio for periodic broadcast and the being-scheduled data, through a novel sample tech., TC-AHB can also eff

11、iciently get more valid data-requested mode. Improved TC-AHB not only inherits those merits of TC-AHB, but also extends the strategy to the broadcast based on transaction scheduling. And, it adopts an idea called distributed periodic broadcast, to solve confliction between a long periodic broadcast

12、interval and real-time requirement of data and transactions.At last, we implement a prototype system for measuring the performance of provided scheduling strategy, and for comparative experiment, we implement not only Improved TC-AHB, but also TC-AHB and an on-demand strategy called EDF-T. The concl

13、usions are: those strategies based on hybrid broadcast mode are more suitable for data broadcast application in real-time environment; and Improved TC-AHB has lower transaction failure ratio, and lower uplink load.Keywords: Embedded Mobile Real-Time DBMS, Data Broadcast, Hybrid Broadcast Mode, Sched

14、uling Strategy, Adaptive目 录摘 要IAbstractII1绪 论1.1嵌入式移动实时数据库的系统模型(2)1.2嵌入式移动实时数据库的数据广播技术(5)1.3本文主要研究内容与组织(7)2广播调度策略的基本理论和方法2.1广播调度策略的评价指标(9)2.2周期广播调度(10)2.3按需广播调度(11)2.4混合广播调度(12)2.5多数据项的广播调度(13)2.6基于事务的调度(13)2.7小结(14)3实时数据广播模型3.1数据广播模式(15)3.2实时数据的特征(17)3.3实时数据广播模型(18)3.4研究中的假设(20)3.5小结(21)4一种改进的自适应混合

15、广播调度策略4.1TC-AHB调度策略(22)4.2TC-AHB调度策略的性能分析及改进措施(26)4.3改进的TC-AHB（Improved TC-AHB）调度策略(27)4.4小结(30)5仿真实验与性能评价5.1仿真系统设计(31)5.2实验参数(32)5.3性能评价指标(33)5.4实验结果及分析(34)5.5小结(38)6结束语6.1本文总结(39)6.2进一步工作(39)致 谢(41)参考文献(42)1 绪 论随着蜂窝通信、无线局域网及卫星通信等无线通信技术的飞速发展，许多终端用户已经可以在自由移动的过程中保持与网络的连接。于是人们迫切需求移动终端能够在任何时候、任何地点访问任何数

16、据，而原来基于有线网络和固定主机的分布式数据库并不适应这些应用需求，基于无线网络的移动数据库技术（MDBMS）便应运而生，并且得到迅速广泛的应用。有一类应用，如军事指挥系统、实时交通信息管理系统、海上导航系统等，它们普遍要求事务的实时处理以及数据请求的实时响应，过期的未处理事务或实效的数据有可能带来灾难性的后果。因而移动实时数据库（MRTDBMS）受到业界以及学界研究者的关注。一般认为移动实时数据库系统就是移动环境（GSM 等无线网络）所支持的实时数据库系统1。在移动实时数据库系统中，移动客户端一般不是传统的台式计算机，而是车载设备、PDA、智能手机等嵌入式设备，数据库系统往往嵌入到这些设备中

17、，运行与嵌入式操作系统（如Linux、WinCE、VxWorks等）之上，所以它又称为嵌入式移动实时数据库（EMRTDBMS）。与分布式数据库系统的网络环境相比，移动实时数据库系统的网络环境具有带宽小、通信质量差的特点2。在一个无线广播单元内，从广播服务器（或称移动服务基站MSS）到移动用户MC的下行通信带宽一般要远大于从MC到MSS的上行通信带宽，而且MC从MSS接收数据的开销也远小于发送开销，因此在大部分场合，即使是处于断接状态，MC也可以选择接收从服务器发送的下行广播信息。为了支持大量用户并发访问服务器上的数据，有效地利用通信带宽，人们提出了数据广播（Data Broadcast）这一新

18、的数据分发模式2，由服务器将数据库中被大多数用户频繁访问的数据（即“热点数据”）组织起来向空中广播，移动用户从空中获取数据。数据广播是提高移动实时数据库系统可伸缩性的重要技术。对数据广播的研究主要分为如下3个方向：（1）广播模式，即数据的分发方式；（2）广播调度，即数据被选入广播序列，服务器所使用的策略；（3）广播组织，即数据在广播序列中的索引结构。文章将在1.2节对数据广播的这3个研究方向进行简要概述。本文主要围绕广播调度策略展开研究，在提出适用于实时移动环境的数据广播模型之后，进一步提出一种改进的自适应混合广播调度策略。本章组织结构如下：1.1节参考国内外研究文献，给出嵌入式移动实时数据库

19、的系统模型；1.2节对嵌入式移动实时数据库的数据广播技术及其研究方向进行简要概述；1.3节列出本文的研究内容及方向，并且给出章节组织结构。1.1 嵌入式移动实时数据库的系统模型Fix Network（WAN/Intranet/ATM etc.）ISMSSMSSERTDBMSLDBERTDBMSLDBERTDBMSLDBMCMCMCMCMCERTDBMSRepDBERTDBMSRepDBWirelessBroadcastUnitWired ConnectWireless Connect图1.1 嵌入式移动实时数据库的系统模型ISLSMSSDisconnectFH为了有效的研究数据广播技术，一个清

20、晰的系统结构至关重要。参考文献3, 4，本文建立嵌入式移动实时数据库的系统模型，如图1.1所示。系统由固定网络及移动网络两大部分组成。固定网络由一组移动服务基站MSS（Mobile Server Station）、信息服务器IS（Information Server）、位置服务器LS（Location Server）、以及固定主机FH（Fix Host）构成，它们通过WAN或其它有线网络连接，数据库分布于IS和MSS中；移动网络由一系列相交或者不相交的无线广播单元WBU（Wireless Broadcast Unit）构成，每个WBU由一个MSS支持，并且由一组移动客户MC（Mobile Cl

21、ient）组成，每个MC为一个嵌入式移动设备，它可以夸单元移动。下面详细讲述主要组成模块的功能特征。1.1.1 信息服务器ISIS 扮演数据库服务器的角色，它有本地数据库LDB（Local Database），并且由一嵌入式实时数据库管理系统ERTDBMS支持，它为MSS提供广播所需的数据。同时IS维持本地数据的更新。更新事务由传感器周期地或偶然地创建。传感器捕获外部环境的实时状态的变化，然后传输给IS来维护数据库中数据与外部数据的一致性。IS 的数据更新特性包括以下两个方面：更新频率（Frequency of Updates）：按广播系统支持的应用类型，IS 中数据的更新频率分为频繁、普通和

22、不更新三种。更新方法（Update Method）：指IS中数据被更新后，通过什么方法告知用户。常用的方式可向MC发送数据失效报告，或直接向MC发送最新数据。本文的研究不考虑数据的收集和更新。在以下论述中，如不特别说明，服务器（广播服务器）均指移动服务基站MSS。1.1.2 移动服务基站MSS（广播服务器）MSS提供对其负责的无线广播单元的通信支持，某些MSS同时扮演IS的角色，即数据的存储与更新。由前文所述可知，广播技术是系统的重要数据分发模式，MSS详细描述了广播结构，并定义了广播据的主要特征：广播内容（Broadcast Contents）：在一些广播系统中，广播内容是不变的，广播内容的

23、值可被更新（如股票系统）。另外，广播内容也可以根据用户的数据需求动态产生和替换。存储桶容量（Bucket Size）：存储桶是广播程序中广播的最小粒度，它又称为页面（Page）。一般桶（页面）的容量是定长的。广播磁盘结构（Broadcast Disk Structure）：可分为平坦（Flag）结构和偏斜（Skewed）结构。其中平坦结构指在广播周期中各个数据项的出现频率相同。偏斜结构与之相反，指各个数据项出现的频率不完全相同。广播周期（Broadcast Cycle）：分为周期（Periodic）广播和非周期（Aperiodic）广播。在周期广播中，MSS循环地广播数据。而在非周期广播系统中

24、，MSS通过特殊的事件触发机制广播数据。数据库内容（Database Content）：广播的数据可以是数据库中的全部数据（全集），或部分数据（子集）。数据项的放置（Data Item Placement）：静态调度中，不同的广播周期，所有数据项的调度顺序均保持不变。动态调度则根据用户的需求动态确定数据项的广播顺序。索引（Index）：MC 可通过索引信息知道在什么时间从广播信道接收自己想要的数据，从而在等待时转入休眠模式而节约移动计算设备的电池消耗。1.1.3 无线网络（Wireless Network）（1） 带宽（Bandwidth）：不同的无线网络通信特点各不相同。无线电（Wirele

25、ss Radio）通信覆盖范围广，但带宽只有19.2Kbps，且信道可伸缩性差。无线局域网通信带宽大（2-10Mbps），但覆盖范围通常小于100米。卫星通信有很大的带宽和很强的覆盖范围，但价格昂贵。（2） 连接性（Connection）：分为强可靠（Strong Reliable）和弱可靠（Weak Reliable）两种。在弱可靠网络中，当大规模并发用户访问数据时，对索引的等待、广播内容的改变、过时的Cache等因素可能导致系统性能下降。另外，信号的衰减和噪音使得位错误率（Bit Error Rate）增加，从而导致吞吐率（Throughput）下降。而在强可靠网络中，吞吐率和数据响应时间

26、均有保障。（3） 覆盖范围（Range）：无线广播单元WBU指一个MSS同时覆盖的领域，其范围从直径 100 米到全球卫星单元。当今网络技术趋向于采用更小的广播单元，一个地域被划分成更多的单元，从而 MC 需要更频繁地穿越不同单元的边界，不同广播单元可以有所交叉覆盖。1.1.4 移动用户MC（Mobile Client）MC为数据库系统的客户端，一般为嵌入式设备，如PDA、智能手机等。MC侦听广播信道，从 MSS的广播序列中获取信息。不同的广播系统设定不同类型的用户。按参与性可将用户分成主动用户和被动用户，按优先级可分为高优先级用户和低优先级用户，另外还可分为缓存用户和无缓存用户，拥有反向信道

27、（Backchannel）的用户和无反向信道的用户等。1.2 嵌入式移动实时数据库的数据广播技术在图1.1所示的嵌入式移动实时数据库的系统模型中，移动客户MC和广播服务器MSS间的通信具有如下的特性：在一个无线广播单元WBU内，从MSS到MC的下行通信带宽一般要远大于从MC到服务器的上行通信带宽。而且MC从MSS接收数据的开销也远小于发送开销，在极端的情况下，即使是处于断接状态下（即无法向服务器发送消息）的MC也可以选择接收从MSS发送的下行广播信息。因此，采用数据广播是解决移动实时数据库系统用户规模庞大和网络通讯非对称性等问题的一个有效的方法。在数据广播中，有3个主要的性能衡量参数5：（1）

28、访问时间（access time，也称为存取时间），它指从MC提出查询请求，到结果返回所需的时间。访问时间一般作为系统响应时间的衡量标准；（2）调谐时间（tuning time）：它指MC为了获得查询结果，用于侦听信道的时间。MC侦听信道需要消耗电源，因而一般将该参数作为数据访问消耗电源的衡量标准；（3）请求成功率（request success ratio，也称请求响应率）：它描述MC的数据请求在截止期前得到满足的比率，它是实时环境下，广播系统负载能力的一个重要衡量标准。近年来数据广播技术已引起了广泛的研究，针对上述性能参数的优化，主要研究方向分为以下3类：广播模式，即MSS与MC之间的数据

29、交互方式；广播调度策略，即MSS选择被广播数据的策略；广播组织方式，即被调度数据在广播序列中的索引结构。1.2.1 广播模式在移动环境中，MSS的数据分发方式可以分为三种：（1）PULL方式，在此方式下，MSS根据数据的静态访问模式，单向周期广播既定数据，MSS不考虑MC的具体需求；（2）PUSH方式，在此方式下，MSS响应MC的数据请求，广播请求数据，但它不考虑数据的访问模式；（3）混合（Hybrid）方式，它将PULL方式与PUSH方式相结合。基于这三种方式，存在三种数据广播模式，分别为周期广播模式，按需广播模式，和混合广播模式。3.1节将对这3种广播模式进行较为详细的介绍，并且基于混合广

30、播模式，提出一种适用于实时移动环境下的数据广播模型。1.2.2 广播调度移动实时应用环境中，数据有随时间变化的特性，移动用户的应用处理也有定时限制，因此对数据的存取也有定时限制，过了时的数据将不再是用户所需要的数据。如股票数据、交通状况数据。为了满足移动用户对数据需求的定时限制，不仅要求动态地组织广播内容，还要对广播内容进行合理的调度。根据数据广播模式的不同，广播调度策略分为3大类：周期广播调度策略，按需广播调度策略，混合广播调度策略。本文将在第2章概述国内外学者在广播调度策略方向上的研究工作。本文的研究目标是提出一种改进的自适应混合调度策略。1.2.3 广播组织移动客户MC到达一个无线广播单

31、元WBU后，就开始侦听广播，如果对广播序列的数据不做任何形式的目录和索引，MC必须一直侦听广播，直到收到所需的数据为止。MC一直处于盲目侦听状态，这将极大降低MC的并行计算能力，增大MC的电源消耗。如果合理组织数据，使MC有目标、有选择性地侦听广播，将大大减少它的侦听时间。为此，广播服务器MSS需要广播数据索引以指出数据在广播序列中的位置，以便MC有效地收听。广播索引的构造问题类似于文件系统中的索引结构，然而在文件系统领域并未对索引结构作细致深入的研究，这是因为：在文件系统中，访问索引的代价远小于CPU和IO等其它操作；文件系统中频繁的更新操作使得维护复杂的索引结构非常困难。在移动环境下，由于

32、侦听目录占去了移动事务的大部分时间，所以构造相对复杂的索引是有意义的。已有的工作中提出了使用hash 函数的方法6，文献7提出了使用B 树的方法，文献8提出了一种称为signature的方法，文献9提出了混合B树和signature的方法。如果在每次数据广播中只发送一次索引，则当用户错过接收索引时间时，只能等待下一次广播，这将会增加延迟时间。可以采取在一次数据广播中重复发送m次索引的方法，降低因为用户错过接收索引而带来的延迟，这称为(l, m)索引技术7。在(1, m)索引技术中，每次复制的索引没有必要完全相同，只需保证每次复制的索引包含接下来要广播的内容即可。1.3 本文主要研究内容与组织本

33、文的研究目标是提出一种适用于实时移动环境下的广播调度策略，以提高事务请求的成功率及信道的利用效率。具体章节安排如下：第一章简要介绍嵌入式移动实时数据库及其数据广播技术，引进一种嵌入式移动实时数据库的系统模型，为本文进一步的研究工作提供系统支持。第二章综述了国内外近年来在广播调度策略方向上的研究进展及成果。该章将调度策略的研究进行了进一步分类，横向分为：（1）基于周期广播模式的调度策略；（2）基于按需广播模式的调度策略；（3）基于混合广播模式的调度策略。纵向分为：（1）基于单数据项的调度策略；（2）基于多数据项的调度策略；（3）基于事务的调度策略。该章给出各类调度策略的研究现状、算法思想、适用范

34、围、以及定性的性能评价。第三章在分析移动环境下实时数据的主要特征之后，提出一种实时数据广播模型，该模型基于混合广播模式。模型为第四章实时调度策略提供了可运行的基础设施。在第三章最后给出数据广播研究中的系统假设。第四章首先简要描述文献10提出的一种适用于实时环境下的混合广播调度策略自适应混合广播调度策略TC-AHB，然后对该策略进行了定性的性能分析，提出改进措施。最后给出一种改进的自适应混合调度策略Improved TC-AHB，该改进策略将TC-AHB策略扩展到基于事务的广播调度中，同时，该改进策略采用“分布式周期广播”思想，以使TC-AHB策略更加适应于实时事务的广播调度。第五章对Impro

35、ved TC-AHB策略进行仿真实验和性能评价。该章首先给出仿真系统的体系结构，并且在该系统之上实现了EDF-T调度策略、TC-AHB调度策略、以及Improved TC-AHB调度策略。运行该仿真系统，调节各种系统参数，如事务平均到达时间、事务截止期分布、数据偏斜度等，得到调度策略在事务失败率、上行信道负荷等性能上的多组实验数据。实验结果表明，Improved TC-AHB策略具有更低的事务失败率，以及更小的上行信道负荷。2 广播调度策略的基本理论和方法在实时移动环境中，移动事务对数据的访问概率、访问兴趣会随着时间不断变化，并且对数据具有随机的实时性要求，所以服务器不仅要动态地选择广播数据，

36、还要合理地调度广播数据，以使用户访问时间最短，并且事务失败率最低。如何调度广播信道中的数据，使之适合于移动用户的访问需求，即广播调度策略的实现问题，是广播技术中的一个重要研究方向， 本章综述了近年来国内外学者在广播调度策略方面的研究进展。2.1节给出广播调度策略的评价标准，包括访问时间、调谐时间、以及事务成功率；2.2节至2.4节分别综述了国内外文献对周期广播调度、按需广播调度、以及混合广播调度的研究；在实际应用中，系统的工作的原子粒度往往是事务，而事务所请求的数据往往是多数据项的，2.5节至2.6节综述了国内外对基于多数据项和基于事务的调度策略的研究概况。2.1 广播调度策略的评价指标评价一

37、个广播调度策略的性能，主要考虑以下三个指标5：（1） 访问时间（Access Time）：指从移动用户提出数据访问请求开始，到该用户从数据广播中得到结果为止所需的时间。访问时间决定了移动用户查询的响应时间。（2） 调谐时间（Tuning Time）：指在完成一个访问请求期间，移动用户必须保持侦听广播的总时间，由于广播序列中索引的存在，从而使移动用户可以在等待数据的同时，并行进行其它操作，或进入休眠状态。（3） 事务成功率（Transaction Success Ratio，以下简称 TSR）：指满足截止期的事务占所有事务的百分比。它用于衡量服务器满足事务及数据时效要求的能力。在实时环境下，如何

38、减少访问时间和调谐时间并不是主要关心的问题。保证请求在一定的时间限制内得到满足是主要考虑的问题。通常在非实时系统中，数据传送失败是被忽略的。它基于的假设是获取数据时出现失败可以容忍，因为用户可以在下次广播时再次接受数据。而对于实时系统，这个假设可能导致请求超出截止期。所以在实时广播调度中，事务成功率是调度策略的一个重要性能评价指标。2.2 周期广播调度周期调度广播调度策略（静态调度策略）针对具有固定请求模式的应用环境，服务器已知数据请求模式。使用这种广播调度策略，服务器周期性地广播数据，用户被动地接收数据。周期广播调度方面的研究包括文献11-17等，其中最著名的是美国Brown大学的Achar

39、ya S.等人首先提出一种多盘广播（Multidisk Broadcast）11。将数据库的所有数据项按照访问概率分为 K 组，在一个广播调度中，同一个组内的数据项以相同的频率广播，而不同组的广播频率是不同的，数据广播可以比喻为K个具有不同传输率的磁盘（Disk），通过将访问概率高的数据项放在相对较快速的磁盘中，就可以降低所有请求的平均访问时间；此外，这种多盘广播机制还考虑了客户机上的缓存问题，利用预取和缓存技术来进一步提高用户访问空中数据的性能。但是，多盘调度机制缺乏可操作性，其设备参数必须由手工确定，且无章可循；而且，他们没有考虑数据广播的调谐时间优化问题，因此无法有效支持电源有限的嵌入式

40、设备。国防科技大学的周兴铭院士等人提出了启发式多盘调度算法（Heuristic Multidisk，HMD）15, 16。采用Zipf 启发式策略将数据项分割到K个具有不同广播频率的盘中，并根据各盘平均访问概率的平方根之比确定其相对广播频率。虽然HMD算法由计算机自动确定数据项到各盘的分配以及各盘的相对频度，但仍需人工确定盘数。复旦大学孙未未博士提出了朴素逼近调度算法（Naive Approach Schedule Algorithm，NASA）17。在指定的广播周期长度内，首先计算出最接近理论最优值的每个数据项的广播频度（整数）；然后根据得到的广播频度尽可能均匀地把数据项组织成一个完整的广播

41、调度。NASA 算法中只有广播周期一个输入参数，保证了对于每个数据项其最大平均访问时间不超过二分之一广播周期。但是同样地，NASA 算法没有考虑数据广播调谐时间的优化问题。2.3 按需广播调度在按需广播调度策略（动态调度策略）下，移动客户首先提出数据请求，服务器考察没响应的所有请求，按照一定优先级计算方式选择下一个广播的数据项。按需调度和静态调度的差别是，它的一个核心研究课题是确定数据项广播的优先次序，即下一个广播周期中应该广播哪些数据项。动态数据广播调度算法的研究主要包括：Aksoy D.提出FCFS（First-Come-First-Served）调度算法，按访问请求的时间顺序广播数据项1

42、8。由于只考虑访问请求的时间，而不考虑对数据项访问概率的差别，所以平均性能较差。Bender M.A.提出LWF（Long-Wait-First）调度算法，把具有最大等待时间的数据项优先广播19。Acharya S.提出LTSF（Longest-Total-Stretch-First）调度算法，在LWF基础上考虑了数据项不等长的因素20。Wong J.W.提出MRF（Most-Requests-First）调度算法，优先广播那些具有最多请求数的数据项21。因为每次广播的都是那些访问最频繁的数据项，所以在每次广播都有最大的响应比（响应的请求数/总请求数），能得到很小的平均访问时间。Aksoy D

43、.提出RxW算法，它结合MRF和FCFS 算法的优点，根据当前请求队列的状态调度数据项22。Xuan P.提出EDF（Earliest Deadline First）算法，把具有最小截止期的数据项优先广播。EDF-BATCH算法在EDF算法的基础上考虑相同数据项的处理23。这些动态数据广播调度算法在确定一个数据项是否编入广播调度中时，仅依据数据的单一特征，没有一个意义明确的优先级计算模型。并且均没有考虑一个请求很长时间得不到响应时的处理，只提到采取一些措施来减少这种情况发生的概率。而不对很长时间得不到响应的请求做出必要的处理，允许无限等待的出现，在实时环境下是无法忍受的。针对以上缺点，Sun

44、W.W.提出LDCF（Largest-Delay-Cost-First）算法24。通过对每个数据项计算把它延迟到下一个周期广播所增加的开销，以此作为每个数据项的优先级，按优先级确定参与广播的数据，然后根据访问概率调度数据。2.4 混合广播调度混合广播结合了静态广播和动态广播的优点。在混合数据广播中，上行信道用于传输在广播程序中没有被满足的用户数据访问请求；下行广播带宽分为静态广播和动态广播两部分，其中静态广播周期地广播“热点数据”，动态广播根据用户需求动态地广播数据。混合数据广播算法的研究主要有：Xuan P.提出BoD广播模型，将下行广播带宽分为两部分：一部分周期地广播热点数据，另一部分根据

45、移动客户需求动态广播23。BoD模型中明确考虑了数据项的最低响应时间限制，但静态广播和动态广播的带宽分配是固定不变的，不能随工作量的变化而动态调整。Jesus F.C.提出一个自适应混合数据广播策略10, 25，在静态广播和动态广播中分别应用 PINOPT 算法26, 27和EDF算法广播数据，以尽可能多地满足用户对数据的最低响应时间限制要求。此算法根据系统工作量动态地分配静态和动态广播带宽，以使得用户平均等待时间最短和请求失败率最低为目标。但算法通过产生大量的冗余数据来尽可能地满足用户对数据请求的时限要求，信道利用率较低，用户的平均访问时间较长。Hu J.H.提出一种混合数据广播策略28。将

46、移动用户分成普通用户、联机请求用户和优先级用户三类，其中普通用户只能被动地接收广播数据，联机请求和优先级用户可通过上行信道提出数据访问请求，优先级用户拥有系统资源的最高使用权。此算法通过区分各类用户对信道的使用权限来获取低的平均访问时间。混合数据广播调度策略的研究关键是如何根据系统负荷，自适应地分配下行信道的带宽。文献293031对移动计算环境中信道的分配进行了详细的研究。Lee W.C.将信道的使用分为三种方式：所有信道专用于数据广播、专用于用户按需请求和混合使用，并提出应根据系统工作量选择合适的信道使用方式3031。通过比较这三种信道分配方式的优缺点，Hu Q.L.提出一个动态信道分配算法，以获得系统最优的信道分配方案，和最小的用户访问时间30。2.5 多数据项的广播调度以上列举的文献均假设移动客户任一时刻只访问广播信道中的一个数据项，即单数据项广播。但在很多应用中，移动客户需要同时访问广播信道中的多个数据项，这就是多数据项广播。多数据项广播调度能减少移动客户与服务器之间的通信，有效地节约上行信道的带宽。Lee G.L.提出了基于数据访问图的调度策略，该策略首先构造数据访问图，然后计算数据项的加权距离，根据加权距离合并数据访问图的顶点，直到合并成一个顶点为止，合并顶点的顺序即为调度数据项的顺序32。Lam K.提出EQSD（Equal Slack Data）和RP（Req