基于網(wǎng)絡(luò)編碼的確定性逐層構(gòu)造算法

徐光憲，趙 越，賴(lài)俊寧

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

0 引言

在傳統(tǒng)網(wǎng)絡(luò)通信中，節(jié)點(diǎn)只能對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)單的存儲(chǔ)和轉(zhuǎn)發(fā)，不能對(duì)數(shù)據(jù)作任何處理。然而在2000年Ahlswede等[1]首次提出了網(wǎng)絡(luò)編碼的基本原理，其核心思想是允許中間節(jié)點(diǎn)對(duì)輸入信息進(jìn)行合理編碼，然后將編碼信息發(fā)送到下級(jí)節(jié)點(diǎn)，最后信宿通過(guò)解碼矩陣對(duì)編碼信息進(jìn)行解碼即可恢復(fù)出原始信息。Koetter等[2]提出了關(guān)于確定線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造方法，2005年Jaggi等[3]簡(jiǎn)化了文獻(xiàn)[2]方法，把構(gòu)造網(wǎng)絡(luò)編碼的復(fù)雜程度從指數(shù)級(jí)別降到了多項(xiàng)式級(jí)別，也使網(wǎng)絡(luò)編碼中使用的伽羅華域次數(shù)有所縮減[4-5]。隨著研究的不斷深入，線性網(wǎng)絡(luò)編碼構(gòu)造算法被分成了隨機(jī)線性網(wǎng)絡(luò)編碼構(gòu)造算法[6]和確定線性網(wǎng)絡(luò)編碼構(gòu)造算法[7]。隨機(jī)線性網(wǎng)絡(luò)編碼是指在信息傳輸過(guò)程中從有限域中隨機(jī)選取編碼向量，并對(duì)接收到的信息進(jìn)行編碼，所以隨機(jī)線性網(wǎng)絡(luò)編碼要求編碼節(jié)點(diǎn)有較強(qiáng)的運(yùn)算能力，并且當(dāng)信宿點(diǎn)接收到了足夠的數(shù)據(jù)后，就可以進(jìn)行解碼操作。與隨機(jī)線性網(wǎng)絡(luò)編碼不同，確定線性網(wǎng)絡(luò)編碼是先確定編碼向量，再進(jìn)行數(shù)據(jù)傳輸。確定性網(wǎng)絡(luò)通常指有線網(wǎng)絡(luò)拓?fù)?，其全局網(wǎng)絡(luò)拓?fù)涫枪潭ǖ?，編碼節(jié)點(diǎn)的位置也是確定的，所以編碼向量可根據(jù)全局網(wǎng)絡(luò)拓?fù)渲R(shí)來(lái)確定。由于確定性網(wǎng)絡(luò)中間節(jié)點(diǎn)是通過(guò)固定鏈路連接的，鏈路拓?fù)鋭?dòng)態(tài)變化表現(xiàn)在鏈路權(quán)值的波動(dòng)，不存在節(jié)點(diǎn)移動(dòng)和鏈路斷路的情況，那么在不穩(wěn)定網(wǎng)絡(luò)拓?fù)渲芯幋a節(jié)點(diǎn)不斷變化，隨機(jī)線性網(wǎng)絡(luò)編碼構(gòu)造算法更能發(fā)揮優(yōu)勢(shì)；而確定線性網(wǎng)絡(luò)編碼構(gòu)造算法的編碼節(jié)點(diǎn)位置是確定的，適用于網(wǎng)絡(luò)狀態(tài)較穩(wěn)定的組播通信，其所需運(yùn)算空間更小、運(yùn)算量更少。

線性網(wǎng)絡(luò)編碼在國(guó)內(nèi)外已經(jīng)得到了廣泛深入的研究，文獻(xiàn)[5]基于線性編碼找到了計(jì)算最大組播容量的分布式算法；王龍翔[8]在組播率小于組播容量的前提下，提出了有線網(wǎng)絡(luò)編碼路由算法；文獻(xiàn)[9]涉及了靜態(tài)多播連接時(shí)構(gòu)造最小代價(jià)子圖算法。然后研究者們又從網(wǎng)絡(luò)拓?fù)淙胧郑岢隽硕喾N網(wǎng)絡(luò)編碼算法：文獻(xiàn)[10]提出了一種基于向量空間正交補(bǔ)的確定線性網(wǎng)絡(luò)編碼構(gòu)造算法，該算法相對(duì)復(fù)雜需要消耗較長(zhǎng)時(shí)間，適用在網(wǎng)絡(luò)拓?fù)浞€(wěn)定的情況下；文獻(xiàn)[11]在基于網(wǎng)絡(luò)編碼的多路徑分簇路由算法的基礎(chǔ)上，提出了一種分布式隨機(jī)網(wǎng)絡(luò)編碼算法，該算法適用于拓?fù)渥兓l繁的分布式網(wǎng)絡(luò)中；文獻(xiàn)[12]針對(duì)網(wǎng)絡(luò)拓?fù)湮粗那闆r提出了一種基于信宿反饋的確定線性網(wǎng)絡(luò)編碼構(gòu)造(Sink Nodes Feedback Deterministic Network Coding, SNFDNC)算法，該算法需要進(jìn)行多次試播來(lái)確定編碼方案，網(wǎng)絡(luò)編碼收斂時(shí)間較長(zhǎng)；文獻(xiàn)[13]提出了一種基于網(wǎng)絡(luò)編碼的分布式衛(wèi)星路由算法和一種基于機(jī)會(huì)搜尋的隨機(jī)網(wǎng)絡(luò)編碼構(gòu)造算法，并將兩種算法相結(jié)合實(shí)現(xiàn)了隨機(jī)的網(wǎng)絡(luò)編碼組播通信；隨后文獻(xiàn)[14]在基于網(wǎng)絡(luò)編碼的多路徑分簇路由算法的基礎(chǔ)上，提出了一種分布式隨機(jī)網(wǎng)絡(luò)編碼算法，該算法擴(kuò)展性強(qiáng)，可成功移植到組播路由算法中，但由于該算法運(yùn)用隨機(jī)線性網(wǎng)絡(luò)編碼構(gòu)造方案，所以不能充分利用帶寬資源且運(yùn)算量過(guò)大。

