網絡編碼--權威專家王新梅教授學術講座.ppt

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