基于鏈路共享度的網(wǎng)絡(luò)編碼多播路由算法

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004)

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(60962002)；廣西高校人才小高地建設(shè)創(chuàng)新團(tuán)隊(duì)資助計(jì)劃項(xiàng)目(桂教人[2007]71號)；廣西信息與通訊技術(shù)重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(20904)；2010年廣西研究生教育創(chuàng)新計(jì)劃項(xiàng)目(105931003089)

FoundationItem:The National Natural Science Foundation of China(No.60962002);Program to Sponsor Teams for Innovation in the Construction of Talent Highlands in Guangxi Institutions of Higher Learning (GUIJIAOREN[2007]71);Foundation of Guangxi Key Laboratory of Information and Communication(No.20904)；2010 Innovation Projects of Guangxi Graduate Education(No.105931003089)

1 引 言

網(wǎng)絡(luò)編碼理論是對傳統(tǒng)的存儲(chǔ)-轉(zhuǎn)發(fā)通信機(jī)制的重要變革，其本質(zhì)是允許網(wǎng)絡(luò)的中間節(jié)點(diǎn)對傳輸?shù)臄?shù)據(jù)進(jìn)行編碼操作處理[1]，以此來解決存儲(chǔ)-轉(zhuǎn)發(fā)的路由策略中所遇到的帶寬瓶頸問題。文獻(xiàn)[1]首次指出采用網(wǎng)絡(luò)編碼可以實(shí)現(xiàn)多播網(wǎng)絡(luò)的傳輸容量上界，這也是網(wǎng)絡(luò)編碼最初被人們認(rèn)識的主要優(yōu)點(diǎn)，隨后的一系列研究表明，網(wǎng)絡(luò)編碼在網(wǎng)絡(luò)魯棒性以及負(fù)載均衡性等方面也都表現(xiàn)出優(yōu)越的性能。

針對網(wǎng)絡(luò)編碼的編碼方案是目前的一個(gè)重要研究方向，其主要解決碼字的構(gòu)造問題，以便有效求得每條鏈路的編碼向量。文獻(xiàn)[2]給出了網(wǎng)絡(luò)編碼的代數(shù)編碼框架并提出了網(wǎng)絡(luò)編碼的指數(shù)時(shí)間算法；文獻(xiàn)[3]給出了網(wǎng)絡(luò)編碼的多項(xiàng)式時(shí)間算法；Ho等人提出了一種分布式算法，即隨機(jī)網(wǎng)絡(luò)編碼算法[4]；文獻(xiàn)[5]針對移動(dòng)Ad Hoc網(wǎng)絡(luò)，給出了一種冗余網(wǎng)絡(luò)編碼算法，具有較高的實(shí)際應(yīng)用價(jià)值。

然而，網(wǎng)絡(luò)編碼要成功應(yīng)用于多播傳輸中，其數(shù)據(jù)分發(fā)分為兩個(gè)階段：構(gòu)造編碼子圖，即確定數(shù)據(jù)從信源到信宿的最佳分發(fā)路徑；確定編碼方案，即確定節(jié)點(diǎn)對收到的數(shù)據(jù)的編碼模式。針對編碼子圖的構(gòu)造問題，文獻(xiàn)[6]給出了基于最大流的網(wǎng)絡(luò)編碼組播路由算法；文獻(xiàn)[7]提出了一種在約簡網(wǎng)絡(luò)上搜索多播路徑的方法;對于應(yīng)用廣泛的無線mesh網(wǎng)絡(luò)，文獻(xiàn)[8-9]中提出了適用網(wǎng)絡(luò)編碼的路由算法。但是，上述方法并沒有考慮多條路徑的最大共享鏈路，對網(wǎng)絡(luò)資源的利用率不高。

