杜文龍，黃 余

(1.江蘇電子信息職業(yè)學(xué)院 計(jì)算機(jī)與通信學(xué)院，江蘇 淮安 223003；2.圣路易斯大學(xué) 研究生院，菲律賓 碧瑤 2600)

0 引 言

網(wǎng)絡(luò)技術(shù)的進(jìn)步和可用帶寬的增長(zhǎng)導(dǎo)致了眾多媒體內(nèi)容提供商提供數(shù)據(jù)傳播服務(wù)，如實(shí)時(shí)和按需媒體流。這些媒體內(nèi)容提供商的一個(gè)主要關(guān)注點(diǎn)是網(wǎng)絡(luò)資源(即網(wǎng)絡(luò)容量)的供應(yīng)；媒體內(nèi)容提供商的要求以及對(duì)使用資源的付費(fèi)通過(guò)服務(wù)級(jí)協(xié)議(service level agreements，SLA)[1,2]和因特網(wǎng)服務(wù)提供商(internet service providers，ISPs)獲得。超出SLA中規(guī)定限額的使用一般會(huì)引起高于SLA中最初商定的額外費(fèi)用。由于客戶的未來(lái)需求本身是不確定的，所以媒體內(nèi)容提供商的初始容量供應(yīng)過(guò)程必須基于預(yù)期客戶使用模式和需求的預(yù)測(cè)對(duì)成本達(dá)成平衡。

由于多播利用了信息的可復(fù)制性，從而可獲得高效的帶寬利用和高吞吐量[3]。如果進(jìn)一步利用網(wǎng)絡(luò)編碼，將使得多播路由算法是最優(yōu)的和高效可計(jì)算的。對(duì)于有向和無(wú)向網(wǎng)絡(luò)中的多播來(lái)說(shuō)，采用網(wǎng)絡(luò)編碼會(huì)得到更高的吞吐量以及更便宜的路由成本[3,4]。此外，還可以采用線性規(guī)劃(linear programs，LP)來(lái)計(jì)算高效多播。

已有大量文獻(xiàn)研究了不同情形下通信網(wǎng)絡(luò)的容量規(guī)劃。文獻(xiàn)[5]提出了一種用于需求不確定時(shí)的容量規(guī)劃算法；文獻(xiàn)[6]針對(duì)面臨不確定性流量需求時(shí)需要提前預(yù)留最佳帶寬的虛擬專用網(wǎng)絡(luò)(virtual private networks，VPN)客戶，提出了一種基于隨機(jī)規(guī)劃模型；文獻(xiàn)[7]通過(guò)對(duì)不同場(chǎng)景下網(wǎng)絡(luò)資源分配方法進(jìn)行需求分析，提出了完全壟斷和完全競(jìng)爭(zhēng)的網(wǎng)絡(luò)資源分配模型；文獻(xiàn)[8]提出并分析了一種基于定價(jià)的收入管理模型，同時(shí)針對(duì)隨機(jī)需求提出了一種基于動(dòng)態(tài)規(guī)劃的解決方案。

也有不少文獻(xiàn)對(duì)隨機(jī)優(yōu)化進(jìn)行研究。文獻(xiàn)[9]采用隨機(jī)優(yōu)化理論對(duì)異構(gòu)網(wǎng)絡(luò)中的若干關(guān)鍵問(wèn)題進(jìn)行了研究，同時(shí)介紹了隨機(jī)優(yōu)化中采用的一些技術(shù)和模型；近年來(lái)，隨機(jī)優(yōu)化問(wèn)題還受到了計(jì)算機(jī)理論界的廣泛關(guān)注。文獻(xiàn)[10]對(duì)各種經(jīng)典組合優(yōu)化問(wèn)題的各種隨機(jī)形式進(jìn)行了研究；文獻(xiàn)[11]將LP四舍五入用來(lái)得到隨機(jī)Steiner樹(shù)問(wèn)題的常數(shù)因子近似；文獻(xiàn)[12]采用了一種新的原始對(duì)偶技術(shù)來(lái)求解隨機(jī)環(huán)境中尋找最優(yōu)Steiner森林的問(wèn)題。

