高偉濤,崔占忠,張海旸

(1.北京理工大學 宇航學院, 北京 100081； 2.北京郵電大學 計算機科學與技術學院, 北京 100876)

網格是目前比較熱門的一個研究領域,它被普遍認為是下一代的互聯(lián)網. 網格最大的特點是各種資源的充分共享,這種共享是智能的、普遍的和便利的,這使得網絡上的各種資源可以得到充分有效的利用,并且精簡了網絡終端的功能. 在網格中較為普遍的一種服務就是VoD服務,因此針對多媒體服務中的視頻流進行研究，可以為這種多媒體服務提供更好的QOS保證.

在網格中服務的方式采用多對多服務模式,也就是多個服務器對多個用戶進行并行服務. 這樣可以充分、有效地利用這多個服務器的資源,并且可以為用戶提供更穩(wěn)定、優(yōu)良的服務質量. 在這種服務模式下,Internet網絡的多媒體VoD的視頻流模型已經不再適用,為此作者在已有VoD視頻流模型的基礎上，提出了三層隨機過程描述方式,對網格中的VoD服務中的視頻流進行建模.

較早的視頻業(yè)務流量模型是由Maglaric等人提出的一階自回歸AR模型[1],在此基礎上R.Grunenfelder和徐樹公等分別提出了ARMA模型及基于Gamma分布的AR模型[2-3]. 這些模型將視頻數據流量視為一個平穩(wěn)隨機過程,只適合于無場景變化的視頻源. 而實際的視頻流大多是非平穩(wěn)隨機過程,文獻[4-5]中根據I幀或GOP的數據量大小,通過閾值分割法,將這一非平穩(wěn)隨機過程劃分為一段段近似平穩(wěn)隨機過程,但是這種分割方法的閾值不易確定. 文獻[6]中提出了基于視頻圖像內容的分割方法,提出了由AR模型調制的半馬爾可夫隨機過程,它可以適合于各種場景的視頻業(yè)務流量模型.

作者針對網格中不同的流媒體服務方式,對AR模型進行了改進,提出了復合AR模型(MAR). 在視頻圖像分割方法的基礎上,將一段視頻分割成為多個視頻片斷,把每一個視頻流片斷內部當作平穩(wěn)過程看待,采用AR模型來描述,把每一個視頻流片段之間近似看作是半馬爾可夫過程. 并且考慮到了不同視頻流段的來源不同，從而僅在每一個視頻流段中視頻流片斷符合半馬爾可夫過程,而在整個視頻流中各個視頻流片斷符合泊松分布.

1 網格中的VoD服務模式

在網格中有多個VoD服務器對用戶同時提供服務，在此只考慮一個用戶情況下的服務模式,將多對多模型簡化成為多對一的服務模型. 不失一般性,假設有3個VoD服務器,通過3條不同帶寬、不同延遲和不同丟包率的鏈路來同時為一個用戶提供服務. 這3個服務器分別為S1,S2,S3,3個鏈路的帶寬分別為B1,B2,B3,3個鏈路的延遲分別為τ1,τ2,τ3,3個鏈路的丟包率分別為ε1,ε2,ε3. 網格中的VoD的多對一的服務種類有2種：一為多個VoD服務器,每個根據自身的帶寬、延遲和丟包率分別傳輸一段視頻流給用戶,在客戶端將這些視頻流進行合成；二為從這些VoD服務器中選擇一個性能最優(yōu)的服務器來為用戶提供服務,在其它的服務器中選擇一個備份服務器組提供各種備份流以保證不同的服務質量要求.

本文中討論多個VoD服務器，每個服務器根據自身的帶寬、延遲和丟包率的合成函數,分別傳輸一段視頻流V1,V2,V3,在客戶端將這些視頻流段進行合成. 每個視頻流段的時間長度用式(1)計算

t=C1B+C2τ+C3ε.

(1)

式中C1,C2,C3分別為帶寬、延遲和丟包率在計算視頻流段時間長度時的權值. 帶寬、延遲和丟包率分別為歸一化值,折合為時間量. 在VoD點播中,帶寬為主要因素,帶寬直接決定可用的傳輸速率. 延遲和丟包率對于VoD業(yè)務的質量、傳輸速率有較小的影響,對視頻流的抖動有一定影響,因此C1的值應該比C2,C3大一些,其確切值由實際VoD服務進行測定.

2 網格中的MAR流媒體服務模型

