張有為 (長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院,湖北荊州434023)

雖然應(yīng)用層組播技術(shù)的應(yīng)用日益廣泛,但是其缺點(diǎn)也比較明顯,主要在于可靠性不高,并且缺乏網(wǎng)絡(luò)擁塞控制機(jī)制[1～2]。基于 “單數(shù)據(jù)流”的應(yīng)用層組播協(xié)議,如 Narada[3]、HMTP[4]、NICE[5]、DONet[6]等可以解決應(yīng)用層組播某一方面的問題,但是無法兼顧系統(tǒng)的可擴(kuò)展性和健壯性。

采用多描述編碼MDC(Multiple Description Coding,MDC)技術(shù)[7～8]的組播協(xié)議CoopNet[9]和SplitSream[10]通過多路并發(fā)傳輸?shù)姆绞捷^好地平衡了組播系統(tǒng)的可擴(kuò)展性和健壯性。但多樹模型卻無法有效解決描述的同步問題,從而無法獲得較高的圖像質(zhì)量。此外,節(jié)點(diǎn)在加入系統(tǒng)時(shí),多樹結(jié)構(gòu)的的控制開銷要遠(yuǎn)大于單樹結(jié)構(gòu)。

為此,筆者充分考慮節(jié)點(diǎn)的異構(gòu)性以及節(jié)點(diǎn)失效而對(duì)性能造成的影響,提出了一種基于層次結(jié)構(gòu)的應(yīng)用層組播模型-RSA。RSA采用多描述編碼技術(shù)對(duì)媒體數(shù)據(jù)編碼,并以此構(gòu)造多樹的分層結(jié)構(gòu)模型,采用分布式算法實(shí)現(xiàn)了節(jié)點(diǎn)中描述資源和對(duì)資源請(qǐng)求的均勻分布,以提高流媒體系統(tǒng)的健壯性和可擴(kuò)展性。

1 基于層次結(jié)構(gòu)的應(yīng)用層組播模型

對(duì)于組播節(jié)點(diǎn)而言,采用多描述編碼技術(shù)不需要考慮描述的接收次序,因此特別適合于動(dòng)態(tài)的網(wǎng)絡(luò)環(huán)境?；趯哟谓Y(jié)構(gòu)的應(yīng)用層組播模型RSA中采用該技術(shù)對(duì)節(jié)目?jī)?nèi)容進(jìn)行編碼,并以此構(gòu)建多樹的組播模型。

RSA給出了一種基于多樹的分層結(jié)構(gòu)模型,這種結(jié)構(gòu)很好地解決了描述之間的同步問題,實(shí)現(xiàn)了節(jié)點(diǎn)的快速加入,并提高了圖像質(zhì)量。此外,RSA還提出了基于資源均勻分布的最大覆蓋算法MAXC-通過將節(jié)點(diǎn)對(duì)描述的請(qǐng)求均勻地分布在最多的父節(jié)點(diǎn)以實(shí)現(xiàn)模型的健壯性,同時(shí)也有利于實(shí)現(xiàn)圖像質(zhì)量快速恢復(fù)。

如圖1所示,節(jié)目?jī)?nèi)容在源節(jié)點(diǎn)S被編碼成3個(gè)描述(D1,D2,D3),節(jié)點(diǎn)之間的可用帶寬按照式(1)映射成描述碼率的倍數(shù)Weight(其中SubDescription和Avail_BW分別為單個(gè)描述的碼率和節(jié)點(diǎn)間的可用帶寬):

圖1 多樹模型的數(shù)據(jù)傳輸

例如A→D之間的帶寬權(quán)值為3,表示D可以從A獲取3個(gè)描述。如圖1(a)所示,節(jié)點(diǎn)D可以從父節(jié)點(diǎn)集{A}、{A,B}、{A,C}或{A,B,C}中均能獲得最大的描述集(D1,D2,D3)。但是,只考慮圖像質(zhì)量這一個(gè)方面無法保障系統(tǒng)的健壯性。MAXC算法將對(duì)最大描述集的請(qǐng)求均勻地分布在最大的父親集中,從而保證在節(jié)點(diǎn)失效的情況下不至于出現(xiàn)圖像質(zhì)量的劇烈抖動(dòng)。圖1中的節(jié)點(diǎn)D選擇{A,B,C}作為其父親集,并根據(jù)加權(quán)的MAXC算法將對(duì)(D1,D2,D3)的請(qǐng)求均勻地分布在3個(gè)父節(jié)點(diǎn)上。

