大規(guī)?？蛻舳艘曨l流帶寬調度①

丁佳龍,譚 光

(中山大學 智能工程學院,廣州 510006)

1 引言

自視頻流服務興起以來,視頻流量逐漸成為網(wǎng)絡上主體流量類型.預計到2022年,網(wǎng)絡流量的4/5 都將是流媒體服務[1].與此同時,互聯(lián)網(wǎng)總用戶數(shù)量將達到53 億,這意味著多客戶端共享帶寬成為常態(tài).例如在家庭、校園或者企業(yè)內(nèi)部,多個智能設備共享網(wǎng)絡帶寬鏈路請求視頻服務.當多個用戶同時在線觀看視頻時,不同的視頻流之間會相互競爭有限的帶寬資源,如何給多客戶端分配合適的帶寬以提供最大的用戶體驗質量非常具有挑戰(zhàn)性.

現(xiàn)有的視頻流服務采用基于HTTP的動態(tài)自適應流(dynamic adaptive streaming over HTTP,DASH)[2]標準傳輸視頻,客戶端可以在播放已緩存的視頻內(nèi)容的同時繼續(xù)請求下載后續(xù)內(nèi)容.如圖1所示,區(qū)別于傳統(tǒng)的視頻流結構,DASH 服務器上將視頻分成多個視頻塊,并且編碼成多種比特率以供客戶端選擇,在客戶端上部署的自適應比特率(adaptive bitrate,ABR)算法[3]可以動態(tài)調整請求下載的視頻塊比特率,從而改善用戶的體驗質量.ABR 算法會根據(jù)不同的網(wǎng)絡條件(預測帶寬以及緩沖區(qū)占用)對視頻塊的比特率作出決策,保證客戶端的最佳QoE.鑒于QoE的決定因素相互影響,需要根據(jù)不同的用戶偏好設定對應的權重以進行權衡,盡可能為用戶提供平滑高清的觀看體驗服務.

圖1 DASH 視頻流傳輸結構

隨著視頻流服務的發(fā)展,業(yè)內(nèi)對ABR 算法的研究也在不斷改善.最初的自適應比特率算法僅從網(wǎng)絡預測吞吐量[4-7]或是當前緩沖區(qū)占用[8-11]角度優(yōu)化QoE,盡管相比于非自適應視頻流提升了用戶體驗質量,但由于缺乏完整的環(huán)境信息造成帶寬浪費或者卡頓事件.在此基礎上Yin 等人綜合兩種指標提出基于控制理論方式的決策算法[12],把預測帶寬以及緩沖區(qū)當前占用作為輸入信號,通過優(yōu)化QoE 進行比特率決策并保證單客戶端獲得最優(yōu)體驗質量.Mao 等人結合強化學習作為比特率決策算法[13],采用asynchronous advantage actor-critic (A3C)訓練神經(jīng)網(wǎng)絡,摒棄過去的假設模型,將客戶端的預測帶寬和緩沖器占用作為狀態(tài)空間,直接從觀測結果中學習經(jīng)驗并不斷優(yōu)化控制策略,最后得到視頻流客戶端最佳比特率決策.

雖然現(xiàn)存的ABR 算法可以保證單個用戶最優(yōu)的體驗質量,但是當應用于客戶端規(guī)模較大的場景時,每個客戶端會基于自身部署的自適應算法請求最大比特率的視頻塊,這會占用更多的帶寬導致彼此相互制約而降低觀看體驗質量.不同的帶寬分配方案會導致ABR 算法給出截然不同的決策,尤其是當客戶端數(shù)目很大時,缺乏合理的帶寬調度方案會使得多客戶端相互競爭.

本文提出一種大規(guī)模客戶端視頻流帶寬調度方案,針對較大數(shù)量的客戶端,根據(jù)其預測帶寬以及當前緩沖器占用情況進行聚類并劃分成幾種不同的客戶端類型,進而將大規(guī)模的客戶端場景縮小成幾類客戶端帶寬調度情形,不同類的客戶端根據(jù)其所在類占比添加權重并計算每一類應分配的帶寬份額,相同類的客戶端分配等量的帶寬資源,以此實現(xiàn)大規(guī)?？蛻舳藢崟r帶寬調度.