假設各個VoD服務器和客戶端之間的鏈路是穩(wěn)定的,不會發(fā)生故障,鏈路的帶寬、延遲和丟包率也是恒定的不隨時間改變的,因而各個VoD服務器提供的視頻流段長度固定且不隨時間變化.

在VoD視頻流中,當量化尺度及GOP格式固定后,其輸出的數據比特流的大小主要由視頻圖像紋理的復雜度和圖像運動的復雜度決定. 因此可以根據圖像復雜度將視頻流分割成一段段近似平穩(wěn)的視頻片斷. 為簡化起見,將視頻片斷分為高、中、低復雜度3種類型(H,M,L). 在視頻片斷內部,數據流可以假設為平穩(wěn)的,因此可以用一階自回歸AR模型進行模擬[6]. 對于MPEG壓縮方式的VoD視頻流,假設GOP格式為IBBPBBPBBPBB,因此可用3個一階AR模型分別對I，P和B幀進行模擬. 則一個視頻片斷可定義為[2-3]

X(i)=[ARIARPARBt(i)].

(2)

式中t(i)為每個視頻段持續(xù)的時間. AR模型定義為

λ(k)=aλ(k-1)+bw(k),|a|<1.

(3)

式中：λ(k)為壓縮后第k幀每個像素的平均比特數；a,b為常數；w(k)為均值為η,方差為1的正態(tài)高斯白噪聲.λ(k)的均值、方差和自相關函數分別為

E(λ)=bη/(1-a),

(4)

(5)

(6)

每個來自于某個VoD服務器的視頻流段由若干個視頻片斷組成,每一個視頻片斷分別屬于{H,M,L}這3個狀態(tài),并且更新間距為：t={τn,n=0,1,2,…}. 令隨機序列X={Xn,n≥0}具有狀態(tài)空間為視頻片斷復雜度于視頻片斷來源的組合：{H1,H2,H3,M1,M2,M3,L1,L2,L3},下標1,2,3分別代表來自不同的VoD視頻服務器. 對于確定的一個視頻流片斷,它只能在{H,M,L}3個狀態(tài)之間進行轉換,由于這3個狀態(tài)之間的相關性與實際的視頻流的內容有關,因此只能根據統(tǒng)計來確定這些狀態(tài)之間的轉移概率矩陣Pij,i,j∈{H,M,L}.

由于在每個視頻片斷的轉移與前面的視頻片斷的狀態(tài)無關,因此可以將隨機序列X看做是馬爾可夫鏈. 而在一個視頻流段內部的視頻流片斷序列定義為隨機過程

B={Bt,t≥0,且Bt=Xn,當τn-1≤t≤τn}.

(7)

隨機過程B即為由馬爾可夫鏈調制的半馬爾可夫過程.

對于每一個VoD服務器提供的視頻流來說,雖然每個視頻流段的時間長度不同,但是這個長度是相對固定的. 因此可以把整個視頻流看作是這些視頻流段組成的Poisson過程. 來自3個VoD服務器的視頻流的長度固定為Tv1,Tv2,Tv3,而且假設視頻流的順序為任意的,即V1,V2,V3,可以隨機排列. 每兩個視頻流之間的間隔為tSi. 這樣,當把視頻流段的長度和間隔看成是對于視頻流段到達的隨機時間,則整個視頻流所包含的視頻流段數{N(t),t≥0}可以看成是一個Poisson過程.

(8)

λ=E{N(t)}/t.

(9)

E{S(t)}=(λt)E{Yn},

(10)

(11)

而考慮到視頻流片斷之間是半馬爾可夫過程，以及視頻流片斷內部是平穩(wěn)隨機過程,則整個視頻流可以表示為三重的隨機過程：在最高層,視頻流可以看作由視頻流段組成的類似復合泊松過程,而每個視頻流段可以看成由視頻流片斷組成的半馬爾可夫過程,最后,每個視頻流片斷的內部可以看成是平穩(wěn)過程.

3 仿真實驗

由于網格規(guī)模龐大,要在網格上實現(xiàn)較好的流媒體服務,對流媒體調度算法的要求非常高,在調度算法的研究中,無法直接應用到大規(guī)模的實際網格中檢驗其性能,必須通過仿真大規(guī)模網格,以及其上的流媒體業(yè)務模型來驗證調度算法的性能.

