一种基于分组融合策略的三级流调度算法(图文)

1、一种基于分组融合策略的三级流调度算法(图文)论文导读：最初的流媒体调度算法的根本思想是：当用户发出一个请求后，效劳器尽快产生一个包含连续媒体对象(视频、音频)的完整节目流(称为Regular流)来满足用户。这是最早的一级流调度算法。但是Patching算法只是实现了利用补丁流来满足用户的二级流调度的思想，并没有采用适当的技术来处理补丁流，所以在一定程度上限制了算法性能的提升和效率的提高。因此考虑对Patching算法进行改良，利用上述分组融合策略来处理Patching流，将时间间隔在分组窗口内的Patching流利用融合技术进行合并，提高系统中Patching流的利用率，实现三级调度的思想。关

2、键词：流媒体，调度算法，分组融合，补丁流0 引 言自从2O世纪9O年代初流媒体;概念诞生以来，流技术得到了飞速的开展。VOD视频点播应用是最常用的也是最重要的一种流媒体发布模式，流调度技术又是大规模VOD视频点播系统的关键技术，其性能好坏直接影响系统的效劳能力和用户的收看效果【1】。针对用户大量且频繁的访问少数热门;连续媒体信息的情况, 尤其是当用户请求比拟集中且强度比拟大时，系统可能会因为流信息数目过多而导致网络阻塞或资源的浪费。为了减轻效劳器和网络的负载, 各研究机构提出了多种利用Multicast技术的流调度算法.在这些算法中，Patching算法较其它算法具有明显的系统性能提升【2】。

3、1 Patching算法现状分析最初的流媒体调度算法的根本思想是：当用户发出一个请求后，效劳器尽快产生一个包含连续媒体对象(视频、音频)的完整节目流(称为Regular流)来满足用户。有多少个用户请求，系统中就会产生多少个Regular流。这是最早的一级流调度算法。在这类算法中，每个用户都是由一个独立的流信息来满足的，相互没有任何影响，但是随着用户请求数目的增多，系统中的Regular流数目急剧增加，流信息的重复局部也大大增多，加大了系统的负担，造成资源浪费和网络阻塞。论文大全。为了缓解这一问题，Patching算法诞生了。Patching算法的根本思想是:让用户同时最多接收两个连续媒体流,并

4、提供一定的缓冲区，到达多个用户共享网络数据的目的.如图1 所示,令在t0 时刻生成一个Regular流,播放长度为V。用户缓冲区中可以缓存播放时间为B 的数据。新的用户请求在t 时刻到达,如果(t- t0)图1Patching算法Fig. 1PatchingalgorithmPatching算法实现了一个Regular流带多个Patching流来共同满足多个用户的思想，是目前较先进、性能较好的一种流媒体调度算法。但是Patching算法只是实现了利用补丁流来满足用户的二级流调度的思想，并没有采用适当的技术来处理补丁流，所以在一定程度上限制了算法性能的提升和效率的提高。据资料说明，对于大范围的用

5、户请求强度变化, Patching流承当了绝大多数的节目点播请求,从图2 可以看出,在不同的用户请求强度情况下,假设缓冲区大小为5min,在一个提供1000个节目,具有1200个节目发送通道的系统中,Patching流满足了约70%的用户请求【3】。论文大全。当用户请求比拟集中且强度比拟大时，想要满足这么多的用户，Patching流的数目就会不断增加，系统可能会因为流数目过多而造成网络阻塞或资源的浪费，甚至影响系统的吞吐量和效率。同时因为视频文件播放时占用的带宽较大如MPEG1为1.5M/S,MPEG2为4M/S-6M/S，而磁盘和网络的带宽都是有限的，想要支持更多的用户，就有必要采取一定的策

6、略。针对这一问题，本文通过对Patching算法的研究与分析，充分考虑系统中补丁流的重要地位，结合分组融合策略，对具有二级流调度思想的Patching算法进行改良，提出了一种基于分组融合策略的三级流调度算法，使用户请求撤销率降低、用户平均等待时间缩短，进一步提升算法的性能。图2Patching算法性能分析Fig.2Theanalysis of Patching algorithms capability2 基于分组融合的三级流调度算法2.1 分组融合策略分组融合策略是分组策略和融合策略的结合，即利用分组策略来加快融合速度，同时利用融合策略来缩短用户的等待时间。该策略同时设有分组窗口和融合窗口。

7、分组窗口是一个时间段,假设用户请求在规定的时间间隔之内,那么将它们分为一组，然后选择相同的请求分配一个共同的信道,共享一个相同的视频流。融合窗口是一个帧数值,在这个值里,两个相同的视频流发出时,让前一个降低播放速度,或(和) 后一个提高播放速度,那么在某一个时间点称为时间融合点(或某一帧上称为空间融合点) 到达完全融合,然后多余的一个流可以释放。播放速率的改变可以通过丢弃或增加帧到原始的流中来实现(NTSC 标准的视频流要求30帧/ 秒,改变帧的数目而不引起用户注意意味着每秒可增加或丢弃1. 5 帧2 帧)。丢弃或增加帧可以通过前面或后面的帧延长或缩短播放时间来代替,以减少两者之间的不连续性。

