网络编码导论 PDF下载

编辑推荐

该书为通信与信息系统方向专著。全书采用由简入深的方法，将新兴的相对“晦涩”的网络编码理论娓娓道来。内容上，本书侧重于从工程角度引出网络编码理论知识，浅显易懂，非常适用于通信相关领域内网络编码的初学者了解基本的网络编码概念；同时，该书也基于工程实例辐射至相关理论基础，深入推演了网络编码理论的由来，并提供了丰富的导读信息，对需要进一步学习网络编码理论的相关技术人员具有较强的参考作用，可以作为通信与信息系统相关专业本科生和研究生的教材。；

内容简介

本书以网络编码的起源开篇，对网络编码技术进行了全面系统的论述。内容包括网络编码的基本概念、无损多播网络编码、会话间网络编码、有损网络中的网络编码、子图选择以及网络编码的安全性等。本书内容全面，示例丰富，深入浅出，是网络编码领域不可多得的入门读物，对相关领域科研人员和工程技术人员都具有较大的参考价值。

作者简介

暂无

网络编码导论 PDF下载

目录
 ；
第1章简介
 ；
1.1网络编码的定义
 ；
1.2网络编码的效用
 ；
1.2.1吞吐量
 ；
1.2.2鲁棒性
 ；
1.2.3复杂度
 ；
1.2.4安全
 ；
1.3网络模型
 ；
1.4本书概要
 ；
1.5备注及导读
 ；
第2章无失真多播网络编码
 ；
2.0符号规定
 ；
2.1基本网络模型和多播网络编码问题推导
 ；
2.2无延迟标量线性网络编码
 ；
2.3可解性和吞吐量
 ；
2.3.1单播情况
 ；
2.3.2多播情况
 ；
2.3.3多信源节点多播
 ；
2.3.4最大吞吐量增益
 ；
2.4多播网络编码构造
 ；
2.4.1集中式多项式时间构造
 ；
2.4.2随机线性网络编码
 ；
2.5分组网络
 ；
2.5.1分组网络中的分布式随机线性编码
 ；
2.6有环网络和卷积网络编码
 ；
2.6.1卷积网络编码的代数表达
 ；
2.7相关信源过程
 ；
2.7.1联合信源网络编码
 ；
2.7.2信源编码与网络编码的分离
 ；
2.8备注及导读
 ；
2.A附录： 随机网络编码
 ；
第3章会话间网络编码
 ；
3.1标量与向量线性网络编码
 ；
3.2分数编码问题公式化
 ；
3.3线性网络编码的非充分性
 ；
3.4信息论方法
 ；
3.4.1多路单播网络
 ；
3.5构造方法
 ；
3.5.1有线网络中的成对异或编码
 ；
3.5.2无线网络中的异或编码
 ；
3.6备注及导读
 ；
第4章失真网络的网络编码
 ；
4.1随机线性网络编码
 ；
4.2编码定理
 ；
4.2.1单播连接
 ；
4.2.2多播连接
 ；
4.3有独立同分布(i.i.d)丢包的泊松流错误因子
 ；
4.4备注及导读
 ；
第5章子图选择
 ；
5.1基于流的方法
 ；
5.1.1会话内编码
 ；
5.1.2计算受限编码
 ；
5.1.3会话间编码
 ；
5.2基于队列长度的方法
 ；
5.2.1多个多播会话的会话内网络编码
 ；
5.2.2会话间编码
 ；
5.3备注及导读
 ；
第6章对抗差错的安全性
 ；
6.0符号惯例
 ；
6.1差错修正
 ；
6.1.1集中式网络编码的纠错界
 ；
6.1.2分布式随机网络编码和多项式复杂度纠错
 ；
6.2对抗差错检测
 ；
6.2.1模型和问题描述
 ；
6.2.2检测概率
 ；
6.3备注及导读
 ；
6.A附录： 对抗差错检测结果的证明
 ；
参考文献

媒体评论

前沿

