大规模客户端视频流带宽调度①

丁佳龙,谭 光

(中山大学 智能工程学院,广州 510006)

1 引言

自视频流服务兴起以来,视频流量逐渐成为网络上主体流量类型.预计到2022年,网络流量的4/5 都将是流媒体服务[1].与此同时,互联网总用户数量将达到53 亿,这意味着多客户端共享带宽成为常态.例如在家庭、校园或者企业内部,多个智能设备共享网络带宽链路请求视频服务.当多个用户同时在线观看视频时,不同的视频流之间会相互竞争有限的带宽资源,如何给多客户端分配合适的带宽以提供最大的用户体验质量非常具有挑战性.

现有的视频流服务采用基于HTTP的动态自适应流(dynamic adaptive streaming over HTTP,DASH)[2]标准传输视频,客户端可以在播放已缓存的视频内容的同时继续请求下载后续内容.如图1所示,区别于传统的视频流结构,DASH 服务器上将视频分成多个视频块,并且编码成多种比特率以供客户端选择,在客户端上部署的自适应比特率(adaptive bitrate,ABR)算法[3]可以动态调整请求下载的视频块比特率,从而改善用户的体验质量.ABR 算法会根据不同的网络条件(预测带宽以及缓冲区占用)对视频块的比特率作出决策,保证客户端的最佳QoE.鉴于QoE的决定因素相互影响,需要根据不同的用户偏好设定对应的权重以进行权衡,尽可能为用户提供平滑高清的观看体验服务.

图1 DASH 视频流传输结构

随着视频流服务的发展,业内对ABR 算法的研究也在不断改善.最初的自适应比特率算法仅从网络预测吞吐量[4-7]或是当前缓冲区占用[8-11]角度优化QoE,尽管相比于非自适应视频流提升了用户体验质量,但由于缺乏完整的环境信息造成带宽浪费或者卡顿事件.在此基础上Yin 等人综合两种指标提出基于控制理论方式的决策算法[12],把预测带宽以及缓冲区当前占用作为输入信号,通过优化QoE 进行比特率决策并保证单客户端获得最优体验质量.Mao 等人结合强化学习作为比特率决策算法[13],采用asynchronous advantage actor-critic (A3C)训练神经网络,摒弃过去的假设模型,将客户端的预测带宽和缓冲器占用作为状态空间,直接从观测结果中学习经验并不断优化控制策略,最后得到视频流客户端最佳比特率决策.

虽然现存的ABR 算法可以保证单个用户最优的体验质量,但是当应用于客户端规模较大的场景时,每个客户端会基于自身部署的自适应算法请求最大比特率的视频块,这会占用更多的带宽导致彼此相互制约而降低观看体验质量.不同的带宽分配方案会导致ABR 算法给出截然不同的决策,尤其是当客户端数目很大时,缺乏合理的带宽调度方案会使得多客户端相互竞争.

本文提出一种大规模客户端视频流带宽调度方案,针对较大数量的客户端,根据其预测带宽以及当前缓冲器占用情况进行聚类并划分成几种不同的客户端类型,进而将大规模的客户端场景缩小成几类客户端带宽调度情形,不同类的客户端根据其所在类占比添加权重并计算每一类应分配的带宽份额,相同类的客户端分配等量的带宽资源,以此实现大规模客户端实时带宽调度.

对于缩小规模的聚类客户端利用模型预测控制算法(model predictive control,MPC)[12]建立视频流带宽调度模型:(1)带宽调度:在客户端之间加入带宽控制器以统计预测带宽,根据总预测带宽情况判定是否需要进行带宽调度,当预测带宽总数超过带宽阈值时为每个聚类客户端预分配带宽;(2)比特率决策:结合预测带宽以及缓冲器占用情况计算不同的带宽分配方式下各聚类客户端所能达到的最大QoE,最后选取最大QoE 对应的带宽分配方式以及视频块的比特率决策.最后,本文通过在真实带宽轨迹上进行仿真实验,比较在同一带宽阈值下通过聚类带宽调度、Minerva[14]以及均分带宽3 种方案取得的总用户体验质量,验证我们的方案能够显著提高总用户的QoE.

2 研究背景和动机

在多客户端视频流场景中,多客户端相互竞争可用带宽,造成带宽资源缺乏.基于现有的ABR 算法,每个客户端都追求自身QoE 最大化,请求更高质量的视频块使得带宽占用增加,而当多个用户受限于同一带宽约束时,会引发网络拥塞并使得QoE 受损.另一方面各客户端上的播放缓冲器的性能不一,其可存储的视频块上限不同,此外不同比特率的视频块尺寸大不相同,每个设备当前剩余可缓存视频容量的差异也会导致不同视频比特率的选择.

