基于多目標優(yōu)化的多源組播網(wǎng)絡(luò)編碼的構(gòu)造

摘 要:在基于單目標優(yōu)化構(gòu)造網(wǎng)絡(luò)編碼的基礎(chǔ)上，提出了基于多目標優(yōu)化的網(wǎng)絡(luò)編碼的構(gòu)造方法。把多源組播網(wǎng)絡(luò)劃分成多個單源組播網(wǎng)絡(luò)，各單源組播網(wǎng)絡(luò)的組播容量互相制約，為了使各單源組播網(wǎng)絡(luò)的組播容量達到最大，采用粒子群優(yōu)化算法進行子圖劃分，動態(tài)求解包含各子圖組播容量的Pareto解集。用戶可以優(yōu)先考慮某個子圖的組播容量，選擇相應(yīng)的解向量進行線性網(wǎng)絡(luò)編碼構(gòu)造。仿真測試結(jié)果表明，本方法是可行的。

關(guān)鍵詞:多源組播; 多目標優(yōu)化; 粒子群優(yōu)化算法; 子圖劃分; Pareto解集; 線性網(wǎng)絡(luò)編碼

中圖分類號:TN711

文獻標志碼:A

文章編號:1001-3695(2010)02-0668-04

doi:10.3969/j.issn.1001-3695.2010.02.073

Network coding construction for multi-source multicast connectionbased on multi-objective optimization

LU Hua1，2， YANG Lu-ming1， PU Bao-xing1，3

(1.School of Information Science Engineering， Central South University， Changsha 410083， China; 2.Dept. of Computer Science Engineering， Hunan International Economics University， Changsha 410205， China; 3.Dept. of Information Engineering， Shaoyang College， Shaoyang Hunan 422001， China)

Abstract:This paper proposed network coding construction method for multi-objective optimization based on single-objective optimization. Divided the network into several sub-graphs， which were single-source multicast networks and the multi-cast capacities of all single-source multicast networks constrain each other.In order to maximize the multi-cast capacity of each single-source multicast network， adopted particle swarm optimization algorithm to divide the network into sub-graphs，worked out the pareto solution set which contain the multi-cast capacity of each sub-graphs dynamicly.The user can take into account the multi-cast capacity of certain sub-graphs firstly，and choose the corresponding solution，then construct the linear network coding. Simulation and test results show that the proposed approach is feasible.

Key words:multi-source multicast; multi-objective optimization; particle swarm optimization algorithm; partition of sub-graphs; Pareto solution set; linear network coding

傳統(tǒng)的網(wǎng)絡(luò)組播中，網(wǎng)絡(luò)節(jié)點只對數(shù)據(jù)分組進行路由和轉(zhuǎn)發(fā)，很難達到網(wǎng)絡(luò)組播的最大傳播容量。Elias等人[1]指出:通信網(wǎng)絡(luò)端到端的最大信息流，是由網(wǎng)絡(luò)有向圖的最小割決定的。但目前傳統(tǒng)路由器的存儲轉(zhuǎn)發(fā)模式根本不可能達到香農(nóng)最大流最小割定理規(guī)定的上界，Ahlswede等人[2]于2000年提出的網(wǎng)絡(luò)編碼指出對組播網(wǎng)絡(luò)中的某些節(jié)點附加額外的編碼操作能使源點與組播成員間達到最大流最小割的組播速率[3]。網(wǎng)絡(luò)編碼一經(jīng)提出便引起了學術(shù)界的廣泛關(guān)注，其理論和應(yīng)用已成為通信領(lǐng)域研究的新熱點。已有文獻主要針對單源組播網(wǎng)絡(luò)編碼設(shè)計進行研究，并得到了較成熟的解決方法[4~6];而對多源組播問題的研究還比較少。文獻[7]為了實現(xiàn)網(wǎng)絡(luò)的吞吐量達到最大，把劃分子圖問題歸結(jié)為一個組合優(yōu)化問題，在各源點組播數(shù)據(jù)無優(yōu)先級的條件下給出了基于單目標優(yōu)化的劃分子圖方法。在實際應(yīng)用中，若需要對各個源點的吞吐率進行考慮，每一個源點都期望能達到最大的吞吐率，但各個源點的吞吐率又相互制約，則對多源組播網(wǎng)絡(luò)的子圖劃分是一個多目標優(yōu)化問題。

