信息論-網(wǎng)絡(luò)編碼課件

網(wǎng)絡(luò)編碼組員：代亮亮徐杰郭鑫李文杰胡怡劉慧芳張曉宇網(wǎng)絡(luò)編碼組員：1概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理2概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理31、概念網(wǎng)絡(luò)編碼：通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突破。網(wǎng)絡(luò)編碼：融合了編碼和路由轉(zhuǎn)發(fā)的信息交換技術(shù)，在傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過(guò)允許對(duì)接收的多個(gè)數(shù)據(jù)包進(jìn)行編碼(如模二加、有限域上的運(yùn)算等)信息融合，增加單次傳輸?shù)男畔⒘?，以提高網(wǎng)絡(luò)信息傳輸效率和整體性能核心：允許網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)傳輸信息進(jìn)行編碼處理經(jīng)典信息論中的信息傳輸：?jiǎn)渭児蚕砭W(wǎng)絡(luò)和鏈路資源，彼此獨(dú)立。1、概念網(wǎng)絡(luò)編碼：通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突4網(wǎng)絡(luò)編碼的起源與發(fā)展概念誕生：1998論文“NetworkInformationFlowTheory”1999Yeung和Zhang發(fā)表的關(guān)于衛(wèi)星通信的論文正式發(fā)表：2000網(wǎng)絡(luò)編碼理論的奠基之作：先鋒論文“NetworkInformationFlow”里程碑（2003）：香港中文大學(xué)訊息工程系的李碩彥教授、楊偉豪教授、蔡寧教授發(fā)表了論文“LinearNetworkCoding”指出線性網(wǎng)絡(luò)編碼可以達(dá)到多播方式下的網(wǎng)絡(luò)容量。Koetter和Medard提出網(wǎng)絡(luò)編碼的代數(shù)學(xué)(Algebra)框架，即用抽象代數(shù)來(lái)解決線性網(wǎng)絡(luò)編碼的問(wèn)題，為研究網(wǎng)絡(luò)編碼提供了一個(gè)用力的數(shù)學(xué)工具

Sanders等提出具有多項(xiàng)式復(fù)雜度的線性信息流算法，該算法屬于集中式的碼構(gòu)造算法。Ho等提出隨機(jī)網(wǎng)絡(luò)編碼(RandomNetworkCoding,RNC)，屬于分布式的碼構(gòu)造方法。網(wǎng)絡(luò)編碼的起源與發(fā)展概念誕生：5基礎(chǔ)知識(shí)：最大流最小割定理1/5割:網(wǎng)絡(luò)中定點(diǎn)的一個(gè)劃分，把網(wǎng)絡(luò)中所有的頂點(diǎn)劃分為兩個(gè)頂點(diǎn)的集合S和T，其中源點(diǎn)s屬于S，匯點(diǎn)t屬于T，記為CUT（S，T）頂點(diǎn)集:S={1,2,3},T={4,5}構(gòu)成一個(gè)割框外是容量，框內(nèi)是流量注：源點(diǎn)和匯點(diǎn)不能屬于同一個(gè)頂點(diǎn)集合：如下就不能構(gòu)成一個(gè)割基礎(chǔ)知識(shí)：最大流最小割定理1/5割:網(wǎng)絡(luò)中定點(diǎn)的一個(gè)劃分，把6基礎(chǔ)知識(shí)：最大流最小割定理2/5s-t圖：a一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)b有向邊，<i,j>是從i到j(luò)c每條邊都有一個(gè)非負(fù)的權(quán)值d容量cap（i，j）等于0，說(shuō)明不存在邊基礎(chǔ)知識(shí)：最大流最小割定理2/5s-t圖：7基礎(chǔ)知識(shí)：最大流最小割定理3/5割邊：如果一條弧的兩個(gè)頂點(diǎn)分別屬于頂點(diǎn)集S和T（一個(gè)在S，另一個(gè)在T），這條弧成為CUT（S，T）的一條割邊。割的容量：割CUT（S,T）中所有正向割邊的容量和，稱為CUT（S，T）的容量，不同割的容量不同。最小割：所有割中權(quán)重和最小的一個(gè)割。eg.左圖中：割的容量為4+4=8

正向流量：4+2=6

逆向流量：1基礎(chǔ)知識(shí)：最大流最小割定理3/5割邊：如果一條弧的兩個(gè)頂點(diǎn)分8定理一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S,T）是任意一個(gè)割，那么f的值等于正向割邊的流量與負(fù)向割邊的流量之差。推論一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S，T）是一個(gè)割，那么f的值不超過(guò)割CUT（S,T）的容量推論二：網(wǎng)絡(luò)中的最大流不超過(guò)任何割的容量。定理二：在網(wǎng)絡(luò)中，如果f是一個(gè)流，CUT（S,T）是一個(gè)割，且f的值等于割CUT（S，T）的容量，那么f是一個(gè)最大流，CUT（S,T）是一個(gè)最小割?；A(chǔ)知識(shí)：最大流最小割定理4/5定理一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S,T）是任意一個(gè)9最大流最小割定理：任何網(wǎng)絡(luò)中，最大流等于最小割的容量形象的比喻：水流管道的最大流量由最細(xì)的管子容量決定。網(wǎng)絡(luò)的最大流量由最小割決定。基礎(chǔ)知識(shí)：最大流最小割定理5/5最大流最小割定理：任何網(wǎng)絡(luò)中，最大流等于最小割的容量形象的比10概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理11網(wǎng)絡(luò)編碼基本原理蝴蝶網(wǎng)絡(luò)”（ButterflyNetwork）左圖為“單信源二信宿”蝴蝶網(wǎng)絡(luò)設(shè)各鏈路容量為1S：信源節(jié)點(diǎn)。Y,Z：信宿節(jié)點(diǎn)。其余為中間節(jié)點(diǎn)。由最大流最小割定理，該多播的最大理論傳輸容量為2。即理論上信宿Y和Z能夠同時(shí)收到信源S發(fā)出的2個(gè)單位的信息,，也就是說(shuō)能同時(shí)收到b1和b2。網(wǎng)絡(luò)編碼基本原理左圖為“單信源二信宿”蝴蝶網(wǎng)絡(luò)12圖(a)圖(b)網(wǎng)絡(luò)編碼基本原理圖(a)圖(b)網(wǎng)絡(luò)編碼基本原理13網(wǎng)絡(luò)編碼基本原理網(wǎng)絡(luò)編碼的核心思想具備編碼條件的網(wǎng)絡(luò)節(jié)點(diǎn)A對(duì)接收到的信息進(jìn)行一定方式的處理(編碼)，然后傳輸給下一級(jí)的網(wǎng)絡(luò)節(jié)點(diǎn)BB再編碼，然后傳輸給C。如此反復(fù)，直到所有經(jīng)過(guò)處理后的信息都匯聚到信宿節(jié)點(diǎn)為止。在信宿節(jié)點(diǎn)，通過(guò)逆過(guò)程的操作(譯碼)，即可譯出信源發(fā)送的原始信息。網(wǎng)絡(luò)編碼基本原理14目的：A和B希望分別向?qū)Ψ桨l(fā)送數(shù)據(jù)塊x和yBSBSSSARBXY

簡(jiǎn)單網(wǎng)絡(luò)編碼示例基站中繼站用戶站BRYRBXARXRAY傳統(tǒng)方法：需要4個(gè)時(shí)隙1)

2)3)4)

網(wǎng)絡(luò)編碼方法：需要的時(shí)隙數(shù)減為3個(gè)1)2)3)R對(duì)X，Y執(zhí)行異或操作并向A,B廣播，A，B各自有X，Y的信息，可以通過(guò)譯碼得到X，和YARXBRY網(wǎng)絡(luò)編碼基本原理目的：BSBSSSA15概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理16