对于多客户端视频流,有研究表明可以通过中心管理控制器统一调度[15]来提升客户端QoE,其关键指标在于稳定性、公平性以及高利用率.稳定性要求客户端尽可能请求相近或者同比特率的视频块减少比特率切换次数,保证平滑播放;公平性则考虑多客户端设备的性能以及观看视频内容保证他们平等共享带宽资源;高利用率则是指所有客户端对总带宽的利用率尽可能高,这就要求给每个客户端分配合理的带宽资源避免浪费.基于视频流传输结构特性,统一调度控制器既可以部署在服务器上,也可以部署在DASH 客户端之间.

Nathan 等人提出多客户端QoE 公平调度框架Minerva[14],避免各客户端长期处于QoE 较低或较高的状态.该框架使用MPC 作为决策算法,通过计算历史视频块平均QoE 以及预测MPC 视野块的QoE 计算效用函数,在均分带宽的基础上添加权重来实现多客户端的带宽分配,保证各客户端的QoE 公平性.

Spiteri 等人通过在服务器上部署来解决可用带宽问题[16].在服务器端进行比特率整形,通过码率整形器控制各客户端视频块的最终决策.这种方式大大增加了服务器端的开销,而且需要额外修改传输视频文件,可能违反DASH 视频流设计标准.Altamimi 等人利用服务器和客户端的协同解决多客户端的不公平性问题[17],让服务器定期更新视频文件清单,结合多代理强化学习[18]提出Dec-POMDP 模型,使用强化学习寻找并发多客户端网络带宽分配的公平性解决方案.

以上所有研究尽管针对多客户端,但大多仅适用于数量不多的客户端场景,当客户端规模较大时无法保持ABR 算法的性能.本文考虑对大规模客户端通过聚类缩小规模,然后在聚类客户端和服务器中间加入网络代理,统一对每一类客户端的带宽进行调度以保证所有客户端具有最大的总QoE.

3 视频流决策和多客户端聚类

在本节介绍视频流决策优化函数QoE 以及多客户端的聚类.

3.1 QoE 公式

QoE是用于评估视频流服务的体验质量的指标,具体而言就是从用户感知因素的角度衡量观看视频的舒适程度,例如当用户观看视频时会重视视频画质、视频卡顿时长以及次数、流畅程度等因素.越高的比特率对应更高质量的视频,卡顿时间越少对应更高的平滑度.考虑到不同用户侧重不同的QoE 影响因素,为统一量化用户体验质量,采用视频块质量,缓冲时间以及切换平滑度作为衡量指标.视频块质量可以用比特率度量,缓冲时间则是由视频块下载时间与当前缓冲器剩余可播放时间差值决定,切换平滑度取决于相邻两个视频块质量变化大小,则QoE的计算公式如下:

其中,q(Ri)指 第i个视频块的视频质量,Si是缓冲时间,最后一项则代表切换平滑度.

对于大规模客户端(假定客户端数目为M)而言,优化目标变为最大化所有客户端的总QoE:

3.2 模型预测控制算法

模型预测控制算法可以通过预测未来几步的环境变量,然后根据预测结果解决一个确切的优化问题.考虑到视频流中的ABR 算法需要对预测带宽以及缓冲器占用综合考虑进行决策,故而可以将模型预测控制算法用作比特率决策.对于多客户端场景,MPC 控制器可以通过调整QoE 影响因素参数以及视野适用于不同类型的客户端.

DASH 视频流采用MPC 进行决策的过程如下:当前客户端请求下载视频块i时,首先通过带宽预测器对前几个视频块的带宽取均值得到预测带宽,结合当前缓冲器占用情况Bi以及上一个视频块的比特率Ri-1计算未来L个视频块(未来视野)的预期QoE,通过比较不同的比特率选择方式得到的QoE 求最大值,并给出预下载视频块的最佳比特率决策:

3.3 多客户端聚类

对于大规模客户端视频流,由于客户端上的ABR算法根据下载视频请求时的预测带宽以及缓冲器占用情况进行决策,故而可以采用K 均值聚类算法[19]进行聚类,将上述两个数值作为每一个客户端的坐标,选定k个聚类中心并通过计算聚类内平方和(withincluster sum-of-squares,WCSS)[20]进行划分,把具有相似分布的客户端聚在一起记为一个簇,将所有客户端分成k类,对每一类客户端分配相同的网络带宽和相同的比特率决策.

为了确定K 均值聚类算法选取的客户端数目k,采用拐点法进行分析.拐点法的衡量指标是数据的误差平方累加和(sum of the squared error,SSE)[21],可以代表聚类效果的好坏,通过改变k值比较聚类效果,从中选择聚类效果最好的k作为客户端分类的代表个数.

