《隨機線性網(wǎng)絡編碼》PPT課件

《《隨機線性網(wǎng)絡編碼》PPT課件》由會員分享，可在線閱讀，更多相關《《隨機線性網(wǎng)絡編碼》PPT課件（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、編 碼 模 型方 案 舉 例 總 結 與 展 望overviewA Random Linear Network Coding Approach to Multicast 簡 要 介 紹 簡 要 介 紹最 大 流 最 小 截 定 理網(wǎng) 絡 容 量問 題 隨 機 分 布問 題滿 足 網(wǎng) 絡 容 量 要 求 多 源 （ 包括 相 關 源 ）多 徑 問 題一 般 組 播 網(wǎng) 絡 結 構 簡 要 介 紹對 于 除 了 信 宿 節(jié) 點 外 的 所 有 中 間 節(jié) 點 ， 只 要 在 一 個 足 夠 大 的 有 限域 上 隨 機 選 擇 它 們 輸 入 鏈 路 到 輸 出 鏈 路 的 映 射 ， 且 各 節(jié)

2、 點 映 射 關系 的 選 取 是 相 互 獨 立 的 ， 從 而 保 證 各 信 宿 能 以 較 高 概 率 成 功 譯 碼各 鏈 路 上 的 系 數(shù) 向 量 和 信 源 發(fā)送 的 信 息 進 行 同 步 傳 輸 ， 信 息在 通 過 編 碼 節(jié) 點 時 ， 系 數(shù) 向 量根 據(jù) 隨 機 選 取 的 映 射 關 系 進 行更 新 ， 最 終 信 宿 節(jié) 點 收 到 的 輸入 信 息 將 包 含 輸 入 鏈 路 對 應 的全 局 編 碼 向 量 和 信 源 發(fā) 送 的 信息 流 ， 然 后 采 用 高 斯 消 元 法 （ 解 線 性 方 程 組 ） 正 確 譯 碼 獲得 信 源 原 始 傳 輸

3、 的 信 息 簡 要 介 紹我 們 考 慮 的 問 題 怎 樣 構 建 隨 機 線 性 網(wǎng) 絡 編 碼 怎 樣 在 分 布 網(wǎng) 絡 中 有 效 的 將 信 息 傳 輸 到 接 收 節(jié) 點 編 碼 模 型 做 出 的 假 設 每 條 鏈 路 的 容 量 是 一 比 特 每 單 元 ， 如 果 某 條 邊 的 容 量 大 于 一 比 特每 單 位 時 間 ， 則 看 做 是 幾 條 并 行 的 邊 。 如 果 邊 的 容 量 不 是 整 數(shù) ， 則將 時 間 單 元 取 得 大 一 點 ， 使 得 小 數(shù) 部 分 可 以 近 似 成 整 數(shù) 。 假 設 每 條 鏈 路 的 延 遲 是 一 樣 的

4、。 對 于 線 性 相 關 源 ， 我 們 認 為 每 一 個 獨 立 信 源 的 熵 率 是 一 比 特 每 單位 時 間 ， 如 果 不 是 ， 則 將 它 們 變 成 一 些 并 行 的 熵 率 是 一 比 特 每 單 位時 間 的 源 的 集 合 。 對 于 任 意 相 關 源 ， 我 們 要 求 信 源 的 熵 是 整 數(shù) ， 并 且 有 著 任 意 的 聯(lián) 合 概 率 分 布 對 于 不 同 的 節(jié) 點 ， 它 們 要 處 理 的 隨 機 過 程 之 間 是 相 互 獨 立 的 ， 這個 假 設 符 合 通 信 網(wǎng) 絡 一 般 的 情 況 Add your title in her

5、e 編 碼 模 型多 信 源 的 Slepian Wolf定 理 ：有 r個 離 散 的 無 記 憶 信 息 源 ,它 們 是 隨 機 二 進 制 序 列 ，對 每 個 信 源 獨 立 進 行 編 碼 ， 再 進 行 聯(lián) 合 譯 碼 ， 其 性 能 跟 所 有 信 源聯(lián) 合 編 碼 是 一 致 的 。 只 要 滿 足 在 r個 信 源 中 任 取 k個 信 源 的 和 速 率 ，不 能 小 于 這 k個 信 源 以 剩 余 的 r-k個 信 源 為 條 件 的 熵 ， 而 對 于 總 的和 速 率 不 能 小 于 這 r個 信 源 的 聯(lián) 合 熵 。 rXXX , 21 Add your ti

