1、School of Computer and Communication Degui XiaoDegui Xiao CN 1網(wǎng)絡(luò)編碼知識概述網(wǎng)絡(luò)編碼知識概述報告人：后學(xué)知報告人：后學(xué)知 導(dǎo)師：張大方導(dǎo)師：張大方 何施茗何施茗School of Computer and Communication Degui XiaoDegui Xiao大綱大綱 一一 研討背景研討背景 二二 問題論述問題論述 三三 我的任務(wù)我的任務(wù) 四四 詳細(xì)算法詳細(xì)算法 五五 仿真結(jié)果仿真結(jié)果 六六 參考文獻參考文獻 CN 2School of Computer and Communication Degui XiaoDeg

2、ui Xiao研討背景研討背景 近年來，隨著對無線網(wǎng)絡(luò)的逐漸普及，對于無線網(wǎng)絡(luò)的近年來，隨著對無線網(wǎng)絡(luò)的逐漸普及，對于無線網(wǎng)絡(luò)的性能的研討也越來越頻繁。性能的研討也越來越頻繁。 CN 3School of Computer and Communication Degui XiaoDegui Xiao研討背景研討背景 網(wǎng)絡(luò)編碼網(wǎng)絡(luò)編碼(Network Coding) 是進入是進入21 世紀(jì)后通訊領(lǐng)域的一項艱苦世紀(jì)后通訊領(lǐng)域的一項艱苦突破突破,它交融了編碼和路由的概念它交融了編碼和路由的概念,經(jīng)過允許對來自不同鏈路的信息經(jīng)過允許對來自不同鏈路的信息進展編碼組合進展編碼組合,使得網(wǎng)絡(luò)節(jié)點既實現(xiàn)路由功

3、能又實現(xiàn)編碼功能。在使得網(wǎng)絡(luò)節(jié)點既實現(xiàn)路由功能又實現(xiàn)編碼功能。在這種全新的體系構(gòu)造下這種全新的體系構(gòu)造下,網(wǎng)絡(luò)性能可以到達(dá)最大流傳輸?shù)膶嶋H極限網(wǎng)絡(luò)性能可以到達(dá)最大流傳輸?shù)膶嶋H極限。 下面是幾種很經(jīng)典的網(wǎng)絡(luò)編碼算法下面是幾種很經(jīng)典的網(wǎng)絡(luò)編碼算法 CN 4School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 copesc CN 5School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 COPE主要包括主要包括3種主要技術(shù)種主要技術(shù) (a) Opp

4、ortunistic Listening 1 無線網(wǎng)絡(luò)是廣播信道無線網(wǎng)絡(luò)是廣播信道 2 每個節(jié)點都有時機偷聽到包并在一個有限的時間內(nèi)每個節(jié)點都有時機偷聽到包并在一個有限的時間內(nèi)進展保管進展保管 3 保管包后，每個節(jié)點廣播接納報告給它鄰居節(jié)點保管包后，每個節(jié)點廣播接納報告給它鄰居節(jié)點 CN 6School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 7 CN 7 (b) Opportunistic CodingSchool of Computer and Communication Degui XiaoDegui X

5、iao詳細(xì)算法詳細(xì)算法 ANCAnalog Network Coding CN 8School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 9 (b) Opportunistic Coding 多重單播流在一同編碼，但是解碼時會分成不同流多重單播流在一同編碼，但是解碼時會分成不同流 算法保證一切編碼得包的下一跳節(jié)點可以解碼相對的原算法保證一切編碼得包的下一跳節(jié)點可以解碼相對的原始包始包 設(shè)有設(shè)有n個包個包p1, ., pn到到n個下一跳個下一跳r1, ., rn，一個節(jié)點，一個節(jié)點可以可以XORn個包前提是每個下一

6、跳個包前提是每個下一跳ri有有n 1 個包個包pj 且且 j = iSchool of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 10 (c) Learning Neighbor State 由于網(wǎng)絡(luò)擁塞，接納報告能夠喪失或者延時，當(dāng)接納報由于網(wǎng)絡(luò)擁塞，接納報告能夠喪失或者延時，當(dāng)接納報告到達(dá)時也許節(jié)點曾經(jīng)做出了非最正確選擇告到達(dá)時也許節(jié)點曾經(jīng)做出了非最正確選擇 我們改動無線路由協(xié)議來采用猜測的方法來估計對方節(jié)我們改動無線路由協(xié)議來采用猜測的方法來估計對方節(jié)點有什么包點有什么包 當(dāng)節(jié)點計算錯誤而無法解碼包時那么相關(guān)的未