資源供應(yīng)最主要的挑戰(zhàn)是未來(lái)需求的不確定性，因此，本文假設(shè)存在一個(gè)概率分布，這個(gè)概率分布可以用來(lái)估計(jì)對(duì)多播服務(wù)感興趣的未來(lái)客戶集，于是將采用網(wǎng)絡(luò)編碼的多播容量供應(yīng)問(wèn)題建模為一個(gè)2-階段隨機(jī)優(yōu)化問(wèn)題，目標(biāo)就是設(shè)計(jì)指導(dǎo)在第一階段容量購(gòu)買(mǎi)決策的算法，從而使得兩個(gè)階段的總體成本在預(yù)期中最小化。

1 預(yù)備知識(shí)

將通信網(wǎng)絡(luò)建模為一個(gè)圖G=(V,E,C,w)， 其中V是節(jié)點(diǎn)的集合，E是邊的集合，C和w分別為容量和成本向量。邊e∈E有固定容量C(e)， 以及相關(guān)的每單位流量成本w(e)。

假設(shè)一個(gè)固定的源節(jié)點(diǎn)s∈V為多播接收者集合T?V提供多播服務(wù)。要研究的問(wèn)題是采用網(wǎng)絡(luò)信息流時(shí)，對(duì)隨機(jī)環(huán)境中一個(gè)給定的數(shù)據(jù)速率，最優(yōu)化其多播成本。多播流是一個(gè)向量f∈Q+E， 其中Q+是非負(fù)有理數(shù)集合。假設(shè)期望的多播(數(shù)據(jù))吞吐量為d，目標(biāo)是得出一個(gè)流量路由方案，使得多播服務(wù)的總成本最小化。假設(shè)e∈E的每單位流量成本為w(e)， 用W(T) 表示服務(wù)集T的多播最優(yōu)成本，多播成本函數(shù)對(duì)于有向網(wǎng)絡(luò)是次可加性的，即對(duì)于不相交集合A,B?T， 滿足

W(A∪B)≤W(A)+W(B)

(1)

網(wǎng)絡(luò)編碼結(jié)果表明，當(dāng)且僅當(dāng)一個(gè)速率d是從源分別到每個(gè)接收者的可行單播速率時(shí)，d的多播速率就是可行的[13,14]，即如果能在獨(dú)立單個(gè)的會(huì)話中得到每個(gè)接收者的速率d的單播流，則該速率的多播流也存在。這樣，可以把有效多播看作是從源到每個(gè)接收者的概念單播流的結(jié)合，因而可以通過(guò)線性規(guī)劃來(lái)計(jì)算概念單播流的有效結(jié)合。

假設(shè)每個(gè)接收者t∈T都有一個(gè)通往源的路徑集合Pt。對(duì)于路徑p∈Pt，用f(p)表示沿p從s到t的概念流，用f(e)表示邊e上的真實(shí)流，則可以通過(guò)下面的LP計(jì)算最小的多播流成本

Minimize： ∑ew(e)f(e)

(2)

滿足

∑p∈Ptf(p)=d?t

(3)

f(e)≥∑p∈Pt∶e∈pf(p) ?e,?t

(4)

C(e)≥f(e) ?e

(5)

f(e)≥0；f(p)≥0 ?e,?p∈Pt,?t

約束條件式(3)要求全部多播接收者必須獲得d的流速率。每個(gè)邊上的真實(shí)流是采用該邊的全部概念流的最大值，即

f(e)=maxt∑p∈Pt;e∈pf(p)

(6)

盡管max(·)函數(shù)是非線性的，但約束條件式(4)等價(jià)地給出了優(yōu)化方向，最后，每個(gè)邊上的流量必須遵從容量約束條件式(5)。

圖1 不采用網(wǎng)絡(luò)編碼與采用網(wǎng)絡(luò)編碼的成本比較

2 基于2-階段成本優(yōu)化的隨機(jī)多播

2.1 最優(yōu)多播模型

