集中式網絡編碼組播路由算法*

徐光憲，賴俊寧

遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

集中式網絡編碼組播路由算法*

徐光憲，賴俊寧+

遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

Abstract:From magnifying multicast capacity and reducing multicast delay,this paper proposes a centralized network coding cycle augmented multicast routing algorithm(NCCA)to further improve the transmission rate of multicast communication.Firstly,each node traverses the link state packets to get the topology information of the network by breadth first search(BFS)algorithm.Then,each sink node augments routing set by using Dijkstra algorithm and selects the optimal routing set.Finally,the routing sets of all sink nodes are combined to get the entirety routing of multicast group.The theoretical analysis and simulation results show that the NCCA multicast routing algorithm can further improve the transmission rate of multicast communication in a stable network.

Key words:network coding;multicast capacity;multicast delay;multicast transmission rate

從提高組播容量和降低組播延遲入手，提出了一種集中式網絡編碼循環增廣組播路由算法（centralized network coding cycle augmented multicast routing algorithm，NCCA），從而進一步提高了組播通信的傳輸速率。首先各節點通過廣度優先搜索（breadth first search，BFS）算法遍歷鏈路狀態分組獲得整個網絡的拓撲信息，以Dijkstra算法為基礎增廣每個信宿節點的路由集，然后選出最優路由集，最后將所有信宿節點的路由集進行組合，得到組播組的整體路由。通過對算法進行理論分析及仿真實驗，證明了NCCA組播路由算法在較穩定的網絡上能進一步提高組播通信的傳輸速率。

網絡編碼；組播容量；組播延遲；組播傳輸速率

1 引言

傳統網絡的信息傳輸大部分是基于存儲和轉發的路由機制，Ahlswede等人[1]于2000年首次提出了網絡編碼的基本原理，它允許中間節點對輸入信息進行編碼，在提高網絡吞吐量，改善負載均衡，減小傳輸延遲，增強網絡魯棒性和提高信息安全性等方面具有重要意義。近年來網絡編碼在優化與安全等領域得到了深入研究，對組播路由的研究也逐漸成為網絡編碼的新熱點。

早期的組播路由算法有KMB組播路由算法、最小代價啟發式組播路由算法（minimum path cost heuristic multicast algorithm，MPH）和輕量自適應組播路由算法（lightweight adaptive multicast algorithm，LAM）等[2]。KMB和MPH為集中式的Steiner最小樹啟發式算法，在此基礎上衍生出的新型組播路由算法有基于加權節點的最小代價路徑啟發式算法（node weight based minimum cost path heuristic algorithm，NWMPH）[3]和多跳自組織按需距離矢量組播路由算法（multicast ad-hoc on-demand distance vector routing algorithm，MAODV）[4]等。NWMPH算法在MPH算法基礎上通過加權公式對所有非正則點進行權值計算，從而構造組播樹，是一種基于加權節點的表驅動啟發式算法。MAODV是分布式AODV按需路由協議在組播方式下的擴展，是適用于自組網的分布式距離向量多播路由算法，可以實現快速移動節點間的通信。文獻[5]首次應用網絡編碼思想提出了一種基于最大流的網絡編碼組播路由算法（max-flow based network coding multicast routing algorithm，NCMA），各信宿節點進行一次增廣，通過組合得到組播組的整體路由。

本文從提高組播容量和降低組播延遲入手，提出了一種集中式網絡編碼循環增廣組播路由算法（centralized network coding cycle augmented multicast routing algorithm，NCCA），從而進一步提高了組播通信的傳輸速率。NCCA是一種集中式組播路由算法，首先每個路由節點都需要通過周期性發布動態的鏈路狀態分組獲得網絡信息，然后維護整個網絡的拓撲信息，最后根據網絡拓撲信息獨立地構造多播樹。針對NCMA一次增廣不一定能得到網絡的最大組播容量和最小組播延遲的問題，本文運用NCCA選出每個信宿的最優路由集，將所有信宿的路由集進行組合，得到組播組的整體路由。仿真實驗表明，在中等網絡規模下，應用NCCA組播路由算法在較穩定的網絡上能進一步提高組播通信的傳輸速率。

