网络编码

网络编码是一种通过中继节点对接收到的信息进行编码来达到提高多播网络容量的技术。Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung在2000年首次提出网络编码的概念。

在右图的网络拓扑中，s节点试图向t_{1}, t_{2}组播两条消息x,y。设每条消息占用的带宽为1，每个节点之间的网络带宽也为1，那么每个节点之间只能同时传输一条消息。线路cd上会需要同时传输x,y，这在一般的传输方案中是行不通的，所以需要网络编码在c处将x,y异或，合成一条消息然后发送。

• 在传统的数据传输技术中，中继节点只负责数据的存储转发，而基于网络编码技术的网络的中继节点在具备传统中继功能的基础上，会根据网络编码规则将接收到的信息进行线性或非线性处理再进行传播，这种做法最直观的优势是减少了传输次数。利用图论中最大流最小割原理论证了网络编码可以达到网络最大信息流。
• 网络编码的相关领域：信息论、图论、编码理论

线性网络编码
假设网络是有向的，执行线性网络编码时每个节点收到所有连入线路的数据后，再执行编码，然后把数据从连出线路发出。新的数据包括执行线性编码所用的系数以及合成后的数据。

例如组播源发送三条封包，p_{1}=1，p_{2}=2，p_{3}=3。封包经过一系列的中间节点，目标节点收到的封包是((5,8,1),24),((2,3,7),29),((9,6,5),36)。目标节点对下列矩阵求解，可得p_{1},p_{2},p_{3}的值。

\begin{bmatrix}
24\\
29\\
36
\end{bmatrix}
=
\begin{bmatrix}
5 & 8 & 1\\
2 & 3 & 7\\
9 & 6 & 5
\end{bmatrix}
\begin{bmatrix}
p_{1}\\
p_{2}\\
p_{3}
\end{bmatrix}
\Rightarrow
\begin{cases}
24=5p_{1}+8p_{2}+p_{3} & \\
29=2p_{1}+3p_{2}+7p_{3} & \\
36=9p_{1}+6p_{2}+5p_{3} &
\end{cases}
或\begin{bmatrix}
p_{1}\\
p_{2}\\
p_{3}
\end{bmatrix}
=
\begin{bmatrix}
5 & 8 & 1\\
2 & 3 & 7\\
9 & 6 & 5
\end{bmatrix}^{-1}
\begin{bmatrix}
24\\
29\\
36
\end{bmatrix}

随机线性网络编码
随机线性网络编码可以取得更好的组播传输速率，较为实用。在实际网络中，节点会将来自连入线路的封包缓存起来，当节点需要发送封包时再将缓存的封包执行网络编码，然后发出。

例如节点A有2个上游节点X,Y，X向A发送了封包((2,2,1),2x_{1}+2x_{2}+x_{3})(2x_{1}+2x_{2}+x_{3}是数据体，（2,2,1）是对数据体执行线性编码时所用的系数）,Y向A发送了封包((1,5,4),x_{1}+5x_{2}+4x_{3})。当A需要发送数据时，便把缓存的这两个封包取出来，随机选择2个系数（如2和1），获得新的数据体(2x_{1}+2x_{2}+x_{3}) \times 2+(x_{1}+5x_{2}+4x_{3}) \times 1 =5x_{1}+9x_{2}+6x_{3}和新的合成系数(2,2,1)\times 2+(1,5,4) \times 1 =(5,9,6)。所以A就把合成后的数据体5x_{1}+9x_{2}+6x_{3}连同合成系数(5,9,6)，向下游节点发送出去。

参考文献