1.1.1　网络编码快速入门——蝶形网络

初识网络编码，可从了解其优势入手。网络编码的优势可通过与路由（Routing）的比较加以说明，路由采用存储—转发（Store-and-Forward）的方式，网络编码则采用存储—编译码—转发的方式。网络编码与路由的性能比较可通过蝶形网络（Butterfly Network）[3,19]形象地说明（见图1-1-1）：在网络节点允许采用网络编码后可达到网络的多播容量（Multicast Capacity），而采用路由却不一定能达到。容量是指理论上吞吐量（Throughput）的最大值。

图1-1-1（a）所示的有向无环网络（Directed Acyclic Network）是典型的蝶形网络，假设其链路（Link）具有单位容量且无时延，考虑信宿节点R1和R2能否同时收到信源节点s发出的数据a和b（共2 bits）。

图1-1-1　蝶形网络中网络编码与路由的性能比较

若采用路由方式，由于链路UV是该网络传输的瓶颈，只能传送1bit（数据a或b），图1-1-1（b）中的链路UV传送数据b，因此信宿节点R1可以收到数据a和b（共2bits），而信宿节点R2只能收到数据b（1bit），每个信宿节点的平均吞吐量为(2+1)bits÷2节点=1.5 bits/节点；类似地，图1-1-1（c）中的链路UV传送数据a，因此信宿节点R2可以收到数据a和b（共2bits），而信宿节点R1只能收到数据a（1bit），每个信宿节点的平均吞吐量仍为1.5bits/ 节点。

若采用网络编码方式，图1-1-1（d）中的链路UV上传送数据a与b的线性组合（此处为异或操作），信宿节点R1可以收到数据a并译码出数据b［利用a⊕ (a⊕b)译码出b］，相当于收到2bits，信宿节点R2可以收到数据b并译码出数据a［利用b⊕ (a⊕b)译码出a］，相当于收到2bits。这样，每个信宿节点的平均吞吐量为(2+2)bits÷2节点=2bits/节点（大于1.5bits/节点）。可见，在采用网络编码后所达到的吞吐量可严格大于采用路由后所达到的吞吐量。

上述蝶形网络的例子直观地说明了网络编码在本质上不同于路由的新性能：网络编码允许网络所有节点参与编译码，可以达到网络的多播容量，而仅采用路由可能达不到。

可采用编码优势（Coding Advantage，CA）[48-50]定量反映网络编码吞吐量性能优于路由的程度，其定义为采用网络编码时的最大吞吐量与未采用网络编码时的最大吞吐量之比。例如，蝶形网络（见图1-1-1）的编码优势为2/1.5≈1.33（严格大于1）。当编码优势严格大于1时，说明网络编码可达到的吞吐量严格大于路由可达到的吞吐量，或者简单地讲，网络编码的性能可严格优于路由的性能。正是因为网络编码与路由存在本质差别，所以有必要深入研究网络编码理论。

通常，网络编码的优势能否得到发挥与网络拓扑有较直接关系[51,52]。蝶形网络拓扑较为特殊，采用网络编码时的吞吐量“严格大于”采用路由时的吞吐量。在一般的网络拓扑中，并不总能保证采用网络编码的吞吐量严格大于采用路由的吞吐量。2013年Yin等人[52]从图子式（Graph Minor）[53,54]的角度研究了网络编码性能与网络拓扑之间的本质联系，指出若网络拓扑的图子式含有4个节点的完全图K4时，则网络编码可以发挥作用，即采用网络编码可严格优于采用路由。

通过蝶形网络初识网络编码的概念之后，若希望从理论上进一步快速理解网络编码，建议阅读经典英文教材Network Coding Theory[3]2.3节之前的内容（含2.3节）。建议阅读后达到的目标是：理解两个重要概念——局部编码内核（Local Encoding Kernel）和全局编码内核（Global Encoding Kernel）及其关系，重点理解线性网络编码（Linear Network Coding）的四个性质——线性多播（Linear Multicast，LM）、线性广播（Linear Broadcast，LB）、线性扩散（Linear Dispersion，LD）和一般线性网络码（Generic Linear Network Code，GLNC）的定义和物理意义，以及它们在线性无关性上具有逐级增强的特性。对这四个性质及其关系的理解有助于了解网络编码可优于路由的本质原因，从而进一步从理论角度深入认识网络编码。

要想了解网络编码相关领域的最新发展动态，可及时关注相关的重要国际国内会议、著名国内外高校和研究机构主页。对于会议方面，除著名的网络通信计算机会议［如SIGCOMM（Special Interest Group on Data Communication）、INFOCOM（Internation Conference on Computer Communications）等］外，与网络编码方向直接相关的国际会议是于2005年开始举办的NetCod（Workshop on Network Coding,Theory,and Applications），该会议于2010年起更名为International Symposium on Network Coding[15]，会议缩写名NetCod仍保持不变。还有与信息论直接相关的会议，如IEEE ISIT（International Symposium on Information Theory）和IEEE ITW（Information Theory Workshop）等。于2010年在香港中文大学成立的网络编码研究所（Institute of Network Coding，INC），其主页提供网络编码相关领域研究的最新信息和资料，如各种重要会议信息、学术讲座及音视频资料等，是学习和跟踪最前沿网络编码的直接途径。2011年11月INC在香港中文大学深圳研究院成立了第一个分支机构INC（SZ）——网络编码研究所（深圳），为研究网络编码的内地学者提供了更多机会。