1.2　网络编码的优势和劣势

1.2.1　网络编码的优势

1.2.1.1　提高网络吞吐量

提高网络吞吐量是网络编码较显著的优点之一。具体地，网络编码可以提高多播（Multicast）、单播（Unicast）和广播（Broadcast）方式[56]的网络吞吐量。多播指一个信源节点发送数据给多个信宿节点，记为One-to-Many。多播的两个特例分别是单播和广播：当多播中信宿节点的个数为1时，多播退化为单播，记为One-to-One；当多播中信宿节点的个数等于网络中除信源外所有节点的个数时，多播即广播，记为One-to-All。

1．提高多播方式的网络吞吐量

在蝶形网络（见图1-1-1）中，信源节点S采用多播方式同时发送2个数据到信宿节点R1和R2，由1.1.1节的分析可知，采用网络编码可以达到网络的多播容量（2bits），而采用多播路由[57]则无法达到。可见，网络编码可以提高多播方式的网络吞吐量。

2．提高单播方式的网络吞吐量

如图1-2-1（a）所示，考虑到具有单位容量、无时延的有向无环网络中的“单位容量”，通信目标是信源节点s1传输数据a到信宿节点R1，同时信源节点s2传输数据b到信宿节点R2。

若采用路由方式，由于链路UV是瓶颈，故一次仅能传输1 bit数据：若链路UV传输数据a，如图1-2-1（b）所示，则信源节点s1可以传输数据a到信宿节点R1，但信源节点s2无法同时传输数据b到信宿节点R2；若链路UV传输数据b，如图1-2-1（c）所示，则信源节点s2可以传输数据b到信宿节点R2，但信源节点s1无法同时发送数据a到信宿节点R1。可见，采用路由不能同时达到通信目标。

若采用网络编码方式，如图1-2-1（d）所示，则可以在中间节点U进行线性编码（此处为a⊕b），信宿节点R1可以收到数据b并译码出数据a［利用b⊕ (a⊕b)译码出a］，信宿节点R2可以收到数据a并译码出数据b［利用a⊕ (a⊕b)译码出b］，从而同时达到通信目标。

上述通信目标中存在两对单播，属于多源网络编码[4,5]问题，常采用可达速率区域（Achievable Rate Region）[17]作为其性能指标。若采用路由，两对单播可达速率区域如图1-2-2（a）所示；若采用网络编码，两对单播可达速率区域如图1-2-2（b）所示，可明显看到采用网络编码的性能优势。

3．提高广播方式的网络吞吐量

广播方式的典型实例之一是无线网络，如图1-2-3（a）所示，假设信源节点s1和s2的无线传输范围均仅能覆盖中继节点R，通信目标是无线网络中信源节点s1与s2通过中继节点R交换数据a和b。

若采用路由方式，如图1-2-3（b）所示，为避免无线传输中同时接入时的冲突，信源节点s1和s2不能同时传输数据给中继节点R，只能采用分次传输的方法：①信源节点s1通过广播方式传输数据a给中继节点R；②信源节点s2通过广播方式传输数据b给中继节点R；③中继节点R通过广播方式传输数据a给s2；④中继节点R通过广播方式传输数据b给s1。这样就实现了信源节点s1与s2间的数据互换，总共需要进行4次广播传输。

若采用网络编码方式，如图1-2-3（c）所示，则仅需进行3次广播传输，其中前两步与上述采用路由方式一致，第三步则采用网络编码方式。该方式的具体步骤是：①信源节点s1通过广播方式传输数据a给中继节点R；②信源节点s2通过广播方式传输数据b给节点R；③中继节点R对数据a与数据b进行线性编码（此处为a⊕b），然后将其通过广播方式传输给信源节点s1和s2，信源节点s1可以利用已有的数据a和收到的a⊕b译码出数据b［利用a⊕ (a⊕b)译码出b］，信源节点s2可以利用已有的数据b和收到的a⊕b译码出数据a［利用b⊕ (a⊕b)译码出a］，从而达到通信目标。

由于采用网络编码减少了1次传输次数，因此提高了网络带宽利用率，相当于提升了网络吞吐量。在无线网络中，由于减少了传输次数，因此相应地减少了无线传输的能量损耗，这对于能耗较敏感的网络（如无线传感器网络）具有较大的实际意义。

1.2.1.2　均衡网络流量

如图1-2-4（a）所示的有向无环网络，假设每条链路的流量为2 bits，信源节点s采用多播方式将数据a和b传输给信宿节点R1、R2和R3。

若采用多播路由[57]方式，信源节点s通过构建多播路由树[57]，如图1-2-4（b）所示，将数据a和数据b传输给信宿节点R1、R2和R3，其中，多播路由树中每条链路的流量均为2 bits。这样，流量主要集中在9条链路中的5条（sU、UR1、UR2、sW和WR3）上，其余的链路均未被利用。

