基于網絡編碼的確定性逐層構造算法

徐光憲，趙 越，賴俊寧

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

0 引言

在傳統網絡通信中，節點只能對數據進行簡單的存儲和轉發，不能對數據作任何處理。然而在2000年Ahlswede等[1]首次提出了網絡編碼的基本原理，其核心思想是允許中間節點對輸入信息進行合理編碼，然后將編碼信息發送到下級節點，最后信宿通過解碼矩陣對編碼信息進行解碼即可恢復出原始信息。Koetter等[2]提出了關于確定線性網絡編碼的代數構造方法，2005年Jaggi等[3]簡化了文獻[2]方法，把構造網絡編碼的復雜程度從指數級別降到了多項式級別，也使網絡編碼中使用的伽羅華域次數有所縮減[4-5]。隨著研究的不斷深入，線性網絡編碼構造算法被分成了隨機線性網絡編碼構造算法[6]和確定線性網絡編碼構造算法[7]。隨機線性網絡編碼是指在信息傳輸過程中從有限域中隨機選取編碼向量，并對接收到的信息進行編碼，所以隨機線性網絡編碼要求編碼節點有較強的運算能力，并且當信宿點接收到了足夠的數據后，就可以進行解碼操作。與隨機線性網絡編碼不同，確定線性網絡編碼是先確定編碼向量，再進行數據傳輸。確定性網絡通常指有線網絡拓撲，其全局網絡拓撲是固定的，編碼節點的位置也是確定的，所以編碼向量可根據全局網絡拓撲知識來確定。由于確定性網絡中間節點是通過固定鏈路連接的，鏈路拓撲動態變化表現在鏈路權值的波動，不存在節點移動和鏈路斷路的情況，那么在不穩定網絡拓撲中編碼節點不斷變化，隨機線性網絡編碼構造算法更能發揮優勢；而確定線性網絡編碼構造算法的編碼節點位置是確定的，適用于網絡狀態較穩定的組播通信，其所需運算空間更小、運算量更少。

線性網絡編碼在國內外已經得到了廣泛深入的研究，文獻[5]基于線性編碼找到了計算最大組播容量的分布式算法；王龍翔[8]在組播率小于組播容量的前提下，提出了有線網絡編碼路由算法；文獻[9]涉及了靜態多播連接時構造最小代價子圖算法。然后研究者們又從網絡拓撲入手，提出了多種網絡編碼算法：文獻[10]提出了一種基于向量空間正交補的確定線性網絡編碼構造算法，該算法相對復雜需要消耗較長時間，適用在網絡拓撲穩定的情況下；文獻[11]在基于網絡編碼的多路徑分簇路由算法的基礎上，提出了一種分布式隨機網絡編碼算法，該算法適用于拓撲變化頻繁的分布式網絡中；文獻[12]針對網絡拓撲未知的情況提出了一種基于信宿反饋的確定線性網絡編碼構造(Sink Nodes Feedback Deterministic Network Coding, SNFDNC)算法，該算法需要進行多次試播來確定編碼方案，網絡編碼收斂時間較長；文獻[13]提出了一種基于網絡編碼的分布式衛星路由算法和一種基于機會搜尋的隨機網絡編碼構造算法，并將兩種算法相結合實現了隨機的網絡編碼組播通信；隨后文獻[14]在基于網絡編碼的多路徑分簇路由算法的基礎上，提出了一種分布式隨機網絡編碼算法，該算法擴展性強，可成功移植到組播路由算法中，但由于該算法運用隨機線性網絡編碼構造方案，所以不能充分利用帶寬資源且運算量過大。

近年來，關于網絡編碼的研究已經從單源組播通信[2-4]過渡到了多源組播通信，文獻[15-17]通過引入虛擬信源的方法對一般多源組播問題的網絡容量進行研究，提高了鏈路吞吐量和組播系統的穩定性，但是算法復雜度普遍較高，使得收斂時間過長。其中：文獻[15]提出了一種基于埃德蒙茲最大流的公平分層組播網絡編碼構造算法，通過運用多項式復雜度啟發式方案來確保信宿接收信息的可解碼性，但該算法需要反復尋找信源到信宿之間的增廣路徑，需要較長運算時間，只有在較大規模的網絡拓撲中才能發揮其優勢；文獻[16]將網絡編碼分層組播應用于多媒體點對多點的資源分配中，通過多速率傳輸策略實現了網絡拓撲中各層下行鏈路廣播分組數的最小化，然而文中沒有給出用于分配各層數據所需鏈路帶寬的方案，導致網絡帶寬利用率較低；文獻[17]為了降低網絡延遲，提高網絡傳輸效率，提出了一種最小化網絡延遲的編碼感知傳輸調度算法，其有效性在實驗中得到了驗證，并為路由和編碼的聯合設計提供了更多可能性；文獻[18]提出一種基于多源組播的獨立安全網絡編碼方案，保證了多播網絡的安全性和可靠性，使大容量網絡拓撲的形成成本有所降低，但該方案需要評估所有可能潛在的網絡拓撲，因此需要很高的計算復雜度。

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

