太阳城集团

  • / 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://zh228.com/p-6420207.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');