黃 勝，王 琰，劉煥淋，秦 亮

(重慶郵電大學(xué)光纖通信技術(shù)重點實驗室重慶 400065)

0 引言

組播技術(shù)是中間節(jié)點對信息進行復(fù)制與轉(zhuǎn)發(fā)的信息傳遞技術(shù)［1］，與單播相比可極大地節(jié)省帶寬。其中，光層組播通過分光器實現(xiàn)信息復(fù)制，與傳統(tǒng)IP組播相比，避免了光/電/光轉(zhuǎn)換，性能有所提高，且保證服務(wù)質(zhì)量。不過，傳統(tǒng)的光組播需消耗大量波長資源，使帶寬資源緊張，網(wǎng)絡(luò)傳輸質(zhì)量下降［2］。2000年，Ahlswede等［3］首次提出了網(wǎng)絡(luò)編碼的概念，指出網(wǎng)絡(luò)編碼可有效減少鏈路使用波長數(shù)，提高網(wǎng)絡(luò)吞吐量。2003年，Li等［4］提出了單源組播網(wǎng)絡(luò)中具體的線性網(wǎng)絡(luò)編碼實現(xiàn)方式。從此，網(wǎng)絡(luò)編碼不再只停留在理論層面。

網(wǎng)絡(luò)編碼在光層組播中的應(yīng)用需解決2個問題:①組播路由的確定，即編碼子圖［5］的構(gòu)造;②編碼方案的選取。光組播網(wǎng)絡(luò)可分為單源［5－6］和多源［7］，其中，在單源光組播網(wǎng)絡(luò)中，編碼子圖和編碼方案的研究已比較成熟。多源光組播由于在生活中應(yīng)用廣泛(如多方視頻會議等)一直受到研究者們關(guān)注，但相關(guān)的研究成果并不顯著。多源組播網(wǎng)絡(luò)路由問題的研究，即編碼子圖的構(gòu)建，主要可分為2種:① 建立有源樹［8］，即為每個源建立一棵組播樹;② 在網(wǎng)絡(luò)中建立共享樹［9－14］，即尋找核心節(jié)點，以核心節(jié)點為根建立組播樹。考慮到有源樹占用較多網(wǎng)絡(luò)資源且不一定能保證服務(wù)質(zhì)量，現(xiàn)多采用建立共享樹的方式來解決路由問題。而現(xiàn)有多源光組播中的編碼方案仍存在或多或少的缺點，導(dǎo)致多源編碼路由方法研究成果更少:如文獻［7］根據(jù)源節(jié)點將多源網(wǎng)絡(luò)劃分為多個子圖，從而把多源網(wǎng)絡(luò)轉(zhuǎn)換為單源，然后，運用線性網(wǎng)絡(luò)編碼，提高網(wǎng)絡(luò)吞吐量。該算法不適用于大多數(shù)鏈路容量不支持劃分為多個子圖的網(wǎng)絡(luò)，但確實解決了多源編碼問題。根據(jù)上述2個方面的分析，本文選取核心節(jié)點將多源網(wǎng)絡(luò)轉(zhuǎn)換為單源，采用單源組播中的隨機線性網(wǎng)絡(luò)編碼［15］方案，建立共享樹來研究多源光組播中路由問題。

