分布式視頻轉碼服務調度算法研究

譚智一，宋建新

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

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

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

1 研究背景及問題描述

1.1 分布式視頻轉碼服務

可以為客戶提供視頻轉碼的分布式網絡如圖1所示。

圖1 分布式視頻轉碼服務示意圖

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

1.2 問題描述

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

2 反饋的定義

2.1 處理節點資源

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

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

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

表1 不同空間分辨力轉碼資源占用統計結果

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

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

2.3 信道質量反饋的設定

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

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

3 任務接收策略

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

4 視頻分段傳輸控制算法

圖2 動態任務接收流程

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

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

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

步驟1，若k=1，檢查第k+1個分段是否到達服務器端;若分段k+1尚未到達，跳轉至步驟3，否則跳轉至步驟4。

步驟2，若k＞1，檢查第k－1個分段是否到達服務器端;若分段k－1已發送，跳轉至步驟5;若分段k－1到達服務器端尚未發送，跳轉至步驟6;否則等待分段k－1。

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

步驟4，直接發送分段k，并跳轉至步驟2。

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

步驟6，立即發送分段k－1，跳轉至步驟5。

5 仿真與實驗

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

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

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

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

圖3 客戶端服務延遲對比

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

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

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

6 小結

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

［1］LUO Haiyan，SONG Ci，WU Dalei.A cross－ layer optimized distributed scheduling algorithm for peer－to－peer video streaming over multi－hop 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.