网络编码

在计算机网络中，线性网络编码是中间节点通过线性组合的方式将数据从源节点传输到汇节点的程序。

网络编码可用于提高网络的吞吐量、效率和可扩展性，以及减少攻击和窃听。 网络的节点接收多个数据包并组合起来进行传输。 该过程可用于在网络中获得xxx可能的信息流。

已经证明，从理论上讲，线性编码足以实现单源多播问题的上界。 然而，线性编码通常是不够的； 即使对于更一般的线性版本，例如卷积编码和滤波器组编码。 为具有任意需求的一般网络问题寻找最佳编码解决方案仍然是一个悬而未决的问题。

在线性网络编码问题中，一组节点 P {displaystyle P} 参与将数据从 S {displaystyle S} 源节点移动到 K {displaystyle K} 汇节点。 每个节点生成新数据包，这些新数据包是过去接收到的数据包的线性组合，方法是将它们乘以从有限域中选择的系数，通常大小为 G F ( 2 s ) {displaystyle GF(2{s})} 。

由于操作是在有限域中计算的，因此生成的消息与原始消息的长度相同。

汇聚节点接收这些网络编码消息，并将它们收集在一个矩阵中。 可以通过对矩阵进行高斯消元来恢复原始消息。

网络由有向图 G = ( V , E , C ) {displaystyle {mathcal {G}}=(V,E,C)} 表示。 V {displaystyle V} 是节点或顶点的集合，E {displaystyle E} 是有向链接（或边）的集合，而 C {displaystyle C} 给出了 E { displaystyle E} 。 设 T ( s , t ) {displaystyle T(s,t)} 是从节点 s {displaystyle s} 到节点 t {displaystyle t} 的xxx可能吞吐量。 根据xxx流最小割定理，T ( s , t ) {displaystyle T(s,t)} 的上界是所有割的最小容量，即边的容量之和 切，在这两个节点之间。

Karl Menger 证明了在单播场景中总有一组边不相交的路径达到上限，称为xxx流最小割定理。 后来，Ford-Fulkerson 算法被提出来在多项式时间内找到这样的路径。

但是，组播场景下的情况比较复杂，实际上，使用传统的路由思想是达不到这样一个上限的。 阿尔斯韦德等人。 证明如果可以在中间节点完成额外的计算任务（传入数据包组合成一个或多个传出数据包），则可以实现。

蝴蝶网络经常被用来说明线性网络编码如何优于路由。 两个源节点（在图片的顶部）具有必须传输到两个目标节点（在底部）的信息 A 和 B。 每个目标节点都想知道 A 和 B。每条边只能携带一个值（我们可以认为边在每个时隙中传输一个位）。

如果只允许路由，则中央链路将只能承载 A 或 B，而不能同时承载两者。 假设我们发送 A 通过中心； 那么左边的目的地将收到 A 两次而根本不知道 B。 发送 B 对正确的目的地提出了类似的问题。 我们说路由是不充分的，因为没有路由方案可以同时将 A 和 B 传送到两个目的地。 同时，两个目的节点知道 A 和 B 总共需要 4 个时隙。

使用一个简单的代码，如图所示，A 和 B 可以通过两个中继节点发送符号之和同时传输到两个目的地——使用公式 A+B 对 A 和 B 进行编码。