一種改進(jìn)的多源組播網(wǎng)絡(luò)的線性網(wǎng)絡(luò)編碼構(gòu)造方案

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

從圖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 是由源點(diǎn)廣播的信息。

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

在宿點(diǎn)r 處，解碼的線性方程組如下：

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

圖6 子圖2 的編碼信道

圖7 改進(jìn)后的子圖2 的編碼信道

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

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

表2 各宿點(diǎn)輸入信道的全局編碼向量

5 結(jié)語

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