分布式視頻轉(zhuǎn)碼服務(wù)調(diào)度算法研究

譚智一，宋建新

(南京郵電大學(xué)通信與信息工程學(xué)院圖像處理與圖像通信實驗室，江蘇 南京 210003)

分布式視頻轉(zhuǎn)碼服務(wù)是基于云特性的視頻服務(wù)之一，將一個大的視頻轉(zhuǎn)碼源序列按不同粒度(GOP，Slice等)劃分為多個小的分段作為子任務(wù)并將這些子任務(wù)分配到分布式網(wǎng)絡(luò)中位于不同物理位置通過網(wǎng)絡(luò)相互連接的處理節(jié)點上進(jìn)行轉(zhuǎn)碼處理，可以較為有效地緩解不斷增加的視頻轉(zhuǎn)碼任務(wù)負(fù)擔(dān)給視頻處理服務(wù)器造成的壓力和單臺節(jié)點計算機(jī)視頻處理能力不足的缺陷。在這種分布式的轉(zhuǎn)碼任務(wù)處理模式下，有2個有待解決的問題:一是如何根據(jù)節(jié)點資源及客戶信道質(zhì)量合理地接收客戶任務(wù)請求;二是如何將處理后的Close－GOP分段有控制地發(fā)送給客戶端使客戶可以收看到流暢的視頻服務(wù)，同時保證盡可能低的額外延遲代價。

Haiyan Luo，Song Ci等人在文獻(xiàn)［1］中提出的P2P網(wǎng)絡(luò)中跨層優(yōu)化實時傳輸控制算法;Sonia Nazari和Hamid Beigy在文獻(xiàn)［2］中提出的WiMAX網(wǎng)絡(luò)中的上行實時任務(wù)數(shù)據(jù)傳輸控制算法以及Chenghan Tsai和Taiyi Huan在文獻(xiàn)［3］中提出的基于QoS的基于時間片實時任務(wù)傳輸調(diào)度算法均是對上述問題有意義的探索和研究。

1 研究背景及問題描述

1.1 分布式視頻轉(zhuǎn)碼服務(wù)

可以為客戶提供視頻轉(zhuǎn)碼的分布式網(wǎng)絡(luò)如圖1所示。

圖1 分布式視頻轉(zhuǎn)碼服務(wù)示意圖

圖1中Node表示分布式網(wǎng)絡(luò)中的1個節(jié)點，任意節(jié)點根據(jù)其是否發(fā)出任務(wù)請求(圖1中Task Request)或者是否愿意為服務(wù)節(jié)點Service Node提供資源可以自由地作為客戶節(jié)點或者處理節(jié)點。Client Cluster中的節(jié)點向Processing Node Cluster中的Service Node發(fā)出任務(wù)請求，Service Node根據(jù)當(dāng)前從Processing Node Cluster中獲取的當(dāng)前可利用節(jié)點資源總量的反饋以及從Client Cluster中獲取的發(fā)出請求的各客戶端信道質(zhì)量的反饋接收來自Client Cluster的Task Request;來自客戶的Task Request根據(jù)客戶自身信道質(zhì)量調(diào)整為合適任務(wù)版本后(這里主要是視頻的空間分辨力)作為1個任務(wù)(Job)接入。每個任務(wù)按一定粒度劃分為多個子任務(wù)(Sub－Job)被分配到Processing Node Cluster中的各個處理節(jié)點上進(jìn)行處理［4］。完成處理后，Service Node將重新調(diào)整各處理節(jié)點返回的視頻序列分段向客戶端的發(fā)送順序和間隔，為客戶端提供流暢的視頻服務(wù)。

1.2 問題描述

設(shè)當(dāng)前有n個視頻轉(zhuǎn)碼任務(wù)，集合{delayi}={delay1，delay2，…，delayn}表示其相應(yīng)的服務(wù)延遲，集合{dli}={dl1，dl2，…，dln}表示任務(wù)各自的deadline。{wi}={w1，w2，…，wn}為相應(yīng)任務(wù)在GOP級別并行處理模式下的任務(wù)負(fù)載;對于每一個任務(wù)ti，令ti_j為其按Close－GOP分割后第j個分段，Aj表示當(dāng)前到達(dá)客戶端j的視頻任務(wù)i的分段集合，集合{ATi_k}表示對于客戶任務(wù)ti的第j個分段到達(dá)的時間，集合{EXCi_j}表示該分段在客戶端上的執(zhí)行時間(解碼時間+播放時間)，集合{BSj}表示客戶端j的視頻緩沖區(qū)大小。利用以上設(shè)定，可以把本文1.1節(jié)中所述的兩個問題描述為如下最優(yōu)化問題形式

