线性网络编码研究

2008年第02期，第41卷 通 信 技 术 Vol.41，No.02,2008总第194期 Communications Technology No.194,Totally

线性网络编码研究

周伟伟

（南京邮电大学 光电学院，江苏 南京 210003）

【摘 要】最大流最小割定理决定了网络的最大吞吐量。近来研究表明，网络编码可以使这一理论在多播方式的网络环境中得以实现。网络编码的提出彻底地改变了计算机通信网络中的信息处理方式，其研究结合了信息论、计算机通信网络、组播技术、多用户信息论和图论等很多方面的知识。文中简要介绍了网络编码的基本原理，线性网络编码的基本概念及其发展，并且提出一种实现线性网络编码的算法。

【关键词】网络编码；线性网络编码；最大流最小割；线性码组播

【中图分类号】TP91 【文献标识码】A 【文章编号】1002-0802(2008)02-0097-03

Ｓｔｕｄｙ　ｏｎ　Ｌｉｎｅａｒ　Ｎｅｔｗｏｒｋ　Ｃｏｄｉｎｇ

ZHOU Wei-wei

(College of Optical and Electronic Engineering Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210003,China)

【Abstract】The famous max-flow min-cut theorem determines the maximum throughput of a network. The recent research has shown that the network coding can make this theorem realized in multicasting network environment. Network coding has absolutely changed the information operation method in the computer communication network. Its research involves the knowledge about information theory, computer communication networks, multicast technique, multiple user information theory and graph theory. In this paper, principle of network coding, the concept and development of linear network coding are briefly presented, including a new algorithm for implementing linear network coding.

　　　【Ｋｅｙ　ｗｏｒｄｓ】ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ；　ｌｉｎｅａｒ　ｎｅｔｗｏｒｋ　ｃｏｄｉｎｇ；　ｍａｘ－ｆｌｏｗ　ｍｉｎ－ｃｕｔ；　ｌｉｎｅａｒ－ｃｏｄｅ　ｍｕｌｔｉｃａｓｔ　

0 引言

网络编码是由A.Rhlswede等人在2000年提出的，其精髓来源于图论中著名的Max－flow Min－cut理论。网络编码的实现依靠网络中节点在转发信息前对接收到的信息进行编码后再传输。具备了网络编码功能的节点从各个输入链路获得信息，并进行编码，然后把信息传送给所有输出链路。不论是源节点还是中间节点都进行编码，以更好的利用网络带宽，增大网络吞吐量。网络节点对信息比特流进行特定的操作，例如模2和等，不仅仅是存储转发，就是网络编码。若对网络中所有节点对其输入信息进行线性操作，称为线性网络编码，否则为非线性网络编码。继A.Rhlswede等提出网络编码概念之后，Li等人证明了使用线性网络编码已经能够达到网络多播容量。Medard等提

[3]

[2]

[1]

出了网络编码的代数框架，并证明了存在满足多播容量的线性时不变编码。后两者的工作为网络编码的发展准备了必要的理论条件。随机网络编码，是由Ho，Medard等人在2003年提出的，它的提出使得网络编码不再局限于确定的网络拓扑。Cai利用分布式网络编码来纠正整个网络中的差错，并论述了网络编码在安全方面的应用。

[6]

[5]

[4]

1 最大流最小割定理和网络编码原理

最大流最小割定理:对于已知的网络流图，从出发点

[7]

s到接收点t的流量w的最大值等于其最小割的容量，即:

maxflow(s,t)=minC(s,t)。

对于有向网络，可以用Ford-Fulkerson算法来求解网络的最大流。

收稿日期：2007-10-10。

作者简介：周伟伟（1982-），女，硕士研究生，主要研究方向为现代通信系统与通信信号处理。

97

对于网络信息流，G(V,E)为一个多播网络，h为信息从信源s到信宿t1,t2, ,tL的多播传输速率。令信源s到信宿tl的最大流值为maxflow(s,tl)，则对于所有的l=1,2, ,L，有

hmax≤maxflow(s,tl)， （1）即

hmax≤minmaxflow(s,tl)， （2）

l

（1）v(s)= ；

（2）对于每一信道xy都有，v(x,y)∈v(x)；（3）对于网络中任意非源节点集合 ，有 <{v(T):T∈ }>=<{v(x,y):x ,y∈ }>，这里< >表示线性张成；

（4）给节点T的输出边分配的编码向量是其输入边所分配的编码向量的线性组合。

LCMv刻画了一种信息在网络中传输的结构。将信源节点s要传输的信息分成d维向量组，称作信息向量。传输过程中，每条信道上传输的数据符号I(e)是信源向量和全局编码向量v(x,y)的乘积。

图1a是一个线性编码组播的例子。图中从源点s组播两比特信息b1，b2到节点y和z。网络编码的基域为F2，每条链路分配的编码列向量为

v(s,t)=v(t,w)=v(t,y)=(1 0)T, T

v(s,u)=v(u,w)=v(u,z)=(1 0), （3）

T v(w,x)=v(x,y)=v(x,z)=(1 1),信源s的信息向量为(b1 b2)，每条链路上传输的信息符号为信息向量(b1 b2)和该链路编码列向量的乘积。

上述线性码组播可以实现图1a中网络的通信。但是对于任意复杂的通信网络，如何确定其所有的全局编码向量呢？文中在图论基础上提出一种求全局编码向量的方法。

将这个称作网络多播传输的最大流限。

对于只有一个信宿节点的网络，依靠路由就可以获得最大流。下面看一个具有 …… 此处隐藏：3989字，全部文档内容请下载后查看。喜欢就下载吧 ……