胡 平

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

在目前的通信網(wǎng)絡(luò)中，不管是采用電路交換還是采用分組交換的方式傳輸信息，中間節(jié)點(diǎn)都僅僅轉(zhuǎn)發(fā)或存儲轉(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ā)信息前對輸入信息流進(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è)計了一個數(shù)學(xué)框架。另外Sanders等人提出了一種實(shí)現(xiàn)網(wǎng)絡(luò)編碼的多項式時間算法[4-5]，這種方法將網(wǎng)絡(luò)編碼的構(gòu)造進(jìn)一步簡化。

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

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

在研究網(wǎng)絡(luò)編碼的過程中，通信網(wǎng)一般簡化為相應(yīng)的圖來表示。假定有一個(如圖1所示)的通信網(wǎng)絡(luò)，這是一個擁有單個信源和2個接收節(jié)點(diǎn)的網(wǎng)絡(luò)，假設(shè)每條鏈路都無時延和無差錯。其中，s是信源節(jié)點(diǎn)，y和z是接收節(jié)點(diǎn)。圖1(a)給出了每條邊的信息速率均為1 bit/單位時間。由最大流最小割定理容易得出從信源s到接收節(jié)點(diǎn)y和z的最大流均為2。由此得到信源s可以同時發(fā)送2 bit信息給y和z。但是，如果按如圖1(b)傳統(tǒng)路由方式，在1個單位時間內(nèi)將無法完成以上傳輸。圖1(c)給出一種編碼方案，從圖中可以看出，為了從信源節(jié)點(diǎn)s同時傳輸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。因此，在這個簡單的組播問題中，中間節(jié)點(diǎn)w不再只進(jìn)行簡單的存儲轉(zhuǎn)發(fā)，而是引入一定的操作，從而可以在1個單位時間內(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)對信息bit流進(jìn)行一定的操作，如模 2“加”、“與”、“或”等，而不是僅僅對其進(jìn)行復(fù)制轉(zhuǎn)發(fā)。

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

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

(1)Ω′(s)=Ω。

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

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

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

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

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

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

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

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

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

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

把有環(huán)網(wǎng)絡(luò)分為兩部分：(1)先將其看作是個無環(huán)無時延網(wǎng)絡(luò)，分配其編碼向量；(2)考慮每個節(jié)點(diǎn)的時延，設(shè)當(dāng)前時刻為 t，k個單位時延的因子即為 σ(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)移矩陣來描述輸入變量與輸出變量之間的關(guān)系。設(shè)節(jié)點(diǎn)v是網(wǎng)絡(luò)中的唯一信源，用x=(X(v，1)，X(v，2)，…，X(v，μ(v)))來表示信源 v 的輸出，其中X(v，μ(v))是一個離散隨機(jī)過程，μ(v)表示信源的出度。置用 z=(Z(v，1)，Z(v，2)，…，Z(v，η(v)))來表示信宿節(jié)點(diǎn)v 的輸入。同理，Z(v，μ(v))是一個離散隨機(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 是一個|E|×|E|的單位陣。

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

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

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

本文簡要介紹了網(wǎng)絡(luò)編碼以及線性網(wǎng)絡(luò)編碼的基本原理，提出了一種基于有環(huán)網(wǎng)絡(luò)的改進(jìn)代數(shù)構(gòu)造算法，有效地解決了網(wǎng)絡(luò)中存在環(huán)路時的編碼問題。網(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.