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

《《隨機(jī)線性網(wǎng)絡(luò)編碼》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《隨機(jī)線性網(wǎng)絡(luò)編碼》PPT課件（23頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

6、tle 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ò)上 的 傳 輸 可 以 被 模 仿 成 原 來 循 環(huán) 網(wǎng)絡(luò) k個(gè) 時(shí) 隙 的 步 驟 。 這 種 情 況 我 們假 設(shè) 每 個(gè) 鏈 路 的 延 遲 是

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

8、( )邊 ie1ie邊 ie 1ieO( )ieie進(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 編 碼 模 型 符 號(hào) 簡 介 （ 2）)(v I定 義 為 所 有 以 節(jié) 點(diǎn) V為 結(jié) 束 點(diǎn) 的 邊的 集 合 veheadEevI )(:)(定 義 為 所 有 從 節(jié) 點(diǎn) V開 始 的 邊 的 集 合)(0 v vetailEev )(:)(0)(vI )(0 v 接 收 機(jī) 處

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

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

11、 的 。 Add your title in here 編 碼 模 型 GF( )域以 m=4為 例 ， 它 的 本 原 多 項(xiàng) 式 為 ,即 在 伽 羅 華 域 中 ， 加 法 等 于 對 應(yīng) 位 異 或先 給 出 推 導(dǎo) 過 程0 0000 10001 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) 生 。 在 伽 羅 華 域 中 ， 每 對 應(yīng) 一 個(gè) m， 會(huì) 有 一 個(gè) 相 應(yīng) 的 本 原 多 項(xiàng)式 ， 根 據(jù) 這 個(gè) 本 原 多 項(xiàng)

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

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

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

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

16、編 碼 部 分 或 所 有 的 編 碼 系 數(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ò) 編 碼 的 多

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

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

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