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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1編碼過程

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

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

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

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

2.2解碼過程

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

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

2.3線性組合方案

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

(1)確定的編碼方案

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

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

(2)隨機(jī)編碼方案

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

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

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

前期網(wǎng)絡(luò)編碼研究的背景主要是基于有線網(wǎng)絡(luò)的，逐步深入的研究展示了網(wǎng)絡(luò)編碼擴(kuò)展到無線網(wǎng)絡(luò)中的廣闊前景。但是在網(wǎng)絡(luò)編碼的理論和應(yīng)用方面，無線自組織網(wǎng)絡(luò)與有線網(wǎng)絡(luò)有著顯著的差別，這主要是由無線自組織網(wǎng)絡(luò)的結(jié)構(gòu)特征和無線傳輸信道的時(shí)變衰落特性決定的。與通過電纜或者光纖等可靠媒介形成固定而獨(dú)立連接的有線網(wǎng)絡(luò)不同，無線自組織網(wǎng)絡(luò)的節(jié)點(diǎn)在分布上具有多維空間上的隨機(jī)特性，節(jié)點(diǎn)之間的連接因受節(jié)點(diǎn)移動或節(jié)點(diǎn)分布地域的限制，不但具有時(shí)間域上的時(shí)變特性而且在空間域上具有相互制約的相關(guān)性，在信號傳輸上受到時(shí)變衰落信道的影響具有時(shí)間域上的隨機(jī)性和不可靠性。所以把網(wǎng)絡(luò)編碼從有線網(wǎng)絡(luò)推廣到無線自組織網(wǎng)絡(luò)，用來提高無線網(wǎng)絡(luò)傳輸?shù)挠行�性和可靠性，一個(gè)首要的問題就是對承載傳輸業(yè)務(wù)的無線自組織網(wǎng)絡(luò)的結(jié)構(gòu)特性和傳輸特性進(jìn)行深入透徹的認(rèn)識，即加強(qiáng)對網(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)注的熱點(diǎn)，相關(guān)的研究人員如Medard、Effro和Yeung等人已經(jīng)在建立網(wǎng)絡(luò)編碼的數(shù)學(xué)描述方法等方面作了大量的工作，得到了有線網(wǎng)絡(luò)中利用網(wǎng)絡(luò)編碼實(shí)現(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)用還面臨著很多獨(dú)特的問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

網(wǎng)絡(luò)編碼機(jī)制可以提高網(wǎng)絡(luò)容量。已經(jīng)證明應(yīng)用網(wǎng)絡(luò)編碼，可以達(dá)到香農(nóng)極限。網(wǎng)絡(luò)編碼通過編碼節(jié)點(diǎn)對輸入信息線性或非線性的編碼處理，可以在不提高消耗帶寬的情況下，使不同的信息同時(shí)通過有限的鏈路，從而提高網(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)生編譯碼錯(cuò)誤，這將增大網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)恼`碼率。而就網(wǎng)絡(luò)編碼本身而言，對誤碼率有著相當(dāng)苛刻的要求，只有較小的誤碼率才能保證網(wǎng)絡(luò)編碼的有效性和可靠性，否則使用網(wǎng)絡(luò)編碼可能還會帶來系統(tǒng)整體性能的降低。因此，如何設(shè)計(jì)可靠的網(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é)點(diǎn)間傳輸效率和網(wǎng)絡(luò)吞吐量，還會對網(wǎng)絡(luò)的安全性能產(chǎn)生影響。一方面，由網(wǎng)絡(luò)編碼導(dǎo)致的信息的分散性和編譯碼特性增加了信息破譯難度，對安全性而言是一種改善；另一方面，對確定性編碼算法而言，由于傳輸過程中將涉及較多的節(jié)點(diǎn)數(shù)目，以及編碼算法方案的確定性，會導(dǎo)致系統(tǒng)的安全性能的降低。因此編碼算法的設(shè)計(jì)中也需要考慮系統(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ù)的研究需要在加深理論研究的同時(shí)，考慮實(shí)際的應(yīng)用場景，側(cè)重解決實(shí)際應(yīng)用中遇到的問題，比如需要降低編碼復(fù)雜度，需要考慮系統(tǒng)本身的延時(shí)以及網(wǎng)絡(luò)編碼帶來的延時(shí)影響等。網(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é)點(diǎn)不可能同時(shí)監(jiān)聽來自多個(gè)源的信息，對網(wǎng)絡(luò)編碼的應(yīng)用造成了一定的阻礙。如何結(jié)合無線分布式網(wǎng)絡(luò)的特點(diǎn)揚(yáng)長避短，找到能夠最大程度發(fā)揮網(wǎng)絡(luò)編碼優(yōu)勢的結(jié)合點(diǎn)，是需要考慮的主要問題。

5 結(jié)束語

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

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