高偉濤,崔占忠,張海旸

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

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

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

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

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

1 網(wǎng)格中的VoD服務(wù)模式

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

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

t=C1B+C2τ+C3ε.

(1)

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

2 網(wǎng)格中的MAR流媒體服務(wù)模型

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

在VoD視頻流中,當量化尺度及GOP格式固定后,其輸出的數(shù)據(jù)比特流的大小主要由視頻圖像紋理的復雜度和圖像運動的復雜度決定. 因此可以根據(jù)圖像復雜度將視頻流分割成一段段近似平穩(wěn)的視頻片斷. 為簡化起見,將視頻片斷分為高、中、低復雜度3種類型(H,M,L). 在視頻片斷內(nèi)部,數(shù)據(jù)流可以假設(shè)為平穩(wěn)的,因此可以用一階自回歸AR模型進行模擬[6]. 對于MPEG壓縮方式的VoD視頻流,假設(shè)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幀每個像素的平均比特數(shù)；a,b為常數(shù)；w(k)為均值為η,方差為1的正態(tài)高斯白噪聲.λ(k)的均值、方差和自相關(guān)函數(shù)分別為

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

(4)

(5)

(6)

每個來自于某個VoD服務(wù)器的視頻流段由若干個視頻片斷組成,每一個視頻片斷分別屬于{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視頻服務(wù)器. 對于確定的一個視頻流片斷,它只能在{H,M,L}3個狀態(tài)之間進行轉(zhuǎn)換,由于這3個狀態(tài)之間的相關(guān)性與實際的視頻流的內(nèi)容有關(guān),因此只能根據(jù)統(tǒng)計來確定這些狀態(tài)之間的轉(zhuǎn)移概率矩陣Pij,i,j∈{H,M,L}.

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

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

(7)

隨機過程B即為由馬爾可夫鏈調(diào)制的半馬爾可夫過程.

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

(8)

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

(9)

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

(10)

(11)

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

3 仿真實驗

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

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻：

[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網(wǎng)VBR視頻業(yè)務(wù)模型[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．