• / 17
  • 下載費用:30 金幣  

一種數據傳輸方法及網絡節點.pdf

摘要
申請專利號:

CN200910251379.2

申請日:

2009.12.03

公開號:

CN102088331B

公開日:

2015.01.14

當前法律狀態:

有效性:

法律詳情: 授權|||實質審查的生效IPC(主分類):H04L 1/00申請日:20091203|||公開
IPC分類號: H04L1/00; H04L12/70(2013.01)I; H04L29/08 主分類號: H04L1/00
申請人: 株式會社NTT都科摩
發明人: 王曉利; 張永生
地址: 日本東京都千代田區永田町2-11-1山王
優先權:
專利代理機構: 北京德琦知識產權代理有限公司 11018 代理人: 郭曼;王琦
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN200910251379.2

授權公告號:

102088331B||||||

法律狀態公告日:

2015.01.14|||2012.12.12|||2011.06.08

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開了一種數據傳輸方法以及網絡節點,一方面可以減小控制開銷,另一方面可以降低解碼失敗概率。本發明的方法包括:下載節點和種子節點分別生成網絡編碼系數表;下載節點分別向各個種子節點發送下載請求,所述下載請求包括請求待下載數據的標識以及網絡編碼系數標識;各個種子節點根據所接收下載請求中攜帶的編碼系數標識從自身生成的網絡編碼系數表中獲取相應的列向量作為網絡編碼系數;各個種子節點根據所獲取的網絡編碼系數對由下載請求中攜帶的數據標識所指示的數據中包含的數據單位進行網絡編碼,并將編碼后的數據單位發送給下載節點;下載節點分別接收來自各個種子節點的經過網絡編碼后的數據單位,通過解碼得到待下載數據。

權利要求書