協(xié)作通信通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的方式接收轉(zhuǎn)發(fā)其他伙伴的信息到目的端，以獲得系統(tǒng)的分集增益，從而對(duì)抗無(wú)線信道的各種衰落。網(wǎng)絡(luò)編碼借助于融合了編碼和路由的新思想，通過(guò)允許中間節(jié)點(diǎn)對(duì)來(lái)自不同鏈路的信息進(jìn)行解碼組合，利用數(shù)據(jù)包之間的相關(guān)性來(lái)解碼，從而提升整個(gè)網(wǎng)絡(luò)的性能。網(wǎng)絡(luò)編碼在無(wú)線協(xié)作通信中的應(yīng)用背景與意義協(xié)作通信通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的方式接收轉(zhuǎn)發(fā)其他伙伴17協(xié)作通信系統(tǒng)模型

結(jié)合網(wǎng)路編碼思想與協(xié)作通信技術(shù)，以能更好的充分發(fā)揮網(wǎng)絡(luò)編碼技術(shù)在無(wú)線協(xié)作通信系統(tǒng)中的應(yīng)用優(yōu)勢(shì)，進(jìn)一步提高基于網(wǎng)絡(luò)編碼的無(wú)線協(xié)作系統(tǒng)性能.協(xié)作通信系統(tǒng)模型結(jié)合網(wǎng)路編碼思想與協(xié)作通信技術(shù)，以能18協(xié)作通信的分類放大轉(zhuǎn)發(fā)（AF,AmplifyandForward）

在信道質(zhì)量較差的情況下，AF會(huì)將噪聲放大。解碼轉(zhuǎn)發(fā)（DF,DecodeandForward）

在信道質(zhì)量較差的情況下，DF中繼無(wú)法正確解碼。兩者都是信息的重復(fù)傳輸，信道利用率不高，造成資源浪費(fèi)。編碼協(xié)作（CC，CooperationCoded）

提供比重復(fù)編碼更高效的編碼方式，從而帶來(lái)更多的編碼增益。但是中繼點(diǎn)復(fù)雜度高，中繼點(diǎn)信號(hào)處理時(shí)延增大，降低了時(shí)效性。協(xié)作通信的分類放大轉(zhuǎn)發(fā)（AF,AmplifyandFo19編碼協(xié)作（CC）

CC協(xié)議是解碼轉(zhuǎn)發(fā)協(xié)作（DF）的進(jìn)一步延伸，它改變DF策略的重復(fù)編碼方式，通過(guò)兩條不同的，相互獨(dú)立的衰落信道來(lái)發(fā)送每個(gè)用戶的信息碼字的不同部分，從而提供更多的編碼增益。編碼協(xié)作（CC）CC協(xié)議是解碼轉(zhuǎn)發(fā)協(xié)作（DF）的進(jìn)一20無(wú)線網(wǎng)絡(luò)編碼分類1.網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼2.物理層網(wǎng)絡(luò)編碼無(wú)線網(wǎng)絡(luò)編碼分類1.網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼21網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼

針對(duì)網(wǎng)絡(luò)層編碼技術(shù)，目前的一個(gè)研究重點(diǎn)是在實(shí)際的網(wǎng)絡(luò)條件下，采樣網(wǎng)絡(luò)編碼后的網(wǎng)絡(luò)容量以及可以達(dá)到的網(wǎng)絡(luò)容量的傳輸策略網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼針對(duì)網(wǎng)絡(luò)層編碼技術(shù)，目前的一個(gè)研究重點(diǎn)是在實(shí)22物理層網(wǎng)絡(luò)編碼

物理層網(wǎng)絡(luò)編碼提高了無(wú)線頻譜的利用率，物理層網(wǎng)絡(luò)編碼技術(shù)目前的研究重點(diǎn)是怎樣有效的從混合信號(hào)中分離出需要的信號(hào)。物理層網(wǎng)絡(luò)編碼物理層網(wǎng)絡(luò)編碼提高了無(wú)線頻譜的利用率，物理層23S1RS2D傳輸時(shí)隙信息傳輸方向傳輸信息簡(jiǎn)要說(shuō)明時(shí)隙1（直傳）S1(R,D)X1S1傳送信息X1到R和D時(shí)隙2（直傳）S2(R,D)X2S2傳送信息X2到R和D時(shí)隙3（協(xié)作）R（D）X1X2R將收到的信息進(jìn)行編碼后轉(zhuǎn)發(fā)給D時(shí)隙1時(shí)隙2時(shí)隙3S1RS2D傳輸時(shí)隙信息傳輸方向傳輸信息簡(jiǎn)要說(shuō)明時(shí)隙1（24網(wǎng)絡(luò)編碼在分布式存儲(chǔ)中的應(yīng)用網(wǎng)絡(luò)編碼在分布式存儲(chǔ)中的應(yīng)用25分布式存儲(chǔ)由來(lái)及優(yōu)越性傳統(tǒng)的存儲(chǔ)模型中,大多為直連式存儲(chǔ)系統(tǒng),其存儲(chǔ)設(shè)備直接與服務(wù)器相連。此類存儲(chǔ)模型可擴(kuò)展性極差,數(shù)據(jù)共享能力弱。1986年,著名學(xué)者李凱針對(duì)大數(shù)據(jù)存儲(chǔ)困難的現(xiàn)狀提出了分布式存儲(chǔ)

的概念,該思想源于虛擬存儲(chǔ)系統(tǒng)。分布式存儲(chǔ)就是將源文件分散的存儲(chǔ)到網(wǎng)絡(luò)中的相互獨(dú)立的空閑節(jié)點(diǎn)中。優(yōu)越性(1)高可靠性(2)修復(fù)功能(3)可擴(kuò)展性(4)高性能(5)透明性分布式存儲(chǔ)由來(lái)及優(yōu)越性26網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用網(wǎng)絡(luò)糾錯(cuò)碼

網(wǎng)絡(luò)編碼的初衷在于提高網(wǎng)絡(luò)的吞吐量,但是隨著進(jìn)一步研究發(fā)現(xiàn)它也是一種安全網(wǎng)絡(luò)傳輸?shù)暮梅绞?。然而在抗擊拜占庭攻擊時(shí),我們不僅要能夠檢測(cè)出敵手對(duì)信息的惡意攻擊,還要盡量能夠做到對(duì)這些信息的恢復(fù),這就是網(wǎng)絡(luò)糾錯(cuò)碼.傳統(tǒng)的密碼學(xué)方法存在一定的局限性計(jì)算復(fù)雜度較大、數(shù)據(jù)傳輸速率較低、消息冗余較大網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用網(wǎng)絡(luò)糾錯(cuò)碼27分布式存儲(chǔ)的維護(hù)最常用冗余數(shù)據(jù)的維護(hù)技術(shù)是復(fù)制和糾刪碼。當(dāng)我們?cè)诶眉m刪碼對(duì)失效節(jié)點(diǎn)進(jìn)行修復(fù)的時(shí)候，首先要將原始數(shù)據(jù)重建，然后將其用網(wǎng)絡(luò)編碼的方法進(jìn)行編碼，但是這樣修復(fù)時(shí)數(shù)據(jù)的下載量遠(yuǎn)遠(yuǎn)多于節(jié)點(diǎn)的存儲(chǔ)，即修復(fù)帶寬遠(yuǎn)大于存儲(chǔ)量。分布式存儲(chǔ)的維護(hù)最常用冗余數(shù)據(jù)的維護(hù)技術(shù)是復(fù)制和糾刪碼。28再生碼兩種常用的冗余數(shù)據(jù)維護(hù)技術(shù)在對(duì)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行修復(fù)時(shí)，需要消耗很大的下載帶寬，于是產(chǎn)生了一種新型的技術(shù)——再生碼。實(shí)現(xiàn)了存儲(chǔ)量與修復(fù)下載帶寬的良好折中，部分還巧妙地結(jié)合了復(fù)制與糾刪碼的各自優(yōu)點(diǎn)，保證了具有極高的節(jié)點(diǎn)成功修復(fù)的可能性。再生碼兩種常用的冗余數(shù)據(jù)維護(hù)技術(shù)在對(duì)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行修復(fù)時(shí)，需要29信息流圖他們把節(jié)點(diǎn)修復(fù)的問(wèn)題刻畫(huà)為網(wǎng)絡(luò)系統(tǒng)中普遍的單源多播問(wèn)題，然后把對(duì)分布式存儲(chǔ)系統(tǒng)的分析化成對(duì)信息流圖的分析信息流圖他們把節(jié)點(diǎn)修復(fù)的問(wèn)題刻畫(huà)為網(wǎng)絡(luò)系統(tǒng)中普遍的單源多播問(wèn)30再生碼的一個(gè)定理對(duì)于任意，分布式存儲(chǔ)系統(tǒng)中的點(diǎn)是可行的，它可以通過(guò)線性網(wǎng)絡(luò)編碼來(lái)實(shí)現(xiàn)。當(dāng)時(shí)，在信息理論上是不可能實(shí)現(xiàn)的。其理論界函數(shù)如下：其中對(duì)于給定的n，k，d，最小修復(fù)帶寬的值為再生碼的一個(gè)定理對(duì)于任意31信息論-網(wǎng)絡(luò)編碼課件32MSR和MBRMSR和MBR33網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用34網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用傳統(tǒng)的密碼學(xué)方法存在一定的局限性

