线性网络编码

网络编码是从1990年代末到2000年代初的一系列论文中建立的研究领域。然而，网络编码的概念，特别是线性网络编码，出现得更早。在1978年的一篇论文中，提出了一种通过卫星提高双向通信吞吐量的方案。在这个方案中，两个试图相互通信的用户将他们的数据流传输到卫星，卫星通过求和模2来组合这两个流，然后广播组合流。两个用户中的每一个在接收到广播流后，都可以使用自己流的信息对另一个流进行解码。

2000年的论文给出了蝴蝶网络示例，该示例说明了线性网络编码如何优于路由。该示例等效于上述卫星通信方案。同一篇论文给出了一个具有一个源节点和三个目的节点的网络的最佳编码方案。这是第一个说明卷积网络编码（一种更一般的线性网络编码形式）在循环网络上的最优性的例子。

线性网络编码可用于提高网络的吞吐量、效率和可扩展性，以及抵御攻击和窃听的能力。网络的节点不是简单地中继它们接收到的信息包，而是将多个数据包组合在一起进行传输。这可用于在网络中获得最大可能的信息流。

数学上已经证明，理论上线性编码足以在一个源的多播问题中达到上限。然而，线性编码通常是不够的（例如，具有任意需求的多源、多汇），即使对于更一般的线性版本，如卷积编码和滤波器组编码也是如此。为具有任意需求的一般网络问题寻找最佳编码解决方案仍然是一个悬而未决的问题。

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

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

使用一个简单的代码，如图所示，A和B可以通过两个中继节点发送符号之和同时传输到两个目的地——换句话说，我们使用公式“A+B”对A和B进行编码。左边的目的地接收A和A+B，可以通过减去这两个值来计算B。同样，正确的目的地会收到B和A+B，也能同时确定A和B。因此，采用网络编码，只需要三个时隙，提高了吞吐量。

随机线性网络编码是一种简单而强大的编码方案，在广播传输方案中使用分散算法允许接近最佳吞吐量。节点传输它们接收的数据包的随机线性组合，系数从伽罗瓦域中选择。如果字段大小足够大，则接收器获得线性无关组合（从而获得创新信息）的概率接近1。然而需要注意的是，虽然随机线性网络编码具有出色的吞吐量性能，但如果如果接收者获得的数据包数量不足，则他们极不可能恢复任何原始数据包。这可以通过发送额外的随机线性组合来解决，直到接收器获得适当数量的数据包。

线性网络编码仍然是一个相对较新的主题。基于之前的研究，RLNC中存在三个重要的开放性问题：

1. 由于使用Gauss-Jordan消元法，解码计算复杂度高
2. 由于将大系数向量附加到编码块而导致高传输开销
3. 系数向量之间的线性相关性，可以减少创新编码块的数量

无线的广播性质（加上网络拓扑）决定了干扰的性质。无线网络中的同时传输通常会导致所有数据包丢失。因此，无线网络需要调度程序（作为MAC功能的一部分）来最小化此类干扰。因此，网络编码的任何收益都会受到底层调度程序的强烈影响，并且会偏离有线网络中看到的收益。此外，由于硬件限制，无线链路通常是半双工的；即，由于两条路径之间缺乏足够的隔离，一个节点不能同时发送和接收。

虽然最初网络编码被提议用于网络层，但在无线网络中，网络编码已广泛用于MAC层或PHY层。已经表明，在无线网状网络中使用网络编码时，需要精心设计和思考以利用数据包混合的优势，否则无法实现优势。影响吞吐量性能的因素还有很多，例如媒体访问层协议、拥塞控制算法等。目前尚不清楚网络编码如何共存而不危及现有的拥塞和流量控制算法为我们的互联网所做的工作.

应用于设备到设备通信的网络编码的简短说明。D1和D2表示设备，BS是基站，M1、M2和M3是特定的消息。

由于线性网络编码是一个相对较新的主题，因此它在工业中的采用仍有待确定。与其他编码不同，线性网络编码由于其特定的使用场景狭窄，因此并不完全适用于一个系统。理论家正试图连接到现实世界的应用程序。事实上，人们发现BitTorrent方法远远优于网络编码。

预计网络编码可用于以下领域：

• 由于一般信息中心网络和特别是命名数据网络的多源、多播内容交付性质，线性编码可以提高整个网络的效率。
• 传统和无线网络中存在数据包丢失的前向纠错和ARQ的替代方法。例如：编码TCP，多用户ARQ
• 对网络攻击（如窥探、窃听、重放或数据损坏攻击）的稳健性和弹性。
• 数字文件分发和P2P文件共享。例如：来自微软的雪崩
• 分布式存储。
• 无线网状网络的吞吐量增加。例如：COPE,CORE,编码感知路由,BATMAN
• 空间传感器网络中的缓冲和延迟减少：空间缓冲多路复用
• 减少单跳无线组播传输的数据包重传次数，从而提高网络带宽。
• 分布式文件共享
• 到移动设备的低复杂度视频流
• 设备到设备(D2D)扩展

出现了在多路访问系统中使用网络编码来开发软件定义的线域网络(SD-WAN)的新方法，这些网络可以提供更低的延迟、抖动和高稳健性。该提案提到该方法与LTE、以太网、5G等底层技术无关。

由于该领域相对较新，并且目前对该主题的数学处理仅限于少数人，因此网络编码尚未找到在产品和服务中实现商业化的途径。目前尚不清楚这个主题是否会占上风，或者作为一个好的数学练习而停止。

研究人员明确指出，需要特别注意探索网络编码如何与现有路由、媒体访问、拥塞、流量控制算法和TCP协议共存。否则，网络编码可能不会提供太多优势，并且会增加计算复杂性和内存要求。