基于用戶行為特征的SVC分片調度算法

唐朝偉,張 希,王雪鋒,周 旭,宋俊平

(1.重慶大學通信工程學院,重慶400030;2.中國科學院聲學研究所高性能網絡實驗室,北京100190)

基于用戶行為特征的SVC分片調度算法

唐朝偉1,張 希1,王雪鋒1,周 旭2,宋俊平2

(1.重慶大學通信工程學院,重慶400030;2.中國科學院聲學研究所高性能網絡實驗室,北京100190)

針對異構環境中網絡和終端的復雜性,以及用戶隨機搜索行為造成的視頻點播服務中播放進度的突變性,提出一種異構環境中基于用戶行為特征的可擴展視頻編碼分片調度算法。設計2類調度窗口,即根據當前播放時刻保證順序播放數據持續功能的播放窗口和依據服從Weibull分布的用戶隨機搜索行為設計的加入數據預取機制的錨點窗口。對播放窗口和第一個錨點窗口采用逐層調度策略,以保證數據的及時性,其余錨點窗口使用rarestfirst策略,以平衡整個系統的分片分布。在OverSim平臺上的仿真結果表明,與現有的逐層調度算法和權值調度算法相比,該算法在發生用戶隨機搜索行為的應用場景中能提高節點分片調度性能,縮短響應時延,降低服務器負載,提高用戶觀看視頻的質量和流暢度。

異構環境;用戶行為;分片調度;錨點窗口;對等網絡;可擴展視頻編碼

1 概述

近年來,互聯網行業中對等網絡(Peer-to-Peer Network,PPN)技術發展迅速,這歸功于它不僅能夠明顯地緩解傳統C/S(客戶端/服務器)網絡架構中服務器端負載壓力過大、單點失效等瓶頸問題,具有低成本、可擴展、健壯等優勢,又能充分利用和分享各終端的豐富資源,在現今網絡視頻需求和流量的飛速增長的大環境下,基于對等網絡的視頻流媒體技術在當前互聯網領域得到廣泛的應用[1]。

隨著無線移動互聯網日新月異的發展以及三網融合產業蒸蒸日上的趨勢,當前所面臨的是一個越發豐富和復雜的異構環境。主要表現在:(1)網絡異構,表現為接入網類型多樣化,如3G、以太網、WLAN、LTE等;(2)終端異構,表現為用戶所使用客戶終端類型多樣化。除了傳統的電腦作為視頻流媒體系統客戶終端,電子產品的發展也使智能電視機、便攜的平板電腦、智能手機等成為當下流行的流媒體播放載體[2]。

要處理好異構環境中所普遍存在的用戶帶寬、處理能力、分辨率、在網時間等方面的差異,可擴展視頻編碼(Scalable Video Coding,SVC)技術在對等網絡視頻流媒體系統中的應用已獲得越來越多的關注。SVC技術將同一視頻文件編碼成一個基礎層(Base Layer,BL)和若干增強層(Enhancement Layer, EL),用戶可根據自身網絡狀況和終端能力合理選擇接受層數,形成同一視頻文件以不同的播放質量適應不同的用戶終端的模式,更加適用于異構環境[2]。

在基于對等網絡+SVC流媒體系統的視頻點播服務中,客戶端的分片調度方法舉足輕重,直接影響用戶觀看質量和整個系統的負載及分發效率。隨著快餐速食文化模式的發展,一個用戶體驗質量高且生命力長的視頻點播服務,不但要滿足用戶隨意選擇觀看內容,還要支持用戶在觀看視頻過程中類似使用傳統錄像機的一些交互式操作(VCR操作)。如在客戶端播放過程中可隨意暫停、恢復播放,以及一些隨機搜索的行為即隨機改變播放進度,如前向搜索、后向搜索等[3]。研究表明,用戶行為是服從一定統計分布的高頻行為[3-4],所以,在分片調度算法中還應考慮到此因素,使用戶盡可能流暢地欣賞視頻內容,縮短由于發生VCR行為特別是其中的隨機搜索行為引起的響應時間。

