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