其中,Ai代表第i个簇,a代表簇内的数据,ci代表所有数据的均值(质心).k从1 开始逐渐增大,客户端划分的类别在增加的同时也变得更加细致,所有客户端依据带宽以及缓冲器占用情况分类得到的簇聚合程度不断上升,SSE的值逐渐变小,通常随着k的增大SSE变化幅度越小并逐渐趋于稳定,选取使SSE变化幅度从较大过渡到平缓时对应的k值即为所需的客户端聚类数.

在实际应用中,考虑带宽受限的情形,按与均分带宽的大小关系划分可分为3 类(大于、小于、等于);考虑客户端缓冲占用情况,将缓冲器划分为3 类(无缓冲、满缓冲和介于二者之间).综上结合实际数值将聚类客户端k值限定在10 以内.通过可视化方法计算多客户端不同k值下得到的SSE曲线斜率变化找寻突变点即为合适的聚类数目,此后随着k的增大聚类效果不再有较大变化.

4 多客户端缩放模型和带宽调度

本节介绍聚类客户端缩放模型以及出现带宽竞争现象时的调度策略.

4.1 多客户端缩放模型

在确定多客户端的聚类数后,采用均值聚类算法将大规模客户端缩小为k个客户端,并得到k个客户端对应的聚类中心点为(Tk,Bk).每一类客户端的预测带宽和缓冲器占用为中心点对应数值,且其权重 αk由该类客户端包含的客户端数目在所有客户端总数的占比决定,记总客户端数目为M,总约束带宽为Tupper,第k类客户端包含的客户端数为nk,则有:

如上把大规模客户端的带宽调度转化为缩放的k个客户端的带宽分配问题,则总带宽约束条件按缩放模型变为:

于是可以参照上一节进行比特率决策以及带宽调度,对于第k个客户端下载第i个视频块时比特率决策Rk,i和预测带宽为:

其中,Tk′为客户端k采用带宽调度算法(第4.2 节)得到的分配带宽.

4.2 聚类客户端带宽调度

由于真实环境中网络带宽持续波动,通过带宽预测器得到的预测带宽也会随之波动.在共享带宽链路瓶颈下,当所有聚类客户端的预测带宽总数超过阈值时,需要对各客户端的带宽进行调度.尽管通过聚类大大降低了客户端的规模,但由于聚类客户端之间互相制约,各QoE 性能随不同的带宽分配而不同,为了根据网络状况动态进行带宽调度,需要比较多种分配方案下的总QoE 大小来进行抉择.本文采用模拟退火算法探索最佳带宽调度方案,性能与迭代次数有关,流程如图2所示,具体步骤如下:

图2 多客户端带宽调度流程图

(1)参数设定:设定多组预分配带宽初始值集合以及迭代次数l.

(2)初始化:从初始值集合选择一组作为各聚类客户端的分配带宽,结合缓冲器占用信息送入MPC 控制器计算最大总用户QoE,记为QoEbest,对应的带宽分配方案记为Tk′.

(3)更新:对分配带宽添加扰动,保证总带宽不超过阈值,计算新的分配方式下最大总用户体验质量QoEnew,与QoEbest比较,将最大的数值记为新的QoEbest,将对应的带宽分配方案更新为Tk′.继续添加扰动,重复更新步骤直至达到迭代次数上限.

(4)返回第(2)步,选取新的初始分配带宽,继续执行步骤(2)-(3)直至初始值集合所有分配方案计算完毕,此时得到最大总用户体验质量QoEbest以及相应的最佳带宽分配Tk′.

4.3 带宽调度算法分析

算法复杂度:在实际应用中,考虑M个客户端,采用K 均值聚类算法过程中计算每个点与中心点的距离,其算法复杂度为d,假定聚类数为k,迭代次数为t,则整个聚类算法的时间复杂度为O(t×M×k×d),相比较大规模客户端数目M而言,t、k、d可视为常数.在带宽调度过程中,其迭代次数为l,客户端数目为k,MPC决策复杂度为a,为复杂度为O(l×k×a),为保证调度性能,迭代次数相对较大,k、a视为常数.故本文所用聚类调度算法复杂度为平方复杂度.

时间开销:k值的不同选择会相应地增加执行时间,k值越小执行时间越短.为验证算法调度的实时性能,统计1-10 个客户端的单个视频块在是否产生调度情况下的运行时间,在未发生调度时决策时间平均为4.5 ms,产生带宽调度的决策时间在11-110 ms 范围变化,而单个视频块的下载时间在600-7 000 ms 范围变化.

本文提出的多客户端聚类带宽调度算法复杂度从原始的立方复杂度降为平方,在执行时间上远小于视频块的下载时间,故而在实际应用中可以满足实时性要求.

5 实验评估

在本节描述多客户端聚类调度算法的实施.

