现代通信系统的历史以令人震惊的洞察力闪现为标志。
克劳德·E·香农，数学家和工程师，大约 60 年前发起了一场这样的革命，他为新的通信数学理论奠定了基础——现在被称为信息论。他的工作的实际成果，涉及数据的压缩和可靠传输，今天可以在互联网、有线和无线电话系统以及存储设备（从硬盘驱动器到 CD、DVD 和闪存盘）中看到。
香农处理的是专用于个人通话的电话线路上的通信。如今，信息越来越多地通过共享网络（如互联网）传输，在共享网络中，多个用户同时通过相同的媒介进行通信——无论是电缆、光纤还是无线系统中的空气。共享网络有可能提高通信系统的实用性和效率，但它们也造成了对公共资源的竞争。许多人必须争夺访问权限，例如，提供可下载歌曲的服务器或无线热点。
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您正在帮助确保有关塑造我们当今世界的发现和想法的具有影响力的故事的未来。
因此，挑战在于找到使共享顺利进行的方法；幼儿的父母会认识到这个问题。网络运营商经常试图通过增加资源来解决这一挑战，但这种策略通常是不够的。例如，铜线、电缆或光纤现在可以为商业和住宅用户提供高带宽，但铺设成本高昂，并且难以修改和扩展。超宽带和多天线传输系统可以扩大无线网络服务的客户数量，但可能仍然无法满足不断增长的需求。
因此，也需要提高效率的技术。在互联网和其他共享网络上，信息目前由路由器中继——路由器是在信令路径或链路相交的节点处运行的交换机。路由器将传入的消息分流到通往消息最终目的地的链路。但是，如果想要效率，路由器是这些交叉点的最佳设备吗？交换甚至是执行的正确操作吗？
直到七年前，很少有人想到会问这样的问题。但随后，德国比勒费尔德大学的鲁道夫·阿爾斯韋德，以及当时都在香港中文大学的蔡寧、李碩彥和楊偉豪，发表了开创性的工作，引入了一种在共享网络上分发信息的新方法。在这种称为网络编码的方法中，路由器被编码器取代，编码器传输关于消息的证据，而不是发送消息本身。当接收器收集证据时，他们会从组装的线索中推断出原始信息。
尽管这种方法听起来可能违反直觉，但仍在研究中的网络编码有可能极大地加速和提高各种通信系统的可靠性，并很可能引发该领域的下一次革命。调查人员当然也在探索提高效率的其他途径；但据我们所知，这些其他方法通常扩展了现有方法。
比特不是汽车
阿爾斯韋德和他的同事部分基于香农提出的观点构建了他们的提案，即传输关于数据的证据实际上可能比直接传递数据更有用。他们还意识到，一旦收集到足够的线索，接收器就能够推断出原始数据，但接收器不需要获得所有发出的证据。一种线索可以被另一种线索取代，重要的是接收到一些线索的组合，这些线索共同揭示原始消息。（如果接收器事先被告知用于生成证据的规则，或者如果关于如何使用证据的说明包含在证据本身中，则接收器将能够理解证据。）
网络编码打破了经典观点，即通信信道类似于道路，而比特就像在这些道路上行驶的汽车。但是，对通信的交通运输模型的理解有助于理解新方案的工作原理以及它为何如此有前途。
香农在数学上证明，每个信道都有一个容量——它在任何给定的时间范围内可以中继的信息量——并且只要不超过信道的容量，通信就可以可靠地进行。在交通运输类比中，道路的容量是每秒可以安全处理的汽车数量。如果交通量保持在容量以下，则通常可以保证在一端进入道路的汽车在另一端出口时保持不变（除非发生罕见的事故）。工程师们基于交通运输模型构建了越来越复杂的通信系统。例如，香农思考的电话系统为每次对话分配了一条不同的“道路”；通过传统电话线的两个呼叫永远不会在同一时间和频率共享一条线路。
计算机网络——尤其是互联网——本质上是一个合并、分支和交叉道路的迷宫。从一台计算机传输到另一台计算机的信息通常会经过多条道路才能到达目的地。来自单个消息的比特被分组到数据包中（信息高速公路上的拼车或公共汽车），每个数据包都标有其预定目的地。路由器位于道路的交叉口，检查每个数据包的标头，并将该数据包转发到其目的地。
具有讽刺意味的是，推动当今复杂通信系统发展的交通运输模型现在却阻碍了进步。毕竟，比特不是汽车。当两辆车在同一座狭窄的桥梁上会合时，它们必须轮流通过瓶颈。但是，当两个比特到达瓶颈时，可能会有更多选择——这就是网络编码的用武之地。
工作原理
框“基本思想”中描述的假设的六节点数字网络可以帮助澄清这些选项。回想一下，在计算机中，所有消息都采用二进制代码字符串的形式。想象一下，此网络中的每个链路或道路每秒可以携带一位——无论是 0 还是 1——并且仅在相应箭头指定的方向上携带。节点 A 的网络用户 Amy 希望以每秒一位的速度向节点 D 的 Dana 发送信息。与此同时，节点 B 的 Ben 希望以完全相同的速度和速率向节点 C 的 Carl 发送信息。Amy 和 Ben 的需求能否同时得到满足，而不会超过任何链路的容量？
在路由器系统中（框中最左侧），前景似乎黯淡。从 Amy 到 Dana 以及从 Ben 到 Carl 的两条路径都需要穿过链路 5。此链路成为狭窄的单车道桥梁的等效物。链路 5 起始节点 E 处的路由器每秒总共接收两个比特（来自链路 2 的一个比特和来自链路 3 的一个比特），但由于链路 5 的容量为 1，因此路由器每秒只能沿其发送一个比特。在交通运输模型中，此类瓶颈会导致噩梦般的交通拥堵，随着时间的推移，越来越多的比特堆积起来，等待轮到它们。
但在新方法中（框的右侧部分），普通的路由器将被编码器取代，编码器将比交通警察有更多选择。编码器可以发送完全不同的信息，而不是中继瓶颈处收集的实际比特流。例如，它可以将任何给定秒内到达的 1 的数量相加，如果该总和为偶数，则发送 0。如果总和为奇数，则设备可以发送 1。因此，如果链路 5 同时从链路 2 和 3 接收到 1 和 0，则它携带 1。如果从链路 2 和 3 接收到两个 0 或两个 1，则链路 5 携带 0。然后，结果由路由器 F 通过链路 6 和 7 分别发送到 Carl 和 Dana。
这种方法用两个比特的混合体替换节点 E 处的每对比特。这样的比特流似乎很荒谬。我们提出的编码器所做的相当于以一种模糊两者的方式将一个电话交谈与另一个电话交谈结合起来。这种方法的明显荒谬性正是它长期以来未被研究的原因。
但有时明显的疯狂是真正的创新。混合比特流可能无法完美地描述任何一种传输，但它可以提供关于两者的证据。假设我们还通过链路 1 将 Amy 的消息发送给 Carl，并通过链路 4 将 Ben 的消息发送给 Dana。发送这两条消息使用了路由系统无法有效利用网络资源（链路 1 和 4）来满足 Amy 和 Ben 的需求。Carl 的节点接收到 Amy 的传输，并且对于每个时刻（来自链路 6），它都知道 Amy 和 Ben 发出的消息对中 1 的数量是偶数还是奇数。如果 Carl 的节点被编程为也“知道”链路 5 起始处的编码器使用的规则，或者如果它可以从证据本身推断出规则，则收集的证据将使其能够解密 Ben 发送的消息。Dana 的节点也将类似地解开 Amy 的消息。
明显的优势
这种策略实现了交通运输模型的局限性所无法想象的两个目标。首先，它使离开节点的比特能够同时走两条路径，这是汽车无法做到的。其次，它允许到达瓶颈头部的两比特流合并成单比特流，而会聚到一条狭窄桥梁上的两辆汽车不能成为一个实体；一辆汽车必须等待另一辆汽车通过才能继续过桥。
我们的六节点模型（阿爾斯韋德及其同事在 2000 年首次给出的一个次要变体）所例证的数据处理方法有可能在不需要添加额外管道的情况下增加网络容量，因为它避免了交通堵塞。仅使用路由，我们的六节点网络可以维持平均每秒二分之一比特的并发传输。（由于两个竞争传输将不得不共享链路 5，因此对于每个竞争需求，有效数据速率将为每两秒一位，或每秒二分之一比特。）使用网络编码，同一系统支持每秒一位的并发传输。因此，在这里，网络编码使容量翻倍。
有时，网络编码可能会产生更大的容量增益，有时则不会。但这种方法永远不会降低网络的容量，因为在最坏的情况下，它会精确地模仿路由器系统的操作。它还应该提高相对庞大网络中的可靠性和抗攻击能力，因为证据的可互换性意味着一些证据数据包可能会丢失而不会造成问题。
来自多播网络的经验
到目前为止，对实施网络编码的大部分研究都集中在多播网络上——在多播网络中，所有接收器都需要获得相同的信息。互联网视频游戏依赖于多播系统，以便在每次有人移动时更新每个玩家。视频或现场体育赛事的网络广播以及以电子方式发布给大量客户的新软件也通过多播网络传输。如今，此类网络仍然使用路由器，而回归交通运输类比有助于解释为什么设计它们通常非常困难。
想象一下，全国的公路上挤满了汽车。每个路由器都像一个警察，在单个十字路口指挥交通。驶入的汽车加入到达它们之前的车辆后面的队列。警官依次读取每辆汽车的目的地，并将其引导到行驶路线上。系统设计中的目标是让每个路由器以不仅加快后续每辆汽车到达其预定目的地的速度，而且还允许全国交通运输系统作为一个整体满足尽可能多的驾驶员的方式指挥交通。
即使是拥有全国所有道路完整地图的中央设计师也很难确定每个路由器要遵循的最佳策略。随着网络随时间变化，难度会增加：高峰时段、道路维修、事故和体育赛事意味着道路和对道路的需求不断变化。
直觉可能会认为，设计一个依赖于网络编码的系统应该更加困难，因为有更多选项需要考虑。节点可以转发未更改的数据，从而模仿路由器。但它也可能在发送之前混合两个或多个传入数据流，并且如何混合它们也可能需要考虑；此外，不同的节点可能使用不同的算法。
幸运的是，这种逻辑是有缺陷的。有时添加更多选项实际上会简化事情。如果没有编码，多播系统的架构师将需要枚举从发射器到每个接收器的尽可能多的路径，然后确定网络可以同时支持多少条路径。即使对于简单的网络，查找和测试所有路径组合也将是一项令人眼花缭乱的任务。
相比之下，使用网络编码的多播系统将非常容易设计。令人震惊的事实是，加法和乘法是编码网络需要应用的唯一数学函数。此外，即使网络中每个编码器中编程的功能或规则是独立于消息和其他编码功能选择的，并且在没有任何网络布局知识的情况下选择的，整个系统也将以极高的概率以最佳性能运行。即使系统随时间变化（移动或可重新配置网络中可能会发生这种情况），网络也将继续以最佳方式运行，而无需重新设计。要了解原因，请参见“代码设计示例”。
未来的网络
因此，如果编码器取代路由器，网络的运行方式将大不相同。我们的消息遍历网络的方式将会改变：它们不仅会与其他传输共享“道路”，而且可能会与来自各种其他来源的流量紧密纠缠在一起。有些人可能担心这种纠缠会损害消息的安全性。然而，更可能的是，遍历网络的流量将变成局部无法解密的代数流。网络上的用户将在不知不觉中相互协作以实现共同利益，不仅允许更高的数据速率或更快的数据下载，而且在无线网络的情况下，还可以提高能源效率。（由于每次无线传输都会消耗能量，因此节点可以通过将打算发送给多个邻居的信息混合在一起并仅发送一次传输来减少消耗。）
通过改变网络的功能，网络编码可能会以我们目前无法想象的方式影响社会。
此外，视频下载延迟和手机通话丢失的情况将大大减少。在互联网上，路由器会发生故障或被关闭进行维护，并且数据包会一直被丢弃。这就是为什么人们有时必须重新请求网页以及为什么站点有时加载缓慢的原因。可靠性将随着网络编码的提高而提高，因为它不需要每一条证据都通过。
网络管理员将在无需添加新通信信道的情况下提供这些好处，因为现有信道将得到更好的利用。因此，网络编码将补充其他通信技术，使用户能够尽可能多地从中受益。
有时用户会知道网络编码正在运行，因为它可能会修改一些常用应用程序（例如点对点下载）的功能。今天，寻求下载文件的用户会在其机器上驻留该文件的协作用户中进行搜索。在使用网络编码的系统中，文件将不再以整体或可识别的片段形式存储。
但是用户个人不必弄清楚如何找到获得所需文件所需的证据。从用户的计算机或电话发送到网络中的请求将导致该个人的计算机或本地服务器在网络中搜寻与感兴趣的文件相关的证据片段。收集到的证据（包括与所需文件相关的代数混合信息片段）将有助于恢复该文件。服务器或个人计算机不是将拼图拼在一起，其碎片是整体的可识别片段，而是求解代数方程组。并且，一直以来，大多数人都会对这些操作一无所知——就像我们大多数人都不了解我们手机中复杂的纠错操作一样。
军方已经认识到网络编码的稳健性，目前正在资助对其在移动自组织网络中的应用进行研究，移动自组织网络可以动态形成。此类网络在高度可变的环境中很有价值，例如在战场上，可靠的通信至关重要，并且建立和维护光纤电缆或蜂窝塔的基础设施很困难。在自组织网络中，每个士兵的无线电都成为通信系统中的一个节点，每个节点都寻找并建立与相邻节点的连接；这些连接共同建立网络的链路。每个节点既可以发送和接收消息，也可以充当中间人来传递发送给其他接收器的消息。此技术将通信能力扩展到远远超出单个节点的传输范围。它还具有极大的灵活性，因为网络随用户移动，并根据需要不断重新配置和重新建立连接。
通过改变网络的功能，网络编码可能会以我们目前无法想象的方式影响社会。与此同时，我们这些研究它的人正在考虑实施的障碍。从我们的基于路由器的系统过渡到网络编码系统实际上将是较小的障碍之一。这种转换可以通过逐步更改而不是突然的彻底改革来处理；可以重新编程一些路由器，而未构建为执行编码操作的其他路由器将被逐步替换。
更大的挑战将是应对超越用编码器替换路由器的问题。例如，当接收节点将收集足够的证据以从混合物中恢复其所需内容时，混合信息是一种好的策略。这种情况始终在多播网络中得到满足，但在一般情况下可能并非如此。此外，在某些情况下，例如当传输多个多播时，混合信息会使使用者难以或不可能提取正确的输出。那么，当多个连接共享同一网络时，节点如何决定哪些信息可以混合以及哪些信息不能混合？无线网络中的网络编码在哪些方面必须不同于其在有线网络中的使用？网络编码的安全优势和含义是什么？当一个人的数据必然与其他用户的数据混合在一起时，人们将如何为通信服务付费？在全球范围内的合作中，我们和其他人正在思考如何解开这些结，同时我们也在努力增强通信网络的能力，这些网络已成为如此多生活不可或缺的一部分。
更多探索
通信的数学理论。 C. E. 香农，载于贝尔系统技术杂志，第 27 卷，第 379-423 页和第 623-656 页；1948 年 7 月和 10 月。可在 http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html 获取
网络信息流。 R. 阿爾斯韋德、N. 蔡、S.-Y. R. 李和 R. W. 楊，载于IEEE 信息论汇刊，第 46 卷，第 4 期，第 1204-1216 页；2000 年 7 月。
线性网络编码。 S.-Y. R. 李、R. W. 楊和 N. 蔡，载于IEEE 信息论汇刊，第 49 卷，第 2 期，第 371-381 页；2003 年 2 月。
网络编码的代数方法。 R. 科特和 M. 梅达德，载于IEEE/ACM 网络汇刊，第 11 卷，第 5 期，第 782-795 页；2003 年 10 月。
多播网络代码构造的多项式时间算法。 S. 贾吉、P. 桑德斯、P. A. 周、M. 埃夫罗斯、S. 埃格纳、K. 贾恩和 L.M.G.M. 托尔胡伊岑，载于IEEE 信息论汇刊，第 51 卷，第 6 期，第 1973-1982 页；2005 年 6 月。
多播的随机线性网络编码方法。 T. 何、M. 梅达德、R. 科特、D. R. 卡格尔、M. 埃夫罗斯、J. 石和 B. 梁，载于IEEE 信息论汇刊，第 52 卷，第 10 期，第 4413-4430 页；2006 年 10 月。