基于網(wǎng)絡(luò)編碼的分層媒體多播中的層速率分配優(yōu)化

林曉斌 許胤龍 詹 成 王青山

①(中國科學(xué)技術(shù)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 合肥 230027)②(安徽省高性能計算重點(diǎn)實驗室 合肥 230027)③(合肥工業(yè)大學(xué)理學(xué)院 合肥 230009)

1 引言

隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，視頻會議、遠(yuǎn)程教學(xué)、交互視頻游戲等眾多流媒體應(yīng)用受到廣泛的關(guān)注。由于網(wǎng)絡(luò)的異構(gòu)性，同一個多播會晤中各接收節(jié)點(diǎn)可能具有不同的接收帶寬。單速率多播中，所有接收節(jié)點(diǎn)以相同速率接收服務(wù)，不適合異構(gòu)網(wǎng)絡(luò)。而多速率多播在同一個多播會晤中以不同的速率為不同接收節(jié)點(diǎn)提供服務(wù)，更適合大規(guī)模異構(gòu)網(wǎng)絡(luò)的多媒體應(yīng)用。

分層多播(累積分層多播)[1]是一種廣泛應(yīng)用的多速率多播技術(shù)。在分層多播中，源節(jié)點(diǎn)將多媒體數(shù)據(jù)編碼成一個基礎(chǔ)層和若干增強(qiáng)層?；A(chǔ)層包含最基本數(shù)據(jù)，能夠獨(dú)立解碼；而增強(qiáng)層k只有在基礎(chǔ)層，增強(qiáng)層1，增強(qiáng)層2，…，增強(qiáng)層k?1都收到時才能解碼。接收節(jié)點(diǎn)收到的分層數(shù)量越多服務(wù)質(zhì)量越好。各接收節(jié)點(diǎn)可以根據(jù)各自的帶寬接收相應(yīng)層數(shù)的分層數(shù)據(jù)。

在傳統(tǒng)的網(wǎng)絡(luò)通信中，中間節(jié)點(diǎn)收到數(shù)據(jù)后對數(shù)據(jù)不進(jìn)行任何處理，只實現(xiàn)存儲轉(zhuǎn)發(fā)。而利用網(wǎng)絡(luò)編碼(network coding)[2]，中間節(jié)點(diǎn)對收到的數(shù)據(jù)進(jìn)行編碼處理后再轉(zhuǎn)發(fā)，接收節(jié)點(diǎn)收到足夠的編碼數(shù)據(jù)后，通過解碼操作即可得到所有參與編碼的原始數(shù)據(jù)。通過網(wǎng)絡(luò)編碼，中間節(jié)點(diǎn)可以增加每次傳輸?shù)挠行畔⒘浚瑥亩岣呔W(wǎng)絡(luò)吞吐量。Ahlswede等人[2]、Koetter等人[3]證明了利用網(wǎng)絡(luò)編碼多播組可以達(dá)到的最大多播速率等于源節(jié)點(diǎn)到各接收節(jié)點(diǎn)的最大流的最小值。Li等人[4]證明了利用線性網(wǎng)絡(luò)編碼多播組就可以達(dá)到最大多播速率。Sanders等人[5]則提出了構(gòu)造線性編碼的多項式時間算法來保證多播組能達(dá)到最大多播速率。

近年來，基于網(wǎng)絡(luò)編碼的多速率媒體多播引起了一些專家學(xué)者的關(guān)注。文獻(xiàn)[6-9]研究了多速率多播的問題，但沒有考慮分層之間的優(yōu)先級，不符合分層多播中高層數(shù)據(jù)依賴低層數(shù)據(jù)解碼的特性。在每層速率已知的前提下，Zhao等人[10]、Xu等人[11]、Wu等人[12]分別研究了基于網(wǎng)絡(luò)編碼的分層多播。由于這些工作都假定各層速率是預(yù)先固定的，不能根據(jù)網(wǎng)絡(luò)拓?fù)鋭討B(tài)分配各層速率，從而不能充分利用網(wǎng)絡(luò)帶寬。在層速率可變的假定下，Zhang等人[13]研究了基于網(wǎng)絡(luò)編碼的層速率分配問題。由于該問題是一個非線性整數(shù)規(guī)劃的問題，他們提出了確定層速率的近似算法ApproxIVM。但該算法根據(jù)少數(shù)最大流較小的接收節(jié)點(diǎn)的最大流來確定層速率，會導(dǎo)致多數(shù)最大流較大的接收節(jié)點(diǎn)不能充分利用帶寬；且每一分層速率確定后，文中沒有給出算法用于分配每層數(shù)據(jù)所需的鏈路帶寬，從而不能充利用網(wǎng)絡(luò)帶寬。