7、編碼包重當(dāng)節(jié)點計算錯誤而無法解碼包時那么相關(guān)的未編碼包重新發(fā)送。新發(fā)送。School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 11 Coding Gain定義定義 不用不用COPE傳送的次數(shù)與用傳送的次數(shù)與用COPE傳送的次數(shù)的比值傳送的次數(shù)的比值。實際上最大值為實際上最大值為2實踐由于時機編碼，傳輸喪失，過大的頭使實踐值小于實踐由于時機編碼，傳輸喪失，過大的頭使實踐值小于2School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN

8、12 CN 12School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 13 CN 13 Coding+MAC Gain 帶寬平均分配，因此瓶頸鏈路的包被丟棄。帶寬平均分配，因此瓶頸鏈路的包被丟棄。 Coding+MAC的最大值無限。的最大值無限。School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 14 Packet Coding Algorithm (1) 我們遵照包從不延時的實際，在節(jié)點隊列頭的包檢我們遵照包從不延時的實際，

9、在節(jié)點隊列頭的包檢測能否有可以異或的包有那么異或，沒有也不等待這樣測能否有可以異或的包有那么異或，沒有也不等待這樣的包到來。的包到來。 (2) COPE優(yōu)先選擇異或長度相近的包優(yōu)先選擇異或長度相近的包 (3) COPE不會把具有一樣下一跳的包編碼在一同，因不會把具有一樣下一跳的包編碼在一同，因此我們只需思索具有不同下一跳的包。此我們只需思索具有不同下一跳的包。School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 15 保證找到適宜的包關(guān)鍵在于維持一大一小兩個虛擬隊保證找到適宜的包關(guān)鍵在于維持一大一小兩個虛擬隊列

10、。從虛擬隊列的頭開場找以免亂序列。從虛擬隊列的頭開場找以免亂序 亂序問題需求減少。主要有兩個緣由亂序問題需求減少。主要有兩個緣由 1 我們編碼要找適宜的包。這個影響其實很小。我們編碼要找適宜的包。這個影響其實很小。 2包喪失導(dǎo)致重傳，這個為主要緣由。包喪失導(dǎo)致重傳，這個為主要緣由。 我們處理這個問題在接納端。我們處理這個問題在接納端。 最后要保證鄰居節(jié)點可以解碼出他的未編碼的包。最后要保證鄰居節(jié)點可以解碼出他的未編碼的包。School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 16 每個節(jié)點維持以下的數(shù)據(jù)構(gòu)造每個

11、節(jié)點維持以下的數(shù)據(jù)構(gòu)造 1 每個節(jié)點輸出隊列按照先入先出轉(zhuǎn)發(fā)數(shù)據(jù)。每個節(jié)點輸出隊列按照先入先出轉(zhuǎn)發(fā)數(shù)據(jù)。 2 對于每個鄰居，每個節(jié)點維持兩個虛擬電路，一個為對于每個鄰居，每個節(jié)點維持兩個虛擬電路，一個為大包，一個為小包大包，一個為小包 3每個節(jié)點維持一個哈希表，闡明每個節(jié)點擁有包的能每個節(jié)點維持一個哈希表，闡明每個節(jié)點擁有包的能夠性。夠性。School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 17 Packet Decoding 每個每個節(jié)點維持一個包池，用來保管每個未編碼包的每個每個節(jié)點維持一個包池，用來保管

12、每個未編碼包的復(fù)制件。復(fù)制件。 當(dāng)一個節(jié)點收到一個由當(dāng)一個節(jié)點收到一個由N各未編碼的包組成的編碼包，各未編碼的包組成的編碼包，然后一個一個檢查然后一個一個檢查ID，然后再包池了檢查相應(yīng)的包。，然后再包池了檢查相應(yīng)的包。 最后進展異或運算得到原始包。最后進展異或運算得到原始包。School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 18 Pseudo-broadcast COPE不用不用broadcast方式由于可靠性差并且短少回方式由于可靠性差并且短少回退機制退機制 我們選用我們選用pseudo-broadcas

13、t來處理這個問題，它借來處理這個問題，它借用了單播的可靠性和回退機制。用了單播的可靠性和回退機制。 這個方法根據(jù)目的節(jié)點這個方法根據(jù)目的節(jié)點MAC地址和地址和XOR頭來鑒定包頭來鑒定包的下一跳能否是本節(jié)點，假設(shè)不是并且沒收到源節(jié)的下一跳能否是本節(jié)點，假設(shè)不是并且沒收到源節(jié)點會重發(fā)直至確認(rèn)或者超時點會重發(fā)直至確認(rèn)或者超時School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 19 Hop-by-hop ACKs and Retransmissions (a) Why hop-by-hop acks 1包有幾個下一跳

14、在其中一些下一跳能夠喪失包有幾個下一跳在其中一些下一跳能夠喪失 2 COPE沒有足夠的信息來獲取下一跳的信息來沒有足夠的信息來獲取下一跳的信息來解碼解碼School of Computer and Communication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 20 (b) Asynchronous Acks and Retransmissions 同步確認(rèn)對于編碼得包來說效率低下同步確認(rèn)對于編碼得包來說效率低下 COPE對于編碼包采用異步確認(rèn)。一旦確認(rèn)喪失進展重對于編碼包采用異步確認(rèn)。一旦確認(rèn)喪失進展重傳。傳。School of Computer and Comm