2 模型設(shè)計(jì)

RAS模型結(jié)構(gòu)如圖2所示,主要由描述資源的均勻分布算法和資源請(qǐng)求的最大覆蓋算法、組播過程中節(jié)點(diǎn)的加入、數(shù)據(jù)傳輸?shù)膬?yōu)化和對(duì)節(jié)點(diǎn)失效的恢復(fù)等幾部分組成。

圖2 RSA模型結(jié)構(gòu)圖

2.1 描述資源均勻分布優(yōu)化算法

多樹組播模型在動(dòng)態(tài)環(huán)境中有較好的健壯性,但是,如果描述資源在父節(jié)點(diǎn)中的分布不均勻,卻會(huì)造成對(duì)擁有豐富描述資源節(jié)點(diǎn)的過度依賴,進(jìn)而在節(jié)點(diǎn)失效時(shí)產(chǎn)生圖像質(zhì)量的劇烈抖動(dòng)。如圖 1(a)所示,當(dāng)節(jié)點(diǎn)A失效時(shí),圖像質(zhì)量會(huì)下降,且無法依靠節(jié)點(diǎn)B、C(不包含描述D3)中已有的描述資源來進(jìn)行恢復(fù),只能重新搜索新的父節(jié)點(diǎn)來進(jìn)行圖像質(zhì)量的恢復(fù),但會(huì)產(chǎn)生較大的延遲。因此,筆者提出了一種描述資源均勻分布的方案,以此來提高動(dòng)態(tài)網(wǎng)絡(luò)中的圖像質(zhì)量。

由圖1(a)可知,描述資源的分布比例為:D1＞D2＞D3。如果節(jié)點(diǎn)C不再請(qǐng)求D1而是D3,則會(huì)形成如圖1(b)所示的分布比例:D1=D2=D3,均勻分布。則節(jié)點(diǎn)D請(qǐng)求父親集{A}、{A,B}、{A,C}、{B,C}、{A,B,C}中的任一集合均能獲得最大的描述集;與此同時(shí),當(dāng)節(jié)點(diǎn)D的父節(jié)點(diǎn)集{A,B,C}中任一節(jié)點(diǎn)的失效時(shí),仍然可以通過調(diào)用MAXC算法來重新調(diào)整對(duì)父節(jié)點(diǎn)的描述請(qǐng)求,從在線的父節(jié)點(diǎn)中請(qǐng)求最大描述集,從而在不降低圖像質(zhì)量的情況下實(shí)現(xiàn)節(jié)點(diǎn)的無縫切換和快速恢復(fù)。

為實(shí)現(xiàn)描述資源在各層節(jié)點(diǎn)中的均勻分布,需要為節(jié)點(diǎn)中的描述設(shè)定屬性參數(shù) RefCount-“引用計(jì)數(shù)”。節(jié)點(diǎn)應(yīng)優(yōu)先請(qǐng)求父節(jié)點(diǎn)中RefCount的描述。圖3(a)所示為節(jié)點(diǎn)C(假設(shè)C在A,B之后加入組播樹)根據(jù)父親集信息生成的請(qǐng)求矩陣Req_MX,其中,Res_set為父節(jié)點(diǎn)中的描述資源,請(qǐng)求集 Req_set初始化為NULL。圖3(b)顯示父節(jié)點(diǎn)中描述資源的引用情況,其中D3的RefCount在C加入前為1,C加入后向S請(qǐng)求D3描述,其RefCount更新為2。圖3(c)顯示按以下規(guī)則生成所生成的掃描矩陣Scan_MX:

1)Res(描述資源)按照RefCount升序排列;

2)若RefCount相同,則按Res在所有父節(jié)點(diǎn)中的資源數(shù)量的升序排列;

圖3 均勻分布算法中的數(shù)據(jù)結(jié)構(gòu)