序言前言网络编码背后的基本思想非常简单。正如本书中给出的定义，网络编码不过是对包的内容进行编码操作——不再像传统的存储转发体系结构中典型采用的严格复制转发方式，而是对包的内容进行任意映射。不过，虽然网络编码简单，却没能在网络发展历史中占据一席之地。理由很显然：主导网络发展历史的传统有线技术中，网络编码不是非常实用或者说非常有利。今天，我们看发展，不仅看新技术，也看新服务。在针对这些新技术、新服务设计新的网络协议时，我们必须小心谨慎，不能因为熟悉而简单移植旧的协议。相反地，我们必须考虑一些其他迄今未使用的思想，它们有可能会对新情况提供更好的解决方案。网络编码正是这样一种思想。各种理论和实验研究均表明，在多跳无线网络多播会话业务中，采用网络编码可以获得明显增益，这正是迅速崛起的技术或服务的典型代表。下面，以微软的Avalanche项目为例进行说明。Avalanche项目旨在建立端到端的文件分发系统。这些研究促使微软在该项目中采用网络编码作为核心技术来发掘其在多播业务中的优势。至此，网络编码的时机终于成熟。因此，本书的动机在于：我们认为在未来分组网络设计中网络编码潜能巨大，我们将推进这种潜能的实现。同时，我们也鼓励在该新兴领域开展更多的研究。为此，本书面向两类(不一定完全区分)读者：第一类，从业者，致力于应用；第二类，理论家，致力于网络编码特性的深入研究。针对两类读者，虽然本书内容上是理论的，但我们却倾向于满足第一类应用需求的从业者。我们将采用网络编码应用人员容易理解的方式对理论进行详细论述，进而弥补当前这方面书籍不够的现状。相较于这类书籍，针对理论家的书籍则比较泛滥。除了本书以外，有关网络编码的重要理论结果还可以参考另两本优秀的概述资料：作者Yeung等的网络编码理论［144,145］和作者Fragouli、Soljanin的网络编码基础［45］原书中误写为［44］。。对于从业者，作者Fragouli、Soljanin即将出版的网络编码应用［46］原书中误写为［45］。可以作为补充。本书内容充分参考了我们的博士论文［55,90］，突出了个人开展工作的偏好。不过，我们仍然努力在正文或总结中涵盖网络编码相关的绝大部分有意义的工作，每章最后一节的备注及导读即为总结。书中难免存在疏漏，提前敬请谅解。宽泛地说，本书适用于电子工程或计算机科学背景的任何读者。我们使用的一些数学方法，比如代数算法、最优化方法等可能对这类读者而言不熟悉，所以对这些方法不作介绍，仅提供适当的相关参考书目。本书的出版要感谢许多人的帮助和支持。首先要特别感谢我们俩的博士、博士后导师——Medard教授和Koetter教授，他们是我们学习的楷模和专业导师。同时，也要感谢和我们一起进行网络编码研究的优秀团队成员： Ahmed、Chang、Deb、Effros、Eryilmaz、Fragouli、Gerla、Han、Harvey、Jaggi、Karger、Katabi、Katti、Kliewer、Langberg、Lee、Leong、Maymounkov、Pakzad、Park、Ratnakar、Ray、Shi、Traskov、Vishwanath、Viswanathan和赵方。总体上，整个网络编码团队充满欢笑、友爱，并互相激励，为此我们要感谢所有成员。还要感谢崔涛、Dikaliotis和Erez，他们对本书的初稿提出了建设性意见和评价。此外，我们还要感谢另外两个团队，没有他们就没有这本书。第一个是剑桥大学出版社的专业团队，他们伴随着本书的出版，尤其要感谢Meyler、Littlewood、Barton和Karpinski。第二个是我们的家人，感谢他们在我们研究生阶段和本书的写作过程中给予的爱与支持。Tracey HoDesmond S.Lun于2007年秋

免费在线读