1 相關知識

1.1 網絡編碼多源組播原理

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

(1)

(2)

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

經過任一編碼節點的輸出信息向量均可看作是信源所發送信息的線性組合，該線性組合的系數就是編碼節點輸出鏈路e的全局編碼向量。

1.2 伽羅華域

在伽羅華域GF(2m)中，m代表伽羅華域的次數，由既約多項式確定[5]，q=2m代表伽羅華域的階數，由于在固定伽羅華域中字符都是有限個相同數目的二進制字符串，這樣計算較為方便，所以本文中確定線性網絡編碼運算都是在伽羅華域環境下進行的。令多源組播網絡中的組播率為h，每個信道上傳輸的數據塊長度為L個字符，因為采用的伽羅華域為GF(2m)，則每個字符均為m比特的二進制數，那么組播通信一次數據傳輸的信息量為mLh比特。

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

τ(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)

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

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

(7)

(8)

2 逐層構造網絡編碼方案

2.1 方案的理論依據

源點單位時間傳遞信息的速率稱為組播率，最大組播率即為組播容量，它等于信源到信宿容量函數的最小值，也就是信源到信宿的最小割值[22]。在已知網絡拓撲的多源組播網絡G(V,E)中，信源集合為S=(S1,S2,…,Sn)，且各源點相互獨立，信宿集合為T=(T1,T2,…,Td)，其中n>1，d>1。令z∈T，且?D?S，記min-c(D,z)為信源集合D與信宿點z的最小割值，那么m-f(D,T)為信源集合D與每個信宿點最小割值的最小值，也就是信源集D到信宿集T的最大流，如式(9)所示。在多源組播網絡拓撲中加入一個虛擬信源S′后，m-f(D,T)用m-f(S′,T)表示。

(9)

網絡拓撲中每條鏈路的鏈路容量可用該鏈路的最大傳輸速率來表示，若鏈路容量為C，C大于1且C為正整數，則該鏈路可看作是由C條鏈路容量為1的信道構成。

定理1 在多源組播網絡拓撲中，如果虛擬信源和各組播源點只采用路由方式傳遞信息并不進行編碼，且每個源點需傳輸信息到全部信宿點，設各個源點的組播率分別為h1,h2,…,hn，那么當S′的組播容量與其輸出信道數關系滿足式(10)，S′的組播率h與各個源點的組播率關系滿足式(11)時，則一定可以找到一個可行的網絡編碼方案[20]。

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

(10)

(11)

證明 由式(9)可證式(10)成立。又因為虛擬信源和實際信源只進行數據傳輸不進行編碼，所以用虛擬信源代替實際信源時，只需令虛擬信源信道數等于各信源信道數之和即可。而且每個源點需要傳輸信息至全部宿點，那么通過調整各編碼節點的局部編碼向量使每個信宿點接收到滿秩的全局編碼矩陣則代表編碼成功，證明原理如圖1所示。

組播網絡通過組播路由算法生成組播路由方案確定了編碼節點的位置，但是在數據傳輸的整個過程中，網絡拓撲的動態變化會引起路由方案的變動(主要體現在鏈路權值的變化)，這就需要重構信道的局部編碼向量來形成一個新的可行編碼方案。

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

確定線性網絡編碼可以在網絡拓撲已知的前提下，采用集中方法構造網絡編碼方案[23],通過調整部分編碼節點的局部編碼向量使每個節點收到的全局編碼矩陣滿秩，保證每個信宿獲得的解碼矩陣可以成功解碼。

定義1 在已知全局網絡拓撲的前提下，采用確定性網絡編碼，以給定組播率由上而下逐層進行局部編碼向量的構造，數據傳輸過程中采用這些編碼向量進行編碼運算，則稱為確定線性網絡編碼逐層構造策略。

