线性网络编码

网络编码方案可以被分为线性网络编码和非线性网络编码。由于线性网络编码具有很好的代数结构，并且已有较好的编码方案。因此，线性网络编码使用得更为广泛，本文研究的网络编码方案均为线性网络编码。

线性网络编码基础

当网络中的源节点开始发送数据包到一组目的节点时，为了使得所有的汇聚节点能够以组播容量的速率接收，源节点也需要进行编码。如果有$n$个数据包$p_1,p_2,...,p_n$需要被编码，那么源节点需要首先获得一个$N\times n$的矩阵$M$，在这个矩阵中的元素均是来自于有限域$GF(2^m)$。 $N$通常大于等于$n$。 $$M=\left( \begin{array}{ccc} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{N1} & \cdots & a_{Nn}\\ \end{array} \right)$$

经过编码后的数据包如下所示：

$P_k=a_{k1}\times p_1 +a_{k2}\times p_2+\cdots+a_{kn}\times p_n,k\in [1,N]$

尽管本文在上式中采用了普通实数域上的加法和乘法符号，但是这里的操作通常要基于有限域。接下来本文将简略介绍一下有限域上的运算。当源节点完成编码后，将数据发送出去。 中间节点在接收到数据后，如果需要进行中间节点编码操作则进行再编码。当汇聚节点接收到$n$个数据包后，根据对应的全局编码向量，进行矩阵求逆运算。最后将求得逆矩阵与所有的接收数据矩阵相乘，即可恢复出原始数据。

相信大家都学习过线性代数，线性网路编码本质上就是进行一系列的矩阵运算，网络编码的编解码操作可以概括为3个阶段，即源节点的编码操作，中间节点的再编码操作，以及目的节点的解码操作。

如果说$M$为包含原始数据的矩阵，这个好理解，如果是一副图片，1MB的大小，如果将其子代文件大小设置为4，那么我们的$M$就是一个$4\times 256$的二维数组。我们选择一个$4\times 4$的生成矩阵$G$对其进行编码，数据就变成了$GM$，在传输时，部分节点进行了网络编码操作，这等价于将编码后的矩阵中某几行又进行了线性混合，这在宏观上等价于左乘了一个矩阵$T$，此时变为$TGM$，接收端只需要左乘矩阵$G^(-1)T^(-1)$即可得到原始数据$M$$。$

随机线性网络编码

随机线性网络编码的出现是网络编码领域内重要突破，RLNC采用随机策略在中间节点进行再编码，中间节点在编码时随机地从有限域中选择编码系数对输入的数据进行编码，然后将编码后的数据发送出去。研究表明，只要有限域的尺寸足够大，便能保证汇聚节点以很高的概率解码。比如当有限域为 时，目的节点解码的概率为0.996。

RLNC的优点主要有如下：

1. 该方案能够以分布式的方式运行，即网络中的节点在运行时并不需要知道网络的全局拓扑结构，这一特点极大地促进了实际应用的发展。
2. 该方案能够适应于动态变化的网络环境，源节点和中间节点只需要按照既定的传输策略传输数据即可。

基于以上两点，该方案易于实施，因而被广泛应用于后续的研究中。

RLNC方法的缺点在于，需要工作在较大的域尺寸上，这样才能保证令人满意的解码率。采用较大的有限域带来的问题是编码过程中计算的开销会相应地增加。理论上来说，所需的编码域越小，计算的开销越小。并且，即使在一个较大的有限域上，也不能保证目的节点能够100%解码。

因此，采用确定性的算法设计网络编码方案能够改善这一问题。但是确定编码方法的缺点在于需要知道全局的网络拓扑结构。网络的整体拓扑不变时，此类算法获取网络整体拓扑信息，然后计算出网络编码方案，最后将方案用于数据传输。当网络的数据量较大时，采用确定性算法是值得的。因为对于全局的网络拓扑信息只需要计算一次就够了。

确定性的网络编码算法的优点有以下两点。

1. 该方法能够使得网络的编码方案工作在一个非常小的有限域上。这有助于提升网络编码的效率。
2. 此类算法能够保障目标节点在接收到指定的数据时，能够以100%的概率解码。