近年來(lái)，關(guān)于網(wǎng)絡(luò)編碼的研究已經(jīng)從單源組播通信[2-4]過(guò)渡到了多源組播通信，文獻(xiàn)[15-17]通過(guò)引入虛擬信源的方法對(duì)一般多源組播問(wèn)題的網(wǎng)絡(luò)容量進(jìn)行研究，提高了鏈路吞吐量和組播系統(tǒng)的穩(wěn)定性，但是算法復(fù)雜度普遍較高，使得收斂時(shí)間過(guò)長(zhǎng)。其中：文獻(xiàn)[15]提出了一種基于埃德蒙茲最大流的公平分層組播網(wǎng)絡(luò)編碼構(gòu)造算法，通過(guò)運(yùn)用多項(xiàng)式復(fù)雜度啟發(fā)式方案來(lái)確保信宿接收信息的可解碼性，但該算法需要反復(fù)尋找信源到信宿之間的增廣路徑，需要較長(zhǎng)運(yùn)算時(shí)間，只有在較大規(guī)模的網(wǎng)絡(luò)拓?fù)渲胁拍馨l(fā)揮其優(yōu)勢(shì)；文獻(xiàn)[16]將網(wǎng)絡(luò)編碼分層組播應(yīng)用于多媒體點(diǎn)對(duì)多點(diǎn)的資源分配中，通過(guò)多速率傳輸策略實(shí)現(xiàn)了網(wǎng)絡(luò)拓?fù)渲懈鲗酉滦墟溌窂V播分組數(shù)的最小化，然而文中沒(méi)有給出用于分配各層數(shù)據(jù)所需鏈路帶寬的方案，導(dǎo)致網(wǎng)絡(luò)帶寬利用率較低；文獻(xiàn)[17]為了降低網(wǎng)絡(luò)延遲，提高網(wǎng)絡(luò)傳輸效率，提出了一種最小化網(wǎng)絡(luò)延遲的編碼感知傳輸調(diào)度算法，其有效性在實(shí)驗(yàn)中得到了驗(yàn)證，并為路由和編碼的聯(lián)合設(shè)計(jì)提供了更多可能性；文獻(xiàn)[18]提出一種基于多源組播的獨(dú)立安全網(wǎng)絡(luò)編碼方案，保證了多播網(wǎng)絡(luò)的安全性和可靠性，使大容量網(wǎng)絡(luò)拓?fù)涞男纬沙杀居兴档?，但該方案需要評(píng)估所有可能潛在的網(wǎng)絡(luò)拓?fù)?，因此需要很高的?jì)算復(fù)雜度。

在基于網(wǎng)絡(luò)編碼的多源組播通信情形下，首先需要運(yùn)用組播路由算法來(lái)確定路由方案；然后選取合適的網(wǎng)絡(luò)編碼構(gòu)造算法來(lái)確定編碼方案。文獻(xiàn)[12]提出了一種基于信宿反饋的確性定網(wǎng)絡(luò)編碼構(gòu)造(SNFDNC)算法，該算法在單源組播問(wèn)題上，可以通過(guò)試播法確定組播容量和編碼方案，試播過(guò)程中均采用隨機(jī)線性網(wǎng)絡(luò)編碼方案。本文延續(xù)了文獻(xiàn)[12]的基本思想，針對(duì)以上文獻(xiàn)提到的網(wǎng)絡(luò)編碼算法的不足，以在鏈路狀態(tài)可變的確定性網(wǎng)絡(luò)中實(shí)現(xiàn)高效組播通信為目的，提出了一種可動(dòng)態(tài)調(diào)整各編碼節(jié)點(diǎn)局部編碼向量的確定線性網(wǎng)絡(luò)編碼逐層構(gòu)造算法(Deterministic Layered Structure algorithm based on Network Coding， DLSNC)。該算法只需通過(guò)一次虛擬試播即可由上到下逐層重構(gòu)變換節(jié)點(diǎn)的局部編碼向量，同時(shí)允許對(duì)輸入數(shù)據(jù)冗余鏈路進(jìn)行修剪枝，最終產(chǎn)生可行的局部編碼向量方案，保證信宿成功解碼。通過(guò)仿真測(cè)試證實(shí)：本文算法進(jìn)一步提高了多源組播通信的平均傳輸速率，收斂時(shí)間更短，并提高了網(wǎng)絡(luò)帶寬利用率。

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

1.1 網(wǎng)絡(luò)編碼多源組播原理

假設(shè)一個(gè)多源組播網(wǎng)絡(luò)用有向無(wú)環(huán)二元組G(V,E)表示，V和E分別表示有限節(jié)點(diǎn)集和有限鏈路集，鏈路集為編碼節(jié)點(diǎn)間的有向鏈路。設(shè)S={S1,S2,…,Sn}為各組播源點(diǎn)的集合,T={T1,T2,…,Td}為各信宿點(diǎn)的集合，在有向圖中標(biāo)記輸入節(jié)點(diǎn)vi的鏈路集為ΓI(vi)，輸出節(jié)點(diǎn)vi的鏈路集為ΓO(vi)，用|ΓI(vi)|和|ΓO(vi)|分別表示節(jié)點(diǎn)vi的入度和出度。在多源組播通信中，應(yīng)該使組播率在不大于組播容量的前提下無(wú)限接近組播容量，編碼節(jié)點(diǎn)可通過(guò)對(duì)輸入信息進(jìn)行編碼來(lái)使組播容量等于理論上的最大流[19]。通常選取|ΓI(vi)|大于|ΓO(vi)|的節(jié)點(diǎn)為編碼節(jié)點(diǎn)，其輸出信道都有各自對(duì)應(yīng)的編碼器來(lái)存儲(chǔ)編碼向量，并對(duì)輸入信息進(jìn)行編碼[20]，編碼器個(gè)數(shù)為|ΓO(vi)|。設(shè)d為編碼節(jié)點(diǎn)v的輸入鏈路，e為其輸出鏈路，輸入信息向量為y(d)，輸出編碼信息向量y(e)，y(d)與y(e)的關(guān)系如式(1)所示；輸入全局編碼向量為g(d)與輸出的全局編碼向g(e)的關(guān)系如式(2)所示:

(1)

(2)

其中：mde構(gòu)成了輸出鏈路e的局部編碼向量，用m(e)表示，即：m(e)={mde∈GF(2m):d∈In[tail(e)]}，其中m(e)的維數(shù)等于節(jié)點(diǎn)vi的輸入鏈路數(shù)。

經(jīng)過(guò)任一編碼節(jié)點(diǎn)的輸出信息向量均可看作是信源所發(fā)送信息的線性組合，該線性組合的系數(shù)就是編碼節(jié)點(diǎn)輸出鏈路e的全局編碼向量。

1.2 伽羅華域

在伽羅華域GF(2m)中，m代表伽羅華域的次數(shù)，由既約多項(xiàng)式確定[5]，q=2m代表伽羅華域的階數(shù)，由于在固定伽羅華域中字符都是有限個(gè)相同數(shù)目的二進(jìn)制字符串，這樣計(jì)算較為方便，所以本文中確定線性網(wǎng)絡(luò)編碼運(yùn)算都是在伽羅華域環(huán)境下進(jìn)行的。令多源組播網(wǎng)絡(luò)中的組播率為h，每個(gè)信道上傳輸?shù)臄?shù)據(jù)塊長(zhǎng)度為L(zhǎng)個(gè)字符，因?yàn)椴捎玫馁ち_華域?yàn)镚F(2m)，則每個(gè)字符均為m比特的二進(jìn)制數(shù)，那么組播通信一次數(shù)據(jù)傳輸?shù)男畔⒘繛閙Lh比特。

