無線自組織網(wǎng)絡(luò)的網(wǎng)絡(luò)編碼技術(shù)

網(wǎng)絡(luò)編碼作為一種新的技術(shù)在寬帶無線自組織網(wǎng)絡(luò)中有很好的應(yīng)用，通過網(wǎng)絡(luò)編碼，中間節(jié)點可以將接收信息進(jìn)行編碼并發(fā)送出去，提高了網(wǎng)絡(luò)吞吐量和健壯性。為不對現(xiàn)有網(wǎng)絡(luò)的軟硬件設(shè)備和相應(yīng)的協(xié)議做很大的修改，可以選擇在高層實現(xiàn)網(wǎng)絡(luò)編碼。無線傳感器網(wǎng)絡(luò)、無線格狀網(wǎng)(Mesh)等無線自組織網(wǎng)絡(luò)都可以使用網(wǎng)絡(luò)編碼技術(shù)顯著提高多跳鏈路的傳輸性能。目前網(wǎng)絡(luò)編碼的研究熱點集中在網(wǎng)絡(luò)編碼節(jié)點選取方案、網(wǎng)絡(luò)編碼算法的設(shè)計、網(wǎng)絡(luò)編碼復(fù)雜度分析、網(wǎng)絡(luò)編碼的性能分析、網(wǎng)絡(luò)編碼與系統(tǒng)安全性分析、網(wǎng)絡(luò)編碼在無線分布式網(wǎng)絡(luò)中的應(yīng)用等方面。

寬帶無線多跳通信系統(tǒng)的設(shè)計目標(biāo)是在充分利用有限的無線網(wǎng)絡(luò)資源的前提下，使各接收節(jié)點能快速收到完整信息。如何提高多跳自組織無線網(wǎng)絡(luò)的性能，一直是業(yè)界研究和關(guān)注的重點[1]。

1 網(wǎng)絡(luò)編碼技術(shù)原理

網(wǎng)絡(luò)編碼(Network coding)從廣義上來講，是網(wǎng)絡(luò)中的節(jié)點將接收到的信息進(jìn)行編碼后再轉(zhuǎn)發(fā)出去的多點傳送(Multicast)技術(shù)。多點傳送(也稱組播)是網(wǎng)絡(luò)中的一種重要的通信方式。當(dāng)一個或幾個節(jié)點同時向若干個其他節(jié)點發(fā)送數(shù)據(jù)時，往往要借助其他節(jié)點的傳遞。

在傳統(tǒng)的網(wǎng)絡(luò)中，作為中繼的節(jié)點只能對接收到的信號進(jìn)行復(fù)制、放大和轉(zhuǎn)發(fā)，這對于網(wǎng)絡(luò)資源有時候是一種浪費。網(wǎng)絡(luò)編碼技術(shù)打破了這種限制，它允許中繼節(jié)點對接收到的信息進(jìn)行編碼，并將接收到的多個數(shù)據(jù)包按照某種特定算法重新組合再發(fā)送出去。

圖1所示為一無線通信領(lǐng)域3節(jié)點拓?fù)涞膶嵗�：�?jié)點A、節(jié)點B相互傳遞信息a、b。圖1中的箭頭代表有向鏈路，假設(shè)每條鏈路的容量為“1”。圖1(a)采用傳統(tǒng)的通信方式，A首先向S發(fā)送信息a，然后B向S發(fā)送信息b，S然后依次把信息a和b分別廣播給節(jié)點A和節(jié)點B。這樣經(jīng)過4條鏈路的傳輸節(jié)點B可以獲得信息a，而節(jié)點A可以獲得信息b 。但是當(dāng)信息a和b準(zhǔn)備通過節(jié)點S進(jìn)行轉(zhuǎn)發(fā)時，如果應(yīng)用網(wǎng)絡(luò)編碼技術(shù)，將a和b作模2和運算后直接轉(zhuǎn)發(fā)出去，則在節(jié)點B處，根據(jù)接收到的信息可恢復(fù)出a來；同理，在節(jié)點A處也可以恢復(fù)出信息b來，從而可以譯碼得到信息b。采用了網(wǎng)絡(luò)編碼技術(shù)后(見圖1(b))，只需要使用3條鏈路就可以實現(xiàn)傳統(tǒng)方式的所有通信要求。

