集中式網(wǎng)絡(luò)編碼組播路由算法*

徐光憲，賴俊寧

遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105

集中式網(wǎng)絡(luò)編碼組播路由算法*

徐光憲，賴俊寧+

遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 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

從提高組播容量和降低組播延遲入手，提出了一種集中式網(wǎng)絡(luò)編碼循環(huán)增廣組播路由算法（centralized network coding cycle augmented multicast routing algorithm，NCCA），從而進(jìn)一步提高了組播通信的傳輸速率。首先各節(jié)點(diǎn)通過廣度優(yōu)先搜索（breadth first search，BFS）算法遍歷鏈路狀態(tài)分組獲得整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?，以Dijkstra算法為基礎(chǔ)增廣每個(gè)信宿節(jié)點(diǎn)的路由集，然后選出最優(yōu)路由集，最后將所有信宿節(jié)點(diǎn)的路由集進(jìn)行組合，得到組播組的整體路由。通過對(duì)算法進(jìn)行理論分析及仿真實(shí)驗(yàn)，證明了NCCA組播路由算法在較穩(wěn)定的網(wǎng)絡(luò)上能進(jìn)一步提高組播通信的傳輸速率。

網(wǎng)絡(luò)編碼；組播容量；組播延遲；組播傳輸速率

1 引言

傳統(tǒng)網(wǎng)絡(luò)的信息傳輸大部分是基于存儲(chǔ)和轉(zhuǎn)發(fā)的路由機(jī)制，Ahlswede等人[1]于2000年首次提出了網(wǎng)絡(luò)編碼的基本原理，它允許中間節(jié)點(diǎn)對(duì)輸入信息進(jìn)行編碼，在提高網(wǎng)絡(luò)吞吐量，改善負(fù)載均衡，減小傳輸延遲，增強(qiáng)網(wǎng)絡(luò)魯棒性和提高信息安全性等方面具有重要意義。近年來網(wǎng)絡(luò)編碼在優(yōu)化與安全等領(lǐng)域得到了深入研究，對(duì)組播路由的研究也逐漸成為網(wǎng)絡(luò)編碼的新熱點(diǎn)。

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

本文從提高組播容量和降低組播延遲入手，提出了一種集中式網(wǎng)絡(luò)編碼循環(huán)增廣組播路由算法（centralized network coding cycle augmented multicast routing algorithm，NCCA），從而進(jìn)一步提高了組播通信的傳輸速率。NCCA是一種集中式組播路由算法，首先每個(gè)路由節(jié)點(diǎn)都需要通過周期性發(fā)布動(dòng)態(tài)的鏈路狀態(tài)分組獲得網(wǎng)絡(luò)信息，然后維護(hù)整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?，最后根?jù)網(wǎng)絡(luò)拓?fù)湫畔ⅹ?dú)立地構(gòu)造多播樹。針對(duì)NCMA一次增廣不一定能得到網(wǎng)絡(luò)的最大組播容量和最小組播延遲的問題，本文運(yùn)用NCCA選出每個(gè)信宿的最優(yōu)路由集，將所有信宿的路由集進(jìn)行組合，得到組播組的整體路由。仿真實(shí)驗(yàn)表明，在中等網(wǎng)絡(luò)規(guī)模下，應(yīng)用NCCA組播路由算法在較穩(wěn)定的網(wǎng)絡(luò)上能進(jìn)一步提高組播通信的傳輸速率。

2 相關(guān)知識(shí)

2.1 廣度優(yōu)先搜索算法遍歷鏈路狀態(tài)分組

廣度優(yōu)先搜索（breadth first search，BFS）算法從各節(jié)點(diǎn)訪問所有與之相鄰的節(jié)點(diǎn)，訪問完這些節(jié)點(diǎn)后，再訪問與這些節(jié)點(diǎn)相鄰的未被訪問的節(jié)點(diǎn)，重復(fù)整個(gè)過程直到所有的節(jié)點(diǎn)都被訪問，通過序列號(hào)控制鏈路狀態(tài)分組的擴(kuò)散過程[6]。發(fā)布的鏈路狀態(tài)分組包括一個(gè)發(fā)送方標(biāo)識(shí)、序列號(hào)、年齡以及一個(gè)包含距離的鄰居列表。每當(dāng)鏈路狀態(tài)發(fā)生改變時(shí)重新創(chuàng)建并發(fā)布分組，從而構(gòu)造實(shí)時(shí)的網(wǎng)絡(luò)拓?fù)洹?/p>

