1.1 蝴蝶网络

图1-1（a）是典型的蝴蝶网络，在不少文献中用于描述网络编码的原理，它是一个有向无环单源多播网络，其中节点S是源点，T1和T2是宿点，节点2、3、4、5为中间节点。设每条链路的信道容量均为1，即每条链路在单位时间内最多只能传输一个字符，而源点S欲通过网络多播信息至两个宿点T1、T2。若采用路由传输技术，因为节点4至节点5的信道是数据传输的瓶颈，在一个时间单元内，源点最多只能多播一个1.5个字符至两个宿点，若采用网络编码技术，则可以多播2个字符。

图1-1 蝴蝶网络及路由传输方式

采用路由传输方式，则数据传输方式如图1-1（b）和图1-1（c）所示。在第1个时间单元内，数据传输方式如下。

（1）S把字符a传输至输出信道<S,2>，把字符b传输至输出信道<S,3>。

（2）节点2从信道<S,2>上接收到字符a后，把它分别转发至输出信道<2, T1>和<2,4>；节点3从信道<S,3>上接收到字符 b 后，把它转发至输出信道<3,4>和<3, T2>。

（3）节点4尽管收到了两个字符，它们分别来自于信道<2,4>和<3,4>，由于信道<4,5>是数据传输的瓶颈，它在一个时间单元内只能传输一个字符。不妨令节点4转发的字符为b，由节点5接收，节点5把接收到的字符从其输出信道分别转发出去，从而T1收到了字符a和b，而T2只收到字符b。因此，以一个时间单元为传输周期，则源点只能成功地多播1个字符至每一个宿点，如图1-1（b）所示。

若以两个时间单元为一个传输周期，第1个时间单元的传输情况如图1-1（b）所示，而第2个时间单位的传输情况如图1-1（c）所示，从而在2个时间单元内，源点成功地多播了3个字符（a, b, c）至每一个宿点，则平均每个时间单元实现了多播1.5个字符。

若采用网络编码，即中间节点允许把接收到的信息进行编码后再转发，则能在每个时间单元内实现多播2个字符。在一个时间单元内各信道的传输情况如图1-2所示，传输方式如下。

图1-2 蝴蝶网络中采用网络编码数据传输方式

（1）S把字符a传输至输出信道<S,2>，把字符b传输至输出信道<S,3>。

（2）节点2从信道<S,2>上接收到字符a后，把它分别转发至输出信道<2, T1>和<2,4>；节点3从信道<S,3>上接收到字符 b 后，把它转发至输出信道<3,4>和<3, T2>。

（3）节点4分别从信道<2,4>和<3,4>上接收字符a和字符b后，对接收到的信息进行编码，即做异或运算：c=a⊕b，然后把编码运算的结果c传输至输出信道<4,5>。

（4）节点5从信道<4,5>收到信息c后，把它分别传输至信道<5, T1>和<5, T2>。

（5）宿点 T1分别从信道<2, T1>和<5, T1>上收到信息 a 和 c 后，做异或运算a⊕c，得到b，从而宿点T1接收到了源点播出的信息a和b；同理，宿点T2分别从信道<3, T2>和<5, T2>上收到信息b和c后，做异或运算b⊕c，得到a，从而宿点T2也接收到了源点播出的信息a和b。