确定线性网络编码

根据确定性网络编码算法的时间复杂度来分，分为指数时间算法和多项式时间算法。由于指数时间算法的复杂度随着节点的规模变大显著增加，P. Sanders等人提出了多项式时间复杂度的网络码字构造算法。这是第一个多项式级别的确定性网络编码算法。本节仅对此确定性算法做详细介绍。

该方法的核心内容是采用向量空间正交补的思想保证在经过中间编码后，多个相关的目的节点能够确定解码。该方法的所需的有限域尺寸仅为$|T|$,$T$为组播通信中目的节点的个数，并且计算码字的工作可以在多项式时间内完成。

该方法的步骤如下：

1. 获取一个单位容量的有向无环网络$G$。网络中仅有一个源节点，多个目的节点。
2. 采用Ford-Fulkerson算法分别计算出源节点到这几个目的节点$T$的最大流$h_t$。选取这些最大流中的最小一个作为网络的组播容量$C$。对于每一个目的节点$t$，从自己的$h_t$条不相交路径中选取$C$条路径，保证从源节点到每个目的节点有且仅有$C$条不相交的路径。其他的链路被认为是冗余链路。
3. 构造一个虚拟的源点$S'$,$S'$到$S$有$C$条不相交的平行单位容量链路。选定有限域尺寸使得$q \ge |T|$，然后将$S'$到$S$的$C$条链路的全局编码内核分别设置为单位向量$e_1,e_2,...,e_C$。
4. 每一个目的节点维护一个路径集合$R$和这些链路对应的全局编码向量集合$B$。在初始情况下，$B$ 即为$C$个单位向量。
5. 从源节点开始，按照拓扑顺序确定所有节点输出链路的全局编码向量。当一个链路$e$只有一个输入链路时，则该链路的全局编码向量与其前一链路$pre\underline{ }e$的全局编码向量相同。当一条链路有多个输入链路时，则需要对该链路$e$进行编码，编码的任务由该链路的起始端节点完成。

对于所有目的节点，如果链路$e$属于被其占用，需要把集合$R$中$pre\underline{ }e$换成$e$，同时把$B$中$g(pre \underline{}e)$换成$g(e)$，使得所有与此相关的汇聚节点均能保证各自的$B$中$C$个向量是线性无关的。

有两种方法可以确定$pre\underline{}e$和$e$中的节点的编码方法。

方法一是采用随机方法，随机获得编码系数对输入的信息进行编码，当所用的有限域足够大时，能够以很大概率使得经过替换后相关的汇聚节点各自$B$中的向量仍然线性无关。

S Jaggi等人还提出了一种确定的方法来确定中间节点如何编码。该方法基于下面定理。 定理1.2：当$n\le q$，考虑$(x_i, y_i)\in F^h \times F^h$ ，其中对于$1\le i\le n, x_i\cdot y_i\ne0$。存在一个$x_1,x_2,...,x_n$的线性组合$u$使得对于$1\le i\le n, u \cdot y_i \ne 0$。 证明：见文献[58].

该定理的证明过程即为线性组合的寻找过程，该定理保证了当有限域的尺寸大于接收节点数目时，确定性的网络编码方案一定存在，显然，该方案所需的有限域尺寸非常小。

S Jaggi提出的这个多项式时间的确定性算法的理论意义要远大于实际意义。在实际中，很少看到某个网络编码方案采用这个确定性算法。RLNC用的反而特别多。如果大家没看懂，我也觉得也不必纠结，直接跳过这一节即可。但如果想深入理解的话，还是建议搞懂，大家可以去看他05年发表在IEEE TRANS ON TIT的原文。在第三章，我们将重点编程实现这两种算法。届时，您将能够深入了解这两种典型的网络编码算法。事实上，根据M. Medard之前的文章，随机线性网络编码已能够满足绝大多数的应用场景。但在一些特殊场合，如分布式存储，再生码，安全网络网络码字构造方面，确定性网络编码也非常重要。