2.2 Dijkstra算法尋路

NCCA以Dijkstra算法尋路，它的基本思路是先建立一個(gè)網(wǎng)絡(luò)圖，圖中的每個(gè)節(jié)點(diǎn)代表一臺(tái)路由器，每條弧代表一條通信鏈路。每一個(gè)節(jié)點(diǎn)都有一個(gè)兩項(xiàng)的標(biāo)號(hào)，標(biāo)號(hào)第一項(xiàng)是最短路徑上對(duì)應(yīng)的前趨節(jié)點(diǎn)，第二項(xiàng)是這個(gè)路徑的長(zhǎng)度，每個(gè)標(biāo)號(hào)分為暫時(shí)的或永久的，初始時(shí)所有標(biāo)號(hào)都是暫時(shí)的。初始時(shí)所有的節(jié)點(diǎn)都標(biāo)記為無限遠(yuǎn)，隨著算法的不斷進(jìn)行，當(dāng)確定了一個(gè)標(biāo)號(hào)為從原點(diǎn)到該節(jié)點(diǎn)的最短路徑時(shí)，標(biāo)號(hào)變成永久的并且不再改變。此時(shí)信宿節(jié)點(diǎn)到組播源范圍內(nèi)的節(jié)點(diǎn)都會(huì)生成自己的標(biāo)號(hào)，每個(gè)標(biāo)號(hào)都對(duì)應(yīng)著各自的路由選擇，標(biāo)記為永久節(jié)點(diǎn)后可通過反向追蹤確定最短路徑[2]。

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

2.3 網(wǎng)絡(luò)編碼

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

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

2.4 NCCA多播樹

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

3 NCCA組播路由算法

3.1 NCCA組播路由算法原理

組播傳輸速率v表示單位時(shí)間內(nèi)信宿接收到信息的大小，組播容量c表示網(wǎng)絡(luò)中組播率hs的上限，組播容量c越大，傳輸速率v也越高。組播延遲d指的是一次組播中信息從發(fā)出到接收所經(jīng)歷的時(shí)間，組播延遲d越小，傳輸速率v就越高[9]。因此可從提高組播容量和降低組播延遲入手，進(jìn)一步提高組播通信的傳輸速率。

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

Fig.1 Typical butterfly network圖1 典型的蝴蝶網(wǎng)絡(luò)

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

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

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

3.2 NCCA組播路由算法流程

NCCA組播路由算法的總體設(shè)計(jì)框圖如圖2所示。定義參數(shù)si為由鏈表構(gòu)造的路徑，ts為路由延遲，S為組播路由集，TS為臨時(shí)組播路由集，d為組播延遲，c為組播容量，Td、Tc分別是臨時(shí)組播延遲和容量，i為首選路徑的循環(huán)參數(shù)，n為首選路徑等級(jí)，q為循環(huán)選路模塊的循環(huán)參數(shù)，fd為首選路徑延遲，sd為標(biāo)準(zhǔn)延遲上界。

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

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

如圖2，NCCA組播路由算法主程序中的D模塊與循環(huán)模塊由一個(gè)小循環(huán)連接構(gòu)成，小循環(huán)憑借參數(shù)i自加運(yùn)行，負(fù)責(zé)為信宿到信源尋一條路徑si并保存到路由集Ts中，增廣路由集的公式為：

通過排序子模塊計(jì)算單個(gè)路徑延遲ts，將最大的延遲作為路由集的組播延遲Td，然后修訂拓?fù)鋱D。當(dāng)ts≥d，ts≥sd或無法生成新路徑時(shí)跳出小循環(huán)，保存路由集的組播容量Tc，進(jìn)入容量/延遲比較模塊。

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

Fig.2 NCCAoverall design diagram圖2 NCCA總體設(shè)計(jì)框圖

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

3.3 收斂性以及算法復(fù)雜度分析

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

用鄰接鏈表表示拓?fù)鋱D，用斐波那契堆實(shí)現(xiàn)優(yōu)先隊(duì)列，Dijkstra算法的時(shí)間復(fù)雜度為O(E+nlgn)。NCCA求信宿節(jié)點(diǎn)到每個(gè)信源節(jié)點(diǎn)的最短路徑，則每個(gè)信源需調(diào)用一次Dijkstra算法，設(shè)組播率為hs，算法循環(huán)k次達(dá)到收斂，則算法的時(shí)間復(fù)雜度為O(khs(E+lgn))。對(duì)于空間復(fù)雜度，首先需要空間n保存距離，另需空間n存儲(chǔ)前一個(gè)節(jié)點(diǎn)以保存路徑，此外還需一個(gè)斐波那契堆及其反向指針，而且NCCA算法在每個(gè)節(jié)點(diǎn)保存hs條最短路徑，每次更新路徑集的代價(jià)相當(dāng)于把hs個(gè)長(zhǎng)度為4n的表合并在一起，因此NCCA的空間復(fù)雜度為O(4nhs)。