針對每層速率可變的分層多播問題，本文研究了基于網(wǎng)絡(luò)編碼的層速率優(yōu)化分配算法。該算法首先將網(wǎng)絡(luò)圖按接收節(jié)點(diǎn)的總數(shù)分解成子圖，然后將這些子圖按分層層數(shù)進(jìn)行合并，在合并后的各子圖中接收節(jié)點(diǎn)的最大流的最小值即是優(yōu)化分配的各層速率大小。相比低帶寬接收節(jié)點(diǎn)優(yōu)先的層速率分配算法ApproxIVM[13]，本文的算法居于全局優(yōu)化，能夠滿足不同接收節(jié)點(diǎn)的帶寬需求。模擬實驗表明本文算法能夠顯著提高網(wǎng)絡(luò)吞吐量，提高網(wǎng)絡(luò)帶寬的利用率。

2 問題模型

本節(jié)對基于網(wǎng)絡(luò)編碼的分層媒體多播中的層速率分配優(yōu)化問題進(jìn)行簡要的形式化描述。表1給出幾個重要的變量。

將網(wǎng)絡(luò)用有向圖G(V, E, s, T)表示，其中V是節(jié)點(diǎn)集，E是邊集，s是源節(jié)點(diǎn)，T是所有n個接收節(jié)點(diǎn)的集合，即T={t1, t2,…,tn}?V 。邊(u, v)表示節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的鏈路，c(u, v)表示鏈路(u, v)的容量。假定s上的視頻數(shù)據(jù)經(jīng)編碼器分層編碼后形成m(m≤n)個具有順序關(guān)系的層：第1層(基礎(chǔ)層)，第2層(增強(qiáng)層1)，…，第m層(增強(qiáng)層m?1)。為保證各接收節(jié)點(diǎn)能夠正確地解碼接收的網(wǎng)絡(luò)編碼數(shù)據(jù)包，本文限定對分層編碼的視頻文件進(jìn)行網(wǎng)絡(luò)編碼時只是在同一分層的數(shù)據(jù)包之間進(jìn)行。因為如果允許不同分層的數(shù)據(jù)包之間進(jìn)行網(wǎng)絡(luò)編碼，可能造成低帶寬的接收節(jié)點(diǎn)由于只能接收部分的網(wǎng)絡(luò)編碼包，從而不能正確解碼。

表1 模型的部分變量

由文獻(xiàn)[11,13]，基于網(wǎng)絡(luò)編碼的分層媒體多播中的層速率優(yōu)化分配問題可模型化為以下數(shù)學(xué)規(guī)劃：

數(shù)學(xué)規(guī)劃的目標(biāo)是最大化各接收節(jié)點(diǎn)的接收速率總和，即網(wǎng)絡(luò)吞吐量。約束條件(1)和條件(2)是分層媒體數(shù)據(jù)的解碼條件，即第k層在第1層到第k?1層都接收的前提下才能解碼。約束條件(3)是從源節(jié)點(diǎn)s到每一特定接收節(jié)點(diǎn)ti(?ti∈T)的第k(?k=1,2,…,m)層的數(shù)據(jù)流的平衡條件。約束條件(4)是基于網(wǎng)絡(luò)編碼的帶寬使用特性：同一層數(shù)據(jù)流之間不競爭鏈路帶寬。約束條件(5)保證每條鏈路的帶寬使用在其容量限制之內(nèi)。

3 啟發(fā)式算法

在分層媒體多播中，網(wǎng)絡(luò)各鏈路為每層數(shù)據(jù)分配鏈路帶寬。根據(jù)各鏈路為m層數(shù)據(jù)分配的鏈路帶寬，網(wǎng)絡(luò)圖G (V, E, s, T)被分解成m個子圖Gk(Vk, Ek,s, Tk)(1≤k≤m)。Gk(Vk, Ek, s, Tk)是第k層數(shù)據(jù)在網(wǎng)絡(luò)G (V, E, s, T)中的傳輸圖，其中Ek={(u, v)|fk(u, v)＞0,(u, v)∈E}，V為與E中的邊關(guān)聯(lián)的節(jié)點(diǎn)集合, Tk是接收第k層的接收節(jié)點(diǎn)集合。在層速率固定(即在問題模型的數(shù)學(xué)規(guī)劃中，bk是已知常量，此時數(shù)學(xué)規(guī)劃為整數(shù)線性規(guī)劃)的情形下，文獻(xiàn)[13]證明了數(shù)學(xué)規(guī)劃的可行解對應(yīng)于將網(wǎng)絡(luò)圖分解的各子圖中的各參數(shù)，文獻(xiàn)[10,11]設(shè)計了相應(yīng)的算法根據(jù)給定的各層速率將網(wǎng)絡(luò)圖分解成子圖。而在層速率可變(即在問題模型的數(shù)學(xué)規(guī)劃中，bk是需優(yōu)化的變量，此時數(shù)學(xué)規(guī)劃為非線性整數(shù)規(guī)劃)的情形下，本文通過證明定理1從而求解各層的優(yōu)化速率并得到各層相應(yīng)的傳輸子圖。