為解決基于網(wǎng)絡(luò)編碼的多源光組播路由問題，文獻［10］提出一種基于分布式網(wǎng)絡(luò)編碼的共享樹構(gòu)建方法，根據(jù)源節(jié)點選取核心節(jié)點，并直接選擇到各目的節(jié)點的2條通路構(gòu)成共享樹，均衡網(wǎng)絡(luò)負(fù)載，減少波長消耗。但該算法會因目的節(jié)點數(shù)目增加而消耗大量鏈路與波長資源來傳輸編碼信息保證解碼。文獻［11－12］均根據(jù)源節(jié)點選取核心節(jié)點，并設(shè)置該節(jié)點為編碼節(jié)點，構(gòu)建約簡網(wǎng)絡(luò)，以核心節(jié)點為根構(gòu)造共享樹，不過算法仿真拓?fù)湓垂?jié)點固定為2，只能通過增加源節(jié)點組播率來增加網(wǎng)絡(luò)傳輸數(shù)據(jù)量，算法適用范圍再次縮小，且該共享樹構(gòu)造方法同樣受目的節(jié)點數(shù)目影響。文獻［10－12］中都是在核心節(jié)點與每個目的節(jié)點之間尋找2條可分離路徑構(gòu)建共享樹，因此，可能出現(xiàn)目的節(jié)點只接收到部分源節(jié)點數(shù)據(jù)的現(xiàn)象，或為接收到全部數(shù)據(jù)，犧牲編碼子圖中的波長資源，為解決該問題，本文參考了文獻［6］中基于最大流思想構(gòu)建編碼子圖的思想，即為最大流h尋找h條鏈路分離路徑(路徑間沒有鏈路重合)，來保證實現(xiàn)網(wǎng)絡(luò)最大流。

基于以上分析，本文在每個源節(jié)點需要將數(shù)據(jù)傳輸給所有的目的節(jié)點的特殊多源網(wǎng)絡(luò)［3］，提出一種基于網(wǎng)絡(luò)編碼的多核組播路由算法(multi－core multicast routing algorithm based on network coding，MCMR－NC)，為最大流h尋找h條可分離路徑構(gòu)建共享樹，并為目的節(jié)點尋找多個核心節(jié)點，這些核心節(jié)點負(fù)責(zé)解碼并將解碼信息傳輸給一定范圍內(nèi)的目的節(jié)點。與上述算法相比，本算法能最大限度減少目的節(jié)點數(shù)目對編碼子圖的影響，簡化目的節(jié)點加入過程，減少鏈路、波長消耗。

1 基于網(wǎng)絡(luò)編碼的多源組播路由

因為多源光組播網(wǎng)絡(luò)中編碼方案的構(gòu)造還不夠成熟，所以，一般將多源光組播網(wǎng)絡(luò)通過選取核心節(jié)點或劃分子圖等方式轉(zhuǎn)換為相應(yīng)的單源網(wǎng)絡(luò)。將網(wǎng)絡(luò)根據(jù)源節(jié)點劃分子圖相當(dāng)于構(gòu)建有源樹，該方法占用較多網(wǎng)絡(luò)資源，只適用于源節(jié)點很少的情況下解決路由問題。選取核心節(jié)點將多源網(wǎng)絡(luò)轉(zhuǎn)換為單源，相當(dāng)于在以核心節(jié)點為源節(jié)點的單源網(wǎng)絡(luò)中解決路由問題。該方法中多個源節(jié)點發(fā)送的數(shù)據(jù)可共享鏈路和波長資源，更為合理。

基于網(wǎng)絡(luò)編碼的組播路由問題基本相當(dāng)于選擇傳輸編碼數(shù)據(jù)的通路，構(gòu)建編碼子圖問題。

多源組播光網(wǎng)絡(luò)轉(zhuǎn)換為單源，運用隨機線性網(wǎng)絡(luò)編碼進行數(shù)據(jù)傳輸?shù)那闆r如圖1所示。節(jié)點D有2條輸入鏈路1條輸出鏈路，為編碼節(jié)點。圖1a中，源節(jié)點發(fā)送數(shù)據(jù)總數(shù)為2，需2條鏈路分離路徑使解碼節(jié)點收到的數(shù)據(jù)分別為a，a⊕b和b，a⊕b，成功解碼出a，b。將圖1a推廣到一般情況。

圖1 組播網(wǎng)絡(luò)編碼示意圖Fig.1 Network coding in multicast network