對于縮小規(guī)模的聚類客戶端利用模型預測控制算法(model predictive control,MPC)[12]建立視頻流帶寬調度模型:(1)帶寬調度:在客戶端之間加入帶寬控制器以統(tǒng)計預測帶寬,根據(jù)總預測帶寬情況判定是否需要進行帶寬調度,當預測帶寬總數(shù)超過帶寬閾值時為每個聚類客戶端預分配帶寬;(2)比特率決策:結合預測帶寬以及緩沖器占用情況計算不同的帶寬分配方式下各聚類客戶端所能達到的最大QoE,最后選取最大QoE 對應的帶寬分配方式以及視頻塊的比特率決策.最后,本文通過在真實帶寬軌跡上進行仿真實驗,比較在同一帶寬閾值下通過聚類帶寬調度、Minerva[14]以及均分帶寬3 種方案取得的總用戶體驗質量,驗證我們的方案能夠顯著提高總用戶的QoE.

2 研究背景和動機

在多客戶端視頻流場景中,多客戶端相互競爭可用帶寬,造成帶寬資源缺乏.基于現(xiàn)有的ABR 算法,每個客戶端都追求自身QoE 最大化,請求更高質量的視頻塊使得帶寬占用增加,而當多個用戶受限于同一帶寬約束時,會引發(fā)網(wǎng)絡擁塞并使得QoE 受損.另一方面各客戶端上的播放緩沖器的性能不一,其可存儲的視頻塊上限不同,此外不同比特率的視頻塊尺寸大不相同,每個設備當前剩余可緩存視頻容量的差異也會導致不同視頻比特率的選擇.

對于多客戶端視頻流,有研究表明可以通過中心管理控制器統(tǒng)一調度[15]來提升客戶端QoE,其關鍵指標在于穩(wěn)定性、公平性以及高利用率.穩(wěn)定性要求客戶端盡可能請求相近或者同比特率的視頻塊減少比特率切換次數(shù),保證平滑播放;公平性則考慮多客戶端設備的性能以及觀看視頻內(nèi)容保證他們平等共享帶寬資源;高利用率則是指所有客戶端對總帶寬的利用率盡可能高,這就要求給每個客戶端分配合理的帶寬資源避免浪費.基于視頻流傳輸結構特性,統(tǒng)一調度控制器既可以部署在服務器上,也可以部署在DASH 客戶端之間.

Nathan 等人提出多客戶端QoE 公平調度框架Minerva[14],避免各客戶端長期處于QoE 較低或較高的狀態(tài).該框架使用MPC 作為決策算法,通過計算歷史視頻塊平均QoE 以及預測MPC 視野塊的QoE 計算效用函數(shù),在均分帶寬的基礎上添加權重來實現(xiàn)多客戶端的帶寬分配,保證各客戶端的QoE 公平性.

Spiteri 等人通過在服務器上部署來解決可用帶寬問題[16].在服務器端進行比特率整形,通過碼率整形器控制各客戶端視頻塊的最終決策.這種方式大大增加了服務器端的開銷,而且需要額外修改傳輸視頻文件,可能違反DASH 視頻流設計標準.Altamimi 等人利用服務器和客戶端的協(xié)同解決多客戶端的不公平性問題[17],讓服務器定期更新視頻文件清單,結合多代理強化學習[18]提出Dec-POMDP 模型,使用強化學習尋找并發(fā)多客戶端網(wǎng)絡帶寬分配的公平性解決方案.

以上所有研究盡管針對多客戶端,但大多僅適用于數(shù)量不多的客戶端場景,當客戶端規(guī)模較大時無法保持ABR 算法的性能.本文考慮對大規(guī)模客戶端通過聚類縮小規(guī)模,然后在聚類客戶端和服務器中間加入網(wǎng)絡代理,統(tǒng)一對每一類客戶端的帶寬進行調度以保證所有客戶端具有最大的總QoE.

3 視頻流決策和多客戶端聚類

在本節(jié)介紹視頻流決策優(yōu)化函數(shù)QoE 以及多客戶端的聚類.

3.1 QoE 公式

QoE是用于評估視頻流服務的體驗質量的指標,具體而言就是從用戶感知因素的角度衡量觀看視頻的舒適程度,例如當用戶觀看視頻時會重視視頻畫質、視頻卡頓時長以及次數(shù)、流暢程度等因素.越高的比特率對應更高質量的視頻,卡頓時間越少對應更高的平滑度.考慮到不同用戶側重不同的QoE 影響因素,為統(tǒng)一量化用戶體驗質量,采用視頻塊質量,緩沖時間以及切換平滑度作為衡量指標.視頻塊質量可以用比特率度量,緩沖時間則是由視頻塊下載時間與當前緩沖器剩余可播放時間差值決定,切換平滑度取決于相鄰兩個視頻塊質量變化大小,則QoE的計算公式如下:

