随机线性网络编码 | Codeboy's Blog

形式陈述

在有限有向无环、单位容量的单源多播网络中，源有 $k\ge1$ 个 $\mathbb F_q$ 符号，各终点最小割至少为 $k$ 。随机线性网络编码让每个节点对每条输出边独立、均匀选取局部组合系数，再按线性网络码的源／非源约定转发：源组合其持有的 $k$ 个符号，其他节点组合入边值。

终点收到编码向量矩阵 $A_t$ 后检查秩； $\operatorname{rank}A_t=k$ 就能恢复。随机性只决定码的选择，合法实现应能检测秩不足，而不是在失败时仍假装输出已恢复。

对每个终点选一个不恒为零的满秩子式，把这些子式相乘得多项式 $P$ 。若其总次数为 $D$ ，各系数独立均匀取自 $\mathbb F_q$ ，则

\Pr[P=0]\le\min(1,D/q).

所有选中子式非零就同时可译码。这个保守界直接说明域变大如何降低失败概率， $D$ 取决于所选网络与子式。

直觉

一个随机组合通常能提供一个新方向。小域中方向选择少，碰到已有张成空间的概率较大；大域中可选方向多，更容易补齐秩。节点只需要知道入边上的包及其编码向量，不必由中央预先协调每个系数。

上述概率是在声明的独立均匀系数分布下计算的。某些系数被固定为零或由不匹配的伪随机规则相关地产生时，须重新检查分析条件。

例子与边界

先看一个终点直接收到 $k$ 个独立均匀编码向量的模型。第一个向量不为零的概率为 $1-q^{-k}$ ；已有 $j$ 个独立向量后，其张成空间有 $q^j$ 个元素，新向量逃出该空间的概率为 $1-q^{j-k}$ 。所以

\Pr[\text{满秩}]=\prod_{j=0}^{k-1}(1-q^{j-k}) =\prod_{i=1}^k(1-q^{-i}).

$k=2,q=2$ 时概率为 $(1-1/2)(1-1/4)=3/8$ ，并不高。 $k=2,q=256$ 时约为 $0.99608$ 。这两个数适用于独立均匀全局向量；一般网络中全局向量会共享上游随机系数，不能未经证明直接套这个乘积公式。

收到一包后，按精确行化简把其编码向量与已有行作消元。若余行全零，它不增加秩，可丢弃；否则选择一个新主元，将这行及同步变换后的负载存入基。维护的不变量是：存储行线性独立，且每行负载仍等于该行向量作用于源数据。

累计秩到 $k$ 即可回代恢复。每包长度 $L$ 、当前秩至多 $k$ 时，朴素增量消元用 $O(k(k+L))$ 次域运算，保存 $O(k(k+L))$ 个域符号。编码向量头部占 $k$ 个域符号，是实际通信开销的一部分。

推论与应用

成功概率高不代表对所有随机种子都成功；需要零错误结果时，可以验秩后请求更多包或重新选择系数。这把随机构造的风险转成可检测的延迟或通信开销。

网络丢包可能让终点收不到足够的独立包；恶意节点注入错误线性组合又是另一种威胁。普通随机线性编码提供冗余与解码机制，本身不提供认证或抗污染保证。

参考资料