定理1 在圖G(V, E, s, T)按最大化吞吐量最優(yōu)分解的m個子圖Gk(Vk, Ek, s, Tk)(1≤k≤m)中，從s到Tk的各接收節(jié)點(diǎn)最大流的最小值minmaxflow(Gk)是第k層的最優(yōu)層速率。

證明 不妨設(shè)在傳輸子圖Gk(Vk, Ek, s, Tk)中從s到ti(ti∈Tk)的最大流maxflow(ti)=min-maxflow(Gk)。若min-maxflow(Gk)＜，則ti不能收到第k層，即ti?Tk，矛盾。若min-maxflow(Gk)＞，利用算法LIF[5]設(shè)定網(wǎng)絡(luò)編碼系數(shù)，對在子圖Gk(Vk,Ek, s, Tk)中傳輸?shù)臄?shù)據(jù)包進(jìn)行網(wǎng)絡(luò)編碼，能夠保證Tk中的所有接收節(jié)點(diǎn)都以min-maxflow(Gk)接收數(shù)據(jù)，與題設(shè)是第k層的最優(yōu)層速率矛盾。因此，min-maxflow(G)=。 證畢

由定理1，優(yōu)化分配m層的層速率即是將網(wǎng)絡(luò)圖優(yōu)化分解成m個傳輸子圖，每個傳輸子圖中從源到各接收節(jié)點(diǎn)的最大流的最小值即是優(yōu)化的層速率。由于直接將網(wǎng)絡(luò)圖分解成m(m≤n)個子圖較困難，本文先設(shè)計算法NRAA(N-layer Rate Allocation Algorithm)將網(wǎng)絡(luò)圖按接收節(jié)點(diǎn)的個數(shù)n分解成n個傳輸子圖Hl(Vl, El, s, Tl)(1≤l≤n)，其中E={(u, v)|yl(u, v)＞0,(u, v)∈E}且yl(u, v)表示n層機(jī)制下鏈路(u, v)為第l層分配的帶寬，Vl是與El中的邊相關(guān)聯(lián)的節(jié)點(diǎn)集合，Tl是接收n層機(jī)制下第l層的接收節(jié)點(diǎn)集合；然后設(shè)計算法MRAA(M-layer Rate Allocation Algorithm)將n個子圖Hl(Vl, El, s, Tl)(1≤l≤n)合并成m個子圖Gk(Vk,Ek, s, Tk)(1≤k≤m)，在合并而成的各子圖中接收節(jié)點(diǎn)最大流的最小值即是優(yōu)化分配的m層機(jī)制下的各層速率。

3.1 算法NRAA

將圖G (V, E, s, T)分解成n個子圖，則每個接收節(jié)點(diǎn)都能按照各自的接收帶寬接收分層數(shù)據(jù)。假定圖Rl(Vl, El, s, Tl)是網(wǎng)絡(luò)圖G (V, E, s, T)為n層機(jī)制下的第1層到第l?1(2≤l≤n)層分配鏈路帶寬后的殘余圖。由定理1，我們可根據(jù)圖Rl(Vl, El, s, Tl)中從s到Tl的各接收節(jié)點(diǎn)的最大流來確定n層機(jī)制下第l層速率，并設(shè)計如下算法NRAA：如果所有接收節(jié)點(diǎn)的最大流都大于0，則以最大流的最小值為第l層速率，各鏈路為第l層優(yōu)化分配鏈路帶寬以構(gòu)造傳輸子圖Hl(Vl, El, s, Tl)(1≤l≤n)。否則如果最大流等于0的接收節(jié)點(diǎn)個數(shù)δ≥1，則刪除當(dāng)前最大流為0的全部接收節(jié)點(diǎn)并確定第l層到第l+δ?1層的速率為0，即本文允許空層的存在。重復(fù)上述操作，直至n層機(jī)制下各層速率和各層傳輸子圖都得以確定。在算法NRAA構(gòu)造的各層傳輸子圖Hl(Vl,El, s, Tl)(1≤l≤n)中利用算法LIF[5]作為網(wǎng)絡(luò)編碼方案，能夠保證Tl中的所有接收節(jié)點(diǎn)都能以圖Hl(Vl, El, s, Tl)中從s到Tl的各接收節(jié)點(diǎn)的最大流的最小值作為接收速率接收n層機(jī)制下的第l層數(shù)據(jù)。

