论文部分内容阅读
数据广播是一种被广泛接受的用于动态和可扩展的无线信息分发的方法。随着数据广播系统中移动用户和实时应用数量的快速增长,来自客户端的实时数据需求变得更加棘手。而且,大规模数据需求导致服务器端需要大规模数据库。因而,基于推的广播调度程序不能获取最优的性能。因为这种广播是基于历史的数据访问统计数据或者预定义的请求配置文件的静态的数据广播。因此,按需广播比基于推的广播更适合此种情况。然而,按需广播需要在线的数据调度。这是很难获得最优或接近最优的性能的。其次,在一些紧急的应用中,比如道路交通导航系统,客户端可能同时请求不止一个相互依赖的数据项。因此,对于实时按需数据广播系统,这样的多数据项请求在有截止期限制的条件下将使得数据调度算法的设计更为复杂。第三,虽然已有的多信道结构增加了满足大数据需求的可用带宽,但是因为一个客户端在一个时间仅能从一个信道获取一个数据项,所以多信道结构也增加了客户端在多信道之间的带宽共享的难度。基于以上分析,如何设计一个好的数据调度算法是实时按需数据广播系统的核心部分。随着实时应用的增加,在调度多数据项请求时最小化请求截止期错过率已经成为一项重要的任务。在本文中,我们证明在单信道和多信道数据广播环境下调度实时多数据项请求的NP难度。而且,我们分别针对单信道和多信道结构提出两种基于profit的调度算法,PVC和SSA。两种算法都利用了我们提出的两个概念。一个是需求数据项的‘’profit"(利润),另一个是待满足请求的"opportunity cost"(机会成本)。据我们所知,这是第一次在按需广播调度中引入来自经济学中的机会成本。根据由PVC做出的调度决策,SSA将调度到的请求中的数据项分配到可用信道上。总体上,单信道调度中PVC在请求截止期错过率方面优于其它算法。多信道调度中SSA在请求截止期错过率方面随着信道数的增加比其它算法具有更大的优势。此外,在总带宽相同条件下,仿真实验结果表明,在单信道环境下调度比在多信道环境下调度具有更好的实时性能,即请求截止期错过率。这启发我们通过理论建模比较这两种调度。理论结果表明,在总带宽相同条件下,单信道调度比多信道调度有更好的平均周转时间。据我们所知,虽然在有线网络和无线网络中已经有多种面向连接的接入控制的工作,但是在实时数据广播系统中尚未有接入控制的探索。在无线的移动网络环境中,由于数据广播一次响应能够满足包含相同数据项的众多请求,这一潜在优势使得它成为越来越受欢迎的信息分发方法。此外,数据广播能够容纳任意多的具有相同兴趣的客户端。在实时应用中,所有请求有截止期限制,即错过截止期即意味请求的失败。然而,在没有接入控制条件下,客户端必须等待接收它们所需要的数据项直到请求截止期失效。如果清求最终失败,客户端电池的能量和时间都将被浪费。此外,在请求提交时,客户端不知道它们提交的请求能否得到满足,这将降低客户体验和服务吸引力。为了减少失败请求的不必要的等待时间并提供客户端一定的QoS(服务质量)保证,我们在实时数据广播系统中引入广播接入控制。请求提交后,请求的数据项将被分配到信道中,如果分配不可行,清求将提前被拒绝。然而,通过构建广播接入控制的子问题,即团问题,我们证明以最大化带宽共享为目标的实时多数据项请求的广播接入控制问题是NP(非确定性多项式,non-deterministic polynomial)难的问题。之后,我们提出一个简化的接入控制算法,称为数据项层接入控制(Item Level Admission Control, ILAC)。在接入控制之后,为了达到带宽共享的最大化,信道分配问题被模型化为二部图的最大带权匹配问题并由经典的原始对偶方法解决。此外,利用动态规划技术优化了信道间的跳转代价。以上两点构成我们提出的基于匹配的信道分配算法(Matching Based Allocation, MBA)。仿真实验验证了我们所提的接入控制和信道分配算法的优势。