從實例可以看出，網(wǎng)絡(luò)編碼技術(shù)可以顯著地提高多點傳送的數(shù)據(jù)率。在一個網(wǎng)絡(luò)中傳遞的信息，可以形象的稱之為“流”。網(wǎng)絡(luò)的最大流量即為從源點到收點的最大傳輸數(shù)據(jù)率。而廣播的最大流量是指源點同時向所有收點發(fā)送同樣數(shù)據(jù)時，每個收點能接收到的最大數(shù)據(jù)傳輸速率。理論上講，最大流取決于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，即各節(jié)點的連接關(guān)系和帶寬。利用圖論中著名的最大流最小割定理可以得到給定網(wǎng)絡(luò)中某個源點到收點的最大流[2]。

最大流最小割定理：任何帶發(fā)點和收點的網(wǎng)絡(luò)中都存在最大流和最小割，并且最大流的流值等于最小割的容量。

從圖1還可以看出，一個容許的網(wǎng)絡(luò)編碼方案，必須使得收點能夠從接收到的數(shù)據(jù)中恢復(fù)出原始信息，也就是說，根據(jù)接收到的數(shù)據(jù)，和已知的編碼方案，可以唯一地解出原始的數(shù)據(jù)。如果把整個網(wǎng)絡(luò)看作一個系統(tǒng)，源點發(fā)送的數(shù)據(jù)可以視為系統(tǒng)的輸入，收點接收到的數(shù)據(jù)作為輸出，中間每個編碼節(jié)點的操作作為系統(tǒng)函數(shù)，則要求從源點到每個收點之間的信息傳輸矩陣滿秩，才能夠滿足廣播的要求。

數(shù)據(jù)在經(jīng)過中間網(wǎng)絡(luò)時，可能經(jīng)過多次編碼。一個節(jié)點如果自身不是源點，那么它發(fā)出的信息只能來源于收到的信息。因此無論怎樣編碼，它發(fā)出的信息量必然小于等于收到的信息量。從信息論的角度講，數(shù)據(jù)在傳輸過程中每經(jīng)過一個節(jié)點，其信息熵都是非增的。所以，為了保證最后傳到收點處的信息熵不降低，就要求每一個中間節(jié)點在編碼時，系統(tǒng)的傳輸矩陣不降秩，即無損編碼。而該節(jié)點為了判斷當(dāng)前的編碼方案是否會造成系統(tǒng)傳輸矩陣降秩，還要知道其他節(jié)點處的編碼情況。這就需要整個網(wǎng)絡(luò)的通力協(xié)作，這是迥異于傳統(tǒng)網(wǎng)絡(luò)的新概念。在傳統(tǒng)的網(wǎng)絡(luò)通信中，每個節(jié)點只知道自己和臨近節(jié)點的狀態(tài)，并致力于滿足自身的最優(yōu)化目標(biāo)。但網(wǎng)絡(luò)編碼技術(shù)要求各個節(jié)點之間的合作，以保證整個通信系統(tǒng)的最優(yōu)化。如何讓各節(jié)點協(xié)同工作，并不降低編碼效率和網(wǎng)絡(luò)其他方面的性能，是網(wǎng)絡(luò)編碼算法設(shè)計的重大挑戰(zhàn)之一。

網(wǎng)絡(luò)編碼方案可分為線性和非線性兩種，其中線性方法的編碼和解碼都相對簡單，因此，一般都傾向于采用線性方法。Li[3]指出在有向網(wǎng)絡(luò)中，如果一個網(wǎng)絡(luò)編碼問題有解，則一定有線性解。從理論上保證了線性算法的有效性。線性組合要求網(wǎng)絡(luò)節(jié)點具有更高的計算能力，然而根據(jù)摩爾定律，隨著處理成本的降低，網(wǎng)絡(luò)的“瓶頸”逐漸轉(zhuǎn)向業(yè)務(wù)所需的更高的帶寬支持和服務(wù)質(zhì)量(QoS)保證。網(wǎng)絡(luò)編碼實際上是用節(jié)點處理能力換取更高的網(wǎng)絡(luò)效率。

2 線性網(wǎng)絡(luò)編碼處理過程