2 相關知識

2.1 廣度優先搜索算法遍歷鏈路狀態分組

廣度優先搜索（breadth first search，BFS）算法從各節點訪問所有與之相鄰的節點，訪問完這些節點后，再訪問與這些節點相鄰的未被訪問的節點，重復整個過程直到所有的節點都被訪問，通過序列號控制鏈路狀態分組的擴散過程[6]。發布的鏈路狀態分組包括一個發送方標識、序列號、年齡以及一個包含距離的鄰居列表。每當鏈路狀態發生改變時重新創建并發布分組，從而構造實時的網絡拓撲。

2.2 Dijkstra算法尋路

NCCA以Dijkstra算法尋路，它的基本思路是先建立一個網絡圖，圖中的每個節點代表一臺路由器，每條弧代表一條通信鏈路。每一個節點都有一個兩項的標號，標號第一項是最短路徑上對應的前趨節點，第二項是這個路徑的長度，每個標號分為暫時的或永久的，初始時所有標號都是暫時的。初始時所有的節點都標記為無限遠，隨著算法的不斷進行，當確定了一個標號為從原點到該節點的最短路徑時，標號變成永久的并且不再改變。此時信宿節點到組播源范圍內的節點都會生成自己的標號，每個標號都對應著各自的路由選擇，標記為永久節點后可通過反向追蹤確定最短路徑[2]。

其中路徑長度可以憑借跳數、傳輸延遲、隊列長度和帶寬等衡量，本文用延遲ts作為路徑長度的度量。為了滿足不同服務類型[7]信號的延遲要求，通常設置一個組播延遲上界sd，延遲過大的路由被舍棄，從而避免因傳輸延遲而造成的信號質量問題，但是延遲上界往往使網絡達不到理論上的最大組播容量。

2.3 網絡編碼

設d為編碼節點的輸入鏈路，e為輸出鏈路，局部編碼向量m(e)={mde∈GF(2m):d∈In[tail(e)]}，輸入的信息向量為y(d)，輸出的編碼信息向量為y(e)，那么生成y(e)的公式為：

設組播率為hs，組播源信息向量組成一個L行hs列原始信息矩陣A，全局編碼向量組成hs行hs列的編碼矩陣B，信宿Ti接收到的L行hs列的編碼信息矩陣為C。根據網絡編碼進行的矩陣變換A×B=C，僅當編碼矩陣B滿秩時，每個信宿節點Ti可以計算編碼矩陣B的逆矩陣B-1并存儲在內存中，根據A=C×B-1解出原始矩陣A。其中B由全局編碼向量g(dTij)組成，而C由編碼信息向量y(dTij)組成，dTij為信宿Ti的第j條輸入鏈路，y(dTij)與g(dTij)的代數關系為：

2.4 NCCA多播樹

網絡編碼組播路由必須保證有hs個分離路徑輸入每個信宿節點，并且每條分離路徑的全局編碼向量線性無關。NCCA所確定的路由集實質上都構成了一棵以每個信源節點為根的多播樹，連接了多播組中所有信宿節點，它本質上同Steiner最小樹是一致的，只不過算法通過調整運算策略充分利用了帶寬資源。在多個組播源的網絡中，有些Steiner節點可能屬于不同的組播樹，選擇其中入度大于出度的節點為編碼節點，然后分配局部編碼向量，最后生成滿秩的編碼矩陣。文獻[8]給出了一種網絡編碼小生境最小代價優化（network coding simple-genetic minimum-cost，NCSM）協議。

3 NCCA組播路由算法

3.1 NCCA組播路由算法原理

組播傳輸速率v表示單位時間內信宿接收到信息的大小，組播容量c表示網絡中組播率hs的上限，組播容量c越大，傳輸速率v也越高。組播延遲d指的是一次組播中信息從發出到接收所經歷的時間，組播延遲d越小，傳輸速率v就越高[9]。因此可從提高組播容量和降低組播延遲入手，進一步提高組播通信的傳輸速率。

經典的組播蝴蝶網絡如圖1所示。假設每條鏈路帶寬為1單位，傳輸分組大小為1單位，s1和s2分別發送信息分組a、b至t1和t2，根據最大流最小割定理可知最大組播容量為2[1]。