第3章会话间网络编码目前为止，我们已经考虑了网络编码用于单个通信会话,也就是单播通信到单一信宿或多播通信相同信息到多个信宿。由于这类网络编码只对信宿集合内所有信宿节点均需译码的信息符号进行编码，故该类网络编码被称为会话内网络编码。对于会话内网络编码，每个节点的输出只需为其输入的随机线性组合。每个信宿只要接收足够多的关于信源过程的独立线性组合即可译码。当有多个会话共享网络时，一个简单实用的方法是为每个会话分配网络容量下的不相交子网。如果每个会话的分配子图对每一个信宿都满足最大流/最小割的条件(定理2.2和定理2.7)，则我们通过每个会话的内部信息符号间的独立编码，便可获得会话内网络编码的一个解。5.1.1节和5.2.1节讨论这样一种方法。然而，更普遍地，实现最优传输速率可能需要会话间网络编码，也就是在不同会话的信息符号间进行编码。会话间网络编码比会话内网络编码更复杂。我们必须采取策略性的网络编码以确保每个信宿能译码它所期望的源信息。注意，这里节点不能再简单地将它们的输入进行随机编码，因为信宿可能没有足够的输入容量来译码全部的随机组合的信源过程。与会话内网络编码不同的是，会话间网络编码可能一定需要非信宿节点进行译码操作。我们会在3.5.1节给出例子说明。目前，对于一般的多会话网络问题，如何确定其可行性或构造最佳的网络编码仍然是未被解决的问题。在本章，我们首先讨论一些理论的方法和结果，之后讨论次优但实用的会话间网络编码的构造和实现。3.1标量与向量线性网络编码
单会话多播中的标量线性网络编码已经在2.2节作过讨论。一般情况下的多会话，每个信宿t∈T所需求的是信息源的一个任意子集

Dt{1,2,…,r}(3.1)

对于一般情况的标量线性网络编码的定义与单会话多播情况类似，唯一的区别是每个信宿只需要译码它所需求的信息子集。我们可归纳标量线性可译性的准则如下：在单会话情况下，对于每个信宿t,转换矩阵行列式det Mt非零，该行列式为编码系数(a,f,b)的函数——这与每个信宿能译码所有源信息相对应。在会话间网络编码情况下，该准则为存在系数(a,f,b)的取值满足(1) Mt中由集合Dt内元素索引的行构成的子矩阵是非奇异的；；(2) Mt中剩余行全为零值。这对应为每个信宿能够根据自己的需求在去除无用信息干扰后，提取并译码它自己需要的源信息。一个一般网络是否具有标量线性网络编码解已经被证明(通过简化3CNF)CNF为合取范式(conjunctive normal form)。是NP完全问题［114］。该问题可以如下简化为判定一个相关代数簇是否为空的问题。令m1(a,f,b),…,mk(a,f,b)表示Mt(t∈T)中所有根据条件(2)必须赋值为零的元素。令d1(a,f,b),…,dL(a,f,b)表示根据条件(1)必须非零的子矩阵行列式。令ξ为一个新变量，I为m1(a,f,b),…,mk(a,f,b),1-ε∏Li=1di(a,f,b)生成的理想，则译码条件等同于与理想I相关的簇是否为空的条件。这可以通过计算I的Grbner基来判定。虽然该计算的复杂度不是多项式的，但有标准的数学软件进行计算。与单会话多播情况不同的是，标量线性网络编码在一般情况下不是最优的。标量编码是时不变的。上述方法确定的标量线性解不包括标量解中的分时。图3.1给出了一个网络问题的例子，该问题可以通过在不同的路由方案之间分时来解决，但无法通过标量线性网络编码方式解决。节点1和节点2是信源，节点6~9是信宿。源信息A和A′由节点1生成；源信息B和B′由节点2生成。每个信宿都要求一对不同的源信息。所示的分时解决方案在两个步进间运作。

图3.1本图经允许从文献［101］中翻印。
(a) 本网络问题能通过在不同的路由方案之间分时解决，但没有标量线性网络编码解。
(b) 一个分时路由解。