其中,q(Ri)指 第i個視頻塊的視頻質量,Si是緩沖時間,最后一項則代表切換平滑度.

對于大規(guī)?？蛻舳?假定客戶端數(shù)目為M)而言,優(yōu)化目標變?yōu)樽畲蠡锌蛻舳说目俀oE:

3.2 模型預測控制算法

模型預測控制算法可以通過預測未來幾步的環(huán)境變量,然后根據(jù)預測結果解決一個確切的優(yōu)化問題.考慮到視頻流中的ABR 算法需要對預測帶寬以及緩沖器占用綜合考慮進行決策,故而可以將模型預測控制算法用作比特率決策.對于多客戶端場景,MPC 控制器可以通過調整QoE 影響因素參數(shù)以及視野適用于不同類型的客戶端.

DASH 視頻流采用MPC 進行決策的過程如下:當前客戶端請求下載視頻塊i時,首先通過帶寬預測器對前幾個視頻塊的帶寬取均值得到預測帶寬,結合當前緩沖器占用情況Bi以及上一個視頻塊的比特率Ri-1計算未來L個視頻塊(未來視野)的預期QoE,通過比較不同的比特率選擇方式得到的QoE 求最大值,并給出預下載視頻塊的最佳比特率決策:

3.3 多客戶端聚類

對于大規(guī)?？蛻舳艘曨l流,由于客戶端上的ABR算法根據(jù)下載視頻請求時的預測帶寬以及緩沖器占用情況進行決策,故而可以采用K 均值聚類算法[19]進行聚類,將上述兩個數(shù)值作為每一個客戶端的坐標,選定k個聚類中心并通過計算聚類內(nèi)平方和(withincluster sum-of-squares,WCSS)[20]進行劃分,把具有相似分布的客戶端聚在一起記為一個簇,將所有客戶端分成k類,對每一類客戶端分配相同的網(wǎng)絡帶寬和相同的比特率決策.

為了確定K 均值聚類算法選取的客戶端數(shù)目k,采用拐點法進行分析.拐點法的衡量指標是數(shù)據(jù)的誤差平方累加和(sum of the squared error,SSE)[21],可以代表聚類效果的好壞,通過改變k值比較聚類效果,從中選擇聚類效果最好的k作為客戶端分類的代表個數(shù).

其中,Ai代表第i個簇,a代表簇內(nèi)的數(shù)據(jù),ci代表所有數(shù)據(jù)的均值(質心).k從1 開始逐漸增大,客戶端劃分的類別在增加的同時也變得更加細致,所有客戶端依據(jù)帶寬以及緩沖器占用情況分類得到的簇聚合程度不斷上升,SSE的值逐漸變小,通常隨著k的增大SSE變化幅度越小并逐漸趨于穩(wěn)定,選取使SSE變化幅度從較大過渡到平緩時對應的k值即為所需的客戶端聚類數(shù).

在實際應用中,考慮帶寬受限的情形,按與均分帶寬的大小關系劃分可分為3 類(大于、小于、等于);考慮客戶端緩沖占用情況,將緩沖器劃分為3 類(無緩沖、滿緩沖和介于二者之間).綜上結合實際數(shù)值將聚類客戶端k值限定在10 以內(nèi).通過可視化方法計算多客戶端不同k值下得到的SSE曲線斜率變化找尋突變點即為合適的聚類數(shù)目,此后隨著k的增大聚類效果不再有較大變化.

4 多客戶端縮放模型和帶寬調度

本節(jié)介紹聚類客戶端縮放模型以及出現(xiàn)帶寬競爭現(xiàn)象時的調度策略.

4.1 多客戶端縮放模型

在確定多客戶端的聚類數(shù)后,采用均值聚類算法將大規(guī)?？蛻舳丝s小為k個客戶端,并得到k個客戶端對應的聚類中心點為(Tk,Bk).每一類客戶端的預測帶寬和緩沖器占用為中心點對應數(shù)值,且其權重 αk由該類客戶端包含的客戶端數(shù)目在所有客戶端總數(shù)的占比決定,記總客戶端數(shù)目為M,總約束帶寬為Tupper,第k類客戶端包含的客戶端數(shù)為nk,則有:

如上把大規(guī)?？蛻舳说膸捳{度轉化為縮放的k個客戶端的帶寬分配問題,則總帶寬約束條件按縮放模型變?yōu)?

