一種網(wǎng)絡(luò)編碼構(gòu)造算法研究

胡 平

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

在目前的通信網(wǎng)絡(luò)中，不管是采用電路交換還是采用分組交換的方式傳輸信息，中間節(jié)點(diǎn)都僅僅轉(zhuǎn)發(fā)或存儲(chǔ)轉(zhuǎn)發(fā)它所接收到的信息，除了數(shù)據(jù)復(fù)制以外，網(wǎng)絡(luò)的中間節(jié)點(diǎn)并不需要做任何其他的數(shù)據(jù)處理。

2000年，Ahlswede等人發(fā)表了一篇題為“網(wǎng)絡(luò)信息流”的文章，提出了“網(wǎng)絡(luò)編碼”這一概念，該理論通過允許中間節(jié)點(diǎn)在轉(zhuǎn)發(fā)信息前對(duì)輸入信息流進(jìn)行編碼，以實(shí)現(xiàn)網(wǎng)絡(luò)組播容量的極限。但這只是給出了網(wǎng)絡(luò)最大信息傳送速率的存在性證明，并沒有給出具體的網(wǎng)絡(luò)編碼實(shí)現(xiàn)方式。Li、Yeung和Cai[1]提出單一信源、多接收節(jié)點(diǎn)網(wǎng)絡(luò)的最大傳輸速率可以通過線性網(wǎng)絡(luò)編碼實(shí)現(xiàn)；Koetter和Medard[2-3]為網(wǎng)絡(luò)編碼設(shè)計(jì)了一個(gè)數(shù)學(xué)框架。另外Sanders等人提出了一種實(shí)現(xiàn)網(wǎng)絡(luò)編碼的多項(xiàng)式時(shí)間算法[4-5]，這種方法將網(wǎng)絡(luò)編碼的構(gòu)造進(jìn)一步簡(jiǎn)化。

上述方法都是基于已知整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔ⅰhou等提出了不需網(wǎng)絡(luò)拓?fù)湫畔⒌姆植际骄W(wǎng)絡(luò)編碼[6]。另外，現(xiàn)在關(guān)于網(wǎng)絡(luò)編碼和其他方面結(jié)合的研究也很多，例如網(wǎng)絡(luò)編碼和糾錯(cuò)碼的結(jié)合、網(wǎng)絡(luò)編碼和加密體制的結(jié)合等。

1 網(wǎng)絡(luò)編碼原理

在研究網(wǎng)絡(luò)編碼的過程中，通信網(wǎng)一般簡(jiǎn)化為相應(yīng)的圖來(lái)表示。假定有一個(gè)(如圖1所示)的通信網(wǎng)絡(luò)，這是一個(gè)擁有單個(gè)信源和2個(gè)接收節(jié)點(diǎn)的網(wǎng)絡(luò)，假設(shè)每條鏈路都無(wú)時(shí)延和無(wú)差錯(cuò)。其中，s是信源節(jié)點(diǎn)，y和z是接收節(jié)點(diǎn)。圖1(a)給出了每條邊的信息速率均為1 bit/單位時(shí)間。由最大流最小割定理容易得出從信源s到接收節(jié)點(diǎn)y和z的最大流均為2。由此得到信源s可以同時(shí)發(fā)送2 bit信息給y和z。但是，如果按如圖1(b)傳統(tǒng)路由方式，在1個(gè)單位時(shí)間內(nèi)將無(wú)法完成以上傳輸。圖1(c)給出一種編碼方案，從圖中可以看出，為了從信源節(jié)點(diǎn)s同時(shí)傳輸2 bit信息b1，b2到接收節(jié)點(diǎn)，則在中間節(jié)點(diǎn) w處，必須通過網(wǎng)絡(luò)編碼，使輸出邊(w，x)傳輸 2條輸入邊上所攜帶信息的線性組合 b1+b2(模 2加)，那么在接收節(jié)點(diǎn) y和 z處，才可分別由 b1+b2和 b1、b1+b2和b2通過模2加恢復(fù)出所有的信息 b1、b2。因此，在這個(gè)簡(jiǎn)單的組播問題中，中間節(jié)點(diǎn)w不再只進(jìn)行簡(jiǎn)單的存儲(chǔ)轉(zhuǎn)發(fā)，而是引入一定的操作，從而可以在1個(gè)單位時(shí)間內(nèi)把 2 bit的信息傳輸給接收節(jié)點(diǎn) y和z，這就是網(wǎng)絡(luò)編碼的思想。