标量线性网络编码与分时均为向量线性网络编码的特例。在向量线性网络编码中，与每个源过程以及弧过程所对应的比特流被分为由有限域符号组成的向量；与某条弧相对应的向量是一个与其输入相对应的向量的线性函数，该函数可由一个矩阵确定。向量线性网络编码已在2.7节用于相关源过程的多播场景。3.2分数编码问题公式化在2.1节的基本模型和问题公式化中，是针对固定的信源速率和弧容量（假设均相等）来定义解的。对于一个给定的网络问题和一类编码/路由策略，其解要么存在要么不存在。这里给出一种更灵活的方法，用于比较多会话情况下不同种类的策略。即，根据信源/信宿的位置和需求定义网络问题，并给出一定弧容量下可达多大的传输速率。速率区域是对某类编码策略可达速率的最普遍刻画。该区域给出了不同信源速率间的权衡。若只是为比较不同种类的网络编码，一个更为简单的刻画可假设信源速率是相等的并且弧上的传输速率也相等，从而求解每个信源速率和每一条弧上的传输速率之间的最大比。特别地，我们考虑通过每条可传输n个符号组成向量的弧发送每个信源生成的k个符号组成的向量。这些符号选自某一符号集(目前在我们已经考虑过的编码里，符号集被建模成一个有限域，但是我们也可以考虑更广义的符号集例如代数的环结构)。这样一个网络问题是通过一幅图(N,A)，信源节点si∈N,i=1,…,r，一个信宿节点集TN，以及每个信宿t∈T所需求的源过程Dt{1,…,r}来定义的。为了简便起见，我们在后面将这样一个网络问题简称为一个网络。一个(k,n)分数解定义为网络节点的编码操作以及信宿的译码操作，使得每个信宿均可以完全地复制其所需的源过程的值。2.1节所述的解对应着一个k=n时的分数解。一个标量解也是分数解的一种特殊情况，其中k=n=1。一个网络在一个字符集B和一类网络编码C下的编码容量是

sup{k/n: C中存在一个字符集B内的α(k,n)分数网络编码}

3.3线性网络编码的非充分性一般地，线性网络编码不能满足多会话情况。这可以通过一个非线性编码容量为1的网络P不存在线性解来证明。图3.2描绘了网络P以及它的非线性解。网络P不存在线性解，

图3.2非线性编码容量大于线性网络编码容量的一个网络问题范例。弧上的标识给出了一个在大小为4的符号集上的非线性解。符号和-表示在整数模4环Z4中的加与减，表示按位异或，且t表示在一个2比特二元字符串中的位置置换操作。此图经允许从文献［34］中翻印。

指的是在一类比3.1节所描绘的基于有限域的向量线性编码更广义的线性编码中不存在线性解。该不存在性所考虑的线性网络编码将信源过程与弧过程同基于任意环R的包含多个元素的任意有限R模G中的元素关联起来。(环是域的一个概括，区别于环的元素不需要有乘法的逆。R模是向量空间的一个扩展，该扩展将域代替为环R。)网络P的构建基于和拟阵论的联系。通过将拟阵元素与网络里的源过程和弧过程对应，一个(非唯一的)拟阵网络可以从一个给定的拟阵构造出来，从而该拟阵的独立性与非独立性可在所构建的网络里反映出来。拟阵的环路(最小非独立集合)被反映在一个节点的输出弧过程与输入弧过程的相关性上。拟阵的基(最大独立集合)对应着全部信源过程集合，或者需求全部信源过程的信宿的输入过程。
网络P的构建基于两个拟阵网络P1和P2(如图3.4和图3.6所示)，它们分别与著名的Fano和非Fano拟阵相关联(如图3.3和图3.5所示)。对于拟阵网络P1，给定任意

图3.3Fano拟阵的几何表示。被标记的点对应拟阵的基集元素。当且仅当任何三个元素位于图中的同一条直线或一个圈上时，它们是非独立的。此图经允许从文献［35］中翻印。

图3.4一个与Fano拟阵相关联的网络。源过程a、b、c分别由信源1、2、3生成，并分别被信宿14、13、12所需求。信源与边上的标识与图3.3中Fano拟阵的元素一致。对于该网络而言，给定任意一个具有奇特征的有限域以及任意维度，均不存在一个向量线性解。此图经允许从文献［35］中翻印。

一个具有奇特征的有限域以及任意维度，均不存在一个向量线性解；对于拟阵网络P2，给定任意一个具有特征为2的有限域以及任意维度，均不存在一个向量线性解在更广义的基于G的R线性编码情况中，向量线性可解性对应着在一个更大模上的标量线性可解性。可以证明如果网络P有一个标量线性解，那么它一定有一个基于R的标量线性解，其中R是一个可以忠实地作用在模G上并有单位元I的环。在这种情况下，如果 I I ≠ 0,则P1没有基于G的标量R线性解；如果I I=0，则P2没有基于G的标量R线性解。。这种不相容性可用于构造一个无线性解，却有一个在大小为4的符号集上的非线性解的网络范例，如图3.2所示。

