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

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

正向流量：4+2=6

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

簡單網絡編碼示例基站中繼站用戶站BRYRBXARXRAY傳統方法：需要4個時隙1)

2)3)4)

網絡編碼方法：需要的時隙數減為3個1)2)3)R對X，Y執行異或操作并向A,B廣播，A，B各自有X，Y的信息，可以通過譯碼得到X，和YARXBRY網絡編碼基本原理目的：BSBSSSA15概念12應用3總結4目錄原理概念12應用3總結4目錄原理16

協作通信通過網絡節點協作的方式接收轉發其他伙伴的信息到目的端，以獲得系統的分集增益，從而對抗無線信道的各種衰落。網絡編碼借助于融合了編碼和路由的新思想，通過允許中間節點對來自不同鏈路的信息進行解碼組合，利用數據包之間的相關性來解碼，從而提升整個網絡的性能。網絡編碼在無線協作通信中的應用背景與意義協作通信通過網絡節點協作的方式接收轉發其他伙伴17協作通信系統模型

結合網路編碼思想與協作通信技術，以能更好的充分發揮網絡編碼技術在無線協作通信系統中的應用優勢，進一步提高基于網絡編碼的無線協作系統性能.協作通信系統模型結合網路編碼思想與協作通信技術，以能18協作通信的分類放大轉發（AF,AmplifyandForward）

在信道質量較差的情況下，AF會將噪聲放大。解碼轉發（DF,DecodeandForward）

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

提供比重復編碼更高效的編碼方式，從而帶來更多的編碼增益。但是中繼點復雜度高，中繼點信號處理時延增大，降低了時效性。協作通信的分類放大轉發（AF,AmplifyandFo19編碼協作（CC）

CC協議是解碼轉發協作（DF）的進一步延伸，它改變DF策略的重復編碼方式，通過兩條不同的，相互獨立的衰落信道來發送每個用戶的信息碼字的不同部分，從而提供更多的編碼增益。編碼協作（CC）CC協議是解碼轉發協作（DF）的進一20無線網絡編碼分類1.網絡層網絡編碼2.物理層網絡編碼無線網絡編碼分類1.網絡層網絡編碼21網絡層網絡編碼

針對網絡層編碼技術，目前的一個研究重點是在實際的網絡條件下，采樣網絡編碼后的網絡容量以及可以達到的網絡容量的傳輸策略網絡層網絡編碼針對網絡層編碼技術，目前的一個研究重點是在實22物理層網絡編碼

物理層網絡編碼提高了無線頻譜的利用率，物理層網絡編碼技術目前的研究重點是怎樣有效的從混合信號中分離出需要的信號。物理層網絡編碼物理層網絡編碼提高了無線頻譜的利用率，物理層23S1RS2D傳輸時隙信息傳輸方向傳輸信息簡要說明時隙1（直傳）S1(R,D)X1S1傳送信息X1到R和D時隙2（直傳）S2(R,D)X2S2傳送信息X2到R和D時隙3（協作）R（D）X1X2R將收到的信息進行編碼后轉發給D時隙1時隙2時隙3S1RS2D傳輸時隙信息傳輸方向傳輸信息簡要說明時隙1（24網絡編碼在分布式存儲中的應用網絡編碼在分布式存儲中的應用25分布式存儲由來及優越性傳統的存儲模型中,大多為直連式存儲系統,其存儲設備直接與服務器相連。此類存儲模型可擴展性極差,數據共享能力弱。1986年,著名學者李凱針對大數據存儲困難的現狀提出了分布式存儲

的概念,該思想源于虛擬存儲系統。分布式存儲就是將源文件分散的存儲到網絡中的相互獨立的空閑節點中。優越性(1)高可靠性(2)修復功能(3)可擴展性(4)高性能(5)透明性分布式存儲由來及優越性26網絡編碼理論在數據安全領域的應用網絡糾錯碼

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

(1)計算復雜度較大

(2)數據傳輸速率較低

(3)消息冗余較大網絡糾錯碼

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

p2p網絡系統：