2 反饋的定義

2.1 處理節(jié)點資源

本文所設(shè)計的任務(wù)接受控制策略使用的反饋有2項:一是處理節(jié)點的資源反饋［5－6］，另一項則是用戶的信道質(zhì)量反饋［7］。在本文的研究中，對于視頻轉(zhuǎn)碼處理任務(wù)，考察的節(jié)點資源為CPU和RAM空閑率。按照1.2中的問題設(shè)定，首先在分布式網(wǎng)絡(luò)中選擇1個處理節(jié)點作為參考節(jié)點，設(shè)εi為處理節(jié)點i的環(huán)境等級因子，用于描述節(jié)點由自身硬件配置決定的視頻轉(zhuǎn)碼任務(wù)處理能力的高低，則參考節(jié)點的環(huán)境等級因子為1。ri表示經(jīng)過本節(jié)公式(1)計算后得到的處理節(jié)點i資源，CoffCPU和CoffRAM分別為CPU和RAM的加權(quán)系數(shù)，表示在視頻轉(zhuǎn)碼處理對二者的占用比重;UCPU_i和URAM_i分別為處理節(jié)點i上當(dāng)前的CPU和RAM的占用率。利用這些變量設(shè)定，我們提出公式1用于計算處理節(jié)點當(dāng)前的可用資源量

2.2 參量εi、CoffCPU及CoffRAM的獲取

通過對視頻轉(zhuǎn)碼實驗(本文主要是空間分辨力轉(zhuǎn)碼)的資源占用數(shù)據(jù)進(jìn)行分析表明，任一空間分辨力視頻轉(zhuǎn)碼任務(wù)在執(zhí)行過程中的資源占用只與其源序列的空間分辨力和序列大小有關(guān)，而與音視頻采樣率，音視頻碼率以及目標(biāo)空間分辨力等其他任務(wù)參數(shù)無關(guān)。表1為實驗中的部分統(tǒng)計數(shù)據(jù)(統(tǒng)計平均)。

表1 不同空間分辨力轉(zhuǎn)碼資源占用統(tǒng)計結(jié)果

此外，實驗表明不同源序列空間分辨力和序列大小的視頻轉(zhuǎn)碼任務(wù)對CPU和RAM占用的比值基本上是不變的。據(jù)此，取一組空間分辨力和大小均不相等的源視頻序列{Si}={S1，S2，…，Sk}，在2.1中所選定的參考節(jié)點上執(zhí)行空間分辨力轉(zhuǎn)碼任務(wù)。令ΔUCPU_j和ΔURAM_j分別為序列Sj處理時的CPU和RAM占用率，則由公式(5)和公式(6)可以分別得到CoffCPU和CoffRAM的值

同樣使用上述隨機(jī)視頻序列{Sj}，令ΔUCPU_j_i和ΔURAM_j_i分別為序列Sj在節(jié)點i上進(jìn)行處理時的CPU和RAM占用率，ΔUCPU_j_s和ΔURAM_j_s為序列Sj在該參考節(jié)點上處理時相應(yīng)的CPU和RAM占用率。則可以由公式(7)計算得到任一處理節(jié)點i相對于該參考節(jié)點的環(huán)境等級因子εi

2.3 信道質(zhì)量反饋的設(shè)定

由于本文研究的主要是有線信道，因此可以認(rèn)為信道自身是穩(wěn)定的，不存在突發(fā)的丟包率波動。因此，文章考慮的信道質(zhì)量主要是信道的等效帶寬。信道等效帶寬決定了視頻分段數(shù)據(jù)從服務(wù)器端傳輸?shù)娇蛻舳怂枰臅r間。若令RTTj為服務(wù)器測得的單位大小數(shù)據(jù)包在客戶端j信道中的往返傳輸時間，BWj為客戶端j與服務(wù)器連接的等效信道帶寬，那么任務(wù)序列i的第k個分段在信道j中的傳輸時延可以由公式(8)計算得出