8、当两个流融合后,再让它们以正常的速度播放。假设在融合窗口里没有融合,即视为没有融合的必要,不再融合。分组与融合联用,可以有效地减少I/ O带宽要求而不用增加过多延迟。其整个过程如图3所示：图3分组融合策略Fig.3 The strategy ofstream-merging in group根据图2所示，首先，确定适宜的分组窗口和融合窗口,确保在融合窗口里边能够融合两个相隔分组窗口长度的流。其次，在分组窗口边界处,为了能最大限度地减少系统负载,选一个等待队列最长视频流播放。论文大全。 然后，当一个流新到达时，先检查捕获窗口里最近处是否有相同的流在它前面,是否用最小播放速率播放。假设是的话,它采

9、用最大播放速率播放争取跟前面的流融合，两个流融合后再以正常速率播放;假设不是,它改变播放速率到最小,等待后面的流来融合,在将要离开融合窗口前调整播放速率到正常直到结束【4】。2.2 对Patching算法的改良当用户请求比拟集中且强度比拟大时，针对同一个Regular流可能会产生多个比拟密集的Patching流，这些Patching流之间的时间间隔非常小，有可能会出现某一时刻系统中因流数目过多而造成拥挤状态，运行速度会受到影响。因此考虑对Patching算法进行改良，利用上述分组融合策略来处理Patching流，将时间间隔在分组窗口内的Patching流利用融合技术进行合并，提高系统中Patc

10、hing流的利用率，实现三级调度的思想。同时也可以将分组融合策略应用在对Regular流的处理上，通过减少Regular流和Patching流数目的方式来到达减少系统中流的总数，从而缓解网络阻塞问题，提高系统性能。假设t0时刻系统对节目M1产生组播流R，t1时刻对R产生Patching流P1,t2时刻对R产生patching流P2,算法中分组窗口为20s，融合窗口为10帧，要传输的数据块的大小为3M，传输速度为1.5M/s (MPEG-1格式的传输速度)，那么每帧的长度为3M/1.5M/s=2s,融合所需的帧数为16s/2s=8帧改良后的算法是将组播流Regular流的概念移植到了补丁流群中，

11、即将时间间隔非常小的众多补丁流Patching流分为一组视为一个补丁流群，将这个群体中的某个补丁流视为该群的组播流;，采用融合策略使多条补丁流合并为一条补丁流，形成一个补丁流带多个补丁流的形式，这比一个组播流带多个补丁流的二级调度思想又增加了一级，因此改良后的算法是一种结合了分组融合策略的具有三级调度思想的新的流媒体调度算法。2.3 算法的验证表1系统仿真参数Tab.1 The parameter in emulationsystem 系统参数 缺省值 参数变化范围 节目总数部 50 10-100 运行时间min 720 用户到达时间 服从Poisson分布 用户请求强度(次/min) 40

12、1-120 缓冲区大小min 5 0-10 用户等待时间上限s 120 30-300 算法性能的好坏宏观上主要表现在用户方面，因此采用用户请求撤消率、用户平均等待时间作为本文评价算法性能的指标。(1)用户请求撤消率当用户等待效劳时间过长时，用户可能会放弃点播请求。用户请求撤消率越低，说明调度算法的性能越好，可以到达的系统吞吐量越高，定义用户请求撤消率为： -(1) 其中ndefection表示用户撤消的请求总数,n表示用户请求总数【3】。(2)用户平均等待时间W一个好的流调度算法应该保证用户的平均等待时间很小,定义用户平均等待时间为： -(2) 其中n表示用户请求总数，Wi表示第i个用户请求的

13、等待时间【3】。针对FCFS先来先效劳算法和改良后的算法，利用表1的仿真参数进行仿真实验，根据实验数据和公式(1)、公式2，计算两种算法的用户请求撤消率和用户平均等待时间，得出实验结果如图4、图5所示：图4 不同请求强度下用户请求撤消率比拟Fig.4 compare the user request defectionratio under different request intensity图5 不同请求强度下用户平均等待时间比拟Fig.5 compare the user average waitingtime under different request intensity上述实验结

14、果说明，改良后的算法与传统的FCFS算法相比，明显降低了用户请求撤消率，缩短了用户平均等待时间。当用户请求逐渐增加的时候，无论是用户请求撤消率，还是用户平均时间等待，均到达了预期的效果，呈现出一种趋于平稳且渐减的状态。根据图4和图5中曲线的走势可以预测，当用户请求强度继续增大时，上述两个参数的走势将会继续呈现平稳或渐减的趋势，由此可以说明改良后算法性能的稳定性和有效性。综上所述，改良后算法的性能较传统算法做出了进一步的提升，是一种优化了的、有效的三级流调度算法。3 结束语本文在传统Patching算法的根底上，将分组融合策略应用到处理系统中的Patching流上，形成了一种三级流调度算法，有效提高了系统资源利用率和吞吐量，缓解了网络阻塞问题。由于文中所提算法对Patching流采取了适当的处理技术，从而获得更好的性能。特别是在用户请求较集中且请求强度较大的情况下，该算法可以显著降低用户请求撤销率、缩短用户平均等待时间。参考文