張東秋

(牡丹江師范學(xué)院 計算機(jī)與信息技術(shù)學(xué)院，牡丹江157011)

非線性隨機(jī)網(wǎng)絡(luò)編碼研究

張東秋

(牡丹江師范學(xué)院 計算機(jī)與信息技術(shù)學(xué)院，牡丹江157011)

針對網(wǎng)絡(luò)編碼里的“全有或全無”以及因線性網(wǎng)絡(luò)編碼糾錯能力過低而導(dǎo)致重傳代價過大的問題，提出了非線性隨機(jī)網(wǎng)絡(luò)編碼的方法.該法用有限域上非線性函數(shù)的系數(shù)代替線性網(wǎng)絡(luò)編碼里的線性函數(shù)系數(shù)，在中間節(jié)點用一般的非線性函數(shù)對上游消息進(jìn)行復(fù)合函數(shù)操作，在信宿節(jié)點用查表法進(jìn)行譯碼.實驗結(jié)果表明：非線性隨機(jī)網(wǎng)絡(luò)編碼比線性網(wǎng)絡(luò)編碼具有更低的能量消耗、更低的時延，碼的長度相同時能糾正更多的錯誤.

網(wǎng)絡(luò)編碼；非線性；糾錯

網(wǎng)絡(luò)編碼技術(shù)可以增強多播網(wǎng)絡(luò)的吞吐量，具有巨大的應(yīng)用前景[1].目前網(wǎng)絡(luò)編碼主要采用線性編碼方案[2],線性網(wǎng)絡(luò)編碼主要采用有限域上的線性函數(shù)進(jìn)行運算.在線性隨機(jī)網(wǎng)絡(luò)編碼中，每個數(shù)據(jù)包的頭部都攜帶一個編碼向量，該向量為待解n維消息向量的系數(shù)向量[3].假若中間節(jié)點從K條入邊收到K個消息，對于其每一條出邊，會在本地隨機(jī)產(chǎn)生一個K維的有限域上的向量，利用該向量與收到的消息包相乘，然后將得到新的數(shù)據(jù)包在該條出邊上發(fā)送出去,中間節(jié)點對每一條出邊都從事上述操作.信宿節(jié)點如果收到含n個消息的頭部編碼向量組成的矩陣滿秩，利用線性方程理論就可以解碼出原始消息.

線性網(wǎng)絡(luò)編碼方案具有實現(xiàn)方案簡單、計算復(fù)雜度低等特點.李碩彥證明了針對多播網(wǎng)絡(luò)，線性網(wǎng)絡(luò)編碼可以達(dá)到多播容量上限[1].但線性網(wǎng)絡(luò)編碼依然具有幾個明顯缺點.首先，在非多播即一般網(wǎng)絡(luò)里，勒曼已經(jīng)證明線性網(wǎng)絡(luò)編碼并不能達(dá)到所有類型非多播網(wǎng)絡(luò)的容量上限[4].其次，線性網(wǎng)絡(luò)編碼存在“全有或全無”問題[5]，當(dāng)隨機(jī)線性網(wǎng)絡(luò)編碼里的編碼向量彼此不獨立時，無法得出唯一解，造成解碼失敗.此時，即使想恢復(fù)信源消息的一小部分也不可能[5, 6].第三，即使是在多播網(wǎng)絡(luò)里，雖然線性網(wǎng)絡(luò)編碼可以達(dá)到多播容量上限，但必須有一個前提條件是網(wǎng)絡(luò)不存在錯誤，如果有錯誤發(fā)生，因為中繼節(jié)點對上游消息的多次組合操作，所以即使很小的錯誤也有可能擴(kuò)散至全網(wǎng)而造成信宿節(jié)點不可譯碼[7].

針對線性網(wǎng)絡(luò)編碼的上述問題，提出非線性網(wǎng)絡(luò)編碼的概念[8].非線性網(wǎng)絡(luò)編碼和線性網(wǎng)絡(luò)編碼的本質(zhì)區(qū)別是其采用非線性函數(shù)來代替線性函數(shù).針對n個原始消息，編碼包頭部的編碼向量不再是n維的，而是qn維的，它代表有限域Fq上的每個變量最高為q-1次的多項式的系數(shù).非線性網(wǎng)絡(luò)編碼可以部分地克服線性網(wǎng)絡(luò)編碼的上述缺點.

1 隨機(jī)線性網(wǎng)絡(luò)編碼

1.1 線性網(wǎng)絡(luò)編碼模型

