梁建勝 譚思敏

1(東莞職業(yè)技術(shù)學(xué)院 廣東 東莞 523808)2(東莞中國科學(xué)院云計算產(chǎn)業(yè)技術(shù)創(chuàng)新與育成中心 廣東 東莞 523808)

0 引 言

在許多重大事件或者體育比賽的直播中，直播商大多提供多視點的直播服務(wù)，為用戶提供高真實度和沉浸式的觀看體驗[1]。隨著智能終端的流形和普及，大量的普通用戶會在社交網(wǎng)絡(luò)或者直播平臺對同一個事件做直播，由于直播視頻流的數(shù)據(jù)量較大，而且需要長期占用帶寬資源，為移動無線網(wǎng)絡(luò)帶來了沉重的負(fù)擔(dān)[2]。云視頻技術(shù)[3]是解決上述問題的一個有效方案，云視頻技術(shù)采用云服務(wù)站點[4]為直播視頻進(jìn)行緩存、轉(zhuǎn)碼和分發(fā)，將合適的視頻數(shù)據(jù)流傳遞至用戶終端。

云視頻技術(shù)能夠以較低的成本為用戶提供高質(zhì)量的在線視頻直播服務(wù)，但是云視頻技術(shù)目前存在3大挑戰(zhàn)[5]：① 視頻直播的啟動延遲和緩存延遲對用戶的觀看體驗具有較大的影響；② 視頻回放延遲和視點切換延遲對用戶的觀看體驗具有較大的影響；③ 在滿足用戶QoE(Quality of Experience)期望的前提下，服務(wù)提供商希望最小化視頻流的傳輸成本和計算成本。專家學(xué)者針對上述問題進(jìn)行了深入的研究，并給出了切實可行的方案。文獻(xiàn)[6]總結(jié)了影響終端用戶QoE的若干因素，包括：資源分配、帶寬分配和容錯能力等，設(shè)計了結(jié)合樸素貝葉斯算法和Guess Fit算法的虛擬機分布方案，該方案主要針對虛擬機的部署問題，而非選擇問題。文獻(xiàn)[7]設(shè)計了低成本的云服務(wù)優(yōu)化算法，通過聯(lián)合優(yōu)化方案粗粒度地調(diào)節(jié)視頻源的地理分布和調(diào)度，該算法僅考慮了單視點的視頻直播服務(wù)，但多視點視頻直播已成為當(dāng)前行業(yè)的主流應(yīng)用。

本文考慮觀看人數(shù)眾多的多視點視頻直播場景，期望在滿足用戶QoE需求的前提下，最小化系統(tǒng)的總體成本。人工蜂群算法(Artificial Bee Colony, ABC)[8]在求解旅行商問題、路徑規(guī)劃等NP-Hard問題上具有良好的性能，并且ABC的參數(shù)簡單、易于實現(xiàn)[9]，因此采用ABC計算目標(biāo)問題的最優(yōu)解。根據(jù)諸多專家的研究結(jié)論，ABC算法容易陷入局部最優(yōu)、后期收斂速度慢，而禁忌搜索(Tabu Search, TS)[10]是一種確定性的局部極小突跳策略，能夠有效地跳出局部最優(yōu)的情況。本文將禁忌搜索引入ABC算法中，以避免ABC陷入局部最優(yōu)，禁忌搜索和ABC算法的混合算法簡稱為禁忌人工蜂群算法(Tabu Artificial Bee Colony, TABC)。本文針對觀看人數(shù)眾多的多視點視頻直播場景，總結(jié)了符合實際的QoE評估方法，設(shè)計了增強的人工蜂群算法計算云視頻直播優(yōu)化問題的次優(yōu)解。

1 云視頻直播問題

首先總結(jié)了云視頻直播系統(tǒng)的QoE指標(biāo)，給出影響QoE的關(guān)鍵參數(shù)。然后，將視頻的顯示格式選擇問題和轉(zhuǎn)碼站點選擇問題建模為整數(shù)規(guī)劃(Integer Programming, IP)問題，以最小化總成本為優(yōu)化目標(biāo)。因為直播系統(tǒng)對實時性具有高要求，所以采用TABC算法搜索目標(biāo)問題的次優(yōu)解。圖1所示是多視點視頻直播的總體結(jié)構(gòu)圖，在事件現(xiàn)場多個攝像設(shè)備從不同角度拍攝視頻，通過基站傳輸至云計算的控制中心，控制中心的觀眾交互模塊(Viewer Interation model, VI)負(fù)責(zé)接收視頻流，質(zhì)量控制模塊負(fù)責(zé)決定視頻流的格式，資源調(diào)度模塊負(fù)責(zé)分配視頻轉(zhuǎn)碼資源?？刂浦行母鶕?jù)用戶、云服務(wù)站點、視頻拍攝點三個位置選擇最佳地點的云服務(wù)站點，滿足用戶的QoE需求、降低總體的運營成本。

