劉宴濤，夏桂陽，徐 靜，秦 娜

（渤海大學工學院，遼寧錦州121000）

一種基于子樹分解的組播線性網(wǎng)絡編碼算法

劉宴濤，夏桂陽，徐 靜，秦 娜

（渤海大學工學院，遼寧錦州121000）

針對拓撲不變網(wǎng)絡的單源組播網(wǎng)絡編碼問題，基于子樹分解提出一種新的線性網(wǎng)絡編碼算法。該算法由線圖變換、子樹分解、邊不相鄰路徑搜索、全局編碼矢量分配和局部編碼矢量計算等過程組成。算法輸入為滿足組播條件的有向無環(huán)網(wǎng)絡，輸出為各邊的全局編碼矢量和局部編碼矢量。在子樹分解過程中，子樹內(nèi)部的邊不需要編碼，只對子樹之間的邊進行編碼。理論分析和仿真實驗結果表明，利用子樹分解可以降低網(wǎng)絡規(guī)模以及路徑搜索和分配編碼矢量的計算復雜度，縮短編碼算法的運行時間，因此該算法是一種高效的單源組播網(wǎng)絡編碼算法。

線性網(wǎng)絡編碼；有向無環(huán)圖；線圖；子樹分解；編碼矢量

1 概述

網(wǎng)絡編碼的基本思想是在網(wǎng)絡中傳輸數(shù)據(jù)包時，允許中間節(jié)點對收到的數(shù)據(jù)包進行組合、運算和編碼等操作，從而生成新的數(shù)據(jù)包向后繼節(jié)點發(fā)送。這與傳統(tǒng)的路由技術有很大不同，因為路由采用存儲轉發(fā)的策略，不允許中間節(jié)點對數(shù)據(jù)包進行其他操作。與路由技術相比，網(wǎng)絡編碼技術帶來了包括網(wǎng)絡吞吐量、通信魯棒性、無線帶寬、能效節(jié)省、網(wǎng)絡安全等收益［1］。為了換取這些收益，網(wǎng)絡節(jié)點對數(shù)據(jù)包的處理功能要更為復雜，但隨著集成電路和通信技術突飛猛進的發(fā)展以及摩爾定律的作用，現(xiàn)代網(wǎng)絡通信的瓶頸越來越多地出現(xiàn)在通信信道的帶寬上，而不是出現(xiàn)在網(wǎng)絡設備的處理能力上，所以，網(wǎng)絡編碼技術將成為突破這一瓶頸的理想選擇。

網(wǎng)絡編碼技術一經(jīng)提出就引起了科學界和工程界的強烈興趣，目前對該技術的研究主要從理論和應用2個層面進行。理論工作者熱衷于探討包括信息不等式［2］、網(wǎng)絡編碼的代數(shù)框架［3］、路由容量［4］以及編碼容量［5］的性能極限、網(wǎng)絡編碼符號集的應用［6］、如何處理有環(huán)網(wǎng)絡的延時［7］、非組播業(yè)務［8］中線性網(wǎng)絡編碼的不足以及網(wǎng)絡糾錯碼［9］等理論問題。為分析這些問題，各種理論方法被應用在網(wǎng)絡編碼領域，其中包括信息論、代數(shù)、幾何、圖論、擬陣論、組合優(yōu)化等。在工程應用方面，研究者紛紛提出各種編碼方法將網(wǎng)絡編碼付諸工程實踐，應用領域包括Ad Hoc網(wǎng)絡、分布式存儲、內(nèi)容發(fā)布、網(wǎng)絡糾錯、P2P網(wǎng)絡等［1］。編碼方法包括線性編碼［7］、非線性編碼［8］、隨機編碼［10］、多項式時間編碼［11］、子空間網(wǎng)絡糾錯碼［9］、標量編碼和矢量編碼［12］等。對網(wǎng)絡編碼的綜述性介紹可見文獻［1-2，13］。

本文從工程應用方面出發(fā)，針對拓撲不變的單源組播網(wǎng)絡提出一種基于子樹分解的線性網(wǎng)絡編碼算法（Linear Network Coding Based on Subtree Decomposition，LNCBSD），通過子樹分解的預處理過程把網(wǎng)絡圖縮減為子樹圖，利用靜態(tài)子樹集和動態(tài)子樹集的方法為每棵子樹分配全局編碼矢量，并進一步計算局部編碼矢量。