本文研究了在多源組播網(wǎng)絡(luò)中，要求每個子圖的吞吐量最大的問題。該問題在實際中應(yīng)用非常廣泛，例如，用戶需要收看本地新聞，同時又要觀看世界杯的決賽，這是兩個源點組播信息到多個宿點的情形，用戶希望這兩個源點的吞吐率都最優(yōu)。本文列出了劃分子圖的數(shù)學模型，采用基于多目標優(yōu)化的粒子群算法求解。假定所有源點組播數(shù)據(jù)的優(yōu)先級相同，則不存在哪一個源點需要優(yōu)先發(fā)送的情況。當子圖劃分后，采用Ford-Fulkerson[8]算法計算每個子圖的組播容量，則各個子圖的組播容量之和為多源組播網(wǎng)絡(luò)的吞吐量，可以動態(tài)求得問題的Pareto解集[9]。每一種解對應(yīng)一種子圖劃分方式。若用戶需要優(yōu)先考慮某個子圖的組播容量，則在Pareto解集中選擇此子圖組播容量達到最大值的一個解向量;然后根據(jù)這個解向量對應(yīng)的子圖劃分方式，采用實現(xiàn)單源組播連接的技術(shù)分別對各子圖的信道進行編碼構(gòu)造。

1 相關(guān)知識

1.1 單源組播網(wǎng)絡(luò)

假設(shè)一個單源組播網(wǎng)絡(luò)用有向無環(huán)圖G=(V，E)來表示。其中:V為網(wǎng)絡(luò)中的節(jié)點集;E為有向邊集，有向邊表示網(wǎng)絡(luò)節(jié)點之間存在的有向鏈路，鏈路的容量為整數(shù)。設(shè)S是源點，R={r1，r2，…，rd}為宿點集。

線性網(wǎng)絡(luò)編碼對單位容量的信道進行編碼，當連接兩個節(jié)點的有向鏈路的容量大于1時，把這條鏈路分成多條單位容量的信道。對于節(jié)點v∈V，記in(v)和out(v)分別為輸入信道集和輸出信道集，|in(v)|和|out(v)|分別為節(jié)點v的輸入信道數(shù)和輸出信道數(shù)。

信道傳輸以數(shù)據(jù)包為單位，數(shù)據(jù)包由若干字符構(gòu)成，而編碼和解碼以字符為單位。選定一個有限域GF(2m)[10]，設(shè)源點的數(shù)據(jù)傳輸速率(簡稱組播率)為h。在源點，信息流被劃分成h等分，每等分恰好是GF(2m)上的一個字符，分別記為y1，y2，…，yh。

節(jié)點輸出信道傳輸?shù)淖址窃摴?jié)點所有輸入字符的線性組合，信道e傳輸?shù)淖址洖閥(e)，則由式(1)計算:

y(e)=d∈in(tail(e))md，ey(d)(1)

其中:md，e是GF(2m)上的一個系數(shù)，這些系數(shù)的組合構(gòu)成信道e的局部編碼向量，記為m(e)。

信道e傳輸?shù)淖址€可以表示成y1，y2…，yh的線性組合，記為

y(e)=ge，1y1+ge，2y2+…+ge，hyh(2)

其中:g(e)=(ge，1，ge，2，…，ge，h)稱為信道e的全局編碼向量，且下式成立。

g(e)=∑d∈in(tail(e))md，eg(d)(3)

由式(2)，信道的全局編碼向量和傳輸?shù)淖址纬梢粋€關(guān)于y1，y2，…，yh的線性方程，宿點r(r∈R)從輸入信道接收信息后，得到一個關(guān)于y1，y2，…，yh的解碼方程組。只有當該方程組的系數(shù)矩陣的秩為h時，才能恢復出源點播出的信息。

