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

华 中 科 技 大 学 硕 士 学 位 论 文嵌入式移动实时数据库管理系统的数据广播调度策略研究毕业论文目 录摘 要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一种改进的自适应混合广播调度策略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)II1 绪 论随着蜂窝通信、无线局域网及卫星通信等无线通信技术的飞速发展，许多终端用户已经可以在自由移动的过程中保持与网络的连接。于是人们迫切需求移动终端能够在任何时候、任何地点访问任何数据，而原来基于有线网络和固定主机的分布式数据库并不适应这些应用需求，基于无线网络的移动数据库技术（MDBMS）便应运而生，并且得到迅速广泛的应用。有一类应用，如军事指挥系统、实时交通信息管理系统、海上导航系统等，它们普遍要求事务的实时处理以及数据请求的实时响应，过期的未处理事务或实效的数据有可能带来灾难性的后果。因而移动实时数据库（MRTDBMS）受到业界以及学界研究者的关注。一般认为移动实时数据库系统就是移动环境（GSM 等无线网络）所支持的实时数据库系统1。在移动实时数据库系统中，移动客户端一般不是传统的台式计算机，而是车载设备、PDA、智能手机等嵌入式设备，数据库系统往往嵌入到这些设备中，运行与嵌入式操作系统（如Linux、WinCE、VxWorks等）之上，所以它又称为嵌入式移动实时数据库（EMRTDBMS）。与分布式数据库系统的网络环境相比，移动实时数据库系统的网络环境具有带宽小、通信质量差的特点2。在一个无线广播单元内，从广播服务器（或称移动服务基站MSS）到移动用户MC的下行通信带宽一般要远大于从MC到MSS的上行通信带宽，而且MC从MSS接收数据的开销也远小于发送开销，因此在大部分场合，即使是处于断接状态，MC也可以选择接收从服务器发送的下行广播信息。为了支持大量用户并发访问服务器上的数据，有效地利用通信带宽，人们提出了数据广播（Data Broadcast）这一新的数据分发模式2，由服务器将数据库中被大多数用户频繁访问的数据（即“热点数据”）组织起来向空中广播，移动用户从空中获取数据。数据广播是提高移动实时数据库系统可伸缩性的重要技术。对数据广播的研究主要分为如下3个方向：（1）广播模式，即数据的分发方式；（2）广播调度，即数据被选入广播序列，服务器所使用的策略；（3）广播组织，即数据在广播序列中的索引结构。文章将在1.2节对数据广播的这3个研究方向进行简要概述。本文主要围绕广播调度策略展开研究，在提出适用于实时移动环境的数据广播模型之后，进一步提出一种改进的自适应混合广播调度策略。本章组织结构如下：1.1节参考国内外研究文献，给出嵌入式移动实时数据库的系统模型；1.2节对嵌入式移动实时数据库的数据广播技术及其研究方向进行简要概述；1.3节列出本文的研究内容及方向，并且给出章节组织结构。1.1 嵌入式移动实时数据库的系统模型Fix Network（WAN/Intranet/ATM etc.）ISMSSMSSERTDBMSLDBERTDBMSLDBERTDBMSLDBMCMCMCMCMCERTDBMSRepDBERTDBMSRepDBWirelessBroadcastUnitWired ConnectWireless Connect图1.1 嵌入式移动实时数据库的系统模型ISLSMSSDisconnectFH为了有效的研究数据广播技术，一个清晰的系统结构至关重要。参考文献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 Client）组成，每个MC为一个嵌入式移动设备，它可以夸单元移动。下面详细讲述主要组成模块的功能特征。1.1.1 信息服务器ISIS 扮演数据库服务器的角色，它有本地数据库LDB（Local Database），并且由一嵌入式实时数据库管理系统ERTDBMS支持，它为MSS提供广播所需的数据。同时IS维持本地数据的更新。更新事务由传感器周期地或偶然地创建。传感器捕获外部环境的实时状态的变化，然后传输给IS来维护数据库中数据与外部数据的一致性。IS 的数据更新特性包括以下两个方面：更新频率（Frequency of Updates）：按广播系统支持的应用类型，IS 中数据的更新频率分为频繁、普通和不更新三种。更新方法（Update Method）：指IS中数据被更新后，通过什么方法告知用户。常用的方式可向MC发送数据失效报告，或直接向MC发送最新数据。本文的研究不考虑数据的收集和更新。在以下论述中，如不特别说明，服务器（广播服务器）均指移动服务基站MSS。1.1.2 移动服务基站MSS（广播服务器）MSS提供对其负责的无线广播单元的通信支持，某些MSS同时扮演IS的角色，即数据的存储与更新。由前文所述可知，广播技术是系统的重要数据分发模式，MSS详细描述了广播结构，并定义了广播据的主要特征：广播内容（Broadcast Contents）：在一些广播系统中，广播内容是不变的，广播内容的值可被更新（如股票系统）。另外，广播内容也可以根据用户的数据需求动态产生和替换。存储桶容量（Bucket Size）：存储桶是广播程序中广播的最小粒度，它又称为页面（Page）。一般桶（页面）的容量是定长的。广播磁盘结构（Broadcast Disk Structure）：可分为平坦（Flag）结构和偏斜（Skewed）结构。其中平坦结构指在广播周期中各个数据项的出现频率相同。偏斜结构与之相反，指各个数据项出现的频率不完全相同。广播周期（Broadcast Cycle）：分为周期（Periodic）广播和非周期（Aperiodic）广播。在周期广播中，MSS循环地广播数据。而在非周期广播系统中，MSS通过特殊的事件触发机制广播数据。数据库内容（Database Content）：广播的数据可以是数据库中的全部数据（全集），或部分数据（子集）。数据项的放置（Data Item Placement）：静态调度中，不同的广播周期，所有数据项的调度顺序均保持不变。动态调度则根据用户的需求动态确定数据项的广播顺序。索引（Index）：MC 可通过索引信息知道在什么时间从广播信道接收自己想要的数据，从而在等待时转入休眠模式而节约移动计算设备的电池消耗。1.1.3 无线网络（Wireless Network）（1） 带宽（Bandwidth）：不同的无线网络通信特点各不相同。无线电（Wireless Radio）通信覆盖范围广，但带宽只有19.2Kbps，且信道可伸缩性差。无线局域网通信带宽大（2-10Mbps），但覆盖范围通常小于100米。卫星通信有很大的带宽和很强的覆盖范围，但价格昂贵。（2） 连接性（Connection）：分为强可靠（Strong Reliable）和弱可靠（Weak Reliable）两种。在弱可靠网络中，当大规模并发用户访问数据时，对索引的等待、广播内容的改变、过时的Cache等因素可能导致系统性能下降。另外，信号的衰减和噪音使得位错误率（Bit Error Rate）增加，从而导致吞吐率（Throughput）下降。而在强可靠网络中，吞吐率和数据响应时间均有保障。（3） 覆盖范围（Range）：无线广播单元WBU指一个MSS同时覆盖的领域，其范围从直径 100 米到全球卫星单元。当今网络技术趋向于采用更小的广播单元，一个地域被划分成更多的单元，从而 MC 需要更频繁地穿越不同单元的边界，不同广播单元可以有所交叉覆盖。1.1.4 移动用户MC（Mobile Client）MC为数据库系统的客户端，一般为嵌入式设备，如PDA、智能手机等。MC侦听广播信道，从 MSS的广播序列中获取信息。不同的广播系统设定不同类型的用户。按参与性可将用户分成主动用户和被动用户，按优先级可分为高优先级用户和低优先级用户，另外还可分为缓存用户和无缓存用户，拥有反向信道（Backchannel）的用户和无反向信道的用户等。1.2 嵌入式移动实时数据库的数据广播技术在图1.1所示的嵌入式移动实时数据库的系统模型中，移动客户MC和广播服务器MSS间的通信具有如下的特性：在一个无线广播单元WBU内，从MSS到MC的下行通信带宽一般要远大于从MC到服务器的上行通信带宽。而且MC从MSS接收数据的开销也远小于发送开销，在极端的情况下，即使是处于断接状态下（即无法向服务器发送消息）的MC也可以选择接收从MSS发送的下行广播信息。因此，采用数据广播是解决移动实时数据库系统用户规模庞大和网络通讯非对称性等问题的一个有效的方法。在数据广播中，有3个主要的性能衡量参数5：（1）访问时间（access time，也称为存取时间），它指从MC提出查询请求，到结果返回所需的时间。访问时间一般作为系统响应时间的衡量标准；（2）调谐时间（tuning time）：它指MC为了获得查询结果，用于侦听信道的时间。MC侦听信道需要消耗电源，因而一般将该参数作为数据访问消耗电源的衡量标准；（3）请求成功率（request success ratio，也称请求响应率）：它描述MC的数据请求在截止期前得到满足的比率，它是实时环境下，广播系统负载能力的一个重要衡量标准。近年来数据广播技术已引起了广泛的研究，针对上述性能参数的优化，主要研究方向分为以下3类：广播模式，即MSS与MC之间的数据交互方式；广播调度策略，即MSS选择被广播数据的策略；广播组织方式，即被调度数据在广播序列中的索引结构。1.2.1 广播模式在移动环境中，MSS的数据分发方式可以分为三种：（1）PULL方式，在此方式下，MSS根据数据的静态访问模式，单向周期广播既定数据，MSS不考虑MC的具体需求；（2）PUSH方式，在此方式下，MSS响应MC的数据请求，广播请求数据，但它不考虑数据的访问模式；（3）混合（Hybrid）方式，它将PULL方式与PUSH方式相结合。基于这三种方式，存在三种数据广播模式，分别为周期广播模式，按需广播模式，和混合广播模式。3.1节将对这3种广播模式进行较为详细的介绍，并且基于混合广播模式，提出一种适用于实时移动环境下的数据广播模型。1.2.2 广播调度移动实时应用环境中，数据有随时间变化的特性，移动用户的应用处理也有定时限制，因此对数据的存取也有定时限制，过了时的数据将不再是用户所需要的数据。如股票数据、交通状况数据。为了满足移动用户对数据需求的定时限制，不仅要求动态地组织广播内容，还要对广播内容进行合理的调度。根据数据广播模式的不同，广播调度策略分为3大类：周期广播调度策略，按需广播调度策略，混合广播调度策略。本文将在第2章概述国内外学者在广播调度策略方向上的研究工作。本文的研究目标是提出一种改进的自适应混合调度策略。1.2.3 广播组织移动客户MC到达一个无线广播单元WBU后，就开始侦听广播，如果对广播序列的数据不做任何形式的目录和索引，MC必须一直侦听广播，直到收到所需的数据为止。MC一直处于盲目侦听状态，这将极大降低MC的并行计算能力，增大MC的电源消耗。如果合理组织数据，使MC有目标、有选择性地侦听广播，将大大减少它的侦听时间。为此，广播服务器MSS需要广播数据索引以指出数据在广播序列中的位置，以便MC有效地收听。广播索引的构造问题类似于文件系统中的索引结构，然而在文件系统领域并未对索引结构作细致深入的研究，这是因为：在文件系统中，访问索引的代价远小于CPU和IO等其它操作；文件系统中频繁的更新操作使得维护复杂的索引结构非常困难。在移动环境下，由于侦听目录占去了移动事务的大部分时间，所以构造相对复杂的索引是有意义的。已有的工作中提出了使用hash 函数的方法6，文献7提出了使用B 树的方法，文献8提出了一种称为signature的方法，文献9提出了混合B树和signature的方法。如果在每次数据广播中只发送一次索引，则当用户错过接收索引时间时，只能等待下一次广播，这将会增加延迟时间。可以采取在一次数据广播中重复发送m次索引的方法，降低因为用户错过接收索引而带来的延迟，这称为(l, m)索引技术7。在(1, m)索引技术中，每次复制的索引没有必要完全相同，只需保证每次复制的索引包含接下来要广播的内容即可。1.3 本文主要研究内容与组织本文的研究目标是提出一种适用于实时移动环境下的广播调度策略，以提高事务请求的成功率及信道的利用效率。具体章节安排如下：第一章简要介绍嵌入式移动实时数据库及其数据广播技术，引进一种嵌入式移动实时数据库的系统模型，为本文进一步的研究工作提供系统支持。第二章综述了国内外近年来在广播调度策略方向上的研究进展及成果。该章将调度策略的研究进行了进一步分类，横向分为：（1）基于周期广播模式的调度策略；（2）基于按需广播模式的调度策略；（3）基于混合广播模式的调度策略。纵向分为：（1）基于单数据项的调度策略；（2）基于多数据项的调度策略；（3）基于事务的调度策略。该章给出各类调度策略的研究现状、算法思想、适用范围、以及定性的性能评价。第三章在分析移动环境下实时数据的主要特征之后，提出一种实时数据广播模型，该模型基于混合广播模式。模型为第四章实时调度策略提供了可运行的基础设施。在第三章最后给出数据广播研究中的系统假设。第四章首先简要描述文献10提出的一种适用于实时环境下的混合广播调度策略自适应混合广播调度策略TC-AHB，然后对该策略进行了定性的性能分析，提出改进措施。最后给出一种改进的自适应混合调度策略Improved TC-AHB，该改进策略将TC-AHB策略扩展到基于事务的广播调度中，同时，该改进策略采用“分布式周期广播”思想，以使TC-AHB策略更加适应于实时事务的广播调度。第五章对Improved TC-AHB策略进行仿真实验和性能评价。该章首先给出仿真系统的体系结构，并且在该系统之上实现了EDF-T调度策略、TC-AHB调度策略、以及Improved TC-AHB调度策略。运行该仿真系统，调节各种系统参数，如事务平均到达时间、事务截止期分布、数据偏斜度等，得到调度策略在事务失败率、上行信道负荷等性能上的多组实验数据。实验结果表明，Improved TC-AHB策略具有更低的事务失败率，以及更小的上行信道负荷。72 广播调度策略的基本理论和方法在实时移动环境中，移动事务对数据的访问概率、访问兴趣会随着时间不断变化，并且对数据具有随机的实时性要求，所以服务器不仅要动态地选择广播数据，还要合理地调度广播数据，以使用户访问时间最短，并且事务失败率最低。如何调度广播信道中的数据，使之适合于移动用户的访问需求，即广播调度策略的实现问题，是广播技术中的一个重要研究方向， 本章综述了近年来国内外学者在广播调度策略方面的研究进展。2.1节给出广播调度策略的评价标准，包括访问时间、调谐时间、以及事务成功率；2.2节至2.4节分别综述了国内外文献对周期广播调度、按需广播调度、以及混合广播调度的研究；在实际应用中，系统的工作的原子粒度往往是事务，而事务所请求的数据往往是多数据项的，2.5节至2.6节综述了国内外对基于多数据项和基于事务的调度策略的研究概况。2.1 广播调度策略的评价指标评价一个广播调度策略的性能，主要考虑以下三个指标5：（1） 访问时间（Access Time）：指从移动用户提出数据访问请求开始，到该用户从数据广播中得到结果为止所需的时间。访问时间决定了移动用户查询的响应时间。（2） 调谐时间（Tuning Time）：指在完成一个访问请求期间，移动用户必须保持侦听广播的总时间，由于广播序列中索引的存在，从而使移动用户可以在等待数据的同时，并行进行其它操作，或进入休眠状态。（3） 事务成功率（Transaction Success Ratio，以下简称 TSR）：指满足截止期的事务占所有事务的百分比。它用于衡量服务器满足事务及数据时效要求的能力。在实时环境下，如何减少访问时间和调谐时间并不是主要关心的问题。保证请求在一定的时间限制内得到满足是主要考虑的问题。通常在非实时系统中，数据传送失败是被忽略的。它基于的假设是获取数据时出现失败可以容忍，因为用户可以在下次广播时再次接受数据。而对于实时系统，这个假设可能导致请求超出截止期。所以在实时广播调度中，事务成功率是调度策略的一个重要性能评价指标。2.2 周期广播调度周期调度广播调度策略（静态调度策略）针对具有固定请求模式的应用环境，服务器已知数据请求模式。使用这种广播调度策略，服务器周期性地广播数据，用户被动地接收数据。周期广播调度方面的研究包括文献11-17等，其中最著名的是美国Brown大学的Acharya S.等人首先提出一种多盘广播（Multidisk Broadcast）11。将数据库的所有数据项按照访问概率分为 K 组，在一个广播调度中，同一个组内的数据项以相同的频率广播，而不同组的广播频率是不同的，数据广播可以比喻为K个具有不同传输率的磁盘（Disk），通过将访问概率高的数据项放在相对较快速的磁盘中，就可以降低所有请求的平均访问时间；此外，这种多盘广播机制还考虑了客户机上的缓存问题，利用预取和缓存技术来进一步提高用户访问空中数据的性能。但是，多盘调度机制缺乏可操作性，其设备参数必须由手工确定，且无章可循；而且，他们没有考虑数据广播的调谐时间优化问题，因此无法有效支持电源有限的嵌入式设备。国防科技大学的周兴铭院士等人提出了启发式多盘调度算法（Heuristic Multidisk，HMD）15, 16。采用Zipf 启发式策略将数据项分割到K个具有不同广播频率的盘中，并根据各盘平均访问概率的平方根之比确定其相对广播频率。虽然HMD算法由计算机自动确定数据项到各盘的分配以及各盘的相对频度，但仍需人工确定盘数。复旦大学孙未未博士提出了朴素逼近调度算法（Naive Approach Schedule Algorithm，NASA）17。在指定的广播周期长度内，首先计算出最接近理论最优值的每个数据项的广播频度（整数）；然后根据得到的广播频度尽可能均匀地把数据项组织成一个完整的广播调度。NASA 算法中只有广播周期一个输入参数，保证了对于每个数据项其最大平均访问时间不超过二分之一广播周期。但是同样地，NASA 算法没有考虑数据广播调谐时间的优化问题。2.3 按需广播调度在按需广播调度策略（动态调度策略）下，移动客户首先提出数据请求，服务器考察没响应的所有请求，按照一定优先级计算方式选择下一个广播的数据项。按需调度和静态调度的差别是，它的一个核心研究课题是确定数据项广播的优先次序，即下一个广播周期中应该广播哪些数据项。动态数据广播调度算法的研究主要包括：Aksoy D.提出FCFS（First-Come-First-Served）调度算法，按访问请求的时间顺序广播数据项18。由于只考虑访问请求的时间，而不考虑对数据项访问概率的差别，所以平均性能较差。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.提出RxW算法，它结合MRF和FCFS 算法的优点，根据当前请求队列的状态调度数据项22。Xuan P.提出EDF（Earliest Deadline First）算法，把具有最小截止期的数据项优先广播。EDF-BATCH算法在EDF算法的基础上考虑相同数据项的处理23。这些动态数据广播调度算法在确定一个数据项是否编入广播调度中时，仅依据数据的单一特征，没有一个意义明确的优先级计算模型。并且均没有考虑一个请求很长时间得不到响应时的处理，只提到采取一些措施来减少这种情况发生的概率。而不对很长时间得不到响应的请求做出必要的处理，允许无限等待的出现，在实时环境下是无法忍受的。针对以上缺点，Sun W.W.提出LDCF（Largest-Delay-Cost-First）算法24。通过对每个数据项计算把它延迟到下一个周期广播所增加的开销，以此作为每个数据项的优先级，按优先级确定参与广播的数据，然后根据访问概率调度数据。2.4 混合广播调度混合广播结合了静态广播和动态广播的优点。在混合数据广播中，上行信道用于传输在广播程序中没有被满足的用户数据访问请求；下行广播带宽分为静态广播和动态广播两部分，其中静态广播周期地广播“热点数据”，动态广播根据用户需求动态地广播数据。混合数据广播算法的研究主要有：Xuan P.提出BoD广播模型，将下行广播带宽分为两部分：一部分周期地广播热点数据，另一部分根据移动客户需求动态广播23。BoD模型中明确考虑了数据项的最低响应时间限制，但静态广播和动态广播的带宽分配是固定不变的，不能随工作量的变化而动态调整。Jesus F.C.提出一个自适应混合数据广播策略10, 25，在静态广播和动态广播中分别应用 PINOPT 算法26, 27和EDF算法广播数据，以尽可能多地满足用户对数据的最低响应时间限制要求。此算法根据系统工作量动态地分配静态和动态广播带宽，以使得用户平均等待时间最短和请求失败率最低为目标。但算法通过产生大量的冗余数据来尽可能地满足用户对数据请求的时限要求，信道利用率较低，用户的平均访问时间较长。Hu J.H.提出一种混合数据广播策略28。将移动用户分成普通用户、联机请求用户和优先级用户三类，其中普通用户只能被动地接收广播数据，联机请求和优先级用户可通过上行信道提出数据访问请求，优先级用户拥有系统资源的最高使用权。此算法通过区分各类用户对信道的使用权限来获取低的平均访问时间。混合数据广播调度策略的研究关键是如何根据系统负荷，自适应地分配下行信道的带宽。文献293031对移动计算环境中信道的分配进行了详细的研究。Lee W.C.将信道的使用分为三种方式：所有信道专用于数据广播、专用于用户按需请求和混合使用，并提出应根据系统工作量选择合适的信道使用方式3031。通过比较这三种信道分配方式的优缺点，Hu Q.L.提出一个动态信道分配算法，以获得系统最优的信道分配方案，和最小的用户访问时间30。2.5 多数据项的广播调度以上列举的文献均假设移动客户任一时刻只访问广播信道中的一个数据项，即单数据项广播。但在很多应用中，移动客户需要同时访问广播信道中的多个数据项，这就是多数据项广播。多数据项广播调度能减少移动客户与服务器之间的通信，有效地节约上行信道的带宽。Lee G.L.提出了基于数据访问图的调度策略，该策略首先构造数据访问图，然后计算数据项的加权距离，根据加权距离合并数据访问图的顶点，直到合并成一个顶点为止，合并顶点的顺序即为调度数据项的顺序32。Lam K.提出EQSD（Equal Slack Data）和RP（Request Proportion）算法33。明确考虑了事务包含的数据项数目和定时限制，以使得请求失败率最低和平均响应时间最短。但算法均没有考虑对用户重复申请数据项的处理。Yuen J.C.H.在单数据项广播调度算法的基础上进行改进，提出RTAHB调度算法34。此算法采用混合广播模式，根据系统工作量自适应地分配广播带宽。但算法通过广播冗余数据项来满足用户对数据的定时限制要求，信道利用率较低，用户的平均访问时间较长。Huang J.L.通过分析多信道广播环境中多数据项广播的特性，得出平均访问时间的理论特征，采用遗传算法来产生数据广播程序3536。但遗传算法时间复杂度和空间复杂度大，不能较好地适用于实际应用。2.6 基于事务的调度基于事务的调度指以事务存取的数据项集合作为完整的广播调度单位，只有当事务存取的多个数据项全部调度成功时，事务才调度成功。主要研究有：刘云生提出EDF-T（Earliest Deadline First for Transaction）、HUF-T（Highest Urgency First for Transaction ） 和HCF-T（ Highest Contribution First for Transaction）调度算法37。这些算法考虑了事务包含的数据项数目和时间限制对广播调度的影响，有效地保证了事务调度的成功率，适合于实时系统的数据广播。但是它们均没有考虑如何减少用户的平均访问时间。Chung Y.D.提出QEM方法，它以访问概率为基准，以贪心法扩展数据请求中的所有数据项，其主要思想是将一个客户申请的所有数据项尽可能地放置在一起调度来减少平均访问时间38。Lee G.L.提出改进的QEM算法，通过放松QEM的两个约束条件，获得了比QEM算法更好的性能32。Chang Y.I.提出改进QEM算法，通过应用关联规则挖掘技术（Mining Association Rules Technique），将相关程度高的数据项尽可能地一起调度来获得低的平均访问时间39。QEM及其改进算法应用查询距离（Query Distance）来求得数据请求的访问时间，并将事务存取的多个数据项作为整体进行调度，能获得较低的平均访问时间。但它们没有考虑用户对数据的时效要求，不能很好地适应实时数据广播调度。2.7 小结本章首先给出了调度策略性能的评价指标，然后概述了近年来国内外学者对广播调度策略的研究情况，并且将这些研究按调度模式进行了横向分类，按调度数据项的数目多少进行了纵向分类。本章定性给出了这些研究的性能评价，及其适用范围。453 实时数据广播模型在移动计算环境中，数据分发方式可以分为三种， 即纯PULL方式 （ Pure-Pull-Based）、 纯PUSH方式（Pure-Push-Based）和混合（Hybrid）方式。基于这三种方式，存在三种数据广播模式，分别为周期广播模式、按需广播模式、混合广播模式。其中，混合广播模式综合考虑了数据的实时性要求，以及数据的请求频率等数据特性，从而在实时环境下，能够表现出更高的系统性能。本文即是提出一种基于此模式的数据调度策略。本章给出一种实时数据广播模型，以供调度策略的实施。3.1节首先给出数据广播模式的分类；3.2节介绍实时数据的特征，如实时性、请求频度、关键性等特征；3.3节在综合考虑这些数据特征的情况下，给出一种实时环境下的数据广播模型；3.4节给出本文在广播技术研究中的一些系统假设。3.1 数据广播模式3.1.1 周期广播模式在基于PUSH技术的周期数据广播模式中， 服务器利用广播信道周期地广播既定数据，移动客户通过索引或其它方式监听广播信道，以获取所需的数据。由于移动客户不能向服务器提出数据请求，而只能被动地接收数据，因此该模式又被称为静态数据广播11。这种模式在许多应用中是很适用的，如股票证券信息发布、天气信息发布、城市交通信息发布等等。这些应用的共同特点是数据的请求模式具有相对的稳定性，并且广播服务器在系统启动之前，就已经获取这些请求模式。但这种模式却不适合动态实时的系统应用，因为系统对数据的选择是在服务器端进行的，它并不考虑移动客户对数据的实际需求特征，更不会考虑这些需求的变化，同时移动事务及数据的实时特征也不会得到有效满足，所以在实时环境下，这种模式必然带来较大的事务失败率。3.1.2 按需广播模式按需数据广播结合 PULL 和 PUSH 技术，它将信道划分为上行和下行两个信道，其中上行信道带宽较低，用于传送移动客户的事务及数据请求，下行信道用于服务器广播这些响应。由于服务器根据移动客户的请求，动态的选取广播的数据，因此该模式又被称为动态数据广播40。在应用该模式的广播系统中，事务及数据的实时特征可以通过上行信道到达服务器，广播服务器可以根据这些数据特征来更加合理地进行数据调度，从而能够有效地降低实时事务的失败率。在按需广播模式中，每个调度数据只广播一次，它并不考虑数据的请求频率等信息，从而不能满足将来事务的数据请求，即不能有效的将数据请求满足在请求发出之前。在系统负荷较大的情况下，事务的失败率仍然较高。3.1.3 混合广播模式混合广播模式中上行信道的用途与按需广播的相同，用于传送移动客户的事务及数据请求。不同点是下行信道被分为周期广播和按需广播两部分。信道带宽分配如图3.123所示。上行信道下行信道周期广播按需广播图3.1 混合广播模式的带宽分配该模式的最大特点是通过上行信道收集移动客户的动态数据请求信息，并以此为依据，不断地调整周期广播的序列内容，从而尽可能地多满足最多用户的数据访问需求，以此来减少用户与服务器之间的通信。而对于不能在周期广播中满足的数据请求，将在按需广播时段广播。周期广播的采用既可以减少上行信道的负荷，又能最大限度地利用下行广播的带宽，使广播优势发挥得最好。但混合数据广播的实现比周期数据广播和按需数据广播更加复杂。具体有以下两个难点：（1） 如何分配周期广播和按需数据广播的带宽，从而使信道达到最大的利用率，以及达到最高的事务成功率。因为数据的请求模式等数据特征会随着时间的变化而动态变化，所以优良的混合广播调度策略应该可以基于这些变化，动态地调整带宽的分配比例。（2） 如何获取有效的数据请求模式。由于移动客户的部分数据请求在周期广播中已得到满足，所以这些请求可能不会到达服务器，从而服务器也无法获取有效的数据请求模式，导致数据的请求模式不再有效，进而影响后继周期广播的数据调度。一般使用采样技术来获取这些“热点数据”的请求模式。3.2 实时数据的特征实时数据库中数据具有丰富的类型特征，如图3.241所示，这些不同特征的数据在移动环境中要求有不同的管理机制。数据特征实时性存取频率关键性持久性非实时实时短有效期长有效期高频低频关键非关键临时永久图3.2 实时数据库系统中的数据特征实时数据与非实时数据：传统数据库系统中的数据属于非实时数据，这种类型数据时间的流失不影响数据的合法性。实时数据具有一个外部有效期 evi（External Valid Internal）37，数据仅在此期间内有效。当 evi 很长时称为长有效期数据，当 evi 很短时称为短有效期数据。数据的时限由数据的本身有效期和事务的时限决定。设 Dvi 为数据的有效期，Tvi 为事务的时限，则用户要求的数据的有效期 Devi = DviTvi37。高频数据和低频数据：高频数据即通常所说的热点数据，这类数据由于经常被移动客户请求，应将他们缓存在移动主机中，或通过广播发送。而低频数据则可在需要时临时传送。关键数据与非关键数据：关键数据对应着高优先级，应优先被调度。持久性数据与非持久数据：持久数据是要进行长久保存和归档的数据，这类数据经常被许多移动客户请求，因此当在移动客户上产生或更新后，必须提交给服务器保存。以上各种数据特性可以交叉组合，从而使移动实时数据库中数据具有复杂性，实时数据广播模型一定要有利于反映数据实时性、优先级以及存取模式等特性。3.3 实时数据广播模型在1.2节所述的嵌入式移动实时数据库系统模型中，一个无线广播单元由一个移动支持基站（MSS）和由该MSS覆盖的所有移动客户（MC）构成。移动客户与MSS通过无线信道通信，MSS即为广播服务器。每个无线广播单元具有广播的独立性。本文的研究只基于一个无线广播单元，本文忽略数据及事务的分布等因素对广播调度的影响。文献37提出一种实时数据广播模型，移动客户利用上行信道向广播服务器提出数据请求。广播服务器响应用户请求，将移动客户所需数据组织在广播通道中，利用下行信道广播数据。该模型的设计基于按需广播模式，它不仅识别移动客户提出的请求，同时将数据以广播的方式发布，发挥了广播通信的优势，使通信带宽具有可伸缩性。结合文献37给出的模型，本文提出如图3.3所示的实时数据广播模型，该模型采用混合数据广播模式。广播服务器在下行信道的周期广播带宽中，广播“热点数据”，在按需广播带宽中响应移动客户的实时数据请求。周期广播 | 按需广播接收调度请求队列就绪队列广播数据请求数据库数据请求模式集图3.3 实时数据广播模型信道该实时数据广播模型分为接收、调度和广播三个模块。接受模块负责接收移动客户的数据请求，将这些请求按照截止期或其它数据特征排队于请求队列中；调度模块负责根据当前请求队列数据以及数据请求模式来调度数据，并将被调度数据存储在就绪队列中，调度分为周期广播调度和按需广播调度；同时调度模块根据请求队列数据来更新数据请求模式（通过采样技术完成）；广播模块负责周期性地广播就绪队列中的数据。一个有效的数据广播模型不仅要满足用户对数据的时间限制要求，还要利用数据广播技术分发数据，有效地利用通信带宽，满足最多用户的数据需求。图3.3所示的广播模型的具有以下优点：（1） 采用混合数据广播模式：用户通过上行信道上传请求，从而能够使服务器获取事务及数据的时间限制，进而能够更好地满足这些时间限制；服务器通过下行信道周期性的广播数据，从而发挥了广播通信的优势，使通信带宽具有较大地伸缩性。（2） 采用数据请求模式集：调度模块根据这些请求模式能够更加合理的调度数据，广播“热点数据”，以满足更多用户的数据需求。（3） 上行信道，数据请求模式集，下行信道三者形成一个良性互动的生态圈：服务器根据上行信道的数据请求来更新数据请求模式集，以使这些模式趋向于实际模式；下行信道的周期广播根据这些请求模式生成，从而使数据调度具有较强的合理性；有效的周期广播能够极大地满足移动客户的数据需求，从而降低了上行信道的负荷。3.4 研究中的假设为了便于研究，对广播模型及广播环境作了一些限制，下面是一些基本的假设：（1） 移动客户对广播数据访问的独立性：服务器向移动客户广播时所基于的通信网络具有固定的广播能力，即被广播的数据对所有的移动客户机都是可同时访问的，各个移动客户之间互不干扰。并且移动客户的前后数据请求具有相互独立性。（2） 广播数据格式的一致性：广播数据的最小单位是数据项，且所有被广播的数据项都是等长度的。在实际应用中，这些数据项可以是关系数据库中的记录、面向对象数据库中的对象，或者是数据库中的一个存储页面。（3） 广播数据项的自我识别性：即移动客户通过收任意一个数据项可以知道它是不是自己所要访问的数据项。这可以通过在每个广播数据项之前插入适当的头标识来实现。（4） 广播数据项以主键标识其唯一性：即每个广播数据项拥有一个主键，它能够唯一地标识一个数据项，并且移动客户机总是根据主键来访问数据广播中的数据项。（5） 广播数据项地址的确定：定义一个数据项在数据广播中的地址为该数据项在广播信道中到达的偏移时间。假定数据广播信道具有固定的网络带宽，且广播一个数据项的时间为单位时间 l，则当移动客户从一个广播周期起始处开始接听时，后续每个广播数据项的地址依次为 1，2，3，。（6） 数据库的一致性假设：数据库的一致性以一个广播周期为单位，即：如果在一个广播周期内发生了数据库的更新，则更新结果将在下一个广播周期内反映出来。3.5 小结本章首先介绍了近年来在数据广播技术研究中流行的数据广播模式，然后给出实时环境中数据的新特征，最后提出一种基于混合广播模式的实时广播模型，该模型能够综合考虑了数据的实时性及请求频度等特征，最后本章给出数据广播研究中的一些系统假设。实时数据广播模型的提出，为本文进一步的调度策略研究提供有效的基础设施。4 一种改进的自适应混合广播调度策略在实时环境下，数据和事务往往具有时间限制，超过请求的时限，事务将会夭折，数据将会贬值，有时甚至会带来灾难性的后果；同时，在实际应用中，数据一般具有一定的请求模式，广播调度应该充分利用这些模式，广播“热点数据”，以满足更多用户的数据需求。由本文前述可知，混合广播调度结合按需广播与周期广播的优点，能够较好地满足这些应用需求，但它的实现面临如下两个难点：（1）如何高效合理地分配周期广播和按需数据广播的带宽比例；（2）如何获取有效的数据请求模式。文献10提出一种自适应混合广播调度策略TC-AHB(Tim