用有向賦權(quán)圖G(V，E，W)表示多源組播網(wǎng)絡(luò)，V為節(jié)點集;E為鏈路集;W為邊權(quán)重集合，代表鏈路長短，稱為鏈路代價;源節(jié)點集S={S1，S2，…，S|S|};目的節(jié)點集 D={D1，D2，…，D|D|};將網(wǎng)絡(luò)中源節(jié)點和目的節(jié)點之外的節(jié)點稱為中間節(jié)點，用集合M表示;網(wǎng)絡(luò)中源節(jié)點組播率為1。

將源節(jié)點發(fā)送的數(shù)據(jù)用 k=［k1，k2，…，k|S|］表示;解碼節(jié)點接收到的數(shù)據(jù)用 b=［b1，b2，…，b|S|］表示。由于網(wǎng)絡(luò)采用隨機線性網(wǎng)絡(luò)編碼，則編碼子圖中傳輸?shù)臄?shù)據(jù)均為源節(jié)點輸出向量k中各元素的線性組合:bi=ci1k1+ci2k2+ … +ci|S|k|S|，i=1，2，…，|S|。解碼節(jié)點接收到的信息可表示為

通過方程k=(C-1b)T可譯出原始數(shù)據(jù)。由該方程可知，為保證C矩陣可逆，C應(yīng)為滿秩，此時需要傳輸?shù)膢S|個信息線性獨立。

若想解碼出原始數(shù)據(jù)，解碼節(jié)點需接收到|S|個線性獨立的編碼信息。此時，需要|S|條通路傳輸這些編碼信息，即組播率為1的多源組播路由中若要保證解碼，必須有|S|條通路連接源節(jié)點與解碼節(jié)點。該條件是網(wǎng)絡(luò)編碼光組播路由的前提。

文獻［10－12］中均使用2條通路傳輸編碼信息，一定程度上減少了編碼子圖大小，但當(dāng)源節(jié)點發(fā)送信息增加，算法只能通過增大固定通路上的波長消耗來增加傳輸編碼信息通路數(shù)，不利于網(wǎng)絡(luò)總數(shù)據(jù)傳輸量增加。圖1中，當(dāng)源節(jié)點傳輸數(shù)據(jù)由2增加到4時，共享樹(編碼子圖)上鏈路平均波長使用量增加1倍。文獻［5］中引入鏈路共享度定義，增加編碼子圖中鏈路共用次數(shù)，減少編碼子圖。

以上算法均選取核心節(jié)點將網(wǎng)絡(luò)轉(zhuǎn)換為單源，并在保證解碼的前提下，盡可能減小編碼子圖，優(yōu)化網(wǎng)絡(luò)鏈路代價和波長資源。但解碼節(jié)點均為目的節(jié)點，使目的節(jié)點的增加對編碼子圖影響很大，解碼所需編碼信息傳輸消耗的波長資源和鏈路代價隨之明顯增加。

基于以上分析，本文提出一種尋找多個核心節(jié)點的網(wǎng)絡(luò)組播共享樹構(gòu)建方法，首先，算法通過為源節(jié)點尋找單核點將網(wǎng)絡(luò)轉(zhuǎn)換為單源，然后，將解碼設(shè)置到為目的節(jié)點選取的多個核心節(jié)點上，減少目的節(jié)點變化對編碼子圖大小的影響。通過用|S|條鏈路分離路徑構(gòu)建編碼子圖，使編碼子圖上波長消耗一直為1，增大網(wǎng)絡(luò)總的數(shù)據(jù)傳輸量。

2 基于網(wǎng)絡(luò)編碼的多核組播路由算法

根據(jù)多源光網(wǎng)絡(luò)組播路由問題的分析，可知解決組播路由問題需要:①有|S|條通路傳輸線性獨立編碼信息;②減少編碼子圖鏈路代價和波長消耗。