在基于網(wǎng)絡(luò)編碼的組播通信中，無(wú)論是隨機(jī)線性網(wǎng)絡(luò)編碼還是確定線性網(wǎng)絡(luò)編碼，數(shù)據(jù)包的數(shù)據(jù)字段都需要在編碼節(jié)點(diǎn)進(jìn)行字符間的編碼運(yùn)算[21]，在伽羅華域中加法運(yùn)算與減法運(yùn)算相當(dāng)于異或運(yùn)算；乘法運(yùn)算首先是將二進(jìn)制多項(xiàng)式相乘，然后在合并同類(lèi)項(xiàng)系數(shù)時(shí)同樣采用異或運(yùn)算；除法運(yùn)算則是乘法的逆運(yùn)算。網(wǎng)絡(luò)編碼時(shí)就是在執(zhí)行乘法運(yùn)算過(guò)程中將系數(shù)進(jìn)行模2加后，對(duì)形成的多項(xiàng)式進(jìn)行多次降次，直到其最高次數(shù)小于m，那么該多項(xiàng)式的系數(shù)就是對(duì)應(yīng)字符的相應(yīng)位。文獻(xiàn)[5]證明了在伽羅華域上加減、乘法、除法的運(yùn)算量分別為m、3m2和3m2+m3/3，依次用α(m)，β(m)和χ(m)表示。在整個(gè)編碼過(guò)程中，編碼節(jié)點(diǎn)v的輸入鏈路個(gè)數(shù)為|ΓI(v)|，輸出鏈路個(gè)數(shù)為|ΓO(v)|，則每個(gè)輸出信息向量分別需要進(jìn)行|ΓI(v)|次乘法和|ΓO(v)|次加法，文獻(xiàn)[5]也給出了編碼節(jié)點(diǎn)v應(yīng)用確定線性網(wǎng)絡(luò)編碼和隨機(jī)線性網(wǎng)絡(luò)編碼的運(yùn)算量，如式(3)和式(4)所示，確定線性網(wǎng)絡(luò)編碼和隨機(jī)線性網(wǎng)絡(luò)編碼信宿節(jié)點(diǎn)T解碼的運(yùn)算量如式(5)和式(6)所示，可見(jiàn)確定線性網(wǎng)絡(luò)編碼的運(yùn)算量遠(yuǎn)小于隨機(jī)線性網(wǎng)絡(luò)編碼。本文提出的SNFDNC算法，就是在已知路由方案的網(wǎng)絡(luò)拓?fù)渲杏么_定線性網(wǎng)絡(luò)編碼為編碼節(jié)點(diǎn)選取適當(dāng)?shù)木幋a系數(shù)后，對(duì)多個(gè)輸入數(shù)據(jù)流進(jìn)行多項(xiàng)式乘法并執(zhí)行異或運(yùn)算的過(guò)程。

τ(v)=L[α(m)+β(m)]|ΓI(v)||ΓO(v)|

(3)

τ(v)=(L+h)[α(m)+β(m)]|In(v)||Out(v)|

(4)

τ(T)=Lh2[α(m)+β(m)]

(5)

τ(T)=(Lh2+4h3/3)[α(m)+β(m)]+hχ(m)

(6)

在多源組播中，一次完整的數(shù)據(jù)傳輸是指：數(shù)據(jù)包從一個(gè)組播源發(fā)出后，要經(jīng)過(guò)多個(gè)中間節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)編碼，然后傳入信宿節(jié)點(diǎn)進(jìn)行解碼，直到最后一個(gè)組播信宿成功解碼的過(guò)程，所以多源組播的一次數(shù)據(jù)傳輸延遲等于所有組播源中一次數(shù)據(jù)傳輸延遲的最大值。確定線性網(wǎng)絡(luò)編碼和隨機(jī)線性網(wǎng)絡(luò)編碼組播一次群的運(yùn)算延遲如式(7)和式(8)所示，確定線性網(wǎng)絡(luò)編碼延遲更短。通過(guò)分析得出影響運(yùn)算延遲的因素僅與數(shù)據(jù)信息字符長(zhǎng)度L和伽羅華域的階數(shù)m有關(guān)[5]。

τ=L(w+h2)(3m2+m)

(7)

(8)

2 逐層構(gòu)造網(wǎng)絡(luò)編碼方案

2.1 方案的理論依據(jù)

源點(diǎn)單位時(shí)間傳遞信息的速率稱(chēng)為組播率，最大組播率即為組播容量，它等于信源到信宿容量函數(shù)的最小值，也就是信源到信宿的最小割值[22]。在已知網(wǎng)絡(luò)拓?fù)涞亩嘣唇M播網(wǎng)絡(luò)G(V,E)中，信源集合為S=(S1,S2,…,Sn)，且各源點(diǎn)相互獨(dú)立，信宿集合為T(mén)=(T1,T2,…,Td)，其中n>1，d>1。令z∈T，且?D?S，記min-c(D,z)為信源集合D與信宿點(diǎn)z的最小割值，那么m-f(D,T)為信源集合D與每個(gè)信宿點(diǎn)最小割值的最小值，也就是信源集D到信宿集T的最大流，如式(9)所示。在多源組播網(wǎng)絡(luò)拓?fù)渲屑尤胍粋€(gè)虛擬信源S′后，m-f(D,T)用m-f(S′,T)表示。

(9)

網(wǎng)絡(luò)拓?fù)渲忻織l鏈路的鏈路容量可用該鏈路的最大傳輸速率來(lái)表示，若鏈路容量為C，C大于1且C為正整數(shù)，則該鏈路可看作是由C條鏈路容量為1的信道構(gòu)成。

定理1 在多源組播網(wǎng)絡(luò)拓?fù)渲?，如果虛擬信源和各組播源點(diǎn)只采用路由方式傳遞信息并不進(jìn)行編碼，且每個(gè)源點(diǎn)需傳輸信息到全部信宿點(diǎn)，設(shè)各個(gè)源點(diǎn)的組播率分別為h1,h2,…,hn，那么當(dāng)S′的組播容量與其輸出信道數(shù)關(guān)系滿(mǎn)足式(10)，S′的組播率h與各個(gè)源點(diǎn)的組播率關(guān)系滿(mǎn)足式(11)時(shí)，則一定可以找到一個(gè)可行的網(wǎng)絡(luò)編碼方案[20]。

m-f(S′,T) = |Out(S′)|

(10)

(11)

證明 由式(9)可證式(10)成立。又因?yàn)樘摂M信源和實(shí)際信源只進(jìn)行數(shù)據(jù)傳輸不進(jìn)行編碼，所以用虛擬信源代替實(shí)際信源時(shí)，只需令虛擬信源信道數(shù)等于各信源信道數(shù)之和即可。而且每個(gè)源點(diǎn)需要傳輸信息至全部宿點(diǎn)，那么通過(guò)調(diào)整各編碼節(jié)點(diǎn)的局部編碼向量使每個(gè)信宿點(diǎn)接收到滿(mǎn)秩的全局編碼矩陣則代表編碼成功，證明原理如圖1所示。

組播網(wǎng)絡(luò)通過(guò)組播路由算法生成組播路由方案確定了編碼節(jié)點(diǎn)的位置，但是在數(shù)據(jù)傳輸?shù)恼麄€(gè)過(guò)程中，網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化會(huì)引起路由方案的變動(dòng)(主要體現(xiàn)在鏈路權(quán)值的變化)，這就需要重構(gòu)信道的局部編碼向量來(lái)形成一個(gè)新的可行編碼方案。

圖1 虛擬信源示意圖 Fig. 1 Schematic diagram of virtual source

確定線性網(wǎng)絡(luò)編碼可以在網(wǎng)絡(luò)拓?fù)湟阎那疤嵯拢捎眉蟹椒?gòu)造網(wǎng)絡(luò)編碼方案[23],通過(guò)調(diào)整部分編碼節(jié)點(diǎn)的局部編碼向量使每個(gè)節(jié)點(diǎn)收到的全局編碼矩陣滿(mǎn)秩，保證每個(gè)信宿獲得的解碼矩陣可以成功解碼。

