图3 分组融合策略
Fig.3 The strategy ofstream-merging in group
根据图2所示，首先，确定合适的分组窗口和融合窗口,确保在融合窗口里边能够融合两个相隔分组窗口长度的流。其次，在分组窗口边界处,为了能最大限度地减少系统负载,选一个等待队列最长视频流播放。论文大全。 然后，当一个流新到达时，先检查捕获窗口里最近处是否有相同的流在它前面,是否用最小播放速率播放。若是的话,它采用最大播放速率播放争取跟前面的流融合，两个流融合后再以正常速率播放;若不是,它改变播放速率到最小,等待后面的流来融合,在将要离开融合窗口前调整播放速率到正常直到结束[4]。
2.2 对Patching算法的改进
当用户请求比较集中且强度比较大时，针对同一个Regular流可能会产生多个比较密集的Patching流，这些Patching流之间的时间间隔非常小，有可能会出现某一时刻系统中因流数目过多而造成拥挤状态，运行速度会受到影响。因此考虑对Patching算法进行改进，利用上述分组融合策略来处理Patching流，将时间间隔在分组窗口内的Patching流利用融合技术进行合并，提高系统中Patching流的利用率，实现三级调度的思想。同时也可以将分组融合策略应用在对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帧<10帧(融合窗口大小)，在融合窗口内两条Patching流P1、P2分别丢弃和增加8帧/2＝4帧即可达到融合，即P1按照每秒钟丢弃2帧的速度增加4帧，需2s完成2次加帧，每次加帧将增加帧的后面的帧减少2s*2帧=4s的播放时间；P2按照每秒钟丢弃2帧的速度丢帧,也需2s完成2次丢帧，每次丢帧将所丢弃帧前面的一帧加长2s*2帧=4s的播放时间，这样两个Patching流在8s后融为一条流，达到了融合的目的。
改进后的算法是将组播流（Regular流）的概念移植到了补丁流群中，即将时间间隔非常小的众多补丁流（Patching流）分为一组视为一个补丁流群，将这个群体中的某个补丁流视为该群的“组播流”，采用融合策略使多条补丁流合并为一条补丁流，形成一个补丁流带多个补丁流的形式，这比一个组播流带多个补丁流的二级调度思想又增加了一级，因此改进后的算法是一种结合了分组融合策略的具有三级调度思想的新的流媒体调度算法。
2.3 算法的验证
2.3.1 系统仿真参数如表1
表1 系统仿真参数
Tab.1 The parameter in emulationsystem
| 系统参数 |
缺省值 |
参数变化范围 |
| 节目总数（部） |
50 |
10-100 |
| 运行时间（min） |
720 |
|
| 用户到达时间 |
服从Poisson分布 |
|
| 用户请求强度(次/min) |
40 |
1-120 |
| 缓冲区大小（min） |
5 |
0-10 |
| 用户等待时间上限（s） |
120 |
30-300 |
2.3.2 算法评价参数
算法性能的好坏宏观上主要表现在用户方面，因此采用用户请求撤消率、用户平均等待时间作为本文评价算法性能的指标。
(1)用户请求撤消率
当用户等待服务时间过长时，用户可能会放弃点播请求。用户请求撤消率越低，说明调度算法的性能越好，可以达到的系统吞吐量越高，定义用户请求撤消率为：
 -----(1)
其中ndefection表示用户撤消的请求总数,n表示用户请求总数[3]。
(2)用户平均等待时间W
一个好的流调度算法应该保证用户的平均等待时间很小,定义用户平均等待时间为：
 -----(2)
其中n表示用户请求总数，Wi表示第i个用户请求的等待时间[3]。
2.3.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
上述实验结果表明，改进后的算法与传统的FCFS算法相比，明显降低了用户请求撤消率，缩短了用户平均等待时间。当用户请求逐渐增加的时候，无论是用户请求撤消率，还是用户平均时间等待，均达到了预期的效果，呈现出一种趋于平稳且渐减的状态。根据图4和图5中曲线的走势可以预测，当用户请求强度继续增大时，上述两个参数的走势将会继续呈现平稳或渐减的趋势，由此可以表明改进后算法性能的稳定性和有效性。
综上所述，改进后算法的性能较传统算法做出了进一步的提升，是一种优化了的、有效的三级流调度算法。
3 结束语
本文在传统Patching算法的基础上，将分组融合策略应用到处理系统中的Patching流上，形成了一种三级流调度算法，有效提高了系统资源利用率和吞吐量，缓解了网络阻塞问题。由于文中所提算法对Patching流采取了适当的处理技术，从而获得更好的性能。特别是在用户请求较集中且请求强度较大的情况下，该算法可以显著降低用户请求撤销率、缩短用户平均等待时间。
参考文献：
[1]. 李述冰,范铁生, 崔奇明. 一种新的基于补丁优先的流调度算法[J].计算机工程与应用,2006,06:179-182.
[2]. 王浩, 钟玉琢. 一种新的基于流合并的调度策略[J].计算机学报,2001,3,24(3):225-230.
[3]. 钟玉琢, 向哲, 沈洪. 流媒体和视频服务器[M].北京:清华大学出版社,2003:87-92.
[4]. 周宁, 姜昱明. VOD视频服务器中的视频流调度策略[J].计算机应用研究,2002,(12):151-155.
2/2 首页 上一页 1 2 |