1.2 多源組播網(wǎng)絡(luò)

定義1 在一個有向無環(huán)網(wǎng)絡(luò)中，若R為宿點集，對于任一非宿點v(vR)和宿點r(r∈R)，記mincut(v，r)為分離節(jié)點v與宿點r的最小割中的信道數(shù);記maxflow(v，R)為節(jié)點v至所有宿點的最小割的信道數(shù)的最小值，即

maxflow(v，R)=minr∈R{mincut(v，r)}(4)

其中:maxflow(v，R)是節(jié)點v至宿點集R最大流，稱為組播容量。若節(jié)點v需要組播數(shù)據(jù)至R中的所有宿點，由文獻[1]，則數(shù)據(jù)傳輸速率不能超過maxflow(v，R)。在網(wǎng)絡(luò)拓撲已知的環(huán)境下，可以采用Ford-Fulkerson算法來求兩點之間的最小割值，從而可以求出組播容量。

定義2 多源組播連接是多源組播網(wǎng)絡(luò)中多個源點需要組播數(shù)據(jù)至相應(yīng)的宿點。多源多宿組播網(wǎng)絡(luò)用有向圖G=(V，E)表示。其中:V表示節(jié)點集;E表示有向邊集，有向邊代表節(jié)點之間的有向鏈路。假定鏈路是無錯的，S={s1，s2，…，sn}為源點集。其中n>1為源點的個數(shù)，各源點是相互獨立的，R={r1，r2，…，rd}為宿點集，其中d>1為宿點的個數(shù)，各宿點沒有輸出邊，T={t1，t2，…，tn}為虛擬宿點集，各虛擬宿點對應(yīng)的宿點集可以存在交集。虛擬宿點的個數(shù)等于源點的個數(shù)，S中的每一源點需要組播數(shù)據(jù)至相應(yīng)的一個虛擬宿點。

圖1給出了這類問題的一個示例。其中:S={s1，s2}為源點集;R={r1，r2，r3，r4}為宿點集，T={t1，t2}為宿點集，各源點要求同時組播數(shù)據(jù)至相應(yīng)宿點，即源點s1需要組播信息到宿點r1和r2，源點s2需要組播信息到宿點r3和r4，圖中的有向邊代表連接兩個頂點的鏈路，鏈路的容量如圖所示。將圖中容量大于1的邊分成多條單位容量的信道，即分成多條權(quán)值為1的有向邊，則圖1對應(yīng)的多重圖為圖2。

1.3 多目標優(yōu)化

多目標優(yōu)化問題在一定約束下，希望使得多個目標都能達到最優(yōu)。由于存在目標之間的沖突和無法比較的現(xiàn)象，一個解在某個目標上是最好的，在其他的目標上可能比較差。Pareto在1986年提出多目標的解不受支配解(non-dominated set)的概念。其定義為:假設(shè)任何二解S1及S2對所有目標而言，S1均優(yōu)于S2，則稱S1支配S2，若S1的解沒有被其他解所支配，則S1稱為非支配解(不受支配解)，也稱Pareto解。Pareto最優(yōu)指資源分配的一種狀態(tài)，在不使任何目標境況變壞的情況下，不可能再使某些目標變好。所有Pareto最優(yōu)解的集合構(gòu)成Pareto最優(yōu)解集。

1.4 粒子群優(yōu)化算法