定義2 虛擬源點發送的數據包逐層經過編碼節點，同時每層節點將其收到的全局編碼矩陣反饋給上層與之相關的編碼節點，直到信宿完成反饋，該過程稱為一次虛擬試播[12]。

由于在虛擬試播階段只需要考察各節點接收到的全局編碼矩陣，而并不需要考察其接收到的數據信息，所以試播虛擬矩陣即可。因為虛擬信源組播率為h，所以要發送h×h階試播矩陣，實驗包結構中的數據段可以忽略不進行傳遞，其格式如圖2所示。

圖2 實驗包結構 Fig. 2 Structure of test package

定理2 虛擬試播過程中，如果虛擬信源的試播矩陣以及中間節點的全局編碼矩陣是滿秩的，那么一定存在可行的線性網絡編碼方案。

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

AorigGB=Y

(12)

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

(13)

本文進行試播時無需對信息進行傳遞，所以可將試播矩陣近似看成加密矩陣G，由矩陣論知識得出：只有保證試播矩陣G和全局編碼矩陣B滿秩，才能形成可行的線性網絡編碼方案，成功恢復出原始信息矩陣Aorig。

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

證明 因為M1是上三角矩陣，M2是下三角矩陣，同時二者的對角線都是非零元素，所以矩陣M1和M2是滿秩矩陣，那么兩個滿秩矩陣相乘得到的矩陣也是滿秩的，即試播矩陣滿秩。試播矩陣的確定就是按照定理3的方法，在伽羅華域中隨機選取的。

2.2 逐層構造網絡編碼算法

本文通過虛擬試播運用確定線性網絡編碼逐層構造策略進行局部編碼向量可行方案的確定。由定理3可知：只要在伽羅華域GF(2m)上隨機選取元素構成矩陣M1和M2即可確定試播矩陣，由于網絡編碼對編碼節點的運算能力和存儲空間有較高要求[22]，所以本文為了計算方便，試播矩陣選用h×h階的單位矩陣E，這樣輸入節點vi的編碼信息就等于一個由舊全局編碼向量組成的L×|ΓI(vi)|階矩陣，如式(14)所示，那么輸出到鏈路e的信息向量等于輸入信息向量與編碼節點vi的局部編碼向量之積，也就是編碼節點vi新生成的全局編碼向量，如式(15)所示，最后信宿節點收到的編碼信息矩陣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 在確定局部編碼向量可行方案時，用Mij表示輸入節點vij的全局編碼矩陣，用RM表示Mij的秩，用p代表每層獲得非滿秩全局編碼矩陣的節點個數。若Mij非滿秩，則需改變vij的上層編碼節點的局部編碼向量，以確保矩陣Mij滿秩，稱符合變換要求的第i-1層的編碼節點為潛在變換節點，其數目記為q；稱潛在變換節點中改變了局部編碼向量的編碼節點為變換節點。

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

定義4 在數據傳輸過程中，當編碼節點的部分輸入鏈路無法為網絡編碼提供有用數據時，則對其進行修剪，該過程稱為修剪枝。

例如多條鏈路傳送相同或線性相關信息到同一編碼節點時，便可對其中部分鏈路進行修剪。在網絡編碼時進行修剪枝，可以減少數據冗余，避免鏈路復用，從而提高網絡帶寬利用率。

在進行統計各層獲得非滿秩全局編碼矩陣節點個數時，采用了決策樹算法[24]。決策樹是一類常見的機器學習方法，它以一種樹形結構對樣本進行分類，其中每個節點代表一個屬性上的測試，每個分支代表一個測試輸出，每個葉節點代表一種類別。其中C5.0決策樹算法[24]有著非常好的泛化能力和魯棒性，可以對訓練樣本中“變化”和“未變化”的樣本進行高度識別與區分，最終得到正確分類。

本文在網絡拓撲發生動態變化后，就是利用C5.0決策樹算法自動提取檢測網絡拓撲中各層節點的編碼矩陣，然后對編碼節點進行重新分類的，其中一類是獲得滿秩全局編碼矩陣的節點；另一類是獲得非滿秩全局編碼矩陣的節點。同時，C5.0決策樹算法還可以對各類樣本的數目進行統計。該算法將網絡拓撲中所有節點作為訓練樣本集，通過訓練會具有很好的泛化能力，所以可快速準確地找到變換和未變換的樣本。本文需要統計的是各層未獲得滿秩全局編碼矩陣的節點，其數目用p表示。

