多信道数据广播系统的实时多数据项请求调度.pdf

《多信道数据广播系统的实时多数据项请求调度.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国科学技术大学博士学位论又多信道数据广播系统的实时多数据项请求调度作者姓名：学科专业：导师姓名：完成时间：吕劲松计算机应用技术陈恩红教授二。一二年五月UniversityofScienceandTechnologyofChinaAdissertationfordoctordegreeSchedulingRea1．．timeMulti·—itemRequestsinMulti—-channelDataBroadcastSystemsAuthor’SName"JingsongLvSpeciality：ComputerSoftwareandTheorySupervisor：

2、Prof．EnhongChenFinishedtime：May,2012中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论

3、文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。√公开保密——年作者签名：要幽导师签名：{＆2翌垒二摘要数据广播是一种被广泛接受的用于动态和可扩展的无线信息分发的方法。随着数据广播系统中移动用户和实时应用数量的快速增长，来自客户端的实时数据需求变得更加棘手。而且，大规模数据需求导致服务器端需要大规模数据库。因而，基于推的广播调度程序不能获取最优的性能。因为这种广播是基于历史的数据访问统计数据或者预定义的请求配置文件的静态的数据广播。因此，按需广播

4、比基于推的广播更适合此种情况。然而，按需广播需要在线的数据调度。这是很难获得最优或接近最优的性能的。其次，在一些紧急的应用中，比如道路交通导航系统，客户端可能同时请求不止一个相互依赖的数据项。因此，对于实时按需数据广播系统，这样的多数据项请求在有截止期限制的条件下将使得数据调度算法的设计更为复杂。第三，虽然已有的多信道结构增加了满足大数据需求的可用带宽，但是因为一个客户端在一个时间仅能从一个信道获取一个数据项，所以多信道结构也增加了客户端在多信道之间的带宽共享的难度。基于以上分析，如何设计一个好的数据调度算法是实时按需数据广播系统的核心部分。随着实时应用的增加，在调度多

5、数据项请求时最小化请求截止期错过率已经成为一项重要的任务。在本文中，我们证明在单信道和多信道数据广播环境下调度实时多数据项请求的NP难度。而且，我们分别针对单信道和多信道结构提出两种基于profit的调度算法，PVC和SSA。两种算法都利用了我们提出的两个概念。一个是需求数据项的“profit”(利润)，另一个是待满足请求的“opportunitycost”(机会成本)。据我们所知，这是第一次在按需广播调度中引入来自经济学中的机会成本。根据由PVC做出的调度决策，SSA将调度到的请求中的数据项分配到可用信道上。总体上，单信道调度中PVC在请求截止期错过率方面优于其它算法

6、。多信道调度中SSA在请求截止期错过率方面随着信道数的增加比其它算法具有更大的优势。此外，在总带宽相同条件下，仿真实验结果表明，在单信道环境下调度比在多信道环境下调度具有更好的实时性能，摘要即请求截止期错过率。这启发我们通过理论建模比较这两种调度。理论结果表明，在总带宽相同条件下，单信道调度比多信道调度有更好的平均周转时间。据我们所知，虽然在有线网络和无线网络中已经有多种面向连接的接入控制的工作，但是在实时数据广播系统中尚未有接入控制的探索。在无线的移动网络环境中，由于数据广播一次响应能够满足包含相同数据项的众多请求，这一潜在优势使得它成为越来越受欢迎的信息分发方法。此

7、外，数据广播能够容纳任意多的具有相同兴趣的客户端。在实时应用中，所有请求有截止期限制，即错过截止期即意味请求的失败。然而，在没有接入控制条件下，客户端必须等待接收它们所需要的数据项直到请求截止期失效。如果请求最终失败，客户端电池的能量和时间都将被浪费。此外，在请求提交时，客户端不知道它们提交的请求能否得到满足，这将降低客户体验和服务吸引力。为了减少失败请求的不必要的等待时间并提供客户端一定的QoS(H艮务质量)保证，·我们在实时数据广播系统中引入广播接入控制。请求提交后，请求的数据项将被分配到信道中，如果分配不可行，请求将提前被拒绝。然而