图3.5非Fano拟阵的几何表示。被标记的点对应拟阵的基集元素。当且仅当任何三个元素位于图中的同一条直线时，它们是非独立的。此图经允许从文献［35］中翻印。

图3.6一个与非Fano拟阵相关联的网络。源过程a、b、c分别由信源1、2、3生成，并分别被信宿集{14,15},{13,15},{12,15}所需求。信源与边上的标识与图3.5中非Fano拟阵的元素一致。对于该网络而言，给定任意一个具有特征为2的有限域以及任意维度，均不存在一个向量线性解。此图经允许从文献［35］中翻印。

对于基于有限域的向量线性编码，运用下节所述的信息论论据可以证明，这个例子的线性编码容量是10/11。具体证明在文献［34］里给出。因此，基于有限域的向量线性网络编码甚至不是渐进最优的。

3.4信息论方法对于任意一个网络如何确定它的编码容量是一个开放的问题，但是利用信息论中熵的论点，对于各种情况下的编码容量刻画或界限约束的研究已经有了进展。信息论方法把源过程和弧过程建模成随机变量(或随机变量的序列)。信源随机变量的熵可以利用源速率确定(或作为下界)，而弧随机变量的熵可以利用弧容量作为上界。一些涉及这些随机变量各种子集的联合/条件熵的其他约束关系，可以经编码相关性和译码需求推导得出。下文中，设置S={1,…,r}表示信息源集合，I(v),O(v)∈A以及S(v)S分别表示节点v的输入弧、输出弧，以及信息源的集合。如前所述，DtS表示一个信宿t所需求的信息源集合。对于一个无环网络，假设存在一个基于符号集B的(k,n)分数网络编码解。将第i个源信息(1≤i≤r)表示为随机向量Xi，Xi由k个独立均匀分布在字符集B上的随机变量组成； Yj表示在给定的分数网络编码解下每条弧j∈A所对应传输的随机向量；对应弧集A′A，简写为YA′={Yj:j∈A′}；对应信源集A′A，简写为XS′={Xi:i∈S′}。我们可得到下列熵条件：；

H(Xi)=k(3.2)
H(XS)=rk(3.3)
H(Yj)≤n,j∈A(3.4)
H(YO(v)|XS(v)，YI(v))=0,v∈N(3.5)
H(XDt|YI(t))=0,t∈T(3.6)

式(3.2)和式(3.3)表示每个信源向量Xi的熵为k(其单位经过按照符号集大小的对数比例缩放)并且是独立的。不等式(3.4)用弧容量n上界约束了每个弧向量Yj的熵。式(3.5)所表达的条件是每个节点的输出是其输入的确定函数。式(3.6)所表达的要求是每个信宿能够通过其输入信息的一个确定函数来复制它所需求的源信息。给定一个特定网络问题的式(3.2)~式(3.6)，信息不等式可被应用于达到化简等式和得到比例k/n的一个界限的目的。信息不等式是涉及一个随机变量集合中子集信息度量的不等式(熵、条件熵、互信息以及条件互信息)，这些不等式对于随机变量的任意联合分布都是成立的。直观地，信息不等式是为了使这些信息度量的取值与某些联合分布的值相一致而必须满足的约束条件。对于任意离散随机变量集合N，以及N的任意子集U、U′、U″我们有下列基本不等式：；

H(U)≥0
H(U|U′)≥0
I(U；U′)≥0
I(U；U′|U″)≥0

基本不等式和所有可由基本不等式引申出来的不等式被称为Shannon型信息不等式。对于4个或以上的随机变量，存在无法由基本不等式推导而得的不等式，其被称为非Shannon型信息不等式。一个包含4个随机变量X1、X2、X3、X4的非Shannon型信息不等式例子为

2I(X3； X4)≤I(X1； X2) I(X1； X3； X4) 3I(X3； X4|X1) I(X3； X4|X2)(3.7)