1)當p=0時，證明第i層編碼節點全部得到了滿秩的全局編碼矩陣，則跳到第i+1層繼續判斷。

2)當p>0時，證明第i層存在p個編碼節點得到了非滿秩全局編碼矩陣，接下來查找這些編碼節點的上層潛在變換節點數q：

① 當q=|ΓI(Vij)|-RMij時，令q個潛在變換節點全部成為變換節點。

② 當q>|ΓI(Vij)|-RMij時，首先進行潛在變換節點優先級的判定，即編碼節點的輸入鏈路數目越少，其重構局部編碼向量的運算量越低，優先級越高。通過優先級判定從q個潛在變換節點中選出|ΓI(Vij)|-RMij個變換節點，若優先級相同，則任選其一即可。

③ 當q<|ΓI(Vij)|-RMij時，令q個潛在變換節點都為變換節點的同時要對組播路由方案進行修剪枝，去掉與該編碼節點相連的|ΓI(Vij)|-RMij-q條相關上游鏈路，也就是修剪掉數據冗余鏈路，減少網絡開銷，提高帶寬利用率。

本文以一個已經確定了組播路由方案的18節點無向圖來展示確定線性網絡編碼逐層構造算法的原理，如圖3所示，設入度大于1的網絡節點可以作為編碼節點，初始局部編碼向量組成全部默認為1，組播信宿數|T|=4，有4層網絡節點(虛擬信源不參與計數)，用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。下面對確定線性網絡編碼逐層構造算法進行舉例說明，在信宿層節點通過決策樹算法得知信宿點T2全局編碼矩陣的秩為3，未獲得滿秩全局編碼矩陣，所以要重構其上層變換節點V2.1的局部編碼向量，最終使信宿點T2獲得滿秩的全局編碼矩陣，如式(16)所示：

(16)

在圖3中還可以看到算法對編碼節點V2.5的輸入鏈路進行了修剪枝，因為它的輸入全局編碼矩陣的秩小于輸入鏈路數目，是非滿秩矩陣，它的上層潛在變換節點數為0，所以要對其進行修剪枝，減少鏈路冗余，提高網絡帶寬。編碼節點的輸出鏈路對應著各自的編碼器，在確定變換節點后，需要重構其相應輸出鏈路編碼器的編碼系數，從而生成新的編碼向量，直至同層所有變換節點完成了局部編碼向量的重構，再將新生成的編碼向量重新輸入到各自對應的第i層的p個編碼節點。然后，這些編碼節點再次計算各自的輸入全局編碼矩陣是否滿秩，循環至p=0便進入到下一層編碼節點的局部編碼向量構造。重復以上操作，直到信宿層的全局編碼矩陣Bi滿秩，即編碼成功。

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

2.3 逐層構造網絡編碼算法流程

算法描述：

步驟1 算法初始化。

步驟2 虛擬信源發送試播矩陣，同層編碼節點開始編碼，各編碼節點為其輸出信道產生全局編碼向量，按式(15)計算出輸出信道全局編碼向量并轉發實驗包。

步驟3 運用決策樹算法標記出p個第i層獲得非滿秩全局編碼矩陣的編碼節點vij,若p=0，層數i自加并跳轉到下一層編碼節點，若p>0，需要調整vij的上層變換節點編碼向量。

步驟4 當p>0時，標記與編碼節點vij對應的第i-1層潛在變換節點位置，并計數為q。

1)當q=|ΓI(Vij)|-RMij時，令q個潛在變換節點全部成為變換節點；

2)當q>|ΓI(Vij)|-RMij時，進行潛在變換節點優先級的判定，確定變換節點；

3)當q<|ΓI(Vij)|-RMij時，令q個潛在變換節點都為變換節點并進行修剪枝。

步驟5 確定變換節點后，調整其局部編碼向量，將新生成的全局編碼向量再次傳入編碼節點vij，不斷循環，直到使vij輸入鏈路的全局編碼向量滿秩。

步驟6 Untilp=0。

步驟7i+1→i。

步驟8 Untili=f。

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

2.4 算法復雜度分析

通過上述算法可以得到確定性網絡編碼方案，用鄰接鏈表表示網絡拓撲，用Steiner樹可以實現總代價最小分布樹的方法來保證網絡鏈路開銷最小。在隨機線性網絡編碼構造算法中，編碼節點的編碼系數是隨機選取的，而在確定性網絡編碼方案中需要通過計算得到編碼節點的編碼系數。本文算法只需進行一次虛擬試播，設虛擬信源的組播率為h，Vc為編碼節點，D為Steiner節點，則算法的整個復雜度表示為O[|Vc||D|h(|D|+h)]。