這部分建立一個(gè)隨機(jī)環(huán)境下的最優(yōu)多播模型。如前所述，本文研究的隨機(jī)多播問(wèn)題包括2個(gè)階段。在第一階段，得到潛在多播接收者集合T的概率分布，這些分布基于市場(chǎng)預(yù)測(cè)或歷史客戶使用模式；在第二階段，將此建模為真實(shí)的多播接收者集合A的實(shí)現(xiàn)。對(duì)于一個(gè)接收者t∈T，令P(t) 為t在第二階段將要訂閱的多播服務(wù)的概率，并假設(shè)這些概率是獨(dú)立的，即?t,t′∈T，P({t,t′}?A)=P(t)P(t′)。 定義一個(gè)膨脹參數(shù)λ，它使得在第二階段中邊e的成本從w(e)增加到λw(e)，這相當(dāng)于使用了超過(guò)SLA規(guī)定限額而引起的更高價(jià)格。目標(biāo)就是在第一階段要明智地購(gòu)買(mǎi)容量，使得在第二階段中對(duì)于多播集的所有可能實(shí)現(xiàn)A?T的期望總成本最小化。令g∈Q+E為在第一階段購(gòu)買(mǎi)容量的向量，hA∈Q+E表示當(dāng)集合A實(shí)現(xiàn)時(shí)在第二階段所需要的額外容量的向量，定義

P(A)=∏t∈AP(t)∏t?A(1-P(t))

(7)

則可以將2個(gè)階段的最小化期望成本構(gòu)建為一個(gè)LP

Minimize： ∑ew(e)g(e)+∑e∑A?TP(A)λw(e)hA(e)

(8)

滿足

∑p∈PtfA(p)=d?t∈A,?A

(9)

fA(e)≥∑p∈Pt∶e∈pfA(p)?e,?t∈A,?A

(10)

C(e)≥fA(e) ?e,?A

(11)

g(e)+hA(e)≥fA(e) ?e,?A

(12)

g(e),hA(e),fA(e),fA(p)≥0 ?e,?p∈Pt,?t∈A,?A

LP式(8)計(jì)算服務(wù)集A的全部可能實(shí)現(xiàn)的最小期望成本即最優(yōu)解。前3個(gè)約束條件表明，對(duì)于每個(gè)集合A?T，網(wǎng)絡(luò)編碼多播的可行性要求必須滿足，最后的約束條件表明，在2個(gè)階段購(gòu)買(mǎi)的容量數(shù)量必須足以容納服務(wù)集A的多播流fA。

在獨(dú)立分布概率的情況下，存在指數(shù)級(jí)的多個(gè)集合A，而且直接用LP式(8)計(jì)算最優(yōu)向量g*是很難的。因此，下面提出2種算法來(lái)指導(dǎo)第一階段的購(gòu)買(mǎi)，使得總成本接近通過(guò)LP式(8)計(jì)算得到的最優(yōu)解成本。

2.2 啟發(fā)式算法

算法基于以下前提：由于容量因因子λ而變得更昂貴，直觀上，如果e上需要c的概率大于1/λ，則可以通過(guò)在e上購(gòu)買(mǎi)容量c來(lái)最小化預(yù)期成本。

具體來(lái)說(shuō)，假設(shè)T是潛在接收者集合，令f為從源到T的全部成員的最優(yōu)最小成本流。對(duì)于每個(gè)邊e，令ft(e)為該邊上從s到一個(gè)特定接收者t∈T的總的概念流。由于概念流不競(jìng)爭(zhēng)帶寬，因此，全部接收者在每個(gè)邊上就存在k≤|T| 個(gè)不同級(jí)別的總的概念流。用li表示邊e上的級(jí)別為i∈{1,2,…,k} 的總流量，不失一般性，假設(shè)這些級(jí)別按總流量的降序排序，即li+1li的接收者t出現(xiàn)的概率，這相當(dāng)于沒(méi)有從子集Ti-1(e) 中得到未來(lái)接收者的概率。更準(zhǔn)確地說(shuō)，用P≤(li,e) 表示邊e需要至多l(xiāng)i個(gè)單位流的容量的概率，同樣，P≥(li,e) 為邊e需要至少li個(gè)單位流的容量的概率，則P≤(li,e) 可計(jì)算為