流式媒體服務(wù)自身的特點決定了1個視頻任務(wù)并不需要客戶端等到所有分段到達(dá)后才開始解碼和播放，只要在當(dāng)前分段播放結(jié)束前，下一個分段到達(dá)客戶端并完成解碼即可實現(xiàn)流暢的視頻服務(wù)。雖然目標(biāo)空間分辨率并不影響視頻轉(zhuǎn)碼任務(wù)執(zhí)行時的資源占用，但其決定處理后的序列分段大小。如果令集合{STi_k}表示任務(wù)序列i的第k個分段從服務(wù)節(jié)點發(fā)出的時間，那么參量Tik與1.2節(jié)中分段到達(dá)時間ATi_k的關(guān)系可由公式(9)表示，而每個視頻分段的播放時間EXCi_k是已知的，因此，流暢視頻服務(wù)的條件則可以表示為公式(10)

3 任務(wù)接收策略

用于任務(wù)接收的兩個控制條件，一是接收的任務(wù)資源占用不能超過當(dāng)前節(jié)點的可用資源總量［8］;另一個則是一輪任務(wù)的接受周期不能太長以至于最先接入的任務(wù)失去其生存周期［9－10］。利用前面3個小節(jié)的設(shè)定，首先設(shè)置1個用于任務(wù)接收控制的資源終止門限Thstop以及1個任務(wù)最大接受周期TAmax。使用的反饋信息為客戶端的信道往返傳輸時延RTTj和信道等效帶寬BWj，并將公式(8)計算得到的傳輸時延Tik_j設(shè)為信道質(zhì)量閾值。根據(jù)公式(10)，對于任一目標(biāo)分辨率的任務(wù)，客戶端相應(yīng)的Tik_j最大值應(yīng)該在兩個相鄰任務(wù)分段連續(xù)發(fā)送，也即發(fā)送間隔趨向于零的時候達(dá)到，即滿足條件Tik_j≤EXCi_k－1。根據(jù)以上分析，本文設(shè)計的動態(tài)任務(wù)接受策略如圖2所示。

4 視頻分段傳輸控制算法

圖2 動態(tài)任務(wù)接收流程

本文1.2節(jié)的問題描述說明了流暢的視頻服務(wù)應(yīng)該滿足的條件，即下1個視頻分段必須在當(dāng)前視頻分段播放結(jié)束之前到達(dá)客戶端。由于每個客戶端信道的質(zhì)量狀況是可以通過反饋信息確定的，因此，傳輸控制算法主要控制的是分段之間的發(fā)送間隔。過大的發(fā)送間隔會導(dǎo)致視頻服務(wù)的中斷，而過小的間隔則會造成客戶端視頻緩沖區(qū)的溢出;合理的傳輸控制算法還應(yīng)該在保證流暢視頻服務(wù)的同時盡量減少其帶來的額外服務(wù)延遲［10－11］。

對于視頻轉(zhuǎn)碼任務(wù)，通過實驗數(shù)據(jù)統(tǒng)計發(fā)現(xiàn)，空間分辨力轉(zhuǎn)碼任務(wù)的處理時間與源序列的空間分辨力和序列大小相關(guān)。本文研究中為便于實驗統(tǒng)計和算法設(shè)計，使用了相同空間分辨力的任務(wù)源視頻序列，則對于任一源序列i，實驗數(shù)據(jù)統(tǒng)計表明其處理時間與序列大小成近似線性正比關(guān)系，由此可以近似得到該序列每個分段的估計處理時間{ETik}={ETi1，ETi2，…，ETih}。由于對于任一分段而言，其大小均小于源序列大小;因此，每一個分段均可以在任務(wù)自身deadline之內(nèi)完成處理。令{WTik}表示任務(wù)i的第k個分段在完成處理后在服務(wù)器端等待發(fā)送的時間，利用本文1.2節(jié)的問題說明和公式(10)的相關(guān)設(shè)定，將流暢視頻服務(wù)的條件進(jìn)一步改寫為

在公式(11)描述的條件中，任務(wù)的估計運行時間ETik、客戶端信道質(zhì)量Tik_j和分段在客戶端上的執(zhí)行之間EXCik均是無法控制的;因此，本文設(shè)計的傳輸控制算法控制的參量主要是分段在服務(wù)器端的等待時間WTik。對于到達(dá)服務(wù)器端的任務(wù)序列i的分段k，本文提出的控制算法處理步驟如下:

步驟1，若k=1，檢查第k+1個分段是否到達(dá)服務(wù)器端;若分段k+1尚未到達(dá)，跳轉(zhuǎn)至步驟3，否則跳轉(zhuǎn)至步驟4。

步驟2，若k＞1，檢查第k－1個分段是否到達(dá)服務(wù)器端;若分段k－1已發(fā)送，跳轉(zhuǎn)至步驟5;若分段k－1到達(dá)服務(wù)器端尚未發(fā)送，跳轉(zhuǎn)至步驟6;否則等待分段k－1。

步驟3，計算WTik=×(ETik+1+Tik+1_j)，比較WTik與dli－ETik－Tik_j的大小;若WTik≤dli－ETik－Tik_j，則分段k在等待WTik時間后發(fā)送;否則等待dli－ETik－Tik_j時間后發(fā)送。

步驟4，直接發(fā)送分段k，并跳轉(zhuǎn)至步驟2。

步驟5，檢查分段k+1是否到達(dá)服務(wù)器;計算WTik=× (ETik+1+Tik+1_j)，若 WTik+Tik_j≤ EXCik－1，分段k在等待WTik后發(fā)送;否則等待EXCik－1－Tik_j時間后發(fā)送分段k，考察分段k+1，跳轉(zhuǎn)至步驟3。

步驟6，立即發(fā)送分段k－1，跳轉(zhuǎn)至步驟5。

5 仿真與實驗

對本文算法的驗證實驗，選擇在UNIX環(huán)境下使用C語言編程進(jìn)行實現(xiàn)，使用的實驗編程環(huán)境為Ubuntu11.04，編譯器版本gcc－4.5.1，系統(tǒng)內(nèi)核版本為Linux－2.6.38。利用前文對轉(zhuǎn)碼任務(wù)資源占用的特點分析，實驗中對不同序列使用資源占據(jù)因子ε來計算其資源占用。實驗中有意選擇了Close－GOP分段大小不均勻的序列(但排除大小差異極大的極端情況)便于對比本文提出的傳輸控制算法在保障流暢視頻服務(wù)上的效能。在實驗中使用的視頻序列參數(shù)如表2所示，每個任務(wù)序列均有176×144，360×240和480×360這3種不同的可供客戶端選擇的目標(biāo)分辨力，其相應(yīng)的客戶信道質(zhì)量閾值分別設(shè)置為0.2 s，0.3 s和0.5 s，3種目標(biāo)分辨力的任務(wù)各自的deadline分別設(shè)為6 s，8 s和12 s。此處為方便實驗對比，有意限制了等效帶寬;deadline是目前相應(yīng)分辨力視頻服務(wù)常見的deadline。

表2 用于實驗的視頻序列信息

一共設(shè)置了30個客戶端節(jié)點，每個節(jié)點的任務(wù)請求均相互獨立。實驗中，將測試在使用和未使用本文所設(shè)計的傳輸控制算法的情況下，每個客戶端的服務(wù)延遲以及視頻的中斷情況。

圖3為使用和未使用傳輸控制算法的情況下，客戶端收到視頻服務(wù)的延遲對比。

圖3 客戶端服務(wù)延遲對比

圖4為使用和未使用傳輸控制算法的情況下，客戶端收看到視頻的總中斷時間對比。

圖3和圖4所描述的實驗結(jié)果表明，在服務(wù)器端使用本文設(shè)計的傳輸控制算法之后，相比于不使用該控制算法的情況下，客戶端收看到視頻服務(wù)的延遲會略有增加。時間的增量按照源視頻序列Close－GOP分段的大小波動情況的不同大約在5%～25%之間(實際延遲增量在0.2～1.5 s之間)，但任務(wù)的延遲基本上仍控制在實驗中設(shè)定的deadline范圍之內(nèi)。而在圖4中，視頻服務(wù)的中斷情況相比不使用傳輸控制算法的情況而言有了較為明顯的改觀;相比而言，出現(xiàn)服務(wù)中斷的任務(wù)有所減少。但同時也可以看到，本文提出的傳輸控制算法并不能完全杜絕流式視頻服務(wù)的中斷;由于人眼的視覺暫留效應(yīng)，只要中斷時間足夠短，在用戶看來也屬于流暢的視頻服務(wù)。而圖4中表明，在使用了本文設(shè)計的傳輸控制算法之后，出現(xiàn)中斷的視頻，其在實驗中表現(xiàn)出的中斷時間基本被控制在0.5s以內(nèi)，具有較為良好的視覺流暢性。對比本文提出的分段傳輸控制算法在視頻服務(wù)流暢性上的提升，該算法的延遲代價是可以接受的。