傳統的調度算法采取將視頻數據根據大小分塊[5],沒有考慮到異構環境的適用性以及對網絡動態變化的彈性自適應。隨著異構環境的復雜度增加,需要在異構環境中生存的對等網絡+SVC分片調度算法越來越受到重視。在調度算法中引入窗口概念也成為熱點,其將視頻數據的下載范圍局限在一個或多個實時的窗口中,這樣通過窗口的規劃、下載策略和滑動可以有條不紊地合理利用資源,實現優化調度。文獻[6-8]采用了視頻SVC分層的處理方法以及單窗口分層以固定順序下載的策略,在調度上利用了SVC的分層特性,保證了播放的實時性,但該方法只考慮到順序播放中靠近播放點的數據到達的實時性,未考慮到整個系統的分發效率。文獻[9-10]采取窗口內下載順序根據分片權值的大小來決定的策略,綜合考慮待下載分片距離播放點遠近、分片稀有程度(在鄰居節點存在的拷貝數目)、基礎層分片等因素,但未考慮用戶行為。文獻[11]提出一種考慮用戶行為、跳轉受限、流行度感知的數據預取機制,但是沒有把異構環境納入考慮因素。

基于對等網絡+SVC技術,通過在視頻點播系統客戶端上引入數據預取功能以解決上述問題。數據預取即根據現在的播放情況預測用戶的將來數據需求,更好地利用合理的空閑資源預先獲取部分數據[5],以便在用戶人為改變播放進度時,系統各終端能夠作出及時響應,優先使用本地資源。

本文基于對等網絡和SVC技術的視頻點播系統,考慮用戶隨機搜索行為,運用窗口概念,提出一種基于用戶行為特征的Anchor-對等網絡SVC分片調度算法(UACS),該算法在縱向(“層”的角度)上根據網絡和終端條件選擇下載SVC層數,在橫向(“時間”的角度)采用一個播放窗口+若干錨點窗口的模式。前者保證順序播放條件下的數據持續,后者根據用戶隨機搜索行為特征的數學模型生成,從而保證在發生用戶隨機搜索行為時能優先利用預取數據,縮短響應時間,提高用戶體驗質量。

2 用戶行為數學模型

流媒體系統在為用戶提供視頻點播服務時,在客戶端可發生一系列隨機搜索的用戶行為,文獻[3]的測量、分析、總結顯示,用戶在觀看視頻過程中發生的隨機搜索行為(隨機跳轉長度)符合Weibull分布,概率密度函數如下:

視頻文件的長度不同(分為長視頻、短視頻),隨機搜索的方向不同(分為跳轉到大于當前播放點時刻的前向搜索,跳轉到小于當前播放點時刻的后向搜索),所滿足的Weibull分布參數也不一樣,如表1所示。

表1 隨機搜索跳轉長度特征參數設置

流媒體點播服務支持客戶端用戶邊看邊下載,看過的內容得以保存,則小于播放點播放時刻的后向搜索易于實現。因此,本文在設計調度算法時主要考慮的應用場景是用戶發生的長視頻前向搜索跳轉行為。由表1可知,其跳轉長度分布服從參數α=0.10916,β=0.54129的Weibull分布。

3 本文算法設計

在本文基于異構環境中用戶行為特征的Anchor-對等網絡SVC分片調度算法中,運用原有窗口概念,除設計保證數據及時性的播放窗口外,引入考慮用戶行為的錨點窗口。其中,播放窗口采用已有的逐層調度策略;錨點窗口則根據用戶行為特征模型對播放窗口進行補償以及分段輻射整個播放區間,并根據播放進度周期更新。通過播放窗口+錨點窗口的機制,既保證播放的實時性,又縮短用戶行為引起的響應時延。

主要步驟如下:

Step1根據當前播放時刻狀況,依據上述窗口設計的原則規劃播放窗口和錨點窗口的數據范圍。

Step2首先申請下載播放窗口中分片,然后為第一錨點窗口分片,最后為剩下錨點窗口分片。

Step3判定緩存達到解碼播放條件,進行播放。

Step43種情況下播放窗口被觸發滑動,則重復Step1。