P≤(li,e)=∏j∈Ti=1(e)(1-P(j))

(13)

此外，還有

P≥(li,e)=1-P≤(li+1,e)

(14)

可見(jiàn)，在預(yù)期中，無(wú)論概率P≥(li,e) 是否大于1/λ，當(dāng)單獨(dú)考慮這個(gè)邊時(shí)，通過(guò)購(gòu)買(mǎi)等于li個(gè)單位流量的容量可以使得成本最小化。

將網(wǎng)絡(luò)中的每個(gè)邊應(yīng)用上面的算法思想，其偽代碼實(shí)現(xiàn)如算法1；算法首先計(jì)算最小成本流f，然后檢查每個(gè)邊上不同的概念流級(jí)別。然后，算法建議當(dāng)且僅當(dāng)P≥(li,e)>1/λ時(shí)對(duì)于邊e購(gòu)買(mǎi)等于li個(gè)流量單位的容量。

算法1： 啟發(fā)式算法

Input： 潛在多播接受者集合T,t∈T的訂閱概率P(t)， 網(wǎng)絡(luò)圖G(V,E,C,w)

Output： 在第一階段要購(gòu)買(mǎi)的容量向量g∈Q+E

(1)在T上運(yùn)行LP式(2), 令f為得到的流;

(2)g(e)∶=0,?e∈E;

(3)for eache∈Edo

(4) for eacht∈Tdo

(5)ft(e)∶=∑p∈Pt∶e∈pf(p);

(6)F(e)∶={ft(e)|ft(e)>0};

(7) 對(duì)F(e)排序, 令l1,…,lk為e上概念流級(jí)別的降序;

(8)Ti(e)∶={t|ft(e)≥li} ?i∈{1,…,k};

(9) for eachi∈{1,…,k} do

(10)P≤(li+1,e)∶=∏j∈Ti(e)(1-P(j));

(11)P≥(li,e)∶=1-P≤(li+1,e);

(12) ifP≥(li,e)>1/λthen

(13)g(e)∶=li;

(14) end

(15) end

(16)end

(17)輸出g

圖2 啟發(fā)式算法導(dǎo)致沒(méi)有恒定約束的示例網(wǎng)絡(luò)

在這個(gè)示例中算法1性能較差，因?yàn)樵诔跏甲钚〕杀玖饔?jì)算中沒(méi)有考慮接收者的概率分布。這就要求求解方法需要考慮初始流計(jì)算階段的分布。因此，下一節(jié)提出一種基于采樣的方法，為預(yù)測(cè)未來(lái)情形提供一種更準(zhǔn)確的方法，并在理論上具有可證明的性能保證。

2.3 采樣算法

下面首先給出具體的采樣算法，然后證明它的性能約束。

2.3.1 采樣算法

算法2： 采樣算法

Input： 潛在多播接受者集合T,t∈T的訂閱概率P(t)， 網(wǎng)絡(luò)圖G(V,E,C,w)

Output： 在第一階段要購(gòu)買(mǎi)的容量向量g∈Q+E

(1)Λ∶={?};

(3)Ai={?};

(4) for eacht∈Tdo

(5)r∶=[0,1] 中的隨機(jī)數(shù);

(6) ifr≤P(t) then

(7)Ai∶=Ai∪{t};

(8) end

(9) end

(10)Λ∶=A∪Ai;

(11)end

(12)在Λ上運(yùn)行LP式(2), 令f*為最優(yōu)最小成本流向量;

(13)for eache∈Edo

(14)g(e)=f*(e);

(15)end

(16)輸出g

在第二階段，一旦接收者的真實(shí)集合S已知，就需要用服務(wù)集合S所需的額外容量來(lái)增加第一階段的解。對(duì)于每個(gè)邊e，用兩個(gè)邊e′和e″替換它。設(shè)e′的容量為g(e)，成本w(e′)=0， 并將剩余容量和初始成本分配給e″，即C(e″)=C(e)-g(e) 且w(e″)=w(e)， 則在這個(gè)新圖上計(jì)算得到的最小成本是集合S/Λ對(duì)Λ增加的成本，用WAUG(Λ,S/Λ) 表示。