算法NRAA與算法ApproxIVM[13]有些相似，但不同的是：算法ApproxIVM是通過m(m≤n)次迭代地取殘余圖中的非零最大流的最小值來確定m層機(jī)制下的各層速率；且對于層速率優(yōu)化的關(guān)鍵部分(即層速率確定后如何優(yōu)化分配為滿足該層速率所需的鏈路帶寬)，算法ApproxIVM沒有給出相應(yīng)的鏈路帶寬分配策略，從而直接影響下一層速率的大小，本文則在算法NRAA中提出如下啟發(fā)式算法NALBA(New Algorithm for Link Bandwidth Allocation)為第l(1≤l≤n)層數(shù)據(jù)優(yōu)化分配鏈路帶寬，進(jìn)而從殘余圖Rl(Vl, El, s, Tl)中優(yōu)化分解出n層機(jī)制下第l層傳輸子圖Hl(Vl, El, s, Tl)。

因為本文以圖Rl(Vl, El, s, Tl)中從s到Tl的各接收節(jié)點(diǎn)的最大流的最小值為第l層速率，所以圖Rl(Vl, El, s, Tl)中最大流最小的接收節(jié)點(diǎn)的路徑帶寬全部分配給第l層數(shù)據(jù)。因此，在非最小最大流的接收節(jié)點(diǎn)的各路徑上為第l層數(shù)據(jù)分配帶寬時，應(yīng)讓它們充分利用最大流最小的接收節(jié)點(diǎn)路徑上為第l層數(shù)據(jù)必需分配的帶寬。根據(jù)此思想，算法NALBA詳細(xì)過程如下：

在圖Rl(Vl, El, s, Tl)中，根據(jù)算法Edmonds-Karp[14]計算從s到ti(ti∈Tl)的最大流maxflow(ti)，并找出最大流經(jīng)過的路徑集合Pi。假設(shè)maxflow(ti)經(jīng)過路徑的流量是，經(jīng)過鏈路(u, v)的流量是Fi(u, v)。令表示Tl中最大流最小的接收節(jié)點(diǎn)集合。確定Tl中接收節(jié)點(diǎn)的最大流的最小值min為第l層速率。要使中的所有接收節(jié)點(diǎn)都能接收第l層數(shù)據(jù)，則在鏈路(u, v)上需分配的帶寬f'(u, v)=max{Fi(u, v)|ti∈}。對最大流大于min的每個接收節(jié)點(diǎn)ti(ti∈Tl?)，都分別執(zhí)行如下各步驟為第l層分配鏈路帶寬(表2)。

表2 第l層分配鏈路帶寬

表2中第(3)步對均勻分?jǐn)偩W(wǎng)絡(luò)帶寬到各路徑的處理方法，可參見文獻(xiàn)[10]的Heuristic Approach。在算法NALBA中，路徑為從s到ti(ti∈)的第l層數(shù)據(jù)分配的帶寬=，路徑為從s到ti(ti∈Tl?)的第l層數(shù)據(jù)分配的帶寬=preFlo+evenFlo。n層機(jī)制下鏈路(u, v)上為通往ti(ti∈Tl) 的第l層數(shù)據(jù)分配的帶寬：

因此，n層機(jī)制下鏈路(u, v)為第l(1≤l≤n)層數(shù)據(jù)分配的總帶寬為