定義1 在已知全局網(wǎng)絡(luò)拓?fù)涞那疤嵯?，采用確定性網(wǎng)絡(luò)編碼，以給定組播率由上而下逐層進(jìn)行局部編碼向量的構(gòu)造，數(shù)據(jù)傳輸過(guò)程中采用這些編碼向量進(jìn)行編碼運(yùn)算，則稱(chēng)為確定線性網(wǎng)絡(luò)編碼逐層構(gòu)造策略。

定義2 虛擬源點(diǎn)發(fā)送的數(shù)據(jù)包逐層經(jīng)過(guò)編碼節(jié)點(diǎn)，同時(shí)每層節(jié)點(diǎn)將其收到的全局編碼矩陣反饋給上層與之相關(guān)的編碼節(jié)點(diǎn)，直到信宿完成反饋，該過(guò)程稱(chēng)為一次虛擬試播[12]。

由于在虛擬試播階段只需要考察各節(jié)點(diǎn)接收到的全局編碼矩陣，而并不需要考察其接收到的數(shù)據(jù)信息，所以試播虛擬矩陣即可。因?yàn)樘摂M信源組播率為h，所以要發(fā)送h×h階試播矩陣，實(shí)驗(yàn)包結(jié)構(gòu)中的數(shù)據(jù)段可以忽略不進(jìn)行傳遞，其格式如圖2所示。

圖2 實(shí)驗(yàn)包結(jié)構(gòu) Fig. 2 Structure of test package

定理2 虛擬試播過(guò)程中，如果虛擬信源的試播矩陣以及中間節(jié)點(diǎn)的全局編碼矩陣是滿(mǎn)秩的，那么一定存在可行的線性網(wǎng)絡(luò)編碼方案。

證明 令虛擬信源在一個(gè)時(shí)隙T內(nèi)發(fā)出h個(gè)數(shù)據(jù)包，它們包含h個(gè)原始信息向量和h個(gè)全局編碼向量，設(shè)每個(gè)信息向量長(zhǎng)度為L(zhǎng)字符，便構(gòu)成了L×h階原始信息矩陣Aorig。在傳遞過(guò)程中，信息需要經(jīng)過(guò)中間節(jié)點(diǎn)進(jìn)行編碼，即對(duì)h個(gè)虛擬信源的全局編碼向量進(jìn)行線性組合生成新的全局編碼向量，最終每個(gè)信宿Ti都會(huì)接收到一個(gè)h×h階全局編碼矩陣B以及L行h列的編碼信息矩陣Y。而通常為了保障網(wǎng)絡(luò)編碼的安全性，需要用h×h階的信源加密矩陣G對(duì)原始信息進(jìn)行加密處理，最終得到網(wǎng)絡(luò)編碼矩陣變換公式如(12)所示，解碼公式如(13)所示:

AorigGB=Y

(12)

Aorig=[(AorigG)B](GB)-1

(13)

本文進(jìn)行試播時(shí)無(wú)需對(duì)信息進(jìn)行傳遞，所以可將試播矩陣近似看成加密矩陣G，由矩陣論知識(shí)得出：只有保證試播矩陣G和全局編碼矩陣B滿(mǎn)秩，才能形成可行的線性網(wǎng)絡(luò)編碼方案，成功恢復(fù)出原始信息矩陣Aorig。

定理3 試播矩陣的選取是隨機(jī)的，令M1是n×n階對(duì)角線以下元素都是0的上三角矩陣，M2是n×n階對(duì)角線以上元素都是0的下三角矩陣，M1和M2的對(duì)角線都是非零元素，那么M1×M2便可得到滿(mǎn)秩的試播矩陣G。

證明 因?yàn)镸1是上三角矩陣，M2是下三角矩陣，同時(shí)二者的對(duì)角線都是非零元素，所以矩陣M1和M2是滿(mǎn)秩矩陣，那么兩個(gè)滿(mǎn)秩矩陣相乘得到的矩陣也是滿(mǎn)秩的，即試播矩陣滿(mǎn)秩。試播矩陣的確定就是按照定理3的方法，在伽羅華域中隨機(jī)選取的。

2.2 逐層構(gòu)造網(wǎng)絡(luò)編碼算法

本文通過(guò)虛擬試播運(yùn)用確定線性網(wǎng)絡(luò)編碼逐層構(gòu)造策略進(jìn)行局部編碼向量可行方案的確定。由定理3可知：只要在伽羅華域GF(2m)上隨機(jī)選取元素構(gòu)成矩陣M1和M2即可確定試播矩陣，由于網(wǎng)絡(luò)編碼對(duì)編碼節(jié)點(diǎn)的運(yùn)算能力和存儲(chǔ)空間有較高要求[22]，所以本文為了計(jì)算方便，試播矩陣選用h×h階的單位矩陣E，這樣輸入節(jié)點(diǎn)vi的編碼信息就等于一個(gè)由舊全局編碼向量組成的L×|ΓI(vi)|階矩陣，如式(14)所示，那么輸出到鏈路e的信息向量等于輸入信息向量與編碼節(jié)點(diǎn)vi的局部編碼向量之積，也就是編碼節(jié)點(diǎn)vi新生成的全局編碼向量，如式(15)所示，最后信宿節(jié)點(diǎn)收到的編碼信息矩陣C就是其全局編碼矩陣B。

[L×|ΓI(vi)|]=E×[h×|ΓI(vi)|]=

[h×|ΓI(vi)|]

(14)

y(e)=[h×|ΓI(vi)|]×(c1,c2,…,c|ΓI(vi)|)T=g(e)

(15)

定義3 在確定局部編碼向量可行方案時(shí)，用Mij表示輸入節(jié)點(diǎn)vij的全局編碼矩陣，用RM表示Mij的秩，用p代表每層獲得非滿(mǎn)秩全局編碼矩陣的節(jié)點(diǎn)個(gè)數(shù)。若Mij非滿(mǎn)秩，則需改變vij的上層編碼節(jié)點(diǎn)的局部編碼向量，以確保矩陣Mij滿(mǎn)秩，稱(chēng)符合變換要求的第i-1層的編碼節(jié)點(diǎn)為潛在變換節(jié)點(diǎn)，其數(shù)目記為q；稱(chēng)潛在變換節(jié)點(diǎn)中改變了局部編碼向量的編碼節(jié)點(diǎn)為變換節(jié)點(diǎn)。

在已知路由方案的情況下，多源組播網(wǎng)絡(luò)采用線性網(wǎng)絡(luò)編碼方法傳遞數(shù)據(jù)，設(shè)共有f層網(wǎng)絡(luò)節(jié)點(diǎn)，f=1代表組播源點(diǎn)集，源點(diǎn)不進(jìn)行編碼，k為同層編碼節(jié)點(diǎn)總數(shù)，vij表示第i層第j個(gè)編碼節(jié)點(diǎn)，其中i和j的取值都為正整數(shù)且2≤i≤f,0≤j≤k，信宿為第f層編碼節(jié)點(diǎn)。在試播過(guò)程中，vij的輸入鏈路數(shù)與輸出鏈路數(shù)分別為|ΓI(vij)|、|ΓO(vij)|，當(dāng)p>0時(shí)，需要改變與vij對(duì)應(yīng)的變換節(jié)點(diǎn)的局部編碼向量以確保vij得到的全局編碼矩陣滿(mǎn)秩。

