网络编码理论研究综述

弋改珍

摘   要：文章通过对部分网络编码理论相关文献的调查，以网络编码技术的提出、线性网络编码、随机网络编码、卷积码为主线，研究了网络编码理论的发展和研究成果。在前期理论研究的基础上，根据现有的研究资料，总结了网络编码理论未来可能的研究方向。

关键词：网络编码;线性网络编码;随机线性网络编码;卷积网络码

Shannon[1]《通信的数学理论》一文的发表，使信息论科学诞生，开始了数字通信，通过网络传递信息。2000年，开创性文章《Network information flow》通过介绍信息流概念，证明信息的组合可以提高网络的容量，优于路由所能达到的容量，并将现有网络中的路由机制—存储转发，作为一个特例，诞生了一种新的研究领域，即网络编码。它允许网络中间节点对输入信息执行编码操作，接收节点采用编码理论进行解码，以此提高网络吞吐量。

十多年来，人们对网络编码理论及其应用越来越感兴趣。该领域的研究还激励了数学工具（编码轮、代数、拟阵论、几何、图论、组合学等）的综合应用，产生了今天的网络编码。

1    网络编码理论研究线路

Ahlswede等[2]首次提出提高网络吞吐量的新的研究领域—“网络编码”。通过研究多播场景编码速率区域的特征化问题，建立了最大流最小割定理，限制了网络的最大容量，并提出了简化信息理论问题求解的几何框架和集合理论框架。

对于网络编码框架的研究，Li等[3]利用有限域中选取的系数对信息进行线性组合，采用线性码组播，得到最优的网络码，从而提出了有向无环图的最大流最小割的最优解，开始了确定性网络编码的理论框架的概念。Koetter等[4]通过将代数几何与矩阵论连接起来，为构建确定性网络编码理论框架，开发了一种完整的代数框架。该代数框架为随机线性网络编码奠定了坚实的基础。

在研究有向无环网络环境中网络编码的基础上，Li等[5]分析了网络编码应用于无向网络中的行为和优势;同时提出在有向有环图中，卷积网络编码是更好的解决方案。

网络编码的算法实现是使网络编码理论应用与实际的重要前提。算法的复杂度受网络编码所需的有限域大小的影响，并依赖于通信中接收者的数量。影响复杂度的其他因素还有边数和源的传送速率。组合学和图论中的许多工具的应用有助于降低复杂性算法的设计。

2    网络编码理论的发展

在网络编码概念和框架的基础上，研究者进一步在编码实现算法、有限域大小、随机线性网络编码、卷积码和多播问题可解性等方面进行了研究，取得了丰硕成果，进一步完善了网络编码在实际中应用的理论基础。

2.1  线性网络编码

早在1998年，Li和Yeung首次定义了在网络中多播信息的线性码，该线性码在节点处引入了信息守恒定律。因此，在线性编码的特殊情况下，指派给网络节点输出信道的向量是指派给同一节点输入信道向量的线性组合。此外，作者阐明最大流是每个非源节点收到的信息速率的上界，他们给出如何实现这个边界和使用通用线性码多播（Linear Code Multicast，LCM）实现多播的最优解。对于有环网络中的信息传送问题，作者建议由节点处的时隙编码操作和时隙传送信道组成的解决方案。解有环问题的另一种方法是LCM的实现。在无环场景中，将一般LCM和拟阵论联系在一起，证明了基本结果：如果向量空间足够大，每个无环网络上存在通用LCM。随后，在2003年，Yeung和Cai提供了描述的结果，并首次描述了线性网络编码的理论框架，几年之后，他们定义了一般线性网络码的线性多播、线性广播和线性分散的概念。随后，Yeung又解释了线性分散和一般网络编码之间的关系，也找到与码的基域大小的关系。2008年，Yeung给出网络编码理论基础的完整定义。

不同于Cai和Yeung的研究思路，2001年，Koetter等推导出验证多播问题可行性的一个代数框架，新框架完全是代数的，使得将代数的数学定理应用到网络编码中成为可能。目标是解决最普遍的网络编码问题。

2003年，Ho等人提出解决线性网络编码场景中多播问题的两种方法：（1）关于网络流的方法。（2）使用Edmonds矩阵行列式价差二部图是否完美匹配，在计算中没有涉及矩阵的乘积和逆变换，简化了计算复杂度。Koetter等利用之前的结果开始了关于网络编码的随机化方法的研究，并提出了一个更好的、新的上界。

在实现方面，Jaggi等对首次提出的构造通用LCM的算法进行了独立修改和开发，使新的LCM在计算上更加高效。此外，新算法对基域大小的阈值比前一种算法更低，最初提出该算法用于构建线性多播，但也适用于线性广播。后来，他们实现了多播网络码构造的多项式时间算法，为有向无环图中的线性网络编码提供了确定性多项式时间算法和随机算法。