證明 算法NALBA對所有接收節(jié)點(diǎn)執(zhí)行相同操作，所以我們以單個接收節(jié)點(diǎn)ti(ti∈Tl)為例進(jìn)行分析。不妨設(shè)ti為非最小最大流的接收節(jié)點(diǎn)。首先執(zhí)行算法Edmonds-Karp[14]計算maxflow(ti)并找出ti的路徑集Pi，時間復(fù)雜度為O(| Vl||El|2)。其次，算法NALBA為第l層分配鏈路帶寬各步驟的時間復(fù)雜度為O(|El|)。綜上，對單個接收節(jié)點(diǎn)ti所需執(zhí)行操作的時間復(fù)雜度為O(| Vl||El|2)+O(|El|)=O(| Vl||El|2)。共有|Tl|個接收節(jié)點(diǎn)，因此算法NALBA的時間復(fù)雜度為O(| Tl||Vl||El|2)。 證畢

基于算法NALBA分配n層機(jī)制下各層傳輸子圖的鏈路帶寬，本文設(shè)計算法NRAA如表3所示：

表3 本文設(shè)計算法NRAA

在算法NRAA構(gòu)造的圖Hl(Vl, El, s, Tl)(1≤l≤n)中利用算法LIF[5]作為網(wǎng)絡(luò)編碼方案，能夠保證Tl中的所有接收節(jié)點(diǎn)都接收到n層機(jī)制下的第l層數(shù)據(jù)。

由算法NRAA優(yōu)化分配n層機(jī)制下的層速率列表A=＜a1, a2,…,an＞，并得到n層機(jī)制下各接收節(jié)點(diǎn)的接收速率列表C=＜c1, c2,…,cn＞，則根據(jù)算法NRAA的設(shè)計思想顯然易證以下性質(zhì)。

性質(zhì)1 若由算法NRAA得到的各接收節(jié)點(diǎn)的接收速率c1, c2,…,cn滿足c1≤c2≤…≤cn，則ci(1≤i≤n)與n層機(jī)制下各層速率a1, a2,…,an之間的關(guān)系滿足ci=a1+a2+…+ai。

定理3 在網(wǎng)絡(luò)G (V, E, s, T)中，n(|T|=n)層機(jī)制下的層速率優(yōu)化分配算法NRAA的時間復(fù)雜度為O(| V||T|2|E|2)。

證明 算法NRAA的時間復(fù)雜度是由n次調(diào)用算法NALBA決定的。而由定理2，在網(wǎng)絡(luò)G (V, E,s, T)的殘余子圖Rl(Vl, El, s, Tl)中，算法NALBA的時間復(fù)雜度為O(| Tl||Vl||El|2)，其中Vl?V, El?E, Tl?T。所以算法NRAA的時間復(fù)雜度為n*O(| T||V||E|2)=O(| V||T|2|E |2)。 證畢

3.2 算法MRAA

為優(yōu)化分配m(m≤n)層的層速率，本文將由算法NRAA預(yù)先分成的n層視頻數(shù)據(jù)合并成m層。假定由算法NRAA優(yōu)化分配的n層機(jī)制下層速率列表A=＜a1, a2,…,an＞，接收節(jié)點(diǎn)接收速率的有序列表C=＜c1, c2,…,cn＞(其中c1≤c2≤…≤cn)。在最大化網(wǎng)絡(luò)吞吐量的目標(biāo)下，將n層合并成m層的過程等價于在最大化的目標(biāo)下，將有序列表C劃分成m個子列表C1, C2,…,Cm。其中|Ck|表示子列表Ck的元素個數(shù)，min(Ck)表示子列表Ck中的最小值。上述劃分即是將n個接收節(jié)點(diǎn)劃分成m個接收組Q1, Q2,…,Qm，在接收組Qk中有|Ck|個接收節(jié)點(diǎn)且組中的所有接收節(jié)點(diǎn)都能以速率min(Ck)接收在m層機(jī)制下從第1層到第k層的共計k層的分層數(shù)據(jù)。因此可優(yōu)化分配m層機(jī)制下各層速率為

對于有序列表劃分成子列表的問題，Gau等人[15]證明了有序列表的最優(yōu)劃分一定是有序劃分，并提出了把元素個數(shù)為n的有序列表劃分成m個有序子列表的多項式時間算法FALP(Fast Algorithm for List Partition)。

不妨設(shè)有序列表C=＜c1, c2,…,cn＞(其中c1≤c2≤…≤cn)，經(jīng)算法FALP劃分成有序子列表(每個子列表的元素從小到大排序)為：C1=＜c1, c2,…,ci1?1＞(注：i0=1),C2=＜ci1,ci1+1,…,ci2?1＞,…,Cm=＜cim?1,cim?1+1,…cn＞，則接收節(jié)點(diǎn)集合T={t1, t2,…,tn}被分成的m個接收分組：

