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

（渤海大學(xué)工學(xué)院，遼寧錦州121000）

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

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

（渤海大學(xué)工學(xué)院，遼寧錦州121000）

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

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

1 概述

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

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

本文從工程應(yīng)用方面出發(fā)，針對(duì)拓?fù)洳蛔兊膯卧唇M播網(wǎng)絡(luò)提出一種基于子樹分解的線性網(wǎng)絡(luò)編碼算法（Linear Network Coding Based on Subtree Decomposition，LNCBSD），通過子樹分解的預(yù)處理過程把網(wǎng)絡(luò)圖縮減為子樹圖，利用靜態(tài)子樹集和動(dòng)態(tài)子樹集的方法為每棵子樹分配全局編碼矢量，并進(jìn)一步計(jì)算局部編碼矢量。

2 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

4 LNCBSD算法

4.1 算法說明

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

具體過程如下：

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

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

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

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

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

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

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

算法 LNCBSD

輸入 一個(gè)滿足組播條件的網(wǎng)絡(luò)拓?fù)鋱DG=（V，E，S，R），其中，V表示頂點(diǎn)集合；E表示邊集合；S是唯一的信源節(jié)點(diǎn)；R表示信宿節(jié)點(diǎn)集合

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

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

4.2 算法示例

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

圖2 示例網(wǎng)絡(luò)

應(yīng)用LNCBSD算法，具體步驟如下：

（1）生成與原圖相對(duì)應(yīng)的線圖，如圖3所示。

圖3 圖2所對(duì)應(yīng)的線圖

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

圖4 圖3化簡后的子樹圖

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

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

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

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

寫成向量的形式分別為：

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

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

4.3 算法分析

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

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

4.4 仿真實(shí)驗(yàn)

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

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

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

圖7 LNCBSD和文獻(xiàn)［10］算法的運(yùn)行時(shí)間比較

5 結(jié)束語

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

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

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

［2］ Yeung RW.信息論與網(wǎng)絡(luò)編碼［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］.李慧霸，王鳳芹，譯.北京：清華大學(xué)出版社，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)絡(luò)編碼的多跳無線網(wǎng)絡(luò)可靠組播［J］.電子與信息學(xué)報(bào)，2012，34（11）：2721-2727.

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

［23］ 郭網(wǎng)媚，李 娜，王 驍.序列矩陣表示的卷積網(wǎng)絡(luò)編碼的譯碼方法［J］.吉林大學(xué)學(xué)報(bào)，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)絡(luò)編碼算法［J］.計(jì)算機(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

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

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

2014-08-18

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