設(shè)G(V,E)是無延遲的通信網(wǎng)絡(luò).信源節(jié)點集：{s1,s2,…}?V，信宿節(jié)點集：R={r1,r2,…}?V，邊e的頭節(jié)點用h(e)=v表示，邊e的尾節(jié)點用t(e)=v′表示.X(v,i)表示源節(jié)點v的n長消息的第i個字符.稱這樣的編碼為線性網(wǎng)絡(luò)編碼，如果對于網(wǎng)絡(luò)中的每一條邊e=(v,v′)的傳輸符號均滿足：

(1)

其中αi,e,βe′,e∈Fq.

從函數(shù)映射角度，對邊集E中的每條邊e=(v,v′)，存在一種映射：

(2)

這里，fg是有限域Fq上的線性函數(shù).本文主要考慮一個信源節(jié)點的多播網(wǎng)絡(luò)，此多播網(wǎng)絡(luò)最大流最小割為n，所以信源消息是一個n長的一維向量.

隨機(jī)線性網(wǎng)絡(luò)編碼模型如圖1所示. 源節(jié)點v發(fā)出的的原始待解消息數(shù)據(jù)包X(v,i)用Xi表示.節(jié)點從入邊收到的包個數(shù)為K.如果是信宿節(jié)點，由于最大流最小割是n，其最大有效數(shù)據(jù)包個數(shù)為n，即K=n.信宿收到n個數(shù)據(jù)包為Y1,…，Yi,…，Yn.Yi頭部包含一個n長的編碼向量gi,1,gi,2,…,gi,n.收到的n個數(shù)據(jù)包Y=(Y1,Y2,…,Yn)為一組，針對的待解信源消息為X=(X1,X2,…,Xn).

圖1 隨機(jī)線性網(wǎng)絡(luò)編碼成組傳輸數(shù)據(jù)包格式Fig.1 The data-packet format of group transmission in random network coding

網(wǎng)絡(luò)中存在很多這樣的組，為了區(qū)別哪些數(shù)據(jù)包為一組，用數(shù)據(jù)包的頭部數(shù)據(jù)區(qū)Groupid進(jìn)行唯一標(biāo)識.為了節(jié)省頭部編碼向量標(biāo)標(biāo)識帶來的通信開銷，這里進(jìn)行成組傳輸，每組容納的Y1,…,Yi,…,Yn個數(shù)為b，b越大，數(shù)據(jù)包的頭部數(shù)據(jù)區(qū)Groupid帶來的開銷將被稀釋得越厲害[9].

1.2 線性網(wǎng)絡(luò)編碼的不足

第一是線性網(wǎng)絡(luò)編碼不能達(dá)到所有類型非多播網(wǎng)絡(luò)的容量上限.勒曼指出，針對某些非多播網(wǎng)絡(luò)，非線性網(wǎng)絡(luò)編碼能帶來更多的傳輸增益[4].

第二是解碼時存在“全有或全無”問題.由圖1可知，信宿節(jié)點解碼時會將n個編碼向量組合在一起形成一個關(guān)于未知數(shù)X1,…,Xi,…,Xn的n元一次線性方程組.方程組的系數(shù)矩陣記為：

(3)

方程記為：GX=Y.如果G滿秩，則能解出信源消息X，但如果G不滿秩，則不能得到X的任何一部分.上述問題是線性網(wǎng)絡(luò)編碼里的“全有或全無”問題.一般的解決方法是重傳更多的數(shù)據(jù)包直到G滿秩.但這樣會加重傳輸負(fù)擔(dān)，降低傳輸效率.

第三是線性網(wǎng)絡(luò)編碼的糾錯能力不強.網(wǎng)絡(luò)編碼中的錯誤和點對點通信中的錯誤不同，由于中間節(jié)點的混合操作，原始發(fā)生的錯誤會不斷被擴(kuò)散至下游節(jié)點而造成信宿節(jié)點不可譯碼.

2 非線性隨機(jī)網(wǎng)絡(luò)編碼

2.1 非線性隨機(jī)網(wǎng)絡(luò)編碼模型

如果將(2)式的函數(shù)fg調(diào)整為有限域Fq上的非線性函數(shù)，那么線性網(wǎng)絡(luò)編碼將成為非線性網(wǎng)絡(luò)編碼.

2.1.1 非線性編碼向量

其數(shù)據(jù)包格式和圖1基本相同.不同的主要是編碼向量由gi,1,gi,2,…,gi,n改為gi,q1,gi,q2,…,gi,qn，也就是編碼向量長度由n變?yōu)閝n.為了減小消息包頭部編碼向量的開銷，有限域設(shè)定為{0,1}，即q=2.雖然非線性編碼向量的長度比線性編碼的長度大很多，但是如果不斷加大圖1中成組傳輸里的b的數(shù)值，由此帶來的通信開銷會不斷減小.

