《隨機(jī)線性網(wǎng)絡(luò)編碼》PPT課件.ppt

,編碼模型,方案舉例,總結(jié)與展望,overview,A Random Linear Network Coding Approach to Multicast,簡(jiǎn)要介紹,簡(jiǎn)要介紹,最大流最小截定理,網(wǎng)絡(luò)容量問(wèn)題,隨機(jī)分布問(wèn)題,滿足網(wǎng)絡(luò)容量要求,多源（包括相關(guān)源）多徑問(wèn)題,一般組播網(wǎng)絡(luò)結(jié)構(gòu),簡(jiǎn)要介紹,對(duì)于除了信宿節(jié)點(diǎn)外的所有中間節(jié)點(diǎn)，只要在一個(gè)足夠大的有限域上隨機(jī)選擇它們輸入鏈路到輸出鏈路的映射，且各節(jié)點(diǎn)映射關(guān)系的選取是相互獨(dú)立的，從而保證各信宿能以較高概率成功譯碼,各鏈路上的系數(shù)向量和信源發(fā)送的信息進(jìn)行同步傳輸，信息在通過(guò)編碼節(jié)點(diǎn)時(shí)，系數(shù)向量根據(jù)隨機(jī)選取的映射關(guān)系進(jìn)行更新，最終信宿節(jié)點(diǎn)收到的輸入信息將包含輸入鏈路對(duì)應(yīng)的全局編碼向量和信源發(fā)送的信息流，然后采用高斯消元法（解線性方程組）正確譯碼獲得信源原始傳輸?shù)男畔?簡(jiǎn)要介紹,我們考慮的問(wèn)題,怎樣構(gòu)建隨機(jī)線性網(wǎng)絡(luò)編碼 怎樣在分布網(wǎng)絡(luò)中有效的將信息傳輸?shù)浇邮展?jié)點(diǎn),編碼模型,做出的假設(shè),每條鏈路的容量是一比特每單元，如果某條邊的容量大于一比特每單位時(shí)間，則看做是幾條并行的邊。如果邊的容量不是整數(shù)，則將時(shí)間單元取得大一點(diǎn)，使得小數(shù)部分可以近似成整數(shù)。 假設(shè)每條鏈路的延遲是一樣的。 對(duì)于線性相關(guān)源，我們認(rèn)為每一個(gè)獨(dú)立信源的熵率是一比特每單位時(shí)間，如果不是，則將它們變成一些并行的熵率是一比特每單位時(shí)間的源的集合。 對(duì)于任意相關(guān)源，我們要求信源的熵是整數(shù)，并且有著任意的聯(lián)合概率分布 對(duì)于不同的節(jié)點(diǎn)，它們要處理的隨機(jī)過(guò)程之間是相互獨(dú)立的，這個(gè)假設(shè)符合通信網(wǎng)絡(luò)一般的情況,Add your title in here,編碼模型,多信源的Slepian Wolf定理：,有r個(gè)離散的無(wú)記憶信息源 ,它們是隨機(jī)二進(jìn)制序列，對(duì)每個(gè)信源獨(dú)立進(jìn)行編碼，再進(jìn)行聯(lián)合譯碼，其性能跟所有信源聯(lián)合編碼是一致的。只要滿足在r個(gè)信源中任取k個(gè)信源的和速率，不能小于這k個(gè)信源以剩余的r-k個(gè)信源為條件的熵，而對(duì)于總的和速率不能小于這r個(gè)信源的聯(lián)合熵。,Add your title in here,編碼模型,不考慮延遲,考慮延遲,考慮邊容量為1的情況，每個(gè)節(jié)點(diǎn)在等到所有進(jìn)入此節(jié)點(diǎn)的信息后才發(fā)往離開此節(jié)點(diǎn)的出邊,有著v個(gè)節(jié)點(diǎn)和信息傳輸速率是r的循環(huán)網(wǎng)絡(luò)可以變成非循環(huán)網(wǎng)絡(luò)，此網(wǎng)絡(luò)有kv個(gè)節(jié)點(diǎn)，信息傳輸速率大于等于（k-v）r,信息在這種網(wǎng)絡(luò)上的傳輸可以被模仿成原來(lái)循環(huán)網(wǎng)絡(luò)k個(gè)時(shí)隙的步驟。這種情況我們假設(shè)每個(gè)鏈路的延遲是一樣的。,Add your title in here,編碼模型,非循環(huán)圖G=（V,E）表示的網(wǎng)絡(luò)中，每條邊可以根據(jù)網(wǎng)絡(luò)拓?fù)溥M(jìn)行順序編號(hào):如 ，對(duì)于每條從屬于E的邊，它的源表示為o( ),它的目的節(jié)點(diǎn)表示為d( )。一個(gè)路徑就是一系列的鏈路集合 ，對(duì)任意的i j, 。,進(jìn)入一個(gè)節(jié)點(diǎn)的邊數(shù)稱為一個(gè)節(jié)點(diǎn)的入度，由一個(gè)節(jié)點(diǎn)發(fā)出的邊數(shù)稱為節(jié)點(diǎn)的出度，節(jié)點(diǎn)的入度和出度的和稱為節(jié)點(diǎn)的度數(shù),Add your title in here,編碼模型,定義 為所有以節(jié)點(diǎn)V為結(jié)束點(diǎn)的邊的集合,定義 為所有從節(jié)點(diǎn)V開始的邊的集合,接收機(jī)處的終端鏈路的集合稱為,是在節(jié)點(diǎn)v收集到的u(v)個(gè)離散隨機(jī)過(guò)程,在邊e上傳輸?shù)碾S機(jī)過(guò)程稱為Y(e),Add your title in here,編碼模型,如圖是一個(gè)非延遲網(wǎng)絡(luò)，對(duì)于鏈路e上的隨機(jī)處理過(guò)程滿足,對(duì)于匯節(jié)點(diǎn)的輸出Z是由屬于 的所有邊上的隨機(jī)過(guò)程Y(e)形成的,這里的，都是從伽羅華域中隨機(jī)選擇的,如果，是獨(dú)立的，則系統(tǒng)是時(shí)不變的，否則系統(tǒng)是時(shí)變的,Add your title in here,編碼模型,表示在源節(jié)點(diǎn)觀察到的輸入信號(hào)矢量,另v點(diǎn)是一個(gè)網(wǎng)絡(luò)的匯結(jié)點(diǎn)，我們認(rèn)為 是這個(gè)節(jié)點(diǎn)的輸出過(guò)程矢量,另M表示一個(gè)網(wǎng)絡(luò)的傳輸矩陣，這樣z=x*M,對(duì)于固定的系數(shù)，我們不難看出，M矩陣?yán)锏臄?shù)也是從伽羅華域中選取的。,Add your title in here,編碼模型,伽 羅 華 域 簡(jiǎn) 介,GF( )域 以m=4為例，它的本原多項(xiàng)式為 ,即 在伽羅華域中，加法等于對(duì)應(yīng)位異或 先給出推導(dǎo)過(guò)程 0 0000 1000 1 0001 0011 1001 0010 0110 0001 0100 可以看出，當(dāng)m=4時(shí)，GF(4)是一個(gè)包含15個(gè)數(shù)的有限域，且這15個(gè)數(shù)循環(huán)產(chǎn)生。 在伽羅華域中，每對(duì)應(yīng)一個(gè)m，會(huì)有一個(gè)相應(yīng)的本原多項(xiàng)式，根據(jù)這個(gè)本原多項(xiàng)式，就可以推出域里面的值。,Add your title in here,編碼模型,傳輸矩陣可以表示為,Add your title in here,編碼模型,矩陣 A為源節(jié)點(diǎn)輸入信息與邊之間的關(guān)系矩陣，矩陣B為接收節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)進(jìn)行線性組合。單源單匯的節(jié)點(diǎn)的信息傳輸時(shí)，只要相應(yīng)的轉(zhuǎn)移矩陣是滿秩的，則源節(jié)點(diǎn)輸出的信息在接收端就可以準(zhǔn)確的恢復(fù)。單源多匯的節(jié)點(diǎn)的信息多播傳輸，利用網(wǎng)絡(luò)編碼時(shí)，只要能保證各個(gè)目的節(jié)點(diǎn)對(duì)應(yīng)的網(wǎng)絡(luò)轉(zhuǎn)移矩陣是滿秩的，則目的節(jié)點(diǎn)就可以準(zhǔn)確的恢復(fù)出原始發(fā)送的信息。,傳輸矩陣可以表示為,編碼模型,對(duì)有向網(wǎng)絡(luò)來(lái)說(shuō)，對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行排序，定義相應(yīng)的鄰接矩陣F，F(xiàn)矩陣的第i行第 j 列元素表示網(wǎng)絡(luò)流圖中第i條邊與第 j 條邊的連接關(guān)系，F(xiàn)可表示為 其中 表示有向邊 的終點(diǎn)與有向邊 的起點(diǎn)重合， 是有限域中的一非 0 元素，則M可表示為： 這種編碼的構(gòu)造簡(jiǎn)單而且有效，但是計(jì)算量大。,編碼模型,圖中節(jié)點(diǎn) v ，接收到編碼包 和 。節(jié)點(diǎn) v 應(yīng)用隨機(jī)網(wǎng)絡(luò)編碼的思想，在有限域中隨機(jī)選取系數(shù)(1,2)，并對(duì)接收到的兩個(gè)編碼包進(jìn)行運(yùn)算 ，得到新的編碼系數(shù)(3,10,13)，并將新的編碼包發(fā)送。,編碼模型,隨機(jī)網(wǎng)絡(luò)編碼中中間節(jié)點(diǎn)只需要對(duì)接收到的數(shù)據(jù)進(jìn)行線性組合，而不需要判斷接收到的信息是否線性相關(guān)。這樣在接收節(jié)點(diǎn)處有可能出現(xiàn)線性相關(guān)的編碼信息導(dǎo)致解碼失敗。對(duì)于任意一個(gè)可行的多播網(wǎng)絡(luò)，如果網(wǎng)絡(luò)編碼部分或所有的編碼系數(shù)都是獨(dú)立的均勻的在一個(gè)有限域 上選取，則所有的目的節(jié)點(diǎn)能夠成功進(jìn)行解碼的概率至少為 ，q d ，其中 d 表示目的節(jié)點(diǎn)的數(shù)目， 為隨機(jī)選取編碼系數(shù)的鏈路數(shù)目，q為編碼符號(hào)域的大小。當(dāng)有限域的字母表大小 q 遠(yuǎn)大于接收節(jié)點(diǎn)數(shù)目 d 時(shí)，所有的接收節(jié)點(diǎn)可以以很高的概率恢復(fù)出原始信息。采用隨機(jī)線性網(wǎng)絡(luò)編碼的多播網(wǎng)絡(luò)中，多個(gè)源節(jié)點(diǎn)可以相互獨(dú)立，也可以線性相關(guān)。對(duì)于線性相關(guān)的源，隨機(jī)線性編碼起到了信息壓縮的作用。,方案舉例,從源節(jié)點(diǎn)發(fā)送兩個(gè)隨機(jī)過(guò)程 到矩形網(wǎng)絡(luò)中的未知位置,網(wǎng)絡(luò)的目的是每個(gè)節(jié)點(diǎn)都能收到信源發(fā)出的兩個(gè)隨機(jī)過(guò)程,隨機(jī)流結(jié)構(gòu)(RF) 源節(jié)點(diǎn)延兩個(gè)軸向分別發(fā)送兩 個(gè)信息 只接收到一個(gè)信息過(guò)程的節(jié)點(diǎn)向其它三個(gè)方向發(fā)送信息 接收到兩個(gè)信息過(guò)程的節(jié)點(diǎn)分別向?qū)?yīng)的軸向發(fā)送相應(yīng)的信息,方案舉例,隨機(jī)編碼結(jié)構(gòu)(RC) 源節(jié)點(diǎn)延兩個(gè)軸向分別發(fā)送兩 個(gè)信息 只接收到一個(gè)信息過(guò)程的節(jié)點(diǎn)向其它三個(gè)方向發(fā)送信息 接收到兩個(gè)信息過(guò)程的節(jié)點(diǎn)向其余的軸向發(fā)送接收到的信息的線性組合,對(duì)于接收位置為（x,y）的點(diǎn)，接收機(jī)能接收到兩個(gè)發(fā)送信息的概率為 RF RC （q是伽羅華域字母表）,方案舉例,RF方案和RC方案在不同點(diǎn)成功解調(diào)的概率,可以看到，當(dāng)網(wǎng)絡(luò)比較大時(shí)，RF方案是不適用的；對(duì)于RC，當(dāng)有限域越大時(shí)，能成功解調(diào)的概率越大,總結(jié)與展望,分布式隨機(jī)線性網(wǎng)絡(luò)編碼能有效地壓縮相關(guān)源。,隨機(jī)線性網(wǎng)絡(luò)編碼無(wú)須了解網(wǎng)絡(luò)的拓?fù)淝闆r，適用于鏈路動(dòng)態(tài)變化的場(chǎng)景，具有很強(qiáng)的實(shí)用性。,有限域的值越大時(shí)，