2 相關研究

文獻［14］論證了網(wǎng)絡編碼與路由相比的優(yōu)點，證明了當網(wǎng)絡拓撲滿足從源節(jié)點到各個接收節(jié)點的最小割的最小值等于h時（本文稱此為組播條件），如果允許中間節(jié)點進行編碼且符號取自足夠大的有限域，則可以實現(xiàn)從源節(jié)點向多個接收節(jié)點同時組播h個符號。該文獻的工作相當于把單播應用中的最大流最小割定理［15］推廣到了組播應用中，這是路由技術所無法完成的?；谖墨I［14］的工作，文獻［7］提出在有限域上進行線性運算即可實現(xiàn)組播，從而提出了線性網(wǎng)絡編碼（Linear Network Coding，LNC）的概念，雖然后來也出現(xiàn)了非線性編碼的概念，但線性編碼由于其編譯碼的簡單性依然作為主流的編碼方法。文獻［3］把網(wǎng)絡編碼問題轉換為代數(shù)問題，把網(wǎng)絡的輸入輸出用轉移矩陣聯(lián)系起來，從而可以應用狀態(tài)變量方程或矩陣完成等方法解決編譯碼問題。文獻［8］舉反例證明在非組播應用中線性編碼是非充分的，并討論了矢量編碼和非線性編碼的作用。文獻［10］針對拓撲可變的無線網(wǎng)絡提出了隨機編碼的方法，其基本思想是在每個中間節(jié)點處隨機產(chǎn)生本地編碼矢量，并且在發(fā)送正式符號之前，先發(fā)送h個單位矢量的符號，這樣在接收節(jié)點處就可以獲得全局編碼矢量，從而進行譯碼。這種方法最大的問題是額外開銷問題，其降低了網(wǎng)絡利用率，而且全局編碼矢量的計算對網(wǎng)絡傳輸錯誤非常敏感。文獻［11］針對組播應用提出了一種多項式時間復雜度的線性網(wǎng)絡編碼方法，把網(wǎng)絡編碼向工程應用中推進了一步，該方法的時間復雜度是O（|E||T|h（h+|E|））。其中，|E|表示邊數(shù)；|T|表示接收節(jié)點數(shù)；h表示源節(jié)點組播的符號數(shù)，這種算法的復雜度的上界函數(shù)是邊數(shù)的平方，因此，是一種多項式時間算法。與之相比，本文算法復雜度的上界函數(shù)是網(wǎng)絡中子樹數(shù)的平方，因此低于文獻［11］方法的復雜度。文獻［16］另辟蹊徑，對系統(tǒng)轉移矩陣采用迭代的矩陣完成的方法計算編碼矢量，該方法的計算復雜度為O（|E|3|T|log|E|）。文獻［17］提出了網(wǎng)絡的子樹分解的概念，并基于子樹分解提出了射影幾何編碼的分布式方法，該方法把子樹的全局編碼矢量設計成射影線PG（n，q）上的射影點坐標，從而保證了不同路徑上子樹的編碼矢量的線性無關性。本文也使用了子樹分解的方法，但本文是通過建立靜態(tài)子樹集和動態(tài)子樹集，并在子樹上動態(tài)推進，為各個子樹分配全局編碼矢量，由于分配全局編碼矢量時要考慮不同路徑上子樹的線性無關性，因此本文算法是一種拓撲依賴的確定性方法。需要說明的是，文獻［17］方法雖然在分配編碼矢量時是分布式的，不需要考慮其他節(jié)點的矢量分配情況，但子樹分解時依然是拓撲依賴的。文獻［18］研究了對有噪網(wǎng)絡進行隨機線性網(wǎng)絡編碼的問題，設計一種信道模型把隨機錯誤建模為對碼字的擾動，并提出了一種基于隨機稀疏圖的糾錯碼的編解碼方法。文獻［19］針對多組播組的分組競爭問題，提出了一種分組調(diào)度算法用以最小化所需的同步緩沖器大小。文獻［20］應用博弈論的方法分析了多重單播無線網(wǎng)絡中，當節(jié)點獨立地選擇各自路由時的傳輸次數(shù)代價問題，求得了最好和最差穩(wěn)定解的限，并提出了一種優(yōu)化的代價共享協(xié)議。

