一種改進的多源組播網絡的線性網絡編碼構造方案

盧花，高海波，張誠，馮新

（湖南涉外經濟學院信息與機電工程學院，長沙410205）

0 引言

網絡編碼[1-2]技術通過向網絡多播中的一些節點附加編碼操作來最大化源點和每個宿點之間的多播容量。網絡編碼可以提高網絡性能，甚至改變網絡結構。其中,線性網絡編碼是重點研究方向。在文獻[3]中，為了實現網絡的最大吞吐量，子圖問題通過組合優化解決。在考慮分源點優先級的情況下，提出了基于單目標優化的子圖劃分方法。文獻[4]研究了多播節點執行網絡編碼的時間。實驗數據表明，在極端情況下，節點編碼操作的成本將產生很大的影響。文獻[5]提出了多種方法降低網絡編碼成本。因要考慮多源組播網絡中節點編碼和解碼的時間要求[6]，需要優化網絡編碼算法。利用粒子群優化算法進行子圖劃分[7-8]，可以優化子圖的線性網絡編碼方案。

1 線性網絡編碼

網絡編碼允許中間節點復制和轉發信息，中間節點對輸入的信息還可以進行編碼，再將編碼后的信息轉發給下游節點，后者起到編碼器的作用。網絡編碼節點可以對從輸入信息進行編碼，并相應地將編碼信息輸出到相應鏈路。在接收節點處，解碼器對接收的多播信息進行解碼。如果節點對輸入信息進行線性編碼，則稱為線性網絡編碼。

圖1 和圖2 中所示的蝶形網絡說明了網絡編碼和路由的不同性質以及網絡編碼的優點。它也是可以實現最大多播容量的網絡編碼的示例。在網絡編碼示例中，每個信道僅使用一次，這不僅減少了傳輸次數，使網絡負載更加平衡，同時減少了網絡延遲并增加了網絡吞吐量。

圖1 傳統路由示例

圖2 網絡編碼示例

文獻[9-10]中單源組播網絡采用網絡編碼技術能獲得最大組播能力，而利用傳統的路由傳輸技術很難實現這種最大流量邊界。

2 線性網絡編碼的構造

線性網絡編碼針對單位容量的信道進行編碼，容量大于1 的信道被劃分為多條單位容量的信道。

源點播出的字符和信道的全局編碼向量構成一個線性方程。在接收點r(r ∈R)，可獲得相應的解碼方程組。只有當該方程組的系數矩陣的秩為h 時，才能求得源點廣播的信息。

從圖3 可以看出，信宿r 從第一輸入信道接收的信息是y1=4*x1+2*x2，信宿r 從第二輸入信道接收的信息是y2=7*x1+3*x2，信宿r 從第三輸入信道接收的信息是y3=2*x1+7*x2。其中，x1、x2 和x3 是由源點廣播的信息。

圖3 線性網絡編碼示例

在宿點r 處，解碼的線性方程組如下：

此系數矩陣的秩為3，解線性方程組可恢復出s 播出的信息x1、x2 和x3。

3 改進的線性網絡編碼的構造

改進的線性網絡編碼的思想是：采用傳統路由方式與線性網絡編碼相結合的方式進行傳輸。對于每一個節點，先計算該節點的入度，以及該節點與相連的每個后續節點之間的吞吐量，若入度小于等于每一個相連節點之間的吞吐量，則這樣的節點采用路由方式對信息進行存儲和轉發，而無需進行網絡編碼。若入度大于任意一個與之相連的后續節點之間的吞吐量，則此節點無法通過傳統路由方式保證吞吐量，這樣的節點需要進行線性網絡編碼，輸出信息是該點所有輸入字符的線性組合。

對于節點v∈V，記節點v 的入度為Indegree(v)=W(E1,v)+W(E2,v)+…+W(Ein,v)，E1,v表示以節點1 為弧尾，v 節點為弧頭的弧線，in 表示以v 節點為弧頭，與該節點相連的所有節點數目，W(E1,v)表示以節點1 為弧尾，v 節點為弧頭的所有弧線數量，即有向邊的權值。記節點v的出度為Outdegree(v)=W(Ev,1)+W(Ev,2)+…+W(Ev,out)，Ev,1表示以節點v 為弧尾，1 節點為弧頭的弧線，out 表示以v 節點為弧尾，與該節點相連的節點數目，W(Ev,1)表示以節點v 為弧尾，1 節點為弧頭的所有弧線數量，即有向邊的容量，則節點v 與相連的后續節點之間的容量為{W(Ev,1),W(Ev,2),…,W(Ev,out)}，若?(W(Ev,i))≥Indegree(v)(i=1,…,out)，節點v 采用路由方式對信息進行存儲和轉發，不進行網絡編碼。若?(W(Ev,i))≤Indegree(v)(i=1,…,out)，則節點v 進行隨機線性網絡編碼。同理，計算出全局編碼矩陣的逆矩陣，可恢復出源點的信息。

如圖4 所示，節點A、B、D 的入度均為1，后續每一個相連節點之間的容量均為1，入度小于等于相連的后續節點之間的容量，則節點A、B、D 采用路由方式對信息進行存儲和轉發，而無需進行網絡編碼，圖中用虛線表示。節點C 的入度為2，出度為1，入度大于等于任意一個與之相連的后續節點之間的容量，節點C 無法通過一次傳統路由方式傳輸信息x1 和x2，節點C 進行線性網絡編碼，輸出信息是x1 和x2 的線性組合。

圖4 改進的線性網絡編碼

4 仿真實驗與結果分析

圖5 有向無環網絡G1

s1 對應宿點{r1,r2,r3}，s2 對應宿點{r4,r5,r6}，s3 對應宿點{r6,r7,r8}，{t1,t2,t3}為虛擬宿點集。對G1 劃分子圖，選取pareto 解集為{4,4,3}，得到3 個子圖。假定優先考慮s2 的吞吐率，圖6 子圖2 中顯示的信道可使s2獲得最大組播容量，得到了從源點到各宿點的邊互不重疊的傳輸路徑，得到了一個可行的編碼方案。

圖7 顯示了改進編碼方案后時s2組播信息所經由的信道，可獲得最大組播容量，與圖6 的編碼信道相比較，虛線部分的有向鏈路2-7、8-13、8-14、12-18、12-19、14-21、21-r6 均為存儲轉發方式，并未參與網絡編碼。在一定程度上節省了時間和存儲資源。

圖6 子圖2 的編碼信道

圖7 改進后的子圖2 的編碼信道

表1 各編碼節點的局部編碼向量

表1 是各編碼節點隨機生成的局部編碼向量，表2是各宿點對應各信道的全局編碼向量，以宿點r4 為例，根據線性網絡編碼構造方案求解源點發出的字符。

表2 各宿點輸入信道的全局編碼向量

5 結語

網絡編碼技術可以提高組播吞吐量。如果網絡中的某些節點或信道發生故障，接收器仍然可以解碼。網絡編碼可以增強網絡的容錯能力，改善了網絡鏈路的負載均衡，實現了多目標優化，無需其他加密算法，可以改善網絡安全性。在后續工作中，需要考慮多源組播的安全性，并進一步完善本文的解決方案。