粒子群優(yōu)化(PSO)算法最早源于對鳥群覓食行為的研究。研究者發(fā)現(xiàn)鳥群在飛行過程中經(jīng)常改變方向、散開、聚集，其行為不可預(yù)測，但其整體總保持一致性，個體與個體間也保持著最適宜的距離。通過對類似生物群體行為的研究，發(fā)現(xiàn)生物群體中存在著一種社會信息共享機制，它為群體的進化提供了一種優(yōu)勢，這也是PSO算法形成的基礎(chǔ)。在PSO中，每個粒子就是解空間中的一個解，粒子在搜索空間的飛行速度動態(tài)地隨粒子自身和同伴的歷史飛行行為改變而改變。每個粒子在飛行過程所經(jīng)歷過的最好位置，就是粒子本身找到的最優(yōu)解。整個群體所經(jīng)歷過的的最好位置，就是整個群體目前找到的最優(yōu)解。前者叫做個體極值(pbest)，后者叫做全局極值(gbest)。每個粒子都通過上述兩個極值不斷更新自己，從而產(chǎn)生新一代群體。實際操作中通過由優(yōu)化問題所決定的適應(yīng)度函數(shù)來評價粒子的好壞程度。

粒子i在搜索空間的速度和位置根據(jù)下式確定:

v[]=v[]+c1rand()(pbest[]-present[])+

c2rand()(gbest[]-present[]) (5)

present[]=persent[]+v[] (6)

其中:v[]是粒子的速度;persent[]是當前粒子的位置;pbest[]和gbest[]如前定義;rand()是介于(0，1)之間的隨機數(shù);c1、c2是學習因子。

2 問題的描述

本文采用鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)輸入多源組播網(wǎng)絡(luò)圖，將權(quán)值為m(m>1)的邊看做權(quán)值為1的m條邊，將原網(wǎng)絡(luò)轉(zhuǎn)換為多重圖。假定多源組播網(wǎng)絡(luò)包含有n個源點，分別為s1，s2，…，sn，每個源點對應(yīng)的宿點集為t1，t2，…，tn，即源點si需要組播信息到相應(yīng)宿點集ti中的每個宿點。

本文采用粒子群算法把多源組播網(wǎng)絡(luò)對應(yīng)的多重圖劃分為多個子圖，每一子圖包含一個源點和該源點對應(yīng)的宿點集，各個子圖間的有向邊互不重疊，從而每一個子圖形成一個單源組播網(wǎng)絡(luò)。把一條邊隸屬于哪一個子圖稱之為該條邊的隸屬屬性值，記x1，x2，…，xk為隸屬屬性值不惟一的邊，稱為可變化的邊，對應(yīng)的子圖分別記為Gi(x1，x2，…，xk)(i=1，2，…，n)，記各個單源組播網(wǎng)絡(luò)的組播容量為mflow(Gi(x1，x2，…，xk)) (i=1，2，…，n)。采用Ford-Fulkerson算法計算每個子圖的組播容量(式(4))，各粒子組播容量向量簡記為{mflow(G1)，mflow(G2)，…，mflow(Gn)}，各個子圖的組播容量之和為多源組播網(wǎng)絡(luò)的吞吐率。

假定所有源點組播數(shù)據(jù)的優(yōu)先級相同，則不存在哪一個源點需要優(yōu)先發(fā)送的情況，擬采用線性網(wǎng)絡(luò)編碼技術(shù)進行數(shù)據(jù)傳輸，并使n個單源組播網(wǎng)絡(luò)的組播容量達到最大，則劃分子圖的問題是一個多目標優(yōu)化問題。

采用多目標粒子群算法可以求得問題的Pareto解集:

{mflowj(G1)， mflowj(G2)，…，mflowj(Gn)}

其中:j=1，2，…，p， p為Pareto解集中解向量的個數(shù)。Pareto解集中的每一個解向量對應(yīng)一種子圖劃分方式，則用戶可以根據(jù)偏好選擇p種子圖劃分方式中的任意一種，然后采用實現(xiàn)單源組播連接的技術(shù)對選取的解向量所對應(yīng)的子圖劃分方式進行網(wǎng)絡(luò)編碼構(gòu)造。

3 基于多目標優(yōu)化的多源組播網(wǎng)絡(luò)編碼的構(gòu)造方法

3.1 子圖劃分

因線性網(wǎng)絡(luò)編碼技術(shù)對單位容量的信道進行編碼，把多源組播網(wǎng)絡(luò)中容量為m(m>1)的鏈路分成m條單位容量的信道，即所考慮的網(wǎng)絡(luò)是一個多重圖。