圖1 多視點視頻直播的總體結(jié)構(gòu)圖

1.1 直播視頻流的QoE

基于以下兩個原則推導(dǎo)視頻直播的QoE指標(biāo)：(1) 評價參數(shù)應(yīng)當(dāng)易于獲??；(2) 應(yīng)當(dāng)能夠?qū)崟r地調(diào)節(jié)這些參數(shù)?；谏鲜鲈瓌t考慮了兩個參數(shù)：傳輸延遲和視頻質(zhì)量?？刂葡到y(tǒng)能夠簡單地獲取這兩個參數(shù)，同時自適應(yīng)地調(diào)節(jié)這兩個參數(shù)。兩個參數(shù)具體對應(yīng)視頻直播的兩個指標(biāo)：① 視頻質(zhì)量：適合觀看者帶寬的視頻格式；② 視點切換延遲：計算為從觀看者到轉(zhuǎn)碼服務(wù)器的平均往返延遲(Round-Trip Time，RTT)。指標(biāo)①說明應(yīng)該為觀看者提供其帶寬支持的最佳顯示格式，指標(biāo)②說明需要決定轉(zhuǎn)碼服務(wù)器的地點，使同一個視點所有觀看者的平均延遲最短。

根據(jù)觀看者接收視頻的能力估計視頻的顯示格式。如果觀看者的帶寬支持接收1 080 p或4 K格式的視頻流，而該視點僅提供了360 p和720 p兩種格式，那么觀看者從服務(wù)器收到720 p格式的視點vj，觀看者接收的vj質(zhì)量低于可用帶寬，此時觀看者認(rèn)為視頻質(zhì)量較低。直播視頻流需要被持續(xù)轉(zhuǎn)碼，導(dǎo)致視頻流需要長時間持續(xù)占用轉(zhuǎn)碼資源，所以許多直播網(wǎng)站僅支持少量的顯示格式，例如：YY直播支持4個格式。另外根據(jù)文獻(xiàn)[11]的統(tǒng)計和分析，4種格式即可滿足大多數(shù)觀看者的需求。

設(shè)Sq為觀看者接收的視頻質(zhì)量，設(shè)l=||表示支持的視頻顯示格式。=1/l表示視頻質(zhì)量的衰減，lr表示觀看者接收的視頻質(zhì)量，lu表示可用帶寬支持的最佳視頻質(zhì)量。視頻質(zhì)量的衰減表示為下式：

(1)

觀看者接收的視頻質(zhì)量表示為：

qu=qmax-u

(2)

式中:qmax設(shè)為定值1，表示視頻的最佳質(zhì)量。如果視頻質(zhì)量未損失，觀看者接收的質(zhì)量等于其可用帶寬支持的質(zhì)量(lu=lr)，那么qu等于1。將觀看者感知的視頻質(zhì)量評分量化為下式：

Sq=Urep_max-|log(qu)|

(3)

式中:Urep_max設(shè)為定值1，表示觀看者的最高滿意度。

延遲評分設(shè)為Sde，評估用戶對視點切換延遲的滿意度，視點切換的延遲越短，延遲評分則越高。視點切換延遲依賴觀看者和轉(zhuǎn)碼服務(wù)器之間的距離，由于所有的云服務(wù)站點均提供直播視頻轉(zhuǎn)碼的服務(wù)，而不同的站點和觀看者之間的距離存在差異，所以每個云服務(wù)站點的Sde存在差異。切換視點會導(dǎo)致額外的延遲，所以觀看者距離云服務(wù)站點越遠(yuǎn)，Sde評分越小。表1所示是全球大型云服務(wù)站點之間的RTT延遲矩陣，各個云服務(wù)站點之間RTT的延遲范圍較大，將RTT延遲值歸一化至[0,1]范圍。

表1 全球大型云服務(wù)站點之間的RTT延遲矩陣 ms