線性網(wǎng)絡(luò)編碼是將節(jié)點傳送信息線性映射到一個有限域內(nèi)，利用線性關(guān)系實現(xiàn)編譯碼過程[4]。假設(shè)每個信息數(shù)據(jù)包為L 比特，當(dāng)它與要組合的數(shù)據(jù)包長度不同時，較短的信息附加額外一串“0”，將包中的s個連續(xù)比特組成域上的一個符號，則一個包中包含L /s個符號。在線性編碼下，運用乘法和加法運算，使從節(jié)點發(fā)送出去的數(shù)據(jù)為該節(jié)點接收到信息的線性組合。

2.1編碼過程

假設(shè)一個源或多個源產(chǎn)生的原始數(shù)據(jù)包信息為M 1……M n，則在線性網(wǎng)絡(luò)編碼中傳輸?shù)臄?shù)據(jù)可表示為為(其中g(shù)1……gn表示相應(yīng)的編碼系數(shù))，對每個符號有：，

Mik和Xk分別為Mi和X的第k個符號。傳輸?shù)臄?shù)據(jù)包中既包括編碼向量，又包括信息向量，編碼向量用于接收端的解碼。

編碼過程采用迭代的方法，若一個節(jié)點已經(jīng)接收和存儲的包信息集合為(g1,X1)……(gm,X m)，則這個節(jié)點可以通過選定編碼系數(shù)h1……hm和運用算式得到新的信息包

(g',X')，編碼向量g'可以通過直接的代數(shù)計算得到，該過程可以在若干個節(jié)點中重復(fù)操作。

2.2解碼過程

假設(shè)節(jié)點接收集合為(g 1,X 1)……(g m,X m)，為了恢復(fù)原始信息，需要求解｛｝的m個等式中的n個未知數(shù)M i，恢復(fù)所有數(shù)據(jù)要求M≥n，也就是說接收包的個數(shù)至少為原信息的個數(shù)。而有些線性組合可能是線性相關(guān)的，M≥n并不是充分條件，但卻是網(wǎng)絡(luò)編碼的重要條件。

解碼需要求解一組線性方程。實際中，可以應(yīng)用高斯消去的方法：節(jié)點存貯編碼向量以及編碼之后的結(jié)果，以行向量的形式，存儲在所謂解碼矩陣中。最初，解碼矩陣中只包含未經(jīng)該節(jié)點編碼的包以及與之相對應(yīng)的編碼向量(如果有的話)，否則為空。當(dāng)接收到一個已編碼包后，會從中抽取它的編碼向量以及編碼結(jié)果，放入到解碼矩陣中。解碼矩陣會經(jīng)過等價變換變成行階梯型，最終變成行最簡型。所收到的某一個包如果可以增加矩陣的秩，則稱之為更新包，如果所收到的包是非更新的，它可以通過等價變換變?yōu)槿�零，從而可以忽略。�?dāng)解碼矩陣變換成最簡型后，方程組得解。這種情況發(fā)生在當(dāng)接收到n 個線性獨立的編碼向量之后。

2.3線性組合方案

設(shè)計網(wǎng)絡(luò)編碼的問題在于每個節(jié)點如何進(jìn)行編碼組合，目前在算法設(shè)計上，可以分為確定性編碼和隨機編碼兩種方案。

(1)確定的編碼方案

Yeung[3]提出了線性網(wǎng)絡(luò)編碼的疊代實現(xiàn)方法，通過分析網(wǎng)絡(luò)結(jié)構(gòu)，根據(jù)節(jié)點的輸入輸出個數(shù)設(shè)計相應(yīng)的局部編碼向量，用迭代的方式得到全局編碼向量，從而實現(xiàn)網(wǎng)絡(luò)編碼；Koettor[5]則提出了較為完備的線性網(wǎng)絡(luò)編碼的代數(shù)實現(xiàn)。但他們的方法運算量太高。于是Jaggi[6]等人又提出了一種確定多項式-時間的編碼設(shè)計算法，可以為特定的廣播網(wǎng)絡(luò)找到可行的網(wǎng)絡(luò)編碼，目前已有對此算法的各種改進(jìn)。

確定性的編碼方案由于每個節(jié)點應(yīng)用的都是固定的編碼向量，因此網(wǎng)絡(luò)中傳遞的數(shù)據(jù)中只需要包含信息向量，節(jié)省帶寬，并且所需的符號集比較小；但確定性的網(wǎng)絡(luò)編碼需要了解全網(wǎng)的情況，復(fù)雜度比較高，難于分布式地實現(xiàn)。一旦網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生了變化，就必須對整個編碼方案進(jìn)行修改，魯棒性比較差。