(1)計(jì)算復(fù)雜度較大

(2)數(shù)據(jù)傳輸速率較低

(3)消息冗余較大網(wǎng)絡(luò)糾錯(cuò)碼

網(wǎng)絡(luò)編碼的初衷在于提高網(wǎng)絡(luò)的吞吐量,但是隨著進(jìn)一步研究發(fā)現(xiàn)它也是一種安全網(wǎng)絡(luò)傳輸?shù)暮梅绞?。然而在抗擊拜占庭攻擊時(shí),我們不僅要能夠檢測(cè)出敵手對(duì)信息的惡意攻擊,還要盡量能夠做到對(duì)這些信息的恢復(fù),這就是網(wǎng)絡(luò)糾錯(cuò)碼.網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用傳統(tǒng)的密碼學(xué)方法存在一定的局35搭載竊聽(tīng)網(wǎng)絡(luò)通信的模型網(wǎng)絡(luò)通信的模型m:是消息本身k:是為了達(dá)到安全的隨機(jī)數(shù)右圖中紅線是竊聽(tīng)集，但是一個(gè)時(shí)間內(nèi)只允許敵手竊聽(tīng)其中的一條，這樣接收節(jié)點(diǎn)T和T＇能夠安全接收到信源傳來(lái)的消息ｍ。網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用搭載竊聽(tīng)網(wǎng)絡(luò)通信的模型網(wǎng)絡(luò)通信的模型m:是消息本身網(wǎng)絡(luò)編碼理36圖3Alice、Bob和Eve的數(shù)據(jù)包X:表示Alice發(fā)出的原始消息塊Z:表示攻擊者Eve注入的錯(cuò)誤消息塊Y:表示經(jīng)過(guò)篡改被Bob接收的消息塊矩陣I、L和T分別表示數(shù)據(jù)包X、Y和Z的編碼向量。圖3是有線和無(wú)線網(wǎng)絡(luò)的帶有拜占庭攻擊者的攻擊模型，為了簡(jiǎn)化符號(hào)，只考慮單信源單信宿的通信問(wèn)題。相似于許多網(wǎng)絡(luò)編碼的算法，這里每個(gè)體制都可以從單個(gè)接收方的情形推廣到多播通信。網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用圖3Alice、Bob和Eve的數(shù)據(jù)包X:表示Al373種主要攻擊模型(1)秘密共享模型此模型假定Alice和Bob有一個(gè)低速率的秘密信道，Eve不知道秘密信道上的傳輸消息?？紤]將消息經(jīng)過(guò)網(wǎng)絡(luò)編碼后在網(wǎng)絡(luò)上傳輸，Eve可以觀察到所有除秘密信道之外的所有傳輸，也可以選擇是否在他所控制的節(jié)點(diǎn)處在要傳輸?shù)臄?shù)據(jù)包中注入一些惡意數(shù)據(jù)到從而達(dá)到阻止Alice和Bob通信的目的。(2)萬(wàn)能攻擊者模型此模型中Eve除了在控制鏈接數(shù)目上受到一定限制外，是萬(wàn)能的、無(wú)所不知的，Alice和Bob之間沒(méi)有獨(dú)立于Eve的秘密信道。(3)有限的竊聽(tīng)模型在這個(gè)模型中，Eve的竊聽(tīng)能力是有限制的，只能觀察到至多ZI個(gè)傳送的包。3種主要攻擊模型(1)秘密共享模型38網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用39網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用————p2p系統(tǒng)簡(jiǎn)介

p2p網(wǎng)絡(luò)系統(tǒng)：

P2P全稱為：Peer-to-Peer，即對(duì)等網(wǎng)絡(luò)或?qū)Φ扔?jì)算。主要采用非集中式的拓?fù)浣Y(jié)構(gòu)，可以應(yīng)對(duì)集中式拓?fù)浣Y(jié)構(gòu)出現(xiàn)的過(guò)量存儲(chǔ)負(fù)載、DOS（DenialofService，拒絕服務(wù)）攻擊，網(wǎng)絡(luò)帶寬限制等一些難以解決的問(wèn)題。P2p網(wǎng)絡(luò)系統(tǒng)發(fā)展的四種拓?fù)浣Y(jié)構(gòu):中心化拓?fù)洹⑷植际椒墙Y(jié)構(gòu)化拓?fù)?、全分布結(jié)構(gòu)式拓?fù)洹敕植际酵負(fù)渚W(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用————p2p系統(tǒng)簡(jiǎn)介

p240網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——p2p系統(tǒng)簡(jiǎn)介p2p網(wǎng)絡(luò)系統(tǒng)四種技術(shù)優(yōu)勢(shì)：非中心化：資源和服務(wù)分散在對(duì)等結(jié)點(diǎn)上，信息的交付直接在結(jié)點(diǎn)之間進(jìn)行，無(wú)需服務(wù)器介入，避免了可能的瓶頸。可擴(kuò)展性：系統(tǒng)的資源和服務(wù)能力可以隨著新用戶的加入和服務(wù)需求的增加而提高。魯棒性：即系統(tǒng)的健壯性，在抗異常和突發(fā)危險(xiǎn)情況的能力。服務(wù)是分散在各對(duì)等結(jié)點(diǎn)上的，沒(méi)有中心節(jié)點(diǎn)和特殊節(jié)點(diǎn)，某些節(jié)點(diǎn)出現(xiàn)異?；蛟馐芄魰r(shí)，整個(gè)網(wǎng)絡(luò)的影響很小，具有很強(qiáng)的自組織性和自愈性。負(fù)載均衡：每個(gè)節(jié)點(diǎn)既是服務(wù)器又是客戶機(jī)，同時(shí)因資源分布在多個(gè)節(jié)點(diǎn)，能更好實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的負(fù)載均衡。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——p2p系統(tǒng)簡(jiǎn)介p2p網(wǎng)絡(luò)41網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載三種文件下載方式：無(wú)分代隨機(jī)網(wǎng)絡(luò)編碼技術(shù)：優(yōu)點(diǎn)是分塊隨機(jī)組合后，整個(gè)網(wǎng)絡(luò)的分塊分布均衡化，而且能夠適應(yīng)P2P系統(tǒng)的動(dòng)態(tài)變化。缺點(diǎn)是編碼解碼過(guò)程是在一個(gè)文件的所有分塊之間進(jìn)行的，計(jì)算量大，系統(tǒng)開(kāi)銷過(guò)大，尤其是大文件分發(fā)時(shí)。分代網(wǎng)絡(luò)編碼方法：優(yōu)點(diǎn)是解決無(wú)分代網(wǎng)絡(luò)編碼的問(wèn)題。缺點(diǎn)是節(jié)點(diǎn)的退出使得網(wǎng)絡(luò)中已經(jīng)不存在足夠多線性無(wú)關(guān)的編碼組合以解碼得出某一代的原始分塊，從而導(dǎo)致無(wú)法解除完整的文件；源節(jié)點(diǎn)不知如何從本代信息傳輸切換到下一代信息傳輸?shù)?。代間網(wǎng)絡(luò)編碼方法：優(yōu)點(diǎn)：當(dāng)本代集中的某一代沒(méi)有足夠多線性無(wú)關(guān)的編碼塊時(shí)，可以由本代集其他代的線性無(wú)關(guān)編碼塊來(lái)彌補(bǔ)。缺點(diǎn)：無(wú)法單獨(dú)成功解出某一代的原始數(shù)據(jù)。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載三種文件下載方式42網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載假設(shè)服務(wù)器需要傳輸文件給對(duì)等節(jié)點(diǎn)A，首先將服務(wù)器上的文件分解成n個(gè)文件塊，B1—Bk，然后應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼，隨機(jī)選擇系數(shù)C1—Cn，將線性網(wǎng)絡(luò)編碼后的組合塊E1=c1B1+c2B2…cnBk傳送給對(duì)等節(jié)點(diǎn)A，同理得出E2=C1'B1+C2'B2…Cn'Bk，該組合塊來(lái)自其它對(duì)等節(jié)點(diǎn)或者服務(wù)器。然后對(duì)等節(jié)點(diǎn)A再隨機(jī)選擇編碼系數(shù)C1''、C2''