從2008年開始，網(wǎng)絡糾錯碼成為網(wǎng)絡編碼領域的一個熱點研究方向。網(wǎng)絡糾錯碼把網(wǎng)絡編碼和糾錯碼相結合，用網(wǎng)絡編碼的空間冗余度代替糾錯碼的時間冗余度，實現(xiàn)糾錯的功能。在網(wǎng)絡糾錯碼中具有代表性的是文獻［9］提出的一種基于子空間編碼的方法，該方法利用線性隨機網(wǎng)絡編碼的子空間不變性（即發(fā)送矢量張成的子空間和接收矢量張成的子空間是同一個子空間），在發(fā)送端發(fā)送子空間的基矢量，在接收端根據(jù)收到的矢量計算子空間，并根據(jù)子空間距離進行最小距離譯碼。這種方法實現(xiàn)了非相關網(wǎng)絡編碼功能，發(fā)送和接收節(jié)點不需要知道網(wǎng)絡結構，也不需要如文獻［11］中數(shù)據(jù)包的額外開銷。文獻［21］針對組播應用中數(shù)據(jù)丟失問題，提出了一種可靠組播算法，通過數(shù)據(jù)包分代傳送和網(wǎng)絡編碼相結合的方法完成數(shù)據(jù)恢復。文獻［22］采用M arkov鏈的方法分析了單播應用中隨機線性網(wǎng)絡編碼的時延特征與有限域大小的關系。文獻［23］給出了網(wǎng)絡編碼的序列矩陣描述方法，從而把確定性編碼、隨機編碼和卷積編碼統(tǒng)一在一個框架內(nèi)，并提出了一種多項式時間的譯碼方法。

3 線性網(wǎng)絡編碼

本文討論的問題和方法屬于線性網(wǎng)絡編碼的范疇。首先規(guī)定：本文討論的網(wǎng)絡屬于有向無環(huán)圖（Directed Acyclic Graph，DAG），節(jié)點之間靠單位容量的有向邊相連接，節(jié)點之間允許多邊存在，且網(wǎng)絡中沒有環(huán)路。網(wǎng)絡中有一個源節(jié)點S向網(wǎng)絡中發(fā)送h個符號σ1，σ2，…，σh，這些符號產(chǎn)生于有限域GF（2m），即σ1，σ2，…，σh∈GF（2m）。網(wǎng)絡中存在多個接收節(jié)點Ri等待接收這些符號。網(wǎng)絡的拓撲結構滿足組播條件，即源節(jié)點和每個接收節(jié)點之間的最小割都大于等于流量h。

如圖1所示，在對滿足組播條件的網(wǎng)絡進行線性網(wǎng)絡編碼時，中間節(jié)點收到來自入邊的符號后，在每個出邊輸出一個新符號，這些輸出符號分別由輸入符號的某個線性組合得到。具體地說，對于某個中間節(jié)點t，假設t的入邊集合為｛e1，e2，…，，出邊集合為，則出邊e′j上的符號f（e′j）和所有入邊上的符號f（ei）之間靠本地編碼矢量｛l1j，l2j…，l|IN（t）|j｝，lij∈GF（2m），聯(lián)系起來［2，15］，即：

圖1 線性網(wǎng)絡編碼示意圖

進一步不難發(fā)現(xiàn)，由于各個中間節(jié)點都執(zhí)行線性運算，因此在網(wǎng)絡中各個邊E上流動的符號f（E）又可以看成是源節(jié)點s發(fā)出的符號σ1，σ2，…，σh的線性組合，即：

稱（g1，g2，…，gh），gh∈GF（2m）為邊E的全局編碼矢量。

每個接收節(jié)點收到來自入邊E1，E2，…，Eh的h個符號f（E1），f（E2），…，f（Eh）后，通過在有限域GF（2m）上求解線性方程組可得源節(jié)點發(fā)出的h個符號σ1，σ2，…，σh。因為線性方程組：

有解的充要條件是系數(shù)行列式（4）滿秩，所以，線性網(wǎng)絡編碼問題就等價于如何為網(wǎng)絡中各個邊分配全局編碼矢量，使得在各個接收節(jié)點處系數(shù)行列式（4）滿秩的問題。

