实时数据广播调度与索引组织策略研究硕士学位毕业论文.docx
《实时数据广播调度与索引组织策略研究硕士学位毕业论文.docx》由会员分享，可在线阅读，更多相关《实时数据广播调度与索引组织策略研究硕士学位毕业论文.docx（71页珍藏版）》请在冰点文库上搜索。
实时数据广播调度与索引组织策略研究硕士学位毕业论文
硕士学位论文
实时数据广播调度与索引组织策略研究
AThesisSubmittedinPartialFulfillmentoftheRequirements
fortheDegreeofMasterofEngineering
ResearchonReal-timeDataBroadcastSchedulingandIndexOrganizingStrategy
Candidate:
ZhouMingjie
Major:
ComputerSoftwareandTheory
Supervisor:
Prof.LuYansheng
HuazhongUniversityofScienceandTechnology
Wuhan430074,P.R.China
May,2008
独创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。
尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。
对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。
本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名：
日期：
年月日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：
学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。
本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
保密□，在_______年解密后适用本授权书。
本论文属于
不保密□。
（请在以上方框内打“√”）
学位论文作者签名：
指导教师签名：
日期：
年月日 日期：
年月日
摘要
在嵌入式移动实时数据库系统环境中，为了支持大量移动客户端并发访问服务器上的数据，人们提出了数据广播技术。
数据广播充分利用移动环境中网络带宽的非对称性，周期性的将热点数据广播出去，有效地解决了移动端用户规模庞大的问题。
数据广播技术的研究主要包括广播模式、广播调度、广播索引和广播结构，其中大量的研究主要集中在广播调度和广播索引两方面。
数据广播调度可分为传统数据广播调度和实时数据广播调度，实时数据广播调度需要着重考虑数据的时间特性。
索引技术可分为树索引、哈希索引和混合索引。
树索引能大幅减少调谐时间，获得广泛的研究。
实时数据广播调度策略大多基于优先级的调度思想。
公平的实时数据广播调度策略（FairSchedulingforReal-timeDataBroadcast，FS-RDB）从数据项生产力最大化的角度出发，综合考虑了数据项的实时性、数据请求数目和公平性。
其中生产力的计算代价较高，可以用近似值计算公式进行优化。
广播索引技术是为了减少系统的调谐时间，降低移动端的电源消耗。
通过分析调谐时间的计算公式，设计了次优查找索引树（NearlyOptimalSearchIndexTree，NOSIT）的构造方法。
该算法借鉴了次优查找树的构造思想。
索引树的中间结点也可索引数据项，减少了索引树空间开销，因此减小了数据的访问时间。
数据广播调度策略和广播索引技术的仿真试验结果表明，公平的数据广播调度策略FS-RDB的数据请求成功率明显高于EDF-T和PRDS，事务请求成功率变化平缓，抗压能力较强。
次优查找索引技术NOSIT的调谐时间小于B+树，在数据访问偏斜的情况下更为明显。
关键词：
嵌入式移动实时数据库，数据广播，公平的实时数据广播调度，次优查找索引树
Abstract
Intheenvironmentofembeddedmobilereal-timedatabasemanagementsystem（EMRTDBMS）,databroadcasttechnologyisprovidedtosupportalargenumberofmobileclientsaccessingdatainserverconcurrently.Databroadcastefficientlyutilizethebandwidthasymmetryofmobilenetwork,broadcastperiodicallythepopulardataandsolvetheproblemofnumerousclientsavailably.Databroadcastresearchmainlyfocusesonbroadcastmode,broadcastscheduling,broadcastindexandbroadcaststructure.Amongthesetopics,mostresearchconcernthebroadcastschedulingandbroadcastindex.
Databroadcastschedulingincludestraditionaldatabroadcastschedulingandreal-timedatabroadcastschedulingandtimeconstraintsshouldbeespeciallyconsideredinreal-timedatabroadcastscheduling.Broadcastindexconsistsoftreeindex,hashindex,hybridindex.Treeindexcanefficientlyreducetuningtimeandbringonmuchresearch.
Mostreal-timedatabroadcastschedulingarebasedonpriority.Thefairschedulingforreal-timedatabroadcastisdesignedfromtheangleofdataproductivity.ItiscalledFS-RDBthatincorporatestheurgency,thenumberofpendingrequestsandfairness.Toreducethecomputationcostofdataproductivity,wegivetheapproximatecalculation.
Broadcastindexisdesignedtodecreasethetuningtimeandtoreducethepowerconsumptionamount.NOSIT（NearlyOptimalSearchIndexTree）isdesignedthroughtheanalysisoftuningtimeformula.Asthetargetisalmostthesamewithnearlyoptimalsearchtree,wecandesignthesimilaralgorithm.Themiddlenodealsocanindexdataitem,sothespaceconsumptionisreducedandaccesstimeisdecreased.
WeimplementaprototypesystemofdatabroadcastandapplythedesignedFS-RDBandNOSIT.ResultsshowthatDRSR（DataRequestSuccessRatio）ofFS-RDBishigherthanEDF-TandPRDSandTSR（TransactionSuccessRatio）ofFS-RDBchangessmoothlywithtransactioninterval.ThetuningtimeofNOSITislowerthanB+tree,especiallyindeclineddataaccessprobability.
Keywords:
EmbeddedMobileReal-timeDBMS,DataBroadcast,FS-RDB,NOSIT
目录
摘要………
Abstract
1绪论
1.1数据广播系统的体系结构
（2）
1.2数据广播的研究现状（4）
1.3本文主要研究内容与组织（8）
2数据广播调度和广播索引的基本理论和方法
2.1数据的广播调度策略（10）
2.2数据广播的索引技术（13）
2.3本章小结（17）
3一种公平的实时数据广播调度策略
3.1研究中的假设（18）
3.2实时数据广播调度的评价指标（19）
3.3公平的实时数据广播调度策略（22）
3.4调度策略的性能分析及改进措施（30）
3.5本章小结（31）
4基于次优查找树的数据广播索引策略
4.1数据广播索引策略的性能指标（32）
4.2次优查找索引树的设计（33）
4.3实时应用中索引树的改进措施（36）
4.4本章小结（39）
5仿真实验与性能分析
5.1仿真系统设计（40）
5.2性能评价指标（42）
5.3实验环境及参数设置（43）
5.4实验结果及性能分析（44）
5.5本章小结（47）
6结束语
6.1本文总结（48）
6.2未来展望（49）
致谢（50）
参考文献（51）
附录攻读学位期间参与的科研项目（55）
1绪论
无线通信网络、移动设备和互联网技术的迅速发展，使得传统的分布式计算进一步向无线领域延伸，出现了移动计算。
于是人们迫切希望移动终端能够在任何时候、任何地点访问任何数据，移动数据库在这方面的应用体现了其独特的优越性，受到了业界和学术界的重视。
移动数据库的应用非常广泛，有些特殊领域的应用对数据的处理提出了更高的要求。
交通信息系统、海上导航系统和股票交易系统等实时性应用普遍要求在移动环境下实现实时事务处理。
同时移动数据库系统的终端设备都是诸如掌上电脑、PDA、移动电话等嵌入式设备，因此我们一般称为嵌入式移动实时数据库管理系统（EMRDBMS）[1]。
嵌入式移动实时数据库系统是指支持移动计算的实时数据库管理系统，它涉及到数据库、实时系统、分布式计算和移动通信等多种技术，已经成为数据库领域新的研究热点。
嵌入式移动实时数据库的应用领域与基于固定网络的传统分布式计算环境相比具有鲜明的特点[2]，如计算平台的移动性、连接的频繁断接性、网络条件的多样性、网络通信的非对称性、规模的易变性、不可靠性、数据的实时性以及电源能力的有限性等。
由于移动终端经常处于断接状态，而且与服务器通信的网络带宽也很有限，因此要实现大规模移动用户随时随地访问数据的目标是一个真正的挑战。
在无线环境中，从服务器到移动终端的下行带宽大于从移动终端到服务器的上行带宽，而且移动终端接收数据的开销也小于发送开销。
即使移动终端处于断接状态无法向服务器发送消息的情况下，移动终端也可以选择接收从服务器发送的下行广播信息。
数据广播充分利用网络通信的不对称性，将热点数据通过无线信道以广播的形式向客户机发送，有效地解决了移动终端用户规模庞大的问题。
与传统的C/S联机数据请求方式相比，数据广播具有以下优点：
（1）良好的可伸缩性，广播的开销不依赖移动用户数量的变化而变化，以很小的代价支持大量的移动终端同时访问数据；
（2）节约有限带宽，从数据广播中取数据，减少移动终端与服务器的上行网络通信；（3）适应网络的断接性，通过数据广播，即使在断开时，也允许移动终端访问最新数据。
近几年来，人们对数据广播进行了深入的研究，在广播模式、广播调度、广播索引和广播结构等方面取得了丰富的成果。
本文主要讨论广播调度策略和广播索引技术。
1.1数据广播系统的体系结构
在移动计算环境中，通用的数据广播系统的体系结构[3]如图1.1所示。
它包括信息服务器IS（InformationServer）、移动服务基站MSS（MobileServiceStation）、固定主机FH（FixedHost）、移动客户MC（MobileClient）和通信网络。
固定网络连接固定主机、信息服务器和移动服务基站，它一般是WAN或其它有线网络。
无线网络的广播范围被划分成多个无线广播单元WBU（WirelessBroadcastUnit），WBU指一个MSS覆盖的领域。
当今网络技术趋向于采用更小的广播单元，一个地域被划分成更多的单元，从而MC需要更频繁地穿越不同单元的边界，不同广播单元可以有所交叉覆盖。
图1.1数据广播的系统模型
1.1.1信息服务器
信息服务器IS一般为固定结点，负责存储数据，维护有本地数据库LDB（LocalDatabase）。
服务器之间由高速的可靠互联网连接在一起，构成一个传统意义上的分布式数据库，服务器可以处理用户的请求。
另外在某些特殊环境中服务器可能出现在移动计算机上，通过无线网络与固定网络相连。
本文假定服务器位于固定结点，并且将固定网络中的所有信息服务器作为一个整体看待，不考虑信息服务器之间的同步问题。
IS维持本地数据的更新。
更新事务由传感器周期地或偶然地创建。
传感器捕获外部环境的实时状态的变化，然后传输给IS来维护数据库中数据与外部数据的一致性。
IS的数据更新特性包括更新频率和更新方法两个方面。
更新频率可分为频繁、普通和不更新三种；更新方法指IS中数据被更新后，通过什么方法告知用户。
常用的方式可向MC发送数据失效报告，或直接向MC发送最新数据。
本文的研究不考虑数据的收集和更新。
在以下论述中，如不特别说明，服务器均指移动服务基站MSS。
1.1.2移动服务基站
移动服务基站MSS也位于固定网路中，并具有无线通信的能力，用于支持一个无线广播单元WBU。
MSS可以和IS是同一台机器，同时具备数据存储更新和广播分发的功能。
MSS负责广播数据，因此也称为广播服务器。
它详细定义了MC接收数据的主要特征：
广播内容（BroadcastContents）：
一些广播系统中，广播内容是不变的，广播内容的值可被更新。
广播内容也可以根据用户的数据需求动态产生和替换。
存储桶容量（BucketSize）：
存储桶是广播程序中广播一个数据项的单位，在数据库内容的广播中一般以数据库的页面为单位。
广播磁盘结构（BroadcastDiskStructure）：
可分为平坦结构和非平坦结构（偏斜结构）。
其中平坦结构指在广播周期中各个数据项的出现频率相同。
非平坦结构与之相反。
广播周期（BroadcastCycle）：
分为周期广播和非周期广播。
数据库内容（DatabaseContent）：
广播的数据可以是数据库中的全部数据（全集），或部分数据（子集）。
数据项的放置（DataItemPlacement）：
静态调度中，不同的广播周期，所有数据项的调度顺序均保持不变。
动态调度则根据用户的需求动态确定数据项的广播顺序。
索引（Index）：
MC可通过索引信息知道在什么时间从广播信道接收自己想要的数据，从而在等待时转入休眠模式而节约移动计算设备的电池消耗。
1.1.3移动用户
移动用户MC一般为PDA、智能手机等嵌入式设备，处理能力和存储能力有限。
无线网络连接，经常与固定主机断接，且具有移动性（即可以出现在任何一个无线广播单元中）。
网络环境多变，一般MC与MSS的网络通道分为上行带宽和下行带宽，上行带宽较窄，可靠性较低，网络延时较大。
MC侦听广播信道，从MSS的广播序列中获取信息。
不同的广播系统设定不同类型的用户。
按参与性可将用户分成主动用户和被动用户，按优先级可分为高优先级用户和低优先级用户，另外还可分为缓存用户和无缓存用户，拥有反向信道（Backchannel）的用户和无反向信道的用户等。
1.2数据广播的研究现状
在图1.1所示的嵌入式移动实时数据库的系统模型中，移动客户MC和广播服务器MSS间的通信具有如下的特性：
在一个无线广播单元WBU内，从MSS到MC的下行通信带宽一般要远大于从MC到服务器的上行通信带宽。
而且MC从MSS接收数据的开销也远小于发送开销，在极端的情况下，即使是处于断接状态下（即无法向服务器发送消息）的MC也可以选择接收从MSS发送的下行广播信息。
因此，采用数据广播是解决移动实时数据库系统用户规模庞大和网络通讯非对称性等问题的一个有效的方法。
在数据广播中，有3个主要的性能衡量参数：
（1）访问时间（accesstime，也称为存取时间），它指从MC提出查询请求，到结果返回所需的时间。
访问时间一般作为系统响应时间的衡量标准；
（2）调谐时间（tuningtime）：
它指MC为了获得查询结果，用于侦听信道的时间。
MC侦听信道需要消耗电源，因而一般将该参数作为数据访问消耗电源的衡量标准；（3）请求成功率（requestsuccessratio，也称请求响应率）：
它描述MC的数据请求在有效期前得到满足的比率，它是实时环境下，广播系统负载能力的一个重要衡量标准。
近年来数据广播技术已引起了广泛的研究，针对上述性能参数的优化，主要研究方向分为以下四类：
广播模式，即MSS与MC之间的数据交互方式；广播调度策略，即MSS确定广播数据的选择策略和广播顺序；广播索引方式，即被调度数据在广播序列中的索引结构；广播结构即广播周期中数据和索引的组织形式。
1.2.1广播模式
数据广播模式是指MSS与MC之间的数据交互方式。
在传统的固定网络中应用较多的C/S和B/S模式都属于单播模式。
服务器与客户间的连接是一对一的关系，数据广播中服务器与客户间的连接是一对多的关系。
广播模式可以从很多角度加以划分，这里列出一些常见的模式类型，有些属于基本类型组成的混合类型。
根据客户端有无联机请求MSS端数据的分发方式可以分为PUSH方式、PULL方式、混合（Hybrid）方式[4,5]。
PUSH方式中MSS周期性广播既定的数据，不考虑MC的临时需求；PULL方式下客户向服务器发送数据请求，服务器相应用户请求并广播数据。
混合方式将PUSH和PULL方式相结合，因此也叫PP方式。
基于这三种分发方式产生了三种数据广播模式，分别为周期广播模式、按需广播模式（联机请求广播模式）和混合广播模式。
按照广播数据的更新情况可以划分为整体广播和更新广播。
整体广播将需要广播的数据全部广播出去而不考虑数据有无更新。
更新广播[6]只广播上一周期内更新的数据，这就存在没有更新时无数据广播的情况，需要广播一个空数据块表明该周期内无数据更新。
以上讨论的数据广播的下行通道都是基于单通道的，在实际应用中还存在一些多通道的情况，它将下行带宽划分成多个子通道。
文献[7]深入讨论了在多通道情况下数据的分配及其性能，另外Waluyo等人则研究了多通道中树型索引信息的划分类型[8]并对其性能进行了比较。
这类应用比较少见，本文其它地方讨论的数据广播的下行带宽都作为单通道来考虑。
1.2.2广播调度
广播调度是按照一定的顺序动态组织需要广播的数据，这直接影响MC对广播数据的访问时间。
访问时间是衡量数据广播系统性能的一个重要指标，设计时应根据具体的应用选择合适的广播调度算法。
移动实时应用环境中，数据有随时间变化的特性，移动用户的应用处理也有定时限制，因此对数据的存取也有定时限制，过了时的数据将不再是用户所需要的数据。
如股票数据、交通状况数据。
为了满足移动用户对数据需求的定时限制，不仅要求动态地组织广播内容，还要对广播内容进行合理的调度。
根据数据广播模式的不同，广播调度策略分为3大类：
周期广播调度策略，按需广播调度策略，混合广播调度策略。
本文将在第2章概述国内外学者在广播调度策略方向上的研究工作。
在第3章将提出一种公平的实时数据广播调度策略。
1.2.3广播索引
在数据广播系统的应用环境中，移动设备通过侦听信道的方式获取所需的数据，在侦听过程中需要不断的匹配数据，耗费了大量的电源。
如果为广播数据建立索引，则移动设备可以在所需的数据到达时侦听信道，而其他时候都处于休眠状态（dozemode）。
由于休眠状态只需消耗极少量的电源，因而该方法大大降低了移动设备电源的消耗。
在索引广播中，移动设备侦听信道的时间（调谐时间，tuningtime）与访问数据时需要遍历索引结点的数目成正比，问题就转换为如何减少平均访问的索引节点的数目。
传统索引技术一般采用简单的索引结构，这主要是因为在传统的文件系统中，访问索引的代价跟CPU，I/O操作相比小得多，建立复杂的索引结构对提高整体效率作用不大。
但在移动环境中，由于侦听信道是耗费电源的主要方式，因而为广播数据建立精巧的索引结构以降低侦听时间显得尤为重要。
在一个基于索引技术的数据广播环境中，数据访问的基本步骤包括：
（1）初次访问：
移动客户机访问广播信道，获取下一次索引的广播时间，然后转入休眠状态；
（2）搜索：
移动客户机在索引到达后转为活动状态，在索引中进行检索以确定所需数据的到达时间。
这中间可能要经过多步，和索引的设计有关。
然后进入休眠状态（3）访问数据：
当数据到达时转为活动状态，移动客户机访问广播信道，接收该数据。
广播索引技术大多在传统索引技术的基础上进行了改进，研究内容大致可分为树型索引、哈希索引和混合索引。
广播索引的具体设计思想将在本文第二章进行详细的叙述。
1.2.4广播结构
广播结构指索引和数据在广播信道中的组织形式，它决定了数据以何种结构发送给用户。
在带索引的数据广播系统中，客户端获取数据请求大致要经历四个时间段，具体过程如图1.2所示。
ATI（AccessTimeforIndex）指用户等待索引所需时间，TTI（TuningTimeforIndex）指用户收听索引所需时间，ATD（AccessTimeforData）指用户获取索引后到想要的数据开始广播所用的等待时间，CTD（CompleteTimeforData）指用户想要的数据开始广播到广播完成的时间。
索引在广播周期中的位置及索引的方式都将极大的影响系统的性能，文献[9]将数据广播结构归纳为六种，其中有些是考虑到多广播通道及数据联机请求等情况。
本文只考虑单通道的情况，按照索引的分布可将广播结构分为两种形式。
图1.2所示的广播结构中，索引在一个广播周期内只被广播一次。
索引位于广播的头部，因此数据请求首先要等待ATI单位时间获取索引信息。
最坏情况下ATI为整个广播周期。
为了避免这种情况发生，图1.3的结构中索引在广播周期中被广播若干次（假设为d次）。
在现实环境中，由于用户的数据访问模式不能被事先预测，所以要确定一个最优的d并不容易。
在基于概率的数据多盘调度中，可以将数据广播每个子
升级会员 