，對(duì)E1和E2進(jìn)行線性操作，將操作的結(jié)果E3=

C1''E1+

C2''

E2

發(fā)送給對(duì)等節(jié)點(diǎn)B，對(duì)等節(jié)點(diǎn)B又傳送給其它的對(duì)等節(jié)點(diǎn)。只要每一個(gè)對(duì)等節(jié)點(diǎn)收到足夠多的線性無(wú)關(guān)組合，就可以通過(guò)解線性方程組譯出原始文件塊。無(wú)分代隨機(jī)網(wǎng)絡(luò)編碼技術(shù)網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載假設(shè)服務(wù)器需要傳43網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載把傳輸?shù)奈募确殖啥鄠€(gè)代，每個(gè)代再分成一定數(shù)目的塊，并且每代擁有的分塊數(shù)目是固定的。網(wǎng)絡(luò)編碼和解碼的過(guò)程只在同一代內(nèi)進(jìn)行，代與代之間編碼過(guò)程是獨(dú)立的。如圖所示，首先將文件分成m（m≥2）個(gè)代，每個(gè)代內(nèi)再分成n（n≥2，n>>m）個(gè)文件分塊。編碼過(guò)程在代內(nèi)進(jìn)行，而且代與代之間的編碼過(guò)程是彼此獨(dú)立的。源節(jié)點(diǎn)首先對(duì)第一代內(nèi)的文件執(zhí)行無(wú)分代網(wǎng)絡(luò)編碼直到信宿可以正確譯出第一代的所有信息，然后再在第二代內(nèi)執(zhí)行無(wú)分代網(wǎng)絡(luò)編碼信息傳輸，以此類推，直到傳輸完整個(gè)文件。分代網(wǎng)絡(luò)編碼方法網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載把傳輸?shù)奈募确?4網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載首先把文件分代，代內(nèi)再分組，然后把本代及其之前所有的代組合成一個(gè)代集，在代集內(nèi)進(jìn)行編碼。代集之間編碼過(guò)程是獨(dú)立的。如圖所示：首先把要發(fā)送的源文件分成m代，每代再分成k個(gè)塊，本代及其之前所有的代構(gòu)成代集，編碼過(guò)程和解碼過(guò)程都在代集內(nèi)進(jìn)行，并且代集之間彼此獨(dú)立。代間網(wǎng)絡(luò)編碼方法網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載首先把文件分代，45流媒體與文件下載的最大區(qū)別是前者要求邊下載邊播，而后者沒(méi)有這個(gè)要求。目前基于p2p的實(shí)時(shí)流媒體系統(tǒng)中，根據(jù)覆蓋網(wǎng)節(jié)點(diǎn)所構(gòu)成的拓?fù)湟?guī)劃，分為單組播樹(shù)拓?fù)洹⒍嘟M播樹(shù)拓?fù)浜途W(wǎng)狀拓?fù)淙?。如上圖所示現(xiàn)有p2p流媒體傳輸系統(tǒng)很多是基于分層編碼實(shí)現(xiàn)的，其系統(tǒng)主要由兩個(gè)模塊組成：資源發(fā)現(xiàn)模塊和資源傳輸模塊。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體流媒體與文件下載的最大區(qū)別是前者要求邊下載邊播，而后者沒(méi)有這46空間分層編碼實(shí)現(xiàn)不同大小圖像的服務(wù)兼容性。先在原始圖像中采樣的方法得到一幀空間上低頻分辨率的圖像。從原始圖像減去經(jīng)過(guò)內(nèi)插的抽樣圖像得到的差值圖像，對(duì)差值圖像再進(jìn)行編碼得到增強(qiáng)層。時(shí)間分層編碼為實(shí)現(xiàn)不同頻率的視頻服務(wù)兼容。其基本層和增強(qiáng)層具有相同的空間分辨率和SNR?；緦訄D像進(jìn)行運(yùn)動(dòng)估計(jì)時(shí)只能在基本層中選取，同理增強(qiáng)層也是。視頻的精細(xì)分層為支持信道特性多變的包交換網(wǎng)上多媒體應(yīng)用和服務(wù)而提出網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體分層編碼網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體分層編碼47網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源發(fā)現(xiàn)模塊

主要任務(wù)是協(xié)助新的節(jié)點(diǎn)找到自己感興趣的流媒體文件的所在位置。

節(jié)點(diǎn)接入機(jī)制——每一個(gè)節(jié)點(diǎn)有一個(gè)在整個(gè)系統(tǒng)中的全局唯一的標(biāo)識(shí)，如IP地址，超級(jí)節(jié)點(diǎn)維護(hù)一個(gè)系統(tǒng)中其他節(jié)點(diǎn)的標(biāo)識(shí)緩存。當(dāng)新的節(jié)點(diǎn)A接入時(shí)，首先通過(guò)資源查找獲得所需文件的伙伴節(jié)點(diǎn)列表。對(duì)于列表中的節(jié)點(diǎn)，A通過(guò)“三次握手”的機(jī)制與對(duì)方建立連接，并測(cè)試對(duì)方的可用帶寬，A從所有的備選節(jié)點(diǎn)中選擇合適的節(jié)點(diǎn)作為自己的上游節(jié)點(diǎn)，則此建立連接的過(guò)程得以完成，新節(jié)點(diǎn)獲得穩(wěn)定的伙伴節(jié)點(diǎn)，開(kāi)始進(jìn)行流媒體下載緩沖，進(jìn)入穩(wěn)定的播放階段網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源發(fā)現(xiàn)模塊48網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源傳輸模塊

目的是完成資源傳輸?shù)娜蝿?wù)分配，任務(wù)調(diào)度以及任務(wù)控制等內(nèi)容。在P2P文件傳輸系統(tǒng)中，流媒體被劃分?jǐn)?shù)據(jù)塊，數(shù)據(jù)塊中的數(shù)據(jù)又被分為多個(gè)數(shù)據(jù)包，并且使用可用度向量的概念來(lái)標(biāo)識(shí)一個(gè)節(jié)點(diǎn)擁有數(shù)據(jù)塊中的哪些數(shù)據(jù)包。P2P流媒體傳輸系統(tǒng)的資源傳輸模塊分為請(qǐng)求數(shù)據(jù)、發(fā)送數(shù)據(jù)和接收數(shù)據(jù)三個(gè)相關(guān)聯(lián)的部分。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源傳輸模塊49接收數(shù)據(jù)部分：接收部分的主要任務(wù)是接收到數(shù)據(jù)后，按照一定的結(jié)構(gòu)將數(shù)據(jù)存放在本地，并且修改本地的數(shù)據(jù)可用度向量。如果接收到重復(fù)數(shù)據(jù)，則直接丟棄。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源傳輸模塊請(qǐng)求數(shù)據(jù)部分：首先向發(fā)送節(jié)點(diǎn)詢問(wèn)當(dāng)前期望傳輸文件塊的可用度向量，得到以后，根據(jù)請(qǐng)求與其他提供資源節(jié)點(diǎn)之間的帶寬情況，計(jì)算出對(duì)應(yīng)于每個(gè)提供資源節(jié)點(diǎn)的隊(duì)列長(zhǎng)度，然后將其發(fā)送的請(qǐng)求放入各自的隊(duì)列中，各隊(duì)列獨(dú)立的向?qū)?yīng)節(jié)點(diǎn)發(fā)送請(qǐng)求。接收數(shù)據(jù)部分：網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源50網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源傳輸模塊發(fā)送數(shù)據(jù)部分：先判斷接收到的請(qǐng)求類型連接請(qǐng)求：檢查是否達(dá)到最大連接數(shù)，達(dá)到則發(fā)送拒絕消息，反之發(fā)送接收消息。數(shù)據(jù)請(qǐng)求：從本地尋找對(duì)應(yīng)數(shù)據(jù)，找到則發(fā)送，未找到不發(fā)送網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——流媒體資源傳輸模塊發(fā)送數(shù)51概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理524.1總結(jié)