傳統(tǒng)的IP多播路由算法通過建立最短路徑樹(SPT)來實(shí)現(xiàn)數(shù)據(jù)分發(fā)，然而網(wǎng)絡(luò)編碼子圖是mesh形狀的拓?fù)浣Y(jié)構(gòu)，不同于傳統(tǒng)多播樹算法。本文提出一種新的基于鏈路共享度的網(wǎng)絡(luò)編碼多播路由算法(NCMSL)，其中鏈路共享度考慮在不增加鏈路負(fù)載的情況下減少鏈路資源消耗，而非文獻(xiàn)[10]中的以鏈路代價(jià)的增加來增加鏈路的可共享性。仿真結(jié)果表明，結(jié)合隨機(jī)網(wǎng)絡(luò)編碼，該算法能大幅度提高多播傳輸?shù)男阅堋?/p>

2 隨機(jī)網(wǎng)絡(luò)編碼

給定有向無環(huán)圖G=(V,E,T)，V是節(jié)點(diǎn)集合，E是鏈路集合，T是信宿節(jié)點(diǎn)集合。信源S發(fā)送h維信息符號向量[x1,x2,…,xh]給信宿節(jié)點(diǎn)t(t∈T)。在隨機(jī)網(wǎng)絡(luò)編碼中[4]，每個(gè)編碼節(jié)點(diǎn)在一定大小的有限域GF(q)中獨(dú)立地為其每條輸出鏈路隨機(jī)選取編碼系數(shù)并對輸入鏈路上的信息進(jìn)行線性編碼組合后轉(zhuǎn)發(fā)到輸出鏈路。每條鏈路上傳輸?shù)木幋a信息有一個(gè)全局編碼向量GC(e)與信源發(fā)送的原始h維信息向量相對應(yīng)，使得鏈路e上傳輸?shù)男畔⒎朰(e)滿足下列關(guān)系：

Y(e)=GC(e)1×h×[x1x2…xh]T=

(1)

對于信宿節(jié)點(diǎn)t而言，可以通過其h條輸入鏈路上的編碼信息符號恢復(fù)h維原始信息符號。假設(shè)信宿t的h條輸入鏈路分別為e1,e2,…,eh，各條鏈路上傳輸?shù)木幋a信息構(gòu)成向量[Y(e1)Y(e2) …Y(eh)]T，全局編碼向量為[GC(e1)GC(e2)…GC(eh)]T，則：

(2)

式中，GC(ei)j表示t的第i條輸入鏈路傳輸?shù)木幋a信息對應(yīng)于第j個(gè)原始信息符號的全局編碼系數(shù)。

從式(2)可知，當(dāng)且僅當(dāng)h條輸入鏈路上的全局編碼向量構(gòu)成的矩陣滿秩時(shí)，信宿t通過X=GC-1Y可恢復(fù)出原始h維信息向量。

3 鏈路共享度

在網(wǎng)絡(luò)編碼的編碼子圖中，需要建立信源到每個(gè)信宿的多播傳輸路徑。其中每個(gè)信宿節(jié)點(diǎn)的多條可分離路徑構(gòu)成一個(gè)路徑集，不同信宿節(jié)點(diǎn)的路徑集中會(huì)有共享鏈路。

定義1(共享鏈路)：設(shè)P(t1)和P(t2)分別為信源S到信宿t1和t2的路徑上的鏈路集合，若P(t1)∩P(t2)={e}，則稱{e}為路徑P(t1)和P(t2)的共享鏈路。

定義2(鏈路共享度)：對于一個(gè)有向無環(huán)圖G=(V,E),其中V為節(jié)點(diǎn)集，E為邊集。indeg(i)表示節(jié)點(diǎn)i的入度， outdeg(i)表示節(jié)點(diǎn)i的出度。對有向鏈路e=(v,u),記λi(e)=v,λo(e)=u,λi(e)和λo(e)分別表示鏈路e的兩個(gè)端點(diǎn)。鏈路e的鏈路共享度如式(3)所示：

D(e)=indeg(λi(e))+outdeg(λo(e))-1，
?e∈E

(3)

鏈路共享度D(e)越大，則多條路徑同時(shí)經(jīng)過鏈路e的可能性越大。