針對條件①，算法根據(jù)源節(jié)點選取一個核心節(jié)點將多源網(wǎng)絡(luò)轉(zhuǎn)變?yōu)閱卧?，以該?jié)點為根在各解碼節(jié)點間搜索|S|條鏈路分離路徑，建立一棵主共享樹(編碼子圖)，以保證編碼子圖波長消耗盡可能小。針對條件②，將根據(jù)目的節(jié)點選取的核心節(jié)點集設(shè)為解碼節(jié)點，并建立傳統(tǒng)共享樹(子共享樹)，將解碼信息傳輸?shù)侥康墓?jié)點，通過減少解碼節(jié)點數(shù)來減少需要尋找的路徑簇數(shù)，使總的尋找通路數(shù)減少;引入鏈路共享度［5］概念，使不同路徑簇間鏈路盡可能的共用，鏈路共用數(shù)目增加，消耗的鏈路總數(shù)減少。

為方便描述，我們將數(shù)據(jù)傳輸路徑分成3個部分:①從源節(jié)點到主共享樹根節(jié)點稱為源區(qū)域;②主共享樹所占區(qū)域稱為核心區(qū)域;③子共享樹的集合稱為目的區(qū)域。其中，核心區(qū)域入節(jié)點，即主共享樹的根節(jié)點我們稱為in-core節(jié)點。子共享樹根節(jié)點，也是核心區(qū)域出節(jié)點，稱為out-core節(jié)點。

基于網(wǎng)絡(luò)編碼的多核組播路由算法大概步驟如下:當(dāng)組播請求到達，首先，根據(jù)網(wǎng)絡(luò)拓?fù)銰，選取incore與out-core set構(gòu)造主共享樹;然后，根據(jù)選定的out-core set和網(wǎng)絡(luò)拓?fù)銰中目的節(jié)點構(gòu)建子共享樹。

2.1 主共享樹構(gòu)建方法

主共享樹(算法中的編碼子圖)以in-core為根，尋找該節(jié)點到每個out-core間的多條鏈路分離路徑。主共享樹鏈路負(fù)載一直為1，有大量剩余波長資源可用于傳輸源節(jié)點發(fā)送的其他數(shù)據(jù)或其他源節(jié)點發(fā)送的數(shù)據(jù)。為發(fā)揮網(wǎng)絡(luò)編碼優(yōu)勢，減小目的區(qū)域傳統(tǒng)共享樹的波長資源消耗，設(shè)置鏈路代價限制Δ，out-core節(jié)點只能在該限制范圍內(nèi)連接目的節(jié)點，使out-core盡可能地靠近目的節(jié)點。

主共享樹具體構(gòu)建步驟如下。

步驟1 按照組播請求，根據(jù)源節(jié)點確定incore，使所有源節(jié)點到該核心節(jié)點距離之和最小。

①判斷中間節(jié)點的出度。選擇出度大于等于|S|的中間節(jié)點作為in-core的候選集，即:

③若多個候選節(jié)點代價和相同，選擇使用總鏈路跳數(shù)最少的節(jié)點作為in-core。

步驟2 根據(jù)確定的in-core節(jié)點，按照以下方法確定out-core節(jié)點。設(shè)out-core節(jié)點集中共有i個節(jié)點，i∈［1，|D|)。具體操作如下。

①判斷中間節(jié)點m的入度。根據(jù)分析，候選out-core入度至少為|S|:out-core_candidate set1={min_degree≥|S|}，m ∈M

② 判斷in-core與out-core_candidate set中各節(jié)點之間的最大流，保證2點之間能夠找到|S|條鏈路分離路徑:

③ 用矩陣法［14］驗證候選out-core與目的節(jié)點之間的覆蓋關(guān)系，得到最少out-core節(jié)點，即為最終確定的out-core集。

