梁建勝 譚思敏

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

0 引 言

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

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

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

1 云視頻直播問(wèn)題

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

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

1.1 直播視頻流的QoE

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

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

Sq=Urep_max-|log(qu)|

(3)

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

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

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

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

(4)

延遲評(píng)分計(jì)算為：

Sde=Ude_max-|log(dscale)|

(5)

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

(6)

QoE依賴Sde和Sq兩個(gè)變量：

Qview=w1×Sde+w2×Sq

(7)

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

1.2 問(wèn)題模型

a·I[avr]

(8)

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

(9)

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

總成本定義為下式：

(10)

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

(11)

約束條件有以下6點(diǎn)：

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

(12)

② 總計(jì)算實(shí)體必須小于計(jì)算約束：

(13)

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

(14)

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

br≤bubu≥b0b0=512 kbit/s

(15)

⑤ 平均延遲評(píng)分必須大于閾值：

Sde≥td

(16)

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

Sq≥tr

(17)

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

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

(18)

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

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

2.1 TABC的總體框架

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

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

圖2 TABC算法的流程框圖

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

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

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

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

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

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

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

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

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

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

1.inti=0;

2.while (i++

/*搜索階段*/

3. 偵察蜂搜索食物源；

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

約束條件的食物源*/

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

5. 觀察蜂評(píng)估食物源；

/*計(jì)算式(10)評(píng)估食物源*/

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

6. 檢查已訪問(wèn)的食物源；

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

8. 雇傭蜂訪問(wèn)食物源；

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

10. 返回蜂巢；

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

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

2.4 分布式DTABC算法

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

圖3 DTABC算法的流程框圖

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

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

表4 里約奧運(yùn)會(huì)官方統(tǒng)計(jì)的觀眾概率分布

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

Popuk=N×pk

(19)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.6 時(shí)間效率分析

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

圖17 本算法對(duì)于全球性事件的平均計(jì)算時(shí)間

4 結(jié) 語(yǔ)

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