2.1.2 中間節(jié)點的非線性編碼復(fù)合函數(shù)

若中間節(jié)點從K條入邊收到K個消息，對于其每一條出邊，會在本地隨機(jī)產(chǎn)生一個K元多項式函數(shù)fe，可以看作是有限域Fq上的的每個元的最高次冪為q-1的多項式.因為Fq={0,1}，所以每個元最高次冪為1，則該函數(shù)有2K個系數(shù).其通式如下：

(4)

當(dāng)某一中間節(jié)點收到3個消息時，即K=3，則:

fe=x1+x1x2x3+x2+x2x3+x1x3，

(5)

系數(shù)c(a1,a2,…,aK)從有限域Fq上隨機(jī)選取.K個數(shù)據(jù)包頭部的編碼向量實際上對應(yīng)以原始n個數(shù)據(jù)包X1,…，Xi,…Xn，為變量的有限域Fq上的多項式，用gi(X1,…，Xi,…，Xn)(1≤i≤K)表示該多項式函數(shù).針對出邊e，節(jié)點的局部編碼函數(shù)不再是線性編碼里的公式(1)，而是復(fù)合函數(shù)操作，即

f(g1(X1,…，Xi,…，Xn),…,gk(X1,…，Xi,…，Xn))=

fg(X1,…，Xi,…，Xn)=

(6)

復(fù)合函數(shù)操作之后函數(shù)的多項式系數(shù)組成新的數(shù)據(jù)包，然后發(fā)送到出邊e上.該數(shù)據(jù)包頭部的編碼向量即為λ1,λ2,…，λn，它與圖1中λ的gi,1,gi,2,…,gi,n是同一個具體值，即(λ1,λ2,…，λn)=(gi,1,gi,2,…,gi,n).非線性復(fù)合函數(shù)的運算過程可以用圖2表示.

圖2 中間節(jié)點的非線性編碼復(fù)合函數(shù)Fig.2 The composite function of an intermediate node for non-linear coding

圖2中，有三條入邊，一條出邊以及一個中間節(jié)點.三條入邊本身被賦予相應(yīng)的全局編碼函數(shù)，中間節(jié)點具有一個局部函數(shù).這三個全局編碼函數(shù)在經(jīng)過中間節(jié)點局部編碼函數(shù)的復(fù)合之后形成新的全局編碼函數(shù)，然后將這個新的全局編碼函數(shù)賦予出邊.這樣就完成了中間節(jié)點的非線性網(wǎng)絡(luò)編碼操作.

2.1.3 無錯誤時的信宿節(jié)點的譯碼

不像線性網(wǎng)絡(luò)編碼的譯碼，非線性編碼里信宿節(jié)點通過查表法進(jìn)行譯碼.信宿節(jié)點會在本地產(chǎn)生n個隨機(jī)多項式函數(shù)，每個隨機(jī)多項式對入邊的消息進(jìn)行復(fù)合函數(shù)運算，得出一個編碼包，然后傳到信宿節(jié)點中的一條想象出邊上.因為有n個原始消息，所以對應(yīng)有n條想象出邊.假設(shè)計算出來的n條想象出邊上的數(shù)據(jù)包頭部編碼向量對應(yīng)的多項式函數(shù)為f1(X1,X2，…，Xn),…，fn(X1,X2，…，Xn)記為f1,…,fn.根據(jù)這些編碼向量繪制解碼函數(shù)數(shù)值對應(yīng)表，如表1所示.

表1 解碼函數(shù)Tab.1 The decoding function

當(dāng)(a1,…,an)，(b1,…,bn)，(c1,…,cn)為(X1,…,Xn)的值確定時，(f1,…,fn)的具體取值也確定.信宿節(jié)點的n條想象出邊上收到的n個數(shù)據(jù)包的數(shù)值部分，即圖1中的Y=(Y1,…,Yi,…，Yn)也對應(yīng)(f1,…,fn)的一組具體值，其為(f1,…,fn)=(Y1,…,Yi,…，Yn).在表1中找到(Y1,…,Yi,…，Yn)，其對應(yīng)的(X1,…,Xn)即為原始信源消息.

上述譯碼成功的前提是表1確定的映射關(guān)系是一一映射.假設(shè)針對(Y1,…,Yi,…，Yn)有兩組或以上的(X1,…，Xn)與之對應(yīng)組合，則譯碼失敗.

2.2 非線性隨機(jī)網(wǎng)絡(luò)編碼的優(yōu)勢

