论文部分内容阅读
【摘 要】网络技术的兴起改变了科技发展的可能路径，为新的编码技术的存在提供了可靠的发展模式。网络编码之所以方兴未艾，就是因为网络优于传统编码载体的特质。通过对网络编码的分析描述，以线性网络技术为基础，剖析网络编码的可能性和可行性。实践表明，网络编码是当前多学科综合发展的成果，代表了未来编码技术的新发展方向。本文试就基于线性网络编码技术的网络编码技术进行浅要分析。
【关键词】线性网络编码；网络编码
【中图分类号】TN919.3+1【文献标识码】A【文章编号】1672-5158（2013）07-0096-01
1、引言
网络编码是一种基于网络本身而诞生的编码技术，这种技术出现的初衷是为了解决日益拥堵的互联网流通问题。人类信息时代的开启，使互联网成为改变人类社会最积极的动力之一。但互联网的使用和发展受到客观环境的限制，包括硬件和软件在内的客观工具的完备与否，都决定了互联网能在多大程度上发挥作用。自本世纪初开始，陆续有学者提出了网络编码的理念，希望通过网络编码的方式解决互联网拥堵的问题，提高互联网使用效率。这一概念的提出，立刻引起诸多学者和科研机构的高度关注。目前通过网络编码技术解决互联网拥堵问题已经成为国内外学界的共识，国外多所著名大学或是科研机构都已展开了网络编码的开拓性研究，如MIT、哈佛大学、多伦多大学和微软实验室等。
2、网络编码研究现状
早在上世纪五十年代，就有学者提出，通信网络端对端的最大信息流是由网络有向图的最小分割决定的，但传统路由器的存储转发模式难以达到最大流最小分割定理的上界。根据传统的理论，网络节点只是对收到的信息进行存储和转发，扮演着转发器的角色，但是从信息理论的观点来说，没有理由让节点只能进行存储转发，可以让节点对多条输入边上收到的信息进行一定的线性或非线性操作（编码），然后再发送出去，这样起着编码器的作用，网络编码正是由此思想产生的，在接收节点上，通过一定的运算，译出信源所发的信息。
本世纪初，学者R.Ahlswdee 等人发表的一篇名为“网络信息流”的文章中提出了网络编码的概念，作者提出，对于已知的网络流图，从发点到收点的流量的最大值小于或等于任何一个割切的容量，而网络编码提出了一个组播传输，信源为S，接收节点集合为无穷，那么可达最高组播速率C。而如果采用传统传输方法，可能无法达到最高组播速率。事实上，近年来对于网络编码的实证性研究也充分证明了这一点，这也从另一个方面佐证了网络编码在客观上的可行性。此外，在R Ahlswede 等人提出网络编码这一概念不久，又有学者证明了目前的网络编码技术已经能够达到网络组播的条件，同时，还用实验证明了存在着基于网络特性的组播方式的线性网络编码。随后的研究深入到了随机网络编码的研究中，Medard等人曾提出如拓展网络编码使用范围的想法，并通过代数计算框架给出了可行的路径。而随机网络编码的出现则更将非线性研究和网络编码研究融为一体，提高了网络编码研究的理论深度[1]。
目前，对网络编码的研究主要以国外的科研机构和大学研究机构为主导，其研究领域已经足够深入，研究框架得到了初步的建立，国内对于网络编码的研究尚处于起步阶段，在实际运用中也不是很多。
3 、基于线性网络编码技术的网络编码研究
网络编码之所以得到众多学者和科研机构的高度关注，不仅在于其手段和理念上的程度比较新，更体现在其独特的功用上。一般来说，通过网络编码技术，科研使组播传输速率达到最大，从而拓展了网络容量的上限，这对于目前拥堵的互联网通道而言是极为重要的；其次，它还可以节省网络带宽资源消耗，正是通过线性编码技术，提高了网络节点的使用效率和功用，减少了网络资源的消耗；另外，网络编码技术还能均衡网络负载，平衡繁忙的网络线路与相对宽 松的网络线路之间的差异，提高网络的鲁棒性。
3.1 网络编码的分类
网络编码可以分为线性网络编码和非线性网络编码两种，前者是研究的重心。在组播和非组播网络传播体系中，网络编码也有不错的应用。组播传输技术指在发送者和每一接收者之间实现点对多点网络连接，如果一个发送者同时给多个的接收者传输相同的数据，也只需复制一份的相同数据包，它提高了数据传送效率，网络编码与组播传输技术的综合，减少了骨干网络出现拥塞的可能性。目前，在组播网络传输中使用的网络编码技术一般有代数构造方式和多项式时间算法两种处理方法，在实际运算中我们需要根据实际情况而定[2]。
3.2 基于现行网络编码技术的网络编码
（1）线性网络编码原理
网络编码技术看似复杂，其原理其实不难，以线性网络编码的编码译码原理为例，其基本思想就是在编码时根据每个节点的每个相邻链路对的局部编码标量，得到每个节点的局部编码矩阵，将局部编码标量和局部编码矩阵的线性组合，得到关于每条链路的全局编码向量，在此基础上，得到实行网络编码后各条连接线路的具体编码信息。在译码时，需要考虑的是译码矩阵，这需要将所有节点受到的全部信息加衣汇总，并对信息进行分析处理，从而译出信源节点所存储和收发的全部信息。综上所述，线性编码的思路其实还是比较简洁的，一般只要确定了局部编译矩阵，便可以确定全局编码向量，然后通过对破译矩阵的运用，剖析信源节点发出的信息，从而实现网络通信中信息的收发。线性网络编码技术提高了网络运行的安全性，提高了网络的总体容量，具有较高的可行性。
（2）网络编码的线性多播性质
在向量空间的一组元素，如果其中没有向量可表示成有限个其他向量的线性组合，则称为线性无关，反之称为线性相关。有向无环网络中，对于任何非信源节点T，输入链路为n，均存在由其所有输入链路d的全局编码向量fS*1集合组成的向量空间vs*n。若n≥s，则vs*n秩的最大值为s。已知全局编码向量均是从s个标准基的线性组合的，所以，向量空间vs*n的每个列向量均是s个标准基的线性组合，所以vs*n的秩为s。在有向无环网络中，对于非信源节点T，当其最大数据流大于等于网络信息输入信息量时，其所有输入链路全局编码向量所生成的向量空间的秩为网络输入信息量，即向量空间中线性无关的全局编码向量的个数为网络信息输入量。
4、结束语
网络编码是近年来兴起的一个新的研究领域，由于其在解决网络拥堵，克服传统网络传输模式方面具有较高的优越性，正在引起人们越来越多的重视。但随着对网络编码研究的深入，一些问题也随着浮出水面，需要得到重视并有待进一步解决。其中包括了网络编码在传输速率、负载消耗、负载均衡、鲁棒性等方面带来的收益需要进行更加深入的研究，而且网络编码需要网络路由器具有编码功能，且现有路由算法、传输协议等需要改变和更新；此外，基于网络编码的差错控制是一种新的差错控制思想，可以为将来的研究提供更多的借鉴。在可以预见的将来，网络编码必然是一种能得到广泛应用与推广的互联网革新力量，将会对整个网络世界的发展产生深远的影响。
参考文献
[1] 吴艳，杨有龙，刘三阳.基于网络流矩阵求解网络最大流[J].系统工程，2007
[2] 谢政，李建平.网路算法与复杂性理论[M].国防科技大学出版社，1995
【关键词】线性网络编码；网络编码
【中图分类号】TN919.3+1【文献标识码】A【文章编号】1672-5158（2013）07-0096-01
1、引言
网络编码是一种基于网络本身而诞生的编码技术，这种技术出现的初衷是为了解决日益拥堵的互联网流通问题。人类信息时代的开启，使互联网成为改变人类社会最积极的动力之一。但互联网的使用和发展受到客观环境的限制，包括硬件和软件在内的客观工具的完备与否，都决定了互联网能在多大程度上发挥作用。自本世纪初开始，陆续有学者提出了网络编码的理念，希望通过网络编码的方式解决互联网拥堵的问题，提高互联网使用效率。这一概念的提出，立刻引起诸多学者和科研机构的高度关注。目前通过网络编码技术解决互联网拥堵问题已经成为国内外学界的共识，国外多所著名大学或是科研机构都已展开了网络编码的开拓性研究，如MIT、哈佛大学、多伦多大学和微软实验室等。
2、网络编码研究现状
早在上世纪五十年代，就有学者提出，通信网络端对端的最大信息流是由网络有向图的最小分割决定的，但传统路由器的存储转发模式难以达到最大流最小分割定理的上界。根据传统的理论，网络节点只是对收到的信息进行存储和转发，扮演着转发器的角色，但是从信息理论的观点来说，没有理由让节点只能进行存储转发，可以让节点对多条输入边上收到的信息进行一定的线性或非线性操作（编码），然后再发送出去，这样起着编码器的作用，网络编码正是由此思想产生的，在接收节点上，通过一定的运算，译出信源所发的信息。
本世纪初，学者R.Ahlswdee 等人发表的一篇名为“网络信息流”的文章中提出了网络编码的概念，作者提出，对于已知的网络流图，从发点到收点的流量的最大值小于或等于任何一个割切的容量，而网络编码提出了一个组播传输，信源为S，接收节点集合为无穷，那么可达最高组播速率C。而如果采用传统传输方法，可能无法达到最高组播速率。事实上，近年来对于网络编码的实证性研究也充分证明了这一点，这也从另一个方面佐证了网络编码在客观上的可行性。此外，在R Ahlswede 等人提出网络编码这一概念不久，又有学者证明了目前的网络编码技术已经能够达到网络组播的条件，同时，还用实验证明了存在着基于网络特性的组播方式的线性网络编码。随后的研究深入到了随机网络编码的研究中，Medard等人曾提出如拓展网络编码使用范围的想法，并通过代数计算框架给出了可行的路径。而随机网络编码的出现则更将非线性研究和网络编码研究融为一体，提高了网络编码研究的理论深度[1]。
目前，对网络编码的研究主要以国外的科研机构和大学研究机构为主导，其研究领域已经足够深入，研究框架得到了初步的建立，国内对于网络编码的研究尚处于起步阶段，在实际运用中也不是很多。
3 、基于线性网络编码技术的网络编码研究
网络编码之所以得到众多学者和科研机构的高度关注，不仅在于其手段和理念上的程度比较新，更体现在其独特的功用上。一般来说，通过网络编码技术，科研使组播传输速率达到最大，从而拓展了网络容量的上限，这对于目前拥堵的互联网通道而言是极为重要的；其次，它还可以节省网络带宽资源消耗，正是通过线性编码技术，提高了网络节点的使用效率和功用，减少了网络资源的消耗；另外，网络编码技术还能均衡网络负载，平衡繁忙的网络线路与相对宽 松的网络线路之间的差异，提高网络的鲁棒性。
3.1 网络编码的分类
网络编码可以分为线性网络编码和非线性网络编码两种，前者是研究的重心。在组播和非组播网络传播体系中，网络编码也有不错的应用。组播传输技术指在发送者和每一接收者之间实现点对多点网络连接，如果一个发送者同时给多个的接收者传输相同的数据，也只需复制一份的相同数据包，它提高了数据传送效率，网络编码与组播传输技术的综合，减少了骨干网络出现拥塞的可能性。目前，在组播网络传输中使用的网络编码技术一般有代数构造方式和多项式时间算法两种处理方法，在实际运算中我们需要根据实际情况而定[2]。
3.2 基于现行网络编码技术的网络编码
（1）线性网络编码原理
网络编码技术看似复杂，其原理其实不难，以线性网络编码的编码译码原理为例，其基本思想就是在编码时根据每个节点的每个相邻链路对的局部编码标量，得到每个节点的局部编码矩阵，将局部编码标量和局部编码矩阵的线性组合，得到关于每条链路的全局编码向量，在此基础上，得到实行网络编码后各条连接线路的具体编码信息。在译码时，需要考虑的是译码矩阵，这需要将所有节点受到的全部信息加衣汇总，并对信息进行分析处理，从而译出信源节点所存储和收发的全部信息。综上所述，线性编码的思路其实还是比较简洁的，一般只要确定了局部编译矩阵，便可以确定全局编码向量，然后通过对破译矩阵的运用，剖析信源节点发出的信息，从而实现网络通信中信息的收发。线性网络编码技术提高了网络运行的安全性，提高了网络的总体容量，具有较高的可行性。
（2）网络编码的线性多播性质
在向量空间的一组元素，如果其中没有向量可表示成有限个其他向量的线性组合，则称为线性无关，反之称为线性相关。有向无环网络中，对于任何非信源节点T，输入链路为n，均存在由其所有输入链路d的全局编码向量fS*1集合组成的向量空间vs*n。若n≥s，则vs*n秩的最大值为s。已知全局编码向量均是从s个标准基的线性组合的，所以，向量空间vs*n的每个列向量均是s个标准基的线性组合，所以vs*n的秩为s。在有向无环网络中，对于非信源节点T，当其最大数据流大于等于网络信息输入信息量时，其所有输入链路全局编码向量所生成的向量空间的秩为网络输入信息量，即向量空间中线性无关的全局编码向量的个数为网络信息输入量。
4、结束语
网络编码是近年来兴起的一个新的研究领域，由于其在解决网络拥堵，克服传统网络传输模式方面具有较高的优越性，正在引起人们越来越多的重视。但随着对网络编码研究的深入，一些问题也随着浮出水面，需要得到重视并有待进一步解决。其中包括了网络编码在传输速率、负载消耗、负载均衡、鲁棒性等方面带来的收益需要进行更加深入的研究，而且网络编码需要网络路由器具有编码功能，且现有路由算法、传输协议等需要改变和更新；此外，基于网络编码的差错控制是一种新的差错控制思想，可以为将来的研究提供更多的借鉴。在可以预见的将来，网络编码必然是一种能得到广泛应用与推广的互联网革新力量，将会对整个网络世界的发展产生深远的影响。
参考文献
[1] 吴艳，杨有龙，刘三阳.基于网络流矩阵求解网络最大流[J].系统工程，2007
[2] 谢政，李建平.网路算法与复杂性理论[M].国防科技大学出版社，1995