因此，m層機(jī)制下，Tk=Qi。在組Qk(1≤k≤m)中的接收節(jié)點(diǎn)的接收速率都為cik?1，又根據(jù)式(3)，優(yōu)化分配m層機(jī)制下各層速率為

而由算法NRAA的性質(zhì)1：ci=a1+a2+…+ai(1≤i≤n)，因此優(yōu)化分配m層機(jī)制下第k(1≤k≤m)層速率為

即m層機(jī)制下的第k(1≤k≤m)層數(shù)據(jù)是由n層機(jī)制下的第ik?2+1層到第ik?1層共ik?1?ik?2層數(shù)據(jù)合并而成的。因此m層機(jī)制下第k(1≤k≤m)層的傳輸子圖Gk(Vk, Ek, s, Tk)的鏈路帶寬fk(u, v)與n層機(jī)制下的各傳輸子圖Hl(Vl, El, s, Tl)(1≤l≤n)的鏈路帶寬yl(u, v)滿足以下等式：

綜上，本文設(shè)計算法MRAA將算法NRAA構(gòu)造的n層機(jī)制下的n個傳輸子圖合并成m個傳輸子圖，優(yōu)化分配m層機(jī)制下的各層速率。算法MRAA如表4所示。

表4 本文設(shè)計算法MRAA

在算法MRAA構(gòu)造的第k(1≤k≤m)層傳輸子圖Gk(Vk, Ek, s, Tk)中，利用算法LIF[5]作為網(wǎng)絡(luò)編碼方案，能夠保證Tk中的所有接收節(jié)點(diǎn)都能以式(6)所示的速率接收m層機(jī)制下的第k層數(shù)據(jù)。

定理4 在網(wǎng)絡(luò)G (V, E, s, T)中，m(m≤n=|T|)層機(jī)制下的層速率分配算法MRAA的時間復(fù)雜度為O(| V||T|2|E|2)。

證明 算法MRAA由3步組成。第1步，調(diào)用算法NRAA，時間復(fù)雜度為O(| V||T|2|E|2)；第2步，按接收速率排序結(jié)果對接收節(jié)點(diǎn)重新編號，時間復(fù)雜度為O(n2)=O(| T|2)；第3步，調(diào)用算法FALP，時間復(fù)雜度為O(mn2)=O(m| T |2)。所以總時間復(fù)雜度為O(| V||T|2|E|2)+O(| T|2)+O(m| T|2)=O(| V||T|2|E |2)。 證畢

4 模擬實驗

本文通過C++模擬實驗進(jìn)行算法性能評價。首先比較為各層視頻數(shù)據(jù)分配鏈路帶寬的新算法NALBA、隨機(jī)分配策略RANDOM、算法Heuristic Approach[10]的均勻分配策略；然后比較層速率全局優(yōu)化分配算法MRAA、低帶寬接收節(jié)點(diǎn)優(yōu)先的層速率分配算法ApproxIVM[13]、層速率固定的算法Heuristic Approach[10]。

文獻(xiàn)[16]表明為滿足網(wǎng)絡(luò)的異構(gòu)性并保持合理的額外開銷，在分層多播中分層層數(shù)為4層是較為合理的值。因此本文在實驗中取分層層數(shù)m=4。

在應(yīng)用網(wǎng)絡(luò)編碼的前提下，從源節(jié)點(diǎn)到某特定接收節(jié)點(diǎn)的最大流的值反映該接收節(jié)點(diǎn)的可接收帶寬的大小。在實驗中本文先采用平均標(biāo)準(zhǔn)化接收速率ANR(Average Normalized Rate)[6]如式(8)所示(其中ri表示ti接收到的各分層數(shù)據(jù)的總速率，maxflow(ti)表示從s到ti的最大流，T是所有接收節(jié)點(diǎn)的集合。)對各算法進(jìn)行比較。參數(shù)ANR反映網(wǎng)絡(luò)中各接收節(jié)點(diǎn)對各自可接收帶寬的平均利用率。參數(shù)ANR越大，表明各接收節(jié)點(diǎn)的實際接收帶寬越趨近各自的可接收帶寬。但是本文的優(yōu)化目標(biāo)是吞吐量，因此本節(jié)定義標(biāo)準(zhǔn)化的總接收速率NTR(Normalized Total Rate)如式(9)所示(式(9)中各變量與式(8)含義一致。)來表示整個網(wǎng)絡(luò)的實際接收帶寬總和占可接收帶寬總和的比例，反映整個網(wǎng)絡(luò)的帶寬使用總量，即網(wǎng)絡(luò)吞吐量。