2.2.1 解決全有或全無問題

如果是線性編碼，當(dāng)G不滿秩時，GX-Y總是得不到解.當(dāng)n=3時，表2和表3是線性編碼和非線性編碼時譯碼函數(shù)不是完全一一映射函數(shù)時的各自的一個具體例子.可以發(fā)現(xiàn)，線性編碼時，針對每一個(f1,…,fn)組合，總有兩個具體的(X1,…,Xn)組合與其對應(yīng).非線性編碼時，雖然對某些(f1,…,fn)組合，總有多個的具體(X1,…,Xn)組合與其對應(yīng)，但還有很多(fn,…,fn)和(X1,…,Xn)的具體數(shù)值一一對應(yīng).如果收到的(f1,…,fn)落入不是一一對應(yīng)的列，則譯碼失敗.而非線性編碼下的解碼函數(shù)不具有一一映射性，如果落到一一映射的列，依然可以譯碼.所以，當(dāng)信宿節(jié)點收到n個數(shù)據(jù)包時，如果數(shù)據(jù)包具有相關(guān)性，對應(yīng)線性編碼質(zhì).這就是“全有或全無”問題.當(dāng)為線性函數(shù)時，總是解碼失敗，此時需要重傳數(shù)據(jù)包.但是當(dāng)為非線性編碼時，還有一定的機(jī)會解碼成功，此時不需要重傳.這樣，非線性網(wǎng)絡(luò)編碼節(jié)省了重傳次數(shù).

表2 線性函數(shù)編碼時G不滿秩時的解碼函數(shù)Tab.2 The decoding function when G for linear function is not full rank

表3 非線性函數(shù)編碼時不是一一映射時的解碼函數(shù)Tab.3 The decoding function when non-linear function is not one-to-one mapping

2.2.2 非線性編碼的糾錯

線性編碼的糾錯方案一般通過加入一定的冗余來識別錯誤.線性糾錯碼里，為了增加檢錯或糾錯能力，在信息里增加多余的碼元，以擴(kuò)大碼字之間的差別，新增加的多余碼元即為冗余.在此時需要傳輸?shù)南⒂洖閡=(u1,u2,…,uk)，通過一個(n,k)的最大距離可分碼的生成矩陣對u=(u1,u2,…,uk)進(jìn)行編碼，編碼后的消息向量為X=(X1,…,Xi,…，Xn).此時冗余的大小為n-k.此編碼的最小距離為n-k+1.如果是點對點通信，只要錯誤個數(shù)t滿足t≤(n-k)/2，則以可正確譯碼.但在線性網(wǎng)絡(luò)編碼中因為中間節(jié)點的混合操作使得t個錯誤發(fā)生擴(kuò)散，擴(kuò)散后的錯誤個數(shù)可能遠(yuǎn)遠(yuǎn)大于t，所以不能譯碼[10, 11].

如果是非線性網(wǎng)絡(luò)編碼，設(shè)計一個和線性編碼的生成矩陣對應(yīng)的編碼函數(shù)矩陣.編碼過程如下.

(7)

其中·為復(fù)合函數(shù)操作.只要函數(shù)β1,β2,…，βn之間的獨立性達(dá)到最大，則其可以對抗盡可能多的錯誤.當(dāng)β1,β2,…，βn為線性函數(shù)時，則此編碼退化為線性編碼時的生成矩陣.非線性的函數(shù)個數(shù)遠(yuǎn)遠(yuǎn)大于線性函數(shù)個數(shù)，β1,β2,…，βn之間的漢明距離更大，所以對抗的錯誤更多.這一性質(zhì)可以局部改善線性網(wǎng)絡(luò)編碼對抗錯誤能力弱的問題.

3 仿真

對比純路由傳輸，線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼三種傳輸方案的正確譯碼率以及能量消耗.q大小設(shè)置為2，3，5，7，以2為主.q如設(shè)置太大，編碼向量太長，將加重通信負(fù)擔(dān).

圖3 多播網(wǎng)絡(luò)的拓?fù)銯ig.3 The topology of a multicast network

圖4 三種傳輸方案對比Fig.4 The comparison among three transmission schemes

圖3是實驗采用的一個多播網(wǎng)絡(luò)的拓?fù)?在圖3里，深色的節(jié)點1表示信源節(jié)點，淺色的節(jié)點12,13表示兩個信宿節(jié)點.其余的節(jié)點為中間節(jié)點，總的節(jié)點數(shù)13.拓?fù)溆赏負(fù)渖善麟S機(jī)生成的.拓?fù)渖善魇荲isual C++編寫的一個拓?fù)渖绍浖?圖 4表明，譯碼的成功率和能量消耗隨著冗余的增加而變化的情況.其中能量評價函數(shù)采用文獻(xiàn)[12]中的模型，其特點是用消耗的時間來表征消耗的能量.能量評價函數(shù)用公式