平均延遲的問題模型為：假設(shè)dmin為延遲矩陣maj的最小平均延遲，dmax為maj的最大平均延遲，那么基于對數(shù)的歸一化方法為：

(4)

延遲評分計算為：

Sde=Ude_max-|log(dscale)|

(5)

如果觀看者和轉(zhuǎn)碼服務(wù)器位于同一個區(qū)域，此時的延遲評分值最大(等于1)，將該情況的變量Sde表示為常量dcon。將dcon設(shè)為矩陣的平均延遲：

(6)

QoE依賴Sde和Sq兩個變量：

Qview=w1×Sde+w2×Sq

(7)

式中:w1和w2分別表示視頻質(zhì)量評分和延遲評分的權(quán)重。如果觀看者獲得了最佳的視頻質(zhì)量，并且在同一個區(qū)域轉(zhuǎn)碼視頻流，那么觀看者認(rèn)為QoE為最佳。

1.2 問題模型

a·I[avr]

(8)

每秒的總數(shù)據(jù)成本可計算為：

(9)

式中:br為顯示格式ri的比特率，每個地區(qū)的數(shù)據(jù)費用不同，所以不同轉(zhuǎn)碼地點的總數(shù)據(jù)費用也不同；I為指示函數(shù)，表示用戶u接收了在地區(qū)a轉(zhuǎn)碼的視點v格式r。

總成本定義為下式：

(10)

算法的目標(biāo)是最小化總成本：

(11)

約束條件有以下6點：

① 所有地區(qū)的總帶寬成本必須小于總帶寬約束：

(12)

② 總計算實體必須小于計算約束：

(13)

③ 每個地區(qū)的云實體數(shù)量為有限值：

(14)

④ 接收視頻的比特率不大于觀看者的帶寬：

br≤bubu≥b0b0=512 kbit/s

(15)

⑤ 平均延遲評分必須大于閾值：

Sde≥td

(16)

⑥ 平均視頻質(zhì)量評分必須大于閾值：

Sq≥tr

(17)

最終，所有的決策變量總結(jié)為下式：

{I[avr],I[avru],I[uvr],I[vr],I[c∈]}∈{0, 1}

(18)

采用ILOG CPLEX solver[12]等軟件可求解上述有約束整數(shù)規(guī)劃問題的最優(yōu)解，但是云計算資源分配問題的規(guī)模龐大、復(fù)雜度高，無法通過軟件實時地響應(yīng)觀眾的視角切換和格式切換需求。因此，提出了TABC(Tabu Artificial Bee Colony)算法求解資源分配問題的次優(yōu)解。

2 基于TABC的云視頻優(yōu)化算法

2.1 TABC的總體框架

ABC是一種基于種群的搜索方法，轉(zhuǎn)碼云服務(wù)器的地點對應(yīng)ABC的食物源，食物源的花蜜對應(yīng)每個解的質(zhì)量。人工蜂在多維空間內(nèi)搜索和開發(fā)，其目標(biāo)是搜索花蜜量最多的食物源。雇傭蜂和觀察蜂根據(jù)經(jīng)歷選擇食物源，偵察蜂在搜索空間內(nèi)隨機搜索食物源。ABC算法通過雇傭蜂、觀察蜂和偵察蜂三個階段實現(xiàn)了較強的局部開發(fā)能力和全局搜索能力。為了解決ABC容易陷入局部最優(yōu)的問題，引入禁忌搜索算法避免ABC陷入局部最優(yōu)。

本模型使用三種蜜蜂：雇傭蜂、觀察蜂和偵察蜂。偵察蜂搜索食物源，雇傭蜂發(fā)現(xiàn)食物源后返回蜂巢通過蜂舞分享發(fā)現(xiàn)的信息。雇傭蜂結(jié)束搜索蜂巢任務(wù)之后，雇傭蜂變?yōu)閭刹旆?，?fù)責(zé)搜索新的食物源。觀察蜂觀看雇傭蜂的舞蹈，根據(jù)舞蹈選擇食物源。圖2所示是TABC算法的流程框圖，偵察蜂在搜索空間內(nèi)搜索，隨之返回蜂巢通過蜂舞分享其信息。根據(jù)食物源的評估結(jié)果，偵察蜂返回最優(yōu)的食物源，采用不同參數(shù)(禁忌列表大小和渴望值)的禁忌搜索對食物源做局部開發(fā)操作。TABC的全局搜索和局部開發(fā)兩個階段均采用了禁忌搜索技術(shù)：全局搜索階段通過禁忌搜索粗略分析所有的可能解，禁忌搜索能夠提高種群的多樣性，算法的偵察蜂數(shù)量設(shè)為1 000，根據(jù)實驗結(jié)果，該值能夠較好地平衡全局搜索和局部開發(fā)。