定義3(可分離路徑)[11]：兩條路徑是可分離路徑當(dāng)且僅當(dāng)它們之間沒有共享鏈路。

圖1表明，在圖1(a)所示的網(wǎng)絡(luò)拓?fù)渲校粢謩e搜索信源S到信宿t1和t2的兩條可分離路徑，依據(jù)鏈路共享度的定義，應(yīng)盡量選擇鏈路(v1,v5)、(v2,v6)或(v3,v5)加入到所構(gòu)建的路徑集中。圖1(b)、(c)分別為依據(jù)鏈路共享度搜索到的t1和t2的兩條可分離路徑的一種情況，(d)為合并后的路徑，可見t1和t2共享了4條鏈路帶寬資源。

(a)網(wǎng)絡(luò)拓?fù)?/p>

(b)t1的可分離路徑

(c)t2的可分離路徑

(d)基于鏈路共享度的傳輸路徑

圖1 鏈路共享度
Fig.1 Link shareability

4 NCMSL算法描述

為了構(gòu)建低代價(jià)的網(wǎng)絡(luò)編碼子圖，需要考慮多播傳輸路徑中鏈路的共享度。不同信宿節(jié)點(diǎn)的路徑集中共享鏈路的數(shù)目越多，則網(wǎng)絡(luò)編碼子圖中執(zhí)行編碼操作的節(jié)點(diǎn)數(shù)目越少，能有效減少網(wǎng)絡(luò)中節(jié)點(diǎn)的計(jì)算開銷和消耗的鏈路帶寬資源，提高帶寬資源的可共享性。

對于多播網(wǎng)絡(luò)，要執(zhí)行網(wǎng)絡(luò)編碼，需要確定每個(gè)信宿節(jié)點(diǎn)的多條可分離路徑，使得傳輸信息通過多條可分離路徑傳送；不同的信宿節(jié)點(diǎn)的可分離路徑集構(gòu)成網(wǎng)絡(luò)編碼子圖。

著名的Dijstra[12]算法是解決最短路徑問題的有效方法，借助其搜索路徑的思想，可簡化路徑搜索過程。本文提出的基于鏈路可共享度的網(wǎng)絡(luò)編碼多播路由算法(NCMSL)描述如下：

輸入：網(wǎng)絡(luò)G=(V,E,S,T), 多播網(wǎng)絡(luò)信息傳輸速率h，以及可分離路徑數(shù)目L；

輸出：所有信宿tk的L(L≤h)條可分離路徑，tk∈T。

步驟2:搜索信源S到信宿tk的第r(1≤r≤L)條可分離路徑:

(1)D(i,j)表示鏈路e=(i,j)的共享度;令A(yù)=?，A′=V，Par(s)=0，Par(i)為當(dāng)前搜索路徑上節(jié)點(diǎn)i的前驅(qū)標(biāo)號，用于回溯時(shí)追蹤路徑;Wi表示信源S(i∈V)到節(jié)點(diǎn)i的路徑共享度(約定路徑共享度為路徑上所有鏈路共享度之和)，初始化為0；Ws初始化為某一足夠大的正整數(shù)m。

(2)如果A=V,則Wtk為信源S到信宿tk的最大路徑共享度，通過Par數(shù)組所記錄的信息反向追蹤可以獲得最大共享度路徑，結(jié)束；否則轉(zhuǎn)入步驟3。

(3)從A′中找到共享度標(biāo)號W最大的節(jié)點(diǎn)j，把它從A′中刪除，加入A。在A中，對于所有從j出發(fā)的有向鏈路(j,i)∈V,若Wi

步驟3：若鏈路(i,j)存在于信宿tk的可分離路徑集中，則將其對應(yīng)的鏈路從網(wǎng)絡(luò)拓?fù)鋱D中刪除，并更新鏈路共享度矩陣D，使得鏈路(i,j)不參與信宿tk的下一條可分離路徑的搜索過程。

步驟4：若已找到tk的L條可分離路徑，則轉(zhuǎn)步驟5；否則，重復(fù)步驟2。

