網(wǎng)絡(luò)編碼文獻(xiàn)研讀

《網(wǎng)絡(luò)編碼文獻(xiàn)研讀》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、網(wǎng)絡(luò)編碼文獻(xiàn)研讀李勒SA09006081摘要：網(wǎng)絡(luò)編碼是通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突破,其核心思想是允許網(wǎng)絡(luò)節(jié)點對傳輸信息進(jìn)行編碼處理。運用網(wǎng)絡(luò)編碼能夠提升網(wǎng)絡(luò)吞吐量、均衡網(wǎng)絡(luò)負(fù)載和提高網(wǎng)絡(luò)帶寬利用率等。網(wǎng)絡(luò)編碼雖然起源于多播傳輸,主要是為解決多播傳輸中的最大流問題,但是隨著研究的不斷深入,網(wǎng)絡(luò)編碼與其它技術(shù)的結(jié)合也越來越受到人們的關(guān)注。本文主要著眼于無線網(wǎng)絡(luò)編碼，介紹網(wǎng)絡(luò)編碼的基本原理，并選取了具有代表性的一些文章進(jìn)行了研讀,著重介紹了網(wǎng)絡(luò)編碼在無線mesh網(wǎng)絡(luò)中的典型應(yīng)用COPE，總結(jié)了網(wǎng)絡(luò)

2、編碼的X-ities，并介紹了網(wǎng)絡(luò)編碼在無線網(wǎng)絡(luò)中的其他典型應(yīng)用。在文章的最后對網(wǎng)絡(luò)編碼的優(yōu)缺點進(jìn)行了總結(jié)。1、引言傳統(tǒng)通信網(wǎng)絡(luò)中使用的路由機(jī)制認(rèn)為網(wǎng)絡(luò)中傳輸?shù)男畔⑹遣荒墀B加的,只能進(jìn)行存儲和轉(zhuǎn)發(fā)。雖然最大流最小割定理刻畫了網(wǎng)絡(luò)的容量，但是之前很多的近似算法并不能達(dá)到其最大理論容量。網(wǎng)絡(luò)編碼[1]技術(shù)是一種融合了編碼和路由的信息的交換技術(shù)。在傳統(tǒng)的路由基礎(chǔ)上，通過對接收的多個數(shù)據(jù)包進(jìn)行編碼增加傳輸?shù)男畔⒘?，提高網(wǎng)絡(luò)的整體性能。Ahlswede等人于2000年提出了網(wǎng)絡(luò)編碼(NetworkCoding),指出對

3、組播網(wǎng)絡(luò)中的某些節(jié)點附加額外的編碼操作能使源與組播成員間達(dá)到最大流最小割的組播速率。該文首次提出了網(wǎng)絡(luò)編碼的概念并從理論上證明:如果允許網(wǎng)絡(luò)節(jié)點對傳輸?shù)男畔凑蘸线m的方式進(jìn)行編碼處理(如模二加、有限域上的運算等)，而非限于存儲和轉(zhuǎn)發(fā),則基于該方式的網(wǎng)絡(luò)多播總能夠?qū)崿F(xiàn)理論上的最大傳輸容量。網(wǎng)絡(luò)編碼徹底改變了通信網(wǎng)絡(luò)中信息處理和傳輸?shù)姆绞?是信息理論研究領(lǐng)域的重大突破。此后網(wǎng)絡(luò)編碼研究拉開序幕，引起了學(xué)術(shù)界的廣泛關(guān)注。2、網(wǎng)絡(luò)編碼介紹2.1網(wǎng)絡(luò)編碼基本概念網(wǎng)絡(luò)編碼的核心思想是：具備編碼條件的網(wǎng)絡(luò)節(jié)點對接收到的信息