Step5播放結束。

3.1 播放窗口的設計

播放窗口的設計準則是保證順序播放中數據的及時性,因此,在設計上緊緊結合當前播放點Pcurrent。設計如下:

(1)窗口size:初始化播放窗口的size為固定值。

(2)窗口的滑動:播放窗口從播放時間為0時開始生成,窗口滑動的觸發模式有3種:

1)窗口的周期更新:系統中每次觸發窗口滑動更新后會在指定的周期時間后再次滑動窗口,每次滑動步長為一個播放窗口size。

2)窗口內數據下載完畢后即時更新:當前窗口內所有的數據申請下載完畢或判定放棄后,距離上次周期更新的時間還未達到周期更新時間,那么會自動觸發即時更新機制,每次滑動步長為一個播放窗口size,周期更新計時刷新。

3)用戶行為的影響:系統內發生用戶前向搜索的行為,播放窗口需要及時反應,窗口起始點更新為用戶跳轉后的當前播放時刻Pcurrent。

(3)窗口內數據塊的調度:由于播放窗口中的數據是所有窗口中數據緊急度最高的區域,具有最高的優先級,因此采用逐層依次調度的策略,即規劃到播放窗口的數據塊依次從基礎層到增強層對分層中缺失的分片進行請求下載。同一分層內,距離播放點越近的分片具有越高的請求下載優先級。

3.2 錨點窗口的設計

除了保證用戶在順序播放過程中數據塊的及時性所設置的播放窗口,本文根據用戶行為的特征模型設計了實現數據預取功能的錨點窗口。根據播放點離結束點的距離計算錨點窗口個數,根據錨點輻射區間范圍內用戶跳轉累計概率,計算該錨點窗口大小。參數說明如表2所示,其中,調整參數根據分片長度和緩存能力設置。

表2 錨點窗口參數描述

錨點窗口的個數、長度計算原理如下:

(1)錨點窗口實時個數:

(2)錨點分區長度:

(3)第n個錨點輻射區間范圍:

第n個錨點輻射區間對應窗口比重:

第n個錨點輻射區間錨點窗口長度:

在確定錨點窗口數目和長度后,數據的調度策略為:第1個錨點窗口是緊跟著播放窗口,根據在Weibull分布的特征,用戶搜索步長落在第1個錨點窗口內的數據被搜索的概率也最大,故將其視為對播放窗口的補償。在此窗口內數據的下載調度采取逐層的方式。

為了均衡整個流媒體視頻點播系統的數據片分布,在余下錨點窗口內,采取rarest-first策略,即是將剩下窗口內的數據片根據鄰居節點中擁有的拷貝數目進行從小到大排列,先下載拷貝數最少的片,如果拷貝數相等則依次優先考慮所在層數越低、距離播放越近的分片。

4 仿真實驗與性能評估

本文基于OverSim仿真平臺,搭建一個對等網絡流媒體系統,模擬異構環境,基于等時長分片的方式[12]采用SVC可擴展視頻編碼技術將視頻源文件分成一個可獨立解碼的基礎層和17個依賴于低層解碼的增強層,每個客戶端節點根據自身入網類型需求申請可下載的SVC視頻層數。

4.1 關鍵性能指標

本文選擇2個重要參數作為分片調度算法的關鍵性能指標,也是此仿真實驗的重要測量對象:

(1)平均接收SVC視頻層數:在客戶端節點使用點播服務過程中,平均接收SVC視頻層數直接反映了客戶端觀看視頻的質量,實際接收SVC視頻層數越多,則獲得的視頻質量越好。

(2)數據塊本地命中率:除了需要測量用戶觀看視頻的質量,觀看視頻時流暢度也是一個重要的性能。在發生用戶跳轉行為時,播放點所在數據塊(即將解碼播放的當前數據塊)若已下載,滿足即時播放的條件,則將其視為數據塊本地命中。數據塊本地命中率越高,則視頻播放越流暢。

4.2 結果分析