4 NCCA路由算法仿真

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

4.1 構(gòu)建網(wǎng)絡(luò)拓?fù)?/h3>

GT-ITM是NS2自帶的開源網(wǎng)絡(luò)拓?fù)渖晒ぞ?，使用GT-ITM建立K均值聚類Waxman隨機(jī)拓?fù)淠Ｐ停↘-means Waxman random network topology model，KRTG），KRTG模型節(jié)點(diǎn)和邊分布均勻，避免了重疊或距離過近，能生成度數(shù)收斂的連通圖[11]。將n個(gè)節(jié)點(diǎn)按KRTG模型分布在平面上，生成鏈路，從而構(gòu)建連通圖的概率分布為：

其中，L為拓?fù)渲兴泄?jié)點(diǎn)距離的最大值，設(shè)a為網(wǎng)絡(luò)的邊長(zhǎng)，則L=a；|V|為節(jié)點(diǎn)數(shù)；d(u,v)是節(jié)點(diǎn)u和v之間的歐式距離；α、β是取自(0,1]的實(shí)數(shù)。選擇適當(dāng)?shù)闹的苁雇負(fù)涓咏鎸?shí)網(wǎng)絡(luò)。概率P(u,v)中，D是節(jié)點(diǎn)平均度。在實(shí)驗(yàn)中鏈路延遲調(diào)用λ=d(u,v)的泊松分布函數(shù)[12]，設(shè)置平面為100 km×100 km的正方形區(qū)域，坐標(biāo)最小刻度為1，α=0.15，D=4。

4.2 應(yīng)用NS2仿真NCCA組播路由算法

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

本文設(shè)計(jì)了兩組實(shí)驗(yàn)對(duì)組播路由算法MAODV、NWMPH、NCCA和NCMA進(jìn)行仿真。每個(gè)節(jié)點(diǎn)通過BFS算法以300 ms為周期發(fā)送鏈路狀態(tài)分組來實(shí)現(xiàn)拓?fù)涞膶?shí)時(shí)更新，理論上每次BFS算法對(duì)整個(gè)網(wǎng)絡(luò)掃描所消耗的時(shí)間是由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)所決定的，和網(wǎng)絡(luò)直徑有直接的關(guān)系。第一組實(shí)驗(yàn)在節(jié)點(diǎn)數(shù)50、100、150、200、250、300、350下分別隨機(jī)生成30次拓?fù)淠Ｐ?，運(yùn)行各算法并在算法執(zhí)行過程中動(dòng)態(tài)加入相同數(shù)量的組播源和信宿，直到達(dá)到最大組播容量。第二組實(shí)驗(yàn)在30組200節(jié)點(diǎn)的網(wǎng)絡(luò)規(guī)模中仿真，在鏈路停留時(shí)間為 0.05、0.10、0.15、0.20、0.25、0.30、0.35 s的情況下使各算法達(dá)到最大組播容量。兩組實(shí)驗(yàn)最終生成了記錄算法執(zhí)行過程參數(shù)的trace跟蹤文件。

4.3 算法性能分析

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

實(shí)驗(yàn)1中MAODV、NWMPH、NCCA和NCMA算法運(yùn)行結(jié)果的平均組播容量、平均組播延遲和平均收斂時(shí)間對(duì)比如圖3、圖4、圖5所示。實(shí)驗(yàn)2中各算法運(yùn)行結(jié)果的組播傳輸速率對(duì)比如圖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關(guān)鍵鏈路的占用以及少量的中心節(jié)點(diǎn)頻繁被選為中繼節(jié)點(diǎn)，導(dǎo)致路由路徑存在較高的重疊率和較高的組播延遲。其中MAODV和NWMPH還不支持網(wǎng)絡(luò)編碼，導(dǎo)致較高的隊(duì)列長(zhǎng)度，因此組播容量較小。另一方面各算法在兩項(xiàng)指標(biāo)上有大致相似的變化趨勢(shì)，這是因?yàn)殡S著網(wǎng)絡(luò)規(guī)模的增加，更多中繼節(jié)點(diǎn)使組播路由有更為豐富的選擇。