P2P全稱為：Peer-to-Peer，即對等網絡或對等計算。主要采用非集中式的拓撲結構，可以應對集中式拓撲結構出現的過量存儲負載、DOS（DenialofService，拒絕服務）攻擊，網絡帶寬限制等一些難以解決的問題。P2p網絡系統發展的四種拓撲結構:中心化拓撲、全分布式非結構化拓撲、全分布結構式拓撲、半分布式拓撲網絡編碼在p2p網絡系統中的應用————p2p系統簡介

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

，對E1和E2進行線性操作，將操作的結果E3=

C1''E1+

C2''

E2

發送給對等節點B，對等節點B又傳送給其它的對等節點。只要每一個對等節點收到足夠多的線性無關組合，就可以通過解線性方程組譯出原始文件塊。無分代隨機網絡編碼技術網絡編碼在p2p網絡系統中的應用——文件下載假設服務器需要傳43網絡編碼在p2p網絡系統中的應用——文件下載把傳輸的文件先分成多個代，每個代再分成一定數目的塊，并且每代擁有的分塊數目是固定的。網絡編碼和解碼的過程只在同一代內進行，代與代之間編碼過程是獨立的。如圖所示，首先將文件分成m（m≥2）個代，每個代內再分成n（n≥2，n>>m）個文件分塊。編碼過程在代內進行，而且代與代之間的編碼過程是彼此獨立的。源節點首先對第一代內的文件執行無分代網絡編碼直到信宿可以正確譯出第一代的所有信息，然后再在第二代內執行無分代網絡編碼信息傳輸，以此類推，直到傳輸完整個文件。分代網絡編碼方法網絡編碼在p2p網絡系統中的應用——文件下載把傳輸的文件先分44網絡編碼在p2p網絡系統中的應用——文件下載首先把文件分代，代內再分組，然后把本代及其之前所有的代組合成一個代集，在代集內進行編碼。代集之間編碼過程是獨立的。如圖所示：首先把要發送的源文件分成m代，每代再分成k個塊，本代及其之前所有的代構成代集，編碼過程和解碼過程都在代集內進行，并且代集之間彼此獨立。代間網絡編碼方法網絡編碼在p2p網絡系統中的應用——文件下載首先把文件分代，45流媒體與文件下載的最大區別是前者要求邊下載邊播，而后者沒有這個要求。目前基于p2p的實時流媒體系統中，根據覆蓋網節點所構成的拓撲規劃，分為單組播樹拓撲、多組播樹拓撲和網狀拓撲三類。如上圖所示現有p2p流媒體傳輸系統很多是基于分層編碼實現的，其系統主要由兩個模塊組成：資源發現模塊和資源傳輸模塊。網絡編碼在p2p網絡系統中的應用——流媒體流媒體與文件下載的最大區別是前者要求邊下載邊播，而后者沒有這46空間分層編碼實現不同大小圖像的服務兼容性。先在原始圖像中采樣的方法得到一幀空間上低頻分辨率的圖像。從原始圖像減去經過內插的抽樣圖像得到的差值圖像，對差值圖像再進行編碼得到增強層。時間分層編碼為實現不同頻率的視頻服務兼容。其基本層和增強層具有相同的空間分辨率和SNR。基本層圖像進行運動估計時只能在基本層中選取，同理增強層也是。視頻的精細分層為支持信道特性多變的包交換網上多媒體應用和服務而提出網絡編碼在p2p網絡系統中的應用——流媒體分層編碼網絡編碼在p2p網絡系統中的應用——流媒體分層編碼47網絡編碼在p2p網絡系統中的應用——流媒體資源發現模塊

主要任務是協助新的節點找到自己感興趣的流媒體文件的所在位置。

節點接入機制——每一個節點有一個在整個系統中的全局唯一的標識，如IP地址，超級節點維護一個系統中其他節點的標識緩存。當新的節點A接入時，首先通過資源查找獲得所需文件的伙伴節點列表。對于列表中的節點，A通過“三次握手”的機制與對方建立連接，并測試對方的可用帶寬，A從所有的備選節點中選擇合適的節點作為自己的上游節點，則此建立連接的過程得以完成，新節點獲得穩定的伙伴節點，開始進行流媒體下載緩沖，進入穩定的播放階段網絡編碼在p2p網絡系統中的應用——流媒體資源發現模塊48網絡編碼在p2p網絡系統中的應用——流媒體資源傳輸模塊

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

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

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