Fig.1 Typical butterfly network圖1 典型的蝴蝶網絡

傳統組播路由算法如MAODV和NWMPH，都以每個信源為根構造Steiner最小樹來實現組播。以s1為根的樹可能為s1—n1—n2—(t1,t2)，以s2為根的樹可能為s2—n1—n2—(t1,t2)。鏈路n1—n2在帶寬受限的情況下，由于節點n1的入度大于出度，信息分組a和b需要在節點n1處排隊，使信宿不能同時接收到分組a和b，而且這種組播策略共占用了8條鏈路（1次s1—n1和s2—n1，2 次n1—n2,n2—t1和n2—t2），不能達到理論上的最大組播容量。

而NCMA與NCCA都以網絡編碼為原理，得到以s1為根的樹可能為s1—n1(t1)—n2—t2，s2為根的樹可能為s2—n1(t2)—n2—t1，信息分組a和b在n1編碼成a+b，信宿t1和t2就能同時接收到a和b了，而且只占用了7條鏈路（1次s1—t1,s2—t2,s1—n1,s2—n1,n1—n2,n2—t1和n2—t2），確實可以達到理論上的最大組播容量2。

在路由方面，NCMA為確定組播組的路由集，應用Dijkstra算法對信宿到所有信源按延遲順序進行尋路，每次尋路獲得到達某個信源的一個新路徑并保存，然后在拓撲圖中去掉這個信源和途經的鏈路，對圖進行下一次尋路，允許分離路徑經過同一節點，直到路徑無法滿足要求則指定為最終路由集并保存，這個過程稱作一次增廣[10]。NCMA只進行了一次增廣，因此NCMA可能無法達到最大組播容量。例如t1增廣分離路徑時，如果路徑t1—n2—n1—s1延遲小于路徑t1—s1，NCMA按順序首選t1—n2—n1—s1會占用信息分組b經過n1—n2的帶寬，最后只能得到路由集s1—n1—n2—t1。而NCCA在每次選路前首先進行路徑等級劃分，在圖1蝴蝶網絡選路時考慮了首選第2路徑t1—s1，再選擇第1路徑t1—n2—n1—s2的情況，增廣出路由集s1—n1(t1)—n2—t2。然后比較得到的路由集，最后選擇了組播容量為2單位的s1—n1(t1)—n2—t2。

3.2 NCCA組播路由算法流程

NCCA組播路由算法的總體設計框圖如圖2所示。定義參數si為由鏈表構造的路徑，ts為路由延遲，S為組播路由集，TS為臨時組播路由集，d為組播延遲，c為組播容量，Td、Tc分別是臨時組播延遲和容量，i為首選路徑的循環參數，n為首選路徑等級，q為循環選路模塊的循環參數，fd為首選路徑延遲，sd為標準延遲上界。

NCCA組播路由算法主程序調用了5個模塊：BFS模塊負責在網絡中遍歷鏈路狀態分組，并且在節點內存中構造圖和優先隊列，目的是為了使每個節點獲得網絡的拓撲信息，在鏈路出現斷路的情況下刪除受影響的路由。模塊需設置初始參數n=1，c=0，d=+∞，S=?。D模塊由Dijkstra算法子模塊和排序子模塊組成。Dijkstra算法子模塊對圖執行一次Dijkstra算法，得到信宿到所有組播源范圍內節點的標號，通過排序子模塊尋找第n路徑，選取當前圖的第n路徑并計算其延遲ts。循環模塊的作用是在首選第n路徑下，以q≤n作為循環終止條件擴充路由集。修訂圖模塊運行在所有鏈路帶寬為1單位，傳輸分組大小為1單位的前提下，它的作用是在一組增廣中，在圖中刪除每次選路的鏈路從而修訂拓撲圖。容量和延遲比較模塊按照先選最大容量再選最小延遲的順序比較出c和d以及所對應的路徑集S。各模塊通過主程序整合在一起，最后將各信宿的最優路由集組成組播組的整體路由。