為了使宿點能正確地解碼，本文采用的思路是:同一條信道傳輸?shù)淖址荒苁悄骋粋€源點播出字符的線性組合，而與其他源點播出的字符不相關(guān)。基于這個思路，把多源組播網(wǎng)絡(luò)劃分為多個子圖，每一個子圖包含了一個源點和該源點對應(yīng)的宿點集，以及源點和宿點間的有向邊，劃分子圖的實質(zhì)是確定每一條有向邊屬于哪一個子圖，即確定每條邊的隸屬屬性值。例如，一條邊屬于第i個子圖，則這條邊的隸屬屬性值為i，當所有邊的隸屬屬性值確定后，則子圖的劃分便惟一確定。圖2中有兩個源點，則可劃分為兩個子圖，其各邊的隸屬屬性值如表1所示。

表1 多重圖G′各邊隸屬屬性值

有向邊隸屬屬性值有向邊隸屬屬性值有向邊隸屬屬性值有向邊隸屬屬性值

s1-111-413-625-r21

s1-211-413-625-r32

s2-222-51，24-r116-r32

s2-322-51，24-r216-r42

從表1中可以確定有向邊s1-1、s1-2、1-4、4-r1、4-r2、5-r2隸屬于子圖1，有向邊s2-2、s2-3、3-6、5-r3、6-r3、6-r4隸屬于子圖2;而有向邊2-5隸屬屬性值不惟一:既可以隸屬于子圖1，也可以隸屬于子圖2，也可以將有向邊2-5分為兩條有向邊后分別隸屬于子圖1和2，如圖3所示。顯然第三種子圖劃分方式可以得到最大的吞吐量。當多源組播網(wǎng)絡(luò)中的可變化的邊較多時，可以限定每一條邊的隸屬屬性值的變化范圍，以便縮小搜索空間。

3.2 采用多目標粒子群優(yōu)化算法求解Pareto解集

假定多源組播網(wǎng)絡(luò)有n個源點，k條可變化邊，在限定范圍內(nèi)，隨機產(chǎn)生k個值，作為k條可變化邊的隸屬屬性值，則x1，x2，…，xk的取值確定，此時構(gòu)成了一個圖的劃分。對應(yīng)的子圖分別記為Gi(x1，x2，…，xk)(i=1，2，…，n)，其對應(yīng)的單源組播網(wǎng)絡(luò)的組播容量為mflow(Gi(x1，x2，…，xk))(i=1，2，…，n)。為了使每個單源組播網(wǎng)絡(luò)的組播容量達到最大，劃分子圖的問題是一個多目標優(yōu)化問題。問題的目標函數(shù)即數(shù)學模型為

max mflow(Gi) (i=1，2，…，n)(7)

以下采用粒子群優(yōu)化算法求解。初始化為一群隨機粒子，然后通過迭代找到最優(yōu)解。在這里粒子的適應(yīng)度值為網(wǎng)絡(luò)的吞吐量，即每個子圖的組播容量之和，記為fitness(x1，…，xk)=∑ni=1mflow(Gi(x1，x2，…，xk))。迭代過程中，確定各子圖的最大組播容量，記錄可變化的有向邊的隸屬屬性值，作為個體極值pbest。記錄最大網(wǎng)絡(luò)吞吐量，即粒子的適應(yīng)度值。記錄此時的有向邊的隸屬屬性值，作為全局極值gbest。在找到這兩個最優(yōu)值時，粒子根據(jù)式(5)和(6)來更新自己的速度和位置，直至最大迭代次數(shù)。