3 仿真測試

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

對已知組播路由方案的多源組播網絡進行仿真測試，實驗環境為NS2自帶的拓撲生成工具GT-ITM生成的K均值聚類Waxman隨機拓撲模型——KRTG(Random Topology Generate algorithm based onK-means)[25],通過在KRTG模型中設置節點數、節點范圍、鏈路帶寬、鏈路長邊與短邊等參數來形成不同規模的網絡拓撲。其基本原理是將設制的n個節點均勻分布在擁有最大距離上限的平面上，節點間生成鏈路的概率如式(17)所示：

(17)

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

3.1 算法有效性測試

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

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

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

3.2 性能對比

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

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

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

圖4 網絡編碼構造算法收斂時間對比 Fig. 4 Convergence time comparison of network coding construction algorithms

由各算法收斂時間折線圖分析得出：雖然在表2中文獻[10]的算法和本文算法一樣與伽羅華域次數m無關，但前者算法收斂時間較長；文獻[15]的算法在各層網絡編碼節點進行分層多播，需要在信源信宿間反復尋找增廣路徑，且需要在網絡內部節點進行解碼，算法復雜度高，收斂時間較長，只有在大規模網絡拓撲中，才能充分發揮其性能；而文獻[11]算法是一種分布式隨機線性網絡編碼構造算法，且其時間復雜度僅為O[|Vc||D|hs2]，所以收斂時間最短[27]，適用于網絡拓撲變化快的環境中，但是每次群組播都需重構局部編碼向量，而且編碼成功的概率取決于伽羅華域次數m；作為確定線性編碼構造算法，文獻[12]算法與本文算法都適用于確定性網絡中，但文獻[12]算法需要進行多次試播，而本文算法只需進行一次虛擬試播便能確定可行編碼方案，所以有更短的收斂時間。

4 結語

針對多源組播網絡，給出了確定性逐層構造網絡編碼算法。通過添加虛擬信源，將多源多宿組播問題轉化成單源多宿組播問題，其試播過程就是求解編碼方案的過程。本文提出了運用決策樹算法尋找目標節點的方法、由上到下逐層構造多源組播網絡的線性網絡編碼方案和修剪枝策略。仿真結果表明了所提算法的可行性和有效性，同時該算法為網絡編碼組播路由算法與網絡編碼構造算法相結合的組播策略提供了新的思路和組合方案。

參考文獻(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] 蒲保興,王偉平.線性網絡編碼運算代價的估算與分析[J].通信學報,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] 陳超.確定網絡編碼的安全特性研究[D].南京:南京理工大學,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] 王龍翔.基于網絡編碼的MAC協議研究[D].成都:電子科技大學,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] 付衛平,蒲保興,劉遠軍,等.確定性網絡編碼構造的仿真實現[J].邵陽學院學報(自然科學版),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] 魏姍.基于網絡編碼的分層組播算法研究[D].長沙:中南大學,2012:25. (WEI S. Layered multicast based on network coding [D]. Changsha: Central South University, 2012: 25.)

[12] 蒲保興,楊路明,王偉平.網絡拓撲未知環境下確定性網絡編碼數據傳輸[J].電子學報,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] 靳美麗.基于網絡編碼的分布式衛星路由算法[D].西安:西安電子科技大學,2013:33-40. (JIN M L. A distributed satellite routing algorithm based on network coding [D]. Xi’an: Xidian University, 2013: 33-40.)

[14] 王白婷.能量有效的無線傳感網分簇路由協議研究[D].長春：吉林大學，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].軍事通信技術,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] 蒲保興,楊路明,王偉平.線性網絡編碼的導出與擴展[J].軟件學報,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] 尹吉星,任平安.基于網絡編碼的多播路由算法研究[J].計算機技術與發展,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] 徐光憲,賴俊寧.新型集中式網絡編碼組播路由算法[J/OL].計算機科學與探索(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決策樹算法的考試結果預測研究[J].微型機與應用,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] 蔡慧,劉洪波,韓國棟,基于K均值聚類的隨機網絡拓撲模型[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] 楊建業.動態網絡拓撲結構變化的多角度度量[D].西安：西安電子科技大學,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.