定義4 在數(shù)據(jù)傳輸過(guò)程中，當(dāng)編碼節(jié)點(diǎn)的部分輸入鏈路無(wú)法為網(wǎng)絡(luò)編碼提供有用數(shù)據(jù)時(shí)，則對(duì)其進(jìn)行修剪，該過(guò)程稱(chēng)為修剪枝。

例如多條鏈路傳送相同或線性相關(guān)信息到同一編碼節(jié)點(diǎn)時(shí)，便可對(duì)其中部分鏈路進(jìn)行修剪。在網(wǎng)絡(luò)編碼時(shí)進(jìn)行修剪枝，可以減少數(shù)據(jù)冗余，避免鏈路復(fù)用，從而提高網(wǎng)絡(luò)帶寬利用率。

在進(jìn)行統(tǒng)計(jì)各層獲得非滿(mǎn)秩全局編碼矩陣節(jié)點(diǎn)個(gè)數(shù)時(shí)，采用了決策樹(shù)算法[24]。決策樹(shù)是一類(lèi)常見(jiàn)的機(jī)器學(xué)習(xí)方法，它以一種樹(shù)形結(jié)構(gòu)對(duì)樣本進(jìn)行分類(lèi)，其中每個(gè)節(jié)點(diǎn)代表一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉節(jié)點(diǎn)代表一種類(lèi)別。其中C5.0決策樹(shù)算法[24]有著非常好的泛化能力和魯棒性，可以對(duì)訓(xùn)練樣本中“變化”和“未變化”的樣本進(jìn)行高度識(shí)別與區(qū)分，最終得到正確分類(lèi)。

本文在網(wǎng)絡(luò)拓?fù)浒l(fā)生動(dòng)態(tài)變化后，就是利用C5.0決策樹(shù)算法自動(dòng)提取檢測(cè)網(wǎng)絡(luò)拓?fù)渲懈鲗庸?jié)點(diǎn)的編碼矩陣，然后對(duì)編碼節(jié)點(diǎn)進(jìn)行重新分類(lèi)的，其中一類(lèi)是獲得滿(mǎn)秩全局編碼矩陣的節(jié)點(diǎn)；另一類(lèi)是獲得非滿(mǎn)秩全局編碼矩陣的節(jié)點(diǎn)。同時(shí)，C5.0決策樹(shù)算法還可以對(duì)各類(lèi)樣本的數(shù)目進(jìn)行統(tǒng)計(jì)。該算法將網(wǎng)絡(luò)拓?fù)渲兴泄?jié)點(diǎn)作為訓(xùn)練樣本集，通過(guò)訓(xùn)練會(huì)具有很好的泛化能力，所以可快速準(zhǔn)確地找到變換和未變換的樣本。本文需要統(tǒng)計(jì)的是各層未獲得滿(mǎn)秩全局編碼矩陣的節(jié)點(diǎn)，其數(shù)目用p表示。

1)當(dāng)p=0時(shí)，證明第i層編碼節(jié)點(diǎn)全部得到了滿(mǎn)秩的全局編碼矩陣，則跳到第i+1層繼續(xù)判斷。

2)當(dāng)p>0時(shí)，證明第i層存在p個(gè)編碼節(jié)點(diǎn)得到了非滿(mǎn)秩全局編碼矩陣，接下來(lái)查找這些編碼節(jié)點(diǎn)的上層潛在變換節(jié)點(diǎn)數(shù)q：

① 當(dāng)q=|ΓI(Vij)|-RMij時(shí)，令q個(gè)潛在變換節(jié)點(diǎn)全部成為變換節(jié)點(diǎn)。

② 當(dāng)q>|ΓI(Vij)|-RMij時(shí)，首先進(jìn)行潛在變換節(jié)點(diǎn)優(yōu)先級(jí)的判定，即編碼節(jié)點(diǎn)的輸入鏈路數(shù)目越少，其重構(gòu)局部編碼向量的運(yùn)算量越低，優(yōu)先級(jí)越高。通過(guò)優(yōu)先級(jí)判定從q個(gè)潛在變換節(jié)點(diǎn)中選出|ΓI(Vij)|-RMij個(gè)變換節(jié)點(diǎn)，若優(yōu)先級(jí)相同，則任選其一即可。

③ 當(dāng)q<|ΓI(Vij)|-RMij時(shí)，令q個(gè)潛在變換節(jié)點(diǎn)都為變換節(jié)點(diǎn)的同時(shí)要對(duì)組播路由方案進(jìn)行修剪枝，去掉與該編碼節(jié)點(diǎn)相連的|ΓI(Vij)|-RMij-q條相關(guān)上游鏈路，也就是修剪掉數(shù)據(jù)冗余鏈路，減少網(wǎng)絡(luò)開(kāi)銷(xiāo)，提高帶寬利用率。

本文以一個(gè)已經(jīng)確定了組播路由方案的18節(jié)點(diǎn)無(wú)向圖來(lái)展示確定線性網(wǎng)絡(luò)編碼逐層構(gòu)造算法的原理，如圖3所示，設(shè)入度大于1的網(wǎng)絡(luò)節(jié)點(diǎn)可以作為編碼節(jié)點(diǎn)，初始局部編碼向量組成全部默認(rèn)為1，組播信宿數(shù)|T|=4，有4層網(wǎng)絡(luò)節(jié)點(diǎn)(虛擬信源不參與計(jì)數(shù))，用f=4表示。

圖3中引入了虛擬信源S′，試播矩陣為4×4階的單位矩陣，S1=(1 0 0 0)T，S2=( 0 1 0 0)T，S3=( 0 0 1 0)T，S4=( 0 0 0 1)T。下面對(duì)確定線性網(wǎng)絡(luò)編碼逐層構(gòu)造算法進(jìn)行舉例說(shuō)明，在信宿層節(jié)點(diǎn)通過(guò)決策樹(shù)算法得知信宿點(diǎn)T2全局編碼矩陣的秩為3，未獲得滿(mǎn)秩全局編碼矩陣，所以要重構(gòu)其上層變換節(jié)點(diǎn)V2.1的局部編碼向量，最終使信宿點(diǎn)T2獲得滿(mǎn)秩的全局編碼矩陣，如式(16)所示：

(16)

在圖3中還可以看到算法對(duì)編碼節(jié)點(diǎn)V2.5的輸入鏈路進(jìn)行了修剪枝，因?yàn)樗妮斎肴志幋a矩陣的秩小于輸入鏈路數(shù)目，是非滿(mǎn)秩矩陣，它的上層潛在變換節(jié)點(diǎn)數(shù)為0，所以要對(duì)其進(jìn)行修剪枝，減少鏈路冗余，提高網(wǎng)絡(luò)帶寬。編碼節(jié)點(diǎn)的輸出鏈路對(duì)應(yīng)著各自的編碼器，在確定變換節(jié)點(diǎn)后，需要重構(gòu)其相應(yīng)輸出鏈路編碼器的編碼系數(shù)，從而生成新的編碼向量，直至同層所有變換節(jié)點(diǎn)完成了局部編碼向量的重構(gòu)，再將新生成的編碼向量重新輸入到各自對(duì)應(yīng)的第i層的p個(gè)編碼節(jié)點(diǎn)。然后，這些編碼節(jié)點(diǎn)再次計(jì)算各自的輸入全局編碼矩陣是否滿(mǎn)秩，循環(huán)至p=0便進(jìn)入到下一層編碼節(jié)點(diǎn)的局部編碼向量構(gòu)造。重復(fù)以上操作，直到信宿層的全局編碼矩陣Bi滿(mǎn)秩，即編碼成功。