網(wǎng)絡(luò)編碼提出的初衷是為使多播傳輸達(dá)到理論上的最大傳輸容量,從而能取得較路由多播更好的網(wǎng)絡(luò)吞吐量。通過(guò)以上介紹，網(wǎng)絡(luò)編碼的優(yōu)點(diǎn)也體現(xiàn)出來(lái)了。提升網(wǎng)絡(luò)吞吐量無(wú)論是均勻鏈路還是非均勻鏈路,網(wǎng)絡(luò)編碼均能夠獲得更高的多播容量,而且對(duì)于節(jié)點(diǎn)平均度數(shù)越大,網(wǎng)絡(luò)編碼在網(wǎng)絡(luò)吞吐量上的優(yōu)勢(shì)越明顯。均衡網(wǎng)絡(luò)負(fù)載網(wǎng)絡(luò)編碼多播可有效利用除多播樹(shù)路徑外其它的網(wǎng)絡(luò)鏈路,可將網(wǎng)絡(luò)流量分布于更廣泛的網(wǎng)絡(luò)上,從而均衡網(wǎng)絡(luò)負(fù)載。這樣就有助于解決網(wǎng)絡(luò)擁塞等問(wèn)題。提高帶寬利用率雖然傳輸鏈路增多了，但是每條鏈路上的信息減少了（均衡了），總體是減少了網(wǎng)絡(luò)帶寬，提高了網(wǎng)絡(luò)帶寬利用率。4.1總結(jié)網(wǎng)絡(luò)編碼提出的初衷是為使多播傳53雖然網(wǎng)絡(luò)編碼優(yōu)點(diǎn)突出,但是缺點(diǎn)也很明顯。運(yùn)用網(wǎng)絡(luò)編碼增加了計(jì)算的復(fù)雜性,而且網(wǎng)路節(jié)點(diǎn)需要緩存足夠的輸入信息,因此編碼操作增加了傳輸時(shí)延和節(jié)點(diǎn)額外的I/O、CPU消耗。應(yīng)用網(wǎng)絡(luò)編碼還存在同步問(wèn)題,主要是由于信宿節(jié)點(diǎn)必須等待收到足夠的編碼信息,才能開(kāi)始譯碼。同步問(wèn)題給在實(shí)時(shí)系統(tǒng)中應(yīng)用網(wǎng)絡(luò)編碼提出了挑戰(zhàn)。雖然網(wǎng)絡(luò)編碼優(yōu)點(diǎn)突出,但是缺點(diǎn)也很明顯。54Thankyou！Thankyou！55網(wǎng)絡(luò)編碼組員：代亮亮徐杰郭鑫李文杰胡怡劉慧芳張曉宇網(wǎng)絡(luò)編碼組員：56概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理57概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理581、概念網(wǎng)絡(luò)編碼：通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突破。網(wǎng)絡(luò)編碼：融合了編碼和路由轉(zhuǎn)發(fā)的信息交換技術(shù)，在傳統(tǒng)存儲(chǔ)轉(zhuǎn)發(fā)的路由方法基礎(chǔ)上，通過(guò)允許對(duì)接收的多個(gè)數(shù)據(jù)包進(jìn)行編碼(如模二加、有限域上的運(yùn)算等)信息融合，增加單次傳輸?shù)男畔⒘?，以提高網(wǎng)絡(luò)信息傳輸效率和整體性能核心：允許網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)傳輸信息進(jìn)行編碼處理經(jīng)典信息論中的信息傳輸：?jiǎn)渭児蚕砭W(wǎng)絡(luò)和鏈路資源，彼此獨(dú)立。1、概念網(wǎng)絡(luò)編碼：通信網(wǎng)絡(luò)中信息處理和傳輸理論研究上的重大突59網(wǎng)絡(luò)編碼的起源與發(fā)展概念誕生：1998論文“NetworkInformationFlowTheory”1999Yeung和Zhang發(fā)表的關(guān)于衛(wèi)星通信的論文正式發(fā)表：2000網(wǎng)絡(luò)編碼理論的奠基之作：先鋒論文“NetworkInformationFlow”里程碑（2003）：香港中文大學(xué)訊息工程系的李碩彥教授、楊偉豪教授、蔡寧教授發(fā)表了論文“LinearNetworkCoding”指出線性網(wǎng)絡(luò)編碼可以達(dá)到多播方式下的網(wǎng)絡(luò)容量。Koetter和Medard提出網(wǎng)絡(luò)編碼的代數(shù)學(xué)(Algebra)框架，即用抽象代數(shù)來(lái)解決線性網(wǎng)絡(luò)編碼的問(wèn)題，為研究網(wǎng)絡(luò)編碼提供了一個(gè)用力的數(shù)學(xué)工具

Sanders等提出具有多項(xiàng)式復(fù)雜度的線性信息流算法，該算法屬于集中式的碼構(gòu)造算法。Ho等提出隨機(jī)網(wǎng)絡(luò)編碼(RandomNetworkCoding,RNC)，屬于分布式的碼構(gòu)造方法。網(wǎng)絡(luò)編碼的起源與發(fā)展概念誕生：60基礎(chǔ)知識(shí)：最大流最小割定理1/5割:網(wǎng)絡(luò)中定點(diǎn)的一個(gè)劃分，把網(wǎng)絡(luò)中所有的頂點(diǎn)劃分為兩個(gè)頂點(diǎn)的集合S和T，其中源點(diǎn)s屬于S，匯點(diǎn)t屬于T，記為CUT（S，T）頂點(diǎn)集:S={1,2,3},T={4,5}構(gòu)成一個(gè)割框外是容量，框內(nèi)是流量注：源點(diǎn)和匯點(diǎn)不能屬于同一個(gè)頂點(diǎn)集合：如下就不能構(gòu)成一個(gè)割基礎(chǔ)知識(shí)：最大流最小割定理1/5割:網(wǎng)絡(luò)中定點(diǎn)的一個(gè)劃分，把61基礎(chǔ)知識(shí)：最大流最小割定理2/5s-t圖：a一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)b有向邊，<i,j>是從i到j(luò)c每條邊都有一個(gè)非負(fù)的權(quán)值d容量cap（i，j）等于0，說(shuō)明不存在邊基礎(chǔ)知識(shí)：最大流最小割定理2/5s-t圖：62基礎(chǔ)知識(shí)：最大流最小割定理3/5割邊：如果一條弧的兩個(gè)頂點(diǎn)分別屬于頂點(diǎn)集S和T（一個(gè)在S，另一個(gè)在T），這條弧成為CUT（S，T）的一條割邊。割的容量：割CUT（S,T）中所有正向割邊的容量和，稱為CUT（S，T）的容量，不同割的容量不同。最小割：所有割中權(quán)重和最小的一個(gè)割。eg.左圖中：割的容量為4+4=8

正向流量：4+2=6