在應用線性網(wǎng)絡編碼時，為了減小問題的規(guī)模和編碼的復雜度，一個思路是當網(wǎng)絡中某個節(jié)點僅有一個入邊時，這樣的節(jié)點只需要轉發(fā)收到的符號，不需要進行編碼，即采用傳統(tǒng)路由的方法?；谶@樣一種考慮，本文提出了一種基于子樹分解的組播線性網(wǎng)絡編碼算法，該算法把網(wǎng)絡分解為若干棵子樹，子樹內(nèi)部不需要編碼，或者說子樹內(nèi)部的所有節(jié)點使用相同的全局編碼矢量。然后為源節(jié)點S到每個接收節(jié)點Ri之間尋找h條不相鄰子樹路徑，并進一步為這些路徑上的子樹分配全局編碼矢量。

4 LNCBSD算法

4.1 算法說明

本文算法的輸入是一個滿足組播條件的單源多宿組播網(wǎng)絡拓撲圖，輸出是網(wǎng)絡中各個邊的全局編碼矢量和本地編碼矢量。算法分為5步執(zhí)行：（1）由原網(wǎng)絡拓撲圖生成與之相對應的線圖；（2）對線圖做子樹分解得到子樹圖；（3）為每個接收節(jié)點Ri分配靜態(tài)子樹集SRi；（4）維護動態(tài)子樹集DRi，為每棵子樹分配全局編碼矢量；（5）由全局編碼矢量計算得到編碼節(jié)點的局部編碼矢量。

具體過程如下：

（1）把原始的網(wǎng)絡拓撲圖變?yōu)榫€圖［15］。所謂線圖就是把原圖中的邊表示成線圖中的節(jié)點，如果原圖中一條邊的箭頭和另一條邊的箭尾共享一個節(jié)點，則在線圖中這2條邊變成的2個節(jié)點相鄰接。需要說明的是如果原圖中源節(jié)點發(fā)出的符號個數(shù)是h，在線圖中將出現(xiàn)h個源節(jié)點；如果原圖中接收節(jié)點的數(shù)目是N，在線圖中將出現(xiàn)hN個接收節(jié)點，即每個接收節(jié)點將擴展成h個分節(jié)點。

（2）對線圖進行子樹分解［17］。子樹分解是指把線圖分解成若干棵子樹，每棵子樹的樹根只能是線圖中的源節(jié)點或具有多個輸入邊的節(jié)點（稱為編碼節(jié)點），且子樹結束于接收節(jié)點或另一個編碼節(jié)點。這樣分解后，每棵子樹內(nèi)部將流動相同的符號，因此在子樹內(nèi)部不需要編碼，僅僅進行轉發(fā)的操作。另外，每個接收節(jié)點的h個分節(jié)點將位于h棵不同的子樹中。經(jīng)過子樹分解后，原本復雜的線圖可以縮減為由子樹之間相連接構成的子樹圖。

（3）在子樹圖中，從h個源節(jié)點到每個接收節(jié)點Rj的h個分節(jié)點之間一一對應地尋找h條邊不相鄰路徑，存入一個靜態(tài)路徑集合SRj里，這些路徑的存在性是被組播條件所保證的。因為共有N個接收節(jié)點，所以靜態(tài)集合也有N個。但是需要說明的是，雖然每個接收節(jié)點的h條路徑不相鄰接，但各個接收節(jié)點之間可能會出現(xiàn)路徑的鄰接，也就是說某個接收節(jié)點的某條子樹路徑和其他接收節(jié)點的某條子樹路徑可能會共用某個中間子樹。

（4）為每棵子樹分配全局編碼核。其中，由于h個源節(jié)點所位于的h棵子樹內(nèi)部流動的是原始符號σ1～σh，所以這h棵子樹的全局編碼核可以分配成h個單位矢量（0…0，1，0…0）T，其中，第i個分量為1，其他分量為0。除了源節(jié)點所位于的h棵子樹外，其他子樹的全局編碼核動態(tài)地生成。不失一般性，假設源節(jié)點所位于的h棵子樹編號為T1～Th，為了給某個子樹分配編碼矢量，需要為每個接收節(jié)點Rj維護一個動態(tài)集合DRj，其中存放的是當前正在編碼的SRj各條路徑最前端的子樹Ti以及該子樹的全局編碼矢量g（Ti），共h個。隨著編碼的進行，集合DRj中存放的h個子樹沿著SRj的各條路徑動態(tài)地向前推進。