迭代過程中，采用基于動態(tài)Pareto解集的PS0算法求解Pareto最優(yōu)解集。通過建立一個動態(tài)的Pareto最優(yōu)解集庫，對庫中近似Pareto最優(yōu)解的動態(tài)調(diào)整，把找到的所有的近似Pareto最優(yōu)解都存在庫中，同時去除非Pareto最優(yōu)解，從而保證此庫中的所有解都是Pareto最優(yōu)解。第一代時，初始化開始，把第一個微粒的組播容量向量放入這個動態(tài)庫中，對隨后隨機產(chǎn)生的每個微粒所得的結(jié)果與庫中保存的所有微粒的結(jié)果進行比較:a)如果此微粒支配庫中存在微粒，則替換庫中的相應(yīng)微粒，支配個數(shù)加1。b)如果此微粒與庫中的微粒等價，等價個數(shù)加1。依此類推，與庫中所有微粒比較完畢后，如果等價個數(shù)與支配個數(shù)之和等于庫中原微粒個數(shù)，則把此微粒的組播容量向量加入庫中。c)否則對庫中的數(shù)據(jù)不進行修改。d)去掉庫中重復的Pareto最優(yōu)解。以后每一次迭代時，將微粒與上一代確定的動態(tài)庫進行比較，得出新的動態(tài)庫，直至達到最大迭代次數(shù)，此時庫中所保存的即為所求的Pareto最優(yōu)解集。下面給出基于多目標粒子群優(yōu)化算法的子圖劃分算法。

算法1

1)算法初始化

2)隨機產(chǎn)生po個粒子

3)對第一代粒子，計算每個子圖的最大組播容量和多源組播網(wǎng)絡(luò)的最大吞吐量作為適應(yīng)度值，初始化Pareto解集動態(tài)庫，確定pbest和gbest并更新粒子的速度和位置

4) while未達到最大的迭代次數(shù)

5)計算每個粒子的組播容量向量，與Pareto解集動態(tài)庫比較，更新Pareto解集動態(tài)庫

6)計算每個子圖的最大組播容量，如果大于歷史最大值，則更新pbest;計算多源組播網(wǎng)絡(luò)的最大吞吐量，如果大于歷史最大值，則更新gbest

7)更新粒子的速度和位置

8)end while

9)輸出Pareto解集

10)算法結(jié)束

3.3 構(gòu)造網(wǎng)絡(luò)編碼

采用粒子群算法計算出Pareto解集后，可以根據(jù)用戶的權(quán)重選擇需要的解。選定解后，就相當于選擇了一個最優(yōu)的子圖劃分方式。每一子圖是一個單源組播網(wǎng)絡(luò)，然后分別為每一單源組播網(wǎng)絡(luò)的信道構(gòu)造網(wǎng)絡(luò)局部編碼向量;擬采用隨機線性網(wǎng)絡(luò)編碼方法，它具有操作簡便的特點，按某一拓撲順序?qū)Ω鞴?jié)點進行排序，按這一順序逐個為各節(jié)點的輸出信道隨機產(chǎn)生局部編碼向量，然后檢測各宿點的全局編碼矩陣的秩，若所有宿點的全局編碼矩陣的秩均與組播率相等，則各信道的局部編碼向量構(gòu)成了組播連接成功的編碼方案。這里采用的方法是:若某一節(jié)點的輸入鏈路數(shù)為I，輸出鏈路數(shù)為O，則對應(yīng)于每一條輸出鏈路需隨機產(chǎn)生I個編碼系數(shù)，且每一條輸出鏈路所傳輸?shù)男畔镮條輸入鏈路輸入信息的線性組合。

如圖3中，由兩個子圖構(gòu)成。對于左邊的子圖，可以把源點s1看成是有兩條輸入鏈路，兩條輸出鏈路的節(jié)點。可以隨機生成兩個字符(x1，x2)作為輸入信息，對于第一條輸出鏈路，隨機生成兩個字符(e11，e12)，作為兩個輸入信息的編碼系數(shù);對于第兩條輸出鏈路，隨機生成兩個字符(e21，e22)，作為兩個輸入信息的編碼系數(shù)，則第一條輸出鏈路的信息為y1=e11x1+e12x2，第二條輸出鏈路的信息為y2=e21x1+e22x2。

對于中間節(jié)點1，則輸入信息為y1，則每一條輸出鏈路隨機生成一個編碼系數(shù)為e31和e41，輸出鏈路有兩條，則輸出信息為y3=e31y1=e31(e11x1+e12x2)，y4=e41y1= e41(e11x1+e12x2)。