質(zhì)量管理體系的不斷完善對于提升鈑金工藝技術(shù)水平具有良好的推動(dòng)作用。結(jié)合上文分析的情況來看，我國的鈑金企業(yè)目前在生產(chǎn)設(shè)計(jì)、設(shè)備管理以及原材料管控等多個(gè)方面都存在明顯的缺陷，這不但會(huì)導(dǎo)致企業(yè)的發(fā)展遲滯，更會(huì)給整個(gè)行業(yè)帶來不利的影響。通過完善質(zhì)量管理體系，建設(shè)更高的技術(shù)標(biāo)準(zhǔn)與統(tǒng)一管理模式，可以實(shí)現(xiàn)優(yōu)勝劣汰，將一些粗放的生產(chǎn)企業(yè)淘汰，同時(shí)引入先進(jìn)的生產(chǎn)技術(shù)與制造工藝，凈化市場環(huán)境的同時(shí)也促進(jìn)了我國鈑金工藝技術(shù)的發(fā)展。

步驟5：若k=|T|結(jié)束；否則，更新Copy-D矩陣，將當(dāng)前信宿節(jié)點(diǎn)tk的可分離路徑集中的鏈路在矩陣Copy-D中對應(yīng)的鏈路共享度加m，即增大該鏈路的可共享性，使得后續(xù)信宿的可分離路徑盡量共享該鏈路，置k=k+1，接著重復(fù)步驟2～4，為避免不同信宿可分離路徑集之間的相互影響，每次初始搜索當(dāng)前信宿的可分離路徑時(shí)都使用更新后的Copy-D矩陣作為鏈路共享度矩陣。

5 性能仿真與分析

5.1 網(wǎng)絡(luò)拓?fù)渑c編碼模式

仿真實(shí)驗(yàn)中采用隨機(jī)網(wǎng)絡(luò)拓?fù)鋄13]，網(wǎng)絡(luò)節(jié)點(diǎn)均勻分布，節(jié)點(diǎn)度控制在5.1～5.3之間，且利用隨機(jī)網(wǎng)絡(luò)編碼進(jìn)行編碼。仿真結(jié)果如圖2所示。從圖2中可以看出，解碼成功率隨有限域增大而增大，當(dāng)q為28時(shí)，解碼成功率接近于1，且28的計(jì)算復(fù)雜度適中，因此在后續(xù)仿真實(shí)驗(yàn)中取q=28。

圖2 有限域大小對解碼成功率的影響Fig.2 Effect of finite field on decoding probability

5.2 性能仿真與結(jié)果分析

5.2.1平均帶寬資源消耗

平均帶寬資源消耗定義為多播算法中總的帶寬消耗與網(wǎng)絡(luò)多播速率的比值。仿真中假定帶寬資源足夠大，信源S的多播傳輸速率為200 bit/s。隨機(jī)生成的網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)數(shù)為50，為每個(gè)信宿尋找4條可分離路徑則，基于鏈路共享度的網(wǎng)絡(luò)編碼多播算法(NCMSL)與基于最短路徑樹(SPT)的傳統(tǒng)IP多播算法的平均帶寬資源消耗對比如圖3所示。

圖3 不同多播路由算法的帶寬資源消耗(節(jié)點(diǎn)總數(shù)n=50)Fig.3 Bandwidth consumption of different algorithms(n=50)