(2)隨機編碼方案

由于確定性網(wǎng)絡(luò)編碼的以上缺點，Ho和Medard等人[7]提出了隨機編碼的概念，隨機編碼是讓網(wǎng)絡(luò)中的節(jié)點以完全獨立的分布式方式，隨機選取編碼系數(shù)，對輸入信息編碼，并把這組隨機向量作為報頭的一部分發(fā)送給收點，以便于解碼。已經(jīng)證明，當(dāng)符號集為無窮大時，采用隨機編碼，系統(tǒng)傳輸矩陣滿秩的概率為“1”。

隨機編碼可以分布式地實現(xiàn)，并可增加保密性。文獻(xiàn)[5]提出的代數(shù)實現(xiàn)的框架指出，線性網(wǎng)絡(luò)編碼可以通過隨機編碼有效地構(gòu)建。Chou[8]應(yīng)用隨機編碼，提出了第一個實用的網(wǎng)絡(luò)編碼方案。為了保證隨機編碼成功概率，編碼向量的符號集必須足夠大，這可能會增加數(shù)據(jù)包頭部的負(fù)擔(dān)，因此符號集的大小必須仔細(xì)選擇。

3 網(wǎng)絡(luò)編碼研究現(xiàn)狀

前期網(wǎng)絡(luò)編碼研究的背景主要是基于有線網(wǎng)絡(luò)的，逐步深入的研究展示了網(wǎng)絡(luò)編碼擴展到無線網(wǎng)絡(luò)中的廣闊前景。但是在網(wǎng)絡(luò)編碼的理論和應(yīng)用方面，無線自組織網(wǎng)絡(luò)與有線網(wǎng)絡(luò)有著顯著的差別，這主要是由無線自組織網(wǎng)絡(luò)的結(jié)構(gòu)特征和無線傳輸信道的時變衰落特性決定的。與通過電纜或者光纖等可靠媒介形成固定而獨立連接的有線網(wǎng)絡(luò)不同，無線自組織網(wǎng)絡(luò)的節(jié)點在分布上具有多維空間上的隨機特性，節(jié)點之間的連接因受節(jié)點移動或節(jié)點分布地域的限制，不但具有時間域上的時變特性而且在空間域上具有相互制約的相關(guān)性，在信號傳輸上受到時變衰落信道的影響具有時間域上的隨機性和不可靠性。所以把網(wǎng)絡(luò)編碼從有線網(wǎng)絡(luò)推廣到無線自組織網(wǎng)絡(luò)，用來提高無線網(wǎng)絡(luò)傳輸?shù)挠行�性和可靠性，一個首要的問題就是對承載傳輸業(yè)務(wù)的無線自組織網(wǎng)絡(luò)的結(jié)構(gòu)特性和傳輸特性進(jìn)行深入透徹的認(rèn)識，即加強對網(wǎng)絡(luò)模型的提取和對網(wǎng)絡(luò)無線傳輸容量的細(xì)致研究。這一研究不但在確立無線網(wǎng)絡(luò)傳輸性能極限上具有重要的理論意義，而且對如何把網(wǎng)絡(luò)編碼應(yīng)用于無線網(wǎng)絡(luò)中有著根本的指導(dǎo)作用。

目前，網(wǎng)絡(luò)編碼是國際信息論和網(wǎng)絡(luò)理論領(lǐng)域所關(guān)注的熱點，相關(guān)的研究人員如Medard、Effro和Yeung等人已經(jīng)在建立網(wǎng)絡(luò)編碼的數(shù)學(xué)描述方法等方面作了大量的工作，得到了有線網(wǎng)絡(luò)中利用網(wǎng)絡(luò)編碼實現(xiàn)最大流傳輸?shù)娜舾膳卸ǘɡ怼Ｈ欢�，他們的工作主要是集中在具有固定拓�(fù)浣Y(jié)構(gòu)和容量的有線網(wǎng)絡(luò)上，對網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的應(yīng)用涉及得較少。由于有線網(wǎng)絡(luò)中的帶寬資源相對豐富，并且超高速傳輸對于處理的復(fù)雜度限制較低。而對于無線自組織網(wǎng)絡(luò)，原有的關(guān)于有線網(wǎng)絡(luò)的固定特性也不適于在任意端到端之間構(gòu)造相應(yīng)的網(wǎng)絡(luò)編碼，難于適合網(wǎng)絡(luò)拓?fù)涞淖兓�。因此網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的應(yīng)用還面臨著很多獨特的問題。