逆向流量：1基礎(chǔ)知識(shí)：最大流最小割定理3/5割邊：如果一條弧的兩個(gè)頂點(diǎn)分63定理一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S,T）是任意一個(gè)割，那么f的值等于正向割邊的流量與負(fù)向割邊的流量之差。推論一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S，T）是一個(gè)割，那么f的值不超過(guò)割CUT（S,T）的容量推論二：網(wǎng)絡(luò)中的最大流不超過(guò)任何割的容量。定理二：在網(wǎng)絡(luò)中，如果f是一個(gè)流，CUT（S,T）是一個(gè)割，且f的值等于割CUT（S，T）的容量，那么f是一個(gè)最大流，CUT（S,T）是一個(gè)最小割?；A(chǔ)知識(shí)：最大流最小割定理4/5定理一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S,T）是任意一個(gè)64最大流最小割定理：任何網(wǎng)絡(luò)中，最大流等于最小割的容量形象的比喻：水流管道的最大流量由最細(xì)的管子容量決定。網(wǎng)絡(luò)的最大流量由最小割決定。基礎(chǔ)知識(shí)：最大流最小割定理5/5最大流最小割定理：任何網(wǎng)絡(luò)中，最大流等于最小割的容量形象的比65概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理66網(wǎng)絡(luò)編碼基本原理蝴蝶網(wǎng)絡(luò)”（ButterflyNetwork）左圖為“單信源二信宿”蝴蝶網(wǎng)絡(luò)設(shè)各鏈路容量為1S：信源節(jié)點(diǎn)。Y,Z：信宿節(jié)點(diǎn)。其余為中間節(jié)點(diǎn)。由最大流最小割定理，該多播的最大理論傳輸容量為2。即理論上信宿Y和Z能夠同時(shí)收到信源S發(fā)出的2個(gè)單位的信息,，也就是說(shuō)能同時(shí)收到b1和b2。網(wǎng)絡(luò)編碼基本原理左圖為“單信源二信宿”蝴蝶網(wǎng)絡(luò)67圖(a)圖(b)網(wǎng)絡(luò)編碼基本原理圖(a)圖(b)網(wǎng)絡(luò)編碼基本原理68網(wǎng)絡(luò)編碼基本原理網(wǎng)絡(luò)編碼的核心思想具備編碼條件的網(wǎng)絡(luò)節(jié)點(diǎn)A對(duì)接收到的信息進(jìn)行一定方式的處理(編碼)，然后傳輸給下一級(jí)的網(wǎng)絡(luò)節(jié)點(diǎn)BB再編碼，然后傳輸給C。如此反復(fù)，直到所有經(jīng)過(guò)處理后的信息都匯聚到信宿節(jié)點(diǎn)為止。在信宿節(jié)點(diǎn)，通過(guò)逆過(guò)程的操作(譯碼)，即可譯出信源發(fā)送的原始信息。網(wǎng)絡(luò)編碼基本原理69目的：A和B希望分別向?qū)Ψ桨l(fā)送數(shù)據(jù)塊x和yBSBSSSARBXY

簡(jiǎn)單網(wǎng)絡(luò)編碼示例基站中繼站用戶站BRYRBXARXRAY傳統(tǒng)方法：需要4個(gè)時(shí)隙1)

2)3)4)

網(wǎng)絡(luò)編碼方法：需要的時(shí)隙數(shù)減為3個(gè)1)2)3)R對(duì)X，Y執(zhí)行異或操作并向A,B廣播，A，B各自有X，Y的信息，可以通過(guò)譯碼得到X，和YARXBRY網(wǎng)絡(luò)編碼基本原理目的：BSBSSSA70概念12應(yīng)用3總結(jié)4目錄原理概念12應(yīng)用3總結(jié)4目錄原理71

協(xié)作通信通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的方式接收轉(zhuǎn)發(fā)其他伙伴的信息到目的端，以獲得系統(tǒng)的分集增益，從而對(duì)抗無(wú)線信道的各種衰落。網(wǎng)絡(luò)編碼借助于融合了編碼和路由的新思想，通過(guò)允許中間節(jié)點(diǎn)對(duì)來(lái)自不同鏈路的信息進(jìn)行解碼組合，利用數(shù)據(jù)包之間的相關(guān)性來(lái)解碼，從而提升整個(gè)網(wǎng)絡(luò)的性能。網(wǎng)絡(luò)編碼在無(wú)線協(xié)作通信中的應(yīng)用背景與意義協(xié)作通信通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)協(xié)作的方式接收轉(zhuǎn)發(fā)其他伙伴72協(xié)作通信系統(tǒng)模型

結(jié)合網(wǎng)路編碼思想與協(xié)作通信技術(shù)，以能更好的充分發(fā)揮網(wǎng)絡(luò)編碼技術(shù)在無(wú)線協(xié)作通信系統(tǒng)中的應(yīng)用優(yōu)勢(shì)，進(jìn)一步提高基于網(wǎng)絡(luò)編碼的無(wú)線協(xié)作系統(tǒng)性能.協(xié)作通信系統(tǒng)模型結(jié)合網(wǎng)路編碼思想與協(xié)作通信技術(shù)，以能73協(xié)作通信的分類放大轉(zhuǎn)發(fā)（AF,AmplifyandForward）

在信道質(zhì)量較差的情況下，AF會(huì)將噪聲放大。解碼轉(zhuǎn)發(fā)（DF,DecodeandForward）

在信道質(zhì)量較差的情況下，DF中繼無(wú)法正確解碼。兩者都是信息的重復(fù)傳輸，信道利用率不高，造成資源浪費(fèi)。編碼協(xié)作（CC，CooperationCoded）

提供比重復(fù)編碼更高效的編碼方式，從而帶來(lái)更多的編碼增益。但是中繼點(diǎn)復(fù)雜度高，中繼點(diǎn)信號(hào)處理時(shí)延增大，降低了時(shí)效性。協(xié)作通信的分類放大轉(zhuǎn)發(fā)（AF,AmplifyandFo74編碼協(xié)作（CC）

CC協(xié)議是解碼轉(zhuǎn)發(fā)協(xié)作（DF）的進(jìn)一步延伸，它改變DF策略的重復(fù)編碼方式，通過(guò)兩條不同的，相互獨(dú)立的衰落信道來(lái)發(fā)送每個(gè)用戶的信息碼字的不同部分，從而提供更多的編碼增益。編碼協(xié)作（CC）CC協(xié)議是解碼轉(zhuǎn)發(fā)協(xié)作（DF）的進(jìn)一75無(wú)線網(wǎng)絡(luò)編碼分類1.網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼2.物理層網(wǎng)絡(luò)編碼無(wú)線網(wǎng)絡(luò)編碼分類1.網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼76網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼

針對(duì)網(wǎng)絡(luò)層編碼技術(shù)，目前的一個(gè)研究重點(diǎn)是在實(shí)際的網(wǎng)絡(luò)條件下，采樣網(wǎng)絡(luò)編碼后的網(wǎng)絡(luò)容量以及可以達(dá)到的網(wǎng)絡(luò)容量的傳輸策略網(wǎng)絡(luò)層網(wǎng)絡(luò)編碼針對(duì)網(wǎng)絡(luò)層編碼技術(shù)，目前的一個(gè)研究重點(diǎn)是在實(shí)77物理層網(wǎng)絡(luò)編碼