為了評估以上調度算法的性能,在OverSim仿真系統中,將基于用戶行為特征的Anchor-對等網絡SVC分片調度算法與基于逐層(Layer by Layer,LL)的分片調度算法[7]和基于權值的分片調度(Score Based Chunk Scheduling,SCS)算法[11]進行實驗。

仿真實驗拓撲如圖1所示。

圖1 仿真實驗拓撲

仿真實驗節點生成為4類:1個Traker,負責索引服務;5個種子節點(Seeds),其擁有視頻文件的所有分片;100個Client節點,分為固網、WLAN、3G,如表3所示。在初始階段,網絡中除了Traker,還有5個以太網方式接入的種子節點。將100個Client節點逐個加入網絡,每個新加入的節點從Traker服務器獲取鄰居節點列表,交換bitmap獲取各鄰居節點的分片擁有情況。

表3 3類Clients節點參數

仿真實驗采用播放時長為60 min(代表長視頻)的視頻源,SVC編碼后共18層。仿真過程中利用Weibull隨機序列發生器模擬系統中各Client節點的發生跳轉的用戶行為,每隔1s統計各Client節點的實際播放層數,以及每次發生跳轉時統計跳轉播放點所在數據塊是否下載。播放結束后,計算實際播放層數的平均值和數據塊本地命中率。

從圖2可以看出,Wired節點、WLAN節點及3G節點客戶端在發生用戶隨機搜索操作行為(LLVCR和SCS-VCR)時的平均接收層數相比只考慮順序播放(LL、SCS)分別降低約36%,24%及18%。說明用戶隨機搜索行為會對只考慮順序播放的算法中的視頻點播體驗造成嚴重影響。

圖2 Client節點平均實際接收視頻層數

從圖3～圖5的Wired、WLAN、及3G用戶節點的實驗結果可以看出,與LL和SCS算法相比,在發生用戶跳轉行為的視頻播放過程中,綜合考慮異構環境和用戶行為的本文算法在不同終端所統計的平均實際解碼接收SVC視頻層數都集中于高質量部分,如WLAN Clients節點統計結果中,使用本文算法有63.1%的用戶可以觀看8層及以上質量的視頻,而LL和SCS算法分別為43.4%和22.9%,明顯看出,本文算法在發生用戶跳轉的應用場景中都優于對比算法,即能使用戶享受到更好的視頻質量。從圖6可以看出,使用本文算法在不同終端所統計的數據塊本地命中率比2種對比算法都有所提高。綜上,使用該算法能從整體上降低響應用戶隨機搜索操作所需要的時間,從而提高觀看過程中的流暢度,減小服務器的負載。

圖3 Wired類型節點平均接收視頻層數

圖4 WLAN類型節點平均接收視頻層數

圖5 3G類型節點平均接收視頻層數

圖6 節點數據塊本地命中率平均值

5 結束語

本文研究異構環境下基于對等網絡+SVC流媒體系統中的分片調度問題。在分析視頻點播用戶隨機搜索行為特征的基礎上,提出一種基于用戶行為特征的Anchor-對等網絡SVC分片調度算法。其優勢在于在客戶端建立播放窗口+錨點窗口的機制,并分別采取不同的調度策略,在保證數據及時性和分片分發效率的同時,解決了用戶隨機搜索行為對播放質量的干擾。仿真結果表明,該算法綜合考慮異構環境和用戶行為,保證用戶觀看視頻時的質量和流暢度,提高用戶體驗,同時也減少了服務器的負載。

[1] 張春紅,裘曉峰,弭 偉,等.P2P技術全面解析[M].北京:人民郵電出版社,2010.

[2] 宋俊平,張 棪,周 旭,等.基于SVC的P2P流媒體系統研究綜述[J].計算機應用研究,2013,30(4): 965-970.

[3] Garcia R,PanedaXG,GarciaV,etal.Statistical Characterization of a Real Video on Demand Service:User Behavior and Streaming-media Workload Analysis[J]. Simulation Modeling Practice and Theory,2007,15(6):627-689.

[4] Choi J,Reaz A,Mukherjee B.A Survey of User Behavior in VoD Service and Bandwidth-saving Multicast Streaming Schemes[J].IEEECommunicationsonSurveys& Tutorials,2012,14(1):156-169.