圖3 DLSNC原理示意圖 Fig. 3 Schematic diagram of DLSNC

2.3 逐層構(gòu)造網(wǎng)絡(luò)編碼算法流程

算法描述：

步驟1 算法初始化。

步驟2 虛擬信源發(fā)送試播矩陣，同層編碼節(jié)點(diǎn)開(kāi)始編碼，各編碼節(jié)點(diǎn)為其輸出信道產(chǎn)生全局編碼向量，按式(15)計(jì)算出輸出信道全局編碼向量并轉(zhuǎn)發(fā)實(shí)驗(yàn)包。

步驟3 運(yùn)用決策樹(shù)算法標(biāo)記出p個(gè)第i層獲得非滿(mǎn)秩全局編碼矩陣的編碼節(jié)點(diǎn)vij,若p=0，層數(shù)i自加并跳轉(zhuǎn)到下一層編碼節(jié)點(diǎn)，若p>0，需要調(diào)整vij的上層變換節(jié)點(diǎn)編碼向量。

步驟4 當(dāng)p>0時(shí)，標(biāo)記與編碼節(jié)點(diǎn)vij對(duì)應(yīng)的第i-1層潛在變換節(jié)點(diǎn)位置，并計(jì)數(shù)為q。

1)當(dāng)q=|ΓI(Vij)|-RMij時(shí)，令q個(gè)潛在變換節(jié)點(diǎn)全部成為變換節(jié)點(diǎn)；

2)當(dāng)q>|ΓI(Vij)|-RMij時(shí)，進(jìn)行潛在變換節(jié)點(diǎn)優(yōu)先級(jí)的判定，確定變換節(jié)點(diǎn)；

3)當(dāng)q<|ΓI(Vij)|-RMij時(shí)，令q個(gè)潛在變換節(jié)點(diǎn)都為變換節(jié)點(diǎn)并進(jìn)行修剪枝。

步驟5 確定變換節(jié)點(diǎn)后，調(diào)整其局部編碼向量，將新生成的全局編碼向量再次傳入編碼節(jié)點(diǎn)vij，不斷循環(huán)，直到使vij輸入鏈路的全局編碼向量滿(mǎn)秩。

步驟6 Untilp=0。

步驟7i+1→i。

步驟8 Untili=f。

步驟9 最終得到局部編碼向量可行方案，算法結(jié)束。

2.4 算法復(fù)雜度分析

通過(guò)上述算法可以得到確定性網(wǎng)絡(luò)編碼方案，用鄰接鏈表表示網(wǎng)絡(luò)拓?fù)洌肧teiner樹(shù)可以實(shí)現(xiàn)總代價(jià)最小分布樹(shù)的方法來(lái)保證網(wǎng)絡(luò)鏈路開(kāi)銷(xiāo)最小。在隨機(jī)線性網(wǎng)絡(luò)編碼構(gòu)造算法中，編碼節(jié)點(diǎn)的編碼系數(shù)是隨機(jī)選取的，而在確定性網(wǎng)絡(luò)編碼方案中需要通過(guò)計(jì)算得到編碼節(jié)點(diǎn)的編碼系數(shù)。本文算法只需進(jìn)行一次虛擬試播，設(shè)虛擬信源的組播率為h，Vc為編碼節(jié)點(diǎn)，D為Steiner節(jié)點(diǎn)，則算法的整個(gè)復(fù)雜度表示為O[|Vc||D|h(|D|+h)]。

3 仿真測(cè)試

本文仿真實(shí)驗(yàn)環(huán)境為Dell PC，處理器為Intel Core- M480 I5 CPU @2.67 GHz、4 GB內(nèi)存，操作系統(tǒng)為32位Windows 7系統(tǒng)，安裝并使用了VC++6.0、CygWin、Matlab R2011b和NS2-allinone2.26軟件。

對(duì)已知組播路由方案的多源組播網(wǎng)絡(luò)進(jìn)行仿真測(cè)試，實(shí)驗(yàn)環(huán)境為NS2自帶的拓?fù)渖晒ぞ逩T-ITM生成的K均值聚類(lèi)Waxman隨機(jī)拓?fù)淠Ｐ汀狵RTG(Random Topology Generate algorithm based onK-means)[25],通過(guò)在KRTG模型中設(shè)置節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)范圍、鏈路帶寬、鏈路長(zhǎng)邊與短邊等參數(shù)來(lái)形成不同規(guī)模的網(wǎng)絡(luò)拓?fù)?。其基本原理是將設(shè)制的n個(gè)節(jié)點(diǎn)均勻分布在擁有最大距離上限的平面上，節(jié)點(diǎn)間生成鏈路的概率如式(17)所示：

(17)

其中：|V|表示節(jié)點(diǎn)總數(shù)；D為節(jié)點(diǎn)平均度；d(u,v)表示節(jié)點(diǎn)u與v之間的歐氏距離；α表示隨機(jī)網(wǎng)絡(luò)中長(zhǎng)距離鏈路數(shù)與短距離鏈路數(shù)的比值，它是取自(0,1]的實(shí)數(shù)；L表示所有節(jié)點(diǎn)的最大距離上限。本實(shí)驗(yàn)將L設(shè)置為100 km，把α設(shè)置為0.18，D設(shè)置為5，使其更符合現(xiàn)實(shí)中的確定性網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，使用KRTG模型避免了生成的連通圖相鄰節(jié)點(diǎn)距離過(guò)近的現(xiàn)象，使節(jié)點(diǎn)分布均勻且疏密得當(dāng)，同時(shí)選擇合適的組播路由算法生成多源組播路由方案，以提供網(wǎng)絡(luò)編碼構(gòu)造算法的運(yùn)行環(huán)境 。

3.1 算法有效性測(cè)試

在隨機(jī)性構(gòu)造算法中用P=(1-t/q)n表示最終生成滿(mǎn)秩的全局編碼矩陣的概率，其中t為組播信宿數(shù)，本文虛擬試播與隨機(jī)性網(wǎng)絡(luò)編碼構(gòu)造算法相似，只有q大于組播信宿t才能保證網(wǎng)絡(luò)可進(jìn)行編碼運(yùn)算，伽羅華域中q=2m表示伽羅華域的階數(shù)，m為伽羅華域的次數(shù)，可見(jiàn)本文的算法對(duì)伽羅華域的次數(shù)m有一定要求。設(shè)置m取3～9，在不同的網(wǎng)絡(luò)規(guī)模下分別仿真本文DLSNC 500次，統(tǒng)計(jì)出信宿獲得滿(mǎn)秩的全局編碼矩陣的次數(shù)，結(jié)果如表1所示。