4.1 參數(shù)ANR比較實驗

圖1采用50個節(jié)點(diǎn)和10個接收節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)拓?fù)洹Ｔ谒惴∕RAA的步驟1，即執(zhí)行算法NRAA時，分別執(zhí)行隨機(jī)分配路徑帶寬的RANDOM策略，算法Heuristic Approach的均勻分配策略和算法NALBA 3種不同的方案為每層數(shù)據(jù)分配鏈路帶寬，得到算法MRAA的3個不同結(jié)果。圖1中RANDOM策略最差。因為RANDOM策略在各路徑上為每層數(shù)據(jù)隨機(jī)分配帶寬，沒有考慮帶寬的有效分配。在圖1中，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)平均度從5增加到8時，算法NALBA相比算法Heuristic Approach的均勻分配策略對ANR參數(shù)的改進(jìn)在圖1(a)中由3%增加到7%，在圖1(b)中由5%增加到10%。這是因為節(jié)點(diǎn)度越大，從源節(jié)點(diǎn)到不同接收節(jié)點(diǎn)的路徑之間有公共鏈路的可能性越大，所以算法NALBA在非最小最大流的接收節(jié)點(diǎn)的路徑上為各層分配帶寬時，讓那些與最大流最小的接收節(jié)點(diǎn)的路徑有公共鏈路的路徑共享最小最大流接收節(jié)點(diǎn)的路徑上為該層視頻數(shù)據(jù)必需分配的帶寬能夠節(jié)省更多的帶寬。

圖2采用100個節(jié)點(diǎn)，接收節(jié)點(diǎn)個數(shù)在[4,40]以步長為4變化，鏈路容量均勻分布在[1,20]的隨機(jī)網(wǎng)絡(luò)拓?fù)洹D2是算法MRAA，算法ApproxIVM，算法Heuristic Approach的比較結(jié)果。其中在層速率固定的算法Heuristic Approach中，本文假定從源節(jié)點(diǎn)到各接收節(jié)點(diǎn)的最大流的范圍已知為[Min,Max]，源節(jié)點(diǎn)根據(jù)此范圍固定第1層的速率為Min，其他層的速率相等且為(Max?Min)/(m?1)，m為分層層數(shù)。從圖2中可以看出，MRAA相比ApproxIVM和Heuristic Approach對ANR參數(shù)的改進(jìn)在圖2(a)中平均分別為6%和20%，在圖2(b)中平均分別為10%和19%。因為MRAA根據(jù)網(wǎng)絡(luò)拓?fù)鋸娜值慕嵌葍?yōu)化分配各層速率，并且采用算法NALBA為各層有效分配鏈路帶寬；ApproxIVM只根據(jù)網(wǎng)絡(luò)中最大流最小的4個接收節(jié)點(diǎn)的最大流來確定4層視頻數(shù)據(jù)的速率而且在各鏈路為每一層數(shù)據(jù)分配帶寬時采用隨機(jī)分配的方式，這些都使得網(wǎng)絡(luò)ANR參數(shù)受影響；而Heuristic Approach中各層速率固定，沒有根據(jù)網(wǎng)絡(luò)拓?fù)浞峙涓鲗铀俾?，因此其ANR參數(shù)最差。

4.2 參數(shù)NTR比較實驗

圖1 NALBA, RANDOM, Heuristic Approach算法的參數(shù)ANR比較

圖2 MRAA, ApproxIVM, Heuristic Approach算法的參數(shù)ANR比較

圖3 NALBA, RANDOM, Heuristic Approach的參數(shù)NTR比較

圖4 MRAA, ApproxIVM, Heuristic Approach的參數(shù)NTR比較

當(dāng)以NTR為比較參數(shù)時，重復(fù)上述實驗得到實驗結(jié)果如圖3和圖4。圖3與圖1相似，而圖4與圖2相比有些變化。在圖4中，MRAA相比Heuristic Approach和ApproxIVM對網(wǎng)絡(luò)吞吐量的提高在圖4(a)中平均分別為16%和15%，在圖4(b)中平均分別為14%和18%。因為MRAA考慮全局最優(yōu)，使得所有接收節(jié)點(diǎn)都能充分利用帶寬，所以各接收節(jié)點(diǎn)的平均帶寬利用率和網(wǎng)絡(luò)吞吐量都是三者中最優(yōu)的。在圖4(a)和圖4(b)中，隨著接收節(jié)點(diǎn)個數(shù)的增加，層速率固定的算法Heuristic Approach的吞吐量反而大于層速率經(jīng)部分優(yōu)化分配的算法ApproxIVM。因為本文設(shè)定Heuristic Approach根據(jù)接收節(jié)點(diǎn)最大流的范圍固定各層速率；而ApproxIVM根據(jù)少數(shù)低帶寬接收節(jié)點(diǎn)的最大流分配各層速率，從而導(dǎo)致多數(shù)最大流較大的高帶寬接收節(jié)點(diǎn)只能以低速率接收分層數(shù)據(jù)，不能充分利用帶寬，從而影響網(wǎng)絡(luò)吞吐量，尤其是當(dāng)接收節(jié)點(diǎn)較多時。