給子樹Ti分配編碼矢量時遵循的原則是其全局編碼矢量g（Ti）和同一動態(tài)集合中其他h-1個全局編碼矢量要彼此線性無關。也就是說，要保證接收節(jié)點Rj的h條不相鄰路徑上子樹的全局編碼矢量彼此線性無關。另外，由于子樹Ti可能位于多個接收節(jié)點的路徑上，因此這個線性無關的原則要保證對所有接收節(jié)點的動態(tài)集合都成立。

（5）根據(jù)所有子樹的全局編碼矢量計算得到各個編碼節(jié)點的局部編碼矢量。不失一般性，假設子樹T有m個父子樹節(jié)點T1，T2，…，Tm（一個子樹的父子樹是指與本子樹相連接，且從信息流上看位于本子樹上游的子樹節(jié)點。），則這些子樹的全局編碼矢量和局部編碼矢量（l1，l2，…，lm）的關系滿足［15］：

由于每個全局編碼矢量g（Ti）都是h維矢量，因此式（5）實際是一個由h個方程構成的方程組。如果該方程組的h×m維系數(shù)矩陣（g（T1），g（T2），…，g（Tm））的秩r=m，則在有限域上求解該方程組，即可得到子樹T的局部編碼矢量（l1，l2，…，lm）；如果r＜m，則出現(xiàn)多解。算法的偽代碼如下：

算法 LNCBSD

輸入 一個滿足組播條件的網(wǎng)絡拓撲圖G=（V，E，S，R），其中，V表示頂點集合；E表示邊集合；S是唯一的信源節(jié)點；R表示信宿節(jié)點集合

輸出 邊集合E中每條邊ei的全局編碼矢量g（ei）和局部編碼矢量l（ei）

在上述算法中，原圖用G=（V，E）表示，線圖用LG=（LV，LE）表示，子樹圖用T=（TV，TE）表示。原圖中的節(jié)點和邊分別用ni和ei表示；線圖和子樹圖中的節(jié)點和邊分別加前綴l和t。此外，用|·|表示集合的基數(shù)。

4.2 算法示例

在本例中，算法的輸入是如圖2所示的單源組播網(wǎng)絡。其中，節(jié)點S為信源，J，H，I分別為3個接收節(jié)點R1，R2，R3，S向3個接收節(jié)點組播傳輸2個符號σ1，σ2∈GF（2）。不難驗證，該網(wǎng)絡滿足組播條件，即S和每個接收節(jié)點之間的最小割都為2。

圖2 示例網(wǎng)絡

應用LNCBSD算法，具體步驟如下：

（1）生成與原圖相對應的線圖，如圖3所示。

圖3 圖2所對應的線圖

（2）基于線圖生成子樹圖，如圖4所示。

圖4 圖3化簡后的子樹圖

（3）接收節(jié)點R1，R2，R3分配靜態(tài)子樹集，結果為：SR1=｛T1，T2T3T4｝，SR2=｛T1，T2T5｝，SR3=｛T1T5，T2｝，即表明，源節(jié)點S通過子樹T1向接收節(jié)點R1傳輸符號σ1，通過子樹T2T3T4向接收節(jié)點R1傳輸符號σ2。S通過子樹T1向接收節(jié)點R2傳輸符號σ1，通過子樹T2T5向接收節(jié)點R2傳輸符號σ2。S通過子樹T1T5向接收節(jié)點R3傳輸符號σ1，通過子樹T2向接收節(jié)點R3傳輸符號σ2。

（4）動態(tài)地生成各個子樹的全局編碼矢量。其中，由于圖3中子樹T1和T2內(nèi)部流動的符號分別是σ1和σ2，因此自然得到T1子樹的全局編碼核g（T1）=（1 0），T2子樹的全局編碼核g（T2）=（0 1）。動態(tài)子樹集和子樹T3，T4，T5的全局編碼核的分配如表1所示。其中，分配g（T5）時要兼顧與g（T1）和g（T2）的線性無關性，因此，分配成g（T5）=（1 1）。另外，由于子樹內(nèi)部的所有節(jié)點（原圖中的邊）和該子樹使用相同的全局編碼矢量，因此自然地得到原圖所有邊的全局編碼矢量。本例中，以子樹T5為例，原圖中邊DG，GH，GI的全局編碼矢量都是（1 1）。