關(guān)于網(wǎng)絡(luò)編碼的復(fù)雜度，Koettor在文獻(xiàn)[5]中證明，應(yīng)用他們的算法，所用編碼系數(shù)的符號集大大小于log2(mh +1)。其中h 是廣播的流量，m是收點的數(shù)目。

Fragouli[9]將其縮小到 2m-7/4+1/2。在文獻(xiàn)[10]中，作者系統(tǒng)地研究了網(wǎng)絡(luò)編碼的線性可解性和符號集大小的關(guān)系，并指出在某個符號集上有解的廣播網(wǎng)絡(luò)編碼，在更大的符號集上未必可解。

在一個廣播會話中，不是所有的中繼節(jié)點都要對輸入信息進(jìn)行編碼處理，只需在必須編碼的節(jié)點處進(jìn)行即可。這些必須編碼的節(jié)點叫做編碼節(jié)點，在編碼節(jié)點處編碼后的信息輸出的鏈路叫做編碼邊。在文獻(xiàn)[11]中，Langberg等人給出了一個廣播網(wǎng)絡(luò)中編碼邊數(shù)的上界和下界。不幸的是，他們還證明了確定編碼邊數(shù)的最小值是個非線性編程-硬(NP－h(huán)ard)問題。這表明，在目前任何尋找編碼節(jié)點和編碼邊的有效算法都只能是近似的。盡管如此，選擇性的編碼比在所有節(jié)點都進(jìn)行編碼的方法系統(tǒng)開銷還是要小得多。Fragouli[9]提出了一種子樹分解算法來尋找編碼節(jié)點。

在算法設(shè)計上，形成了兩個極端。一種是完全確定的編碼方案。Koettor[5]提出了較為完備的線性網(wǎng)絡(luò)編碼的代數(shù)實現(xiàn)。但是他們的方法運算量太高。確定性的編碼方案能夠保證容許性，并且所需的符號集比較小。但是確定性的網(wǎng)絡(luò)編碼需要了解全網(wǎng)的情況，復(fù)雜度比較高，難于分布式的實現(xiàn)。一旦網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生了變化，就必須對整個編碼方案進(jìn)行修改，所以魯棒性比較差。

由于確定性網(wǎng)絡(luò)編碼的以上缺點，后來提出了隨機編碼的概念。隨機編碼是指每個節(jié)點隨機地選取一組編碼向量，對輸入信息進(jìn)行編碼，并把這組隨機向量作為報頭的一部分發(fā)送給收點，以便于解碼。隨機編碼可以分布式地實現(xiàn)，并且可以增加保密性。隨機編碼可以解決分布式實現(xiàn)的問題，但是可能造成系統(tǒng)傳輸矩陣奇異，導(dǎo)致在收點無法恢復(fù)出原始數(shù)據(jù)�？梢宰C明，當(dāng)符號集為無窮大時，采用隨機編碼，系統(tǒng)傳輸矩陣滿秩的概率為“1”。

其余的算法基本上都是以上兩個極端的折衷，例如可以采用半隨機的編碼方案。整個網(wǎng)絡(luò)被化分成若干區(qū)域，各區(qū)域都采用隨機編碼，但為了保證傳輸矩陣滿秩，區(qū)域間要相互傳遞信息，以使每個區(qū)域在選擇編碼向量時盡量不選可能導(dǎo)致解碼失敗的那些向量。為了保證隨機編碼成功概率，編碼向量的符號集必須足夠大，這可能增加數(shù)據(jù)包頭部的負(fù)擔(dān)，因此符號集的大小必須仔細(xì)選擇。

此外，還有一些研究人員利用網(wǎng)絡(luò)編碼的思想提出了一些方案，以達(dá)到與最大流類似的最小費用、最低能量傳輸?shù)染W(wǎng)絡(luò)優(yōu)化目標(biāo)。