圖2 TABC算法的流程框圖

2.2 禁忌搜索算法的實現(xiàn)

(1) 禁忌搜索的總體流程。禁忌搜索是一種確定性的局部極小突跳策略，能夠有效地跳出局部最優(yōu)的情況。禁忌搜索記憶一段時間內(nèi)，各個粒子被選為全局極值的次數(shù)，將次數(shù)作為下一次全局極值的選擇依據(jù)，判斷規(guī)則為：局部最優(yōu)解被選為全局最優(yōu)的次數(shù)越多，則該局部最優(yōu)解的禁忌度就越大。禁忌列表和渴望值是禁忌搜索的兩個關(guān)鍵參數(shù)，禁忌列表越大則跳出局部最優(yōu)的能力越強?？释麥?zhǔn)則能夠覆蓋禁忌狀態(tài)，TS提供了多層次渴望準(zhǔn)則的短期記憶。調(diào)節(jié)禁忌搜索算法的記憶長度可實現(xiàn)集中搜索策略和分散搜索策略：集中搜索側(cè)重探索優(yōu)質(zhì)解，分散搜索側(cè)重搜索尚未搜索的部分。禁忌列表防止重新訪問已經(jīng)評估的區(qū)域。

魯棒禁忌搜索將失敗次數(shù)和禁忌列表作為參數(shù)，失敗次數(shù)定義為無法提高解質(zhì)量的迭代次數(shù)，TABC的偵察蜂階段和雇傭蜂階段使用魯棒TS進(jìn)行局部開發(fā)操作。算法1所示是禁忌搜索算法，當(dāng)發(fā)生禁忌移動，如果滿足渴望準(zhǔn)則，那么允許該禁忌移動。

算法1 魯棒禁忌搜索算法

輸入：flow,dist,maxiter,bestperm,minsize,minTl,maxsize,maxTl,As.

輸出：best_cost

//最優(yōu)成本值

1.Tlist=NULL;

2.evaluate(bestperm);

3.current_solution=bestperm;

4.Δ[j][k]=compute();

5.Tlist[j][k]=-(n×j+k);

6.foreachifrom 1 tomaxiterdo

7.aspire_tag=FALSE;

8. foreach 相鄰節(jié)點(j,k) do

9.cur1=Tlist[j][current_solution[k]];

10.cur2=Tlist[k][current_solution[j]];