圖4 客戶端視頻總中斷時間對比

6 小結(jié)

本文針對分布式網(wǎng)絡(luò)中流媒體服務(wù)的客戶請求接受和流暢服務(wù)的傳輸控制問題進(jìn)行了一定的探索和研究，通過對空間分辨力視頻轉(zhuǎn)碼任務(wù)執(zhí)行時對處理資源的占用分析發(fā)現(xiàn)其資源占用只與源序列分辨力和序列大小相關(guān)的特點。結(jié)合不同分辨力的流式視頻服務(wù)隊客戶信道等效帶寬和傳輸延遲的需求，本文提出了基于節(jié)點資源和客戶信道質(zhì)量反饋的自適應(yīng)客戶任務(wù)請求接收算法。此外，通過分析為實現(xiàn)流暢視頻服務(wù)視頻的分段的發(fā)送控制需要滿足的條件，本文提出了用于保障視頻服務(wù)流暢性的視頻分段傳輸控制算法。通過實驗，證明了本文提出的分段傳輸控制算法可以在較小的額外延遲代價條件下，較為有效地減少流式視頻服務(wù)的中斷概率，提高客戶端收看視頻的流暢性。

［1］LUO Haiyan，SONG Ci，WU Dalei.A cross－ layer optimized distributed scheduling algorithm for peer－to－peer video streaming over multi－h(huán)op wireless mesh networks［C］//Proc.IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks.［S.l.］:IEEE Press，2009:1－9.

［2］NAZARI S，HAMID B.A new distributed uplink packet scheduling algorithm in WiMAX networks［C］//Proc.International Conference on Future Computer and Communication.［S.l.］:IEEE Press，2010:232－236.

［3］TSAI Chenghan ，HUAN Taiyi.An efficient real－time disk－scheduling framework with adaptive quality guarantee［J］.IEEE Trans.Computers，2008，57(5):634－657.

［4］ANTIF Y，HAMIDZADEH B.A scalable scheduling algorithm for realtime distributed systems［C］//Proc.International Conference on Distributed Computing System.［S.l.］:IEEE Press，1998:352－359.

［5］BIZZARRI P，BONDAVALLI A，GIANDOMENICO F D.A schedulin algorithm for aperiodic groups of tasks in disributed real－time system［EB/OL］.［2011－11－03］.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.8989＆rep=rep1＆type=pdf.

［6］LU Chenyang ，WANG Xiaorui，KOUTSOUKOS X.Feedback utilization control in distributed real－time systems eith end－to－end tasks［J］.IEEE Transactions on Parallel and Distributed System，2005，16(6):500－561.

［7］ZHANG Dongsong，JIN Shiyao，WU Tong，et al.Feedback－ based energyaware scheduling algorithm for hard real－time tasks［C］//Proc.IEEE InternationalConference on Networking，Architecture and Storage.［S.l.］:IEEE Press，2009:211－214.

［8］LIU C L，LAYLAND J W.Scheduling algorithms for multiprogramming in a hard－real－time enviroment［EB/OL］.［2011－11－03］http://inst.eecs.berkeley.edu/～ee249/fa07/discussions/liu73scheduling.pdf.

［9］WANG Chenjun.The research on real－time scheduling algorithm in distributed system［C］//Proc.Pacific－Asia Conference on Knowledge Engineering and Software Engineering.［S.l.］:IEEE Press，2009:71－74.

［10］CHAI Yunpeng，DU Zhihui，LI Sanli.A new scheduling algorithm for distributed streaming media system based on multicast［C］//Proc.The 28th International Conference on Distributed Computing Systems Workshops IEEE Computer Society.［S.l.］:IEEE Press，2008:587－592.

［11］LI Jie，GUO Ruifeng，SHAO Zhixiang.The Research of Scheduling Algorithms in Real－time System［C］//Proc.International Conference on Computer and Communication Technologies in Agriculture Engineering.［S.l.］:IEEE Press，2010:333－336.