3)Pat(父節(jié)點(diǎn))按擁有資源數(shù)量的升序排列;

4)矩陣中(i,j)為 “1” 表示Pat擁有 Res;“0”則表示Pat沒有 Res。

節(jié)點(diǎn)以Req_MX和Scan_MX為參數(shù)調(diào)用MAXC算法生成最大資源的覆蓋以及對(duì)應(yīng)的請(qǐng)求,如圖3(a)所示。

2.2 節(jié)點(diǎn)加入

為了避免節(jié)點(diǎn)失效造成過大的圖像質(zhì)量抖動(dòng),系統(tǒng)中節(jié)點(diǎn)的最大入度和出度設(shè)定為K(K為節(jié)目編碼的描述個(gè)數(shù))。當(dāng)節(jié)點(diǎn)加入組播樹時(shí),從服務(wù)器獲取K個(gè)度小于K且Weight≥1的節(jié)點(diǎn)信息作為父親集。節(jié)點(diǎn)根據(jù)父親集信息生成請(qǐng)求矩陣Req_MX和Scan_MX作為MAXC算法的參數(shù),其偽代碼如下:

節(jié)點(diǎn)根據(jù)由MAXC算法生成的請(qǐng)求集向父節(jié)點(diǎn)請(qǐng)求資源請(qǐng)求描述,如圖1(b)所示,節(jié)點(diǎn)D的請(qǐng)求集為(A(D1),B(D2),C(D3))。

2.3 數(shù)據(jù)傳輸優(yōu)化

節(jié)點(diǎn)在加入組播后,需不斷調(diào)整父親集、更新請(qǐng)求集以提高系統(tǒng)的性能。其更新的基本思想為:①當(dāng)節(jié)點(diǎn)加入組播樹后,通過繼續(xù)搜索新的父節(jié)點(diǎn)來請(qǐng)求加入時(shí)所缺描述資源,以獲得最佳視頻質(zhì)量;②繼續(xù)為節(jié)點(diǎn)搜索最大請(qǐng)求集,若對(duì)某個(gè)父節(jié)點(diǎn)的描述請(qǐng)求數(shù)量大于1,則將其分裂為多個(gè)單一的描述請(qǐng)求,即將對(duì)K個(gè)描述的請(qǐng)求均勻地分配到K個(gè)父節(jié)點(diǎn)上。

2.4 節(jié)點(diǎn)失效時(shí)的視頻質(zhì)量恢復(fù)

當(dāng)發(fā)生節(jié)點(diǎn)失效時(shí),系統(tǒng)按照以下步驟對(duì)視頻質(zhì)量進(jìn)行修復(fù):

1)將離線的父節(jié)點(diǎn)從Req_MX刪除。

2)調(diào)用MAXC算法,對(duì)在線父節(jié)點(diǎn)中的資源請(qǐng)求重新分配。

3)根據(jù)數(shù)據(jù)傳輸過程中的優(yōu)化方法為節(jié)點(diǎn)生成新的請(qǐng)求集。

由于實(shí)現(xiàn)了描述資源和描述請(qǐng)求的均勻分布,在2)中,實(shí)現(xiàn)視頻質(zhì)量的無縫切換是大概率事件;通過3)中的優(yōu)化策略,節(jié)點(diǎn)能實(shí)現(xiàn)請(qǐng)求集的快速更新,能避免了圖像質(zhì)量的劇烈抖動(dòng)。

3 仿真試驗(yàn)

采用流行的網(wǎng)絡(luò)仿真器NS2對(duì)RSA模型進(jìn)行仿真,對(duì)平均數(shù)據(jù)接收率 (Mean Receiving Rate,MRR)、平均恢復(fù)時(shí)間 (Mean Recovery Time,MRT)、平均鏈路強(qiáng)度 (Mean Link Stress,M LS)進(jìn)行評(píng)估。

試驗(yàn)中,將RSA和CoopNet進(jìn)行對(duì)比。使用通用的網(wǎng)絡(luò)拓?fù)渖善鱃T-ITM生成 transit-stub類型的物理網(wǎng)絡(luò)拓?fù)?并且將碼率為300Kbps的媒體數(shù)據(jù)編碼成4個(gè)描述,服務(wù)器的度設(shè)定為64,節(jié)點(diǎn)度為4,節(jié)點(diǎn)之間的可用帶寬分布為200～400Kbps。