正向流量：4+2=6

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

簡單網絡編碼示例基站中繼站用戶站BRYRBXARXRAY傳統方法：需要4個時隙1)

2)3)4)

網絡編碼方法：需要的時隙數減為3個1)2)3)R對X，Y執行異或操作并向A,B廣播，A，B各自有X，Y的信息，可以通過譯碼得到X，和YARXBRY網絡編碼基本原理目的：BSBSSSA70概念12應用3總結4目錄原理概念12應用3總結4目錄原理71

協作通信通過網絡節點協作的方式接收轉發其他伙伴的信息到目的端，以獲得系統的分集增益，從而對抗無線信道的各種衰落。網絡編碼借助于融合了編碼和路由的新思想，通過允許中間節點對來自不同鏈路的信息進行解碼組合，利用數據包之間的相關性來解碼，從而提升整個網絡的性能。網絡編碼在無線協作通信中的應用背景與意義協作通信通過網絡節點協作的方式接收轉發其他伙伴72協作通信系統模型

結合網路編碼思想與協作通信技術，以能更好的充分發揮網絡編碼技術在無線協作通信系統中的應用優勢，進一步提高基于網絡編碼的無線協作系統性能.協作通信系統模型結合網路編碼思想與協作通信技術，以能73協作通信的分類放大轉發（AF,AmplifyandForward）

在信道質量較差的情況下，AF會將噪聲放大。解碼轉發（DF,DecodeandForward）

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

提供比重復編碼更高效的編碼方式，從而帶來更多的編碼增益。但是中繼點復雜度高，中繼點信號處理時延增大，降低了時效性。協作通信的分類放大轉發（AF,AmplifyandFo74編碼協作（CC）

CC協議是解碼轉發協作（DF）的進一步延伸，它改變DF策略的重復編碼方式，通過兩條不同的，相互獨立的衰落信道來發送每個用戶的信息碼字的不同部分，從而提供更多的編碼增益。編碼協作（CC）CC協議是解碼轉發協作（DF）的進一75無線網絡編碼分類1.網絡層網絡編碼2.物理層網絡編碼無線網絡編碼分類1.網絡層網絡編碼76網絡層網絡編碼

針對網絡層編碼技術，目前的一個研究重點是在實際的網絡條件下，采樣網絡編碼后的網絡容量以及可以達到的網絡容量的傳輸策略網絡層網絡編碼針對網絡層編碼技術，目前的一個研究重點是在實77物理層網絡編碼

物理層網絡編碼提高了無線頻譜的利用率，物理層網絡編碼技術目前的研究重點是怎樣有效的從混合信號中分離出需要的信號。物理層網絡編碼物理層網絡編碼提高了無線頻譜的利用率，物理層78S1RS2D傳輸時隙信息傳輸方向傳輸信息簡要說明時隙1（直傳）S1(R,D)X1S1傳送信息X1到R和D時隙2（直傳）S2(R,D)X2S2傳送信息X2到R和D時隙3（協作）R（D）X1X2R將收到的信息進行編碼后轉發給D時隙1時隙2時隙3S1RS2D傳輸時隙信息傳輸方向傳輸信息簡要說明時隙1（79網絡編碼在分布式存儲中的應用網絡編碼在分布式存儲中的應用80分布式存儲由來及優越性傳統的存儲模型中,大多為直連式存儲系統,其存儲設備直接與服務器相連。此類存儲模型可擴展性極差,數據共享能力弱。1986年,著名學者李凱針對大數據存儲困難的現狀提出了分布式存儲

的概念,該思想源于虛擬存儲系統。分布式存儲就是將源文件分散的存儲到網絡中的相互獨立的空閑節點中。優越性(1)高可靠性(2)修復功能(3)可擴展性(4)高性能(5)透明性分布式存儲由來及優越性81網絡編碼理論在數據安全領域的應用網絡糾錯碼