一般来讲，Shannon型不等式不足以计算编码容量。这个结论已在文献［35］中通过一个由Vmos拟阵(参见文献［108］)构造出的网络问题证明。在这个网络问题中利用非Shannon型不等式(3.7)可以得到一个比只用Shannon型不等式所推导出的任何界都要紧的关于编码容量的界。信息论方法给出了一个确定型网络编码在一个具有弧容量ck(k∈A)的无环网络上的速率区域的隐性刻画。我们首先介绍一些定义。令N表示一个随机变量集合{Xi:i∈S}∪{Yj:j∈A}。令HN表示一个(2|N|-1)维欧式空间，其坐标与N的2|N|-1个非空子集相对应。对一个向量g∈HN，如果存在N中随机变量的一种联合分布，使得g中的每一个组成部分均与其所对应的随机变量子集的熵相等，则称其可用熵表示定义区域

Γ*N=(g ∈ HN: g可用熵表示)

这个区域本质地总结了包含N中变量的所有可能的信息不等式所带来的影响(我们目前并没有一个对这个区域的完整刻画，或者等价地，也没有一个对所有可能的信息不等式的完整刻画)。我们定义HN中如下的区域：；

C1=h∈HN:H(XS)=∑i∈SH(Xi)
C2={h∈HN:H(YO(v)|XS(v),YI(v))=0,v∈N}
C3={h∈HN:H(Yj)≤cj,j∈A}
C4={h∈HN:H(XDt|YI(t))=0,t∈T}

定理3.1原文笔误为3.9，此处已做修改。对于任意一个多路会话下的无环网络，其容量区域为

R=Λ(projXS(conv(Γ*N∩C12)C3∩C4))

这里对任意区域CHN,

Λ(C)={h∈HN:0≤h≤h′,h′∈C}

projXS(C)={hXS:h∈C}是C在对应信源熵的坐标hXi上的射影，conv(·)表示凸包操作，上画线表示闭，C12=C1∩C2。证明该定理的证明出自文献［142］。对于有环网络，我们还需要考虑时延和传输因果性的约束条件。可以通过对每个弧过程j，研究一个与时隙τ=1,…,T相对应的随机变量序列Y(1)j,…,Y(T)j来实现，从而可以将式(3.5)改为

H(Y(1)O(v),…,Y(τ)O(v)|XS(v),Y(1)I(v),…,Y(τ-1)O(v))=0，v∈N

3.4.1多路单播网络多会话网络编码问题的一种特殊情况是多路单播，也就是说，多路通信会话中的各路均由一个信源和一个信宿组成。对于有向有线网络，任何一个多路会话网络编码问题均可被转化为一个多路单播问题，而并不改变该问题的可解性或线性可解性。因此，仅就容量问题而言，研究多路单播网络便足够了。该网络变换步骤运用了图3.7所示的装置。假设t1和t2是任意一个有向网络里的信宿节点，且同时需要接收信源X。那么如图所示，我们可以增加5个额外的节点，其中节点1是一个额外的被节点5所需求的信源，而节点4需求信源X。在这个合成网络里，为了满足新的信宿4和5的需求，t1和t2虽然不是信宿，但是依然必须译码出X。

图3.7将任意多会话网络编码问题转化为一个多路单播问题的装置。此图经允许从文献［35］中翻印。

对于另一类无向有线网络模型，其每条弧容量可以在信息流的两个方向上任意分割，文献［87］推测网络编码并不会增加此时多路单播会话的吞吐量。不过，由下节内容可知，该推测并不适用于无向无线网络。3.5构造方法会话间网络编码的复杂性为考虑可实际构造并实现的次优网络编码带来了动机。许多构造方法都是基于对采取实用的按位异或编码的简单示例网络的扩展。3.5.1有线网络中的成对异或编码我们已经在第1章出现过的图3.8中给出了一个简单的有线网络的示例，在这个示例中两个单播对话间的按位异或编码使得每个会话可以同时达到吞吐量加倍。这个示例可以通过“有毒解毒”解释：经过编码的信息包b1b2称为一个有毒信息包，因为它本身对任何一个信宿均是没有用的；每个信宿为了恢复其自身会话的信息包，需要一个来自另一个会话信源的解毒信息包。为了扩展这个例子，将每条弧用一个路径段代替。正如图3.9所示，解毒段可以在中间节点之间而不必直接从信源到信宿。我们也可假设从每个信源发出的是一个由多个信息包组成的信息流而不只是一个单一的信息包。对于多过两个的单播会话，一个较易处理的方法是只考虑成对单播间的异或编码。