2004年，Koetter等發现了线性网络编码与线性系统理论之间的联系，特别是与图上编码理论的联系。

2.2  随机线性网络编码

2003年，Ho定义了一种多播的随机网络编码方法，其中节点使用独立、随机选自某有限域的编码系数，在输出信道上传送输入信息的线性组合。然而，在接收端，解码器需要源信息的全部线性组合。在这种新的方法中，作者允许网络编码适用于拓扑未知或变化的网络。此外，通过随机化方法，可以得到一个失效概率，通过增加有限域的维数来任意减小该概率。并计算了编码成功概率的一个下界。2004年，Ho又证明了分布式随机网络码的错误概率取决于某些错误成分，并且提供了随机网络编码理论的完整描述。这些文章描述了与二部匹配和随机网络编码的联系，推广了任意相关源情况下的Slepian-Wolf错误指数，并展示了应用随机网络编码的好处。随机线性网络编码的提出为网络编码的实现、应用与发展提供了坚实的基础。

2.3  卷积网络码和有环网

Fragouli使用子树分解的方法，建議以分散形式实现网络编码的确定性算法，并将图论中的着色问题与网络编码相结合，利用图的着色算法设计了网络编码算法。这些成果，为寻找网络编码与卷积码之间的联系提供了基础。在此基础上，作者设计了网络编码的信息流分解算法。在2006年，Fragouli通过信息流分解技术，找到了一种降低网络编码问题维数的方法，提出了一种基于源和接收者数量实现子树图设计的算法。最后，分析了网络编码和卷积码之间的联系。此外，Fragouli深入研究了网络编码与卷积码的关系，提出了一种简化的循环网络处理方法。Erez提出了一种与分组网络码相似的卷积码算法，并对其开销和解码复杂度进行了分析，该算法将网络编码推广到有环网络。

2005年，Erez提出了一种能够在多项式时间内实现有环网络上最优网络码多播算法，并对该算法进行了完整的描述。2010年，对前期结果进行了增强和充分解释。

2006年，Li和Yeung分别使用与局部编码核和全局编码核相关的有限域上的有理幂级数和向量有理幂级数定义了卷积网络编码。此外，还定义了卷积多播问题，并解释了编码和解码算法。

针对多源多播情况，Barbero等提出了有环网络中网络编码算法。事实上，这种算法可以在任何类型的网络上运行，比如无环网络和有环网络，作者证明它可以在多项式时间内运行。

3    可能的未来方向

网络编码是一个新的研究领域，涉及许多不同的领域，这一事实已经引起了研究领域的广泛关注。可能的潜力和涉及广泛的研究领域，使得网络编码的未来不可估量，也很难预测。另外，网络编码技术研究涉及其他领域。在最新研究成果的基础上，未来可能的研究方向有以下几个。

（1）需要进一步简化网络编码算法的复杂性，分析系数选取的域的大小。

（2）网络编码的理论框架还需进一步的更新和完善。

（3）可变速率网络编码有许多潜力，也是值得深入研究的课题。

（4）有环网络中的卷积网络编码有待进一步完善。

（5）利用信息论几何框架和拟阵理论，在研究网络编码容量域和网络编码极限的过程中，仍存在一些未解决的问题。

（6）网络编码技术付诸实施，还需要一个领域的研究与完善，即网络编码的安全领域研究。

4    结语

首先，本文通过对部分网络编码理论相关文献的调查，以网络编码技术的提出、线性网络编码、随机网络编码、卷积码为主线研究了网络编码理论的发展和研究成果。目的是解释网络编码理论及其应用，使感兴趣的读者参与网络编码技术的研究。其次，讨论网络编码技术涉及的数学基础，为历届网络编码理论奠定了基础。最后，在前期理论研究的基础上，建议了网络编码理论未来可能的研究方向。

[参考文献]

[1]SHANNON C E.A mathematical theory of communication[J].Bell Labs Technical Journal，1948（4）：379-423.

[2]AHLSWEDE R，CAI N，LI S Y R，et al.Network information flow[J].IEEE Transactions on Information Theory，2000（4）：1204-1216.

[3]LI S Y R，YEUNG R W，CAI N.Linear network coding[J].IEEE Transactions Information Theory，2003（2）：371-381.

[4]KOETTER R，MEDARD M.An algebraic approach to network coding[J].IEEE/ACM Transactions on Networking，2003（5）：782-795.

[5]LI Z，LI B.Network coding in undirected networks[C].Princeton：Conference on Information Sciences & Systems，2004.