圖1 經(jīng)典網(wǎng)絡(luò)編碼原理圖

網(wǎng)絡(luò)編碼的定義：網(wǎng)絡(luò)中的節(jié)點(diǎn)對(duì)信息bit流進(jìn)行一定的操作，如模 2“加”、“與”、“或”等，而不是僅僅對(duì)其進(jìn)行復(fù)制轉(zhuǎn)發(fā)。

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

通信網(wǎng)絡(luò)G=(V，E)上的線性碼組播(LCM)是指給通信網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn) v∈V分配向量空間Ω′(v)，同時(shí)給每條邊e∈E分配全局編碼向量Ve(e)。其中：

(1)Ω′(s)=Ω。

(2)Ve(e)∈Ω′(v)對(duì)每一個(gè) e=(v，v′)。

<·>代表其中的向量張成的空間。

(4)對(duì)節(jié)點(diǎn)T輸出邊分配的編碼向量是其輸入邊所分配的編碼向量的線性組合。

LCMV刻畫了一種信息數(shù)據(jù)在網(wǎng)絡(luò)中傳播的結(jié)構(gòu)。將信源節(jié)點(diǎn)s要傳輸?shù)男畔⒎殖蒱維的向量組，稱作信息向量。在傳輸過程中，一條邊上承載的數(shù)據(jù)符號(hào)是信息向量和該邊所分配的向量的向量積。

對(duì)于圖中的通信網(wǎng)絡(luò)，網(wǎng)絡(luò)編碼的基域?yàn)?F2，可以如下給各條邊分配全局編碼向量：

信源s的信息向量為(b1b2)，每條邊上傳輸?shù)男畔⒎?hào)為信息向量(b1b2)和該邊的編碼列向量的向量積。

3 有環(huán)網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼

上面考慮的網(wǎng)絡(luò)編碼都是基于無(wú)環(huán)無(wú)時(shí)延的，不具有一般性意義。

當(dāng)信息流在有環(huán)網(wǎng)絡(luò)傳播的時(shí)候，時(shí)延成為構(gòu)造網(wǎng)絡(luò)編碼必須要考慮的問題。為了數(shù)學(xué)上的方便，將環(huán)上節(jié)點(diǎn)處理的時(shí)延設(shè)為1個(gè)單位時(shí)延。這與卷積編碼器有關(guān)，卷積編碼器由一系列移位寄存器和加法器構(gòu)成，即信息流通過有時(shí)延的節(jié)點(diǎn)相當(dāng)于通過移位寄存器。

當(dāng)網(wǎng)絡(luò)圖存在1個(gè)或多個(gè)環(huán)時(shí)，假設(shè)每個(gè)節(jié)點(diǎn)都有單位時(shí)延，把網(wǎng)絡(luò)圖看成是有限域網(wǎng)絡(luò)卷積碼的組合，則移位寄存器的個(gè)數(shù)等同于圖中邊的數(shù)量。

把有環(huán)網(wǎng)絡(luò)分為兩部分：(1)先將其看作是個(gè)無(wú)環(huán)無(wú)時(shí)延網(wǎng)絡(luò)，分配其編碼向量；(2)考慮每個(gè)節(jié)點(diǎn)的時(shí)延，設(shè)當(dāng)前時(shí)刻為 t，k個(gè)單位時(shí)延的因子即為 σ(t+k)，則求出的編碼向量即為Ve(e)·σ(t+k)。

4 基于有環(huán)網(wǎng)絡(luò)的代數(shù)構(gòu)造算法

基于有環(huán)網(wǎng)絡(luò)如代數(shù)構(gòu)造算法如下：