排序子模塊負責把不同延遲的路由劃分為多個等級，按照路徑延遲從小到大劃分等級，第n等級的稱為第n路徑。在每次執行Dijkstra算法后，信宿節點到組播源范圍內的節點都會生成自己的標號，包括組播源的鄰居節點。等級劃分的規則為選擇第n路徑時，若存在直接到信源節點Si的第n路徑，就選擇這條路徑，不存在時查找一條最遠的第m路徑(m＜n)。最遠的第m路徑是指組播源鄰居節點的標號中延遲項(ts)最大的標號所對應的路徑。沿著這條路徑前溯一個節點，查找這個節點的鄰居，選擇一個第n-m近的鄰居即可找到第n路徑。當前溯的節點沒有第n-m近的鄰居，則依此類推，繼續前溯直到找到第n路徑。根據選擇的第n路徑，保留最下游變更過的節點的標號，然后對變更過的節點逐個向上游重新標號，直到重新標記到組播源為止，根據新標號確定這條第n路徑和它的延遲。每次執行Dijkstra算法后都要進行路徑等級劃分，從而選擇第n路徑。選擇第n路徑是為了按順序循環使算法收斂。

如圖2，NCCA組播路由算法主程序中的D模塊與循環模塊由一個小循環連接構成，小循環憑借參數i自加運行，負責為信宿到信源尋一條路徑si并保存到路由集Ts中，增廣路由集的公式為：

通過排序子模塊計算單個路徑延遲ts，將最大的延遲作為路由集的組播延遲Td，然后修訂拓撲圖。當ts≥d，ts≥sd或無法生成新路徑時跳出小循環，保存路由集的組播容量Tc，進入容量/延遲比較模塊。

初始化圖由兩個參數q和n控制。初始化圖與容量/延遲比較模塊由一個中循環以及一個大循環結構連接構成，中循環憑借參數q運行，q≤n作為其終止條件。每次循環得到一個路由集TS，并把容量和延遲的值賦給Tc和Td，在容量/延遲比較模塊與c和d進行比較，將比較值重新賦給c和d，得到新路由集S=opt[S,TS]，然后初始化圖將參數i和q置1。新路由集S中d和c滿足式（4）和（5）：

Fig.2 NCCAoverall design diagram圖2 NCCA總體設計框圖

大循環憑借參數n運行，n為首選路徑等級，每次循環后n自加，整個算法通過終止條件fd≤d達到收斂，跳出大循環輸出組播容量最大且組播延遲最小的路由集S。

3.3 收斂性以及算法復雜度分析

為了減少運算量，每次尋路后將這條路由延遲ts與sd和d進行比較，如果ts≥sd或ts≥d，則停止這組增廣并跳到下一組。由于逐次比較最優路由方案，組播延遲d會越來越小。而按等級首選第n路徑，首選路徑延遲fd會不斷增大，最后必有d=fd，達到收斂。此后的路由集中fd不可能小于d，即不可能再增廣出更優的路由集，因此把fd≤d作為循環增廣的收斂條件。

用鄰接鏈表表示拓撲圖，用斐波那契堆實現優先隊列，Dijkstra算法的時間復雜度為O(E+nlgn)。NCCA求信宿節點到每個信源節點的最短路徑，則每個信源需調用一次Dijkstra算法，設組播率為hs，算法循環k次達到收斂，則算法的時間復雜度為O(khs(E+lgn))。對于空間復雜度，首先需要空間n保存距離，另需空間n存儲前一個節點以保存路徑，此外還需一個斐波那契堆及其反向指針，而且NCCA算法在每個節點保存hs條最短路徑，每次更新路徑集的代價相當于把hs個長度為4n的表合并在一起，因此NCCA的空間復雜度為O(4nhs)。

4 NCCA路由算法仿真

本文仿真環境為Dell PC機，處理器為Intel?CoreTM-M480 I5 CPU@2.67 GHz，4 GB內存，操作系統為32位Win7系統，安裝并使用了VC++6.0、Cyg-Win、Matlab R2011b和NS2-allinone2.26軟件。

4.1 構建網絡拓撲