表1 DLSNC獲得滿(mǎn)秩編碼矩陣次數(shù)(仿真500次)Tab. 1 Generation times of full rank coding matrix by DLSNC (simulating 500 times)

從表1可以看出：在節(jié)點(diǎn)數(shù)分別為100、200、300的組播路由方案中，網(wǎng)絡(luò)規(guī)模越大對(duì)伽羅華域的次數(shù)要求越高，但只要在網(wǎng)絡(luò)規(guī)模小于300，m大于等于7就能保證信宿獲得滿(mǎn)秩矩陣，所以該算法適用于中等規(guī)模的編碼網(wǎng)絡(luò)。

3.2 性能對(duì)比

為了驗(yàn)證本文算法的優(yōu)勢(shì)，在組播路由方案已知情況下，將本文算法與其他已有構(gòu)造算法進(jìn)行比較。設(shè)網(wǎng)絡(luò)規(guī)模為200個(gè)節(jié)點(diǎn)，伽羅華域的次數(shù)m依次取5～11，分別進(jìn)行10 000次實(shí)驗(yàn)，并記錄信宿接收到滿(mǎn)秩全局編碼矩陣的次數(shù)。通過(guò)表2可以發(fā)現(xiàn)：文獻(xiàn)[11]的算法和文獻(xiàn)[12]的算法與伽羅華域的次數(shù)m成正比，但是很難百分之百生成滿(mǎn)秩全局編碼矩陣；文獻(xiàn)[10]、文獻(xiàn)[15]的算法和本文算法(DLSNC)的成功率與伽羅華域次數(shù)m無(wú)關(guān)，只要伽羅華域次數(shù)滿(mǎn)足m>lbt就能進(jìn)行算法的構(gòu)造，其中t為組播信宿數(shù)。

表2 不同構(gòu)造算法獲得滿(mǎn)秩編碼矩陣次數(shù)對(duì)比(仿真10 000次)Tab. 2 Generation times comparison of full rank coding matrix by different construction algorithms (simulating 10 000 times)

接下來(lái)對(duì)本文算法與其他幾個(gè)算法在收斂時(shí)間上進(jìn)行仿真分析比較。同樣使用K均值聚類(lèi)Waxman隨機(jī)拓?fù)淠Ｐ?KRTG)，采用軟件NS2模擬多源組播數(shù)據(jù)信息的傳輸，在進(jìn)行多源組播數(shù)據(jù)的模擬前需要先在Tcl仿真腳本中設(shè)置鏈路帶寬為1.6 MB/s，傳輸?shù)臄?shù)據(jù)分組大小為1.2 MB/s的固定碼率(Constant Bit Rate, CBR)流，使其小于設(shè)置的帶寬容量，其中多余帶寬留給傳輸鏈路狀態(tài)分組[26]。物理層選用IEEE802.3u，MAC(Medium Access Control)層協(xié)議采用基帶沖突檢測(cè)的載波監(jiān)聽(tīng)多路訪問(wèn)(Carrier Sense Multiple Access with Collision Detection, CSMA/CD)技術(shù)實(shí)現(xiàn)媒體訪問(wèn)機(jī)制，采用TCP(Transmission Control Protocol)，設(shè)置時(shí)隙寬度為60 μs，調(diào)用隨機(jī)早期檢測(cè)(Random Early Detection, RED)隊(duì)列管理協(xié)議[26]，接口隊(duì)列類(lèi)型為Queue/DropTail/PriQueue，對(duì)使用網(wǎng)絡(luò)編碼的策略使用優(yōu)化網(wǎng)絡(luò)編碼協(xié)議(Network Coding optimization Scheme based on Microhabitat genetic algorithm, NCSM)。該實(shí)驗(yàn)在網(wǎng)絡(luò)規(guī)模n分別為100、175、250、325和400的情況下，分別執(zhí)行以上算法100次，并通過(guò)awk程序統(tǒng)計(jì)每次的運(yùn)行時(shí)間并求和，最后將統(tǒng)計(jì)的求和結(jié)果除以運(yùn)行總次數(shù)，就得到了每種算法在不同網(wǎng)絡(luò)規(guī)模下的平均收斂時(shí)間，最后用Matlab畫(huà)出各算法平均收斂時(shí)間與網(wǎng)絡(luò)規(guī)模關(guān)系的折線圖，結(jié)果如圖4所示。

圖4 網(wǎng)絡(luò)編碼構(gòu)造算法收斂時(shí)間對(duì)比 Fig. 4 Convergence time comparison of network coding construction algorithms

由各算法收斂時(shí)間折線圖分析得出：雖然在表2中文獻(xiàn)[10]的算法和本文算法一樣與伽羅華域次數(shù)m無(wú)關(guān)，但前者算法收斂時(shí)間較長(zhǎng)；文獻(xiàn)[15]的算法在各層網(wǎng)絡(luò)編碼節(jié)點(diǎn)進(jìn)行分層多播，需要在信源信宿間反復(fù)尋找增廣路徑，且需要在網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)進(jìn)行解碼，算法復(fù)雜度高，收斂時(shí)間較長(zhǎng)，只有在大規(guī)模網(wǎng)絡(luò)拓?fù)渲?，才能充分發(fā)揮其性能；而文獻(xiàn)[11]算法是一種分布式隨機(jī)線性網(wǎng)絡(luò)編碼構(gòu)造算法，且其時(shí)間復(fù)雜度僅為O[|Vc||D|hs2]，所以收斂時(shí)間最短[27]，適用于網(wǎng)絡(luò)拓?fù)渥兓斓沫h(huán)境中，但是每次群組播都需重構(gòu)局部編碼向量，而且編碼成功的概率取決于伽羅華域次數(shù)m；作為確定線性編碼構(gòu)造算法，文獻(xiàn)[12]算法與本文算法都適用于確定性網(wǎng)絡(luò)中，但文獻(xiàn)[12]算法需要進(jìn)行多次試播，而本文算法只需進(jìn)行一次虛擬試播便能確定可行編碼方案，所以有更短的收斂時(shí)間。

4 結(jié)語(yǔ)

針對(duì)多源組播網(wǎng)絡(luò)，給出了確定性逐層構(gòu)造網(wǎng)絡(luò)編碼算法。通過(guò)添加虛擬信源，將多源多宿組播問(wèn)題轉(zhuǎn)化成單源多宿組播問(wèn)題，其試播過(guò)程就是求解編碼方案的過(guò)程。本文提出了運(yùn)用決策樹(shù)算法尋找目標(biāo)節(jié)點(diǎn)的方法、由上到下逐層構(gòu)造多源組播網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼方案和修剪枝策略。仿真結(jié)果表明了所提算法的可行性和有效性，同時(shí)該算法為網(wǎng)絡(luò)編碼組播路由算法與網(wǎng)絡(luò)編碼構(gòu)造算法相結(jié)合的組播策略提供了新的思路和組合方案。

參考文獻(xiàn)(References)

[1] AHLSWEDE R, CAI N, LI S-Y R, et al. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216.

[2] KOETTER R, MéDARD 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] YEUNG R W. Information Theory and Network Coding [M]. Berlin: Springer-Verlag, 2010: 505-545.