在試驗(yàn)的前500s內(nèi)拓?fù)涔?jié)點(diǎn)數(shù)量按指數(shù)遞增,從16增加到512,在系統(tǒng)穩(wěn)定后的600～1100s內(nèi),每隔100s隨機(jī)安排16個(gè)節(jié)點(diǎn)離開,用來模擬在節(jié)點(diǎn)失效時(shí)數(shù)據(jù)接收率的變化。

圖4表明,隨著節(jié)點(diǎn)的增加,CoopNet的MRR出現(xiàn)了的比較明顯的下降,但是RSA的MRR卻沒有顯著的變化,并且比CoopNet高出約20%。

圖5顯示,在節(jié)點(diǎn)失效時(shí)RSA中圖像質(zhì)量的抖動(dòng)約為15%,而CoopNet達(dá)到了30%;另一方面,圖4顯示RSA在節(jié)點(diǎn)失效時(shí),其MRT為20s,而CoopNet則為40s。

由于資源的均勻分布降低了鏈路的強(qiáng)度,圖6顯示,在0～500s內(nèi),RSA的MLS要比CoopNet的低20%。

圖4 節(jié)點(diǎn)加入時(shí)的平均數(shù)據(jù)接收率

4 結(jié) 語

筆者所提出RSA模型采用MAXC算法提高了節(jié)點(diǎn)的視頻接收質(zhì)量,實(shí)現(xiàn)了節(jié)點(diǎn)失效時(shí)視頻質(zhì)量的快速恢復(fù)。試驗(yàn)證明,RSA具有很好的健壯性和可擴(kuò)展性。

圖5 節(jié)點(diǎn)失效時(shí)的平均數(shù)據(jù)接收率

圖6 節(jié)點(diǎn)加入時(shí)的平均鏈路強(qiáng)度

[1]羅萬明,林闖,閻保平.TCP/IP擁塞控制研究[J].計(jì)算機(jī)學(xué)報(bào),2001,24(1):1～18.

[2]黃偉紅,孫正興,張福炎.Internet視頻流中的自適應(yīng)擁塞控制技術(shù)研究 [J].計(jì)算機(jī)學(xué)報(bào),2001,24(8):797～801.

[3]Chu Yanghua,Sanjay Rao,Zhang Hui.A Case For EndSystem Multicast[A].Selected Areas in Communications[C].Santa Clara,CA:IEEE June,2000.1456～1471.

[4]Zhang B,Jamin S,Zhang L.Host multicast:A frame work fo r delivering multicast to end users[A].T wenty-First Annual Joint Conference of the IEEE Computer and Communications Societies[C].California,US:IEEE June,2002.1366～1375.

[5]Suman Banerjee,Bobby Bhatacharjee,Christopher Kommareddy.Scalable Application Layer Multicast[A].Consumer Communications and Networking Conference[C].Karlsruhe,Germany.IEEE:Jan,2002.43～51.

[6]Zhang X,Liu J,Li B,et al.CoolStreaming/DoNet:A data-Driven Overlay network for peer-to-peer live Media Streaming[A].24th Annual Joint Conference of the IEEE Computer and Communications Societies[C].Miami,FL:IEEE.March,2005.2102～2111.

[7]肖友能,薛向陽,曾瑋.視頻轉(zhuǎn)碼技術(shù)回顧 [J].通信學(xué)報(bào),2002,23(8):72～80.

[8]李彬,黃峰,孫立峰,楊士強(qiáng).一種魯棒靈活的非平衡多描述視頻編碼和傳輸方案 [J].計(jì)算機(jī)學(xué)報(bào),2008,31(7):1155～1164.

[9]Padmanabhan V,Wang H,Chou P,et al.Distributing streaming media content using cooperative networking[J].IEEE Transactions on Multimedia,2002,8(2):233～242.

[10]Castro M,D ruschel P,Kermarrec A M,et al.Split Stream:High-bandwidth content distribution in a cooperative environment[J].IEEE Transactions on Knowledge and Data Engineering,2003,20(9):1273～1281.