盡管算法本身相對(duì)簡(jiǎn)單明瞭，但關(guān)鍵在于證明算法有一個(gè)好的性能約束。為此，首先引入成本分?jǐn)偡桨傅母拍?。成本分?jǐn)偡桨甘菍⒍嗖ソ獾某杀痉峙浣o接收者集合的一種方法。具體說(shuō)，給定一個(gè)最優(yōu)多播算法AM，它計(jì)算一個(gè)接收者集合A的多播成本，則成本分?jǐn)偡桨甫危?V×V→R≥0將成本份額ξ(A,t) 分配給每個(gè)接收者t∈A。

定義1 設(shè)AM是一個(gè)計(jì)算多播最優(yōu)最小成本的算法，ξ(·,·) 是相關(guān)的成本分?jǐn)偡桨?，則對(duì)于任意兩個(gè)不相交接收者集合A,B?T來(lái)說(shuō)，如果以下3個(gè)屬性都滿足，稱ξ(·,·) 為β-嚴(yán)格的成本分?jǐn)偤瘮?shù)：

(1)ξ(A,t)>0僅當(dāng)t∈A；

(2)∑t∈Aξ(A,t)≤W(A)；

前兩個(gè)屬性在博弈論中分別稱為個(gè)體理性和預(yù)算平衡[15]。第一個(gè)屬性表明，如果一個(gè)多播接收者沒(méi)有接收到服務(wù)，則不應(yīng)當(dāng)要求它支付。第二個(gè)屬性表明，收到的支付總額不應(yīng)超過(guò)解的成本。最后一個(gè)屬性關(guān)系到集合B中接收者在集合A∪B中被服務(wù)時(shí)的成本分?jǐn)?，即將B增加到A的現(xiàn)有解的成本。如果β-嚴(yán)格的成本分?jǐn)傟P(guān)于算法AM存在，則B中接收者的成本分?jǐn)倯?yīng)該至少涵蓋集合A的多播解的增加成本的1/β。β-嚴(yán)格的成本分?jǐn)偞_保了增加的成本可以受到這些成本分?jǐn)偟募s束，因此，改用符號(hào)將∑t∈Bξ(A∪B,t) 表示為ξ(A∪B,B)。 下面來(lái)表明算法2的性能約束。

定理1 給定一個(gè)采用網(wǎng)絡(luò)編碼的多播最優(yōu)最小成本的相關(guān)β-嚴(yán)格的成本分?jǐn)偤瘮?shù)，算法2構(gòu)建了一個(gè)采用2-階段隨機(jī)多播問(wèn)題的(1+β)-近似解。

由于篇幅所限，這里不給出該定理的證明過(guò)程。

注意，算法2未明確采用成本分?jǐn)偡桨?。性能約束的證明只需要存在某個(gè)β-嚴(yán)格的成本分?jǐn)偡桨?，它可以與用于計(jì)算最優(yōu)多播流的算法相關(guān)聯(lián)。因此，本文的目標(biāo)是證明成本分?jǐn)偟拇嬖?，特別是對(duì)于網(wǎng)絡(luò)編碼多播是嚴(yán)格的，并且有有界的嚴(yán)格因子β，這樣才能表明算法2是隨機(jī)多播問(wèn)題的一個(gè)很好的解決方案。對(duì)于任意兩個(gè)不相交集A,B?T， 以及一個(gè)給定的成本分?jǐn)偡桨甫?·,·)， 可以將β定義為

(15)

2.3.2 平均成本分?jǐn)偸荗(|T|)-嚴(yán)格的

圖3 平均成本分?jǐn)倢?dǎo)致無(wú)約束嚴(yán)格因子的網(wǎng)絡(luò)(這時(shí)β=k)

(16)

因此，增加的成本為kξ(T,tk)， 這意味著β=k=O(|T|)。 因此，平均成本分?jǐn)倢?duì)于證明采樣算法的約束來(lái)說(shuō)不是一個(gè)可行的候選方案。