GT-ITM是NS2自帶的開源網絡拓撲生成工具，使用GT-ITM建立K均值聚類Waxman隨機拓撲模型（K-means Waxman random network topology model，KRTG），KRTG模型節點和邊分布均勻，避免了重疊或距離過近，能生成度數收斂的連通圖[11]。將n個節點按KRTG模型分布在平面上，生成鏈路，從而構建連通圖的概率分布為：

其中，L為拓撲中所有節點距離的最大值，設a為網絡的邊長，則L=a；|V|為節點數；d(u,v)是節點u和v之間的歐式距離；α、β是取自(0,1]的實數。選擇適當的值能使拓撲更接近真實網絡。概率P(u,v)中，D是節點平均度。在實驗中鏈路延遲調用λ=d(u,v)的泊松分布函數[12]，設置平面為100 km×100 km的正方形區域，坐標最小刻度為1，α=0.15，D=4。

4.2 應用NS2仿真NCCA組播路由算法

NS2是一款開放源代碼的網絡仿真軟件，NS2中網絡協議是可擴展的[13]。為了比較組播算法在有限帶寬下傳輸速率的優劣，且為了方便重新修訂拓撲圖，設置Tcl仿真腳本中鏈路帶寬為1.5 Mb/s，傳輸分組大小為1 Mb的CBR（constant bit rate）流，其中多余帶寬留給傳輸鏈路狀態分組。物理層選用IEEE-802.3u，Mac層協議采用CSMA/CD（carrier sense mul-tiple access with collision detection）實現媒體訪問機制，采用TCP傳輸協議、RED（random early detection）隊列管理協議、網絡編碼優化NCSM協議，接口隊列類型為Queue/DropTail/PriQueue。

本文設計了兩組實驗對組播路由算法MAODV、NWMPH、NCCA和NCMA進行仿真。每個節點通過BFS算法以300 ms為周期發送鏈路狀態分組來實現拓撲的實時更新，理論上每次BFS算法對整個網絡掃描所消耗的時間是由網絡拓撲結構所決定的，和網絡直徑有直接的關系。第一組實驗在節點數50、100、150、200、250、300、350下分別隨機生成30次拓撲模型，運行各算法并在算法執行過程中動態加入相同數量的組播源和信宿，直到達到最大組播容量。第二組實驗在30組200節點的網絡規模中仿真，在鏈路停留時間為 0.05、0.10、0.15、0.20、0.25、0.30、0.35 s的情況下使各算法達到最大組播容量。兩組實驗最終生成了記錄算法執行過程參數的trace跟蹤文件。

4.3 算法性能分析

針對兩組實驗的仿真結果trace文件，編寫awk程序，將分析結果導入Matlab繪制對比折線圖。awk的主要功能是以指定的模式搜索文件的每一行，在符合指定模式的行提取所需參數，直至搜索結束[14]。實驗1提取組播容量c、組播延遲d和收斂時間t，并求平均值，分析比較在不同網絡規模下各算法參數變化情況和性能差異。實驗2提取傳輸速率v并求平均值，分析并比較網絡在不同穩定性下各算法的傳輸速率變化情況和差異。通過NS2對實驗1生成的trace文件進行awk程序分析，得到BFS算法在KRTG模型中網絡規模分別為50、100、150、200、250、300、350時的平均時間消耗分別為76、102、125、144、158、173、186 ms。

實驗1中MAODV、NWMPH、NCCA和NCMA算法運行結果的平均組播容量、平均組播延遲和平均收斂時間對比如圖3、圖4、圖5所示。實驗2中各算法運行結果的組播傳輸速率對比如圖6所示。

Fig.3 Comparison of average multicast capacity for multicast routing algorithms圖3 組播路由算法平均組播容量比較

Fig.4 Comparison of average multicast delay for multicast routing algorithms圖4 組播路由算法平均組播延遲比較

圖3和圖4表明NCCA在組播容量和組播延遲上要好于MAODV、NWMPH和NCMA，這是由于MAODV、NWMPH和NCMA關鍵鏈路的占用以及少量的中心節點頻繁被選為中繼節點，導致路由路徑存在較高的重疊率和較高的組播延遲。其中MAODV和NWMPH還不支持網絡編碼，導致較高的隊列長度，因此組播容量較小。另一方面各算法在兩項指標上有大致相似的變化趨勢，這是因為隨著網絡規模的增加，更多中繼節點使組播路由有更為豐富的選擇。