11.auth_tag=(cur1

12.aspire_tag=(cur1

‖(cur_cost+Δ[j][k]

13. if ((aspire_tag&&aspire) ‖ (aspire&&Δ[j][k])

14.j_ret=j;k_ret=k;

15.minΔ=Δ[j][k];

16. if (aspire_tag) thenaspire=TRUE;

17. if (j_ret≠NULL)

18.exchange(current_solution[j_ret],

current_solution[k_ret])

19.cur_cost=cur_cost+Δ[j_ret][k_ret];

20.Tlist[j_ret][current_solution[j_ret]]

=j+random(minsize,maxsize);

21. if (cur_cost

22.best_cost=cur_cost;

(2) 禁忌搜索的參數(shù)更新。禁忌列表的長度是決定禁忌搜索性能的關(guān)鍵參數(shù)，設(shè)置過小導(dǎo)致搜索容易陷入局部最優(yōu)，設(shè)置過大導(dǎo)致解質(zhì)量較低。文獻(xiàn)[13]將列表的上下界分別設(shè)為1.1×n和0.9×n，n為問題的規(guī)模。根據(jù)文獻(xiàn)[13]的結(jié)論，動態(tài)禁忌列表的效果優(yōu)于靜態(tài)禁忌列表，所以設(shè)計了動態(tài)禁忌列表機制。

禁忌搜索的渴望值一般依賴問題的結(jié)構(gòu)，本文設(shè)計了動態(tài)渴望值機制，每隔10次迭代改變一次渴望值。如果搜索程序陷入局部最優(yōu)，優(yōu)化程序應(yīng)當(dāng)跳出該區(qū)域，并且保留學(xué)習(xí)的經(jīng)驗。動態(tài)渴望值的范圍定義為[n,(n×n×10)]，渴望值越小，則重點開發(fā)當(dāng)前解的附近空間，值越大則能夠跳出局部最優(yōu)。

在本算法的分布式框架中，動態(tài)參數(shù)促使不同處理器的搜索程序具有多樣性，從而有效提高了算法的總體多樣性，提高次優(yōu)解的質(zhì)量。

2.3 TABC優(yōu)化云視頻QoE的實現(xiàn)方法

設(shè)m為支持的視頻格式數(shù)量，n為視點數(shù)量，ki為地區(qū)Ai觀看視點vj的觀眾數(shù)量，ci表示云站點si的計算實體總數(shù)量。Ctotal表示所有云站點的全部可用云計算實體集，Rquality為期望的視頻質(zhì)量評分，Rdelay為期望的延遲評分。在滿足視頻格式和帶寬約束條件下尋找成本最小的資源組合方案。式(10)評估解質(zhì)量(TABC的適應(yīng)度函數(shù))，式(3)、式(5)、式(7)分別評估視頻的質(zhì)量評分、延遲評分和QoE。

算法2所示是基于TABC的云視頻QoE優(yōu)化算法。TABC算法的輸入為事件集、VI模塊統(tǒng)計的觀看數(shù)據(jù)、最低的期望視頻質(zhì)量、最低的期望延遲評分、每個云服務(wù)站點的可用資源量。算法的輸出為資源分配矩陣，矩陣內(nèi)容為滿足用戶視頻質(zhì)量期望和延遲評分期望的云站點集和視頻格式集。

算法2基于TABC的云視頻QoE優(yōu)化算法

1.inti=0;

2.while (i++

/*搜索階段*/

3. 偵察蜂搜索食物源；

/*計算式(3)、式(6)，選出滿足

約束條件的食物源*/

4. 偵察蜂返回食物源跳蜂舞；

5. 觀察蜂評估食物源；

/*計算式(10)評估食物源*/

/*局部開發(fā)階段*/

6. 檢查已訪問的食物源；

7. 選出最優(yōu)食物源；

8. 雇傭蜂訪問食物源；

9. 運行TS開發(fā)局部蜂巢；

10. 返回蜂巢；

11. 收集蜂巢的所有解集；

12. 輸出全局最優(yōu)解；

2.4 分布式DTABC算法

為了利用云計算分布式計算的優(yōu)勢，并加速ABC算法的計算速度，本文補充了分布式形式的TABC算法(Distributed Tabu Artificial Bee Colony, DTABC)。DTABC由一個主節(jié)點和若干的次節(jié)點組成，每個次節(jié)點服務(wù)一個蜂巢和該蜂巢對應(yīng)的偵察蜂、觀察蜂和雇傭蜂，圖3所示是DTABC的結(jié)構(gòu)圖。初始化階段每個處理器隨機初始化種群，全局搜索階段禁忌搜索算法完成少量的失敗(30次)和重啟(50次)，該策略能夠加速搜索過程，每個處理器運行1 000次搜索，255個處理器則同時運行255 000次搜索。偵察蜂的搜索階段結(jié)束后，將搜索的結(jié)果輸入局部開發(fā)階段。局部開發(fā)階段采用禁忌搜索優(yōu)化當(dāng)前解，該階段設(shè)置了4組參數(shù)組合，如表2所示。每個處理器完成優(yōu)化程序后，將處理結(jié)果和運行時間發(fā)送至主處理器，主處理器從收到的結(jié)果中選出最優(yōu)的結(jié)果作為最終的決策結(jié)果。

圖3 DTABC算法的流程框圖

表2 局部開發(fā)階段禁忌搜索的參數(shù)設(shè)置

3 實 驗

3.1 實驗環(huán)境

采用服務(wù)器HP ProLiant DL585 G7(633964-AA1)作為實驗的硬件環(huán)境，服務(wù)器的CPU型號為AMD Opteron 6212，CPU共有8個核心、64個線程。服務(wù)器的內(nèi)存大小為256 GB，磁盤空間為1.5 TB。操作系統(tǒng)為Ubuntu 12.04.5 LTS，采用C語言編程實現(xiàn)各個算法，采用GCC 6.5作為編譯器。

3.2 benchmark數(shù)據(jù)集的實驗結(jié)果

(1) 多視點直播的視頻數(shù)據(jù)集。采用3個多視點直播視頻流數(shù)據(jù)集作為benchmark數(shù)據(jù)集，分別為：① YouTube Live：視頻網(wǎng)站YouTube的直播服務(wù)平臺；② Twitch：面向視頻游戲的實時流媒體視頻平臺；③ 斗魚直播：面向視頻游戲的實時流媒體視頻平臺。這3個直播平臺均具有大量同時在線的觀眾，能夠測試本算法對于大規(guī)模問題的處理效果。YouTube Live數(shù)據(jù)集由多個拍攝者拍攝的視頻流組成，許多頻道的同時在線觀眾數(shù)量高于10萬人。Twitch和斗魚直播均為觀看量巨大的游戲直播平臺，許多熱門頻道的在線觀看人數(shù)也達(dá)到10萬人以上。

對Twitch和斗魚直播的直播頻道做篩選，頻道的受歡迎度定義為同時觀看指定頻道的平均人數(shù)，選擇觀看人數(shù)達(dá)到10 000以上的頻道，然后從選擇的頻道中選擇多視點直播的子集，視點數(shù)量的范圍為2～36。Twitch和斗魚直播兩個平臺將同一個游戲不同視點的直播頻道聚集成同一個事件的多視點直播數(shù)據(jù)集。通過多視點編碼(Multiview Coding, MVC)實現(xiàn)多視點的轉(zhuǎn)碼處理，MVC負(fù)責(zé)刪除時空冗余和可分級編碼機制對視頻的所有視點做轉(zhuǎn)碼處理。

(2) 觀眾端的實驗數(shù)據(jù)。根據(jù)Akamai發(fā)布《2017年互聯(lián)網(wǎng)發(fā)展?fàn)顩r安全報告》，將目標(biāo)觀眾分為4個主要的帶寬類型：(1) 低比特率觀眾(帶寬<4 Mbit/s)；(2) 中比特率觀眾(4 Mbit/s≤帶寬≤9 Mbit/s);(3) 高比特率觀眾(10 Mbit/s≤帶寬≤14 Mbit/s);(4) 超高比特率觀眾(帶寬≥15 Mbit/s)。根據(jù)每個觀眾的帶寬類型分配相應(yīng)的顯示格式，表3所示是YouTube推薦的顯示格式組合。

表3 YouTube推薦的顯示格式組合

實驗中包含了全球性事件和局部性事件，全球性事件包括奧運會等重大體育賽事，局部性事件包括局部的體育賽事、音樂會等。采用2016年的里約奧運會直播視頻集作為全球性事件的benchmark數(shù)據(jù)集，該數(shù)據(jù)集共包含258 PB的視頻數(shù)據(jù)流，最高峰為4.53 Tbit/s流量、1 300 000同時觀眾同時在線，觀眾分布于全球的不同地區(qū)，歐洲、美洲、澳洲、亞洲和非洲分別占據(jù)57%、38%、3%、2%和0%的觀眾比例。假設(shè)采用亞馬遜云服務(wù)器對直播視頻做轉(zhuǎn)碼處理，租用亞馬遜11個地點的云服務(wù)器，考慮亞馬遜每個地點每個小時的云服務(wù)租金，表4所示是里約奧運會官方統(tǒng)計的觀眾概率分布。

表4 里約奧運會官方統(tǒng)計的觀眾概率分布

根據(jù)文獻(xiàn)[14]，全球事件的視點受歡迎程度服從偏態(tài)0.8的齊夫分布(Zipf分布)，仿真實驗中將第k個視點的觀看比例設(shè)為pk，V為事件的總視點數(shù)，視點的受歡迎度計算為下式：

Popuk=N×pk

(19)

式中:N為事件的觀眾總數(shù)量。

建立仿真實驗評估本算法的性能。將本算法與CPLEX的最優(yōu)解比較，觀察TABC計算的次優(yōu)解質(zhì)量，同時與Twitch.tv當(dāng)前實際采用的視頻轉(zhuǎn)碼和格式選擇方案比較(簡稱為“原方案”)，并與近期優(yōu)質(zhì)的泛化多視點優(yōu)化框架(General Multiview Transcoding Framework, GMTF)[15]比較?？紤]不同的視頻質(zhì)量和延遲質(zhì)量組合，延遲評分的約束分別設(shè)為0.4、0.5、0.7、0.95，視頻質(zhì)量評分約束分別設(shè)為0.65、0.75、0.85、0.95。

3.3 YouTube live數(shù)據(jù)集的實驗結(jié)果

使用YouTube Live數(shù)據(jù)集“2014-01-24”1個小時(12:00-13:00)日志數(shù)據(jù)，共有355個直播頻道，其中共有98個觀眾人數(shù)超過10 000的頻道。YouTube Live的直播頻道數(shù)量較少，但其觀眾數(shù)量變化劇烈，有利于評估本算法的實時性和響應(yīng)速度，YouTube Live仿真數(shù)據(jù)的總觀看人數(shù)為394 153。圖4所示是YouTube Live的仿真實結(jié)果，圖中最優(yōu)解的總成本最低。當(dāng)QoE閾值為0.65時，本文TABC成功搜索了最優(yōu)解，其成本與CPLEX的最優(yōu)解相同，而直播系統(tǒng)原方案的成本約為本算法的兩倍，而GMTF的成本優(yōu)于原方案，但是也明顯高于本算法。當(dāng)QoE閾值較高時，本算法的次優(yōu)解略低于CPLEX的最優(yōu)解，但是本算法的結(jié)果也明顯優(yōu)于系統(tǒng)原方案和GMTF算法。

圖4 YouTube live數(shù)據(jù)集的總成本結(jié)果

3.4 Twich.tv數(shù)據(jù)集的實驗結(jié)果

圖5所示是事件總體成本的實驗結(jié)果。因為Twich.tv平臺在不考慮視頻質(zhì)量評分的情況下，將優(yōu)質(zhì)頻道全部轉(zhuǎn)碼為各個視頻格式，所以當(dāng)視頻質(zhì)量評分閾值較低的時候，Twich.tv平臺原方案的成本均較高。CPLEX和本算法根據(jù)延遲評分和視頻質(zhì)量評分的閾值分配優(yōu)化的云計算資源和顯示格式，所以其成本均保持較低的水平。

圖5 全球性事件總體成本的實驗結(jié)果

圖6所示是不同延遲評分和質(zhì)量評分的成本結(jié)果?？梢钥闯?，延遲評分越低，總體成本越低；延遲評分越高，算法分配大量距離近的云服務(wù)站點，從而導(dǎo)致運營成本越高。視頻質(zhì)量評分越高，視頻轉(zhuǎn)碼的計算量越大，數(shù)據(jù)流的傳輸成本也越大，從而導(dǎo)致運營成本越高。由此可得出結(jié)論，本文的資源優(yōu)化算法明顯地降低了系統(tǒng)的總成本。

圖6 不同延遲評分和質(zhì)量評分的成本結(jié)果

圖7所示是不同延遲閾值下觀看者和云服務(wù)站點之間的平均延遲。當(dāng)延遲得分較低時，算法分配總價格最低的云服務(wù)站點資源，隨著延遲得分提高，算法偏向于分配近距離的云服務(wù)站點，有效地降低了平均延遲，但是增加了云計算資源的總體價格。

圖7 不同延遲閾值下觀看者和云服務(wù)站點之間的平均延遲

圖8所示是云設(shè)備數(shù)量(云資源)與視頻質(zhì)量評分的關(guān)系。隨著視頻質(zhì)量的提高，需要增加視頻格式的數(shù)量才能滿足觀眾質(zhì)量需求，對云設(shè)備的需求量也隨之增加。隨著視頻質(zhì)量閾值的提高，本算法消耗的云資源量大于最優(yōu)解，原因是本算法搜索的次優(yōu)解并非最優(yōu)解，而CPLEX搜索所有的可能解，最終獲得滿足質(zhì)量閾值的最優(yōu)顯示格式。

圖8 云設(shè)備數(shù)量與視頻質(zhì)量評分的關(guān)系

圖9所示是帶寬消耗量與視頻質(zhì)量評分的關(guān)系。低質(zhì)量評分所需的數(shù)據(jù)流比特率較低，所以消耗的帶寬較少。隨著視頻質(zhì)量評分的提高，消耗的帶寬也顯著增加，從而達(dá)到QoE的需求。

圖9 帶寬消耗量與視頻質(zhì)量評分的關(guān)系

圖10所示是不同視頻質(zhì)量評分和延遲評分的QoE結(jié)果?？梢钥闯?，本算法成功獲得了次優(yōu)解，而系統(tǒng)原方案不僅總體成本較高，而且QoE也低于本算法。

圖10 不同視頻質(zhì)量評分和延遲評分的QoE結(jié)果

3.5 斗魚直播數(shù)據(jù)集的實驗結(jié)果

圖11所示是斗魚游戲直播的實驗結(jié)果。斗魚平臺在不考慮視頻質(zhì)量評分的情況下，將優(yōu)質(zhì)頻道全部轉(zhuǎn)碼為多個視頻格式，所以當(dāng)視頻質(zhì)量評分閾值較低的時候，斗魚平臺原方案的成本均較高。CPLEX和本算法根據(jù)延遲評分和視頻質(zhì)量評分的閾值分配優(yōu)化的云計算資源和顯示格式，所以其成本均保持較低的水平。

圖11 不同QoE閾值的成本結(jié)果

圖12所示是不同延遲評分和質(zhì)量評分的成本結(jié)果?？梢钥闯?，延遲評分越低，總體成本越低；延遲評分越高，算法分配大量距離近的云服務(wù)站點，從而導(dǎo)致運營成本越高。視頻質(zhì)量評分越高，視頻轉(zhuǎn)碼的計算量越大，數(shù)據(jù)流的傳輸成本也越大，導(dǎo)致運營成本越高。圖12顯示本文的資源優(yōu)化算法明顯降低了系統(tǒng)的總成本。

圖12 不同延遲評分和質(zhì)量評分的成本結(jié)果

圖13所示是不同延遲閾值下觀看者和云服務(wù)站點之間的平均延遲。當(dāng)延遲得分較低時，算法分配總價格最低的云服務(wù)站點資源，隨著延遲得分提高，算法偏向于分配近距離的云服務(wù)站點，有效降低了平均延遲，但是增加了云計算資源的總體價格。

圖13 不同延遲閾值下觀看者和云服務(wù)站點之間的平均延遲

圖14所示是云設(shè)備數(shù)量(云資源)與視頻質(zhì)量評分的關(guān)系。隨著視頻質(zhì)量的提高，需要增加視頻格式的數(shù)量才能滿足觀眾質(zhì)量需求，對云設(shè)備的需求量也隨之增加。隨著視頻質(zhì)量閾值的提高，本算法消耗的云資源量大于最優(yōu)解，原因是本算法搜索的次優(yōu)解并非最優(yōu)解，而CPLEX搜索所有的可能解，最終獲得滿足質(zhì)量閾值的最優(yōu)顯示格式。

圖14 云設(shè)備數(shù)量與視頻質(zhì)量評分的關(guān)系

圖15所示是帶寬消耗量與視頻質(zhì)量評分的關(guān)系。低質(zhì)量評分所需的數(shù)據(jù)流比特率較低，所以消耗的帶寬較少。隨著視頻質(zhì)量評分的提高，消耗的帶寬也顯著增加，從而達(dá)到QoE的需求。

圖15 帶寬消耗量與視頻質(zhì)量評分的關(guān)系

圖16所示是不同視頻質(zhì)量評分和延遲評分的QoE結(jié)果?？梢钥闯?，本算法成功獲得了次優(yōu)解，而系統(tǒng)原方案不僅總體成本較高，而且QoE也低于本算法。

圖16 不同視頻質(zhì)量評分和延遲評分的QoE結(jié)果

3.6 時間效率分析

統(tǒng)計了本算法對于Twich.tv的平均計算時間，結(jié)果如圖17所示。單核心情況下本算法的計算時間大約需要9秒，無法為資源分配提供快速的響應(yīng)，而采用8核的分布式DTABC算法計算時間約為0.1秒，可滿足視頻直播的實時性需求。

圖17 本算法對于全球性事件的平均計算時間

4 結(jié) 語

本文提出了QoE感知的多視點直播視頻流優(yōu)化算法，使用真實直播平臺的trace數(shù)據(jù)建立仿真實驗，評估本算法的性能。計算有約束整數(shù)規(guī)劃問題的最優(yōu)解需要較長的時間，無法滿足視頻直播平臺的實時性需求，因此本文設(shè)計了禁忌人工蜂群優(yōu)化算法，計算云資源優(yōu)化問題的次優(yōu)解，在求解質(zhì)量和計算效率之間取得平衡。轉(zhuǎn)碼不同視頻格式對計算資源的需求有所差異，本模型中考慮分配相等的計算資源，因此會導(dǎo)致資源浪費，未來將關(guān)注于差異化的云設(shè)備分配研究，進(jìn)一步提高算法的性能和效率。