仿真結(jié)果表明，隨著信宿節(jié)點(diǎn)的增加，網(wǎng)絡(luò)中平均帶寬資源消耗是不斷增加的，并且SPT算法的平均帶寬資源消耗遠(yuǎn)遠(yuǎn)大于NCMSL算法的平均帶寬資源消耗。這是因?yàn)殡S著信宿節(jié)點(diǎn)的增加，NCMSL算法中多個(gè)信宿節(jié)點(diǎn)的可分離路徑集中可共享鏈路的數(shù)目越多，并且由于每個(gè)信宿節(jié)點(diǎn)的多播信息流是均勻分布在其多條可分離路徑集中，因此每條鏈路的帶寬消耗很??；而SPT多播路由算法中，信宿節(jié)點(diǎn)增加時(shí)，建立多播路徑樹所需的鏈路數(shù)目隨之增加，并且由于到達(dá)每個(gè)信宿節(jié)點(diǎn)只有一條路徑，因此要實(shí)現(xiàn)多播傳輸速率必須增加每條鏈路的帶寬資源消耗。從圖中可以看出，信宿節(jié)點(diǎn)數(shù)目越多，基于NCMSL的網(wǎng)絡(luò)編碼算法相比SPT算法對帶寬資源的利用率越高。

5.2.2網(wǎng)絡(luò)負(fù)載均衡性

當(dāng)前Internet中網(wǎng)絡(luò)資源有限，當(dāng)帶寬資源分布不均時(shí)，使得網(wǎng)絡(luò)負(fù)載集中于少數(shù)幾條鏈路上，便會(huì)產(chǎn)生網(wǎng)絡(luò)擁塞現(xiàn)象，甚至?xí)l(fā)生鏈路癱瘓，對整個(gè)網(wǎng)絡(luò)性能造成嚴(yán)重影響。因此在設(shè)計(jì)路由算法時(shí)，應(yīng)均衡合理利用網(wǎng)絡(luò)中的帶寬資源，使得整個(gè)網(wǎng)絡(luò)負(fù)載均勻分布在較廣泛的通信鏈路上。

圖4所示為NCMSL網(wǎng)絡(luò)編碼多播算法和基于SPT的多播算法在網(wǎng)絡(luò)負(fù)載分布均衡性方面的比較，其中網(wǎng)絡(luò)負(fù)載均衡性表示多播算法中使用的鏈路數(shù)目占網(wǎng)絡(luò)中總鏈路數(shù)目的百分比。從圖中可以看出，NCMSL算法采用的鏈路數(shù)目在整個(gè)網(wǎng)絡(luò)中的比例遠(yuǎn)遠(yuǎn)大于SPT算法采用的鏈路數(shù)目在整個(gè)網(wǎng)絡(luò)中的比例，且NCMSL算法中每條鏈路的負(fù)載只有h/4,而SPT算法中每條鏈路的負(fù)載為h。NCMSL使得整個(gè)網(wǎng)絡(luò)負(fù)載分布有更好的均衡性，減小了網(wǎng)絡(luò)阻塞的概率。而SPT算法中網(wǎng)絡(luò)負(fù)載僅僅集中在少數(shù)鏈路上，當(dāng)網(wǎng)絡(luò)中傳輸?shù)男畔⒘魉俾试黾訒r(shí)，會(huì)大大增加每條鏈路的負(fù)擔(dān)。

圖4 不同多播路由算法的網(wǎng)絡(luò)負(fù)載均衡性(節(jié)點(diǎn)總數(shù)n=50)Fig.4 Banalance of network load in different algorithms(n=50)

結(jié)合圖3和圖4可以看出，NCMSL算法在采用更廣泛的通信鏈路的同時(shí)卻大大減小了帶寬資源消耗，同時(shí)減小了每條鏈路的負(fù)載，較好地提高了整個(gè)多播網(wǎng)絡(luò)的傳輸性能。由于NCMSL算法在搜索網(wǎng)絡(luò)編碼子圖時(shí)，充分考慮了每條鏈路的共享性，同時(shí)使得每個(gè)信宿節(jié)點(diǎn)可以同時(shí)從多條可分離路徑同時(shí)接收多播信息流，從而使得整個(gè)網(wǎng)絡(luò)負(fù)載分布均勻，結(jié)合網(wǎng)絡(luò)編碼算法，可提高整個(gè)多播網(wǎng)絡(luò)的吞吐量。

6 結(jié)束語

