網(wǎng)絡(luò)編碼--權(quán)威專家王新梅教授學(xué)術(shù)講座.ppt

1 網(wǎng)絡(luò)編碼networkcoding 西電ISN國家重點(diǎn)實(shí)驗(yàn)室2005 3 2 概要 1 網(wǎng)絡(luò)編碼的提出及現(xiàn)狀2 網(wǎng)絡(luò)編碼的基本原理3 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼4 無線組播中的網(wǎng)絡(luò)編碼5 結(jié)束語 3 1 網(wǎng)絡(luò)編碼的提出 在現(xiàn)有通信網(wǎng)絡(luò)中 網(wǎng)絡(luò)節(jié)點(diǎn)只是對(duì)收到的信息進(jìn)行存儲(chǔ)和轉(zhuǎn)發(fā) 扮演著轉(zhuǎn)發(fā)器的角色 但是從信息理論的觀點(diǎn)來說 沒有理由讓節(jié)點(diǎn)只能進(jìn)行存儲(chǔ)轉(zhuǎn)發(fā) 可以讓節(jié)點(diǎn)對(duì)多條輸入邊上收到的信息進(jìn)行一定的線性或非線性操作 編碼 然后再發(fā)送出去 起著編碼器的作用 網(wǎng)絡(luò)編碼正是根據(jù)這思想而產(chǎn)生的 在接收節(jié)點(diǎn)上 通過一定的運(yùn)算 譯出信源所發(fā)的信息 4 網(wǎng)絡(luò)編碼的提出 2000年 R Ahlswede等人在IEEEtrans IT上發(fā)表了一篇題為 網(wǎng)絡(luò)信息流 的文章 提出了網(wǎng)絡(luò)編碼的概念 那么 什么是網(wǎng)絡(luò)編碼呢 網(wǎng)絡(luò)編碼能給我們帶來什么好處呢 5 網(wǎng)絡(luò)編碼的提出 點(diǎn)對(duì)點(diǎn)的最小割最大流定理 對(duì)于已知的網(wǎng)絡(luò)流圖 從發(fā)點(diǎn)到收點(diǎn)的流量的最大值小于或等于任何一個(gè)割切的容量 即記 6 網(wǎng)絡(luò)編碼的提出 一個(gè)組播 multicast pointtomultipoint 傳輸 信源為 接收節(jié)點(diǎn)集合為 那么可達(dá)最高組播速率為如果采用傳統(tǒng)傳輸方法 可能無法達(dá)到速率 如果采用網(wǎng)絡(luò)編碼 可達(dá)到該最高速率 7 網(wǎng)絡(luò)編碼的提出 一個(gè)經(jīng)典例子 采用網(wǎng)絡(luò)編碼后 達(dá)到速率 8 網(wǎng)絡(luò)編碼的提出 網(wǎng)絡(luò)編碼帶來的好處 使組播傳輸速率達(dá)到最小割最大流決定的網(wǎng)絡(luò)容量的上限節(jié)省網(wǎng)絡(luò)帶寬資源消耗均衡網(wǎng)絡(luò)負(fù)載提高網(wǎng)絡(luò)魯棒性 9 網(wǎng)絡(luò)編碼的發(fā)展過程 2000年 Ahlswede等提出了網(wǎng)絡(luò)編碼的概念 2002年 Koetter等給出了網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造算法 是指數(shù)時(shí)間算法 集中式 2002年 Cai等提出了基于網(wǎng)絡(luò)編碼的網(wǎng)絡(luò)糾錯(cuò)碼概念 2002年 Cai等提出了采用網(wǎng)絡(luò)編碼時(shí)的信息完安全性問題 2003年 Sander等給出了網(wǎng)絡(luò)編碼的多項(xiàng)式時(shí)間算法 集中式 2003年 Chou等提出了分布式網(wǎng)絡(luò)編碼 通過仿真得到其性能 2003年 Ho等也提出了隨機(jī)網(wǎng)絡(luò)編碼 分布式 2004年 Wu等將網(wǎng)絡(luò)編碼應(yīng)用于無線網(wǎng)絡(luò)以節(jié)省能量 10 網(wǎng)絡(luò)編碼的現(xiàn)狀 線性網(wǎng)絡(luò)編碼和非線性網(wǎng)絡(luò)編碼 分布式網(wǎng)絡(luò)編碼和集中式網(wǎng)絡(luò)編碼 網(wǎng)絡(luò)編碼在組播和非組播網(wǎng)絡(luò)中的應(yīng)用目前 組播集中式線性網(wǎng)絡(luò)編碼算法主要有兩種 代數(shù)構(gòu)造方式和多項(xiàng)式時(shí)間算法 11 2 網(wǎng)絡(luò)編碼的基本原理 信息傳輸網(wǎng)絡(luò)可用圖表示信源節(jié)點(diǎn)集 信宿節(jié)點(diǎn)集 邊的頭節(jié)點(diǎn)用表示邊的尾節(jié)點(diǎn)用表示 假設(shè)每條邊容量為1比特 單位時(shí)間 可通過合適選取單位時(shí)間大小和將鏈路進(jìn)行拆分實(shí)現(xiàn) 12 網(wǎng)絡(luò)編碼的基本原理 網(wǎng)絡(luò)編碼的數(shù)學(xué)描述 適用于組播和非組播傳輸 對(duì)邊集中的每條邊 存在一種映射 這是對(duì)應(yīng)于每條邊的編碼函數(shù) 13 網(wǎng)絡(luò)編碼的基本原理 網(wǎng)絡(luò)編碼的數(shù)學(xué)描述 適用于組播和非組播傳輸 目的節(jié)點(diǎn)為了得到所需信息 存在映射 映射是對(duì)應(yīng)于目的節(jié)點(diǎn)的第個(gè)信源符號(hào)的譯碼函數(shù) 14 網(wǎng)絡(luò)編碼的基本原理 線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造設(shè)所有信源的總信息輸出速率是比特 單位時(shí)間 把它們的輸出進(jìn)行一個(gè)定序 如下 其中是節(jié)點(diǎn)的信息輸出速率 15 網(wǎng)絡(luò)編碼的基本原理 線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造設(shè)是無延遲的通信網(wǎng)絡(luò) 我們稱這樣的編碼為線性網(wǎng)絡(luò)編碼 如果對(duì)于網(wǎng)絡(luò)中的每一條邊的傳輸符號(hào)均滿足 其中 16 網(wǎng)絡(luò)編碼的基本原理 線性網(wǎng)絡(luò)編碼的代數(shù)構(gòu)造定義矩陣和矩陣如下 則系統(tǒng)轉(zhuǎn)移矩陣為 是信源輸出到所有鏈路的轉(zhuǎn)移矩陣 是鏈路間的轉(zhuǎn)移矩陣 17 網(wǎng)絡(luò)編碼的基本原理 組播線性網(wǎng)絡(luò)編碼成功的條件組播通信網(wǎng)絡(luò)中 信源輸出向量 接收節(jié)點(diǎn)接收向量 其中 是接收節(jié)點(diǎn)的系統(tǒng)轉(zhuǎn)移矩陣 于是 為了由接收到的信息向量解出信源輸入 則必須要求系統(tǒng)轉(zhuǎn)移矩陣可逆 18 3 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 基于網(wǎng)絡(luò)編碼的差錯(cuò)控制是針對(duì)網(wǎng)絡(luò) 而非一條鏈路或一條路徑進(jìn)行操作的 通過合適的選擇信源空間 可以糾正傳輸網(wǎng)絡(luò)中幾條鏈路上發(fā)生的傳輸錯(cuò)誤 這是一個(gè)比較新的差錯(cuò)控制方式 稱之為基于網(wǎng)絡(luò)編碼的差錯(cuò)控制 19 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 參與多播傳輸?shù)逆溌窋?shù)用表示 組播網(wǎng)絡(luò)的網(wǎng)絡(luò)容量為比特 單位時(shí)間 20 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 如果從某條鏈路上輸出的符號(hào)不等于輸入的符號(hào) 那么稱發(fā)生錯(cuò)誤 如果在傳輸網(wǎng)絡(luò)中總共有條鏈路發(fā)生錯(cuò)誤 就稱為網(wǎng)絡(luò)發(fā)生了個(gè)錯(cuò)誤 如果一個(gè)基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼能糾正所有錯(cuò)誤個(gè)數(shù)小于等于的情況 就稱該碼是 差錯(cuò)控制碼 21 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 把發(fā)生在傳輸網(wǎng)絡(luò)上的錯(cuò)誤用一個(gè)維行向量表示 稱為錯(cuò)誤向量 如果其中有個(gè)分量不為零 則稱錯(cuò)誤向量重為 接收符號(hào) 網(wǎng)絡(luò)譯碼后 當(dāng)有錯(cuò)誤發(fā)生時(shí) 其中是的子矩陣 22 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 對(duì)于接收節(jié)點(diǎn) 定義t 錯(cuò)誤圖樣集合如下 對(duì)于接收節(jié)點(diǎn) 定義t 錯(cuò)誤圖樣的差分集合如下 讓 23 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 對(duì)于任意 和可分 即能糾任意重量小于等于t的錯(cuò)誤 當(dāng)且僅當(dāng) 如果存在和 滿足 則存在錯(cuò)誤圖樣和 使 即 則會(huì)出現(xiàn)和不可分的情況 24 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 對(duì)于一個(gè)線性網(wǎng)絡(luò)編碼 要使任意兩個(gè)信源向量和可分 當(dāng)且僅當(dāng) 25 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 如果能夠構(gòu)造一個(gè)奇偶校驗(yàn)矩陣 滿足對(duì)于所有的 有 那么讓 是維空間 則對(duì)于任意 和可分 關(guān)鍵問題 給定一個(gè)有限域 值能夠達(dá)到多大 26 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 矩陣的構(gòu)造 Varshamov算法 構(gòu)造過程 1 將劃分成多個(gè)子集合 其中對(duì)于必須滿足且向量的最后一個(gè)非零分量的位置是 27 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 2 令維列向量空間 是由的前列向量得到 即 28 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 從中任選一列作為 3 2 從中任選一列作為 i 從中任選一列作為 持續(xù)上面操作直到 因此得到矩陣 29 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 可成功構(gòu)造出的條件 對(duì)于線性網(wǎng)絡(luò)編碼 如果 則對(duì)任意有 30 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 可成功構(gòu)造出的條件 因?yàn)?31 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 可成功構(gòu)造出 即構(gòu)造出基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 可糾任何滿足的錯(cuò)誤 因此當(dāng)有限域大小滿足 32 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 根據(jù)上述構(gòu)造校驗(yàn)矩陣的方法 對(duì)于給定的有限域可得到的一個(gè)下界值 但此構(gòu)造方法復(fù)雜度過大 有待找出一種可行的方法 來構(gòu)造出達(dá)到該下界值的校驗(yàn)矩陣 的一個(gè)上界值 Hamming界 其中 33 易知 為使 根據(jù)下界值知就可以構(gòu)造出該糾錯(cuò)碼 需要計(jì)算的差分錯(cuò)誤圖樣的總個(gè)數(shù)有 基于網(wǎng)絡(luò)編碼的糾錯(cuò)碼 小規(guī)模網(wǎng)絡(luò)的糾錯(cuò)碼構(gòu)造 34 4 無線組播中的網(wǎng)絡(luò)編碼 無線組播特性 如果節(jié)點(diǎn)i向節(jié)點(diǎn)j和k發(fā)射相同的信息時(shí) 節(jié)點(diǎn)i上的發(fā)射功率 如果節(jié)點(diǎn)i向節(jié)點(diǎn)j和k發(fā)射不同的信息時(shí) i上的發(fā)射功率 35 無線組播中的網(wǎng)絡(luò)編碼 一個(gè)例子 傳統(tǒng)路由 36 無線組播中的網(wǎng)絡(luò)編碼 一個(gè)例子 利用網(wǎng)絡(luò)編碼來節(jié)省能量 37 無線組播中的網(wǎng)絡(luò)編碼 另一個(gè)例子 無線網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的信息互換 傳統(tǒng)方法 基于網(wǎng)絡(luò)編碼的方法 38 無線組播中的網(wǎng)絡(luò)編碼 利用無線組播特性降低能量消耗時(shí) 用到以下兩點(diǎn) 廣播特性 無線通信網(wǎng)絡(luò)固有的 節(jié)點(diǎn)的輸出邊上必須攜帶相同的信息 使用網(wǎng)絡(luò)編碼 39 無線組播中的網(wǎng)絡(luò)編碼 對(duì)于任何邊 這里的是非源節(jié)點(diǎn) 我們假定其上傳輸相同的信號(hào) 表示為 40 無線組播中的網(wǎng)絡(luò)編碼 類似的 接收節(jié)點(diǎn)輸出的隨機(jī)過程可表示為 41 無線組播中的網(wǎng)絡(luò)編碼 定理 由表征的無線組播網(wǎng)絡(luò)是可解的當(dāng)且僅當(dāng)對(duì)于所有的接收節(jié)點(diǎn)相應(yīng)的系統(tǒng)轉(zhuǎn)移矩陣的行列式在多項(xiàng)式環(huán)上非零 42 無線組播中的網(wǎng)絡(luò)編碼 基于無線組播特性的無線網(wǎng)絡(luò)編碼有以下特點(diǎn) 可以實(shí)現(xiàn)以網(wǎng)絡(luò)的最大流傳輸信息 這是網(wǎng)絡(luò)中容量的理論上限 可以降低無線網(wǎng)絡(luò)中的能量消耗 這對(duì)以電池為能源供給的無線網(wǎng)絡(luò)來說 是至關(guān)重要的 這種方法使系統(tǒng)轉(zhuǎn)移矩陣中的變量個(gè)數(shù)由指數(shù)級(jí)降為多項(xiàng)式級(jí) 從而大大降低了實(shí)現(xiàn)網(wǎng)絡(luò)編碼算法的復(fù)雜度 這種處理方法在降低網(wǎng)絡(luò)編碼實(shí)現(xiàn)算法復(fù)雜度的同時(shí) 并沒有增加網(wǎng)絡(luò)編碼字