表1 全局編碼核的動態(tài)分配表

（5）假設線圖中編碼節(jié)點DF，DG，F(xiàn)J的局部編碼矢量分別為l（DF）=（l1l2），l（DG）=（l3l4），l（FJ）=（l5l6），則應用式（5）可得：

寫成向量的形式分別為：

解得l（DF）=（0 1），l（DG）=（1 1），l（FJ）=（0 1）。

經(jīng)過上述編碼過程，接收節(jié)點J的2條入邊收到的2個符號分別是σ1和σ2；接收節(jié)點H的2條入邊收到的2個符號分別是σ1和σ1⊕σ2；接收節(jié)點I的2條入邊收到的2個符號分別是σ1⊕σ2和σ2。經(jīng)過模2運算后，在H和I也可以恢復出σ1和σ2，實現(xiàn)了組播的功能。

4.3 算法分析

應用LNCBSD算法偽代碼中的符號，為了把原圖轉化為線圖，需要掃描原圖的全部邊并建立鄰接表，因此，其時間復雜度為O（|E|2）。由線圖生成子樹圖的過程中，廣度優(yōu)先搜索的復雜度為O（|LV|+ |LE|），所以生成子樹節(jié)點的復雜度為O（|LE||LV|+ |LE|2），拓撲排序的復雜度為O（|LV|+|LE|）。考慮到|LV|=|E|，且有|LE|=Θ（|E|），因此，生成子樹圖的復雜度為O（|E|2）。在子樹圖T中，為了給每個接收節(jié)點Ri建立靜態(tài)子樹集，需要在源節(jié)點S所位于的h個子樹和接收節(jié)點Ri所位于的h個子樹之間一一對應地建立h條路徑，其時間復雜度為O（h|TE|）。進一步，由于存在著|R|個接收節(jié)點，因此建立靜態(tài)子樹集的時間復雜度為O（h|TE||R|）。分配全局網(wǎng)絡編碼矢量g（tni）時，需要檢測h個h維向量的線性無關性，其復雜度為O（h2），所以為所有子樹分配全局網(wǎng)絡編碼矢量的復雜度為O（h2|TE||R|）。應用式（5）計算局部編碼矢量的復雜度為O（|TV|3）。

從譯碼的角度看，在每個接收節(jié)點處應用式（3）求解符號σ1，σ2，…，σh的復雜度是O（h2）。對大多數(shù)實際網(wǎng)絡，經(jīng)過子樹分解后，子樹圖的節(jié)點數(shù)和邊數(shù)都遠小于原始網(wǎng)絡的節(jié)點數(shù)和邊數(shù)，即|TV|＜＜|V|，|TE|＜＜|E|，所以，問題的規(guī)模和編碼復雜度大大降低。

4.4 仿真實驗

本節(jié)基于Matlab設計了一組仿真實驗對LNCBSD算法和文獻［10］提出的多項式時間算法的效率做比較。首先，作為算法的輸入，隨機生成一個由n個節(jié)點（標號為1～n）構成的有向無環(huán)網(wǎng)絡。為了防止環(huán)路的產(chǎn)生，網(wǎng)絡中有向邊都是由低序號節(jié)點指向高序號節(jié)點。2個節(jié)點之間的有向邊按照概率p=0.7生成。另外，節(jié)點1充當源節(jié)點，再選取滿足組播條件的2個接收節(jié)點。其次，在生成的網(wǎng)絡中執(zhí)行2種算法。為了比較算法的復雜度，對每次仿真讀取原圖和子樹圖的節(jié)點數(shù)和邊數(shù)進行比較，并統(tǒng)計2種算法的運行時間，結果如圖5～圖7所示?？梢?，子樹分解縮減了編碼問題的規(guī)模和算法的運行時間，本文算法是一種高效的網(wǎng)絡編碼算法。

圖5 原圖和子樹圖的節(jié)點數(shù)比較