1: 一種數據傳輸方法, 其特征在于, 包括 : 下載節點和種子節點分別生成網絡編碼系數表, 所述網絡編碼系數表中的任意 n 個列 向量之間是線性獨立的, 其中, n 表示由待傳輸數據劃分出的數據單位的數目 ; 下載節點從服務器獲知所有種子節點后, 分別向各個種子節點發送下載請求, 所述下 載請求包括請求待下載數據的標識以及網絡編碼系數標識 ; 各個種子節點根據所接收下載請求中攜帶的編碼系數標識從自身生成的網絡編碼系 數表中獲取相應的列向量作為網絡編碼系數 ; 各個種子節點根據所獲取的網絡編碼系數對由下載請求中攜帶的數據標識所指示的 數據中包含的數據單位進行網絡編碼, 并將編碼后的數據單位發送給下載節點 ; 下載節點分別接收來自各個種子節點的經過網絡編碼后的數據單位, 并在接收到 n 個 數據單位后進行解碼, 得到待下載數據。
2: 根據權利要求 1 所述的方法, 其特征在于, 所述下載節點和種子節點分別生成網絡 編碼系數表包括 : 下載節點和種子節點分別生成基數大于或等于 n 的矩陣作為所述網絡編碼系數表。
3: 根據權利要求 2 所述的方法, 其特征在于, 所述矩陣的基數為 2n。
4: 根據權利要求 1 所述的方法, 其特征在于, 所述下載節點和種子節點分別生成網絡 編碼系數表包括 : 所述下載節點和種子節點生成不同基數且基數大于或等于 n 的至少兩個矩陣, 并根據 n 大小選擇一個矩陣作為網絡編碼系數表。
5: 根據權利要求 4 所述的方法, 其特征在于, 所述下載節點和種子節點生成不同基數 且基數大于或等于 n 的至少兩個矩陣, 并根據 n 大小選擇一個矩陣作為網絡編碼系數表包 括: 所述下載節點和種子節點分別生成基數為 64, 128, 256, 512 的四個矩陣 ; 若待下載數據所包含的數據單位的數目小于或等于 32, 則選擇基數為 64 的矩陣作為 網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 32 且小于或等于 64, 則選擇基數為 128 矩 陣作為網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 64 且小于或等于 128, 則選擇基數為 256 矩陣作為網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 128 且小于或等于 256, 則選擇基數為 512 的矩陣作為網絡編碼系數表。
6: 根據權利要求 1 所述的方法, 其特征在于, 所述下載節點從服務器獲知所有種子節 點包括 : 下載節點通過向服務器發送請求種子節點列表消息向服務器請求所有可以提供數據 的種子節點的信息 ; 服務器在收到請求種子節點列表消息后, 將向下載節點返回包含有所有種子節點標識 的種子節點標識列表 ; 下載節點根據服務器返回的種子節點標識列表獲知所有提供數據的種子節點。
7: 根據權利要求 1 所述的方法, 其特征在于, 所述網絡編碼系數標識包括編碼系數模 2 值和編碼系數索引 ; 各個種子節點根據所接收下載請求中攜帶的編碼系數標識從自身生成的網絡編碼系 數表中獲取相應的列向量作為網絡編碼系數包括 : 各個種子節點根據如下計算公式計算得到所選擇的作為編碼系數的列向量在網絡編 碼系數表中的編號 : i = x×k+y, 其中, i 為網絡編碼系數表中列向量的編號 ; x 為編碼系數模值, y 為編碼 系數索引, k 為非負整數。
8: 根據權利要求 7 所述的方法, 其特征在于, 下載節點向各個種子節點發送的下載請 求中攜帶的編碼系數模值是相同的, 而編碼系數索引是不同的。
9: 根據權利要求 1 所述的方法, 其特征在于, 所述下載節點分別接收來自各個種子節 點的經過網絡編碼后的數據單位, 并在接收到 n 個數據單位后進行解碼包括 : 下載節點根據發送給各個種子節點的下載請求中攜帶的網絡編碼系數標識從自身生 成的網絡編碼系數表中獲取相應的列向量作為各個種子節點的編碼系數, 再根據各個種子 節點的編碼系數分別對來自各個種子節點的 n 個數據單位數進行解碼。
10: 根據權利要求 9 所述的方法, 其特征在于, 所述網絡編碼系數標識包括編碼系數模 值和編碼系數索引 ; 下載節點根據發送給各個種子節點的下載請求中攜帶的網絡編碼系數標識從自身生 成的網絡編碼系數表中獲取相應的列向量作為各個種子節點的編碼系數包括 : 下載節點根據如下計算公式分別計算各個種子節點所選擇的作為編碼系數的列向量 在網絡編碼系數表中的編號 : i = x×k+y, 其中, i 為網絡編碼系數表中列向量的編號 ; x 和 y 分別為一個種子編碼系 數模值和編碼系數索引, k 為非負整數。
11: 根據權利要求 1 至 10 任一項所述的方法, 其特征在于, 所述數據為一個文件 ; 所述 數據單位為所述文件被劃分得到的至少一個信息片段。
12: 根據權利要求 1 至 10 任一項所述的方法, 所述數據是一個文件被劃分得到的多個 信息片段中的一個 ; 所述數據單位為該數據片段包含的至少一個數據塊。
13: 一種網絡節點, 其特征在于, 包括 : 網絡編碼系數表生成單元, 用于生成網絡編碼系數表, 其中, 網絡編碼系數表中的任意 n 列均是線性獨立的, 其中, n 表示由待傳輸數據劃分的數據單位的數目 ; 種子節點信息獲取單元, 用于從服務器獲取所有提供數據的種子節點 ; 下載請求生成單元, 用于分別對各個種子節點生成下請求, 并將下載請求發送至相應 種子節點, 其中, 下載請求至少包括請求待下載數據的標識以及網絡編碼系數標識 ; 編碼系數生成單元, 用于分別針對各個種子節點根據所生成的下載請求中的網絡編碼 系數標識從自身生成的網絡編碼系數表中獲取相應的列向量作為各個種子節點的網絡編 碼系數 ; 數據接收及解碼單元, 用于從各個種子節點接收經過網絡編碼后的數據單位, 并在接 收到 n 個數據單位后根據各個節點的網絡編碼系數進行解碼, 得到待下載數據。
14: 根據權利要求 13 所述的網絡節點, 其特征在于, 所述網絡編碼系數表生成單元包 括: 3 網絡編碼系數矩陣生成模塊, 用于生成具有不同基數且基數大于或等于 n 的至少一個 矩陣 ; 網絡編碼系數表選擇模塊, 用于根據 n 的大小從所生成的至少一個根據矩陣中選擇一 個作為網絡編碼系數表。
15: 一種網絡節點, 其特征在于, 包括 : 網絡編碼系數表生成單元, 用于生成網絡編碼系數表, 其中, 網絡編碼系數表中的任意 n 列均是線性獨立的, 其中, n 表示由待傳輸數據劃分的數據單位的數目 ; 下載請求接收單元, 用于接收來自下載節點的下載請求 ; 編碼系數生成單元, 用于根據所接收下載請求中攜帶的網絡編碼系數標識從自身生成 的網絡編碼系數表中獲取相應的列向量作為網絡編碼系數 ; 網絡編碼單元, 用于根據所獲取的網絡編碼系數對自身存儲的, 由下載請求中攜帶的 數據標識所指示的數據中包含的數據單位進行網絡編碼, 并將編碼后的數據單位發送給下 載節點。
16: 根據權利要求 15 所述的網絡節點, 其特征在于, 所述網絡編碼系數表生成單元包 括: 網絡編碼系數矩陣生成模塊, 用于生成具有不同基數且基數大于或等于 n 的至少一個 矩陣 ; 網絡編碼系數表選擇模塊, 用于根據 n 的大小從所生成的至少一個根據矩陣中選擇一 個作為網絡編碼系數表。

說明書


