一種網絡編碼構造算法研究

胡 平

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

在目前的通信網絡中，不管是采用電路交換還是采用分組交換的方式傳輸信息，中間節點都僅僅轉發或存儲轉發它所接收到的信息，除了數據復制以外，網絡的中間節點并不需要做任何其他的數據處理。

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

上述方法都是基于已知整個網絡的拓撲信息。Chou等提出了不需網絡拓撲信息的分布式網絡編碼[6]。另外，現在關于網絡編碼和其他方面結合的研究也很多，例如網絡編碼和糾錯碼的結合、網絡編碼和加密體制的結合等。

1 網絡編碼原理

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

圖1 經典網絡編碼原理圖

網絡編碼的定義：網絡中的節點對信息bit流進行一定的操作，如模 2“加”、“與”、“或”等，而不是僅僅對其進行復制轉發。

2 線性網絡編碼

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

(1)Ω′(s)=Ω。

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

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

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

LCMV刻畫了一種信息數據在網絡中傳播的結構。將信源節點s要傳輸的信息分成h維的向量組，稱作信息向量。在傳輸過程中，一條邊上承載的數據符號是信息向量和該邊所分配的向量的向量積。

對于圖中的通信網絡，網絡編碼的基域為 F2，可以如下給各條邊分配全局編碼向量：

信源s的信息向量為(b1b2)，每條邊上傳輸的信息符號為信息向量(b1b2)和該邊的編碼列向量的向量積。

3 有環網絡的網絡編碼

上面考慮的網絡編碼都是基于無環無時延的，不具有一般性意義。

當信息流在有環網絡傳播的時候，時延成為構造網絡編碼必須要考慮的問題。為了數學上的方便，將環上節點處理的時延設為1個單位時延。這與卷積編碼器有關，卷積編碼器由一系列移位寄存器和加法器構成，即信息流通過有時延的節點相當于通過移位寄存器。

當網絡圖存在1個或多個環時，假設每個節點都有單位時延，把網絡圖看成是有限域網絡卷積碼的組合，則移位寄存器的個數等同于圖中邊的數量。

把有環網絡分為兩部分：(1)先將其看作是個無環無時延網絡，分配其編碼向量；(2)考慮每個節點的時延，設當前時刻為 t，k個單位時延的因子即為 σ(t+k)，則求出的編碼向量即為Ve(e)·σ(t+k)。

4 基于有環網絡的代數構造算法

基于有環網絡如代數構造算法如下：

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

(2)已知通信網絡的信源輸出矩陣A，信宿節點輸入矩陣 B，網絡的鄰接矩陣 F，則系統轉移矩陣M=A(IF)-1BT，其中 I 是一個|E|×|E|的單位陣。

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

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

(5)通過一個環記為1個時延，即信息流通過有時延的節點相當于通過移位寄存器。用一系列移位寄存器和加法器構成網絡圖，并求出時延因子σ，每條分配的編碼向量為 Ve(e)·σ。

本文簡要介紹了網絡編碼以及線性網絡編碼的基本原理，提出了一種基于有環網絡的改進代數構造算法，有效地解決了網絡中存在環路時的編碼問題。網絡編碼技術方興未艾，研究前景十分廣闊。

[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.