如圖5所示，NCCA的平均收斂時(shí)間大于其他算法，這是因?yàn)镹CMA和MAODV的時(shí)間復(fù)雜度都為O(hsn2)，NWMPH的時(shí)間復(fù)雜度為O(mn2)，而NCCA的時(shí)間復(fù)雜度為O(khs(E+nlgn))，大于其他算法。隨著網(wǎng)絡(luò)規(guī)模的增加，NCCA的平均收斂時(shí)間大幅增加，而MAODV、NWMPH和NCMA則變化不明顯，這表明網(wǎng)絡(luò)規(guī)模對(duì)NCCA的收斂速度有較大影響。這是由于算法的時(shí)間復(fù)雜度受循環(huán)次數(shù)k的影響，對(duì)于規(guī)模很大的網(wǎng)絡(luò)不易收斂。

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

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

如圖6所示，適用于自組網(wǎng)的分布式路由協(xié)議MAODV在鏈路停留時(shí)間較短時(shí)組播傳輸速率最高，說明MAODV適用于變化頻繁的網(wǎng)絡(luò)。NCCA在鏈路停留時(shí)間較長(zhǎng)時(shí)有較高的組播傳輸速率，表明NCCA適用于相對(duì)穩(wěn)定的網(wǎng)絡(luò)。原因是NCCA的收斂速度較慢，鏈路的頻繁變動(dòng)會(huì)帶來很大的節(jié)點(diǎn)開銷，而如果鏈路較穩(wěn)定，NCCA便能充分利用其優(yōu)化組播容量和組播延遲的優(yōu)勢(shì)。另一方面隨著鏈路停留時(shí)間的增加，NCCA和NCMA的組播傳輸速率大幅增加，而MAODV和NWMPH則變化不明顯，這是因?yàn)镸AODV和NWMPH中節(jié)點(diǎn)無法進(jìn)行網(wǎng)絡(luò)編碼，導(dǎo)致了較重的隊(duì)列擁塞。

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

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

[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.

附中文參考文獻(xiàn)：

[2]陳曉卉.組播路由算法仿真平臺(tái)設(shè)計(jì)[D].大連:大連理工大學(xué),2006.

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

[4]吳繼春.AdHoc網(wǎng)絡(luò)路由協(xié)議的研究與NS2仿真[D].武漢:武漢理工大學(xué),2005.

[5]陶少國(guó),黃佳慶,楊宗凱,等.基于最大流的網(wǎng)絡(luò)編碼組播路由算法[J].計(jì)算機(jī)科學(xué),2008,35(6):109-112.

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

[7]郝琨,金志剛.一種基于確定性網(wǎng)絡(luò)編碼的P2P文件分發(fā)機(jī)制[J].應(yīng)用科學(xué)學(xué)報(bào),2014,32(3):247-251.

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

[9]楊衛(wèi)華,王洪波,程時(shí)端,等.最小割路徑路由算法[J].軟件學(xué)報(bào),2012,23(8):2119-2122.

[10]杜蔚琪.基于網(wǎng)絡(luò)編碼的無線傳感網(wǎng)多徑路由協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)[D].南京:南京郵電大學(xué),2014.

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

[12]沈蒙.網(wǎng)絡(luò)虛擬化中的高效映射與流量管理研究[D].北京:清華大學(xué),2014.

[13]周德榮,夏齡,舒濤,等.NS2網(wǎng)絡(luò)協(xié)議虛擬仿真實(shí)驗(yàn)平臺(tái)研究[J].實(shí)驗(yàn)技術(shù)與管理,2014,31(3):87-90.

[14]田生文.基礎(chǔ)設(shè)施感知的覆蓋網(wǎng)絡(luò)構(gòu)建理論研究[D].北京:北京郵電大學(xué),2015.

[15]李文.機(jī)動(dòng)通信網(wǎng)絡(luò)中的多路徑并行傳輸組網(wǎng)技術(shù)研究[D].北京:北京郵電大學(xué),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(國(guó)家科技支撐計(jì)劃項(xiàng)目);the Innovation and Entrepreneurship Training Program for College Students of Liaoning Province under Grant No.201610147047(遼寧省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目).

Received 2016-08,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版: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—），男，江蘇鹽城人，博士，遼寧工程技術(shù)大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)編碼，信息處理。

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—），男，遼寧阜新人，遼寧工程技術(shù)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)編碼，信息處理。