2.3.3 成本分?jǐn)偟腖P對(duì)偶解是2-嚴(yán)格的

LP式(2)的對(duì)偶線性規(guī)劃為下列最大化問(wèn)題

Maximize： ∑txtd-∑eC(e)s(e)

(17)

滿足

∑tyt(e)≤w(e)+s(e) ?e

(18)

xt≤∑e∈pyt(e) ?p∈Pt,?t

(19)

xt<>0；yt(e)≥0；s(e)≥0 ?t,?e

在對(duì)偶LP中，變量xt、yt(e)和s(e)分別對(duì)應(yīng)于原始LP式(2)中的約束式(3)～式(5)。將對(duì)偶最優(yōu)解表示為 (x*,y*,s*)。 具體來(lái)說(shuō)，如果無(wú)限小流量單位是一個(gè)非合作多播路由博弈中的自私代理，則基于對(duì)偶變量的成本分配方案就能確保最優(yōu)最小成本流是納什均衡。因此，對(duì)偶解成本分?jǐn)偡桨冈诜呛献骶W(wǎng)絡(luò)環(huán)境中執(zhí)行最優(yōu)多播流。

(20)

因此，變量xt表示t的每單位流量成本，這樣，每個(gè)接收者的總成本為xtd。但這種成本分配方案只在成本度量w(e)下是預(yù)算平衡的，也就是說(shuō)，如果用成本w(e)+s(e) 替換每個(gè)邊的成本w(e)，且W′(T) 是該新度量下的最小多播流的成本，則成本分配方案就是預(yù)算平衡的，因此∑t∈Txtd=W′(T)。 下面來(lái)證明這樣的成本分?jǐn)偡桨甘?-嚴(yán)格的。

令W(T)為由LP式(2)計(jì)算得到的接收者集合T的最優(yōu)流量成本，考慮下列線性規(guī)劃

Minimize： ∑ew(e)f(e)

(21)

滿足

∑ew(e)f(e)=W(T)

(22)

∑p∈Ptf(p)≥d?t

(23)

f(e)≥∑p∈Pt∶e∈pf(p) ?e,?t

(24)

f(e)≥0；f(p)≥0 ?e,?p∈Pt,?t

在總成本等于W(T)下，LP式(21)使得多播流成本最小化，即目標(biāo)函數(shù)為W(T)。式(21)的對(duì)偶LP如下

Minimize： ∑txtd+βW(T)

(25)

滿足

xt≤∑e∈pyt(e) ?p∈Pt,?t

(26)

∑tyt(e)≤(1-β)w(e) ?e

(27)

β<>0；xt≥0；yt(e)≥0； ?t,?e

下面的引理表明，LP式(25)中的對(duì)偶向量x構(gòu)成了一個(gè)有效的成本分?jǐn)偡桨福摲桨戈P(guān)于W(T)是預(yù)算平衡的。

引理的證明可以直接從LP的對(duì)偶性得到。因?yàn)閮蓚€(gè)LP的目標(biāo)函數(shù)有相同的最優(yōu)解值，因此，具有所述性質(zhì)的解一定存在。事實(shí)上，如果在具有無(wú)限邊容量的網(wǎng)絡(luò)中最小成本流更便宜，則對(duì)于LP式(25)的每個(gè)最優(yōu)對(duì)偶解，可得到β=0。下面給出有效的成本分?jǐn)偡桨浮?/p>

定義2 令 (x*,y*,β*) 是對(duì)于接收者集合T、多播速率為d的LP式(15)的任意最優(yōu)解，這樣β*=0， 則定義成本分?jǐn)偡桨笧?/p>

(28)

成本分?jǐn)偡桨甫?·,·) 是一種有效的成本分?jǐn)偡桨?，因?yàn)樗穷A(yù)算平衡的，而且不在多播集中的接收者有零成本。

下面表明分?jǐn)偡桨甫?·,·) 是2-嚴(yán)格的，它基于以下3個(gè)引理，引理的證明略。