于是可以參照上一節(jié)進行比特率決策以及帶寬調度,對于第k個客戶端下載第i個視頻塊時比特率決策Rk,i和預測帶寬為:

其中,Tk′為客戶端k采用帶寬調度算法(第4.2 節(jié))得到的分配帶寬.

4.2 聚類客戶端帶寬調度

由于真實環(huán)境中網(wǎng)絡帶寬持續(xù)波動,通過帶寬預測器得到的預測帶寬也會隨之波動.在共享帶寬鏈路瓶頸下,當所有聚類客戶端的預測帶寬總數(shù)超過閾值時,需要對各客戶端的帶寬進行調度.盡管通過聚類大大降低了客戶端的規(guī)模,但由于聚類客戶端之間互相制約,各QoE 性能隨不同的帶寬分配而不同,為了根據(jù)網(wǎng)絡狀況動態(tài)進行帶寬調度,需要比較多種分配方案下的總QoE 大小來進行抉擇.本文采用模擬退火算法探索最佳帶寬調度方案,性能與迭代次數(shù)有關,流程如圖2所示,具體步驟如下:

圖2 多客戶端帶寬調度流程圖

(1)參數(shù)設定:設定多組預分配帶寬初始值集合以及迭代次數(shù)l.

(2)初始化:從初始值集合選擇一組作為各聚類客戶端的分配帶寬,結合緩沖器占用信息送入MPC 控制器計算最大總用戶QoE,記為QoEbest,對應的帶寬分配方案記為Tk′.

(3)更新:對分配帶寬添加擾動,保證總帶寬不超過閾值,計算新的分配方式下最大總用戶體驗質量QoEnew,與QoEbest比較,將最大的數(shù)值記為新的QoEbest,將對應的帶寬分配方案更新為Tk′.繼續(xù)添加擾動,重復更新步驟直至達到迭代次數(shù)上限.

(4)返回第(2)步,選取新的初始分配帶寬,繼續(xù)執(zhí)行步驟(2)-(3)直至初始值集合所有分配方案計算完畢,此時得到最大總用戶體驗質量QoEbest以及相應的最佳帶寬分配Tk′.

4.3 帶寬調度算法分析

算法復雜度:在實際應用中,考慮M個客戶端,采用K 均值聚類算法過程中計算每個點與中心點的距離,其算法復雜度為d,假定聚類數(shù)為k,迭代次數(shù)為t,則整個聚類算法的時間復雜度為O(t×M×k×d),相比較大規(guī)?？蛻舳藬?shù)目M而言,t、k、d可視為常數(shù).在帶寬調度過程中,其迭代次數(shù)為l,客戶端數(shù)目為k,MPC決策復雜度為a,為復雜度為O(l×k×a),為保證調度性能,迭代次數(shù)相對較大,k、a視為常數(shù).故本文所用聚類調度算法復雜度為平方復雜度.

時間開銷:k值的不同選擇會相應地增加執(zhí)行時間,k值越小執(zhí)行時間越短.為驗證算法調度的實時性能,統(tǒng)計1-10 個客戶端的單個視頻塊在是否產(chǎn)生調度情況下的運行時間,在未發(fā)生調度時決策時間平均為4.5 ms,產(chǎn)生帶寬調度的決策時間在11-110 ms 范圍變化,而單個視頻塊的下載時間在600-7 000 ms 范圍變化.

本文提出的多客戶端聚類帶寬調度算法復雜度從原始的立方復雜度降為平方,在執(zhí)行時間上遠小于視頻塊的下載時間,故而在實際應用中可以滿足實時性要求.

5 實驗評估

在本節(jié)描述多客戶端聚類調度算法的實施.

實驗設置:仿真實驗所需的100 個客戶端分別采用來自HSDPA 數(shù)據(jù)集的100 條不同網(wǎng)絡帶寬軌跡模擬視頻播放環(huán)境,總帶寬瓶頸設置為100 Mb/s.實驗預先準備10 個客戶端和視頻流服務器,并從視頻數(shù)據(jù)集DASHDataset2014[22]中選取10 種具有不同比特率編碼的視頻文件,每一個視頻文件包含48 個視頻塊(相同時長).本文使用Mahimahi[23]仿真視頻流請求播放網(wǎng)絡環(huán)境,MPC 算法的預測視野設為3,帶寬調度算法迭代次數(shù)設為100 次.

對照組設置:選取目前多客戶端帶寬調度領域最新技術Minerva 以及均分帶寬方案進行對比.Minerva方案通過計算QoE 占比決定未來視頻塊的帶寬分配值,而均分帶寬方案則對所有客戶端設置相同的帶寬閾值.