圖6 原圖和子樹圖的邊數(shù)比較

圖7 LNCBSD和文獻［10］算法的運行時間比較

5 結束語

本文提出了一種基于子樹分解的組播網(wǎng)絡編碼算法（LNCBSD），該算法可用于解決固定拓撲有線網(wǎng)絡的單源組播網(wǎng)絡編碼問題。LNCBSD算法借助于線圖變換和子樹分解把原始網(wǎng)絡變成了子樹圖，每棵子樹始于源節(jié)點或編碼節(jié)點，終于接收節(jié)點或另一個編碼節(jié)點，在每棵子樹內(nèi)部流動著相同的符號，不需要進行編碼。由于子樹圖的節(jié)點數(shù)和邊數(shù)遠小于原始網(wǎng)絡的節(jié)點數(shù)和邊數(shù)，因此子樹分解大幅縮減了問題的規(guī)模和編碼的復雜度。因為網(wǎng)絡拓撲不變，所以算法只需要執(zhí)行一次就可以獲得各個邊的全局編碼矢量和局部編碼矢量，在隨后的數(shù)據(jù)組播過程中，接收節(jié)點只需要解析發(fā)送符號即可，不需要重復分配和計算編碼矢量。

LNCBSD算法是一種確定性算法，必須在拓撲已知的條件下有效，因此，不適用于如Ad Hoc這種拓撲可變的無線移動網(wǎng)絡。另外，算法還有一些不完善的地方和不適用的場合。這是下一步的研究方向，具體包括：（1）算法不適用于無向圖網(wǎng)絡和拓撲未知網(wǎng)絡，這需要用到諸如隨機網(wǎng)絡編碼等的分布式編碼方法。（2）算法沒有考慮傳輸延時造成的符號不同步接收問題，這可以通過對發(fā)送符號進行分組來解決。（3）算法對單源組播應用有效。對于多源組播應用，可以通過增加虛擬源節(jié)點和虛擬邊的方法轉換成單源組播問題。但對于其他任意的應用場景，比如多重單播、多源任意播等應用，則可能要用到矢量編碼甚至非線性編碼［8］。此外，針對實際應用中有環(huán)網(wǎng)絡、非單位容量邊以及鏈路失效等問題，還需要對本文算法進行改進。

［1］ Fragouli C，Soljanin E.Network Coding Fundamentals［J］. Foundations and Trends in Networking，2007，2（1）：33-42.

［2］ Yeung RW.信息論與網(wǎng)絡編碼［M］.蔡 寧，譯.北京：高等教育出版社，2011：411-483.

［3］ Koetter R，Medard M.An A lgebraic Approach to Network Coding［J］.IEEE/ACM Transactions on Network，2003，11（5）：782-795.

［4］ Cannons J，Dougherty R，F(xiàn)reiling C，et al.Network Routing Capacity［J］.IEEE Transactions on Information Theory，2006，52（3）：777-788.

［5］ Dougherty R，F(xiàn)reiling C，Zeger K.Unachievability of Network Coding Capacity［J］.IEEE Transactions on Information Theory，2006，52（6）：2365-2372.

［6］ Chekuri C，F(xiàn)ragouli C，Soljanin E.On Average Throughput and Alphabet Size in Network Coding［J］. IEEE Transactions on Information Theory，2006，52（6）：2410-2424.

［7］ Li S Y，Sun Q，Shao Z，et al.Linear Network Coding：Theory and Algorithm s［J］.Proceedings of the IEEE，2011，99（3）：372-387.

［8］ Dougherty R，F(xiàn)reiling C，Zeger K.Insufficiency of Linear Coding in Network Information Flow［J］.IEEE Transactions on Information Theory，2005，51（8）：2745-2759.

［9］ Kotter R，Kschischang F R.Coding for Errors and Erasures in Random Network Coding［J］.IEEE Transactions on Information Theory，2008，54（8）：3579-3591.

［10］ 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.

［11］ Jaggi S，Sanders P，Chou P A，et al.Polynom ial Time Algorithms for Multicast Network Code Construction［J］. IEEE Transactions on Information Theory，2005，51（6）：1973-1982.

［12］ Ebrahim i JB，F(xiàn)ragouli C.A lgebraic Algorithm for Vector Network Coding［J］.IEEE Transactions on Information Theory，2011，57（2）：996-1007.