如圖5所示，NCCA的平均收斂時間大于其他算法，這是因為NCMA和MAODV的時間復雜度都為O(hsn2)，NWMPH的時間復雜度為O(mn2)，而NCCA的時間復雜度為O(khs(E+nlgn))，大于其他算法。隨著網絡規模的增加，NCCA的平均收斂時間大幅增加，而MAODV、NWMPH和NCMA則變化不明顯，這表明網絡規模對NCCA的收斂速度有較大影響。這是由于算法的時間復雜度受循環次數k的影響，對于規模很大的網絡不易收斂。

Fig.5 Comparison of average multicast convergence time for multicast routing algorithms圖5 組播路由算法平均收斂時間比較

Fig.6 Comparison of average multicast transmission rate for multicast routing algorithms圖6 組播路由算法平均傳輸速率比較

如圖6所示，適用于自組網的分布式路由協議MAODV在鏈路停留時間較短時組播傳輸速率最高，說明MAODV適用于變化頻繁的網絡。NCCA在鏈路停留時間較長時有較高的組播傳輸速率，表明NCCA適用于相對穩定的網絡。原因是NCCA的收斂速度較慢，鏈路的頻繁變動會帶來很大的節點開銷，而如果鏈路較穩定，NCCA便能充分利用其優化組播容量和組播延遲的優勢。另一方面隨著鏈路停留時間的增加，NCCA和NCMA的組播傳輸速率大幅增加，而MAODV和NWMPH則變化不明顯，這是因為MAODV和NWMPH中節點無法進行網絡編碼，導致了較重的隊列擁塞。

5 結束語

本文提出的NCCA組播路由算法選擇最大組播容量和最小組播延遲的路由集，從而提高了組播網絡的傳輸速率。但是目前NCCA還存在很多有待改進的地方。首先這種路由算法在網絡拓撲變換頻繁的情況下，傳輸速率會變得很低，這是較高的收斂次數k造成的，未來在循環模塊可采取遺傳算法降低收斂次數，減少不必要情況的查找，從而從整體上降低NCCA的時間復雜度。算法目前只在K均值聚類Waxman隨機拓撲模型中進行了仿真，屬于節點間地位平等的平面式網絡，不能完全準確反映實際的Internet特性，應擴展到BA、GLP或LWTC冪律型網絡模型。此外修訂圖模塊假定鏈路帶寬全部為1單位，沒能反映真實網絡的帶寬情況，還處于簡易的去鏈路模型，修訂圖模塊的細節還有待完善。最后可以將集中式NCCA改為分布式路由算法，并使用MPR（multi-point relay）廣播中繼機制[15]，進一步提升帶寬利用率，減小尋路開銷，提高可擴展性，以適應不同的網絡類型。

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

[2]Chen Xiaohui.Multicast routing algorithms'simulation platform designing[D].Dalian:Dalian University of Technology,2006.

[3]Wang Xiaolong.Algorithm and application research of Steiner problem in graphs[D].Nanjing:Nanjing University of Posts and Telecommunications,2015.

[4]Wu Jichun.Research of routing protocols of ad hoc networkand NS2 simulations[D].Wuhan:Wuhan University of Technology,2005.

[5]Tao Shaoguo,Huang Jiaqing,Yang Zongkai,el al.Maxflow based routing algorithm for network coding multicast[J].Computer Science,2008,35(6):109-112.

[6]Yu Yanping.Studies on multicast routing algorithms[D].Hangzhou:Zhejiang University,2002.

[7]Hao Kun,Jin Zhigang.Mechanism of P2P file distribution based on deterministic network coding[J].Journal of Applied Sciences,2014,32(3):247-251.

[8]Xu Guangxian,Wu Wei,Zhou Jia.Research on application of niche genetic algorithm in the network coding optimization[J].Computer Engineering,2015,41(7):152-157.

[9]Yang Weihua,Wang Hongbo,Cheng Shiduan,et al.Min-cut multi-path routing algorithm[J].Journal of Software,2012,23(8):2119-2122.

