网络编码的研究进展 research status of network coding.pdfVIP

… i… 一 i ； jj==鬻 …“ i i j …：一j — j j翟叠：誊薯要 ?量l ii ；i i≥¨ij|蔓j¨}iiii{≤ii蓦至≥I蓍董i：：i耋¨¨；|：ii ii 硕博论文 网络编码的研究进展半 付琳憎，周亮2．李少谦2 (1．成都信息工程学院通信工程系 了交换，路由器只能对信息进行存储转发的传统组播模式， 1 背景 建立起一种全新的网络体系结构及信息编码和传输模式。 NoteontlleMaximumnow 网络编码代表了一种协同工作的理念，这使得它的应用不 香农在论文《A n11Du曲a Ne附ork》指出：“通信网络端对端的最大信息流，是由网络仅仅局限于改进组播增加网络容量，它与其他技术相结合 有向图的最小割决定”，但目前传统路由器的存储转发模式 已经应用于网络管理、纠错、信息安全、P2P对等网络通信、 根本不可能达到香农最大流最小割定理规定的上界。在现 路由和交换等领域。 有的计算机通信网络中，信息传输都是由源节点经过中间 组播技术有效地解决了单点发送多点接收的问题，实 节点，以存储转发的方式传送到目标节点。除了数据复制以 现了网络中点到多点的高效数据传送。能够大量节约网络 外，一般来说在网络的中间节点并不需要做任何数据处理， 带宽、降低网络负载。作为一种与单播和广播并列的通信方 因为普遍认为，中间节点所进行的数据处理对数据传输过 式。组播的意义不仅在于此。更重要的是，可以利用网络的 程本身并不会带来任何好处。然而，2000年R．Ahlswede等组播特性方便地提供一些新的增值业务，包括在线直播、网 提出的网络编码彻底推翻了这一结论[1】。 络电视、远程教育、远程医疗、网络电台、实时视频会议等互 网络编码指出允许路由器对不同的信息流进行编码组 联网的信息服务领域。 合可以达到该上界，在此基础上，参考文献『21进一步证明了 组播是靠在通信网络上建立组播树来实现的，当考虑 在单信源多信宿情况下，应用线性网络编码理论，一定能够 一点向多点的组播路由树的建立时，问题变得复杂起来。一 达到该上界。线性网络编码将原先分立于物理层和网络层 般认为。组播树的建立是一个NP问题。通常采用的方法是 的两个核心概念(编码和路由)有机地融为一体，彻底改变 先用最大流算法找到信源与一个信宿之间的最大流及其实 现的路径，然后再依次寻找其他信宿与信源之间的路径。在 寻找信源与第二个信宿之问的路径时，往往就在原通信网 +教育部博士点基金资助项目(No．20050614009)、国家自然科学基 络中去掉信源与第一个信宿之间已经用过的链路的容量。 金资助项目(No 黧勰麟 万方数据 这样处理是因为，传统路由认为网络中传输的信息是不能 这种方法将网络编码的构造进一步简化，它也是在己知拓 叠加的，只能进行存储转发。这样的组播树的建立方式，会 扑的情况下．首先通过最大流最小割算法找到完成组播所 导致信源与第二个及其后面所有信宿之间的路径都不是 需路径的集合，在找出的这个子图上确定各个节点所需要 以它们之间的最大流进行传输的，最终使得组播可以实 进行的操作。这种方法不但把网络编码构造