對等網(wǎng)絡(luò)(P2P)網(wǎng)絡(luò)中，網(wǎng)絡(luò)編碼策略可以降低下載時間，在大規(guī)模的分配式P2P網(wǎng)絡(luò)中，全局的調(diào)度非常復(fù)雜，而應(yīng)用網(wǎng)絡(luò)編碼后，可以采用很簡單的機制來構(gòu)造隨機的網(wǎng)絡(luò)架構(gòu)，提高系統(tǒng)性能，同時由于已編碼文件塊的密集性，基于網(wǎng)絡(luò)編碼的解決方案健壯性更強，例如當(dāng)某種子節(jié)點過早離開時，編碼機制的應(yīng)用使網(wǎng)絡(luò)信息塊平等，從而可以降低信息丟失的情況。

在增大流量上，利用網(wǎng)絡(luò)編碼可以達(dá)到理論上限，可以應(yīng)用于帶寬有限的無線網(wǎng)絡(luò)，利用其節(jié)點信息可以被周圍鄰居檢測接收的特點。如圖1所示，無線網(wǎng)絡(luò)中當(dāng)兩個無線節(jié)點需要通過一個共同的基站來進(jìn)行通信時，網(wǎng)絡(luò)編碼可以提高雙向業(yè)務(wù)的網(wǎng)絡(luò)流量，將結(jié)論推廣到無線網(wǎng)絡(luò)中的多跳路由中，兩個終端節(jié)點的業(yè)務(wù)是雙向的，且擁有相同的包要交換，在相鄰路由器間應(yīng)用輪詢的時間調(diào)度，通過最初幾步后，所有的中間節(jié)點都存儲了要向兩個方向傳送的數(shù)據(jù)，當(dāng)有傳送機會時，路由器將要向兩個方向傳送的數(shù)據(jù)編碼，傳送出去，從而充分利用無線傳輸?shù)奶攸c；而對于接收節(jié)點，可以通過相應(yīng)譯碼得到所需信息，信道的流量增加了一倍。網(wǎng)絡(luò)編碼還可以在組播、廣播場景中應(yīng)用，于是可以用于無線格狀網(wǎng)(Mesh)、自組織(Ad Hoc)網(wǎng)絡(luò)及無線傳感器等多跳網(wǎng)絡(luò)中。

網(wǎng)絡(luò)編碼機制使信息更加分散，等同于將信息進(jìn)行了隱藏，更難竊聽，提高了信息安全性。節(jié)點需要具有譯碼功能，同時要求得到足夠的數(shù)據(jù)才能正確解碼，信息很難被竊聽，同時網(wǎng)絡(luò)編碼還可以防止擁塞方面的侵害，因此，將網(wǎng)絡(luò)編碼技術(shù)應(yīng)用于軍事等領(lǐng)域，其保密性和魯棒性方面的潛力很大。

為了不對現(xiàn)有網(wǎng)絡(luò)的軟硬件設(shè)備和相應(yīng)的協(xié)議做很大的修改，可以選擇在更高層實現(xiàn)網(wǎng)絡(luò)編碼。基于組播覆蓋網(wǎng)絡(luò)節(jié)點功能更強、拓?fù)浣Y(jié)構(gòu)易構(gòu)建的特點，應(yīng)用簡單的編碼策略就可以提高網(wǎng)絡(luò)容量和降低信息傳輸時延�；�于這種思想，可以考慮在無線傳感器網(wǎng)絡(luò)，無線Mesh網(wǎng)絡(luò)中應(yīng)用網(wǎng)絡(luò)編碼，有效降低成本。

4 網(wǎng)絡(luò)編碼的研究熱點

作為一種新型的網(wǎng)絡(luò)傳輸技術(shù)，網(wǎng)絡(luò)編碼的優(yōu)點不言而喻。但到目前為止，對這一領(lǐng)域的研究還主要集中在理論方面以及應(yīng)用中局限性的分析方面。

4.1網(wǎng)絡(luò)編碼節(jié)點選取方案

