分级网络编码数据传输方法
蒲保兴1, 陈继业1
1
(邵阳学院 激光与信息研究所, 湖南 邵阳，422001)
2
（中南大学 信息科学与工程学院，湖南 长沙，410083）
E-mail ：[email protected]
摘要:为提高网络编码数据传输的吞吐率, 减少编码的运算代价, 提出了一种分级网络编码数据传输策略, 首先分析了网络基于组播通信的网络编码技术所要求的伽罗华给出了适合网络编码的伽罗华域代数运算方法，在此基础上，对网络编码的运算延迟进行了分析并提出了估算网络编码运算延迟的数学模型和求解方法。分析表明，当单源组播网络的宿点个数较多时，网络编码运算延迟将成为不可忽略的因素。据此，提出了分级网络编码方法，在连接子网的节点处解出信息，并以该点为源点把解出的信息采用线性网络编码方法组播至子网，形成了分级网络编码传输。与传统的单级网络编码传输相比，它可以使用较低阶的伽罗华域的阶，有效地减少了运算延迟，并能充分利用网络容量。理论分析和仿真结果表明了提出的方法是有效的。 关键字：组播；网络编码; 伽罗华域; 运算延迟; 分级编码方法
Abstract ：This paper presents algebrioc operation approach of finite field for network coding ，based on which this paper anasized computing ralay and proposes a mathematical model and realize approach for .Analys shows that computer relay of network coding will be a neleage factor when the number of sink nodes of multicast is relatively larger .Acorddingly ,This paper proposes an 分级网络编码方法院,which is that in .
Key words： multicast; random network coding; extended Vandermonde matrix; the probability of unsuccessful multicast transmission ；maximal linear independent class of vectors
1 引言
网络编码是通信领域的一种新型数据传输方式，与传统的路由传输，其特点在于网络节点不仅能进行信息转发和复制，还可以进行信息编码。通过网络编码可以获得组播的“最大流界”，而采用传统的路由方式在大多数情况下无法达到这一极限。文献[1]首次提出了网络编码的概念，文献[2]提出了线性网络编码技术，文献[3]提出了线性网络编码的代数框架。由于线性网络编码技术具有方法简单的特点，其理论和应用得到了深入地研究[4-8]，以至于凡提及网络编码一词均代表线性网络编码。
网络编码是在伽罗华域上实现编码与解码运算。文献[4]证明了：若宿点的个数为d ，采用线性网络编码技术进行数据传输，则所需的伽罗华域的阶q>d(即伽罗华域的字符个数必须大于宿点的个数) 。文献[9]研究了线性网络编码的运算代价，研究表明, 网络的运算延迟与有限域的次的平方成正比，随着所采用的伽罗华域阶的增大，则节点编码和解码的运算代价增大。而在网络编码的数据传输中，节点的编码与解码的运算代价是不可忽略的。
已有的文献均采用单级网络编码方法, 其特点是在中间节点进行编码传输或路由传输，而仅在宿点处进行解码。这一特点不仅不能充分利用网络的传输容量，而且由于宿点个数较多，要求采用的伽罗华域的阶较大，, 这一特点限制了组播网络的容量, 由于个编码体系中宿点的个数较多, 从而要求所采用的伽罗华域的次较大, 在实际的网络中, , 当组播网络的宿点个数较多且网络规模较大时, 当组播网络的宿点较多且网络规模较大时，因使用的伽罗华域的阶[9]较大，而且信
息流经的节点较多，则网络编码运算延迟将增加, 不仅影响了数据传输速度, 而且影响了从源点至宿点的接收信息的延迟增加, ；针对这个问题，本文提出了分级网络编码方法，其策略是：若组播网络中存在父-子网结构，在子网与父网的连接节点对信息进行解码，并把解出的信息采用网络编码传输技术组播至子网。理论分析和仿真结果表明，与单级网络编码方法相比，分级网络编码方法可以采用较低阶的伽罗华域，有效地减少了运算延迟，并能更充分地利用网络的容量。
2 相关工作
文献[1]指出,
3 分级网络编码方法
说明了网络编码宜采用低阶有限域才能减少编码的运算延时。但文献[5，6，7]说明了无论是确定性网络编码方法还是随机网络编码方法，一般情况下均要求所采用的伽罗华域的阶大于节点的个数，从而必须满足下述条件：
+1
m log d 2 (19)
式(9)中m 为所采用的伽罗华域的次，d 为宿点的个数。因此减少宿点的个数是减少降低m 的唯一办法。在实际应用中。网络一般具有分级结构，即主干网下面有若干子网，子网络又可以由子网组成，若子网通过一个接入点w 与父网连接，则该点既可以作为父网的宿点，又可以作为子网的源点。
分级网络编码方法就是在子网的接入点处进行二次编码，主要目标是减少宿点的个数，当网络中某一节点连接一个子网时，可以作为该子网的宿点，从而该点既是父网的宿点又是子网的源点，在该节点处把信息全部解出，再采用网
收稿日期: 基金项目：湖南省教育厅重点科研项目(11A111)。
作者简介：蒲保兴，男，1965年生，副教授，博士，研究方向为网络编码、进化计算。
络编码的方法组播到子网的每一宿点。设全网的宿点个数为d , 设子网的宿点个数为d 1（d 1
定理1：若满足在d 1>1，则采用分级编码方法可以采用较低阶的有阶域，从而减少网络编码的运算延迟。
证明：若采用单级网络编码方法，由于宿点的个数为d, 则所需的伽罗华域的阶为q>d,当采用分级网络编码方法时，因d11，则父网的节点数为d-d1+1
定理2：采用分级编码法的最大组播率不会低于采用单级编码的最大组播率。
证明：设采用单级网络编码的方法的最大组播率为h ，设所有的宿点构成的集合为T={t1,t 2, …,t |T|}，由文献[2]，, 则有以下等式成立。
h =min t {maxflow(s,t i )} (20)
i ∈T
不妨设t 1,..,t k 为子网的宿点，由于子网是由w 点接入，从而
有1≤i ≤k , maxflow(s,
t i ) ≤maxflow(s,w) , 令父网的最大流-最小割为h 1，则h 1≥h ，设子网的最大流-最小割为h 2, 则h 2≥h 。证毕
定理2说明了可以在父网和子网分别以组播率h 组播数据，还可以在父网和子网分别以h 1 和h 2的组播率传输数据。这时当h 1>h2时，若w 有充分的存贮空间，可以采用存贮转发的方法，若h 1>h2，则可以在w 处插播附加的信息。从而充分在利用了网络的信道容量。
4 仿真测试
以下给出一个组播实例，其中s 为源点，1,2,...,34为中间节点，t 1,t 2, …,t 11为宿点，要求从源点s 组播信息至每一宿点，采用Ford-Fulkerson 算法[10]
用容易求出最大组播率为
4, 且要求的伽罗华域的次为4，现采用分级网络编码方法，
把它分成以下5个网络。
图1 组播网络拓扑
主干网：{s，1，2，…,10,t 1,11|,子网1：{10，12,13, …,t 2,16,t 3} 子网2；{11，24，25，…,t 4,28,t 5},子网3：{16，17，…,t6,t7,t8} 子网4：{28，29，30，…,t 9,t 10,t 11}。
以下采用两种方法模拟，得到结果如表1所示。
表1 两种方法的比较
从而可以看出，每一子网的宿点数均为3，从而可以采用的伽罗华域的次的最小值为2。若采用分级网络编码结构，各子网的最大组播率如下：
主干网：7；子网1：7；子网2：4：子网3：4；子网4：8；子网3：5。
若子网的源点具有存贮转发的功能，则主干网以组播率发送字符，则t1，10，11可以以传输速率7接收数据，其中10，11再采用网络编码进行转发，
5 结束语
本文首先给出了适合网络编码的伽罗华域的代数运算方法，在此基础上，给出了估计网络编码运算延时的数据模型和求解方法，分析表明，若宿点较多，则网络编码的运算延时将成为不可忽略的因素。据此，提出了分级网络编码方法，与单级网络编码方法相比，该方法不仅有效地减少的网络编码的运算延时，还能充分地利用网络容量，提高网络安
全性的特点，仿真结果表明了方法的有效性。 参考文献：
[1] Elias P，Feinstein A，Shannon C. A note on the maximum flow through a network[J]. IEEE Transactions on Information Theory,1956,2(4):117-119.
[2] Ahlswede R,Cai N,Li S R,et al..Network information flow [J].IEEE Trans on Information Theory,2000,46(4):1204-1216. [3] Li S-Y R,Yeung R W,Cai N.Linear network coding.IEEE Trans Info Theory,2003,49(2):371-381.
[4] Koetter R,Medard M.An algebraoc approach network coding[J].IEEE/ACM 11(5):782-795.
[5] Jaggi s,Sanders p,Chou A et al..Polynomial time algorithms for multicast network code construction[J].IEEE Trans on Info Theroy,2005:51(6):1973-1982.
[6] Langberg M,Sprintson A,Bruck J.The encoding complexity of
network
coding[J].IEEE
Trans
on
Info
Theory,2006:52(6):2386-2397.
[7] Ho T,Medard M,Koetter R,et al.. A random linear network coding approach to multicast[J]. IEEE Trans. Inform. Theory,2006,52(10):4413-4430.
[8] Cai N,Yeung R W. Network error correction, part II: Lower bounds[J]. Commun. Inform. Syst,2006,6(1):37-54.
[9] 蒲保兴，王伟平. 线性网络编码运算代价的估算与分析[J].通信学报，2011，32(5):47-55.
[9] Fragouli C,Soljanin E.Information flow decomposition for network
coding[J].IEEE
Trans.
on
Information
Theory ,2006,51(4):1295-1312.
[10] Wang Beng-shan. Discrete Mathematics[M]. Changsha: National University of Defence Technology Press, 2004 (in Chinese):263-281. 附中文参考文献：
[10] 王兵山. 离散数学[M].长沙：国防科技大学出版社，2004:263-281.
作者通讯地址:422001 湖南邵阳学院 信息与电气工程系 电话:0739-5432505
E-mail:[email protected]
Trans
on
Networking,
2003，
分级网络编码数据传输方法
蒲保兴1, 陈继业1
1
(邵阳学院 激光与信息研究所, 湖南 邵阳，422001)
2
（中南大学 信息科学与工程学院，湖南 长沙，410083）
E-mail ：[email protected]
摘要:为提高网络编码数据传输的吞吐率, 减少编码的运算代价, 提出了一种分级网络编码数据传输策略, 首先分析了网络基于组播通信的网络编码技术所要求的伽罗华给出了适合网络编码的伽罗华域代数运算方法，在此基础上，对网络编码的运算延迟进行了分析并提出了估算网络编码运算延迟的数学模型和求解方法。分析表明，当单源组播网络的宿点个数较多时，网络编码运算延迟将成为不可忽略的因素。据此，提出了分级网络编码方法，在连接子网的节点处解出信息，并以该点为源点把解出的信息采用线性网络编码方法组播至子网，形成了分级网络编码传输。与传统的单级网络编码传输相比，它可以使用较低阶的伽罗华域的阶，有效地减少了运算延迟，并能充分利用网络容量。理论分析和仿真结果表明了提出的方法是有效的。 关键字：组播；网络编码; 伽罗华域; 运算延迟; 分级编码方法
Abstract ：This paper presents algebrioc operation approach of finite field for network coding ，based on which this paper anasized computing ralay and proposes a mathematical model and realize approach for .Analys shows that computer relay of network coding will be a neleage factor when the number of sink nodes of multicast is relatively larger .Acorddingly ,This paper proposes an 分级网络编码方法院,which is that in .
Key words： multicast; random network coding; extended Vandermonde matrix; the probability of unsuccessful multicast transmission ；maximal linear independent class of vectors
1 引言
网络编码是通信领域的一种新型数据传输方式，与传统的路由传输，其特点在于网络节点不仅能进行信息转发和复制，还可以进行信息编码。通过网络编码可以获得组播的“最大流界”，而采用传统的路由方式在大多数情况下无法达到这一极限。文献[1]首次提出了网络编码的概念，文献[2]提出了线性网络编码技术，文献[3]提出了线性网络编码的代数框架。由于线性网络编码技术具有方法简单的特点，其理论和应用得到了深入地研究[4-8]，以至于凡提及网络编码一词均代表线性网络编码。
网络编码是在伽罗华域上实现编码与解码运算。文献[4]证明了：若宿点的个数为d ，采用线性网络编码技术进行数据传输，则所需的伽罗华域的阶q>d(即伽罗华域的字符个数必须大于宿点的个数) 。文献[9]研究了线性网络编码的运算代价，研究表明, 网络的运算延迟与有限域的次的平方成正比，随着所采用的伽罗华域阶的增大，则节点编码和解码的运算代价增大。而在网络编码的数据传输中，节点的编码与解码的运算代价是不可忽略的。
已有的文献均采用单级网络编码方法, 其特点是在中间节点进行编码传输或路由传输，而仅在宿点处进行解码。这一特点不仅不能充分利用网络的传输容量，而且由于宿点个数较多，要求采用的伽罗华域的阶较大，, 这一特点限制了组播网络的容量, 由于个编码体系中宿点的个数较多, 从而要求所采用的伽罗华域的次较大, 在实际的网络中, , 当组播网络的宿点个数较多且网络规模较大时, 当组播网络的宿点较多且网络规模较大时，因使用的伽罗华域的阶[9]较大，而且信
息流经的节点较多，则网络编码运算延迟将增加, 不仅影响了数据传输速度, 而且影响了从源点至宿点的接收信息的延迟增加, ；针对这个问题，本文提出了分级网络编码方法，其策略是：若组播网络中存在父-子网结构，在子网与父网的连接节点对信息进行解码，并把解出的信息采用网络编码传输技术组播至子网。理论分析和仿真结果表明，与单级网络编码方法相比，分级网络编码方法可以采用较低阶的伽罗华域，有效地减少了运算延迟，并能更充分地利用网络的容量。
2 相关工作
文献[1]指出,
3 分级网络编码方法
说明了网络编码宜采用低阶有限域才能减少编码的运算延时。但文献[5，6，7]说明了无论是确定性网络编码方法还是随机网络编码方法，一般情况下均要求所采用的伽罗华域的阶大于节点的个数，从而必须满足下述条件：
+1
m log d 2 (19)
式(9)中m 为所采用的伽罗华域的次，d 为宿点的个数。因此减少宿点的个数是减少降低m 的唯一办法。在实际应用中。网络一般具有分级结构，即主干网下面有若干子网，子网络又可以由子网组成，若子网通过一个接入点w 与父网连接，则该点既可以作为父网的宿点，又可以作为子网的源点。
分级网络编码方法就是在子网的接入点处进行二次编码，主要目标是减少宿点的个数，当网络中某一节点连接一个子网时，可以作为该子网的宿点，从而该点既是父网的宿点又是子网的源点，在该节点处把信息全部解出，再采用网
收稿日期: 基金项目：湖南省教育厅重点科研项目(11A111)。
作者简介：蒲保兴，男，1965年生，副教授，博士，研究方向为网络编码、进化计算。
络编码的方法组播到子网的每一宿点。设全网的宿点个数为d , 设子网的宿点个数为d 1（d 1
定理1：若满足在d 1>1，则采用分级编码方法可以采用较低阶的有阶域，从而减少网络编码的运算延迟。
证明：若采用单级网络编码方法，由于宿点的个数为d, 则所需的伽罗华域的阶为q>d,当采用分级网络编码方法时，因d11，则父网的节点数为d-d1+1
定理2：采用分级编码法的最大组播率不会低于采用单级编码的最大组播率。
证明：设采用单级网络编码的方法的最大组播率为h ，设所有的宿点构成的集合为T={t1,t 2, …,t |T|}，由文献[2]，, 则有以下等式成立。
h =min t {maxflow(s,t i )} (20)
i ∈T
不妨设t 1,..,t k 为子网的宿点，由于子网是由w 点接入，从而
有1≤i ≤k , maxflow(s,
t i ) ≤maxflow(s,w) , 令父网的最大流-最小割为h 1，则h 1≥h ，设子网的最大流-最小割为h 2, 则h 2≥h 。证毕
定理2说明了可以在父网和子网分别以组播率h 组播数据，还可以在父网和子网分别以h 1 和h 2的组播率传输数据。这时当h 1>h2时，若w 有充分的存贮空间，可以采用存贮转发的方法，若h 1>h2，则可以在w 处插播附加的信息。从而充分在利用了网络的信道容量。
4 仿真测试
以下给出一个组播实例，其中s 为源点，1,2,...,34为中间节点，t 1,t 2, …,t 11为宿点，要求从源点s 组播信息至每一宿点，采用Ford-Fulkerson 算法[10]
用容易求出最大组播率为
4, 且要求的伽罗华域的次为4，现采用分级网络编码方法，
把它分成以下5个网络。
图1 组播网络拓扑
主干网：{s，1，2，…,10,t 1,11|,子网1：{10，12,13, …,t 2,16,t 3} 子网2；{11，24，25，…,t 4,28,t 5},子网3：{16，17，…,t6,t7,t8} 子网4：{28，29，30，…,t 9,t 10,t 11}。
以下采用两种方法模拟，得到结果如表1所示。
表1 两种方法的比较
从而可以看出，每一子网的宿点数均为3，从而可以采用的伽罗华域的次的最小值为2。若采用分级网络编码结构，各子网的最大组播率如下：
主干网：7；子网1：7；子网2：4：子网3：4；子网4：8；子网3：5。
若子网的源点具有存贮转发的功能，则主干网以组播率发送字符，则t1，10，11可以以传输速率7接收数据，其中10，11再采用网络编码进行转发，
5 结束语
本文首先给出了适合网络编码的伽罗华域的代数运算方法，在此基础上，给出了估计网络编码运算延时的数据模型和求解方法，分析表明，若宿点较多，则网络编码的运算延时将成为不可忽略的因素。据此，提出了分级网络编码方法，与单级网络编码方法相比，该方法不仅有效地减少的网络编码的运算延时，还能充分地利用网络容量，提高网络安
全性的特点，仿真结果表明了方法的有效性。 参考文献：
[1] Elias P，Feinstein A，Shannon C. A note on the maximum flow through a network[J]. IEEE Transactions on Information Theory,1956,2(4):117-119.
[2] Ahlswede R,Cai N,Li S R,et al..Network information flow [J].IEEE Trans on Information Theory,2000,46(4):1204-1216. [3] Li S-Y R,Yeung R W,Cai N.Linear network coding.IEEE Trans Info Theory,2003,49(2):371-381.
[4] Koetter R,Medard M.An algebraoc approach network coding[J].IEEE/ACM 11(5):782-795.
[5] Jaggi s,Sanders p,Chou A et al..Polynomial time algorithms for multicast network code construction[J].IEEE Trans on Info Theroy,2005:51(6):1973-1982.
[6] Langberg M,Sprintson A,Bruck J.The encoding complexity of
network
coding[J].IEEE
Trans
on
Info
Theory,2006:52(6):2386-2397.
[7] Ho T,Medard M,Koetter R,et al.. A random linear network coding approach to multicast[J]. IEEE Trans. Inform. Theory,2006,52(10):4413-4430.
[8] Cai N,Yeung R W. Network error correction, part II: Lower bounds[J]. Commun. Inform. Syst,2006,6(1):37-54.
[9] 蒲保兴，王伟平. 线性网络编码运算代价的估算与分析[J].通信学报，2011，32(5):47-55.
[9] Fragouli C,Soljanin E.Information flow decomposition for network
coding[J].IEEE
Trans.
on
Information
Theory ,2006,51(4):1295-1312.
[10] Wang Beng-shan. Discrete Mathematics[M]. Changsha: National University of Defence Technology Press, 2004 (in Chinese):263-281. 附中文参考文献：
[10] 王兵山. 离散数学[M].长沙：国防科技大学出版社，2004:263-281.
作者通讯地址:422001 湖南邵阳学院 信息与电气工程系 电话:0739-5432505
E-mail:[email protected]
Trans
on
Networking,
2003，