[10]Du Weiqi.The research of multipath routing protocol based on network coding in wireless sensor network[D].Nanjing:Nanjing University of Posts and Telecommunications,2014.

[11]Shi Min.The routing algorithm research on PTN network management[D].Wuhan:Wuhan University of Technology,2013.

[12]Shen Meng.Research on efficient embedding and traffic management for network virtualization[D].Beijing:Tsinghua University,2014.

[13]Zhou Derong,Xia Ling,Shu Tao,et al.Research on virtual simulation platform of NS2 network protocol[J].Experimental Technology and Management,2014,31(3):87-90.

[14]Tian Shengwen.Research on construction of overlay network with Internet infrastructure awareness[D].Beijing:Beijing University of Posts and Telecommunications,2015.

[15]Li Wen.Research on multipath parallel transmission network technology in mobile communication network[D].Beijing:Beijing University of Posts and Telecommunications,2015.

附中文參考文獻：

[2]陳曉卉.組播路由算法仿真平臺設計[D].大連:大連理工大學,2006.

[3]王小龍.圖的Steiner最小樹問題的算法與應用研究[D].南京:南京郵電大學,2015.

[4]吳繼春.AdHoc網絡路由協議的研究與NS2仿真[D].武漢:武漢理工大學,2005.

[5]陶少國,黃佳慶,楊宗凱,等.基于最大流的網絡編碼組播路由算法[J].計算機科學,2008,35(6):109-112.

[6]余燕平.多播路由算法的研究[D].杭州:浙江大學,2002.

[7]郝琨,金志剛.一種基于確定性網絡編碼的P2P文件分發機制[J].應用科學學報,2014,32(3):247-251.

[8]徐光憲,吳巍,周佳.小生境遺傳算法在網絡編碼優化中的應用研究[J].計算機工程,2015,41(7):152-157.

[9]楊衛華,王洪波,程時端,等.最小割路徑路由算法[J].軟件學報,2012,23(8):2119-2122.

[10]杜蔚琪.基于網絡編碼的無線傳感網多徑路由協議的設計與實現[D].南京:南京郵電大學,2014.

[11]師敏.基于PTN網管的路由路徑算法研究[D].武漢:武漢理工大學,2013.

[12]沈蒙.網絡虛擬化中的高效映射與流量管理研究[D].北京:清華大學,2014.

[13]周德榮,夏齡,舒濤,等.NS2網絡協議虛擬仿真實驗平臺研究[J].實驗技術與管理,2014,31(3):87-90.

[14]田生文.基礎設施感知的覆蓋網絡構建理論研究[D].北京:北京郵電大學,2015.

[15]李文.機動通信網絡中的多路徑并行傳輸組網技術研究[D].北京:北京郵電大學,2015.

Centralized Network Coding Multicast RoutingAlgorithm*

XU Guangxian,LAI Junning+
College of Electronics and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China

A

TP393.02

+Corresponding author:E-mail:15604293995@163.com

XU Guangxian,LAI Junning.Centralized network coding multicast routing algorithm.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1621-1628.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1621-08

10.3778/j.issn.1673-9418.1608013

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The National Science and Technology Supporting Plan Foundation of China under Grant No.F2013BAH12F00(國家科技支撐計劃項目);the Innovation and Entrepreneurship Training Program for College Students of Liaoning Province under Grant No.201610147047(遼寧省大學生創新創業訓練計劃項目).

Received 2016-08,Accepted 2016-10.

CNKI網絡優先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.008.html

XU Guangxian was born in 1977.He received the Ph.D.degree from Liaoning Technical University.Now he is a professor and Ph.D.supervisor at Liaoning Technical University.His research interests include network coding and information processing.

徐光憲（1977—），男，江蘇鹽城人，博士，遼寧工程技術大學教授、博士生導師，主要研究領域為網絡編碼，信息處理。

LAI Junning was born in 1992.He is an M.S.candidate at Liaoning Technical University.His research interests include network coding and information processing.

賴俊寧（1992—），男，遼寧阜新人，遼寧工程技術大學碩士研究生，主要研究領域為網絡編碼，信息處理。