5 結(jié)束語

本文研究了基于網(wǎng)絡(luò)編碼的分層媒體多播中的層速率分配優(yōu)化問題。證明了將網(wǎng)絡(luò)圖按分層層數(shù)最優(yōu)分解成的各網(wǎng)絡(luò)子圖中的接收節(jié)點(diǎn)的最大流的最小值即是各層的最優(yōu)層速率，并根據(jù)此思想提出了時間復(fù)雜度為O(| V||T|2|E|2)的啟發(fā)式算法MRAA優(yōu)化分配各層速率。模擬實驗表明本文的算法能夠顯著改善網(wǎng)絡(luò)吞吐量，提高各接收節(jié)點(diǎn)的平均帶寬利用率。本文的研究工作基于單會晤多播的情形，而在多會晤情形下基于網(wǎng)絡(luò)編碼的分層媒體多播中的層速率分配優(yōu)化問題要復(fù)雜得多，我們將以此作為將來進(jìn)一步的研究工作。

[1] McCanne S, Jacobson V, and Vetterli M. Receiver-driven layered multicast. Proc. of ACM SIGCOMM 1996, Stanford,CA, USA, Aug. 1996: 117-130.

[2] Ahlswede R, Cai N, and Li S R, et al.. Network information flow. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.

[3] Koetter R and Medard M. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2000, 11(5):782-795.

[4] Li S R, Yueng R W, and Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, 49(2): 371-381.

[5] Sanders P, Egner S, and Tolhuizen L. Polynomial time algorithms for network information flow. Proc. of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, CA, USA, June 2003:286-294.

[6] Sundaram N, Ramanathan P, and Banerjee S. Multirate media stream using network coding. Proc. of the 43rd Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, Sep. 2005.

[7] Wu X, Ma B, and Sarshar N. Rainbow network problems and multiple description coding. IEEE Transactions on Information Theory, 2008, 54(10): 4565-4574.

[8] Shao M, Wu X, and Sarshar N. Rainbow network flow with network coding. Proc. of NetCod 2008, Hong Kong, China,Jan. 2008: 1-6.

[9] Shao M, Dumitrescu S, and Wu X. Toward the optimal multirate multicast for lossy packet network. Proc. of ACM Multimedia 08, Vancouver, BC, Canada, Oct. 2008: 765-768.[10] Zhao J, Yang F, and Zhang Q, et al.. LION: Layered overlay multicast with network coding. IEEE Transactions on Multimedia, 2006, 8(5): 1021-1032.

[11] Xu C, Xu Y, and Zhan C, et al.. On network coding based multirate video streaming in directed network. Proc. of the 26th IPCCC, New Orleans, Louisiana, USA, Apr. 2007:332-339.

[12] Wu Y. Distributing layered content using network coding. 5th IEEE Annual Communications Society Conference on Sensor,Mesh and Ad hoc Communications and Networks Workshops,San Francisco, CA, USA, June 2008: 1-4.

[13] 張牧, 張順頤, 劉偉彥. 多速率多播最大吞吐量問題研究. 電子與信息學(xué)報, 2008, 30(1): 16-20.Zhang M, Zhang S, and Liu W. On the optimal multi-rate throughput for multicast. Journal of Electronics &Information Technology, 2008, 30(1): 16-20.

[14] Cormen T H, Leiserson C E, and Rivest R L, et al..Introduction To Algorithms (Second Edition). Massachusetts:MIT Press, 2001: 643-698.

[15] Gau R, Haas Z J, and Krishnamachari B. On multicast flow control for heterogeneous receivers. IEEE/ACM Transactions on Networking, 2002, 10(1): 86-101.

[16] Yang Y R, Kim M S, and Lam S S. Optimal partitioning of multicast receivers. Proc. of ICNP 2000, Osaka, Japan, Nov.2000: 129-140.