網絡編碼的初衷在于提高網絡的吞吐量,但是隨著進一步研究發現它也是一種安全網絡傳輸的好方式。然而在抗擊拜占庭攻擊時,我們不僅要能夠檢測出敵手對信息的惡意攻擊,還要盡量能夠做到對這些信息的恢復,這就是網絡糾錯碼.傳統的密碼學方法存在一定的局限性計算復雜度較大、數據傳輸速率較低、消息冗余較大網絡編碼理論在數據安全領域的應用網絡糾錯碼82分布式存儲的維護最常用冗余數據的維護技術是復制和糾刪碼。當我們在利用糾刪碼對失效節點進行修復的時候，首先要將原始數據重建，然后將其用網絡編碼的方法進行編碼，但是這樣修復時數據的下載量遠遠多于節點的存儲，即修復帶寬遠大于存儲量。分布式存儲的維護最常用冗余數據的維護技術是復制和糾刪碼。83再生碼兩種常用的冗余數據維護技術在對數據節點進行修復時，需要消耗很大的下載帶寬，于是產生了一種新型的技術——再生碼。實現了存儲量與修復下載帶寬的良好折中，部分還巧妙地結合了復制與糾刪碼的各自優點，保證了具有極高的節點成功修復的可能性。再生碼兩種常用的冗余數據維護技術在對數據節點進行修復時，需要84信息流圖他們把節點修復的問題刻畫為網絡系統中普遍的單源多播問題，然后把對分布式存儲系統的分析化成對信息流圖的分析信息流圖他們把節點修復的問題刻畫為網絡系統中普遍的單源多播問85再生碼的一個定理對于任意，分布式存儲系統中的點是可行的，它可以通過線性網絡編碼來實現。當時，在信息理論上是不可能實現的。其理論界函數如下：其中對于給定的n，k，d，最小修復帶寬的值為再生碼的一個定理對于任意86信息論-網絡編碼課件87MSR和MBRMSR和MBR88網絡編碼理論在數據安全領域的應用網絡編碼理論在數據安全領域的應用89網絡編碼理論在數據安全領域的應用傳統的密碼學方法存在一定的局限性

(1)計算復雜度較大

(2)數據傳輸速率較低

(3)消息冗余較大網絡糾錯碼

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

p2p網絡系統：

P2P全稱為：Peer-to-Peer，即對等網絡或對等計算。主要采用非集中式的拓撲結構，可以應對集中式拓撲結構出現的過量存儲負載、DOS（DenialofService，拒絕服務）攻擊，網絡帶寬限制等一些難以解決的問題。P2p網絡系統發展的四種拓撲結構:中心化拓撲、全分布式非結構化拓撲、全分布結構式拓撲、半分布式拓撲網絡編碼在p2p網絡系統中的應用————p2p系統簡介

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

，對E1和E2進行線性操作，將操作的結果E3=

C1''E1+

C2''

E2

發送給對等節點B，對等節點B又傳送給其它的對等節點。只要每一個對等節點收到足夠多的線性無關組合，就可以通過解線性方程組譯出原始文件塊。無分代隨機網絡編碼技術網絡編碼在p2p網絡系統中的應用——文件下載假設服務器需要傳98網絡編碼在p2p網絡系統中的應用——文件下載把傳輸的文件先分成多個代，每個代再分成一定數目的塊，并且每代擁有的分塊數目是固定的。網絡編碼和解碼的過程只在同一代內進行，代與代之間編碼過程是獨立的。如圖所示，首先將文件分成m（m≥2）個代，每個代內再分成n（n≥2，n>>m）個文件分塊。編碼過程在代內進行，而且代與代之間的編碼過程是彼此獨立的。源節點首先對第一代內的文件執行無分代網絡編碼直到信宿可以正確譯出第一代的所有信息，然后再在第二代內執行無分代網絡編碼信息傳輸，以此類推，直到傳輸完整個文件。分代網絡編碼方法網絡編碼在p2p網絡系統中的應用——文件下載把傳輸的文件先分99網絡編碼在p2p網絡系統中的應用——文件下載首先把文件分代，代內再分組，然后把本代及其之前所有的代組合成一個代集，在代集內進行編碼。代集之間編碼過程是獨立的。如圖所示：首先把要發送的源文件分成m代，每代再分成k個塊，本代及其之前所有的代構成代集，編碼過程和解碼過程都在代集內進行，并且代集之間彼此獨立。代間網絡編碼方法網絡編碼在p2p網絡系統中的應用——文件下載首先把文件分代，100流媒體與文件下載的最大區別是前者要求邊下載邊播，而后者沒有這個要求