out-core與目的節(jié)點之間的關(guān)系可以看作一種集合覆蓋問題。矩陣法是文獻［14］提出的一種基于矩陣解決集合覆蓋問題的啟發(fā)式算法，操作較為簡單。矩陣法大體思想在本算法的體現(xiàn)是設(shè)置參數(shù)Δ，只有out-core候選節(jié)點與每個目的節(jié)點之間的最短距離在Δ以內(nèi)時，out-core候選節(jié)點與目的節(jié)點相連。建立一個大小為|D|×|out-core_candidate set|的覆蓋矩陣Mv，矩陣中數(shù)值表示out-core與目的節(jié)點D之間的連接關(guān)系。每個out-core對應(yīng)一列。按照以下對應(yīng)關(guān)系建立Mv:

優(yōu)先選擇連接目的節(jié)點最多的out-core候選節(jié)點(“1”最多的列)加入out-core set中，刪去該列以及該列中“1”對應(yīng)的行，使目的節(jié)點不重復(fù)連接到outcore上。重復(fù)上述操作，直到Mv為空集。當(dāng)有outcore候選節(jié)點連接目的節(jié)點數(shù)目相同，分別對其進行驗證，選擇含節(jié)點數(shù)最小的集作為最終選定的out-core。

步驟3 以in-core為根，尋找到out-core set中每個節(jié)點的i組路徑簇，每個路徑簇包含|S|條鏈路分離路徑。

①用Dijkstra算法在網(wǎng)絡(luò)中搜索in-core和outcorei之間的最短路徑，將其加入out-corei對應(yīng)的第i個路徑簇中，設(shè)置該路徑中鏈路代價為無窮大，即不再連通;

② 重復(fù)①，直到第i個路徑簇中有|S|條路徑;

③將路徑簇中鏈路的代價設(shè)為0.1，以提高核心區(qū)域鏈路共享度，i=i+1，轉(zhuǎn)向1。

步驟4 將步驟3確定的i組路徑簇加入主共享樹，主共享樹構(gòu)造完成。

源節(jié)點通過最短路徑與選定的in-core相連。圖2，圖3分別為網(wǎng)絡(luò)編碼和網(wǎng)絡(luò)拓?fù)涫疽鈭D。

圖2 網(wǎng)絡(luò)編碼示意圖Fig.2 Network coding diagram

圖3 網(wǎng)絡(luò)拓?fù)涫疽鈭DFig.3 Network topology diagram

考慮到圖2中網(wǎng)絡(luò)拓?fù)涑霈F(xiàn)的可能性，若core沒有編碼能力，鏈路core-D上無論傳輸a，b或c，解碼節(jié)點D2和D3總不能同時接收到源節(jié)點發(fā)送的信息。因此，算法中in-core節(jié)點一定具有編碼能力。

步驟3得到的路徑簇中路徑分別為2點之間的最短路徑、次短路徑…。但在圖3中，A和D之間的最大流為2，若鏈路代價如圖3所示，那么尋找到的最短路徑為A-B-F-G-D，將之設(shè)為不連通后，A和D之間將不存在路徑相連。針對這種情況，可找出A和D間的所有路徑，進行對比組合，最后，得到2條鏈路分離路徑，但不保證為最短或次短路徑。

2.2 子共享樹構(gòu)建方法

算法中的子共享樹定義為以out-core為根，尋找到目的節(jié)點的最短路徑加入樹中建立的傳統(tǒng)共享樹。子共享樹通過減少根節(jié)點與目的節(jié)點之間的路徑數(shù)來減少目的節(jié)點增加對算法鏈路代價的影響。當(dāng)新加入的目的節(jié)點與核心節(jié)點距離在限制范圍Δ內(nèi)時，只需增加一條最短路徑就能將源節(jié)點數(shù)據(jù)傳輸?shù)侥康墓?jié)點。

子共享樹構(gòu)建具體步驟如下。

步驟1 根據(jù)組播請求、網(wǎng)絡(luò)拓?fù)銰和out-core節(jié)點集，用Dijkstra算法搜索out-corei與每個目的節(jié)點間的最短路徑，存入P1中。

步驟2 將最短路徑集P1中路徑代價不大于Δ的路徑選出，存入P2中。