物理層網(wǎng)絡(luò)編碼提高了無(wú)線頻譜的利用率，物理層網(wǎng)絡(luò)編碼技術(shù)目前的研究重點(diǎn)是怎樣有效的從混合信號(hào)中分離出需要的信號(hào)。物理層網(wǎng)絡(luò)編碼物理層網(wǎng)絡(luò)編碼提高了無(wú)線頻譜的利用率，物理層78S1RS2D傳輸時(shí)隙信息傳輸方向傳輸信息簡(jiǎn)要說(shuō)明時(shí)隙1（直傳）S1(R,D)X1S1傳送信息X1到R和D時(shí)隙2（直傳）S2(R,D)X2S2傳送信息X2到R和D時(shí)隙3（協(xié)作）R（D）X1X2R將收到的信息進(jìn)行編碼后轉(zhuǎn)發(fā)給D時(shí)隙1時(shí)隙2時(shí)隙3S1RS2D傳輸時(shí)隙信息傳輸方向傳輸信息簡(jiǎn)要說(shuō)明時(shí)隙1（79網(wǎng)絡(luò)編碼在分布式存儲(chǔ)中的應(yīng)用網(wǎng)絡(luò)編碼在分布式存儲(chǔ)中的應(yīng)用80分布式存儲(chǔ)由來(lái)及優(yōu)越性傳統(tǒng)的存儲(chǔ)模型中,大多為直連式存儲(chǔ)系統(tǒng),其存儲(chǔ)設(shè)備直接與服務(wù)器相連。此類存儲(chǔ)模型可擴(kuò)展性極差,數(shù)據(jù)共享能力弱。1986年,著名學(xué)者李凱針對(duì)大數(shù)據(jù)存儲(chǔ)困難的現(xiàn)狀提出了分布式存儲(chǔ)

的概念,該思想源于虛擬存儲(chǔ)系統(tǒng)。分布式存儲(chǔ)就是將源文件分散的存儲(chǔ)到網(wǎng)絡(luò)中的相互獨(dú)立的空閑節(jié)點(diǎn)中。優(yōu)越性(1)高可靠性(2)修復(fù)功能(3)可擴(kuò)展性(4)高性能(5)透明性分布式存儲(chǔ)由來(lái)及優(yōu)越性81網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用網(wǎng)絡(luò)糾錯(cuò)碼

網(wǎng)絡(luò)編碼的初衷在于提高網(wǎng)絡(luò)的吞吐量,但是隨著進(jìn)一步研究發(fā)現(xiàn)它也是一種安全網(wǎng)絡(luò)傳輸?shù)暮梅绞健Ｈ欢诳箵舭菡纪ス魰r(shí),我們不僅要能夠檢測(cè)出敵手對(duì)信息的惡意攻擊,還要盡量能夠做到對(duì)這些信息的恢復(fù),這就是網(wǎng)絡(luò)糾錯(cuò)碼.傳統(tǒng)的密碼學(xué)方法存在一定的局限性計(jì)算復(fù)雜度較大、數(shù)據(jù)傳輸速率較低、消息冗余較大網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用網(wǎng)絡(luò)糾錯(cuò)碼82分布式存儲(chǔ)的維護(hù)最常用冗余數(shù)據(jù)的維護(hù)技術(shù)是復(fù)制和糾刪碼。當(dāng)我們?cè)诶眉m刪碼對(duì)失效節(jié)點(diǎn)進(jìn)行修復(fù)的時(shí)候，首先要將原始數(shù)據(jù)重建，然后將其用網(wǎng)絡(luò)編碼的方法進(jìn)行編碼，但是這樣修復(fù)時(shí)數(shù)據(jù)的下載量遠(yuǎn)遠(yuǎn)多于節(jié)點(diǎn)的存儲(chǔ)，即修復(fù)帶寬遠(yuǎn)大于存儲(chǔ)量。分布式存儲(chǔ)的維護(hù)最常用冗余數(shù)據(jù)的維護(hù)技術(shù)是復(fù)制和糾刪碼。83再生碼兩種常用的冗余數(shù)據(jù)維護(hù)技術(shù)在對(duì)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行修復(fù)時(shí)，需要消耗很大的下載帶寬，于是產(chǎn)生了一種新型的技術(shù)——再生碼。實(shí)現(xiàn)了存儲(chǔ)量與修復(fù)下載帶寬的良好折中，部分還巧妙地結(jié)合了復(fù)制與糾刪碼的各自優(yōu)點(diǎn)，保證了具有極高的節(jié)點(diǎn)成功修復(fù)的可能性。再生碼兩種常用的冗余數(shù)據(jù)維護(hù)技術(shù)在對(duì)數(shù)據(jù)節(jié)點(diǎn)進(jìn)行修復(fù)時(shí)，需要84信息流圖他們把節(jié)點(diǎn)修復(fù)的問(wèn)題刻畫(huà)為網(wǎng)絡(luò)系統(tǒng)中普遍的單源多播問(wèn)題，然后把對(duì)分布式存儲(chǔ)系統(tǒng)的分析化成對(duì)信息流圖的分析信息流圖他們把節(jié)點(diǎn)修復(fù)的問(wèn)題刻畫(huà)為網(wǎng)絡(luò)系統(tǒng)中普遍的單源多播問(wèn)85再生碼的一個(gè)定理對(duì)于任意，分布式存儲(chǔ)系統(tǒng)中的點(diǎn)是可行的，它可以通過(guò)線性網(wǎng)絡(luò)編碼來(lái)實(shí)現(xiàn)。當(dāng)時(shí)，在信息理論上是不可能實(shí)現(xiàn)的。其理論界函數(shù)如下：其中對(duì)于給定的n，k，d，最小修復(fù)帶寬的值為再生碼的一個(gè)定理對(duì)于任意86信息論-網(wǎng)絡(luò)編碼課件87MSR和MBRMSR和MBR88網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用89網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用傳統(tǒng)的密碼學(xué)方法存在一定的局限性

(1)計(jì)算復(fù)雜度較大

(2)數(shù)據(jù)傳輸速率較低

(3)消息冗余較大網(wǎng)絡(luò)糾錯(cuò)碼

網(wǎng)絡(luò)編碼的初衷在于提高網(wǎng)絡(luò)的吞吐量,但是隨著進(jìn)一步研究發(fā)現(xiàn)它也是一種安全網(wǎng)絡(luò)傳輸?shù)暮梅绞?。然而在抗擊拜占庭攻擊時(shí),我們不僅要能夠檢測(cè)出敵手對(duì)信息的惡意攻擊,還要盡量能夠做到對(duì)這些信息的恢復(fù),這就是網(wǎng)絡(luò)糾錯(cuò)碼.網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用傳統(tǒng)的密碼學(xué)方法存在一定的局90搭載竊聽(tīng)網(wǎng)絡(luò)通信的模型網(wǎng)絡(luò)通信的模型m:是消息本身k:是為了達(dá)到安全的隨機(jī)數(shù)右圖中紅線是竊聽(tīng)集，但是一個(gè)時(shí)間內(nèi)只允許敵手竊聽(tīng)其中的一條，這樣接收節(jié)點(diǎn)T和T＇能夠安全接收到信源傳來(lái)的消息ｍ。網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用搭載竊聽(tīng)網(wǎng)絡(luò)通信的模型網(wǎng)絡(luò)通信的模型m:是消息本身網(wǎng)絡(luò)編碼理91圖3Alice、Bob和Eve的數(shù)據(jù)包X:表示Alice發(fā)出的原始消息塊Z:表示攻擊者Eve注入的錯(cuò)誤消息塊Y:表示經(jīng)過(guò)篡改被Bob接收的消息塊矩陣I、L和T分別表示數(shù)據(jù)包X、Y和Z的編碼向量。圖3是有線和無(wú)線網(wǎng)絡(luò)的帶有拜占庭攻擊者的攻擊模型，為了簡(jiǎn)化符號(hào)，只考慮單信源單信宿的通信問(wèn)題。相似于許多網(wǎng)絡(luò)編碼的算法，這里每個(gè)體制都可以從單個(gè)接收方的情形推廣到多播通信。網(wǎng)絡(luò)編碼理論在數(shù)據(jù)安全領(lǐng)域的應(yīng)用圖3Alice、Bob和Eve的數(shù)據(jù)包X:表示Al923種主要攻擊模型(1)秘密共享模型此模型假定Alice和Bob有一個(gè)低速率的秘密信道，Eve不知道秘密信道上的傳輸消息?？紤]將消息經(jīng)過(guò)網(wǎng)絡(luò)編碼后在網(wǎng)絡(luò)上傳輸，Eve可以觀察到所有除秘密信道之外的所有傳輸，也可以選擇是否在他所控制的節(jié)點(diǎn)處在要傳輸?shù)臄?shù)據(jù)包中注入一些惡意數(shù)據(jù)到從而達(dá)到阻止Alice和Bob通信的目的。(2)萬(wàn)能攻擊者模型此模型中Eve除了在控制鏈接數(shù)目上受到一定限制外，是萬(wàn)能的、無(wú)所不知的，Alice和Bob之間沒(méi)有獨(dú)立于Eve的秘密信道。(3)有限的竊聽(tīng)模型在這個(gè)模型中，Eve的竊聽(tīng)能力是有限制的，只能觀察到至多ZI個(gè)傳送的包。3種主要攻擊模型(1)秘密共享模型93網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用94網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用————p2p系統(tǒng)簡(jiǎn)介