实验设置:仿真实验所需的100 个客户端分别采用来自HSDPA 数据集的100 条不同网络带宽轨迹模拟视频播放环境,总带宽瓶颈设置为100 Mb/s.实验预先准备10 个客户端和视频流服务器,并从视频数据集DASHDataset2014[22]中选取10 种具有不同比特率编码的视频文件,每一个视频文件包含48 个视频块(相同时长).本文使用Mahimahi[23]仿真视频流请求播放网络环境,MPC 算法的预测视野设为3,带宽调度算法迭代次数设为100 次.

对照组设置:选取目前多客户端带宽调度领域最新技术Minerva 以及均分带宽方案进行对比.Minerva方案通过计算QoE 占比决定未来视频块的带宽分配值,而均分带宽方案则对所有客户端设置相同的带宽阈值.

客户端聚类数k值以及预分配带宽:通过统计100个客户端当前请求视频块时的预测带宽以及缓冲器占用情况计算SSE 变化幅度不再突变时对应的K 值.

如图3所示,从图中可以得知最为合适的聚类数k在4 附近,故我们实验选取4 个客户端作为聚类客户端,选取4 个提供不同视频的服务器,并通过预实验选定3 组预设分配带宽,如表1所示.

图3 SSE与聚类数k的对应关系图

表1 各客户端预设带宽初始值 (Mb/s)

多客户端的聚类:为保证聚类算法的精准性,对100 个客户端当前视频块的预测带宽和缓冲器占用数据值进行标准化处理.再根据上述所选k值设定聚类器数目为4,对多客户端采用K 均值聚类,各客户端聚类结果如图4所示.得到4 个聚类客户端对应的聚类中心(包括预测带宽与缓冲器占用两个信息),并统计每一类客户端所包含的客户端数量.

图4 各客户端聚类结果

对缩放的聚类客户端进行带宽动态调度,计算各聚类客户端的最大QoE,再将每一类客户端得到的QoE 乘以该类客户端包含的客户端数目,然后累加得到最大总用户体验质量.为消除客户端视频对实验的影响对照组同样采用4 个客户端以及与聚类带宽调度方案相同的服务器,每一种客户端从聚类带宽调度所用的100 条网络带宽轨迹中各选取25 条进行实验,最后将所有客户端上的最大QoE 累加得到Minerva和均分带宽方案下的总用户体验质量.

图5中3 个子图分别为聚类调度、Minerva 以及均分带宽3 种方案下各视频块对应的具体比特率选择、相应的带宽分配数值以及缓冲器占用情况.相比于均分带宽,聚类调度和Minerva 方案可以更好地进行比特率决策,各客户端的实际带宽在1 Mb/s 左右持续上下波动,两种方案的区别在于聚类调度保证总带宽的利用率而Minerva 旨在维持各客户端QoE的公平.而对于均分带宽方式,由于客户端1 Mb/s的带宽限制,当部分客户端未完全使用带宽而其他客户端带宽完全占用时产生带宽浪费,较低的带宽利用率使得总用户QoE 显著下降.

图5 不同方案下各客户端决策信息

图6为以上3 种方式下对各类客户端计算总QoE的数值,如图所示通过聚类后进行带宽调度(cluster1-4)和Minerva 方案(Minerva1-4)相比于均分带宽方式(mean1-4),每一类客户端上的QoE 都有显著提升.通过带宽动态调度提高了带宽资源的利用效率,将部分客户端多余的带宽分配给其他客户端,进而提高用户体验质量.将各客户端的QoE 累加可以得到两种方式下所有客户端的总用户体验质量,具体数值见表2.通过聚类调度方案获得的总QoE为5 654.8,目前最新技术Minerva方案获得的总QoE为5 109.1,均分带宽的总QoE 值2 836.4,就总体QoE 而言,聚类调度的QoE 相比于均分方案提升99.4%,相比于Minerva 质量提升10.7%.

表2 各类客户端上QoE 总和

图6 不同方案各客户端QoE 分布情况

尽管Minerva 方案相比于均分带宽性能大大改善,但从总体用户体验质量角度出发,不能实现总QoE的最大化,其考虑的QoE 公平性在实际应用中具有很大的局限性,例如选用不同设备观看视频其观看体验有一定差异,本文所提方案从总QoE 出发,通过聚类和带宽调度保证资源的最大化利用,提供极致的体验质量,相比于传统的均分带宽,QoE 获得显著提高.

6 结论与展望

采用K 均值聚类算法降低规模,把问题缩小为几个客户端之间的带宽调度和比特率决策问题,保证带宽调度及时性.本文选取100 个客户端进行仿真实验并通过与Minerva和均分带宽的方案对比证明该方案在QoE 上的显著提升.然而,多客户端调度受预测带宽的影响很大,错误的预测会影响到各客户端的具体调度以及QoE 决策.此后的研究工作是改进带宽预测方式,利用LSTM 确保带宽预测的精准度.此外,可以根据不同视频播放类型定义不同权重QoE 指标.