步驟3 每個目的節(jié)點對應(yīng)P2中的一條路徑，若多個out-core節(jié)點連接到同一目的節(jié)點上，選擇有最小鏈路代價的路徑;當(dāng)鏈路代價相同時，選擇跳數(shù)較少的路徑。因為路徑中鏈路代價越小、跳數(shù)越少，意味著子共享樹消耗的鏈路代價和波長資源越少。

至此，算法完成。圖4為算法可能得到的數(shù)據(jù)傳輸圖及波長消耗情況。圖4中，源節(jié)點發(fā)送數(shù)據(jù)分別為a，b，c，在in-core和out-core間尋找3條鏈路分離路徑。out-core不需在in-core處編碼就能解碼成功，因此，本例中in-core節(jié)點不編碼，但一直有編碼能力。編碼子圖中節(jié)點D為編碼節(jié)點。

圖4 多核點共享樹示意圖Fig.4 Multi－core shared－tree diagram

3 仿真與性能分析

為驗證本文提出的MCMR－NC算法性能，下面將其與傳統(tǒng)共享樹(shared tree algorithm，ST)算法、基于網(wǎng)絡(luò)編碼的共享樹算法［11］(shared tree based on network coding algorithm，ST－NC)進行對比。

3.1 仿真環(huán)境與評價指標(biāo)

本文采用matlab7.0來構(gòu)建仿真平臺，每次組播請求變換一個隨機拓?fù)洌?6］，將隨機拓?fù)涔?jié)點的平均度數(shù)設(shè)置為4，拓?fù)渲懈鶕?jù)鏈路長度生成的權(quán)重值設(shè)為該條鏈路的鏈路代價。選擇拓?fù)渲兄挥谐龆葲]有入度的節(jié)點作為源節(jié)點，只有入度沒有出度的節(jié)點作為目的節(jié)點。網(wǎng)絡(luò)中節(jié)點均具有分光能力，每條鏈路中波長數(shù)目能滿足組播請求。

本文采用以下3個參數(shù)來驗證MCMR－NC算法的性能。

1 )鏈路代價。鏈路代價是網(wǎng)絡(luò)中數(shù)據(jù)傳輸使用的鏈路代價總和。在不考慮波長消耗的前提下鏈路代價越小越好。網(wǎng)絡(luò)編碼的提出，使研究目標(biāo)從用最短的鏈路傳輸有限數(shù)據(jù)變化為充分利用鏈路容量，使鏈路能夠盡可能多地傳輸不同的數(shù)據(jù)。

2 )波長資源消耗［11］。即網(wǎng)絡(luò)中為一個請求所消耗的所有波長總和。相同組播請求下，波長消耗得越少越好。

3.2 仿真結(jié)果與分析

算法主要驗證目的節(jié)點數(shù)目變化對網(wǎng)絡(luò)性能的影響，所以，固定網(wǎng)絡(luò)節(jié)點數(shù)目為100，源節(jié)點數(shù)目為4，變化目的節(jié)點數(shù)目并用鏈路代價、波長資源消耗和鏈路平均負(fù)荷來分析3種算法的性能。

1 )鏈路代價。目的節(jié)點與鏈路代價關(guān)系如圖5所示。

圖5 目的節(jié)點與鏈路代價關(guān)系圖Fig.5 Number of destination node VS link cost

圖5中，2種對比算法的鏈路代價隨目的節(jié)點增加明顯增加，MCMR－NC算法的鏈路代價在目的節(jié)點大于20后增長速度變得緩慢。因為在網(wǎng)絡(luò)規(guī)模一定的情況下，目的節(jié)點越大，相對分布越緊密，已確定的out-core能滿足覆蓋需求，不需要增加，使得編碼子圖大小不變;此時，目的節(jié)點數(shù)目增加，只需消耗out-core節(jié)點到目的節(jié)點的一條最短路徑，因此，鏈路代價變化很小。

2 )波長資源消耗。目的節(jié)點與波長消耗關(guān)系如圖6所示。