［13］ Bassoli R，Marques H，Rodriguez J，et al.Network Coding Theory：A Survey［J］.IEEE Communications Surveys&Tutorials，2013，15（4）：1950-1978.

［14］ Ahlswede R，Cai N，Li S Y，et al.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46（4）：1204-1216.

［15］ Buckley F，Lew inter M.圖論簡明教程［M］.李慧霸，王鳳芹，譯.北京：清華大學出版社，2005：69-70.

［16］ Harvey N JA，Karger D R，Murota K.Deterministic Network Coding by Matrix Completion［C］//Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithm.New York，USA：ACM Press，2005：489-498.

［17］ Fragouli C，Soljanin E.Information Flow Decomposition for Network Coding［J］.IEEE Transactions on Information Theory，2004，52（3）：829-848.

［18］ Montanari A，Urbanke R L.Iterative Coding for Network Coding［J］.IEEE Transactions on Information Theory，2013，59（3）：1563-1572.

［19］ Lien C，Chang C，Lee D.A Universal Stabilization Algorithm for Multicast Flows with Network Coding［J］. IEEE Transactions on Communications，2013，61（2）：712-721.

［20］ Marden JR，Effros M.The Price of Selfishness in Network Coding［J］.IEEE Transactions on Information Theory，2012，58（4）：2349-2361.

［21］ 文瑞涵，馮 鋼.基于網(wǎng)絡編碼的多跳無線網(wǎng)絡可靠組播［J］.電子與信息學報，2012，34（11）：2721-2727.

［22］ 屈毓錛，陳 晨，董 超，等.基于Markov狀態(tài)轉移方法的網(wǎng)絡編碼時延分析［J］.通信學報，2013，34（9）：77-83.

［23］ 郭網(wǎng)媚，李 娜，王 驍.序列矩陣表示的卷積網(wǎng)絡編碼的譯碼方法［J］.吉林大學學報，2013，43（4）：1076-1081.

［24］ Ahuja R K，Magnanti R L，Orlin JB.Network Flows［M］. Englewood Cliffs，USA：Prentice Hall，1993：77-79.

編輯 金胡考

A Multicast Linear Network Coding Algorithm Based on Subtree Decomposition

LIU Yantao，XIA Guiyang，XU Jing，QIN Na
（College of Engineering，Bohai University，Jinzhou 121000，China）

Aiming at network coding for single source multicast networks w th fixed topology，this paper proposes a Linear Network Coding（LNC）algorithm based on subtree decomposition.It is com posed of five steps：line graph transforming，subtree decomposition，edge disjoint path search，global coding vector assignment and local coding vector calculation.The algorithm starts with input of a Directed Acyclic Graph（DAG）with multicast property，and ends with output of global coding vectors and local coding vectors of each edge.Subtree decomposition is based on such a consideration that there is no need of coding within a subtree but only between subtrees.It is proved by theoretical analyses and experimental results show that，both network scale and complexity of path search and coding are greatly decreased through subtree decomposition，which greatly decreases running time of network coding algorithm.It can draw the conclusion that the proposed algorithm is an efficient algorithm to single source multicast networks.

Linear Network Coding（LNC）；Directed Acyclic Graph（DAG）；line graph；subtree decomposition；coding vector

劉宴濤，夏桂陽，徐 靜，等.一種基于子樹分解的組播線性網(wǎng)絡編碼算法［J］.計算機工程，2015，41（11）：153-159.

英文引用格式：Liu Yantao，Xia Guiyang，Xu Jing，et al.A Multicast Linear Network Coding Algorithm Based on Subtree Decomposition［J］.Computer Engineering，2015，41（11）：153-159.

1000-3428（2015）11-0153-07

A

TN915

10.3969/j.issn.1000-3428.2015.11.027

國家自然科學基金資助項目（61101129，61227001）；山東省航天創(chuàng)新基金資助項目（2014JJ005）。

劉宴濤（1975-），男，副教授、博士，主研方向：Ad Hoc網(wǎng)絡，網(wǎng)絡編碼，網(wǎng)絡仿真；夏桂陽、徐 靜、秦 娜，碩士研究生。

2014-08-18

2014-12-24 E-m ail：liuyantaocn@163.com