[5] 朱子榮,壽志勤.P2P點播系統中資源下載算法的研究[J].計算機應用與軟件,2008,25(10):175-178.

[6] Asiolo S,Ramzan N,Izquierdo E.Efficient Scalable Video Streaming over P2P Nextwork[M].Berlin, Germany:Springer,2010.

[7] Ding Yan,Liu Jiangchuan,Wang Dan,et al.Peer-to-peer Video-on-demand with Scalable Video Coding[J]. Computer Communications,2010,33(14):1589-1597.

[8] Lee T C,Liu P C,Shyu W L,et al.Live Video Streaming Using P2P and SVC[M].Berlin,Germany:Springer,2008.

[9] Abboud O,Zinner T,Pussep K,et al.On the Impact of Quality Adaptation in SVC-based P2P Video-on-demand Systems[C]//Proceedings of the 2nd Annual ACM Conference on Multimedia Systems.New York,USA: ACM Press,2011:223-232.

[10] Liu Zhengye,Shen Yanming,Shivendra S P,et al.Using Layered Video to Provide IncentivesinP2PLive Streaming[C]//Proceedings of Workshop on Peer-topeer Streaming and IP-TV.New York,USA:ACM Press,2007:311-316.

[11] 王 娟,紀其進,朱艷琴,等.基于用戶行為特征的P2P視頻點播系統數據預取機制[J].小微型計算機系統, 2010,31(10):2049-2053.

[12] Zhang Yan,Zhou Xu,Song Junping,et al.Time-stamped Equal Size Segmentation and Chunk Scheduling Algorithms for SVC Based P2P Streaming Systems[C]//Proceedings of the18th IEEE International Conference on Parallel and Distributed Systems.[S.l.]:IEEE Computer Society,2012: 706-707.

編輯 劉 冰

SVC Fragment Schedule Algorithm Based on User Behavior Characteristic

TANG Chaowei1,ZHANG Xi1,WANG Xuefeng1,ZHOU Xu2,SONG Junping2
(1.College of Communication Engineering,Chongqing University,Chongqing 400030,China;
2.High Performance Network Lab,Institute of Acoustics,Chinese Academy of Sciences,Beijing100190,China)

In view of the complexity of the network and terminal in heterogeneous environment,and the mutability of playback progress in the video-on-demand service that is caused by user random seeking,an Scalable Video Coding (SVC)fragment schedule algorithm based on user behavior characteristic is proposed.In the proposed algorithm,two types of windows are designed.One is playback window based on current playtime to ensure order data continues,the other one is anchor window designed with data prefetching,which is based on user random seeking following the Weibull distribution.The Layer-by-Layer(LL)schedule strategy is utilized in playback window and the first anchor window to ensure the timeliness of data,and the rarest-first strategy is used in the other anchor windows to balance the fragment distribution of the whole system.Simulation results in OverSim show that,compared with current LL schedule algorithm and weighted schedule algorithm,the proposed algorithm can improve the fragment scheduling performance,shortens the response time delay,reduces the server load,and improves the quality and fluency of the user in watching video.

heterogeneous environment;user behavior;fragment schedule;anchor window;Peer-to-Peer Network (PPN);Scalable Video Coding(SVC)

唐朝偉,張 希,王雪鋒,等.基于用戶行為特征的SVC分片調度算法[J].計算機工程,2015, 41(2):248-252,257.

英文引用格式:Tang Chaowei,Zhang Xi,Wang Xuefeng,et al.SVC Fragment Schedule Algorithm Based on User Behavior Characteristic[J].Computer Engineering,2015,41(2):248-252,257.

1000-3428(2015)02-0248-05

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.02.047

國家科技重大專項基金資助項目(2011ZX03005-004-02);國家自然科學青年基金資助項目(61102076)。

唐朝偉(1966-),男,教授、博士后,主研方向:網絡多媒體技術;張 希(通訊作者)、王雪鋒,碩士;周 旭,副研究員、博士;宋俊平,博士。

2014-03-05

:2014-04-04E-mail:zhangxi1989xi@163.com