圖6 目的節(jié)點與波長消耗關(guān)系圖Fig.6 Number of destination nodes VS wavelength resource consumption

圖6中，隨目的節(jié)點增加，3種算法波長消耗均增大，MCMR－NC算法的波長消耗始終小于對比算法，且隨目的節(jié)點數(shù)目增加，與2種對比算法之間的差值逐漸增大。這是因為若增加的目的節(jié)點在outcore節(jié)點集覆蓋范圍內(nèi)，那么，MCMR－NC算法編碼子圖中波長消耗不變，只需消耗少量波長資源將解碼信息發(fā)送給目的節(jié)點。而基于網(wǎng)絡(luò)編碼的共享樹算法和傳統(tǒng)共享樹算法需為每個目的節(jié)點重新尋找分離路徑或最短路徑，消耗的波長較多。

3 )鏈路平均負(fù)荷。目的節(jié)點與鏈路平均負(fù)荷關(guān)系如圖7所示。

圖7中，傳統(tǒng)共享樹平均鏈路負(fù)荷遠(yuǎn)高于其他2種算法，在3.6～3.8區(qū)間內(nèi)變化。ST－NC算法由于源節(jié)點固定為4，編碼子圖中每條鏈路需消耗2個波長，鏈路平均負(fù)荷近似為 2;MCMR－NC算法中核心區(qū)域每條鏈路消耗一個波長，目的區(qū)域每條鏈路消耗4個波長，因此，平均鏈路負(fù)荷受各區(qū)域鏈路數(shù)目在總的鏈路數(shù)目中所占比重影響，與鏈路負(fù)荷性能較好且比較穩(wěn)定的ST－NC算法總體相差不大:2種算法差值最大是目的節(jié)點為30時，相差0. 19;當(dāng)目的節(jié)點為25時，差值最小為0.01。

圖7 目的節(jié)點與鏈路平均負(fù)荷關(guān)系圖Fig.7 Number of destinations nodes VS the average link load

由仿真結(jié)果可知，MCMR－NC算法通過減少編碼子圖鏈路代價和波長消耗，限制目的區(qū)域共享樹大小，使得在目的節(jié)點較多的網(wǎng)絡(luò)中，波長消耗小于2種對比算法，鏈路代價性能有所改善。

4 結(jié)束語

本文提出一種基于網(wǎng)絡(luò)編碼的多核點組播路由算法，將傳統(tǒng)共享樹和基于網(wǎng)絡(luò)編碼的共享樹相結(jié)合，通過為目的節(jié)點選取多個核心節(jié)點減少目的節(jié)點變化對編碼子圖的影響。該算法適合目的節(jié)點數(shù)目較多，且分布相對密集的網(wǎng)絡(luò)。算法的鏈路代價、波長資源消耗性能均有改善，鏈路平均負(fù)荷雖受網(wǎng)絡(luò)拓?fù)溆绊?，但總趨勢與鏈路平均負(fù)載性能較好的網(wǎng)絡(luò)編碼共享樹算法相近。

［1］劉煥淋，謝蕓徽，李禎，等.基于免疫算法的光組播最少網(wǎng)絡(luò)編碼鏈路研究［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2011，23(4):384－388.

LIU Huanlin，XIE Yunhui，LI Zhen，et al.Study on minimizing network coding links based on immune algorithm for optical multicast network ［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2011，23(4):384－388.

［2］劉煥淋，方強，王楊楊，等.WDM網(wǎng)狀網(wǎng)絡(luò)中一種動態(tài)多播自適應(yīng)業(yè)務(wù)疏導(dǎo)算法［J］.光電子·激光，2013，24(1):69－74.

LIU Huanlin，F(xiàn)ANG Qiang，WANG Yangyang，et al.An adaptive algorithm for dynamicmulticast traffic grooming in WDM mesh networks［J］.Journal of Optoelectronics·Laser，2013，24(1):69－74.