若采用网络编码方式，如图1-2-4（c）所示，信源节点s可以将数据a和数据b传输给信宿节点R1、R2和R3，其中除信宿节点R2直接收到数据a和数据b外，信宿节点R1收到数据a和(a⊕b)并译码出数据b，信宿节点R3收到数据b和(a⊕b)并译码出数据a。在采用网络编码的网络中，所有的9条链路都得到了利用，且每条链路的流量均为1bit。这样，流量被均匀地分配到所有链路，从而实现了网络流量均衡。

1.2.1.3　提高带宽利用率

网络编码可以提高带宽利用率。若采用多播路由方式，如图1-2-4（b）所示，信源节点s将数据a和数据b传输给3个信宿节点，总共使用了10 bits（因为使用了多播路由树中的5条链路，每条链路使用2 bits）。若采用网络编码方式，如图1-2-4（c）所示，信源节点s将数据a和数据b传输给3个信宿节点，总共仅使用了9 bits（因为使用了9条链路，所以每条链路仅使用1 bit）。由此可见，达到同样的通信目标，采用网络编码方式所使用的带宽要小于采用多播路由方式，这就意味着采用网络编码方式可以提高带宽利用率。

1.2.1.4　提高可靠性

网络编码不仅可以提高有效性（提高网络吞吐量和提高带宽利用率），还可提高可靠性。例如，在分布式存储（Distributed Storage）中，如图1-2-5（a）所示，数据源s的数据a和数据b分别存于节点A和B，节点U为备份节点（存储数据a或数据b）。不妨假设所有节点的存储能力相同，若新节点C需得到数据源s的所有数据，则需要分别从节点A和B来获得。若节点A或B出错，则可以由备份节点U来帮助恢复。

若未采用网络编码，则可能存在无法恢复的情况，因为备份节点U仅能存储数据a或数据b。不妨假设备份节点U存储数据a，此时若节点B出错（或者离开网络），则新节点C就无法借助备份节点U获得所有数据，因为无法从备份节点U获得数据b。同理，若备份节点U存储数据b，则当节点A出错时，新节点C就无法获得数据a。

若采用网络编码，则可避免上述问题。因为备份节点可存储数据a⊕b。若节点A出错，如图1-2-5（b）所示，新节点C可以从备份节点U中获得数据a⊕b，然后通过译码得到数据a，从而获得所有数据。同理，若节点B出错，如图1-2-5（c）所示，新节点可以从备份节点U获得数据a⊕b，然后通过译码得到数据b，从而获得所有数据。

可见，网络编码可以提高分布式存储的可靠性。

1.2.1.5　降低问题复杂性

采用网络编码可降低问题的复杂性[51,56,58,59]，主要包含两类问题[59]：最大吞吐量问题和最小代价问题。

对于最大吞吐量问题[51,56,58]，采用网络编码可降低基于单多播（Single Multicast）、多多播（Multiple Multicast）、覆盖层多播（Overlay Multicast）吞吐量最大化问题的复杂性。以单多播的最大吞吐量问题为例，若未采用网络编码，求单多播吞吐量最大化的问题等价于Steiner树装箱（Steiner Tree Packing）问题[60]，属于NP完全（NP-Complete）问题；若采用网络编码，可将上述问题转化为线性规划问题，并在多项式时间内加以解决[51,58]。可见，采用网络编码可以有效降低问题复杂性，使解决问题的效率得到本质上的提升，具有较大应用价值。

网络编码能有效降低问题复杂性，比网络编码提升网络吞吐量更具理论意义和应用价值。因为在多数情况下，网络编码提升网络吞吐量的优势并不明显，这一结论得到理论研究和仿真的验证，如在大规模随机网络情况下编码优势基本保持为1[51,56]。造成这一状况的主要原因之一是网络编码提升网络吞吐量的性能与网络拓扑存在较大关系[51,52]。

类似地，对于最小代价问题[59,61,62]，以单多播的最小代价问题为例，采用网络编码可以将最小代价问题转变为线性规划问题，从而降低问题的复杂性。

1.2.1.6　提升保密性

网络编码中所采用的任何一种编码方式均可看作一种加密编码，由此角度看，网络编码可提升保密性。例如，网络编码可以抵抗搭线窃听（Wiretapping）[63]。如在蝶形网络中［见图1-1-1（a）］，若采用路由［见图1-1-1（b）或图1-1-1（c）］，在节点V进行搭线窃听即可获得原始数据；若采用网络编码［见图1-1-1（d）］，由于节点V收到的是经异或操作后的数据，因此仅在节点V进行搭线窃听是无法获得原始数据的。从这个角度看，随机网络编码是一种天然的加密方法[64]，因为每个节点收到的均是线性编码后的数据。