一種數據傳輸方法及網絡節點

    【技術領域】
     本發明涉及網絡編碼技術, 特別涉及一種基于網絡編碼的數據傳輸方法及網絡節點。 背景技術 網絡編碼技術是在網絡層對數據分組進行編碼的技術, 該技術允許網絡中的節點 對接收到的分組進行編碼, 產生新的分組并轉發出去。 目前, 網絡編碼技術的應用主要集中 在大規模的文件發布, 即源節點或服務器發布大量的信息給網絡中其它節點的業務, 例如, 點對點 (P2P) 文件傳輸業務或 P2P 流業務等等。
     圖 1 給出了一個網絡編碼的簡單實例。在大規模文件發布的應用中, 由于源 節點要發布的文件太大, 而傳輸帶寬有限, 在傳輸文件之前, 源節點首先會把原文件劃 分成 n 個原始信息片段 (Segment)S1, S2, S3, ..., Sn, 再對這 n 個原始信息片段進行線性 編碼生成新的信息片段 E1, E2, ..., 并攜帶其對應的系數在網絡中轉發。因此, Ei 都是 原始信息片段 S1, S2, S3, ..., Sn 的線性組合, 其長度和原始信息片段相同, 區別在于每
     個 Ei 都攜帶了部分或所有原始信息片段的信息。圖 1 中,是從伽羅瓦域中隨機選出的系數, 分別與原始信息片段 S1, S2, S3, ..., Sn 相乘再相加后得到 E1, 即 E2 的生成方式類似。 在本例中, 當網絡節 點 A 從文件發布的源節點處接收到新的信息片段 E1 及其對應的系數之后, 就會給網絡中其 它網絡節點廣播或多播新信息片段。由于網絡節點 A 的緩存中已經保留了信息片段 E2, 網 絡節點 A 將會將信息片段 E1 和信息片段 E2 進行線性編碼, 在得到新的信息片段 E3 后廣播 或多播出去。其中, 網絡節點 A 生成信息片段 E3 的過程如下 : 網絡節點 A 從伽羅瓦域隨機 選擇系數 c 1 和 c2, 然后分別與 E1 和 E2 相乘再相加得到 E3。由于 E1, E2 都是原始信息片 S2, S3, ..., Sn 的線性編碼, 那么 E3 也是這 n 個原始信息片段的線性編碼。需要說明 段 S1, 的是, 網絡節點 A 在廣播或多播新片段 E3 的同時也將把 E3 對應的系數 和 廣播或多 播出去。網絡中的每個網絡節點接收到新的信息片段之后都進行類似的處理, 那么每個網 絡節點只要接收到 n 個不相關的信息片段及其對應的系數, 就能夠恢復出原文件。
     本領域的技術人員可以理解, 在不采用網絡編碼的情況下, 有的原始信息片段 ( 例如一個文件的開始部分 ) 在網絡上可能已經被很多網絡節點擁有了, 也就是具有較高 的流行度 ; 而有些原始信息片段 ( 比如一個文件的結尾部分 ) 則可能在網絡上非常稀缺, 也 就是具有較低的流行度, 此時網絡節點需要根據自身已收到的信息片段判斷先接收哪個信 息片段, 例如為了避免擁有稀缺資源的網絡節點動態離開造成文件下載失敗, 網絡節點通 常選擇先下載流行度較低的原始信息片段。而采用了網絡編碼之后, 由于在網絡中傳播的 信息片段均是原始信息片段的線性組合, 因此所有信息片段具有相同的流行度, 此時網絡 節點無需判斷需要先接收哪個信息片段, 同時, 也不存在稀缺資源的問題, 這樣, 網絡節點 的動態加入和離開, 對其他網絡節點的影響也將會降低。
     由于在上述方法中, 網絡節點必須等到收到足夠多的經過網絡編碼的信息片段之后, 才能開始解碼, 以得到整個文件, 因此, 上述方法不適用于需要一邊下載一遍觀看的 P2P 流業務。為此, 還提出了一種適用于 P2P 流業務的網絡編碼方法。
     在該方法中, 每個信息片段被進一步劃分成若干個信息塊 (block), 參與 P2P 流業 務的種子節點 (Seed) 在轉發數據之前, 首先在一個信息片段內的信息塊之間進行網絡編 碼。這樣, 下載節點 (Peer) 在接收到足夠多經過網絡編碼的信息塊后即可解碼得到信息片 段。這種在信息片段內的信息塊之間進行網絡編碼的方法, 可以支持多個種子節點同時給 一個下載節點發送某個信息片段, 從而縮短傳送某個信息片段的時間, 以減少下載節點用 戶等待觀看的時間。
     然而, 在上述兩種方法中, 無論是信息片段還是信息塊的編碼系數都是隨機選擇 即隨機生成的 ( 這類方法被稱為隨機網絡編碼 ), 而且為了讓下載節點能夠解碼, 生成的 編碼系數必須和信息片段或信息塊一起傳送, 因此具有比較高的控制開銷 (COH, Control Overhead)。通常, 上述方法中的控制開銷的大小可以通過如下公式 (1) 計算得到 :
     其中, q 表示有限域 (GF) 的大小, n 表示一個文件被劃分的信息片段的數目或一個 信息片段中的信息塊的數目。 例如, 如果 GF 的大小是 256, 且一個信息片段中包含 128 個信 息塊, 那么發送一個信息片段需要的控制開銷將達到 16.384Kbytes。
     另外, 由于隨機網絡編碼的編碼系數是隨機生成的, 無法百分之百保證所生成編 碼系數之間是線性獨立的, 因此, 即使下載節點已收到 n 個信息片段或信息塊也不一定可 以正確解碼, 即存在解碼失敗的情況。上述網絡編碼方法的解碼失敗概率可以通過下面的 公式 (2) 計算 :
     其中, q 表示有限域 (GF) 的大小, n 表示一個一個文件被劃分的信息片段的數目或 一個信息片段中的信息塊的數目。從公式 (2) 可以看出, 有限域的大小是解碼失敗概率的 決定性因素, 例如, 當有限域大小取 128 時, 解碼失敗概率在 10-2 量級上。
     發明內容
     為了解決上述技術問題, 本發明提供了一種數據傳輸方法以及網絡節點, 一方面 可以減小控制開銷, 另一方面可以降低解碼失敗概率。
     本發明實施例所述的數據傳輸方法, 包括 :
     下載節點和種子節點分別生成網絡編碼系數表, 所述網絡編碼系數表中的任意 n 個列向量之間是線性獨立的, 其中, n 表示由待傳輸數據劃分出的數據單位的數目 ;
     下載節點從服務器獲知所有種子節點后, 分別向各個種子節點發送下載請求, 所 述下載請求包括請求待下載數據的標識以及網絡編碼系數標識 ;
     各個種子節點根據所接收下載請求中攜帶的編碼系數標識從自身生成的網絡編 碼系數表中獲取相應的列向量作為網絡編碼系數 ;
     各個種子節點根據所獲取的網絡編碼系數對由下載請求中攜帶的數據標識所指 示的數據中包含的數據單位進行網絡編碼, 并將編碼后的數據單位發送給下載節點 ;
     下載節點分別接收來自各個種子節點的經過網絡編碼后的數據單位, 并在接收到n 個數據單位后進行解碼, 得到待下載數據。
     其中, 上述下載節點和種子節點分別生成網絡編碼系數表包括 : 下載節點和種子 節點分別生成基數大于或等于 n 的矩陣作為所述網絡編碼系數表。較佳地, 矩陣的基數為 2n。本說明書中, 給出了一個生成基數大于等于 n 的矩陣的例子, 即構造范德蒙德矩陣。
     上述下載節點和種子節點分別生成網絡編碼系數表包括 : 所述下載節點和種子節 點生成不同基數且基數大于或等于 n 的至少兩個矩陣, 并根據 n 大小選擇一個矩陣作為網 絡編碼系數表。
     具體可以包括 : 所述下載節點和種子節點分別生成基數為 64, 128, 256, 512 的四 個矩陣 ; 若待下載數據所包含的數據單位的數目小于或等于 32, 則選擇基數為 64 的矩陣作 為網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 32 且小于或等于 64, 則選 擇基數為 128 矩陣作為網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 64 且 小于或等于 128, 則選擇基數為 256 矩陣作為網絡編碼系數表 ; 若待下載數據所包含的數據 單位的數目大于 128 且小于或等于 256, 則選擇基數為 512 的矩陣作為網絡編碼系數表。
     上述下載節點從服務器獲知所有種子節點包括 : 下載節點通過向服務器發送請求 種子節點列表消息向服務器請求所有可以提供數據的種子節點的信息 ; 服務器在收到請求 種子節點列表消息后, 將向下載節點返回包含有所有種子節點標識的種子節點標識列表 ; 下載節點根據服務器返回的種子節點標識列表獲知所有提供數據的種子節點。 上述網絡編碼系數標識包括編碼系數模值和編碼系數索引 ; 各個種子節點根據所 接收下載請求中攜帶的編碼系數標識從自身生成的網絡編碼系數表中獲取相應的列向量 作為網絡編碼系數包括 : 各個種子節點根據如下計算公式計算得到所選擇的作為編碼系數 的列向量在網絡編碼系數表中的編號 : i = x×k+y, 其中, i 為網絡編碼系數表中列向量的 編號 ; x 為編碼系數模值, y 為編碼系數索引, k 為非負整數。
     其中, 下載節點向各個種子節點發送的下載請求中攜帶的編碼系數模值是相同 的, 而編碼系數索引是不同的。
     上述下載節點分別接收來自各個種子節點的經過網絡編碼后的數據單位, 并在接 收到 n 個數據單位后進行解碼包括 : 下載節點根據發送給各個種子節點的下載請求中攜帶 的網絡編碼系數標識從自身生成的網絡編碼系數表中獲取相應的列向量作為各個種子節 點的編碼系數, 再根據各個種子節點的編碼系數分別對來自各個種子節點的 n 個數據單位 數進行解碼。
     上述網絡編碼系數標識包括編碼系數模值和編碼系數索引 ; 下載節點根據發送給 各個種子節點的下載請求中攜帶的網絡編碼系數標識從自身生成的網絡編碼系數表中獲 取相應的列向量作為各個種子節點的編碼系數包括 : 下載節點根據如下計算公式分別計算 各個種子節點所選擇的作為編碼系數的列向量在網絡編碼系數表中的編號 : i = x×k+y, 其中, i 為網絡編碼系數表中列向量的編號 ; x 和 y 分別為一個種子編碼系數模值和編碼系 數索引, k 為非負整數。
     上述數據為一個文件 ; 所述數據單位為所述文件被劃分得到的至少一個信息片 段。或者上述數據是一個文件被劃分得到的多個信息片段中的一個 ; 所述數據單位為該數 據片段包含的至少一個數據塊。
     本發明實施例提供的一種網絡節點, 包括 :
     網絡編碼系數表生成單元, 用于生成網絡編碼系數表, 其中, 網絡編碼系數表中的 任意 n 列均是線性獨立的, 其中, n 表示由待傳輸數據劃分的數據單位的數目 ;
     種子節點信息獲取單元, 用于從服務器獲取所有提供數據的種子節點 ;
     下載請求生成單元, 用于分別對各個種子節點生成下請求, 并將下載請求發送至 相應種子節點, 其中, 下載請求至少包括請求待下載數據的標識以及網絡編碼系數標識 ;
     編碼系數生成單元, 用于分別針對各個種子節點根據所生成的下載請求中的網絡 編碼系數標識從自身生成的網絡編碼系數表中獲取相應的列向量作為各個種子節點的網 絡編碼系數 ;
     數據接收及解碼單元, 用于從各個種子節點接收經過網絡編碼后的數據單位, 并 在接收到 n 個數據單位后根據各個節點的網絡編碼系數進行解碼, 得到待下載數據。
     其中, 上述網絡編碼系數表生成單元包括 :
     網絡編碼系數矩陣生成模塊, 用于生成具有不同基數且基數大于或等于 n 的至少 一個矩陣 ;
     網絡編碼系數表選擇模塊, 用于根據 n 的大小從所生成的至少一個根據矩陣中選 擇一個作為網絡編碼系數表。 本發明實施例提供的另一種網絡節點, 包括 :
     網絡編碼系數表生成單元, 用于生成網絡編碼系數表, 其中, 網絡編碼系數表中的 任意 n 列均是線性獨立的, 其中, n 表示由待傳輸數據劃分的數據單位的數目 ;
     下載請求接收單元, 用于接收來自下載節點的下載請求 ;
     編碼系數生成單元, 用于根據所接收下載請求中攜帶的網絡編碼系數標識從自身 生成的網絡編碼系數表中獲取相應的列向量作為網絡編碼系數 ;
     網絡編碼單元, 用于根據所獲取的網絡編碼系數對自身存儲的, 由下載請求中攜 帶的數據標識所指示數據中包含的數據單位進行網絡編碼, 并將編碼后的數據單位發送給 下載節點。
     其中, 上述網絡編碼系數表生成單元包括 :
     網絡編碼系數矩陣生成模塊, 用于生成具有不同基數且基數大于或等于 n 的至少 一個矩陣 ;
     網絡編碼系數表選擇模塊, 用于根據 n 的大小從所生成的至少一個根據矩陣中選 擇一個作為網絡編碼系數表。
     在上述數據傳輸的過程中, 各個種子節點根據下載節點發送的下載請求中攜帶的 編碼系數模值和編碼系數索引選擇編碼系數, 而不是隨機選擇, 因此, 各個種子節點在向下 載節點發送經過網絡編碼后的數據單位時無需向下載節點上報編碼系數, 從而可以大大降 低上述數據傳輸過程的控制開銷。
     另外, 由于各個網絡節點生成的網絡編碼系數表中任意的 n 個列向量之間均是線 性獨立的, 因此, 經過網絡編碼后的數據單位也是線性獨立的。這樣, 下載節點物理無論從 哪些種子節點接收數據, 只要正確接收到 n 個數據單位即可成功進行解碼得到待傳輸的數 據。
     附圖說明 下面將通過參照附圖詳細描述本發明的示例性實施例, 使本領域的普通技術人員 更清楚本發明的上述及其它特征和優點, 附圖中 :
     圖 1 為一種網絡編碼簡單實例的示意圖 ;
     圖 2 為根據本發明實施例的基于網絡編碼的數據傳輸方法的流程圖 ;
     圖 3 為網絡編碼系數表以及各個種子節點選擇網絡編碼系數的示意圖 ;
     圖 4 顯示了作為下載節點的網絡節點的內部結構 ;
     圖 5 顯示了作為種子節點的網絡節點的內部結構 ;
     圖 6 顯示了采用本發明實施例所述方法以及現有隨機網絡編碼方法時控制開銷 隨每個信息片段所包含信息塊數目變化的曲線 ;
     圖 7 顯示了采用本發明實施例所述方法以及現有隨機網絡編碼方法時控制開銷 隨待下載文件所包含信息片段數目變化的曲線。
     具體實施方式
     為了解決上述問題, 本發明的實施例提出了一種基于網絡編碼的數據傳輸方法, 如圖 2 所示, 主要包括如下步驟 :
     步驟 101 : 網絡中的各個網絡節點分別生成網絡編碼系數表 (Network Coding Table)。
     在這里, 上述各個節點包括用于提供數據的種子節點和需要下載數據的下載節點。
     上述網絡編碼系數表用于限定網絡編碼系數的范圍, 各個節點將選擇網絡編碼系 數表的至少一個列向量作為待傳輸數據的編碼系數。需要說明的是, 為了使不同網絡節點 發送的經過網絡編碼的數據之間沒有冗余, 各個網絡節點所生成的網絡編碼系數表需要滿 足以下條件 : 網絡編碼系數表中的任意 n 個列向量之間是線性獨立的, 其中, n 表示由待傳 輸數據劃分出的數據單位的數目, 也即需要進行網絡編碼的數據單位的數目, 例如 P2P 文 件傳輸業務中待下載文件被劃分的信息片段的數目或者 P2P 流業務中每個信息片段內包 含的信息塊的數目等。
     在上述方法應用到 P2P 的應用中時, 每個網絡節點 ( 包括用于提供數據的種子節 點和需要下載數據的下載節點 ) 在安裝 P2P 應用軟件的時候, 就可以同時生成網絡編碼系 數表。
     步驟 102 : 下載節點 (Peer) 從服務器 (Tracker) 獲知所有種子節點 (Seed) 后, 分 別向各個種子節點發送下載請求, 該下載請求至少包括請求待下載數據的標識以及網絡編 碼系數標識。
     具體而言, 在本步驟中, 下載節點首先通過向服務器發送請求種子節點列表消息 向服務器請求所有可以提供數據的種子節點的信息 ; 服務器在收到請求種子節點列表消息 后, 將向下載節點返回包含有所有種子節點標識的種子節點標識列表 ; 下載節點根據服務 器返回的種子節點標識列表獲知所有提供數據的種子節點。
     在本步驟中, 所述的待下載數據可以是一個文件或通過劃分一個文件得到的多個 信息片段中的一個。
     另外, 在本步驟中, 下載請求中包括的網絡編碼系數標識用于指示一個種子節點進行網絡編碼時所使用的編碼系數在網絡編碼系數表中的位置。較佳地, 網絡編碼系數標 識可以包括編碼系數模值和編碼系數索引, 此時, 各個種子節點所選擇的作為編碼系數的 列向量的編號 i 可以按照如下計算公式計算得到 i = x×k+y, 其中, x 為編碼系數模值, y 為編碼系數索引, k 為非負整數 ( 包括 0 和正整數 )。為了保證各個種子節點所選擇的編碼 系數不同, 較佳地, 下載節點向各個種子節點發送的下載請求中攜帶的編碼系數模值是相 同的, 而編碼系數索引是不同的。
     步驟 103 : 各個種子節點根據所接收下載請求中攜帶的編碼系數標識從自身生成 的網絡編碼系數表中獲取相應的列向量作為網絡編碼系數。
     如前所述, 在本步驟中, 若網絡編碼系數標識包括編碼系數模值和編碼系數索引, 則各個種子節點按照如下計算公式計算得到自身的網絡編碼系數向量 : i = x×k+y, 其中, x 為編碼系數模值, y 為編碼系數索引, k 為非負整數 ( 包括 0 和正整數 )。
     步驟 104 : 各個種子節點根據所獲取的網絡編碼系數對由下載請求中攜帶的數據 標識所指示的數據中包含的數據單位進行網絡編碼, 并將編碼后的數據單位發送給下載節 點。
     在本步驟中, 若上述數據是一個文件, 則上述數據單位是該文件被劃分得到的至 少一個信息片段 ; 若上述數據是一個文件被劃分得到的多個信息片段中的一個, 則上述數 據單位為該數據片段包含的至少一個數據塊。 步驟 105 : 下載節點分別接收來自各個種子節點的經過網絡編碼后的數據單位, 并在接收到 n 個數據單位后進行解碼, 得到待下載數據。
     在本步驟中, 下載節點也首先根據發送給各個種子節點的下載請求中攜帶的網絡 編碼系數標識從自身生成的網絡編碼系數表中獲取相應的列向量作為各個種子節點的編 碼系數, 然后再根據各個種子節點的編碼系數分別對來自各個種子節點的數據單位進行解 碼從而得到待下載的數據。具體而言, 若網絡編碼系數標識包括編碼系數模值和編碼系數 索引, 則下載節點將根據如下計算公式分別計算各個種子節點所選擇的作為編碼系數的列 向量在網絡編碼系數表中的編號 : i = x×k+y, 其中, i 為網絡編碼系數表中列向量的編號 ; x 和 y 分別為一個種子編碼系數模值和編碼系數索引, k 為非負整數。
     可以看出, 上述方法使用的編碼系數既不是隨機生成的, 也不是預先固定好的, 因 此上述方法中使用的網絡編碼方法又可稱為半靜態網絡編碼。
     在上述數據傳輸的過程中, 各個種子節點根據下載節點發送的下載請求中攜帶的 編碼系數模值和編碼系數索引選擇編碼系數, 而不是隨機選擇, 因此, 各個種子節點在向下 載節點發送經過網絡編碼后的數據單位 ( 信息片段或信息塊 ) 時無需向下載節點上報編碼 系數, 從而可以大大降低上述數據傳輸過程的控制開銷。
     另外, 由于各個網絡節點生成的網絡編碼系數表中任意的 n 個列向量之間均是線 性獨立的, 因此, 經過網絡編碼后的數據單位 ( 信息片段或信息塊 ) 也是線性獨立的。 這樣, 下載節點物理無論從哪些種子節點接收數據, 只要正確接收到 n 個數據單位 ( 信息片段或 信息塊 ) 即可成功進行解碼得到待傳輸的數據。
     下面將結合具體的示例詳細描述網絡編碼系數表的生成方法。
     如前所述, 為了使不同種子節點發送的經過網絡編碼的數據之間沒有冗余, 網絡 編碼系數表需要滿足 : 網絡編碼系數表中的任意 n 個列向量之間均是線性獨立的, 其中, n
     表示待傳輸數據所包含的數據單位的數據, 例如, 一個文件所包含的信息片段的數目或者 一個信息片段所包含的信息塊數目。通常, 一個信息片段所包含的信息塊的數目在 32-256 之間, 因此, 可以假設 32 ≤ n ≤ 256。網絡編碼系數表可以采用如下公式 (3) 所示矩陣 A 的 形式。
     如前所述, 如果矩陣 A 中任意 n 列均是線性獨立的, 即矩陣 A 的基數為 n, 那么以矩 陣 A 中的列向量作為編碼系數得到的數據單位 ( 信息片段或信息塊 ) 之間將不會包含冗余 信息。此時, 下載節點不管從哪個種子節點接收數據, 只要正確收到 n 個數據單位之后, 就 必然可以成功解碼, 得到原始數據。也就是說只要保證矩陣 A 的基數 (cardinality) 至少 為 n, 就可以大幅降低解碼失敗概率。較佳地, 考慮到網絡節點的動態離開以及鏈路差錯等 因素, A 的基數應當設置為大于 n, 較佳地, 可以設定為 2n, 例如, 當 n 為 256 時, 可以設置 A 的基數為 512。
     經過數學分析可以得到, 保證 A 的基數為 n 的充分條件是有限域 (GF) 的大小為 n。 在本說明書中, 我們給出一個例子來構造基數為 n 的矩陣 A。
     范德蒙德矩陣是一個具有典型特征的矩陣形式, 它可以由下面的公式 (4) 表示,
     該矩陣滿足如下性質 :也就是說, 只要 αi ≠ αj, 當有限域 (GF) 大小為 n 時, 由范德蒙德矩陣構成的 A 就能夠滿足基數為 n, 即任意 n 列線性獨立。
     在實際的應用中, 可以根據待下載數據所包含數據單位的數目確定有限域的大 小, 即矩陣 A 的基數, 再由矩陣構成滿足任意 n 個列向量之間線性獨立的條件的矩陣 A。具 體來講, 各個網絡節點可以分別生成基數大于或等于 n 的矩陣作為上述網絡編碼系數表。 下面通過一個示例詳細說明本發明的實施例。圖 3 為網絡編碼系數表以及各個種 子節點選擇網絡編碼系數的示意圖。
     首先, 網絡中的各個網絡節點生成如圖 3 所示的網絡編碼系數表。在一個 Peer 下載某個數據的時候, 首先根據服務器反饋的 Seed 標識列表選擇合適的種子節點, 包括 Seed1、 Seed2、 Seed3 以及 Seed4, 然后分別為每個 Seed 選擇編碼系數模值 Mod 和編碼系數 為 Seed2 選擇的 Mod 為 8, Index 為 索引 Index, 例如, 為 Seed1 選擇的 Mod 為 8, Index 為 1 ; 2; 為 Seed3 選擇的 Mod 為 8, Index 為 3 以及為 Seed4 選擇的 Mod 為 8, Index 為 4。然后, Peer 將選擇的編碼系數模值和編碼系數索引發送至相應的種子節點。此后, Seed1、 Seed2、 Seed3 以及 Seed4 可以根據這兩個信息分別選擇編碼系數, 再對一個文件的信息片段或一
     個信息片段所包含的信息塊進行編碼。例如, Seed1 將在網絡編碼系數表中選擇其編號模 8 為 1 的列向量作為編碼系數 ( 如第 1, 9, 17... 列 ) ; Seed2 將在網絡編碼系數表中選擇其 編號模 8 為 2 的列向量作為編碼系數 ( 如第 2, 10, 18... 列 ) ; Seed3 將在網絡編碼系數表 中選擇其編號模 8 為 3 的列向量作為編碼系數 ( 如第 3, 11, 19... 列 ) 以及 Seed4 將在網 絡編碼系數表中選擇其編號模 8 為 4 的列向量作為編碼系數 ( 如第 4, 12, 20... 列 )。通過 上述準則選擇編碼系數, 就可以保證每個 seed 不會使用相同的編碼系數, 且每個 Seed 所使 用的編碼系數是線性獨立的。
     為了盡可能減少網絡節點的運算量, 進一步優化上述方法性能, 可以根據待下載 數據所包含的數據單位的數目調整網絡編碼系數矩陣的基數, 也即有限 (GF) 的大小, 進一 步動態調整所生成的網絡編碼系數表的大小。例如, 若待下載數據所包含的數據單位若較 少, 則可以生成基數較小的矩陣作為網絡編碼系數表。 在實際應用中, 網絡節點可以預先生 成不同基數且基數大于或等于 n 的多個矩陣作為備選的網絡編碼系數表, 并根據待下載數 據所包含的數據單位的數目從所有備選的網絡編碼系數表中選擇一個適合的網絡編碼系 數表。然后, 再根據所選擇的網絡編碼系數表得到編碼系數。例如, 網絡中的各個節點分別 生成了基數為 64, 128, 256, 512 的四個矩陣, 唯一的不同的是這四個矩陣的有限域的大小 分別為 GF(64), GF(128), GF(256) 以及 GF(512)。在種子節點收到來自下載節點的下載請 求后, 若待下載數據所包含的數據單位的數目小于或等于 32, 則選擇基數為 64 的矩陣作為 網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 32 且小于或等于 64, 則選擇 基數為 128 的矩陣作為網絡編碼系數表 ; 若待下載數據所包含的數據單位的數目大于 64 且 小于或等于 128, 則選擇基數為 256 的矩陣作為網絡編碼系數表 ; 且若待下載數據所包含的 數據單位的數目大于 128 且小于或等于 256, 則選擇基數為 512 的矩陣作為網絡編碼系數 表。 本領域的技術人員可以理解, 上述方法中, 在待下載數據所包含的數據單位的數目較少 時可以進一步降低網絡節點的運算量, 達到優化網絡節點性能的目的。
     除了上述方法之外, 本發明還提供了作為下載節點的網絡節點以及作為種子節點 的網絡節點的內部結構。
     其中, 圖 4 顯示了作為下載節點的網絡節點的內部結構。如圖 4 所示, --- 該網絡 節點主要包括 :
     網絡編碼系數表生成單元, 用于生成網絡編碼系數表, 其中, 網絡編碼系數表中的 任意 n 列均是線性獨立的, 其中, n 表示由待傳輸數據劃分的數據單位的數目 ;
     種子節點信息獲取單元, 用于從服務器獲取所有提供數據的種子節點 ;
     下載請求生成單元, 用于分別對各個種子節點生成下請求, 并將下載請求發送至 相應種子節點, 其中, 下載請求至少包括請求待下載數據的標識以及網絡編碼系數標識 ;
     編碼系數生成單元, 用于分別針對各個種子節點根據所生成的下載請求中的網絡 編碼系數標識從自身生成的網絡編碼系數表中獲取相應的列向量作為各個種子節點的網 絡編碼系數 ;
     數據接收及解碼單元, 用于從各個種子節點接收經過網絡編碼后的數據單位, 并 在接收到 n 個數據單位后根據各個節點的網絡編碼系數進行解碼, 得到待下載數據。
     更進一步, 上述網絡編碼系數表生成單元可以包括 :
     網絡編碼系數矩陣生成模塊, 用于生成具有不同基數且基數大于或等于 n 的至少一個矩陣 ;
     網絡編碼系數表選擇模塊, 用于根據 n 的大小從所生成的至少一個根據矩陣中選 擇一個作為網絡編碼系數表。
     圖 5 顯示了作為種子節點的網絡節點的內部結構。如圖 5 所示, 該網絡節點主要 包括 :
     網絡編碼系數表生成單元, 用于生成網絡編碼系數表, 其中, 網絡編碼系數表中的 任意 n 列均是線性獨立的, 其中, n 表示由待傳輸數據劃分的數據單位的數目 ;
     下載請求接收單元, 用于接收來自下載節點的下載請求 ;
     編碼系數生成單元, 用于根據所接收下載請求中攜帶的網絡編碼系數標識從自身 生成的網絡編碼系數表中獲取相應的列向量作為網絡編碼系數 ;
     網絡編碼單元, 用于根據所獲取的網絡編碼系數對自身存儲的, 由下載請求中攜 帶的數據標識所指示數據中包含的數據單位進行網絡編碼, 并將編碼后的數據單位發送給 下載節點。
     更進一步, 上述網絡編碼系數表生成單元也可以包括 :
     網絡編碼系數矩陣生成模塊, 用于生成具有不同基數且基數大于或等于 n 的至少 一個矩陣 ;
     網絡編碼系數表選擇模塊, 用于根據 n 的大小從所生成的至少一個根據矩陣中選 擇一個作為網絡編碼系數表。
     下面通過仿真對本發明所述方法以及現有的隨機網絡編碼方法進行比較。假設 網絡中網絡節點的數目為 250, 待下載文件包含 50-200 個信息片段, 每個信息片段包含 32-256 個信息塊。 應用 P2P 流業務時觀看視頻文件每個網絡節點需要緩沖 20 個信息片段。 服務器最多允許接入 8 個下載節點, 每個網絡節點最多允許接入 4 個下載節點, 每個網絡節 點最多允許成為 4 個下載節點的種子節點。在上述情況下, 圖 6 顯示了采用本發明實施例 所述方法以及現有隨機網絡編碼方法時控制開銷隨每個信息片段所包含信息塊數目變化 的曲線。圖 7 顯示了采用本發明實施例所述方法以及現有隨機網絡編碼方法時控制開銷隨 待下載文件所包含信息片段數目變化的曲線。在圖 6 和圖 7 中, 帶方形的曲線為采用本發 明實施例所述方法時控制開銷的變化曲線, 而帶圓形的曲線為采用現有隨機網絡編碼時控 制開銷的變化曲線。 從上述曲線可以看出, 與現有隨機網絡編碼方案相比, 本發明實施例所 述的方法大大降低了控制開銷。例如, 在隨機網絡編碼方案中, 控制包的開銷在 10%左右, 采用了我們的方案, 控制包的開銷不到 0.1%。
     而且, 如前所述, 由于本發明實施例所生成的網絡編碼系數表的任意 n 列均是線 性獨立的, 因此, 下載節點不管從哪個種子節點接收數據, 只要正確收到 n 個數據單位之 后, 就必然可以成功解碼, 得到原始數據, 從而大幅降低解碼失敗概率。
     以上所述僅為本發明的較佳實施例而已, 并不用以限制本發明, 凡在本發明的精 神和原則之內, 所作的任何修改、 等同替換、 改進等, 均應包含在本發明的保護范圍之內。

關 鍵 詞:
一種 數據傳輸 方法 網絡 節點
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種數據傳輸方法及網絡節點.pdf
鏈接地址:http://www.rgyfuv.icu/p-6420207.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图