15、unication Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 21 Preventing TCP Packet Reordering 異步確認(rèn)會導(dǎo)致包亂序，使被異步確認(rèn)會導(dǎo)致包亂序，使被TCP以為是擁塞的信號。以為是擁塞的信號。 COPE采用一個順序代理來處理亂序問題采用一個順序代理來處理亂序問題 代理檢查序號假設(shè)是延續(xù)的那么讓包進入傳輸層，假設(shè)代理檢查序號假設(shè)是延續(xù)的那么讓包進入傳輸層，假設(shè)序號有裂痕那么保管這個區(qū)域直到重發(fā)的包把序號填滿序號有裂痕那么保管這個區(qū)域直到重發(fā)的包把序號填滿，直到延時，直到延時School of Computer and Communicat

16、ion Degui XiaoDegui Xiao詳細(xì)算法詳細(xì)算法 CN 22 CN 22Packet FormatSchool of Computer and Communication Degui XiaoDegui Xiao CN 23 CN 23Control FlowSchool of Computer and Communication Degui XiaoDegui Xiao CN 24詳細(xì)算法詳細(xì)算法 ZigZag Decoding24APAliceBobPa 1 3Pa 1 3Pb2 4Pb42121- 21st collision2nd collision0Can recon

17、struct both packets Pa and Pb!School of Computer and Communication Degui XiaoDegui Xiao CN 25Collision!AliceBobSchool of Computer and Communication Degui XiaoDegui Xiao CN 26AliceBobMore Collisions!RetransmissionsCant get any useful connectionsSchool of Computer and Communication Degui XiaoDegui Xia

18、o CN 27 發(fā)生碰撞時，發(fā)生碰撞時，ZIGZAG能到達(dá)魚不碰撞時一樣的性能，而沒能到達(dá)魚不碰撞時一樣的性能，而沒有碰撞時有碰撞時ZIGZAG表現(xiàn)像經(jīng)典的表現(xiàn)像經(jīng)典的802.11的接納者。的接納者。802.111協(xié)議中用戶在沒收到確認(rèn)或超時的前提下重新發(fā)送數(shù)據(jù)包協(xié)議中用戶在沒收到確認(rèn)或超時的前提下重新發(fā)送數(shù)據(jù)包很能夠再次碰撞。很能夠再次碰撞。2用戶每次發(fā)送閱歷個隨機時間，因此碰撞在開場于一個隨用戶每次發(fā)送閱歷個隨機時間，因此碰撞在開場于一個隨機的機的bit位。位。School of Computer and Communication Degui XiaoDegui Xiao CN 28Sc

19、hool of Computer and Communication Degui XiaoDegui Xiao CN 2912PaPbPaPbSchool of Computer and Communication Degui XiaoDegui Xiao CN 301211 2 1School of Computer and Communication Degui XiaoDegui Xiao CN 31212111 2 School of Computer and Communication Degui XiaoDegui Xiao CN 322122131 2 School of Com

20、puter and Communication Degui XiaoDegui Xiao CN 3321241331 2 School of Computer and Communication Degui XiaoDegui Xiao CN 34212441351 2 School of Computer and Communication Degui XiaoDegui Xiao CN 352161355241 2 School of Computer and Communication Degui XiaoDegui Xiao CN 3621661243571 2 School of C

21、omputer and Communication Degui XiaoDegui Xiao CN 3721681243577School of Computer and Communication Degui XiaoDegui Xiao CN 38 ZIGZAG用一種新穎的方法處理了干涉問題。用一種新穎的方法處理了干涉問題。School of Computer and Communication Degui XiaoDegui Xiao CN 39但是但是zigzag卻可以在最正確發(fā)送速率下發(fā)送包。卻可以在最正確發(fā)送速率下發(fā)送包。經(jīng)過實驗證明采用經(jīng)過實驗證明采用ZIGZAG的算法，在部分或

22、全部發(fā)生隱藏的算法，在部分或全部發(fā)生隱藏終端的情況下丟包率從終端的情況下丟包率從72.6%下降到下降到0.7%。School of Computer and Communication Degui XiaoDegui Xiao CN 40School of Computer and Communication Degui XiaoDegui Xiao CN 41School of Computer and Communication Degui XiaoDegui Xiao CN 421 如何發(fā)現(xiàn)發(fā)生碰撞？如何發(fā)現(xiàn)發(fā)生碰撞？TimeAP received signalPackets start with known preambleCorrelateAP correlates known preamble with signalCorrelationTimePreamble Correlation Detect collision and the value of Works despite interference because correlation with an independent sign