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

（湖南涉外經(jīng)濟學(xué)院信息與機電工程學(xué)院，長沙410205）

0 引言

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

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

網(wǎng)絡(luò)編碼允許中間節(jié)點復(fù)制和轉(zhuǎn)發(fā)信息，中間節(jié)點對輸入的信息還可以進行編碼，再將編碼后的信息轉(zhuǎn)發(fā)給下游節(jié)點，后者起到編碼器的作用。網(wǎng)絡(luò)編碼節(jié)點可以對從輸入信息進行編碼，并相應(yīng)地將編碼信息輸出到相應(yīng)鏈路。在接收節(jié)點處，解碼器對接收的多播信息進行解碼。如果節(jié)點對輸入信息進行線性編碼，則稱為線性網(wǎng)絡(luò)編碼。

圖1 和圖2 中所示的蝶形網(wǎng)絡(luò)說明了網(wǎng)絡(luò)編碼和路由的不同性質(zhì)以及網(wǎng)絡(luò)編碼的優(yōu)點。它也是可以實現(xiàn)最大多播容量的網(wǎng)絡(luò)編碼的示例。在網(wǎng)絡(luò)編碼示例中，每個信道僅使用一次，這不僅減少了傳輸次數(shù)，使網(wǎng)絡(luò)負(fù)載更加平衡，同時減少了網(wǎng)絡(luò)延遲并增加了網(wǎng)絡(luò)吞吐量。

圖1 傳統(tǒng)路由示例

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

文獻[9-10]中單源組播網(wǎng)絡(luò)采用網(wǎng)絡(luò)編碼技術(shù)能獲得最大組播能力，而利用傳統(tǒng)的路由傳輸技術(shù)很難實現(xiàn)這種最大流量邊界。

2 線性網(wǎng)絡(luò)編碼的構(gòu)造

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

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

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

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

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

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

3 改進的線性網(wǎng)絡(luò)編碼的構(gòu)造

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

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

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

圖4 改進的線性網(wǎng)絡(luò)編碼

4 仿真實驗與結(jié)果分析

圖5 有向無環(huán)網(wǎng)絡(luò)G1

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

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

圖6 子圖2 的編碼信道

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

表1 各編碼節(jié)點的局部編碼向量

表1 是各編碼節(jié)點隨機生成的局部編碼向量，表2是各宿點對應(yīng)各信道的全局編碼向量，以宿點r4 為例，根據(jù)線性網(wǎng)絡(luò)編碼構(gòu)造方案求解源點發(fā)出的字符。

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

5 結(jié)語

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