在確定的網(wǎng)絡(luò)結(jié)構(gòu)中，并不是所有的節(jié)點都需要進(jìn)行網(wǎng)絡(luò)編碼，而是選取其中需要編譯碼的節(jié)點，給予編譯碼功能，對于不需要編譯碼的節(jié)點，只要具有傳統(tǒng)的存儲轉(zhuǎn)發(fā)功能即可。這樣不僅可以降低編碼算法的復(fù)雜度，也減小了對硬件的要求，從而使得網(wǎng)絡(luò)編碼的應(yīng)用更為廣泛。文獻(xiàn)[12]根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，利用一種子樹分解算法來尋找編碼節(jié)點。將該算法應(yīng)用于有線網(wǎng)絡(luò)中并使用確定的網(wǎng)絡(luò)編碼機制，效果較好；但對于無線網(wǎng)絡(luò)，節(jié)點之間的連接關(guān)系更為復(fù)雜，并且節(jié)點傳輸覆蓋范圍內(nèi)的節(jié)點都可能接收到網(wǎng)絡(luò)信息，導(dǎo)致拓?fù)浣Y(jié)構(gòu)更為緊密，則應(yīng)用上述方法選擇編碼節(jié)點就不太適合。因此，無線網(wǎng)絡(luò)中主要考慮節(jié)點能量及穩(wěn)定性的影響，選擇編碼節(jié)點或設(shè)計網(wǎng)絡(luò)拓?fù)鋾r應(yīng)盡可能將節(jié)點能量較高、具有較強的運算速度和較大的緩存空間的節(jié)點，以提高網(wǎng)絡(luò)的魯棒性。

4.2網(wǎng)絡(luò)編碼算法的設(shè)計

目前網(wǎng)絡(luò)編碼主要有確定性和隨機性兩種編碼方案，分別用于不同的網(wǎng)絡(luò)應(yīng)用與構(gòu)架上，這些方案主要是基于理論上的分析和實現(xiàn)，因此在實際網(wǎng)絡(luò)上需要針對不同的應(yīng)用設(shè)計相應(yīng)的編碼方式：如對于結(jié)構(gòu)較小的網(wǎng)絡(luò)，可以選擇比較簡單的確定性算法，編碼過程中甚至可以通過轉(zhuǎn)換為對數(shù)，將乘法運算轉(zhuǎn)換成加法運算，降低總的編碼復(fù)雜度；而對于無線網(wǎng)絡(luò)，則應(yīng)用隨機編碼機制是主要的研究趨勢，即令中間節(jié)點隨機生成編碼系數(shù)，對節(jié)點所有的可用信息應(yīng)用線性編碼，并隨時更新編碼系數(shù)，文獻(xiàn)[5]已經(jīng)證明，當(dāng)符號集為無窮大時，采用隨機編碼，系數(shù)傳輸矩陣滿秩的概率是“1”，即編碼成功的概率很大，但同時會增大數(shù)據(jù)報頭的負(fù)擔(dān)，因此符號集的大小需要權(quán)衡各種因素。

4.3網(wǎng)絡(luò)編碼復(fù)雜度的分析

網(wǎng)絡(luò)節(jié)點編碼過程中會涉及到大量的乘法與加法運算，需要較大的計算復(fù)雜度，而接收節(jié)點譯碼過程若應(yīng)用高斯消除方法，也是較大的運算過程。接收節(jié)點個數(shù)和節(jié)點信息塊大小共同決定了編碼符號集的最低門限。對于確定性編碼而言，所需的符號集可以較小，編碼的復(fù)雜度較低，但這種機制需要有中心節(jié)點集中控制網(wǎng)絡(luò)信息，對于網(wǎng)絡(luò)編碼的很多應(yīng)用場景以及網(wǎng)絡(luò)構(gòu)架都不適用，但可以通過對其相應(yīng)的復(fù)雜度分析，來設(shè)計合適的編碼算法從而降低網(wǎng)絡(luò)的復(fù)雜度；對于隨機網(wǎng)絡(luò)編碼而言，所需的符號集較大，而且節(jié)點在傳送信息的同時傳送系數(shù)向量，雖然系數(shù)向量相對于信息而言較小，但同樣會占用較大的帶寬，因此需要設(shè)計合適的算法，保證在提高編碼增益的同時降低復(fù)雜度。網(wǎng)絡(luò)編碼復(fù)雜度要受到符號集大小、節(jié)點計算復(fù)雜度、網(wǎng)絡(luò)編碼方案等諸多因素的影響，需要全面分析得出。

4.4網(wǎng)絡(luò)編碼的性能分析和應(yīng)用