6、tle in here 編 碼 模 型不 考 慮延 遲 考 慮延 遲考 慮 邊 容 量 為 1的 情 況 ，每 個 節(jié) 點 在 等 到 所 有進 入 此 節(jié) 點 的 信 息 后才 發(fā) 往 離 開 此 節(jié) 點 的出 邊 有 著 v個 節(jié) 點 和 信 息 傳 輸 速 率 是 r的循 環(huán) 網(wǎng) 絡 可 以 變 成 非 循 環(huán) 網(wǎng) 絡 ， 此網(wǎng) 絡 有 kv個 節(jié) 點 ， 信 息 傳 輸 速 率 大于 等 于 （ k-v） r,信 息 在 這 種 網(wǎng) 絡上 的 傳 輸 可 以 被 模 仿 成 原 來 循 環(huán) 網(wǎng)絡 k個 時 隙 的 步 驟 。 這 種 情 況 我 們假 設 每 個 鏈 路 的 延 遲 是

7、 一 樣 的 。 Add your title in here 編 碼 模 型 符 號 簡 介 （ 1）非 循 環(huán) 圖 G=（ V,E） 表 示 的網(wǎng) 絡 中 ， 每 條 邊 可 以 根 據(jù)網(wǎng) 絡 拓 撲 進 行 順 序 編 號 :如 ， 對 于 每 條 從屬 于 E的 邊 ， 它 的 源 表 示 為o( ),它 的 目 的 節(jié) 點 表 示為 d( )。 一 個 路 徑 就 是 一 系 列 的 鏈 路 集合 ， 對 任 意 的i j, 。Eeee, 21ie ie )()( 1 ii eoed )( ied )( jed 節(jié) 點 V 即 d( ) 既 稱 為 head（ ）又 稱 為 tail

8、( )邊 ie1ie邊 ie 1ieO( )ieie進 入 一 個 節(jié) 點 的 邊 數(shù) 稱 為 一 個 節(jié)點 的 入 度 ， 由 一 個 節(jié) 點 發(fā) 出 的 邊數(shù) 稱 為 節(jié) 點 的 出 度 ， 節(jié) 點 的 入 度和 出 度 的 和 稱 為 節(jié) 點 的 度 數(shù) Add your title in here 編 碼 模 型 符 號 簡 介 （ 2）)(v I定 義 為 所 有 以 節(jié) 點 V為 結 束 點 的 邊的 集 合 veheadEevI )(:)(定 義 為 所 有 從 節(jié) 點 V開 始 的 邊 的 集 合)(0 v vetailEev )(:)(0)(vI )(0 v 接 收 機 處

9、的 終 端 鏈 路 的 集 合 稱 為 )(,(,),2,(),1,()( vuvXvXvXv 是 在 節(jié) 點 v收 集 到 的u(v)個 離 散 隨 機 過 程在 邊 e上 傳 輸 的 隨 機 過 程 稱 為 Y(e) Add your title in here 編 碼 模 型如 圖 是 一 個 非 延 遲 網(wǎng) 絡 ， 對 于 鏈 路 e上 的 隨 機 處 理 過 程 滿 足對 于 匯 節(jié) 點 的 輸 出 Z是 由 屬 于 的 所 有 邊 上 的 隨 機 過 程 Y(e)形 成的 )(uI 這 里 的 ， ， 都是 從 伽 羅 華 域 中 隨 機選 擇 的 如 果 ， ， 是 獨立 的 ，

10、 則 系 統(tǒng) 是 時 不變 的 ， 否 則 系 統(tǒng) 是 時變 的 Add your title in here 編 碼 模 型 )(,(,),2,(),1,( vuvXvXvXx 表 示 在 源 節(jié)點 觀 察 到 的 輸 入 信 號 矢 量另 v 點 是 一 個 網(wǎng) 絡 的 匯 結 點 ， 我們 認 為 是這 個 節(jié) 點 的 輸 出 過 程 矢 量 )(,(,),2,(),1,( vvZvZvZz 另 M表 示 一 個 網(wǎng) 絡 的 傳 輸 矩 陣 ， 這樣 z=x*M,對 于 固 定 的 系 數(shù) ， ， ， 我 們 不 難 看 出 ， M矩 陣 里 的 數(shù)也 是 從 伽 羅 華 域 中 選 取

11、 的 。 Add your title in here 編 碼 模 型 GF( )域以 m=4為 例 ， 它 的 本 原 多 項 式 為 ,即 在 伽 羅 華 域 中 ， 加 法 等 于 對 應 位 異 或先 給 出 推 導 過 程0 0000 10001 0001 0011 1001 0010 0110 0001 0100 可 以 看 出 ， 當 m=4時 ， GF(4)是 一 個 包 含 15個 數(shù) 的 有 限 域 ，且 這 15個 數(shù) 循 環(huán) 產(chǎn) 生 。 在 伽 羅 華 域 中 ， 每 對 應 一 個 m， 會 有 一 個 相 應 的 本 原 多 項式 ， 根 據(jù) 這 個 本 原 多 項

12、 式 ， 就 可 以 推 出 域 里 面 的 值 。 m2 014 14 2 345 1415 Add your title in here 編 碼 模 型 傳 輸 矩 陣 可 以 表 示 為 Add your title in here 編 碼 模 型 矩 陣 A為 源 節(jié) 點 輸 入 信 息 與 邊 之 間 的 關系 矩 陣 ， 矩 陣 B為 接 收 節(jié) 點 對 接 收 到 的 數(shù)據(jù) 進 行 線 性 組 合 。 單 源 單 匯 的 節(jié) 點 的 信息 傳 輸 時 ， 只 要 相 應 的 轉 移 矩 陣 是 滿 秩的 ， 則 源 節(jié) 點 輸 出 的 信 息 在 接 收 端 就 可以 準 確 的

13、 恢 復 。 單 源 多 匯 的 節(jié) 點 的 信 息多 播 傳 輸 ， 利 用 網(wǎng) 絡 編 碼 時 ， 只 要 能 保證 各 個 目 的 節(jié) 點 對 應 的 網(wǎng) 絡 轉 移 矩 陣 是滿 秩 的 ， 則 目 的 節(jié) 點 就 可 以 準 確 的 恢 復出 原 始 發(fā) 送 的 信 息 。傳 輸 矩 陣 可 以 表 示 為 編 碼 模 型對 有 向 網(wǎng) 絡 來 說 ， 對 網(wǎng) 絡 節(jié) 點 進 行 排 序 ， 定 義 相 應 的 鄰 接 矩陣 F， F矩 陣 的 第 i行 第 j 列 元 素 表 示 網(wǎng) 絡 流 圖 中 第 i條 邊 與 第 j 條 邊 的 連 接 關 系 ， F可 表 示 為其 中

14、表 示 有 向 邊 的 終 點 與 有 向 邊 的 起 點 重合 ， 是 有 限 域 中 的 一 非 0 元 素 ， 則 M可 表 示 為 ： 這 種 編 碼 的 構 造 簡 單 而 且 有 效 ， 但 是 計 算 量 大 。 其 它,0 )()(, jieeji etaileheadF ji)()( ji etailehead ie jeji ee , TBFIAM 1)( 編 碼 模 型圖 中 節(jié) 點 v ， 接 收 到 編 碼 包 和 。 節(jié) 點 v 應 用 隨 機 網(wǎng) 絡 編 碼 的 思 想 ， 在 有 限 域 中 隨 機 選 取 系 數(shù) (1,2)， 并 對 接 收 到 的 兩 個

15、編 碼 包 進 行 運 算 ，得 到 新 的 編 碼 系 數(shù) (3,10,13)， 并 將 新 的 編 碼 包 發(fā) 送 。321 32 xxx 321 54 xxx )54(2)32(1 321321 xxxxxx 編 碼 模 型隨 機 網(wǎng) 絡 編 碼 中 中 間 節(jié) 點 只 需 要 對 接 收 到 的 數(shù) 據(jù) 進 行 線 性 組 合 ，而 不 需 要 判 斷 接 收 到 的 信 息 是 否 線 性 相 關 。 這 樣 在 接 收 節(jié) 點 處有 可 能 出 現(xiàn) 線 性 相 關 的 編 碼 信 息 導 致 解 碼 失 敗 。 對 于 任 意 一 個可 行 的 多 播 網(wǎng) 絡 ， 如 果 網(wǎng) 絡

16、編 碼 部 分 或 所 有 的 編 碼 系 數(shù) 都 是 獨立 的 均 勻 的 在 一 個 有 限 域 上 選 取 ， 則 所 有 的 目 的 節(jié) 點 能 夠 成功 進 行 解 碼 的 概 率 至 少 為 ， q d ， 其 中 d 表 示 目的 節(jié) 點 的 數(shù) 目 ， 為 隨 機 選 取 編 碼 系 數(shù) 的 鏈 路 數(shù) 目 ， q為 編 碼符 號 域 的 大 小 。 當 有 限 域 的 字 母 表 大 小 q 遠 大 于 接 收 節(jié) 點 數(shù) 目 d 時 ， 所 有 的 接 收 節(jié) 點 可 以 以 很 高 的 概 率 恢 復 出 原 始 信 息 。 采用 隨 機 線 性 網(wǎng) 絡 編 碼 的 多

17、播 網(wǎng) 絡 中 ， 多 個 源 節(jié) 點 可 以 相 互 獨 立 ，也 可 以 線 性 相 關 。 對 于 線 性 相 關 的 源 ， 隨 機 線 性 編 碼 起 到 了 信 息 壓 縮 的 作 用 。 qF )/1( qd 方 案 舉 例網(wǎng)絡的目的是每個節(jié)點都能收到信源發(fā)出的兩個隨機過程隨 機 流 結 構 (RF) 源 節(jié) 點 延 兩 個 軸 向 分 別 發(fā) 送 兩 個 信 息 只 接 收 到 一 個 信 息 過 程 的 節(jié) 點向 其 它 三 個 方 向 發(fā) 送 信 息 接 收 到 兩 個 信 息 過 程 的 節(jié) 點 分 別 向 對 應 的 軸 向 發(fā) 送 相 應 的 信 息 方 案 舉 例

18、隨 機 編 碼 結 構 (RC) 源 節(jié) 點 延 兩 個 軸 向 分 別 發(fā) 送 兩 個 信 息 只 接 收 到 一 個 信 息 過 程 的 節(jié) 點 向 其 它 三 個方 向 發(fā) 送 信 息 接 收 到 兩 個 信 息 過 程 的 節(jié) 點 向 其 余 的 軸 向發(fā) 送 接 收 到 的 信 息 的 線 性 組 合對 于 接 收 位 置 為 （ x,y） 的 點 ， 接 收機 能 接 收 到 兩 個 發(fā) 送 信 息 的 概 率 為RF RC （ q是 伽 羅 華 域 字 母 表 ）)2(2)/11( yxq 方 案 舉 例 RF方 案 和 RC方 案 在 不 同 點 成 功 解 調 的 概 率 可

19、 以 看 到 ， 當 網(wǎng) 絡 比 較 大 時 ， RF方 案 是 不 適 用 的 ； 對 于 RC，當 有 限 域 越 大 時 ， 能 成 功 解 調 的 概 率 越 大 總 結 與 展 望總結 分 布 式 隨 機 線 性 網(wǎng) 絡 編 碼 能 有 效 地 壓 縮相 關 源 。隨 機 線 性 網(wǎng) 絡 編 碼 無 須 了 解 網(wǎng) 絡 的 拓 撲情 況 ， 適 用 于 鏈 路 動 態(tài) 變 化 的 場 景 ， 具有 很 強 的 實 用 性 。有 限 域 的 值 越 大 時 ， 能 夠 成 功 解 碼 的 概 率 越 大 總 結 與 展 望展望 編 碼 系 數(shù) 可 以 在 非 均 勻 分 布 的 域 上 選取 ， 可 能 是 依 據(jù) 某 種 適 應 性 ， 使 得 網(wǎng)絡 滿 足 不 同 的 性 能隨 機 選 取 編 碼 系 數(shù) 的 性 質 ， 使 得 隨機 線 性 網(wǎng) 絡 編 碼 可 能 可 以 應 用 于 網(wǎng)絡 安 全對 于 不 同 的 通 信 需 求 ， 今 后 可 以 考 慮 一 些 關 于 隨 機 線 性 網(wǎng) 絡 編 碼 的 通信 協(xié) 議 ， 比 較 一 些 特 殊 的 編 碼 協(xié) 議和 路 由 協(xié) 議 的 性 能 的 不 同 L/O/G/O Thank You!