[5] 蒲保興,王偉平.線性網(wǎng)絡(luò)編碼運(yùn)算代價(jià)的估算與分析[J].通信學(xué)報(bào),2011,32(5):47-55. (PU B X, WANG W P. Evaluation and analysis of the computation [J]. Journal on Communications, 2011, 32(5): 47-55.)

[6] 陳超.確定網(wǎng)絡(luò)編碼的安全特性研究[D].南京:南京理工大學(xué),2012:15. (CHEN C. Research on deterministic network coding [D]. Nanjing: Nanjing University of Science and Technology, 2012: 15.)

[7] CHARLES D, JAUTER K, LAUTER K. Signatures for network coding [J]. International Journal of Information and Coding Theory, 2009, 1(1): 3-4.

[8] 王龍翔.基于網(wǎng)絡(luò)編碼的MAC協(xié)議研究[D].成都:電子科技大學(xué),2013:12. (WANG L X. Research on MAC protocol based on network coding [D]. Chengdu: University of Electronic Science and Technology of China, 2013: 12.)

[9] LUN D S, MéDARD M, KOETTER R, et al. On coding for reliable communication over packet networks [J]. Physical Communication, 2008, 1(1): 3-20.)

[10] 付衛(wèi)平,蒲保興,劉遠(yuǎn)軍,等.確定性網(wǎng)絡(luò)編碼構(gòu)造的仿真實(shí)現(xiàn)[J].邵陽(yáng)學(xué)院學(xué)報(bào)(自然科學(xué)版),2013,10(1):26-32. (FU W P, PU B X, LIU Y J, et al. Simulation implementation of deterministic construction of network coding [J]. Journal of Shaoyang University (Natural Science Edition), 2013, 10(1): 26-32.)

[11] 魏姍.基于網(wǎng)絡(luò)編碼的分層組播算法研究[D].長(zhǎng)沙:中南大學(xué),2012:25. (WEI S. Layered multicast based on network coding [D]. Changsha: Central South University, 2012: 25.)

[12] 蒲保興,楊路明,王偉平.網(wǎng)絡(luò)拓?fù)湮粗h(huán)境下確定性網(wǎng)絡(luò)編碼數(shù)據(jù)傳輸[J].電子學(xué)報(bào),2009,37(10):2119-2124. (PU B X, YANG L M, WANG W P. A deterministic data transmission approach with network coding under unknown network topology [J]. Acta Electronica Sinica, 2009, 37(10): 2119-2124.)

[13] 靳美麗.基于網(wǎng)絡(luò)編碼的分布式衛(wèi)星路由算法[D].西安:西安電子科技大學(xué),2013:33-40. (JIN M L. A distributed satellite routing algorithm based on network coding [D]. Xi’an: Xidian University, 2013: 33-40.)

[14] 王白婷.能量有效的無(wú)線傳感網(wǎng)分簇路由協(xié)議研究[D].長(zhǎng)春：吉林大學(xué)，2016:25. (WANG B T. Research on energy efficient clustering routing protocol for wireless sensor networks [D]. Changchun: Jilin University, 2016: 25.)

[15] WIDMER J, CAPALBO A, ANTA A F, et al. Efficient interlayer network codes for fair layered multicast streaming [J]. IEEE/ACM Transactions on Networking, 2015, 23(4): 1107-1120.

[16] TASSI A, CHATZIGEORGIOU I, VUKOBRATOVIC D. Resource-allocation frameworks for network-coded layered multimedia multicast services [J]. IEEE Journal on Selected Areas in Communications, 2015, 33(2): 141-155.

[17] CHENG M X, YE Q, CHENG X, et al. Network coding and coding-aware scheduling for multicast in wireless networks [C]// ICC 2015: Proceedings of the 2015 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2015: 5703-5708.

[18] KWON M, PARK H. Network coding-based distributed network formation game for multi-source multicast networks [C]// ICC 2017: Proceedings of the 2017 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2017.

[19] 陳仁亮,韓亮,董超，等.基于隨機(jī)網(wǎng)絡(luò)編碼的轉(zhuǎn)發(fā)速率在線控制策略[J].軍事通信技術(shù),2016,37(1):8-11. (CHEN R L, HAN L, DONG C, et al. Online forwarding rate controlling strategy based on random network coding [J]. Journal of Millitary Communications Technology, 2016, 37(1): 8-11.)

[20] 蒲保興,楊路明,王偉平.線性網(wǎng)絡(luò)編碼的導(dǎo)出與擴(kuò)展[J].軟件學(xué)報(bào),2011,2(3):558-571. (PU B X, YANG L M, WANG W P. Generation and extension of linear network coding [J]. Journal of Software, 2011, 22(3): 558-571.)

[21] LANGBERG M, SPRINTSON A, BRUCK J. The encoding complexity of network coding [J]. IEEE/ACM Transactions on Networking, 2006, 14(SI): 2386-2397.

[22] 尹吉星,任平安.基于網(wǎng)絡(luò)編碼的多播路由算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(5):9-82. (YIN J X, REN P A. Multicast routing algorithm based on network coding [J]. Computer Technology and Development, 2014, 24(5): 79-82.)

[23] 徐光憲,賴(lài)俊寧.新型集中式網(wǎng)絡(luò)編碼組播路由算法[J/OL].計(jì)算機(jī)科學(xué)與探索(2016- 11- 01) [2017- 02- 22]. http://d.g.wanfangdata.com.cn/Periodical_pre_cfe78018-9cd1-45c6-8e0b-a99f3e67cab2.aspx. (XU G X, LAI J N. Centralized network coding multicast routing algorithm [J/OL]. Journal of Frontiers of Computer Science and Technology (2016- 11- 01) [2017- 02- 22]. http://d.g.wanfangdata.com.cn/Periodical_pre_cfe78018-9cd1-45c6-8e0b-a99f3e67cab2.aspx.)

[24] 潘峰.基于C5.0決策樹(shù)算法的考試結(jié)果預(yù)測(cè)研究[J].微型機(jī)與應(yīng)用,2016,35(8): 68-70. (PAN F. The test results prediction research based on C5.0 decision tree algorithm [J]. Microcomputer & Its Applications, 2016, 35(8): 68-70.)

[25] 蔡慧,劉洪波,韓國(guó)棟,基于K均值聚類(lèi)的隨機(jī)網(wǎng)絡(luò)拓?fù)淠Ｐ蚚J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(5):1089-1091. (CAI H, LIU H B, HAN G D. Random network topology model based on K-means [J]. Computer Engineering and Design, 2009, 30(5): 1089-1091.)

[26] YUAN N Q, JIANG T, BAI S, et al. Dynamic network model analysis based on communication network [J]. Advanced Materials Research, 2014, 989/990/991/992/993/994: 2639-2642.

[27] 楊建業(yè).動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的多角度度量[D].西安：西安電子科技大學(xué),2013:9. (YANG J Y. Multi-aspects measurement of topological structure in dynamic networks [D]. Xi’an: Xidian University, 2013: 9.)

This work is partially supported by National Science and Technology Support Program of China (2013BAH12F02), the Liaoning Colleges and Universities Fund for Distinguished Young Scholars (LJQ2012029).

XUGuangxian, born in 1977, Ph. D., professor. His research interests include information theory, network coding.

ZHAOYue, born in 1992, M. S. candidate. Her research interests include information theory, network coding, information security.

LAIJunning, born in 1992, M. S. His research interests include network coding, information security.