(8)

結(jié)果顯示，隨機(jī)非線性網(wǎng)絡(luò)編碼具有更高的成功譯碼率，更低的能量消耗.主要原因是即使受到消息之間相關(guān)性的影響，非線性網(wǎng)絡(luò)編碼仍有一定機(jī)會恢復(fù)原始消息.當(dāng)有錯誤存在時，其能容納更多的錯誤.以上兩點減少了重傳的機(jī)率，因而能量消耗也相應(yīng)減少.

4 結(jié)語

相比線性網(wǎng)絡(luò)編碼，非線性網(wǎng)絡(luò)編碼較好地解決了“全有或全無”問題，也能糾正更多的錯誤.但其編碼向量長，增加了一定的通信負(fù)載.解碼算法基于查表法，效率有待提高.相比線性網(wǎng)絡(luò)編碼，非線性網(wǎng)絡(luò)編碼還有更多的潛力有待開發(fā).

[1] Li S Y, Yeung R W, Cai N. Linear network coding [J]. IEEE Transactions on Information Theory, 2003, 49(2):371-381.

[2] 姚世雄，陳 晶，向 琨，等.網(wǎng)絡(luò)編碼理論及應(yīng)用綜述[J].中南民族大學(xué)學(xué)報(自然科學(xué)版)，2017，36(2)：115-128.

[3] Wang L, Yang Z, Xu L, et al. NCVCS: Network-coding-based video conference system for mobile devices in multicast networks [J]. Ad Hoc Networks, 2016, 45:13-21.

[4] Lehman A R, Lehman E. Complexity classification of network information flow problems [C]// ACM.15th Acm-Siam Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. New Orleans:ACM,2004:142-150.

[5] Kwon M, Park H, Frossard P. Compressed network coding: Overcome all-or-nothing problem in finite fields [C]//IEEE. Wireless Communications and Networking Conference. Istanbul:IEEE, 2014:2851-2856.

[6] Yan Z, Xie H, Suter B W. Rank deficient decoding of linear network coding [C]// IEEE. International Conference on Acoustics, Speech and Signal Processing. Florence: IEEE, 2013:5080-5084.

[7] Sanna M, Izquierdo E. A survey of linear network coding and network error correction code constructions and algorithms [J]. International Journal of Digital Multimedia Broadcasting, 2011:1687-7578.

[8] Shang T, Zhang C, Li K, et al. Nonlinear quantum network coding with classical communication resource [C]// IEEE. GlobeCOM Workshops. San Diego: IEEE, 2015:1-6.

[9] Katti S, Rahul H, Hu W, et al. XORs in the Air: Practical wireless network coding [J]. IEEE/ACM Transactions on Networking, 2008, 16(3):497-510.

[10] Langberg M, Effros M. Network coding: Is zero error always possible? [C]//IEEE. Communication, Control and Computing. Monticello: IEEE, 2012:1478-1485.

[11] Gadouleau M, Yan Z. Packing and covering properties of subspace sodes for error control in random linear network coding [J]. IEEE Transactions on Information Theory, 2010, 56(5):2097-2108.

[12] Z. Guo, B. Wang, P. Xie, et al. Efficient error recovery with network coding in underwater sensor networks [J]. Ad Hoc Networks, 2009, 7: 791-802.

StudyonRandomNon-linearNetworkCoding

ZhangDongqiu

(School of Computer and Information Technique, Mudanjiang Normal University, Mudanjiang 157011,China)

The error-correcting capacity of the linear network coding is limited, and the concept of non-linear network coding is presented. A new concept of non-linearly independent is presented to replace the existing concept of linearly independent. When the

symbols are non-linearly dependent, there is a fair possibility to decode the original messages without receiving more symbols. This scheme is just to utilize the pre-existing dependent symbols reasonably to decode original messages, instead of re-transmitting new symbols. Moreover, network coding is performed over binary field to save computational overhead. The simulation results show that this scheme reduces much energy and has low time delay.

network coding; non-linear; error-correcting

2017-09-20

張東秋(1983-)，女，博士，研究方向：計算機(jī)教育技術(shù)和傳感器網(wǎng)絡(luò)，E-mail：307642064@qq.com

國家自然科學(xué)基金資助項目(61571150)

TP39

A

1672-4321(2017)04-0116-05