在流媒體調度算法的實驗中,對于流媒體的模型要求很高,需要更貼近實際的流媒體業(yè)務模型,以便更好地仿真出調度算法的性能,因此流媒體業(yè)務模型對于流媒體調度算法的研究意義非常重大. 在本文中,作者將在仿真環(huán)境中利用ARMA模型和本文提出的MAR模型對同一調度算法的性能進行驗證,并且在小規(guī)模的網格中實現(xiàn)該流媒體調度算法對兩種模型進行評估,從而比較兩種模型與實際網格流媒體業(yè)務特征的吻合程度.

在仿真環(huán)境中使用GT-ITM生成Transit-Stub型網絡拓撲,網絡節(jié)點規(guī)模分別為20，40，60個節(jié)點. 主干Transit網絡采用1Gbit或10Gbit網絡,Transit網絡與Stub之間的鏈路采用100Mbit網絡,Stub內的各節(jié)點之間主要為100Mbit鏈路.

在實際網格中采用了60臺PC機,配置從CPU：P43.0GHz,內存：1GB,硬盤：200GB,到雙CPU：P43.2GHz,內存：2GB. 整個網絡由3臺路由器將3個局域網連接起來,每個局域網中有20臺PC機. 并采用Globus Toolkit3.2搭建網格平臺.

在仿真實驗中借用無縫切換 (seamless switch, SL-Switch)[11]算法來比較采用不同流媒體模型，使得切換算法的性能與實際網絡中性能的相似程度. 在SL-Switch算法中,將Buffer尺寸設為8min,并且將節(jié)點平均故障時間設為1000s,然后通過視頻流的接收幀的穩(wěn)定性來評估算法的性能,并且通過在ARMA模型和MAR模型下與實際網絡中的穩(wěn)定性差來評估流媒體模型與實際的相似程度.

圖1為ARMA, MAR模型與實際網絡中流媒體穩(wěn)定度的比較圖. 從圖1中可以看出,ARMA模型與實際網格中的平均穩(wěn)定性差較大,為0.15,而MAR模型與實際網絡中的平均穩(wěn)定性差較小，為0.90. 因而可以得出,在小規(guī)模網格中,對于多對一的流媒體服務模式，MAR模型比ARMA模型更接近于實際的流媒體業(yè)務特征.

圖1 ARMA，MAR模型與實際網絡中流媒體穩(wěn)定度的比較

4 結 論

提出的針對網格環(huán)境中多對一VoD服務中視頻流的多層模型,在考慮了面向內容的多源視頻流分割和多源相關性后,提出了第1層為AR模型的平穩(wěn)隨機過程，第2層為半馬爾可夫過程，第3層為泊松過程的三重隨機過程模型. 將ARMA，MAR模型與網絡中流媒體的穩(wěn)定性進行比較，結果表明，該模型可在網格環(huán)境下更準確有效地描述網格環(huán)境下多對一VoD服務中的視頻流,為更有效和更高質量地提供VoD服務打下了基礎.

參考文獻：

[1]Maglaris B. Performance models of statistical multiplexing in packet video communication[J]. IEEE Trans on Comm,1988,36(7):834-843.

[2]Grunenfelder R. Characterization of video codes as autoregressive moving average process and related queuing system performance[J]. IEEE JSAC,1989,7:752-760.

[3]徐樹公,黃載祿.一種新的ATM網VBR視頻業(yè)務模型[J].電子學報,1997,25(10):102-105.

Xu Shugong, Huang Zailu. A sort of new ATM net VBR video frequency operation model[J]. Electronics Transaction,1997,25(10):102-105. (in Chinese)

[4]Manzoni P. Workload models of VBR video traffic and their use in resource allocation policies[J]. IEEE/ACM Trans on Networking,1999,7(3):387-397.

[5]Jelenkocvic P R. The effect of multiple time scales and subexponentiality in MPEG video streams on queueing behavior[J]. IEEE JSAC,1997,15(6):1052-1071.

[6]陸大金.隨機過程及其應用[M].北京：清華大學出版社,1986．

Lu Dajin. Stochastic process and application[M]. Beijing: Tsinghua University Press,1986. (in Chinese)

[7]王玉孝.概率論與隨機過程[M].北京：北京郵電大學出版社,2000．

Wang Yuxiao. Probability theory & stochastic process[M]. Beijing: Beijing University of Posts and Telecommunications Press,2000. (in Chinese)

[8]Calvert K L, Doar M B, Zegura E, Modeling internet topology[J]. IEEE Communications Magazine,1997,35(6):160-162．

[9]Sun Xiaoyan, Wu Feng, Li Shipeng. Seamless switching of scalable video bitstreams for efficient streaming[J]. IEEE Trans on Multimedia,2004,6(2):291-303．