客戶端聚類數(shù)k值以及預分配帶寬:通過統(tǒng)計100個客戶端當前請求視頻塊時的預測帶寬以及緩沖器占用情況計算SSE 變化幅度不再突變時對應的K 值.

如圖3所示,從圖中可以得知最為合適的聚類數(shù)k在4 附近,故我們實驗選取4 個客戶端作為聚類客戶端,選取4 個提供不同視頻的服務器,并通過預實驗選定3 組預設分配帶寬,如表1所示.

圖3 SSE與聚類數(shù)k的對應關系圖

表1 各客戶端預設帶寬初始值 (Mb/s)

多客戶端的聚類:為保證聚類算法的精準性,對100 個客戶端當前視頻塊的預測帶寬和緩沖器占用數(shù)據(jù)值進行標準化處理.再根據(jù)上述所選k值設定聚類器數(shù)目為4,對多客戶端采用K 均值聚類,各客戶端聚類結果如圖4所示.得到4 個聚類客戶端對應的聚類中心(包括預測帶寬與緩沖器占用兩個信息),并統(tǒng)計每一類客戶端所包含的客戶端數(shù)量.

圖4 各客戶端聚類結果

對縮放的聚類客戶端進行帶寬動態(tài)調度,計算各聚類客戶端的最大QoE,再將每一類客戶端得到的QoE 乘以該類客戶端包含的客戶端數(shù)目,然后累加得到最大總用戶體驗質量.為消除客戶端視頻對實驗的影響對照組同樣采用4 個客戶端以及與聚類帶寬調度方案相同的服務器,每一種客戶端從聚類帶寬調度所用的100 條網(wǎng)絡帶寬軌跡中各選取25 條進行實驗,最后將所有客戶端上的最大QoE 累加得到Minerva和均分帶寬方案下的總用戶體驗質量.

圖5中3 個子圖分別為聚類調度、Minerva 以及均分帶寬3 種方案下各視頻塊對應的具體比特率選擇、相應的帶寬分配數(shù)值以及緩沖器占用情況.相比于均分帶寬,聚類調度和Minerva 方案可以更好地進行比特率決策,各客戶端的實際帶寬在1 Mb/s 左右持續(xù)上下波動,兩種方案的區(qū)別在于聚類調度保證總帶寬的利用率而Minerva 旨在維持各客戶端QoE的公平.而對于均分帶寬方式,由于客戶端1 Mb/s的帶寬限制,當部分客戶端未完全使用帶寬而其他客戶端帶寬完全占用時產(chǎn)生帶寬浪費,較低的帶寬利用率使得總用戶QoE 顯著下降.

圖5 不同方案下各客戶端決策信息

圖6為以上3 種方式下對各類客戶端計算總QoE的數(shù)值,如圖所示通過聚類后進行帶寬調度(cluster1-4)和Minerva 方案(Minerva1-4)相比于均分帶寬方式(mean1-4),每一類客戶端上的QoE 都有顯著提升.通過帶寬動態(tài)調度提高了帶寬資源的利用效率,將部分客戶端多余的帶寬分配給其他客戶端,進而提高用戶體驗質量.將各客戶端的QoE 累加可以得到兩種方式下所有客戶端的總用戶體驗質量,具體數(shù)值見表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 方案相比于均分帶寬性能大大改善,但從總體用戶體驗質量角度出發(fā),不能實現(xiàn)總QoE的最大化,其考慮的QoE 公平性在實際應用中具有很大的局限性,例如選用不同設備觀看視頻其觀看體驗有一定差異,本文所提方案從總QoE 出發(fā),通過聚類和帶寬調度保證資源的最大化利用,提供極致的體驗質量,相比于傳統(tǒng)的均分帶寬,QoE 獲得顯著提高.

6 結論與展望

采用K 均值聚類算法降低規(guī)模,把問題縮小為幾個客戶端之間的帶寬調度和比特率決策問題,保證帶寬調度及時性.本文選取100 個客戶端進行仿真實驗并通過與Minerva和均分帶寬的方案對比證明該方案在QoE 上的顯著提升.然而,多客戶端調度受預測帶寬的影響很大,錯誤的預測會影響到各客戶端的具體調度以及QoE 決策.此后的研究工作是改進帶寬預測方式,利用LSTM 確保帶寬預測的精準度.此外,可以根據(jù)不同視頻播放類型定義不同權重QoE 指標.