论文部分内容阅读
摘 要： 描述了网络编码的研究现状和存在的问题，通过分析线性网络编码技术的编码和译码原理证明了网络编码的可行性，并基于线性代数理论论证了线性网络编码的最基本性质-线性多播性。提出网络编码技术是一门“混合”的技术，未来网络编码技术将结合计算机网络技术，信息论和编码技术，密码学理论等不断发展和深入。
关键词： 网络编码； 可行性； 线性多播性； 混合
中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2012）12-01-02
Research on network coding based on linear network coding technology
Li Ni， Yang Wangdong， Chen Qiang
（Department of Information Science and Engineering， Hunan City College， Yiyang， Hunan 413000， China）
Abstract： The status of the network coding research and the existing problems are described. The feasibility of network coding is proven through the analysis of linear network coding technology coding and decoding principle. The most basic property of the linear network coding-linear multicast property is demonstrated based on theory of linear algebra. Finally， the network coding technology is put forward as a "hybrid" technology. The network coding technology development will be combined with the computer network technology， information theory， coding technology and cryptography theory.
Key words： network coding； feasibility； linear multicast property； hybrid
0 引言
今天的互联网信息就像高速路上的汽车或管道中的水流一样被传输着，日益增长的网络带宽需求和不可靠网络的QOS需求，已成为制约网络发展的瓶颈。为扩大网络覆盖范围和提高系统容量，采用网络编码技术实现网络的最大流传输，已被国际学术界认定为解决网络问题的重要手段，并成为网络理论研究的热点问题之一。
1 网络编码研究现状和存在的问题
上个世纪50年代香农就提出：通信网络端对端的最大信息流是由网络有向图的最小分割决定的，但传统路由器的存储转发模式难以达到最大流最小分割定理的上界。2000年，香港中文大学R.Ahlswdee等人在发表的论文Network Information Flow中首次提出了网络编码[9]，并根据信息论严格证明了网络编码允许中间节点对接收到的信息进行编码并转发，接收节点通过相应的解码获得原始信息，这样可以达到通信网络的容量上界，从而最大限度利用网络资源。网络编码的提出从本质上打破了通信网络中传统的信息处理方式，是通信网络研究中一个重要的里程碑事件。近年來，网络编码理论的研究已取得重要发展，同时在应用基础和工程实践方面的研究也正在全方面展开。2003年，SYR.Li等人证明了使用线性网络编码已经能足够达到网络多播容量。Koetter R等人提出了网络编码的代数框架，并证明了存在满足多播流量的线性不变编码。这两位学者的工作为网络编码的发展准备了必要的理论条件。随机网络编码是由Ho T、Medard等人在2003年提出的，它的提出拓宽了网络编码的适用场景，使得网络编码不再局限于确定的网络拓扑和集中式算法。Cai Ning利用分布式网络编码来纠正网络中的差错，并论述了网络编码在安全方面的应用，为网络编码增加了新的应用领域。国外多所著名大学如麻省理工学院、多伦多大学、瑞士EPFL学院等，以及多家知名IT研究机构包括微软研究院、贝尔实验室等，都在积极开展网络编码理论和应用的研究，而国内针对编码的研究尚处于起步阶段。
目前，网络编码的理论研究尚处于初步阶段，实际应用也远未挖掘出其真正潜力，还有大量的难题有待解决。①即便网络编码可以提高通过率，能使问题得到有效解决，但是要确定存在合适的边函数却是件不容易的事情。还存在网络什么时候传输的边函数有用，有多少信息需要通过这种方式传送等问题。②在许多实际的网络中，并不一定是有向或无环的。对于有环网络构造的编码是时变的，这在实际中很少应用。并没有证明有环网中最佳时不变码的存在。③多源网络编码构造问题。④目前许多的有效编码算法都只限于应用到组播的情况，缺少一般性。⑤网络安全与网络管理的应用。
2 网络编码技术概述
网络编码的概念源于2000年Ahlswede R，Cai N，SYR.Li，R.W.Yeung发表的论文《Network Information Flow》，其最初的思想即允许网络的中间节点参与编译码。网络编码采用存储-编译码-转发的方式，可达到网络的多播容量[6]。网络编码的实质：①信息流被压缩或被编码；②网络编码是通过计算（编码）提升吞吐量。（网络吞吐量：是指在没有帧丢失的情况下，设备能够接受的最大速率。吞吐量的单位以比特/秒或字节/秒表示。） 网络编码理论也称为网络信息流理论，属于网络信息论的重要分支。经典信息论的编码通常是信源编码和信道编码，而网络编码与其有本质上的不同。网络编码除考虑信源和信宿节点的编码外，中间节点也参与编码，并且网络编码能从整体上提高网络吞吐量，提升通信系统的有效性。
网络编码理论指出网络信息流可以被压缩，从而进一步提升网络吞吐量。并且信息流仍然满足守恒定理，虽然信息内容被处理，但处理前后信息是不增也不减的。
其中，线性网络编码是研究较早，也是较为成熟的一类。有向无环网络中的网络编码称为线性网络编码。蒲保兴等详细分析了线性网络编码的计算时延与关键参量之间的关系[5]。
3 线性网络编码的编码译码原理及其可行性
线性网络编码中的核心是确定两个重要参数，即局部编码矩阵和全局编码向量。
定义1 线性网络编码的局部编码矩阵[8]
有向无环网络中，已知F为有限域（具有有限个元素的域），s（向量矩阵维数）为正数。对于任何节点T，其线性网络编码的局部编码矩阵为：
KT=[kd，e]d∈In（T），e∈Out（T）
式中，In（T）是节点T所有输入链路的集合，Out（T）为节点T所有输出链路的集合，|In（T）|表示节点T输入链路的个数，|Out（T）|表示节点T输出链路的个数。KT矩阵是维数等于|In（T）|×|Out（T）|的矩阵。kd，e表示节点T的每个相邻链路对（d，e）的局部编码标量，取值于有限域F。
对于信源节点由于没有输入链路，一般假设产生s维信号的信源节点存在s条输入链路，由于这s条链路实际并不存在，所以称为虚拟链路。
定义2 线性网络编码的全局编码向量
式中，fd为输入链路d的全局编码向量，fe称为输出链路e的全局编码向量。全局编码的是维数等于s*1的列向量，标记网络输入信号量为s。该迭代公式的初始条件是信源节点的s维虚拟链路的全局编码向量，它是从向量空间上选择的一个s维的标准基。
定义3 线性网络编码中全局编码向量与链路上传输信息的关系
me=x·fe
式中，x为信源节点产生的所有信息行向量，维数为1*s。fe为链路e上的全局编码向量，me为链路e上传输的信息。通过线性编码后每条链路上传输的是关于输入信号的线性表达量。
定义4 线性多播的译码矩阵D
[fe]e∈In（T）·D=Is
式中，maxflow（T）是针对任何满足maxflow（T）≥s的节点T，[fe]e∈In（T）为节点T所有输入链路的全局编码向量并列放置一起所组成的矩阵，Is为s×s维的单位矩阵。
将节点T收到的所有消息（可用消息矩阵x·[fe]e∈In（T）表示）乘以译码矩阵D，即可译码出信源节点S所发出的信息。
线性网络编码的编码和译码原理，其基本思想是，编码时，根据每个节点的每个相邻链路对的局部编码标量，得到每个节点的局部编码矩阵。将局部编码标量和局部编码矩阵的线性组合，得到关于每条链路的全局编码向量。于是得到通过编码后每条链路的实际传输信息。译码时，由定义4得到译码矩阵D，将信宿节点收到的所有消息乘以D，即可译码出信源节点所发出的所有信息。
可见，线性编码的基本思路简洁，当局部编码矩阵确定后，可以惟一确定全局编码向量，并可通过译码矩阵得到其信源信息，并易于在网络通信中实现，保证了在网络中信息的安全，提高了吞吐量，由此网络编码是可行的。
4 网络编码的线性多播性质
在向量空间的一组元素，如果其中没有向量可表示成有限个其他向量的线性组合，则称为線性无关，反之称为线性相关。
有向无环网络中，对于任何非信源节点T，输入链路为n，均存在由其所有输入链路d的全局编码向量fS*1集合组成的向量空间vs*n。若n≥s，则vs*n秩的最大值为s。已知全局编码向量均是从s个标准基的线性组合的，所以，向量空间vs*n的每个列向量均是s个标准基的线性组合，所以vs*n的秩为s。
在有向无环网络中，对于非信源节点T，当其最大数据流大于等于网络信息输入信息量时，其所有输入链路全局编码向量所生成的向量空间的秩为网络输入信息量，即向量空间中线性无关的全局编码向量的个数为网络信息输入量。所以，信源节点发出的信息量为w，则非信源节点最多收到信源发出的w个信息。对满足输入链路大于w的节点，则能同时接收到信源发出的所有信息。在路由的情况这是不可能的，这是网络编码性能优于路由的本质原因。
有向无环网络中，对于任何非信源节点T，存在其所有输入链路e的全局编码列向量fe的集合所生成的向量空间ve。对于满足输入最大流量大于等于网络输入信息量的非信源节点T，均有
dim（ve）=网络输入信息量
则此时的线性网络编码称为线性多播。在有向无环网络中，线性多播是其最基本的特点。
5 结束语
在有向无环网络中，由于不存在环，所以我们可以“由上至下”从信源节点至信宿节点顺序地线性编码传输信息，增强了信息传输安全性，提高了网络吞吐量。在此，我们详细描述了网络编码技术的现状和存在的问题，并通过线性网络编码技术论证了网络编码是一门可行的网络技术，而且，从线性代数理论基础上证明了网络编码存在线性多播性。
有向无环网络编码理论的研究是网络编码技术不可或缺的内容。未来网络编码技术的发展将结合计算机网络技术，信息论和编码技术，密码学理论等知识，并结合现代技术如透明计算，云计算等不断发展和深入。
参考文献：
[1] 谢坚戈，袁涛，王晓灵等.网络编码调度策略的研究[J].电视技术，
2012.36（3）.
[2] Xia Yin， Zhang Tiyuan， Huang Jiaqing J .New algorithm for
variable-rate linear broadcast network coding. Cent. South Univ[J].Technol，2011.18：1193-1199
[3] 蒲保兴，杨路明，王伟平.线性网络编码的导出与扩展[J].软件学报，
2011.22（3）：558-571
[4] 司菁菁.线性网络编码的类型保持转换矩阵[J].计算机工程与应用，
2011.47（7）.
[5] 蒲保兴，王伟平.线性网络编码运算代价的估算与分析[J].通信学报，
2011.32（5）.
[6] Yeung R， Li S，Cai Nl.Network coding theory. foundation and
trends in communications and information theory[M]. Now Publishers，2006：11-55
[7] Tan M，Yeung R，Ho S.A unified framework for linear network
codes.Proceedings of the 4th Workshop on Network Coding Theory and Applications[C].Hong Kong，China，2008：132-136
[8] R.W.Yeung.Information Theory and Network Coding[M].Springer.
J31，2008.
[9] 周伟伟.线性网络编码研究[J].通信技术，2008.41（2）.
关键词： 网络编码； 可行性； 线性多播性； 混合
中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2012）12-01-02
Research on network coding based on linear network coding technology
Li Ni， Yang Wangdong， Chen Qiang
（Department of Information Science and Engineering， Hunan City College， Yiyang， Hunan 413000， China）
Abstract： The status of the network coding research and the existing problems are described. The feasibility of network coding is proven through the analysis of linear network coding technology coding and decoding principle. The most basic property of the linear network coding-linear multicast property is demonstrated based on theory of linear algebra. Finally， the network coding technology is put forward as a "hybrid" technology. The network coding technology development will be combined with the computer network technology， information theory， coding technology and cryptography theory.
Key words： network coding； feasibility； linear multicast property； hybrid
0 引言
今天的互联网信息就像高速路上的汽车或管道中的水流一样被传输着，日益增长的网络带宽需求和不可靠网络的QOS需求，已成为制约网络发展的瓶颈。为扩大网络覆盖范围和提高系统容量，采用网络编码技术实现网络的最大流传输，已被国际学术界认定为解决网络问题的重要手段，并成为网络理论研究的热点问题之一。
1 网络编码研究现状和存在的问题
上个世纪50年代香农就提出：通信网络端对端的最大信息流是由网络有向图的最小分割决定的，但传统路由器的存储转发模式难以达到最大流最小分割定理的上界。2000年，香港中文大学R.Ahlswdee等人在发表的论文Network Information Flow中首次提出了网络编码[9]，并根据信息论严格证明了网络编码允许中间节点对接收到的信息进行编码并转发，接收节点通过相应的解码获得原始信息，这样可以达到通信网络的容量上界，从而最大限度利用网络资源。网络编码的提出从本质上打破了通信网络中传统的信息处理方式，是通信网络研究中一个重要的里程碑事件。近年來，网络编码理论的研究已取得重要发展，同时在应用基础和工程实践方面的研究也正在全方面展开。2003年，SYR.Li等人证明了使用线性网络编码已经能足够达到网络多播容量。Koetter R等人提出了网络编码的代数框架，并证明了存在满足多播流量的线性不变编码。这两位学者的工作为网络编码的发展准备了必要的理论条件。随机网络编码是由Ho T、Medard等人在2003年提出的，它的提出拓宽了网络编码的适用场景，使得网络编码不再局限于确定的网络拓扑和集中式算法。Cai Ning利用分布式网络编码来纠正网络中的差错，并论述了网络编码在安全方面的应用，为网络编码增加了新的应用领域。国外多所著名大学如麻省理工学院、多伦多大学、瑞士EPFL学院等，以及多家知名IT研究机构包括微软研究院、贝尔实验室等，都在积极开展网络编码理论和应用的研究，而国内针对编码的研究尚处于起步阶段。
目前，网络编码的理论研究尚处于初步阶段，实际应用也远未挖掘出其真正潜力，还有大量的难题有待解决。①即便网络编码可以提高通过率，能使问题得到有效解决，但是要确定存在合适的边函数却是件不容易的事情。还存在网络什么时候传输的边函数有用，有多少信息需要通过这种方式传送等问题。②在许多实际的网络中，并不一定是有向或无环的。对于有环网络构造的编码是时变的，这在实际中很少应用。并没有证明有环网中最佳时不变码的存在。③多源网络编码构造问题。④目前许多的有效编码算法都只限于应用到组播的情况，缺少一般性。⑤网络安全与网络管理的应用。
2 网络编码技术概述
网络编码的概念源于2000年Ahlswede R，Cai N，SYR.Li，R.W.Yeung发表的论文《Network Information Flow》，其最初的思想即允许网络的中间节点参与编译码。网络编码采用存储-编译码-转发的方式，可达到网络的多播容量[6]。网络编码的实质：①信息流被压缩或被编码；②网络编码是通过计算（编码）提升吞吐量。（网络吞吐量：是指在没有帧丢失的情况下，设备能够接受的最大速率。吞吐量的单位以比特/秒或字节/秒表示。） 网络编码理论也称为网络信息流理论，属于网络信息论的重要分支。经典信息论的编码通常是信源编码和信道编码，而网络编码与其有本质上的不同。网络编码除考虑信源和信宿节点的编码外，中间节点也参与编码，并且网络编码能从整体上提高网络吞吐量，提升通信系统的有效性。
网络编码理论指出网络信息流可以被压缩，从而进一步提升网络吞吐量。并且信息流仍然满足守恒定理，虽然信息内容被处理，但处理前后信息是不增也不减的。
其中，线性网络编码是研究较早，也是较为成熟的一类。有向无环网络中的网络编码称为线性网络编码。蒲保兴等详细分析了线性网络编码的计算时延与关键参量之间的关系[5]。
3 线性网络编码的编码译码原理及其可行性
线性网络编码中的核心是确定两个重要参数，即局部编码矩阵和全局编码向量。
定义1 线性网络编码的局部编码矩阵[8]
有向无环网络中，已知F为有限域（具有有限个元素的域），s（向量矩阵维数）为正数。对于任何节点T，其线性网络编码的局部编码矩阵为：
KT=[kd，e]d∈In（T），e∈Out（T）
式中，In（T）是节点T所有输入链路的集合，Out（T）为节点T所有输出链路的集合，|In（T）|表示节点T输入链路的个数，|Out（T）|表示节点T输出链路的个数。KT矩阵是维数等于|In（T）|×|Out（T）|的矩阵。kd，e表示节点T的每个相邻链路对（d，e）的局部编码标量，取值于有限域F。
对于信源节点由于没有输入链路，一般假设产生s维信号的信源节点存在s条输入链路，由于这s条链路实际并不存在，所以称为虚拟链路。
定义2 线性网络编码的全局编码向量
式中，fd为输入链路d的全局编码向量，fe称为输出链路e的全局编码向量。全局编码的是维数等于s*1的列向量，标记网络输入信号量为s。该迭代公式的初始条件是信源节点的s维虚拟链路的全局编码向量，它是从向量空间上选择的一个s维的标准基。
定义3 线性网络编码中全局编码向量与链路上传输信息的关系
me=x·fe
式中，x为信源节点产生的所有信息行向量，维数为1*s。fe为链路e上的全局编码向量，me为链路e上传输的信息。通过线性编码后每条链路上传输的是关于输入信号的线性表达量。
定义4 线性多播的译码矩阵D
[fe]e∈In（T）·D=Is
式中，maxflow（T）是针对任何满足maxflow（T）≥s的节点T，[fe]e∈In（T）为节点T所有输入链路的全局编码向量并列放置一起所组成的矩阵，Is为s×s维的单位矩阵。
将节点T收到的所有消息（可用消息矩阵x·[fe]e∈In（T）表示）乘以译码矩阵D，即可译码出信源节点S所发出的信息。
线性网络编码的编码和译码原理，其基本思想是，编码时，根据每个节点的每个相邻链路对的局部编码标量，得到每个节点的局部编码矩阵。将局部编码标量和局部编码矩阵的线性组合，得到关于每条链路的全局编码向量。于是得到通过编码后每条链路的实际传输信息。译码时，由定义4得到译码矩阵D，将信宿节点收到的所有消息乘以D，即可译码出信源节点所发出的所有信息。
可见，线性编码的基本思路简洁，当局部编码矩阵确定后，可以惟一确定全局编码向量，并可通过译码矩阵得到其信源信息，并易于在网络通信中实现，保证了在网络中信息的安全，提高了吞吐量，由此网络编码是可行的。
4 网络编码的线性多播性质
在向量空间的一组元素，如果其中没有向量可表示成有限个其他向量的线性组合，则称为線性无关，反之称为线性相关。
有向无环网络中，对于任何非信源节点T，输入链路为n，均存在由其所有输入链路d的全局编码向量fS*1集合组成的向量空间vs*n。若n≥s，则vs*n秩的最大值为s。已知全局编码向量均是从s个标准基的线性组合的，所以，向量空间vs*n的每个列向量均是s个标准基的线性组合，所以vs*n的秩为s。
在有向无环网络中，对于非信源节点T，当其最大数据流大于等于网络信息输入信息量时，其所有输入链路全局编码向量所生成的向量空间的秩为网络输入信息量，即向量空间中线性无关的全局编码向量的个数为网络信息输入量。所以，信源节点发出的信息量为w，则非信源节点最多收到信源发出的w个信息。对满足输入链路大于w的节点，则能同时接收到信源发出的所有信息。在路由的情况这是不可能的，这是网络编码性能优于路由的本质原因。
有向无环网络中，对于任何非信源节点T，存在其所有输入链路e的全局编码列向量fe的集合所生成的向量空间ve。对于满足输入最大流量大于等于网络输入信息量的非信源节点T，均有
dim（ve）=网络输入信息量
则此时的线性网络编码称为线性多播。在有向无环网络中，线性多播是其最基本的特点。
5 结束语
在有向无环网络中，由于不存在环，所以我们可以“由上至下”从信源节点至信宿节点顺序地线性编码传输信息，增强了信息传输安全性，提高了网络吞吐量。在此，我们详细描述了网络编码技术的现状和存在的问题，并通过线性网络编码技术论证了网络编码是一门可行的网络技术，而且，从线性代数理论基础上证明了网络编码存在线性多播性。
有向无环网络编码理论的研究是网络编码技术不可或缺的内容。未来网络编码技术的发展将结合计算机网络技术，信息论和编码技术，密码学理论等知识，并结合现代技术如透明计算，云计算等不断发展和深入。
参考文献：
[1] 谢坚戈，袁涛，王晓灵等.网络编码调度策略的研究[J].电视技术，
2012.36（3）.
[2] Xia Yin， Zhang Tiyuan， Huang Jiaqing J .New algorithm for
variable-rate linear broadcast network coding. Cent. South Univ[J].Technol，2011.18：1193-1199
[3] 蒲保兴，杨路明，王伟平.线性网络编码的导出与扩展[J].软件学报，
2011.22（3）：558-571
[4] 司菁菁.线性网络编码的类型保持转换矩阵[J].计算机工程与应用，
2011.47（7）.
[5] 蒲保兴，王伟平.线性网络编码运算代价的估算与分析[J].通信学报，
2011.32（5）.
[6] Yeung R， Li S，Cai Nl.Network coding theory. foundation and
trends in communications and information theory[M]. Now Publishers，2006：11-55
[7] Tan M，Yeung R，Ho S.A unified framework for linear network
codes.Proceedings of the 4th Workshop on Network Coding Theory and Applications[C].Hong Kong，China，2008：132-136
[8] R.W.Yeung.Information Theory and Network Coding[M].Springer.
J31，2008.
[9] 周伟伟.线性网络编码研究[J].通信技术，2008.41（2）.