對于中間節(jié)點4，則輸入信息為y3和y4，則每一條輸出鏈路隨機生成兩個編碼系數(shù)，分別為e51和e52，e61和e62。輸出鏈路有兩條，則輸出信息為y5=e51y3+e52y4=e51(e31(e11x1+e12x2))+e52(e41(e11x1+e12x2))，y6=e61y3+ e62y4=e61(e31(e11x1+e12x2))+e62(e41(e11x1+e12x2))。

對于接收節(jié)點r1，輸入信息為y5=e51(e31(e11x1+e12x2))+ e52(e41(e11x1+e12x2))=(e51e31e11+ e52e41e11)x1+(e51 e31 e12+ e52 e41 e12) x2，可以看出r1接收的信息為源點s1發(fā)送信息x1和x2的線性組合。其他節(jié)點的編碼同理。

4 仿真測試

圖4是一個多源組播網(wǎng)絡(luò)，s1需組播數(shù)據(jù)至{r1，r2}，s2需組播數(shù)據(jù)至{r3，r4}，s3需組播數(shù)據(jù)至{r5，r6}，節(jié)點t1，t2，t3為虛擬宿點集。

現(xiàn)采用本文提出的方法對其進行仿真測試，實驗環(huán)境為Pentium D CPU 3.0 GHz，512 MB內(nèi)存。

先把多源組播網(wǎng)絡(luò)轉(zhuǎn)換為一個多重圖，再調(diào)用算法1進行子圖劃分，并求解出Pareto解集。算法1的參數(shù)設(shè)置如下:群體規(guī)模po=100，最大進化代數(shù)iteration=50，隨機因子c1=c2=2，慣性因子w=0.8，速度的初值velocity=1.0。經(jīng)過運算，得到的Pareto解集如表2所示。

表2 Pareto解集

組播容量子圖1子圖2子圖3組播容量子圖1子圖2子圖3

情況1456情況4546

情況2465情況5555

情況3474情況6564

從表2可以看出，Pareto解集中有六個解。若用戶優(yōu)先考慮第一個源點的吞吐率，則可以選擇情況4~6進行編碼;若用戶優(yōu)先考慮第二個源點的吞吐率，則可以選擇情況3進行編碼;同理，若用戶優(yōu)先考慮第三個源點的吞吐率，則可以選擇情況1、4進行編碼。假定優(yōu)先考慮第一個源點的吞吐率，可采用情況6進行子圖劃分。子圖劃分結(jié)果如圖5所示。

限于篇幅，僅列出子圖1的網(wǎng)絡(luò)編碼向量，如表3和4所示。圖6顯示了子圖1獲得最大組播容量時源點組播的信息所經(jīng)由的信道。

源點隨機播出的字符為00 10 01 01。

表3 信道的局部編碼

節(jié)點輸出局部向量節(jié)點輸出局部向量

s1y1=0100，01，01，10y4=0011，00

y2=0111，01，00，11y5=0110，10

y3=1000，10，10，1110y1=0101，01，11

y4=1011，00，00，10y2=0100，00，11

y5=0011，01，00，10y3=0101，10，10

1y1=0011，1114y1=0111，01，11，11，01

y2=0100，01y2=1110，00，11，10，10

y3=1011，01y3=1001，10，11，00，01

2y1=1000，01，00y4=0110，00，00，10，11

y2=1100，10，01y5=1100，10，00，11，00

y3=1001，00，11y6=0100，01，01，00，00

5y1=0001，00，01，11y7=0101，10，01，01，01

y2=1101，10，00，1015y1=0111，01，00，00，11

y3=1101，00，10，00y2=1010，11，01，10，10

y4=1111，00，00，01y3=0011，10，10，01，00

6y1=1010，11y4=0110，10，11，11，01

9y1=0010，00y5=0011，11，11，10，10

y2=0011，00y6=1101，01，10，00，10

y3=0110，10