本文通過引入鏈路共享度的概念，使得構(gòu)建的網(wǎng)絡(luò)編碼子圖最小化。研究表明，通過每次搜索路徑時(shí)尋找共享度最大的鏈路加入多播路徑，可以有效減少參與編碼的節(jié)點(diǎn)數(shù)目和鏈路數(shù)目，從而實(shí)現(xiàn)最小代價(jià)網(wǎng)絡(luò)編碼。NCMSL算法指出充分利用網(wǎng)絡(luò)帶寬資源是提高網(wǎng)絡(luò)傳輸性能的有效途徑。

參考文獻(xiàn)：

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

[2] Koetter R, Medard M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Networking,2003,11(5):782-795.

[3] Jaggi S,Sanders P,Chou P A,et al.Polynomial time algorithms for multicast network code construction[J].IEEE Transactions on Information Theory,2005,51(6):1973-1982.

[4] Ho T, Medard M, Koetter R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[5] 梁智怡，覃團(tuán)發(fā)，羅建中.一種移動(dòng)Ad Hoc網(wǎng)絡(luò)的冗余網(wǎng)絡(luò)編碼方法[J]. 電訊技術(shù),2010，50(1):81-86.

LIANG Zhi-yi, QIN Tuan-fa, LUO Jian-zhong.Post-redundancy network coding strategy in mobile ad hoc networks[J].Telecommunication Engineering,2010,50(1):81-86.(in Chinese)

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

TAO Shao-guo,HUANG Jia-qing,YANG Zong-kai,et al.Maxflow-based routing altorithm for network coding multicast[J].Computer Science，2008,35(6):107-117.(in Chinese)

[7] 王靜，劉景美，王新梅. 基于網(wǎng)絡(luò)編碼的多播路由算法性能分析[J]. 電子與信息學(xué)報(bào)，2008,30(11):2605-2608.

WANG Jing, LIU Jing-mei, WANG Xin-mei. Performance analysis of multicast routing algorithm based on network coding[J].Journal of Electronics and Information Technology,2008,30(11):2605-2608. (in Chinese)

[8] 覃團(tuán)發(fā)，廖素蕓，羅會(huì)平，等. 支持網(wǎng)絡(luò)編碼的無線Mesh網(wǎng)絡(luò)路由協(xié)議[J]. 北京郵電大學(xué)學(xué)報(bào)，2009，32(1):14-18.

QIN Tuan-fa, LIAO Su-yun, LUO Hui-ping, et al. A network coding aware routing protocol in wireless mesh network[J]. Journal of Beijing University of Posts and Telecommunications,2009,32(1):14-18.(in Chinese)

[9] 覃團(tuán)發(fā)，廖素蕓，羅會(huì)平. 無線mesh網(wǎng)絡(luò)中網(wǎng)絡(luò)編碼的文件共享模型[J]. 電訊技術(shù),2008，48(5):17-20.

QIN Tuan-fa,LIAO Su-yun,LUO Hui-ping.The file sharing model based on network coding for wireless mesh network[J].Telecommunication Engineering,2008,48(5):17-20.(in Chinese)

[10] 王東，曾鋒，閔應(yīng)驊.基于鏈路共享性的多播路由算法[J]. 湖南大學(xué)學(xué)報(bào)，2006,33(4):111-114.

WANG Dong, ZENG Feng, MIN Yin-hua. A multicast routing algorithm based on shareability analysis[J].Journal of Hunan University,2006,33(4):111-114. (in Chinese)

[11] Zhu Ying, Li Bao chun. Multicast with network coding in application-layer overlay networks[J]. IEEE Journal on Selected Areas in Communications,2004,22(1):107-120.

[12] 謝金星，刑文訓(xùn)，王振波.網(wǎng)絡(luò)優(yōu)化[M]. 北京：清華大學(xué)出版社,2009:62-63.

XIE Jin-xing, XING Wen-xun, WANG Zhen-bo. Network Optimization[M].Beijing: Tsinghua University Press,2009:62-63.(in Chinese)

[13] Waxman B M. Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Commuications,1988,6(9):1617-1622.