［3］AHLSWEDE R.，CAIN.，LI S.Y R.，et al.Network information flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204－1216.

［4］LI S.Y R，YEUNG R W，CAI Ning.Linear network coding［J］.IEEE Transactions on Information Theory，2003，49(2):371－381.

［5］羅莉，覃團發(fā)，羅建中，等.基于鏈路共享度的網(wǎng)絡(luò)編碼多播路由算法［J］.電訊技術(shù)，2011，51(3):79－83.

LUO Li，QIN Tuanfa，LUO Jianzhong，et al.A Routing Algorithm for Network Coding Multicast Based on Shareable Links［J］.Telecommunication Engineering，2011，51(3):79－83.

［6］TAO Shaoguo，QIAO Wenbo，YANG Zongkai，et al.Routing Algorithm of Network Coding on Multicast［C］//International Conference on Computational Intelligence and Security Workshops.Harbin，Heilongjiang，China:IEEE Press，2007:354－357.

［7］PU Baoxing，YANG Luming，WANG Weiping，et al.Linear Network Coding Construction forMulti－source Multicast Network［C］//First InternationalWorkshop on Education Technology and Computer Science.Wuhan，China:IEEE Press，2009(3):114－118.

［8］CHEN YuhRong，RADHAKRISHNAN Sridhar，DHALL Sudarshan，et al.On multi－stream multi－source multicast routing［J］.Computer Networks，2013(57):2916－2930.

［9］SEKINE Y，MIKOSHI T，TAKENAKA T.Shared－Tree selection method for aggregated multicast［C］//2012 18th Asia－Pacific Conference on Communications(APCC).Jeju island，Korea:IEEE Press，2012:760－764.

［10］肖昊明，張敏，陽小龍.一種基于分布式網(wǎng)絡(luò)編碼的共享樹光組播算法［J］.計算機應(yīng)用研究，2009，26(12):4719－4721.

XIAO Haoming，ZHANG Min，YANG Xiaolong.Shared tree opticalmulticast algorithm based on distributing network coding ［J］.Application Research of Computers，2009，26(12):4719－4721.

［11］王汝言，劉成耀，吳大鵬.一種基于網(wǎng)絡(luò)編碼的共享樹組播算法［J］.半導(dǎo)體光電，2010，31(5):767－770 ，786.

WANG Ruyan，LIU Chengyao，WU Dapeng.A Sharedtree Multicast Algorithm Based on Network Coding［J］.Semiconductor Optoelectronics，2010，31(5):767－770，786.

［12］LU Zhengqiu，HEGuangjun.Research ofMulticast Routing Protocol in Wireless Sensor Networks Based On Network Coding［C］//2012 7th International Conference on Computer Science ＆ Education(ICCSE).Melbourne，Australia:IEEE Press，2012:354－356.

［13］HIROTA Y，HONDA H，TODE H，et al.Multicast Design Method Using Multiple Shared－Trees in Optical WDM Networks［J］.IEICE TRANSACTIONSon Communications，2012，95(2):370－381.

［14］張琨，王珩，劉鳳玉.一種時延約束的多共享組播樹構(gòu)造算法［J］.南京理工大學(xué)學(xué)報，2006，30(2):127－131，141.

ZHANG Kun，WANG Heng，LIU Fengyu.Delay－constrained Multiple Shared Multicast Trees Construction Algorithm［J］.Journal of Nanjing University of Science and Technology，2006，30(2):127－131，141.

［15］HO T，MEDARD M，KOETTER R，et al.A Random Linear Network Coding Approach to Multicast［J］.Information Theory，IEEE Transactions on，2006，52(10):4413－4430.

［16］SALAMA H F，REEVESD S，VINIOTISY.Evaluation ofmulticast routing algorithms for real－time communication on high－speed networks［J］.IEEE Journal on Selected Areas in Communications，1997，15(3):332－345.

(編輯:劉 勇)