引理2 在網(wǎng)絡(luò)編碼多播中，成本分?jǐn)偡桨甫?·,·) 對(duì)于任意兩個(gè)不相交集合A和B，ξ(A∪B,A)≤W(A)；

引理3ξ(A∪B,B)≥W(A∪B)-W(A)；

引理4W(A∪B)-W(A)≤WAUG(A,B)≤2(W(A∪B)-W(A))。

由上面3個(gè)引理可以得到下面的定理。

定理2 LP式(17)的對(duì)偶變量定義了2-嚴(yán)格的成本分?jǐn)偂?/p>

證明：由于成本分?jǐn)傊贿m用于多播接收者，因此要尊重個(gè)體理性，根據(jù)定義，成本分?jǐn)傄彩穷A(yù)算平衡的。根據(jù)引理3和引理4得到

(29)

證明完成。

作為成本分?jǐn)偟膶?duì)偶變量的嚴(yán)格因子的上界顯然是2?，F(xiàn)在通過(guò)考慮圖1所示的網(wǎng)絡(luò)來(lái)給出β的下界。假設(shè)目標(biāo)多播率為1，可以發(fā)現(xiàn)對(duì)偶變量定義了在這種情形下唯一的成本分?jǐn)偅绂?T,t1)=1.5， 其中T={t1,t2,t3}。 此外，WAUG(t2∪t3,t1)=2， 因此β=2/1.5=1.333。

定理1和定理2為采樣算法提供了理論上的性能保證。

3 算法仿真結(jié)果及分析

3.1 仿真環(huán)境及設(shè)置

仿真在采用C++的BRITE[16]網(wǎng)絡(luò)拓?fù)渖善麟S機(jī)生成的網(wǎng)絡(luò)上進(jìn)行。BRITE是一種用于生成與Internet非常相似的拓?fù)涔ぞ?，它可以用自頂向下和自底向上兩種方法來(lái)產(chǎn)生GT-ITM層次模型，同時(shí)可為多個(gè)網(wǎng)絡(luò)模擬程序提供接口，如NS-2、SSF、Omnet++和Jsim等，并支持可視化工具Otter；BRITE能生成路由器層、AS層以及分層結(jié)構(gòu)拓?fù)鋱D，并可為連接分配帶寬和延遲，具有可視化用戶接口；我們?cè)谒惴ㄖ须S機(jī)分配邊容量和成本值，源節(jié)點(diǎn)和多播接收者集合也隨機(jī)選擇。除非特別說(shuō)明，全部接收者都按均勻分布隨機(jī)分配一個(gè)訂閱概率。在第一階段，根據(jù)算法1和算法2的建議購(gòu)買(mǎi)容量，在第二階段，用接收者的訂閱概率隨機(jī)生成真實(shí)的接收者集合，并以膨脹因子為λ的價(jià)格購(gòu)買(mǎi)額外的容量。得到的每個(gè)數(shù)據(jù)點(diǎn)是重復(fù)實(shí)驗(yàn)200次并取平均值的結(jié)果；為了表明本文算法的性能，將通過(guò)LP式(8)得到的最優(yōu)解作為比較基準(zhǔn)，并與文獻(xiàn)[8]的基于網(wǎng)絡(luò)收益最大化的定價(jià)管理模型的成本解進(jìn)行比較。

3.2 仿真實(shí)驗(yàn)結(jié)果

圖4為對(duì)于不同網(wǎng)絡(luò)大小和不同多播接收者數(shù)量得到的不同算法的解成本，其中膨脹參數(shù)λ設(shè)置為5?？梢?jiàn)，對(duì)于不同網(wǎng)絡(luò)大小時(shí)，本文提出的兩種算法與最優(yōu)解非常接近，甚至在某些情形下還優(yōu)于最優(yōu)解。對(duì)于不同多播接收者數(shù)量時(shí)(這時(shí)網(wǎng)絡(luò)大小固定在100個(gè)節(jié)點(diǎn))，啟發(fā)式算法始終優(yōu)于最優(yōu)解；還可看到，在兩種情形下，啟發(fā)式算法略優(yōu)于采樣算法，而且在兩種情形下，本文的兩種算法始終優(yōu)于文獻(xiàn)[8]的方案。