4、進(jìn)行一定方式的處理（編碼），然后傳輸給下一跳的網(wǎng)絡(luò)節(jié)點；收到消息的節(jié)點如果具備編碼條件，又對其接收的信息按照同樣的方式進(jìn)行處理和傳輸。如此反復(fù)，直到所有的經(jīng)過處理后的信息都到達(dá)匯聚節(jié)點。最后，在匯聚節(jié)點，通過譯碼操作就可以得到發(fā)送節(jié)點發(fā)出的原始信息。2.2最大流最小割定理設(shè)G=(V,E)是一個流網(wǎng)絡(luò)，其容量函數(shù)為c.設(shè)s為網(wǎng)絡(luò)的源點，t為匯點。G的流是一個實值函數(shù)f:,且滿足下面三個性質(zhì)：容量限制：對所有V中的u,v，要求f(u,v)≦c(u,v)。反對稱性：對所有V中的u,v，要求f(u,v)=-f(v,u

5、).流守恒性：對所有V中的u,v，要求f(u,v)成為從頂點u到頂點v的流，它可以為正，為零，也可以為負(fù)。最大流最小割定理：如果f是具有源點s和匯點t的流網(wǎng)絡(luò)G=(V，E)中的一個流，則下列條件等價：A.f是G的一個最大流B.殘留網(wǎng)絡(luò)Gf不包含增廣路徑C.對于G的某個割(S,T),有

6、f

7、=c(S,T),即最大流等于達(dá)最小割。猜想1：令G=(V,E)是個有源s和匯t1,...tL的圖，那么一條邊（i,j）的容量記作Rij。(R,h,G)可接收，當(dāng)且僅當(dāng)s到tl，l=1,...L,的值大于等于h（源信息率）。在

8、結(jié)束這部分前，作者將用例子說明一下。首先來看Fig.5.，對于L=1的情況，該猜想顯然是真的。Fig5(a)標(biāo)出了每條邊的容量。根據(jù)最大流最小割定理，從s到t1的最大流s是3，所以Fig5(b)中的流已是最大流。在Fig5(c)中，作者說明如何利用Fig5(b)中的最大流將b1,b2,b3從s發(fā)送到t1。注：方便起見，該文中的圖都采用原文中的圖和標(biāo)識。接下來，作者再舉個例子，如Fig.6顯示，在L=2時，猜想也正確。Fig.6(a)標(biāo)出了每條邊的容量。容易知道從s到t1和t2的最大流分別為5和6。所以猜想斷言

9、作者可以同時發(fā)送b1、b2、b3、b4、b5到t1和t2。Fig.6(b)給出了一個計劃。在這個計劃中，信息只需要通過復(fù)制來達(dá)到最優(yōu)。再看Fig.7的例子。容易知道，從s到tl的容量是2，l=1,2。所以猜想斷言作者可以同時發(fā)送b1、b2到t1和t2。如Fig.7(b)所示，其中"+"表示模2加。在t1中，b2可以被從b1和b1+b2中恢復(fù)出來。注意當(dāng)存在多于一個匯點時，作者使用傳統(tǒng)的方式已經(jīng)不能達(dá)到最優(yōu)。對于L>=2，網(wǎng)絡(luò)編碼對于一個最優(yōu)多播計劃來說已是必不可少的。最后，再舉Fig8中的例子說明L=3時，猜

10、想也成立。易知，s到所有匯的最大流是2。在Fig.8(b)中，作者給出如何多播b1、b2給所有的匯。網(wǎng)絡(luò)編碼的優(yōu)點可以從Fig.7和8中看到。作為一個說明，作者將用兩種方式來量化說明這些優(yōu)點。第一，作者得出當(dāng)引入網(wǎng)絡(luò)編碼后的到了網(wǎng)絡(luò)帶寬的節(jié)約。對于Fig.8(b)，共9bits被發(fā)送。如果網(wǎng)絡(luò)編碼不被允許時，容易看到，為了使t1、t2、t3恢復(fù)出b1和b2，至少要再多傳1比特。因此作者可以看到，如此