網(wǎng)絡(luò)編碼機制可以提高網(wǎng)絡(luò)容量。已經(jīng)證明應(yīng)用網(wǎng)絡(luò)編碼，可以達(dá)到香農(nóng)極限。網(wǎng)絡(luò)編碼通過編碼節(jié)點對輸入信息線性或非線性的編碼處理，可以在不提高消耗帶寬的情況下，使不同的信息同時通過有限的鏈路，從而提高網(wǎng)絡(luò)流量。對于無線網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼性能進(jìn)行分析則需要應(yīng)用網(wǎng)絡(luò)信息論的知識，建立合適的網(wǎng)絡(luò)容量模型來進(jìn)行容量分析。

網(wǎng)絡(luò)編碼導(dǎo)致編解碼的過程中可能會產(chǎn)生編譯碼錯誤，這將增大網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)恼`碼率。而就網(wǎng)絡(luò)編碼本身而言，對誤碼率有著相當(dāng)苛刻的要求，只有較小的誤碼率才能保證網(wǎng)絡(luò)編碼的有效性和可靠性，否則使用網(wǎng)絡(luò)編碼可能還會帶來系統(tǒng)整體性能的降低。因此，如何設(shè)計可靠的網(wǎng)絡(luò)編碼方案以保證數(shù)據(jù)傳輸較低的誤碼率，并盡可能地采用相應(yīng)技術(shù)減少誤碼率對網(wǎng)絡(luò)編碼方案的影響是網(wǎng)絡(luò)編碼研究所必需的。

4.5網(wǎng)絡(luò)編碼與系統(tǒng)安全性分析

網(wǎng)絡(luò)編碼不僅可以提高節(jié)點間傳輸效率和網(wǎng)絡(luò)吞吐量，還會對網(wǎng)絡(luò)的安全性能產(chǎn)生影響。一方面，由網(wǎng)絡(luò)編碼導(dǎo)致的信息的分散性和編譯碼特性增加了信息破譯難度，對安全性而言是一種改善；另一方面，對確定性編碼算法而言，由于傳輸過程中將涉及較多的節(jié)點數(shù)目，以及編碼算法方案的確定性，會導(dǎo)致系統(tǒng)的安全性能的降低。因此編碼算法的設(shè)計中也需要考慮系統(tǒng)的安全性能，通過對不同的編碼算法進(jìn)行恰當(dāng)?shù)陌踩�性能分析，來確定不同網(wǎng)絡(luò)算法對系統(tǒng)安全性的影響，從而針對不同的系統(tǒng)應(yīng)用選用合適的編碼算法，以提高網(wǎng)絡(luò)安全性能，這對于無線通信具有重要意義。

4.6網(wǎng)絡(luò)編碼在無線分布式網(wǎng)絡(luò)中的應(yīng)用

對網(wǎng)絡(luò)編碼技術(shù)的研究需要在加深理論研究的同時，考慮實際的應(yīng)用場景，側(cè)重解決實際應(yīng)用中遇到的問題，比如需要降低編碼復(fù)雜度，需要考慮系統(tǒng)本身的延時以及網(wǎng)絡(luò)編碼帶來的延時影響等。網(wǎng)絡(luò)編碼在無線通信網(wǎng)絡(luò)當(dāng)中的應(yīng)用是一片亟待開發(fā)的熱土，一方面無線網(wǎng)絡(luò)的廣播特性非常利于網(wǎng)絡(luò)編碼的應(yīng)用；另一方面，相對于有線網(wǎng)絡(luò)而言，無線網(wǎng)絡(luò)中的節(jié)點不可能同時監(jiān)聽來自多個源的信息，對網(wǎng)絡(luò)編碼的應(yīng)用造成了一定的阻礙。如何結(jié)合無線分布式網(wǎng)絡(luò)的特點揚長避短，找到能夠最大程度發(fā)揮網(wǎng)絡(luò)編碼優(yōu)勢的結(jié)合點，是需要考慮的主要問題。

5 結(jié)束語

網(wǎng)絡(luò)編碼作為一種新型的信息處理技術(shù)已經(jīng)得到廣泛的研究，本文在綜合介紹了線性網(wǎng)絡(luò)編碼的產(chǎn)生背景和原理及編譯碼方案后，討論了網(wǎng)絡(luò)編碼的優(yōu)點和應(yīng)用場景，并介紹了網(wǎng)絡(luò)編碼的研究熱點，隨著更多學(xué)者對該領(lǐng)域的深入研究，網(wǎng)絡(luò)編碼技術(shù)在未來通信中必將得到廣泛應(yīng)用。

作者：彭木根 王月新 王文博 來源：通信世界網(wǎng)