第1章绪论 1．1历史回顾 在点对点通信网络中，信道无差错传播信息的能力取决于信道容量。数据将从信源节点传输到指定的信宿节点集合。基于传输要求，自然会考虑网络能否满足这些需求，以及如何有效地满足这些需求。 在现有的计算机网络中，信息通过一种存储转发的方式从信源节点经由中间节点传输到每个目标节点。在此方法中,从中间节点的输入信道接收的数据包将被存储,并通过输出信道将副本转发到下一个节点。当中间节点指向多个目标节点时，它会将数据包的副本发送到每一条指向任何目标节点的信道。在数据分发网络中，通常认为除了数据复制外，不需要在中间节点对数据做其他处理。 近年来，科研人员在卫星通信网络［211］中首次提出了网络编码的基本概念，随后网络编码在文献［158］中得到充分的阐释。文献［158］ 首次提出了“网络编码”的术语，并证明了其相对传统存储转发的优势，从而修正了人们对其的一般认识。由于网络编码具有普遍性并存在巨大的应用潜力，使它在信息与编码理论、网络转换、无线通信、复杂度理论、密码学、运筹学和矩阵理论等领域都受到了极大关注。 在文献［211］和文献［158］之前，特殊网络的编码问题已经在分布式信源编码研究中有了进展［177，200，207，211，212］。文献［158］和文献［211］中的工作也分别激发了后续对单一信源和多信源网络编码的研究。网络编码理论在多个领域都得到了发展，网络编码新的应用也不断涌现。比如，在文献［176］中将网络编码技术应用于一个文件共享应用原型见文献［206］对此应用的分析。。对于网络编码主题的简短介绍，推荐读者参考文献［173］。关于网络编码最新的文献，推荐读者浏览网站“网络编码”首页［157］。 这本书旨在成为基本网络编码理论的教程，目的是清晰地阐述网络编码理论而不是展示所有的结果。本书第一部分主要介绍单一信源节点的网络，2.1节从解释网络编码实例开始。第二部分主要处理更加一般的情况，即网络中有多个不同的信源节点、信宿节点集合。 相较于多信源问题，单一信源网络编码问题更好理解。文献［188］指出，当该编码方案被限制为线性变换时，网络编码的优势最有可能实现。因此，第一部分主要运用代数学的方法，而第二部分主要运用概率学的方法。 虽然本书并非是关于这个问题的调查研究，但在相关网站http://dx．doi．org/10．1561/0100000007。上的一个表格中，根据主题的以下分类，本书提供了相应的参考文献摘要(见文后参考文献)。 （1） 线性编码 （2） 非线性编码 （3） 随机编码 （4） 静态码 （5） 卷积码 （6） 分组码 （7） 字母表大小 （8） 代码结构 （9） 算法/协议 （10） 循环网络 （11） 无向网络 （12） 链路故障/网络管理 （13） 分离定理 （14） 纠错/检测 （15） 密码学 （16） 多源 （17） 多播 （18） 成本标准 （19） 非均匀需求 （20） 相关信源 （21） 最大流最小割界 （22） 重叠编码 （23） 网络 （24） 路径 （25） 无线/卫星网络 （26） 自组织/传感器网络 （27） 数据存储/转发 （28） 实施问题 （29） 矩阵理论 （30） 复杂度分析 （31） 图论 （32） 随机图 （33） 填充树 （34） 多商品流 （35） 博弈论 （36） 拟阵理论 （37） 信息不平等 （38） 噪声信道 （39） 排队分析 （40） 速率失真 （41） 多描述符 （42） 拉丁方格 （43） 可逆网络 （44） 多用户信道 （45） 联合网络的信道编码 1.2示例 术语。本书用有限有向图来表示一个通信网络，网络中点与点之间允许存在多条链路。没有输入链路的节点称为信源节点，其他节点称为非信源节点。在有限有向图中，源节点用方块表示，其他节点都用圆圈表示。图中的边也称为信道，表示每单位时间传输一个数据单元的无噪声通信链路。从一个节点到一个邻居节点的直接传输信息的容量由节点之间的信道个数决定。举例来说，如在图1．1(a)中，节点W 到节点X 的信道容量为2。如果一条信道从节点X 到节点Y ，则表示为XY 。 如果一个通信网络中没有有向环路，则此网络称为无环网络。在图1．1(a)和图1.1(b)中的网络都是无环网络。 源节点产生消息，并通过多跳的方式在网络中传播。本书感兴趣的是目的节点能够获得的信息量以及获取信息的速度。然而，这取决于传输信息的中间节点处理数据的性质。 图1．1通信网络中的多播 假设在图1．1(a)所示的无环网络中，将2bit信息b1 和b2 从源节点多播至节点Y 和Z 。每条信道按照设定只能传输b1 和b2 中的一个。通过这种方式，每个中间节点简单地复制和转发从上游接收到的比特信息。 图1．1(b)和图1.1(c)与图1．1(a)相比具有相同的网络，但减少了一条信道，展示了在两个单位时间内，将3bit的信息b1 、b2 和b3 从源点S 多播至节点Y 和Z 的一种方法。这种方法实现了每单位时间内可以多播1．5bit信息。当中间节点仅仅只能复制信息时，这是可能实现的最大速率（详见文献［209］中第11章的问题3）。本书讨论的这种网络即为著名的蝶形网络（butterfly network）。 例1．1(蝶形网络上的网络编码) 图1．1(d)展示了在与图1．1(b)和图1.1(c)相同的网络中，从源点S 多播2bit信息到节点Y 、Z 的不同方式。在图1.1（d）中，节点W 将接收到的比特信息b1 和b2 进行异或b1b2 。从W 到X 的信道上传输的比特为b1b2 ，接着在节点X 处复制比特b1b2 分发给节点Y 和Z 。因此，节点Y 收到了b1 和b1b2 ，通过它们可以解码得到b2 。类似地，节点Z 也可以 通过接收到的比特b2 和b1b2解码得到b1 。通过这种方式，网络中的9条信道都只使用了一次。 异或是一种简单的编码形式。如果仅在中间节点进行比特复制而不进行编码，则要想达到相同的通信目的，至少有一条信道需要使用两次。所以信道使用情况的总数将是至少10个。因此，编码具有最大限度地减少延迟和能量消耗的潜在优势，与此同时，也可以最大化比特率。 例1．2图1．2(a)描述了双方之间的信息交换过程，一方表示节点S 和T 的组合节点，另一方表示S′ 和T′ 的组合节点。双方之间直接通过网络互相发送1bit数据信息。 例1．3图1．2(b)中描述的网络与图1．2(a)相比减少了一条信道，其他均相同。如果只是通过直接数据路由，例1．2中的目标不能达到。但如果节点U运用接收到的比特b1 和b2 编码产生新的比特b1b2 ，并在信道UV 上传输，则例1．2的目标仍然可以达到。和例1．1一样，利用这样的编码机制能够再次提高比特率。这个在中间节点编码的例子揭示了信息论的一个基本事实，其首先在文献［207］中被提出： 当有多个信源在通信网络中传输信息时，信息的联合编码相比单独传输可能会取得更高的比特率。 图1.2双方之间的会话 一方由S和T的节点组合表示，另一方由S′和T′节点组合表示 例1．4图1．3描述了一个在通信网络中相距两倍无线传输范围的两个相邻基站，标注为ST 和S′T′ 。安装在中间的装置是一个中继收发器，标记为UV ，它在1个单位时间内可以发送或者接收1bit数据。通过UV ，两个基站在3个单位时间内交换1bit数据。在前两个单位时间内，中继收发器分别从两个基站接收1bit数据。在第3个单位时间，中继收发器将接收到的2bit数据进行异或编码，并广播到基站，然后基站就可以进行解码。在基站和中继收发机之间的无线传输可以由网络中的图1．2(b)象征性地表示。 图1．3中继收发器的两个无线基站之间的交互 本例的原理可以很容易地推广到两个相邻基站之间的N-1个中继收发器在距离的N倍无线传输范围内传输的情况。 例1.4也可以运用到卫星通信中，节点ST 和S′T′ 代表两个地面站，它们通过卫星UV 相互通信。通过在卫星上运用如前所描述的简单编码，就可以节省50%的下行带宽。 第一部分 单源 第2章无环网络 在存在一定共性的基础上，网络编码能以不同的方式实现。在通常的设定中，源节点产生的消息通过类似在管道中传输的方式多播到特定的目的节点。当网络无环时，网络中的各种操作可以做到同步，每个消息被单独编码并从上游节点传播到下游节点，使得每个消息的处理都与消息序列中的顺序无关。在这种情况下，网络编码问题可以独立于传播延迟进行考虑，包括信道中的传输延迟和节点上的处理延迟。 另一方面，当网络中包含有向环时，消息序列中的消息处理和传输会交织在一起。这时网络中的时延就成为网络编码中需要考虑的一部分。 本章主要基于文献［187］，研究在一个无环网络中处理单个消息的网络编码。包含有向环的网络编码将在第3章中讨论。 2．1网络编码和线性网络编码 通信网络可以看作一个允许节点之间存在多条边的有向图。图中的每条边代表一条具有单位容量的传输信道。网络中没有输入信道的节点为信源节点。在每个无环网络中至少存在一个信源节点。本书的第一部分将无环网络中所有的信源节点合并成一个信源节点，使得在每个无环网络中都有唯一的信源节点S。 对于节点T，记In(T)为节点T的输入信道集合，Out(T)为节点T的输出信道集合。为了方便讨论，假设In(S)是终点为信源节点S的虚拟信道集合，并且这些信道没有起点。虚拟信道的数量通常用ω表示。图2．1给出了在信源节点S处接入两（ω=2）条虚拟信道的例子。 图2．1蝶形网络的信源节点处有两条输入的虚拟信道 一个数据单元可以由基域F中的一个元素表示。例如，当信息单位是比特时，此时F为二元域F=GF(2)。信源节点S产生的消息由基域F中的ω个符号构成，可以将其表示为ω维行向量x∈Fω。信源节点生成消息x并通过每条输出信道发送出去。信息在网络中的传播通过符号f～e(x)∈F在网络中的每条信道e上传输来实现。 非信源节点不需要获得足够的信息来确定整个消息x的值。其仅需要通过编码函数将接收到的所有符号进行运算，映射到每条对应的输出信道上。这种对每条信道进行编码的机制即为一种网络编码。 定义2．1(无环网络中网络编码的局部描述)F为有限域，ω为正整数。对于无环网络，基域F上的ω维网络编码由每条信道e的局部编码映射组成，其定义为 k～e:F|In(T)|→F 其中，T为任意节点，e∈Out(t) 。 网络的无环拓扑使得在所有信道e上传输的符号都可以通过递归地作用于局部编码映射得到，记为f～e(x)。定义2.1中的网络编码并没有显式给出f～e(x)的值，其数学