圖4 不同算法得到的解成本比較

圖5為膨脹參數(shù)λ對(duì)兩種算法性能的影響。對(duì)于小的λ值變化，如圖5(a)所示，兩種算法的性能與最優(yōu)解的差都在10%以內(nèi)，基本不受λ值的影響；隨著膨脹參數(shù)的不斷增大，如圖5(b)所示，兩種算法的性能基本都能收斂到最優(yōu)解。這是因?yàn)楫?dāng)?shù)诙A段的成本增大時(shí)，兩種算法都能為第一階段的全部接收者集合提供最優(yōu)解。

圖5 膨脹參數(shù)λ對(duì)算法1和算法2性能的影響

由前面分析知道，啟發(fā)式算法在初始最小成本流計(jì)算中不考慮接收者的概率分布，從而在某些情形下可能運(yùn)行很差，而采樣算法考慮了接收者的概率分布，為預(yù)測(cè)未來(lái)情形提供了一種更準(zhǔn)確的方法，并具有理論上的性能保證。為了比較兩種算法，我們將訂閱概率在范圍[0,0.1]內(nèi)均勻抽取，網(wǎng)絡(luò)大小由100個(gè)節(jié)點(diǎn)構(gòu)成，有10個(gè)多播接收者且設(shè)置λ=10；圖6為通過(guò)啟發(fā)式算法和采樣算法得到的解成本?？梢钥吹?，兩種算法的解都接近最優(yōu)解，但采樣算法的性能要優(yōu)于啟發(fā)式算法。原因是啟發(fā)式算法最初計(jì)算全部接收者的最優(yōu)多播流，可能最終在更昂貴的邊上購(gòu)買(mǎi)容量，另一方面，當(dāng)在計(jì)算第一階段的目標(biāo)多播集時(shí)，采樣算法通過(guò)考慮訂閱概率來(lái)求解這個(gè)問(wèn)題；還可看到，隨著極低訂閱概率的接收者數(shù)量的增加，與采樣算法相比，啟發(fā)式算法的性能受到的影響越來(lái)越大。

圖6 不同訂閱概率接受者數(shù)量對(duì)算法性能的影響

圖7 采樣輪數(shù)對(duì)采樣算法性能的影響

4 結(jié)束語(yǔ)

由于互聯(lián)網(wǎng)數(shù)據(jù)傳播服務(wù)的普及以及內(nèi)容提供商和ISPs之間的SLA商業(yè)模式，明智的多播容量規(guī)劃使得其自身成為一個(gè)重要的研究方向；本文將具有不確定性的多播容量規(guī)劃構(gòu)建為一個(gè)具有追加的2-階段隨機(jī)優(yōu)化，提出了2種解決方案，即利用網(wǎng)絡(luò)編碼優(yōu)勢(shì)的啟發(fā)式解決方案和進(jìn)一步結(jié)合采樣技術(shù)的改進(jìn)方案。仿真結(jié)果表明，2種解決方案的實(shí)際性能接近最優(yōu)解的性能。

盡管本文的研究為采用網(wǎng)絡(luò)編碼的多播容量規(guī)劃問(wèn)題提供了新的見(jiàn)解，但仍存在一些局限性。本文的解決方案更適用于替代網(wǎng)絡(luò)，如無(wú)線Mesh網(wǎng)或大規(guī)模無(wú)線Ad-hoc網(wǎng)絡(luò)，所以將本文的研究擴(kuò)展到更好的內(nèi)容分發(fā)模型系統(tǒng)是未來(lái)研究的一個(gè)重要方向；此外，本文的研究只考慮了在所有網(wǎng)絡(luò)鏈路的成本一致增加的情況，且只有一個(gè)不確定的階段，還存在非均勻的成本增加，以及多播接收者可以動(dòng)態(tài)訂閱和離開(kāi)多播會(huì)話的多個(gè)階段，這些都是我們未來(lái)研究的內(nèi)容。