(1)引入系統(tǒng)轉(zhuǎn)移矩陣來(lái)描述輸入變量與輸出變量之間的關(guān)系。設(shè)節(jié)點(diǎn)v是網(wǎng)絡(luò)中的唯一信源，用x=(X(v，1)，X(v，2)，…，X(v，μ(v)))來(lái)表示信源 v 的輸出，其中X(v，μ(v))是一個(gè)離散隨機(jī)過程，μ(v)表示信源的出度。置用 z=(Z(v，1)，Z(v，2)，…，Z(v，η(v)))來(lái)表示信宿節(jié)點(diǎn)v 的輸入。同理，Z(v，μ(v))是一個(gè)離散隨機(jī)過程，η(v)表示信源v的出度。則輸入變量和輸出變量之間的關(guān)系可以表示為：z=xM，其中M稱為系統(tǒng)轉(zhuǎn)移矩陣。所以，要想在信宿節(jié)點(diǎn)由接收到的消息向量z得到信源輸入x，則必須要求系統(tǒng)轉(zhuǎn)移矩陣M的行列式不為0。

(2)已知通信網(wǎng)絡(luò)的信源輸出矩陣A，信宿節(jié)點(diǎn)輸入矩陣 B，網(wǎng)絡(luò)的鄰接矩陣 F，則系統(tǒng)轉(zhuǎn)移矩陣M=A(IF)-1BT，其中 I 是一個(gè)|E|×|E|的單位陣。

(3)可以將系統(tǒng)轉(zhuǎn)移矩陣M的每一個(gè)列向量作為每條邊分配的編碼向量。

(4)以及將網(wǎng)絡(luò)圖簡(jiǎn)化，可以把網(wǎng)絡(luò)圖可以分成幾個(gè)子集合，使它們具有相同的特性：①每1個(gè)子集合只含有1個(gè)信源節(jié)點(diǎn)或1個(gè)編碼節(jié)點(diǎn)；②1個(gè)既不是信源節(jié)點(diǎn)也不是編碼節(jié)點(diǎn)的節(jié)點(diǎn)屬于1個(gè)子集合，這個(gè)子集合包含它最近的祖先編碼節(jié)點(diǎn)或信源節(jié)點(diǎn)。“子樹分解”把1個(gè)網(wǎng)絡(luò)劃分為不同的子圖，而屬于同1個(gè)子圖的所有節(jié)點(diǎn)流過的信息流都是相同的。對(duì)1個(gè)編碼設(shè)計(jì)問題來(lái)說，只需要知道怎樣相連，而1個(gè)子樹里面的網(wǎng)絡(luò)結(jié)構(gòu)是什么樣的卻并不起什么作用。因此，可以把每1個(gè)子圖看成1個(gè)節(jié)點(diǎn)，并保留連接子圖的邊。

(5)通過一個(gè)環(huán)記為1個(gè)時(shí)延，即信息流通過有時(shí)延的節(jié)點(diǎn)相當(dāng)于通過移位寄存器。用一系列移位寄存器和加法器構(gòu)成網(wǎng)絡(luò)圖，并求出時(shí)延因子σ，每條分配的編碼向量為 Ve(e)·σ。

本文簡(jiǎn)要介紹了網(wǎng)絡(luò)編碼以及線性網(wǎng)絡(luò)編碼的基本原理，提出了一種基于有環(huán)網(wǎng)絡(luò)的改進(jìn)代數(shù)構(gòu)造算法，有效地解決了網(wǎng)絡(luò)中存在環(huán)路時(shí)的編碼問題。網(wǎng)絡(luò)編碼技術(shù)方興未艾，研究前景十分廣闊。

[1]LI S R，YEUNG R W.Linear network coding[J].IEEE Transaction on Information Theory， 2003，49(2)：371-381.

[2]KOETTER R， MEDARD M.Beyond routing：an algebraic approach to network coding[J].IEEE Computer and Communications Societies， 2002，1(1)：122-130.

[3]KOETTER R，MEDARD M.An algebraic approach to net-work coding[J].IEEE Transactions on Networking， 2003，1(11)：782-795.

[4]SANDERS P，EGNER S.Polynomial time algorithms for network information flow[M].New York， USA：ACM， 2003.

[5]JAGGI S， SANDERS P， CHOU P A， et al.Polynomial time algorithms for network code construction [J].IEEE Transaction on Information Theory， 2005，51(6)：831-836.

[6]CHOU P A，WU Y，JAIN K.Practical network coding[C].In 41stAnnualAllerton Conference on Communication Control and Computing，2003.