论文导读：最初的流媒体调度算法的基本思想是：当用户发出一个请求后，服务器尽快产生一个包含连续媒体对象(视频、音频)的完整节目流(称为Regular流)来满足用户。这是最早的一级流调度算法。但是Patching算法只是实现了利用补丁流来满足用户的二级流调度的思想，并没有采用适当的技术来处理补丁流，所以在一定程度上限制了算法性能的提升和效率的提高。因此考虑对Patching算法进行改进，利用上述分组融合策略来处理Patching流，将时间间隔在分组窗口内的Patching流利用融合技术进行合并，提高系统中Patching流的利用率，实现三级调度的思想。
关键词：流媒体，调度算法，分组融合，补丁流
0 引 言
自从2O世纪9O年代初“流媒体”概念诞生以来，流技术得到了飞速的发展。VOD视频点播应用是最常用的也是最重要的一种流媒体发布模式，流调度技术又是大规模VOD视频点播系统的关键技术，其性能好坏直接影响系统的服务能力和用户的收看效果[1]。
针对用户大量且频繁的访问少数“热门”连续媒体信息的情况, 尤其是当用户请求比较集中且强度比较大时，系统可能会因为流信息数目过多而导致网络阻塞或资源的浪费。为了减轻服务器和网络的负载, 各研究机构提出了多种利用Multicast技术的流调度算法.在这些算法中，Patching算法较其它算法具有明显的系统性能提升[2]。
1 Patching算法现状分析
最初的流媒体调度算法的基本思想是：当用户发出一个请求后，服务器尽快产生一个包含连续媒体对象(视频、音频)的完整节目流(称为Regular流)来满足用户。有多少个用户请求，系统中就会产生多少个Regular流。这是最早的一级流调度算法。在这类算法中，每个用户都是由一个独立的流信息来满足的，相互没有任何影响，但是随着用户请求数目的增多，系统中的Regular流数目急剧增加，流信息的重复部分也大大增多，加大了系统的负担，造成资源浪费和网络阻塞。论文大全。为了缓解这一问题，Patching算法诞生了。
Patching算法的基本思想是:让用户同时最多接收两个连续媒体流,并提供一定的缓冲区，达到多个用户共享网络数据的目的.如图1 所示,令在t0 时刻生成一个Regular流,播放长度为V。用户缓冲区中可以缓存播放时间为B 的数据。新的用户请求在t 时刻到达,如果(t- t0)<B ,则生成一个包含媒体对象开始部分[0,t- t0]的片断流(称为Patching 流),长度为t-t0。用户同时接收Regular流和Patching流的数据,并且立即播放Patching流的数据,将Regular流的数据暂存到缓冲区。当用户播放完Patching流后,随即播放缓存在缓冲区的Regular流数据,同时将接收到的Regular流数据不断加入缓冲区。这样,只要生成一个Patching 流, 就可以达到让用户共享原有的Regular 流的目的。
图1 Patching算法
Fig. 1 Patchingalgorithm
Patching算法实现了一个Regular流带多个Patching流来共同满足多个用户的思想，是目前较先进、性能较好的一种流媒体调度算法。但是Patching算法只是实现了利用补丁流来满足用户的二级流调度的思想，并没有采用适当的技术来处理补丁流，所以在一定程度上限制了算法性能的提升和效率的提高。
据资料表明，对于大范围的用户请求强度变化, Patching流承担了绝大多数的节目点播请求,从图2 可以看出,在不同的用户请求强度情况下,若缓冲区大小为5min,在一个提供1000个节目,具有1200个节目发送通道的系统中,Patching流满足了约70%的用户请求[3]。论文大全。当用户请求比较集中且强度比较大时，想要满足这么多的用户，Patching流的数目就会不断增加，系统可能会因为流数目过多而造成网络阻塞或资源的浪费，甚至影响系统的吞吐量和效率。同时因为视频文件播放时占用的带宽较大（如MPEG1为1.5M/S,MPEG2为4M/S-6M/S），而磁盘和网络的带宽都是有限的，想要支持更多的用户，就有必要采取一定的策略。针对这一问题，本文通过对Patching算法的研究与分析，充分考虑系统中补丁流的重要地位，结合分组融合策略，对具有二级流调度思想的Patching算法进行改进，提出了一种基于分组融合策略的三级流调度算法，使用户请求撤销率降低、用户平均等待时间缩短，进一步提升算法的性能。
图2 Patching算法性能分析
Fig.2 Theanalysis of Patching algorithm’s capability
2 基于分组融合的三级流调度算法
2.1 分组融合策略
分组融合策略是分组策略和融合策略的结合，即利用分组策略来加快融合速度，同时利用融合策略来缩短用户的等待时间。该策略同时设有分组窗口和融合窗口。分组窗口是一个时间段,若用户请求在规定的时间间隔之内,则将它们分为一组，然后选择相同的请求分配一个共同的信道,共享一个相同的视频流。融合窗口是一个帧数值,在这个值里,两个相同的视频流发出时,让前一个降低播放速度,或(和) 后一个提高播放速度,则在某一个时间点称为时间融合点(或某一帧上称为空间融合点) 达到完全融合,然后多余的一个流可以释放。播放速率的改变可以通过丢弃或增加帧到原始的流中来实现(NTSC 标准的视频流要求30帧/ 秒,改变帧的数目而不引起用户注意意味着每秒可增加或丢弃1. 5 帧～2 帧)。丢弃或增加帧可以通过前面或后面的帧延长或缩短播放时间来代替,以减少两者之间的不连续性。当两个流融合后,再让它们以正常的速度播放。若在融合窗口里没有融合,即视为没有融合的必要,不再融合。分组与融合联用,可以有效地减少I/ O带宽要求而不用增加过多延迟。其整个过程如图3所示：
1/2 1 2 下一页 尾页 |