p2p網(wǎng)絡(luò)系統(tǒng)：

P2P全稱為：Peer-to-Peer，即對(duì)等網(wǎng)絡(luò)或?qū)Φ扔?jì)算。主要采用非集中式的拓?fù)浣Y(jié)構(gòu)，可以應(yīng)對(duì)集中式拓?fù)浣Y(jié)構(gòu)出現(xiàn)的過(guò)量存儲(chǔ)負(fù)載、DOS（DenialofService，拒絕服務(wù)）攻擊，網(wǎng)絡(luò)帶寬限制等一些難以解決的問(wèn)題。P2p網(wǎng)絡(luò)系統(tǒng)發(fā)展的四種拓?fù)浣Y(jié)構(gòu):中心化拓?fù)?、全分布式非結(jié)構(gòu)化拓?fù)洹⑷植冀Y(jié)構(gòu)式拓?fù)?、半分布式拓?fù)渚W(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用————p2p系統(tǒng)簡(jiǎn)介

p295網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——p2p系統(tǒng)簡(jiǎn)介p2p網(wǎng)絡(luò)系統(tǒng)四種技術(shù)優(yōu)勢(shì)：非中心化：資源和服務(wù)分散在對(duì)等結(jié)點(diǎn)上，信息的交付直接在結(jié)點(diǎn)之間進(jìn)行，無(wú)需服務(wù)器介入，避免了可能的瓶頸?？蓴U(kuò)展性：系統(tǒng)的資源和服務(wù)能力可以隨著新用戶的加入和服務(wù)需求的增加而提高。魯棒性：即系統(tǒng)的健壯性，在抗異常和突發(fā)危險(xiǎn)情況的能力。服務(wù)是分散在各對(duì)等結(jié)點(diǎn)上的，沒(méi)有中心節(jié)點(diǎn)和特殊節(jié)點(diǎn)，某些節(jié)點(diǎn)出現(xiàn)異?；蛟馐芄魰r(shí)，整個(gè)網(wǎng)絡(luò)的影響很小，具有很強(qiáng)的自組織性和自愈性。負(fù)載均衡：每個(gè)節(jié)點(diǎn)既是服務(wù)器又是客戶機(jī)，同時(shí)因資源分布在多個(gè)節(jié)點(diǎn)，能更好實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的負(fù)載均衡。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——p2p系統(tǒng)簡(jiǎn)介p2p網(wǎng)絡(luò)96網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載三種文件下載方式：無(wú)分代隨機(jī)網(wǎng)絡(luò)編碼技術(shù)：優(yōu)點(diǎn)是分塊隨機(jī)組合后，整個(gè)網(wǎng)絡(luò)的分塊分布均衡化，而且能夠適應(yīng)P2P系統(tǒng)的動(dòng)態(tài)變化。缺點(diǎn)是編碼解碼過(guò)程是在一個(gè)文件的所有分塊之間進(jìn)行的，計(jì)算量大，系統(tǒng)開(kāi)銷過(guò)大，尤其是大文件分發(fā)時(shí)。分代網(wǎng)絡(luò)編碼方法：優(yōu)點(diǎn)是解決無(wú)分代網(wǎng)絡(luò)編碼的問(wèn)題。缺點(diǎn)是節(jié)點(diǎn)的退出使得網(wǎng)絡(luò)中已經(jīng)不存在足夠多線性無(wú)關(guān)的編碼組合以解碼得出某一代的原始分塊，從而導(dǎo)致無(wú)法解除完整的文件；源節(jié)點(diǎn)不知如何從本代信息傳輸切換到下一代信息傳輸?shù)?。代間網(wǎng)絡(luò)編碼方法：優(yōu)點(diǎn)：當(dāng)本代集中的某一代沒(méi)有足夠多線性無(wú)關(guān)的編碼塊時(shí)，可以由本代集其他代的線性無(wú)關(guān)編碼塊來(lái)彌補(bǔ)。缺點(diǎn)：無(wú)法單獨(dú)成功解出某一代的原始數(shù)據(jù)。網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載三種文件下載方式97網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載假設(shè)服務(wù)器需要傳輸文件給對(duì)等節(jié)點(diǎn)A，首先將服務(wù)器上的文件分解成n個(gè)文件塊，B1—Bk，然后應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼，隨機(jī)選擇系數(shù)C1—Cn，將線性網(wǎng)絡(luò)編碼后的組合塊E1=c1B1+c2B2…cnBk傳送給對(duì)等節(jié)點(diǎn)A，同理得出E2=C1'B1+C2'B2…Cn'Bk，該組合塊來(lái)自其它對(duì)等節(jié)點(diǎn)或者服務(wù)器。然后對(duì)等節(jié)點(diǎn)A再隨機(jī)選擇編碼系數(shù)C1''、C2''

，對(duì)E1和E2進(jìn)行線性操作，將操作的結(jié)果E3=

C1''E1+

C2''

E2

發(fā)送給對(duì)等節(jié)點(diǎn)B，對(duì)等節(jié)點(diǎn)B又傳送給其它的對(duì)等節(jié)點(diǎn)。只要每一個(gè)對(duì)等節(jié)點(diǎn)收到足夠多的線性無(wú)關(guān)組合，就可以通過(guò)解線性方程組譯出原始文件塊。無(wú)分代隨機(jī)網(wǎng)絡(luò)編碼技術(shù)網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載假設(shè)服務(wù)器需要傳98網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載把傳輸?shù)奈募确殖啥鄠€(gè)代，每個(gè)代再分成一定數(shù)目的塊，并且每代擁有的分塊數(shù)目是固定的。網(wǎng)絡(luò)編碼和解碼的過(guò)程只在同一代內(nèi)進(jìn)行，代與代之間編碼過(guò)程是獨(dú)立的。如圖所示，首先將文件分成m（m≥2）個(gè)代，每個(gè)代內(nèi)再分成n（n≥2，n>>m）個(gè)文件分塊。編碼過(guò)程在代內(nèi)進(jìn)行，而且代與代之間的編碼過(guò)程是彼此獨(dú)立的。源節(jié)點(diǎn)首先對(duì)第一代內(nèi)的文件執(zhí)行無(wú)分代網(wǎng)絡(luò)編碼直到信宿可以正確譯出第一代的所有信息，然后再在第二代內(nèi)執(zhí)行無(wú)分代網(wǎng)絡(luò)編碼信息傳輸，以此類推，直到傳輸完整個(gè)文件。分代網(wǎng)絡(luò)編碼方法網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載把傳輸?shù)奈募确?9網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載首先把文件分代，代內(nèi)再分組，然后把本代及其之前所有的代組合成一個(gè)代集，在代集內(nèi)進(jìn)行編碼。代集之間編碼過(guò)程是獨(dú)立的。如圖所示：首先把要發(fā)送的源文件分成m代，每代再分成k個(gè)塊，本代及其之前所有的代構(gòu)成代集，編碼過(guò)程和解碼過(guò)程都在代集內(nèi)進(jìn)行，并且代集之間彼此獨(dú)立。代間網(wǎng)絡(luò)編碼方法網(wǎng)絡(luò)編碼在p2p網(wǎng)絡(luò)系統(tǒng)中的應(yīng)用——文件下載首先把文件分代，100流媒體與文件下載的最大區(qū)別是前者要求邊下載邊播，而后者沒(méi)有這個(gè)要求